文档详情

数据结构试题(华南理工大学)数据结构06级试卷A.doc

发布:2018-07-02约3.79千字共9页下载文档
文本预览下载声明
诚信应考,考试作弊将带来严重后果! 华南理工大学期末考试 《 数据结构 》试卷(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. 设散列函数为
显示全部
相似文档