数据结构重修ppt课件

1、1 练习一练习一一、选择题（共一、选择题（共1515分，每题分，每题1.51.5分）分）1 1、适于对动态查找表进行高效率查找的组织结构是（、适于对动态查找表进行高效率查找的组织结构是（ ）A A有序表有序表 B B分块有序表分块有序表 C C二叉排序树二叉排序树 D D线性链表线性链表C C2 2、在一个长度为、在一个长度为n n的线性表中顺序查找值为的线性表中顺序查找值为x x的元素时，查找成功时的平均查找长度的元素时，查找成功时的平均查找长度( (即即x x同元素的平同元素的平均比较次数，假定查找每个元素的概率都相等均比较次数，假定查找每个元素的概率都相等) )为（为（ ）A. n B.

2、 n/2 C.(nA. n B. n/2 C.(n1)/2 D.(n-1)/21)/2 D.(n-1)/2C C3 3、由两个栈共享一个向量空间的好处是：（、由两个栈共享一个向量空间的好处是：（ ）A A减少存取时间，降低下溢发生的机率减少存取时间，降低下溢发生的机率 B B节省存储空间，降低上溢发生的机率节省存储空间，降低上溢发生的机率 C C减少存取时间，降低上溢发生的机率减少存取时间，降低上溢发生的机率 D D节省存储空间，降低下溢发生的机率节省存储空间，降低下溢发生的机率B BTKS1CX0124 4、如下陈述中正确的是（、如下陈述中正确的是（ ）A A串是一种特殊的线性表串是一种特殊

3、的线性表 B B串的长度必须大于零串的长度必须大于零 C C串中元素只能是字母串中元素只能是字母 D D空串就是空白串空串就是空白串A A5 5、设有一个、设有一个1010阶的对称矩阵阶的对称矩阵A A，采用压缩存储方式，以行序为主存储，采用压缩存储方式，以行序为主存储,a,a1111为第一个元素为第一个元素, ,其存储地址其存储地址为为1,1,每个元素占每个元素占1 1个地址空间，则个地址空间，则a a8585的地址为（的地址为（ ）A. 33 B. 13 C. 18 D. 40A. 33 B. 13 C. 18 D. 40A A 6 6、在一棵度为、在一棵度为3 3的树中的树中, ,度为度

4、为3 3的结点个数为的结点个数为2,2,度为度为2 2 的结点个数为的结点个数为1,1,则度为则度为0 0的结点个数为的结点个数为( )( ) A A4 B4 B5 C5 C6 D6 D7 7v v1 1v v6 6v v2 2v v3 3v v5 5v v4 4C C 7 7、右图的一个拓扑有序序列为、右图的一个拓扑有序序列为( )( ) A. v A. v1 1v v2 2v v3 3v v4 4v v5 5v v6 6 B. v B. v5 5v v1 1v v6 6v v2 2v v3 3v v4 4 C. v C. v1 1v v5 5v v2 2v v3 3v v4 4v v6 6

5、 D. v D. v5 5v v1 1v v6 6v v2 2v v4 4v v3 3B BTKS2CX0138 8、将长度为、将长度为n n的单链表链接在长度为的单链表链接在长度为m m的单链表之后的算法的时间复杂度为（的单链表之后的算法的时间复杂度为（ ） A A(1) B(1) B(n) C(n) C(m) D(m) D(m+n) (m+n) C C 9 9、用某种排序方法对关键字序列（、用某种排序方法对关键字序列（2525，8484，2121，4747，1515，2727，6868，3535，2020）进行排序时，序列的）进行排序时，序列的变化情况如下：变化情况如下： 2020，151

6、5，2121，2525，4747，2727，6868，3535，8484 15 15，2020，2121，2525，3535，2727，4747，6868，8484 15 15，2020，2121，2525，2727，3535，4747，6868，8484 则所采用的排序方法是（则所采用的排序方法是（ ） A. A. 选择排序选择排序 B. B. 希尔排序希尔排序 C. C. 归并排序归并排序 D. D. 快速排序快速排序 D D1010、 假设一个有假设一个有n n个顶点和个顶点和e e条弧的有向图用邻接表表示条弧的有向图用邻接表表示, ,则删除与某个顶点则删除与某个顶点v vi i相关的所

