数据结构学位考试试题

数据结构课程学位考试试题（参考答案在题后）

判断题：判断下列各小题叙述的正误。对，在题号后的括号内填入“√ ”；错，在题号后填入“ ×”。 1、数据的最小单位是数据项。??????????.( √)

2、多重表文件中主索引为非稠密索引，次索引为稠密索引。???.( √ )

3、通常数据结构在计算机中有四种不同的表示方法分为顺序存储结构、链式存储结构、索引存储、文件存储。???.??.( × )

4、算法具有输入、输出、可行性、稳定性、有穷性五个特性。……………….( × ) 5、数据的基本单位是数据项。??????????.( × ) 6、算法的复杂度分为时间复杂度和效率复杂度。????.( × ) 7、性质相同的数据元素的集合成为数据对象。…………….( √ )

8、所有结点按1对1的邻接关系构成的整体就是集合结构。???.( × ) 9、散列文件不能顺序存取、只能按关键字随机存取。?????.( √ ) 10、数据的基本单位是数据元素。??????????.( √ ) 11、B+树中的K个孩子的结点必有K个关键字。?? ?.( √) 12、B+树中的K个孩子的结点必有K个关键字。???.??.( √ )

13、倒排表的索引项中没有头指针和链表长度项。????.( √ )

14、磁带是顺序存取的外存储设备。……………………………….……….( × ) 15、索引文件只能是磁盘文件。????????????(√ )

16、顺序文件只适宜于顺序存取。………………………..………….( × ) 17、磁带是顺序存取的外存储设备。??????????.??.( × ) 18、线性的数据结构可以顺序存储，也可以链接存储。?????.( √) 19、倒排表的索引项中没有头指针和链表长度项。???????.( √) 20、散列文件不能顺序存取、只能按关键字随机存取。?.??.( √ ) 21、栈和队列都是顺序存取的的线性表，但它们对存取位置的限制不同。（√） 22、循环链表从任何一个结点出发，都能访问到所有结点....... (√ ) 23、单链表从任何一个结点出发，都能访问到所有结点。??.( ×) 24、线性表采用顺序存储表示时，必须占用一片连续的存储单元。(√ ) 25、循环链表从任何一个结点出发，都能访问到所有结点。…….( √ ) 26、设串S的长度为n,则S的子串个数为n(n+1)/2? ?.( × )

27、线性表采用链接存储表示时，必须占用一片连续的存储单元。.( × ) 28、链接表上做删除和插入运算时的平均时间复杂度都是O(n) ?.( ×)

29、线性表中的每个结点最多只有一个前驱和一个后继。………… …….( √ ) 30、顺序表上做删除和插入运算时的平均时间复杂度都是O(n) .( √ )

n

31、具有n个结点的完全二叉树的高度为┖2log2┘+1?????.( ×)

32、在只有度为0和度为2的结点的二叉树中，设度为0的结点有n0个，度为2的结点有n2个，则有n0=n2+1?????.( √ )

33、循环队列判断队列为满的条件是sq->front+1= =sq->rear。??(× )

34、数组是一种复杂的数据结构，数组元素之间的关系既不是线性的也不是树形的。???.( √ )

35、若二叉树中各结点的值均不相同，则由二叉树的前序序列和中序序列，或由其后序序列和中序序列均能惟一地确定一棵二叉树。.... (√ )

36、有n个结点的不同的二叉树有n！棵。………………………….……….( × )

37、一般树和二叉树的结点数目都可以为0。................( √ ) 38、循环队列判断队列为空的条件是sq->front= =sq->rear。??(√ )

39、设有一顺序栈S，元素s1,s2,s3,s4,s5,s6依次进栈，如果6个元素出线的顺序是s2,s3,s4, s6 , s5,s1,则栈的容量至少应该是3。.( √)

40、在只有度为0和度为k的结点的k叉树中，设度为0的结点有n0个， 度为k的结点有nk个，则有n0=nk+1??????.( × )

41、一个连通图的生成树，是含该连通图的全部顶点的一个极小连通子图.( √ )

i-142、在二叉树的第 i 层上至多有2 个结点???.( √ )

43、先根遍历树和先根遍历与该树对应的二叉树，其结果不一样。... (× ) 44、由树转化成二叉树，其根的右子女指针总是空的???.( √ )

45、网络的最小代价生成树是唯一的………………….……….……….( × ) 46、深度优先搜索遍历类似于树的先根遍历，它所用到的数据结构是队列。(×) 47、在一棵二叉树中，假定每个结点只有左子女，没有右子女，对它分别进行中 序遍历和后序遍历，则具有相同的结果。???(√)

48、对于一棵具有n个结点，其高度为h的二叉树，进行任一种次序遍历的时间复杂度为O（n）。………..………….( √ )

49、图的深度优先搜索类似于树的先根次序遍历????.( √)

50、在无向图中定义顶点V i与Vj之间的路径为从V i到达Vj的一个顶点序列（ √ ） 51、设无向连通图的顶点个数为n，则该图最多有n(n-1)/2条边?.( √ ) 52、图的广度优先遍历是树的按中根遍历推广。???(× )

53、设图G=(V,E)，V={1,2,3,4}, E={<1,2>,<1,3>,<2,4>,<3,4>}，从顶点1出 发，对图G进行广度优先搜索的序列有2种... (√ )

54、用邻接表作为有向图G的存储结构。设有n个顶点、e条弧，则拓扑排序的时间复杂度为O(n*e) ????.( × )

55、查找表是由同一类型的数据元素(或记录)构成的集合(√)

56、存储图的邻接矩阵中，邻接矩阵的大小不但与图的顶点个数有关，而且与图的边数也有关………………………….…….…….…….…….……….( √ ) 57、图的深度和广度遍历两种操作的时间复杂度都为O（n*e）。……….( × n)

1(v )58、只有无向图，顶点数n、边数e和度数之间有如下关系：e= ……D(×i)

2i?159、装载因子是散列表的一个重要参数，它反映了散列表的装满程度。（√） 60、闭散列法通常比开散列法时间效率更高。（ × ） 61、进行折半搜索的表必须是顺序存储的有序表。（ √ ）

62、索引顺序查找的过程也是一个“缩小区间”的查找过程(√)

63、设有100个数据元素，采用折半搜索时，最大比较次数为7. (×)

64、在顺序表中进行顺序搜索时，若各元素的搜索概率不等，则各元素应按照搜索概率的降序排列存放，则可得到最小的平均搜索长度。??.( ×)

65、在二叉搜索树中，若各结点的搜索概率不等，使得搜索概率越小的结点离树 根越近，则得到的是最优二叉搜索树。???(√ ) 66、闭散列法通常比开散列法时间效率更高。（×）

67、折半搜索只适用与有序表，包括有序的顺序表和有序的链表。(√ ) 68、起泡选择排序是一种不稳定的排序方法。(×)

69、折半搜索只适用与有序表，包括有序的顺序表和有序的链表。.……….( × ) 70、除留余法选择一个适当的正整数p,以p除健值以所得的余数作为散列地址。（ √ ） 71、选择排序是一种不稳定的排序方法。(√ )

72、直接选择排序是不稳定的，其时间复杂性为）O(1)。???.(×)

?73、快速排序是一种不稳定的排序方法。(√ )

74、对于有n个对象的待排序序列进行归并排序，所需平均时间为O（nlog2n）。（√） 75、直接选择排序是一种不稳定的排序方法。….…….…….…….…….…( √ ) 76、直接插入排序是一种稳定的排序方法。(√ ) 77、归并排序是一种不稳定的排序方法。(× ) 78、选择排序是一种不稳定的排序方法。(√ ) 79、归并排序是一种不稳定的排序方法。(× ) 80、堆排序是一种不稳定的排序方法。(√ )

