新数据结构讲义(9)

第九讲

总复习课

我们回顾一下学过的内容，数据结构是一门专业课。本课程的目的和任务是使学生较全面地掌握各种常用的数据结构，为学习后续软件课程提供必要的基础，提高运用数据结构解决实际问题的能力。

第一章的目的是介绍数据结构中常用的基本概念和术语以及学习数据结构的意义，要求了解本章介绍的各种基本概念和术语，掌握算法描述和分析的方法。

第二章的目的是介绍线性表的逻辑结构和各种存储表示方法，以及定义在逻辑结构上的各种基本运算及其在存储结构上如何实现这些基本运算。要求能够针对具体应用问题的要求和性质，选择合适的存储结构设计出相应的有效算法，解决与线性表相关的实际问题。

第三章的目的是介绍栈和队列的逻辑结构定义及在两种存储结构上如何实现栈和队列的基本运算，重点是掌握栈和队列在两种存储结构上实现的基本运算。

第四章的目的是介绍串的逻辑结构，存储结构及其串上的基本运算，重点是掌握串上实现的模式匹配算法。

第五章的目的是介绍多维数组的逻辑结构特征及其存储方式，特殊矩阵和稀疏矩阵的压缩存储方法及广义表的概念。重点是熟悉多维数组的存储方式，矩阵的压缩存储方式，广义表的定义及其求表头和表尾的运算。

1

第六章的目的是介绍二叉树的定义，性质，存储结构，遍历，线索化，树的定义，存储结构，遍历，树和森林与二叉树的转换，哈夫曼树及哈夫曼编码等内容。重点是掌握二叉树的遍历算法及其 有关应用。

第七章的目的是介绍图的基本概念，两种常用的存储结构，两种遍历算法以及图的应用算法，要求重点掌握在图的两种存储结构上实现的遍历算法。难点是图的应用算法：求最小生成树，求最短路径以及拓扑排序。

第八章的目的是介绍五类内部排序方法的基本思想，排序过程，算法实现，时间和空间性能的分析以及各种排序方法的比较和选择。重点掌握快速排序，堆排序，归并排序和基数排序的基本思想及排序过程，难点是这四个排序算法的实现。

第九章的目的是介绍线性表，树和散列表的查找方法，算法实现和各种查找方法的时间性能分析。重点掌握顺序查找，二分查找，二叉查找树上查找以及散列表上查找的基本思想和算法实现。

第十章的目的是介绍存储在外存上的数据结构（即文件）的有关概念，各种文件的特点，组织方法及查询和更新操作，要求对这些内容做一般性的了解。

本课程内容多，难度大，要求具有较强的程序设计能力及离散数学，C语言基础，从数据结构的逻辑结构，存储结构和数据的运算三个方面去理解各种数据结构的异同之处及相互之间的关系，懂得从定义和实现两个层次去分析各种数据结构。通过多练习多动手，培养自

2

己的程序设计经验和素质，多做算法设计题来理解，消化和巩固所学的知识，提高分析问题，解决问题的能力以及编程能力。设计较复杂算法的方法和步骤是：首先明确算法要解决的问题目标，选择合适的数据结构，确定在所选的数据结构上必须有哪些操作，写出抽象的算法；然后确定存储结构，对抽象算法中每个操作逐步求精地写出最终的程序。

要求全面系统地学习各章节内容，弄懂和记住各种概念，方法，结论的内涵和外延，注意区分相仿的概念，方法，结论，掌握它们之间的联系。

一、 单项选择题

1、线性表的链接实现有利于 运算。

A、插入 B、读表元 C、查找 D、定位 2、串的逻辑结构与 的逻辑结构不同。

A、线性表 B、栈 C、队列 D、树

3、设单链表中指针P指着结点A，若要删除A之后的结点（若存在），则需要修改指针的操作为 。

A、P→next=P→next→next B、P= P→next C、P=P→next→next D、P→next=P

4、设一数列的顺序为：1，2，3，4，5，6，通过栈结构不可能排成的顺序数列为 。

A、3，2，5，6，4，1 B、1，5，4，6，2，3

3

C、2，4，3，5，1，6 D、4，5，3，6，2，1

5、如果结点A有3个兄弟，而且B为A的双亲，则B的度为 。

A、3 B、4 C、5 D、1

6、线索化二叉树中某结点D，没有左孩子的主要条件是 。

A、D→Lchild=Null B、D→ltag=1 C、D→Rchild=Null D、D→ltag=0 7、下面的序列中， 是堆。

A、1，2，8，4，3，9，10，5 B、1，5，10，6，7，8，9，2 C、9，8，7，6，4，8，2，1 D、9，8，7，6，5，4，3，7 8、具有n个顶点的完全有向图的边数为 。

