1、试卷代号：1252 座位号亡二国家开放大学20 1 9年春季学期期未统一考试数据结构（本）试题2019年7月I:1 I=II四1色分1得分1评卷人一、单项选择题（每小题3分，共30分）1.以下说法正确的是（）。A.在顺序表中可以随机访问任一结点B.一种逻辑结构在存储时只能采用一种存储结构C.对链表进行插入、删除元素的操作一定要移动结点D.在链表中可以随机访间任一结点2.线性表在存储后，如果要求：仅通过已知的指向第1个结点的指针，进行相关操作，访问到该结点的前驱结点，则采用（）存储方式是不可行的。A.单链表B.双链表C.单循环链表D.顺序表3.栈和队列的共同特点是()。A.都是先进后出C.只容许
2、在端点处插入和删除元素B.元素都可以随机进出D.都是先进先出4.元素4,6,8,10按顺序依次进栈，按该栈的可能输出序列依次入队列，该队列的可能输出序列是（）（进栈出栈可以交替进行）。60 l,4,6 8,4 0,18 AC B.10,6,4,8 D.10,8,6,4 5.在一个不带头结点的链队中，假设f和r分别为队头和队尾指针，从该队列中进行出队操作，并把结点的值保存在变量x中的操作为（）。A.x=rdata;r=rnext;B.r=rnext;x=rdata;C.x=fdata;f=fnext;D.f=fnext;x=fdata;582 6.设有一个18阶的对称矩阵A,采用压缩存储的方式，
3、将其下三角部分以行序为主序存到一维数组B中（数组下标从1开始），则矩阵元素a趴2对应于数组B中第（）号元素。（矩阵中的第1个元素是a1.1)A.42 B.39 C.38 D.40 7.一棵采用链式存储的二叉树中，共有n-1个指针域被有效使用（即指针域为非空）。该二叉树中有（）个指针域为空。A.n+l B.n C.n-1 D.n-2 8.设一棵哈夫曼树共有n个非叶结点，则该树共有（）个结点。A.2n C.2n-1 B.2n+l D.2n+2 9.如图所示，若从顶点a出发，按图的广度优先搜索法进行遍历，则可能得到的一种顶点序列为（）。A.ahbedfc C.ahebcdf B.ahcfebd D.
4、ahebcfd 10.线性表以（）方式存储，能进行折半查找。A.关键字有序的链接B.顺序C.关键字有序的顺序D.数组得分1评卷人二、填空题（每小题2分，共24分）11.n个元素进行冒泡法排序，通常需要进行趟冒泡。12.在对一组序列(35,19,77,2,6,53,55,27,26,98)进行直接插入排序时，当把第9个记录26插入到有序表时，为寻找插入位置需进行次元素间的比较。13.在C语言中，分别存储S和s,各需要占用字节。14.数据的逻辑结构在计算机中的表示称为结构。583 15.在一棵二叉树中，若编号为i的结点是其双亲结点的左孩子，则i结点的双亲结点的顺序编号为16.设有一个头指针为hea
5、d的单向链表，p指向表中某一个结点，且有p-next为NULL,现要把该单向链表构造成单向循环链表，可通过操作17.从一个栈顶指针为top的链栈中删除一个结点时，用d保存被删结点的值，可执行d=topdata;和。（结点的指针域为next,数据域为data)。18.循环链队列中，设front和rear分别为队头和队尾指针，（最多元素为MaxSize,采用少用一个元素的模式），判断循环链队列为满的条件为19.一棵有7个权重值构造的哈夫曼树，共有个结点。20.二叉树中有1个1度结点，8个2度结点，则该二叉树树共有个结点。21.如图所示的二叉树，其先序遍历序列为22.在查找表中，通过记录的某关键字能
6、唯一地确定一个记录，该关键字称为得分1评卷人三、综合题（每小题6分，共30分）23.(1)对给定权值4,2,6,6,7,8,构造高度为4层的哈夫曼树。（设根为第1层）提示：构造中当出现有两个以上值相等的可选结点时，可适当选择结点组合，以控制树的高度。(2)求树的带权路径长度。584 24.如下的一棵二叉棵树，(1)请给出前序遍历序列？请给出中序遍历序列？(2)把1,2,3,4,5,6,7,8,9填人，使它成为一棵二叉排序树。提示：设图中的树是二叉排序树，则中序遍历序列是有序的，从而找出中序遍历序列与1,29的对应关系。(3)在图中给出在二叉排序树中插入结点2.5的结果。得分1评卷人四、程序填空
7、题（每空2分，共16分）25.以下函数为直接选择排序算法，对al,a2,an中的记录进行直接选择排序，完成程序中的空格typedef struct int key;NODE;void selsort(NODE a,int n)int i,j,k;NODE temp;for(i=l;i=(1);i+)585 k=i;for(j=i+l;j=ill_ if(aj.keydata;while(q-next!=NULL)q=q-next;(1)q=p;p=p-next;while(p-data!=x)q=p;(2)(3)586 试卷代号：1252 国家开放大学2019年春季学期期末统一考试数据结构（本
8、）试题答案及评分标准（供参考）2019年7月一、单项选择题（每小题2分，共30分）1.A 2.A 6.C 7.A 二、填空题（每题2分，共z,1分）11.n-1 12.6 13.两个和1个14.存储结构15.i/2 16.p-next=head;17.top=top-next;18.front=(rear+l)%MaxSize CB.38 4.D 9.C 5.C 10.C 19.13 19.18 20.1 21.215934786 22.主关键字三、综合应用题（每小题6分，共30分）23.(1)587(2)WPL=(4+2+6+6)*3+C7+8)*2=84 24.(1)前序AlAZ A4 A7 AS A5 A9 A3 A6 中序A7A4 AS AZ A5 A9 Al A3 A6(2)A7 A4 AS AZ A5 A9 Al A3 A6 1 2 3 4 5 6 7 8 9(3)-丿四、程序填空题（每空2分，共16分）25.(l)nl(2)n C3)k=j(4)ai=ak(5)ak=temp 26.(l)qnext=head;(2)p=p-next;(3)q-next=p-next;588
