考试(田际平)

《考试(田际平)》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、学院领导审批并签名AB卷广州大学学年第学期考试卷课程数据结构与算法考试形式（闭卷，考试）信息学院系专业级班学号：姓名：题次一二三四五六总分评卷人分数201010302010100评分一、填空题：（每格2分，共20分）1．任何基于关键字的排序算法，其时间复杂度即使在最坏的情况下也都大于或等于O(nlog2n).2．平衡二叉树（又称AVL树）的一个典型问题是平衡的二叉排序树（又称二叉查找树），保持二叉排序树的平衡形态可避免在查找等操作中使其退化为单枝树，即避免相应算法的时间性能由O(log2n)降低为.矚慫润厲钐瘗睞枥庑赖。3．可用迭代法将递归算法转换为非递归算

2、法，也可利用来模拟递归过程使递归算法转换为非递归算法.4．若一个有向图G中的所有顶点可排成一个线性序列，使得G中任一对顶点u和v若满足∈E(G)则u在该序列中出现在v之前，那么该序列称为图G的.聞創沟燴鐺險爱氇谴净。5．在伙伴系统中记录所占用的内存区（块）大小必为的k次幂.6．复杂数据结构中的不相交集合类主要是为了解决问题.7．在哈希表（散列）中填入的记录个数n，与哈希表的表长m之比称为哈希表的.8．表达式由运算数与运算符（二元运算）序列构成，若某二叉树的中序遍历恰恰反映为这种序列，则表达式的运算符均应为二叉树的结点.残骛楼諍锩瀨濟溆塹籟。9．广义

3、表的元素可能有各种结构，但广义表自身应是的结构10．从稳定性看，快速（分划交换）排序和堆排序相对来说是的.二、单项选择题（每题1分，共10分）1．（）评价算法优劣的基本标准包含A．复杂性和节省性B．正确性和可读性C．确定性和有穷性D．输入性和输出性2．（）线性表两端各设一个指针，插入元素总在一端指针指示处，而删除元素总在另一端指针的指示处，那么按此操作特点它应该是酽锕极額閉镇桧猪訣锥。A．串B．数组C．栈D．队列3．（）深度为k(k≥1)的满二叉树，其结点个数为A．2kB．2k-1C．2k–1D．2k–1–14．（）若待排序的序列已基本有序，要使序列完全有序

4、，则从关键字的比较次数和移动次数考虑，应使用的排序方法是彈贸摄尔霁毙攬砖卤庑。A．快速排序B．归并排序C．直接插入排序D．直接（简单）选择排序5．（）对记录数n=5000的表排序，那么最坏情况下最快且稳定的方法是A．快速排序B．归并排序C．堆排序D．希尔排序6．（）若带权有向图G，已按迪杰斯特拉（Dijkstra）算法求得源点v到G中各顶点的最短路径，则下列各最短路径长度的正确求解次序是謀荞抟箧飆鐸怼类蒋薔。A．60，30，50，10B．30，50，10，60C．50，10，60，30D．10，30，50，607．（）查找可基于各种方法，由于杂凑是基于的，故

5、它融会了表的构造和查找.A．比较B．数字匹配C．函数计算D．交换8．（）以下不是键树（数字查找数）特点的是A．度不小于2的多叉有序树B．查找不是通过关键字之间的比较而是利用关键字自身C．关键字被分解为字符序列且结束符小于任何字符D．树中每个结点代表一个关键字9．（）满足先根次序遍历序列与中根次序遍历序列相同的是A．任一结点均无左子树的单支二叉树B．任一结点均无右子树的单支二叉树C．空树或为任一结点均无左子树的单支二叉树D．空树或为任一结点均无右子树的单支二叉树10．（）下列那条与图的生成树无关A．包含原图的n个顶点和n-1条边的连通图B．在A基础上去掉一条边

6、就成为非连通图C．在A基础上再加一条边就存在环（回路）D．如A产生的连通图是唯一的三、判断题（在括号内填上“√”或“╳”，每题1分，共10分，做错不倒扣）1（）给定二叉树遍历的先序序列和后序序列便可唯一地确定一棵二叉树.2（）串是一种特殊的线性表，所以也能用一维数组或单链表来存储.3（）在串的模式匹配算法中无论怎样也无法消除回溯问题.4（）抽象数据类型（ADT）是一个数学模型及在其上定义的操作集合.5（）在解决具有搜索回溯性质问题的算法中，栈比队列更便于利用.6（）n个顶点的强连通图至少有n条边，这样的有向图是会存在环的.7（）二叉树是一般树的特例.8（）关

7、键路径是指在AOE图中从源点到汇点的路径长度最短的路径.9（）树与森林不同于二叉树的遍历，它们只有先根与后根两种遍历次序.10（）最小生成树的形态是否唯一与图中边的权值无关.四、画图/计算/证明/算法分析（30分）（1）证明题（8分）如果一棵树有n1个度为1的结点，n2个度为2的结点，……，nm个度为m的结点，证明叶结点的个数n0=1+｛提示：模仿二叉树性质证明｝.厦礴恳蹒骈時盡继價骚。（2）画图及计算题（8分）某工程的AOE网如右图所示，弧上的权值为活动a1～a10的期限（即完成活动所需的天数）.求：①该工程各事件的最早发生时间Ve和允许的最晚发生时间Vl

8、及各活动的最早开始时间e和允许的最晚开始时间l(请列