数据结构2020网课答案-中国大学mooc

文章转载自一公一众一号【大学答案帮手】

上面的有完整版的，因为权限限制，仅保留部分答案，题目是全部的

以下是题目

1、多叉路口交通灯的管理问题，采用（ ）关系的数据结构。

A、集合

B、线性

C、树形

D、图状

答案：D

2、（ ） 是数据的基本单位，在计算机程序中通常作为一个整体进行考虑和处理。

A、数据

B、数据元素

C、数据项

D、数据对象

答案：B

3、（ ）是一个值的集合和定义在这个值集上的一组操作的总称。

A、数据类型

B、数据结构

C、抽象数据类型

D、数据对象

答案：A

4、算法的健壮性是指 （）

A、当输入数据非法时，算法也能作出反应或进行处理

B、在任何情况下，算法不会出现死循环

C、算法的执行效率高

D、算法中没有逻辑错误

答案：A

5、当输入非法数据时，算法也能适当地做出反应或进行处理，而不会产生莫名其妙的输出结果。是指算法的（ ）

A、健壮性

B、正确性

C、有穷性

D、可读性

答案：A

6、语句 for(i=1;i<=n;++i) ++x; 的时间复杂可表示为：（）

A、O(n+1)

B、O(n)

C、O(n*n)

D、O(n-1)

答案：B

7、空间复杂度作为算法所需存储空间的量度，只需要分析该算法在实现时所需要的辅助空间单元个数就可以，无需考虑算法本身所占的存储空间。

答案：正确

8、图书馆的数目检索系统采用 关系的数据结构

A、集合

B、线性

C、树形

D、图状

答案：B

9、是相互之间存在一种或多种特定关系的数据元素的集合。

A、数据

B、数据元素

C、数据项

D、数据结构

答案：D

10、是一个值的集合和定义在这个值集上的一组操作的总称。

A、数据类型

B、数据元素

C、数据项

D、数据结构

答案：A

11、算法的确定性是指（ ）

A、当输入数据非法时，算法也能作出反应或进行处理

B、在任何情况下，算法不会出现死循环

C、算法中的每一条指令必须有确切的含义

D、算法中没有逻辑错误

答案：C

12、说说数据结构和程序设计的关系

答案：能说出关键点，且语句通顺

13、数据的逻辑关系，数据的存储结构及数据的运算之间存在着怎样的关系？

答案：数据的逻辑关系反映数据元素之间的逻辑关系(即数据元素之间的关联方式或“邻接关系”),数据的存储结构是数据结构在计算机中的表示,包括数据元素的表示及其关系的表示。数据的运算是对数据定义的一组操作,运算是定义在逻辑关系上的,与存储结构无关,而运算的实现则是以来于存储结构

14、当你为解决某一问题而选择数据结构时，应从哪些方面考虑？在编辑管理通讯录时，什么样的数据结构合适？为什么？

答案：要点基本回答正确

15、线性表中的数据元素除最后一个元素之外都只有一个后继。

答案：正确

16、在长度为n的顺序表的第i个位置上插入一个元素(1<=i<=n+1)，元素的移动次数为：（)

A、n-i+1

B、n-i

C、i

D、i-1

答案：A

17、线性表采用链式存储结构时，其地址（ ）。

A、必须是连续的

B、部分地址必须是连续的

C、一定是不连续的

D、连续与否均可以

答案：D

18、带头结点的循环单链表中空链表的判定条件是 （ ）

A、head == NULL

B、head->next == head

C、head->next == NULL

D、head != NULL

答案：B

19、在双向链表指针p的结点前插入一个指针q的结点操作是（ ）。

A、p->prior=q;q->next=p;p->prior-next=q;q->prior=q；

B、p->prior=q;p->prior->next=q;q->next=p;q->prior=p->prior;

C、q->next=p;q->prior=p->prior;p->prior->next=q;p->prior=q;

D、q->prior=p->prior;q->next=q;p->prior=q;p->prior=q;

答案：C

20、一元多项式的表示及相加采用（）存储结构。

答案：链表

21、用顺序结构存储，删除最后一个结点时（ ）

A、会移动其它结点位置

B、一定不会移动其它结点位置

C、可能会移动其它结点位置

D、其它

答案：B

22、链表中逻辑上相邻的元素的物理地址 相邻。

