数据结构模拟试题四及答案

数据结构仿真问题41、(共计30分，每题2分)个别选题1 .循环队列以阵列A0.m-1保存要素值，在其开头指针分别知道前端和后端时，当前的要素数为()a.(rear-frontm ) mod MB.rear-front 1c.rear-front-1D.rear-front E .以上的答案是错误的2 .在数据结构中，与所使用的计算机无关，使用数据的()a .存储结构b .物理结构c .逻辑结构d .物理结构和存储结构e .以上的答案是错误的3 .在具有n个节点的链表中，实现了()的操作，其算法的时间复杂度均为O(n )。a .在链接表和链接表的第I个节点b .地址为p的节点之后删除节点c .删除开始节点d .地址为p的节点的后续节点e .是错误的。4 .某二叉树前顺扫描序列是IJKLMNO，中顺扫描序列是JLKINMO，后顺扫描序列是()a.jkmnoib.lknjjomic.lkjanomid.lknojmie .以上的答案是错误的5.n如果将下一个方阵设为上三角行列式，则储存的元素数为()A.n B.n*n C.n*n/2 D.n(n 1)/2 E .以上的答案都是错误的6 .字符串的“模式匹配”是指()a .判定两个字符串是否相等b .比较两个字符串的大小c .查找某个字符在字符串中最先出现的位置d .查找某个子字符串在主字符串中最先出现的位置e .以上的回答全部错误7 .具有n个节点的无向图边数最多()A.n 1 B.n(n-1)/2 C.n(n 1) D.2n(n 1) E .以上的答案都是错误的8 .多关键字文件是指()a .具有多个主键的b .具有多个次键的c .具有多个主键的次键d .多个主关键字和多个子关键字e .以上的答案是错误的9 .假设按照某个顺序存储的表中有90000个要素，按照关键字值的额定值的升序排列，各要素的检索概率相同，各要素的关键字值不同。 用逐次检索法检索时，平均比较次数约为()答案A.25000 B.30000 C.45000 D.90000 E .或更高版本是错误的10 .初始步长d=4的希尔排序方法是按阵列(49、38、65、97、76、13、27、50 )的升序排序的第一次结果。a.49，76，65，13，27，50，97，38 b.13，27，38，49，50，65，76，97c.97，76，65，50，49，38，27，13 d.49，13，27，50，76，38，65，97e .上述答案是错误的11 .在下一排序算法中，在第一次排序完成后，最大或最小元素必须位于最终位置的算法是()a .合并排序b .直接插入排序c .快速排序d泡沫排行e .以上的答案是错误的12 .关于树和二叉树的秩序性，正确的结论是()a .树木和二叉树都有秩序b .树木和二叉树也许有秩序c .树和二叉树都无序的d .二叉树有序，树也许有序，也许无序的e .以上的回答是错误的13 .在一个图中，所有顶点的度数和图边数之比为()a.1:2 b.1:1 c.2:1 d.43336301 e .以上所有答案都是错误的14 .在记录集的键码为(46、79、56、38、40、84 )的情况下，以第一记录为基准而得到的分割结果为快速排序的方法()a.38，40，46，56，79，84 b.40，38，46，79，56，84c.40，38，46，56，79，84 d.40，38，46，84，56，79e .上述答案是错误的15 .理论上，如果以()结构存储数据，则检索一个数据所花费的时间不取决于数据的数目n。a .二叉检索树b .链接表c .二叉树d .哈希表e .以上的回答全部错误二、(共计40分，1空间2分)填空问题1 .二元搜索算法的时间复杂度为()2 .在链路列表中，申请新的节点p并将p指定的节点插入s指定的节点的操作是p-next=s-next，其中2个为()3 .到普通树和森林的后列扫描序列的顺序与对应的二叉树的()扫描顺序相同。4 .优先存储每行的二维阵列a 10. 20，5. 10 ，每个元素占据四个单元，其中a 10，5 的地址为160，而a 15，10 的地址为()5 .线性结构反映节点之间的逻辑关系的是()，非线性结构反映节点之间的逻辑关系的是()。6 .霍夫曼树是加权路径长度()的二叉树。序言为abc，后文为cba的二叉树为()本。8 .完全二叉树的高度为8，如果知道第7层有10个叶节点，则二叉树的总结点数至少为()9 .已知二叉树有50个叶节点，只有一个孩子的节点数为30，总结分数为()10 .具有m个叶节点的霍夫曼树有()个节点。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的节点，我们知道这棵树有多少叶子的节点。 请写下导出过程。(15分钟)给出的字符a、b、c、d和e的使用频率是0.09、0.17、0.2、0.23和0.31。 设计了基于该权重的霍夫曼树，给出霍夫曼符号。5、(15分钟)哈希列表的长度为13，哈希函数为H(K)=K，并且给定的关键字序列为19、14、23、01、68、20、84、27、55、11、10、79。 试制了通过线性搜索再哈希解决冲突时构成的哈希表。 求等概率时的该方法求成功与不成功时的平均寻道长度。6.(15分钟)已知的奇偶校验交换次序首先扫描该序列中的奇数项I，并且在第二次扫描该序列中的所有偶数项I并且比较ai和ai 1。 每次比较都要更换aiai 1，两者。 第三次对于所有奇数项目，第四次对于所有偶数项目这样重复，直到整个数组建立秩序。1 )制作奇偶交换排序算法，将要排序的n个要素收纳到排列a1.n中。2 )说明你排序方法的结束条件3 )如果要排序的第一个序列按关键字从小到大的顺序排序，关键字的比较次数是多少？七、(十分)长度为n的线性表a采用顺序存储结构，要素按值的大小呈非递减排列，下一算法删除了线性表中多馀的值相同的要素。 请在算法空白处填写适当的内容，以确保运行正常。假设voidele(intan)/a1an中存在n个要素 int i=1；while (1) doif (Ai！=Ai 1) i；查找满足else /条件的元素 for (2) Aj-1=Aj；/删除第I 1个要素(符合条件的要素)(3) /修改线性表的长度以下称为以下称为八、(15分钟)设计算法知道以二叉树存储的二叉树，根指向根节点，p指向二叉树中的任意一个节点，创建算法以确定从根节点到p指向的节点的路径(要求输出该路径上的各节点的数据)数据结构仿真问题4参考回答1、(共计30分，每题2分)个别选题1 a2c3a4c5d6d7b8c9c 10 d 11 d 13 c 14 c 15 d二、(共计40分，1空间2分)填空问题1. log2n2. s-next=p3 .序言4. 3005.1比1，1比多或多比多的6 .最小7. 48. 2359. 12910.2米- 111 .中序，m12.2，4，413 .相邻矩阵14 .插入排序，然后选择排序15. n 1、线索三、(10分钟)解：设n为总分数，N0为叶节点数，则N=N0 N1 N2 Nm此外，在N-1=度的总数中，N-1=N1*1 N2*2 Nm*mn0=1n22n 3(m-1 )有nm四、(15分钟)c.ccde公司甲组联赛c(00 )d(01 )a(100 )b(101 )e(11 )五、(15分钟)线性探测器重新散列的散列列表：0 1 2 3 4 5 6 7 8 9 10 11 1214168275519208479231110121431139113成功搜索的平均长度为asl=1/12(1*6*2*3*3*4*19)=2.5检索失败的平均长度为ASL=1/13(1 2 3 4. 13)=76(15分钟)(1)void oesort (int an )装模作样int i，flag；do 12222222222222222226flag=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次以下称为7(10分钟) (1)i=n (2)(j=i 1； j=n； j )(3)n-8(15分钟)void路径(t，p )Bintree T，p；Bintree stackmax，q；int tagmax、top=0、find=0