数据结构学位考试试题

1、数据结构课程学位考试试题（参考答案在题后）判断题：判断下列各小题叙述的正误。对，在题号后的括号内填入“”；错，在题号后填入“×”。1、数据的最小单位是数据项。.( )2、多重表文件中主索引为非稠密索引，次索引为稠密索引。.( )3、通常数据结构在计算机中有四种不同的表示方法分为顺序存储结构、链式存储结构、索引存储、文件存储。 . .( × )4、算法具有输入、输出、可行性、稳定性、有穷性五个特性。 .( × )5、数据的基本单位是数据项。.( ×)6、算法的复杂度分为时间复杂度和效率复杂度。.(× )7、性质相同的数据元素的集合成为数据对象。

2、.( )8、所有结点按 1 对 1 的邻接关系构成的整体就是集合结构。.( ×)9、散列文件不能顺序存取、只能按关键字随机存取。.( )10、数据的基本单位是数据元素。.( )11、 B+树中的 K 个孩子的结点必有K 个关键字。.( )12、 B+树中的 K 个孩子的结点必有K 个关键字。 . .( )13、倒排表的索引项中没有头指针和链表长度项。.( )14、磁带是顺序存取的外存储设备。. .(×)15、索引文件只能是磁盘文件。( )16、顺序文件只适宜于顺序存取。. .(× )17、磁带是顺序存取的外存储设备。.( ×)18、线性的数据结构可以顺序

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

4、须占用一片连续的存储单元。.(× )28、链接表上做删除和插入运算时的平均时间复杂度都是O(n) .( × )29、线性表中的每个结点最多只有一个前驱和一个后继。 .( )30、顺序表上做删除和插入运算时的平均时间复杂度都是O(n) .( )31、具有 n 个结点的完全二叉树的高度为2log2 n+1 .(× )32、在只有度为 0 和度为2 的结点的二叉树中，设度为0的结点有n0 个，度为2 的结点有n2 个，则有n0=n2+1 .( )33、循环队列判断队列为满的条件是sq->front+1= =sq->rear。(× )34、数组是一种

5、复杂的数据结构，数组元素之间的关系既不是线性的也不是树形的。.( )35、若二叉树中各结点的值均不相同，则由二叉树的前序序列和中序序列，或由其后序序列和中序序列均能惟一地确定一棵二叉树。. ( )36、有 n 个结点的不同的二叉树有n！棵。 . .( ×)37、一般树和二叉树的结点数目都可以为0。 .( )38、循环队列判断队列为空的条件是sq->front= =sq->rear。 ( )39、设有一顺序栈 S，元素 s1,s 2,s 3,s4,s 5,s 6 依次进栈，如果6 个元素出线的顺序是s2,s 3,s 4, s 6 , s 5,s 1, 则栈的容量至少应该是

6、3。 .( )40、在只有度为 0 和度为 k 的结点的 k 叉树中，设度为0 的结点有 n0 个，度为 k 的结点有 nk 个，则有 n0=nk+1 .(× )41、一个连通图的生成树，是含该连通图的全部顶点的一个极小连通子图.( )42、在二叉树的第 i 层上至多有 2i-1个结点 .( )43、先根遍历树和先根遍历与该树对应的二叉树，其结果不一样。. (× )44、由树转化成二叉树，其根的右子女指针总是空的.( )45、网络的最小代价生成树是唯一的 . . .( ×)46、深度优先搜索遍历类似于树的先根遍历，它所用到的数据结构是队列。( × )47

7、、在一棵二叉树中，假定每个结点只有左子女，没有右子女，对它分别进行中序遍历和后序遍历，则具有相同的结果。( )48 、 对 于 一 棵具 有 n 个结 点 ， 其 高 度 为 h 的 二叉 树 ， 进 行 任一 种次 序遍 历 的 时 间 复杂 度为 O （n）。 . .( )49、图的深度优先搜索类似于树的先根次序遍历.( )50、在无向图中定义顶点V与 V 之间的路径为从V到达 V 的一个顶点序列（ ）ijij51、设无向连通图的顶点个数为n，则该图最多有n(n-1)/2条边 .( )52、图的广度优先遍历是树的按中根遍历推广。( × )53、设图 G=(V,E) ，V=1,2,

