1.在一个无头结点的链队列中，若队首指针与队尾指针的值相同，则表示该队列为 或该队列 。

2.向一个栈顶指针为T的链栈中插入一个新结点*p时，应执行 和 。

3.从一个栈顶指针为T的非空链栈中删除结点并不需要返回栈顶结点的值和回收结点时，应执行 。

4.假定front和rear分别为一个无头结点的链队列的队首和队尾指针，则该链队列中只有一个结点的条件为 。 5.后缀表达式“45*32+-”的值为 。

6．一般地，一个n维数组可视为其数据元素为___________维数组的线性表。数组通常只有___________和___________两种基本运算。

7.通常采用___________存储结构来存放数组 。对二维数组可有两种存储方法：一种是以___________为主序的存储方式，另一种是以___________为主序的存储方式。C语言数组用的是以___________序为主序的存储方法。

8．需要压缩存储的矩阵可分为___________矩阵和___________矩阵两种。

9．对称方阵中有近半的元素重复， 若为每一对元素只分配一个存储空间 ，则可将n2个元素压缩存储到___________个元素的存储空间中。

10．假设以一维数组M（1：n(n+1)/2）作为n阶对称矩阵A的存储结构，以行序为主序存储其下三角（包括对角线）中的元素，数组M和矩阵A间对应的关系为___________。 11．上三角矩阵中，主对角线上的第t行(1<=t<=n)有___________个元素，按行优先顺序存放上三角矩阵中的元素aij时，aij之前的前i-1行共有___________个元素，在第i行上， aij是该行的第___________个元素，M[k]和aij的对应关系是_________。当i>j时，aij=c,c存放在M[___________]中。

12．下三角矩阵的存储和对称矩阵类似。M[K]和aij的对应关系是___________。

13．设有二为数组int M[10][20](注：m为0...10,n为0...20),每个元素（整数）栈两个存储单元，数组的起始地址为2000，元素M[5][10]的存储位置为___________，M[8][19]的存储值为___________。 四、解答题

1．若栈或队列采用顺序存储结构，则都存在“溢出”问题，请说明何谓“溢出”？

2. 有人说，采用循环链表作为存储结构的队列就是循环队列，你认为这种说法正确吗？说明你的理由。

- 17 -

3. 分别简述如何对一个前缀算术表达式求值的算法和一个后缀算术表达式求值的算法。 4．利用两个栈S1，S2模拟一个队列时，如何用栈的运算实现队列的插入、删除运算。请简述算法思想。

5. 设循环队列的容量为40（序号从0到39），现经过一系列的入队和出队运算后，有 ① front=11，rear=19; ② front=19，rear=11；问在这两种情况下，循环队列中各有元素多少个？ 9．设有三对角矩阵（aij）n*n,将其三条对角线上的元素逐行存于数组B(1:3n-2)中，使得B[k]=aij,求：

（1） 用i、j表示k的下标变换公式； （2） 用k表示i、j的下标变换公式. 五、算法设计题

1. 从键盘上输入一批整数，然后按相反的次序打印出来。

2. 试写一个算法，判别读入的一个以?@?为结束符的字符序列是否是“回文”，例如?abba?和?abcba?是回文，?abcde?和?ababab?则不是回文。

3. 判断算术表达式中的三种括号（圆括号，方括号，花括号）是否正确匹配。

4. 假设以数组que[m](假设数组范围在0..m)存放循环队列的元素，同时设变量rear和quelen分别指示循环队列中队尾元素位置和内含元素的个数。试给出此循环队列的队满条件，并写出相应的入队列和出队列的算法。

5. 用n个单元的一维数组构成的一个循环队列，试写由首指针front和尾指针rear计算出队列中元素个数的算法。

6．算术表达式由数字字母变量和加（+）、减（-）、乘（*）、除（\\）运算符组成，编写一个函数把中缀表达式转换为后缀表达式。为使问题简化，可不考虑中缀表达式不正确的情况。

7．设算术表达式由数字字母变量和加（+）、减（-）、乘（*）、除（\\）运算符组成，编写一个函数对以后缀表达式表示的算术表达式求值。为使问题简化，可不考虑后缀表达式不正确的情况。

8．假设以带头结点的循环链表表示队列，并且只设一个指针指向队尾元素结点（注意不设头指针），试编写相应的初始化队列、入队列和出队列算法。

