24 - 25

一、选择题（在每个小题四个备选答案中选出一个正确答案）（本大题共10小题，每小题2分，总计20分）

下面关于广义表的叙述中，不正确的是________。 A) 广义表可以是一个多层次的结构 B) 广义表至少有一个元素 C) 广义表可以被其他广义表所共享 D) 广义表可以是一个递归表
以下数据结构中哪一个是线性结构？ A) 有向图 B) 栈 C) 二叉树 D) B树
字符 A、B、C、D 依次进入一个栈，按出栈的先后顺序组成不同的字符串，至多可以组成________个不同的字符串。 A) 15 B) 16 C) 14 D) 21
对线性表，在下列哪种情况下应当采用链表表示？ A) 经常需要随机地存取元素 B) 经常需要进行插入和删除操作 C) 表中元素需要占据一片连续的存储空间 D) 表中元素的个数不变
为解决计算机与打印机之间速度不匹配的问题，通常设置一个打印数据缓冲区，主机将要输出的数据依次写入该缓冲区，而打印机则依次从该缓冲区中取出数据。该缓冲区的逻辑结构应该是________。 A) 栈 B) 队列 C) 树 D) 图
栈和队列的共同点是________。 A) 都是先进先出 B) 都是先进后出 C) 只允许在端点处插入和删除元素 D) 没有共同点
设有一个二维数组A[m][n]，假设A[0][0]存放位置在600₍₁₀₎，A[3][3]存放位置在678₍₁₀₎，每个元素占一个空间，问A[2][3]₍₁₀₎存放在什么位置？（脚注₍₁₀₎表示用10进制表示，m>3） A) 658 B) 648 C) 633 D) 653
下列关于数据结构的叙述中，哪一个是正确的？ A) 数组是不同类型值的集合 B) 线性表的链式存储结构优于线性存储结构 C) 树是一种线性结构 D) 用一维数组存储一棵完全二叉树是有效的存储方法
已知串 S=‘aaab’，其 Next 数组值为________。 A) 0123 B) 1123 C) 1231 D) 1211
下面关于串的叙述中，哪一个是不正确的？ A) 串是字符的有限序列 B) 空串是由空格构成的串 C) 模式匹配是串的一种重要运算 D) 串既可以采用顺序存储，也可以采用链式存储

二、填空题（本大题共10小题，每小题2分，总计20分）

数据结构被形式地定义为 (D, S)，其中 D 是数据元素的有限集合，S 是 D 上________的有限集合。
邻接矩阵的存储空间大小与图的________有关。
________是被限定为只能在表的一端进行插入操作，在表的另一端进行删除操作的线性表。
设有一稀疏图 G，则 G 采用________存储方式较省空间。
如果 n 个顶点的图是一个环，则它有________棵生成树。
若串 S=‘computer’，其子串的数目是________。
对于 n 个记录的集合进行冒泡排序，在最坏的情况下的时间复杂度是________。
已知广义表 L=((x, y, z), a, (u, t, w))，则 L 的深度为________。
一棵深度为 6 的满二叉树有________个分支结点。
一棵具有 257 个结点的完全二叉树，它的深度为________。

三、算法应用（本大题共4小题，第1~3小题每小题8分，第4小题16分，总计40分）

1. 有向带权图问题（ACM式Input格式）

有向带权图如下：

题目描述：
(1) 以顶点0为出发点，分别写出一条深度优先遍历序列和一条广度优先遍历序列；
(2) 填表格展示应用迪杰斯特拉算法求从顶点0到其余各点的最短路径的过程。

2. 哈希表问题

将关键字序列 {7, 8, 11, 18, 9, 14, 30} 散列存储到哈希表中，其存储空间是一个大小为10、下标从0开始的一维数组，哈希函数为：
h(key) = (key * 3) % 10，
处理冲突采用线性探测再散列法。（注：% 是求余运算）
(1) 请画出所构造的哈希表；
(2) 并计算查找成功的平均查找长度。

3. 排序算法问题

给定关键字序列 {24, 19, 32, 43, 38, 6, 13, 22}，
(1) 请写出快速排序第一趟的结果；
(2) 请画出堆排序时所建的初始堆（大顶堆）。

4. 树结构问题

设有序列：w = {23, 24, 27, 80, 28}，
(1) 试画出二叉排序树；
(2) 试画出平衡二叉树；
(3) 试画出哈夫曼树；
(4) 请给出对于增量 d = 2 按降序执行一趟希尔排序的结果。

四、算法设计（本大题共2小题，每小题10分，总计20分）

1. 单链表插入算法设计
请设计算法 ListInsert_L，用以实现：在带头结点的单链表 L 中第 i 个位置之前插入元素 e。结点结构如下：