8、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 ）。 .( × )58、只有无向图，顶点数n

9、、边数 e 和度数之间有如下关系：e=1n D(×(v i)59、装载因子是散列表的一个重要参数，它反映了散列表的装满程度。2 i1（）60、闭散列法通常比开散列法时间效率更高。（ × ）61、进行折半搜索的表必须是顺序存储的有序表。（ ）62、索引顺序查找的过程也是一个“缩小区间”的查找过程( )63、设有 100 个数据元素，采用折半搜索时，最大比较次数为7. (×)64、在顺序表中进行顺序搜索时，若各元素的搜索概率不等，则各元素应按照搜索概率的降序排列存放，则可得到最小的平均搜索长度。.(×)65、在二叉搜索树中，若各结点的搜索概率不等，使得搜索概

10、率越小的结点离树根越近，则得到的是最优二叉搜索树。( )66、闭散列法通常比开散列法时间效率更高。（× ）67、折半搜索只适用与有序表，包括有序的顺序表和有序的链表。()68、起泡选择排序是一种不稳定的排序方法。( × )69、折半搜索只适用与有序表，包括有序的顺序表和有序的链表。. .(70、除留余法选择一个适当的正整数p, 以 p 除健值以所得的余数作为散列地址。×)（ ）71、选择排序是一种不稳定的排序方法。( )72、直接选择排序是不稳定的，其时间复杂性为）O(1) 。.(× )73、快速排序是一种不稳定的排序方法。( )74、对于有n 个对象的

11、待排序序列进行归并排序，所需平均时间为O（nlog2n ）。（）75、直接选择排序是一种不稳定的排序方法。 . . . . . ()76、直接插入排序是一种稳定的排序方法。( )77、归并排序是一种不稳定的排序方法。( ×)78、选择排序是一种不稳定的排序方法。( )79、归并排序是一种不稳定的排序方法。(×)80、堆排序是一种不稳定的排序方法。( )二、单选题：从选择的答案中选出正确的答案，将其字母编号填入下列叙述中的括号内。1、以下说法错误的是（ B ）A. 数据的物理结构是指数据在计算机内实际的存储形式B. 算法和程序没有区别，所以在数据结构中二者是通用的C. 对链表

12、进行插人和删除操作时，不必移动结点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.散列文件需

13、要索引区D.散列文件的记录不需要进行排序5、设单链表中结点的结构为（data ,next）。已知指针q 所指结点是指针p 所指结事业的直接前驱，若在*q 与 *p 之间插入结点 *s ，则应执行下列哪一个操作？（B）。A.s->next=p->next;p->next=sB q->next=s ;s->next=pC.p->next=s->next;s->next=pD.p->next=s ;s->next=q6、对顺序表上的插入、删除算法的时间复杂性分析来说，通常以（B ）为标准操作A. 条件判断B.结点移动C. 算术表达式D.赋值

14、语句7、在循环链表中，将头指针改设为尾指针（rear ）后，其头结点和尾结点的存储位置分别是（ B ）A.real 和 rear->next->nextB.rear->next和 realC.rear->next->next和 rearD.rear 和 rear->nextO（ 1）、O（n2）、O（ n 38、有一个算法由 3 个部分的线性代码连接组成，每部分的时间复杂度分别为）,该算法的时间复杂度为 ( C)A. O （ 1） +（ n2 ）+（ n3 ）B. O（n2）C. （ n3 ）D.（ n5）9、以下说法错误的是（ A）A. 对循环链表来说，从

15、表中任一结点出发都能通过前后操作而扫描整个循环链表B. 对单链表来说，只有从头结点开始才能扫描表中全部结点C. 双链表的特点是找结点的前趋和后继都很容易D.对双链表来说，结点*P 的存储位置既存放在其前趋结点的后继指针域中，也存放在它的后继结点的前趋指针域中。10、在串的基本运算中，属于加工型运算的有（D）A.EQAL(S,T)B.LENGTH(S)C.CONCA T(S,T)D.REPLACE(S,T,R)11、线性链表不具有的特点是（A ）。A随机访问B不必事先估计所需存储空间大小C插入与删除时不必移动元素D所需空间与线性表长度成正比12、以下说法正确的是（C）A. 在单链表中，任何两个元

16、素的存储位置之间都有固定的联系，因为可以从头结点进行查找任何一个元素B. 在单链表中，要取得某个元素，只要知道该元素的指针即可，因此，单链表是随机存取的存储结构 C. 顺序存储结构属于静态结构，链式结构属于动态结构D.顺序存储方式只能用于存储线性结构13、线性表是一个具有n 个（ C）的有限序列。A表元素B字符C数据元素D数据项14、对于顺序表，以下说法错误的是（ A）A. 顺序表是用一维数组实现的线性表，数组的下标可以看成是元素的绝对地址B. 顺序表的所有存储结点按相应数据元素间的逻辑关系决定的次序依次排列C. 顺序表的特点是 : 逻辑结构中相邻的结点在存储结构中仍相邻D. 顺序表的特点是

17、:逻辑上相邻的元素，存储在物理位置也相邻的单元中15、一个长度为 n 的顺序表的表尾插入一个新元素的渐进时间复杂度为（C）。A. O(n)B. O(n/2)C. O(1)D. O(n2)16、单链表的一个存储结点包含（A.数据域或指针域B.D ）指针域或链域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 ）。A. O(n)B. O(n/2)C. O(1)D. O(n

18、2)19、向顺序栈中压入新元素时，应当（A）。A. 先移动栈顶指针，再存入元素B 先存入元素，再移动栈顶指针 C. 先后次序无关紧要D 同时进行20、顺序队列的人队操作应为( A )21、头结点的单链表firstA. first = NULL;C. first->next = first;为空的判定条件是：( B )B. first->next= NULL;D. first != NULL;22、如果以链表作为栈的存储结构，则入栈操作时（A ）A、必须判别栈是否满B、必须判别栈元素的类型C、必须判别栈是否空D、对栈不作任何判别23、设有一个n n 的对称矩阵那么第 i 行的对角元素

19、AiiA，将其下三角部分按行存放在一个一维数组存放于 B 中（A）处。B 中， A00存放于B0中，A. (i+3)*i/2B. (i+1)*i/2C. (2n-i+1)*i/2D. (2n-i-1)*i/224、一个栈的入栈序列是a,b,c,d,e,则栈的不可能的输出序列是（A）A. d c e a bB.d e c b aC. e d c b aD.a b c d e25、假定一个链式队列的队头和队尾指针分别为front和 rear，则判断队空的条件为( A)。A. front = rearB. front != NULLC. rear != NULLD. front = NULL26、当

20、利用大小为n 的数组顺序存储一个队列时，该队列的最大长度为（B ）。A. n-2B. n-1C. nD. n+127、循环链表主要优点是（ D ）A. 不再需要头指针了B. 已知某个结点的位置后，能够容易找到它的直接前趋C. 在进行插入、删除运算时，能更好地保证链表不断开D. 从表中任一结点出发都能扫描到整个链表28、稀疏矩阵一般采用( C ) 方法压缩存储。A. 三维数组B. 单链表C. 三元组表29、链式栈与顺序栈相比，一个比较明显的优点是（B）A插入操作更加方便B通常不会出现栈满的情况D. 散列表C不会出现栈空的情况D删除操作更加方便30、设有一顺序栈S，元素 s1,s 2,s 3,s

21、4,s 5,s 6 依次进栈，如果的容量至少应该是（B）6 个元素出线的顺序是s2,s3,s4,s6,s5,s1, 则栈A.2B. 3C. 5D.631、设有 50 行 60 元素 A1825 A 3700列的二维数组A5060的存储地址为（A ）。B4376，其元素长度为4 字节，按行优先顺序存储，基地址为200，则C 3900D462032、设 C 语言数组DATAm+1作为循环队列队操作的语句为（D ）SQ的存储空间，front为对头指针rear为对尾指针， 则执行出A.front=front+1B.front=(front+1)%mC.rear=(rear+1)%mD. .front=

22、(front+1)%(m+1)33、循环队列的队满条件为(C)A.(sq.rear+1) % mazsize =(sq.front+1) % maxsize;B.(sq.rear+1 % maxsize =sq.front+1C.sq.(rear+1) % maxsize =sq.front34、在一棵二叉树的二叉链表中，空指针域数等于非空指针域数加（A）。A. 2B. 1C. 0D. 135、具有A 865 个结点的完全二叉树的高度为（B7C6B）。（根的层次号为D 50）36、对某二叉树进行前序遍历的结果为A DBFEACB DFEBCAABDEFC，中序遍历的结果为DBFEAC，则后序遍

23、历的结果为（B）C BDFECAD BDEFAC37、循环队列的出队操作为(A )38、设 F 是一个森林， B 是由 F 转换得到的二叉树， F 中有 n 个非叶结点，则 B 中右指针域为空的结点有（ C ）个。A n-1B nCn+1D n+239、设二叉树结点的先根序列、中根序列和后根序列中，所有叶子结点的先后顺序( B )A. 都不相同B.完全相同C. 先序和中序相同，而与后序不同D.中序和后序相同，而与先序不同40、对于顺序存储的队列，存储空间大小为n，头指针为F，尾指针为R。若在逻辑上看一个环，则队列中元素的个数为(B )A.R-FB. (n+R-F)mod nC.(R-F+1)m

24、od nD. n+R-F41、以下说法错误的是(A )A. 树形结构的特点是一个结点可以有多个直接前趋B. 线性结构中的一个结点至多只有一个直接后继C. 树形结构可以表达 ( 组织 ) 更复杂的数据D.树 ( 及一切树形结构) 是一种 " 分支层次 " 结构42、以下说法错误的是(B )。A. 二叉树可以是空集B. 二叉树的任一结点都有两棵子树C. 二叉树与树具有相同的树形结构D.二叉树中任一结点的两棵子树有次序之分43、在一棵具有n 个结点的二叉树中，所有结点的空子树个数等于（C）A nBn-1C n+1D 2*n44、下列说法中正确的是（A）。A. 一棵二叉树的度可以小

25、于2B. 二叉树中任何一个结点的度都为2C. 二叉树的度为2D. 任何一棵二叉树中至少有一个结点的度为245、在一棵具有5 层的满二叉树中结点数为（A）A 31B 32C 33D 1646、一个二叉树按顺序方式存储在一个维数组中，如图01234567891011 121314ABCDEFGHIJ则结点 E 在二叉树的第（C ）层。A.1B.2C.3D.447、在图的邻接表存储结构上执行广度优先搜索遍历类似于二叉树上的（D）A. 先根遍历B.中根遍历C.后根遍历D.按层次遍历48、任何一棵二叉树的叶结点在其先根、中根、后跟遍历序列中的相对位置(C )A. 肯定发生变化B.有时发生变化C.肯定不发

26、生变化D.无法确定49、在一棵高度为h( 假定树根结点的层号为0) 的完全二叉树中，所含结点个数不小于( B)。A. 2h+1B. 2h-1C. 2h-1D. 2h50、树若用双亲链表表示，则(A)A. 可容易地实现求双亲及子孙的运算B.求双亲及子孙的运算均较困难C.可容易地实现求双亲运算，但求子孙运算较困难D.可容易地实现求子孙运算，但求双亲运算较困难51、任何一个带权的无向连通图的最小生成树（B）A. 只有一棵B. 有一棵或多棵C.一定有多棵D.可能不存在52、设有向图有n 个顶点和e 条边，采用领接表作为其存储表示，在进行拓扑排序时，总的计算时间为（B）。A O（nlog2e C O(n

27、e)）DB O（n+e） O(n2)53、以下说法正确的是（ A ）A. 连通图的生成树，是该连通图的一个极小连通子图。B. 无向图的邻接矩阵是对称的，有向图的邻接矩阵一定是不对称的。C. 任何一个有向图，其全部顶点可以排成一个拓扑序列。D. 有回路的图不能进行拓扑排序。54、以下说法错误的是( D )A. 一般在哈夫曼树中，权值越大的叶子离根结点越近B. 哈夫曼树中没有度数为 1 的分支结点C. 若初始森林中共有n 裸二叉树，最终求得的哈夫曼树共有2n-1个结点D. 若初始森林中共有n 裸二叉树，进行2n-1 次合并后才能剩下一棵最终的哈夫曼树55、如果从无向图的任一顶点出发进行一次深度优先

28、搜索即可访问所有顶点，则该图一定是 (B )A. 完全图B. 连通图C.有回路D.一棵树56、将一棵有50 个结点的完全二叉树按层编号，则对编号为A.无左、右孩子B.有左孩子，无右孩子C. 有右孩子，无左孩子D. 有左、右孩子25 的结点x，该结点( B )57、深度为6 的二叉树最多有(B )个结点A.64B.63C.32D.3158、一个有序顺表有A、128 B 、127 C255 个对象，采用顺序搜索法查表，搜索长度为（、126 D 、 255A）。59、在有向图中每个顶点的度等于该顶点的（A.入度B.出度C. 入度与出度之和D.入度与出度之差C ）。60、具有 n 个顶点的有向无环图最

29、多可包含(A n-1B nCn(n-1)/261、用邻接表作为有向图G的存储结构。设有D) 条有向边。D n(n-1)n 个顶点、 e 条弧，则拓扑排序的时间复杂度为( B )A. O(n)B. O(n+e)C. O(e)D. O(n*e)62、一个有序顺表有255 个对象，采用顺序搜索法查表，搜索长度为（A ）。A 、 128B、 127C、 126D、 25563、在有向图中，所有顶点的入度之和是所有顶点出度之和的（B）倍。B. 1C. 2D.464、以下说法错误的是（B）A. 用相邻矩阵法存储一个图时，在不考虑压缩存储的情况下，所占用的存储空间大小只与图中结点个数有关，而与图的边数无关。

30、B. 邻接表法只能用于有向图的存储，而相邻矩阵法对于有向图和无向图的存储都适用。C.存储无向图的相邻矩阵是对称的，因此只要存储相邻矩阵的下（或上）三角部分就可以了D. 用相邻矩阵 A 表示图，判定任意两个结点Vi和 Vj 之间是否有长度为m 的路径相连，则只要检查 A的第 i 行第 j 列的元素是否为0 即可。65、在图的邻接表存储结构上执行深度优先搜索遍历类似于二叉树上的（A ）A. 先根遍历B. 中根遍历C. 后根遍历D 按层次遍历66、在一个无向图中，所有顶点的度数之和等于所有边数的（B ）倍。A 3B 2C1D 1/267、在无向图中，所有顶点的度数之和是所有边数的（C）倍。A.0.5

31、B.1C.2D.468、设有 6 个结点的无向图，该图至少应有（B）条边能确保是一个连通图。A. 5B. 6C. 7D. 869、以下说法正确的是（D）A. 连通分量是无向图中的极小连通子图。B. 强连通分量是有向图中的极大强连通子图。C.在一个有向图的拓扑序列中，若顶点a 在顶点 b 之前，则图中必有一条弧<a,b> 。D. 对有向图 G,如果从任意顶点出发进行一次深度优先或广度优先搜索能访问到每个顶点，则该图一定是完全图。70、对有 14 个数据元素的有序表 R14进行折半搜索，搜索到R3 的关键码等于给定值，此时元素比较顺序依次为（C）。A R0 ，R1， R2， R3B R

32、0 ， R13 ， R2 ，R3C R6 ，R2， R4， R3D R6 ， R4 ， R2 ，R371、设有序表的关键字序列为1 ， 4， 6，10，18， 35， 42，53， 67， 71，78，84， 92，99 ，当用二分查找法查找健值为99 的结点时，经（C ）次比较后查找成功。A.2B. 3C.4C. 1272、设有100 个数据元素，采用折半搜索时，最大比较次数为（B）A 6B 7C 8D 1073、对长度为n 的有序单链表，若搜索每个元素的概率相等，则顺序搜索到表中任一元素的平均搜索长度为（ B）A n/2B(n+1)/2C (n 1)/2Dn/474、对采用二分查找法进行查

33、找运算的查找表，要求按（C）方式进行存储。A 顺序存储B链式存储C 顺序存储且结点按关键字有序D 链式存储且结点按关键字有序75、二分查找法适用于存储结构为（A）的，且按关键字排序的线性表A. 顺序存储B. 链接存储C. 顺序存储或链接存储D. 索引存储76、在一个长度为n 的顺序表的任一位置插入一个新元素的渐进时间复杂度为（B ）A. O(n)B. O(n/2)C. O(1)2D. O(n )77、在对查找表的查找过程中，若被查找的数据元素不存在，则把该数据元素插入到集合中。这种方式主要适合于 (C )A. 静态查找表B.动态查找表C. 静态查找表与动态查找表D.两种表都不适合78、在一个长

34、度为n 的顺序表的表尾插入一个新元素的渐进时间复杂度为（B）A O (n)BO (1)C O (n 2 )D O (log 2 n)79、设有序表的关键字序列为1 ， 4， 6，10，18， 35， 42，53， 67， 71，78，84， 92，99 ，当用二分查找法查找健值为84 的结点时，经（C ）次比较后查找成功。A2B 3C 4D 1280、静态查找表与动态查找表两者的根本差别在于（C ）A 逻辑结构不同B存储实现不同C 施加的操作不同D 数据元素的类型不同81、以下时间复杂性不是O(n2) 的排序方法是（ B ）A. 直接插入排序B. 二路归并排序C. 冒泡排序 D.直接选择排序8

35、2、一个对象序列的排序码为46 ， 79， 56， 38，40， 84 ，采用快速排序以位于最左位置的对象为基准而得到的第一次划分结果为（C）。A 38 ， 46， 79， 56， 40， 84B 38 ， 79，56， 46，40， 84C 40 ， 38， 46， 56，79， 84D 38 ， 46，56， 79，40， 8483、用顺序查找法对具有n 个结点的线性表查找的时间复杂性量级为（C）A.O （ n2）B. O(nlog 2n)C. O（n）D O(log 2 n)84、用某种排序方法对序列（25， 84， 21， 47， 15， 27， 68， 35， 20）进行排序，记录序

36、列的变化情况如下：258421471527683520152021254727683584152021253527476884152021252735476884则采取的排序方法是（ C ）A. 直接选择排序B.冒泡排序C.快速排序D. 二路归并排序85、一个对象序列的排序码为 46 ， 79， 56， 38，40， 84 ，采用快速排序以位于最左位置的对象为基准而得到的第一次划分结果为（ C ）。A 38 ， 46， 79， 56， 40， 84B 38 ， 79， 56， 46， 40， 84C 40 ， 38， 46， 56， 79， 84D 38 ， 46， 56， 79， 40， 8

37、486、顺序查找法适合于（D）存储结构的查找表。A. 压缩B. 散列C.索引D.顺序或链式87、以下说法错误的是（C ）A. 直接插入排序的空间复杂度为O(1) 。B. 快速排序附加存储开销为O(log 2n) 。C. 堆排序的空间复杂度为O(n) 。D. 二路归并排序的空间复杂度为O(n),需要附加两倍的存储开销。88、对于大文件的排序要研究在外设上的排序技术，即（C）A. 快速排序法B. 内排序法C.外排序法D. 交叉排序法89、对于长度为 9 的有序顺序表，若采用折半搜索，在等概率情况下搜索成功的平均搜索长度为（C ）的值除以 9。A. 20B. 18C. 25D. 2290、具有 24

38、 个记录的序列，采用冒泡排序至少的比较次数是（ B ）A.1B.23C. 24D. 52991、当初始序列已按健值有序时，用直接插入算法进行排序，需要比较的次数为（A ）A.n-1B.log 2nC. 2log2nD.n 292、排序的目的是为了以后对已排序的数据元数进行（D）操作。A. 打印输出B.分类C. 合并D.查找93、以下稳定的排序方法是（ B ）A. 快速排序B.冒泡排序C.直接选择排序D.堆排序94、（ B ）方法是从未排序序列中依次取出元素与已排序序列中的元素作比较，将其放入已排序序列的正确位置上。A. 归并排序B. 插入排序C.快速排序D. 选择排序95、在文件局部有序或文件

39、长度较小的情况下，最佳的排序方法是（ 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 快

40、速排序 D 起泡排序99、以下不稳定的排序方法是（ C ）A. 直接插入排序B.冒泡排序C. 直接选择排序D. 二路归并排100、在一个长度为 n 的顺序表的任一位置插入一个新元素的渐进时间复杂度为（B ）A. O(n)B. O(n/2)C. O(1)D. O(n 2)三、填空题1、有一个算法由3 个部分的线性代码连接组成，每部分的时间复杂度分别为O（n）、 O（ n2）、 O（ n 4） ,该算法的时间复杂度为(O（ n 4 ） ) 。2、数据的基本单位是(数据元素 ) 。3、计算机中的算法指的是解决某一问题的有限运算序列，它必须具备输入、 输出、 可行性、 ( 确定性 ) 和( 有穷性 )

41、等 5个特征4、所有结点按1 对 1 的邻接关系构成的整体就是(线性) 结构5、数据元素之间的关联方式或称“邻接关系”称为(逻辑)关系。6、有一个算法由3 个部分的代码嵌套连接组成，每部分的时间复杂度分别为O（n）、 O（ n2）、 O（ n4） ,该算法的时间复杂度为( O （ n7 ） ) 。7、数据元素之间逻辑关系的整体称为(逻辑结构 )。8、对一个算法要作出全面的分析可分成两用人才个阶段进行，即事先分析和( 事后测试 ) 。9、算法的复杂度分为( 时间复杂度 )和 ( 空间复杂度 )两种。10、数据在计算机中的存储表示（机内表示）称为数据的(存储结构)。11、文件的检索有顺序存取、直接

42、存取和(按关键字存取) 三种方式。12、文件的检索有顺序存取、直接存取和( 按关键字存取 ) 三种方式。13、在顺序表中插入或删除一个元素，需要平均移动(n+1)/2) 元素，具体移动的元素个数与()有关。14、 VSAM文件结构由三部分组成：索引集、( 顺序集 ) 和数据集。15、 ISAM文件是由多级主索引、柱面索引、磁道索引和( 主文件索引 ) 组成。16、已知： s1=I m a teacher ， s2= teacher ， s3= student ，则等于 (I m a teacher) 。REPLACE(s1,s2, s3)17、如果文件中的每个记录都有一个索引项，则这样的索引称为( 稠密索引 ) 。18、如果文件中多个记录只有一个索引项，则这样的索引称为( 非稠密索引 ) 。19、在双链表中，每个结点有两个指针域，一个指向( 前驱 ) ，另一个指向 ( 后继 ) 。20、当且仅当两个