湖北文理学院数据结构试题与答案A.pdf

湖北文理学院数据结构试题与答案A--第1页

湖北文理学院2011－2012学年度下学期

《数据结构与算法》试卷A

专业：计算机科学与技术

姓名：学号：班级：

题目一二三四五总分

满分1020182230100

得分

得分评卷人一、判断题（本题共10小题，每小题1分，共计10分）。

（正确的打√，错的打×）

1、顺序循环队列Q空的条件是：Q.front==Q.rear.()

2、关键路径是始点到终点最小长度的路径。()

3、序列（5,6,7,20,15,8,9,25,22，13）是一个堆。()

4、在插入排序和选择排序中，若原始记录已基本有序，则较适合选用选择排序。()

5、顺序表是随机存取，存取操作的时间为O（1）。()

6、已知一棵二叉树的先序序列和后序序列，一定能构造出该二叉树。()

7、有向图用邻接矩阵表示后，顶点i的出度等于邻接矩阵中第i行的元素个数。()

8、归并排序的时间性能不随记录序列中关键字的分布而改变（与初始状态无关）。()

9、在数据结构中，数据的基本单位是数据项。（）

10、对任意一个图，从某顶点出发进行一次广度优先或深度优先遍历，可访问图的所有顶点。()

得分评卷人

二、填空题（本题共10小题，每小题2分，共计20分）。

（请将正确答案填入空格内，答案是确定和唯一的）

1、任意一棵具有n个结点的二叉树，若它有m个叶子，则该二叉树上度为1的结点数为_____个。

2、常用算法的描述方法有：自然语言、、和流程图。

3、某二叉树的先根遍历序列为IJKLMNO，中根遍历序列为JLKINMO，则该二叉树中根结点的右孩子是

。

湖北文理学院数据结构试题与答案A--第1页第1页共8页

湖北文理学院数据结构试题与答案A--第2页

4、堆排序的时间复杂性为，空间复杂性为。

5、二维数组A[6，7]，按行优先存储，每个元素占2个字节,A基址为600,则元素A[4,5]的存储地址

是。

6、对广义表C=（a,（b,c,d））的运算Tail(Tail(Head((Tail(C))))的结果是。

7、设有一组初始关键字值序列为（49，81，55，36，44，88），则利用快速排序的方法，以第一个

关键字值为基准得到的一次划分为_________________________________________。

8、图的存储结构主要有两种，分别是和。

9、设一个顺序栈S，元素s1，s2，s3，s4，s5，s6依次进栈，如果6个元素的退栈顺序为s2，s3，

s4，s6，s5，s1，则顺序栈的容量至少为________。

10、对于一棵满二叉树，若有m个叶子，则树中结点数为____________。