数据结构单元自测题

第一章 线性表 一 单选题

1 线性表是具有n个____的有限序列。 A) 表元素 B) 字符 C) 数据元素 D) 数据项 E)信息项

**2 线性表的静态链表存储结构与顺序存储结构相比优点是_____。 A) 所有的操作算法实现简单 B) 便于随机存储 C) 便于插入和删除 D) 便于利用零散的存储器空间 3 若长度为n的线性表采用顺序存储结构，在其第i个位置插入一个新元素算法的时间复杂度为____。

2

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

**4 (1) 静态链表既有顺序存储的优点，又有动态链表的优点。所以，它存取表中第i个元素的时间与i无关; (2) 静态链表中能容纳元素个数的最大数在定义是就确定了,以后不能增加; (3) 静态链表与动态链表在元素的插入,删除上类似,不需做元素的移动. 以上错误的是_____. A) (1),(2) B) (1) C) (1),(2),(3) D) (2) P 5 将图1.10所示的s所指结点加到p所指结点之后,其语句应为____.

A) s?next=p+1; p?next=s; B) (*p).next=s; (*s).next=(*p).next; C) s?next=p?next; p?next=s?next; D) s?next=p?next; p?next=s; S 6 在双向链表存储结构中,删除p所指的结点时须修改指针______

图1.10插入结点示意

A) p?next?prior=p?prior; p?prior?next=p?next; B) p?next=p?next?next; p?next?prior=p;. C) p?prior?next=p; p?prior=p?prior?prior; D) p?prior=p?next?next; p?next=p?prior?prior;

7在双向循环链表中,在p指针所指的结点后插入一个指针q所指向的新结点,其修改指针的操作是____. A) p?next=q; q?prior=p; p?next?prior=q; q?next=q;

B) p?next=q; p?next?prior=q; q?prior=p; q?next=p?next;

C) q?prior=p; q?next=p?next; p?next?prior=q; p?next=q; D) q?next=p?next; q?prior=p; p?next=q; p?next=q;

8 将两个各有n个元素的有序表归并成一个有序表,其最少的比较次数是____. A) n B) 2n-1 C)2n D) n-1

9 在一个长度为n的顺序表中,在第i个元素(l≤i≤n+1)之前插入一个新元素时须向后移动___个元素. A) n –1 B ).n-i+1 C)n-i-1 D) .i

10 线性表L=(a1 ,a2,…an),下列说法正确的是____.

A) 每个元素都有一个直接前驱和一个直接后继 B) 线性表中至少有一个元素

C) 表中诸元素的排列顺序必须是由小到大或由大到小

D) 除第一个和最后一个元素外,其余每个元素都有一个且仅有一个直接前驱和直接后继 11 对单链表表示法,以下说法错误的是_____. A) 数据域用于存储线性表的一个数据元素

B) 指针域(或链域)用于存放一个指向本结点所含数据元素的直接后继所在结点的指针

C) 所有数据通过指针的链接而组织成单链表

D) NULL称为空指针,它不指向任何结点只起标志作用

12 若给定有n个元素的向量,则建立一个有序单向链表的时间复杂度的量级是____. A) O(l) B) O(n) C)

2)

O(n D) O(nlog2n)

13 以下说法正确的是____.

A) 顺序存储方式的优点是存储密度大且插入,删除运算效率高 B) 链表的每个结点中都恰好包含一个指针 C) 线性表的顺序存储结构优于链式存储结构

D) 顺序存储结构属于静态结构而链式结构属于动态结构 14 以下说法错误的是____.

A) 对循环链表来说,从表中任一结点出发都能通过前后移操作扫描整个循环链表 B) 对单链表来说,只有从头结点开始才能扫描表中全部结点

C) 双链表的特点是找结点的前驱和后继都很容易

D) 对双链表来说,结点*p的存储位置既存放在其前驱结点的后继指针域中,也存放在它的后继结点的前驱指针

中

15以下说法错误的是____.

A) 求表长,定位这两种运算在采用顺序存储结构时实现的效率不比采用链式存储结构时实现的效率低 B) 顺序存储的线性表可以随机存取

C) 由于顺序存储要求连续的存储区域,所以在存储管理上不够灵活 D) 线性表的链式存储结构优于顺序存储结构

**二 多选题 1 表长为n的顺序存储的线性表,当在任何位置上插入或删除一个元素的概率相等时,插入一个元素所需移动的元素平均个数为____,删除一个元素所需移动的平均个数为____. A) (n-1)/2 B) n C) n+1 D) n-1 E) n/2 F) (n+1)/2 G) (n-2)/2 2 便于插入和删除操作的是____. A) 静态链表 B) 单链表 C) 顺序表 D) 双链表 E)循环链表 3 从表中任一结点出发都能扫描整个表的是____. A) 静态链表 B) 单链表 C) 顺序表 D) 双链表 E)循环链表

三 填空题

1 在单链表中设置头结点的作用是____.

2 设单链表的结点结构为(data,next),next为指针域.已知指针px指向单链表中data为x的结点,指针py指向data为y的新结点,若将结点y插入结点x之后,则需要执行以下语句:________;_________. 3 对于双向链表,在两个结点之间插入一个新结点时需修改的指针共有____个,单链表为____个。

4 顺序存储结构使线性表中逻辑上相邻的数据元素在物理位置上也相邻.因此,这种表便于_____访问,是一种_____结构.

5 对一个线性表分别进行遍历和逆置运算,其最好的时间复杂性量级分别为____和____. 6 在一个循环单链表中,表尾结点的指针域与表头指针_____.

7 求顺序表和单链表长度的时间复杂性的量级分别为_____和_____.

8 在一个不带头结点的单链表中,在表头插入或删除与在其他位置插入或删除其操作过程_____.

9 在线性表的顺序存储中,元素之间的逻辑关系是通过___决定的;在线性表的链式存储中,元素之间的逻辑关系是通过____决定的.

10 单链表表示法的基本思想是用______表示结点间的逻辑关系.

四 判断题

1 线性表采用链表存储时,结点和结点内部的存储空间可以是不连接的. ( ) 2 在具有头结点的链式存储结构中,头指针指向链表中的第一个数据结点. ( ) 3 顺序存储的线性表可以随机存取. ( )

4、在单链表中，要访问某个结点，只要知道该结点的指针即可；因此，单链表是一种随机存取结构。 ( ) 5、在线性表的顺序存储结构中，插入和删除元素时，移动元素的个数与该元素的位置有关。 ( ) 6. 顺序存储结构属于静态结构，链式结构属于动态结构。 ( )

五 算法设计题

**2、在下列程序中，函数difference(A,B)用于求两集合之差C=A-B，即当且仅当e是A中的一个元素，但不是B中的元素时,e是C中的一个元素。集合用有序链表实现，用一个空链表表示一个空集合，表示非空集合的链表根据元素之值按递增排列。执行C=A-B之后，表示集合A和B的链表不变，若结果集合C非空，则表示它的链表根据元素之值按递增排列。函数append()用于在链表中添加结点。 #include Struct node{ Int element; Struct node *link; } Typedef struct node NODE; NODE *A,*B,*C; NODE *append(last,e); NODE *last; Int e; {Last?link=(NODE*)malloc(sizeof(NODE)); last?link?element=e; return(last?link); } NODE *difference(A,B) NODE *A,*B; {NODE *C,*last; C=last=(NODE*)malloc(sizeof(NODE)); While( ( 1 ) ) If(A?element

llink data rlink 5 给定(已生成)一个带头结点的单链表,设head为头指针,结点的结构为(data,next),data为整数元素,next为指针.试写出算法:按递增次序输出单链表中各结点的数据元素并释放结点所占的存储空间.(要求:不允许使用数组作辅助空间).

第二章 栈和队列

一 单选题

1 若用单链表表示队列，则应该选用______.

A) 带尾指针的非循环链表 B) 带尾指针的循环链表 C) 带头指针的非循环链表 D) 带头指针的循环链表 2 若用一个大小为6的数组来实现循环队列，且当rear和front的植分别为0和3.当从队列中删除一个元素,再加入两个元素后,rear和front的值分别为多少? A)1和5 B)2和4 C)4和2 D)5和1

3 设栈的输入序列为1,2,3,…,n,输出序列为a1,a2,….,an,若存在l≤k≤n使得ak=n,则当k≤i≤n时,ai为_____. A)n-i +1 B)n-( i-k) C)不确定

4 设栈的输入序列是(1,2,3,4),则____不可能是其出栈序列. A)1243 B)2134 C)1432 D)4312 E)3214 5 设栈S和队列Q的初始状态为空,元素e1,e2,e3,e4,e5和e6依次通过栈S,一个元素出栈后即进入队列Q,若6个

元素出队的序列是e2,e4,e3,e6,e5,e1,则栈S的容量至少应该是_____. A )6 B)4 C)3 D)2

6 一般情况下,将递归算法转换成等价的非递归算法应该设置_____ A)堆栈 B)队列 C)堆栈或队列 D)

数组

7 已知一算术表达式的中缀形式为A+B*C-D/E,后缀形式为ABC*+DE/-,其前缀形式为_____. A)-A+B*C/DE B)-A+B*CD/E C)-+*ABC/DE D)-+A*BC/DE

8 设栈的输入序列为1,2,…,n,若输出序列的第一个元素是n,则第i个输出元素是_____. A)不确定

B)n-i+1 C)i D)n-i

** 9 已知输入序列为,经过输出受限的双向队列后能得到的输出序列有____. A)dacb B)cadb C)dbca D)bdac E)以上答案都不对 ** 10 如图2.10所示的循环队列中元素数目是____.其中tail=32指向队尾元素,head=15指向队头元素的前一个空位置,队列空间m=60. A)42 B)16 C)17 D)41 tail 12345 30 输出端 输入端 head 15 45 栈S 0

图2.11 栈S示意

图2.10 循环队列