二、单选题：从选择的答案中选出正确的答案，将其字母编号填入下列叙述中的括号内。 1、以下说法错误的是 （ B ）

A.数据的物理结构是指数据在计算机内实际的存储形式 B.算法和程序没有区别，所以在数据结构中二者是通用的 C.对链表进行插人和删除操作时，不必移动结点 D.双链表中至多只有一个结点的后继指针为空 2、下列有关散列文件的说法中不正确的是(C )

A.散列文件具有随机存放的优点 B.散列文件只能按关键字存取 C.散列文件需要索引区 D.散列文件的记录不需要进行排序

3、有一个算法由3个部分的代码嵌套连接组成，每部分的时间复杂度分别为O（1）、O（n2）、O（ n3 ）,该算法的时间复杂度为(D )

A. O（1）+（ n2 ）+（ n3 ） B. O（n2） C. （ n3 ） D. （ n5 ） 4、下列有关散列文件的说法中不正确的是(C )

A.散列文件具有随机存放的优点 B.散列文件只能按关键字存取 C.散列文件需要索引区 D.散列文件的记录不需要进行排序 5、设单链表中结点的结构为（data ,next）。已知指针q所指结点是指针p所指结事业的直接前驱，若在*q与*p之间插入结点*s，则应执行下列哪一个操作？（ B ）。

A.s->next=p->next;p->next=s B．q->next=s ;s->next=p C.p->next=s->next;s->next=p D.p->next=s ;s->next=q

6、对顺序表上的插入、删除算法的时间复杂性分析来说，通常以（ B ）为标准操作 A.条件判断 B.结点移动 C.算术表达式 D.赋值语句

7、在循环链表中，将头指针改设为尾指针（rear）后，其头结点和尾结点的存储位置分别是 （ B ） A.real和rear->next->next B.rear->next 和real

C.rear->next->next和rear D.rear和rear->next

8、有一个算法由3个部分的线性代码连接组成，每部分的时间复杂度分别为O（1）、O（n2）、O（ n3 ）,该算法的时间复杂度为(C)

A. O（1）+（ n2 ）+（ n3 ） B. O（n2） C. （ n3 ） D. （ n5 ） 9、以下说法错误的是 （ A ）

A.对循环链表来说，从表中任一结点出发都能通过前后操作而扫描整个循环链表 B.对单链表来说，只有从头结点开始才能扫描表中全部结点 C.双链表的特点是找结点的前趋和后继都很容易

D.对双链表来说，结点*P的存储位置既存放在其前趋结点的后继指针域中，也存放在它的后继结点的前趋

指针域中。

10、在串的基本运算中，属于加工型运算的有 （ D ）

A.EQAL(S,T) B.LENGTH(S)

C.CONCAT(S,T) D.REPLACE(S,T,R) 11、线性链表不具有的特点是（A）。

A．随机访问 B．不必事先估计所需存储空间大小 C．插入与删除时不必移动元素 D．所需空间与线性表长度成正比 12、以下说法正确的是（C）

A.在单链表中，任何两个元素的存储位置之间都有固定的联系，因为可以从头结点进行查找任何一个元素

B.在单链表中，要取得某个元素，只要知道该元素的指针即可，因此，单链表是随机存取的存储结构 C.顺序存储结构属于静态结构，链式结构属于动态结构 D.顺序存储方式只能用于存储线性结构

13、线性表是一个具有n个（C）的有限序列。

A．表元素 B．字符 C．数据元素 D．数据项 14、对于顺序表，以下说法错误的是 （ A ）

A.顺序表是用一维数组实现的线性表，数组的下标可以看成是元素的绝对地址 B.顺序表的所有存储结点按相应数据元素间的逻辑关系决定的次序依次排列 C.顺序表的特点是:逻辑结构中相邻的结点在存储结构中仍相邻

D.顺序表的特点是:逻辑上相邻的元素，存储在物理位置也相邻的单元中 15、一个长度为n的顺序表的表尾插入一个新元素的渐进时间复杂度为（C）。

2

A. O(n) B. O(n/2) C. O(1) D. O(n) 16、单链表的一个存储结点包含（ D ）

A.数据域或指针域 B.指针域或链域 C.指针域和链域 D.数据域和链域 17、在串的基本运算中，属于引用型运算的有 （ B ）

A.ASSIGN(S,T) B.INSERT(S1,i,S2) C.DELETE(S,i,j) D.SUBSTR(S,i,j)

18、一个长度为n的顺序表的任一位置插入一个新元素的渐进时间复杂度为（ A ）。

2

A. O(n) B. O(n/2) C. O(1) D. O(n) 19、向顺序栈中压入新元素时，应当（ A ）。

A.先移动栈顶指针，再存入元素 B．先存入元素，再移动栈顶指针

C. 先后次序无关紧要 D．同时进行

20、顺序队列的人队操作应为 ( A )

A.sq.rear=sq.rear+1;sq.data[sq.rear]=x B.sq.data[sq.rear]=x;sq.rear=sq.rear+1

C.sq.rear=(sq.rear+1)% maxsize;sq.data[sq.rear]=x D.sq.data[sqrear]=x;sq.rear=(sq.rear+1)% maxsize 21、头结点的单链表first为空的判定条件是：(B)

A. first == NULL; B. first->next== NULL; C. first->next == first; D. first != NULL; 22、如果以链表作为栈的存储结构，则入栈操作时（A）

A、必须判别栈是否满 B、必须判别栈元素的类型

C、必须判别栈是否空 D、对栈不作任何判别

23、设有一个n?n的对称矩阵A，将其下三角部分按行存放在一个一维数组B中，A[0][0]存放于B[0]中，那么第i行的对角元素A[i][i]存放于B中（ A ）处。

A. (i+3)*i/2 B. (i+1)*i/2 C. (2n-i+1)*i/2 D. (2n-i-1)*i/2

24、一个栈的入栈序列是a,b,c,d,e,则栈的不可能的输出序列是（ A ）

A. d c e a b B.d e c b a C. e d c b a D.a b c d e

25、假定一个链式队列的队头和队尾指针分别为front和rear，则判断队空的条件为( A )。 A. front == rear B. front != NULL C. rear != NULL D. front == NULL

26、当利用大小为n的数组顺序存储一个队列时，该队列的最大长度为（ B ）。 A. n-2 B. n-1 C. n D. n+1 27、循环链表主要优点是 （ D ）

A.不再需要头指针了

B.已知某个结点的位置后，能够容易找到它的直接前趋 C.在进行插入、删除运算时，能更好地保证链表不断开 D.从表中任一结点出发都能扫描到整个链表 28、稀疏矩阵一般采用(C )方法压缩存储。

A.三维数组 B.单链表 C.三元组表 D.散列表 29、链式栈与顺序栈相比，一个比较明显的优点是（B）

A 插入操作更加方便 B 通常不会出现栈满的情况 C 不会出现栈空的情况 D 删除操作更加方便

30、设有一顺序栈S，元素s1,s2,s3,s4,s5,s6依次进栈，如果6个元素出线的顺序是s2,s3,s4,s6,s5,s1,则栈的容量至少应该是（ B ） A.2 B. 3 C. 5 D.6

31、设有50行60列的二维数组A[50][60]，其元素长度为4字节，按行优先顺序存储，基地址为200，则元素A[18][25]的存储地址为（A）。 A．3700 B．4376 C．3900 D．4620

32、设C语言数组DATA[m+1]作为循环队列SQ的存储空间，front 为对头指针rear为对尾指针，则执行出

队操作的语句为（D）

