内容发布更新时间 : 2024/11/10 3:27:07星期一 下面是文章的全部内容请认真阅读。

数据结构模拟试题四

一、( 共30分，每题2分)单项选择题

1．循环队列用数组A[0..m-1]存放其元素值，已知其头尾指针分别为front和rear，则当前元素个数为（）

A．(rear-front+m) mod m B．rear-front+1 C．rear-front-1 D．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．JLKMNOI B．LKNJOMI C．LKJNOMI D．LKNOJMI E．以上答案都不对 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．对于序列(49,38,65,97,76,13,27,50)按由小到大进行排序，（）是初始步长d=4的希尔排序法第一趟的结果。

A. 49,76,65,13,27,50,97,38 B. 13,27,38,49,50,65,76,97 C. 97,76,65,50,49,38,27,13 D. 49,13,27,50,76,38,65,97 E. 以上答案都不对 11．下列排序算法中，第一趟排序完毕后，其最大或最小元素一定在其最终位置的算法是（） A．归并排序 B．直接插入排序 C．快速排序 D．冒泡排序 E．以上答案都不对

12．关于树和二叉树的有序性，正确的结论是（）

A. 树和二叉树都是有序的 B．树和二叉树都可能是有序的

C．树和二叉树都是无序的 D．二叉树是有序的，树可能是有序的，也可能是无序的 E．以上答案都不对

13．在一个图中，所有顶点的度数之和与图的边数的比是（）

A．1:2 B．1:1 C．2:1 D．4:1 E．以上答案都不对

14．若一组纪录的关键码为（46，79，56，38，40，84），则利用快速排序的方法，以第一个纪录为基准得到的一次划分结果为（）

A．38，40，46，56，79，84 B．40，38，46，79，56，84 C．40，38，46，56，79，84 D．40，38，46，84，56，79 E．以上答案都不对

15．从理论上讲，将数据以（）结构存放，则查找一个数据所用时间不依赖于数据个数n。 A．二叉查找树 B．链表 C．二叉树 D．哈希表 E．以上答案都不对

二、（共40分，每空2分）填空题

1．二分查找算法的时间复杂度为（ ）

2．在单链表中，申请到新结点p，将p指向的结点后插到s所指结点的操作，其一是p->next=s->next，其二是（ ）。

3．对一般树和森林的后序遍历序列的次序与对应的二叉树的（ ）遍历次序相同。 4．设二维数组A[10..20,5..10]按行优先存储，每个元素占4个单元，A[10,5]的地址为160，则A[15,10]的地址为（ ）。 5．线性结构反映结点间的逻辑关系是（ ）的，非线性结构反映结点间的逻辑关系是（ ）的。

6．赫夫曼树是带权路径长度（ ）的二叉树。

7．前序为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。设计以该权值为基础的赫夫曼树，并给出赫夫曼编码。

五、（15分）设散列表的长度为13，散列函数为H(K)=K，给定的关键字序列为：19，14，23，01，68，20，84，27，55，11，10，79。试画出用线性探测再散列解决冲突时所构成的散列表。并求等概率情况下这种方法查找成功和查找不成功时的平均查找长度。 六、（15分）已知奇偶交换排序如下所述：第一趟对序列中所有奇数项i扫描，将a[i]和a[i+1]进行比较；第二趟对序列中所有偶数项i扫描，将a[i]和a[i+1]进行比较。每次比较时若 a[i]>a[i+1]，则将两者交换。第三趟对所有奇数项，第四趟对所有偶数项……，如此重复，直至整个序列有序。

1) 写出奇偶交换排序算法，设待排序的n个元素存放在数组a[1..n] 中。 2) 说明你的排序方法的结束条件

3) 若待排序的初始序列已按关键字从小到大有序，则关键字的比较次数是多少？ 七、（10分）已知长度为n的线性表A采用顺序存储结构，并且元素按值大小非递减排列，下面的算法删除线性表中多余的值相同的元素。请在算法中空白处填入适当内容，使之能够正常工作。

void DEL(int A[n]) // 设A[1]~A[n]存放着n个元素 { int i=1;

while (1) do if (A[i]!=A[i+1]) i++;

else //查找满足条件的元素

{ for (2) A[j-1]=A[j];//删除第i+1个元素（满足条件的元素） (3) //修改线性表的长度 } }

八、（15分）设计算法， 已知一棵以二叉链表存储的二叉树，root指向根结点，p指向二叉树中任一结点，编写算法求从根结点到p所指结点之间的路径（要求输出该路径上每个结点的数据）。