数据结构模拟试题四及答案(共5页).docx

《数据结构模拟试题四及答案(共5页).docx》由会员分享，可在线阅读，更多相关《数据结构模拟试题四及答案(共5页).docx（5页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、精选优质文档-倾情为你奉上数据结构模拟试题四一、( 共30分，每题2分)单项选择题1循环队列用数组A0.m-1存放其元素值，已知其头尾指针分别为front和rear，则当前元素个数为（）A(rear-front+m) mod m Brear-front+1 Crear-front-1 Drear-front E以上答案都不对2数据结构中，与所使用的计算机无关的是数据的（）A存储结构 B物理结构 C逻辑结构 D物理结构和存储结构E以上答案都不对3在具有n个结点的单链表中，实现（）的操作，其算法的时间复杂度都是O(n)。A遍历链表和求链表的第i个结点 B在地址为p的结点之后插入一个结点 C删除开始

2、结点 D删除地址为p的结点的后继结点E以上答案都不对4某二叉树的前序遍历序列为IJKLMNO，中序遍历序列为JLKINMO，则后序遍历序列为（）AJLKMNOI BLKNJOMI CLKJNOMI DLKNOJMI E以上答案都不对5设n阶方阵是一个上三角矩阵，则需存储的元素个数为（）An Bn*n Cn*n/2 Dn(n+1)/2 E以上答案都不对6串的“模式匹配”是指（）A判两个串是否相等 B对两个串进行大小比较 C找某字符在串中第一次出现位置 D找某子串在主串中第一次出现的位置 E以上答案都不对7有n个结点的无向图的边数最多为（）An+1 Bn(n-1)/2 Cn(n+1) D2n(n+

3、1) E以上答案都不对8多关键字文件是指（）A有多个主关键字 B有多个次关键字 C有一个主关键字多个次关键字D有多个主关键字和多个次关键字 E以上答案都不对9某顺序存储的表格中有90000个元素，已按关键字值额定升序排列，假定对每个元素进行查找的概率是相同的，且每个元素的关键字的值皆不相同。用顺序查找法查找时，平均比较次数约为（）A25000 B30000 C45000 D90000 E以上答案都不对10对于序列(49,38,65,97,76,13,27,50)按由小到大进行排序，（）是初始步长d=4的希尔排序法第一趟的结果。A. 49,76,65,13,27,50,97,38 B. 13,2

4、7,38,49,50,65,76,97C. 97,76,65,50,49,38,27,13D. 49,13,27,50,76,38,65,97E. 以上答案都不对11下列排序算法中，第一趟排序完毕后，其最大或最小元素一定在其最终位置的算法是（）A归并排序 B直接插入排序 C快速排序 D冒泡排序 E以上答案都不对12关于树和二叉树的有序性，正确的结论是（）A. 树和二叉树都是有序的 B树和二叉树都可能是有序的C树和二叉树都是无序的 D二叉树是有序的，树可能是有序的，也可能是无序的 E以上答案都不对13在一个图中，所有顶点的度数之和与图的边数的比是（）A1:2 B1:1 C2:1 D4:1 E以上

5、答案都不对14若一组纪录的关键码为（46，79，56，38，40，84），则利用快速排序的方法，以第一个纪录为基准得到的一次划分结果为（）A38，40，46，56，79，84 B40，38，46，79，56，84C40，38，46，56，79，84 D40，38，46，84，56，79E以上答案都不对15从理论上讲，将数据以（）结构存放，则查找一个数据所用时间不依赖于数据个数n。A二叉查找树 B链表 C二叉树 D哈希表 E以上答案都不对二、（共40分，每空2分）填空题1二分查找算法的时间复杂度为（ ）2在单链表中，申请到新结点p，将p指向的结点后插到s所指结点的操作，其一是p-next=s-n

6、ext，其二是（ ）。3对一般树和森林的后序遍历序列的次序与对应的二叉树的（ ）遍历次序相同。4设二维数组A10.20,5.10按行优先存储，每个元素占4个单元，A10,5的地址为160，则A15,10的地址为（ ）。5线性结构反映结点间的逻辑关系是（ ）的，非线性结构反映结点间的逻辑关系是（ ）的。6赫夫曼树是带权路径长度（ ）的二叉树。7前序为abc且后序为cba的二叉树共有（ ）棵。8已知完全二叉树的高度为8，第7层有10个叶子结点，则二叉树的总结点数至少是（ ）。9已知二叉树有50个叶子结点，且仅有一个孩子的结点数为30，则总结点数为（ ）。10具有m个叶子结点的赫夫曼树共有（ ）个结

