试题(田际平)-1.doc

学院领导审批并签名 AB卷广州大学学年第学期考试卷课程数据结构与算法考试形式(闭卷,考试) 信息学院系专业级班学号: 姓名: 题次一二三四五六总分评卷人分数 2010********** 评分一、填空题:(每格 2 分,共 20分) 1 .任何基于关键字的排序算法,其时间复杂度即使在最坏的情况下也都大于或等于 O(nlog 2n)。 (又称 AVL 树) 的一个典型问题是平衡的二叉排序树(又称二叉查找树),保持二叉排序树的平衡形态可避免在查找等操作中使其退化为单枝树,即避免相应算法的时间性能由 O(log 2n)降低为。 ,也可利用来模拟递归过程使递归算法转换为非递归算法。 G中的所有顶点可排成一个线性序列,使得 G中任一对顶点 u和 v 若满足<u,v>∈ E(G)则 u 在该序列中出现在 v 之前,那么该序列称为图 G的。 (块)大小必为的 k次幂。 。 7 .在哈希表(散列)中填入的记录个数 n ,与哈希表的表长 m 之比称为哈希表的。 (二元运算)序列构成,若某二叉树的中序遍历恰恰反映为这种序列,则表达式的运算符均应为二叉树的结点。 ,但广义表自身应是的结构 ,快速(分划交换)排序和堆排序相对来说是的。二、单项选择题(每题 1 分,共 10分) 1.( )评价算法优劣的基本标准包含 2.()线性表两端各设一个指针,插入元素总在一端指针指示处,而删除元素总在另一端指针的指示处,那么按此操作特点它应该是 3.( )深度为 k(k≥1)的满二叉树,其结点个数为 k - k– k–1–14.()若待排序的序列已基本有序,要使序列完全有序,则从关键字的比较次数和移动次数考虑,应使用的排序方法是 (简单)选择排序 5.( )对记录数 n=5000 的表排序,那么最坏情况下最快且稳定的方法是 6 .( )若带权有向图 G ,已按迪杰斯特拉( Dijkstra )算法求得源点 v到G 中各顶点的最短路径,则下列各最短路径长度的正确求解次序是 A. 60, 30, 50, 10 ,50,10,60 C. 50, 10, 60, 30 D. 10, 30, 50, 60 7.()查找可基于各种方法,由于杂凑是基于的,故它融会了表的构造和查找。 8.( )以下不是.. 键树(数字查找数)特点的是 2的多叉有序树 9.( )满足先根次序遍历序列与中根次序遍历序列相同的是 D.