江南大学网络教育数据结构第二阶段练习题.docVIP

第PAGE5页/共NUMPAGES\*ARABIC5页

江南大学网络教育第二阶段练习题

考试科目:《数据结构》第章至第章（总分100分）

__________学习中心（教学点）批次：层次：

专业：学号：身份证号：

姓名：得分：

一单选题(共10题，总分值20分，下列选项中有且仅有一个选项符合题目要求，请在答题卡上正确填涂。)

1.一棵高为k的二叉树最少有（??）个结点。（2分）

A.k-1

B.k

C.2k-1

D.2k-1

2.广义表(a,(b,(),c))的深度为（）。（2分）

A.1

B.2

C.3

D.4

3.含n个顶点的有向图最多有（??）条弧。（2分）

A.n

B.n(n-1)

C.n(n+1)

D.n2

4.设对下图从顶点a出发进行深度优先遍历，则（）是可能得到的遍历序列。（2分）

A.acfgdeb

B.abcdefg

C.acdgbef

D.abefgcd

5.具有n个顶点的有向强连通图最少有（）条弧。（2分）

A.n-1

B.n

C.n(n-1)

D.n(n-1)/2

6.下列叙述中错误的是（）。（2分）

A.树的度与该树中结点的度的最大值相等

B.二叉树就是度为2的有序树

C.有5个叶子结点的二叉树中必有4个度为2的结点

D.满二叉树一定是完全二叉树

7.由树转换而得的二叉树，根结点（）。（2分）

A.没有左子树

B.没有右子树

C.左右子树都有

D.视树的形态而定

8.一棵二叉树中第６层上最多有（）个结点。（2分）

A.２

B.31

C.32

D.64

9.将一个A[1..100，1..100]的三对角矩阵，按行优先存入一维数组B[1..298]中，则A中的元素A[66，65]在数组B中的位置K=（）。（2分）

A.195

B.196

C.197

D.198

10.按行优先存入一维数组B=，则图Ｇ中共有（）个顶点。（2分）

A.1

B.3

C.4

D.9

二多选题(共5题，总分值10分，下列选项中至少有2个或2个以上选项符合题目要求，请在答题卡上正确填涂。)

11.（）二叉排序树不可以得到一个从小到大的有序序列。（2分）

A.先序遍历;

B.中序遍历;

C.后序遍历;

D.层序遍历

12.对线索二叉树叙述正确的是（）。（2分）

A.加上线索的二叉树称为线索二叉树

B.指向前驱和后继的指针称为线索;

C.若二叉树结点的左孩子指针为空，可用其指向其前驱;

D.若二叉树结点的右孩子指针为空，可用其指向其后继;

E.对二叉树以某种次序遍历使其变为线索二叉树的过程叫做线索化

13.以下说法中正确的是（）。（2分）

A.无向图中的极大连通子图称为连通分量;

B.连通图的广度优先遍历中一般要采用队列来暂存刚访问过的顶点;

C.图的深度优先遍历中一般要采用栈来暂存刚访问过的顶点;

D.有向图的遍历不可采用广度优先遍历方法

14.已知广义表L=（（x,y,z），a，（u，t），w），下列运算中结果为原子项的是（）。（2分）

A.tail(head（tail（tail（L））））

B.head（tail（L））

C.tail（head（L））

D.head(head（tail（tail（L））））

15.先序序列和中序序列相同的二叉树有（）。（2分）

A.空二叉树;

B.左单支树;

C.右单支树;

D.根树

三判断题(共9题，总分值9分正确的填涂“A”，错误的填涂“B”。)

16.最小生成树是指边数最少的生成树。（1分）（?错?）

17.二叉树中序线索化后，不存在空指针域。（1分）（?错?）

18.若图G有环，则G不存在拓扑排序序列。（1分）（?对?）

19.二叉树不是树的特殊情况。（1分）（?对?）

20.具有10个叶结点的二叉树中，有9个度为2的结点。（1分）（?对?）

21