计算机本科《数据结构》复习资料

计算机科学与技术《数据结构》复习资料1

一、填空题

1.若规定二叉树根结点的层次为1,则第4层上最多有个结点。

2.具有N个结点的无向完全图共有条边。

3.树转换为二叉树;其根结点的子树一定为空。

4.对一棵二叉排序树进行中序遍历时，得到的结点序列是一个o

5.已知二维数组a[10][8]采用行优先存储方式，每个元素占2个存储单元，第一个元素的

存储地址是1012,则元素a[4][5]的存储地址为()0

6.快速排序在平均情况下的时间复杂度为,在最坏情况下的时间复杂度为o

7.画出具有3个结点的二叉树的所有形态：o

8.对于一个单链接存储的线性表，假定表头指针指向链表的第一个结点，则在表头插入结点

的时间复杂度为，在表尾插入结点的时间复杂度为o

9.数据结构课程是研究数据的、、等三个方面的内容。

10.已知完全二叉树的第8层有8个结点，则其叶子结点数是o

二、应用题

1.已知二叉树的中序遍历序列和后序遍历序列分别为CBEDAFIGH和CEDBIFHGA,试构造该二

叉树。

2.若一个图的边集为{(A,B),(A,C),(A,D),(B,D),(C,F),(D,E),(D,F)},从顶点A开始分别

对该图进行深度优先搜索和广度优先搜索，要求顶点值小的邻接点被优先访问，则写出得到

的深度优先搜索和广度优先搜索的顶点序列。

3.下图所示是一个无向带权图，请按Prim算法求最小生成树。

4.给定数据元素系列为{47,23,2,15,98,57,22,6,12},请写出直接选择排序各趟的

结果。

5.已知散列函数H(k)=kmod12,键值序列为(25,37,52,43,84,99,120,15,26,11,70,82),

采用拉链法处理冲突，试构造开散列表，并计算查找成功的平均查找长度。

答案

一、填空题

1.8

2.N(N+l)/2

3.右子树

4.有序序列

5.1050.

6.O(log2n),O(log2n)

7.

8.0(1),0(n)

9.操作对象、关系、操作

10.68

二、应用题

1.二叉树的构造过程如图:

2.深度优先搜索得到的顶点序列:A,B,D,E,F,C

广度优先搜索得到的顶点序列：A,B,C,D,F,E

3.解答：按Prim算法求最小生成树的过程如下:

4.解答:

初始:47,23,2,15,98,57,22,6,12.

第一趟:2,[23,47,15,98,57,22,6,12]

弟人人♦一—.趟主业:2,6,[47,15,98,57,22,23,12]

第三趟:2,6,12,[15,98,57,22,23,47]

第四趟:2,6,12,15,[98,57,22,23,47]

第五趟:2,6,12,15,22,[57,98,23,47]

第六趟:2,6,12,15,22,23,【98,57,47]

第七趟:2,6,12,15,22,23,47,[57,98]

第八趟:2,6,12,15,22,23,47,57,[98]

最后所得：2,6,12,15,22,23,47,57,98

5.解答:H(25)=l,H(37)=l,H(52)=4,H(43)=7,H(84)=0,H(99)=3,H(120)=0,H(15)=3,

H(26)=2,H(ll)=ll,H(70)=10,H(82)=10o构造的开散列表如下:

0

1

2

3

4

5

6

7

8

9

10

11

计算机科学与技术《数据结构》复习资料2

一、应用题

1.对给定的一组权值W=(5,2,9,11,8,3,7),试构造相应的哈夫曼树，并计算它的

带权路径长度。

2.若一个图的边集为{(A,B),(A,C),(A,D),(B,D),(C,F),(D,E),(D,F)},从顶点A开始分别

对该图进行深度优先搜索和广度优先搜索，要求顶点值小的邻接点被优先访问，则写出得到

的深度优先搜索和广度优先搜索的顶点序列。

3.已知一组元素为(46,25,78,62,12,37,70,29),试画出按元素排列次序插入生成的一棵二

叉排序树。

4.给定数据元素系列为{47,23,2,15,98,57,22,6,12},请写出直接选择排序各趟的

结果。

5.设散列表的长度m=13；散列函数为H(K)=Kmodm,给定的关键码序列为19,14,23,01,

