内蒙古大学2009～2010 学年第二学期算法与数据结构试卷(A卷)及参考答案

第 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. 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）经过一趟排序之后，若结果为（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-prior=。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. 给出下面稀疏矩阵的三元组表示。四、四、 算法应用题算法应用题 （本大题共本大题共 3 3 小题小题， 第第 2626 小题小题 8 8 分分，第第 2727 小题和第小题和第 2828 小题各小题各 6 6 分，共分，共 2020 分）分）26. 给出拓补排序的算法思想，并对下面 AOV 网进行拓补排序，给出所有可以得到的不同拓补序列。得分得分评卷人评卷人第 6页共 13页（A 卷）27. 按 Dijkstra 算法计算下面无向网中从顶点 A 到其它各个顶点的最短路径和最短路径长度。28. 请对初始序列 22，47，95，45，16，38，47*，10，62，08，28，56 建立最小堆。第 7页共 13页（A 卷）五、五、算法题（本大题共算法题（本大题共 2 2 小题，每小题小题，每小题 1010 分，共分，共 2020 分分）29. 请阅读下列中序遍历二叉树的非递归算法，并在空缺处填入合适的内容，使其成为一个完整的算法。void InOrder ( BinaryTreeNode *root ) / 二叉树以二叉链表存储BinaryTreeNode *t ;Stackstack ;/建立栈（1）;while ( t |（2）) if ( t ) stack.Push ( t );（3）;else （4）;coutt-data;（5）;/InOrder（1）（2）（3）（4）（5）得分得分评卷人评卷人第 8页共 13页（A 卷）30利用栈将中缀表达式转换为后缀表达式，要求（1） 写出算法的算法思想；（2） 给出算法的描述，在算法的关键之处加以注释。第 10页共 13页（A 卷）六六、 单单项项选选择择题题（本本大大题题共共 10 小小题题，每每小小题题 2 分分，共共 20 分分）12345678910CDDBBBABCA七七、 填填空空题题（本本大大题题共共 11 小小题题，每每空空 1 分分，共共 20 分分）11值操作12顺序存储结构链式存储结构13时间复杂度空间复杂度14栈15O(mn)16n1-1172m-1182i2i+1(i-1)/219指针p-prior-nextp20哈希函数冲突21顶点活动八八、 解解答答题题（本本大大题题共共 4 小小题题，每每小小题题 5 分分，共共 20 分分）2223求一棵二叉树的高度的递归算法。24深度优先遍历序列：ABEGCFDHI广度优先搜索序列：ABCDEFGHI深度优先生成树广度优先生成树ACMFKBED本科课程考试试题参考答案及评分标准第 11页共 13页（A 卷）25稀疏矩阵的三元组表示032206151111151723-6353940915228九、九、 算法应用题（本大题共算法应用题（本大题共 3 小题，第小题，第 26 小题小题 8 分，第分，第 27 小题和第小题和第 28 小题各小题各 6 分，共分，共 20 分）分）26拓扑排序的算法思想：输入一个 AOV 网。令 n 为顶点个数。(1) 在 AOV 网中选一个入度为 0 的顶点，并输出之。(2) 从图中删去该顶点，同时删去与该顶点关联的弧。(3) 重复以上 (1)、(2) 步，直到全部顶点均已输出，拓扑序列形成，拓扑排序完成；或图中还有未输出的顶点，但已跳出处理循环。这说明图中还剩下一些顶点，它们都有直接前驱，再也找不到没有前驱的顶点了。这时 AOV 网中一定存在有向回路。所有可以得到的不同拓补序列：aebcdabecdabced2728最短路径最短路径长度11A-D12A-B17A-B-E18A-B-C21A-B-F第 12页共 13页（A 卷）十、十、 算法题（本大题共算法题（本大题共 2 小题，每小题小题，每小题 10 分，共分，共 20 分）分）29 （1）t=root（2）!stack.Empty()（3）t=t-leftChild（4）t=stack.Pop()（5）t=t-rightChild30 （1） 写出算法的算法思想设操作符栈（初始为，记1 为栈顶指针） ，依次读入字符，是操作数则输出，否则（读入的是操作符） ，记为2，判断：若21，则2 入栈；若21，则输出栈顶元素并退栈；若2=1（2 （且） ，退栈但不输出；否则 算法结束。（2） 给出算法的描述，在算法的关键之处加以注释。void In-Post() /OP=, *, /, +, -, (, ), #;SeqStack s;s.Push(#);ch=cin.get();while(ch!=#)|(!s.IsEmpty() if (!In(ch,OP) coutch;ch=cin.get();elseswitch(compare( s. GetTop(),ch) / s. GetTop()为1 ,ch 为2case : op=s.Pop();coutop;break; /switch /while /In-Post