内蒙古大学2008~2009 学年第二学期算法与数据结构试卷(A卷)及参考答案
11页1、第 1页共 8 页计算机学院计算机学院 2007 级级 2008200820092009 学年第二学期学年第二学期算法与数据结构试卷算法与数据结构试卷(A(A 卷卷) )(闭卷 120120 分钟)班级姓名学号重修标记总分题号一二三四五核分人得分复查人得分一、一、单项选择题单项选择题(在每小题的四个备选答案中在每小题的四个备选答案中,选出一选出一个正确的答案,并将其号码填在题干中的括号内。本个正确的答案,并将其号码填在题干中的括号内。本大题共大题共 1010 小题,每小题小题,每小题 2 2 分,共分,共 2020 分)分)1. 向一个有 127 个元素的顺序表中插入一个新元素,平均要移动()个元素(假定每个位置插入的概率都相等)。A.8B.63.5C.63D.642.在头指针为 head 的非空单循环链表中,指针 p 指向尾结点,下列关系成立的是()。A. p-next=headB. p-next-next=headC. p-next=NULLD. p=head3. 设有一个二维数组Amn, 假设A00存放位置在644, A22存放位置在676,每个元素占一个字节,则 A45在()位
2、置。A. 692B.626C.709D. 7244. 设有一个顺序栈 S,元素 s1, s2, s3, s4, s5, s6 依次进栈,如果 6 个元素的出栈顺序为 s2, s3, s4, s6, s5, s1,则顺序栈的容量至少应为()。A.2B.3C.4D.55. 在一个具有 n 个顶点的有向图中,所有顶点的出度之和为 Sum ,则所有顶点的入度之和为() 。A.nB.Sum-1C.Sum+1D.Sum6. 已知用某种排序方法对关键字序列(51,35,93,24,13,68)进行排序时,前两趟排序的结果为(13,51,35,93,24,68)和(13,24,51,35,93,68)所采用的排序方法是()。A. 直接插入排序B. 冒泡排序C. 快速排序D. 归并排序得分得分评卷人评卷人装订线第 2页共 8 页7. 已知一棵含 50 个结点的二叉树中只有一个叶结点, 则该二叉树中度为 1 的结点个数为().A. 0B. 1C. 48D. 498. 某二叉树的前序遍历和后序遍历序列正好相同, 则该二叉树一定是 () 的二叉树。A. 空或只有根结点B. 高度等于其结点数C. 任一结点无做孩
3、子D. 任一结点无有孩子9. DFS 算法的时间复杂度为()。A. O(n)B. O(n2)C. (n3)D. O(n+e)10. 下列排序算法中,时间复杂度不受数据初始状态影响,恒为 O(logn)的是()。A. 直接选择排序B. 冒泡排序C. 堆排序D.快速排序二、二、填空题(本大题共填空题(本大题共 1313 小题,每空小题,每空 1 1 分,共分,共 2020 分)分)11. 数据元素是。数据项是。12. 算法除了具有输入和输出特性之外, 还具有、和特性。13. 队列是特殊的线性表, 它的特殊性在于。14. 将对称矩阵 Ann中进行按行优先顺序压缩存储在一维数组 B中时,元素 Aij(0ijn-1) 在 B 中的下标为。15. 二叉树一共有种形态。16. 在 K(K2)叉树中的第 i 层上最多有个结点(设根在第 1 层) 。17. 在对二叉查找树进行中序遍历时,遍历序列中关键码。18. 对图进行深度优先遍历和广度优先遍历时,算法中用到的关键数据结构分别为和。19.AOE 的含义是。AVL 的含义是。20. 快速排序算法在最坏情况下和平均情况下的时间复杂度分别为和。21. 希尔排
4、序是对排序的改进。22. 若有向图中顶点数为 n,弧数为 e,则用邻接矩阵表示有向图时,有个数据元素,有个非零元素。23. 链接存储的特点是利用来表示数据元素之间的逻辑关系。得分得分评卷人评卷人第 3页共 8 页三、三、解答题解答题(本大题共本大题共 4 小题小题,每小题每小题 5 分分,共共 20 分分)24. 设一棵二叉树的前序序列、中序遍历分别为 DBACFEG 和 ABCDEFG。请画出这棵二叉树,并给出后序遍历序列。25. 请给出一种在循环队列中,解决队空和队满的方案。得分得分评卷人评卷人装订线第 4页共 8 页26. 简述下列算法的功能。intexam1 (BinTreeNode*root ) if ( !root ) return 0;elsereturn 1 + Max (exam1 ( rootleftChild ), exam1 ( rootrightChild ) );其中:Max(a,b)函数是求 a,b 的最大值。27. 请写出下列稀疏矩阵按行优先顺序压缩存储时的三元组表示。 15000900000012022000000000017230000003500A
《内蒙古大学2008~2009 学年第二学期算法与数据结构试卷(A卷)及参考答案》由会员东***分享,可在线阅读,更多相关《内蒙古大学2008~2009 学年第二学期算法与数据结构试卷(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页