国家开放大学本科末考试数据结构历年试题与参考答案19C

1、国家开放大学2021年春季学期期末统一测试数据结构本试题2021年7月一、单项选择题每题3分,共30分1 .以下说法正确的选项是.A.在顺序表中可以随机访问任一结点B.一种逻辑结构在存储时只能采用一种存储结构C.对链表进行插入、删除元素的操作一定要移动结点D.在链表中可以随机访问任一结点参考答案：在顺序表中可以随机访问任一结点2 .线性表在存储后,如果要求：仅通过的指向第i个结点的指针,进行相关操作,访问到该结点的前驱结点,那么采用存储方式是不可行的.A.单链表B.双链表C.单循环链表D.顺序表参考答案：单链表3 .栈和队列的共同特点是.A.都是先进后出B.元素都可以随机进出C.只容许在端点处

2、插人和删除元素D.都是先进先出参考答案：只容许在端点处插人和删除元素4 .元素4,6,8,10按顺序依次进栈,按该栈的可能输出序列依次人队列,该队列的可能输出序列是进栈出栈可以交替进行.A.10,8,4,6B.10,6,4,8C.8,4,6,10D,10,8,6,45 .在一个不带头结点的链队中,假设f和r分别为队头和队尾指针,从该队列中进行出队操作,并把结点的值保存在变量X中的操作为.A.x=r->data；i*=r->next：B.r-r->next；x=r->data；C.x=f->data；f=f->next；D.f-f->next；x-f-&

3、gt;data；参考答案：x=f->data；f=f->next；6 .设有一个18阶的对称矩阵A,采用压缩存储的方式,将其下三角局部以行序为主序存到一维数组B中数组下标从1开始,那么矩阵元素ag.2对应于数组B中第号元素.矩阵中的第1个元素是al.1A.42B.39C.38D.40参考答案：387 .一棵采用链式存储的二义树中,共有n1个指针域被有效使用即指针域为非空.该二义树中有个指针域为空.A.n+1B.nC.n-1D.n-2参考答案：n+18 .设一棵哈夫曼树共有n个非叶结点,那么该树共有个结点.A.2nB.2n+1C.2n一1D.2n+2参考答案：2n+l9 .如下图,假

4、设从顶点a出发,按图的广度优先搜索法进行遍历,那么可能得到的一种顶点序列为oB.ahcfebdD.ahebcfdA.ahbedfcC.ahebcdf参考答案：ahebcdf10 .线性表以方式存储,能进行折半查找.A.关键字有序的链接B.顺序C.关键字有序的顺序D.数组参考答案：关键字有序的顺序二、填空题每题2分,共24分1Ln个元素进行冒泡法排序,通常需要进行n-1趟冒泡.12 .在对一组序列35,19,77,2,6,53,55,27,26,98进行直接插入排序时,当把第9个记录26插入到有序表时,为寻找插入位置需进行6次元素间的比拟.13 .在C语言中,分别存储“S和牙,各需要占用两个和1

5、个字节.14 .数据的逻辑结构在计算机中的表示称为存储结构结构.15 .在一棵二又树中,假设编号为i的结点是其双亲结点的左孩子,那么i结点的双亲结点的顺序编号为i/2.16 .设有一个头指针为head的单向链表,p指向表中某一个结点,且有p>next为NULL,现要把该单向链表构造成单向循环链表,可通过操作p>next=head；.17 .从一个栈顶指针为top的链栈中删除一个结点时,用d保存被删结点的值,可执行d=top->data；和top=top->next；.结点的指针域为next,数据域为data.18 .循环链队列中,设front和rear分别为队头和队尾指

6、针,最多元素为MaxSize,采用少用一个元素的模式,判断循环链队列为满的条件为：front=rear+l%MaxSize.19 .一棵有7个权重值构造的哈夫曼树,共有13个结点.20 .二义树中有1个1度结点,8个2度结点,那么该二义树树共有18个结点.2L如下图的二义树,其先序遍历序列为215934786.22 .在查找表中,通过记录的某关键字能唯一地确定一个记录,该关键字称为主关键字.三、综合题每题6分共30分23 .1对给定权值4,2,6,6,7,8,构造高度为4层的哈夫曼树.设根为第1层提示：构造中当出现有两个以上值相等的可选结点时,可适中选择结点组合,以限制树的高度.求树的带权路径

7、长度.(2)WPL=(4+2+6+6)*3十(7+8)*2=8424 .如下的一棵二叉树,(1)请给出前序遍历序列?请给出中序遍历序列？(2)把1,2,3,4,5,6,7,8,9填人,使它成为一棵二又排序树.提示：设图中的树是二又排序树,那么中序遍历序列是有序的,从而找出中序遍历序列与1,2,9的对应关系.在图中给出在二义排序树中插入结点2.5的结果.2d.(1)前序AlA2AlA7A8ASA9A3A6中序AZA4A&A2A5A9AlA3A6(2)A7A4A8A2ASA9AlA3A61362.5四、程序填空题(每空2分,共16分)25 .以下函数为直接选择排序算法,对al,a2,an中

8、的记录进行直接选择排序,完成程序中的空格typedefstruct(intkey；NODE：voidselsort(NODEa,intn)Inti,j,k；NODEtemp；for(i=1：i<=(1)；i+)k-i：for(j=i+1；j<=(2):j+)if(aj.key<alk.key)(3):if(i!=k)temp=ai；(4)(5)1)参考答案：(l)n-1(2)n(3)k=j(4)ai=ak(5)ak=teinp26.设有一个头指针为head的不带头结点单向链表,且p、q是指向链表中结点类型的指针变量,p指向链表中某结点a(设链表中没有结点的数据域与结点a的数据域相同),在以下程序段中,写出相关语句(1)使该单向链表成为单向循环链表删去a结点q=p；x=p->data；while(q->next!=N