内蒙古大学算法与数据结构试卷(三套)及参考答案
32页1、第 1页共 8 页计算机软件学院计算机软件学院 2006 级级 2007200720082008 学年第一学期学年第一学期算法与数据结构试卷算法与数据结构试卷(A(A 卷卷) )(闭卷 120 分钟)班级姓名学号重修标记总分题号一二三四五核分人得分复查人得分一、一、填空题(本大题共填空题(本大题共 1010 小题,每空小题,每空 1 1 分,共分,共 1616 分分)1.1. 数据结构所讨论的三个方面为、和。2.2. 将下三角矩阵A108的下三角部分按行优先存储到起始地址为1000的内存单元中,已知每个元素占 4 个单元,则 A75的地址是。3.3. 广义表( a ,b ),c ,d,( e ,( f,g ) 的表头是,表尾是,表的长度为,表的深度为。4.4. 在串 S=student 中,以 u 为首字符的子串有个。5.5. 假设以 S 和 X 分别表示入栈和出栈操作,则对输入序列 a , b , c , d 进行一系列操作 SSXSXSXX 之后,得到的输出序列为。6.6. 快速排序在排序码有序的状态下, 其时间复杂度为。 平均情况下快速排序的时间复杂度为。7.7. 已知完全二叉树
2、的第 10 层上有 7 个结点,则其结点总数为。8.8. 含有 n 个顶结点, e 条边的无向图的邻接矩阵中, 零元素的个数为。9.9. 在图的深度优先遍历算法中,用到的重要的数据结构是,10.10. 3 个结点可构成棵不同形态的树。得分得分评卷人评卷人装订线第 2页共 8 页二、二、选择题选择题(在每小题的四个备选答案中在每小题的四个备选答案中,选出一个正选出一个正确的答案,并将其号码填在题干中的括号内,本大题确的答案,并将其号码填在题干中的括号内,本大题共共 1010 小题,每小题小题,每小题 2 2 分,共分,共 2020 分)分)1111下列说法中不正确的是()A. 数据元素是数据的基本单位B. 数据项是数据中不可分割的最小可标识单位C. 数据可由若干个数据元素构成D. 数据项可由若干个数据元素构成1212. 线性表是()A. 一个有限序列,可以为空B. 一个有限序列,不可以为空C. 一个无限序列,可以为空D. 一个无限序列,不可以为空1313. 栈和队列的共同点是()A. 都是先进后出B. 都是先进先出C. 只允许在端点处插入和删除元素D. 没有共同点1414. 串是一种特殊
3、的线性表,其特殊性体现在()A. 可以顺序存储B. 数据元素可以是一个字符C. 可以链式存储D. 数据元素可以是多个字符1515. 对稀疏矩阵采用压缩存储,其缺点之一是()A. 无法判断矩阵有多少行多少列B. 无法根据列号查找某个矩阵元素C. 无法根据行列号计算矩阵元素的存储地址D. 使矩阵元素之间的逻辑关系更加复杂1616. 一棵完全二叉树上有 1001 个结点,其中叶子结点的个数是()A. 250B. 501C. 254D. 5051717. 在一个无向图中,所有顶点的度之和等于边数的()倍A. 1/2B. 1C. 2D. 41818. 一个无向连通图的生成树是含有该连通图的全部顶点的()A. 极小连通子图B. 极小子图C. 极大连通子图D. 极大子图1919. 散列表的平均查找长度()A. 与处理冲突的方法有关而与表的长度无关B. 与处理冲突的方法无关而与表的长度有关C. 与处理冲突的方法有关而与表的长度有关D. 与处理冲突的方法无关而与表的长度无关2020.快速排序方法在()情况下最不利于发挥其长处A. 要排序的数据量太大B. 要排序的数据中含有多个相同值C. 要排序的数据已基
4、本有序D. 要排序的数据个数为奇数得分得分评卷人评卷人第 3页共 8 页三、三、简答题简答题( (本大题共本大题共 5 5 小题,每小题小题,每小题 4 4 分,共分,共 2020 分分) )21.21. 数据结构中研究的逻辑结构有哪些?各有什么特点?2222阅读下列算法,说明下面递归过程的功能。int exam (BinTreeNode *root) /指针 root 指向二叉树的根指针if (t=NULL) return 0;else if (t-leftChild=NULL & t-rightChild=NULL) return 1;else return exam (t-leftChild)+exam (t-rightChild);得分得分评卷人评卷人装订线第 4页共 8 页23.23. 已知一棵二叉树的前序遍历序列为 ABDEHCG, 中序遍历序列为 DBHEACG,请画出此二叉树。24.24. 设哈希表 HT13,采用线性探测再散列解决冲突。哈希函数为:H(key)=key % 13;注:%是求余数运算(=mod)。若插入的关键码序列为2,8,31,20,19,18,53,
5、27。试画出插入这 8 个关键码后的哈希表。25.25. 已知有向图:G= V= a , b , c , d , e , f , g E=,(1) 用图画出该有向图; (2 分)(2) 写出该有向图的一个拓扑序列。 (2 分)26.26.请写出下列稀疏矩阵顺序存储的行主序的三元组表示。 008000000000507202900017000000032000780022A0123456789101112第 5页共 8 页四、四、算法应用题算法应用题( (本大题共本大题共 3 3 小题,每小题小题,每小题 8 8 分,分,共共 2424 分分) )2626. 给出从顶点 1 到顶点 8 的关键路径及关键路径长度。得分得分评卷人评卷人装订线第 6页共 8 页2727. 给出对输入的元素85,50,35,100,65,20,45,30,50,5进行归并排序的示意图。并28.28. 输入一个正整数序列40,28,6,72,100,3,54,1,80,91,38,建立一棵二叉查找树。并对该二叉查找树进行中序遍历。第 7页共 8 页五、算法设计题五、算法设计题( (本大题共本大题共 2 2 小题,
《内蒙古大学算法与数据结构试卷(三套)及参考答案》由会员东***分享,可在线阅读,更多相关《内蒙古大学算法与数据结构试卷(三套)及参考答案》请在金锄头文库上搜索。
幼儿园大班科学活动《智能留言机》课件
幼儿园大班语言绘本阅读《手电筒看见了什么》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页