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

专业《数据结构( C 语言描述) 》期末试卷(—学年第学期) 一、填空(10 分)1、一个 m阶 B- 树中, 每个结点最少有( ceil(m/2) ) 个儿子结点,m 阶 B+ 树中每个结点( 除根外) 最多有(m) 、 n(n>0) 个结点构成的二叉树,叶结点最多有( floor((n+1)/2) ) 个,最少有(1) 个。若二叉树有 m 个叶结点,则度为 2 的结点有( m-1 ) 个。 3 、顺序查找方法适用于存储结构为( 顺序表和线性链表) 的线性表,使用折半查找方法的条件是( 查找表为顺序存贮的有序表) 4 、广义表 A=(( ), (a, (b, c)) , d) 的表尾 Gettail(A) 为( ((a,(b,c)),d) ) 5 、直接插入排序,起泡排序和快速排序三种方法中, ( 快速排序) 所需的平均执行时间最小; ( 快速排序) 所需附加空间最大。二、选择(10 分)1 、倒排文件的主要优点是: (C) A 、便于进行插入和删除 B 、便于进行文件的合并 C 、能大大提高基于非主关键字数据项的查找速度 D 、易于针对主关键字的逆向检索 2 下面程序段的时间复杂性为(C) y=0; while(n>=(y+1)*(y+1)) { y++; }A、 O(n) B、 O(n 2)C、 O(sqrt(n)) D、 O(1) 3、若从二叉树的任一结点出发到根的路径上所经过的结点序列按其关键字有序, 则该二叉树是(C)A 、二叉排序树 B 、哈夫曼树 C 、堆 D、 AVL 树 4 、栈和队列都是( B) A 、顺序存储的线性结构 B 、限制存取点的线性结构 C 、链式存储的线性结构 D 、限制存取点的非线性结构 5 、用顺序查找方法查找长度为 n 的线性表时,在等概率情况下的平均查找长度为( D) A、nB、 n/2 C、(n-1)/2 D、(n+1)/2 三、简答( 30 分) 1、已知一棵二叉树的前序扫描序列和中序扫描序列分别为 ABCDEFGHIJ 和 BCDAFEHJIG , 试给出该二叉树的后序序列并绘出该二叉树对应的森林。题号总分得分院(系) 班级姓名学号……………………………………………装…………………………订………………………线……………………………………………解: 后序序列为: DCBFJIHGEA 2、若对序列(7,3,1,8,6,2,4,5) 按从小到大排序, 请写出起泡排序的第一趟结果和堆排序的初始堆。解: 冒泡: 31762458 堆: 874562133、某通讯系统只可能有 A、B、C、D、E、F6 种字符, 其出现的概率分别是 、 、 、 、 、 ,试画出相应的哈夫曼树,并设计哈夫曼编码。解: 编码: A:1011 B:0 C:1010 D:110 E:111 F:100 4 、在二叉平衡检索树( AVL 树)的调整中,将最靠近新插入点的不平衡结点调整平衡后, 树中是否还会有不平衡结点?为什么? 解: 不会再有不平衡点。因为插入结点发生不平衡现象后,会改变以“靠近新插入点的不平衡结点”为根的子树(即最小不平横树)的高度加 1, 经过调整后使最小不平衡树的整体高度又恢复到原来的值,所以不会对原平衡树的其他部分造成危害,因此不会再有不平衡点。 5 、指定 Hash 函数 H(k)=3*k mod 11 及线性探测开地址法处理冲突,试在 0~10 的散列空间中对关键字序列( 22 , 41 , 53 , 46 , 30 , 13 , 01 , 67 )构造 Hash 表,并求在等查找概率下查找成功的平均查找长度。解: 插入元素后的分布情况: 0123456789 10 22 41 30 01 53 4613 67 ASL = (1+1+1+1+2+2+2+6)/8= 四、( 10 分)下图是带权的有向图 G 的邻接矩阵表示,请给出: 1 、其邻接表存储结构 2 、按 Floyd 算法求所有顶点对之间最短距离的矩阵变化过程。 V1 V2 V3 V4 V1| 01∞4 V2| ∞092 V3| 3508 V4| ∞∞60 解: Floyd 算法执行过程中矩阵的变化情况为(从左到右): 01∞4∞0923407∞∞60 01 10 3∞0923406∞∞60 01 10 3 12 09234069 10 60 0193 1108234069 10 60 五、( 12 分) 设双链表结点结构为 llink data rlink ,请设计算法将其中 P 所指结点与其 rlink 所指结点位置互换的算法。解: typedef struct DLNode{ ElemType data; struct DLNode *llink,