数据结构试题及答案完整版第六章

一、 单项选择题

1.已知一个长度为16的顺序L，气元素按关键字有序排列，或采用折半查找法查找一个不在L中存在的元素，则关键字的比较次数最多的是（ ）。

A．4 B. 5 C. 6 D. 7

2.顺序查找适合于存储结构为（ ）的线性表。

A.顺序存储结构或链式存储结构 B.散列存储结构 C.索引存储结构 D.压缩存储结构

3.对长度为n的有序单链表，若查找每个元素的概率相等，则顺序查找表中任意一个元素的查找成功的平均查找长度为（ ）。

A.n/2 B.(n+1)/2 C.(n-1)/2 D.n/4

4.对长度为3的顺序表进行查找，若查找的第一个元素概率为1/2，查找第二个元素的概率为1/3，查找第三个元素的概率为1/6，则查找表中任意一个元素的平均查找长度为( )。

A.5/3 B.2 C.7/3 D.4/3

5.当采用分块查找时，数据的组织方式为（ ）。 A.数据分成若干块，每块内数据有序

B.数据分成若干块，每块内数据不必有序，但块间

第六章树和二叉树（下载后用阅读版式视图或web版式可以看清）

习 题

一、选择题

1．有一“遗传”关系：设x是y的父亲，则x可以把它的属性遗传给y。表示该遗传关系最适合的数据结构为( )。 A.向量 B.树 C图 D.二叉树 2．树最合适用来表示( )。

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

3．树B的层号表示为la，2b，3d，3e，2c，对应于下面选择的( )。 A. la (2b (3d,3e),2c) B. a(b(D,e),c) C. a(b(d,e),c) D. a(b,d(e),c)

4.高度为h的完全二叉树至少有( )个结点，至多有( )个结点。 A. 2h_l B.h C．2h-1 D. 2h

5.在一棵完全二叉树中，若编号为f的结点存在右孩子，则右子结点的编号为( )。 A. 2i B. 2i-l C. 2i+l D. 2i+2

第六章习题

1．试分别画出具有3个结点的树和3个结点的二叉树的所有不同形态。 2．对题1所得各种形态的二叉树，分别写出前序、中序和后序遍历的序列。

3．已知一棵度为k的树中有n1个度为1的结点，n2个度为2的结点，……，nk个度为k的结点，则该树中有多少个叶子结点并证明之。

4.假设一棵二叉树的先序序列为EBADCFHGIKJ，中序序列为ABCDEFGHIJK，请画出该二叉树。 5．已知二叉树有50个叶子结点，则该二叉树的总结点数至少应有多少个？ 6．给出满足下列条件的所有二叉树：

① 前序和后序相同 ② 中序和后序相同 ③ 前序和后序相同

7． n个结点的K叉树，若用具有k个child域的等长链结点存储树的一个结点，则空的Child域有多少个？ 8．画出与下列已知序列对应的树Ｔ：

树的先根次序访问序列为GFKDAIEBCHJ； 树的后根次序访问序列为DIAEKFCJHBG。

9．假设用于通讯的电文仅由8个字母组成，字母在电文中出现的频率分别为：

0.07，0.19，0.02，0.06，0.32，0.03，0.21，0.10 请为这8个字母设计哈夫曼编码。

10．已知二叉树采用二叉链表存放,要求返回二叉树T的后序序列中

1、下图所示的4棵二叉树中，不是完全二叉树的是（ ）

A B C D

2、二叉树的前序遍历序列中，任意一个结点均处在其子女结点的前面，这种说法（ ）。 A、正确 B、错误 C、不一定

3、已知某二叉树的后序遍历序列是dabec，中序遍历序列是debac，它的前序遍历序列是（ ）。 A、acbed B、decab C、deabc D、cedba

4、如果T2是由有序树T转换而来的二叉树，那么T中结点的后序就是T2中结点的（ ）。 A、前序 B、中序 C、后序 D、层次序

5、深度为5的二叉树至多有（ ）个结点。 A、16 B、32 C、31 D、10

6、在一个非空二叉树的中序遍历序列中，根结点的右边（ ）。 A、只有右子树上的所有结点 B、只有右子树上的部分结点 C、只有左子树上的部分结点 D、只有左子树上的所有结点

7、树最适合用来表示（ ）。

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

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

8、任何一棵二叉树的叶结点在先序、中序和后序遍历序列中的相对次序（ ）

第六章 树和二叉树

一、选择题

1．已知一算术表达式的中缀形式为 A+B*C-D/E，后缀形式为ABC*+DE/-，其前缀形式为( )

A．-A+B*C/DE B. -A+B*CD/E C．-+*ABC/DE D. -+A*BC/DE 【北京航空航天大学 1999 一、3 （2分)】

2．算术表达式a+b*（c+d/e）转为后缀表达式后为（ ）【中山大学 1999 一、5】

A．ab+cde/* B．abcde/+*+ C．abcde/*++ D．abcde*/++ / 3. 设有一表示算术表达式的二叉树（见下图），

+ 它所表示的算术表达式是（ ） + 【南京理工大学1999 一、20（2分）】 * C - * A. A*B+C/(D*E)+(F-G) B. (A*B+C)/(D*E)+(F-G)

D E F G A B C. (A*B+C)/(D*E+（F-G）) D. A*B+C/D*E+F-G

4. 设树T的度为4，其中度为1，2，3和4的结点个数分别为4，2，1，1 则T中的叶子数为（ ）

A．5

第一章 概论

一、选择题

1、研究数据结构就是研究（ D ）。

A. 数据的逻辑结构 B. 数据的存储结构

C. 数据的逻辑结构和存储结构 D. 数据的逻辑结构、存储结构及其基本操作