11假定一个顺序循环队列的队首和队尾指针分别用front和rear表示,则判队空的条件是______. A)front+1==rear B)front==rear+1 C)front==0 D)front==rear

12 假定一个顺序循环队列存储于数组A[n]中,其队首和队尾指针分别用front和rear表示,则判断队满的条件是____.

A)(rear-1)%n==front B)(rear+1)%n==front C)rear==(front-1)%n D)rear==(front+1)%n

** 二 多选题 1 依次读入数据元素序列(a,b,c,d,e,f,g)进栈,每进一个元素,机器可要求下一个元素进栈或出栈;如此进行,则栈空时弹出的元素构成的序列是以下哪些序列? A)(d,e,c,f,b,g,a) B)(f,e,g,d,a,c,b) C)(e,f,d,g,b,c,a) D)(c,d,b,e,f,a,g) 2 循环队列是____. A)顺序存储结构 B)不会产生下溢 C)不会产生上溢 D)队满时rear==front E)不会产生假溢 3 一个输入序列abcd经过一个栈到达输出序列,并且一旦离开输入序列后就不能再返回到输入序列,则下面____为正确的输出序列. A)bcad B)cbda C)dabc D)acbd E)dcba 4 已知输入序列为1234,则输入受限(仅由一端输入)但输出不受限(两端均可输出)的双端队列不可以得到____为输出序列. A)4231 B)1324 C)3214 D)4213 E)2341

三 填空题

1 用S表示入栈操作,X表示出栈操作,若元素入栈顺序为1234,为了得到1342出栈顺序,相应的S和X操作串为_____.

**2 中缀式a+b*3+4*(c-d)对应的前缀式为____,若a=1,b=2,c=3,d=4,则后缀式db/cc*a-b*+的运算结果为_____. **3 用下标0开始的N元数组实现循环队列时,为实现下标变量m加1后在数组有效下标范围内循环,可采用的表达式是m=__. 4 表达式求值是____应用的一个典型例子.

5 用数组Q(其下标在0…n-1中,共有n个元素)表示一个环形队列,f为当前队头元素的前一位置,r为队尾元素的位置.假定队列元素个数小于n,求队列中元素个数的公式是____.

6 用循环链表表示的队列长度为n,若只设头指针,则出队和入队的时间复杂度分别是____和____. 7 队列是特殊的线性表,其特殊性在于______.

8 一个循环队列存于A[M]中,假定队首和队尾指针分别为front和rear,则判断队空的条件为_____,判断队满的条件为____.

9 向一个循环队列存入新元素时,需要首先移动____.然后再向它所指位置___新元素.

10 如图2.11所示,设输入元素的顺序为1,2,3,4,5,要在栈S的输出端得到43521,则应进行栈的基本运算表示应为:push(S,1),push(S,2),push(S,3),push(S,4),pop(S),____,pop(S),pop(S),pop(S). 四 判断题

1 栈和队列都是限制存取点的线性结构

3 即使对不含相同元素的同一输入序列进行两组不同的,合法的入栈组合操作,所得的输出序列也一定相同. 4 消除递归不一定需要使用栈.

5 栈的输入序列为123…n,输出序列为a1a2an,若ai=n（1≤i＜n-1＝,则ai>ai+1>an.

五 算法设计题

1 可用一个数组S(设大小为MAX)作为两个堆栈的共享空间.请说明共享方法,栈满/栈空的判断条件,用C语言设计公用的入栈操作push(I,x),其中I为0或1,用于表示栈号,x为入栈值. 2 试各举一个例子,用示意图和简要说明阐述栈和队列在程序设计中所起的作用.

3 已知Q是一个非空队列,S是一个空栈。使用C语言编写一个算法，仅用队列和栈的ADT函数和少量工作变量，将队列Q中的所有元素逆置. 栈的ADT函数有:

makeEmpty(s:stack); 置空栈

push(s:stack;value:datatype); 新元素value进栈 pop(s:stack):datatype; 出栈,返回栈顶值 isEmpty(s:stack):Boolean; 判栈空否 队列的ADT函数有:

enqueue(q:queue;value:datatype); 元素value进队 deQueur(q:queue):datatype; 出队列,返回队头值 isEmpty(q:queue):Boolean; 判队列空否 4 有递归算法如下: int sum(int n) { if(n==0) sum=0; else

{ cin>>x;

sum=sum(n-1)+x; } }

设初值n=4,读入x=4,9,6,2.

问:(1)若x为局部变量时,该函数递归结束时返回调用程序的sum=?并画出在递归过程中栈状态的变化过程. (2)若x为全程变量,递归结束时返回调用程序的sum=?

5 已知Fibonacci数列的递归定义如下: 试写出求解fib(n)的递归和非递归算法.

0n?0??1n?1 fib(n)=??fib(n?1)?fib(n?2)n?1?第三章 串 一 单选题

1 若串S=’software’,其子串的数目是_____. A)8 B)37 C)36 D)9 2 设串长为n,模式串长为m, 则KMP算法所需的附加空间为______. A)O(m) B)O(n) C)O(n*log2m) D)O(m*n) E)其他

3 设S为一个长度为n的字符串,其中的字符各不相同,则S中互异的非平凡子串(非空且不同于S本身)的个数为____.

n-12 222

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

4 字符串’ababaabab’的nextval为______. A)(0,1,0,1,0,4,1,0,1) B)(0,1,0,1,0,2,1,0,1) C)(0,1,0,1,0,0,0,1,1) D)(0,1,0,1,0,1,0,1,1)

5 在字符串匹配中,当模式串位j与主串位i的比较失败时,新一趟匹配开始,主串的位移公式是______. A)i =i+1 B) i=j+1 C)i=i-j+1 D)i=i-j+2

6 已知串S=’aaab’,其next数组值为____. A)0123 B)1123 C)1231 D)1211

二 多选题

1 串又称字符串________.

A)串中元素只能是字符 B)串中元素只能是字母 C)串是一种特殊的线性表 D)串中可以含有空白字符 E)串长度不为零

2 模式串T=’abcaabbcabcaabdab’,该模式串的next数组值为(1)_____,nextval数组的值为(2)____. A)01112211123456712 B)01112121124567112 C)01110013101100701 D)01112231123456712 E)01100111011001702 F)01102131011021701

3 两个串相等必有___. A)串长度相等 B)串中各位置字符任意 C)串中各位置字符均对应相等 D)串长度不等 E)串长度任意

三 填空题

1 空格串是指_____,其长度等于_____.

2 模式串p=’abaabcac’的next函数值序列为____. 3一个字符串中____称为该串的子串.

4 设正文串长度为n,模式串长度为m,则串匹配的KMP算法的时间复杂度为_____. 5空串和空格串的区别在于:________.

6 在字符串运算中的”模式匹配”是常见的,KMP匹配算法是有用的办法. (1) 其基本思想为_________.

(2) 对模式串P(=P1P2….Pn)求next数组时,next[ i ]是满足下列性质的k的最大值或为0:_________. 7 串相等是指________.

8设有两个串P和Q,求Q在P中首次出现的位置运算称______. 9 串的两种最基本的存储方式是_______.

10 串的顺序存储有两种方法:一种是每个单元只存一个字符,称为____格式;另一种是每个单元存放多个字符,称为____格式.

四 判断题

1 串是由有限个字符构成的连续序列,串长度为串中字符的个数,子串是主串中字符构成的有限序列. 2 子串定位函数的时间复杂度在最坏情况下为O(n*m),因此子串定位函数没有实际使用的价值.

3 KMP算法的最大特点是指示主串的指针不需回朔.

4 设模式串的长度为m,目标串的长度为n;当n≈m且处理只匹配一次的模式时,朴素的匹配(即子串定位函数)

算法所花的时间代价也可能更为节省.

5 设有两个串P和Q,其中Q是P的子串,把Q在P中首次出现的位置作为子串Q在P中的位置算法称为模式匹

配.

五 算法设计题

1 S=”S1S2…Sn”是一个长为N的字符串,存放在一个数组中,编程序将S改造之后输出: (1) 将S的所有第偶数个字符按照其原来的下标从大到小的次序放在S的后半部分: (2) 将S的所有第奇数个字符按照其原来的下标从小到大的次序放在S的前半部分. 例如:S=’ABCDEFGHIJKL’ 则改造后的S为’ACEGIKLJHFDB’. 2 写一个递归算法来实现字符串逆序存储,要求不另设存储空间.

第四章 数组和广义表 一 单选题

1 已知广义表LS=((a,b,c),(d,e,f)，运用head和tail函数取出LS元素e的运算是____. A) head(tail(LS)) B)tail(head(LS)) C)head(tail(head(tail(LS))))

D)head(tail(tail(head(LS))))

2 将一个A[1…100,1..100]的三对角矩阵，按行优先存入一维数组B[1..298]中，A中元素a66,65（即该元素下

标i=66,j=65）,在B数组中的位置K为______. A)198 B)195 C)197

3 若广义表A满足Head(A)=Tail(A),则A为_______. A)() B)(()) C)((),()) D)((),(),())

4 广义表A=(a,b,(c,d),(e,f,g))),则下面式子的值为_______.Head(Tail(Head(Tail(Tail(A))))) A) (g) B) (d) C) c D) d

5 图4.9所示的结构是一个_______. A)线性表 B)数形结构 C)图结构 D)广义表 -1 1 b 0 ^ head

图4.9循环链表

atom info link 图4.9中的结点结构为：

6 二维数组A的每个元素是由6个字符组成的串，其行下标i=0,1,...,8，列下标j=1,2,…,10.若A按行先存储，元素A[8，5]的起始

地址与当A按列先存储时的元素_____的起始地址相同.设每个字符占一个字节. A) A[8,5] B) A[3,10] C) A[5,8] D) A[0,9]

