试卷代号：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(“%dn”,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
2
3
4
5
6
7
8
序列
4
12
18
19
37
55
65
77
(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