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