7 数组SZ[-3…50,0…10]含有元素数目为_____. A) 88 B) 99 C) 80 D) 90 8 稀疏矩阵一般的压缩存储方法有____两种.

A)二维数组和三维数组 B)三元组和散列表 C)三元组和十字链表 D)散列表和十字链表

9 设矩阵A是一个对称矩阵,为了节省存储,将其下三角部分(如图4.10所示)按行序存放在一维数组B[1..n(n-1)/2]中,对下三角部分中任一元素aij(i≥j)在一维数组B的下标位置k值为______. A) i(i-1)/2+j-1 B) i(i-1)/2+j C) i(i+1)/2+j-1 D) i(i+1)/2+j

?a11?a21A=?????an1a22?an2????? ??ann? 4.10 矩阵A的下三角部分 图

10 对于以行为主序的存储结构来说,在数组A[c1..d1,c2..d2]中,c1和d1分别为数组A的第一维下标的下,上界, c2和d2

分别为第二维下标的下,上界,每个数据元素占k个存储单元,二维数组中任一元素a[i,j]的存储位置可由______确定.

A) Loc[i,j]=[(d2-c2+1)(i-c1)+(j-c2)]× k

A) Loc[i,j]=Loc[c1,c2]+[(d2-c2+1)(i-c1)+(j-c2)]× k B) Loc[i,j]=A[c1,c2]+[(d2-c2+1)(i-c1)+(j-c2)]× k C) Loc[i,j]=Loc[0,0]+[(d2-c2+1)(i-c1)+(j-c2)]× k

二 多选题

1 稀疏矩阵的压缩存储方式有____ . A) 顺序存储 B) 三元组表 C) 循环链表 D) 十字链表 2 对广义表来说,下述哪些是正确的____.

A) 广义表是一种多层次的结构 B) 广义表是一种非线性结构 C)广义表是一种共享结构 D) 广义表是一种递归表 E) 广义表是一种单链表结构

三 填空题

1 广义表(a,(a,b),d,e,(i(i,j,),k))的长度是______,深度是____.

2 设有一个10阶对称矩阵A采用压缩存储方式(以行为主序存储:a11=1),则a85的地址为____.

3 设数组a[1..50,1..80]的基地址为2000,每个元素占2个存储单元,若以行序为主序顺序存储,则元素a[45,68]的存储地址为

____;若以列序为主序存储,则元素a[45,68]的存储地址为______.

4 设有三对角矩阵如图4.11所示,将带状区域中的元素aij(|i-j|≤1)放在一维数组B中,则B的大小为_____.元素aij在B中的

位置是_____.(下标从0开始计)

5 三维数组a[ 4 ][ 5 ][ 6 ](下标从0开始计,a有4×5×6个元素),每个元素的长度是2,则a[ 2 ][ 3 ][ 4 ]的地址是______.(设a[ 0 ][ 0 ][ 0 ]的地址是1000,数据以行为主序方式存储) 6 广义表的元素可以是广义表;因此,广义表是一个_____的结构.

7 数组结构是由固定数量的且由一个值和一组下标组成的数据元素构成,其元素的下标关系具有____.

?a11?a?21???????

a12a22a32?a23a33?a34?an,n?1图4.11三对角矩阵 an?1,n?2an?1,n?1????? ?an?1,n??an,n??

8 一维数组的逻辑结构是_____,存储结构是____; 对二维或多维数组,分为按_____和_____两种不同的存储方式.

9 广义表((a))的表头是_____,表尾是_____.

10 需要压缩存储的矩阵可分为______矩阵和_____矩阵两种.

四 判断题

1 稀疏矩阵压缩存储后,必会失去随机存取功能. 2 若一个广义表的表头为空表,则此广义表亦为空表. 3 广义表是线性表的推广,是一类线性数据结构.

4 任何一个非空广义表,其表头可能是单元素或广义表,其表尾必定是广义表.

5 一个稀疏矩阵Am×n采用三元组形式表示.若把三元组中有关行下标与列下标的值互换,并把m和n的值互换,则就完成了Am×n的转置运算 6 数组是同类型值的集合.

7 数组是一种复杂的数据结构;数组元素之间的关系既不是线性的,也不是树形的. 8 广义表是由零或多个原子或子表所组成的有限序列,所以广义表可能是空表.

9 线性表可以看成是广义表的特例,如果广义表的每个元素都是原子,则广义表便成为线性表. 10 广义表中原子个数即为广义表的长度.

五 综合题目

?2? 1 设有矩阵a=3???11323?1??,执行下列语句后,矩阵c和a的结果分别是多少? 1??(1) FOR i:=1 TO 3 DO

FOR j:=1 TO 3 DO

c[ i,j ]:=a[a[ i,j ],a[ j,i ]] (2) FOR i:=1 TO 3 DO

FOR j:=1 TO 3 DO

a[ i,j ]:=a[a[ i,j ],a[ j,i ]]

2 一个n阶对称矩阵A采用一维数组S按行序为主序存放其上三角各元素,写出S[ K ]与A[ i,j ]的关系公式.设A[1,1]存于S[1]中.

3 给定有m个整数的递增有序数组a [1..m ]和有n个整数的递减有序数组b[ 1..n ],试写出算法,将数组a

和b归并为递增有序数组c[ 1..m+n ].(要求算法的时间复杂度为O(m+n))

4 给定一个整数数组b[ 0..N-1 ],b中连续的相等元素构成的子序列称为平台,试写算法,求出b中最长平台的

长度.

5 如果一个数列中的任意一段(至少是两个元素)的各个元素均相同,我们称之为等值数列段等值数列段中元素

的个数叫等值数列段长度.现有由100个元素组成的整数数列A,求A中长度最大的所有等值数列段的首末位置,如果没有等值数列段,则输出特殊标志.

第五章 树和二叉树 一 填空题

1 8层完全二叉树至少有____个结点,拥有100个结点的完全二叉树的最大层数为___. 2 线索二叉树的左线索指向其____,右线索指向其____. 3 树在计算机内的表示方式有____,____,____.

4 一棵有n个结点的满二叉树有____个度为1的结点,有____个分支(非终端)结点和____个叶子,该满二叉树的深度为____.

5 设一棵后序线索树的高度是50,结点x是树中的一个结点,其双亲是结点y,y的右子树高度是31,x是y的左孩子,则确定x的后继最多需经过_____中间结点(不含后继及本身)..

6 设F是由T1,T2,T3三棵树组成的森林,与F对应的二叉树为B.已知T1,T2,T3的结点数分别为n1,n2和n3,则二叉树B的左子树中有___个结点,二叉树B的右子树中有___个结点.

7 若一个二叉树的叶子结点是某子树的中序遍历序列中的最后一个结点,则它必是该子树的_____序列中的最后一个结点.

8 一棵共有n个结点的树,其中所有分支结点的度均为k,则该树中的叶子结点个数为_____.

9 深度为k(设根的层数为1)的完全二叉树至少有____个结点,至多有____个结点,k和结点数n之间的关系是____.

10 一棵含有n个结点的k叉树,可能达到的最大深度为____,最小深度为______. 11 包含结点A,B和C的二叉树有____种不同的形态,____种不同的二叉树. 12 包含结点A,B和C的树有____种不同的形态,____种不同的树.

13 设只包含根结点的二叉树高度为0,则高度为k的二叉树最大结点数为____,最小结点数为_____.

14 某二叉树结点的对称序列为A,B,C,D,E,F,G, 后序序列为B,D,C,A,F,G,E, 则该二叉树结点的前序序列为

____,该二叉树

对应的树林包括___棵树.

15 若二叉树有n个结点,对它分别进行前序遍历,中序遍历,后序遍历时,开辟的栈分别为____个存储单元,___个存储单元,

____个存储单元

16 一棵完全二叉树有999个结点,它的深度是_____.

17 对于一棵具有n个结点的树,该树中所有结点的度数之和为_____. A 18 有n个结点并且其高度为n的二叉树有____个.

19 图5.42为某树的静态双亲链表表示,则结点D,E的双亲分别为______. B

0 1 2 3 4 A B C D E -1 0 0 1 2 C E 图5.43 树 F G D H

图5.42双亲链表 I 20 一棵具有n个结点的二叉树,若它有n0个叶子结点,则该二叉树上度为1的结点n1=_______. 21 若一棵二叉树的叶子数为n0,则该二叉树中左,右子树皆非空的结点个数为_____. 22 设n0为哈夫曼树的叶子结点数目,则该哈夫曼树共有_____个结点.

23 若以{4,5,6,7,8}作为叶子结点的权值构造哈夫曼树,则其带权路径长度是_____. 24 如果结点A有3兄弟,而且B是A的双亲,则B的度为_____. 25 高度为h的二叉树中叶子结点的数目至多为______.

26 具有n个结点的二叉树,采用二叉链表存储,共有___个空链域. 27 利用树的孩子兄弟表示法存储,可以将一棵树转换成___. 28 二叉树的线索化实质是将二叉链表中的____改为___.

29 在一棵树中,___结点没有前驱结点,其余每个结点有且只有一个____,可以有任意多个_____结点. 30 二叉树有不同的链式存储结构,其中最常用的是___与____.

31 对于一棵完全二叉树,设一个结点的编号为i,若它的左孩子结点存在,则其编号为____;若右孩子结点存在,则其编号为___;

而双亲结点的编号为_____.

32 对于一棵具有n个结点的二叉树,对应二叉链表中指针总数为___个,其中____个用于指向孩子结点,____个指针空闲者.

33 一棵左右子树均不空的二叉树在先序线索化后,其空指针域有____个.

34 用一维数组存放一棵完全二叉树:ABCDEFGHIJKL,则后序遍历该二叉树的结点序列为_____. 35 在图5.43的树中，结点H的祖先为_____.

36 深度为k的完全二叉树,其前k-1层共有___个结点.

37 对任何二叉树,,若度为2的结点数为n2,则叶子数n0=___.

