2018年闽南师范大学粒计算重点实验室916计算机专业基础之数据结构考研强化五套模拟题
● 摘要
一、填空题
1． 完善算法:求KMP 算法.next 数组。
k :＝_____；next[1]:＝0；
k :＝_____；
END ；
【答案】0；next[k]
2． 设正文串长度为n ，模式串长度为m ，则串匹配的KMP 算法的时间复杂度为_____。
【答案】O(m＋n)
3． 高度为4的3阶B-树中，最多有_____个关键字。
【答案】26
【解析】第4层是叶结点，1层至3层每个结点两个关键字，每个节点的关键字达到最大时，关键字最多。
4． 设有N 个结点的完全二叉树顺序存放在向量
【答案】 中，其下标值最大的分支结点为_____。
【解析】最大的分支结点是最后一个叶子结点的父结点。
5． 二叉树由_____，_____，_____三个基本单元组成。
【答案】根结点；左子树；右子树
6． 如果按关键码值递增的顺序依次将关键码值插入到二叉排序树中，则对这样的二叉排序树检索时，平均比较次数为_____。 【答案】
序查找效率一样为
。 【解析】如果关键码是排好序的，构建二叉排序树就会形成一个单支树，它的查找效率和顺
二、单项选择题
7． 假定有k 个关键字互为同义词，若用线性探测法把这k 个关键字存入哈希表中，至少要进行多少次探测？（ ）
A.k －1次
B.k 次
C.k+1次 D.
【答案】D
【解析】至少探测次数。
8． 采用开址定址法解决冲突的哈希查找中，发生集聚的原因主要是（ ）。
A. 数据元素过多
B. 负载因子过大
C. 哈希函数选择不当
D. 解决冲突的算法选择不好
【答案】D
【解析】开放定址法就是从发生冲突的那个单元开始，按照一定的次序，从散列表中查找出一个空闲的存储单元，把发生冲突的待插入元素存入到该单元中的一类处理冲突的方法。
9． 若线性表最常用的操作是存取第I 个元素及其前驱和后继元素的值，为节省时间应采用的存储方式（ ）。
A. 单链表
B. 双向链表
C. 单循环链表
D. 顺序表
【答案】D
【解析】线性表采用顺序表，便于进行存取任一指定序号的元素。
10．下面关于哈希(Hash，杂凑) 查找的说法正确的是（ ）。
A. 哈希函数构造的越复杂越好，因为这样随机性好，冲突小
B. 除留余数法是所有哈希函数中最好的
C. 不存在特别好与坏的哈希函数，要视情况而定
D. 若需在哈希表中删去一个元素，不管用何种方法解决冲突都只要简单地将该元素删去即可
【答案】C
【解析】若数据结构中存在关键字和K 值相等的记录，则必定在f(K)的存储位置上，由此，不需要进行比较便可直接取得所查记录。在此，称这个对应关系f 为哈希(Hash)函数，哈希函数的
次
选择要视具体情况而定。
11．某以太网拓扑及交换机当前转发表如下图所示, 主机后, 向主机
A.
C.
D. 和和 B.{2, 3}和{1} 和
{1}
向主机发送1个数据帧, 主机收到该帧发送一个确认帧, 交换机对这两个帧的转发端口分别是（ ）
【答案】B
【解析】
第一次交换机没有
这个数据报源MAC 地址的信息的信息, 只能选择从其他端口全部发送, 同时记录, 确认帧发送时已经有的信息了所以只用从1端口转发。
12．若x=103, y=-25测下列表达式采用8位定点补码运算实现时, 会发生溢出的是（ ）
A.x+y
B.-x+y
C.x-y
D.-x-y
【答案】C
答:8位定点补码能表示的数的范围为:-128~127
A 结果为78, B 结果为-128, D结果为-78都在此范围内, 只有C 结果128超过了8位定点补码能表示的数的范围, 会发生溢出
13． 已知三叉树T 中6个叶结点的权分别是2, 3, 4, 5, 6, 7, T 的带权(外部) 路径长度最小是（ ）
A.27
B.46
C.54
D.56
【答案】B
【解析】利用三叉树的6个叶子结点的权构建最小带权生成树, 最小的带权路径长度为