1.以下与数据的存储结构无关的术语是（c ）C、哈希表2.一个向量第一个元素的存储地址是100，每个元素的长度为2，则第5个元素的地址是（B ）B、1083.假设带头结点的单向循环链表的头指针为head,则该链表为空的判定条件是（C）C、head–>next= =head4.若进栈序列为1，2，3，4，5，6，且进栈和出栈可以穿插进行，则不可能出现的出栈序列是（ D ）D、2，3，5，1，6，45.下列关键字序列中，构成小根堆的是（ A ）A、{12，21，49，33，81，56，69，41}6.下列数据结构中，不属于二叉树的是（ A ）A、B树7.用顺序存储的方法来存储一棵二叉树，存放在一维数组A[1..N]中，若结点A[i]有右孩子，则其右孩子是（ C ）。

C、A[2i+1]8.设树T的高度为4，其中度为1、2、3、4的结点个数分别为4、2、1、1，则T中叶子数为（ D ）D、 89.有数据{53，30，37，12，45，24，96}，从空二叉树开始逐个插入数据来形成二叉排序树，若希望高度最小，则应选择下面哪个序列输入（ B ）B、37，24，12，30，53，45，9610.对下面有向图给出了四种可能的拓扑序列，其中错误的是（ C ）C、5，1，6，3，4，211.m阶B-树中所有非终端（除根之外）结点中的关键字个数必须大于或等于( B )B、[m/2]-112.散列文件也称为( C )B 、索引文件13.数据结构是（D ）D、相互之间存在一种或多种特定关系的数据元素的集合14.从逻辑关系来看，数据元素的直接前驱为0个或1个的数据结构只能是（C ）C、线性结构和树型结构15.设p为指向双向循环链表中某个结点的指针，p所指向的结点的两个链域分别用p→llink和p→rlink表示，则同样表示p指针所指向结点的表达式是（D ）D、p→llink→rlink16.若栈采用顺序存储方式存储，现两栈共享空间V[1..m]，top[i]代表第i个栈( i =1,2)栈顶，栈1的底在v[1]，栈2的底在V[m]，则栈满的条件是（B ）B、 top[1]+1=top[2]17.若一棵二叉树有11个叶子结点，则该二叉树中度为2的结点个数是（A ）A、1018.树的先根序列等同于与该树对应的二叉树的（A ）A、先序序列19.下面关于哈希(Hash，杂凑)查找的说法正确的是( C )C、不存在特别好与坏的哈希函数，要视情况而定20.下列序列中，（ D ）是执行第一趟快速排序后所得的序列。

D、 [68，11，69，23，18] [93，73]21.下列关键字序列中，构成小根堆的是( D )D、 (15，28，46，37，84，58，62，41)22.ISAM文件和VASM文件属于( C )C、索引顺序文件23.下面程序段的时间复杂度为（C ）for (i=0; i<m; i++)for (j=0; j<n; j++)A[i][j]=i*j;C、O(m*n)24.已知指针p和q分别指向某单链表中第一个结点和最后一个结点。

假设指针s指向另一个单链表中某个结点，则在s所指结点之后插入上述链表应执行的语句为（A ）A、q->next=s->next；s->next=p；25.为便于判别有向图中是否存在回路，可借助于（ D ）D、拓扑排序算法26.若以S和X分别表示进栈和退栈操作，则对初始状态为空的栈可以进行的栈操作系列是（ D ）D、SSSXXSXX27.设有一顺序栈S，元素s1,s2,s3,s4,s5,s6依次进栈，如果6个元素出栈的顺序是s2,s3,s4,s6,s5,s1,则栈的容量至少应B、328.假设以数组A[m]存放循环队列的元素。

已知队列的长度为length，指针rear指向队尾元素的下一个存储位置，则队头元素所在的存储位置为（B）。

B、(rear-length+m)%m29.在一个链队列中，front和rear分别为头指针和尾指针，则插入一个结点s的操作为（ D ）。

D、rear->next=s;rear=s;30.对于哈希函数H(key)=key%13,被称为同义词的关键字是（ D ）D、25和5131.采用二叉链表存储的n个结点的二叉树，共有空指针（ A ）个。

A、n+132.连通网的最小生成树是其所有生成树中（ D ）D、边的权值之和最小的生成树33.对记录序列(314，298，508，123，486，145)依次按个位和十位进行两趟基数排序之后所得结果为（ B ）B、508，314，123，145，486，29834.任何一个无向连通图的最小生成树( C )。

C、一棵或多棵35.无向图的邻接矩阵是一个( C )C、对称矩阵36.设无向图G-=(V,E)和G’=(V’,E’),如G’为G的生成树，则下列说法中不正确的是( B )。

B、G’为G 连通分量37.以v1为起始结点对下图进行深度优先遍历，正确的遍历序列是（ D ）D、v1，v2，v5，v6，v7，v3，v438.下面几个符号串编码集合中，不是前缀编码的是（ B ）B、{0,1,00,11}39.希尔排序的增量序列必须是（B ）。