38 具有n个结点的完全二叉树,若按层次从上到下,从左到右对其编号(根结点为1),则编号最大的分支结点序号是____,编号

最小的分支结点序号是____.

39 结点最少的树是_____,结点最少的二叉树是____.

40 若二叉树的一个叶子结点是某子树中根遍历序列中的第一个结点,则它必然是该子树后根遍历序列中的____个结点.

41二叉树通常有____存储结构和_____存储结构. 42 具有n个结点互不相似的二叉树的数目为_____.

43 哈夫曼树是带权路径长度______的树,通常权值较大的结点离根_____.

二 判断题

1 完全二叉树的某结点若无左孩子,则它必是叶结点.

2二叉树中,具有两个子女结点的中序后继结点最多只能有一个子女. 3 存在这样的二叉树,对它采用任何次序的遍历,结果相同. 4二叉树就是结点度为2的树.

5二叉树中不存在度大于2的结点,当某个结点只有一棵子树时无所谓左右之分. 6 任何一棵二叉树都可以不用栈实现前序线索树的前序遍历. 7 对任何二叉树的后序线索树进行后序遍历时都必须用栈.

8 一棵有n(n≥1)个结点的d叉树,若用多重链表表示,树中每个结点都有d个链域,则在树的nd个链域中,有n(d-1)+1个是

空链域,只有n-1个是非空链域.

9 一般来说,若深度为k的n个结点的二叉树具有最小路径长度,那麽从根结点到第k-1层具有最多的结点数为k-1

2,余下的

k-1

n-2+1个结点在第k层的任一位置上.

10 若有一个结点是某二叉树子树的中序遍历序列中的最后一个结点,则它必是该子树的前序遍历序列中的最后一个结点.

11若有一个结点是某二叉树子树的前序遍历序列中的最后一个结点,则它必是该子树的中序遍历序列中的最后一个结点.

12 已知二叉树的前序遍历序列和后序遍历序列并不能唯一地确定这棵树,因为不知道树的根结点是哪一个. 13 在哈夫曼编码中,当两个字符出现的频率相同时,其编码也相同,对于这种情况应作特殊处理. 14 对n个结点的二叉树用递归程序进行中序遍历时,最坏情况下要附加n个辅助存储空间.

k-1

15 当k≥1时,高度为k的二叉树至多有2个结点.

16 一棵含有n个结点的完全二叉树,它的高度是?log2n??1.

17 ( 101 , 88 , 46 , 70 , 34 , 39 , 45 , 58 , 66 , 10 )是堆. 18 将一棵树转换成二叉树后,根结点没有左子树. 19 用树的前序遍历和中序遍历可以导出数的后序遍历.

20 即使对不含相同元素的同一输入序列进行两组不同的,合法的入栈和出栈组合操作,所得的输出序列也一定相同.

21 哈夫曼树是带权路径长度最短的树,路径上权值较大的结点离根较近. 22 中序遍历一棵二叉排序树的结点就可得到排好序的结点序列. 23 将一棵树转换成二叉树后,根结点没有左子树. 24 用树的前序遍历和中序遍历可以导出树的后序遍历.

25 哈夫曼树是带权路径长度最短的树,路径上权值较大的结点离根较近. 26 在叶子数目和权值相同的所有二叉树中,最优二叉树一定是完全二叉树. 27 后序遍历森林和中序遍历与该森林相对应的二叉树其结果不同.

28 若一个二叉树的树叶是某子树的中序遍历序列的第一个结点,则它必是该子树的后序遍历序列中的第一个结点.

29 不使用递归也能实现二叉树前序,中序和后序遍历.

30 对于后序线索二叉树要找它的任一结点的后继有时是很困难的,因此还需要使用栈. 31 在二叉树中,具有一个子女的父结点,在中序遍历中,它没有后继子女结点. 32 中序线索二叉树的优点之一是便于在中序下查找前驱结点和后继结点. 33前序遍历森林和前序遍历与该森林相对应的二叉树其结果不同.

34 二叉树中每个结点有两个子女,而对一般的树则无此限制,因此二叉树是树的特殊情形. 35 用一维数组存储二叉树时,总是以前序遍历顺序存储结点.

36 一棵左右子树均不空的二叉树在先序线索化后,其空指针域数为n-1.

三 选择题

1 一棵非空的二叉树的先序遍历序列与后序遍历序列正好相反,则该二叉树一定满足______.

A) 所有的结点均无左孩子 B) 所有的结点均无右孩子 C)只有一个叶子结点 D)是任意一棵二叉树 2 一棵完全二叉树上有1001个结点，其中叶子结点的个数是_______. A) 250 B)500 C) 254 D) 505 E)以上答案都不对

3 以上说法正确的是____.

A) 若一个树叶是某二叉树前序遍历序列中的最后一个结点,则它必是该子树后序遍历序列中的最后一个结点 B) 若一个树叶是某二叉树前序遍历序列中的最后一个结点,则它必是该子树中序遍历序列中的最后一个结点 C) 在二叉树中,具有两个子女的父结点,在中序遍历序列中,它的后继结点最多只能有一个子女结点 D) 在二叉树中,具有两个子女的父结点,在中序遍历序列中,它没有后继子女结点 4 以下说法错误的是______.

A) 哈夫曼树是带权路径长度最短的树,路径上权值较大的结点离根较近.

B) 若一个二叉树的树叶是某子树的中序遍历序列的第一个结点,则它必是该子树的后序遍历序列中的第一个

结点.

C) 已知二叉树的前序遍历序列和后序遍历序列并不能唯一地确定这棵树,因为不知道树的根结点是哪一个. D) 在前序遍历二叉树的序列中,任何结点其子树的所有结点都是直接跟在该结点之后的. 5 二叉树在线索化后,仍不能有效求解的问题是_____.

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

6 任何一棵二叉树的叶结点在前(先)序,中序和后序遍历序列中的相对次序___. A) 不发生变化 B) 发生变化 C)不能确定

7 设A,B为一棵二叉树上的两个结点.在中序遍历时,A在B前面的条件是____. A) A在B的后方 B) A在B的左方 C) A是B的祖先 D) A是B的子孙 8 在一棵具有个结点的完全二叉树中，树枝结点的最大编号为____. A) ?(n?1)/2? B) ?(n?1)/2? C) ?n/2? D) ?n/2?

9 在N个结点的线索二叉树中，线索的数目为_______. A)N-1 B)N C)N+1 D)2N

10 设深度为K的二叉树上只有度为0和度为2的结点,则这类二叉树上所含有的结点总数为__. A) K+1 B)2K C)2K-1 D)2K+1

11 设有13个值,用它们组成一棵哈夫曼树,则该哈夫曼树共有____个结点. A)13 B)12 C) 26 D) 25 12下面4 棵二叉树,都有4个叶子结点a,b,c,d,分别带权7,5,2,4,其中是哈夫曼树的是______.

c

2 a b c d d

7 5 2 4 4 a 7 b A B D 5 C d 4 2 c a 7 a 7 b 5 5 b c d

13 下面几个符号串编码集合中,不是前缀编码的是______.

A) { 0 , 10 , 110 , 1111 } B) { 11 , 10 , 001 , 101 , 0001 } C) { 00 , 010 , 0110 , 1110 } D)

{ B , C , AA , AC , ABA , ABB , ABC } 14 以下说法错误的是______.

A) 存在这样的二叉树,对它采用任何次序遍历其结点访问序列均相同 B) 二叉树是树的特殊情形

C) 由树转换成二叉树,其根结点的右子树总是空的

D) 在二叉树只有一棵子树的情况下也要明确指出该子树是左子树还是右子树

15 如果T2是由有序树T转换而来的二叉树,那麽T中结点的后序就是T2中结点的____.

A) 先序 B) 中序 C) 后序 D) 层次序

16 树的基本遍历策略可分为先根遍历和后根遍历; 二叉树的基本遍历策略可分为前序,中序和后序三种遍历.我们把由树转化

得到的二叉树称该树对应二叉树,则下面是_____正确的.

A) 树的先根遍历序列与其对应的二叉树先序遍历序列相同 B) 树的后根遍历序列与其对应的二叉树后序遍历序列相同 C) 树的先根遍历序列与其对应的二叉树中序遍历序列相同 D) 以上都不对

17 设F是一森林,B是由F变换得到的二叉树.若F中有N个非终端结点,则B中右指针域为空的结点有____个.

A) N-1 B) N C) N+1 D) N+2

18 一棵有N个结点的二叉树,按层次从上到下,同一层从左到右的顺序存储在一维数组A[1...N]中, 则二叉树中第I个结点

(I从1开始用上述方法编号)的右孩子在数组A中的位置是____.

A) A[ 2I ] (2I≤N) B)A[ 2I+1 ] (2I+1≤N) C) A[ I/2 ] D) 条件不充分,无法确定 19 将有关二叉树的概念推广到三叉树,则一棵有244个结点的完全三叉树的高度是_____. A) 4 B) 5 C) 6 D) 7

20 设树T的高度为4,其中度为1,2,3和4的结点个数分别为4,2,1,1,T中的叶子数为_____. A) 5 B) 6 C) 7 D) 8

21 下列有关二叉树的说法正确的是___.

A)二叉树的度为2 B)一棵二叉树度可以小于2 C)二叉树中至少有一个结点的度为2 D)二叉树中任一个结点的度都为2

22 某二叉树中序列为a b c d e f g ,后序序列为b d c a f g e ,则前序序列是_____. A) e g f a c b d B) e a c b d g f C) e a g c f b d D)上面的都不对

23 设森林F对应的二叉树为B,它有M个结点,B的根为P,P的右子树结点个数为N,森林F中第一棵树的结点个数是___.

A) M-N B)M-N-1 C)N+1 D)条件不充分,无法确定 50 24 图5.44所示的二叉树____是结构.

A) AVL树 B) BST树 C)判定树 D) 堆

