本科题单项选择题（每题2分，共30分）（注意：在本试题上直接答题无效,请将试题答案写在后面的答题纸上。

）1．算法的时间复杂度取决于（）A．问题的规模 B. 待处理数据的初态 C. A和B2. 线性表采用链式地址时，其地址（）A. 必须是连续的B. 一定是不连续的C. 部分地址必须是连续的D. 连续与否均可以3. 链表不具有的特点是（）A．插入、删除不需要移动元素B．可随机访问任一元素C．不必事先估计存储空间D．所需空间与线性长度成正比4．有六个元素6，5，4，3，2，1 的顺序进栈，问下列哪一个不是合法的出栈序列？（）A. 5 4 3 6 1 2B. 4 5 3 1 2 6C. 3 4 6 5 2 1D. 2 3 4 1 5 65. 最大容量为n的循环队列，队尾指针是rear，队头是front，则队空的条件是（）。

A. (rear+1) MOD n=frontB. rear=frontC．rear+1=front D. (rear-l) MOD n=front6. 串是一种特殊的线性表，其特殊性体现在（）A. 可以顺序存储B. 数组元素是一个字符C. 可以连续存储D. 数据元素可以是多个字符7. 设A是n*n的对称矩阵，将A的对角线及对角线上方的元素以列为主的次序存放在一维数组B[1..n(n+1)/2]中，对上述任一元素aij(1≤i，j≤n，且i≤j)在B中的位置为( )。

A. i(i-l)/2+jB. j(j-l)/2+iC. j(j-l)/2+i-1D. i(i-l)/2+j-18. 已知广义表: A=(a,b), B=(A,A), C=(a,(b,A),B), 求下列运算的结果:tail(head(tail(C))) =( )。

A.（a）B. AC. aD. (b)E. bF. (A)9. 已知某二叉树的后序遍历序列是dabec, 中序遍历序列是debac , 它的前序遍历是（）。

A．acbed B．decab C．deabc D．cedba10. 一棵具有n个结点的完全二叉树的树高度（深度）是（）A．⎣logn⎦+1 B．logn+1 C．⎣logn⎦D．logn-111. 哈希查找中k个关键字具有同一哈希值，若用线性探测法将这k个关键字对应的记录存入哈希表中，至少要进行( )次探测。

A．k B. k+1 C. k(k+1)/2 D.1+k(k+1)/212. 要连通具有n个顶点的有向图，至少需要（）条边。

A．n-l B．n C．n+l D．2n13. 用DFS遍历一个无环有向图，并在DFS算法退栈返回时打印相应的顶点，则输出的顶点序列是( )。

A．逆拓扑有序B．拓扑有序C．无序的14. 具有12个关键字的有序表，折半查找的平均查找长度（）A. 3.1B. 4C. 2.5D. 515. 二叉查找树的查找效率与二叉树的树型有关, 在( )时其查找效率最低。

A. 结点太多B. 完全二叉树C. 呈单枝树D. 结点太复杂。

判断题（正确打√，错误打×，每题1分，共10分）（注意：在本试题上直接答题无效,请将试题答案写在后面的答题纸上。

）1．算法的优劣与算法描述语言无关，但与所用计算机有关。

( )2. 顺序存储方式的优点是存储密度大，且插入、删除运算效率高。

( )3. 栈和队列都是限制存取点的线性结构。

（）4. 稀疏矩阵压缩存储后，必会失去随机存取功能。

（）5. 一棵有n个结点的二叉树，从上到下，从左到右用自然数依次给予编号，则编号为i的结点的左儿子的编号为2i(2i< n)，右儿子是2i+1（2i+1<n）。

（）6. 在图G的最小生成树G1中，可能会有某条边的权值超过未选边的权值.（）7．对无序表用二分法查找比顺序查找快（）8. 快速排序总比简单排序快。

（）9. 在查找树（二叉树排序树）中插入一个新结点，总是插入到叶结点下面。

( )10. 在AOE图中，关键路径上某个活动的时间缩短，整个工程的时间也就必定缩短。

（）三、阅读下列程序，说明完成的功能(共10分，每题5分) （注意：在本试题上直接答题无效,请将试题答案写在后面的答题纸上。

）1. void exam1(SeqStack S, int m){ SeqStack T; int i；IniStack(T);while(!Stackempty (S))if ((i=pop(S))!=m) push(T,i);while (!Stackempty(T)){ i=pop（T）; push(S,i); }} //exam1LinkList exam2(LikeList l){ //L是无头结点的的单链表ListNode *P,*Q;if (L && L->next){ Q=L; L=L->next; P=L;while ( P->next ) P=P->next;P->next=Q; Q->next=NULL;}//ifreturn L;}//exam2四、简答题(共22分) （注意：在本试题上直接答题无效,请将试题答案写在后面的答题纸上。

）1. 已知模式串pat=’ADABBADADA’,写出该模式串的next函数值；（4分）2. 试叙述一维数组与有序表的异同。

（3分）3. 将下列树转换成为二叉树（只要求给出转换结果）（4分）4. 给定权值2，3，4，6，8，10，12，构造相应的哈夫曼树，并计算其带权路径长度。

