1、试卷代号：1252 座位号亡二国家开放大学（中央广播电视大学）2018年秋季学期“开放本科”期未考试数据结构（本）试题口-+-+-1产艺|三一、单项选择题（每小题3分，共30分）2019年1月1.如下图所示，若从顶点a出发，按图的广度优先搜索法进行遍历，则可能得到的一种顶点序列为（）。A.acebdf B.aecbfd C.aecbdf D.acefdb 2.结构中的元素之间存在一对多的关系是（）。A.集合B.线性结构C.树形结构D.图状结构3.设有一个长度为18的顺序表，要在第4个元素之前插入1个元素（也就是插入元素作为新表的第4个元素），则移动元素个数为（）。A.15 C.5 B.16 D
2、.4 615 4.一个不带头结点的单循环链表，尾指针为rear,在链表中插入一个s所指向的新结点，并作为新的尾结点，可执行（）。A.rear-next=s;s-next=rear-next;rear=s;B.rear-next=s-next;rear=s;C.s-next=rear-next;rear-next=s-next;rear=s;D.s-next=rear-next;rear-next=s;rear=s;5.元素a,b,c,d按顺序依次进栈，则该栈的不可能输出序列是（替进行）。）（进栈出栈可以交A.c,b,a,d C.a,c,b,d B.d,c,b,a D.d,c,a,b 6.在一个
3、栈顶指针为top的链栈中进行出栈操作，用变量x保存栈顶元素的值，则执行()A.x=top-data;top=top-next;B.x=top-data;C.top=top-next;x=top-data;D.top=top-next;x=data;7.设有一个18阶的对称矩阵A,采用压缩存储的方式，将其下三角部分以行序为主序存储到一维数组B中（数组下标从1开始），则矩阵中a10,B元素对应于数组中第（矩阵中的第1个元素是a1,1)A.51 B.53 C.52 D.54）号元素。8.一棵采用链式存储的二叉树中，共有n个指针域被有效使用（即指针域为非空）。该二叉树有（）个指针域为空。A.n-t-1
4、 C.n-1 B.n D.n+2 9.在一棵二叉树中，若编号为9的结点存在右孩子，则右孩子的顺序编号为（）。A.18 C.15 B.16 D.19 10.设一棵哈夫曼树共有15个非叶结点，则该树总共有（616 A.29 c.31 B.27 D.28）个结点。得分1评卷人二、填空题（每小题2分，共24分）11.在n个整数中求最大数的算法中，其基本操作是12.设有一个长度为20的顺序表，要删除第5个元素，则最少要移动元素的个数为。13.在双向链表中，要删除p所指的结点，其中所用的一条语句(p-prior)-next=p-next;的功能是：使P所指结点的直接前驱的右指针指向14.设有一个头指针为h
5、ead的单向链表，p指向链表中的某结点，若要使该链表成为单向循环链表，可用语句while(p-next!=NULL);和p-next=head;。15.在一个链队中，设front和rear分别为队头和队尾指针，则s所指结点（数据域已赋们）的入队操作为s-next=NULL;.和rear=s;。16.字符串al=heijing,a2=hef,a3=heifang,a4=hefi中最小的是。17.栈的特点之一是：元素进、出栈的次序是：后进_o18.在对10个记录的序列(14,30,10,7,22,13,66,85,47,58)进行直接插入排序时，当把第C个记录13插人到有序表时，为寻找插人位置，元
6、素间需比较次。（由小到大排列）19.18个元素进行冒泡法排序，通常需要进行17趟冒泡，其中第10趟冒泡共需要进行次元素间的比较。20.一棵有15个结点的哈夫曼树，采用链式结构存储，该树结构中有个叶结点。21.广义表的(b,(a,b),d,(c,(e,f),j)深度是。22.序列4,2,7,9,5,3,8,6采用归并排序算法（升序），经一趟归并后，序列的结果为得分1评卷人三、综合题（每小题6分，共30分）23.(1)已知某二叉树的后序遍历序列是febch,给出该二叉树的根结点？又该二叉树的中序遍历序列是fbehc,分别给出该二叉树的左、右子树的结点？(2)画出上述二叉树？若上述二叉树的各个结点的
7、字符分别代表不同的整数（其中没有相等的），并恰好使该树成为一棵二叉排序树，试给出h、b、C、f、e的大小关系。617 24.设查找表为(1,2,3,4,5,6,7,8,9,10,11)(1)画出对上述查找表进行折半查找所对应的判定树（树中结点用数值表示）。(2)说明成功查找到元素5,9各需要经过多少次元素间的比较？(3)说明查找不到元素4.2,5.5各需要经过多少次元素间的比较？四、程序填空题（每空2分，共16分）25.以下程序是折半插入排序的算法618 设待排序的记录序列存放在al,an中，以aO作为辅助工作单元，以下程序是要把ai插入到已经有序的序列alai-1中。void binsort
8、(NODE a J,int n)int x,i,j,s,k,m;for(i=2;i=Cl);i+)aO=ai;x=ai.key;s0=1;j=i-1;while(s=j)m=(Z)if(x=j+l;k-)(5)=ak;aj+l千=aO;26.以下程序是中序遍历二叉树的递归算法的程序，完成程序中空格部分（树结构中，左、右指针域分别为left和right,数据域data为字符型，BT指向根结点）。void Inorder(struct BTreeNode*BT)ifCBT!=NULL)(1)(2)Inorder(BT-right);利用上述程序对右图进行遍历，结果是(3)勹-619 试卷代号：12
9、52 国家开放大学（中央广播电视大学）2018年秋季学期“开放本科”期末考试数据结构（本）试题答案及评分标准（供参考）2019年1月-、单项选择题（每小题3分，共30分）LC 2.C 6.A 7.B 二、填空题（每题2分，共24分）11.元素间的比较12.15 13.P所指结点的直接后继14.p=p-next 15.rear-:next=s;16.a2 17.先出18.4 19.8 20.8 21.4 3.A 8.D 4,D 9.D 5.D 10.C 22.2,4,7,9,3,5,6,8 三、综合应用题（每小题6分，共30分）23.(1)根h左子树b,f,e 右子树c(2)O G,j f fbehleft)(2)printf(%c,BT-data)(3)bedfa 621