20 95 25 在一棵度为3的树中,度为3的结点数为2个,度为2 的结点数为1个,度为1的结点数为2个,则度为0的结点数为____个. A) 4 B)5 C) 6 D) 7

10 30 56 26 在一棵具有K层的满三叉树中,结点总数为_____ . KKKKA) (3-1)/2 B) 3-1 C) (3-1)/3 D) 3 27 在一棵深度为H的完全二叉树中，所含结点的个数不小于_____. H H-1 H H-1图5.44 二叉树 A) 2 B) 2 C) 2-1 D) 2

28 在一棵具有N个结点的二叉树第I层上，最多具有____个结点.

13 A) 2 B) 2 C) 2-1 D)2

29 在下列情况中,可称为二叉树的是_____.

A) 每个结点至多有两棵子树的树 B) 哈夫曼树 C) 每个结点至多有两棵子树的有序树 D) 每个结点只有一棵右子树 E) 以上答案都不对 30 树最适合用来表示____.

A) 有序数据元素 B) 无序数据元素 C) 元素之间具有分支层次关系的数据 D) 元素之间无联系的数据 31 以下说法错误的是____.

a) 一般在哈夫曼树中,权值越大的叶子离根结点越近 b) 哈夫曼树中没有度数为1的分支结点

c) 若初始森林中共有N棵二叉树,最终求得的哈夫曼树中共有2N-1个结点

d) 若初始森林中共有N棵二叉树,进行2N-1次合并后才能剩下最终的哈夫曼树 32 以下说法错误的是____.

A) 二叉树可以是空集 B) 二叉树的任一结点都可以有两棵子树

C) 二叉树与树具有相同的树形结构 D) 二叉树中任一结点的两棵子树有次序之分 33 某二叉树的前序序列和后序序列正好相反,则该二叉树一定是_____的二叉树.

A) 空或只有一个结点 B) 任一结点无左子树 C) 高度等于其结点数 D) 任一结点无右子树

第六章 图 一 单选题

1 关键路径是事件结点网络中_____.

A) 从源点到汇点的最长路径 B) 从源点到汇点的最短路径 C) 最长的回路 D) 最短的回路 2 如图6.55所示,在下面的5个序列中符合深度优先遍历的序列有_____个. A) 5个 B) 4个 C) 3个 D) 2个

(1)a e b d f c (2) a c f d e b (3) a e d f c b (4) a e f d c b (5) a e f d b c 3 下面不正确的说法是_____. A) (1),(2),(3) B) (1) C) (1),(3) D) (2),(3) a (1)求从指定源点到其余各顶点的迪杰斯特拉最短路径算法

b 中弧上权不能为负的原因是在实际应用中无意义;

c (2)利用迪杰斯特拉算法求每一对不同顶点的最短路

e 径的算法时间是(图用邻接矩阵表示) (3)利用Floyd求每对不同顶点的算法中允许弧上

的权为负,但不能有权和为负的回路

d f 4 下面说法不正确的是______. A) (1) B) (2) C) (3) D) (1),(2) (1)在AOE-网中,减小任一关键活动上的权值后,整个工期也就相应减小; 图6.55 无向图 (2)AOE-网工程工期为关键活动上的权之和;

(3)在关键路径上的活动都是关键活动,而关键活动也必在关键路径上

5 下面哪一个方法可以判断出一个有向图中是否有环(回路)? A) 深度优先遍历 B)拓扑排序 C)求最短路径 D)求关键路径

6 已知有8个结点值为A,B,C,D,E,F,G和H的无向图,其邻接矩阵的存储结构见表6.11,由此结构从A结点开始深度优先遍历,

得到的结点序列是______.

A) ABCDGHFE B) ABCDGFHE C) ABGHFECD D) ABFHEGDC E) ABEHFGDC F) ABEHGFCD

表6.11 无向图的邻接矩阵

I I-1 I N

结

点 A B C D E F G H

结点

A 0 1 0 1 0 0 0 0

B 1 0 1 0 1 1 1 0

C 0 1 0 1 0 0 0 0 D 1 0 1 0 0 0 1 0 E 0 1 0 0 0 0 0 1 F 0 1 0 0 0 0 1 1 G 0 1 0 1 0 1 0 1 H 0 0 0 0 1 1 1 0 7 设无向图的顶点个数为n,则该无向图最多有

2

______条边. A) n-1 B) n(n-1)/2 C) n(n+1)/2 D) 0 E) n

8 用DFS遍历一个无环有向图,并在DFS算法退栈返回时打印出相应的顶点,则输出的顶点序列是_____. A) 逆拓扑有序的 B) 拓扑有序的 C) 无序的

9 在下列两种求图的最小生成树的算法中,_____算法适合于求边稀疏的网的最小生成树. A) Prim B) Kruskal

10 下面的叙述中不正确的是______.

a A) 关键活动不按期完成就会影响整个工程的完成时间

B) 任何一个关键活动提前完成,将使整个工程提前完成 C) 所有关键活动都提前完成,则整个工程将提前完成

b d e f D) 某些关键活动若提前完成,将使整个工程提前完成 11 图6.56有向图G的深度优先搜索得到的结点序列是____. c g A) a b c f d e g B) a b c g f d e C) a b c d e f g D) a b c f g d e 12 采用邻接表存储的图,其深度优先遍历类似于二叉树的_______. 图6.56 有向图 A)中序遍历 B)先序遍历 C)后序遍历 D)按层次遍历 13 采用邻接表存储的图,其广度优先遍历类似于二叉树的______. A)按层次遍历 B)中序遍历 C)后序遍历 D)先序遍历

14 一个图中包含有k个连通分量,若按深度优先(DFS)搜索方法访问所有结点,则必须调用____次深度优先遍历.

A) k B) 1 C) k-1 D) k+1

15 设有无向图G=(V,E)和G1=(V1,E1),,如G1是G的生成树,则下面不正确的是_____.

A) G1为G的连通分量 B) G1是G的无环子图 C) G1为G的子图 D) G1为G的极小连通子图且V1=V 16 以下说法正确的是_______.

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

C) 在一个有向图的拓扑序列中若顶点a在顶点b之前,则图中必有一条弧

D) 对有向图G,如果以任一顶点出发进行一次深度优先或广度优先搜索能访问到每个顶点,则该图一定是完全

图

17 下列说法不正确的是_____.

A) 无向图中的极大连通子图称为连通分量

B) 连通图的广度优先搜索中一般要采用队列来暂存刚访问过的顶点 C) 图的深度优先搜索中一般要采用栈来暂存刚访问过的顶点 D) 有向图的遍历不可采用广度优先搜索方法

2

18 具有n个顶点的有向图最多有____条边. A) n B) n(n-1) C) n(n+1) D) n 19 在有向图G的拓扑序列中,若顶点Vi在顶点Vj之前,则下列情况不可能出现的是_____.

A) G中有弧 B) G中有一条从Vi到Vj的路径 C) G中没有弧 D) G中有一条从Vj到Vi的路径

20 一个n个顶点的连通无向图,其边的个数最少为______. A) n-1 B) n C) n+1 D) nlog2n

21 下列说法正确的是________.

A)最小生成树也是哈夫曼树 B)最小生成树唯一

2

C)普里姆(Prim)最小生成树算法时间复杂度为O(n)

D)克鲁斯卡尔(Kruskal)最小生成树算法比普里姆算法更适合于边稠密的网 22 图6.57所示的拓扑排列的结果序列为______.

A E A) 125634 B) 516234 C) 123456 D) 521634

1 3

B D

2

5 6 4 C F 图6.57 有向图 图6.58 无向图

23 判定一个有向图是否存在回路,除了可以利用拓扑排序的方法外,还可以利用_____.

A) 求关键路径的方法 B) 求最短路径的Dijkstra方法 C) 深度优先遍历算法 D) 广度优先遍历算法 24 在一个具有n个结点的有向图中,若所有顶点的出度之和s,则所有顶点的入度之和为_____. A) s B) s-1 C) s+1 D) n

25 在一个无向图中,若两个顶点之间的路径长度为k,则该路径上的顶点数为_____. A) k B) k+1 C) k+2 D) 2k

26 图6.58的深度优先搜索序列为______.

A) DFS(A):ABEDCF B) DFS(A):AEFCDB C) DFS(A):ABCEDF D) DFS(A):ACBDEF 27 一个有n个顶点的无向连通图,它所含有的连通分量个数为_______. A) 0 B) 1 C) n D) n+1 28 对于一个有向图,若一个顶点的入度k1,出度为k2,则对应邻接表中该顶点单链表中的结点数为_____. A) k1 B) k2 C) k1-k2 D) k1+k2

29 对于一个有向图,若一个顶点的入度k1,出度为k2,则对应逆邻接表中该顶点单链表中的结点数为_____. A) k1 B) k2 C) k1-k2 D) k1+k2 30 对于一个无向图,下面_____的说法是正确的.

A)每个顶点的入度等于出度 B)每个顶点的度等于其入度与出度之和 C)每个顶点的入度为0 D)每个顶点的出度为0

31 为了方便地对图状结构的数据进行存取操作,则其中数据存储结构宜采用____. A)顺序存储 B)链式存储 C)索引存储 D)散列存储

二 多选题

1 如图6.59所示,从无向图的顶点1出发,对它进行深度优先遍历得到的顶点序列是(1)_____;而进行广度优先遍历得到的

序列是(2)_____.

(1) A) 1354267 B) 1347625 C) 1534276 D) 1247653 E)以上答案均不对 (2) A) 1534267 B) 1726453 C) 1354276 D) 1247653 E)以上答案均不对

1 3 2 4 ^

1 2 ^ 2

3 4 5 ^

3 4 7 4 ^

5 6 5 2 4 ^ 图6.59 无向图 图6.60 邻接表 2 从邻接矩阵A=??010??可以看出,该图共有(1)____个顶点.如果是有向图,该图共有(2)____条弧;如果是无向101??图,则共有(3)____条边.

