2023年10月自考02142数据结构导论试题及答案含评分标准

绝密考试结束前

★

年月高等教育自学考试

202310

数据结构导论试题

课程代码:02142

请考生按规定用笔将所有试题的答案涂、写在答题纸上。

1.

答题前,考生务必将自己的考试课程名称、姓名、准考证号用黑色字迹的签字笔或钢笔

2.

填写在答题纸规定的位置上。

选择题部分

注意事项:

每小题选出答案后用铅笔把答题纸上对应题目的答案标号涂黑如需改动用橡皮

,2B。,

擦干净后再选涂其他答案标号不能答在试题卷上

,。。

一、单项选择题:本大题共15小题,每小题2分,共30分。在每小题列出的备选项中只有一项

是最符合题目要求的,请将其选出。

时间复杂度的常数阶表示为

1.

2n

A.O(1)B.O(n)C.O(n)D.O(2)

下列关于单链表的描述错误的是

2.,

所有结点通过指针链接∙形∙成链表头指针变量不一定非要用来标识

A.B.head

尾结点指针域的值称为空指针通常用尾指针来表示一个单链表

C.NULLD.

线性表实现顺序存储可使用

3.

栈队列数组链表

A.B.C.D.

设单链表中指针指向结点要删除之后的结点若存在则修改指针的操作为

4.pA,A(),

A.pnext=pnextnextB.p=pnext

C.p=pnextnextD.pnext=p

出队列操作使用的赋值语句是

5.

A.SQ.rear=SQ.rear+1B.SQ.rear=SQ.rear-1

C.SQ.front=SQ.front+1D.SQ.front=SQ.front-1

在一个具有个单元的顺序栈中假定以地址低端即单元作为栈底以为栈顶指

6.n,(0),top

针当栈未满时进行进栈操作此时

,,

不变

A.topB.top--C.top++D.top=0

浙数据结构导论试题第页共页

02142#1(4)

带头结点链队列的头指针和尾指针分别为和则判断队列空的条件为

7.frontrear,

A.front==rearB.front!=NULL

C.rear!=NULLD.front==NULL

深度为的二叉树的结点数最多为

8.k(k1)

≥

k-1kkk+1

A.2B.2-1C.2+1D.2

下列关于树形结构的描述正确的是

9.,

树形结构是线性结构树中每个结点可以有多个直接前驱结点

A.B.

树可以用顺序存储树中每个结点只能有一个直接后继结点

C.D.

对任何一棵二叉树若度数为的结点叶结点个数为度数为的结点个数为则

10.,0()n0,2n2,

等于

n0

A.0B.n2-1C.n2D.n2+1

设有个顶点的无向图若它为连通图则它具有的边数最少为

11.10,,

A.9B.10C.11D.12

设含有个顶点条弧的有向图采用邻接表存储则拓扑排序算法的时间复杂度为

12.n,eG,

2

A.O(n)B.O(n+e)C.O(n)D.O(n×e)

当查找表中有个数据元素时假设为查找第个元素的概率在等概

13.n,Pi(i=1,2,…,n)i,Pi

率的条件下顺序查找算法的平均查找长度为

,

A.n/2B.(n+1)/2C.nD.n+1

二维数组以行为主序存储每个元素占个存储单元若元素的存储地址是

14.A,1。A[1][1]

的存储地址是则的存储地址是

420,A[3][3]446,A[5][5]

A.470B.471C.472D.473

冒泡排序属于

15.

插入排序归并排序选择排序交换排序

A.B.C.D.

非选择题部分

注意事项:

用黑色字迹的签字笔或钢笔将答案写在答题纸上不能答在试题卷上

,。

二、填空题:本大题共13小题,每小题2分,共26分。

在数据库中数据项又称为字段或

16.▲。

在单链表存储结构中线性表的表长等于单链表中的结点个数

17.,▲。

二叉树的顺序存储结构可以用维数组来实现

18.▲。

在操作系统中为了保持多个进程和按某种次序依次执行需要一个

19.,P1、P2、P3P4,▲

来实现这个过程

。

浙数据结构导论试题第页共页

02142#2(4)

对称矩阵有近一半元素可以通过其对称元素获得因此可将含有2个元素的对称矩阵压

