数据结构各章习题

第3章 栈和队列 一 单项选择题

1. 一个栈的入栈序列a，b，c，d，e，则栈的不可能的输出序列是__ __。 A. edcba B. decba C. dceab D. abcde

2. 若已知一个栈的入栈序列是1，2，3，?，n，其输出序列为p1，p2，p3，?，pn，若p1=n，则pi为___ _。

A. i B. n=i C. n-i+1 D. 不确定

3. 栈结构通常采用的两种存储结构是__ __。

4. 判定一个顺序栈ST（最多元素为m）为空的条件是___ _。 5. 判定一个顺序栈ST（最多元素为m）为栈满的条件是__ __。 6. 栈的特点是____，队列的特点是____。 A. 先进先出 B. 先进后出 7. 一个队列的数据入列序列是1，2，3，4，则队列的出队时输出序列是__ __ 。 8. 判定一个循环队列Q（最多元素为m）为空的条件是 _ ___, 为满的条件是_ ___。

9. 循环队列用数组A[0，m-1]存放其元素值，已知其头尾指针分别是front和rear，则当前队列中的元素个数是____。

A. (rear-front+m)%m B. rear-front+1 C. rear-front-1 D. rear-front 10. 栈和队列的共同点是_ ___。

A. 都是先进后出 B. 都是先进先出 C. 只允许在端点处插入和删除元素 D. 没有共同点

二 填空题（将正确的答案填在相应的空中） 1. 向量（数组）、栈和队列都是_ ___结构，可以在向量的__ __位置插入和删除元素；对于栈只能在_ ___插入和删除元素；对于队列只能在__ __插入元素和__ __删除元素。

2. 向栈中压入元素的操作是__ __。对栈进行退栈时的操作是__ __。（写涵数调用语句）

3. 在一个循环队列中，队首指针指向队首元素的__ __。 4. 从循环队列中删除一个元素时，其操作是_ ___。（写涵数调用语句）

三、简答题

1. 什么是栈？什么是队列？它们各自的特点是什么？ 2. 线性表、栈、队列有什么异同？ 3. 简述栈的入栈、出栈操作的过程。（用文字描述） 4. 在循环队列中简述入队、出队操作的过程。（用文字描述） 5. 在什么情况下，会选择使用栈或队列数据结构？

6. 顺序队的“假溢出”是怎样产生的？如何知道循环队列是空还是满？

四、读栈队相关的程序，写出程序的运行结果

五、算法设计题

1. 输入一个任意的非负十进制整数,输出与其等值的八进值数。

5

2. 试写一个算法判别读入的一个以‘@’为结束符的字符序列是否是“回文”。。 3. 设计一算法能判断一个算术表达式中的圆括号配对是否正确。（提示：对表达式进行扫描，凡遇到“（”就进栈，遇到“）”就退出栈顶的“（”，表达式扫描完毕时栈若为空则圆括号配对正确。

第5章 树与二叉树 一、 单项选择题

1.树最适合用来表示__ __。

A. 有序数据元素 B. 无序数据元素

C. 元素之间具有分支层次关系的数据 D. 元素之间无联系的数据

2.假定在一棵二叉树中，双分支结点数为15，单分支结点数为30个，则叶子结点数为 个。

A．15 B．16 C．17 D．47

3. 按照二叉树的定义，具有3个结点的不同形状的二叉树有__ __种。 A. 3 B. 4 C. 5 D. 6 5. 深度为5的二叉树至多有__ __个结点。 A. 16 B. 32 C. 31 D. 10 6. 如果某二叉树的前根次序遍历结果为stuwv，中序遍历为uwtvs，那么该二叉树的后序为__ __。

A. uwvts B. vwuts C. wuvts D. wutsv

7. 二叉树的前序遍历序列中，任意一个结点均处在其子女结点的前面，这种说法_ ___。 A. 正确 B. 错误