A、n(n-1)/2 B、n(n-1) C、2n D、(n+1)(n-1) 9、具有2000个节点的二叉树，其高度至少为 。

A、9 B、10 C、11 D、12

10、若给定的关键字集合为{20，15，14，18，21，36，40，10}，一趟快速排列结束时，键值的排列为 。

A、10，15，14，18，20，36，40，21 B、10，15，14，18，20，40，36，21 C、10，15，14，20，18，40，36，21 D、15，10，14，18，20，36，40，21 11、有一棵二叉树如下图，该树是 。

4

A、二叉平衡树 B、二叉排序树 C、堆的形状 D、以上都不是

12、设有100个元素，用二分法查找时，最大比较次数是 ，最小比较次数是 。

A、25 B、7 C、10 D、1 13、在内部排序中，排序时不稳定的有 。

A、插入排序 B、冒泡排序 C、快速排序 D、归并排序 14、对于下图V1的度为 。

5

A、1 B、2 C、3 D、4

15、中根遍历一棵二叉排序树所得到的结点访问序列是键值的 序列。

A、递增或递减 B、递减 C、递增 D、无序

16、下列哪种排序需要的附加存储开销最大 。

A、快速排序 B、堆排序 C、插入排序 D、冒泡排序

17、在有n个叶子结点的哈夫曼树中，其结点总数为 。

A、不确定 B、 2n C、2n+1 D、2n-1

6

18、若线性表最常用的操作是存取第i个元素及其前趋的值，则采用

存储方式节省时间。

A、单链表 B、双链表 C、单循环链表 D、顺序表

19、某二叉树的先序序列和后序序列正好相反，则该二叉树一定是 的二叉树。

A、空或只有一个结点 B、高度等于其结点数 C、任一结点无左孩子 D、任一结点无右孩子 20、已知数据表A中每个元素距其最终位置不远，则采用 排序算法最省时间。

A、堆排序 B、插入排序 C、直接选择排序 D、快速排序

21、设连通图G的顶点数为n，则G的生成树的边数为 。

A、n B、 n-1 C、2n D、2n-1

22、有一个散列表，表长度m为100，采用除余法构造散列函数，即H（K）=K%P，（P小于等于m ）,为使散列函数有较好的性能，P的选择应是 。

A、99 B、97 C、91 D、93

23、对有14个元素的有序表A[1…14]作二分查找，查找元素A[4]时的被比较元素依次为 。

A、A[1]，A[2]，A[3]，A[4] B、A[1]，A[14]，A[7]，A[4]

7

C、A[7]，A[3]，A[5]，A[4] D、A[7]，A[5]，A[3]，A[4] 24、具有65个结点的完全二叉树其深度为 。

A、8 B、7 C、6 D、5

25、若表R在排序前已按元素键值递增顺序排列，采用 的比较次数少。

A、直接插入排序 B、快速排序 C、归并排序 D、选择排序

26、在一个具有n个结点的单链表中查找其值等于x的结点时，在查找成功的情况下，需平均比较 个元素结点。

A、n/2 B、n C、(n+1)/2 D、(n-1)/2

27、对一个具有n个元素的线性表，建立其有序单链表的时间复杂度为 。

A、O(n) B、O(1) C、O(n) D、O(㏒2n)

228、在一棵度为3的树中，度为3的结点数为2个，度为2的结点数为1个，度为1的结点数为2个，那么度为0的结点数为 个。

A、5 B、5 C、6 D、7

29、已知8个元素（34，76，45，18，26，54，92，65），按照依次插入结点的方法生成一棵二叉排序树，该树的深度为 。

A、4 B、5 C、6 D、7

30、给定权的集合{15，3，14，2，6，9，16，17}，所构造出的哈夫

8

曼树的带权路径长度为 。

A、129 B、219 C、189 D、229 二、填空题

1、循环链表的主要优点是从任一结点出发可以遍历链表中的所有结点。

2、一个n×n的对称矩阵，如果以行或列为主序存入内存，则其容量为n(n+1)/2。

3、假设用向量V[0…m-1]来存储栈，m表示栈的最大容量，则入栈操作为top+=1；V[top]=x；出栈操作为x=V[top]，top-=1。 4、给定表（55，63，44，38，75，80，31，56），用筛选法建立初始堆，则初始堆表为（31，38，44，56，75，80，55，63）或（80，75，55，56，63，44，31，38）。 5、具有64个结点的完全二叉树的深度为7。

6、设有一空栈，栈顶指针为1000H（十六进制），现有输入序列为1，2，3，4，5，经过push，push，pop，push，pop，push，push后，输出序列为2，3。

7、一个具有n个结点的有向完全图的弧度为n(n-1)。

