数据结构试卷答案

《数据结构》模拟试卷

专业________ 学号_________ 姓名________ 成绩_______ 一、选择题（本大题共20小题，每小题2分，共40分） 1.一个栈的输入序列为1，2，3，4，下面哪一个序列不可能是这个栈的输出序列？（C ）

A. 1，3，2，4 B. 2，3，4，1 C. 4，3，1，2 D. 3，4，2，1

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

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

3. 请指出在顺序表{2、5、7、10、14、15、18、23、35、41、52}中，用二分法查找关键码

12需做（ C ）次关键码比较。 A.2 B.3 C.4 D.5

4．下面关于图的存储的叙述中，哪一个是正确的。（ A ） A．用相邻矩阵法存储图,占用的存储空间数只与图中结点个数有关,而与边数无关

B．用相邻矩阵法存储图,占用的存储空间数只与图中边数有关,而与结点个数无关

C．用邻接表法存储图，占用的存储空间数只与图中结点个数有关，

而与边数无关

D．用邻接表法存储图，占用的存储空间数只与图中边数有关，而与结点个数无关

5.对一棵查找树根结点而言，左子树中所有结点与右子树中所有结点的关键字( A )

A.小于 B.大于 C.等于 D.不小于

6.算法分析的目的是（ C ）；

Ａ. 找出数据结构的合理性 B. 研究算法中的输入和输出的关系 C. 分析算法的效率以求改进 D. 分析算法的易懂性和文档性

7.线性表的存储结构是一种（A）的存储结构。

A．随机存取B．顺序存取C．索引存取D．HASH存取 8.若线性表采用顺序存储结构，每个元素占用4个存储单元，第一个元素的存储地址为100,

则第12个元素的存储地址是（ B ） A．112 B.144 C.148 D.412

9.在一个长度为n 的顺序表中，向第i个元素（1≤i≤n＋１）之前插入一个新元素时，

需要向后移动（ B ）个元素。 A.n-i B.n-i+1 C.n-i-1 D.i

10. 已知某二叉树的后序遍历序列是dabec,中序遍历序列是debac,它的前序遍历（ D ）。

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

11.若由森林转化得到的二叉树是非空的二叉树，则二叉树形状是

（ C ）

A. 根结点无右子树的二叉 B. 根结点无左子树的二叉树

C. 根结点可能有左二叉树和右二叉树 D. 各结点只有一个儿子的二叉树

12.删除一个双链表中结点p(非头结点和尾结点)的操作是（ B ） A. p->left->right=p->left;p->right->left=p->right B. p->left->right=p->right;p->right->left=p->ieft C. p->left=NULL;p->right=NULL D. p->right->left=p;p->left->right=p

13. 非空的循环单链表head的尾结点（由p所指向）满足（ C ）。 A.p->next=NULL; B.p=NULL; C.p->next=head; D.p=head;

14．设高度为h的二叉树上只有度为0和度为2的结点，则此类二叉树中所包含的结点数至少为（ B ）。

A．2h B．2h-1 C．2h+l D．h+l

15. 串是一种特殊的线性表，其特殊性体现在（ D ）。 A．可以顺序存储B．数据元素是一个字符 c．可以链接存储D．数据元素可以是多个字符

16.设有两个串p和q，求q在p中首次出现的位置的运算称作（B ）。

A．连接B．模式匹配C．求子串D．求串长 17. 栈和队列的共同点是（ C ）。 A．都是先进后出B．都是先进先出

C．只允许在端点处插入和删除元素D．没有共同点 18．n个顶点的强连通图中至少含有( B )。 A.n—l条有向边 B.n条有向边

C.n(n—1)／2条有向边 D.n(n一1)条有向边

19．判定一个循环队列QU(最多元素为m0)为满队列的条件是( C ) A．QU->front==QU->rear B．QU->front!=QU->rear C

．

QU->front==(QU->rear+1)

％

m0

D．QU->front!=(QU->rear+1)％m0

20 .设结点x和结点y是二叉树T中的任意两个结点，若在先根序列中x在y之前，而在后

根序列中x在y之后，则x和y的关系是（ C ） A.x是y的左兄弟 B.x是y的右兄弟 C.x是y的祖先 D.x是y的后代

二、判断题（每小题1分，共10分）

（×）1.线性表的长度是线性表占用的存储空间的大小。 （×）2.队列只能采用链式存储方式。

（×）3.树（或森林）转化为对应的二叉树后，两者的分支数相等。 （√）4.由二叉树的先序序列和中序序列能唯一确定一棵二叉树。 （×）5.图中一个顶点i的出度等于其邻接矩阵中第i列的非0元个数。

（√）6.线性链表中各个链结点之间的地址不一定要连续。 （×）7.线性表的链接存储，表中元素的逻辑顺序与物理顺序一定相同。

（×）8.二叉树中任何一个结点的度都是2。

（×）9.一个无向图的邻接矩阵中各元素之和与图中边的条数相等。 （√）10.一棵哈夫曼树中不存在度为1的结点。 三、填空题（每小题2分，共20分）

1.当问题的规模n趋向无穷大时，算法执行时间T(n)的数量级被称为算法的时间复杂度

______。

2.空串的长度是__0______；空格串的长度是__1______。

3.在一棵度为3的树中，度为2的结点个数是1，度为0的结点个数是6，则度为3的结点

个数是___2_____。

4 . 有N个顶点组成的无向连通图，最多可以有___n(n-1)/2__________________条边。

5. 在有n个结点的二叉链表中，空链域的个数为____n+1_____。 6. 一棵有n个叶子结点的哈夫曼树共有____2n-1______个结点。 7.含有100个结点的树有________99____条边。

8.在一个无环有向图G中，若存在一条从顶点i到顶点j的弧，则在顶点的拓扑序列中，顶点i与顶点j的先后次序是___i在前,j在后_________。

9.在一个无向图的邻接表中，若表结点的个数是m，则图中边的条数是____m/2________条。

10.对序列(49,38,65,97,76,27,13,50)采用快速排序法进行排序，以序列的第一个元素为基准元素得到的划分结果是___(13,38,27)49(76,97,65.50)_______________。

四、简答题（每小题10分，共30分）

1.什么是堆？试对序列{40，38，60，95，76，10，25，50，99}用堆排序方法进行从小到大排序。要求写出主要过程。略

2.已知二叉树的先序、中序和后序序列分别如下，但其中有一些已模糊不清，构造出该二树

先序序列ABCDEFGH 中序序列BDECAGFH

后序序列EDCBGHFA自己画出二叉树

3.已某个不带权的无向图采用邻接矩阵存储方法依次将顶点的数据信息存放于一维数组ABCDEFGH中，边的信息存放于邻接矩阵中，邻接矩阵为

0 1 1 0 0 0 0 0 1 0 0 0 1 0 1 1

1 0 0 1 0 1 0 0 0 0 1 0 0 1 0 0 0 1 0 0 0 0 0 1 0 0 1 1 0 0 0 0 0 1 0 0 0 0 0 0 0 1 0 0 1 0 0 0

请写出从顶点A出发对该图进行深度优先遍历后得到的顶点序列。略