《09-10-1福建师范大学数据结构试卷d》由会员分享，可在线阅读，更多相关《09-10-1福建师范大学数据结构试卷d（4页珍藏版）》请在金锄头文库上搜索。
1、福建师范大学试卷纸 第 1 页 共 4 页 福建师范大学 数学与计算机科学 学院2009 2010 学年第 1 学期考试 D 卷 考 生 信 息 栏 学院系 专业 年级 姓名 学号 装 订 线专 业： 年 级： 课程名称: 数据结构 任课教师： 试卷类别：开卷（ ）闭卷（） 考试用时： 分钟 考试时间: 年 月 日 午 点 分 题号 一 二 三 四 五 总得分 评卷人 得分 题号 六 七 八 九 十 得分福建师范大学试卷纸 第 2 页 共 4 页 一、选择：(每题 2分，共 30分) 1、若从二叉树的任一结点出发到根的路径上所经过的结点序列按其关键字有序，则该二叉树是( ) A、二叉排序树 B
2、、哈夫曼树 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 2 4、非空循环链表 head 的尾结点 p 满足下列( )条件。 A. head-next=p B. head=p C. p-next=head D. p-next=nil 5、从下列有关树的叙述中,选出正确的叙述（ ） A)二叉树中每个结点有两个子结点,而树无此
3、限制,因此二叉树是树的特殊情况。 B)当K1时高度为K的二叉树至多有2 k-1 个结点。 C)哈夫曼树是带权路径最短的树,路径上权值较大的结点离根较近。 D)在二叉树中插入结点,该二叉树便不再是二叉树。 6、用顺序查找方法查找长度为n的线性表时，在等概率情况下的平均查找长度为（ ） A、n B、n/2 C、(n-1)/2 D、(n+1)/2 7、对一组数据（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 则采用的排序是
4、 ( )。 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. 5 9、已知有向图G=(V,E)，其中V=V 1 ,V 2 ,V 3 ,V 4 ,V 5 ,V 6 ,V 7 ，E=, , , , , , , , ,G的拓扑序列是（ ） 。 A)V 1 ,V 3 ,V 4 ,V 6 ,V 2 ,V 5 ,V 7B)V 1 ,V 3 ,V 2 ,V 6 ,V 4 ,V 5 ,V 7 C)V 1 ,V 3 ,V 4 ,V 5 ,V
5、 2 ,V 6 ,V 7D)V 1 ,V 2 ,V 5 ,V 3 ,V 4 ,V 6 ,V 7 10、有一组数据（15，9，7，8，20，-1，7，4） 用快速排序的划分方法进行一趟划分后数据的 排序为 ( )（按递增序） 。 A)下面的B，C，D都不对。 B)9，7，8，4，-1，7，15，20 C)20，15，8，9，7，-1，4，7 D) 9，4，7，8，7，-1，15，20 11、如果求一个连通图中以某个顶点为根的高度最小的生成树，应采用（ ） A)深度优先搜索算法 B)广度优先搜索算法 C)求最小生成树的prim算法 D)拓扑排序算法 12、从下列有关树的叙述中,选出正确的叙述（ ）
6、 A)二叉树中每个结点有两个子结点,而树无此限制,因此二叉树是树的特殊情况。 B)当K1时高度为K的二叉树至多有2 k-1 个结点。 C)哈夫曼树是带权路径最短的树,路径上权值较大的结点离根较近。福建师范大学试卷纸 第 3 页 共 4 页 考 生 信 息 栏 学院系 专业 年级 姓名 学号 装 订 线 D)在二叉树中插入结点,该二叉树便不再是二叉树。 13、在最好和最坏情况下的时间复杂度均为 O(n*logn)且稳定的排序方法是：（ ） A.快速排序 B.堆排序 C.归并排序 D.基数排序 14、一棵具有 n个结点的完全二叉树的树高度（深度）是（ ） A)logn+1 B)logn+1 C)l
7、ogn D)logn-1 15、下面给出的四种排序法中( )排序法是不稳定性排序法。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
8、、将一棵有 100个结点的完全二叉树从上到下，从左到右依次对结点进行编号， 根结点的编号为 1，则编号为 49的结点的孩子编号为：_ 6、在AOE-网中，设e(i)和l(i)分别表示活动 的最早开始时间和最晚开始时 i a 间，则当且仅当_时， 为关键活动。 i a 7、下面程序段的时间复杂度为_。 （用O估计）FOR i:=1 TO n DOFOR j:=i TO n DOs=s+j; 8、后根遍历树林正好等同于按_ _遍历对应的二叉树。 9、在有序表A1.12中，采用二分查找算法查等于A12的元素，所比较的元 素下标依次为 福建师范大学试卷纸 第 4 页 共 4 页 三、解答题：(每题 6
9、分，共 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 V4 V1| 0 1 4 V2| 0 9 2 V3| 3 5 0 8 V4| 6 0 5、判断下列二叉树是否为二叉搜索树，如果是，是否为AVL树，依次插入 22、4、1，并对此表作相应的调整。30 15 40 10 25 50 20 28 四、算法题：(每题 10分，共 20分) 1、已知某哈希表的装载因子小于1，哈希函数H（key）为关键字（标识符）的第一个字母在字母 表中的序号，处理冲突的方法为线性探测开放定址法，请编写一个按第一个字母的顺序输出哈希 表中所有关键字的算法。 void Print_Hash(HashTable H)/按第一个字母顺序输出 Hash 表中的所有关键字, 2、写出二叉树前根遍历的递归算法。