A.front=front+1 B.front=(front+1)%m

C.rear=(rear+1)%m D. .front=(front+1)%(m+1) 33、循环队列的队满条件为 (C)

A.(sq.rear+1) % mazsize ==(sq.front+1) % maxsize; B.(sq.rear+1 % maxsize ==sq.front+1 C.sq.(rear+1) % maxsize ==sq.front D.sq.rear ==sq.front

34、在一棵二叉树的二叉链表中，空指针域数等于非空指针域数加（ A ）。

A. 2 B. 1 C. 0 D. –1 35、具有65个结点的完全二叉树的高度为（B）。（根的层次号为0） A．8 B．7 C．6 D．5

36、对某二叉树进行前序遍历的结果为ABDEFC，中序遍历的结果为DBFEAC，则后序遍历的结果为（ B ）

A．DBFEAC B．DFEBCA

C．BDFECA D．BDEFAC 37、循环队列的出队操作为 (A )

A.sq.front=(sq.ftont+1)% maxsize B.sq.front=sq.front+1

C.sq.rear=(sq.rear+)% maxsize D.sq.rear=sq.rear+1 38、设F是一个森林，B是由F转换得到的二叉树，F中有n个非叶结点，则B中右指针域为空的结点有（ C ）个。

A．n-1 B．n C．n+1 D．n+2

39、设二叉树结点的先根序列、中根序列和后根序列中，所有叶子结点的先后顺序( B )

A.都不相同 B.完全相同 C.先序和中序相同，而与后序不同 D.中序和后序相同，而与先序不同

40、对于顺序存储的队列，存储空间大小为n，头指针为F，尾指针为R。若在逻辑上看一个环，则队列中元素的个数为 (B )

A.R-F B. (n+R-F)mod n C.(R-F+1)mod n D. n+R-F 41、以下说法错误的是 (A )

A.树形结构的特点是一个结点可以有多个直接前趋 B.线性结构中的一个结点至多只有一个直接后继 C.树形结构可以表达(组织)更复杂的数据 D.树(及一切树形结构)是一种\分支层次\结构 42、以下说法错误的是(B ) 。

A.二叉树可以是空集

B.二叉树的任一结点都有两棵子树 C.二叉树与树具有相同的树形结构 D.二叉树中任一结点的两棵子树有次序之分

43、在一棵具有n个结点的二叉树中，所有结点的空子树个数等于（ C ） A．n B．n-1 C．n+1 D．2*n 44、下列说法中正确的是（ A ）。 A.一棵二叉树的度可以小于2 B.二叉树中任何一个结点的度都为2 C.二叉树的度为2 D.任何一棵二叉树中至少有一个结点的度为2 45、在一棵具有5层的满二叉树中结点数为（ A ） A 31 B 32 C 33 D 16

46、一个二叉树按顺序方式存储在一个维数组中，如图

0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 A B C D E F G H I J 则结点E在二叉树的第（ C ）层。 A.1 B.2 C.3 D.4

47、在图的邻接表存储结构上执行广度优先搜索遍历类似于二叉树上的（D） A.先根遍历 B.中根遍历 C.后根遍历 D.按层次遍历

48、任何一棵二叉树的叶结点在其先根、中根、后跟遍历序列中的相对位置 (C ) A.肯定发生变化 B.有时发生变化 C.肯定不发生变化 D.无法确定

49、在一棵高度为h(假定树根结点的层号为0)的完全二叉树中，所含结点个数不小于( B )。

h+1h-1hh

A. 2 B. 2 C. 2-1 D. 2

50、树若用双亲链表表示，则(A) A.可容易地实现求双亲及子孙的运算 B.求双亲及子孙的运算均较困难

C.可容易地实现求双亲运算，但求子孙运算较困难 D.可容易地实现求子孙运算，但求双亲运算较困难 51、任何一个带权的无向连通图的最小生成树（B）

A.只有一棵 B.有一棵或多棵 C.一定有多棵 D.可能不存在

52、设有向图有n个顶点和e条边，采用领接表作为其存储表示，在进行拓扑排序时，总的计算时间为（ B ）。

A．O（nlog2e） B．O（n+e） C．O(ne) D．O(n2) 53、以下说法正确的是 （ A ）

A.连通图的生成树，是该连通图的一个极小连通子图。

B.无向图的邻接矩阵是对称的，有向图的邻接矩阵一定是不对称的。 C.任何一个有向图，其全部顶点可以排成一个拓扑序列。 D.有回路的图不能进行拓扑排序。 54、以下说法错误的是 ( D )

A.一般在哈夫曼树中，权值越大的叶子离根结点越近 B.哈夫曼树中没有度数为1的分支结点

C.若初始森林中共有n裸二叉树，最终求得的哈夫曼树共有2n-1个结点

D.若初始森林中共有n裸二叉树，进行2n-1次合并后才能剩下一棵最终的哈夫曼树 55、如果从无向图的任一顶点出发进行一次深度优先搜索即可访问所有顶点，则

该图一定是( B )

A.完全图 B.连通图 C.有回路 D.一棵树

56、将一棵有50个结点的完全二叉树按层编号，则对编号为25的结点x，该结点(B ) A.无左、右孩子 B.有左孩子，无右孩子 C.有右孩子，无左孩子 D.有左、右孩子

57、深度为6的二叉树最多有(B )个结点 A.64 B.63 C.32 D.31

58、一个有序顺表有255个对象，采用顺序搜索法查表，搜索长度为（ A ）。 A、128 B、127 C、126 D、255

59、在有向图中每个顶点的度等于该顶点的（ C ）。

A. 入度 B. 出度

C. 入度与出度之和 D. 入度与出度之差

60、具有n个顶点的有向无环图最多可包含( D )条有向边。 A．n-1 B．n C．n(n-1)/2 D．n(n-1)

61、用邻接表作为有向图G的存储结构。设有n个顶点、e条弧，则拓扑排序的时间复杂度为(B ) A. O(n) B. O(n+e) C. O(e) D. O(n*e)

62、一个有序顺表有255个对象，采用顺序搜索法查表，搜索长度为（A）。 A、128 B、127 C、126 D、255

63、在有向图中，所有顶点的入度之和是所有顶点出度之和的（B）倍。 A.0.5 B. 1 C. 2 D.4 64、以下说法错误的是（B）

A.用相邻矩阵法存储一个图时，在不考虑压缩存储的情况下，所占用的存储空间大小只与图中结点个数有关，而与图的边数无关。

B.邻接表法只能用于有向图的存储，而相邻矩阵法对于有向图和无向图的存储都适用。

C.存储无向图的相邻矩阵是对称的，因此只要存储相邻矩阵的下（或上）三角部分就可以了

D.用相邻矩阵A表示图，判定任意两个结点Vi和Vj之间是否有长度为m的路径相连，则只要检查A的第 i行第j列的元素是否为0即可。

65、在图的邻接表存储结构上执行深度优先搜索遍历类似于二叉树上的（ A ） A.先根遍历 B. 中根遍历 C. 后根遍历 D按层次遍历 66、在一个无向图中，所有顶点的度数之和等于所有边数的（ B ）倍。 A．3 B．2 C．1 D．1/2

67、在无向图中，所有顶点的度数之和是所有边数的（ C ）倍。 A.0.5 B.1 C.2 D.4

68、设有6个结点的无向图，该图至少应有（B）条边能确保是一个连通图。 A. 5 B. 6 C. 7 D. 8 69、以下说法正确的是（ D ）

A.连通分量是无向图中的极小连通子图。 B.强连通分量是有向图中的极大强连通子图。

C.在一个有向图的拓扑序列中，若顶点a在顶点b之前，则图中必有一条弧。 D.对有向图G,如果从任意顶点出发进行一次深度优先或广度优先搜索能访问到每个顶点，则该图一定是完全图。

70、对有14个数据元素的有序表R[14]进行折半搜索，搜索到R[3]的关键码等于给定值，此时元素比较顺序依次为（ C ）。

A．R[0]，R[1]，R[2]，R[3] B．R[0]，R[13]，R[2]，R[3] C．R[6]，R[2]，R[4]，R[3] D．R[6]，R[4]，R[2]，R[3]

71、设有序表的关键字序列为{1，4，6，10，18，35，42，53，67，71，78，84，92，99}，当用二分查找法查找健值为99的结点时，经（ C ）次比较后查找成功。 A.2 B. 3 C.4 C. 12

72、设有100个数据元素，采用折半搜索时，最大比较次数为（B） A 6 B 7 C 8 D 10

73、对长度为n的有序单链表，若搜索每个元素的概率相等，则顺序搜索到表中任一元素的平均搜索长度为（ B）

A．n/2 B．(n+1)/2 C．(n –1)/2 D．n/4

74、对采用二分查找法进行查找运算的查找表，要求按（C）方式进行存储。 A顺序存储 B 链式存储

C顺序存储且结点按关键字有序 D 链式存储且结点按关键字有序 75、二分查找法适用于存储结构为（A）的，且按关键字排序的线性表 A.顺序存储 B. 链接存储 C. 顺序存储或链接存储 D.索引存储

76、在一个长度为n的顺序表的任一位置插入一个新元素的渐进时间复杂度为（B ） A. O(n) B. O(n/2) C. O(1) D. O(n2)

77、在对查找表的查找过程中，若被查找的数据元素不存在，则把该数据元素插入到集合中。这种方式主要适合于(C )

A.静态查找表 B.动态查找表 C.静态查找表与动态查找表 D.两种表都不适合

78、在一个长度为n的顺序表的表尾插入一个新元素的渐进时间复杂度为（ B ）

2

A．O (n) B．O (1) C．O (n) D．O (log2 n)

79、设有序表的关键字序列为{1，4，6，10，18，35，42，53，67，71，78，84，92，99}，当用二分查找法查找健值为84的结点时，经（ C ）次比较后查找成功。 A2 B 3 C 4 D 12

80、静态查找表与动态查找表两者的根本差别在于（ C ）

A逻辑结构不同 B 存储实现不同

C施加的操作不同 D 数据元素的类型不同

2

81、以下时间复杂性不是O(n)的排序方法是 （ B ） A.直接插入排序 B.二路归并排序 C.冒泡排序 D.直接选择排序

82、一个对象序列的排序码为{46，79，56，38，40，84}，采用快速排序以位于最左位置的对象为基准而得到的第一次划分结果为（ C）。

A．{38，46，79，56，40，84} B．{38，79，56，46，40，84} C．{40，38，46，56，79，84} D．{38，46，56，79，40，84} 83、用顺序查找法对具有n个结点的线性表查找的时间复杂性量级为（C） A.O（n2） B. O(nlog2n) C. O（n） D O(log2n)

84、用某种排序方法对序列（25，84，21，47，15，27，68，35，20）进行排序，记录序列的变化情况如下：

25 84 21 47 15 27 68 35 20 15 20 21 25 47 27 68 35 84 15 20 21 25 35 27 47 68 84 15 20 21 25 27 35 47 68 84 则采取的排序方法是 （ C ）

A.直接选择排序 B.冒泡排序 C.快速排序 D.二路归并排序

85、一个对象序列的排序码为{46，79，56，38，40，84}，采用快速排序以位于最左位置的对象为基准而得到的第一次划分结果为（ C ）。

A．{38，46，79，56，40，84} B．{38，79，56，46，40，84} C．{40，38，46，56，79，84} D．{38，46，56，79，40，84} 86、顺序查找法适合于（ D ）存储结构的查找表。

A.压缩 B. 散列 C.索引 D.顺序或链式 87、以下说法错误的是 （C ）

A.直接插入排序的空间复杂度为O(1)。 B.快速排序附加存储开销为O(log2n)。 C.堆排序的空间复杂度为O(n)。

D.二路归并排序的空间复杂度为O(n),需要附加两倍的存储开销。 88、对于大文件的排序要研究在外设上的排序技术，即（ C）

A.快速排序法 B. 内排序法 C.外排序法 D.交叉排序法

89、对于长度为9的有序顺序表，若采用折半搜索，在等概率情况下搜索成功的平均搜索长度为（ C ）的值除以9。

A. 20 B. 18 C. 25 D. 22

90、具有24个记录的序列，采用冒泡排序至少的比较次数是 （ B ） A.1 B.23 C. 24 D. 529

91、当初始序列已按健值有序时，用直接插入算法进行排序，需要比较的次数为（ A） A.n-1 B.log2n C. 2log2n D.n2

92、排序的目的是为了以后对已排序的数据元数进行（D）操作。 A.打印输出 B.分类 C. 合并 D.查找 93、以下稳定的排序方法是 （ B）

A.快速排序 B.冒泡排序 C.直接选择排序 D. 堆排序 94、（ B ）方法是从未排序序列中依次取出元素与已排序序列中的元素作比较，将其放入已排序序列的正确位置上。

A.归并排序 B. 插入排序 C.快速排序 D.选择排序

95、在文件局部有序或文件长度较小的情况下，最佳的排序方法是 （A） A.直接插入排序 B. 冒泡排序 C. 直接选择排序 D.归并排序

96、如果只想得到1024个元素组成的序列中的前5个最小元素，那么用（ C ）方法最快。 A．起泡排序 B．快速排序 C．堆排序 D．直接选择排序

97、对一个由n个整数组成的序列，借助排序过程找出其中的最大值，希望比较次数和移动次数最少，应选用（ C ）方法。

A.归并排序 B.直接插入排序 C.直接选择排序 D.快速排序

98、对待排序的元素序列进行划分，将其分为左、右两个子序列，再对两个子序列施加同样的排序操作，直到子序列为空或只剩一个元素为止。这样的排序方法是（ C ） A 直接选择排序 B 直接插入排序 C 快速排序 D 起泡排序 99、以下不稳定的排序方法是 （ C ）

A.直接插入排序 B.冒泡排序 C.直接选择排序 D.二路归并排

100、在一个长度为n的顺序表的任一位置插入一个新元素的渐进时间复杂度为（B ） A. O(n) B. O(n/2) C. O(1) D. O(n2)

三、填空题

1、有一个算法由3个部分的线性代码连接组成，每部分的时间复杂度分别为O（n）、O（n2）、O（ n4 ）,该算法的时间复杂度为(O（ n4 ）)。

2、数据的基本单位是(数据元素) 。

3、计算机中的算法指的是解决某一问题的有限运算序列，它必须具备输入、输出、可行性、(确定性)和(有穷性)等5个特征

4、所有结点按1对1的邻接关系构成的整体就是(线性) 结构 5、数据元素之间的关联方式或称“邻接关系”称为(逻辑)关系。

6、有一个算法由3个部分的代码嵌套连接组成，每部分的时间复杂度分别为O（n）、O（n2）、O（ n4 ）,该算法的时间复杂度为( O（ n7 ） )。

7、数据元素之间逻辑关系的整体称为(逻辑结构) 。

8、对一个算法要作出全面的分析可分成两用人才个阶段进行，即事先分析和(事后测试)。 9、算法的复杂度分为(时间复杂度) 和(空间复杂度) 两种。

10、数据在计算机中的存储表示（机内表示）称为数据的( 存储结构 )。 11、文件的检索有顺序存取、直接存取和( 按关键字存取)三种方式。 12、文件的检索有顺序存取、直接存取和(按关键字存取)三种方式。 13、在顺序表中插入或删除一个元素，需要平均移动((n+1)/2 )元素，具体移动的元素个数与( ) 有关。

14、VSAM文件结构由三部分组成：索引集、(顺序集)和数据集。

15、ISAM文件是由多级主索引、柱面索引、磁道索引和(主文件索引)组成。

16、已知：s1=〃I’m a teacher〃，s2=〃teacher〃，s3=〃student〃，则REPLACE(s1,s2, s3) 等于(I’m a teacher )。

17、如果文件中的每个记录都有一个索引项，则这样的索引称为(稠密索引) 。 18、如果文件中多个记录只有一个索引项，则这样的索引称为(非稠密索引)。

19、在双链表中，每个结点有两个指针域，一个指向(前驱)， 另一个指向(后继)。

20、当且仅当两个串的(长度)相等并且各个对应位置上的字符都相同时，这两个串相等。一个串中任意个

连续字符组成的序列称为该串的( 子串 )串。

21、VSAM文件结构由三部分组成：索引集、(顺序集)和数据集。

22、串的顺序存储有两种方法：一种是每个单元只存一个字符，称为(非紧缩格式)格式，另一种是每个单元存放多个字符，称为(紧缩格式)格式。

23、线性表的常见链式存储结构有单链表、(双向链表)和(循环链表)。

24、线性表典型的基本运算包括初始化、(插入)、(删除)、查找定位、求长度、存取等六种。 25、已知：s1=〃I’m a teacher〃，s2=〃teacher〃，s3=〃student〃，则SUBSTR(s1,7,7)等于(student)。 26、已知：s1=〃I’m a teacher〃，s2=〃teacher〃，s3=〃student〃，则DELETE(s1,4,10) 等于( I’m )。

27、已知：s1=〃I’m a teacher〃，s2=〃teacher〃，s3=〃student〃，则EQUAL(s1,s2)等于(0 ) 。 28、顺序表中逻辑上相邻的元素的物理位置(必须)紧邻。单链表中逻辑上相邻的元素的物理位置(不需要)紧邻。

29、四维数组是一种非线性结构，其中的每一个数组元素最多有(4)个直 接前驱（或直接后继）

30、一般地，栈和线性表类似有两种实现方法，即( 顺序 )实现和( 链接 )实现。 31、含零个字符的串称为( 空串)串，用(Ф)表示。

32、栈是一种限定在表的一端进行插入和删除的线性表，又被称为(后进先出)线性表。 33、在栈的顺序实现中，设栈顶指针为top，栈空的条件为(top=0)。

34、若已知一个栈的入栈序列是1，2，3，4，?，n ，其输出序列是P1，P2，P3，?，Pn，若P1=n，则Pi为(n-i+1 )。

35、对于顺序存储的栈，因为栈的空间是有限的，在进行(后进)运算时，可能发生栈的上溢，在进行(先出)运算时，可能发生栈的下溢。

36、(栈)可以作为实现递归函数调用的一种数据结构。

37、对任何二叉树，若度为2的节点数为n2，则叶子数n0=( n2+1 )。 38、队列中允许进行删除的一端称为(对头)。

39、一般地，一个n维数组可视为其数据元素为( n )维数组的线性表。数组通常只有(删除)和(插入)两种基本运算。

40、二叉树有不同的链式存储结构，其中最常用的是(二叉链表 )与(三叉链表 )。 41、以下运算实现在顺序栈上的进栈，请在( )处用适当的语句予以填充。

Int Push(SqStackTp *sq,DataType x)

{ if(sp->top==sqstack_maxsize-1}{error(“栈满”);return(0);} else{( sq->top++):

(sq->data[sq->top])=x;

return(1);}

}

42、深度为90的满二叉树上，第11层有(210)个结点。

43、已知一棵度为3的树有2个度为1的结点，3个度过为2的结点，1个度为3 的结点，则该树中有(6)个叶子结点。

44、深度优先搜索遍历类似于树的(先根)遍历，它所用到的数据结构是(栈)。 45、具有n个结点的完全二叉树的深度为([log2n]＋1 )。

46、(树 )中结点的最大度数允许大于2，而( 二叉树 )中结点的最大度数不允许大于2

47、一棵树按照左子女-右兄弟表示法转换成对应的二叉树，则该二叉树中树根结点肯定没有(右)子女。

k48、深度为k(k>=1)的二叉树至多有(2-1 )个结点。

49、有m个叶子结点的哈夫曼树，其结点总数为( 2m-1 )。

50、在一棵树中，( 根)结点没有前驱结点。

51、对无向图，其邻接矩阵是一个关于(对角线)对称的矩阵。

52、n (n﹥0) 个顶点的有向连通图最多有(n(n-1) )条边，最少有(n-1)条边 53、设无向连通图G的顶点数为n，则G最少有(n-1 )条边。

54、遍历图的基本方法有(深度)优先搜索和( 广度 )优先搜索两种。

55、在集合这种逻辑结构中，任何结点之间都不存在( 逻辑 )关系，这是集合这种逻辑结构的基本特点。 56、一个有向图G中若有弧,、和,则在图G的拓扑序列中，顶点Vi、Vj和Vk的相对位置为(省略)。

57、广度优先搜索遍历类似于树的(层次)遍历，它所用到的数据结构是(队列)。 58、由( 树)转换成二叉树时，其根结点的右子树总是空的。 59、设图G=(V,E)，V={1,2,3,4}, E={<1,2>,<1,3>,<2,4>,<3,4>}，从顶点1出发，对图G进行广度优先搜索的序列有种( 2 )。

60、任何连通图的连通分量只有一个，即(本身)。 61、向一棵二叉搜索树中插入一个元素时，若元素的值小于根结点的值，则应把它插入到根结点的(左子树)上。

62、对有序表(25，30，32，38，47，54，62，68，90，95)用二分查找法查找32，则所需的比较次数为( 3 )。 63、静态查找表包括(建表)、(查找)、(读元素)三种基本运算。

64、动态查找表包括建表、查找、读元素、( 插入)、( 删除 )五种基本运算。

65、根据一组记录（56，42，50，64，48）依次插入结点生成一棵AVL树（高度平衡的二叉搜索树）时，当插入到值为(50)的结点时需要进行旋转调整。

66、平衡二叉排序树上任一结点的平衡因子只可能是(0)、(1)或(-1)。

67、在二叉排序树上插入新结点时，不必移动其它结点，仅需使某结点的指针域由(空)变为(指向该结点)即可。

68、在一棵AVL树（高度平衡的二叉搜索树）中，每个结点的左子树高度与右子 树高度之差的绝对值不超过( 1 )。

69、在具有24个元素的有序表上进行二分查找，则比较一次查找成功的结点数为( 1 )。 70、快速排序是不稳定的，其时间复杂性为( O（nlog2n） ) 71、直接选择排序是不稳定的，其时间复杂性为(O（n2) )。 72、按排序过程中依据的不同原则对内部排序方法进行分类，主要有：插入排序、(选择排序)、(交换排序)、归并排序等四类