(1) A) 9 B) 3 C) 6 D) 1 E) 以上答案均不对 (2) A) 5 B) 4 C) 3 D) 2 E) 以上答案均不对 (3) A) 5 B) 4 C) 3 D) 2 E) 以上答案均不对

3 对于一个具有n个顶点和e条边的无向图,若采用邻接表表示,则表向量的大小为(1)____,所有顶点的邻接表的结点总数为(2)____.

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

4 已知一有向图的邻接表存储结构如图6.60所示.则按深度优先遍历算法从顶点V1出发,所得到的顶点序列为(1)____;按广度优先

遍历算法从顶点V1出发,所得到的顶点序列为(2)_____.

A) V1,V2,V3,V5,V4 B)V1,V2,V3,V4,V5 C)V1,V3,V4,V5,V2 D)V1,V3,V2,V4,V5 E)V1,V2,V4,V5,V3 5 给定一无向图G如图6.61所示,下列哪些是由顶点1 1 12 出发的深度优先搜索序列_____.

1 2 A) 1243 B) 1234 C) 1342 D) 1324 E)1423 15 2 3 5 6 图的应用算法有_____.

A) 克鲁斯卡尔算法 B) 哈夫曼算法 C)迪杰斯特拉算法 4 20 3 D) 欧几里得算法 E) 拓扑排序算法 6 10 图6.61 无向图

8 4 5 三 填空题

1 如果含n个顶点的图形成一个环,则它有___棵生成树.

4 9 2 一个非连通无向图,共有28条边,则该图至少有___个顶点.

6 3 具有10个顶点的无向图,边的总数最多为____.

4 对于如图6.62所示的图,用Prim算法从顶点①开始求最小生成树,按次序产生的边为___, 图6.62 无向图 共____条边; 用Dijkstra算法产生的边的次序是_____.(注: 边用( i,j )的形式表示) 5 在有n个顶点的有向图中,每个顶点的度最大可达_____.

V1 6 设图G有n个顶点e条边，采用邻接表存储，则拓扑排序算法的时间复杂度为____. 7克鲁斯卡尔算法的时间复杂度为____,它对___图较为适合.

8 遍历图的过程实质是____.Breadth-first search 遍历图的时间复杂度为____, V3 V2 depth-first search遍历图的的时间复杂度为___,

两者不同之处在于_____,反映在数据结构上的差别是_____. 9 设有向图G如图6.63所示.(1)写出所有的拓扑序列:_____.

V4 (2)添加弧___后,则仅可能有唯一的拓扑序列. 10 遍历图的基本方法有深度优先搜索和广度优先搜索, 图6.63 无向图 其中_____是一个递归过程.

11 若一个连通图中每个边上的权值均不同,则得到的最小生成树是____的.

12 设图G有n个顶点和e条边,则对用邻接矩阵表示的图进行深度或广度优先搜索遍历时的时间复杂度为____,而用邻接表

表示的图进行深度或广度优先搜索遍历时的时间复杂度为____;图的深度或广度优先搜索遍历时的时间复杂度为____.

13 深度优先搜索遍历类似于树的____遍历, 它所用到的数据结构是___;

广度优先搜索遍历类似于树的____遍历,它所用到的数据结构是_____. 14 一个图的____表示法是唯一的,而___表示法是不唯一的.

15 对无向图,若它有n个顶点e条边,则其邻接表中需要____个结点.其中,____个结点构成邻接表,___个结点构成顶点表 .

16 有n个顶点的有向图,至少需要____条弧才能保证是连通的.

17 求从某源点到其余各顶点的Dijkstra算法,当图的顶点数为10,用邻接矩阵表示图时计算时间约为10ms,则

当图的顶点数

为40时,计算时间为___ms.

18 一个连通图的_____是一个极小连通子图.

19 在AOE网中,从源点到汇点路径上各活动的时间总和最长的路径称为____. 20 n个顶点的连通图用邻接矩阵表示时,该矩阵至少有____个非零元素. 21有向图中的结点前驱后继关系的特征是____.

22 Prim算法适用于求____的网的最小生成树;Kruskal算法适用于求_____网的最小生成树. 23 AOV网是_____有向图.

24 有向图的极大强连通子图称为____

25 在一个具有n个顶点的无向完全图中,包含有____条边;在一个具有n个顶点的有向完全图中,包含有____条边.

26 根据图的存储结构进行某种次序的遍历,得到的顶点序列是____的.

27 对含有n个顶点e条边的无向连通图,利用Prim算法生成最小生成树的时间复杂度为_____. 利用Kruskal算法生成最小生成树的时间复杂度为_____.

28 若无向图G的顶点度数最小值大于等于____时,G至少有一条回路. 29 连通分量是无向图中的___连通分量.

30 从源点到汇点长度最长的路径称关键路径,该路径上的活动称____.

四 判断题

1 在n个结点的无向图中,若边数>n-1,则该图必是连通图.

2 若一个有向图的邻接矩阵中对角线以下元素均为0,则该图的拓扑有序序列必定存在. 3 已知一有向图的邻接矩阵An×n ,其顶点vi的入度为

?[j,i].

j?1nn 4 已知一有向图的邻接矩阵An×n ,其顶点vi的出度为

?[j,i].

j?1 5 任何AOV网拓扑排序的结果都是唯一的. 6有回路的图不能进行拓扑排序.

m

7 用邻接矩阵A表示图,判定任意两个结点vi和 vj之间是否有长度为m的路径相连,则只要检查A的第i行第j列的元素

是否为0即可.

8 对于一个有向图,除了拓扑排序方法外,还可以通过对有向图进行深度优先遍历的方法来判断有向图中是否有环存在.

9 一个图的广度优先搜索树是唯一的.

10 图的深度优先搜索序列和广度优先搜索序列不是唯一的.

11 有n个顶点的无向图,采用邻接矩阵表示,图中的边数等于邻接矩阵中非零元素之和的一半. 12 若连通图上各边权值均不相同,则该图的最小生成树是唯一的.

13 无向图的邻接矩阵一定是对称矩阵,且有向图的邻接矩阵一定是非对称矩阵.

14 用邻接矩阵存储一个图时,所占用的存储空间大小只与图中结点的个数有关,而与图的边数无关. 15 邻接表只能用于存储有向图,而邻接矩阵则可以存储有向图和无向图. 16 无向图的邻接矩阵是对称的,因此可只存储邻接矩阵的上(或下)三角阵. 17连通分量是无向图中的极小连通子图.

18强连通分量是有向图中的极大强连通子图.

19 如果连通网中存在相同权值的边,则最小生成树不唯一. 20 用邻接矩阵表示图时,矩阵元素的个数与边的条数有关.

第七章 查找 一 选择题

1 设有一个按各元素的值排好序的线性表且长度大于2,对给定的值K,分别用顺序查找法和二分查找法查找一个与K相等的元素,

比较次数分别是s和b;在查找不成功的情况下,正确的s和b的数量关系是____. A) s=b B) s>b C) s

3 关于杂凑查找说法不正确的有___个. A) 1 B) 2 C) 3 D) 4 (1) 采用链地址解决冲突时,查找一个元素的时间是相同的;

(2) 采用链地址解决冲突时,若规定插入总是在链首,则插入任一个元素的时间是相同的; (3) 采用链地址解决冲突易引起聚集现象; (4) 用哈希法不易产生聚集

4 对有18个元素的有序表作二分(折半)查找,则查找A[3]的比较序列的下标为____. A) 1,2,3 B) 9,5,2,3 C) 9,5,3 D) 9,4,2,3

5 若在线性表中采用折半查找法查找元素,该线性表应该____.

A)元素按值有序 B)采用顺序存储结构 C)元素按值有序且采用顺序存储结构 D)元素按值有序且采用链式存储结构

6 在关键字随机分布的情况下,用二叉排序树的方法进行查找,其查找长度与_____量级相当. A) 顺序查找 B) 折半查找 C) 前两者均不正确

8 假定有K个关键字互为同义词,若用线性探测法把这K个关键字存入散列表中,至少要进行___次探测. A) k-1 B) k C) k+1 D) k(k+1)/2

9 具有5层结点的AVL树至少有____个结点. A) 10 B) 12 C) 15 D) 17

11 设散列地址空间0~m-1,k为关键字,用P去除k,将余数作为k的散列地址,即h(k)=k%P,为了减少发生冲突的可能性,

一般取P为_____. A)小于m的最大奇数 B)小于m的最大素数 C)小于m的最大偶数 D)小于m的最大合数

12 设散列表的长m=14,散列函数h(k)=k,表中已有4个记录(如图7.61所示),如果用二次探测散列来处理冲突,则关键字

为49的记录其存储地址是_____. A) 8 B) 3 C) 5 D) 9

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

15 38 61 84 图7.61 散列表

13 从具有n个结点的二叉排序树中查找一个元素时,最坏情况下的时间复杂度为_____.

2

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

14 在采用线性探测法处理冲突的闭散列表上，假定装填因子α的值为0.5,则查找任一元素的平均查找长度为____.

A) 1 B) 1.5 C) 2 D) 2.5

15在采用链接法处理冲突的开散列表上，假定装填因子α的值为4,则查找任一元素的平均查找长度为____. A) 3 B) 3.5 C) 4 D) 2.5 17 以下说法错误的是______.

A) 散列表存储的基本思想是由关键码值决定数据的存储地址

B) 散列表的结点中只包含数据元素自身的信息,不包含任何指针 C) 装填因子是散列法的一个重要参数,它反映了散列表的装填程度

D) 散列表的查找效率主要取决于散列表造表时选取的散列函数和处理冲突的方法

