单项选择题（每小题2分，共14分）1.线性链表不具有的特点是（）。A．随机访问B．不必事先估计所需存储空间大小C．插入与删除时不必移动元素D．所需空间与线性表长度成正比2.若进栈顺序为1234，则可能出现的序列是（）A.3412B.3124C.4123D.43213．在有n个结点的二叉链表中的空链域有（）个。A.nB.n+1C.n-1D.n+24．设有无向图G的顶点个数为n，则该图最多有（）条边。A.n(n+1)/2B.n(n-1)C.n(n-1)/2D.n-15.若第4题的无向图G是连通图，其边的个数至少为（）A.n(n+1)/2B.n(n-1)C.n(n-1)/2D.n-16．含有n各结点的二叉排序树在最坏情况下查找成功时的平均查找长度为（设每个记录的查找概率相等）（）A.nB.(n-1)/2C.(n+1)/2D.n-17．二维数组A[10][20]采用行优先顺序存储，每个元素占1个存储单元，并且初始地址是200，则A[6][12]的地址是（）A.365B.326C.360D.332填空题（每空1分，共18分）8.数据的基本单位是，最小单位。9.算法的的特性有、、、输入、输出。10.当线性表的长度变化不大并且主要操作是查找时，用存储结构较好。11.空格串是指，其长度等于。12.二叉树的第i层上至多有个结点；具有n个结点的完全二叉树的深度为。13.如图，该树的先根遍历序列为，后根遍历序列为。14．一棵有n个顶点的生成树有且仅有条边。15．图的遍历中，设置辅助数组是为了。16．G是一个非连通图，共有28条边，则该图至少有个顶点。17．影响哈希表关键字比较次数的因素有三个：、、。三、判断题（每题2分，共12分）18．队列只允许在表的一端进行插入，而在另一端删除元素。（）19．广义表的表尾可以是原子也可以是列表。（）20．二叉树的中序和后序遍历序列可以唯一确定一棵二叉树。（）21．分块查找比折半查找的查找效率高。（）22．用简单选择排序方法分别对序列S1=（1，2，3，4，5，6，7）和序列S2=（7，5，3，2，4，1，6）进行排序，两者的比较次数不相同。（）23．基数排序是稳定的内部排序方法，它最适用于n值很小而关键字较大的序列。（）四、应用题（共36分）24.画出和下列已知序列对应的二叉树：先序访问序列为ABCDEFGHIJKL,中序访问序列为CBEFDGAJIKLH（4分）25.画出对长度为10的有序表进行折半查找的判定树，并求其等概率时查找成功的平均查找长度。（6分）26.已知某系统在通讯联络中只可能出现5种字符{a,b,c,d,e}，其概率分别为0.10，0.22，0.27，0.15，0.26，试画出赫夫曼树并设计赫夫曼编码。（6分）27.下图为一无向带权图，（1）写出其邻接矩阵和邻接表；（2）按克鲁斯卡尔算法求其最小生成树。（10分）28.给出一组关键字T=（12，2，16，30，8，28，4，10，20）。写出用下列算法从小到大排序时第一趟结束时的序列（写出过程）（10分）（1）希尔排序（第一趟排序的增量为4）（3’）（2）快速排序（选第一个纪录为数轴）(5’)（3）归并排序(2’)五、算法设计题（共20分）29.请根据下列数据结构定义完善简单选择排序的算法，并分析算法在待排序列按关键字正序和逆序情况下的记录的比较和移动次数。（10分）#defineMAXSIZE20typedefintKeytype;//定义关键字类型为整型typedefstruct{KeyTypekey;//关键字项InfoTypeotherinfo;//其他数据项}RedType;//记录类型typedefstruct{RedTyper[MAXSIZE+1];//r[0]闲置或用作哨兵intlength;//顺序表长度}SqList;//顺序表类型voidSelectSort(SqList&L){//对顺序表作简单选择排序}//SelectSort元素的比较次数元素的移动次数为在逆序情况下在正序情况下30.我们可以借助队列对二叉树进行层次遍历，请补充下列算法。（每空2分，10分）typedefstructBiTNode{//二叉链表的定义TElemTypedata;StructBiTNode*lchild,*rchild;}BiTNode,*BiTree;typedefBiTNode*ElemType;typedefstruct{QElemType*base;intfront,rear;}SqQueue;voidLevelOrderTraverse(B