电子文档交易市场
安卓APP | ios版本
电子文档交易市场
安卓APP | ios版本

《数据结构》期末考试题及答案

7页
  • 卖家[上传人]:小**
  • 文档编号:60832369
  • 上传时间:2018-11-19
  • 文档格式:PDF
  • 文档大小:61.98KB
  • / 7 举报 版权申诉 马上下载
  • 文本预览
  • 下载提示
  • 常见问题
    • 1、1 2011-2012 学年第一学期期末考查 数据结构试卷 (答案一律写在答题纸上,在本试卷上做答无效) 一、选择(每题 1 分,共 10 分) 1.长度为 n 的线性表采用顺序存储结构,在其第i 个位置插入一个新元素的算法时间复 杂度为() A.O(0) B.O(1) C.O(n) D.O(n 2) 2.六个元素按照 6,5,4,3,2,1 的顺序入栈,下列哪一个是合法的出栈序列?() A.543612 B.453126 C.346512 D.234156 3.设树的度为 4,其中度为 1、2、3、4 的结点个数分别是4、2、1、2,则树中叶子个数 为( ) A.8 B.9 C.10 D.11 4.设森林 F 对应的二叉树 B 有 m 个结点, B 的右子树结点个数为n,森林 F 中第一棵树 的结点个数是() A. m-n B.m-n-1 C.n+1 D.m+n 5.若一棵二叉树具有10 个度为 2 的结点,5 个度为 1 的结点,则度为 0 的结点个数是( ) A.9 B.11 C.15 D.不确定 6.下列哪一个方法可以判断出一个有向图是否有环。() A.深度优先遍历B.拓扑排序

      2、C.求最短路径D.求关键路径 7.第 7 层有 10个叶子结点的完全二叉树不可能有()个结点。 A.73 B.234 C.235 D.236 8.分别用以下序列构造二叉排序树,与用其他三个序列构造的结果不同的是() A.(100,80,90,60,120,110,130 )B.(100, 120, 110,130,80, 60,90 ) C.(100,60,80,90,120,110,130 )D.(100,80, 60,90, 120, 130,110 ) 9.对一组数据( 84,47,25,15,21)排序,数据的排列次序在排序过程中变化如下: (1)84 47 25 15 21 (2)15 47 25 84 21 (3)15 21 25 84 47 (4)15 21 25 47 84则采用 的排序方法是() 2 A.选择排序B.起泡排序C.快速排序D.插入排序 10.对线性表进行折半查找时,要求线性表必须() A.以顺序方式存储B.以顺序方式存储,且数据元素有序 C.以链接方式存储D.以链接方式存储,且数据元素有序 二、填空(每空 1 分,共 15 分) 1.数据结构中评价算法的

      3、两个重要指标是、空间复杂度。 2.在单链表中, 指针 P所指结点有后继的条件是。 (结点构成: data和 next) 3.栈的特点是。 4.判断循环队列是否队满的条件表达式是。 5.完全二叉树中的结点个数为n,则编号最大的分支结点的编号为。 6.如果 A 有 7 个兄弟,而 B 是 A 的双亲,则 B 的度是。 7.如果二叉树中有20 个叶子节点, 30 个度为1 的结点,则该二叉树的总结点数 为。 8.设二叉树中每个结点均用一个字母表示,若一个结点的左子树或者右子树为空,用. 表示。现前序遍历二叉树的结点序列为ABD.G CE.HF,则中序遍历二叉树的结点序 列为。 9.若用 n 表示图中的顶点数目,则有条边的无向图被称为完全图。 10.如果具有 n 个顶点的图是一个环,则它有棵生成树。 11.克鲁斯卡尔算法的时间复杂度是, 它适合求图的最小生成树。 12.顺序查找 n 个元素的线性表,若查找成功时的平均查找长度为。 13.高度为 5 的完全二叉树,其结点最少有个。 14.直接插入排序中使用的监视哨的作用是。 三、判断题(每题1 分,共 10 分) 1.算法独立于具体的程序设计语言

      4、,与具体的计算机无关。() 2.线性表采用链式存储时,结点内部的存储空间可以是不连续的。() 3.栈和队列的存储方式,既可以是顺序方式,又可以是链式方式。() 4.哈夫曼树的结点总个数一定是偶数。() 5.已知二叉树的先序遍历序列和中序遍历序列,可以画出这棵二叉树()。 3 6.有 e条边的无向图,在其对应的邻接表中有e个结点。() 7.连通分量指的是无向图的极大连通子图。() 8.在哈希表的查找过程中的“比较”操作是无法避免的。() 9.完全二叉树肯定是平衡二叉树。() 10.堆排序是稳定的排序算法。() 四、简答题(共 30 分) 1. 线性结构的特点是?( 4 分) 2. 已知图的邻接矩阵存储如下所示,请根据该邻接矩阵画出对应的图,并给出从 A 出发 的广度优先搜索序列,以及相应的广度优先生成树。(6 分) A B C D E F A B C D E F 3. 已知一棵二叉树的后序遍历序列为EICBGAHDF ,中序遍历序列为CEIFGBADH ,请 画出这棵二叉树,并把这棵二叉树转换成相应的树(或森林)。(6 分) 4. 已知电文内容为: ACACBACDAACDBAACADA

      5、A,字符集为 A,B,C,D,设计一 套二进制编码,使得上述电文的编码最短。(6 分) 5. 已知有序序列 3 ,7,11,20,45,77,90,请分别写出折半查找10和查找 99 的过 程,并求出 ASL(4 分) 6. 已知序列 34,17,6,29,33,11,80,37请用快速排序的方法进行排序,并给出 详细过程。( 4 分) 五、算法填空(每空5 分,共 20 分) (1)按先序次序输入二叉树中的结点值(字符)构造二叉树 Status CreateBiTree(BiTree 010010 100011 000101 001001 110000 011100 4 read(ch); if( ch= ) T = NULL; else T = (BiTree)malloc(sizeof(BiTNode); (1) ; CreateBiTree(T-lchild); (2) ; return OK; (2)在顺序表 L 的第 i 个元素之前插入新的元素e Status ListInsert(SqList / 插入位置不合法 for ( j= L.length ; ji ; j -

      6、- ) (3) ; L.elemi-1 = e ; / 插入 e (4) ; return OK; / ListInsert_Sq 六、写算法(共 15 分) 1.请写出链式存储的线性表中,删除第i 个位置数据元素的实现算法。(给出相应的结 构体定义,关键部分给出注释。) 20112012 学年第一学期期末考查 数据结构标准答案 一、选择(每题 1 分,共 10 分) 1-5 DBBBB 6-10 ACCDB 二、填空(每空 1 分,共 15 分) 1.时间复杂度,空间复杂度 2.FIFO,LIFO 3.Q.rear=Q.front 5 4.7 5.8 6.O(n 2) ,稠密图 7.极大连通子图 8.n(n-1) 9.n-1 10.集合结构,树形结构,图状结构 三、判断题(每题1 分,共 10 分) 1.2. 3. 4. 5. 6. 7. 8. 9. 10. 四、简答题(共 30 分) 1. (1)在二叉树的第i 层上至多有 2i-1 个结点;(i1) (2)深度为 k 的二叉树上至多含2k-1 个结点( k1); (3)对任何一棵二叉树,若它含有n0 个叶子结点、 n2 个度为 2

      7、 的结点,则必存在关系 式:n0 = n2+1; (4)具有 n 个结点的完全二叉树的深度为log2n +1 。 (5)若对含 n 个结点的完全二叉树从上到下且从左至右进行1 至 n 的编号,则对完全 二叉树中任意一个编号为i 的结点: 若 i=1,则该结点是二叉树的根,无双亲,否则, 编号为i/2的结点为其双亲结点;若2in,则该结点无左孩子,否则,编号为2i 的 结点为其左孩子结点;若2i+1n,则该结点无右孩子结点,否则,编号为2i+1 的结点 为其右孩子结点。 评分标准:答对 5 条中的 4 条得 4 分。 2. 深度优先遍历序列: abefdc 深度优先生成树: 评分标准:深度优先遍历序列3 分,深度优先生成树3 分。 3.(1)T-next-next=P-next; (2)Q=T; c d f e b a 6 While(Q-!=P) Q=Q-next; Q-next=P-next; free(P); 评分标准:回答( 1)或者( 2)都正确。 4. 5.11,3,7,77,20,45,90 查找过程: 11,3,7,77 或者 90,45,20,77 6.34,17,6,29,33,11,80,37 d=5 11,17,6,29,33,34,80,37 d=3 11,17,6,29,33,34,80,37 d=1 6,11,17,29,33,34,37,80 五、算法填空(每空5 分,共 20 分) 1. (1)visit(T-data); 或者printf(T-data); (2)PreOrderTraverse(T-rchild); 2.(1)return mid; (2)high=mid-1; 六、写算法(共 15 分) /删除表 L 中第 i 个元素,结果用e返回,操作成功返回OK,失败时返回 ERROR Status ListDelete(SqList A B C D E F 7 e=L.elemi-1; for(int j=i+1;j=L.length;j+) L.elemj-2=L.elemj-1; L.length-; return OK;

      《《数据结构》期末考试题及答案》由会员小**分享,可在线阅读,更多相关《《数据结构》期末考试题及答案》请在金锄头文库上搜索。

      点击阅读更多内容
    最新标签
    发车时刻表 长途客运 入党志愿书填写模板精品 庆祝建党101周年多体裁诗歌朗诵素材汇编10篇唯一微庆祝 智能家居系统本科论文 心得感悟 雁楠中学 20230513224122 2022 公安主题党日 部编版四年级第三单元综合性学习课件 机关事务中心2022年全面依法治区工作总结及来年工作安排 入党积极分子自我推荐 世界水日ppt 关于构建更高水平的全民健身公共服务体系的意见 空气单元分析 哈里德课件 2022年乡村振兴驻村工作计划 空气教材分析 五年级下册科学教材分析 退役军人事务局季度工作总结 集装箱房合同 2021年财务报表 2022年继续教育公需课 2022年公需课 2022年日历每月一张 名词性从句在写作中的应用 局域网技术与局域网组建 施工网格 薪资体系 运维实施方案 硫酸安全技术 柔韧训练 既有居住建筑节能改造技术规程 建筑工地疫情防控 大型工程技术风险 磷酸二氢钾 2022年小学三年级语文下册教学总结例文 少儿美术-小花 2022年环保倡议书模板六篇 2022年监理辞职报告精选 2022年畅想未来记叙文精品 企业信息化建设与管理课程实验指导书范本 草房子读后感-第1篇 小数乘整数教学PPT课件人教版五年级数学上册 2022年教师个人工作计划范本-工作计划 国学小名士经典诵读电视大赛观后感诵读经典传承美德 医疗质量管理制度 2 2022年小学体育教师学期工作总结 2022年家长会心得体会集合15篇
    关于金锄头网 - 版权申诉 - 免责声明 - 诚邀英才 - 联系我们
    手机版 | 川公网安备 51140202000112号 | 经营许可证(蜀ICP备13022795号)
    ©2008-2016 by Sichuan Goldhoe Inc. All Rights Reserved.