68,20,84,27,55,11,试画出用线性探查法解决冲突时所构造的散列表。

二、算法设计题

1.设计一个算法，在顺序线性表L中删除第i个元素，并返回其值。

答案

一、应用题

1.构造的哈夫曼树如图:

树的带权路径长度为：WPL=2X4+3X4+5X3+7X3+8X3+9X2+11X2=120

2.深度优先搜索得到的顶点序列：A,B,D,E,F,C

广度优先搜索得到的顶点序列：A,B,C,D,F,E

4.解答:

初始:47,23,2,15,98,57,22,6,12.

第一趟：2,[23,47,15,98,57,22,6,12]

第二趟：2,6,[47,15,98,57,22,23,12]

第三趟：2,6,12,[15,98,57,22,23,47]

第四趟:2,6,12,15,[98,57,22,23,47]

第五趟：2,6,12,15,22,[57,98,23,47]

第六趟：2,6,12,15,22,23,【98,57,47]

第七趟:2,6,12,15,22,23,47,【57,98]

第八趟:2,6,12,15,22,23,47,57,[98]

最后所得：2,6,12,15,22,23,47,57,98

5.解答：

设散列表的长度m=13；散列函数为H(K)=Kmodm,给定的关键码序列为

19,14,23,01,68,20,84,27,55,11,则有

H(19)=6,成功;H(14)=l,成功;H(23)=10,成功;

H(01)=l,冲突,=2,成功;H(68)=3,成功;H(20)=7,成功;

H(84)=6,冲突,冲突，=8,成功;

H(27)=1,冲突,=2,冲突，=3,冲突，=4,成功;

H(55)=3,冲突,=4,冲突，=5,成功;H(ll)=ll,成功。

0123456789101112

14016827551920842311

⑴(2)(1)(4)(3)(1)(1)(3)(1)⑴

二、算法设计题

1•【解答】

StatusListDelete_Sq(SqList&L,inti,ElemType&e)

(

if(i<l|i>L.length)teturnERROR;

p=&L.elem[i-l];

e=*p;

q=L.elem+L.length-1;

for(++p;p<=q;++p)*(p+l)=*p;

一L.length;

returnOK;

计算机科学与技术《数据结构》复习资料3

一、应用题

1.对于下列二叉树，请写出:

(1)前、中、后序遍历次序;

(2)中序线索二叉树；

2.若一个图的边集为{(A,B),(A,C),(A,D),(B,D),(C,F),(D,E),(D,F)},从顶点A开始分别

对该图进行深度优先搜索和广度优先搜索，要求顶点值小的邻接点被优先访问，则写出得到

的深度优先搜索和广度优先搜索的顶点序列。

3.给定叶子结点的权值{1,4,6,2,9},请构造哈夫曼树，并给出叶子结点的哈夫曼编码。

4.已知一组记录为(46,74,53,14,26,38,86,65,27,34),给出采用快速排序法进行排序时每

一趟的排序结果。

5.设散列表的长度m=13；散列函数为H(K)=Kmodm,给定的关键码序列为

19,14,23,01,68,20,84,27,55,11,试画出用线性探查法解决冲突时所构造的散列表。

二、算法设计题

1、设计一个算法，通过一趟遍历在单链表中确定值最大的结点。

答案

一、应用题

1.(1)前序遍历次序：ABDGCEFH

中序遍历次序：DGBAECHF

后序遍历次序：GDBEHFCA

(2)中序线索二叉树

2.深度优先搜索得到的顶点序列：A,B,D,E,F,C

广度优先搜索得到的顶点序列：A,B,C,D,F,E

3.解答：

各符号的哈夫曼编码为:1:000；2：0001；4：001；6：01；9：1

4.解答:

初始：[46745314263886652734]

第一趟：[3414263827]46[86655374]

第二趟：[271426]343846[746553]86

第三趟：[2614]27343846[5365]7486

第四趟：14262734384653657486

5.解答：

设散列表的长度m=13；散列函数为H(K)=Kmodm,给定的关键码序列为

19,14,23,01,68,20,84,27,55,11,则有

H(19)=6,成功;H(14)=l,成功;H(23)=10,成功;

H(01)=l,冲突，=2,成功；H(68)=3,成功；H(20)=7,成功;

H(84)=6,