数据结构(C语言描述)期末试卷.doc

1 专业《数据结构( C 语言描述) 》期末试卷(—学年第学期) 一、填空(10 分)1 、一个 m阶 B- 树中,每个结点最少有() 个儿子结点,m 阶 B+ 树中每个结点( 除根外)最多有() 、 n(n>0) 个结点构成的二叉树, 叶结点最多有())个, 最少有()个。若二叉树有 m 个叶结点,则度为 2 的结点有() 个。 3 、顺序查找方法适用于存储结构为() 的线性表,使用折半查找方法的条件是() 4 、广义表 A=(( ), (a, (b, c)) , d) 的表尾 Gettail(A) 为() 5 、直接插入排序, 起泡排序和快速排序三种方法中,() 所需的平均执行时间最小;() 所需附加空间最大。二、选择(10 分)1 、倒排文件的主要优点是: () A 、便于进行插入和删除 B 、便于进行文件的合并 C 、能大大提高基于非主关键字数据项的查找速度 D 、易于针对主关键字的逆向检索 2 下面程序段的时间复杂性为() y=0; while(n>=(y+1)*(y+1)) { y++; }A、 O(n) B、 O(n 2)C、 O(sqrt(n)) D、 O(1) 3、若从二叉树的任一结点出发到根的路径上所经过的结点序列按其关键字有序, 则该二叉树是()A 、二叉排序树 B 、哈夫曼树 C 、堆 D、 AVL 树 4 、栈和队列都是( ) A 、顺序存储的线性结构 B 、限制存取点的线性结构 C 、链式存储的线性结构 D 、限制存取点的非线性结构 5、用顺序查找方法查找长度为 n 的线性表时, 在等概率情况下的平均查找长度为() A、nB、 n/2 C、(n-1)/2 D、(n+1)/2 三、简答( 30 分) 1、已知一棵二叉树的前序扫描序列和中序扫描序列分别为 ABCDEFGHIJ 和 BCDAFEHJIG , 试给出该二叉树的后序序列并绘出该二叉树对应的森林。题号总分得分院(系) 班级姓名学号……………………………………………装…………………………订………………………线…………………………………………… 2 2、若对序列(7,3,1,8,6,2,4,5) 按从小到大排序, 请写出起泡排序的第一趟结果和堆排序的初始堆。 3、某通讯系统只可能有 A、B、C、D、E、F6 种字符, 其出现的概率分别是 、 、 、 、 、 ,试画出相应的哈夫曼树,并设计哈夫曼编码。 4 、在二叉平衡检索树( AVL 树)的调整中,将最靠近新插入点的不平衡结点调整平衡后, 树中是否还会有不平衡结点?为什么? 5 、指定 Hash 函数 H(k)=3*k mod 11 及线性探测开地址法处理冲突,试在 0~10 的散列空间中对关键字序列( 22 , 41 , 53 , 46 , 30 , 13 , 01 , 67 )