8. 某二叉树的前序遍历结点访问顺序是abdgcefh，中序遍历的结点访问顺序是dgbaechf，则其后序遍历的结点访问顺序是__ __。

A. bdgcefha B. gdbecfha C. bdgaechf D. gdbehfca 9. 在一非空二叉树的中序遍历序列中，根结点的右边____。

A. 只有右子树上的所有结点 B. 只有右子树上的部分结点 C. 只有左子树上的部分结点 D. 只有左子树上的所有结点 10. 一棵二叉树如图6.1所示，其中序遍历的序列为 __。

a b d g e h c f

A. abdgcefh B. dgbaechf C. gdbehfca D. abcdefgh

11．设a,b为一棵二叉树上的两个结点，在中序遍历时，a在b前的条件是 。

A．a在b的右方 B．a在b的左方 C．a是b的祖先 D．a是b的子孙 12. 已知某二叉树的后序遍历序列是dabec，中序遍历序列是debac，它的前序遍历序列是_ ___。

6

图6.1

A. acbed B. decab C. deabc D. cedba

13.已知一棵完全二叉树的结点总数为9个，则最后一层的结点数为 。 A. 1 B. 2 C. 3 D. 4 14. 如图6.2所示的4棵二叉树，____不是完全二叉树。

(A) (B) (C) (D)

图6.2

二、 填空题（将正确的答案填在相应的空中） 1. 将树转化为二叉树的基本目的是___ _。

2. 深度为k的完全二叉树至少有___ _个结点。至多有_ ___个结点，若按自上而下，从左到右次序给结点编号（从1开始），则编号最小的叶子结点的编号是 ____。

3. 在一棵二叉树中，度为零的结点的个数为n0，度为2的结点的个数为 n2，则有n0=__ __。

4. 一棵二叉树的第i（i≥1）层最多有__ __个结点；一棵有n（n>0）个结点的满二叉树共有__ __个叶子和_ ___个非终端结点。

5. 哈夫曼树是指______________________________________________的二叉树 6. 有如图6.3所示的二叉树，回答以下问题： ⑴ 其中序遍历序列为____； a ⑵ 其前序遍历序列为____；

b c ⑶ 其后序遍历序列为____；

def

g h i 图6.3 一棵二叉树 三、应用题

1.分别写出下图所示二叉树的前序、中序和后序遍历序列。

2. 若二叉树中各结点值均不相同。

7

1)已知一个二叉树的中序和后序遍历序列分别为GDHBAECIF和GHDBEIFCA，请画出此二叉树。

2)已知一个二叉树的前序和中序分别为ABCDEFGH和BDCEAFHG，请画出此二叉树。

3. 一个二叉树如图所示,将其转换为树。 a b c

def

g h

i 图6.4 一棵二叉树

4．画出该森林对应的二叉树。

A G K L C I B H M D E F J O N

图6.5 森林

5．有一份电文中共使用5个字符：a、b、c、d、e，它们的出现频率依次为{5、2、1、6、4}；试画出对应的哈夫曼树，并求出每个字符的哈夫曼编码。

四、算法设计题

1. 一个二叉树以链式结构存储，分别给出求二叉树结点总数和叶子结点总数和高度的算法。

2. 一个二叉树以链式结构存储，写出在二叉树中查找值为x的结点的算法。 3. 设计算法将一个以链式存储结构的二叉树进行各种遍历

第6章 图 一、单项选择题

1．在一个图中，所有顶点的度数之和等于所有边数的____倍。

A. 1/2 B. 1 C. 2 D. 4 2．任何一个无向连通图的最小生成树 。

A.只有一棵 B.有一棵或多棵 C.一定有多棵 D.可能不存在

3．在一个有向图中，所有顶点的入度之和等于所有顶点的出度之和的____倍。

A. 1/2 B. 1 C. 2 D. 4 4．一个有n个顶点的无向图最多有____条边。

A. n B. n(n-1) C. n(n-1)/2 D. 2n 5．具有4个顶点的无向完全图有____条边。

8