73、归并排序的空间复杂度为(O(1))。

74、二叉排序树是一种特殊的、增加了限制条件的二叉树，其限制条件是任一结点的键值(大 )于其左孩子（及其子孙）的键值且(小)于其右孩子（及其子孙）的键值。 75、归并排序的时间复杂度是(O（nlog2n）)。

2

76、简单排序的时间复杂性为( O（n) )，空间复杂度为( O(1) )。

i-1

77、二叉树第i（i>=1）层至多有(2 )个节点。

2

78、直接插入排序是稳定的，它的时间复杂性为(O（n))，空间复杂度为(O（1))。 79、归并排序要求待排序列由若干个(有序)的子序列组成。

80、按照排序过程涉及的存储设备的不同，排序可分为(内)排序和（外)排序。

四、计算题

1、设二维数组A8*9的每个元素占4个字节，已知Loc（a00）=1000，A共占多少个字节？A的终端结点a78的起始地址为多少？按行和按列优先存储时，a45的起始地址分别为多少？ 答案： （(1）288；（2）1284；（3）行：1164 列：1176)

2、设二维数组A8*9的每个元素占4个字节，行下标i的范围从1到8， 列下标j的范围从0到8已知Loc（a10）=1000，A共占多少个字节？ A的终端结点a78的起始地址为多少？按行和按列优先存储时，a65的起 始地址分别为多少？

