数据结构课程学位考试试题（参考答案在题后）
判断题：判断下列各小题叙述的正误。对，在题号后的括号内填入“√ ”；错，在题号后填入“ ×”。 1、数据的最小单位是数据项。??????????.( √)
2、多重表文件中主索引为非稠密索引，次索引为稠密索引。???.( √ )
3、通常数据结构在计算机中有四种不同的表示方法分为顺序存储结构、链式存储结构、索引存储、文件存储。???.??.( × )
4、算法具有输入、输出、可行性、稳定性、有穷性五个特性。……………….( × ) 5、数据的基本单位是数据项。??????????.( × ) 6、算法的复杂度分为时间复杂度和效率复杂度。????.( × ) 7、性质相同的数据元素的集合成为数据对象。…………….( √ )
8、所有结点按1对1的邻接关系构成的整体就是集合结构。???.( × ) 9、散列文件不能顺序存取、只能按关键字随机存取。?????.( √ ) 10、数据的基本单位是数据元素。??????????.( √ ) 11、B+树中的K个孩子的结点必有K个关键字。?? ?.( √) 12、B+树中的K个孩子的结点必有K个关键字。???.??.( √ )
13、倒排表的索引项中没有头指针和链表长度项。????.( √ )
14、磁带是顺序存取的外存储设备。……………………………….……….( × ) 15、索引文件只能是磁盘文件。????????????(√ )
16、顺序文件只适宜于顺序存取。………………………..………….( × ) 17、磁带是顺序存取的外存储设备。??????????.??.( × ) 18、线性的数据结构可以顺序存储，也可以链接存储。?????.( √) 19、倒排表的索引项中没有头指针和链表长度项。???????.( √) 20、散列文件不能顺序存取、只能按关键字随机存取。?.??.( √ ) 21、栈和队列都是顺序存取的的线性表，但它们对存取位置的限制不同。（√） 22、循环链表从任何一个结点出发，都能访问到所有结点....... (√ ) 23、单链表从任何一个结点出发，都能访问到所有结点。??.( ×) 24、线性表采用顺序存储表示时，必须占用一片连续的存储单元。(√ ) 25、循环链表从任何一个结点出发，都能访问到所有结点。…….( √ ) 26、设串S的长度为n,则S的子串个数为n(n+1)/2? ?.( × )
27、线性表采用链接存储表示时，必须占用一片连续的存储单元。.( × ) 28、链接表上做删除和插入运算时的平均时间复杂度都是O(n) ?.( ×)
29、线性表中的每个结点最多只有一个前驱和一个后继。………… …….( √ ) 30、顺序表上做删除和插入运算时的平均时间复杂度都是O(n) .( √ )
n
31、具有n个结点的完全二叉树的高度为┖2log2┘+1?????.( ×)
32、在只有度为0和度为2的结点的二叉树中，设度为0的结点有n0个，度为2的结点有n2个，则有n0=n2+1?????.( √ )
33、循环队列判断队列为满的条件是sq->front+1= =sq->rear。??(× )
34、数组是一种复杂的数据结构，数组元素之间的关系既不是线性的也不是树形的。???.( √ )
35、若二叉树中各结点的值均不相同，则由二叉树的前序序列和中序序列，或由其后序序列和中序序列均能惟一地确定一棵二叉树。.... (√ )
36、有n个结点的不同的二叉树有n！棵。………………………….……….( × )
37、一般树和二叉树的结点数目都可以为0。................( √ ) 38、循环队列判断队列为空的条件是sq->front= =sq->rear。??(√ )
39、设有一顺序栈S，元素s1,s2,s3,s4,s5,s6依次进栈，如果6个元素出线的顺序是s2,s3,s4, s6 , s5,s1,则栈的容量至少应该是3。.( √)
40、在只有度为0和度为k的结点的k叉树中，设度为0的结点有n0个， 度为k的结点有nk个，则有n0=nk+1??????.( × )
41、一个连通图的生成树，是含该连通图的全部顶点的一个极小连通子图.( √ )
i-142、在二叉树的第 i 层上至多有2 个结点???.( √ )
43、先根遍历树和先根遍历与该树对应的二叉树，其结果不一样。... (× ) 44、由树转化成二叉树，其根的右子女指针总是空的???.( √ )
45、网络的最小代价生成树是唯一的………………….……….……….( × ) 46、深度优先搜索遍历类似于树的先根遍历，它所用到的数据结构是队列。(×) 47、在一棵二叉树中，假定每个结点只有左子女，没有右子女，对它分别进行中 序遍历和后序遍历，则具有相同的结果。???(√)
48、对于一棵具有n个结点，其高度为h的二叉树，进行任一种次序遍历的时间复杂度为O（n）。………..………….( √ )
49、图的深度优先搜索类似于树的先根次序遍历????.( √)
50、在无向图中定义顶点V i与Vj之间的路径为从V i到达Vj的一个顶点序列（ √ ） 51、设无向连通图的顶点个数为n，则该图最多有n(n-1)/2条边?.( √ ) 52、图的广度优先遍历是树的按中根遍历推广。???(× )
53、设图G=(V,E)，V={1,2,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）。……….( × n)
1(v )58、只有无向图，顶点数n、边数e和度数之间有如下关系：e= ……D(×i)
2i?159、装载因子是散列表的一个重要参数，它反映了散列表的装满程度。（√） 60、闭散列法通常比开散列法时间效率更高。（ × ） 61、进行折半搜索的表必须是顺序存储的有序表。（ √ ）
62、索引顺序查找的过程也是一个“缩小区间”的查找过程(√)
63、设有100个数据元素，采用折半搜索时，最大比较次数为7. (×)
64、在顺序表中进行顺序搜索时，若各元素的搜索概率不等，则各元素应按照搜索概率的降序排列存放，则可得到最小的平均搜索长度。??.( ×)
65、在二叉搜索树中，若各结点的搜索概率不等，使得搜索概率越小的结点离树 根越近，则得到的是最优二叉搜索树。???(√ ) 66、闭散列法通常比开散列法时间效率更高。（×）
67、折半搜索只适用与有序表，包括有序的顺序表和有序的链表。(√ ) 68、起泡选择排序是一种不稳定的排序方法。(×)
69、折半搜索只适用与有序表，包括有序的顺序表和有序的链表。.……….( × ) 70、除留余法选择一个适当的正整数p,以p除健值以所得的余数作为散列地址。（ √ ） 71、选择排序是一种不稳定的排序方法。(√ )
72、直接选择排序是不稳定的，其时间复杂性为）O(1)。???.(×)
?73、快速排序是一种不稳定的排序方法。(√ )
74、对于有n个对象的待排序序列进行归并排序，所需平均时间为O（nlog2n）。（√） 75、直接选择排序是一种不稳定的排序方法。….…….…….…….…….…( √ ) 76、直接插入排序是一种稳定的排序方法。(√ ) 77、归并排序是一种不稳定的排序方法。(× ) 78、选择排序是一种不稳定的排序方法。(√ ) 79、归并排序是一种不稳定的排序方法。(× ) 80、堆排序是一种不稳定的排序方法。(√ )
二、单选题：从选择的答案中选出正确的答案，将其字母编号填入下列叙述中的括号内。 1、以下说法错误的是 （ B ）
A.数据的物理结构是指数据在计算机内实际的存储形式 B.算法和程序没有区别，所以在数据结构中二者是通用的 C.对链表进行插人和删除操作时，不必移动结点 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.散列文件需要索引区 D.散列文件的记录不需要进行排序 5、设单链表中结点的结构为（data ,next）。已知指针q所指结点是指针p所指结事业的直接前驱，若在*q与*p之间插入结点*s，则应执行下列哪一个操作？（ B ）。
A.s->next=p->next;p->next=s B．q->next=s ;s->next=p C.p->next=s->next;s->next=p D.p->next=s ;s->next=q
6、对顺序表上的插入、删除算法的时间复杂性分析来说，通常以（ B ）为标准操作 A.条件判断 B.结点移动 C.算术表达式 D.赋值语句
7、在循环链表中，将头指针改设为尾指针（rear）后，其头结点和尾结点的存储位置分别是 （ B ） A.real和rear->next->next B.rear->next 和real
C.rear->next->next和rear D.rear和rear->next
8、有一个算法由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、在串的基本运算中，属于加工型运算的有 （ D ）
A.EQAL(S,T) B.LENGTH(S)
C.CONCAT(S,T) D.REPLACE(S,T,R) 11、线性链表不具有的特点是（A）。
A．随机访问 B．不必事先估计所需存储空间大小 C．插入与删除时不必移动元素 D．所需空间与线性表长度成正比 12、以下说法正确的是（C）
A.在单链表中，任何两个元素的存储位置之间都有固定的联系，因为可以从头结点进行查找任何一个元素
B.在单链表中，要取得某个元素，只要知道该元素的指针即可，因此，单链表是随机存取的存储结构 C.顺序存储结构属于静态结构，链式结构属于动态结构 D.顺序存储方式只能用于存储线性结构
13、线性表是一个具有n个（C）的有限序列。
A．表元素 B．字符 C．数据元素 D．数据项 14、对于顺序表，以下说法错误的是 （ A ）
A.顺序表是用一维数组实现的线性表，数组的下标可以看成是元素的绝对地址 B.顺序表的所有存储结点按相应数据元素间的逻辑关系决定的次序依次排列 C.顺序表的特点是:逻辑结构中相邻的结点在存储结构中仍相邻
D.顺序表的特点是:逻辑上相邻的元素，存储在物理位置也相邻的单元中 15、一个长度为n的顺序表的表尾插入一个新元素的渐进时间复杂度为（C）。
2
A. O(n) B. O(n/2) C. O(1) D. O(n) 16、单链表的一个存储结点包含（ D ）
A.数据域或指针域 B.指针域或链域 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 ）。
2
A. O(n) B. O(n/2) C. O(1) D. O(n) 19、向顺序栈中压入新元素时，应当（ A ）。
A.先移动栈顶指针，再存入元素 B．先存入元素，再移动栈顶指针
C. 先后次序无关紧要 D．同时进行
20、顺序队列的人队操作应为 ( A )
A.sq.rear=sq.rear+1;sq.data[sq.rear]=x B.sq.data[sq.rear]=x;sq.rear=sq.rear+1
C.sq.rear=(sq.rear+1)% maxsize;sq.data[sq.rear]=x D.sq.data[sqrear]=x;sq.rear=(sq.rear+1)% maxsize 21、头结点的单链表first为空的判定条件是：(B)
A. first == NULL; B. first->next== NULL; C. first->next == first; D. first != NULL; 22、如果以链表作为栈的存储结构，则入栈操作时（A）
A、必须判别栈是否满 B、必须判别栈元素的类型
C、必须判别栈是否空 D、对栈不作任何判别
23、设有一个n?n的对称矩阵A，将其下三角部分按行存放在一个一维数组B中，A[0][0]存放于B[0]中，那么第i行的对角元素A[i][i]存放于B中（ A ）处。
A. (i+3)*i/2 B. (i+1)*i/2 C. (2n-i+1)*i/2 D. (2n-i-1)*i/2
24、一个栈的入栈序列是a,b,c,d,e,则栈的不可能的输出序列是（ A ）
A. d c e a b B.d e c b a C. e d c b a D.a b c d e
25、假定一个链式队列的队头和队尾指针分别为front和rear，则判断队空的条件为( A )。 A. front == rear B. front != NULL C. rear != NULL D. front == NULL
26、当利用大小为n的数组顺序存储一个队列时，该队列的最大长度为（ B ）。 A. n-2 B. n-1 C. n D. n+1 27、循环链表主要优点是 （ D ）
A.不再需要头指针了
B.已知某个结点的位置后，能够容易找到它的直接前趋 C.在进行插入、删除运算时，能更好地保证链表不断开 D.从表中任一结点出发都能扫描到整个链表 28、稀疏矩阵一般采用(C )方法压缩存储。
A.三维数组 B.单链表 C.三元组表 D.散列表 29、链式栈与顺序栈相比，一个比较明显的优点是（B）
A 插入操作更加方便 B 通常不会出现栈满的情况 C 不会出现栈空的情况 D 删除操作更加方便
30、设有一顺序栈S，元素s1,s2,s3,s4,s5,s6依次进栈，如果6个元素出线的顺序是s2,s3,s4,s6,s5,s1,则栈的容量至少应该是（ B ） A.2 B. 3 C. 5 D.6
31、设有50行60列的二维数组A[50][60]，其元素长度为4字节，按行优先顺序存储，基地址为200，则元素A[18][25]的存储地址为（A）。 A．3700 B．4376 C．3900 D．4620
32、设C语言数组DATA[m+1]作为循环队列SQ的存储空间，front 为对头指针rear为对尾指针，则执行出
队操作的语句为（D）
A.front=front+1 B.front=(front+1)%m
C.rear=(rear+1)%m D. .front=(front+1)%(m+1) 33、循环队列的队满条件为 (C)
A.(sq.rear+1) % mazsize ==(sq.front+1) % maxsize; B.(sq.rear+1 % maxsize ==sq.front+1 C.sq.(rear+1) % maxsize ==sq.front D.sq.rear ==sq.front
34、在一棵二叉树的二叉链表中，空指针域数等于非空指针域数加（ A ）。
A. 2 B. 1 C. 0 D. –1 35、具有65个结点的完全二叉树的高度为（B）。（根的层次号为0） A．8 B．7 C．6 D．5
36、对某二叉树进行前序遍历的结果为ABDEFC，中序遍历的结果为DBFEAC，则后序遍历的结果为（ B ）
A．DBFEAC B．DFEBCA