数据结构学位考试试题

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

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

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

4、插入运算时的平均时间复杂度都是O(n) ( X)29、 线性表中的每个结点最多只有一个前驱和一个后继。 ( V )30、 顺序表上做删除和插入运算时的平均时间复杂度都是O(n) ( V )31、 具有n个结点的完全二叉树的高度为匚2log2 nj +1 ( X )则有32、在只有度为 0 和度为 2 的结点的二叉树中，设度为 0 的结点有 n0 个，度为 2 的结点有 n2 个，n0=n2+1 (V )33、 循环队列判断队列为满的条件是sq->front+1= =sq->rear 。 (X )34、 数组是一种复杂的数据结构，数组元素之间的关系既不是线性的也不是树形的。( V )

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

6、0个，度为k的结点有nk个，则有n0=nk+1 .( x )41、 一个连通图的生成树，是含该连通图的全部顶点的一个极小连通子图.(V )42、 在二叉树的第i层上至多有2-个结点.(V )43、 先根遍历树和先根遍历与该树对应的二叉树，其结果不一样。(X )44、 由树转化成二叉树，其根的右子女指针总是空的.(V )45、 网络的最小代价生成树是唯一的 .(X )46、 深度优先搜索遍历类似于树的先根遍历，它所用到的数据结构是队列。(X )47、在一棵二叉树中，假定每个结点只有左子女，没有右子女，对它分别进行中序遍历和后序遍历，则具有相同的结果。(V)48、对于一棵具有n个结点，其高度为h的

7、二叉树，进行任一种次序遍历的时间复杂度为 O(n)。 .( V )49、 图的深度优先搜索类似于树的先根次序遍历 .(V)50、 在无向图中定义顶点V i与V之间的路径为从 V i到达V的一个顶点序列(V )51、 设无向连通图的顶点个数为n,则该图最多有n(n-1)/2 条边.(V )52、 图的广度优先遍历是树的按中根遍历推广。(X )53、 设图 G=(V,E) , V=1,2,3,4, E=<1,2>,<1,3>,<2,4>,<3,4>，从顶点 1 出发，对图G进行广度优先搜索的序列有2种( V )54、 用邻接表作为有向图G的存储结构。

8、设有 n个顶点、e条弧，则拓扑排序的时间复杂度为O(n*e) .( x )55、 查找表是由同一类型的数据元素(或记录)构成的集合(V)56、存储图的邻接矩阵中，邻接矩阵的大小不但与图的顶点个数有关，而且与图的边数也有关 . .(V )57、 图的深度和广度遍历两种操作的时间复杂度都为O (n*e )。 .(x n)158、 只有无向图，顶点数n、边数e和度数之间有如下关系：e=DXv)59、 装载因子是散列表的一个重要参数，它反映了散列表的装满程度。(V) i 160、 闭散列法通常比开散列法时间效率更高。(X )61、 进行折半搜索的表必须是顺序存储的有序表。(V )62、 索引顺序查找的

9、过程也是一个“缩小区间”的查找过程(V)63、 设有100个数据元素，采用折半搜索时，最大比较次数为7. ( X)64、在顺序表中进行顺序搜索时，若各元素的搜索概率不等，则各元素应按照搜索概率的降序排列存放，则可得到最小的平均搜索长度。.(X )65、在二叉搜索树中，若各结点的搜索概率不等，使得搜索概率越小的结点离树根越近，则得到的是最优二叉搜索树。(V)66、闭散列法通常比开散列法时间效率更高。( X )67、 折半搜索只适用与有序表，包括有序的顺序表和有序的链表。(V )68、 起泡选择排序是一种不稳定的排序方法。(X )69、 折半搜索只适用与有序表，包括有序的顺序表和有序的链表。.(X

10、 )70、 除留余法选择一个适当的正整数p,以p除健值以所得的余数作为散列地址。(V )71、 选择排序是一种不稳定的排序方法。(V )72、 直接选择排序是不稳定的，其时间复杂性为)O(1)。 .( X )73、 快速排序是一种不稳定的排序方法。(V )74、 对于有n个对象的待排序序列进行归并排序，所需平均时间为O (nIog2n )。(V)75、 直接选择排序是一种不稳定的排序方法。.(V )76、 直接插入排序是一种稳定的排序方法。(V )77、 归并排序是一种不稳定的排序方法。(X )78、 选择排序是一种不稳定的排序方法。(V )79、 归并排序是一种不稳定的排序方法。(X )80

