《《数据结构》复习资料.docx》由会员分享，可在线阅读，更多相关《《数据结构》复习资料.docx（15页珍藏版）》请在三一办公上搜索。
1、数据结构复习资料1一、选择题1. 一棵二叉树中第6层上最多有()个结点。A. 2B. 31C. 32D. 642. 顺序表中数据元素的存取方式为()。A. 随机存取B. 顺序存取C. 索引存取D. 连续存取3. 设有无向图 G=(V,E)，其中顶点集合 V=a,b,c,d,e,f，边集合 E=(a,b), (a,e), (a,c), (b,e), (c,f), (f,d), (e,d)。对G进行深度优先遍历，正确的遍历序列是()。A. a,b,e,c,d,fB. a,c,f,e,b,dC. a,e,b,c,f,dD. a,e,d,f,c,b4. 在待排元素序列基本有序的前提下，效率最高的排序方
2、法是()。A. 插入B. 选择C. 快速D. 归并5. 设表中含100个数据元素，用折半查找法进行查找，则所需最大比较次数为()。A. 50B. 25C. 10D. 76. 设哈希表地址范围为019，哈希函数H(key)=key%17，使用二次探测再散列法处理冲突。若表中已存放有关键字值为6、22、38. 55的记录，则再放入关键字值为72的记录时，其存 放地址应为（）。A. 2B. 3C. 4D. 7E. 8F. 以上都不对7. 设对下图从顶点a出发进行深度优先遍历，则（）是可能得到的遍历序列。A. acfgdebB. abcdefgC. acdgbefD. abefgcd8. 若需在O（n
3、log2n）的时间内完成对数组的排序，且要求排序是稳定的，则可选择的排序方 法是（）。A. 快速排序B. 堆排序C. 归并排序D. 直接插入排序9. 设有一组关键字值(46,79,56,38,40,84)，则用堆排序的方法建立的初始堆为()。A. 79,46,56,38,40,84B. 84,79,56,38,40,46C. 84,79,56,46,40,38D. 84,56,79,40,46,3810. 设广义表 L=(a,(),b,(c,d,e)，则 Head(Tail(Tail(L)的值为()。A. bB. cC. (c)D. (c,d,e)11. 在树形结构中，数据元素间存在()的关系
4、。A. 一对一B. 一对多C. 多对多D. 除同属一个集合外别无关系12. 一棵度为3的树中，度为3的结点有2个，度为2的结点有2个，度为1的结点有2个， 则度为0的结点有()。A. 5个B. 6个C. 7个D. 8个13. ()是数据的不可分割的最小单位。A. 数据元素B. 数据对象C. 数据项D. 数据结构14. 直接插入排序在最好情况下的时间复杂度为()。A. O(logn)B. O(n)C. O(n*logn)D. O(n2)15. 以下属单链表优点的是()。A. 顺序存取B. 插入操作能在O(1)的时间复杂度上完成C. 插入时不需移动数据元素D. 节省存储空间16. 在长为n的顺序表
5、中删除一个数据元素，平均需移动()个数据元素。A. nB. n-1C. n/217. 若采用顺序映象，则数据元素在内存中占用的存储空间（）。A. 一定连续B. 一定不连续C. 可连续可不连续18. 若用一个大小为6的数组来实现循环队列，且当前队尾指针rear和队头指针front的值 分别为0和3，当从队列中删除一个元素，再加入两个元素后，rear和front的值分别为（）。A. 1和 5B. 2 和 4C. 4 和 2D. 5和119. 串的长度是指（）。A. 串中所含不同字母的个数B. 串中所含字符的个数C. 串中所含不同字符的个数D. 串中所含非空格字符的个数20. 设在一不带头结点的链队
6、列中，front和rear分别为其队头和队尾指针，则判定该队中 只有一个结点的条件是（）。A. front-nextB. rear-nextC. front=rearD. front!二rear二、填空题1. 具有N个结点的无向完全图共有 条边。2. 数据结构课程是研究数据的、等三个方面的内容。3. 对一棵二叉排序树进行中序遍历时，得到的结点序列是一个。4. 已知二维数组a108采用行优先存储方式，每个元素占2个存储单元，第一个元素的 存储地址是1012，则元素a45的存储地址为。5. 画出具有3个结点的二叉树的所有形态：。6. 对于一个单链接存储的线性表，假定表头指针指向链表的第一个结点，则
7、在表头插入结点 的时间复杂度为，在表尾插入结点的时间复杂度为。7. 已知完全二叉树的第8层有8个结点，则其叶子结点数是。三、问答题1. 假设将循环队列定义为：以域变量rear和length分别指示循环队列中队尾元素的位置和内含元素的 个数，试写出其入队和出队算法(在出队算法中要返回队头元素)。2. 设有上三角矩阵(aij)nxn，将其上三角元素逐行存于数组Bm中(m充分大)，使得Bk=aij,求用 i和j表示k的下标变换公式。3. 设n为正整数，则在下面的程序段中，语句“a+=2;”的频度为多少？for(x=0;xn;+x)for(y=0;y=n-1B . e=n-2C .e=n-3D . e
8、=n-43.能采用二分查找的数据结构是（A .线性表B.二叉树C.有序表D .哈希表4.下列哪一个不属于算法的性质（）。A.输入性B.输出性C.可执行性D.可修改性5.一棵有n （n0）个结点的满二叉树共有（）个叶子结点。A.2nB.2n-1C.2n+1D. (n-1)/26.假设指针p指向单链表中的某一结点，若在p指针的后面插入一个新结点q,只需修改下列哪个指针值即可（）。A.p=q;q=p.next;B. p=q.next;q.next二p.nextC.p.next=q;q.next二p.next;D. q.next二p.next;p.next二q;7.若进栈系列为：a,b, c, d,则
9、下列哪一个不可能是出栈系列（）。A.a, b, c, dB. c, d, b, aC. a, c, d, bD. c, a, b, d8. 将一个递归算法改为对应的非递归算法时，通常需要使用()。A. 栈B.队列C.循环队列D.优先队列9. 在循环队列中用数组A0.m-1存放队列元素，其队头和队尾指针分别为front和rear,则当前队列中的元素个数是()。A. (front rear + 1) % mB. (rear - front + 1) % mC. (front - rear + m) % mD. (rear - front + m) % m10. n个顶点的连通图至少有()条边A.
10、n-1B. nC. n+1D.0二应用题1. 对给定的一组权值W=(5, 2, 9, 11, 8, 3, 7),试构造相应的哈夫曼树，并计算它的 带权路径长度。2. 已知一组元素为(46,25,78,62,12,37,70,29),试画出按元素排列次序插入生成的一棵二 叉排序树。3. 设散列表的长度m=13；散列函数为H(K)=Kmodm,给定的关键码序列为19, 14, 23, 01, 68, 20, 84, 27, 55, 11,试画出用线性探查法解决冲突时所构造的散列表。三. 算法设计题1. 设计一个算法，通过一趟遍历在单链表中确定值最大的结点。一. 选择题1. C2.A3.B4.D5.
11、B6.C7.D8.A9.D10.A二. 应用题1.构造的哈夫曼树如图：树的带权路径长度为：WPL=2X4+3X4+5X3+7X3+8X3+9X2+11X2 =1202. 解答：3. 解答：设散列表的长度m=13；散列函数为H(K)=K mod m,给定的关键码序列为19,14,23,01,68,20,84,27,55,11,则有H(19)=6，成功；H(14)=1,成功；H(23)=10,成功；H(01)=1,冲突，=2,成功； H(68)=3,成功；H(20)=7，成功;H(84)=6，冲突，=7,冲突，=8,成功；H(27)=1，冲突，=2，冲突，=3，冲突，=4，成功；H(55)=3，冲
12、突，=4，冲突，=5，成功；H(11)=11,成功。1401叫2755192084I 2311(1) (2) (1) (4) (3) (1) (1) (3)(1)三. 算法设计题1.【解答】ElemType Max (LinkList L )(/假定第一个结点中数据具有最大值 if(L-next=NULL) return NULL;pmax=L-next; p=L-next-next;/如果下一个结点存在while(p != NULL )(如果p的值大于pmax的值，则重新赋值 if(p-data pmax-data) pmax=p;遍历链表p=p-next;return pmax-data;
13、数据结构复习资料3一.应用题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)=k
14、mod 12,键值序列为(25, 37, 52, 43, 84, 99, 120, 15, 26, 11, 70, 82),采用拉链法处理冲突，试构造开散列表，并计算查找成功的平均查找长度。二、算法设计题 1.设计一个算法，在顺序线性表L中删除第i个元素，并返回其值。一.应用题1.二叉树的构造过程如图:2.3.A,B,C,D,F,EA,B,D,E,F,C深度优先搜索得到的顶点序列:广度优先搜索得到的顶点序列:解答：按Prim算法求最小生成树的过程如下:4.解答：初始： 47, 23, 2, 15, 98, 57, 22, 6, 12.第 趟：2,【23, 47, 15, 98, 57, 22,
15、 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,
16、 98 5.解答:H(25)=1, H(37)=1, H(52)=4, H(43)=7, H(84)=0, H(99)=3, H(120)=0, H(15)=3,H(26)=2, H(11)=11, H(70)=10, H(82)=10。构造的开散列表如下：二、算法设计题1.【解答】Status ListDelete_Sq(SqList &L, int i, ElemType &e) (if(iL.length) teturn ERROR;p = &L.elemi-1;e = *p;q = L.elem +L.length-1;for(+p;p=q;+p) *(p+1) = *p;-L.length;return OK;