A、必定

B、不一定

C、一定不

D、其它

答案：B

23、线性表中的数据元素有一个前驱多个后继

答案：错误

24、假设某个单向循环链表的长度大于1，且表中既无头结点也无头指针。已知s为指向链表中某个结点的指针，试编写算法在链表中删除指针s所指结点的前驱结点。 Status ListDelete_CL(LinkList &S){ LinkList p,q; if(S==S->next)return ERROR; q=S; p=S->next; while( ){ q=p; p=p->next; } q->next=p->next; free(p)； return OK; }

答案：p->next!=s

25、设顺序表va中的数据元素递增有序。试写一算法，将x插入到顺序表的适当位置上，以保持该表的有序性。

答案：算法基本思路正确逻辑无错误算法整体可行

26、已知线性表中的元素以值递增有序排列，并以单链表作存储结构。试写一高效的算法，删除表中所有值大于mink且小于maxk的元素（若表中存在这样的元素），同时释放被删结点空间，并分析你的算法的时间复杂度（注意，mink和maxk是给定的两个参变量，它们的值可以和表中的元素相同，也可以不同）。

答案：算法基本思路正确逻辑无错误，算法整体可行算法能实现题目中的所有要求，并分析出算法的时间复杂度

27、已知栈的最大容量为4。若进栈序列为1，2，3，4，5，6，且进栈和出栈可以穿插进行,则可能出现的出栈序列为（ ）

A、5，4，3，2，1，6

B、2，3，5，6，1，4

C、3，2，5，4，1，6

D、1，4，6，5，2，3

答案：C

28、在一个具有n个单元的顺序栈中，假定以地址低端（即0单元）作为栈底，以top为栈顶指针，则当做出栈处理时，top变化为( )

A、top++

B、top--

C、top不变

D、top=0

答案：B

29、数制转换采用（）结构来实现。

A、栈

B、队列

C、链表

D、顺序表

答案：A

30、在判别一个表达式中左、右括号是否配对出现的算法，采用（）数据结构最佳。

A、线性表的顺序存储结构

B、队列

C、线性表的链式存储结构

D、栈

答案：D

31、4.表达式a*(b+c)-d的后缀表达式是（ ）。

A、abcd*+-

B、abc+*d-

C、abc*+d-

D、-+*abcd

答案：B

32、假设从终端接受了这样一行字符：whli##ilr#e（s#s)，实际有效的是while (ss)。

答案：错误

33、一个递归算法必须包括（ ）。

A、递归部分

B、终止条件和递归部分

C、迭代部分

D、终止条件和迭代部分

答案：B

34、关于栈和队列的说法中正确的是（ ）

A、栈和队列都是线性结构

B、栈是线性结构，队列不是线性结构

C、栈不是线性结构，队列是线性结构

D、栈和队列都不是线性结构

答案：A

35、链队列中的插入P指针指向的结点的操作为（ ）

A、Q.rear->next = p; Q.rear = p

B、Q.rear = p; p->next=NULL

C、Q.rear->next = p; Q.rear = NULL

D、空

答案：A

36、在具有m个单元的循环队列中，队头指针为front，队尾指针为rear，则队满的条件是（）

A、front==rear

B、(front+1)%m==rear

C、rear+1==front

D、(rear+1)%m==front

答案：D

37、在离散事件的模拟中，（）采用队列结构来实现。

A、到达事件和离开事件

B、每个窗口的客户

C、其它

D、空

答案：B

38、在具有m个单元的循环队列中，队头指针为front，队尾指针为rear，则队满的条件是（ ）

A、front==rear

B、(front+1)%m==rear

C、rear+1==front

D、(rear+1)%m==front

答案：D

39、若以S和X分别表示进栈和退栈操作，则对初始状态为空的栈可以进行的栈操作系列合法的是（ ）

A、SXSSXXXX

B、SXXSXSSX

C、SXSXXSSX

D、SSSXXSXX

答案：D

40、设计一个迷宫求解的算法，采用 数据结构最佳。

A、线性表的顺序存储结构

B、栈

C、队列

D、线性表的链式存储结构

答案：B

41、循环队列存储在数组A[0..m-1],则出队时的操作为（ ）

A、front=front+1

B、front=(front+1)mod (m-1)