20.,n

缩存储到含有个元素的一维数组中

▲。

设有一个带头结点的链栈其头指针为现有一个新结点入栈指向该结点的指针为

21.,head,,

则入栈操作为和

p,▲headnext=p。

满二叉树一定是二叉树

22.▲。

在树形结构中结点间具有关系

23.,▲。

在图中序列中顶点不重复出现的路径称为路径

24.,▲。

算法用于求问题

25.Dijkstra▲。

求最小生成树有方法和方法

26.▲Kruskal。

若在查找过程中向表中插入不存在的数据元素或者从表中删除某个数据元素则称此类

27.,,,

表为查找表

▲。

在二分查找索引顺序查找和散列查找三种查找方法中平均查找长度与元素个数没有关

28.、,

系的查找方法是

▲。

三、应用题:本大题共5小题,每小题6分,共30分。

设有一个链栈的输入序列为当输出序列分别为和时请写出对应的进

29.A、B、C,ABCBCA,

栈和出栈过程

。

设有一森林如题图所示请分别写出先序遍历和中序遍历的序列

30.F30,。

题图

30

如题图所示长度为的散列表其散列函数为在表中已填入键

31.3113,H(key)=keymod13,

值分别为的元素

16,30,54。

现要插入键值为的元素应用线性探测法计算填入散列表中单元的序号

(1)29,,。

要求给出求解过程

()

线性探测法中如何减少堆积的机会

(2),?

0123456789101112

541630

题图

31

浙数据结构导论试题第页共页

02142#3(4)

如题图所示的图结构请写出以为源点的广度优先搜索得到的顶点访问序列并画

32.32,10,

出搜索过程图同等情况下值小的结点优先访问

。(,)

题图

32

给定有序表用二

33.D={006,087,155,188,220,465,505,508,511,586,656,670,700,766},

分查找法在中查找试给出查找过程

D511,。

四、算法设计题:本大题共2小题,每小题7分,共14分。

编制函数求

34.1+2+…+n。

已知循环队列的结构类型如下

35.:

typedefstructcycqueue

{

DataTypedatamaxsize

intfrontrear

}CcQue

y

CycQueCQ

设计入队列的算法

。

浙数据结构导论试题第页共页

02142#4(4)

绝密启用前

★

年月高等教育自学考试全国统一命题考试

202310

数据结构导论试题答案及评分参考

课程代码02142

()

一、单项选择题:本大题共15小题,每小题2分,共30分。

1.A2.D3.C4.A5.C6.C7.B8.B9.C10.D

11.A12.B13.B14.C15.D

二、填空题:本大题共13小题,每小题2分,共26分。

域数据元素一

16.17.18.

队列

19.20.n(n+1)/221.pnext=headnext

完全层次简单

22.23.24.

单源最短路径动态

25.26.Prim27.

散列查找

28.

三、应用题:本大题共5小题,每小题6分,共30分。

输出进出进出进出分

29.ABC:A,A,B,B,C,C;(3)

输出进进出进出出分

BCA:A,B,B,C,C,A。(3)

先序序列为分

30.ABCDEFGHJI;(3)

中序序列为分

BCDAFEJHIG。(3)

散列函数求出其散列地址为在地址上面已有元素发生冲突分应用线性

31.(1)3,316,。(1)

探测法得到下一个地址为仍冲突分则再求下一个地址这个位置

,d+1=4,,(1)d+2=5,

上没有元素将元素填入散列表中序号为的单元分

,5。(2)

应设法使后继散列地址尽量均匀地分散在整个散列表中分

(2)。(2)

序列分

32.:10,20,30,50,40,60(3)

分

(3)

答图

32

数据结构导论试题答案及评分参考第页共页

1(2)

33.0102030405060708091011121314

(1)006087155188220465505508511586656670700766

↑↑↑

lowmidhigh

分

(2)

(2)006087155188220465505508511586656670700766

↑↑↑

lowmidhigh

分

(2)

(3)006087155188220465505508511586656670700766

↑↑↑

lowmidhigh

分

(2)

四、算法设计题:本大题共2小题,每小题7分,共14分。

34.intfact1(intn)

{inti,j,temp,s;

分

s=0;(2)

<=