2、表B、广义表B、都是先进先HlD、没有共同点D、0(m+n)C、双向链表D、稀疏矩阵5、算法必须在执行有穷步骤之后结束，这是算法的oA、正确性B、有穷性C、确定性D、可行性6、某一叉树的前序序列为EACBDGF,中序序列为ABCDEFG,则该一叉树的后序序列为B.BDCFAGEA.BDCAFGEC.EGFACDBD.EGACDFB7、在一个单链表中，HL指向该单链表的头结点，若耍在头结点的后面插入一个由指针p指向的结点，则执行A、HL=p;p->next-HL;B、p->next-HL;HL=p;C、p->next-HL;p-HL;D、p->nex
3、t=HL->next;HL->next=p;8、栈的插入与删除操作在进行。A、栈顶B、栈底C、任意位置D、指定位置9、在有n个结点的哈夫曼树中，其结点总数为。A、不确定B、2nC^2n+lD、2n~l10、判定一个循坏队列QU(最多元素为m0个)为满队列的条件是A、QU->front=^QU->rearB、QU->front!=QU->rearC、QU->front==(QU->rear+l)%m0D、QU->front!=(QU->rear+1)%m011、以下说法错误的是A、一.叉树可以是空集B、一•叉树的任一结点最多有两棵了树C、一叉树不是一
4、种树D、一叉树中任一结点的两棵子树有左右次序Z分12、若止元素1,2,3依次进栈，则出栈次序不可能出现种情况。A、3,2,1B、2,1,3C、3,1,2D、1,3,213、深度为5的一叉树至多有个结点。A、16B、32C、31D、1014、采用邻接表存储的图的宽度优先遍历算法，类似于二叉树的A.先序遍历中序遍历C.后序遍历D.按层次遍历15、在一个图屮，所有顶点的度数之和等于图的边数的倍。A、1/2B、1C、2D、420142011学年第1学期班级学号姓名考试科目数据结构吐因卷共5页密封线学生答题不得超过此线16、有8个顶点的无向连通图最少有条边。
5、A、5B、6C、7D、817、在对n个元素进行冒泡排序的过程中，至少需要趟完成。A、1B>nC>n-1D、n/218、在对n个元素进行直接选择排序的过程中，在第i趟需要从个元素中选择出最小值元素。A、n-i+1B、n-iC、iD、i+119、顺序查找算法适合于存储结构为的线性表。A.散列存储B.顺序存储或链式存储C.压缩存储D.索引存储20、下述几种排序方法屮，要求辅助存储空间最大的是A、插入排序B、选择排序C、快速排序D、归并排序一•、填空题（每空1分，共计15分）1、一棵有n（n>0）个结点的满二叉树共仃个叶子结点和个非终端结点。2、数据的存储
6、结构是数据在计算机存储器里的表示，通常有下列4类，,,索引存储，散列存储。3、假定一棵完全二叉树存储在顺序表a中，贝肿（a+i）元素的人孩子元素为,右孩子元素为。4、在带头结点的单链表中，当删除某一指定结点时，必须找到该结点的结点。5、在一棵二叉树中，度为0的结点个数为n0,度为2的结点个数为n2,则有n0=。6、排序算法中，若数据量非常大，且要求排序稳定，则应选用堆排序还是归并排序更为合适？。7、一组数据{40,46,20,10,56},用堆排序的方法对其从小到大排序，写出初始的大根堆。8、在一个链队列q中封装了队头指针front和队尾指针rea
7、r,若（q->front==q->rear）,则表示该队列为。9、在操作序列push（1）,push（2）,pop（）,push（5）,push（7）,pop0,push（6）之后，栈顶元素是，栈底元素是。10、以一分查找方法查找一个线性表时，此线性表必须是存储的表。三、综合题（共计40分）1、（7分）如图所示为某图的邻接表：（1）（3分）请写出该图的邻接矩阵。（2）（4分）根据如下邻接表，给出从顶点1出发，对邻接表进行深度优先搜索得到的顶点序列。2、（共8分）有一份电文屮共使用5个字符：a、b、c、d、e,它们的出现频率依次为4、7、5、2、9,
8、试以各个字母为叶子结点，以其出现的概率作为结点的权（1）构造哈夫曼树，画出该哈夫曼树。（请按左了树根结点的权小于等于右了树
