试卷代号：1 252
国家开放大学2 0 2 0年春季学期期末统一考试
数据结构（本） 试题
2020年7月
一.单项选择题（每小题3分，共30分）
1.设主串为“DBcCDABcdEFdBc”，以下模式串能与主串成功匹配的是（ ）。
A.dBcB.BCd
C.DBCD.Abc
2.顺序表所具备的特点之一是（ ）。
A.可以随机访问任一结点B.不用占用连续的存储空间
C.插入删除操作不需要移动元素D.必须要有头指针
3.在一个链队中，假设f和r分别为队头和队尾指针，p指向一个已生成的结点，现要为该结点的数据域赋值e，并使结点入队的运算为p->data=e;p->next一NULL;和（ ）。
A. f->next=p; f=pB.r->next=p;r=p
C. p->next=r;r=pD.p->next=f; f=p
4.在一个头指针为head的带头结点的单向循环链表中，p指向尾结点，要使该链表成为
不带头结点的单向链表，可执行（ ）。
A. head= head->next;p=NULL
B.head—head- >next; P- >next= head
C.head- >next= p- >next
D. head- head->next;p->next=NULL
5。元素212，214，216，218按顺序依次进栈，则该栈的不可能输出序列是（ ）（进栈出栈可以交替进行）。
A.212, 214, 216, 218B.216, 214, 212,218
C.214 ,212, 218, 216D.218, 216, 212, 214
6.设有一个25阶的对称矩阵A(第一个元素为ai，，，采用压缩存储的方式，将其下三角部分以行序为主序存储到一维数组B中(数组下标从1开始)，则矩阵中元素a4，s在一维数组B中的下标是（ ）。
A.10B.9
C.7D.8
7.在一棵二叉树中，编号为19的结点的双亲结点的顺序编号为（ ）。
A.9B.8
C.34D.35
8.线性表以（ ）方式存储，能进行折半查找。
A.关键字有序的B.顺序
C.链接D.关键字有序的顺序
9.如图1所示的一个图，若从顶点a出发，按深度优先搜索法进行遍历，则可能得到的一
种顶点序列为（ ）。
A. abecdfg B. aecbdfg
C. aebcfdg D. aedfcbg
10.设一棵哈夫曼树共有31个结点，则该树共有（ ）个非叶子结点。
A.14B.15
C.16D.17
二、填空题（每小题2分，共24分）
II.____结构中，数据元素的位置之间存在多对多的关系。
12.设有一个长度为20的顺序表，要插入一个元素，并作为第6个元素，需移动元素的个数为__ __。
13.数组a经初始化char a[]一“fhglisp”；a[6]中存放的是________。
14.序列4，2，15，13，18，16，采用冒泡排序算法，经一趟冒泡后，序列的结果是
。
15.对19个元素的序列用冒泡排法进行排序，通常第7趟冒泡中，共需要进行 次元素间的比较。
16.对一组记录(41，25，93，20，12，78，46，51，89)进行直接插入排序（由小到大排序），当把第7个记录46插入有序表，为寻找插入位置需比较____次。
17.设有一棵深度为5的完全二叉树，第5层上有4个结点，该树共有一个结点。
（根所在结点为第1层）
18.设有串pl=”DEADFG”，P2=”DEAFDF”，P3=”DEADFAB”P4=”DEAFE”，四个串中最大的是___ _。
19. 一棵有8个叶结点的哈夫曼树，则该树共有_ _个结点。
20.__ __遍历二叉排序树可得到一个有序序列。
21.广义表(g，(a，b，d，c)，d，e，((i，j)，k》的长度是__ __。
22.在一个单向链表中，已知q指向p所指结点的直接前驱结点，现要删除p所指结点，则可以用操作q-> next=___ _____。
三、综合题（每小题中每问6分，共30分）
23.(1)设有数据集合{50，39，17，83，111，14，65，13，91，102，49}，依次取集合中各数据构造一棵二叉排序树。
(2) -组记录的关键字序列为(6，9，7，4，5，8)，利用堆排序（堆顶元素是最小元素）的方法建立初始堆。（要求用完全二叉树表示）
24.(1)如下为一个长度为10的有序表，给出按折半查找对该表进行查找的判定树。
(2)按折半查找对该表进行查找，求在等概率情况下查找成功的平均比较次数。
(3)以1，2，3，6，7，8作为叶结点的权，构造一棵哈夫曼树。
序号
1
2
3
4
5
6
7
8
9
10
序列
28
35
60
75
79
80
86
90
95
99
四、程序填空题（每空2分，共16分）
25.设线性表以不带头结点的单向链表存储，链表头指针为head，以下程序的功能是：(1)输出链表中各结点中的数据域data。(2)把该单向链表改为以p作为尾指针的单向循环链表。(链表中结点的指针域为next，数据域为data)。
# define NULL 0
void main（ ）
{ NODE*head，*p；
p= head； /*p为工作指针*／
do
{printf(“%d n”，(1) )；
(2) ；
｝while(p ->next!=(（3） );printf(“%dn”p->data);
（（4） ）
｝
26.以下程序是后序遍历二叉树的递归算法的程序，完成程序中空格部分（树结构中左、右指针域分别为left和right，数据域data为字符型，BT指向根结点）。完成程序中空格部分。
void postorder (struct BTreeNode*BT)
{
if((1) )｛
postorder(BT->left)；
(2)
(3)
｝
利用上述程序对下图所示二叉树遍历的结果为(4)