C、ront=(front+1)mod m

D、front=(front mod m)+1

答案：C

42、试写一个算法，识别依次读入的一个以@为结束符的字符序列是否为形如‘序列1&序列2’模式的字符序列。其中序列1和序列2中都不含字符‘&’，且序列2是序列1的逆序列。例如，‘a+b&b+a’是属该模式的字符序列，而‘1+3&3-1’则不是。 BOOL Symmetry(char a[]){ int i=0; Stack s; InitStack(s); ElemType x; while(a[i]!='&' && a[i]){ ; i++; } if(a[i]) return FALSE; i++; while(a[i]){ Pop(s,x); if(x!=a[i]){ DestroyStack(s); return FALSE; } i++; } return TRUE; }

答案：Push(s,a[i])

43、假设称正度和反读都相同的字符序列为“回文”，例如，‘abba’和‘abcba’是回文，‘abcde’和‘ababab’则不是回文。试写一个算法判别读入的一个以‘@’为结束符的字符序列是否是“回文”。 Status SymmetryString(char p){ Queue q; if(!InitQueue(q)) return 0; Stack s; InitStack(s); ElemType e1,e2; while(p){ Push(s,*p); ; p++; } while(!StackEmpty(s)){ Pop(s,e1); DeQueue(q,e2); if(e1!=e2) return FALSE; } return OK; }

答案：EnQueue(q,*p)

44、假设以S和X分别表示入栈和出栈的操作，则初态和终态均为空栈的入栈和出栈的操作序列可以表示为仅由S和X组成的序列。称可以操作的序列为合法序列（例如，SXSX为合法序列，SXXS为非法序列）。试给出区分给定序列为合法序列或非法序列的一般准则，并证明：两个不同的合法（栈操作）序列（对同一输入序列）不可能得到相同的输出元素（注意：在此指的是元素实体，而不是值）序列

答案：给出区分给定序列为合法序列或非法序列的一般准则写出合理正确的证明过程

45、试证明：若借助栈由输入序列12…n得到的输出序列为P1P2...PN(它是输入序列的一个排列)，则在输出序列中不可能出现这样的情形：存在着i<j<k是Pj<Pk<Pi

答案：写出合理正确的证明过程

46、若按教科书3.1.1节中图3.1(b)所示铁道进行车道(注意:两侧铁道均为单向行驶道)，则请回答： （1）如果进站的车厢序列为123，则可能得到的出站车厢序列是什么？ （2）如果进站的车厢序列为123456，则能否得到435612和135426的出站序列，并请说明为什么不能得到或者如何得到(即写出‘S’表示进栈和以‘X’表示出栈的栈操作序列)

答案：第一问回答正确第二问回答正确，能说出合理的理由

47、简述线性表，栈和队列的相同点和不同点

答案：能够准确的说清楚三者的异同点

48、串（即字符串）是一种特殊的线性表，是最基本的非数值数据，它的每个数据元素仅由一个字符组成。

答案：正确

49、C语言中提供的串类型以（）存储方式实现。

A、定长顺序

B、堆

C、其它

D、空

答案：B

50、在串的定长顺序存储表示中执行串连接操作可能会出现字符串的“截断”现象。

答案：正确

51、用链表存储时，通常一个结点中可以存放一个字符，也可以存放多个字符。

52、设有两个串p和q，其中q是p的子串，求q在p中首次出现的位置的算法称为（ ）

A、求子串

B、联接

C、匹配

D、求串长

53、下面关于串的叙述中，哪一个是不正确的？（ ）

A、串是字符的有限序列

B、空串是由空格构成的串

C、模式匹配是串的一种重要运算

D、串既可以采用顺序存储，也可以采用链式存储

54、设s=’I AM A STUDENT’ , t=’GOOD’ , q=’WORKER’则Concat(Substring(s,6,2) ,Concat(t,Replace(s,’STUDENT’,q)))=( )

A、A GOOD I AM A WORKER

B、ST GOODSTUDENT

C、A GOOD STUDENT

D、A GOOD WORKER

55、设串sl=″Data Structures with Java″,s2=“it″，则子串定位函数index(s1,s2)的值为（ ）

A、15

B、16

C、17

D、18

56、空串与空格串是相同的。

57、常对数组进行的两种基本操作是____。

A、建立与删除

