数据结构试题(华南理工大学)数据结构06级试卷A.doc
文本预览下载声明
诚信应考,考试作弊将带来严重后果!
华南理工大学期末考试
《 数据结构 》试卷(A)
注意事项:1. 考前请将密封线内各项信息填写清楚;
2. 所有答案请直接答在试卷上;
3.考试形式:闭卷;
4. 本试卷共 7 大题,满分100分, 考试时间120分钟。
题 号 一 二 三 四 五 六 七 总分 得 分 评卷人
单选题(10小题共20分)
1. 数据结构在计算机内存中的表示是指 。
A) 数据的逻辑结构 B) 数据的存储结构
C) 数据元素之间的关系 D) 数据类型
2. 计算机中算法是指解决某一问题的有限运算步骤。它必须具备输入、输出、 。
A) 可行性、可移植性和可扩充性 B) 确定性、有穷性和稳定性
C) 易读性、稳定性和确定性 D) 可行性、有穷性和确定性
3. 链表不具有的特点
A) 所需空间与线性表长度成正比 B) 可随机访问任一个结点
C) 插入删除操作不需要移动元素 D) 不必事先估计存储空间大小
4. 在带头结点*head的单循环链表中,判断表长的条件是
A) head-next!=head B) head-next!=NULL
C) head-next-next!=NULL D) head!=NULL
5. 经过以下的栈运算后,x的值是
InitStack(s);Push(s,a);Push(s,b);Push(s,c);Pop(s,x);GetTop(s,x)
A) a B) b
C) c D) s
6. 判断一个循环队列Q(所用的存储数组[0..QueueSize-1])队列满的条件是
A) Q.rear==(Q.front+1)%QueueSize B) Q.front+1==Q.rear
C) Q.fornt==(Q.rear+1)%QueueSize D) Q.rear+1==Q.front
7. 在高度为h的完全二叉树中,
A) 度为0的结点都在第h层上 B) 第i()层上都是度为2的结点
C) 不存在度为1的结点 D) 第i()层上有个结点
8. 对于广义表((a , b)…13]={ 1,3,9,12,32,41,47,66,77,86,95,99,100 },当用二分查找法查找值为95的结点时,经过 次比较后查找成功。
A) 1 B) 2
C) 4 D) 5
填空题(10小题共20分)
1. 将各函数:按增长率由小到大的顺序排
列:
2. 设n是问题的规模大小,则下面函数的时间复杂度为
void fun(int n)
{ int i=0, s=0;
while ( sn )
{ i++; s=s+i;}
}
3.快速排序法的平均时间复杂度是 。
4. 将转化为递归函数,其递归出口是
,其递归体是
5. 已知模式串=“ababa”,则KMP算法中的next函数值为(填下表):
j 0 1 2 3 4 模式串 a b a b a Next[j] 6. 将一个n阶对称矩阵压缩存储到一维数组B中,则B的元素个数
是 。
7. tail[head[ ((a,(b)),(c,d),e) ] ]=
8. 若以{4,5,6,7,8}作为叶子结点的权值构造哈夫曼树,则其带权路径长度WPL= 。
9. 在对一组记录{50,40,95,20,15,70}进行堆排序时,从初始记录调整生成初始堆后,该堆的记录为{ }。
10. 在一个10阶B-树中,每个非根结点内所含的关键字的数目最多和最少分别是 。
计算题(3小题共18分)
1. 已知二叉树的前序遍历为:ABDFCEG, 中序遍历为:BFDACGE。请画出该二叉树,并写出其后序遍历。
2. 设散列函数为
显示全部