《数据结构》期末考试题及答案 .pdfVIP

2011-2012学年第一学期期末考查

《数据结构》试卷

（答案一律写在答题纸上，在本试卷上做答无效）

一、选择（每题1分，共10分）

1.长度为n的线性表采用顺序存储结构，在其第i个位置插入一个新元素的算法时间复

杂度为（）

2

A.O(0)B.O(1)C.O(n)D.O(n)

2.六个元素按照6，5，4，3，2，1的顺序入栈，下列哪一个是合法的出栈序列？（）

A.543612B.453126C.346512D.234156

3.设树的度为4，其中度为1、2、3、4的结点个数分别是4、2、1、2，则树中叶子个数

为（）

A.8B.9C.10D.11

4.设森林F对应的二叉树B有m个结点，B的右子树结点个数为n，森林F中第一棵树

的结点个数是（）

A.m-nB.m-n-1C.n+1D.m+n

5.若一棵二叉树具有10个度为2的结点，5个度为1的结点，则度为0的结点个数是（）

A.9B.11C.15D.不确定

6.下列哪一个方法可以判断出一个有向图是否有环。（）

A.深度优先遍历B.拓扑排序C.求最短路径D.求关键路径

7.第7层有10个叶子结点的完全二叉树不可能有（）个结点。

A.73B.234C.235D.236

8.分别用以下序列构造二叉排序树，与用其他三个序列构造的结果不同的是（）

A.（100,80,90,60,120,110,130）B.（100,120,110,130,80,60,90）

C.（100,60,80,90,120,110,130）D.（100,80,60,90,120,130,110）

9.对一组数据（84，47，25，15，21）排序，数据的排列次序在排序过程中变化如下：

（1）8447251521（2）1547258421（3）1521258447（4）1521254784则采用

的排序方法是（）

1

A.B.C.D.

10.

A.B.

C.D.

115

1.

2.Pdatanext

3.

4.

5.n

6.A7BAB