川大计算机学院数据结构与算法分析期末试题(2007级B)_无答案.docVIP

四川大学 期末考试试题 （2008-2009学年第1学期） 课程号： 课程名称： 数据结构与算法分析（B卷） 任课教师： 适用专业年级： 学号： 姓名： 考试须知 四川大学学生参加由学校组织或由学校承办的各级各类考试，必须严格执行《四川大学考试工作管理办法》和《四川大学考场规则》。有考试违纪作弊行为的，一律按照《四川大学学生考试违纪作弊处罚条例》进行处理。 四川大学各级各类考试的监考人员，必须严格执行《四川大学考试工作管理办法》、《四川大学考场规则》和《四川大学监考人员职责》。有违反学校有关规定的，严格按照《四川大学教学事故认定及处理办法》进行处理。 题 号 1 2 3 4 5 6 7 8 9 卷面成绩 得 分 20 10 10 10 10 10 10 10 10 阅卷教师 阅卷时间 一、单项选择题（每小题 2 分，共20分） 1．数据类型为（ ）。 A）数据项的集合 B）值的集合及定义在其上的一组操作的总称 C）数据元素的集合 D）关键字的集合 2．链表不具有的特点是（　　　）。 A）可随机直接访问任一元素 B）插入删除不需要移动元素 C）不必事先估计元素个数 D）所需空间与线性表长度成正比 3．设一个栈的入栈序列是ABCD，则借助于一个栈所得到的出栈序列不可能是（　　　）。 A）ABCD B）DCBA C）ABCD D）DABC 4．将对称矩阵Anxn压缩存储在一维数组B[m]中，则m的值至少为（　　　）。 A）n(n+1)/2 B）n(n-1)/2 C）n(n+1) D）n2 5．设二叉树中有n2个度为2的结点，n1个度为1的结点，n0个叶子结点，则此二叉树中空指针域个数为（　　　）。 A）n0+n1+n2 B）n2+n1+2n0 C）2n2+n1 D）2n0+n1 6．对于具有n个顶点的强连图，其弧条数的最小值为（　　　）。 A）n+1 B）n C）n-1 D）n-2 7．一棵深度为k的平衡二叉树，其每个非终端结点的平衡因子均为0，则该树共有（　　　）个结点。 A）2k-1-1 B）2k-1 C）2k-1+1 D）2k-1 8．归并排序的时间复杂度是（　　　）。 A）O(1) B）O(n) C）O(n2) D）O(nlogn) 9．每一趟都能选出一个元素放在其最终位置上，并且不稳定的排序算法是（　　　）。 A）冒泡排序 B）简单选择排序 C）希尔排序 D）直接插入排序 10．按照二叉树的定义，具有3个结点的不同形态（相似）的二叉树有（　　　）种。 A）3 B）4 C）5 D）6 二、（本题10分） 利用两个栈S1、S2模拟一个队列（如客户队列）时，如何用栈的运算实现队列的插入、删除运算，请简述算法思想。 三、（本题10分） 已知一棵二叉树的先序序列与中序序列分别如下，试画出此二叉树。 先序序列：ABCDEFGHIJ 中序序列：CBEDAGHFJI 四、（本题10分） 对于权值序列w={7,5,2,4}，试画出它对应的哈夫曼树。 五、（本题10分） 对于下图，用Kruskal算法构造出一棵最小生成树，要求图示出构造过程中每一步的变化情况。 六、（本题10分） 已知序列{4,1,7,1,3,8,2,}，试构造二叉排序树。 七、（本题10分） 已知一组关键字为（19，14，23，1，68，20，84，27，55，11，10，79），哈希函数为H(key)=key MOD 13，哈希地址空间为0~12，请构造用链地址法处理冲突的哈希表，并求平均查找长度。 八、（本题10分） 使用堆排序所使用的调整方法把存放在数组中的10个数据元素45,25,15,80,50,75,60,40,35,70调整成一个堆。 九、（本题10分） 试写出按层次遍历二叉树的算法。 课程名称：数据结构与算法分析 任课教师： 学号： 姓名： 本题2页，本页为第2页 教务处试题编号： 注：试题字迹务必清晰，书写工整。 本题2页，本页为第1页 教务处试题编号：