2025年算法设计与数据结构题库挑战

数据构造试题库

一、单项选择题

1.下列程序段所代表的算法的时间复杂度为(D)。

x=n;

y=0;

while(x>=(y+l)*(y+l))

y++;

2n

(A)O(n)(B)O(n)(C)O(log2)(D)O(7n)

2.在一种长度为n的以次序构造存储的线性表中，假设在线性表的任何位置删除

元素的概率相等，则删除一种元素时线性表所需移动元素的平均次数为

(B)o

(A)n2(B)(n-l)/2(C)(n+1)/2(D)n/2

3.在一种栈顶指针为HS的链栈中插入一种心结点时，应执行执行操作为

(C)0

(A)HS->next=s;(B)s->next=HS->next;HS->next=s;

(C)s->next=HS;HS=s;(D)s->next=HS;HS=HS>next;

4.假设以带头结点的循环链表表达队列Q,并且队列只设一种头指针front,不设

队列尾指针。若要进队一种元素*s,则在下列程序算法的空白处应添加的操作

语句是(A)。

voidAddQueue(structlinkqueueQ)

{p=Q->front;

while(p->next!=Q->front)p=p->next;

__________)

(A)p->ncxt=s;s->ncxt=Q->front;

(B)Q->front->next=s;Q->front=s;

(C)s->next=p;p->next=Q->front;

(D)Q->front->next=s;s->next=p;

5.设高度为h的二叉树上只有度为0和度为2的结点，则此类二叉树中所包括的

结点数至少为(B)。

(A)2h-1(B)2h"+1(C)2h1(D)2h-'3

6,既有数据集{53,30,37,12,45,24,96},从空二叉树逐一插入数据形成二叉排序树，

若但愿查找此二叉树中任一结点的平均查找长度最小，则应选择下面哪个序列

输入(C)。

(A)45,24,53,12,37,96,30(B)30,24,12,37,45,96,53

(C)37,24,12,30,53,45,96(D)12,24,30,37,45,53,96

7.有一组数值{5,12,9,20,3),用以构造哈夫曼树，则其带权途径长度WPL值为

(D)o

(A)93(B)96(C)123(D)I03

8.已知一种有向图G的顶点v={vl,v2,v3,v4,v5,v6),其邻接表如下图所示，根据

有向图的深度优先遍历算法，从顶点vl出发，所得到的顶点遍历序列是

(B)o

9.设有m=2U个关键字，假设对每个关键字查找的概率相等，查找失败的概率为

0,若采用二分法查找一种关键字，则平均查找长度为(D)。

(A)n-l(B)n-n/m(C)(n-l)-n/m(D)(n-l)+n/m

10.己知一种待散列存储的线性表{18,81,58,34,26,75,67,49,93},散列函数为

h(k)=k%ll,散列地址空间为。〜10。若采用线性探查法处理冲突，则平均查找

长度为(A)。

(A)5/3(B)13/9(C)16/9(D)3/2

11.下列程序段所代表的算法的时间复杂度为(C)。

y=n；

x=1;

while(x<=y)

x*=2;

2n

(A)O(n)(B)O(n)(C)O(log2)(D)O(V«)

12.在一种长度为n的以次序构造存储的线性表中，假设在线性表的任何位置插

入元素的概率相等，则插入一种元素时线性表所需移动元素的平均次数为

(B)o

(A)n2(B)(n+l)/2(C)(n-l)/2(D)n/2

13.若对一种已经有序的线性表最频繁的操作是查找值为x的元素(假设存在的

话)，则采用(D)存储方式实现查找，其算法的时间复杂度为最小。

(A)单链表(B)双链表(C)单循环链表(D)次序表

14.一种带头结点head的循环单链表为空的判断条件是(C)。

(A)head==NULL(B)head->next==NULL

(C)head->next==head(D)head!=NULL

15.若链队列HQ中只有一种结点，则队列的头指针和尾指针满足下列条件

(D)o

(A)HQ->rear->next==HQ->front(B)HQ->front->next==HQ->rear->next

(C)HQ->front==HQ->rear(D)HQ->front->next==HQ->rear

16.从一种栈顶指针为HS的链栈中删除一种结点时，用x保留被删除结点的

值，则应执行操作为(A)。

(A)x=HS->data;HS=HS->next;(B)x=HS->data;HS->NEXT=NULL;

(C)HS=HS->next;x=HS->data;(D)x=HS->data;HS=NULL;

17.一棵有n个结点的满二叉树，有m个叶子结点，深度为h,那么n、m和h

满足条件(D)。

(A)n=m+h(B)h+m=2n(C)m=h-1(D)n=2h-1

