百年教育职业培训中心 广东 国家开放大学1252操作系统复习参考题

报名本机构合作学校，赠送复习资料，复习课程，确保录取。并且可以申请学校奖学金500元～1500元不等！

答案：微信搜索【渝粤教育】公众号

试卷代号：1252

国家开放大学2021年春季学期期末统一考试

数据结构（本） 试题

2021年7月

一、单项选择题（把合适的选项编号填写在括号内。每小题3分，共45分）

1.下面程序段的时间复杂度是（ ）。

for（i=1；i＜=n；i++）

for（j=1；j＜=n；j++）{

c[i][j]=O；

for(k=l；k＜=n；k++)

c[i][j]=c[i][j]+a[i][k]*b[k][j]；

}

A.O(1)B.O(log2n)

C.O(n)D.O(n3)

2.数据的存储结构包括数据元素的表示和（ ）。

A.数据处理的方法B.相关算法

C.数据元素的类型D.数据元素间的关系的表示

3.在一个单链表中p所指结点之后插入一个s所指的结点时，可执行（ ）。

A.p->next=s；s->next=p->next

B.p->next=s->next

C.p=s->next

D.s->next=p->next；p->next=s

4.在一个单链表中，p、q分别指向表中两个相邻的结点，且q所指结点是p所指结点的直接后继，现要删除q所指结点，可用语句（ ）。

A.p=q->nextB.p->next=q

C.p->next=q->nextD.q->next=NULL

5.若让元素1，2，3依次进栈，则出栈顺序不可能为（ ）。

A.3，2，1B.2,1,3

C.3，1，2D.1，3,2

6.表达式a*(b+c)-d的后缀表达式是（ ）。

A.abcd*+-B.abc+*d-

C.abc*++d-D.-+*abcd

7.判断顺序栈s满（元素个数最多n个）的条件是（ ）。

A.s->top= =0B.s->top!=0

C.s->top= =n-lD.s->top!=n-l

8.串的长度是指（ ）。

A.串中所含不同字母的个数B.串中所含字符的个数

C.串中所含不同字符的个数D.串中所含非空格字符的个数

9.广义表的(a，(d，a，b)，h，(e，((i，j)，k)))深度是（ ）。

A.6B.10

C.8D.4

10.在一棵二叉树中，若编号为8的结点存在右孩子，则右孩子的顺序编号为（ ）。

A.18B.16

C.15D.17

11.在一棵二叉树上，第5层的结点数最多为（ ）。

A.8B.15

C.16D.32

12.-个具有n个顶点的无向完全图包含（ ）条边。

A.n(n-l)B.n(n+1)

C.n(n-l)/2D.n(n+l)/2

13.对于一个具有n个顶点和e条边的无向图，若采用邻接表表示，则所有顶点邻接表中

的结点总数为（ ）。

A.nB.e

C.2nD.2e

14.对于一个线性表，若要求既能进行较快地插入和删除，又要求存储结构能够反映数据元素之间的逻辑关系，则应该（ ）。

A.以顺序存储方式B.以链接存储方式

C.以索引存储方式D.以散列存储方式

15.从未排序序列中挑选元素，并将其放人已排序序列的一端，此方法称为（ ）。

A.插入排序B.交换排序

C.选择排序D.归并排序

二、判断题（根据叙述正确与否在其后面的括号内打对号“√”或打叉号“×”。每小题2分，共30分）

16.数据的逻辑结构与数据元素本身的内容和形式无关。（ ）

17.通常可以把一本含有不同章节的书的目录结构抽象成线性结构。（ ）

18.要在一个单向链表中删除p所指向的结点，已知q指向p所指结点的直接前驱结点，若链表中结点的指针域为next，则可执行q->next=p->next。（ ）

19.要在一个带头结点的单向循环链表中删除头结点，得到一个新的不带头结点的单向循环链表，若结点的指针域为next，头指针为head，尾指针为p，则可执行head=head->next；p->next=head；。（ ）

20.若让元素1，2，3依次进栈，则出栈次序1，3，2是不可能出现的情况。（ ）