答案：（1）288；（2）1284；（3）行：1200 列：1180

3、设二维数组A8*9的每个元素占5个字节，行下标i的范围从0到7，列下标j的范围从1到9已知Loc（a01）=2000，A共占多少个字节？A的终端结点a78的起始地址为多少？按行和按列优先存储时，a45的起始地址分别为多少？

答案：（1）360；（2）2355；（3）行：2200 列：2185

4、设二维数组A11*9的每个元素占7个字节，行下标i的范围从0到10，

列下标j的范围从1到9已知Loc（a01）=2500，A共占多少个字节？A的终端结点a109的起始地址为多少？按行和按列优先存储时，a75的起始地址分别为多少？ 答案：（1）693；（2）3186；（3）行：2969 列：2857

5、设二维数组A7*9的每个元素占4个字节，已知Loc（a11）=2000，A共占多少个字节？A的终端结点a68的起始地址为多少？按行和按列优先存储时，a55的起始地址分别为多少？

答案：（1）252；（2）2208；（3）行：2160 列：2128

6、设二维数组A8*9的每个元素占8个字节，已知Loc（a00）=2000，A 共占多少个字节？A的终端结点a78的起始地址为多少？ 答案：（1）576；（2）2568

7、设有一个10阶的对称矩阵A[10][10]，采用压缩存储方式按行将矩阵

