10636: 初赛集训 课堂测试11-3 数据结构 综合练习
[Creator : ]
Description
1. [J-2023-8]后缀表达式“6 2 3 + - 3 8 2 / + * 2 ^ 3 +”对应的中缀表达式是（ ）
A. ((6 - (2 + 3)) * (3 + 8 / 2)) ^ 2 + 3
B. 6 - 2 + 3 * 3 + 8 / 2 ^ 2 + 3
C. (6 - (2 + 3)) * ((3 + 8 / 2) ^ 2) + 3
D. 6 - ((2 + 3) * (3 + 8 / 2)) ^ 2 + 3
2.[J-2021-5]对于入栈顺序为 a, b, c, d, e 的序列，下列（ ）不是合法的出栈序列。
A. a, b, c, d, e
B. e, d, c, b, a
C. b, a, c, d, e
D. c, d, a, e, b
3. [J-2021-11]在数据压缩编码中的哈夫曼编码方法，在本质上是一种（ ）的策略。
A. 枚举
B. 贪心
C. 递归
D. 动态规划
4. [J-2023-10]假设有一组字符{a,b,c,d,e,f}，对应的频率分别为5%，9%，12%，13%，16%，45%。请问以下哪个选项是字
符a,b,c,d,e,f分别对应的一组哈夫曼编码？（ ）
A. 1111，1110，101，100，110，0
B. 1010，1001，1000，011，010，00
C. 000，001，010，011，10，11
D. 1010，1011，110，111，00，01
5. [S-2023-5]以下对数据结构的表述不恰当的一项是：
A. 队列是一种先进先出（FIFO）的线性结构
B. 哈夫曼树的构造过程主要是为了实现图的深度优先搜索
C. 散列表是一种通过散列函数将关键字映射到存储位置的数据结构
D. 二叉树是一种每个结点最多有两个子结点的树结构
6. [S-2010-11]（多选）元素R1、R2、R3、R4、R5入栈的顺序为R1、R2、R3、R4、R5。如果第1个出栈的是R3，那么第5个出栈的可能是（ ）。？
A. R1
B. R2
C. R4
D. R5
7. [J-2023-4]假设有一个链表的节点定义如下：
```cpp
struct Node {
int data;
Node* next;
};
```
现在有一个指向链表头部的指针：Node* head。如果想要在链表中插入一个新节点，其成员data的值为42，并使
新节点成为链表的第一个节点，下面哪个操作是正确的？（ ）
A. Node* newNode = new Node; newNode->data = 42; newNode->next = head; head = newNode;
B. Node* newNode = new Node; head->data = 42; newNode->next = head; head = newNode;
C. Node* newNode = new Node; newNode->data = 42; head->next = newNode;
D. Node* newNode = new Node; newNode->data = 42; newNode->next = head;
8. [J-2009-14]一个有n个分支结点（非叶结点）的非空二叉树，它的叶结点数目最多为：
A. 2n+1
B. 2n-1
C. n-1
D. n+1
9. [S-2016-7]一棵二叉树如右图所示，若采用二叉树链表存储该二叉树（各个结点包括结点的数据、左孩子指针、右孩子指针）。如果没有左孩子或者右孩子，则对应的为空指针。那么该链表中空指针的数目为（ ）。
A. 6
B. 7
C. 12
D. 14
10. [S-2012-20]（多选）一棵二叉树一共有 19 个节点，其叶子节点可能有（ ）个。
A. 1
B. 9
C. 10
D. 11
A. ((6 - (2 + 3)) * (3 + 8 / 2)) ^ 2 + 3
B. 6 - 2 + 3 * 3 + 8 / 2 ^ 2 + 3
C. (6 - (2 + 3)) * ((3 + 8 / 2) ^ 2) + 3
D. 6 - ((2 + 3) * (3 + 8 / 2)) ^ 2 + 3
2.[J-2021-5]对于入栈顺序为 a, b, c, d, e 的序列，下列（ ）不是合法的出栈序列。
A. a, b, c, d, e
B. e, d, c, b, a
C. b, a, c, d, e
D. c, d, a, e, b
3. [J-2021-11]在数据压缩编码中的哈夫曼编码方法，在本质上是一种（ ）的策略。
A. 枚举
B. 贪心
C. 递归
D. 动态规划
4. [J-2023-10]假设有一组字符{a,b,c,d,e,f}，对应的频率分别为5%，9%，12%，13%，16%，45%。请问以下哪个选项是字
符a,b,c,d,e,f分别对应的一组哈夫曼编码？（ ）
A. 1111，1110，101，100，110，0
B. 1010，1001，1000，011，010，00
C. 000，001，010，011，10，11
D. 1010，1011，110，111，00，01
5. [S-2023-5]以下对数据结构的表述不恰当的一项是：
A. 队列是一种先进先出（FIFO）的线性结构
B. 哈夫曼树的构造过程主要是为了实现图的深度优先搜索
C. 散列表是一种通过散列函数将关键字映射到存储位置的数据结构
D. 二叉树是一种每个结点最多有两个子结点的树结构
6. [S-2010-11]（多选）元素R1、R2、R3、R4、R5入栈的顺序为R1、R2、R3、R4、R5。如果第1个出栈的是R3，那么第5个出栈的可能是（ ）。？
A. R1
B. R2
C. R4
D. R5
7. [J-2023-4]假设有一个链表的节点定义如下：
```cpp
struct Node {
int data;
Node* next;
};
```
现在有一个指向链表头部的指针：Node* head。如果想要在链表中插入一个新节点，其成员data的值为42，并使
新节点成为链表的第一个节点，下面哪个操作是正确的？（ ）
A. Node* newNode = new Node; newNode->data = 42; newNode->next = head; head = newNode;
B. Node* newNode = new Node; head->data = 42; newNode->next = head; head = newNode;
C. Node* newNode = new Node; newNode->data = 42; head->next = newNode;
D. Node* newNode = new Node; newNode->data = 42; newNode->next = head;
8. [J-2009-14]一个有n个分支结点（非叶结点）的非空二叉树，它的叶结点数目最多为：
A. 2n+1
B. 2n-1
C. n-1
D. n+1
9. [S-2016-7]一棵二叉树如右图所示，若采用二叉树链表存储该二叉树（各个结点包括结点的数据、左孩子指针、右孩子指针）。如果没有左孩子或者右孩子，则对应的为空指针。那么该链表中空指针的数目为（ ）。
A. 6
B. 7
C. 12
D. 14
10. [S-2012-20]（多选）一棵二叉树一共有 19 个节点，其叶子节点可能有（ ）个。
A. 1
B. 9
C. 10
D. 11