9．编写算法:按行优先存储顺序，将稀疏矩阵转换为三元组的表示形式。

10．稀疏矩阵用三元组的表示形式，试写一算法实现两个稀疏矩阵相加，结果仍用三元组表示。

- 18 -

第 6 章 树和二叉树

一、单选题

1、一个结点拥有的子树数称为该结点的

A、权

B、维数

C、度

D、序

2、n个结点的线索二叉树中线索的数目为

A、(n-1)个

B、n个

C、(n+1)个

D、 (n+2)个

3、在有n个叶子结点的赫夫曼树中，其结点总数为

A、2n-1

B、2n

C、2n+1

D、2n+2

4、树最适合用来表示

A、有序数据元素

B、无序数据元素

D、元素之间无联系的数据

C、元素之间具有分支层次关系的数据

5、在一棵度为3的树中，度为3的结点个数为2，度为2 的结点个数为1，则度为0的结点个数为 Ａ、4

Ｂ、5

Ｃ、6

Ｄ、7

6、二叉树是结点的有限集合，其根结点的个数

A、有0个或1个 C、有且只有1个

B、有0个或多个 D、有1个或1个以上

7、对二叉树从1开始进行连续编号，要求每个结点的编号大于其左右孩子的编号，同一个结点的左右孩子中，其左孩子的编号小于其右孩子的编号，则可采用哪种遍历方式实现编号

A、先序遍历

B、中序遍历

C、后序遍历

D、层次遍历

8、某二叉树 T 有 n 个结点，设按某种顺序对 T 中的每个结点进行编号，且有如下性质：T 中任一结点 v，其编号等于左子树上的最小编号减 1，而 v 的右子树的结点中，其最小编号等于 v 左子树上的结点的最大编号加1，则可采用哪种遍历方式实现编号 A、先序遍历

二、判断题

1、一棵满二叉树，有n个结点，深度为h，则n=2h-1。 2、度为2的树是二叉树。

B、中序遍历

C、后序遍历

D、层次遍历

- 19 -

3、满二叉树一定是完全二叉树。 4、完全二叉树就是满二叉树。

5、深度为 h 的非空二叉树的第 i 层最多有 2 i-1个结点。

6、二叉树叶子结点的数目只与度为 2 的结点的数目有关，而与度为 1 的结点的数目无关。 7、一棵有 n ≥ 1 个结点的 d 度树，若用多重链表表示，树中每个结点都有 d 个链域，则在树的 nd个链域中，有 n(d-1)+1个是空域，只有 n-1个是非空链域。

8、若有一个结点是某二叉树子树的中序遍历序列中的最后一个结点，则它必是该子树的先序遍历序列中的最后一个结点。

9、若有一个结点是某二叉树子树的先序遍历序列中的最后一个结点，则它必是该子树的中序遍历序列中的最后一个结点。

10、不使用递归，也可实现二叉树的先序、中序和后序遍历。 11、由二叉树的先序序列和中序序列可以唯一确定一棵二叉树。 12、由二叉树的中序序列和后序序列可以唯一确定一棵二叉树。 13、由二叉树的先序序列和后序序列可以唯一确定一棵二叉树。 14、给定一组权值，可以唯一构造出一棵赫夫曼树。 15、赫夫曼树一定是完全二叉树。 16、赫夫曼树中没有度为 1 的结点。

17、在赫夫曼编码中，当两个字符出现的频率相同时，其编码也相同，对于这种情形应作特殊处理。

18、将一棵树转换成二叉树（即，孩子兄弟树）存储，则根结点没有左子树。

三、填空题

1、三个结点的树的共有___________种形态，三个结点的二叉树共有___________种形态。 2、已知二叉树中叶子结点数为50，仅有一个孩子的结点数为30，则总结点数为________。 3、深度为 6 的满二叉树共有___________个度为 2 的分支结点。

4、在二叉链表中，判断某指针p所指结点为叶子结点的条件是_______________________。 5、任何非空树中有且仅有一个结点没有前驱结点，该结点就是树的___________。 6、已知树中结点总数为 n，则此树中所有结点的度之和为___________。

7、在具有n个结点的各棵树中，其中深度最小的那棵树的深度是___________，它共有___________个叶子结点和___________个分支结点；其中深度最大的那棵树的深度是

- 20 -