内容发布更新时间 : 2024/5/3 7:06:52星期一 下面是文章的全部内容请认真阅读。

数据结构A.B卷及其参考答案beta2.0

————————————16数学与计算机系<计科>2017.6.1 数据结构试卷A

本试卷卷面满分100分，答题时间120分钟。

题号 得分 一 二 三 四 五 六 七 八 总分 复核人

得分 评卷人 一、选择题（共15小题，每题2分，共30分）

1.数据结构是一门研究数值计算的程序设计问题中计算机的（ ）以及它们之间 的（ ）运算的学科。 （ ） A.操作对象 关系 B.计算方法 逻辑存储 C.数据映象 结构 D.运算 算法 2．栈和队列的共同点是： （ ） A.都是先进后出 B.都是先进先出 C.只允许在端点出插入和删除 D.没有共同点 3．在数据结构中，从逻辑上可以 把数据结构分成： （ ） A.动态结构和静态结构 B.紧凑结构和非紧凑结构 C.线性结构和非线性结构 D.内部结构和外部结构 4.链表是一种采用 （ ） 存储结构存储的线性表。 （ ） A．顺序 B．链式 C．星式 D ．网状 5.判定一个循环队列QU（最多元素m0）为满队列的条件是： （ ） A. QU?front==QU?rear B.QU?front ！=QU?rear

C. QU?front==（QU?rear+1）%m0 D.QU?front ！=（QU?rear+1）%m0 6．一个向量第一个元素的存储地址是100，每个元素的长度为2，则第5个元素的地址是： （ ） A．110 B．108 C．100 D．120 7．线性表若采用链式存储结构时，要求内存中可用存储单元的地址。 （ ） A．必须是连续的 B．部分地址必须是连续的 C．一定是不连续的 D．连续或不连续都可以

8．有8个结点的无向连通图最少有（ ） 条边。 （ ） A．5 B．6 C． 7

9．设某完全无向图中有n个顶点，则该完全无向图中有（ ）条边。

(A) n(n-1)/2 (B) n(n-1) (C) n2 (D) n2-1 10.设栈的输入序列是（1,2,3,4），则（ ）不可能是其出栈序列。 （A）1243 （B）2134 （C）1432 （D）4312 11.设串s1=“ABCDEFG”，s2=“PQRST”，函数concat(x,y)返回x和y串的连接串，substr(s,i,j)返回串s从序号i的字符开始的j个字符组成的字串，len(s)返回串s的长度，则concat(substr(s1,2,len(s2)),substr(s1,len(s2),2))的结果是（ ）。

（A）BCDEF （B）BCDEFG （C）BCPQRST （D）BCDEFEF

12.假定在一棵二叉树中，双分支结点数为11个，单分支结点数为23个，则叶子结点数为（ ）。

（A）13 （B）16 （C）12 （D）14 13.任何一个无向连通图的最小生成树（ ）。

（A）只有一棵 （B）有一棵或多棵 （C）一定有多棵 （D）可能不存在

14.在一个长度为n的顺序表中删除第i个元素，需要向前移动（ ）个元素。 （A）n-i （B）n-i+1 （C） n-i-1 （D） i+1

15.在中序遍历非空二叉树所得的序列中，根结点的右边包含（ ）。 （A）右子树上的所有结点 （B）右子树上的部分结点 （C）左子树上的所有结点 （D）左子树上的部分结点 得分 评卷人

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

1.队是一种插入与删除操作分别在表的两端进行的线性表，是一种先进后出型结。

( )

2.栈和队列的存储方式既可是顺序方式，也可是链接方式。 ( ) 3.二叉树中每个结点有两个孩子结点，而对一般的树则无此限制。 ( ) 4.有n个顶点的连通图至少有n条边。 ( ) 5.用二叉链表法存储包含n个结点的二叉树，结点的2n个指针区域中有n+1个为空指针。 ( ) 6.线性表在顺序存储时，逻辑上相邻的元素未必在存储的物理位置次序上相邻。 ( ) 7.一个栈的输入序列是12345，则栈的输出序列不可能是12345。 ( ) 8．队是一种插入与删除操作分别在表的两端进行的线性表，是一种先进后出型结构。 （ ） 9．满二叉树中所有结点个数是2K-1个，其中k是树的深度。 （ ） 10．广义表可以递归定义。 （ ） 得分 评卷人

三、填空题（每空2分，共20分）

1.一个算法的效率可分为_ _效率和 效率。

2．若在采用顺序存储结构的长度为n的线性表的第i个位置插入一个新元素，所需移动元素的个数是 。

3．设有两个串p和q，求q在p中首次出现的位置的运算称作 。 4．一个具有n（n>1）个顶点的连通图至少有 条边。 5．稀疏矩阵的两种常用的压缩存储方式是 。 6．有n个顶点无向图最多可能有__ ___ 条边。

7.已经二叉树的前序序列为ABDEGCFHIJ，中序序列为DBGEAHFIJC，则其后序序列为 。

8.队列的插入操作在 进行，删除操作在 进行。

得分 评卷人

四、解答题(共3小题，共24分)

1.请画出下图的邻接矩阵和邻接表。（8分）

2. 已知一棵二叉树的前序和中序序列，试画出这棵二叉树，并求该二叉树的后

序序列。（本题8分）

前序序列：A, B, C, D, E, F, G, H, I, J 中序序列：C, B, A, E, F, D, I, H, J, G