B、递减的40.采用起泡排序法对n个关键字进行升序排序，若要使排序过程中比较关键字的次数最多，则初始时的序列应满足条件（ D ）D、关键字从大到小排列41.在下列内部排序中( A )是不稳定的。

42.分别以下列序列构造二叉排序树，与用其它三个序列所构造的结果不同的是( C )。

A 、（100，80， 90， 60， 120，110，130） 43.在查找过程中，冲突指的是（ C ）。

C 、不同键值对应相同的存储地址 44.对有14个元素的有序表A[1..14]作二分查找，查找元素A[4]时的被比较元素依次为（ D ）。

D 、A[7]，A[3]，A[5]，A[4] 45.以v1为起始结点对下图进行广度度优先遍历，正确的遍历序列是（ A ） A 、 v1，v2，v3，v4，v5，v6，v7二、填空题(本大题共10小题，每小题2分，若有两个空格，每个空格1分，共20分) 1. 数据的物理结构包括 数据元素的存储和数据之间关系的存储。

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

3.下面程序段的时间复杂度是n log 3。

i=1；while (i<=n) i=i*3； 4.循环队列用数组A[0..m-1]存放其元素值，已知其头尾指针分别是front 和rear ，则当前队列的元素个数是 （ rear-front+m ）% m 5. 主要是使插入和删除等操作统一 6. （n-1）/2 。

7. 在单链表中设置头结点的作用是深度优先。

8.线性表L=（a1,a2,…,an ）用数组表示，假定删除表中任一元素的概率相同，则删除一个元素平均需要移动元素的个数是 相同值关键字。

9.已知一无向图G=（V ，E ），其中V={a,b,c,d,e } E={(a,b),(a,d),(a,c),(d,c),(b,e)}现用某一种图遍历方法从顶点a 开始遍历图，得到的序列为abecd ，则采用的是前移遍历方法。

10. 如果排序过程不改变 时间复杂度 之间的相对次序，则称该排序方法是稳定的。

11. 从顺序表中删除一个元素时，表中所有在被删元素之后的元素均需出度一个位置。

12. 当问题的规模n 趋向无穷大时，算法执行时间T(n)的数量级被称为算法的10。

13.若以邻接矩阵表示有向图，则邻接矩阵上第i 行中非零元素的个数即为顶点vi 的sxssxxssxssxxx 。

14.一棵含999个结点的完全二叉树的深度为12。

15.假设S和X分别表示进栈和出栈操作，由输入序列“ABC”得到输出序列“BCA”的操作序列为SSXSXX，则由“a*b+c/d”得到“ab*cd/+”的操作序列为4。

16..如图所示的有向无环图可以排出L->next->next==L17.边种不同的拓扑序列。

18.从空树起，依次插入关键字1l，27，35，48，52，66和73构造所得的二叉排序树，在等概率查找的假设下，查找成功时的平均查找长度为384。

19.带头结点的双循环链表L中只有一个元素结点的条件是队列。

20.求最小生成树的克鲁斯卡尔(Kruskal)算法耗用的时间与图中边稠密、边稀疏的数目正相关。

21.已知一棵完全二叉树中共有768结点，则该树中共有5个叶子结点。

22.实现图的广度优先搜索，除了一个标志数组标志已访问的图的结点外，还需要8、64存放被访问的结点以实现遍历。

23.Prim（普里姆）算法适用于求2h-1的网的最小生成树；kruskal（克鲁斯卡尔）算法适用于求2h-1的网的最小生成树。

24.对长度为20的有序表进行二分查找的判定树的高度为n-1。

25.设一棵完全二叉树有128个结点，则该完全二叉树的深度为n，有_个叶子结点。

26.高度为h的完全二叉树中最少有栈个结点，最多有个结点。

27.设连通图G中有n个顶点e条边，则对应的最小生成树上有3条边。

28.构造n个结点的强连通图，至少有O(n2)条弧。

29.表达式求值是（42,13,94,55,05,46,17）应用的一个典型例子。

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

31.快速排序算法在最差的情况下其时间复杂度是。

32.对序列{55，46，13，05，94，17，42}进行基数排序，第一趟排序后的结果是。

三、应用题（本大题共5小题，每小题6分，共30分）1.已知二叉树的先序遍历序列ABCDEFGH，中序遍历序列为CBEDFAGH，画出二叉树。

答案：二叉树形态AFHGDECB2.如图请给出邻接表、邻接矩阵及逆邻接表。

参考答案如下：（1）邻接表：(注意边表中邻接点域的值是顶点的序号，这里顶点的序号是顶点的下标值-1) vertex firstedge next（2）逆邻接表：（3）V1V3V2V43.由字符集{s ，t ，a ，e ，I}及其在电文中出现的频度构建的哈夫曼树如图所示。

已知某段电文的哈夫曼编码为111000010100，请根据该哈夫曼树进行译码，写出原来的电文。

答案：原来的电文为：eatst4.请画出下图所示的树所对应的二叉树，并写出对应二叉树的先序遍历和中序遍历。

答案：先序遍历为：12345687 中序遍历为：348675211 2 34 5678 1 23456 785.设散列表为HT[13], 散列函数为H (key) = key %13。