国家开放大学电大本科《数据结构》期末试题及答案（试卷号：1252）

国家开放大学电大本科《数据结构》期末试题及答案（试卷号：1252）一、单项选择题（每小题3分，共30分）1.设主串为“DBcCDABcdEFdBc",以下模式串能与主串成功匹配的是（ ）A.d&B.BCdC.DBCD.AbeA.d&B.BCdC.DBCD.Abe顺序表所具备的特点之一是（A.可以随机访冋任一结点B.不用占用连续的存储空间C.插入珈除操作不需要移动元素A.可以随机访冋任一结点B.不用占用连续的存储空间C.插入珈除操作不需要移动元素D.必须要有头指针在一个链队中，假设f和r分别为队头和队尾指针,p指向一个已生成的结点，现要为该结点的数据域赋值e,并使結点入队的运算为p—>data-e；p—>next=NULL；和（A.f—>next=p;f=pr—>next=p»r=pA.f—>next=p;f=pr—>next=p»r=pA.B.C.head—>nexEp—>nextA.B.C.head—>nexEp—>nextp—>next=r；r=p在一个头指针为head的带头结点的单向循环链表中，p指向尾結点，要使该链表成为不带头結点的单向链表，可执行（head=head—>nextp=NULLhead=head—>next；P—>nejffheadD.head=head—>next；p—>ne«=NULLD.元素212,214,216.218技顺序依次进栈•则该栈的不可能输岀序列是（ ）（进栈岀栈可以交替进行）.A.212,214.216,218B.216,214,212,218A.212,214.216,218B.216,214,212,218C.214,212,218,216218,216,212,214C.214,212,218,216218,216,212,2146.设有一个25阶的对林矩阵A（第一个元素为ain，釆用压缩存储的方式，将其下三角部分以行序为主序存储到一维数组B中（数組下标从1开始），则矩阵中元素在一维数组6.设有一个25阶的对林矩阵A（第一个元素为ain，釆用压缩存储的方式，将其下三角部分以行序为主序存储到一维数组B中（数組下标从1开始），则矩阵中元素在一维数组B中的下标是（A.10B.9C-7D.87.在一棵二叉树中，编号为19的结点的双亲结点的顺序编号为（A.9B.C34D.358.线性表以（ ）方式存储，能进行折半査找.A.关键字有序的B-C.链接D.A.关键字有序的B-C.链接D.顺序关键字有序的顺序9.如图1所示的一个图，若从顶点a出发,按深度优先搜索法进行遍历.则可能得到的一种顶点序列为（ ）.A.abecdfgA.abecdfgC.aebcfdgB.aecbdfgaedfcbg10.设一採哈夫是树共有31个结点，则该树共有（）个非叶子结点。A.14B.15C.16D.17 得分丨评卷人 二、填空题（每小題2分,共24分）11.结构中，数据元素的位置之间存在多对多的关系.设有一个长度为20的颛序表，要插入一个元素，并作为第6个元素，需移动元素的个TOC\o"1-5"\h\z数为 数组a经初始化chara[]="fhglisp”；a[6]中存放的是序列4,2.15.13,18,16,釆用冒泡排序算法，经一趟冒泡后，序列的结果是对19个元素的序列用冒泡排法进行排序，通常第7趟冒泡中，共需要进行 次元素间的比较.对一组记录（41,25,93,20,12,78,46,51,89）进行直接插入排序（由小到大排序），当把第7个记录46插入冇序衣,为寻找插入位置需比较 设有-棵深度为5的完全二叉树，第5层上有4个结点，该树共有 个結点。（根所在结点为第［层）设有申pl=”DEADFG”，P2=”DEAFDF”，P3=”DEADFAB”P4=”DEAFE”，四个串中龄大的是 . 一棵有8个叶结点的哈夫曼树，则该树共有 个结点。 遍历二叉排序树可得到一个有序序列.广义表（g.（a,b,d.c）.d.e.（（i,j）,k））的长度 •在一个单向链表中，已知q指向P所指结点的直接前驱结点，现要剝除P所指结点，则可以用操作q->nexF= ・三、综合题（每小题中每间6分，共30分）（1）设有数据集合（0,39,17,83111,14,65,13,91,102,49）,依次取集合中各数据构造一棵二叉排序树。（2）一组记录的关键字序列为（6,9,7,4,5,8）,利用堆排序（堆顶元素是最小元素）的方法建立初始堆。（要求用完全二叉树表示）（1）如下为一个长度为10的有序表，给出按折半査找对该表进行査找的判定树。（2）按折半査找对该表进行査找，求在等概率情况下査找成功的平均比较次数。四、程序填空題（每空2分，共16分）设线性表以不带头结点的单向链表存储，链表头指针为heal,以下程序的功能是：（1）输岀链表中各结点中的数据城data.（2）把该单向链表改为以p作为尾指针的单向循环链表。（链表中结点的指针域为next,数据域为data）.adefineNULL0voidmain()(NODE*head,*p；p=head；/-p为工作指针*/do)while(p->next!=(3) )；printf(M%d\n'b—〉data)；

«4)以下程序是后序遍历二叉树的递归算法的程序，完成程序中空格部分（树结构中左、右指针域分别为left和right,数据域data为字符型，BT指向根结点）.完成程序中空格部分.voidpostordcr(struciBTrecNodc*BT)postorderCBT—>left)；(2)(3)利用上述程序对下图所示二叉树遍历的结果为（4）图2试题答案及评分标准（仅供参考）一、单项选择题（每小题3分，共30分）].A2.A3.B4.D5.D6.B7.A8.D9.D10.B].A2.A3.B4.D5.D6.B7.A8.D9.D10.B二、填空题（毎小題2分，共24分）11.图状12.1513.字符11.图状12.1513.字符P14.2,4,13,15,16,188812TOC\o"1-5"\h\z319P415中序5P—>next三、综合題(毎小題中毎问6分，共30分)(1)24.24.(1)(1+2*2+