四川大学期末考试试题 （2010-2011学年第1学期） 课程号： 课程名称： 数据结构与算法分析（A卷） 适用专业年级： 学号： 姓名： 任课教师： 考试须知 四川大学学生参加由学校组织或由学校承办的各级各类考试，必须严格执行《四川大学考试工作管理办法》和《四川大学考场规则》。有考试违纪作弊行为的，一律按照《四川大学学生考试违纪作弊处罚条例》进行处理。 四川大学各级各类考试的监考人员，必须严格执行《四川大学考试工作管理办法》、《四川大学考场规则》和《四川大学监考人员职责》。有违反学校有关规定的，严格按照《四川大学教学事故认定及处理办法》进行处理。 题 号 得 分 阅卷教师 阅卷时间 1 20 2 10 3 10 4 10 5 10 6 10 7 10 8 10 9 10 卷面成绩 一、单项选择题（每小题 2 分，共20分） 1．数据结构可形式地定义为(D,S)，其中S是D上（ ）的有限集。 A）操作 B）存储映像 C）关系 D）数据元素 2．用链表表示线性表的优点是（ ）。 A）便于随机存取 B）便于插入删除操作 C）占用的存储空间一定比顺序存储少 D）元素的物理顺序与逻辑顺序相同 3．在解决计算机主机与打印机之间速度不匹配问题时通常设置一个打印数据缓冲区，这样主机将要输出的数据依次写入该缓冲区，而打印机则从该缓冲区中取出数据打印。该缓冲区最好采用（ ）结构。 A）栈 B）队列 C）数组 D）线性表 4．串的长度是（ ）。 A）串中不同字母的个数 B）串中不同字符的个数 C）串中所含数字的个数 D）串中所有字符的个数 5．一棵深度为5的满二叉树的结点数为（ ）。 A）16 B）15 C）32 D）31 6．对于下图所示的二叉树，按（ ）遍历得到的序列是4251376。 A）先序 B）中序 C）后序 D）层次 7．采用邻接表存储的图按深度优先搜索方法进行遍历的算法类似于二叉树的（ ）。 A）先序遍历 B）中序遍历 C）后序遍历 D）层次遍历 8．一棵深度为k的平衡二叉树，其每个非终端结点的平衡因子均为0，则该树共有（ ）个结点。 A）2k-1-1 B）2k-1 C）2k-1+1 D）2k-1 9．堆排序的时间复杂度是（ ）。 A）O(1) B）O(n) C）O(n2) D）O(nlogn) 210．快速排序在最坏情况下时间复杂度是O(n)，比（ ）的性能差。 A）归并排序 B）起泡排序 C）选择排序 D）直接插入排序 二、（本题10分） 由带权9、1、3、5、6的五个叶子结点构造哈夫曼树，要求图示出构造过程。 注：试题字迹务必清晰，书写工整。 本题2页，本页为第1页 教务处试题编号： 课程名称：数据结构与算法分析 任课教师： 学号： 姓名： 三、（本题10分） 设某二叉树前序为abdcef，中序为dbaecf，试画出这棵二叉对。 四、（本题10分） 如下图所示的网，用Prim算法从顶点1出发构造出一棵最小生成树，要求图示出每一步的变化情况。 五、（本题10分） 已知一组关键字为（19，14，23，1，68，20，84，27，55，11，10，79），哈希函数：H(key)=key % 13，哈希地址空间为0~12，请构造用链地址法处理冲突的哈希表，并求平均查找长度。 六、（本题10分） 已知序列{4,1,7,1,3,8,2,}，试构造二叉排序树，要求图示出构造过程。 七、（本题10分） 已知序列{32，47，12，8，2，19，30}，试构造堆顶元素最小的初始堆，要求画出构造过程。 八、（本题10分） 给出如下图所示有向图的所有拓扑有序序列。 九、（本题10分） 试写出二叉树中序遍历的非递归算法 本题2页，本页为第2页 教务处试题编号： 本文来源：https://www.wddqw.com/doc/d66990d90408763231126edb6f1aff00bed570a7.html