中下三角部分的元素存入一维数组B[ ]中，A[0][0]存入B[0]中，则A[7][5]在B[ ]中位置为多少？

答案：33

8、设二维数组A10*9的每个元素占4个字节，已知Loc（a00）=2000，按行和按列优先存储时，a56的起始地址分别为多少？ 答案；（1）2024；（2）2260

9、设有一个10阶的对称矩阵A[10][10]，采用压缩存储方式按行将矩阵中下三角部分的元素

存入一维数组B[ ]中，A[0][0]存入B[0]中，则A[8][5]在B[ ]中位置为多少？

答案：41

10、设二维数组A10*9的每个元素占7个字节，已知Loc（a00）=1500，A 共占多少个字节？A的终端结点a98的起始地址为多少？ 答案：（1）630；（2）2123

11、设有一个10阶的对称矩阵A[20][20]，采用压缩存储方式按行将矩阵

中下三角部分的元素存入一维数组B[ ]中，A[0][0]存入B[0]中，则A[14][12]在B[ ]中位置为多少？

答案：117

12、设二维数组A6*7的每个元素占5个字节，已知Loc（a00）=1000，A共占多少个字节？A的终端结点a56的起始地址为多少？按行和按列优先存储时，a46的起始地址分别为多少？

答案：（1）210；（2）1205；（3）行：1170 列：1200

13、设二维数组A12*9的每个元素占4个字节，已知Loc（a11）=2000，A共占多少个字节？A的终端结点a118的起始地址为多少？按行和按列优先存储时，a85的起始地址分别为多少？

答案:（1）432；（2）2428；（3）行：2268 列：2220

五、综合题

1、给出下列二叉树的前序序列、中序序列、后序序列。

答案：前序：CABEFDHG

中序：BAFECHDG 后序：BFEAHGDC

2、假定用于通信的电文仅由4个字母a，b，c，d, e组成，各个字母在电文中出现的频率分别为7，6, 5，2，4。试为这5个字母设计Huffman树且写出对应的Huffman编码。 答案:

a :10 b: 00 c: 01 d:110 e :111

b c a d e

3、把下面的森林转换为对应的二叉树。

A E H D G I K

C J B

搜索成功时的平均搜索长度为：ASLsucc=2.5

12、已知待排序记录的关键字序列为{83，69，41，22，15，33，8，20}，

要求：（1）用归并排序法按从小到大顺序写出每趟排序的结果，直到排序结束； 答案：8，15，20，22，33，41，69，83

13、设二叉树t的中序序列为BADCE，后序序列为BDECA，请给出二叉树的前序序列。

要求：（1）画出这棵二叉树：（3分） （2）写出这棵二叉树的前序遍历序列。 (1)

C B

E D

（3分）

(2)前序序列：ABCDE

14、假定用于通信的电文仅由8个字母a，b，c，d，e，组成，各个字母在电文中出现的频率

分别为5，3，6，10，4。试为这5个字母设计Huffman树。

A 答案：

a c d b e

15、把下面的二叉树转换为相应的森林。

答案：

b a c e f h

d g

16、已知一个图的邻接矩阵如下，请分别写出从顶点V0出发按深度和广度优先遍历时得到的顶点序列。

01234567011000000100110001100001102010000013010000014001000015001000016000111107

答案：深度遍历：VO,V1,V3,V7,V4,V5,V2,V6

广度遍历：V0,V1,V2,V3,V4,V5,V6,V7

17、已知散列函数为H(K)=K mod 6,健值序列为25，37，52，43，84，99，120， 15，26，11采用拉链法处理冲突，试构造开散列表，并计算查找 成功的平均查找长度。

答案：开散列表省略，

ASL=1.3

18、一个对象序列的排序码为{46，79，56，38，40，84}，采用快速排序以位于最左位置的对

象为基准而得到的第一次划分结果为多少？

答案：{40，38，46，56，79，84}

19、已知一棵二叉树的前序和中序序列，求该二叉树的后序序列。

前序序列：A, B, C, D, E, F, G, H, I, J 中序序列：C, B, A, E, F, D, I, H, J, G

后序序列：

答案：后序序列：CBFEIJHGDA

20、把下面的二叉树转换为对应的森林

E

H A

答案：

C B D G I

A E F H I D G

C B 21、已知无向图G的邻接表如下，请画出其所有的连通分量。

答案： V3 V1 V2

V5 V4 22、给出如图所示的有向图G的邻接矩阵的存储结构。

23、已知散列函数为H(K)=K mod 9,健值序列为19，14，25，01，68，28，84，27，56，12采用拉链法处理冲突，试构造开散列表，并计算查找成功的平均查找长度。 答案：

开散列表省略， ASL= 1.5

24、对于给定的一组键值：83，40，63，13，84，35，96，57，39，79，61，15， 请给出采用起泡排序法对该序列作升序排序时的每一趟的结果。

25、已知某二叉树的中序序序列为ABCDEGFHI，后序序列为ACDBGIHFE，请给出二叉树的前序序列。

要求：（1）画出这棵二叉树：（3分）

（2）写出这棵二叉树的前序遍历序列。（2分） 答案：

B F

A D G C

（3分）

先序序列：EBADCFGHI （2分）

26、把下面的二叉树转换为对应的森林。

E

E H I

A D C J B H G I K

答案：

A E H D G I K

C B

J 27、假定用于通信的电文仅由4个字母a，b，c，d组成，各个字母在电文中出现的频率分别为7，5，2，4。试为这4个字母设计Huffman树。 答案：