2、算法分析的两个主要方面是（ A ）。

A. 空间复杂度和时间复杂度 B. 正确性和简单性 C. 可读性和文档性 D. 数据复杂性和程序复杂性 3、具有线性结构的数据结构是（ D ）。

A. 图 B. 树 C. 广义表 D. 栈

4、计算机中的算法指的是解决某一个问题的有限运算序列，它必须具备输入、输出、（ B ）等5个特性。

A. 可执行性、可移植性和可扩充性 B. 可执行性、有穷性和确定性

C. 确定性、有穷性和稳定性 D. 易读性、稳定性和确定性 5、下面程序段的时间复杂度是（ C ）。 for(i=0;i

A. O(m2) B. O(n2) C. O(m*n) D. O(m+n) 6、算法是（ D ）。

A. 计算机程序 B. 解决问题的计算方法 C. 排序算法 D. 解决问题的有限运算序列

7、某算法的语句执行频度

第一章 概论

一、选择题

1、研究数据结构就是研究（ D ）。

A. 数据的逻辑结构 B. 数据的存储结构

C. 数据的逻辑结构和存储结构 D. 数据的逻辑结构、存储结构及其基本操作

2、算法分析的两个主要方面是（ A ）。

A. 空间复杂度和时间复杂度 B. 正确性和简单性 C. 可读性和文档性 D. 数据复杂性和程序复杂性 3、具有线性结构的数据结构是（ D ）。

A. 图 B. 树 C. 广义表 D. 栈

4、计算机中的算法指的是解决某一个问题的有限运算序列，它必须具备输入、输出、（ B ）等5个特性。

A. 可执行性、可移植性和可扩充性 B. 可执行性、有穷性和确定性

C. 确定性、有穷性和稳定性 D. 易读性、稳定性和确定性 5、下面程序段的时间复杂度是（ C ）。 for(i=0;i

A. O(m2) B. O(n2) C. O(m*n) D. O(m+n) 6、算法是（ D ）。

A. 计算机程序 B. 解决问题的计算方法 C. 排序算法 D. 解决问题的有限运算序列

7、某算法的语句执行频度

第一章 概论

一、选择题

1、研究数据结构就是研究（ D ）。

A. 数据的逻辑结构 B. 数据的存储结构

C. 数据的逻辑结构和存储结构 D. 数据的逻辑结构、存储结构及其基本操作

2、算法分析的两个主要方面是（ A ）。

A. 空间复杂度和时间复杂度 B. 正确性和简单性 C. 可读性和文档性 D. 数据复杂性和程序复杂性 3、具有线性结构的数据结构是（ D ）。

A. 图 B. 树 C. 广义表 D. 栈

4、计算机中的算法指的是解决某一个问题的有限运算序列，它必须具备输入、输出、（ B ）等5个特性。

A. 可执行性、可移植性和可扩充性 B. 可执行性、有穷性和确定性

C. 确定性、有穷性和稳定性 D. 易读性、稳定性和确定性

5、下面程序段的时间复杂度是（ C ）。 for(i=0;i

A. O(m2) B. O(n2) C. O(m*n) D.

O(m+n)

6、算法是（ D ）。

A. 计算机程序 B. 解决问题的计算方法 C. 排序算法 D. 解决问题的有限运算序列

7、某算法的语句执行频度

第一章 概论

一、选择题

1、研究数据结构就是研究（ D ）。

A. 数据的逻辑结构 B. 数据的存储结构

C. 数据的逻辑结构和存储结构 D. 数据的逻辑结构、存储结构及其基本操作

2、算法分析的两个主要方面是（ A ）。

A. 空间复杂度和时间复杂度 B. 正确性和简单性 C. 可读性和文档性 D. 数据复杂性和程序复杂性 3、具有线性结构的数据结构是（ D ）。

A. 图 B. 树 C. 广义表 D. 栈

4、计算机中的算法指的是解决某一个问题的有限运算序列，它必须具备输入、输出、（ B ）等5个特性。

A. 可执行性、可移植性和可扩充性 B. 可执行性、有穷性和确定性

C. 确定性、有穷性和稳定性 D. 易读性、稳定性和确定性 5、下面程序段的时间复杂度是（ C ）。 for(i=0;i

A. O(m2) B. O(n2) C. O(m*n) D. O(m+n) 6、算法是（ D ）。

A. 计算机程序 B. 解决问题的计算方法 C. 排序算法 D. 解决问题的有限运算序列

7、某算法的语句执行频度

第一章 概论

一、选择题

1、研究数据结构就是研究（ D ）。

A. 数据的逻辑结构 B. 数据的存储结构

C. 数据的逻辑结构和存储结构 D. 数据的逻辑结构、存储结构及其基本操作

2、算法分析的两个主要方面是（ A ）。

A. 空间复杂度和时间复杂度 B. 正确性和简单性 C. 可读性和文档性 D. 数据复杂性和程序复杂性 3、具有线性结构的数据结构是（ D ）。

A. 图 B. 树 C. 广义表 D. 栈

4、计算机中的算法指的是解决某一个问题的有限运算序列，它必须具备输入、输出、（ B ）等5个特性。

A. 可执行性、可移植性和可扩充性 B. 可执行性、有穷性和确定性

C. 确定性、有穷性和稳定性 D. 易读性、稳定性和确定性

5、下面程序段的时间复杂度是（ C ）。 for(i=0;i

A. O(m2) B. O(n2) C. O(m*n) D.

O(m+n)

6、算法是（ D ）。

A. 计算机程序 B. 解决问题的计算方法 C. 排序算法 D. 解决问题的有限运算序列

7、某算法的语句执行频度