国开大学2019年07月1252《数据结构(本)》期末考试参考答案.docx

上传人(卖家):天方乘风 文档编号:6900064 上传时间:2023-08-19 格式:DOCX 页数:13 大小:91.85KB
下载 相关 举报
国开大学2019年07月1252《数据结构(本)》期末考试参考答案.docx_第1页
第1页 / 共13页
亲,该文档总共13页,到这儿已超出免费预览范围,如果喜欢就下载吧!
资源描述

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

展开阅读全文
相关资源
猜你喜欢
相关搜索
资源标签

当前位置:首页 > 大学
版权提示 | 免责声明

1,本文(国开大学2019年07月1252《数据结构(本)》期末考试参考答案.docx)为本站会员(天方乘风)主动上传,163文库仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对上载内容本身不做任何修改或编辑。
2,用户下载本文档,所消耗的文币(积分)将全额增加到上传者的账号。
3, 若此文所含内容侵犯了您的版权或隐私,请立即通知163文库(发送邮件至3464097650@qq.com或直接QQ联系客服),我们立即给予删除!


侵权处理QQ:3464097650--上传资料QQ:3464097650

【声明】本站为“文档C2C交易模式”,即用户上传的文档直接卖给(下载)用户,本站只是网络空间服务平台,本站所有原创文档下载所得归上传人所有,如您发现上传作品侵犯了您的版权,请立刻联系我们并提供证据,我们将在3个工作日内予以改正。


163文库-Www.163Wenku.Com |网站地图|