a b c d

28、写出有向图的拓扑排序序列。

答案：V3,V1,V4,V5,V2,V6

V4 V5 V3 V1 V2 V6 29、已知散列函数为H(K)=K mod 12,健值序列为25，37，52，43，84，99，120，

15，26，11，70，82，采用拉链法处理冲突，试构造开散列表，并计算查找 成功的平均查找长度。

答案：开散列表省略，

ASL=19/12

30、已知待排序记录的关键字序列为{83，69，41，22，15，33，8}， 要求：（1）用直接选择排序法按从小到大顺序写出每趟排序的结果，直到排序结束；

答案：

第一趟：8，69，41，22，15，33，83 第二趟：8，15，41，22，69，33，83 第三趟：8，15，22，41，69，33，83 第四趟：8，15，22，33，69，41，83 第五趟：8，15，22，33，41，69，83 第六趟：8，15，22，33，41，69，83

31、把下面的树转换为对应的二叉树

答案：

A B E C D L K H I F J

G

32、已知一棵树二叉如下，请分别写出按箭序、中序、后序和层次遍历时得到的结点序列。

A

B C

D E F

G H

前序： 中序： 后序： 层次：

答案：前序：ABDGCEFH 中序：DGBAECHF 后序：GDBEHFCA 层次：ABCDEFGH

33、已知权值 W={ 8，6, 2, 15，7}，请构造对应的Huffman树。 答案：

8 7 15 6 2

34、写出如下有向图的拓扑排序序列。

V3 V1 V2 V6

V4 V5

答案：V1,V3,V4,V5,V2,V6

35、已知散列函数为H(K)=K mod 8,健值序列为25，37，52，43，84，99，120，15，26，11，采用拉链法处理冲突，试构造开散列表，并计算查找成功的平均查找长度

答案：开散列表省略，

ASL=1.2

36、已知待排序记录的关键字序列为{55，69，41，22，15，33，8，20}， 要求：（1）用堆排序法找出最大的值，要求写出排序过程；

答案：69；过程略

37、已知一棵二叉树的中序遍历的结果为：ABCEFGHD，后序遍历的结果为：ABFHGEDC

请给出二叉树的前序序列。

要求：（1）画出这棵二叉树：（3分）

（2）写出这棵二叉树的前序遍历序列。（2分） 答案：

C

B A

前序序列：CBADEGFH （2分）

D E G F H 38、试画出下面二叉试画出下面二叉树对应的二叉链表。。

39、假定用于通信的电文仅由4个字母a，b，c，d, e组成，各个字母在电文中

出现的频率分别为3，2, 4，6，5。试为这5个字母设计Huffman树且写出对应的Huffman编码。

c d e a b a :110 b: 111 c: 00 d:01 e :10

40、已知一个图的邻接表如下，请写出从顶点C0出发按深度遍历时得到的顶点序列。

答案：C0—C1—C3—C4—C5—C2

41、已知散列函数为H(k)=k mod 13， 关键字序列为25、37、52、43、84、99、120、15、26、11、80、23，处理冲突的方法为线性探测法，散列表长度为13，

（1）试画出该散列表。（3分）

（2）求出在等概率情况下的查找成功时的平均查找长度。(2分)

答案：（1）哈希表：

0 1 2 3 4 5 6 7 8 9 10 11 12

52 26 15 120 43 11 84 80 99 23 37 25

42、已知待排序记录的关键字序列为{83，69，41，22，15，33，8，20}， 要求：（1）用堆排序法找出最小的值，要求写出排序过程；

43、已知一棵二叉树的中序和后序序列如下，求该二叉树的高度（假定空树的高度为-1）和度

为2、度为1及度为0的结点个数。 中序序列：c,b,d,e,a,g,i,h,j,f

后序序列：c,e,d,b,i,j,h,g,f,a 答案：度为2为：3 度为1为：3 度为0为：4

44、给定权值7，18，3，32，5，26，12，8，构造相应的哈夫曼树

45、已知一个图的邻接表如下，请写出从顶点C0出发按广度遍历时得到的顶点序列。

答案：C0,C1,C2,C3,C4,C5

46、(该题2选1做)

4 B A 27 11 2

F 30 7 10 E D C 1 6 28

对于上图所示的无向图，要求：

(1)按普里姆(prim)算法从顶点A出发求其最小生成树，要求写出求解的顺序步骤。 (2)按克鲁斯卡尔(kruskal)算法求其最小生成树，要求写出求解的顺序步骤。

47、设散列表的长度ｍ＝１３；散列函数为Ｈ（Ｋ）＝Ｋ mod m，给定的关键码序列为19，14，25，01，68，28，84，27，56，12，试画出用线性探查法解决冲突时所构造的散列表。并求出在等概率的情况下，这种方法的搜索成功时的平均搜索长度。

0 1 2 3 4 5 6 7 8 9 10 11 12 搜索成功时的平均搜索长度为：ASLsucc=

答案：

0 1 2 3 4 5 6 7 8 9 10 11 12 12 14 01 68 28 27 19 84 56 25 解： H（19）=19 mod 13=6 H（14）=14 mod 13=1 H（25）=25 mod 13=12 H（01）=01 mod 13=1

a.elem[1]不空，所以第一次冲突处理后的地址为H（01）=（01+1） mod 13=2 H（68）=68 mod 13=3 H（28）=28 mod 13=2

a.elem[2]不空，所以第一次冲突处理后的地址为H（28）=（28+1） mod 13=3 a.elem[3]不空，所以第二次冲突处理后的地址为H（28）=（28+2） mod 13=4 H（84）=84 mod 13=6

a.elem[6]不空，所以第一次冲突处理后的地址为H（84）=（84+1） mod 13=7 H（27）=27 mod 13=1

a.elem[1]不空，所以第一次冲突处理后的地址为H（27）=（27+1） mod 13=2 a.elem[2]不空，所以第二次冲突处理后的地址为H（27）=（27+2） mod 13=3 a.elem[3]不空，所以第三次冲突处理后的地址为H（27）=（27+3） mod 13=4 a.elem[4]不空，所以第五次冲突处理后的地址为H（27）=（27+4） mod 13=5

H（56）=56 mod 13=4

a.elem[4]不空，所以第一次冲突处理后的地址为H（56）=（56+1） mod 13=5 a.elem[5]不空，所以第二次冲突处理后的地址为H（56）=（56+2） mod 13=6 a.elem[6]不空，所以第二次冲突处理后的地址为H（56）=（56+3） mod 13=7 a.elem[7]不空，所以第二次冲突处理后的地址为H（56）=（56+4） mod 13=8

H（12）=12 mod 13=12

a.elem[12]不空，所以第一次冲突处理后的地址为H（12）=（12+1） mod 13=0 平均搜索长度 ASLsucc=2.3

48、判断下列两序列是否为堆？如不是，按照建堆的思想把它调整为堆，并用图表示建堆的过程。 （1）（3，10，12，22，36，18，28，40）； （2）（5，8，11，15，23，20，32，7）。

49、某二叉树的结点数据采用顺序存储表示如下：

0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 E A F D H C G I B （1）试画出此二叉树的图形表示。（3分） （2）写出结点D的双亲结点及左、右子女。（3分）

（3）将此二叉树看作森林的二叉树表示，试将它还原为森林。（4分）

答案：(1) E

H A

B

(2) A;C; Ф (3)

C D G I

A E F H I D G

C B

50、已知权值 W={ 5, 6, 2, 9, 7 }，请构造对应的Huffman树。

6 7 9 5 2

51、给出如图所示的无向图G的邻接矩阵和邻接表两种存储结构。

