数据结构模拟试题3

1、数据结构模拟试题(三)本试卷分两部分，第一部分为选择题，第二部分为非选择题。选择题20分，非选择题80分，满分100分 考试时间150分钟。第一部分选择题一、单项选择题(本大题共20 题，每小题1分，共20分)在每小题列岀的四个选项中只有一个选项是符合题目要求的，请将正确选项前的字母填在题后的括号内。I 若对数据结构采用了顺序存储，第一个节点的地址为1001，每个节点的值需占用 2个存储单元，则第三个节点的起始地址为【】A. 1003B. 1005C. 1006D. 10072下列算法的时间复杂度是【】for(i = 0;i<n； i + + )for(j= 0;j<m;j+)ci

2、j = 0；A. O(1)B. O(m+ n)C. O(log mn)D. O(n)3在有n个节点的顺序表中做插入、删除运算，平均时间复杂度为【】A. 0(1 )B . O(n)C. O(log 2n)D. O(n2)4在一个单链表中，若P所至节点不是最后节点，在P之后插入S所指节点，则执行【】A. S->next = P;P->netxt = S;B. S->next = P->next; P = S;C. S->next = P->next; P = S;D. P->next = S; S->next = P;5.经过下列栈的运算后，Stac

3、kTop(s)的值是【】A. aB. bC. 1D. 26. 4个元素进Q队列的顺序是A,B,C,D,进行DEQUEUEA. AB. BC. CD. D7.广义表A=(a),则表尾为【】A. aB.()C.空表D (a)&广义表c=(A,B,(),c的长度为【】A. 1B. 2C. 3D. 49朴素模式匹配算法在最好的情况下的运行时间是A. MB. NC. M+ND. M*NlnitStack(s);Push(s,a);Push(s,b);Push(s);(Q操作后，对头元素是【】10.串是一种特殊的线性表A.可以顺序存储C.可以链接存储,其特殊性体现在【】B.数据元素是一个字符D.数

4、据元素可以是多个字符以一次内循环为单位11.判断线索二叉树中某节点A. P! = nullP有左孩子的条件是【】B. P- > lchild! = nullC. P- > ltag=0D. P- > ltag=112有m个叶节点的霍夫曼树所具有的节点数为【】A.mB.m+lC.2m-1D.2m13.在一个具有n个节点的无向图中，要连通全部节点至少需要 条边。【】A.nB.n+1C.n-1D.n/214采用邻接表存储的图的广度优先遍历类似于二叉树的【】A.先序遍历B.中序遍历C.后序遍历D.层次遍历15.目前以比较为基础的内部排序方法中其比较次数与待排序的记录的初始排列状态无关

5、的是【 A.插入排序C.快速排序16下列关键字序列中A. 16,72,31,23,94,53C. 16,53,23,94,31,7217顺序文件特别适应于【A.磁带存储器C.光盘18索引文件由A.索引表C.索引表和主文件两部分B.二分插入排序D.冒泡排序 是堆。【】.94,23,31,72,16,53D. 16,23,53,31,94,72】B.硬磁盘存储器D.软磁盘存储器构成。【】"B.主文件D.查找表19设有100个元素，用折半查找法进行查找时，最小比较次数是【A. 7B. 4C. 2D. I20.散列函数有一个共同性质，即函数值应当以.A.同等概率C.最小概率.最大概率平均概率

6、取其值域的每个值。【第二部分非选择题二、填空题（本大题共 16小题,每空1分,共20分）1线性表中第一个节点没有直接前趋，称为 .2数据的 结构是独立于计算机的。3当线性表很少做插入删除操作时，应采用 存储结构为好。4带有一个头节点的单链表head为空的条件是 。5对于队列，只能在 插入元素，在 删除元素。6.广义表（a）,（b）,J,（的长度是，深度是。7空串的长度等于。& 称为串的模式匹配。9. 有20个节点的完全二叉树，编号为10的节点的父节点的编号是 。10. 已知完全二叉树的第 7层有10个叶子节点，则整个二叉树的节点数最多是 。11. 具有m个叶节点的霍夫曼树共有 个节点。

7、12设有一稠密图G,则G采用存储较省空间。13图的逆邻接表存储结构只适用于 图。14在堆排序、 和归并排序中，若只从平均情况下速度最快考虑，则应选取 15在堆排序、快速排序和归并排序中，若只从排序结果的稳定性考虑，则应选取方法。16. VSAM勺中文意思是 ，采用作为动态索引结构。三、名词解释（本大题共 5小题，每题3分，共15分）1. 双链表2. 链栈3. 三元组表4. 霍夫曼（Huffman ）树5简单路径四、简答题（本大题共 5小题，每题5分，共25分）1与顺序队列相比，循环队列有哪些优点？2写岀按行优先与列优先顺序存储的三维数组元素ajk的地址计算公式。3.己知二叉树如下图，画出它的中

8、序线索二叉树。4已知一无向图如图所示，根据遍历算法画出从0顶点出发图的DFS生成树和BFS生成树5.试述顺序查找法、折半查找法和分块查找法对被查找元素的要求，每种查找法对长度为 n的表的等概率查找长度是多少。五、应用题（本大题共 2小题，每题10分,共20分）1己知两个单链表 A与B分别表示两个集合，其元素递增排列。设计一个AB交集C, C的元素也是增序的单键表。2输岀二叉树中所有是偶数的叶节点。数据结构模拟试题（三）参考答案、单项选择题1 B2.D3.B4 . B5 . A6. B7. C8.C9 . A10 . B11. C12. C13.C14 . D15 . B16. D17. A18

9、.C19 . D20 . A二、填空题1 .开始节点2.逻辑3.顺序表4.head->next=NULL5 队尾队首6 .347零8.子串的定位运算9. 510.23511. 2m-112.邻接矩阵13有向14.快速排序快速排序15归并排序16.虚拟存储存取方法 B+树三、名词解释1 链表的每个节点结构中有两个链域，一个用来存放节点的直接后继的地址，另一个指向其直接前趋。2栈的链式存储结构称为链栈，它是运算受限的单链表，其插入和删除操作仅限制在表头位置上进行。3若线性表顺序存储的每一个节点均是三元组，则该线性表的存储结构称为三元组表。4. 又称最优二叉树。它是 n个带权叶子节点构成的所有

10、二叉树中带权路径长度WPL最小的二叉树5. 条路径上除了开始顶点和结束顶点外，其余顶点均不相同。四、简答题1 顺序队列中存在“假上溢”现象。因为在入队和出队操作中，头尾指针只增加不减少，致使被删元素的 空间永远无法重新利用。因此，尽管队列中实际的元素个数远远小于向量空间的规模，但也可能由于尾指 针已超越向量空间的上界而不能做入队操作。该现象称为“假上溢”。为充分利用向量空间，克服上述假上溢现象的方法是将向量空间想象为一个首尾相接的圆环，并称这种向 量为循环向量，存储在其中的队列称为循环队列。在循环队列中进行出队、入队操作时，头尾指针仍要加1, 朝前移动。只不过当头尾指针指向向量上界时，其加1操

11、作是指向向量的下界。2. 按行优先存储:Address(aijk)=Address(aOOO)+i*m*n+j*n+k*d按行优先存储：Address(aijk) = Address(aOOO)+ k* l* m+ j* l+i* d4答案:3答案：5.顺序查找：表中元素可以任意存放。查找成功的平均查找长度为(n + I ) /2。折半查找：表中元素必须以关键字的值递增或递减的存放且只能以顺序表存放。查找成功的平均查找长度 为 log 2(n+1)-1 。分块查找：表中每块内的元素可以任意存放，但块于块之间必须以关键字的值递增或递减的存放，即前一 块内所有元素的关键字不能大于(或小于)后一块内

12、任意元素的关键字。若用顺序表查找确定所在块，平 均查找长度为1/2*(n/s+s) + l。若用折半查找确定所在块，平均查找长度为log 2(n/s+1)+s/2 。五、应用题l . node * inter(a,b)node *a, *b;node *p, *q, *r, *s, *c;c=(node * ) malloc (sizeeof(nede);r=c;P=a,q=b;while (p!=null && q!=null)if (p->data < q->data) P=P->next; else if (p->data > q-&g

13、t;data) q=q->next else s=(node *)malloc(sizeof(node);s->data=p->data;r->next=s;P=P->next;q=q_>next;r->next=null;c=c->next;return(c );2. Void outputleaf(t)if(t!=0)outputleaf(lt);outputleaf(rt);if (lt=0&&rt=0)if(t%2=0)printf(“d' ,t);Whe n you are old and grey and fu

14、ll of sleep,And no ddi ng by the fire, take down this book,And slowly read, and dream of the soft lookYour eyes had once, and of their shadows deep;How many loved your mome nts of glad grace,And loved your beauty with love false or true,But one man loved the pilgrim soul in you,And loved the sorrows

15、 of your cha nging face;And bending dow n beside the glow ing bars,Murmur, a little sadly, how love fledAnd paced upon the mountains overheadAnd hid his face amid a crowd of stars.The furthest dista nee in the worldIs not betwee n life and deathBut whe n I sta nd in front of youYet you don't know thatI love you.The furthest dista nee in the worldIs not whe n I sta nd in front of youYet you can't see my loveBut whe n un doubtedly knowing the love from bothYet cannot be together.The furthest dista nee in the worldIs not being apart while being in loveBut whe n I p