四川大学计算机学院数据结构与算法分析期末试题(2012级A).doc

《四川大学计算机学院数据结构与算法分析期末试题(2012级A).doc》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、四川大学期末考试试题（2013-2014学年第1学期）课程号：课程名称：数据结构与算法分析（A卷）任课教师：适用专业年级：学号：姓名：考试须知四川大学学生参加由学校组织或由学校承办的各级各类考试，必须严格执行《四川大学考试工作管理办法》和《四川大学考场规则》。有考试违纪作弊行为的，一律按照《四川大学学生考试违纪作弊处罚条例》进行处理。四川大学各级各类考试的监考人员，必须严格执行《四川大学考试工作管理办法》、《四川大学考场规则》和《四川大学监考人员职责》。有违反学校有关规定的，严格按照《四川大学教学事故认定及处理

2、办法》进行处理。题号123456789卷面成绩得分201010101010101010阅卷教师阅卷时间一、单项选择题（每小题2分，共20分）1．在一株高度为2的5阶B树中，所含关键字的个数最少是（）。A）5B）7C）8D）142．当求链表的直接后继与求直接前驱的时间复杂度都相同时，此链表应为（　　　）。A）单链表B）双向链表C）单向循环链表D）前面都不正确3．用单链表表示的链式队列的队头在链表的（　　　）位置。A）链头B）链尾C）链中D）任意4．串是（　　　）。A）不少于一个字符的序列B）有限个字符的序列C）不

3、少于一个字母的序列D）任意个字母的序列5．一棵深度为5的满二叉树的结点数为（　　　）。A）16B）15C）32D）316．在如下图所示的AOE网中，关键路径长度为（　　　）。A）16B）13C）10D）97．二叉排序树不具有的特征是（　　　）。A）如左子树不空，则左子树上所有结点的值均小于根结点的值B）如右子树不空，则右子树上所有结点的值均大于根结点的值C）任一结点的左、右子树的深度之差的绝对值<2D）左、右子树也分别为二叉排序树8．归并序的时间复杂度是（　　　）。A）O(1)B）O(n)C）O(n2)D）O(

4、nlogn)9．数据表中有10000个元素，如果仅需求出其中最大的10个元素，则采用（　　　）排序算法最节省时间。A）快速排序B）希尔排序C）堆排序D）直接选择排序10．若X是后序线索二叉树中的叶结点，且X存在左兄弟结点Y，则X的右线索指向的是A）X的双亲结点B）以Y为根的子树的最左下结点C）X的左兄弟结点YD）以Y为根的子树的最右下结点二、（本题10分）有二叉树中序序列为：ABCED；后序序列为：ABEDC；请画出此二叉树。三、（本题10分）给出如下图的所有拓扑有序序列。四、（本题10分）用Kruskal算法

5、分别构造如下所示网络的最小生成树。五、（本题10分）已知哈希表地址空间为0..8，哈希函数为H(key)=key%7，采用线性探测再散列处理冲突，将数据序列{100,20,21,35,3,78,99,45}依次存入此哈希表中，列出插入时的比较次数，并求出在等概率下的平均查找长度。六、（本题10分）已知序列{4,1,7,3,8,2,}，试构造二叉排序树。七、（本题10分）使用堆排序所使用的调整把存放在数组中的10个数据元素45,25,15,80,50,75,60,40,35,70调整成一个小顶堆。要求图示出构造过

6、程。八、（本题10分）一棵非空的有向树中恰有一个顶点入度为0，其他顶点入度为1。但一个恰有一个顶点入度为0、其他顶点入度为1的有向图却不一定是一棵有向树。请举例说明之。九、（本题10分）编写复制一棵二叉树的非递归算法。函数模板声明如下：templatevoidCopyBitree(BinaryTree*fromBtPtr,BinaryTree*&toBtPtr)//操作结果:复制二叉树fromBt到toBt的非递归算法