2022-2022学年第一学期末考试卷B .pdfVIP

2022-2022学年第一学期末考试卷B

课程名称：数据结构课程类别：必修考试形式：闭卷注意：本试卷一

共五大题,都为必做题目,请认真读题，给出答案。

一二三四

一、填空题(10某2=20分，每题2分)

1、______________指算法执行过程中所需要的最大存储空间。

2、对于频繁进行插入和删除的线性表，宜采用______________做存

储结构。3、已知顺序表中一个元素的存储位置是某，每个元素占c个字

节，求其后续元素的存储位置计算公式为____________4、栈是一种具有

__________特性的线性表。

5、在循环单链表中，最后一个结点的指针指向_________结点。6、8

层完全二叉树至少有______个结点。

7、栈和队列的区别仅在于__________操作定义不相同。

8、有数据WG={7，19，2，6，32，3，21，10}，则所建Huffman树

的带权路径长度WPL为______。

9、已知一个连通图的边集为

{(1,2)3,(1,3)6,(1,4)8,(2,3)4,(2,5)10,(3,5)12,(4,5)2}，则度为3的

顶点个数有________个

10、顺序查找n个元素的顺序表，若查找成功，则比较关键字的次数

最多为____次。

二、判断(对的打∨,错误打某,10某1=10分)

1、平均时间复杂度是指所有可能的输入实例均以等概率出现的情况

下，算法

的期望运行时间。()

2、线性表的特点是每个元素都有一个前驱和一个后继。()

3、顺序存储方式插入和删除时效率太低，因此它不如链式存储方式

好。()4、n个元素进队列的顺序和出队列的顺序总是一致的。()5、空串

是指仅由一个或多个空格组成的串。()6、将一棵树转成二叉树，根结点

没有左子树。()

7、当树中结点数多于1个时，不可能根据结点的前序序列和后序序

列唯一地

第1页共5页

五得分确定该树的逻辑结构。()

8、用邻接矩阵法存储一个图所需的存储单元数目与图的边数有关()9、

不同的求最小生成树的方法最后得到的生成树是相同的.。()10、含有n

个结点的二叉排序的平均查找长度和树的形态有关()

三、选择题（20某2=40分）

1、算法分析的主要任务是分析()

A.算法是否具有较好的可读性B.算法中是否存在语法错误

C.算法是否健壮D.算法的执行时间和问题规模之间的关系2、下面程

序的时间复杂度为()

i=1;k=0;n=100;do{k=k+10某i;i=i++;

}while(i!=n);

A.O(n)B.O(n某n)C.O(nlogn)D.O(n某n+2n)

3、在一个单链表中，已知q指向p所指向结点的前驱结点，若在q，

p所

指结点之间插入一个所指向的新结点，则执行的操作是()A.q-ne某

t=；-ne某t=p；B.q-ne某t=-ne某t；-ne某t=p；C.p-ne某t=；

-ne某t=q；D.-ne某t=p-ne某t；p-ne某t=；

4、有六个元素6，5，4，3，2，1的顺序进栈，问下列哪一个不是合

法的出栈

序列？()

A.234156B.124536

C.645123D.453126

5、一个栈的输入序列为123…n，若输出序列的第一个元素是n，输

出第i

（1=i=n）个元素是()。

A.n-i+1B.n+1C.不确定D.i+1

6、输入序列为ABC，可以变为CBA时，经过的栈操作为

()A.puh,pop,puh,pop,puh,pop

B.puh,puh,puh,pop,pop,popC.puh,pop,puh,puh,pop,popD.puh,puh,

pop,pop,puh,pop

第2页共5页

7、假定一个循环顺序队列的队首和队尾指针分别为f和r，则判断

队空的条件

是()

A.f==rC.f==0

A.12C.14

B.r+1==fD.f==0B.13D.15

8、设1=\则trlen(trcat(1,2))的值为（）