7、有弧的时间相关的所有弧的时间复杂度是复杂度是( )( ) A A(n) B(n) B(e) C(e) C(n+e) D(n+e) D(n(ne)e)C CTKS3CX014二、判断题（共二、判断题（共 9 9分，每题分，每题 1.51.5分）（正确的打分）（正确的打，错误的打，错误的打）1 1、（、（ ）完全二叉树中，若一个结点没有左孩子，则它必是树叶。）完全二叉树中，若一个结点没有左孩子，则它必是树叶。 2 2、（、（ ）队列只能采用链式存储方式。）队列只能采用链式存储方式。 3 3、（、（ ）数据的逻辑结构是指各数据元素之间的逻辑关系，是用户按使用需要而建立的。）数据的逻辑结构是指各数据元

8、素之间的逻辑关系，是用户按使用需要而建立的。 4 4、（、（ ）线性表的长度是线性表占用的存储空间的大小。）线性表的长度是线性表占用的存储空间的大小。 5 5、（、（ ）所谓冲突即是两个关键字的值相同的元素，其散列地址相同。）所谓冲突即是两个关键字的值相同的元素，其散列地址相同。 6 6、（、（ ）由二叉树的先序序列和中序序列能唯一确定一棵二叉树。）由二叉树的先序序列和中序序列能唯一确定一棵二叉树。 三、填空题三、填空题（第第6 6题题2 2分，其它每空分，其它每空1 1分，共分，共1515分分）1、栈顶的位置是随着_和_操作而变化的。 入栈入栈 出栈出栈TKS4CX0152 2、在一个带头结

9、点的单循环链表中，、在一个带头结点的单循环链表中，p p指向尾结点的直接前驱，则指向头结点的指针指向尾结点的直接前驱，则指向头结点的指针headhead可用可用p p表示表示为为head= _head= _ _p-next-nextp-next-next 3 3、在一棵高度为、在一棵高度为5 5的理想平衡二叉树中，最少含有的理想平衡二叉树中，最少含有_个结点，最多含有个结点，最多含有_个结点。个结点。 161631314 4、数据的逻辑结构是从逻辑关系上描述数据，它与数据的、数据的逻辑结构是从逻辑关系上描述数据，它与数据的 _无关，是独立于计算机的。无关，是独立于计算机的。存储结构存储结构 5