（4分）5. 有一随机数组(25,84,21,46,13,27,68,35,20),现采用某种方法对它们进行排序,其每趟排序结果如下, 则该排序方法是什么排序方法? （3分）初始:25,84,21,46,13,27,68,35,20第一趟:20,13,21,25,46,27,68,35,84第二趟:13,20,21,25,35,27,46,68,84第三趟:13,20,21,25,27,35,46,68,846．已知某图的邻接表存储结构如下图所示：（4分）1). 写出从1号顶点出发的深度优先访问顺序；2). 画出深度优先生成树；五、算法设计题(共28分)1. 编写算法实现对给定的二叉树是否为二叉排序树的判别。

设二叉树以二叉链表存储表示。

（要求写出二叉链表的类型定义）。

（10分）2．设一图G以邻接表作为存储结构，请写出广度优先遍历图G的算法。

（10分）3．请写出直接选择排序的算法，并分析算法的时间复杂度和空间复杂度。

是否稳定的排序？如果是不稳定的，试举出一例。

（8分）专科题一、选择题(每小题2分，共20分)1. 以下四类基本的逻辑结构反映了四类基本的数据组织形式，解释错误的是( )A、集合中任何两个结点之间都有逻辑关系但组织形式松散B、线性结构中结点按逻辑关系依次排列形成一条"锁链"C、树形结构具有分支、层次特性，其形态有点像自然界中的树D、图状结构中的各个结点按逻辑关系互相缠绕，任何两个结点都可以邻接2. 若结点的存储地址与其关键字之间存在某种映射关系，则称这种存储结构为( )A、顺序存储结构B、链式存储结构C、索引存储结构D、散列存储结构3. 在长度为n的顺序表的第i (1≤i≤n+1)个位置上插入一个元素，元素的移动次数为( )A、n-i+1B、n-iC、iD、i-14. 对于只在表的首、尾两端进行插入操作的线性表，宜采用的存储结构为( )A、顺序表B、用头指针表示的单循环链表C、用尾指针表示的单循环链表D、单链表5. 一个栈的入栈序列是a,b,c,d,e，则栈的不可能的输出序列是（）A、e d c b aB、d e c b aC、d c e a bD、a b c d e6. 已知图1如右所示，若从顶点A出发按深度优先搜索进行遍历，则可能得到的顶点序列为（）A、A，B，E，C，D，FB、A，C，F，E，B，DC、A，E，B，C，F，DD、A，E，D，F，C，B7. n个顶点的有向图中含有向边的数目最多为( )A、n-1B、nC、n(n-1)/2D、8. 若一个栈的输入顺序是1，2，…，n，输出序列的第一个元素是n，则第i（1≤i≤n）A、n-iB、n-i-1C、i+1D、n-i+19. 已给图2，（）是该图的正确的拓扑排序序列A、1，2，3，4，5B、1，3，2，4，5C、1，2，4，3，5D、1，2，3，5，410. 为查找某一特定单词在文本中出现的位置，可应用的串运算是( )A、插入B、删除C、串联接D、子串定位图2二、填空题(每小题2分，共30分)存储结构是逻辑结构的__________实现。

若一个算法中的语句频度之和为T(n)=n+4nlogn，则算法的时间复杂度为________。

3. 数组A[1..10,-2..6,2..8]以行优先顺序存储，设基地址为100，每个元素占3个存储单元，则元素A[5,0,7]的存储地址是。

4. 在无向图的邻接矩阵A中，若A[i,j]等于1，则A[j,i]等于________。

对带有头结点的链队列lq，判定队列中只有一个数据元素的条件是___________。

设数组data[0..m]作为循环队列sq的存储空间，front为队头指针，rear为队尾指针，则执行出队操作后其头指针front的值为。

设栈S和队列Q的初始状态为空，元素e1，e2，e3，e4,e5和e6依次通过栈S，一个元素出栈后即进队列Q，若6个元素出队的序列是e3，e5，e4,e6,e2,e1,则栈S的容量至少应该是。

设有顺序栈s[0..m-1]，若栈底设在下标最大的一端，则栈满的条件是（设栈顶指针为top，指向栈顶元素的位置）。

有一个10阶对称矩阵A，采用压缩存储方式，以行序为主序存储，A[1,1]为第一元素，其存储地址为1，每个元素占一个地址空间，则A[7,5]的地址为。

在序列(2,5,8,11,15,16,22,24,27,35,40)中采用折半查找，查找元素11，需进行次元素之间的比较。

深度为h的完全二叉树至少有_________个结点。

在对一组记录（18，6，27，12，52，15，47，29）进行直接插入排序时，当把第6个记录15插入到有序表时，为寻找插入位置需比较次。

在直接插入排序和快速排序中，若初始数据基本有序，则选用_________；在冒泡排序和堆排序中，若要求数据的稳定性，则选用_________。

广义表运算式TAIL(((a,b)，(c,d))) 的运算结果为。

一组记录的关键字为(42,59,36,28,10,84)，则利用快速排序的方法，以第一个记录为基准得到的一次划分结果为。

三．应用题（每小题5分，共35分）设有序列(45，24，53，12，28，90)，请构成一棵二叉排序树，并求其查找成功时的平均查找长度。