国家开放大学2021至2022年(202101-202207)《1252数据结构(本)》期末考试真题.docxVIP

试卷代号：1252

国家开放大学2020年秋季学期期末统一考试

数据结构（本）试题

2021年1月

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

在数据结构中，从逻辑上可以把数据结构分为（）o

B.紧凑结构和非紧凑结构D.

B.紧凑结构和非紧凑结构

D.线性结构和非线性结构

C.内部结构和外部结构

）。下面程序段的时间复杂度是（for（i=l;i=n；i++）

）。

for（j=l；j=n；j++）（c[i][j]=0；for（k=l；k=n；k++）

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

A.0（1） B.0（log2n）

C.O（n） D.0（n3）

在一个单链表中p指向结点a,q指向结点a的直接后继结点b,要删除结点b,可执行（）o

A.p-next=q-next B.p=q-next

C.p-next=q D.p-next=q

设有一个长度为n的顺序表，要在第i个元素之前（也就是插入元素作为新表的第i个元素），插入一个元素，则移动元素个数为（）。

A.n-i B.n-i-1

C.n-i+1 D.i

一个队列的人队序列是1,2,3,4。则队列的输出序列是（）o

A.4,3,2,1 B.1,2,3,4

C.1,4, 3,2 D.3,2.4,1

在一个栈顶指针为top的链栈中，将一个p指针所指的结点人栈，应执行（）o

top-next=p

p-next=top-next;top-next=p

p-next=top；top二p

p-next=top-next,top=top-next

判断一个循环队列Q(最多元素为m)为满的条件是(

Q-front==Q-rear

Q-front!=Q-rear

Q-front—(Q-rear+l)%m

Q-front!=(Q-rear+l)%m

求q在p中首次岀现的位置的算法称为（设有两个串p和q,其中q是p

求q在p中首次岀现的位置的算法称为（

B.连接D.求串长

B.连接

D.求串长

C.模式匹配

一个非空广义表的表头()o

A.不可能是原子 B.只能是子表

C.只能是原子 D.可以是子表或原子

树中的结点数等于所有结点的度数加（）。

TOC\o1-5\h\zA.1 B.0

C.2 D.-1

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

A.8 R.15

C.16 D.32

在一个图G中，所有顶点的度数之和等于所有边数之和的（）倍。

A.1/2 B.1

C.2 D.4

对于一个具有n个顶点和e条边的无向图，若采用邻接表表示，则所有顶点邻接表中的结点总数为（）o

A.n B.e

C.2n D.2e

有一个长度为12的有序表，按折半査找对该表进行査找，在等概率情况下査找成功的平均比较次数为（）。

A.37/12 B.39/12

C.41/12 D.35/12

从未排序序列中依次取出元素与己经排好序的序列中的元素作比较。将其放人已排序序列的正确的位置上，此方法称为（）o

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

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

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

数据的逻辑结构是指各数据元素之间的逻辑关系，是用户根据应用需要建立的。（）

数据结构中，元素之间存在多对多的关系称为图状结构。（）

设有一个单向链表，结点的指针域为next,头指针为head,p指向尾结点，为了使该单向链表改为単向循环链表，可用语句p-next=heado（）

设有一个单向循环链表，结点的指针域为next,头指针为head,指针p指向表中某结点，若逻辑表达式p-next=

二head;的结果为真，贝ijp所指结点为尾结点。（）

栈和队列都是特殊的线性表，但它们对存取位置的限制不同。（）

栈是限定在表的两端进行插入和删除操作的线性表，又称为先进先岀表。（）

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

-个空格的串的长度是0。（）

对稀疏矩阵进行压缩存储，矩阵中每个非零元素对应的三元组包括该元素的行号、列号和元素值三项信息。（）

深度为k的完全二叉树至少有个结点。（）

完全二叉树中没有度为1的结点。（）

图的生成树是惟一的。（）

对连通图进行深度优先遍历可以访问到该图屮的所有顶点。（）

在顺序查找、折半查找、哈希表查找3种方法中，平均查找长度与结点个数n无关的査找方法是折半査找。（）

n个元素进行冒泡法排序，通常需要进行n-1趟冒泡。（）

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

在下面空格处填写一条语句，以使下面的链式队列全部元素出队