答案：

52、已知散列函数为H(k)=k mod 13， 关键字序列为25、37、52、43、84、99、120、15、26、

11、70、82，处理冲突的方法为线性探测法，散列表长度为13，

（1）试画出该散列表。（3分）

（2）求出在等概率情况下的查找成功时的平均查找长度。(2分)

答案：（1）哈希表：

0 1 2 3 4 5 6 7 8 9 10 11 12

52 26 15 120 43 11 84 70 99 82 37 25 （2） 在等概率情况下查找成功的平均查找次数为：2.25

53、已知待排序记录的关键字序列为{83，69，41，22，15，33，8}， 要求：（1）用起泡排序法按从小到大顺序写出每趟排序的结果，直到排序结束；

参考答案：

83 69 41 22 15 15 8 69 41 22 15 22 8 15 41 22 15 33 8 22 22 15 33 8 33 15 33 8 41 33 8 69 8 83

初 第 第 第 第 第 第 始 一 二 三 四 五 六 关 趟 趟 趟 趟 趟 趟 键 排 排 排 排 排 排 字 序 序 序 序 序 序

后 后 后 后 后 后

54、已知一棵二叉树的中序和前序序列如下，求该二叉树的后序序列。

中序序列：c，b，d，e，a，g，I，h，j，f 前序序列：a，b，c，d，e，f，g，h，I，j 后序序列：

答案：后序：bedcfhjiga

55、

（1）树中哪个结点为根结点？哪些结点为叶子结点？ （2）结点B的双亲为哪个结点？其子女为哪些结点？ （3）哪些结点为结点D的兄弟？哪些结点为结点K的兄弟？ （4）结点A、C的度分别为多少？树的度为多少？ （5）以结点B为根的子树的高度为多少？

答案：（1）A;E,G,H,I,C,J,K,L

(2)A;E,F,G,H,I (3)B,C,L;J

(4)4;0;4 (5)3

56、设某密码电文由a,b,c,d,e,f,h,i 8个字母组成，每个字母在电文中的出现

频率分别是7，19，2，6，32，3，21，10，试为这8个字母设计相应的哈 夫曼编码

答案：a:1110;b:00;c:11010;d:1100;e:10;f:11011;h:01;i:1111 57、设有一无向图G=(V,E),其中

V={1,2,3,4,5,6},E={(1,2),(1,6),(2,6),(1,4),(6,4),(1,3),(3,4),(6,5),(4,5),(1,5),(3,5)}。

（1） 按上述顺序输入后，画出其相应的邻接表；

（2） 在该邻接表上，从顶点4开始，写出DFS序列和BFS序列。

58、已知散列函数为H(K)=K mod 7,健值序列为19, 01, 23, 14, 55, 68, 11, 82, 36，采用拉链法处理冲突，试构造开散列表，并计算查找成功的平均查找长度

参考答案：

开散列表省略， ASL= 13/9

59、已知序列（70，83，100，65，10，32，7，9），请给出采用直接插入排序法对该序列作升

序排序时的每一趟的结果

六、程序填空题

1、p是指向待删结点的前趋结点

void delete_lklist(lklist head,int I) {

p=find_lklist(head,I-1)

if(p!=NULL)&&( ( p–>nex ) !=NULL) {

q= p –>next;

p –>next= ( q –>next ) ; free(q); }

else error(“不存在这样的结点”)； }

2、单链表的插入操作

void insert_lklist(lklist head,datatype x,int I) {

p=find_lklist(head,I-1) if(p=NULL)

error(“不存在这样的结点”） else {

s= ( malloc ) (size);

s –>data=( x );

s –>next = p –>next; p –>next=( s ); } }

3、顺序表的插入操作

# define maxsize 100

typedef int DataType; typedef struc{

DataType data[maxsize]; int last; } Sqlist;

Void Insert_sqlist(Sqlist L，DataType x，int I) { if (L.last==( maxsize )) error(“表满”）； if(I<( 1 ) || I>( L.last+1 ))

error(“非法位置”）； for(j=L. last;j>=I;j--)

L.data[j]= (L.data[j-1] ); L.data[I-1]=x; L. last= ( L.last+1 ); }

4、查找第一个与给定值X相同的表结点的序号。 Pointer find_lklist(lklist head,int I) {

p=( head );j=0;

while(p –>next!=NULL)&&( ( p –> data ) !=x) {

p=( p –>next );j++; }

if p –> data ==x return(p); else return(0); }

5、顺序表上的查找算法。

int Search_Seq(SSTable ST, KeyType key) {。

ST.elem[( 0 )].key = key; // “哨兵”

for (i=ST.length; ST.elem[i].key!=key; ( i-- )); // 从后往前找 return i; // 找不到时，i为0 } // Search_Seq

6、INITIATE()的功能是建立一个空表。请在________处填上正确的语句。 lklist initiate_lklist() /*建立一个空表*/

{__ t=malloc(size)_; ___t –>next=NULL _; return(t); }

7、以下为求单链表表长的运算，分析算法，请在 ________处填上正确的语句。 int length_lklist(lklist head) /*求表head的长度*/ { p=head ;

j=0;

while(p->next!=NULL) {__ p=p –>next _; j++;

}

return(j); /*回传表长*/ }

8、以下对r[h],r[h+1],??r[p]子序列进行一趟快速排序。请分析算法，并在________上填充适当的语句。

int quickpass(list r,int h,int p)

{i=h;j=p;x=r[i];/*置初值，以第一个记录的键值为标准*/ while(i

{while((r[j].key>=x.key)&&(i

{ (r[i]=r[j] );i++;/* 将r[j].kiy

if(i

r[i]=x;return(i);/*一趟快速 排序结束，将x移至正确的位置*/ }

9、在一个单链表中的P所指的结点之前插入一个S所指结点，可执行如下操作。 S->next= ( p->next ) ; p->next=s; t=p->data;

p->data= ( s->data ) ; s->data= ( t ) ;

10、以下算法在有序表R中用二分查找法查找键值等于K的元素，请分析程序，并在________上填充合适的语句。

int binsearch(sqtable R,keytype K)

{low=1;hig=R.n;/*置查找区间初值。low,hig分别标记查找区间的下、上界*/ while(low<=hig)

{mid=（low+hig)/2; switch

{case K==R.item[mid].key:return(mid);/*找到，返回位置mid*/ case KR.item[mid].kiy:__low = mid + 1_;break;/*缩小区间*/ }

}

return(0);/*若区间长度已为0但仍不成功，则返回0，表示查找不成功*/ }

11、以下为单链表的建表算法，分析算法，请在____处填上正确的语句。 lklist create_lklist2() /*直接实现的建表算法。*/

{ head=malloc(size); p=( head );

scanf(“%f”,&x); while(x!=’$’) { q=malloc(size); q->data=x; p->next=q; ( p=q );

scanf(“%f”,&x); }

( p->next=NULL ); return(head); }

12、以下为冒泡排序的算法。请分析算法，并在________上填充适当的语句。 void bulbblesort(int n,list r) /*flag为特征位，定义为布尔型*/ {for(i=1;i=( n-1 );i++) {( flag=1 );

for(j=1;j=n-i;j++)

if(r[j+1].key

13、顺序表的删除操作 # define maxsize 100

typedef int DataType; typedef struc{

DataType data[maxsize]; int last; } Sqlist;

Void delete_sqlist(Sqlist L，int I) {

if(I<1 || I>( L.last+1 )) error(“非法位置”）； for(j=I+1;j>= L.last;j++)

L.data[j-2]= ( L.data[j-1] ); L. last=( L. last-1 ); }

本文来源：https://www.bwwdw.com/article/z7a6.html