10、 5、在串、在串S=S=“structurestructure”中，以中，以t t为首字符的子串有为首字符的子串有 个。个。 12126 6、取出广义表、取出广义表A=(a,(x,b,c,d)A=(a,(x,b,c,d)中原子中原子x x的函数是的函数是_head(head(tail(A) head(head(tail(A) 7 7、在以、在以HLHL为表头指针的带表头结点的单链表和循环单链表中，链表为空的条件分别为为表头指针的带表头结点的单链表和循环单链表中，链表为空的条件分别为_和和_。 HL-next=NULL HL-next=NULL HL-next=HL HL-next=HL 8 8

11、、对于一棵完全二叉树，若一个结点的编号为、对于一棵完全二叉树，若一个结点的编号为i i，则它的左孩子结点的编号为，则它的左孩子结点的编号为_，双亲结点，双亲结点的编号为的编号为_。 2i2ii/2i/2TKS5CX0169 9、对于一个具有、对于一个具有n n个顶点和个顶点和e e条边的有向图和无向图，在其对应的邻接表中，所含边结点分别为条边的有向图和无向图，在其对应的邻接表中，所含边结点分别为_ _ 和和 _条。条。 2e2ee e四、应用题（共四、应用题（共4545分）分）1 1、假定用于通信的电文仅由、假定用于通信的电文仅由8 8个字母个字母c1, c2, c3, c4, c5, c6,

12、 c7, c8c1, c2, c3, c4, c5, c6, c7, c8组成组成, , 各字母在电文中出现的各字母在电文中出现的频率分别为频率分别为5, 25, 3, 6, 10, 11, 36, 45, 25, 3, 6, 10, 11, 36, 4。试为这。试为这8 8个字母设计个字母设计HuffmanHuffman编码编码, , 使电文中字符的二进制使电文中字符的二进制内部表示最短。要求：内部表示最短。要求：(1)(1)画出对应的哈夫曼树；画出对应的哈夫曼树；(2)(2)各字符的编码表；各字符的编码表；(3)(3)以各字符出现的频度为权，以各字符出现的频度为权，计算其带权路径的长度。计

13、算其带权路径的长度。(9(9分分) )0100100 010100000000 00100101 1001001011011111100010001c c1 1c c2 2c c3 3c c4 4c c5 5c c6 6c c7 7c c8 8(1)(1)哈夫曼树哈夫曼树(2)(2)各字符的编码表各字符的编码表(3)(3)带权路径的长度带权路径的长度wpl=(3+4+5+6)wpl=(3+4+5+6)* *4+(10+11)4+(10+11)* *3+(25+36)3+(25+36)* *2=72+63+122=72+63+122=257 2=257 TKS6CX0172 2、已知线性表的关键

14、字集合、已知线性表的关键字集合87, 25, 310, 08, 27, 132, 68, 95, 187, 123, 70, 63, 4787, 25, 310, 08, 27, 132, 68, 95, 187, 123, 70, 63, 47，已知，已知散列函数为散列函数为H(k)=k MOD 13H(k)=k MOD 13，采用拉链法处理冲突，要求（，采用拉链法处理冲突，要求（8 8分）分）(1) (1) 设计出该开散列表的结构；设计出该开散列表的结构；(2) (2) 求出等概略查找下查找成功的平均查找长度；求出等概略查找下查找成功的平均查找长度；(3) (3) 求出等概略查找下查找不成

15、功的平均查找长度。求出等概略查找下查找不成功的平均查找长度。 0123456789101112 27 27 (1)(1)(2)(2)(3)(3) ASL=(10 ASL=(10* *1+31+3* *2)/13=16/132)/13=16/13 ASL=(3 ASL=(3* *1+71+7* *2+32+3* *3)/13=26/13=23)/13=26/13=2 TKS7CX01 70 70130 130 68 68 95 95 187 187 123 123 47 47 8 8 87 87 63 63310 310 12 12 83 3、对右图所示的连通网络，应用、对右图所示的连通网络，应

16、用PrimPrim算法求解连通网络的最小生成树问题。算法求解连通网络的最小生成树问题。(7(7分分) )(1) (1) 按如下格式给出在构造最小生成树过程中按如下格式给出在构造最小生成树过程中( (从顶点从顶点v v1 1出发的出发的) )顺序选出的各条边；顺序选出的各条边；(5(5分分) )(2) (2) 画出一棵最小生成树；画出一棵最小生成树；(2(2分分) )( (始顶点号，终顶点号，始顶点号，终顶点号， 权值权值 ) )( , , )( , , )( , , )( , , )( , , )( , , )( , , )( , , )( , , )( , , )v v6 610101212

17、8 820206 61818141411119 95 5v v1 1v v2 2v v3 3v v4 4v v5 510105 56 61111 9 9v v6 6v v1 1v v2 2v v3 3v v4 4v v5 5v v1 1 v v6 6 9 9 v v6 6 v v5 5 10 10 v v6 6 v v2 2 11 11 v v2 2 v v3 3 5 5 v v3 3 v v4 4 6 6 TKS8CX0194 4、设待排序的排序码序列为、设待排序的排序码序列为12, 2, 16, 30, 28, 10, 1612, 2, 16, 30, 28, 10, 16* *, 20,

18、 6, 18, , 20, 6, 18, 试分别写出使用以下排试分别写出使用以下排序方法每趟排序后的结果。序方法每趟排序后的结果。(11(11分分) )(1)(1)直接插入排序直接插入排序( (设监视哨设监视哨) (5) (5分分) )(2)(2)快速排序快速排序(6(6分分) ) (1)(1)直接插入排序直接插入排序( (设监视哨设监视哨) (5) (5分分) )i = 1 12 2 16 30 28 10 16i = 1 12 2 16 30 28 10 16* * 20 6 18 20 6 18 i = 2 2 12 16 30 28 10 16i = 2 2 12 16 30 28 1

19、0 16* * 20 6 18 20 6 18 i = 3 2 12 16 30 28 10 16i = 3 2 12 16 30 28 10 16* * 20 6 18 20 6 18 i = 4 2 12 16 30 28 10 16i = 4 2 12 16 30 28 10 16* * 20 6 1820 6 18i = 5 2 12 16 28 30 10 16i = 5 2 12 16 28 30 10 16* * 20 6 1820 6 18i = 6 2 10 12 16 28 30 16i = 6 2 10 12 16 28 30 16* * 20 6 1820 6 18i

20、= 7 2 10 12 16 16i = 7 2 10 12 16 16* * 28 30 20 6 1828 30 20 6 18i = 8 2 10 12 16 16i = 8 2 10 12 16 16* * 20 28 30 6 1820 28 30 6 18i = 9 2 6 10 12 16 16i = 9 2 6 10 12 16 16* * 20 28 30 1820 28 30 18i =10 2 6 10 12 16 16i =10 2 6 10 12 16 16* * 18 20 28 3018 20 28 30TKS9CX0110(2)(2)快速排序快速排序(6(6分分

21、) )Pivot 0 1 2 3 4 5 6 7 8 9Pivot 0 1 2 3 4 5 6 7 8 9 12 12 2 16 30 28 10 16 12 12 2 16 30 28 10 16* * 20 6 1820 6 18 6 6 2 10 12 28 30 16 6 6 2 10 12 28 30 16* * 20 16 1820 16 18 28 2 6 10 12 28 30 16 28 2 6 10 12 28 30 16* * 20 16 1820 16 18 18 2 6 10 12 18 16 16 18 2 6 10 12 18 16 16* * 20 28 302

22、0 28 30 16 16* * 2 6 10 12 162 6 10 12 16* * 16 18 20 28 3016 18 20 28 30 2 6 10 12 16 2 6 10 12 16* *16 18 20 28 3016 18 20 28 30TKS10CX0111252530121281017153040353512124545201515v v1 1v v5 5v v3 3v v4 4v v6 6V V7 7v v2 25 5、如右图所示的有向网络，要求、如右图所示的有向网络，要求(10(10分分) )(1)(1)写出该网的邻接矩阵；写出该网的邻接矩阵；(2(2分分) )(

23、2)(2)写出用写出用DijkstraDijkstra算法求从顶点算法求从顶点v v1 1出发到其它各顶点最短路径出发到其它各顶点最短路径的执行过程；的执行过程；(6(6分分) )(3)(3)写出从顶点写出从顶点v v1 1出发到顶点出发到顶点v v3 3的最短路径及其长度。的最短路径及其长度。(2(2分分) )178301520301510401235251245COST= COST= 选代次数选代次数 选择选择V V 最短路长最短路长 集合集合S d1 d2 d3 d4 d5 d6 d7S d1 d2 d3 d4 d5 d6 d7 初态初态 v v1 1 0 45 12 25 35 0 45 12 25 35 1 v 1 v4 4 12 v 12 v1 1v v4 4 0 45 12 25 42 320 45 12 25 42 32 2 v 2 v5 5 25 v 25 v1 1v v4 4v v5 5 0 40 55 12 25 42 320 40 55 12 25 42 32 3 v 3 v7 7 32 v 32 v1 1v v4 4v v5 5v v7 7 0 40 55 12 25 42 320 40 55 12 25 42 32 4 v 4 v2 2 40 v