试卷代号：1252 座位号□□
国家开放大学2 0 1 9年秋季学期期末统一考试
数据结构（本）试题
2020年1月
一、单项选择题(每小题3分，共30分)
1．以下说法不正确的是( )。
A．线性表的链式存储结构不必占用连续的存储空间
B．一种逻辑结构只能有唯一的存储结构
C. 一种逻辑结构可以有不同的存储结构
D．线性表的顺序存储结构必须占用连续的存储空间
2．单向链表所具备的特点之一是( )。
A．可以随机访问表中任一结点
B．需要占用连续的存储空间
C．插入元素和删除元素的操作不需要移动元素
D．可以通过指向某元素的指针操作，直接访问到该结点的直接前驱结点
3．线性结构中数据元素的位置之间存在( )的关系。
A．多对多
B．一对多
C．一对一
D．每一个元素都有一个直接前驱和一个直接后继
4．在一个单向链表中，p和q分别是指向结点类型的指针，要删除p所指结点的直接后继
结点，可执行( )。
A.q=p->next;p->next= q- >next
B．q=p;p=q->next
C.q-p- >next;p->next=q
D．q-p；p->next=q
5．设有带头结点的且头指针为head的非空的单向链表，指针p指向其尾结点，要使该单向链表成为不蒂头结点的单向循环链表，则可利用下述语句：head=head->next;和( )。
A．p- head B. p=NULL
C. p->next=head n head=p
6．元素20，14·160，180按顺序依次进栈，则该栈的不可能输出序列是( )。（进栈出
栈可以交替进行）。
A. 180,160,14,20 B.20,14,160,180
C. 180,160,20,14 D. 14,20,180,160
7．设有一个15阶的对称矩阵A(第一个元素为a1，1)，采用压缩存储的方式，将其下三角部分以行序为主序存储到一维数组B中（数组下标从1开始），则矩阵中元素a5，3在一维数组
B中的下标是( )。
A．11 B．13
C．14 D．12
8．设一棵有n个叶结点的二叉树，度数为1的结点有4个，则该树共有( )个结点。
A．2n B．2n+3
C．2n+2 D．2n+4
9．设根结点所在层为第一层，一棵具有5层的完全二叉树，最后一层有6个结点，则该树
总共有( )个结点。
A．22 B．20
C.21 D.10
10．已知如图l所示的一个图，若从顶点a出发，按深度优先搜索法进行遍历，则可能得到的一种顶点序列为( )。
图1
A．abecdfg B．acfebdg
C．aebcfdg D．aedfcbg
二、填空题（每小题2分，共24分）
11．把数据存储到计算机中，并具体体现数据元素间的逻辑关系称为____结构。
12．设有一个长度为22的顺序表，要删除第8个元素需移动元素的个数为____。
13．在一棵二叉树中，若编号为i的结点存在右孩子，则右孩子的顺序编号为____。
14．设一棵哈夫曼树共有18个非叶结点，则该树总共有____个结点。
15．栈元素的进、出栈次序是：后进一 。
16．在对10个记录的序列(8，36，19，78，4，10，53，45，27，68)进行直接插入排序时，当把第6个记录10插入到有序表时，为寻找插入位置，元素间需比较____次。
17．n个元素进行冒泡法排序，通常需要进行n-l趟冒泡，其中第j趟冒泡共需要进行
次元素间的比较。
18．序列7，1，4，2，5，3，8，6用归并法排序（升序），经一次归并后的结果序列是 。
19．中序遍历一棵____ 树可得到一个有序序列。
20．广义表(h，(b，a)．f，e，（（i，j)，k））的深度是____。
21．____结构中，数据元素间存在一对多的关系。
22．字符串al= "beijing”，a2一“bef”，a3一“beifang”，a4一“befi”最小的是____。
三、综合题（每小题中每问6分，共30分）
23．设查找表为
序号
1
2
3
4
5
6
7
8
9
10
11
序列
11
16
24
25
43
61
71
83
91
92
123
(1)画出对上述查找表进行折半查找所对应的判定树（树中结点用下标表示）。
(2)说明不成功查找元素45需要经过多少次比较？
(3)求在等概率条件下，成功查找的平均比较次数？
24．(1) 一组记录的关键字序列为(37，67,43，25，27，32)，给出利用堆排序（堆顶元素是最
小元素）的方法建立的初始堆（要求以完全二叉树描述）。
(2)对关键字序列(40，73，49，31·33，77)采用快速排序，给出以第一个关键字为分割元素，
经过一次划分后的结果。
四、程序填空题（每空2分，共16分）
25.以下函数在a[0]到a[n-l]中，用折半查找算法查找关键字等于k的记录，查找成功
返回该记录的下标，失败时返回-l，完成程序中的空格。
typedef struct
{ int key,
……
｝NODE;
int Binary_Search(NODEa[] ,int n,int k)
{
int low, mid, high;
low=0：
(l)
while(_low<= high)
{
Mid= (2)
if (a[mid]. key==k)
return(3)
else if(a[mid]. key<k)
low=mid+l;
else(4) ｝
(5)
｝
26.以下程序是先序遍历二叉树的递归算法的程序，完成程序中空格部分（树结构中左、
右指针域分别为left和right，数据域data为字符型，BT指向根结点）。
void Preorder(struct BTreeNode* BT)
{
if(BT! =NULL)(
(l)
(2)
Preorder(BT->right);)
}
利用上述程序对下图进行遍历，结果是(3) ；
图2