11、、 堆排序是一种不稳定的排序方法。(V ) 二、单选题：从选择的答案中选出正确的答案，将其字母编号填入下列叙述中的括号内。1、 以下说法错误的是( B )A. 数据的物理结构是指数据在计算机内实际的存储形式B. 算法和程序没有区别，所以在数据结构中二者是通用的C. 对链表进行插人和删除操作时，不必移动结点D. 双链表中至多只有一个结点的后继指针为空2、 下列有关散列文件的说法中不正确的是(C )A. 散列文件具有随机存放的优点B.散列文件只能按关键字存取C.散列文件需要索引区D.散列文件的记录不需要进行排序3、有一个算法由 3个部分的代码嵌套连接组成，每部分的时间复杂度分别为 O(1)、 O(

12、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=sB q->next

13、=s ;s->next=pC.p->next=s->next;s->next=pD.p->next=s ;s->next=q6、 对顺序表上的插入、删除算法的时间复杂性分析来说，通常以(B )为标准操作A. 条件判断B.结点移动C.算术表达式D.赋值语句7、 在循环链表中，将头指针改设为尾指针(rear )后，其头结点和尾结点的存储位置分别是( B )A. reaI 和 rear->next->nextB. rear->next和 reaIC. rear->next->next和 rearD. rear 和 rear->n

14、ext8、有一个算法由 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、在串的基本运算中，属于加

15、工型运算的有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. 在单链表中，任何两个元素的存储位置之间都有固定的联系，因为可以从头结点进行查找任何一个B. 在单链表中，要取得某个元素，只要知道该元素的指针即可，因此，单链表是随机存取的存储结构C. 顺序存储结构属于静态结构，链式结构属于动态结构D顺序存储方式只能用于存储线性结构13、线性表是一个具有 n个（C）的有

16、限序列。A. 表元素B .字符 C .数据元素D .数据项14、 对于顺序表，以下说法错误的是（ A ）A. 顺序表是用一维数组实现的线性表，数组的下标可以看成是元素的绝对地址B. 顺序表的所有存储结点按相应数据元素间的逻辑关系决定的次序依次排列C. 顺序表的特点是 : 逻辑结构中相邻的结点在存储结构中仍相邻D. 顺序表的特点是 :逻辑上相邻的元素，存储在物理位置也相邻的单元中2D. O(n 2)15、一个长度为 n 的顺序表的表尾插入一个新元素的渐进时间复杂度为（C）。A. O(n)B. O(n/2)C. O(1)16、单链表的一个存储结点包含（ D ）A. 数据域或指针域B.指针域或链域C

17、. 指针域和链域D.数据域和链域精选17、在串的基本运算中，属于引用型运算的有（ B ）A.ASSIGN(S,T) B.INSERT(S1,i,S2)A )。C.DELETE(S,i,j) D.SUBSTR(S,i,j)18、一个长度为 n 的顺序表的任一位置插入一个新元素的渐进时间复杂度为(2A. O(n)B. O(n/2)C. O(1)D. O(n 2)19、 向顺序栈中压入新元素时，应当(A )。A. 先移动栈顶指针，再存入元素B .先存入元素，再移动栈顶指针 C. 先后次序无关紧要D .同时进行20、 顺序队列的人队操作应为( A )A. sq.rear=sq.rear+1;sq.da

18、tasq.rear=xB. sq.datasq.rear=x;sq.rear=sq.rear+1C. sq.rear=(sq.rear+1)% maxsize;sq.datasq.rear=xD. sq.datasqrear=x;sq.rear=(sq.rear+1)% maxsize21、 头结点的单链表first 为空的判定条件是： (B)A. first = NULL;B. first->next= NULL;C. first->next = first;D. first != NULL;22、如果以链表作为栈的存储结构，则入栈操作时（A）A、必须判别栈是否满B 、必须判别栈

19、元素的类型C、必须判别栈是否空D、对栈不作任何判别23、 设有一个n n的对称矩阵A,将其下三角部分按行存放在一个一维数组B中，A00存放于B0中, 那么第i行的对角元素 Aii 存放于B中(A )处。A. (i+3)*i/2 B. (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 b B.d e c b aC. e d c b a D.a b c d e25、 假定一个链式队列的队头和队尾指针分别为front 和 rear ，则判断队空的条件为 ( A ) 。A

20、. front = rearB. front != NULLC. rear != NULLD. front = NULL26、当利用大小为 n 的数组顺序存储一个队列时，该队列的最大长度为( B )。A. n-2 B. n-1 C. n D. n+127、循环链表主要优点是( D )A. 不再需要头指针了B. 已知某个结点的位置后，能够容易找到它的直接前趋C. 在进行插入、删除运算时，能更好地保证链表不断开D. 从表中任一结点出发都能扫描到整个链表28、稀疏矩阵一般采用 (C ) 方法压缩存储。A. 三维数组B. 单链表C. 三元组表D. 散列表29、链式栈与顺序栈相比，一个比较明显的优点是(

21、B)A 插入操作更加方便 B 通常不会出现栈满的情况C 不会出现栈空的情况 D 删除操作更加方便30、设有一顺序栈 S,元素S1,S2,s3,s4,S5,S 6依次进栈，如果 6个元素出线的顺序是S2,S3,s4,S6,S5,s1,则栈的容量至少应该是( B )A.2B. 331、设有 50 行60列的二维数组 A5060 元素 A1825A3700C3900设 C 语言数组C. 5D.6，其元素长度为 4 字节，按行优先顺序存储，基地址为200，则32、的存储地址为( A)。B4376D4620DATAm+1作为循环队列SQ的存储空间，front为对头指针 rear 为对尾指针，则执行出33

22、、34、35、队操作的语句为( D)A.front=front+1B.front=(front+1)%mD. .front=(front+1)%(m+1)(C)C.rear=(rear+1)%m循环队列的队满条件为A. (Sq.rear+1) % mazSize =(Sq.front+1) % maxSize;B. (Sq.rear+1 % maxSize =Sq.front+1C. Sq.(rear+1) % maxSize =Sq.frontD. Sq.rear =Sq.front在一棵二叉树的二叉链表中，空指针域数等于非空指针域数加(A. 2B. 1C. 0具有65个结点的完全二叉树的高

23、度为(B)o (根的层次号为A )。D. 10)A 8B 7 C6D 5DBFEAC则后序遍历的结果为36、对某二叉树进行前序遍历的结果为ABDEFC中序遍历的结果为A DBFEACB DFEBCAC. BDFECA D . BDEFAC37、 循环队列的出队操作为（A ）A. sq.fr on t=（sq.ft on t+1）% maxsizeB. sq.fr on t=sq.fr on t+1C. sq.rear=（sq.rear+）% maxsizeD. sq.rear=sq.rear+138、 设F是一个森林，B是由F转换得到的二叉树，F中有n个非叶结点，则B中右指针域为空的结点有 （

24、C ） 个。A. n-1 B. n C . n+1 D . n+239、 设二叉树结点的先根序列、中根序列和后根序列中，所有叶子结点的先后顺序（B ）A.都不相同B.完全相同C.先序和中序相同，而与后序不同D.中序和后序相同，而与先序不同40、 对于顺序存储的队列，存储空间大小为n,头指针为F,尾指针为R。若在逻辑上看一个环，则队列中 元素的个数为（B ）A.R-FB. （n+R-F）mod nC.（R-F+1）mod nD. n+R-F41、 以下说法错误的是（A ）A. 树形结构的特点是一个结点可以有多个直接前趋B. 线性结构中的一个结点至多只有一个直接后继C. 树形结构可以表达（组织）更

25、复杂的数据D.树（及一切树形结构）是一种”分支层次”结构42、以下说法错误的是（B ）。A. 二叉树可以是空集B. 二叉树的任一结点都有两棵子树C. 二叉树与树具有相同的树形结构D. 二叉树中任一结点的两棵子树有次序之分43、 在一棵具有n个结点的二叉树中，所有结点的空子树个数等于（C ）A. n B . n-1 C . n+1D. 2*n44、下列说法中正确的是（ A ）oA. 一棵二叉树的度可以小于2 B.二叉树中任何一个结点的度都为2C. 二叉树的度为2D.任何一棵二叉树中至少有一个结点的度为245、在一棵具有5层的满二叉树中结点数为（ A ）A 31 B 32 C 33 D 1646、

26、一个二叉树按顺序方式存储在一个维数组中，如图0123 456 78 9 10 11 12 13 14ABCDEFGHIJ则结点E在二叉树的第（C ）层。A.1B.2C.3D.447、在图的邻接表存储结构上执行广度优先搜索遍历类似于二叉树上的（D）A.先根遍历B.中根遍历C.后根遍历 D.按层次遍历48、任何一棵二叉树的叶结点在其先根、中根、后跟遍历序列中的相对位置（C ）A.肯定发生变化C.肯定不发生变化49、在一棵高度为h+1A. 2B.有时发生变化D.无法确定h（假定树根结点的层号为B. 2h-1 C. 20）的完全二叉树中，所含结点个数不小于h-1D. 2 h(B)。50、树若用双亲链表

27、表示，则 (A)A. 可容易地实现求双亲及子孙的运算B. 求双亲及子孙的运算均较困难C可容易地实现求双亲运算，但求子孙运算较困难D.可容易地实现求子孙运算，但求双亲运算较困难51、任何一个带权的无向连通图的最小生成树( B)A.只有一棵B.有一棵或多棵C.一定有多棵D.可能不存在52、设有向图有 n 个顶点和 e 条边，采用领接表作为其存储表示，在进行拓扑排序时，总的计算时间为 ( B )。O(n+e)O(n2)A O(nlog2e )BC O(ne)D53、以下说法正确的是( A )A. 连通图的生成树，是该连通图的一个极小连通子图。B. 无向图的邻接矩阵是对称的，有向图的邻接矩阵一定是不对

28、称的。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.

29、 无左、右孩子B. 有左孩子，无右孩子C. 有右孩子，无左孩子D. 有左、右孩子57、深度为 6的二叉树最多有 (B ) 个结点A.64B.63C.32D.3158、一个有序顺表有 255 个对象，采用顺序搜索法查表，搜索长度为( A )。A、 128 B 、 127 C 、 126 D 、 25559、 在有向图中每个顶点的度等于该顶点的(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条弧，

30、则拓扑排序的时间复杂度为(B )A. O(n)B. O(n+e)C. O(e)D. O(n*e)62、一个有序顺表有 255 个对象，采用顺序搜索法查表，搜索长度为( A)。A、 128B、 127 C、 126 D、 25563、 在有向图中，所有顶点的入度之和是所有顶点出度之和的(B)倍。A.0.5B. 1C. 2D.464、以下说法错误的是( B)A. 用相邻矩阵法存储一个图时，在不考虑压缩存储的情况下，所占用的存储空间大小只与图中结点个数有关，而与图的边数无关。B. 邻接表法只能用于有向图的存储，而相邻矩阵法对于有向图和无向图的存储都适用。C. 存储无向图的相邻矩阵是对称的，因此只要存

31、储相邻矩阵的下（或上）三角部分就可以了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/267、 在无向图中，所有顶点的度数之和是所有边数的（C ）倍。A.0.5B.1C.2D.468、设有6个结点的无向图，该图至少应有（B）条边能确保是一个连通图。A. 5 B. 6C

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

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

34、储A 顺序存储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 的顺序表的表尾插入一个新元素

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

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

37、83584152021253527476884152021252735476884则采取的排序方法是( C)A.直接选择排序B.冒泡排序C.快速排序D.二路归并排序85、 一个对象序列的排序码为46，79，56，38，40，84 ，采用快速排序以位于最左位置的对象为基准而 得到的第一次划分结果为（ C ）。A38 ，46，79，56，40，84B38，79，56，46，40，84C40 ，38，46，56，79，84D38，46，56，79，40，8486、 顺序查找法适合于（D ）存储结构的查找表。A.压缩B.散列C.索引D.顺序或链式87、以下说法错误的是（C ）A. 直接插入排序的空间复

38、杂度为0（1）。B. 快速排序附加存储开销为O（log 2n）。C. 堆排序的空间复杂度为 0（n） 。D. 二路归并排序的空间复杂度为0（n）,需要附加两倍的存储开销。88、 对于大文件的排序要研究在外设上的排序技术，即（C）A.快速排序法B.内排序法C.外排序法D.交叉排序法89、对于长度为 9 的有序顺序表，若采用折半搜索，在等概率情况下搜索成功的平均搜索长度为（C ）的值除以 9。A. 20 B. 18 C. 25 D. 2290、 具有 24 个记录的序列，采用冒泡排序至少的比较次数是（ B ）A.1B.23C. 24D. 52991、 当初始序列已按健值有序时，用直接插入算法进行排

39、序，需要比较的次数为（A）A.n-1B.log 2nC. 2log2nD.n292、 排序的目的是为了以后对已排序的数据元数进行（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个元素组成

40、的序列中的前 5 个最小元素，那么用（ C ）方法最快。A.起泡排序 B 快速排序 C 堆排序 D 直接选择排序97、对一个由 n 个整数组成的序列，借助排序过程找出其中的最大值，希望比较次数和移动次数最少，应 选用（ C ）方法。A. 归并排序B.直接插入排序C. 直接选择排序 D. 快速排序98、对待排序的元素序列进行划分，将其分为左、右两个子序列，再对两个子序列施加同样的排序操作，直到子序列为空或只剩一个元素为止。这样的排序方法是（C ）A 直接选择排序 B 直接插入排序 C 快速排序 D 起泡排序99、 以下不稳定的排序方法是（ C ）A. 直接插入排序 B. 冒泡排序 C. 直接选择

41、排序 D. 二路归并排100、在一个长度为 n 的顺序表的任一位置插入一个新元素的渐进时间复杂度为（ B ）A. O（n）B. O（n/2）C. O（1）D. O（n2）O（n）、O（n2）、O（ n 4 ）O（n）、 O（ n2）、 O（ n4 ）（ 事后测试 ） 。三、填空题1、有一个算法由 3 个部分的线性代码连接组成，每部分的时间复杂度分别为 该算法的时间复杂度为 （O（ n 4 ） ） 。2、数据的基本单位是 （数据元素 ） 。它必须具备输入、输出、可行性、 （确定性）和（有3、计算机中的算法指的是解决某一问题的有限运算序列， 穷性 ）等 5个特征4、所有结点按 1对 1的邻接关系构

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

43、取 ） 三种方式。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、 如果文件中多个记录只有一个索引项

44、，则这样的索引称为（非稠密索引 ）。19、 在双链表中，每个结点有两个指针域，一个指向（ 前驱 ） ， 另一个指向 （ 后继 ） 。20、当且仅当两个串的 （长度 ）相等并且各个对应位置上的字符都相同时，这两个串相等。一个串中任意个连续字符组成的序列称为该串的 （ 子串 ） 串。21、 VSAM文件结构由三部分组成：索引集、（顺序集）和数据集。22、 串的顺序存储有两种方法：一种是每个单元只存一个字符，称为（ 非紧缩格式 ） 格式，另一种是每个单 元存放多个字符，称为 （ 紧缩格式 ） 格式。23、 线性表的常见链式存储结构有单链表、（双向链表 ）和（循环链表 ）。24、 线性表典型的基本运算

45、包括初始化、（ 插入）、 （删除） 、查找定位、求长度、存取等六种。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、 顺序表中逻辑

46、上相邻的元素的物理位置（必须）紧邻。单链表中逻辑上相邻的元素的物理位置 （不需要 ） 紧邻。29、 四维数组是一种非线性结构，其中的每一个数组元素最多有（4） 个直 接前驱（或直接后继）30、 一般地，栈和线性表类似有两种实现方法，即（ 顺序 ） 实现和 （ 链接 ） 实现。31、 含零个字符的串称为（空串）串，用（）表示。32、 栈是一种限定在表的一端进行插入和删除的线性表，又被称为（后进先出 ）线性表。33、 在栈的顺序实现中，设栈顶指针为top ，栈空的条件为 （top=0） 。34、 若已知一个栈的入栈序列是1, 2, 3, 4，n，其输出序列是 P1, P2, P3,，Pn,若P仁n

47、,则 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->t

48、op=sqstack_maxsize-1error（ else（ sq->top+）:（sq->datasq->top）=x;return（1）;维数组的线性表。数组通常只有 （删除）和（插入）两种（ 二叉链表 ） 与（ 三叉链表 ） 。处用适当的语句予以填充。“栈满” ）;return（0）;42、深度为 90 的满二叉树上,第 11 层有（210）个结点。43、已知一棵度为 3的树有 2个度为 1的结点, 3个度过为 2的结点, 1个度为 3 的结点,则该树中有 （6） 个叶子结点。44、 深度优先搜索遍历类似于树的（先根）遍历,它所用到的数据结构是 （栈）。45、具有

49、n 个结点的完全二叉树的深度为 （log2n 1 ）。46、（树 ） 中结点的最大度数允许大于 2,而 （ 二叉树 ） 中结点的最大度数不允许大于 247、一棵树按照左子女 -右兄弟表示法转换成对应的二叉树,则该二叉树中树根结点肯定没有（右）子女。48、深度为 k（k>=1） 的二叉树至多有 （2k-1 ）个结点。49、有m个叶子结点的哈夫曼树，其结点总数为 （2m-1 ）。50、在一棵树中， （ 根） 结点没有前驱结点。51、对无向图，其邻接矩阵是一个关于（对角线 ） 对称的矩阵。52、 n （n > 0）个顶点的有向连通图最多有 （n（n-1）条边，最少有（n-1）条边53、设

50、无向连通图 G的顶点数为n,贝U G最少有（n-1 ）条边。54、遍历图的基本方法有 （深度）优先搜索和 （ 广度 ） 优先搜索两种。55、 在集合这种逻辑结构中,任何结点之间都不存在（ 逻辑 ） 关系,这是集合这种逻辑结构的基本特点。56、 一个有向图 G中若有弧，<Vi,Vj>、<Vj,Vk>和<Vi,Vk>则在图G的拓扑序列中，顶点V、Vj和Vk的相对 位置为 （省略 ）。57、 广度优先搜索遍历类似于树的（层次）遍历,它所用到的数据结构是 （队列）。58、由 （ 树） 转换成二叉树时,其根结点的右子树总是空的。59、设图 G=（V,E） , V=1,

51、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、 动态查找表包括建表、查找、读

52、元素、（ 插入 ） 、 （ 删除 ） 五种基本运算。65、 根据一组记录（56, 42, 50, 64, 48）依次插入结点生成一棵AVL树（高度平衡的二叉搜索树）时， 当插入到值为 （50） 的结点时需要进行旋转调整。66、 平衡二叉排序树上任一结点的平衡因子只可能是（0） 、 （1）或（-1） 。（空）变为 （指向该结点 ）即树高度之差的绝对值不超（ 1 ）。（ 选择排序 ） 、 （ 交换排序 ） 、67、在二叉排序树上插入新结点时,不必移动其它结点,仅需使某结点的指针域由 可。68、在一棵AVL树（高度平衡的二叉搜索树）中，每个结点的左子树高度与右子过（ 1 ） 。69、在具有 24 个

53、元素的有序表上进行二分查找,贝比较一次查找成功的结点数为70、 快速排序是不稳定的,其时间复杂性为（ O（ nlog2n） ）71、 直接选择排序是不稳定的,其时间复杂性为（O（ n2） ）。72、 按排序过程中依据的不同原贝对内部排序方法进行分类,主要有： 插入排序、 归并排序等四类73、 归并排序的空间复杂度为（O（1） 。74、 二叉排序树是一种特殊的、增加了限制条件的二叉树,其限制条件是任一结点的键值（大 ） 于其左孩子 （及其子孙）的键值且 （小）于其右孩子（及其子孙）的键值。75、 归并排序的时间复杂度是（O（nlog2n ） ）。276、 简单排序的时间复杂性为（ O（n2） ） ,空间复杂度为 （ O（1） ） 。77、二叉树第 i （ i>=1 ）层至多有 （2 i-1 ） 个节点。278、 直接插入排序是稳定的,它的时间复杂性为（O（n2） ,空间复杂度为 （O（1） 。79、 归并排序要求待排序列由若干个（有序）的子序列组成。80、 按照排序过程涉及的存储设备的不同,排序可分为（内）排序和（外 ）排序。四、计算题1、设二维数组 A8*9 的每个元素占 4 个字节,已知 Loc（a00） =1000, A 共占多少个字节？ A