21.递归定义的数据结构通常用递归算法来实现对它的操作。（ ）

22.队列的特性是先进后出。（ ）

23.用字符数组存储长度为n的字符串，数组长度至少为n+l。（ ）

24.-个广义表的表头总是一个广义表。（ ）

25.若树的度为2时，该树为二叉树。（ ）

26.深度为5的二叉树最多有31个结点。（ ）

27.存储图的邻接矩阵中，邻接矩阵的大小不但与图的顶点个数有关，而且与图的边数也有关。（ ）

28.图的深度优先搜索序列和广度优先搜索序列不是惟一的。（ ）

29.理想情况下，哈希表查找等概率查找成功的时间复杂度是O(1)。（ ）

30.n个元素进行冒泡法排序，通常第j趟冒泡要进行n-j次元素间的比较。（ ）

三、综合应用及程序设计题（每小题5分，共25分）

31.设线性表以不带头结点的单向链表存储，链表头指针为head。以下程序的功能是输出链表中各结点中的数据域data，完成程序中空格部分。

# define NULL 0

Void main（）

{ NODE * head，* p ；

p=head；／*p为工作指针*／

do

{ printf(“%d\n”,p->data)；

   ①   ；

}while( ② )；

}

①（3分）

A.head=p->next B.p=head->next

C.p=p->next D.head=head->next

②（2分）

A.p==NULL B.p!=NULL

C.p!=head D.p= =head

32.写出下列程序执行后的结果

SeqQueue Q；

InitQueue(Q)；

inta[4]={5,8,12,15)；

for(inti一0；i<4；i++)InQueue(Q,a[i])；

InQueue(Q,OutQueue(Q》；

InQueue(Q,30)；

InQueue(Q,OutQueue(Q)+10)；

while(!QueueEmpty(Q》printf("%d”,OutQueue(Q》；

执行后的输出结果为：____。

A.58121530 B.121553018

C.812153018 D.121551830

33.设查找表为：

(1)画出对上述查找表进行折半查找所对应的判定树是（ ）。（3分）

(2)用折半查找在该查找表成功查找到元素55需要经过（ ）次比较。（2分）

A.1B.2

C.3D.4

34.顺序查找算法如下，完成程序中空格部分。

Int search(NODEa[],int n,int k)

／* 在a[0]，a[1]…a[n-1]中查找关键字等于k的记录，查找成功返回记录的下标，失败

时返回-1*／

( int i=0；

while(i<n && a[i].key!=k)

   ①   

if（   ②   ）

returni；

else return -1,

}

①（2分）

A.k++；B.i++；

C.n++；D.a++：

②(3分)

A.a[i].key==nB.a[i].key==k

C.a[n].key==kD.a[n].key==i

35.设数据序列为：{53，30，37，12，45，24，96）

(1)从空二叉树开始逐个插入该数据序列来形成二叉排序树，若希望高度最小，应该选择的序列是（ ）。（3分）

A.45,24,53,12,37,96,30B.37,24,12,30,53,45,96

C.12,24,30,37,45,53,96D.30,24,12,37,45,96,53

(2)用链接地址法将该数据序列构造哈希表，哈希函数为H(key)=keymod13，则散列地址为1的链中有（ ）个记录。（2分）

A.0B.1

C.2D.3

报名联系方式

1、报名热线：13662661040（微信），0755-21017149，QQ：2864330758 郭老师

2、报名地址：深圳市龙华新区工业西路68号中顺商务大厦B704

2022年广 东理工学院成人高考招生简章

2022年广 州城建职业学院成人高等教育招生简章

2022年广 东科学技术职业学院招生简章

2022年广 东 工业大学 成人 高考 招生简章

2022年广 东生态工程职业学院成人高考招生专业

2022年清 远职业技术学院 成人高考 招生专业简介

2022年韶 关学院成人高考招生简章

2022年广 东财经大学成人 高考 高等教育招生简介

2022年广 东理工学院成人高考招生简章

2022年广 东第二师范学院成人高考招生简章

2022年广 东南方职业学院成人高考招生简章