typedef struct LNode {
    ElemType        data;
    struct LNode   *next;
} LNode, *LinkList;
Status ListInsert_L(LinkList &L, int i, ElemType e) { ... }
// 在带头结点的单链表 L 中第 i 个位置之前插入元素 e。

2. 二叉树中序遍历非递归算法设计
以二叉链表作存储结构，请设计中序遍历非递归算法 InOrderTraverse，对每个数据元素调用函数 Visit。二叉树的二叉链表存储表示如下：

typedef struct BiTNode {
    TElemType       data;
    struct BiTNode  *lchild, *rchild; // 左右孩子指针
} BiTNode, *BiTree;
Status InOrderTraverse(BiTree T, Status(* Visit)(TElemType e)) { ... }
// 采用二叉链表存储结构，Visit 是对数据元素操作的应用函数。
// 中序遍历二叉树 T 的非递归算法，对每个数据元素调用函数 Visit。

23 - 24

一、填空题（本大题每空 3 分，共 30 分）

对于给定的 $n$ 个元素，可以构造出的逻辑结构有集合、线性结构、、四种。
数据结构中评价算法的两个重要指标是 ________ 和空间复杂度。

下面程序段的时间复杂度为 ________。（ $n > 1$ ）

for (j = 1; j <= n; ++j)
    for (k = 1; k <= n; ++k)
        {++x; s += x;}

已知数组 $A [0..9, 0..9]$ 的每个元素占 5 个存储单元，将其按列优先次序存储在起始地址为 1000 的连续的内存单元中，则元素 $A [5, 4]$ 的地址为 ________。
设广义表 $A = (x, a, b, c, d)$ ，则 $Head (Tail (A)) =$ ________。
模式串 $P = ‘abaaabac‘$ 的 next 函数值序列为 ________。
设有一个空栈，现有输入序列为 $1, 2, 3, 4, 5$ ，经过 $PUSH$ , $PUSH$ , $POP$ , $PUSH$ , $POP$ , $PUSH$ , $POP$ 之后，输出序列是 ________。
设一棵树的二元组形式表示为 $T = (D, R)$ ，其中 $D = {A, B, C, D, E, F, G}$ ， $R = {(Λ, B), (A, C), (A, D), (B, E), (C, F)}$ ，则该树的深度为 ________，叶子结点的个数为 ________。

二、简答题（本大题共 2 小题，每小题 10 分，共 20 分）

线性表有两种存储结构：一是顺序表，二是链表。试问：
（1）如果有 $n$ 个线性表同时并存，并且在处理过程中各表的长度会动态变化，线性表的总数也会自动地改变。在此情况下，应选用哪种存储结构？为什么？
（2）若线性表的总数基本稳定，且很少进行插入和删除，但要求以最快的速度存取线性表中的元素，那么应采用哪种存储结构？为什么？
已知一棵二叉树的先序序列ABDGJEHCFIKL;中序序列DJGBEHACKILF,画出二叉树的形态。

算法设计

1. 哈夫曼编码问题

假设用于通信的电文仅由 8 个字母 (a, b, c, d, e, f, g, h) 组成。字母在电文中出现的频率分别为 0.07, 0.17, 0.19, 0.06, 0.28, 0.03, 0.11, 0.09。
要求：

构造哈夫曼树
计算带权路径长度
为这 8 个字母设计哈夫曼编码
评分标准：构造过程 2 分，树 3 分，编码 3 分，长度计算过程 1 分，结果 1 分

2. Kruskal 算法问题

题目：试写出用克鲁斯卡尔（Kruskal）算法构造下图的一棵最小生成树的过程。（需给出中间步骤）

图结构描述（节点 1-7，边权重如下）：

//ACM式input(u,v,w)
1 7 6
1 6 4
1 2 18
1 5 23
7 6 7
6 4 3
6 5 25
5 4 15
4 3 10
3 2 5
5 2 12
2 4 8

3. 已知一图如下所示：

(u,v,weight，标记)
1 2 3 A
1 3 2 B
2 4 2 C
2 5 3 D
3 4 4 E
3 6 3 F
4 6 2 G
5 6 1 H

要求：

写出该图的邻接矩阵
以 1 为源点、6 为终点，给出所有事件允许发生的最早时间和最晚时间
求出关键路径（列出各活动的最早发生时间和最迟发生时间）并指明完成该工程所需的最短时间

4.哈希表构造问题

已知条件：

关键字集合：{19, 14, 23, 01, 68, 20, 84, 27, 55, 11, 10, 79}（注：01 即 1）
散列函数：H(Key) = Key MOD 13
冲突处理：线性探测再散列
地址空间：A[0..15] 要求：
构造哈希表
计算 ASL（平均查找长度）
评分标准：构造过程 4 分，哈希表 4 分，ASL 2 分

5. 快速排序问题