《数据结构模拟试题8》由会员分享，可在线阅读，更多相关《数据结构模拟试题8（7页珍藏版）》请在金锄头文库上搜索。
1、本试卷分两部分，第一部分为选择题, 考试时间150分钟。数据结构模拟试题(八)第二部分为非选择题；选择题20分，非选择题80分，满分100分第一部分选择题一、单项选择题(本大题共20小题，每小题1分，共20分)在每小题列岀的四个选项中只有一个选项是符合题目要来的，请将正确选项前的字母填在题后的括号内 1 数据元素是数据的基本单位，其中 数据项【】A. 只能包含一个B .不包含C.可以包含多个D .可以包含也可以不包含2下列时间复杂度中复杂度最高的是【】A. O (I )B. O (n)C. O (log 2n)D. O (n2 )3相对于顺序存储而言，链接存储的优点是【】A.随机存取B.节约空
2、间C.增、删操作方便D.节点间关系简单4带头节点的单链表 head为空的判定条件是【】A. head = NULLB. head - next = NULLC. head - next = headD. head ! = NULL5.个栈的入栈序列是a，b，c，d，e,则栈的不可能的输出序列是【6.栈与一般线性表的区别主要在【】A.元素个数B .元素类型C.逻辑结构D .插入、删除元素的位置7.串的模式匹配是指【】A. edcbaB. decbaC. dceabD. abcdeA. 判断两个串是否相等B. 对两个串进行大小比较C. 找某字符在串中第一次岀现的位置D. 找某子串在主串中第一次岀现
3、的位置&以下说法正确的是【】A.空串与空格串是相同的B.“ fox是“ Foxbase ” 的子串C.空串是零个字符的串D.空串长度等于19.对于二维数组a【4【4，数组的元素起始地址为Ioc00=1000, loc22A.1000B. 1010C.1008D . 102010.广义表C=(A, B，()的表头是【】A.CB ()C . AD.B11 具有n个节点的完全二叉树的深度为【】A. L log 2n+lB. log 2n+l为【 】C. log 2nD. l log 2n12.在具有n (n 1)为个节点的完全二叉树中，节点i(21n)的左孩子节点是【】A. 2iC.不存在B. 2i
4、+ 1 D .是 2i -113对于任何一棵二叉树，如果其终端节点数为A. m= n 十 1B. n=m+1n，度为2的节点数为m则【 】C. n = 2m+ 1D. m=2n+ 114已知一有向图的邻接表如下所示，根据算法，则从顶点V1岀发按广度忧先遍历的节点序列是【A.V1,V2,V3,V4,V5B.V1,V3,V2,V4,V5C.V1,V3,V4,V5,V2D.V1,V4,V3,V5,V215.堆排序是一种排序【】A.插入B.选择C.交换D.归并16快速排序的方法要求被排序的数据存储【A.必须是顺序B.必须是链表C.顺序或链表D.二叉树】17.有一个有序表为1 ,3,9,12,32,41
5、,45,62,75,77,82,95,100 当二分查找值为 82的节点时，次比较后查找成功【】A. 1B. 2C. 4D. 818顺序查找法适合于存储结构为的线性表【】A.散列存储C.压缩存储B.顺序存储或链接存储D.索引存储19在顺序文件中，所有逻辑记录在存储介质中的实际顺序与它们进入存储器的顺序【】A. 致C.无关B.不必一致D.不能一致20.存放在外存中的数据的组织结构是【】A.数组C.文件B.表D.链表第二部分非选择题二、填空题（本大题共 15小题，每空1分，共20分）1算法的时间复杂度不仅仅依赖于何题的 ，也取决于输入实例的 。2选择合适的 是解决应用问题的关键步骤。3链式存储方式
6、中，存储每个节点需要两个域，一是 ，二是。4 当程序中同时使用两个栈时，可以将两个栈的设在向量空间的两端，仅当两个相遇时，才会发生上溢。5稀疏矩阵的三元组中，第 3列存储的是稀疏数组中的 。6. 设 S = IAM A TEACHER”，其长度等于 。7. 在串的运算中， strcmp （ aaa ”， aabb ” 的值。&将一棵树转换成一棵二叉树后，二叉树根节点没有 子树。9对于一棵含有 n个节点的完全二叉树，它的高度是 。10三个节点可以组成中不同形态的树。11. n个节点的连通图至少有 条边。12. n个顶点e条边的图若采用邻接矩阵存储，则空间复杂度为 。13 堆排序的时间复杂度为 。
7、14. 对n个不同的排序码进行冒泡排序，在元素无序的情况下比较的次数为一。15. 常用的处理冲突的两类方法是 和。16. 文件的操作主要有两类： 和维护。三、名词解释（本大题共 5小题，每题3分，共15分）1 线性表2. 循环队列3. 对称矩阵4. 中序遍历四、简答题（本大题共 5小题，每题5分，共25分）1 简述头指针、头节点、开始节点的区别。2比较栈和队列的异同点。3简述算法复杂度的评价方法。4.已知某二又树的前根排序序列是abedc,中根排序序列是 ebdac,根据这两个序列能否惟一确定一棵二叉树，若能，请画岀。5 写岀右图的所有拓扑序列。五、应用题（本大题共 2小题，每题10分，共20
8、分）1 输岀二叉树中值为x节点的父节点。2.设计实现SHELL排序的函数。数据结构模拟试题（八）参考答案一、单项选择题l C2.D3 .C4.D5 .C6. D7.D8 .C9 ,.Dl0.Cll Al2.Cl3 .Bl4.Bl5.Cl6 Al7.Cl8 .Bl9.C20.C、填空题1 .规模初始状态2 .数据结构3.指针域数据域4 .栈底栈顶5.非零元素6 . 147. V 08 .右9 .匚 log 2 n+110 . 211 . n l12 . O (n2)13 . O (nlogn )14 . n (n-1 ) /215 .开放地址法拉链法16 .检索三、名词解释I 是由n （n=0）
9、个数据元素（节点） al ，a2，an组成的有限序列。它是一种线性结构。2为克服顺序队列中“假上溢”现象，将向量空间想象为个首尾相接的圆环，存储在其中的队列称为循环 队列。3在一个A阶方阵A中，若元素满足aij= aji（O=i，jdata=x)stop+,stop.p=t,stop.tag=0;t=t-left;if (t!=null & t-data=x)printf(father node is %d,x),for(i= 1;idata); break, elsewhile(top0 & stop.tag= l ) top-;if (top0) stop.tag= i;t=stop.p-
10、right;2. sortshell(ftype r,int n)int d=n,f;while(d1)d=d/2;dor=1;for(i= 1;irj.key)x=ri;ri=rj； rj=x;while(!f);for (i= 1;i=n;i+)printf(%dn,ri.key);Whe n you are old and grey and full of sleep,And no ddi ng by the fire, take dow n this book,And slowly read, and dream of the soft lookYour eyes had once,
11、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 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 d
