25-26-2-数据结构与算法-期末（电子工程学院）

一、单选题

已知循环队列的队头指针为 front，队尾指针为 rear，队列存储空间大小为 MAXSIZE（或 m），约定少用一个元素空间以区分队空和队满，则当前队列中的元素个数为 ( )

rear - front

(rear - front + MAXSIZE) % MAXSIZE

(rear - front + MAXSIZE - 1) % MAXSIZE

(rear - front + 1) % MAXSIZE

一棵完全二叉树共有 64 个结点，则该完全二叉树的层数 ( )

6

7

8

9

在双向链表的结点 p 之后插入由指针 s 所指的新结点，已知以下操作序列：s->prior = （ ① ）;s->next = p->next;（ ② ） = s;s->next->prior = s; 则 ① 和 ② 处应分别填入 ( )

p，p->prior

s，p->prior

p，p->next

s，p->next

在含有 n 个结点的二叉链表存储结构中，非空指针域的数量为 ( )

n

n - 1

n + 1

2n

一棵哈夫曼树有 n 个叶子结点，则该哈夫曼树的总结点数为 ( )

2n

2n - 1

2n + 1

2(n - 1)

二、判断题

三、填空题

在数据结构中，除了要存储数据元素本身，还需要存储【暂无答案】。
两个递增有序链表，元素个数均为 N，合并为一个递增有序链表，最少的比较次数为【暂无答案】。
队列中，循环队列的引入，是为了解决【暂无答案】问题。
括号匹配问题中，最适宜采用的数据结构是【暂无答案】。
顺序表查找中，设置监视哨（哨兵）的目的是为了避免每次循环时都要检查【暂无答案】。

四、简答题

29.

一个二叉树，先序遍历为 $abdgcefh$ ，中序遍历为 $dgbaechf$ 。

画出该二叉树
写出该二叉树的顺序存储

30.

依次输入 $1, 12, 5, 3, 8, 13, 7, 10, 9, [???]$ 构成二叉排序树。

画出该二叉树
如何能依次输出这些数字

31

已知一组关键字序列： $10, 38, 32, 17, 31, 30$ ，散列函数为 $H(key) = key\,\%\,7$ ，散列表地址空间大小为 $m = 10$ （地址范围 0~9），采用线性探测再散列处理冲突。

请回答以下问题：

画出最终构造出的散列表；
计算等概率情况下，查找成功时的平均查找长度；
计算等概率情况下，查找失败时的平均查找长度。

32.

$79, 46, 84, 38, 40, 56$

写出冒泡排序和 2 路归并排序前两遍
分析冒泡排序和 2 路归并排序稳定性

五、算法题

写出单链表代码定义
写出删除单链表中重复数据的函数 Delete(linklist La)
去重算法的时间复杂度

六、应用题

某图书馆管理系统需维护海量书籍信息，数据规模约数百万条。每本书籍具有唯一标识符 ISBN，并包含书名、作者等属性。系统面临以下操作需求：

每日需处理大量按精确 ISBN 进行的点查询操作；
每日需执行上千次动态更新操作，包括插入、删除和修改书籍记录；
系统偶尔需要按照 ISBN 升序输出全部书籍信息。

假定服务器内存资源充足，但系统对稳定性要求极高，单次操作的长时间阻塞不可接受。

现有三种存储方案：

方案A：采用顺序存储结构，记录按任意随机顺序（非 ISBN 有序）存放；
方案B：采用顺序存储结构，记录按 ISBN 升序存放；
方案C：采用平衡二叉搜索树（如 AVL 树或红黑树），支持查找、插入、删除及中序遍历操作。

请回答以下问题：

分析方案A不可行的原因；
分析方案B不可行的原因；
说明方案C为何能够满足系统需求；
若将方案C中的平衡二叉搜索树替换为普通（非平衡）二叉搜索树，会引发何种不良后果？请结合具体操作序列举例说明；
给出方案C中中序遍历操作的伪代码实现。