09-10-1福建师范大学数据结构试卷D.docVIP

福建师范大学 数学与计算机科学 学院 2009 2010 学年第 1 学期考试 D 卷考生信息栏学院系 专业 年级姓名 学号装 订 线 专 业： 年 级： 课程名称: 数据结构 任课教师： 试卷类别：开卷（ ）闭卷（） 考试用时： 分钟考试时间: 年 月 日 午 点 分题号一二三四五总得分评卷人得分题号六七八九十得分 一、 选择：(每题2分，共30分)1、若从二叉树的任一结点出发到根的路径上所经过的结点序列按其关键字有序，则该二叉树是( )A、二叉排序树 B、哈夫曼树 C、堆 D、AVL树2、下列排序方法中，哪一个是稳定的排序方法？（ ） A)堆排序 B)二分法插入排序 C)希尔排序 D)快速排序3、一个栈的输入序列为1 2 3 4 5，则下列序列中不可能是栈的输出序列的是（ ）。 A) 2 3 4 1 5 B) 5 4 1 3 2 C) 2 3 1 4 5 D) 1 5 4 3 24、非空循环链表head 的尾结点 p 满足下列( )条件。A. head-next=p B. head=p C. p-next=head D. p-next=nil5、从下列有关树的叙述中,选出正确的叙述（ ）A)二叉树中每个结点有两个子结点,而树无此限制,因此二叉树是树的特殊情况。B)当K1时高度为K的二叉树至多有2k-1个结点。C)哈夫曼树是带权路径最短的树,路径上权值较大的结点离根较近。D)在二叉树中插入结点,该二叉树便不再是二叉树。6、用顺序查找方法查找长度为n的线性表时，在等概率情况下的平均查找长度为（ ）A、n B、n/2 C、(n-1)/2 D、(n+1)/27、对一组数据（84，47，25，15，21）排序，数据的排列次序在排序的过程中的变化为（1） 84 47 25 15 21 （2） 15 47 25 84 21 （3） 15 21 25 84 47 (4） 15 21 25 47 84 则采用的排序是 ( )。 A) 选择 B) 冒泡 C) 快速 D) 插入8、有一个有序表为 1，3，9，12，32，41，45，62，77，88，92，100，用折半查找法，若要找62，要经过( )次比较。A. 3 B. 6 C. 4 D. 59、已知有向图G=(V,E)，其中V=V1,V2,V3,V4,V5,V6,V7，E=, , , , , , , , ,G的拓扑序列是（ ）。A)V1,V3,V4,V6,V2,V5,V7 B)V1,V3,V2,V6,V4,V5,V7C)V1,V3,V4,V5,V2,V6,V7 D)V1,V2,V5,V3,V4,V6,V710、有一组数据（15，9，7，8，20，-1，7，4） 用快速排序的划分方法进行一趟划分后数据的排序为 ( )（按递增序）。 A)下面的B，C，D都不对。 B)9，7，8，4，-1，7，15，20C)20，15，8，9，7，-1，4，7 D) 9，4，7，8，7，-1，15，2011、如果求一个连通图中以某个顶点为根的高度最小的生成树，应采用（）A)深度优先搜索算法B)广度优先搜索算法C)求最小生成树的prim算法D)拓扑排序算法12、从下列有关树的叙述中,选出正确的叙述（ ）A)二叉树中每个结点有两个子结点,而树无此限制,因此二叉树是树的特殊情况。B)当K1时高度为K的二叉树至多有2k-1个结点。C)哈夫曼树是带权路径最短的树,路径上权值较大的结点离根较近。考生信息栏学院系 专业 年级姓名 学号装 订 线D)在二叉树中插入结点,该二叉树便不再是二叉树。13、在最好和最坏情况下的时间复杂度均为O(n*logn)且稳定的排序方法是：（ ）A.快速排序 B.堆排序 C.归并排序 D.基数排序14、一棵具有 n个结点的完全二叉树的树高度（深度）是（ ）A)logn+1 B)logn+1 C)logn D)logn-115、下面给出的四种排序法中( )排序法是不稳定性排序法。 A) 插入 B) 冒泡 C) 二路归并 D) 快速排序二、 填空题：(每空2分，共20分)1、 树中结点的最大层次称为树的_。 2、已知二叉树后序为DGEBFCA，中序为DBGEACF，则前序一定是 3、用一维数组r0. .m-1表示顺序存储的循环队列，设队头和队尾指针分别是front和rear，且队头指针所指的单元闲置，则队满的条件是_，队空的条件是_。4、在顺序表（8,11,15,19,25,26,30,33,42,48,50）中，用二分（折半）法查找关键码值11，需做的关键码比较次数为 5、将一棵有100个结点的完全二叉树从上到下，从左到右依次对结点进行编号，根结点的编号为1，则编号为49的结点的孩子编号为：_6、在AOE-网中，设e(i)和l(i)分别表示活动的最早开始时间和最晚开始时间，则当且仅当_时，为关键活动。7、下面程序段的时间复杂度为_。（用O估计） FOR i:=1 TO n DO FOR j:=i TO n DO s=s+j;8、后根遍历树林正好等同于按_ _遍历对应的二叉树。9、在有序表A1.12中，采用二分查找算法查等于A12的元素，所比较的元素下标依次为 三、 解答题：(每题6分，共30分)1、 在具有n个结点的K（k=2)叉树的K叉链表表示中，有多少个空指针。2、 已知一棵二叉树的前序序列和中序序列分别为abdghcefi和gdhbaecif,请画出该二叉树。3、 若一组记录的关键码为(46,79,56,38,40,84),则利用快速排序的方法,分别写出以第一个记录为基准得到的前三次划分结果。4、下图是带权的有向图G的邻接矩阵表示，请给出：1、其邻接表存储结构2、按Floyd算法求所有顶点对之间最短距离的矩阵变化过程。 V1 V2 V3 V4V1| 0 1 4V2|092V3| 3 5 0 8V4| 6 05、判断下列二叉树是否为二叉搜索树，如果是，是否为AVL树，依次插入22、4、1，并对此表作相应的调整。 30 15 40 10 25 50 20 28 四、 算法题：(每题10分，共20分)1、已知某哈希表的装载因子小于1，哈希函数H（key）为关键字（标识符）的第一个字母在字母表中的序号，处理冲