8、在双向循环链表中，设指针P指向待删除的结点，则删除结点*P需执行的语句为

P→prior→next=P→next，P→next→prior=P→prior。

9、采用堆排序、快速排序、冒泡排序，对初态为有序的表，则最省时间的是冒泡排序。

9

10、取出广义表A=（（x，y，z），（a，b，c，d））中的原子 b的函数是head(tail(head(tail(A))))。

11、在有n个顶点的有向图中，每个顶点的度最大可达2(n-1)。 12、已知二叉树中叶子数为50，仅有一个孩子的结点数为30，则总结点数为129。

13、在二叉链表中判断某指针P所指结点为叶子结点的条件是（P→lchild==Null&&P→rchild==Null）。

14、直接选择排序算法在最好情况下所作的交换元素的次数为0。 15、设一棵二叉树共有50个叶结点（终端结点），则共有49个度为2的结点。

16、3个结点可构成2棵不同形状的树。

17、设有向图G的邻接矩阵为A，如果图中不存在弧〈Vi,Vj〉，则A[i][j]的值为0。

18、利用直接选择排序算法对n个记录进行排序，最坏情况下，记录交换的次数为n-1。

19、如果要将序列{50，16，23，68，94，70，73}建成堆，则需把16与50相互交换。 三、判断对错

1、对任意一个图，从它的某个顶点出发进行一次深度优先或广度优先搜索遍历可访问到该图的每个顶点。 （ 错 ）

2、已知一棵树的先序序列和后序序列，一定能构造出该树。（ 对 ） 3、快速排序是排序算法中最快的一种。 （ 错 ）

10

平均查找长度ASL=（1+2×2+3×3+4×2）/8=11/4。

7、设散列函数H（K）=K，给定键值序列为13，41，15，44，6，68，12，25，38，64。试画出相应的散列表，并求在等概率下成功查找时的平均查找长度。 解：

13=2 15=4 6=6 12=1 41=8 44=0 68=2 25=3 38=5 64=9

散列表为：

16

在等概率情况下成功查找的平均查找长度为： ASL=1/10（1+1+1+1+1+1+1+1+1+2）=1.1

8、已知下面二叉排序树的各结点的值依次为1∽9，请标出各结点的值。 解：

17

9、给定有序表D={15，17，18，22，35，51，60，88，93}，用二分法查找法在D中查找18，试用图示法表示查找过程。 解：查找过程为：

18

10、求下列带权图的最小生成树，并给出Prim执行过程，假设u={3}。

19

解：从V3顶点出发用Prim算法求该图最小生成树的过程为：

20

五、算法设计题

1、 试写出求二叉树结点数目的算法。 解：递归模型为：

f(t)=0 t=Null

f(t)=1 t→lchild=Null且t→rchild=Null f(t)=f(t→lchild)+（t→rchild）+1 其他 函数为：

int nodes(t) bitree *t {

int num1, num2;

21

if (t==Null)

return 0;

else

if (( t→lchild==Null)&&(t→rchild==Null)) return 1; else {

num1=nodes(t→lchild); num2=nodes(t→rchild); return (num1+num2+1);

}

}

2、已知一个单链表中每个结点存放一个整数，并且其结点数不少于2，试设计算法以判断该链表中从第二项起的每个元素值是否等于其序号的平方减去其前驱的值，若满足，返回Ture，否则返回False。 解：函数为：

int judge(head) linklist *head; {

int flag, i;

linklist *p, *q;

22

q=head→next;

flag=false; i=2;

while(p!=Null) {

if((p→data)==(i*i-q→data))

flag=ture; else

return false; q=p; p=p→next; i++; }

if(flag==ture) return ture; }

3、设计一个算法，求出指定结点在给定的二叉排序树中所在的层次。 解：算法为：

void level(t, p, h, k) bitree *t, *p; int h, k; {

23

if (t==Null) h=0; else if(p==t) h=k;

else {

level(p, t→lchild, h, k+1); if(h==-1)

level(p, t→rchild, h, k+1);

} }

4、写出在中序线索二叉树中求指定结点的后继的算法。 解：算法为：

bitree *succ(p) bitree *p; {

bitree *q; if(p→rtag==1)

return (p→rchild); else {

q=p→rchild; while (q→ltag==0) q=q→lchild; return (q);

24

}

}

5、设计一个算法，求出指定结点在给定的二叉树中所在的层次。 解：算法为：

int level(t, p) bitree *t, *p; {

int count; count=0; if(t==Null) return (0); else {

count=count+1;

while(t→data!=p→data) {

if(t→data

t=t→lchild; count=count+1; }

25

本文来源：https://www.bwwdw.com/article/oo8f.html