18.一棵左、右子树均不为空的二叉树在先序线索化后，其空指针域数为

(B)o

(A)()(B)l(C)2(D)不确定

19.有一组数值{5,12,9,20,3},用以构造哈夫曼树，则其带权途径长度WPL值为

(C)O

(A)49(B)96(C)103(D)125

20.在一种n个结点的二叉排序树中查找一种关键字，进行关键字比较次数最大

值为(A)。

(A)n(B)n/2(C)log2n(D)n*log2n

21.已知有向图G=(V,E),其中V={vl,v2,v3,v4,v5,v6},则下列边集合E中

(A)所对应的有向图没有拓扑序列。

(A)E={<v2,v1>,<V6,V2>,<VI,v3>,<v2,v3>,<v5,v3>,<v3,v4>,<v4,v6>,<v5,v6>}

(B)E=(<v1,v2>,<vl,v3>,<vI,v4>,<v3,v5>,<v3,v2>,<v4,v5>,<v6,v5>,<v6,v4>}

(C)E={<vhv3>,<v1,v4>,<v1,v5>,<v2,v3>,<v2,v2>,<v3,v5>,<v3,v6>,<v4,v5>,<v4,

v6>,<v5,v6>}

(D)E={<vl,v2>,<v1,v3>,<v2,v3>,vvI,v4>,<v2,v5>,<v3,v6>,<v4,v6>,<v5,v6>}

22.冒泡排序算法在最佳状况下的时间复杂度为(B)。

2

(A)O(log2n)(B)O(n)(C)O(l)(D)O(n)

23.在下列内部排序措施中，排序时不稳定的，并且关键字的比较次数与记录的

初始排列次序无关的是(D)。

(A)迅速排序(B)冒泡排序(C)归并排序(D)堆排序

24.B知一种待散列存储的线件表(1X》1,5X,.34,26,75,67,49,93)•散列函数为

h(k)=k%11,散列地址空间为0〜10。若采用线性探查法处理冲突，则平均杳找

长度为(C)。

(A)5/3(B)13/9(C)16/9(D)3/2

25.下列程序段所代表的算法的时间复杂度为(D)。

i=l；j=0；

whiic(i<=n){

i+=j；

j++；

)

2n

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

26.将两个各有n个元素的有序表归并成一种有序表，在最坏的状况下，其比较

次数是(A)。

(A)2n-1(B)n(C)n+1(D)n-I

27.若某链表中最常用的操作是在最终的一种结点之后插入一种结点或删除最终

一种结点，则采用(D)存储方式最节省运行时间。