18 设有一个用线性探测法解决冲突得到的散列表如图7.62所示: 散列函数为H(k)=k,若要查找元素14 ,探测的次数是___. A) 8 B) 9 C) 3 D) 6 0 1 2 3 4 5 6 7 8 9 10 13 25 80 16 17 6 14 图7.62 散列表

19 设散列函数为H(k)=k%7,一组关键码为23,14,9,6,30,12,18,散列表T的地址空间为0~6,用线性探测法解决冲突,依次将这组

关键码插入T中,则得到的散列表为____. 0 1 2 3 4 5 6

0 1 2 3 4 5 6 A) B) 14 6 23 9 18 30 12 14 18 23 9 30 12 6

C) D) 0 1 2 3 4 5 6

0 1 2 3 4 5 6

6 23 30 14 18 12 9

14 12 9 23 30 18 6

20 散列表的平均查找长度_______.

A) 与处理冲突方法有关而与表的长度无关 B) 与处理冲突方法无关而与表的长度有关 C) 与处理冲突方法有关而与表的长度有关 D) 与处理冲突方法无关而与表的长度无关 21 在采用线性探测法处理冲突所构成的闭散列表上进行查找,可能要探测多个位置,在查找成功的情况下,所探测的这些

位置上的键值是_____. A) 一定都是同义词 B) 一定都不是同义词 C) 都不同 D) 不一定都是同义词

+

22 m路B树是一棵(1)_____,其结点中关键字最多为(2)______个,最少为(3)____个. (1) A) m路平衡查找树 B) m路平衡索引树 C) m路Ptrie树 D) m路键树

(2) E) m-1 F) m G) m+1 H) ?m2?1? (3) I) ?m2? J)?m2?1?

23 在构造哈希表的过程中,不可避免地会出现冲突,通常解决它的方法有______.

A)平方取中法 B)开放地址法 C)随机探查法 D) 再哈希法 E)拉链分散法(链地址法) 24 散列函数是指定关键字与存储地址间的映射关系,常用的构造方法有_______.

A)自身函数(直接定址)法 B)折叠函数法 C)平方取中法 D) 链接表法 E)除留余数法 25 如果要求一个线性表既能较快地查找,又能适应动态变化的要求,则可采用的查找方法是____. A)分块查找 B)顺序查找 C)折半查找 D)基于属性查找

26 有数据{53,30,37,12,45,24,96},从空二叉树开始逐个插入数据来形成二叉排序树,若希望高度最小,则应选择

下面哪个序列输入_____.

A) 45,24,53,12,37,96,30 B) 37,24,12,30,53,45,96 C) 12,24,30,37,45,53,96 D) 30,24,12,37,45,96,53

27 利用逐点插入法建立序列{50,72,43,85,75,20,35,45,65,30}对应的二叉排序树以后,查找元素35要进行___元素之间的比较.

A) 4次 B) 5次 C) 7次 D) 10次

28 在非空m阶B-树上,除根结点以外的所有其他非终端结点______.

A)至少有?m/2?棵子树 B)至多有?m/2?棵子树 C)至少有?m/2?棵子树 D)至多有?m/2?棵子树 29 在顺序表(n足够大)中进行顺序查找,其查找不成功的平均长度是_____. A) (n+1)/2 B) n/2+1 C) n D) n+1

30 采用二分检索方法检索长度为n的有序表,检索每个元素时的平均比较次数与对应的判定树高度(设高度≥2)相比较为____.

A) 小于 B) 大于 C) 等于 D) 大于等于 31 对线性表进行二分检索时,要求线性表必须____.

A)以顺序存储方式存储 B)以链式存储方式存储 C)以顺序存储方式存储且数据有序 D)以链式存储方式存储且数据有序

34 在散列查找中,平均查找长度主要与___有关.

A)散列表长度 B)散列元素个数 C)装填因子 D)处理冲突方法

35 若根据查找表建立长度m的闭散列表并采用二次探测处理冲突,假定对一个元素第一次计算的散列地址为d,则第4 次

计算的散列地址机为____. A) (d+1)%m B) (d-1)%m C) (d+4)%m D) (d-4)%m 36 以下说法正确的是____.

A) 数字分析法需事先知道所有可能出现的键值及所有键值的每一位上各数字分布情况,并且键值的位数比散列地址的位数多.

B) 除余法要求事先知道全部键值

C) 平方取中法需要事先掌握键值的分布情况 D) 随机数法适用于键值不相等的场合 37 分块查找的时间效率______.

A)低于二分查找 B)高于顺序查找而低于二分查找 C) 高于顺序查找 D)低于顺序查找而高于二分查找 38 在一个具有n个结点的单链表中查找值为m的某结点,若查找成功,则平均比较_____个结点. A) n B) n/2 C) (n-1)/2 D) (n+1)/2 39 下述命题_____是不成立的.

A)m阶B-树中的每一个结点的子树个数都小于或等于m

B) m阶B-树中的每一个结点的子树个数都大于或等于?m/2?

C)m阶B-树中的任何一个结点的子树高度都相等

D) m阶B-树具有K个子树的非叶子结点含有K-1个关键字

二 填空题

1 对有7 个元素的有序表A[ 1…17 ]作二分查找,在查找其等于A[ 8 ]的元素时,被比较的元素下标依次是_____.

2 假定有K个关键字互为同义词,若用县性探测再散列法把这个K个关键字存入散列表中,至少要进行____次探测.

3 顺序查找n个元素的顺序表，若查找成功,则比较关键字的次数最多为_____次;但使用监视哨时,若查找失败,则比较

关键字的次数为___次.

4 构造哈希函数的方法有_____,____,____等.

5 向一棵m阶B-树插入操作时,当结点的关键字数为___时,则要分裂该结点;删除时结点中关键字数为____时,可能需要同

左过右兄弟合并.

6 高度为5(除叶子层之外)的三阶B-树至少有____个结点 . 7 高度为8的平衡二叉树的结点数至少有___个.

8 具有n个关键字的B-树的查找犁镜长度不会大于_____.

9 在n个记录的有序顺序表中进行折半查找,最大的比较次数是_____.

10 用二分法查找一个线性表时,该线性表必须具有的特点是____ ;而分块查找法要求将待查找的表均匀地分为若干块且块

中诸记录的顺序可以是任意的,但块与块之间_______..

11 分块检索中，若索引表各块内均用顺序查找,则有900个元素的线性表分成_____块最好;若分成25块,其平均查找长度为____.

12 对于二叉排序树的查找,若根结点元素的键值大于被查元素的键值,则应该在二叉树的_____上继续查找. 13 若一个待散列存储的线性表长度为n用于散列的散列表长度为m,则m应____n,装填因子α为_____.

14 在二叉排序树上插入新结点时,不必移动其他结点,仅需使树叶结点的指针由____指向新结点即可.

15 设线性表(a1,a2,…,a500)元素的值由小到大排列,对一个给定的K值用二分法查找线性表,在查找不成功的情况下至多

需要比较____次.

16 二叉排序树的查找效率与树的形态有关.当二叉排序树退化为单支树时,查找算法退化为____查找,其平均查找长度上升为___.

17 设有两个散列函数H1(K)=K和H2(K)=K+1,散列表为T[ 0…12 ],用双重散列解决冲突.函数H1用来计算散列地址,当

发生冲突时,H2作为计算下一个探测地址增量,假定在某一时刻表T的状态如图7.63所示. 下一个被插入的关键字是42,则其插入的位置是______. 0 1 2 3 4 5 6 7 8 9 10 11 12

80 85 34 图7.63 散列表T

18 二叉排序树的查找长度不仅与___有关,也与二叉排序树的___有关.

19 按13,24,37,90,53的次序形成二叉平衡树,则该二叉平衡树的高度是__,其根为___.左子树中的数据是___,右子树中的数据是__.

20 在二叉平衡树上删除一个结点后可以通过旋转使其平衡,最坏情况下需___次旋转.

21 一个无序序列可以通过构造一棵____树而变成一个有序序列,构造树的过程即为对无序序列进行排序的过程.

22 在一棵有n个结点的非平衡二叉树中进行查找,平均时间复杂度的上限(即最坏情况平均时间复杂度)为

___.

23已知有序表为(12,18,24,35,47,50,62,83,90,115,134),当用二分法查找90时,需进行___次查找可确定成

功;查找47 时需进行__

次查找可确定成功;查找100时, 需进行___次查找才能确定不成功.

24 假设有n个关键字,它们具有相同哈希函数值,用线性探测法解决冲突,把这n个关键字散列到大小为n的

地址空间中,共计

需要做___次插入和探测操作.

25 ___法构造的哈希函数肯定不会发生冲突.

26 在分块检索中，对256个元素的线性表分成____块最好,每块的最佳长度是_____;若每块的长度为8,其平均检索长度为___.

27 在顺序表上施行的三个查找算法,就平均查找长度来看,____最小,____最大. 28 在一棵二叉排序树上实施___遍历后,其关键字序列是一个有序表.

29 对长度为n的查找表进行查找时,假定查找第i个元素的概率为Pi,查找长度(即在查找过程中依次同有关元素比较的总次数)为Ci,则在查找成功情况下的平均长度的计算公式为____.

30 一棵深度为h的B-树,任一个叶子结点所处的层数为____,当向B-树插入一个新关键字时,为检索插入位置需读取____个结点.

31 二分查找的存储结构仅限于____,且是____. 32 对闭散列表来说,___的方法就是处理冲突的方法.

33 平衡二叉排序树上任一结点的平衡因子只可能是____,____或_____.

34 顺序查找不要求关键字______,其ASL(平均查找长度)为____;折半查找要求关键字_____,其ASL为______.

35 用二叉排序树查找,在最坏情况下,ASL为____;当二叉排序树是一棵平衡二叉树时,ASL为_____. 36 在B-树上进行查找的过程是一个____和____交叉进行的过程. 37 ___查找法的平均查找长度与元素个数n无关.

三 判断题

1 用向量和单链表表示的有序表均可使用折半查找方法来提高查找速度.

