数据结构考试复习资料(编辑修改稿)

数据结构考试复习资料(编辑修改稿)内容摘要：

1. 请分别简答顺序存储结构与链式存储结构的构造原理以及它们的特点。 答：线性表的顺序存储结构是在存储器中用一片地址连续的存储单元依次存 放线性 表中的数据元素，数据元素之间的逻辑关系通过数据元素的存储地址直接反映。 在这种存储结构中，逻辑上相邻的两个数据元素在物理位置上也一定相邻。 2. 对二叉树中的结点进行按层次顺序（每一层自左至右）的访问操作称为二叉树的层次遍历，遍历所得到的结点序列称为二叉树的层次序列。 现已知一棵二叉树的层次序列为ABCDEFGHIJ，中序序列为 DBGEHJACIF，请画出该二叉树。 【解答】 3. 已知无向图 G=(V,E) ，其中，顶点集合为 V={v1,v2,v3,v4,v5,v6,v7}, ，边的集合为 {(v1,v2),(v1,v3),(v2,v1),(v2,v4),(v2,v6),(v3,v1),(v4,v2),(v4,v7),(v5,v4),(v5,v6),(v6,v2),(v6,v2),(v7,v4)},请先给出邻接表结构，然后分别给出根据该 邻接表从顶点 v1 出发进行深度优先搜索与广度优先搜索后的顶点序列。 【解答】 邻接表结构： 深度优先搜索序列为： v1， v2， v4， v5， v6， v7， v3 广度优先搜索序列为： v1， v2， v3， v4， v6， v5， v7 4. 用宽度优先搜索和深度优先搜索对如图所示的无向图 G进行遍历 (从顶点 1 出发 )， 给出遍历序列 【解答】搜索本题图的宽度优先搜索的序列为： 12， 4， 3， 6， 5， 8， 7，深度优先搜索的序列 为： 1， 2， 6， 4， 5， 7， 8， 30 5. 指出下列算法的时间复杂度。 sum1(int n) { int p=1,sum=0,1。 for(i=1。 i=n。 i++) { p*=I。 sum+=p。 } return(sum)。 } 【解答】 sum1()的嵌套最深层语句： p*=I。 sum+=p。 它的频度为 n 次，所以其时间复杂度是 O(n)。 6. 对于一个栈，给出输入项 A,B,C。 如果输入项序列由 A,B,C 所组成，试给出全部可能的输出序列。 【解答】 ABC， ACB， BAC， BCA， CBA 7. 有 n 个顶点的无向连通图至少有多少条边。 有 n 个顶点的有向强连通图至少有多少条边。 试举例说明。 【解答】 n 个顶点的无向连通图至少有 n1 条边， n个顶点的有向强连通图至少有 n 条边。 例如： 8. 请分别叙述在一个连续顺序文件中采用顺序查找法、折半查找法和分块查找法查找一个记录，该文件记录应该满足什么要求。 【解答】 采用顺序查找法：文件中记录可以任意次序存放。 采用折半查找法：文件中的记录必须按照关键字值从小到大或从大到小有序存放。 采用分块查找法：将文件分成若干段，每一块中的记录可以任意存放，但块与块之间必须按照关键字从小到大或从大到小的次序存放，即前一块中 的所有记录的关键字值必须小于后一块中所有记录的关键字值。 9. 试对右图所示的 AOE 网络 : (1) 这个工程最早可能在什么时间结束。 (2) 求每个活动的最早开始时间 e( )和最迟开始时间 l( )。 (3) 确定哪些活动是关键活动。 【解答】按拓扑有序的顺序计算各个顶点的最早可能开始时间 Ve 和最迟允许开始时间 Vl。 然后再计算各个活动的最早可能开始时间 e 和最迟允许开始时间 l，根据 l e = 0? 来确定关键活动，从而确定关键路径。 此工程最早完成时间为 43。 关键 路径为 1, 33, 22, 55, 6 10. 何为数据的逻辑结构。 何为数据的存储结构。 一般情况下，两者之间有什么联系。 这种联系是如何反映的。 【解答】 数据的逻辑结构是指数据元素之间在客观世界中所具有的逻辑关系。 数据的存储结构是指数据在计算机存储器中的存储方式。 在数据的顺序存储与链式存储结构中，通常要能够反映数据所具有的逻辑结构。 在顺序存储结构中，通过数据元素的存储地址来直接反映数据元素之间的逻辑关系，而链式存储结构则是通过指针来间接反映数据元素之间的逻辑关系。 11．分别写出如图所示 各二叉树的前序、中序和后序序列 【解答】： （ 1）前序 （ a） 12357864 （ b） 124735689 （ 2）中序 (a ) 17583624 (b) 472153869 （ 3）后序 (a ) 78563421 (b) 742589631 12. 画出下图所示的 AOV网的所有拓扑有序序列。 【解答】 ADBECF ADBEFC ADEBCF ADEBFC DABECF DABEFC DAEBCF DAEBFC 13. 何为数据的逻辑结构。 何为数据的存储结构。 一般情况下，两者之间有什么联系。 这种联系是如何反映的。 【解答】 数据的逻辑结构是指数据元素之间在客观世界中所具有的逻辑关系。 数据的存储结构是指数据在计算机存储器中的存储方式。 在数据的顺序存储与链式存储结构中，通常要能够反映数据所具有的逻辑结构。 在顺序存储结构中，通过数据元素的存储地址来直接反映数据元素之间的逻辑关系，而链式存储结构则是通过指针来间接反映数据元素之间的逻辑关系 14 . 已知序列 (35， 70， 12， 26， 90， 41， 66， 58)，请写出对该序列采用泡排序方法 进行升序排序时各趟的结果。 【解答】 原始序列： 35， 78， 12， 26， 90， 41， 66， 58 第 — 趟后： 35， 12， 26， 78， 41， 66， 58， 90 第二趟后： 12， 26， 35， 41， 66， 58， 78， 90 第三趟后： 12， 26， 35， 41， 58， 66， 78， 90 第四趟后： 12， 26， 35， 41， 58， 66， 78， 90 15. 何为数据的逻辑结构。 何为数据的存储结构。 一般情况下，两者之间有什么联系。 这种联系是如何反映的。 【解答】 数 据的逻辑结构是指数据元素之间在客观世界中所具有的逻辑关系。 数据的存储结构是指数据在计算机存储器中的存储方式。 在数据的顺序存储与链式存储结构中，通常要能够反映数据所具有的逻辑结构。 在顺序存储结构中，通过数据元素的存储地址来直接反映数据元素之间的逻辑关系，而链式存储结构则是通过指针来间接反映数据元素之间的逻辑关系。 16．给定一组权值 : 23, 15, 66, 07, 11, 45, 33, 52, 39, 26, 58, 试构造一棵具有最小带权外部路径长度的扩充 4叉树 , 要求该 4叉树中所有内部结点的度都是 4, 所有外部结点的度都是 0。 这棵扩充 4 叉树的带权外部路径长度是多少 ? 【解答】 仿照霍夫曼树的构造方法来构造扩充 4 叉树，每次合并 4 个结点。 17. 已知序列 (35， 78， 12， 26， 66， 41， 66， 58)，请写出对该序列采用选择排序方法进行升序排序时各趟的结果。 【解答】 原始序列： 35， 78， 12， 26， 90， 41， 66， 58 第 — 趟后： 12， 78， 35， 26， 90， 41， 66， 58 第二趟后： 12， 26， 35， 78， 90， 41， 66， 58 ， 第三趟后： 12， 26， 35， 78， 90， 41， 66， 58 第四趟后： 12， 26， 35， 41， 90， 78， 66， 58 第五趟后： 12， 26， 35， 41， 58， 78， 66， 90 第六趟后： 12， 26， 35， 41， 58， 66， 78， 90 第七趟后： 12， 26， 35， 41， 58， 66， 78， 90 18. 数据逻辑结构包括哪三种类型。 树形结构和图形结构合称为什么。 【解答】 包括线性结构、树形结构和图形结构。 树形结构和图形结构合称为非线 性结构 19 . 请分别叙述在一个连续顺序文件中采用顺序查找法、折半查找法和分块查找法查找一个记录，该文件记录应该满足什么要求。 【解答】 采用顺序查找法：文件中记录可以任意次序存放。 采用折半查找法：文件中的记录必须按照关键字值从小到大或从大到小有序存放。 采用分块查找法：将文件分成若干段，每一块中的记录可以任意存放，但块与块之间必须按照关键字从小到大或从大到小的次序存放，即前一块中的所有记录的关键字值必须小于后一块中所有记录的关键字值。 20. 有向图的邻接表如下 试给出至少两个拓扑序列。 【解答】 V1 V2 V3 V4 V5 V6 V1 V3 V2 V4 V5 V6 五、算法题 1. 已知非空双向循环链表最左边那个链结点的指针为 list,请写一逆置该双向循环链表的算法 【解答】 2. 借助栈将输入任意一个非负的十进制数 ,打印输出与其等值的八进制。 【解答】 conversion( ) {InitStack(s)。 scanf(%d,n)。 while(n) {Push(S,n%8)。 n=n/8。 } while(!StackEmpty(s)) {Pop(s,X)。 priintf(%d,X) } } 3. 设有一个表头指针为 h的单链表。 试设计一个算法，通过遍历一趟链表，将链表中所有结点的链接方向逆转，如下图所示。 要求逆转结果链表的表头指针 h指向原链表的最后一个结点。 解答 1】 templateclass Type void ListType :: Inverse ( ) { if ( first == NULL ) return。 ListNodeType *p = first→ link。 , *pr = NULL。 while ( p != NULL ) { first→ link = pr。 //逆转 first 指针 pr = first。 first = p。 p = p→ link。 //指针前移 } } 【解答 2】 templateclass Type void ListType :: Inverse ( ) { ListNodeType *p, *head = new ListNodeType ( )。 while ( first != NULL ) { p = first。 first = first→ link。 //摘下 first 链头结点 p→ link = head→ link。 head→ link = p。 //插入 head 链前端 } first = head→ link。 delete head。 //重置 first } 4. 有 — 个循环双链表，每个结点由两个指针 (nght 和 left)以及关键字 (key)构成， p指向其中某一结点，编写一个函数从该循环双链表中删除 p 所指向的结点。 【解答】 本题的关 键是找出 p 所指结点的前后结点，这可以循环指针找到。 实现本题功能的函数如下： struct dlist { int key。 struct dlist *left,*right。 } void delnode(p) struct dlist *p。 { struct dlist *q,*r。 q=p。 while(qright!=p)q=qright。 r=p。 while(rleft!=p)r=rleft。 qright=r。 rleft=q。 free(p)。 } while(rleft!=p)r=rleft。 qright=r。 rleft=q。 free(p)。 } 5. 已知一个顺序表Ａ中的元素按值非递减有序，编写一个函数插入一个元素Ｘ后保持该顺序表是有序的 【解答】 define MAX 100 typedef int vector[MAX] void insert(vector A,int n,x) { int,j。 if(x=A[n])A[n+1]=x。 else { i=1。 while(x=A[i])i++。 for(j=n。 j=i。 j)A[j+1]=A[j]。 A[i]=x。 n++。 } } 6. 试写出后序遍历二。