B、索引和修改

C、查找和修改

D、查找与索引

58、二维数组A[8][9]按行优先顺序存储，若数组元素A[2][3]的存储地址为1087，A[4][7]的存储地址为1153，则数组元素A[6][7]的存储地址为（）

A、1207

B、1209

C、1211

D、1213

59、设 n行n列的下三角矩阵A已压缩到一维数组B[0..n*（n+1）/2-1]中，若按行为主序存储，则Ai,j对应的B中存储位置为___。

A、i(i-1)/2+j-1

B、i*i/2+j

C、i*i/2+j-1

D、其它

60、三元组用来存储（ ）

A、稠密矩阵

B、稀疏矩阵

C、广义表

D、特殊矩阵

61、广义表是 （ ）的推广。

A、数组

B、线性表

C、队列

D、树

62、若一个广义表的表尾为空表，则此广义表亦为空表。

63、若一个广义表的表头为空表，则此广义表亦为空表。

64、下面说法不正确的是( )。

A、广义表的表头总是一个广义表

B、广义表的表尾总是一个广义表

C、广义表难以用顺序存储结构

D、广义表可以是一个多层次的结构

65、设广义表L=（（a,b,c）），则L的长度和深度分别为（）。

A、1和1

B、1和3

C、1和2

D、2和3

66、广义表的深度=Max {子表的深度} +1。

67、数组A中，每个元素A的长度为3个字节，行下标i从1到8，列下标j从1到10，从首地址SA开始连续存放在存储器内，存放该数组至少需要的单元数是____。

A、80

B、100

C、240

D、270

68、假设有二维数组A6×8，每个元素用相邻的6个字节存储，存储器按字节编址。已知A的起始存储位置为1000，计算数组A按行存储时元素A[14]第一个字节的位置（ ）

A、1018

B、1024

C、1030

D、1072

69、广义表（（（））,a,((b,c),(),d),(((e)))）的长度为（）

A、3

B、4

C、5

D、2

