计算机学院数据结构历年试题

1、PAGE PAGE 3华南师范大学试卷（A卷） 考试科目： 数据结构 考试日期：2003.1.16 成绩： 系级班别：2001级本科 学生姓名： 学号： 一、选择题（10分）1.在内排序中,不论待排序记录的初始状态如何，其时间复杂性一样的是( ). A插入排序B二分法插入排序 C快速排序D冒泡排序2.根据n个元素建立一棵二叉排序树，其时间复杂度大致为（ ） A. O(n) B.O(nlogn) C.O(logn) D.O(n2)3设一个具有t个非零元素的m*n大小的稀疏矩阵采用顺序存储结构（即三元组存储结构），其转置矩阵的普通转置算法的时间复杂度为（ ） A.O(m) B.O(n) C.O(n

2、*m) D.O(m*t) E.O(n*t)4. 在堆排序的过程中，需要对n个记录建立初始堆。假设将这n个记录存放于数组 A0.n-1中，则在建立初始堆时，最先进行堆调整的结点的编号是（ ）A.n div 2 B. n div 2 +1 C. n div 2-1 D. (n-1) div 25.下面算法的时间复杂度为（ ） function f ( n:integer):integer;begin if ( n=0) or ( n=1 ) then return 1 else return n*f(n-1);end. A. O(1) B.O(n) C.O(n2) D.O(n!)二、填空题（10分

3、）1.在堆排序的过程中，对n个记录建立初始堆需要进行 次筛选运算，由初始堆到堆排序结束，需要对树根结点进行 次筛选运算。2.假设一个循环队列的元素存放于m1.max+1中，则判断队满的条件为 。3.设A是一个线性表（a0,a1,.an），采用顺序存储结构，则在等概率的前提下，平均没插入一个元素需要移动的元素个数为 ；若元素插入在ai与ai+1之间（0in-1）的概率为(n-i)/(n*(n+1)/2),则平均每插入一个元素所要移动的元素个数是 。4.在散列表的查找算法中，平均查找长度与表的 无关，只与所选取的 、 、 有关。5通过取表头HEAD运算和取表尾TAIL运算从广义表L=(a,b),(

4、),(c,(d)中提取出 c 的表达式是。三、应用解答题（25分）1设有三对角矩阵A（n*n）,将其三条对角线（即三条对角线是指主对角线和与其相邻的上下两条对角线）上的元素逐行地存于数组B1.x中，使得Bk=aij，则: (1)x的值等于多少。 (2)试用i,j表示k的下标变换公式。 (3)若将该三条对角线上的元素存于数组C-1.1,1.n中，使得Cu,v=aij，试用i,j表示u,v下标变换的公式。2.选取哈希函数H(k)= (3k) mod 11。用线性探测开放定址法处理冲突。试在0 10的散列地址空间中对关键字序列（11，19，53，24，30，13，12，56）构造哈希表。并分别求在等

5、概率情况下查找成功和不成功时的平均查找长度。3.在设计电话目录管理系统时，什么样的数据结构最适合？为什么？4.已知树的前序遍历序列为：ABECFGH，后序遍历序列为：EBFGCHA，试问能否构造出唯一的树？如果不可以则请说明原因。如果可以则请把该树的树形画出来。四、算法填空题（15分）1.下面的程序段是输出二叉树的算法：将以二叉链式存储结构存储的二叉树以广义表的形式输出。struct btreenode struct btreenode *lchild; int data; struct btreenode *rchild;void printbtree(struct btreenode *b

6、t)if ( bt!=NULL) / 递归结束条件：二叉树为空则结束递归，不空则做 cout ; if ( ) cout(; /输出左括号 ；if ( ) coutrchild); / 输出右子树cout); /输出右括号 五、算法设计题（40分）1.设计一个递归算法来将二叉树的前序序列中倒数第k个结点输出。假定二叉树用二叉链表表示。要求算法的时间复杂度为O(k)。并说明你的算法达到了这个要求。2.设有单链表HL为： 请写一个时间复杂度为O(n)的算法, 将HL改造为如下所示的单链表. 3.请设计一个递归算法：判别一棵二叉树是否为二叉排序树。要求算法的时间复杂度最佳。4.请设计一个递归算法：判别两个广义表是否