1、试卷代号:1252 座位号I国家开放大学2020年春季学期期末统一考试数据结构(本)试题2020年7月巨I-四三得分1评卷人一、单项选择题(每小题3分,共30分)1.设主串为DBcCDABcdEFdBc,以下模式串能与主串成功匹配的是()。A.dBc C.DEC 2.顺序表所具备的特点之一是()。A.可以随机访问任一结点C.插入删除操作不需要移动元素B.BCd D.Abe B.不用占用连续的存储空间D.必须要有头指针3.在一个链队中,假设f和r分别为队头和队尾指针,p指向一个巳生成的结点,现要为该结点的数据域赋值e,并使结点入队的运算为p-data=e;pnext=NULL;和()。A.fne
2、xt=p;f=p C.p-next=r;r=p B.r-next=p;r=p D.p-next=f;f=p 4.在一个头指针为head的带头结点的单向循环链表中,p指向尾结点,要使该链表成为不带头结点的单向链表,可执行()。A.head=headnext;p=NULL B.head=head-next;P-next=head C.headnext=pnext D.head=head-next;p-next=NULL 545 5.元素212,214,216,218按顺序依次进栈,则该栈的不可能输出序列是()(进栈出栈可以交替进行)。A.212,214,216,218 C.214,212,218,
3、216 B.216,214,212,218 D.218,216,212,214 6.设有一个25阶的对称矩阵AC第一个元素为a口,采用压缩存储的方式,将其下三角部分以行序为主序存储到一维数组B中(数组下标从1开始),则矩阵中元素a4,3在一维数组B中的下标是()。A.10 B.9 C.7 D.8 7.在一棵二叉树中,编号为19的结点的双亲结点的顺序编号为()。A.9 B.8 C.34 D.35 8.线性表以()方式存储,能进行折半查找。A.关键字有序的C.链接B.顺序D.关键字有序的顺序9.如图1所示的一个图,若从顶点a出发,按深度优先搜索法进行遍历,则可能得到的一种顶点序列为()。546 A
4、.abecdfg C.aebcfdg 图1B.aecbdfg D.aedfcbg 10.设一棵哈夫曼树共有31个结点,则该树共有()个非叶子结点。46 11.AC B.15 D.17 得分1评卷人二、填空题(每小题2分,共24分)11.结构中,数据元素的位置之间存在多对多的关系。12.设有一个长度为20的顺序表,要插入一个元素,并作为第6个元素,需移动元素的个数为13.数组a经初始化chara=fhglisp;a6中存放的是14.序列4,2,15,13,18,16,采用冒泡排序算法,经一趟冒泡后,序列的结果是15.对19个元素的序列用冒泡排法进行排序,通常第7趟冒泡中,共需要进行次元素间的比较
5、。16.对一组记录(41,25,93,20,12,78,46,51,89)进行直接插入排序(由小到大排序),当把第7个记录46插入有序表,为寻找插入位置需比较次。17.设有一棵深度为5的完全二叉树,第5层上有4个结点,该树共有个结点。(根所在结点为第1层)18.设有串pl=DEADFG,P2=DEAFDF,P3=DEADF ABP4=DEAFE,四个串中最大的是19.一棵有8个叶结点的哈夫曼树,则该树共有个结点。20.遍历二叉排序树可得到一个有序序列。21.广义表(g,Ca,b,d,c),d,e,C(i,j),k)的长度是。22.在一个单向链表中,已知q指向p所指结点的直接前驱结点,现要删除p
6、所指结点,则可以用操作qnext=547 得分1评卷人三、综合题(每小题中每问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)按折半查找对该表进行查找,求在等概率情况下查找成功的平均比较次数。:I 218 I:51630 174517591860 I:61980 I:51:(3)以1
7、,2,3,6,7,8作为叶结点的权,构造一棵哈夫曼树。得分1评卷人四、程序填空题(每空2分,共16分)25.设线性表以不带头结点的单向链表存储,链表头指针为head,以下程序的功能是:(1)输出链表中各结点中的数据域data。(2)把该单向链表改为以p作为尾指针的单向循环链表。(链表中结点的指针域为next,数据域为data)。#define NULL O void main()NODE*head,*p;p=head;/*p为工作指针do printf(%d n,(1);(2);while(p-next!=(3);print(%dn pdata);548(4)26.以下程序是后序遍历二叉树的递
8、归算法的程序,完成程序中空格部分(树结构中左、右指针域分别为left和right,数据域data为字符型,BT指向根结点)。完成程序中空格部分。void postorder(struct BTreeNode*BT)if(1)postorder(BT-left);(2)(3)利用上述程序对下图所示二叉树遍历的结果为(4)图2549 试卷代号:1252 国家开放大学2020年春季学期期末统一考试数据结构(本)试题答案及评分标准(供参考)一、单项选择题(每小题3分,共30分)1.A 2.A 6.B 7.A 二、填空题(每小题2分,共24分)11.图状12.15 13.字符p14.2,4,13,15,
9、16,18 15.12 16.3 17.19 18.P4 19.15 20.中序21.5 22.P-next 550 3.B 8.D 2020年7月4.D 5.D 9.D 10.B 三、综合题(每小题中每问6分,共30分)23.(1)(2)4,5,7,9,6,8 b0 551 24.(1)(2)0+2*2+3*4+4*3)/10=29/10(3)2/:552 四、程序填空题(每空2分,共16分)25.(1)pdata(2)p=p-next(3)NULL(4)pnex=head 26.(1)BT!=NULL(2)postorder(BT-right)(3)printf(%c,BT-data)(4)9,6,5,8,7,4 553