资源描述：
《试题(田际平)1》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。
1、学院领导审批并签名广州大学学年第学期考试卷课程数据结构与算法考试形式（闭卷，考试）信息学院系专业级—班学号：姓名：题次—二三四五六总分评卷人分数201010302010100评分一、填空题：（每格2分，共20分）1•任何基于关键字的排序算法，其时间复杂度即使在最坏的情况下也都大于或等于O（nlog2n）o2.平衡二叉树（又称AVL树）的一个典型问题是平衡的二叉排序树（又称二叉查找树），保持二叉排序树的平衡形态可避免在查找等操作中使其退化为单枝树，即避免相应算法的吋间性能由O（log2n）降低为o3.可用迭代法将递归算
2、法转换为非递归算法，也可利用来模拟递归过程使递归算法传换为非递归算法。4.若一个有向图G中的所有顶点可排成一个线性序列，使得G中任一对顶点u和v若满足vu,v>GE（G）则u在该序列中出现在v之询，那么该序列称为图G的o5.在伙伴系统中记录所占用的内存区（块）大小必为的k次幕。6.复杂数据结构中的不相交集合类主要是为了解决问题。7.在哈希表（散列）中填入的记录个数n,与哈希表的表长mZ比称为哈希表的o8.表达式由运算数与运算符（二兀运算）序列构成，若某二叉树的屮序遍历恰恰反映为这种序列，则表达式的运算符均应为二叉树的
3、结点。9•广义表的元素可能有各种结构，但广义表口身应是的结构10•从稳定性看，快速（分划交换）排序和堆排序相对来说是的。二、单项选择题（每题1分，共10分）1.(）评价算法优劣的基本标准包含A.B.C.D.复杂性和节省性正确性和口J读性确定性和有穷性输入性和输岀性2.(）线性表两端各设一个指针，插入元素总在一端指针指示处，而删除元素总在另一端指针的指示处，那么按此操作特点它应该是A.串B.数组C.栈D.队列3.()深度为k（kMl）的满二叉树，其结点个数为A.2kB.2k_,C.2k-1D.2k_1-14.(）若待排
4、序的序列已基木有序，要使序列完全有序，则从关键字的比较次数和移动次数考虑，应使用的排序方法是A.快速排序B.归并排序C.直接插入排序D.直接（简单•）选择排序5.()对记录数n=5000的表排序，那么最坏情况下最快且稳定的方法是A.快速排序B.归并排序C.堆排序D.希尔排序6.()若带权冇向图G,已按迪杰斯特拉（Dijkstni）算法求得源点v到G中各顶点的最短路径，则卜•列各最短路径长度的止确求解次序是A.60,30,50,10B.30,50,10,60C.50,10,60,30D.10,30,50,607.（）查
5、找可基于各种方法，由于朵凑是基于的，故它融会了表的构造和查找。A.B.C.D.()A.B.C.D.9.10.()满足先根次序遍丿刃序列与中根次序遍丿刃序列相同的是A.B.C.D.()A・B.C・D.任一结点均无左子树的单支二叉树任一结点均无右子树的单支二叉树空树或为任一结点均无左子树的单支二叉树空树或为任一结点均无右了树的单支二叉树卜•列那条与图的生成树无关••包含原图的n个顶点和n・l条边的连通图在A基础上去掉一•条边就成为非连通图在A基础上再加一条边就存在环(回路)如A产生的连通图是唯一的比较数字匹配函数计算交换
6、以下不是键树(数字查找数)特点的是••度不小于2的多叉有序树查找不是通过关键字之间的比较而是利用关键字自身关键字被分解为字符序列11结束符小于任何字符树中每个结点代表一个关键字三、扣)12345678910四、串是一种特殊的线性表，所以也能用一维数组或单链表来存储。在吊的模式匹配算法中无论怎样也无法消除回溯问题。抽彖数据类型(ADT)是一个数学模型及在其上定义的操作集合。在解决具有搜索冋溯性质问题的算法中，栈比队列更便于利用。n个顶点的强连通图至少有n条边，这样的有向图是会存在环的。二叉树是一般树的特例。关键路径是指
7、在AOE图中从源点到汇点的路径长度最短的路径。判断题(在括号内填上“厂或“X”，每题I分，共10分，做错不倒)给定二叉树遍历的先序序列和后序序列便可唯一地确定一棵二叉树。))))))))树与森林不同于二叉树的遍丿力，它们只冇先根与后根两种遍历次序。)最小生成树的形态是否唯一与图中边的权值无关。画图/计算/证明/算法分析(30分)(1)证明题(8分)，%个度为m如果一棵树有ni个度为1的结点，血个度为2的结点,的结点，匹叩叶结点的个数no=l+^(/-lX.｛提示：模仿二叉树性质证明｝o（2）画图及计算题（8分）某工程
8、的AOE网如右图所示，弧上的权值为活动al-alO的期限（即完成活动所需的天数）。求：①该工程各事件的最早发生时间Ve和允许的最晚发牛.时间VI及各活动的最早开始时间e和允许的最晚开始时间1（谙列表Ve,Vl,e,I的各时间），②完成此项工程至少需要多少时问，及哪些活动是关键活动？（3）已知某段电文中仅可能出现C,A,T,F,I五个字符,它们出
