1．线性链表不具有的特点是（）。A．随机访问B．不必事先估计所需存储空间大小C．插入与删除时不必移动元素D．所需空间与线性表长度成正比2．设一个栈的输入序列为1，2，3，4，则输出序列不可能是()。A．1,2,3,4B．4,3,2,1C．1,3,2,4D．4,1,2,33．下列排序算法中，()排序在每趟结束后不一定能选出一个元素放到其排好序的最终位置上。A．归并B．冒泡C．选择D．堆4．下列序列中，()是执行第一趟快速排序后得到的序列(排序的关键字类型是字符串)。A．[da,ax,eb,de,bb]ff[ha,gc]B．[cd,eb,ax,da]ff[ha,gc,bb]C．[gc,ax,eb,cd,bb]ff[da,ha]D．[ax,bb,cd,da]ff[eb,gc,ha]5．设有一个10阶的对称矩阵A[10][10]，采用压缩存储方式按行将矩阵中下三角部分的元素存入一维数组B[]中，A[0][0]存入B[0]中，则A[8][5]在B[]中（）位置。A．32B．33C．41D．656.下面哪一种图的邻接矩阵肯定是对称矩阵()。A．有向图B．无向图C．AOV网D．AOE网7．具有2008个结点的二叉树，其深度至少为()。A．9B．10C．11D．128.关键路径是边表示活动的网（AOE网）中的()。A．从源点到汇点的最长路径B．从源点到汇点的最短路径C．最长的回路D．最短的回路9．一个广义表为(a,(a,b),d,e,((i,j),k))，则该广义表的长度为()。A．不确定B．8C．5D．610．设循环队列中数组的下标范围是0～n–1，其头尾指针分别为f和r，则其元素个数为()。A．r–fB．r–f+1C．(r–f)modn+1D．(r–f+n)modn1．算法具有的五个重要特性是：有穷性，确定性，_______，输入和输出。2．一组记录的关键字为（45,80,55,40,42,85），则利用堆排序的方法建立的初始堆为____________。3．对如下无向图G，从结点V1出发，写出一个按深度优先遍历图的结点序列：__________________。V1eq\o\ac(○,1)V6V2eq\o\ac(○,2)eq\o\ac(○,5)V8V7V4V3eq\o\ac(○,3)eq\o\ac(○,4)V5第3题图eq\o\ac(○,6)第4题图4．写出右上图中的一个拓扑有序序列____________________。5．对于顺序存储的线性表，访问结点和删除结点的时间复杂度分别为_____________。6．平衡二叉树上所有结点的平衡因子只可能是________________。7．假定对线性表R[1..60]进行分块查找，共分为10块，每块长度等于6。若假定查找索引表和块均用顺序查找的方法，则查找每一个元素的平均查找长度为___________。8．将一棵有100个结点的完全二叉树从根这一层开始，每一层上从左到右依次对结点进行编号，根结点的编号为1，则编号为37的双亲结点编号为_______。9．设有一个字符串s=’science’，其非空子串的数目是________。10．有n个顶点的强连通有向图G至少有________条弧。一棵二叉树的先序序列和中序序列分别如下，先序序列：ABCDEFGHIJ中序序列：CBDEAGIHJF画出该二叉树。（3分）写出其后序序列。（3分）2．给出用Kruskal算法构造下列带权图的最小生成树的过程。V1V23V3154V63V4416V523.已知一个长度为12的表（6，8，4，12，2，10，7，3，9，1，11，5）。（1）将表中的元素依次插入到一个初始为空的二叉排序树中，画出该二叉排序树并求其在等概率下的平均查找长度。（3分）（2）若先对表中的记录排序，构成有序表后再对其进行折半查找，画出判定树并求其在等概率下的平均查找长度。（3分）4．已知哈希表地址空间为0..10，哈希函数为H(key)=keyMOD11，采用链地址法处理冲突，将下面数据序列依次插入该哈希表中，并求出在等概率下查找成功时的平均查找长度。12，24，1，34，38，44，27，22。5．假定用于通信的电文仅由8个字母a，b，c，d，e，d，f，g，h组成，各个字母在电文中出现的频率分别为5，23，3，6，10，11，36，4。要求：（1）以这些频率作为叶子结点的权值构造Huffman树。（2分）（2）试为这8个字母设计不等长Huffman编码。（2分）Abcdefgh（3）计算出电文总长度。（2分）1.有两个不带头结点的单循环链