综合练习及参考答案Word格式.docx
《综合练习及参考答案Word格式.docx》由会员分享，可在线阅读，更多相关《综合练习及参考答案Word格式.docx（53页珍藏版）》请在冰点文库上搜索。
2．对下图：
（1）写出其邻接矩阵。
（2分）
（2）按Kruskal算法求其最小生成树；
并写出相应的边集数组。
（4分）
3．请画出后序和中序序列相同的二叉树的所有形态。
（3分）
4．散列函数为H（k）=k%7，散列表的地址从0到6，用线性探查法解决冲突，建立散列表ht。
给定关键字序列
{32，13，49，55，22，38，21}
要求：
（1）构造散列表（只画出表，不写算法）；
（5分）
（2）求出平均查找长度。
5．用直接选择排序方法对下列关键字进行排序，请写出每一趟排序的结果。
（6分）
68452090151050
五、算法设计（在下列算法的横线上填上适当的表达式或语句或运算符。
每空3分，共30分）
1．在带头结点的head单链表的结点a之后插入新元素x
structnode
{elemtypedata;
node*next;
};
voidlkinsert（node*head,elemtypex）
{node*s,*p;
s=──────────────────────;
s->
data=_____;
p=head->
next;
while（p!
=NULL）&
&
（p->
data!
=a）
___________________;
if（p==NULL）
cout<
<
“不存在结点a”;
else{__________________________;
__________________________;
}
2．快速排序
voidqksort（intR[],intp,intq）//按递增序对R[p]~R[q]进行快速排序
{inti=p,j=q;
R[0]=R[i];
//R[0]作临时单元
while（_______）
{
while（j>
i）&
（R[j]____R[0]）j--;
if（j>
i）
{R[i]=R[j];
i++;
while（i<
j）&
（R[i]____R[0]）i++;
if（i<
j）{R[j]=R[i];
j--;
}
R[i]=_____;
if（j>
p）qksort（R,p,j）;
if（i<
q）;
《数据结构》（01111、01211）作业题
（二）
每小题1分，共10分）
（）1.数据的存贮结构独立于计算机。
（）2.线性表简称为“顺序表”。
（）3.对数据的任何运算都不能改变数据原有的结构特性。
（）4.从循环单链表的任一结点出发，可以找到表中所有结点。
（）5.栈是一种先进先出的线性表。
（）6.链表的主要缺点是不能随机访问。
（）7.二叉树是树的特殊形式。
（）8.图可以没有边，但不能没有顶点。
（）9.冒泡排序算法是稳定的排序。
（）10.散列法是一种对关键字进行比较的查找方法。
1．对数据所施加的运算可分为两类，即型和型。
2．将插入限定在表的一端，而删除限定在表的另一端进行的线性表称为；
允许插入的一端称为。
3．二叉树的叶结点数n0与二度结点数n2的关系是。
4．对于顺序循环队列Q[M]，下标从0到M－1，头尾指针分别用F和R表示，则队空条件是。
5．n个顶点的无向完全图具有条边。
6．拓扑排序的操作对象是。
7．快速排序的最坏情况是初始序列为正序和反序，其时间复杂度为。
8．希尔排序是属于排序的改进方法。
三、单选题（本题的每一备选答案中，只有一个是正确的，请把你认为正确的答案的题号填入题干的括号内，多选不给分，每小题3分，共15分）
1．栈和队列都是（）
（1）顺序存贮的线性结构
（2）限制存取点的线性结构
（3）链接存贮的线性结构（4）限制存取点的非线性结构
2．与线性表的链接存贮不相符合的特性是（）
（1）便于插、删运算
（2）存贮空间动态分配
（3）需要连续的存贮空间（4）只能顺序查找
3．设二叉树的根为第一层，则第i层上的结点数最多有（）
（1）２i
（2）２i+1（3）２i-１（4）２i-1
4．直接选择排序的时间复杂度为（）
（1）O（n）
（2）O（n㏒2n）（3）O（n2）（4）O（㏒2n）
5．给定下列有向图，从顶点V1出发，其深度优先搜索序列为（）
（1）12534
（2）12435（3）14325（4）12345
四、应用题（25分）
1．画出下列二叉树所对应的森林。
2．对于下边有向图
（1）画出其邻接表（4分）
（2）写出三种不同的拓扑序列（3分）
3．请画出先序与中序序列相同的二叉树的所有形态。
4．给定关键字序列{19，14，27，68，84，23，1，20，55，12，10，79}，散列函数为H[K]=K%11散列表的地址从0到10，用外链法处理冲突，散列地址为d的同义词均挂在以ht[d]为头指针的单链表中。
（1）请画出其散列表（不写算法）；
（2）求出成功的平均查找长度。
5．对下列关键字序列进行快速排序，请写出第一趟排序结果，并标识出在第一趟排序过程中数据交换的情况。
359215191080100
第一趟排序结果：
五、算法设计（在下列算法的横线内填上适当的语句或表达式。
每空3分，共30分）
1．直接插入排序
voidinsertsort（intR[]）
//按递增序对R[1]~R[n]进行直接插入排序
{inti,j;
for（i=2;
i<
=;
i++）
{R[0]=R[i];
//设定R[0]为监视哨
j=；
while（R[0]R[j]）
{;
j--;
R[j+1]=;
//插入第i个记录
2．先序遍历二叉树
设二叉树用二叉链表表示，以t为根指针，二叉链表结点的类型为node；
栈s的元素类型为指向node的指针类型,栈容量M足够大。
先序遍历的非递归算法如下：
{chardata;
node*lc,*rc;
voidpreorder（node*t）
{node*s[M]，*p=______;
inttop=-1；
//置栈空;
do
{while（p!
=NULL）
s[++top]=;
;
if（top!
=-１）
｛p=s[top--]；
；
}
}while（（top!
=-1）||（p!
=NULL））;
《数据结构》（01111、01211）作业题（三）
每题1分，共10分）
（）1.数据是计算机加工处理的对象。
（）2.数据结构的概念包括数据的逻辑结构、数据在计算机中的存储方式和数据的运算三个方面。
（）3.线性表是由n≥0个相同类型元素组成的有限序列。
（）4.栈是一种后进先出的线性表。
（）5.从循环链表的某一结点出发，只能找到它的后继结点，不能找到它的前趋结点。
（）6.单链表设置头结点的目的是为了简化运算。
（）7.深度为h的二叉树最多有2h-1个结点。
（）8.图G由两个集合V（G）和E（G）所组成，其中顶点集V（G）可以为空集，而边集E（G）不能为空。
（）9.散列法是一种对关键字进行运算的查找方法和存储方法。
（）10.快速排序在任何情况下，都是速度最快的一种排序方法。
1．数据元素之间存在的相互关系称为。
2．数据结构从逻辑上分为结构和结构。
3．线性表的顺序存储结构称为。
4．所有插入在表的一端进行，而所有删除在表的另一端进行的线性表称为。
5．深度为h的二叉树，最少有个结点。
6．折半查找要求待查表为表。
7．n个记录按其关键字大小递增或递减的次序排列起来的过程称为
8．存储数据的时侯，不仅要存储数据元素的，还要存储元素之间的相互。
三、选择题（本题的每一备选答案中，只有一个是正确的，请把你认为正确的答案的题号填入题干的括号内，多选不给分，每小题3分，共15分）
1．与线性表的链接存储相符的特性是（）
（1）插入和删除操作灵活
（2）需要连续存储空间
（3）便于随机访问（4）存储密度大
2．若进队序列为1，2，3，4，则出队序列是（）
（1）4，3，2，1
（2）1，2，3，4
（3）1，3，2，4（4）3，2，4，1
3．已知广义表A=（（a,b）,（c,d））,则head（A）等于（）
（1）（a,b）
（2）（（a,b））（3）a,b（4）a
4．n个结点的二叉树，若用二叉链表作为存贮结构，则非空闲的左、右孩子链域为（）
（1）n
（2）2n（3）n-1（4）n+1
5．6个顶点的连通图的深度优先生成树，其边数为（）
（1）6
（2）5（3）7（4）4
四、应用题（共25分）
1．已知二叉树的中序序列为DBHEIAFJCKG，先序序列为ABDEHICFJGK，请画出该二叉树。
2．对于给定的5个实数W={8，5，13，2，6}，试构造Huffman树；
并求出该树的最小带权路径长度。
（7分）
3．对于下边的图G
（1）画出其邻接表（4分）。
（2）写出从V1出发的深度优先搜索序列（3分）。
4．给定有序表D={15，17，18，22，35，51，60，88，93}，用折半查找法在D中查找18。
现要求：
（1）试用图示法表示查找过程；
（2）求出其成功的平均查找长度ASL。
1．直接选择排序
voidselectsort（intR[]）
//按递增序对R[0]~R[n-1]进行直接选择排序
{inti,j,k,temp;
for（i=0;
i<
=;
i++）
{k=i;
for（j=;
j<
=n-1;
j++）
if（R[j]R[k]）
k=j;
if（）
{temp=R[i];
R[i]=;
R[k]=temp;
2．中序遍历二叉树
栈s的元素类型为指向node的指针类型,栈容量m足够大。
中序遍历的非递归算法如下：
structnode
voidpreorder（node*t）
{node*s[m]，*p=t;
inttop=-1；
//置栈空
{s[++top]=;
;
；
}while（（———————）||（p!
《数据结构》（01111、01211）作业题（四）
（）1.数据的存储结构是数据的逻辑结构的存储映象，不仅要存储数据元素的值，还要存储元素之间的相互关系。
（）2.算法是对解题方法和步骤的描述。
（）3.线性表简称为“顺序表”。
（）4.队列是一种先进后出的线性表。
（）5.从循环链表的某一结点出发，既能找到它的后继结点，又能找到它
的前趋结点。
（）6.单链表设置头结点的目的是为了把空表与非空表、第一个结点处与非第一个结点处的运算统一起来。
（）8.图G由两个集合V（G）和E（G）所组成，其中顶点集V（G）和边集E（G）都可以为空集。
（）9.散列法既是一种查找方法，又是一种存储方法。
（）10.对快速排序来说，初始序列为正序和反序，都是最坏情况。
3．线性表的链接存储结构简称为。
4．所有插入和删除都限定在表的同一端进行的线性表称为。
5．二叉树的第i层上，最多有个结点。
6．树所对应的二叉树，其根结点的子树一定为空。
7．顶点表示活动、有向边表示活动间优先关系的网称为。
8．折半查找的前提条件是要求待查表为表。
9．将n个记录按其关键字大小递增或递减的次序排列起来的过程称为。
1．线性表的顺序存储不相符的特性是（）
（1）插入和删除操作灵活
（2）需要连续存储空间
（3）便于随机访问（4）存储密度大
2．若进队序列为1，2，3，则出队序列是（）
（1）3，2，1
（2）1，2，3（3）1，3，2（4）3，2，1
3．已知广义表A=（（a,b）,（c,d））,则head（A）等于（）
5．具有8个顶点的连通图的深度优先生成树，其边数为（）
（1）8
（2）9（3）7（4）6
1．已知二叉树的中序序列为CDBAEGF，后序序列为DCBGFEA，请画出该二叉树。
并求出每个叶子结点的哈夫曼编码。
3．对下图：
（2）求出从顶点V5出发的广度优先搜索遍历序列（4分）
4．给定无序表D={18，88，15，93，35，51，60，17，22}，用二叉排序树查找法在D中查找51。
（1）试画出二叉排序树，并画出查找过程；
五、算法设计（在下列算法的横线内填上适当的语句或表达式或运算符。
1．二分插入排序
voidinsertsort（intR[]）
//按递增序对R[1]~R[n]进行二分插入排序
{inti,j,left,right,mid;
i++）
left=1;
right=；
while（leftright）
if（R[0]<
R[mid]）right=mid-1;
elseleft=mid+1;
for（j=i-1;
j>
=left;
j--）
R[j+1]=;
//元素后移
R[left]=temp;
}}
2．层次遍历二叉树
队列s的元素类型为指向node的指针类型,队列容量m足够大。
层次遍历二叉树的算法如下：
{node*s[m]，*p=;
intf=r=1；
//设置队列头、尾指针
s[1]=———————;
while（f<
=r）
{p=s[f++];
if（p->
lc!
｛r++；
}；
if（p->
rc!
{ ；
s[r]=p->
rc;
《数据结构》（01111、01211）作业题（五）
每题1分，共10分）
（）1.算法可以用任意的符号来描述。
（）2.数据的逻辑结构可以看作是从具体问题抽象出来的数学模型。
（）3.线性表的顺序存储方式是按逻辑次序将元素存放在一片地址连续
的空间中。
（）4.栈是一种先进后出的线性表。
（）5.将插入和删除限定在表的同一端进行的线性表称为队列。
（）6.单链表的结点有且仅有一个指针域。
（）8.在有向图G中，<
V2，V1>
和<
V1，V2>
是两条不同的边。
（）9.折半查找方法要求待查表必须是有序表。
（）10.快速排序在最坏情况下的时间复杂度为O（n2）。
1．数据的存贮结构的四种形式为存贮，存贮，存贮和存贮。
2．所有插入和删除都在表的一端进行的线性表称为。
3．n个结点的满二叉树,其深度k=。
4．对于顺序循环队列Q[M]，下标从0到M-1，头尾指针分别为F和R，出队时，队首指针循环加1可表示F=。
5．设二叉树的叶结点数为n0,二度结点数为n2,则两者之间的关系可表示为。
6．n个顶点的连通图的生成树具有条边。
7．顺序查找的平均查找长度为。
三、单选题（在本题的每一个备选答案中，只有一个是正确的，请把你认为正确的答案的题号填入题干的括号里，多选不给分，每题3分，共15分）
1．设输入序列为1，2，3，4借助一个栈不可能得到的输出序列是（）
（1）1，2，3，4
（2）4，3，2，1（3）3，4，1，2（4）1，3，4，2
2．下列排序算法中，最坏情况下，时间复杂度为O（n2）的排序算法是（）
（1）堆排序
（2）希尔排序（3）归并排序（4）快速排序
3．在单向循环链表中，若头指针为h，那么p所指结点为尾结点的条件是（）
（1）p=NULL
（2）p→next=NULL（3）p=h（4）p→next=h
4．与线性表的链接存储不相符的特性是（）
（1）插入和删除操作灵活
（2）需要连续的存储空间
（3）存储空间动态分配（4）需另外开辟空间来保存元素间的关系
5．对于下边的二叉树，其中序序列为（）
（1）DBEHAFCG
（2）DBHEAFCG（3）ABDEHCFG（4）ABCDEFGH
1．请分别画出具有三个结点的树和二叉树的所有形态。
2．画出下列二叉树所对应的中序线索二叉树。
3．写出上述二叉树的后序遍历序列。
4．假定有以下关键字序列，试给出快速排序的第一趟排序结果。
[8015852565900595]
第一趟排序结果为：
5．已知有一带头结点的双向循环链表（结点个数>
=3），其头指针为head，写出删除最后一个结点的语句序列（引进一个临时指针P,须先找到尾结点）。
设双向循环链表的结点类型为：
structbnode
{datatypedata;
bnode*prior,*next;
五、算法设计（在下列算法的横线上填上适当的表达式或语句。
每空3分，共30分）。
1．将两个有序的顺序表合并成一个有序表
voidmerge（intR[],intA[],ints,intm,intt）
//对两个升序
升级会员 