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