7、点。11从一棵二叉树的前序序列和（ ）可唯一确定这棵二叉树。设某二叉树的后序遍历为ABKCBPM，则可知该二叉树的根为（ ）。12设广义表C=(x,(a,b),(x,(a,b),y),则C的长度为（ ），深度为（ ）。13设有一稠密图G，则G采用（ ）存储较省空间。14在插入和选择排序中，若初始数据基本正序，则选用（ ）；若初始数据基本反序，则选用（ ）。15有n结点的二叉链表中，空指针域有（ ）个；利用这些空指针域，存放指向结点在中序次序下的前趋或后继的指针，这种附加的指针称为（ ）。三、（10分）已知一棵度为m的树中有N1个度为1的结点，N2个度为2的结点，Nm个度为m的结点，问该树中有多

8、少个叶子结点。请写出推导过程。四、（15分）给定字母a,b,c,d,e的使用频率为0.09,0.17,0.2,0.23, 0.31。设计以该权值为基础的赫夫曼树，并给出赫夫曼编码。五、（15分）设散列表的长度为13，散列函数为H(K)=K%13，给定的关键字序列为：19，14，23，01，68，20，84，27，55，11，10，79。试画出用线性探测再散列解决冲突时所构成的散列表。并求等概率情况下这种方法查找成功和查找不成功时的平均查找长度。六、（15分）已知奇偶交换排序如下所述：第一趟对序列中所有奇数项i扫描，将ai和ai+1进行比较；第二趟对序列中所有偶数项i扫描，将ai和ai+1进行比

9、较。每次比较时若 aiai+1，则将两者交换。第三趟对所有奇数项，第四趟对所有偶数项，如此重复，直至整个序列有序。1) 写出奇偶交换排序算法，设待排序的n个元素存放在数组a1.n 中。2) 说明你的排序方法的结束条件3) 若待排序的初始序列已按关键字从小到大有序，则关键字的比较次数是多少？七、（10分）已知长度为n的线性表A采用顺序存储结构，并且元素按值大小非递减排列，下面的算法删除线性表中多余的值相同的元素。请在算法中空白处填入适当内容，使之能够正常工作。void DEL(int An) / 设A1An存放着n个元素 int i=1;while (1) do if (Ai!=Ai+1) i+

10、; else /查找满足条件的元素 for (2) Aj-1=Aj;/删除第i+1个元素（满足条件的元素） (3) /修改线性表的长度 八、（15分）设计算法， 已知一棵以二叉链表存储的二叉树，root指向根结点，p指向二叉树中任一结点，编写算法求从根结点到p所指结点之间的路径（要求输出该路径上每个结点的数据）。数据结构模拟试题四参考答案一、( 共30分，每题2分)单项选择题1A 2C 3A 4C 5D 6D 7B 8C 9C 10D 11D 12D 13C 14C 15 D二、（共40分，每空2分）填空题1. log2n2. s-next=p3. 中序4. 3005. 一对一的，一对多或多对

11、多的6. 最小7. 48. 2359. 12910. 2m-111. 中序，M12. 2，413. 邻接矩阵14. 插入排序，选择排序15. n+1,线索三、（10分）解：设N为总结点数，N0为叶子结点数则：N=N0+N1+N2+Nm又有：N-1=度的总数，则：N-1=N1*1+N2*2+Nm*m则有：N0=1+N2+2N3+(m-1)Nm四、（15分）ccdeabc(00)d(01)a(100)b(101)e(11)五、（15分）线性探测再散列的散列表：0 1 2 3 4 5 6 7 8 9 10 11 1214168275519208479231110121431139113查找成功的平均

12、长度为ASL=1/12（1*6+2*1+3*3+4*1+9）=2.5查找不成功的平均长度为ASL=1/13（1+2+3+4.+13）=7六（15分）（1）void oesort ( int an)int i,flag;doflag=0;for (i=1;iai+1) flag=1 ;t=ai+1;ai+1=ai;ai=t;for (i=2;iai+1)flag=1;t=ai+1;ai+1=ai;ai=t; while (flag);（2） 两趟排序无交换出现（3） n-1次七（10分）（1）i=n （2）(j=i+1;jlchild;if (top0) q=stacktop-1; if (tagtop-1=1) if (q=p) for (i=0;idata);find=1; else top-; if (top0&!find) q=q-rchild; tagtop-1=1;专心-专注-专业