2018年武汉工程大学计算机科学与工程学院835数据结构之数据结构教程考研仿真模拟五套题
● 摘要
一、单项选择题
1． 若平衡二叉树的高度为6, 且所有非叶结点的平衡因子均为1, 则该平衡二叉树的结点总数为（ ）。
A.12
B.20
C.32
D.33
【答案】B 。
【解析】本题的实际问题是, 具有6层结点的平衡二叉树含有最少的结点数是多少。
深度为h 的平衡二叉树中含有的最少结点数, 有
由此可得。对应的平衡二叉树如下图所示。
表示
2． 下列关于USB 总线特性的描述中, 错误的是（ ）。
A. 可实现外设的即插即用和热插拔
B. 可通过级联方式连接多台外设
C. 是一种通信总线, 可连接不同外设
D. 同时可传输2位数据, 数据传输率高
【答案】D 。
【解析】USB 总线即通用串行总线, 它的特点有:
(1)即插即用; (2)热插拔; (3)有很强的链接能力能将所有外设链接起来, 且不损失带宽;
(4)有很好的可扩展性; (5)高速传输, 速度可达480Mbps 。
所有A , B , C 都符合USB 总线的特点。对于选项D , USB 是串行总线, 不能同时传输两位数据, 所以答案为D 。
3． 排序过程中, 对尚未确定最终位置的所有元素进行一遍处理称为一趟排序。下列排序方法中, 每一趟排序结束时都至少能够确定一个元素最终位置的方法是（ ）。
Ⅰ. 简单选择排序
Ⅱ. 希尔排序
Ⅲ. 快速排序
Ⅳ. 堆排
Ⅴ. 二路归并排序
A. 仅Ⅰ、Ⅲ、Ⅳ
B. 仅Ⅰ、Ⅱ、Ⅲ
C. 仅Ⅱ、Ⅲ、Ⅳ
D. 仅Ⅲ、Ⅳ、Ⅴ
【答案】A 。
【解析】其中简单选择排序、堆排序属于选择类排序, 每一趟排序结束时将确定最大(或最小) 关键字所在的位置。快速排序每一趟排序结束时将确定基准关键字所在的位置。希尔排序、二路归并排序每一趟排序结束时不一定能确定一个元素的最终位置。
4． 下列关于管道(Pipe)通信的叙述中, 正确的是（ ）
A. —个管道可实现双向数据传输
B. 管道的容量仅受磁盘容量大小限制
C. 进程对管道进行读操作和写操作都可以被阻塞
D. —个管道只能有一个读写进程或一个写进程对其操作
【答案】C
【解析】只有写进程才能对管道写入数据, 读进程对管道进行读取数据, 只能半双工通信, 即某一时刻只能单向传输。管道为空, 则读操作被堵塞, 而如果有写操作对管道进行写的话那就要堵塞了。那么C 正确
二、综合题
5． 设目标为
(1)计算模式p 的nextval 函数值；
(2)不写出算法，只画出利用KMP 算法进行模式匹配时每一趟的匹配过程。
【答案】(1)P的nextval 函数值为0110132(P的next 函数值为0111232) 。
(2)利用KMP(改进的nextval) 算法，每趟匹配过程如下:
第一趟匹配:abcaabbabcabaacbacba
abcab(i＝5，j ＝5)
第二趟匹配:abcaabbabcabaacbacba
，模式为
abc(i＝7jj ＝3)
第三趟匹配:abcaabbabcabaacbacba
a(i＝7，j ＝l)
第四趟匹配:abcaabbabcabaacbacba
(成功)abcabaa(i＝15，j ＝8)
6． 将关键字序列(7，8，30，11，18，9，14) 散列存储到散列表中，散列表的存储空间是一个下标从0开始的一维数组. 散列函数是:H(key)＝(key×3)M0D7，处理冲突采用线性探测再散列法，要求装填(载）因子为.
(1)请画出所构造的散列表.
(2)分别计算等概率情况下查找成功和查找不成功的平均查找长度.
【答案】(1)
要求装填因子为
列函数值如下表:
采用线性探测法再散列法处理冲突，所构造的散列表为:
(2)查找成功时，在等概率情况下，查找表中每个元素的概率是相等的，因此是根据表中元素个数来计算平均查找长度，各关键字的比较次数如下表所示:
故查找成功的平均查找长度为(1+1+1+1+3+3+2)/7＝12/7.
在不成功的情况下，由于任意关键字key ，H(key)的值只能是0〜6之间，H(key)为0需要比较3次，H(key)为1需要比较2次，H(key)为2需要比较1次，H(key)为3需要比较2次，H(key)为4需要比较1次，H(key)为5需要比较5次，H(key)为6需要比较4次，共7种情况，如下表所示:
所以，在等概率下，查找失败的平均查找长度为:(3+2+1+2+1+5+4)/7＝18/7.
7． 将算术表达式转化为二叉树。 ，数组的长度应该为数组下标为0〜9. 各关键字的散
【答案】该算术表达式转化的二叉树如图所示。