(AJ单链表(B)单循环链表(C)无头双向链表(D)带头双向链表

28.已知head是一种非空单链表的头指针，指针p指向单链表的最终一种结点，

若要在p之后插入一种新结点*s,并将单链表变为循环单链表，则应执行的操

作是(B)。

(A)s->next=p->next;p->next=s;(B)s->next=head;p->nexl=s;

(C)s->next=p->next;p->next=head;(D)s->next=p->next;s->next=p;

29.已知用循环链表表达的队列长度为n,若只设头指针，则出队和入队一种元

素的时间复杂度分别是(B)。

(A)O(l)和0(1)(B)O(1)和O(n)

(C)O(n)和0(1)(D)O(n)和0(n)

30.设链队列Q的头指针和尾指针分别为front和rear,初始时队列为空，若向队

列插入一种元素*s,则应执行的指针操作为(C)。

(A)Q->front->nexl=s;s->next=Q->rear;Q->rear=NULL;

(B)s->next=Q->front;Q->rear->next=s;Q->rear=NULL;

(C)Q->rcar->ncxt=s;Q->rcar=s;s->ncxt=NULL;

(D)Q->front->next=s;Q->rear=s;s->next=NULL;

31.已知一种带权图的顶点集V和边集G分别为：

V={1,2,345,6,7,8};

E={(3,1)6,(3,4)7,(3,7)5,(1,2)3,(1,4)4,(4,7)8,(4,5)4,(7,8)5,(2,6)3,

(2,5)5,(5,8)8,(5,6)5,(8,6)6),

则该图的最小生成树的权值为(C)。

(A)24(B)29(C)30(D)31

32.当待排序的关键字个数n很小，且初始排列为逆序时，采用下列排序措施中

的(D),算法的时间复杂度最小。

(A)直接插入排序(B)简朴选择排序

(。冒泡排序(D)迅速排序

33.对二叉排序树进行(C)遍历，可以得到该二叉树所有结点构成的排序序

列。

(A)层次(B)前序(C)中序(D)后序

34.已知一种长度为12的线性表(8,2,5,7,12,3,10,4,1,6,9,

11)，并将线性表中的元素依次插入到一种原先为空的二叉排序树中去。假设

查找每一种元素的概率相似，则查找该二叉树中任一结点的平均查找长度为

(A)o

(A)10/3(B)13/3(037/12(D)13/2

35.一组关键字序列｛15,92,124,5,27,28,18,6,36,34,3(),26,32,

259｝,将它们用散列函数H(key)=keyMODII按次序散列到HASH表HT

(0:10)中，用链地址处理冲突。假设查找每一种元素的概率相似，则查找该

HASH表中任一元素的平均查找长度为(C)。

(A)3/2(B)l()/7(C)ll/7(D)9/7

36.以数据集｛4,5,6,7,12,18,10｝为结点权值所构造的哈夫曼树，则其带

权途径长度WPL为(A)。

(A)165(B)203(C)124(D)187

37.假定对线性表进行分块查找，若将表均匀地分为b块，每块具有

n/b个记录；又假定表中每个记录的查找概率相等，并用次序查找确定所在的

块，若要使分块查找的平均查找长度ASL最小，则分块数b的值应为(B)。

nn

(A)V^(B)Vn+i(C)riog2j(D)rjog2j+i

38.对n个记录进行直接插入排序，所需的关键字比较次数的最大值和最小值分

别是(C)O

(A)n(n+1)/2和n(B)n(n-l)/2和n-1

(C)n(n+1)/2-1和n-1(D)n2和n

39.若在一种具有n个结点的有序单链表中插入一种新结点并仍然有序，则该操

作的时间复杂度是()。

2n

(A)O(l)(B)O(n)(C)O(nlog2)(D)O(n)

40.在一种头结点为head的空循环链表中插入一种结点s,则指针s应执行操作

()O

(A)heacl->ncxt=s;s->next=NULL;

(B)s->next=head;head->nexl=NULL;

(C)head->next=s;s->next=head->ncxt;

(D)s->next=head;head->next=s;

41.设链队列Q的头指针和尾指针分别为fronl和rear,队中元素个数为n(n>l),

指针*p指向队首元素m。若删除元素m,则应进行的指针操作为()。

(A)Q->front->next=p->next(B)Q->reai-Q->front

(C)Q->front=p->rcar(D)Q->rcar=p->next

42.假设二叉树T中有n个叶子结点，且所有非叶子结点均有左、右子树，那么

二叉树T共有()个结点。

(A)2n(B)2n-1(C)2n+1(D)2n+2

43.已知有向图G的邻接矩阵如下所示，则下列序列中()不也许是图G的拓

扑序列。

(A)vI,v6,v3,v4,v2,v5(B)vl,v6,v4,v3,v2,v5

(C)vI,v3,v2,v4,v6,v5(D)vI,v3,v6,v4,v5,v2

rA

011100

000000

010010

000010

000000

000110

44.已知一棵二叉树的结点数据采用次序存储构造，数组内容如下表所示，则该

二叉树的后序遍历序列为()。

1234567891()1112131415161718192021

EAFDGCJIHB

(A)ACBDJEFIGH(B)ABCDJEFHGI

(C)BCJDAHIGFE(D)EADCBJFGIH

45.若T为n个结点的完全二叉树，则T的叶子结点数为()。

(A)n/2(B)(n-2)/2(C)(n-l)/2(D)(n+l)/2

46.有一组数值14,21,32,15,28,用以构造huffman树，则其WPL值为()。

(A)267(B)189(C)110(D)294

47.采用折半插入排序，关键字的比较次数与移动次数分别为()。

2

(A)O(n),O(log2n)(B)O(n),O(log2n)

22

(C)O(log2n),O(n)(D)O(nlog2n),O(n)

48.假设结点序列为{60,30,90,50,95,70,40,80},以此构成一棵二叉排序树，则在

该二叉排序树上查找一种结点的平均查找长度为()。

(A)23/8(B)ll/4(C)9/2(D)4

49.下面程序段的时间复杂性的量级为(D)。

fbr(i=l;i<=n;i++)

for(j=l;j<=m;j++){

c[i][j]=O;

for(k=l;k<=w;k++)

c[i][j]+=a[i][k]*b[k]|j]

)

(A)O(i*j*k)(B)O(n*m*k)

(C)O(n*j*k)(D)O(n*m*w)

50.在一种长度为n的线性表中，删除值为x的元素时需要比较元素和移动元素

的总次数为(C)。

(A)(n+1)/2(B)n/2

(C)n(D)n+1

51.运用3,6,8,12,5,7这六个值作为叶子结点的权，生成一棵哈夫曼树，

该树的深度为(B)。

(A)3(B)4(C)5(D)6

52.一棵二叉树的广义表表达为a(b(c,d),e(,f(g))),则得到的层次遍历序列为

(D)o

(A)a,b,c,d,e,f,g(B)c,b,d,a,e,g,f

(C)c,d,b,g,f,e,a(D)a,b,e,c,d,f,g

53.若长度为n的线性表采用次序存储构造，在其第i个位置插入一种新元素的

算法的时间复杂度为()。(l<i<n+l)

(A)O(O)(B)O(l)(C)O(n)(D)O(n2)

54.若在线性表中采用折半查找法查找元素，该线性表应当()。

(A)元素按值有序(B)采用次序存储构造

(C)元素按值有序，且采用次序存储构造

(D)元素按值有序，月.采用链式存储构造

55.己知一算术体现式的中缀形式为A+B*C-D/E,后缀形式为ABC*+DE/-,其

前缀形式为()。

(A)-A+B*C/DE(B)-A+B*CD/E

(C)-+*ABC/DE(D)-+A*BC/DE

56.若二叉树采用二叉链表存储构造，要互换其所有分支结点左右子树的位置，

运用()遍历措施最合适。

(A)前序(B)中序(C)后序(D)按层次

57.对二叉排序树进行()遍历，可以得到该二叉树所有结点构成的排序序列。

(A)前序(B)中序(C)后序(D)按层次

58.具有n个顶点的有向图最多有()条边。

(A)n(B)n(n—1)Cn(n+1)(D)n2

59.从未排序序列中依次取出一种元素与已排序序列中的元素依次进行比较，然

后将其放在已排序序列的合适位置.，该排序措施称为()排序法。

(A)插入(B)选择(C)shcll(D)二路归并

60.排序趟数与序列的原始状态有关的排序措施是()排序法。

(A)插入(B)选择(C)冒泡(D)迅速

61.下面给出的四种排序法中()排序法是不稳定性排序法。

(A)插入(B)冒泡(C)二路归并(D)堆

62.一种对象序列的排序码为{46,79,56,38,40,84},采用迅速排序以位于

最左位置的对象为基准而得到的第一次划提成果为()。

(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}

63.线性链表不具有的特点是()。

(A)随机访问(B)不必事先估计所需存储空间大小

(C)插入与删除时不必移动元素(D)所需空间与线性表长度成正比

64.设F是一种森林，B是由F转换得到的二叉树，F中有n个非叶结点，贝ijB

中右指针域为空的结点有()个。

(A)n-l(B)n(C)n+1(D)n+2

65.具有65个结点的完全二叉树的高度为()。(根的层次号为0)

(A)8(B)7(C)6(D)5

66.若待排序对象序列在排序前已按其排序码递增次序排序，则采用()措施比

较次数至少。

(A)直接插入排序(B)迅速排序

(C)归并排序(D)直接选择排序

67.在一种无向图中，所有顶点的度数之和等于所有边数的()倍。

(A)3(B)2(C)l(D)l/2

68.对有14个数据元素的有序表R[14]进行折半搜索，搜索到R[3]的关键码等于

给定值，此时元素比较次序依次为()。

(A)R[O],R[1],R⑵,R[3](R)R[O],R[13],R[2],R[3]

(C)R[6],R[2],R[4],R[3](D)R[6J,R[4],R[2],R[3]

69.若度为m的哈夫曼树中，其叶结点个数为n,则非叶结点的个数为()。

(A)[(n+l)/(m+1)]-1(B)[n/m]-l

(C)[(n-l)/(m-l)](D)[n/(m-l)]-l

70.下面有关算法说法错误的是()。

(A)算法最终必须由「算机程序实现

(B)为处理某问题的算法同为该问题编写的程序含义是相似的

(C)算法的可行性是指指令不能有二义性

(D)以上几种都是错误的

71.如下与数据的存储构造无关的术语是()。

（A）循环队列（B）链表（C）哈希表（D）栈

72.如下数据构造中，哪一种是线性构造（）。

（A）广义表（B）二叉树（C）稀疏矩阵（D）串

73.如下那一种术语与数据的存储构造无关？（）

（A）栈（B）哈希表（C）线索树（D）双向链表

74.在下面的程序段中，对x的赋值语句的频度为（）。

FORi:=lTOnDO

FORj:=lTOnDO

x:=x+l;

（A）0（2n）（B）O（n）（C）O（n2）（D）O（log2n）

75.如下哪个数据构造不是多型数据类型（）。

（A）栈（B）广义表（C）有向图（D）字符串

76.持续存储设计时，存储单元的地址（）。

（A）一定持续（B）一定不持续

（C）不一定持续（D）部分持续，部分不持续

77.一棵左右子树均不空的二叉树在先序前驱和后序后继线索化后，其空链域数

为（A）。

（A）0（B）l（C）2（D）不确定

78.设图G采用邻接表存储，则拓扑排序算法的时间复杂度是（B）。

（A）O（n）（B）O（n+e）（C）O（n2）（D）O（n*e）

79.下列排序算法中，时间复杂度为O（Mog2n）且占用额外空间至少的是（A）。

（A）堆排序（B）冒泡排序（C）迅速排序（D）SHELL排序

80.已知数据表A中每个元素距其最终位置不远，则采用（B）排序算法最节省

时间。

（A）堆排序（B）插入排序（C）迅速排序（D）直接选择排序

81.串是（D）。

（A）不少于一种字母的序列（B）任意个字母的序列

（C）不少于一种字符的序列（D）有限个字符的序列

82.一种栈的输入序列为12345,则下列序列中是栈的输出序列的是(A)。

(A)23415(B)54132(C)31245(D)14253

83.设循环队列中数组的下标范围是1〜n,其头尾指针分别为f和r,则其元素个

数为(D)。

(A)r-f(B)r-f+l(C)(r-f)modn+1(D)(r-f+n)modn

84.二叉树在线索化后，仍不能有效求解的问题是(D)。

(A)先序线索二叉树中求先序后继(B)中序线索二叉树中求中序后继(C)中

序线索二叉树中求中序前驱(D)后序线索二义树中求后序后继

85.求最短途径的FLOYD算法的时间复杂度为(D)o

(A)O(n)(B)O(n+e)(C)O(n2)(D)O(n3)

86.一棵左右子树不空的二叉树在先序线索化后，其空指针域数为(B)。

(A)0(B)1(C)2(D)不确定

87.数组的每个元素占5个单元，将其按行优先次序存储在起始地址

为1000的持续的内存单元中，则元素A[5,5]的地址为(A)。

(A)1140(B)1145(C)112()(D)1125

88.在下列排序算法中，在待排序的数据表已经为有序时，花费时间反而最多的

是(A)。

(A)迅速排序(B)希尔排序(C)冒泡排序(D)堆排序

89.对有18个兀索的有序表做折半查找，则查找A⑶的比较序列的卜标依次为

(D)o

(A)1-2-3(B)9-5-2-3(C)9-5-3(D)9-4-2-3

90.下列排序算法中，某一趟结束后未必能选出一种元素放在其最终位置上的是

(D)o

(A)堆排序(B)冒泡排序(C)迅速排序(D)直接插入排序

91.在平衡二叉树中抵入一种结点后导致了不平衡，设最低的不平衡点为A,并

己知A的左孩子的平衡因子为-1,右孩子的平衡因子为0,则做(B)型调整

以使其平衡。

(A)LL(B)LR(C)RL(D)RR

92.下列各式中，按增长率由小至大的次序对的排列的是()。

(A)^,n!,2n,n3/2(B)n3/2,2n,nlogn,2100

(C)2n,logn,nlogn,n3/2(D)21()0,logn,2n,nn

93.若要在单链表中的结点*p之后插入一种结点处,则应执行的语句是()。

(A)s->next=p->next;p->next=s;

(B)p->next=s;s->next=p->next

(C)p->next=s->next;s->nexl=p;

(D)s->next=p;p->next=s->next;

94.若要在O(1)的E寸间复杂度上实现两个循环链表头尾相接，则应对两个循环

链表各设置一种指针，分别指向()。

(A)各自的头结点(B)各自的尾结点

(。各自的第一种元素结点(D)一种表的头结点，另一种表的尾结点

95.栈的两种常用存储构造分别为()。

(A)次序存储构造和链式存储构造(B)次序存储构造和散列存储构造

(C)链式存储构造和索引存储构造(D)链式存储构造和散列存储构造

96.已知循环队列的存储空间为数组data[21],且目前队列的头指针和尾指针的值

分别为8和3,则该队的目前长度为()。

(A)5(B)6(C)16(D)17

97.已知在如下定义的链串结点中，每个字符占1个字节，指针占4个字节，则

该链串的存储密度为()。

typedefstructnode{

chardate[8];

structnode*next;

)LinkStrNode;

(A)1/4(B)l/2(C)2/3(D)3/4

98.应用简朴的匹配算法对主串s="BDBABDABDAB”与子串t="BDA”进行

模式匹配，在匹配成功时，进行的字符比较总次数为()。

(A)7(B)9(C)10(D)12

99.二维数组A[20][1Q]采用列优先的存储措施，若每个元素占2个存储单元，且

第1个元素的首地址为200,则元素A[8J⑼的存储地址为()。

(A)574(B)576(C)578(D)580

100.对广义表L=((a,b),c,d)进行操作tail(head(L))的成果是()。

(A)(c,d)(B)(d)(C)b(D)(b)

101.已知一-棵树的前序序列为ABCDEF,后序序列为CEDFBA,则对该树进行

层次遍历得到的序列为()。

(A)ABCDEF(B)ABCEFD(C)ABFCDE(D)ABCDFE

102.一种含n个顶点和e条弧的有向图以邻接矩阵表达法为存储构造，则计算

该有向图中某个顶点出度的时间复杂度为()。

(A)O(n)(B)O(e)(C)O(n+e)(D)O(n2)

103.在关键字序列(12,23,34,45,56,67,78,89,91)中二分查找关键

字为45,89和12的结点时，所需进行的比较次数分别为()。

(A)4,4,3(B)4,3,3(C)3,4,4(D)3,3,4

104.下列排序措施中，最佳与最坏时间复杂度不相似的排序措施是()，

(A)冒泡排序(B)直接选择排序(C)堆排序(D)归并排序

105.已知含10个结点的二叉排序树是一棵完全二叉树，则该二叉排序树在等概

率状况下查找成功的平均查找长度等于()。

(A)1.0(B)2.9(C)3.4(D)5.5

106.在下列多种文献中，不能进行次序查找的文献是()。

(A)次序文献(B)索引文献(C)散列文献(D)多重表文献

107.下面带有@标识的语句的频度(n>10)是()。

for(inti=0;i<n-l;i++)

fbr(intj=i+l;j<n;j++)

@cout«i«j«endl;

(A)n*(n-l)/2(B)n*n/2(C)n*(n+l)/2(D)不确定

108.已知使用次序表存储数据，表长为n,假设在表中的任意位置插入元素的

概率相等，则插入一•种元素，平均需要移动的元素个数()。

(A)(n-l)/2(B)n/2(C)(n+l)/2(D)不确定

109.在双向链表p所指结点之后插入s所指结点的操作是()。

(A)p^right=s;s->left=p;p-^right^left=s;s->right=p^right;

(B)p->right=s;p->right^left=s;s->left=p;s^right=p->right;

(C)s->left=p;s->right=p->right;p->right=s;p->rightsleft=s;

(D)s->left=p;s->right=p->right;p->right->left=s;p^right=s;

110.字符串相等的充足必要条件是()。

(A)串长度相等(B)串使用相似的存储构造

(C)串相似位置对应的字符相等(D)A和C

111.将一种递归算法改为对应的非递归算法时，一般需要使用()。

(A)数组(B)栈(C)队列(D)二叉树

112.一种栈的入栈序列1,2,3,4,5,则栈的不也许的输出杼列是(

(A)12345(B)54321(C)32514(D)12354

113.设循环队列中数组的下标范围是1〜n,其头尾指针分别为f和r,则其元素

个数为()。

(A)r-f(B)r-f+l(C)(r-f)modn+1(D)(r-f+n)modn

114.某二叉树的前序遍历结点访问次序是ABDEFCGH,中序遍历的结点访问次

序是DBFEAGHC,则其后序遍历的结点访问次序是()。

(A)DFEBHCGA(B)DFEBHGCA

(C)DEFBHGCA(D)DFEHBGCA

115.正则二叉树是只有度为0和2的结点的二叉树，己知正则二叉树的叶子结

点个数为n,则该二叉树总得结点数为()。

(A)n+1(B)2*n(C)2*n+l(D)2*n-1

116.下面有关排序的说法错误的是()。

(A)迅速排序、归并排序都是一种不稳定的排序措施

(B)直接插入排序和折半插入排序移动元素的次数相似

(C)简朴选择排序移动元素的次数至少

(D)根据排序需要的平均时间，迅速排序是目前最佳的一种内部排序措施

117.折半查找有序表(3,4,5,1(),13,14,20,30),若查找元素3,则

被比较的元素依次为()。

(A)10,20,30(B)10,14,30(C)13,3(D)10,4,3

118.下面有关栈和队列的说法对的的是()。

(A)栈是先进先出的线性表，队列是后进先出的线性表

(B)栈是先进先出的线性表，队列也是先进先出的线性表

(C)栈是后进先出的线性表，队列是先进先出的线性表

(D)栈是后进先出的线性表，队列也是后进先出的线性表

119.两个各有n个元素的有序列表并成一种有序表，其至少的比较次数是

()O

(A)n(B)2n-1(C)2n(D)n-l

120.设循环队列中数组的下标范围是。〜n-1,f表达队首元素的前驱位置，r表

达队尾元素的位置，则队列中元素个数为()。

(A)r-f(B)r-f1(C)(r-f1)modn(D)(r-fn)modn

121.一种5行6列的二维数组s采用从最终一行开始，每一行的元素从右至左的

方式映射到一维数组a中，s和a的下标均从0开始，则s[3]⑶在a中的下标是

)

(A)7(B)8(C)9(D)l()

122.设只含根结点的二叉树的高度为1,则高度为n的二叉树中所含叶子结点的

个数最多为()个。

(A)2n(B)n(C)2n-1(D)2n-1

123.设高度为h的二叉树上只有度为()和度为2的结点，则此二叉树中所包括

的结点数至少为()个(设只含根结点的二叉树的高度为I)。

(A)2h(B)2h-1(C)2h+1(D)h+1

124.对一棵二叉检索树进行()得到的结点序列是一种有序序列。

(A)前序环游(B)中序环游(C)后序环游(D)层次环游

125.一棵前序序列为1,2,3,4的二叉树，其中序序列不也许是()。

(A)4,l,2,3(B)4,3,2,l©2,4,31(D)3,4,2,l

126.在含n个顶点和e条边的有向图的邻接矩阵中，零元素的个数为()。

(A)e(B)2e(C)n2-e(D)n2-2e

127.具有n个顶点和e条边的图的深度优先搜索算法的时间复杂度为()。

(A)O(n)(B)O(n3)(C)O(n2)(D)O(ne)

128.假如具有n个顶点的图是一种环，则它有()棵生成树。

(A)n(B)n1(C)n-l(D)2n

129.堆排序算法在平均状况下的时间复杂度为()。

(A)O(n)(B)O(nlogn)(C)O(n2)(D)O(logn)

130.在待排序数据已基本有序的前提下，二述排序措施中效率最高的是

()O

(A)直接插入排序(B)直接选择排序(C)迅速排序(D)归并排序

131.在理想状况下，散列表中查找元素所需的比较次数为()。

(A)n(B)O(C)n/2(D)l

132.在一棵m阶B树中，若在某结点中插入一种新关键字而引起该结点分裂，

则此结点中原有的关键字的个数是()。

(A)m(B)m+1(C)m-l(D)m/2

133.设次序循环队列Q[0：M-1]的头指针和尾指针分别为F和R,头指针F总

是指向队头元素的前一位置，尾指针R总是指向队尾元素的目前位置，则该循

环队列中的元素个数为(C)。

(A)R-F(B)F-R(C)(R-F+M)%M(D)(F-R+M)%M

134.设某棵二叉树的中序遍历序列为ABCD,前序遍历序列为CABD,则后序

遍历该二叉树得到序列为(A)。

(A)BADC(B)BCDA(C)CDAB(D)CBDA

135.设某完全无向图中有n个顶点，则该完全无向图中有(A)条边。

(A)n(n-l)/2(B)n(n-l)(C)n2(D)n2-l

136.设某棵二叉树中有个结点，则该二叉树的最小高度为(C)。

(A)9(B)1()(C)11(D)12

137.设某有向图中有n个顶点，则该有向图对应的邻接表中有(B)个表头结

点。

(A)n-1(B)n(C)n+1(D)2n-l

138.设一组初始记录关键字序列(5,2,6,3,8),以第一种记录关键字5为基

准进行一趟迅速排序的成果为(C)。

(A)2,3,5,8,6(B)3,2,5,8,6

(03,2,5,6,8(D)2,3,6,5,8

139.设某数据构造的二元组形式表达为A=(D,R),D={01,02,03,04,05,

06,07,08,09),R={r},r={<01,02>,<01,03>,<01,04>,<02,05>,

<02,06>,<03,07>,<03,08>,<03,09>),则数据构造A是(B)。

(A)线性构造(B)树型构造(C)物理构造(D)图型构造

140.下面程序的时间复杂为(B)

for(i=l,s=0；i<=n；i++){t=l：for(j=1；j<=i；j++)t=t*j•s=s+t；}

(A)0(n)(B)0(n2)(C)0(n3)(D)0(n4)

141.设指针变量p指向单链表中结点A,若删除单链表中结点A,则需要修改

指针的操作序列为(A)。

(A)q=p->next；p->data=q->data；p->next=q->next；free(q)；

(B)q=p->ncxt；q->data=p->data；p->ncxt=q->ncxt；frcc(q)；

(C)q=p->next；p->next=q->next；free(q)；

(D)q=p->nexl；p->dala=q->data；free(q)；

142.设有n个待排序的记录关键字，则在堆排序中需要(A)个辅助记录单

兀0

(A)1(B)n(C)nlog2n(D)n2

143.设一组初始关键字记录关键字为(20,15,14,18,21,36,40,10),则以

20为基准记录的一趟迅速排序结束后的成果为(A)。

(A)1(),15,14,18,20,36,40,21

(B)10,15,14,18,20,40,36,21

(C)10,15,14,20,18,40,36,21

(D)15,10,14,18,20,36,40,21

144.设二叉排序树中有n个结点，则在二叉排序树的平均平均查找长度为

(B)o

(A)0(1)(B)O(log2n)(C)Iog2n(D)O(n2)

145.设无向图G中有n个顶点e条边，则其对应的邻接表中的表头结点和表结

点的个数分别为(D)。

(A)n,e(B)e,n(C)2n,e(D)n,2e

146.设某强连通图中有n个顶点，则该强连通图中至少有(C)条边。

(A)n(n-l)(B)n+1(C)n(D)n(n+l)

147.设有5000个待排序的记录关键字，假如需要用最快的措施选出其中最小的

10个记录关键字，则用下列(B)措施可以到达此目的。

(A)迅速排序(B)堆排序(C)归并排序(D)插入排序

148.下列四种排序中(D)的空间复杂度最大。

(A)插入排序(B)冒泡排序(。堆排序(D)归并排序

149.设一维数组中有n个数组元素，则读取第i个数组元素的平均时间复杂度为

(C)O

(A)O(n)(B)O(nlog2n)(C)0(1)(D)O(n2)

150.设一棵二叉树的深度为k,则该二叉树中最多有(D)个结点。

(A)2k-1(B)2k(C)2k-1(D)2k-1

151.设某无向图中有n个顶点e条边，则该无向图中所有顶点的入度之和为

(D)o

(A)n(B)e(C)2n(D)2e

152.在二叉排序树中插入一种结点的时间复杂度为(B)。

(A)0(1)(B)0(n)(C)O(log2n)(D)0(n2)

153.设某有向图的邻接表中有n个表头结点和m个表结点，则该图中有(C)

条有向边。

(A)n(B)n-1(C)m(D)m-1

154.设一组初始记录关键字序列为(345,253,674,924,627),则用基数排序

需要进行(A)趟的分派和回收才能使得初始关键字序列变成有序序列。

(A)3(B)4(C)5(D)8

155.设用链表作为栈的存储构造则退栈操作(B)。

(A)必须鉴别栈与否为满(B)必须鉴别栈与否为空

(C)鉴别栈元素的类型(D)对栈不作任何鉴别

156.下列四种排序中(A)的空间复杂度最大。

(A)迅速排序(B)冒泡排序(C)希尔排序(D)堆

157.设某二叉树中度数为0的结点数为No,度数为1的结点数为Nh度数为2

的结点数为N2,则下列等式成立的是(C)。

(A)NO=N1+1(B)NO=N1+N2(C)N0=N2-I(D)NO=2N1+1

158.设有序次序表中有n个数据元素，则运用二分查找法查找数据元素X的最

多比较次数不超过(A)。

(A)log2n+l(B)log2n-l(C)log2n(D)log2(n+1)

159.数据的最小单位是(A)。

(A)数据项(B)数据类型(C)数据元素(D)数据变量

160.设一组初始记录关键字序列为(50,40,95,20,15,70,60,45),则以增

量d=4的一趟希尔排序结束后前4条记录关键字为(B)。

(A)40,50,20,95(B)15,40,60,20

(C)15,20,40,45(D)45,40,15,20

161.设一组初始记录关键字序列为(25,50,15,35,80,85,20,40,36,

70)其中具有5个长度为2的有序子表,则用归并排序的措施对该记录关犍字

序列进行一趟归并后的成果为(A)。

(A)15,25,35,50,20,40,8(),85,36,70

(B)15,25,35,50,80,20,85,40,70,36

(C)15,25,35,50,80,85,20,36,40,70

(D)15,25,35,50,80,20,36,40,70,85

162.设一种有序的单链表中有n个结点，现规定插入一种新结点后使得单链表

仍然保持有序，则该操作的时间复杂度为(D)。

(A)O(log2n)(B)O(l)(C)0(n2)(D)0(n)

163.设一棵m叉树中度数为0的结点数为No,度数为1的结点数为Ni，

度数为m的结点数为Nm,