《数据结构》复习资料.doc

数据结构》复习资料1 一、选择题 1. 一棵二叉树中第6层上最多有()个结点。 A. 2 B. 31 C. 32 D. 64 2. 顺序表中数据元素的存取方式为()。 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,f B. a,c,f,e,b,d C. a,e,b,c,f,d D. a,e,d,f,c,b 4. 在待排元素序列基本有序的前提下，效率最高的排序方法是()。 A. 插入 B. 选择 C. 快速 D. 归并 5. 设表中含100个数据元素，用折半查找法进行查找，则所需最大比较次数为()。 A. 50 B. 25 C. 10 D. 7 6. 设哈希表地址范围为0~19，哈希函数H(key)=key%17，使用二次探测再散列法处理冲突。 若表中已存放有关键字值为6、22、38、55的记录，则再放入关键字值为72的记录时，其存放地址应为()。 A. 2 B. 3 C. 4 D. 7 E. 8 F. 以上都不对 7. 设对下图从顶点a出发进行深度优先遍历，则()是可能得到的遍历序列。 B. abcdefg C. acdgbef D. abefgcd 8. 若需在O(nlog2n)的时间内完成对数组的排序，且要求排序是稳定的，则可选择的排序方 法是()。 A. 快速排序 B. 堆排序 C. 归并排序 D. 直接插入排序 9. 设有一组关键字值(46,79,56,3&40,84),则用堆排序的方法建立的初始堆为()。 A. 79,46,56,38,40,84 B. 84,79,56,38,40,46 C. 84,79,56,46,40,38 D. 84,56,79,40,46,38 10. 设广义表L=((a,()),b,(c,d,e)),则Head(Tail(Tail(L)))的值为()) A. b B. c C. (c) D. (c,d,e) 11. 在树形结构中，数据元素间存在（）的关系。 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的顺序表中删除一个数据元素，平均需移动（）个数据元素。 A. n B. n-1 C. n/2 D. (n-1)/2 17. 若采用顺序映象，则数据元素在内存中占用的存储空间（）。 A. 一定连续 B. 一定不连续 C. 可连续可不连续 18. 若用一个大小为6的数组来实现循环队列，且当前队尾指针rear和队头指针front的值分别为0和3,当从队列中删除一个元素，再加入两个元素后，rear和front的值分别为（）。 A. 1和5 B. 2和4 C. 4和2 D. 5和1 19. 串的长度是指（）。 A. 串中所含不同字母的个数 B. 串中所含字符的个数 C. 串中所含不同字符的个数 D. 串中所含非空格字符的个数 20. 设在一不带头结点的链队列中，front和rear分别为其队头和队尾指针，则判定该队中只有一个结点的条件是（）。 A. front->next B. rear->next C. front==rear D. front!=rear 二、填空题 1. 具有N个结点的无向完全图共有条边。 2．数据结构课程是研究数据的、、等三个方面的内容。 3．对一棵二叉排序树进行中序遍历时,得到的结点序列是一个。 4. 已知二维数组a[10][8]采用行优先存储方式，每个元素占2个存储单元，第一个元素的存储地址是1012，则元素a[4][5]的存储地址为。 5．画出具有3个结点的二叉树的所有形态：。 6．对于一个单链接存储的线性表，假定表头指针指向链表的第一个结点，则在表头插入结点 的时间复杂度为，在表尾插入结点的时间复杂度为。 7．已知完全二叉树的第8层有8个结点，则其叶子结点数是。 三、问答题 1. 假设将循环队列定义为：以域变量rear和length分别指示循环队列中队尾元素的位置和内含元素的个数，试写出其入队和出队算法(在出队算法中要返回队头元素)。 2. 设有上三角矩阵(aij)nxn，将其上三角元素逐行存于数组B[m]中(m充分大)，使得B[k]=aij,求用 i和j表示K的下标变换公式。 3. 设n为正整数，则在下面的程序段中，语句“a+=2;”的频度为多少？ for(x=0;x=n-4 3．能采用二分查找的数据结构是（ ) A.线性表 B.二叉树 C.有序表 4．下列哪一个不属于算法的性质（ ）。 A.输入性 B.输出性 C.可执行性 A.e>=n-1 B.e>=n-2 C.e>=n-3 D.哈希表 D.可修改性 5. —棵有n（n>0）个结点的满二叉树共有（）个叶子结点。 A.2n B.2n-1 C.2n+1 D.(n-1)/2 6. 假设指针p指向单链表中的某一结点，若在p指针的后面插入一个新结点q,只需修改下列哪个指针值即可（）。 A．p=q;q=p.next;B．p=q.next;q.next=p.next C．p.next=q;q.next=p.next;D．q.next=p.next;p.next=q; 7. 若进栈系列为：a,b,c,d,则下列哪一个不可能是出栈系列()。 8. 将一个递归算法改为对应的非递归算法时，通常需要使用()。 A.栈B.队列C.循环队列D.优先队列 则当前队列中的元素个数是( A.(front-rear+1)%m C.(front-rear+m)%m 10.n个顶点的连通图至少有( 9. 在循环队列中用数组A[O..m-l]存放队列元素，其队头和队尾指针分别为front和rear,)。 B.(rear-front+1)%m D.(rear-front+m)%m A.n-1 B.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.B6.C7.D8.A9.D10.A 二•应用题 1.构造的哈夫曼树如图： 树的带权路径长度为：WPL=2X4+3X4+5X3+7X3+8X3+9X2+11X2=120 2. 解答： 3. 解答： 设散列表的长度m=13；散列函数为H(K)=Kmodm,给定的关键码序列为 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，冲突，=4,冲突，=5,成功；H(11)=11,成功。 0123456789101112 14 01 68|27 55 19 20 84 I23 11 (1)(2)(1)(4)(3)(1)(1)(3)(1)(1)三．算法设计题 1.【解答】ElemTypeMax(LinkListL) { //假定第一个结点中数据具有最大值 if(L->next==NULL)returnNULL; pmax=L->next;p=L->next->next; ////如果下一个结点存在 while(p!=NULL){ //如果p的值大于pmax的值，则重新赋值 if(p->data>pmax->data)pmax=p; //遍历链表 p=p->next; } returnpmax->data; 数据结构》复习资料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)=kmod12,键值序列为(25,37,52,43,84,99,120,15,26,11, 70,82)，采用拉链法处理冲突，试构造开散列表，并计算查找成功的平均查找长度。 二、算法设计题1•设计一个算法，在顺序线性表L中删除第i个元素，并返回其值。 答案 一．应用题 1. 二叉树的构造过程如图： A,B,D,E,F,C 2. 深度优先搜索得到的顶点序列： 广度优先搜索得到的顶点序列： A,B,C,D,F,E 3. 解答：按Prim算法求最小生成树的过程如下: 初始：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】 解答： 4. 第八趟：2，6，12，15，22，23，47，57，【98】 最后所得：2，6，12，15，22，23，47，57，98 二、算法设计题 H(120)=0,H(15)=3, 1.【解答】 &L,inti,ElemType&e) StatusListDelete_Sq(SqList if(i<1||i>L.length)teturnERROR; p=&L.elem[i-1]; e=*p; q=L.elem+L.length-1;for(++p;p<=q;++p)*(p+1)=*p; --L.length; returnOK;