试卷代号：1252
国家开放大学2020年秋季学期期末统一考试
数据结构（本）试题
2021年1月
一、单项选择题（把合适的选项编号填写在括号内。每小题3分，共 45分）
1.在数据结构中，从逻辑上可以把数据结构分为( )。
A.动态结构和静态结构 B.紧凑结构和非紧凑结构
C.内部结构和外部结构 D.线性结构和非线性结构
2.下面程序段的时间复杂度是( )。
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.O(log2n)
C.O(n)D.0(n3)
3.在一个单链表中p指向结点a，q指向结点a的直接后继结点b，要删除结点b，可执行( )。
A.p->next=q->next B.p=q->next
C.p->next=q D.p->next=q
4.设有一个长度为n的顺序表，要在第i个元素之前（也就是插入元素作为新表的第i个元素），插入一个元素，则移动元素个数为( )。
A.n-i B.n-i-l
C.n-i+l D.i
5.一个队列的人队序列是1，2，3，4。则队列的输出序列是( )。
A.4,3，2，1 B.1,2,3,4
C.1，4，3，2 D.3,2.4,1
6.在一个栈顶指针为top的链栈中，将一个p指针所指的结点人栈，应执行( )。
A.top->next=p
B.p->next=top->next;top->next=p
C.p->next=top； top=p
D.p-> next= top->next, top= top->next
7.判断一个循环队列Q(最多元素为m)为满的条件是( )。
A.Q->front= =Q->rear
B.Q->front！ =Q->rear
C.Q->front==(Q->rear+l)%m
D.Q->front! =(Q->rear+l)%m
8.设有两个串p和q，其中q是p的子串，求q在p中首次出现的位置的算法称为( )。
A.求子串 B.连接
C.模式匹配 D.求串长
9.一个非空广义表的表头( )。
A.不可能是原子 B.只能是子表
C.只能是原子 D.可以是子表或原子
10.树中的结点数等于所有结点的度数加( )。
A.1 B.0
C.2 D.-1
11.在一棵二叉树上，第5层的结点数最多为( )。
A.8 B.15
C.16 D.32
12.在一个图G中，所有顶点的度数之和等于所有边数之和的( )倍。
A.1/2 B.1
C.2 D.4
13.对于一个具有n个顶点和e条边的无向图，若采用邻接表表示，则所有顶点邻接表中的结点总数为( )。
A.n B.e
C.2n D.2e
14.有一个长度为12的有序表，按折半查找对该表进行查找，在等概率情况下查找成功的平均比较次数为( )。
A.37/12 B.39/12
C.41/12 D.35/12
15.从未排序序列中依次取出元素与已经排好序的序列中的元素作比较。将其放人已排序序列的正确的位置上，此方法称为( )。
A.插入排序 B.交换排序
C.选择排序 D.归并排序
二、判断题（根据叙述正确与否在奠后面的括号内打对号“√”或打叉号“×”。每小题2分，共30分）
16.数据的逻辑结构是指各数据元素之间的逻辑关系，是用户根据应用需要建立的。( )
17.数据结构中，元素之间存在多对多的关系称为图状结构。( )
18.设有一个单向链表，结点的指针域为next，头指针为head，p指向尾结点，为了使该单向链表改为单向循环链表，可用语句p->next=head。( )
19.设有一个单向循环链表，结点的指针域为next，头指针为head，指针p指向表中某结点，若逻辑表达式p->next= =head;的结果为真，则p所指结点为尾结点。( )
20.栈和队列都是特殊的线性表，但它们对存取位置的限制不同。( )
21.栈是限定在表的两端进行插入和删除操作的线性表，又称为先进先出表。( )
22.递归定义的数据结构通常用递归算法来实现对它的操作。( )
23.一个空格的串的长度是0。( )
24.对稀疏矩阵进行压缩存储，矩阵中每个非零元素对应的三元组包括该元素的行号、列号和元素值三项信息。( )
25.深度为k的完全二叉树至少有2k-l个结点。( )
26.完全二叉树中没有度为1的结点。( )
27.图的生成树是惟一的。( )
28.对连通图进行深度优先遍历可以访问到该图中的所有顶点。( )
29.在顺序查找、折半查找、哈希表查找3种方法中，平均查找长度与结点个数n无关的查找方法是折半查找。( )
30.n个元素进行冒泡法排序，通常需要进行n-l趟冒泡。( )
三、综合应用及程序设计题（每小题5分，共25分）
31.在下面空格处填写一条语句，以使下面的链式队列全部元素出队的算法完整。
int write(LinkQueue*q)
(QueueNode*p；
if(q->front= =q->rear) *队空*／
{ printf（“队空！无元素可取”）；
exit(0)；
}
while (q->fronr->next!=NULL)
（p=q->front->next；
q->front->next= p- >next; ／*出队*／
printf(“%4d”,p->data);
free(p)； ／*释放已出队结点x／
}
／*队空时，头尾指针指向头结点*／
}
A.q->front=q->rear B.q=q->next
C.q->rear=q->front D.p=p->next
32.以下程序是先序遍历二叉树的递归算法的程序，完成程序中空格部分（树结构中左、
右指针域分别为left和right，数据域data为字符型，BT指向根结点）。
void Preorder (struct BTreeNode* BT)
(if (BT! =NULL)
{____；
Preorder(BT- >left)；
Preorder(BT- >right)；
}
}
A.printf(“%c”,BT->left) B.printf(“%c”.BT->right)
C printf(“%c”,BT->data) D.printf(“%d”,BT->data)
33.一组记录的关键字序列为(6，9，7，4，5，8)，利用堆排序（堆顶元素是最小元素）的方法建立初始堆是如下哪个图？( )
34.设关键字序列为：(36，69，46，28，30，74)
(1)将此序列用快速排序的方法，以第一个记录为基准得到的一趟划分的结果为( )。
（本小题3分）
A.30,28.46,36,69,74 B.28,30,36,46,69,74
C.28,30,46,36,69,74 D.30,28.36,46,69,74
(2)用冒泡法对上述序列排序，经过两趟冒泡的结果序列为( )。（本小题2分）
A.36,28,30,46,69,74 B.36,46,28,20,69,74
C.38,36,30,46,69,74 D.28,36,30,46,69,74
35.设数据序列为：{53，30，37，12，45，24，96)
(l)从空二叉树开始逐个插入该数据序列来形成二叉排序树，若希望高度最小，应该选择
的序列是( )。（本小题3分）
A.45,24,53,12,37,96,30 B.37,24,12,30,53,40,96
C.12,24,30,37.45,53,96 D.30, 24 ,12,37,45,96,53
(2)用链接地址法将该数据序列构造哈希表，哈希函数为H(key) =key mod 13，则散列地址为1的链中有( )个记录。（本小题2分）
A.0 B.1
C.2 D.3