数据结构期末复习题及答案3

2.对于栈，输入序列为（1，2，3，4），不可能得到的输出序列有__D_____。 (A)（1，2，3，4） (B)（4，3，2，1） (C)（1，3，4，2） (D)（3，1，2，4）

3.用单循环链表表示队列，正确的说法是 B 。 (A)可设一个头指针使入队、出队都方便； (B)可设一个尾指针使入队、出队都方便； (C)必须设头尾指针才能使入队、出队都方便； (D)无论如何,只可能使入队方便。 3、判断题

1.栈的特点是先进先出。（ × ） 2.可以在队列的任意位置插入元素。（ ×） 3.递归程序化非递归程序必须用到栈。（ × ）

4.如果进栈的序列为（1，2，3，4），则（4，2，3，1）不可能是出栈序列。（√） 5.在用顺序表表示的循环队列中，可用标志位来区分队空或队满的条件。（√） 第4章 串 1、选择题

1. 设有两个串p和q，求q在p中首次出现的位置的运算称作（ B ） A．连接 B．模式匹配 C．求子串 D．求串长 2、判断题

1.空串和空格串是同一个概念，二者没有区别。（ × ） 第5章 数组和广义表 1、填空题

1.二维数组在内存中存储可以有两种存储方式，一种是___行__优先存储，一种是 列 优先存储。

2.设广义表L＝(（），（），（（））)。则head(L)是 （） ； tail(L)是 (（），（（））) ；L的长度是 3 ；L的深度是 3 。 3.设广义表L＝(（a），（b），（（c））) 则head(L)是__（a）__；

tail(L)是_(（b），（（c））)___。 2、选择题

1.在C语言中，如果有数组定义 int A[8][9]；假定每个整型数据占2字节，则数

组元素A[4][4]的地址是（ A ）。

A. A+80 B. A+76 C.A+82 D.以上都不对

2.广义表A=（a,b,(c,d),(e,(f,g))）,则下面式子的值为( D )； Head(Tail(Head(Tail(Tail(A)))))

A．（g） B.(d) C.c D.d 3、判断题

1.在C语言中，多维数组的存储采取的是行优先的方式。（ √ ） 2.广义表在本质上也是线性表。（ × ）

3.可以用三元组存储法来压缩存储稀疏矩阵。（ √）

4.已知广义表A=((a,b,c),(d,e,f)),从A中取出原子e的运算是head(tail(head(tail(A))))。 ( √ ) 第6章 树和二叉树 1、填空题

1.一棵62个叶结点的完全二叉树,最多有___62*2=124______个结点。

2.若规定仅有根的二叉树的高度为1，那么高为h的完全二叉树最多有-____2^h-1___________个结点，最少有___2^(h-1)______个结点。 3.设只包含有根结点的二叉树的高度为0，则高度为k的二叉树的最大结点数为-____2^(k+1)-1____________，最小结点数为____k+1____________。

4.设仅包含根结点的二叉树的高度为1，则高度为k的二叉树的最大结点数为-_______2^k-1_________，最小结点数为____k______。 2、选择题

1.具有N个结点的完全二叉树的深度是__B______。 (A)? log2N ? (B) ? log2N ?+1 (C) ? log2(N) ? (D) ? log2N ?-1

2.设二叉树的树根为第一层，则第i层上至多有__C_____结点。

i-1

(A)1 (B)2 (C)2 (D)2i-1 3、判断题

1.二叉树的左右子树次序是严格的，不能够任意改变。（ √ ）

2.若根为第一层，则深度为k的满二叉树的结点为2^k-1 。

（ √）

3.二叉树的三叉链表存储结构可以方便的访问到双亲结点。 （√ ） 4、应用题

1.在一段文字中，共出现a、b、c、d、e、f六种字符，每种字符出现的频率分别为7,9,12,22,23,27。请回答下列问题：

（1）什么是哈夫曼树？（3分）

（2）根据题目所给频率值，画出相应的哈夫曼树。（11分） （3）给出各个字符对应的哈夫曼编码。（6分） （4）该段文字经过哈夫曼编码后，长度是多少。（4分） 参考答案如下：

（1）答案为：带权路径长度最小的二叉树称为哈夫曼树。（3分） （2）根据题目所给频率值，画出相应的哈夫曼树。（11分，每个结点1分） （3）给出各个字符对应的哈夫曼编码。（6分） a:1110 b:1111 c:110 d:00 e:01 f:10 （4）该段文字经过哈夫曼编码后，长度是多少。（4分）

(7+9)*4+12*3+(22+23+27)*2=244 或者100+45+55+28+16=244

0 1 55 100 0 1 45 0 22 d 23 e 1 27 f 0 12 c 28 1 16 0 7 a

1 9 b

2. 设一棵二叉树的先序遍历序列为abcde，中序遍历序列为badce，请画出对应的二叉树，并写出对应后序遍历序列。（15分）

参考答案如下： (1)画出二叉树（10分）

错一个结点扣2分。

a b c d e

（2）后序遍历序列为：bdeca （5分）

3. 通信报文中出现的字符A、B、C、D、E，在报文中出现的频率分别为0.23、0.2、

0.32、0.12、0.13，分别给出相应字符的哈夫曼编码（要求画出哈夫曼树，并且把权值小的结点放在左边）。（共14分） 参考答案如下：

为处理方便，关键字都乘以100，为{23，20，32，12，13} 构造哈夫曼树为：（9分,每个结点1分）

0 43 0 20 B 23 A 1 100 1 57 0 25 1 32 1 13 E

C 0 12 D 所以编码为：A：01 B：00 C：11 D：100 E：101 （5分，每个编码1分）

4. 某二叉树结点的中序序列为H，B，C，D，E，F，G，后序序列为B，D，C，H，F，

G，E，请据此画出该二叉树，再给该树加上中序线索。（共15分）

对应的二叉树为：（7分,每个结点1分）对应中序线索树为：（8分，每条线索1分）

E G

H H

C C F 5

D G E F B B D