24-25-2-数据结构与算法设计-期中

一、选择题（每空2分，共20分）

1. 以下术语不属于存储结构的是 ( )

广义表

二叉链表

双向循环链表

顺序表

检查

2. 在一个长度为 $n$ 的顺序表中删除第 $i$ 个数据元素 $(1\le i\le n)$ 时，需要向前移动的数据元素个数为 ( )

$n$

$i-1$

$n-i$

$n-i+1$

检查

3. 若某表最常用的操作是在最后一个结点之后插入一个结点或删除最后一个结点，则下列各种存储方式中最节省时间的是 ( )

带头结点的单链表

带头指针的单循环链表

带尾指针的单循环链表

带头指针的双循环链表

检查

4. 在一个二维数据组 $A$ 中，假设每个数据元素长度为 3 个存储单元，行下标 $i$ 为 $0-8$，列下标 $j$ 为 $0-9$。从首地址 $SA$ 开始按行优先顺序连续存放，则元素 $A[8][5]$ 的起始地址为 ( )

$SA+255$

$SA+222$

$SA+144$

$SA+141$

检查

5. 一棵完全二叉树上有 2023 个结点，其中叶子结点的个数时 ( )

1010

1011

1012

1013

检查

6. 已知 $L$ 是带头节点的非空单链表，且 $P$ 结点既不是首元结点，也不是尾元结点。试从下列提供的答案中选择合适的语句序列。

a. 删除 $P$ 节点的直接后继节点的语句序列是 【暂无答案】

b. 删除 $P$ 节点的直接前驱节点的语句序列是 【暂无答案】

c. 删除 $P$ 节点的语句序列是 【暂无答案】

d. 删除首元结点的语句序列是 【暂无答案】

e. 删除尾元结点的语句序列是 【暂无答案】

备选语句：

1. P = P -> next
2. P -> next = P
3. P -> next = P -> next -> next
4. P = P -> next -> next
5. While (P != NULL) P = P -> next
6. While (Q -> next != NULL) Q = Q -> next
7. While (P -> next != Q) P = P -> next
8. While (P -> next -> next != Q) P = P -> next
9. While (P -> next -> next != NULL) P = P -> next
10. Q = P
11. Q = P -> next
12. P = L
13. L = L -> next
14. free (Q)

二、判断题（每题1分，共10分）

1. 顺序存储利用物理位置来表征逻辑关系，因此顺序存储只用来存储线性结构。【暂无答案】
2. 在存储数据时，只需要存储各数据元素的值和数据元素的类型。【暂无答案】
3. 设计表达式括弧匹配算法是，会用到队列结构。【暂无答案】
4. 某二叉树中序序列的第一个结点不是叶结点，则该节点一定是其后序遍历的第一个结点。【暂无答案】
5. 采用三元组存储矩阵，仍然可以进行随机存取。【暂无答案】
6. 消除递归不一定需要使用栈。【暂无答案】
7. 栈和队列都是操作受限的线性表，只允许在表的一端进行操作。【暂无答案】
8. 若完全二叉树的某个结点没有左子，则此结点必是叶子结点。【暂无答案】
9. 若一个广义表的表尾为空表，则此广义表亦为空表。【暂无答案】
10. 用一维数组存储二叉树时，总是以层序遍历顺序存储结点。【暂无答案】

三、

已知某二叉树的先序遍历和中序遍历的序列分别是 $ABDEGJCFHKI$ 和 $DBEJGACHKI$。（10分）

1. 画出这棵二叉树。
2. 给出这棵二叉树后序遍历序列。

【显示答案】 DJGEBHIKFCA

3. 给出这棵二叉树层序遍历序列。

【显示答案】 ABCDEFGHKJI

四、

假设一个英文文本文件中只包含 $d,f,g,h,s,t,y$ 七个字体，每个字符在文件中出现的次数分别为：20，10，36，44，3，80，50。现在需要利用赫夫曼编码对这个文件进行压缩。（10分）

1. 画出为这 7 个字体进行赫夫曼编码的赫夫曼树。
2. 计算这棵树的 WPL。
3. 给出每个字符的赫夫曼编码。

五、

设字符串 $S = 'aabaabaabaabaac', P = 'aabaac'$，试回答下列问题。（10分）

1. 求出 $P$ 的 next 数组值和 nextval 数组值，并填入下表。
2. 若 $S$ 作为目标串，$P$ 作为模式串，试画出利用改进的 KMP 算法（即采用 nextval 数组）的匹配过程。

六、

已知广义表 $A = (((a)),(b),c,(a),(((d,e))))$；试回答以下问题。（10分）

1. 画出表 A 采用头尾链表方式存储的示意图。
2. 求出表 A 的长度与深度。
3. 用求头部 $head()$ 求尾部 $tail()$ 的函数求出原子 $e$。

七、

在某个电商网站上，商品信息存储在一个带头节点单链表中，$head$ 是该链表的头指针，每个节点的数据域保存的事商品信息，包括商品编号和商品类别编号，每种类别中会有多个不同的商品，商品编号是唯一的。请编写算法，计算出该电商网站一共有多少种类别的商品。（10分）

typedef struct node {
  int no;        // 商品编号
  int classnum;  // 商品类别编号
  struct node *next;
} node, *HNode;

int ProductCat(HNode head) // head 为头指针

八、

已知含 $n$ 个结点的二叉树以双亲表示法进行存储（如图例所示）；若该二叉树是由某树（或森林）转换而来，试给出算法在 $O(n)$ 时间复杂度之内求该二叉树对应的树（或森林）的叶节点的个数。（10分）

typedef struct Node {  // 节点结构
  etype data;
  int parent;        // 双亲位置域
} PTNode;

typedef struct Tree {  // 二叉树结构
  PTNode node[1,...,MAX_TREE_SIZE];
  int n;             // 二叉树的节点个数
} PTree;

int Countleaf(PTree tree)  // 函数返回值为树（或森林）叶子结点数

九、

已知二叉树以二叉链表方式存储，在每个结点中增加一个子孙域用于存储该节点子孙的个数；是给出递归算法为每个节点子孙域赋值，并返回该值。（10分）

typedef struct node {
  etype data;
  int descnum; // 结点的子孙数
  struct node *left, *right;
} node, *bitptr;

int Descnum(bitptr root) // root 为根结点。函数返回值为结点子孙数