试卷代号：1252
国家开放大学2022年春季学期期末统一考试
数据结构（本）试题
2022年7月
一、单项选择题（把合适的选项编号填写在括号内。每小题3分，共45分）
1.线性结构、树形结构、图形结构都是按数据的( )来分类的。
A.存储结构B.物理和存储结构
C.物理结构D.逻辑结构
2.在数据结构中，从逻辑上可以把数据结构分为( )。
A.动态结构和静态结构B.紧凑结构和非紧凑结构
C.内部结构和外部结构D.线性结构和非线性结构
3.设有一个长度为n的顺序表，要删除第i个元素，则需移动元素的个数为( )。
A.iB.n-i-l
C.n-iD.n-i+l
4.设有一个长度为10的顺序表，要在第3个元素之后插入一个元素，则需移动元素的个数为( )。
A.3B.6
C.7D.8
5.-个队列的入队序列是10，20，30，40。则队列的输出序列是( )。
A.40,30,20,10B.10,20,30940
C.10,40,30,20D.30,20,40,10
6.在一棵二叉树中（其根结点编号为1），若编号为8的结点存在右孩子，则该右孩子的顺序编号为( )。
A.18B.16
C.15D.17
7.队列的出队操作在( )进行。
A.队头B.队尾
C.任意位置D.指定位置
8.串函数index(a,b)的功能是进行( )。
A.求子串B.串连接
C.模式匹配D.求串长
9.一个非空广义表的表头元素( )。
A.不可能是原子B.只能是子表
C.只能是原子D.可以是子表或原子
10.链表所具备的特点之一是( )。
A.可以随机访问任一结点B.需要占用连续的存储空间
C.插入元素的操作不需要移动元素D.删除元素的操作需要移动元素
11.树中所有结点数等于所有结点的度加( )。
A.1B.O
C.2D.-1
12.在一个无向图G中，所有边数之和等于的所有顶点的度数之和( )倍。
A.1/2B.1
C.2D.4
13.对于一个具有4个顶点和5条边的无向图，若采用邻接表表示，则所有顶点邻接表中的结点总数为( )。
A.4B.5
C.8D.10
14.有一个长度为5的线性表，按顺序查找某关键字，在等概率情况下查找成功的平均比较次数为( )。
A.2B.2.5
C.3D.3.5
15.假定一组记录的排序码为(46，79，56，38，40，80)，对其进行归并排序的过程中，第二趟归并后的结果为( )。
A.46,79,56,38,40,80B.46979,38,56,40,80
C.38,46,56,79,40,80D.38,40,46,56,79,80
二、判断题（根据叙述正确与否在其后面的括号内打对号“√”或打叉号“×”。每小题2分，共30分）
16.数据的逻辑结构与数据元素本身的内容和形式无关。( )
17.数据结构中，元素之间存在一对多的关系称为图状结构。( )
18.设有一个单向链表，结点的指针域为next，头指针为head，p指向尾结点，为了使该单向链表改为单向循环链表，可用语句p->next=head。( )
19.线性表用关键字的顺序方式存储，可以用二分法查找。( )
20.往栈中插入元素的操作方式是：先写入元素，后移动栈顶指针。( )
21.栈是限定在表的一端进行插入和删除操作的线性表，又称为先进后出表。( )
22.递归定义的数据结构通常用递归算法来实现对它的操作。( )
23.串是一种特殊的线性表，其特殊性表现在组成串的数据元素都是字符。( )
24.对稀疏矩阵进行压缩存储，矩阵中每个非零元素对应的三元组包括该元素的行号、列号和元素值三项信息。( )
25.二叉树只能采用二叉链表来存储。( )
26.完全二叉树中没有度为1的结点。( )
27.图的生成树是惟一的。( )
28.对连通图进行深度优先遍历可以访问到该图中的所有顶点。( )
29.在有序顺序存储的线性表中查找一个元素，用折半查找速度一定比顺序查找快。( )
30.对n个元素进行冒泡法排序，最多需要进行n-l趟冒泡。( )
三、综合应用及程序设计题（每小题5分，共25分）
31.在下面空格处填写一条语句，以使下面的链式队列全部元素出队的算法完整。
Int write(LinkQueue*q)
{QueueNode * p；
if(q->front==q->rear) ／*队空*／
{printf(“队空！无元素可取”)；
exit(0)；
｝
while(q->front->next ! =NULL)
{p=q->front->next；
q->front->next=p->next; ／*出队*／
printf(“%4d”,p->data);
free(p)； ／*释放已出队结点*／
｝
_____________ /*队空时，头尾指针指向头结点*／
｝
程序中空格部分的选项为：
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)
330-组记录的关键字序列为(6，9，7，4，5，8)，利用堆排序（堆顶元素是最小元素）的方法建立初始堆是如下哪个图？( )
34.以下利用直接插入排序算法对存放在a[0]，a[l]，...，a[n-l]中，长度为n的记录序列按关键字key由小到大排序，完成程序中空格部分。
Void disort(NODE a[],int n)
{ int i，j；
NODE temp；
for(i=l；i<n；i++)
{temp=a[i]；
j=i-l；
while(j>=0＆＆temp.key<a[j].key)
{a[j+1]一a[j]；
_________________________；
｝
a[j+l]=temp;
｝
｝
程序中空格部分的选项为：
A.j++B.i++
C.j--D.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)=key mod13，则散列地址为1的链中有( )个记录。（本小题2分）
A.0B.1
C.2D.3