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

注：试题字迹务必清晰，书写工整。本题2页，本页为第1页教务处试题编号：四川大学期末考试试题（2014-2015学年第1学期）课程号：课程名称：数据结构与算法分析（A卷）任课教师：适用专业年级：学号：姓名：考试须知四川大学学生参加由学校组织或由学校承办的各级各类考试，必须严格执行《四川大学考试工作管理办法》和《四川大学考场规则》。有考试违纪作弊行为的，一律按照《四川大学学生考试违纪作弊处罚条例》进行处理。四川大学各级各类考试的监考人员，必须严格执行《四川大学考试工作管理办法》、《四川大学考场规则》和《四川大学监考人员职责》。有违反学校有关规定的，严格按照《四川大学教学事故认定及处理办法》进行处理。题号123456789卷面成绩得分201010101010101010阅卷教师阅卷时间一、单项选择题（每小题2分，共20分）1．在一棵高度为5的2叉树中，所含结点个数最多为（）。A）30B）31C）32D）292．当求链表的直接后继与求直接前驱的时间复杂度都相同时，此链表应为（）。A）单链表B）双向链表C）单向循环链表D）前面都不正确3．队列的工作方式是（）。A）可在队尾删除B）可在队头插入C）先进先出D）先进后出4．若串S=software，其子串数目是（）。A）8B）37C）36D）95．设一棵二叉树中没有度为1的结点，已知叶子结点数为n，此树的结点数为（）。A）2n+2B）2n+1C）2nD）2n-16．对于具有n个顶点的强连有向图，其有向边条数的最小值为（）。A）n+1B）nC）n-1D）n-27．已知某二叉树先序遍历为A，B，D，C，E，则它可能的中序遍历序列为（）。A）B，C，A，D，EB）C，B，A，D，EC）B，E，A，C，DD）B，D，A，E，C8．在折半查找中，第i次查找成功的记录个数最多为（）。A）2iB）2i+1C）2i-1D）2i-19．快速排序执行一遍之后，已经到位的元素个数是（）。A）1B）3C）4nD）2n10．如果只想得到1000个元素组成的序列中第5个最小元素之前的部分排序的序列，用（）方法平均时间最少。A）起泡排序B）简单选择排序C）Shell排序D）堆排序二、（本题10分）一棵非空的有向树中恰有一个顶点入度为0，其他顶点入度为1。但一个恰有一个顶点入度为0、其他顶点入度为1的有向图却不一定是一棵有向树。请举例说明之。三、（本题10分）已知某字符串S中共有8种字符，各种字符分别出现2次、1次、4次、5次、7次、3次、4次和9次，对该课程名称：数据结构与算法分析任课教师：学号：姓名：本题2页，本页为第2页教务处试题编号：字符串用｛0，1｝进行前缀编码，问该字符串的编码至少有多少位？四、（本题10分）用Kruskal算法分别构造如下所示网络的最小生成树。五、（本题10分）已知一组关键字为（19，14，23，1，68，20，84，27，55，11，10，79），哈希函数：H(key)=key%13，哈希地址空间为0~12，请构造用链地址法处理冲突的哈希表，并求平均查找长度。六、（本题10分）含12个结点的平衡二叉树的最大深度（设根结点层次数为1）是多少？七、（本题10分）判别序列（12，70，33，65，24，56，48，92，86，33）是否为堆，如果不是，则将它调整为堆，试给出堆排序方法在平均时间性能、最坏情况下的时间性能和辅助存储量，并与快速排序方法在以上三方面进行比较。八、（本题10分）试分别画出具有3个结点的树和具有3个结点的二叉树的所有不同形态。九、（本题10分）试编写中序遍历二叉树的非递归算法。