2 有n个数存放在一维数组A[ 1..n ]中,在进行顺序查找时,这n个数的排列有序或无序其平均查找长度不同.

3在任意一棵非空二叉树中,删除某结点后又将其插入,则所得二叉排序树与删除前原二叉排序树相同. 4 若散列表的负载因子α<1,则可避免碰撞的产生.

5 二叉树中除叶子结点外,对于任一结点X,其左子树根结点的值小于该结点(X)的值,其右子树结点的值不小于该结点(X)的值,

则此二叉树一定是二叉排序树.

6 折半查找是先确定待查有序表记录的范围,然后逐步缩小范围,直到找到或找不到该记录为止. 7 二叉排序树的任意一棵子树中,关键字最小的结点必无左孩子,关键字最大的结点必无右孩子.

8 无论是顺序表还是树表,其结点在表中的位置与关键字之间存在着唯一的对应关系;因此进行查找时,总是实施一系列的和

关键字的比较操作来体现.

9 就平均查找长度而言,分块查找最小,折半查找次之,顺序查找最大. 10 散列表的结点中包含数据元素自身的信息,不包含任何指针.

11 对二棵具有相同关键字集合而形状不同的二叉排序树,按中序遍历它们得到的序列顺序是一样的. 12 在二叉排序树上删除一个结点时,不必移动其他结点,只要将该结点的父结点的相应指针域置空即可. 13 在所有结点的权都相等的情况下,只有最下面两层结点的度数可以小于2,其它结点的度数必须等于2的二叉排序树才是 最佳二叉树

14 任一二叉排序树的平均查找时间都小于用顺序查找法查找同样结点的线性表的平均查找时间 15 哈希表的查找效率主要取决于哈希表造表时选取的哈希函数和处理冲突的方法 16在采用线性探测法处理冲突的散列表中,所有同义词在表中一定相邻 17对二叉排序树的查找都是从根结点开始的,则查找失败一定落在叶子上 18顺序查找法适用于存储结构为顺序或链接存储的线性表。

19 装填因子是散列表的一个重要参数，它反映散列表的装满程度。 20中序遍历一棵二叉树的结点就可得到排好序的结点序列。

21 AVL树是一棵二叉树，该树上任一结点的平衡因子的绝对值不大于1。 22 二叉排序树的查找和折半查找时间的性能相同。

23 散列法存储的基本思想是由关键码的值决定数据的存储地址。

24 虽然关键字序列的顺序不一样，但依次生成的二叉排序树是一样的。

25 在所有结点的权都相等的情况下，具有平衡特性的二叉排序树一定是最佳二叉排序树。 26 m阶B-树具有K个子树的非叶子结点含有K-1个关键字。

第八章 排序 一 单选题

1 以下序列不是堆的是_____.

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)

2 在文件”局部有序”或文件长度较小的情况下,最佳内部排序方法是_____. A)直接插入排序 B)冒泡排序 C)简单选择排序 D)归并排序

3 在下列算法中,____算法可能出现:在最后一趟开始之前,所有的元素都不在其最终的位置上. A)堆排序 B)冒泡排序 C)插入排序 D)快速排序

4从未排序的序列中依次取出一个元素与已排序序列中的元素依次进行比较,然后将其放在排序序列的合适位置,该排序方法

称为____排序法. A)插入 B)选择 C)希尔 D)二路归并

5 排序趟数与序列原始状态有关的排序方法是___排序法. A)插入 B)选择 C)冒泡 D)快速 6 下面给出的4种排序法中,___排序是不稳定排序法. A)插入 B)冒泡 C)二路归并 D)堆

7 快速排序在最坏情况下时间复杂度是O(n),比____排序的性能差. A)堆 B)起泡 C)选择 8若需在O(nlog2n)的时间内完成对数组的排序,且要求排序是稳定的,则可选择___排序法. A)快速B)堆C)归并D)直接插入

9 下列二叉树中,___不是堆.

A) B) 10 10

1412

1220

201816

1416 18

D) 10

C) 101216

141412

181620

1820

10 对任意的7 个关键字排序,至少需要进行____次关键字之间的两两比较. A) 13 B) 14 C) 15 D) 16 E) 17

11 已知待排序的n个元素可分为n/k个组,每个组包含k个元素,且任一组内的各元素均分别大于前一组内的所有元素

和小于后一组内的所有元素,若采用基于比较的排序,其时间下界应为______. A) O(klog2k) B) O(klog2n) C) O(nlog2k) D) O(nlog2n)

12 对给出的一组关键字{14,5,19,20,11,19}.若按关键字非递减排序,第一趟排序结果为{14,5,19,20,11,19},问采用的是___排序.

A)简单选择 B)快速 C)希尔 D)二路归并

13 就排序算法所用的辅助空间而言,堆排序,快速排序,归并排序的关系是____ A) 堆排序＜快速排序＜归并排序 B) 堆排序＜归并排序＜快速排序 C) 堆排序＞归并排序＞快速排序 D) 堆排序＞快速排序＞归并排序 E) 以上答案都不对

14 假设某文件经过内部排序得到27个初始归并段，若要使多路归并3趟完成，则应取归并的路数为______. A) 2 B) 3 C) 4 D) 5

15 下面排序方法中,关键字比较次数与记录的初始排列无关的是____排序. A)希尔 B)冒泡C)直接插入 D)直接选择

16 对记录的关键字集合key={50,26,38,80,70,90,8,30,40,20}进行排序,各趟排序结束时的结果为: 50 26 38 80 70 90 8 30 40 20 50 8 30 40 20 90 26 38 80 70 26 8 30 40 20 80 50 38 90 70 8 20 26 30 38 40 50 70 80 90

其使用的排序方法是____排序. A)快速 B)基数 C)希尔 D)归并

17 一组记录的关键字为{45,80,55,40,42,85},则使用堆排序的方法建立的初始堆为_____.

A) 80,45,50,40,42,85 B) 85,80,55,40,42,45 C) 85,80,55,45,42,40 D) 85,55,80,42,45,40

2

18一组记录的关键字为{25,50,15,35,80,85,20,40,36,70},其中含有5 个长度为2的有序表,用归并排序方法对该序列

进行一趟归并后的结果为___.

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,50,35,80,85,20,36,40,70 D) 15,25,35,50,80,20,36,40,70,85

19 在对n个元素进行冒泡排序的过程中,最好情况下的时间复杂度为____. A) O(1) B)O(Log2n) 2

C)O(n) D)O(n)

20 在对n个元素进行快速排序的过程中,第一次划分最多需要移动____次元素(包括开始将基准元素移到临时变量的那一次).

A) n/2 b) n-1 C) n D) n+1

21 下述几种排序方法中,要求内存量最大的是____排序. A)插入 B)选择 C)快速 D)归并

2

22 下面排序方法中,时间复杂度不是O(n)的是___排序. A)直接插入 B)二路归并 C)冒泡 D)直接选择

23 一个序列中有0000 个元素,若只想得到其中前10 个最小元素,最好采用____排序. A) 快速 B) 堆 C) 插入 D)二路归并

24 对下列4个序列用快速排序方法进行排序,以序列的第一个元素为基准进行划分.在第一趟划分过程中,元素移动次数

最多的是序列 _____.

A) 70,75,82,90,23,16,10,68 B) 70,75,68,23,10,16,90,82 C) 82,75,70,16,10,90,68,23 D)

23,10,16,70,82,75,68,90

25 在对n个元素的序列进行排序时,堆排序所需要的附加存储空间是___. A) O(log2n) B) O(1) C) O(n) D) O(nlog2n)

26 对下面四种排序方法,在排序中关键字比较次数同记录初始排列无关的是____. A)直接插入 B) 二分法插入 C) 快速排序 D) 归并排序

2

27 采用简单选择排序,比较次数与移动次数分别是___. A) O(n),O(log2n) B) O(log2n),O(n) C)

2

O(n),O(n) D) O(nlog2n), O(n)

2

28 归并排序中,归并的趟数是____. A) O(n) B) O(log2n) C) O(nlog2n) D) O(n)

29 在待排序的元素序列基本有序的前提下,效率最高的排序方法是____排序. A)插入 B)选择 C)快速 D)归并

30 直接插入排序在最好情况下的时间复杂度为_____. A) O(log2n) B) O(n) C) O(nlog2n) D) 2

O(n)

31 对外部排序的K路平衡归并,采用败者树时,归并效率与K____. A)有关 B)无关 32将两个各有n个元素的有序表归并成一个有序表,其最少的比较次数是___. A) n B) 2n-1 C) 2n D) n-1

33 下列排序算法中稳定的排序算法是___排序. A) 堆 B) 快速 C) 基数 D) 希尔

34 就平均性能而言,目前最好的内排序方法是___排序. A) 冒泡 B) 希尔插入 C) 交换 D) 快速 35 快速排序____在情况下不利于发挥其长处.

A)待排序数据量太大 B)待排序数据相同值过多 C)待排序数据已基本有序 D)待排序数据值差过大 36 一组记录的关键字为{45,80,55,40,42,85},则使用快速排序方法并以第一个记录为基准得到一次划分结果是___.

A) 40,42,45,55,80,85 B) 42,40,45,80,55,85 C) 42,40,45,55,80,85 D) 42,40,45,85,55,80 37若对n个元素进行直接插入排序,则进行第i趟排序过程前，有序表中的元素个数为____. A) i B) i+1 C) i-1 D) 1

38若对n个元素进行直接选择排序过程中,第i趟需从____个元素中选择出最小值元素. A) n-i+1 B) n-i C) i D) i+1

39若对n个元素进行直接选择排序,则进行任一趟排序的过程中,为寻找最小值元素所需要的时间复杂度为____.

2

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

40 在下列排序方法中,空间复杂度为O(log2n)的方法是___排序. A)直接选择 B)归并 C)插入 D)选