五邑大学2014数据结构与算法考题A

--------试卷编号试卷编号命题人： 金旺春 审批人: 试卷分类（A卷或B卷） A五邑大学试卷学期：2012至2013学年度 第一 学期课程：班级：数据结构与算法专业：姓名：学号：题号题号一二总分得分一、得分单项选择题(在每小题的四个备选答案中，选出一个正确答案，并将正确答案的序号填在题干的括号内。每小题2分，共20分) 二叉树的先序序列和后序序列正好相同，则该二叉树一定( )的二叉树A.任一结点无右孩子 B.高度等于其结点数C.任一结点无左孩子 D.空或只有一个结点一个栈的输入序列为1234则下列序列中不可能是栈的输出序列的( )A.23415 B.23145C.54132 D.15432设循环队列中数组的下标范围是0～n-1，其头尾指针分别为f和则其元素个数( )r-f B.r-f+1C.(r-f) modn+1 D.(r-f+n) mod n若某链表最常用的操作是在最后一个结点之后插入一个结点和删除第一个结点，则采用( )存储式最节省时间。单链表 B.单循环链表C.双链表 D.带头结点的双循环链5.在有n个结点的二叉链表中，非空的链域的个数( )A.n-1 B.2n-1C.n+1 D.2n+1对有18个元素的有序表作二分查找，则查找A［3］的比较序列的下标依次( A.1，2，3 B.9，5，2，3C.9，5，3 D.9，4，2，3基于邻接表的DFS算法的时间复杂度( )A.O(n) B.O(n3)C.O(n2) D.O(n+e)8.队列操作的原则是()A.先进先出B.后进先出C.只能进行插入D.只能进行删除有64个结点的完全二叉树的深度( )(根的层次为。8 B.7C.6 D.5下列数据中（ ）是非线性数据结构。栈 B.队列 C.完全二叉树 D.堆二、得分 判断题(判断下列各题，正确的在题后括号内打“√，错的打“×。小题1分，共10分)1.给出不同的输入序列建造二叉排序树，一定得到不同的二叉排序树( )2..队列和栈都是操作受限的线性表( )在对带头结点的链队列作出队操作时，不会改变front指针的值( )若一个栈的输入序列为123…n，其输出序列的第一个元素为n，则其输出序列的每个元素ai一定满ai=n-i+1(i=1,2...,n)( )二叉树中的叶子结点就是二叉树中没有左右子树的结点( )一棵树中的叶子结点数一定等于与其对应的二叉树中的叶子结点数( )有向图用邻接矩阵表示后，顶点i的入度等于邻接矩阵中第i行的非零元素个数( )任何一棵二叉树中至少有一个结点的度为。( )单链表中的首结点就是单链表的第一个结点( )删除二叉排序树中一个结点，再重新插入上去，一定能得到原来的二叉排序树( )三、得分 应用(每小题10分，共50分)125,(10分)33535^给定某顺序字符栈，设有四个字符abcd,求出出栈序列的可能数量。 {a，b，c，d，e}135个字符设计哈夫曼编码。要求：求出所构造的哈夫曼树的WPL01的规则，分别写出与每个字符对应的编码。对于以下二叉树，分别写出各种遍历的结果。50503565545608040ABABCD--------EF GEFG四、得分 算法设计题（每小题10分,共20分）在D:\试卷文件下打开工作空间文件在Bitreelib.h中有两个成员函intCountLeaf(BiNode<T>*bt); //求二叉树叶子数intdepth(BiNode<T>*bt) ; //未完成，