70、下面说法不正确的是 ( ）

A、广义表的表头总是一个广义表

B、广义表的表尾总是一个广义表

C、广义表难以用顺序存储结构

D、广义表可以是一个多层次的结构

71、若采用三元组压缩技术存储稀疏矩阵,只要把每个元素的行下标和列下标互换,就完成了对该矩阵的转置运算

72、试按教科书5.5节图5.10所示的结点结构编写复制广义表的递归算法。 // 由广义表L复制广义表T int CopyGList(GList& T,GList& L){ if(!L) T=NULL; else{ T=new GLNode; if(!T) exit(OVERFLOW); T->tag=L->tag; if(L->tag==ATOM) T->atom=L->atom; else{ ; CopyGList(T->tp,L->tp); } } return OK; }

73、已知等差数列的第一项为a1,公差为d,试写出该数列前n项的和S(n)()的递归定义

74、已知顺序表L含有n个整数，试分别以函数形式写出下列运算的递归算法：（1）求表中的最大整数（2）求表中的n个整数之和

75、利用广义表的GetHead和GetTail操作写出如上题的函数表达式，把原子banana分别从下列广义表中分离出来。 (1)L1=((apple,pear),(banana,orange)); (2)L2=(apple,(pear),((banana)),(((orange)))); (3)L3=((((apple),pear),banana),orange);

76、按教科书5.5节中图5.8所示节点结构，画出下列广义表的存储结构图，并求它的深度。 ((((a),b)),((( ),d,(e,f)))

77、在一棵度数为4的树T中，若有20个度为4的结点，10个度为3的结点，1个度为2的结点，10个度为1的结点，则树T的叶结点个数是（ ）

A、41

B、82

C、113

D、122

78、深度为i的二叉树至多有( )结点

A、

B、

C、

D、

79、若一棵具有n个结点的二叉树采用二叉链表存储结构,那么该二叉树所有结点共有（）个空指针域。

A、n+1

B、n

C、n-1

D、n-2

80、由于二叉树中每个结点的度最大为2,所以二叉树是一种特殊的树.

81、二叉树的先序遍历序列中,任意一个结点均处在其子女结点的（）位置。

A、后面

B、前面

C、中间

D、不确定

82、引入二叉线索树的目的是（）

A、加快查找结点的前驱或后继的速度

B、为了能在二叉树中方便的进行插入与删除

C、为了能方便的找到双亲

D、使二叉树的遍历结果唯一

83、利用二叉链表存储树，则根结点的右指针是（）。

A、指向最左孩子

B、指向最右孩子

C、空

D、非空

84、把一棵树转换为二叉树后，这棵二叉树的形态是()。

A、唯一的

B、有多种

C、有多种，但根结点都没有左孩子

D、有多种，但根结点都没有右孩子

85、已知一棵树的先根次序访问序列为GFKDAIEBCHJ;数的后根次序访问序列为DIAEKFCJHBG 。 请问这棵树中结点I的双亲为( )。

A、A

B、B

C、C

D、D

86、设给定权值总数有n个，其哈夫曼树的结点总数为( )

A、不确定

B、2n

C、2n+1

D、2n-1

87、2.哈夫曼编码得到的是定长编码。

88、已知一棵树边的集合为{<I,M>, <I,N>, <E,I>, <B,E>, <B,D>, <A,B>, <G,J>, <G,K>, <C,G>, <C,F>, <H,L>, <C,H>, <A,C>},问这棵树中结点G的双亲结点为( )

A、A

B、C

C、I

D、B

89、一棵二叉树中，叶子的个数为10，则其度为2的结点的个数为

A、9

B、10

C、11

D、12

90、假如一棵二叉树的中序遍历结果为ABCD，则结点A和结点D的关系一定不是( )

A、结点A是结点D的双亲结点

B、结点A是结点D的右子树上的结点

C、结点A是结点D的左子树上的结点

D、结点A与结点D具有共同的双亲的右子树上的结点

91、已知一棵树边的集合为{<I,M>, <I,N>, <E,I>, <B,E>, <B,D>, <A,B>, <G,J>, <G,K>, <C,G>, <C,F>, <H,L>, <C,H>, <A,C>},将此树转化为二叉树后，E的左孩子为（ ）

A、A

B、C

C、I

D、B

92、一棵哈夫曼树有17个结点，则其叶子结点的个数是

A、7

B、8

C、9

D、10

93、编写递归算法，将二叉树中所有结点的左、右子树相互交换。 Status ExchangeBiTree(BiTree& T) { BiTree p; if(T){ p=T->lchild; T->lchild=T->rchild; T->rchild=p; ; ExchangeBiTree(T->rchild); } return OK; }

94、已知一棵度为k的树中有个度为1的结点，个度为2的结点，…，个度为k的结点，问该树中有多少个叶子结点？

95、对于那些所有非叶子结点均含有左右子数的二叉树： (1) 试问：有n个叶子结点的树中共有多少个结点？ (2) 试证明：，其中n为叶子结点的个数，表示第i个叶子结点所在的层次（设根节点所在层次为1）。

96、证明：树中结点u是结点v的祖先，当且仅当在先序序列中u在v之前，且在后序序列中u在v之后。

97、假设n和m为二叉树中两结点，用“1”、“0”或“Φ”(分别表示肯定、恰恰相反或者不一定)填写下表： 前序遍历时n在m前？ 中序遍历时n在m前？ 后序遍历时n在m前？ n在m左方 n在m右方 n是m祖先 n是m子孙 注：如果(1)离a和b最近的共同祖先p存在，且(2)a在p的左子树中，b在p的右子树中，则称a在b的左方(即b在a的右方)。

98、将下列森林转换为相应的二叉树，并分别按以下说明进行线索化： (1)先序前驱线索化； (2)中序全线索化前驱线索和后继线索； (3)后序后继线索化。

99、假设一颗二叉树的先序序列为EBADCFHGIKJ和中序序列为ABCDEFGHIJK。请画出该树。

100、在一个无向图中，所有顶点的度数之和等于所有边数的___倍。

A、1/2

B、2

C、3

D、1

101、对于一个具有n个顶点和e条边的无向图,若采用邻接表表示，所有邻接表中的结点总数是（）。

A、e/2

B、e

C、2e

D、n+e

102、下面结构中最适于表示稀疏有向图的是（）。

A、邻接矩阵

B、逆邻接表

C、邻接多重表

D、十字链表

103、下面结构中最适于表示稀疏无向图的是（）。

A、邻接矩阵

B、逆邻接表

C、邻接多重表

D、十字链表

104、一个有向图的邻接矩阵中各非零元素之和与图中边的条数相等。

105、采用邻接表存储的图的深度优先遍历算法类似于二叉树的（）。

A、先序遍历

B、中序遍历

C、后序遍历

D、按层遍历

106、图的广度优先遍历算法需要采用（）结构来实现。

A、栈

B、队列

C、链表

D、其它

107、具有6个顶点的无向连通图至少应该有 ( )条边。

A、5

B、6

C、7

D、8

108、一个有n个结点的图，最少有（）个连通分量。

A、0

B、1

C、n-1

D、n

109、求图的最小生成树有两种算法，克鲁斯卡尔算法适合于求稠密图的最小生成树。

110、下面（）方法可以判断出一个有向图中是否有环（回路）

A、深度优先遍历

B、拓扑排序

C、最短路径

D、关键路径

111、关键路径是事件结点网络中（ ）。

A、从源点到汇点的最长路径

B、从源点到汇点的最短路径

C、最长回路

D、无

112、迪杰斯特拉（Dijkstra）提出依路径长度递减的次序求得各条最短路径的算法。

113、弗洛伊德（Floyd）算法采用邻接矩阵存储结构来实现。

114、下图中结点B的出度为( )

A、0

B、1

C、2

D、3

115、对于一个具有n个顶点的无向图,若采用邻接矩阵表示,则该矩阵的大小为（ ）

A、n ×n

B、(n-1)× (n-1)

C、(n-1)×n

D、n×(n+1)

116、采用邻接表存储的图的宽度优先遍历算法类似于二叉树的（）

A、先序遍历

B、中序遍历

C、后序遍历

D、层次遍历

117、下面的无向带权图的最小生成树包含的边有( )

A、ae ge gf eb bc cd

B、ae ed dc cb eg df

C、ag gf fd dc cb be

D、ae eb bc cd df eg

118、判定一个有向图是否存在回路除了可以利用拓扑排序方法外,还可以利用（ ）

A、求关键路径的方法

B、求最短路径的Dijkstm方法

C、宽度优先遍历算法

D、深度优先遍历算法

119、编写算法实现从邻接表中取出某个顶点V的存储位置。 int LocateVex(ALGraph& G,VertexType v) { int i=0; while( &&i<G.vernum) i++; if(G.vertices[i].data==v) return i; else return -1; }

120、请对下图的无向带权图，(1)写出它的邻接矩阵，并按普里姆算法求其最小生成树； (2)写出它的临接表，并按克鲁斯卡尔算法求其最小生成树

121、试列出下图中全部可能的拓扑有序序列，并指出应用在7.5.1节中算法Topological Sort求得的是哪一个序列(注意：应先确定其存储结构)。

122、试利用Dijkstra算法求下图中从顶点a到其他各顶点间的最短路径，写出执行算法过程中各步的状态。

123、若查找每个记录的概率均等，则在具有n个记录的连续顺序文件中采用顺序查找法查找一个记录，其平均查找长度ASL为（）。

A、(n-1)/2

B、n/2

C、(n+1)/2

D、n

124、当在一个有序的顺序表上查找一个数据时，既可用折半查找，也可用顺序查找，但前 者比后者的查找速度 ( )

A、必定快

B、在大部分情况下要慢

C、取决于表递增还是递减

D、在大部分情况下要快

125、既希望较快的查找又便于线性表动态变化的查找方法是（ ）。

A、顺序查找

B、折半查找

C、索引顺序查找

D、哈希法查找

126、二叉排序树的查找效率与二叉树的（ ）有关。

A、高度

B、结点的多少

C、树型

D、结点的位置

127、m阶B_树中的m是指（ ）

A、每个结点至少有m棵子树

B、每个结点至多有m棵子树

C、非终端结点中关键字的个数

D、m阶B_树的深度（或高度）

128、在各种查找方法中,平均查找长度与结点个数n无关的查法方法是（ ）

A、哈希表

B、顺序表

C、有序表

D、二叉排序树

129、好的哈希函数有一个共同的性质，即函数值应当以( )取其值域的每个值。

A、最大概率

B、最小概率

C、平均概率

D、同等概率

130、如果两个关键字的值不等但哈希函数值相等，则称这两个关键字为同义词。

131、散列法的平均检索长度不随表中结点数目的增加而增加，而是随负载因子的增大而增大。

132、对线性表进行二分查找时,要求线性表必须（ ）。

A、以顺序方式存储

B、以链接方式存储

C、以顺序方式存储,且结点按关键字有序排序

D、以链接方式存储,且结点按关键字有序排序

133、下列描述中不符合二叉排序树特点的是（ ）

A、左子树中所有结点的关键字小于根结点的关键字

B、右字树中所有结点的关键字大于根节点的关键字

C、根结点的关键字大于左、右子树中所有结点的关键字

D、关键字插入的顺序影响二叉排序树的形态

134、设哈希表长m=14，哈希函数H(key)=key%11。表中已有4个结点： addr (15)=4; addr (38)=5; addr (61)=6; addr (84)=7 如用二次探测再散列处理冲突，关键字为49的结点的地址是（ ）。

A、8

B、3

C、5

D、9

135、试将折半查找的算法改写成递归算法。 Int bisearch (sqlist L,int low, int high , elemtype x ) { If (low>high) reeturn( 0 ); else { mid=(low+high)/2; if (L.data[mid]= =x) return (mid); else if (L.data[mid]>x) bisearch(L,low,mid-1,x); else ; } }//bisearch

136、设计算法判定给定二叉树是否为二叉排序树。 void BSTree(BiTree t,int &flag,int &last);//声明 Status IsBSTree(BiTree t){ int flag = 1; int last =0; BSTree(t,flag,last); return flag; } void BSTree(BiTree t,int &flag,int &last){//取地址不需要返回值 if(t->lchild&&flag) BSTree(t->lchild,flag,last);//遍历左子树 if(t->data.key>last&&flag) last = t->data.key; else flag=0; //last原为父节点值，但到了树叶节点后被树叶节点的key值覆盖，然后开始向上反馈key if(t->rchild&&flag) ； }

137、画出对长度为10的有序表进行折半查找的判定树，并求其等概率时查找成功的平均查找长度。

138、已知如下所示长度为12的表 (Jan,Feb,Mar,Apr,May,June,July,Aug,Sep,Oct,Nov,Dec) (1)试按表中元素的顺序依次插入一棵初始为空的二叉排序树，画出插入完成之后的二叉排序树，并求其在等概率的情况下查找成功的平均查找长度。 (2)若对表中元素先进行排序构成有序表，求其在等概率的情况下对此有序表进行折半查找时查找成功的平均查找长度。 (3)按表中元素顺序构造一棵平衡二叉排序树，并求其在等概率的情况下查找成功的平均查找长度。

139、试从空树开始，画出按以下次序向2-3树即3阶B-树中插入关键码的建树过程：20,30,50,52,60,68,70。如果此后删除50和68，画出每一步执行后2-3树的状态。

140、某内排序方法的稳定性是指（ ）。

A、该排序算法不允许有相同的关键字记录

B、该排序算法允许有相同的关键字记录

C、平均时间为0（n log n）的排序方法

D、以上都不对

141、排序方法中,从未排序序列中依次取出元素与己排序序列(初始时为空)中的元素进行比 较,将其放入己排序序列的正确位置上的方法,称为（）

A、希尔排序

B、起泡排序

C、插入排序

D、选择排序

142、对序列{15，9，7，8，20，-1，4，}用希尔排序方法排序，经一趟后序列变为{15，-1，4，8，20，9，7}，则该次采用的增量是（）。

A、1

B、4

C、3

D、2

143、对初始状态为递增序列的表按递增顺序排序，最省时间的是直接插入排序算法。

144、一组记录的关键码（46，79，56，38，40，84），则利用快速排序的方法，以第一个记录为基准得到的一次划分结果为 （ ）

A、38，40，46，56，79，84

B、40，38，46，79，56，84

C、40，38，46，56，79，84

D、40，38，46，84，56，79

145、采用简单选择排序，比较次数与移动次数分别为（ ）。

A、O(n),O(logn)

B、O(logn),O(n*n)

C、O(n*n),O(n)

D、O(nlogn),O(n)

146、以下序列不是堆的是（ ）。

A、(100,85,98,77,80,60,82,40,20,10,66)

B、(100,98,85,82,80,77,66,60,40,20,10)

C、(10,20,40,60,66,77,80,82,85,98,100)

D、(100,85,40,77,80,60,66,98,82,10,20)

147、树形选择排序的过程可用一棵有n个叶子结点的完全二叉树表示。

148、下列排序算法中，算法在进行一趟相应的排序处理结束后不一定能选出一个元素放到其最终位置上。 ( )

A、直选择排序

B、冒泡排序

C、归并排序

D、堆排序

149、设一组初始记录关键字序列为(345，253，674，924，627)，则用基数排序需要进行（ ）趟的分配和回收才能使得初始关键字序列变成有序序列。

A、3

B、4

C、5

D、8

150、在多关键字排序方法中低位优先排序采用的排序算法必须是稳定的算法.

151、下列排序算法中，其时间复杂度和记录的初始排列状态无关的是 ( )

A、直接选择排序

B、冒泡排序

C、快速排序

D、插入排序

152、设一组初始记录关键字序列为(50，40，95，20，15，70，60，45)，则以增量d=4 的一趟希尔排序结束后前4条记录关键字为（）。

A、40，50，20，95

B、15，40，60，20

C、15，20，40，45

D、45，40，15，20

153、快速排序方法在情况下最不利于发挥其长处。( )

A、要排序的数据量太大

B、要排序的数据中含有多个相同值

C、要排序的数据已基本有序

D、要排序的数据个数为奇数

154、一组记录的排序码为(46,79,56,38,40,84),则利用堆排序的方法建立的初始推为（）

A、79,46,56,38,40,80

B、84,79,56,38,40,46

C、84,79,56,46,40,38

D、84,56,79,40,46,38

155、设一组初始记录关键字序列为(25，50，15，35，80，85，20，40，36，70)，其中含有5个长度为2的有序子表，则用归并排序的方法对该记录关键字序列进行一趟归并后的结果为（ A ）。

A、15，25，35，50，20，40，80，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

156、设有1000个无序的元素,希望用最快的速度挑选出其中前10个最大的元素,最好的排序方法是（）。

A、选择排序

B、快速排序

C、堆排序

D、插入排序

157、具有10个记录的序列，采用冒泡排序最少的比较次数是 ( )

A、9

B、81

C、1

D、54

158、设一组初始记录关键字序列为(345，253，674，924，627)，则用基数排序需要进行（ ）趟的分配和回收才能使得初始关键字序列变成有序序列。

A、3

B、4

C、5

D、8

159、基数排序的设计思想是按照对关键字的比较来实施的.

160、试以L.r[k+1]作为监视哨改写教科书10.2.1节中给出的直接插入排序算法。其中，L.r[1..k]为待排序记录且k<MAXSIZE。 void InsertionSort ( SqList &L ) { // 对顺序表 L 作直接插入排序。 for ( i=k-1-1; i>=1; --i ){ if (L.r[i+1].key < L.r[i].key){ L.r[k+1] = L.r[i]; // 复制为监视哨 for ( j=i+1; L.r[k+1].key > L.r[j].key; ++ j ) L.r[j] = L.r[j+1]; // 记录前移 }//end if ； }//end for } // InsertSort

161、编写算法，对n个关键字取整数值的记录序列进行整理，以使所有关键字为负值的记录排在关键字为非负值的记录之前，要求： (1)采用顺序存储结构，至多使用一个记录的辅助存储空间； (2)算法的时间复杂度为O(n); void Divide(int a[ ],int n){//把数组a中所有值为负的记录调到非负的记录之前 low=0;high=n-1; while（low<high）{ while(low<high&&a[high]>=0) high--; //以0作为虚拟的枢轴记录 ; while(low<high&&a[low]<0) low++; a[low]<->a[high]; } }//Divide

162、以关键码序列(503,087,512,061,908,170,897,275,653,426)为例，手工执行以下排序算法，写出一趟排序结束时的关键码状态： (1)直接插入排序； (2)希尔排序(增量d[1]=5)； (3)快速排序； (4)堆排序； (5)归并排序； (6)基数排序。

163、判别以下序列是否为堆(小顶堆或大顶堆)。如果不是，则把它调整为堆(要求记录交换次数最少)。 (1) (100,86,48,73,35,39,42,57,66,21); (2) (12,70,33,65,24,56,48,92,86,33)。