内蒙古大学2009~2010 学年第二学期算法与数据结构试卷(A卷)及参考答案
11页1、第 1页共 13页(A 卷)计算机学院计算机学院 2008 级级 2009200920102010 学年第二学期学年第二学期算法与数据结构试卷算法与数据结构试卷(A(A 卷卷) )(闭卷 120120 分钟)班级姓名学号重修标记总分题号一二三四五核分人得分复查人得分一、一、 单项选择题(在每小题的四个备选答案中,选出单项选择题(在每小题的四个备选答案中,选出一个正确的答案,并将其号码填在下面表格内。本一个正确的答案,并将其号码填在下面表格内。本大题共大题共 1010 小题,每小题小题,每小题 2 2 分,共分,共 2020 分)分)123456789101. 算法的特性除了具有输入、输出、可行性和有穷性外,还具有() 。A. 正确性B. 高效率C. 确定性D. 可读性2. 在线性表的下列存储结构中,读取元素花费时间最少的是() 。A. 单链表B. 双向链表C. 循环链表D. 顺序表3. 为了节省空间, 对对称矩阵进行压缩存储, 若只存储主对角以及主对角以下的元素,则对于 A1010的对称矩阵,元素 A85应存储在一维数组 M 中的下标为() (设下标均从 0 开始) 。A. 23B.
2、32C. 14D. 414. 为解决计算机与打印机之间速度不匹配的问题,通常设置一个打印数据缓冲区,主机将要输出的数据依次写入该缓冲区,而打印机则依次从该缓冲区中取出数据。该缓冲区的逻辑结构应该是() 。A. 栈B. 队列C. 树D. 图得分得分评卷人评卷人装订线第 2页共 13页(A 卷)5. 对于有序查找表:11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,用二分查找法查找 16 时需进行()次比较。A. 2B. 3C. 4D. 56. 对二叉排序树进行() ,可使得元素的关键码从小到大排序。A. 前序遍历B. 中序遍历C. 后序遍历D. 层次遍历7. 若无向图 G(V,E)中含 11 个顶点,则保证图 G 在任何顶点都是连通的情况下,需要的边数最少是() 。A. 10B. 11C. 12D. 138. 求单源最短路径采用的是()算法。A. PrimB. DijkstraC. KruskalD. Floyd9. 下面()排序是不稳定排序。A直接插入B. 归并C. 堆D. 冒泡10. 对一组数据(22,50,38,66,05,18)经过一趟排序
3、之后,若结果为(18,05,22,66,38,50) ,则采用的排序方法可能是() 。A快速排序B. 希尔排序C. 直接选择排序D. 折半插入排序二、二、 填空题(本大题共填空题(本大题共 1111 小题,每空小题,每空 1 1 分,共分,共 2020 分)分)11. 数据类型定义为一个的集合以及定义在该值集合上的一组的总称。12. 数据的存储结构分为和。13.一个算法的效率主要由和来度量。14. 递归和密不可分。15. 输出一个二维数组 Amn中所有元素值的时间复杂度是。16. 设森林 F 中有 4 棵树,第 1、2、3、4 棵树的结点个数分别为 n1、n2、n3、n4,当把该森林 F 转换成一棵二叉树后,其根结点的左子树有个结点。17. 有 m 个叶结点的二叉树最少有个结点。得分得分评卷人评卷人第 3页共 13页(A 卷)18. 若对一棵二叉树从 1 开始进行结点编号,并按此编号把它顺序存储到一维数组a 中,则 ai元素的左子女结点编号为,右子女结点编号为,双亲结点编号为。19. 与单链表相比,双向链表在每个结点中增加了一个域,若指针 p指向表中某一结点,则 p-next-prio
4、r=。20. 在建造哈希表时不仅要设计一个“好”的,同时也要设计一种处理的方法。21. AOE 网是用表示事件,用弧表示一个工程中的各项,用弧上的权值表示活动的持续时间的网。三、三、 解答题解答题 (本大题共本大题共 4 4 小题小题, 每小题每小题 5 5 分分, 共共 2020 分分)22. 已知一棵二叉树的中序遍历序列为 DBKEAFMC,后序遍历序列为 DKEBMFCA,试画出满足以上遍历序列的二叉树。得分得分评卷人评卷人第 4页共 13页(A 卷)23读下列算法,叙述该算法的功能。intexam(BinaryTreeNode *t) / 初值 t 为指向二叉树的根指针if (!t) return0;lh=exam(t-leftChild);rh=exam(t-rightChild);return 1+(lhrh?lh:rh);24对下列无向图进行:(1)从顶点 A 出发进行深度优先遍历所得到的序列和深度优先生成树;(2)从顶点 A 出发进行广度优先遍历所得到的序列和广度优先生成树。第 5页共 13页(A 卷)25. 给出下面稀疏矩阵的三元组表示。四、四、 算法应用题算法应用题
《内蒙古大学2009~2010 学年第二学期算法与数据结构试卷(A卷)及参考答案》由会员东***分享,可在线阅读,更多相关《内蒙古大学2009~2010 学年第二学期算法与数据结构试卷(A卷)及参考答案》请在金锄头文库上搜索。
幼儿园大班科学活动《智能留言机》课件
幼儿园大班语言绘本阅读《手电筒看见了什么》PPT
幼儿园小班科学《教宝宝认识动物》课件
幼儿园中班语言《灰狼家的小饭桶们》教案
【国家审计报告】审计报告W-06审计处罚决定书
【企业财务管理办法】会计档案管理办法
【员工主动离职-风险防范】劳动争议判决书
【员工被动离职-后续工作】70-070员工违反有关商业秘密的约定可以索赔吗
【员工被动离职-辞退申请】第六节 员工任免通知书
【员工被动离职-后续工作】70-050因员工的原因使服务期无法完成可以索赔吗
企业岗位管理制度12办公室行为规范
企业岗位管理制度30离职人员薪资发放通知单
幼儿园春游活动美丽的公园教案
呼职院电力机车制动机讲义11高速列车和重载列车制动
武理工《运输管理》教案第1章 运输系统
中海大海洋化学讲义02海洋的形成和海水的组成——兼论地球上水的起源、变迁和循环
武理工船舶柴油机习题库及答案04燃油喷射和燃烧
厦大海洋生态学课件07海洋初级生产力
华北理工水声学课件05声波在目标上的反射和散射-1目标强度及常见声纳目标的目标强度的一般特征
武理工船舶结构与设备课件02船体结构与管系-4专用船特殊船体结构特点
2023-09-25 37页
2023-09-25 10页
2023-09-25 33页
2023-09-25 26页
2023-04-03 8页
2023-04-03 4页
2023-04-03 8页
2023-03-29 10页
2023-03-22 10页
2023-03-20 8页