03数据结构阶段测评共80题

1、 1.数据结构-阶段测评1 1 .计算机识别、存储和加工处理的对象被统称为(A) A.数据B.数据元素C.数据Z构D.数据类型本题考核数据的基本概念 2 .非空的循环单链表head的尾结点(由p所指向)满足(Q。 A.p-next=NULLB.p=NULIC.p-next=headD.p=head 本题考核循环单链表的基本特点。 3 .若长度为n的线性表采用顺序存储结构存储，在第i个位置上插入一个新元素的时间复杂度为(A)。 A.O(n)B.O(1)C.O(n2)D.O(n3) 本题考核顺序表的插入运算的时间复杂度。 4 .下面程序段中aij=0语句执行的时间复杂度是(D)。 for(i=0;

2、in;i+) for(j=1;jO(n)B.O(m+n+1)C.O(m+n)D.O(m*n) 本题考核时间复杂度的计算方法 5 .在一个具有n个结点的有序单链表中插入一个新结点并保持单链表仍然有序的时间复杂度是(B)。 A.O(1)B.O(n)C.O(n2)D.O(nlog2n) 因要保持有序，所以需要查找插入结点的位置，而在链表中查找结点位置的时间复杂度为O(n),所以本题选Bo 6 .在一个长度为n的顺序表中删除第i个元素(1=inext;B.p-next=p-next-next;C.p-next=p;D.p=p-next-next;本题考核单链表结点删除的基本操作 14 .在一个单链表中

3、，若删除p所指结点的后续结点，则执行(A)。 A.p-next=p-next-next;B.p=p-next;p-next=p-next-next;C.p-next=p-next;D.p=p-next-next;考核单链表的删除操作 15 .若结点的存储地址与其关键字之间存在某种映射关系，则称这种存储结构为(D)。 A.顺序存储结构B.链式存储结构C.索引存储结构D.散列存储结构本题考核散列存储的基本概念 16 .若将数据结构形式定义为二元组(K,R),其中K是数据元素的有限集合，则R是K上(D)。 A.操作的有限集合B.映象的有限集合C.类型的有限集合D.关系的有限集合本题考核数据结构的基本

4、概念 17 .将长度为n的单链表链接在长度为m的单链表之后的算法的时间复杂度为(C)。 A.O(1)B.O(n)C.O(m)D.O(m+n)本题考核单链表的基本特点 18 .关于栈和队列的说法中正确的是(A)。 A.栈和队列都是线性结构B.栈是线性结构，队列不是线性结构 C栈不是线性结构，队列是线性结构D.栈和队列都不是线性结构 栈和队列都是一种特殊的线性表。 19 .判定“带头结点的链队列为空”的条件是(C)。 A.Q.front=NULLB.Q.rear=NULLC.Q.front=Q.rearD.Q.front!=Q.rear本题考核链队列的基本概念，答案选Co 20 .设栈S和队列Q的

5、初始状态为空，元素a,b,c,d,e,f,g依次入栈S。若每个元素出栈后立即进入队列Q,且7个元 素出列的顺序是b,d,c,f,e,a,g,则栈S的容量至少是(C)。 A.1B.2C.3D.4 本题考核栈与队列的性质以及进栈、出栈、进队、出队等基本操作方法。 21 数据结构-阶段测评2 1 .引起循环队列队头位置发生变化的操作是(A)。 A.出队B.入队C取队头元素D取队尾元素本题考核循环队列的基本操作。 2 .从广义表L=(e),c,d)中分解得到原子c的操作为(B)。 A.head(head(head(L)B.head(tail(head(L)C.tail(head(head(L)D.ta

6、il(tail(head(L)本题考核广义表的基本操作。| 3 .对矩阵压缩存储是为了(B)。 A.方便运算B.节省空间C方便存储D.提高运算速度压缩存储就是为了节省存储空间。 4 .顺序循环队列中(数组的大小为6),队头指示front和队尾指示rear的值分别为3和0,当从队列中删除1个 元素，再插入2个元素后，front和rear的值分别为(D)。 A.5和1B.2和4C.1和5D.4和2本题考核顺序循环队列的基本特点。 5 .设栈S和队列Q的初始状态为空，元素a,b,c,d,e,f,g依次入栈S。若每个元素出栈后立即进入队列Q,且7个元素出列的顺序是b,d,c,f,e,a,g,则栈S的容

7、量至少是(C)。 A.1B.2C.3D.4 本题考核栈与队列的性质以及进栈、出栈、进队、出队等基本操作方法。 6 .队列和栈的主要区别是(A)。 A.限定插入和删除的位置不同B.存储结构不同C.所包含的运算个数不同D.逻辑结构不同 本题考核栈与队列的基本特点| 7 .表达式a*(b+c)-d的后缀表达式是(B)。 A.abc*d+-B.abc+*d-C.abc*+d-D.-+*abcd本题考核中缀表达式转后缀表达式的基本方法。 8 .栈是一种特殊的线性表，具有(B)性质。 A.先进先出B.先进后出C后进后出D.顺序进出 考核栈的基本概念 9 .对广义表L=(a,b),(c,d),(e,f)执行

8、操作tail(tail(L)的结果是(B) A.(e,f)B.(e,f)C.(f)D.()考核广义表的基本操作 10 .设栈的输入序列为(1、2、3、4),则不可能的出栈序列为(C)。 A.1243B.2134C.4312D.1432 本题考核栈的进栈与出栈特点，根据先进后出、后进先出的特点，可知本题答案选Co 11 .操作系统的CPU管理程序为实现先来先服务的作业管理，需要设置一个存储区，用于记录当前用户作业，这个存 储区的逻辑结构是(B)。 A.栈B.队列C树D.图本题考核队列的基本特点。 12 .若进栈序列为1,2,3,4,5,6,且进栈和出栈可以穿插进行，则不可能出现的出栈序列是(C)

9、。 A.2,4,3,1,5,6B.4,3,2,1,5,6C.2,3,5,1,6,4D.3,2,4,1,6,5核具有先进后出，后进先出的特点，根据这个特点，可知本题答案为C。 13 .判定“带头结点的链队列为空”的条件是(C)。 A.Q.front=NULLB.Q.rear=NULLC.Q.front=Q.rearD.Q.front!=Q.rear本题考核链队列的基本概念，答案选Co 14 .关于栈和队列的说法中正确的是(A)。 A.栈和队列都是线性结构B.栈是线性结构，队列不是线性结构 C栈不是线性结构，队列是线性结构D.栈和队列都不是线性结构 栈和队列都是一种特殊的线性表。 15 .已知循环

10、队列的存储空间为数组data21，且当前队列的头指针和尾指针的值分别为8和3,则该队列当前长度 为(C) A.5B.6C.16D.17 考核顺序循环队列的特点 16 .从广义表LS=(p,q),r,s)中分解出原子q的运算是(B)。 A.tail(head(LS)B.head(tail(head(LS)C.head(tail(LS)D.tail(tail(head(LS)本题考核广义表的基本操作。 17 .链栈与顺序栈相比，比较明显的优点是(D)。 A.插入操作更加方便B.删除操作更加方便C不会出现下溢的情况D.不会出现上溢的情况 链栈采用动态内存分配，一般不会出现栈满的情况，即一般不会出现上

11、溢的情况。所以答案选Do 18 .将长度为n的单链表链接在长度为m的单链表之后的算法的时间复杂度为(C)。 A.O(1)B.O(n)C.O(m)D.O(m+n)本题考核单链表的基本特点 19 .在一个具有n个结点的有序单链表中插入一个新结点并保持单链表仍然有序的时间复杂度是(B)。 A.O(1)B.O(n)C.O(n2)D.O(nlog2n) 因要保持有序，所以需要查找插入结点的位置，而在链表中查找结点位置的时间复杂度为O(n),所以本题选Bo 20 .下面程序段中aij=0语句执行的时间复杂度是(D)。 for(i=0;in;i+) for(j=1;j0),空链域的个数为(B)。 A.2n-

12、1B.n+1C.n-1D.2n+1 n个结点的二叉树共有n-1条边，所以空链域的个数为n+1。 2 .若邻接表中有奇数个表结点，则一定(D)。 A.图中有奇数个顶点B.图中有偶数个顶点C.图为无向图D.图为有向图 本题考核图的邻接表存储结构及其特点。| 3 .一棵完全二叉树有999个结点，它的深度为(B)。 A.9B.10C.11D.12 本题考核完全二叉树的性质。 4 .一棵完全二叉树上有1001个结点，其中叶子结点的个数为(D)。 A.250B.500C.254D.501 本题考核完全二叉树的性质 5 .n个顶点的强连通图中至少含有(B)。 A.n-1条有向边B.n条有向边C.n(n-1)

13、/2条有向边D.n(n-1)条有向边 本题考核强连通图的基本性质。 6 .无向图中一个顶点的度是指图中(B)。 A.通过该顶点的简单路径数B.与该顶点相邻接的顶点数C.通过该顶点的回路数D.与该顶点连通的顶点数 本题考核顶点的度的基本概念。 7 .下列哪一个选项不是下图所示有向图的拓扑排序结果(C)。 A.AFBCDEB.FABCDEC.FACBDED.FADBCE本题考核图的拓扑排序基本思想。 8 .设有一个有向图如图所示，请指出下列哪个序列不是该图的拓扑排序序列(C)。 A.EAFBGDCB.AEBCGFDC.ABCGEFDD.EABGFCD 本题考核图的拓扑排序基本思想。 9 .无向图的

14、邻接矩阵是一个(A) A.对称矢I阵B.零矩阵C上三角矢I阵D.对角矩阵 由于是无向图，所以该图的邻接矩阵是对称矩阵。 10 .如果某图的邻接矩阵是对角线元素均为零的上三角矩阵，则此图是(D)。 A.有向完全图B.连通图C强连通图D.有向无环图 本题考核图的邻接矩阵存储结构的基本特点。 11 .设有向图的邻接链表如图所示，则该图的边的数目是(A)。 A.6B7C.8D.12 本题考核图的邻接表存储结构的基本特点。 12 .下列陈述中正确的是(D) A.二叉树是度为2的有序树B.二叉树中结点只有一个孩子时无左右之分 C二叉树中必有度为2的结点D.二叉树中最多只有两棵子树，并且有左右之分 本题考核

15、二叉树与度为二的树的区别，答案选D。 13 .对于一棵具有n个节点，度为4的树来说，(A)。 A.树的高度至多是n-3B.树的高度至多是n-4 C第i层至多有4(i-1)个节点D.至少在某一层上正好有4个节点 本题考核树的基本性质。 14 .一棵含18个结点的二叉树的高度至少为(C)。 A.3B.4C.5D.6 当二叉树为完全二叉树时该树具有最小高度。 本题考核二叉排序树的基本概念。 15 .假设一个有n个顶点和e条弧的有向图用邻接表表示，则删除与某个顶点vi相关的所有弧的时间复杂度是(B)。 A.O(n)B.O(e)C.O(n+e)D.O(n*e) 考核邻接表的基本特点 16 .设有一棵哈夫

16、曼树的节点总数为35,则该哈夫曼树共有(A)个叶子结点。 A.18B.20C.35D.30 具有n个叶子结点(外部结点)的哈夫曼树具有n-1个内部结点。根据这个性质可以计算出本题的叶子结点数为18。 17 .深度为k的二叉树至多有(C) A.2k个结点B.2k-1个结点C.2k-1个结点D.2k-1-1个结点 当二叉树为满二叉树时，具有最多的结点个数。 18 .无向图G=(V,E),其中：V=a,b,c,d,e,f,E=(a,b),(a,e),(a,c),(b,e),(c,f),(f,d), (e,d),对该图进行深度优先遍历，得到的顶点序列正确的是(C)。 A.a,b,e,c,d,fB.a,

17、c,f,e,b,dC.a,e,d,f,c,bD.a,e,b,c,f,d 考核深度优先遍历的基本思想 19 .按照二叉树的定义，具有三个结点的二叉树有（A）。 A.5种B.4种C.3种D.6种 二叉树严格区分左、右子树，根据定义易知具有三个结点的二叉树共有5种。 20 .在按层次遍历二叉树的算法中，需要借助的辅助数据结构是（A）。 A.队列B.栈C线性表D.有序表 层次遍历二叉树需要用到队列结构。 21 数据结构-阶段测评4 1.在下列各棵二叉树中，二叉排序树是（B）。 A.AB.BC.CD.D 2 .若需在O（nlogn）的时间内完成对数组的排序，且要求排序算法是稳定的，则可选择的排序方法是（

18、B）。 A.堆排序B.归并排序C快速排序D.直接插入排序考核各种排序算法的稳定性与时间复杂度 3 .对关键字序列（56,23,78,92,88,67,19,34）进行增量为3的一趟希尔排序的结果为（D）。 A.（19,23,56,34,78,67,88,92）B.（23,56,78,66,88,92,19,34） C.（19,23,34,56,67,78,88,92）D.（19,23,67,56,34,78,92,88） 本题考核希尔排序的基本思想。 4 .设二叉排序树中关键字由1至1000的整数构成，现要检索关键字为363的结点，下述关键字序列哪一个不可能是 二叉排序树上搜索到的序列（C）。

19、 A.2,252,401,398,330,344,397,363B.924,220,911,244,898,258,362,363 C.952,202,911,240,912,245,363D.2,399,387,219,266,382,381,278,363 本题考核二分查找的基本思想。 5 .在待排关键字序列基本有序的前提下，效率最高的排序方法是（A）。 A.直接插入排序B.快速排序C.直接选择排序D归并排序直接插入排序在序列基本有序的情况下，具有较好的排序效率。本题答案选Ao 6 .希尔排序的增量序列必须是（C）。 A.递增的B.随机的C.递减的D.非递减的希尔排序是一种改进的插入排序，

20、要求增量序列必须递减的。 7 .有数据53,30,37,12,45,24,96,从空二叉树开始逐步插入数据形成二叉排序树，若希望高度最小，则应该选择下列（A）的序列输入。 A.37,24,12,30,53,45,96B.45,24,53,12,37,96,30C.12,24,30,37,45,53,96D.30,24,12,37,45,96,53考核二叉排序树的建立算法 8 .查找运算主要是对关键字的（C）。 A.移位B.交换C比较D.定位查找运算主要是通过比较判断是否查找成功。 9 .已知一组关键字为25,48,36,72,79,82,23,40,16,35,其中每相邻两个为有序子序列。采用

21、归并排序 对这些子序列进行一趟两两归并的结果是（C）。 A.25,36,48,72,16,23,35,40,79,82B.25,36,48,72,16,23,40,79,82,35 C.25,36,48,72,23,40,79,82,16,35D.16,23,25,35,36,40,48,72,79,82本题考核归并排序的基本思想。 10 .对于哈希函数H（key）=key%13,被称为同义词的关键字是（C）。 A.35和41B.23和39C.25和51D.15和44考核散列存储中同义词的基本概念 11 .在下列算法中，（B）算法可能出现下列情况：在最后一趟开始之前，所有的元素都不在其最终的位置上。 A.堆排序B.插入排序C冒泡排序D.快速排序本题考核插入排序的基本思想。 12 .适用于折半查找的表的存储方式及元素排列要求为（D）。 A.链式方式存储，元素无序B.链式方式存储，元素有序 C顺序方式存储，元素无序D.顺序方式存储，元素有序 考核折半查找的基本概念 13 .下列说法错误的是（D）。 A.冒泡排序在数据有序的情况下具有最少的比较次数。B.直接