数据结构阶段测评大全含答案(1)56页

1、数据结构-阶段测评11.单选题 1.15.0计算机识别、存储和加工处理的对象被统称为(A )您答对了· a数据·· b数据元素·· c数据结构·· d数据类型·本题考核数据的基本概念1.25.0非空的循环单链表head的尾结点（由p所指向）满足（C）。您答对了· ap->next=NULL·· bp=NULL·· cp->next=head·· dp=head·本题考核循环单链表的基本特点。1.35.0若长度为n的线性表采用

2、顺序存储结构存储，在第i个位置上插入一个新元素的时间复杂度为（A）。您答对了· aO(n)·· bO(1)·· cO(n2)·· dO(n3)·本题考核顺序表的插入运算的时间复杂度。1.45.0下面程序段中aij=0语句执行的时间复杂度是( D)。for(i=0;i<n;i+)for(j=1;j<m;j+)aij=0；您答对了· aO(n)·· bO(m+n+1)·· cO(m+n)·· dO(m*n)·本题考核时间复杂度的

3、计算方法1.55.0在一个具有n个结点的有序单链表中插入一个新结点并保持单链表仍然有序的时间复杂度是（B）。您答对了· aO(1)·· bO(n)·· cO(n2)·· dO(nlog2n)·因要保持有序，所以需要查找插入结点的位置，而在链表中查找结点位置的时间复杂度为O(n)，所以本题选B。1.65.0在一个长度为n的顺序表中删除第i个元素（1<=i<=n）时，需向前移动（A）个元素。您答对了· an-i·· bn-i+1·· cn-i-1·

4、· di·考核顺序表的基本操作1.75.0设顺序表有10个元素，则在第5个元素前插入一个元素所需移动元素的个数为（ B）。您答对了· a5·· b6·· c7·· d9·在第5个元素前插入元素需要将第5个元素开始的所有元素后移，所以本题答案为B。1.85.0算法指的是（D ）。您答对了· a计算机程序·· b解决问题的计算方法·· c排序算法·· d解决问题的有限运算序列·考核算法的基本概念1.95.0线性表采用链式

5、存储时，结点的存储地址（B ）您答对了· a必须是不连续的·· b连续与否均可·· c必须是连续的·· d和头结点的存储地址相连续·链式存储分配的结点在内存连续与不连续均可，所以答案选B。1.105.0对于只在表的首、尾两端进行插入操作的线性表，宜采用的存储结构为( C)。您答对了· a顺序表·· b用头指针表示的单循环链表·· c用尾指针表示的单循环链表·· d单链表·本题考核循环单链表的基本特点。1.115.0在长度为n的顺序表的第

6、i(1in+1)个位置上插入一个元素，元素的移动次数为( A)。您答对了· an-i+1·· bn-i·· ci·· di-1·本题考核顺序表的插入运算。1.125.0线性表若采用链式存储结构时，要求内存中可用存储单元的地址（D）。您答对了· a必须是连续的·· b部分地址必须是连续的·· c一定是不连续的·· d连续不连续都可以·考核链式存储结构的特点1.135.0在单链表中，指针p指向元素为x的结点，实现“删除x的后继”的语句是（B

7、 ）。您答对了· ap=p->next;·· bp->next=p->next->next;·· cp->next=p;·· dp=p->next->next;·本题考核单链表结点删除的基本操作1.145.0在一个单链表中，若删除p所指结点的后续结点，则执行（A）。您答对了· ap->next=p->next->next;·· bp=p->next; p->next=p->next->next;

8、3;· cp->next=p->next;·· dp =p->next->next;·考核单链表的删除操作1.155.0若结点的存储地址与其关键字之间存在某种映射关系，则称这种存储结构为（ D）。您答对了· a顺序存储结构·· b链式存储结构·· c索引存储结构·· d散列存储结构·本题考核散列存储的基本概念1.165.0若将数据结构形式定义为二元组(K，R)，其中K是数据元素的有限集合，则R是K上(D )。您答对了· a操作的有限集合

9、83;· b映象的有限集合·· c类型的有限集合·· d关系的有限集合·本题考核数据结构的基本概念1.175.0将长度为n的单链表链接在长度为m的单链表之后的算法的时间复杂度为（C ）。您答对了· aO（1）·· bO（n）·· cO（m）·· dO（m+n）·本题考核单链表的基本特点1.185.0关于栈和队列的说法中正确的是（ A）。您答对了· a栈和队列都是线性结构·· b栈是线性结构，队列不是线性结构·

10、3; c栈不是线性结构，队列是线性结构·· d栈和队列都不是线性结构·栈和队列都是一种特殊的线性表。1.195.0判定“带头结点的链队列为空”的条件是(C )。您答对了· aQ.front=NULL·· bQ.rear=NULL·· cQ.front=Q.rear·· dQ.front!=Q.rear·本题考核链队列的基本概念，答案选C。1.205.0设栈S和队列Q的初始状态为空，元素a,b,c,d,e,f,g依次入栈S。若每个元素出栈后立即进入队列Q，且7个元素出列的顺序是b,d,c

11、,f,e,a,g，则栈S的容量至少是（C）。您答对了· a1·· b2·· c3·· d4·本题考核栈与队列的性质以及进栈、出栈、进队、出队等基本操作方法。数据结构-阶段测评21.单选题 1.15.0引起循环队列队头位置发生变化的操作是(A )。您答对了· a出队·· b入队·· c取队头元素·· d取队尾元素·本题考核循环队列的基本操作。1.25.0从广义表L=(e),c,d)中分解得到原子c的操作为(B )。您答对了· a

12、head(head(head(L)·· bhead(tail(head(L)·· ctail(head(head(L)·· dtail(tail(head(L)·本题考核广义表的基本操作。1.35.0对矩阵压缩存储是为了（B ）。您答对了· a方便运算·· b节省空间·· c方便存储·· d提高运算速度·压缩存储就是为了节省存储空间。1.45.0顺序循环队列中（数组的大小为6），队头指示front和队尾指示rear的值分别为3和0，当从队列中删除

13、1个元素，再插入2个元素后，front和rear的值分别为（D）。您答对了· a5和1·· b2和4·· c1和5·· d4和2·本题考核顺序循环队列的基本特点。1.55.0设栈S和队列Q的初始状态为空，元素a,b,c,d,e,f,g依次入栈S。若每个元素出栈后立即进入队列Q，且7个元素出列的顺序是b,d,c,f,e,a,g，则栈S的容量至少是（C）。您答对了· a1·· b2·· c3·· d4·本题考核栈与队列的性质以及进栈、出栈、

14、进队、出队等基本操作方法。1.65.0队列和栈的主要区别是（ A）。您答对了· a限定插入和删除的位置不同·· b存储结构不同·· c所包含的运算个数不同·· d逻辑结构不同·本题考核栈与队列的基本特点1.75.0表达式a*(b+c)-d的后缀表达式是(B)。您答对了· aabc*d+-·· babc+*d-·· cabc*+d-·· d-+*abcd·本题考核中缀表达式转后缀表达式的基本方法。1.85.0栈是一种特殊的线性表，具有（B

15、）性质。您答对了· a先进先出·· b先进后出·· c后进后出·· d顺序进出·考核栈的基本概念1.95.0对广义表L=(a,b),(c,d),(e,f)执行操作tail(tail(L)的结果是(B)您答对了· a(e,f)·· b(e,f)·· c(f)·· d( )·考核广义表的基本操作1.105.0设栈的输入序列为（1、2、3、4），则不可能的出栈序列为（ C）。您答对了· a1243·· b2134

16、·· c4312·· d1432·本题考核栈的进栈与出栈特点，根据先进后出、后进先出的特点，可知本题答案选C。1.115.0操作系统的CPU管理程序为实现先来先服务的作业管理，需要设置一个存储区，用于记录当前用户作业，这个存储区的逻辑结构是（ B）。您答对了· a栈·· b队列·· c树·· d图·本题考核队列的基本特点。1.125.0若进栈序列为1，2，3，4，5，6，且进栈和出栈可以穿插进行，则不可能出现的出栈序列是( C)。您答对了· a2，4，3，

17、1，5，6·· b4，3，2，1，5，6·· c2，3，5，1，6，4·· d3，2，4，1，6，5·核具有先进后出，后进先出的特点，根据这个特点，可知本题答案为C。1.135.0判定“带头结点的链队列为空”的条件是(C )。您答对了· aQ.front=NULL·· bQ.rear=NULL·· cQ.front=Q.rear·· dQ.front!=Q.rear·本题考核链队列的基本概念，答案选C。1.145.0关于栈和队列的说法中正确的是（

18、 A）。您答对了· a栈和队列都是线性结构·· b栈是线性结构，队列不是线性结构·· c栈不是线性结构，队列是线性结构·· d栈和队列都不是线性结构·栈和队列都是一种特殊的线性表。1.155.0已知循环队列的存储空间为数组data21，且当前队列的头指针和尾指针的值分别为8和3，则该队列当前长度为(C)您答对了· a5·· b6·· c16·· d17·考核顺序循环队列的特点1.165.0从广义表LS（(p, q), r, s）中分解出

19、原子q的运算是（B）。您答对了· atail (head (LS)·· bhead (tail (head (LS)·· chead (tail (LS)·· dtail (tail (head (LS)·本题考核广义表的基本操作。1.175.0链栈与顺序栈相比，比较明显的优点是( D)。您答对了· a插入操作更加方便·· b删除操作更加方便·· c不会出现下溢的情况·· d不会出现上溢的情况·链栈采用动态内存分配，一般不会出现栈满的情

20、况，即一般不会出现上溢的情况。所以答案选D。1.185.0将长度为n的单链表链接在长度为m的单链表之后的算法的时间复杂度为（ C）。您答对了· aO（1）·· bO（n）·· cO（m）·· dO（m+n）·本题考核单链表的基本特点1.195.0在一个具有n个结点的有序单链表中插入一个新结点并保持单链表仍然有序的时间复杂度是（B）。您答对了· aO(1)·· bO(n)·· cO(n2)·· dO(nlog2n)·因要保持有序，所以需要

21、查找插入结点的位置，而在链表中查找结点位置的时间复杂度为O(n)，所以本题选B。1.205.0下面程序段中aij=0语句执行的时间复杂度是( D)。for(i=0;i<n;i+)for(j=1;j<m;j+)aij=0；您答对了· aO(n)·· bO(m+n+1)·· cO(m+n)·· dO(m*n)·本题考核时间复杂度的计算方法数据结构-阶段测评31.单选题 1.15.0以二叉链表作为二叉树的存储结构，有具有n个结点的二叉链表中（n>0），空链域的个数为（ B）。您答对了· a2n

22、-1·· bn+1·· cn-1·· d2n+1·n个结点的二叉树共有n-1条边，所以空链域的个数为n+1。1.25.0若邻接表中有奇数个表结点，则一定（D）。您答对了· a图中有奇数个顶点·· b图中有偶数个顶点·· c图为无向图·· d图为有向图·本题考核图的邻接表存储结构及其特点。1.35.0一棵完全二叉树有999个结点，它的深度为（B）。您答对了· a9·· b10·· c11·

23、· d12·本题考核完全二叉树的性质。1.45.0一棵完全二叉树上有1001个结点，其中叶子结点的个数为（D）。您答对了· a250·· b500·· c254·· d501·本题考核完全二叉树的性质1.55.0n个顶点的强连通图中至少含有（B ）。您答对了· an-1条有向边·· bn条有向边·· cn（n-1）/2条有向边·· dn（n-1）条有向边·本题考核强连通图的基本性质。1.65.0无向图中一个顶点的度是

24、指图中( B)。您答对了· a通过该顶点的简单路径数·· b与该顶点相邻接的顶点数·· c通过该顶点的回路数·· d与该顶点连通的顶点数·本题考核顶点的度的基本概念。1.75.0下列哪一个选项不是图所示有向图的拓扑排序结果（C）。您答对了· aAFBCDE·· bFABCDE·· cFACBDE·· dFADBCE·本题考核图的拓扑排序基本思想。1.85.0设有一个有向图如图所示，请指出下列哪个序列不是该图的拓扑排序序列（C ）。您答对

25、了· aEAFBGDC·· bAEBCGFD·· cABCGEFD·· dEABGFCD·本题考核图的拓扑排序基本思想。1.95.0无向图的邻接矩阵是一个（ A）您答对了· a对称矩阵·· b零矩阵·· c上三角矩阵·· d对角矩阵·由于是无向图，所以该图的邻接矩阵是对称矩阵。1.105.0如果某图的邻接矩阵是对角线元素均为零的上三角矩阵，则此图是（D）。您答对了· a有向完全图·· b连通图·&

26、#183; c强连通图·· d有向无环图·本题考核图的邻接矩阵存储结构的基本特点。1.115.0设有向图的邻接链表如图所示，则该图的边的数目是（ A）。您答对了· a6·· b7·· c8·· d12·本题考核图的邻接表存储结构的基本特点。1.125.0下列陈述中正确的是( D)您答对了· a二叉树是度为2的有序树·· b二叉树中结点只有一个孩子时无左右之分·· c二叉树中必有度为2的结点·· d二叉树中最多只有两棵

27、子树，并且有左右之分·本题考核二叉树与度为二的树的区别，答案选D。1.135.0对于一棵具有n个节点，度为4的树来说，（ A）。您答对了· a树的高度至多是n-3·· b树的高度至多是n-4·· c第i层至多有4（i-1）个节点·· d至少在某一层上正好有4个节点·本题考核树的基本性质。1.145.0一棵含18个结点的二叉树的高度至少为( C)。您答对了· a3·· b4·· c5·· d6·当二叉树为完全二叉树时该树具有最小

28、高度。本题考核二叉排序树的基本概念。1.155.0假设一个有n个顶点和e条弧的有向图用邻接表表示，则删除与某个顶点vi相关的所有弧的时间复杂度是（B）。您答对了· aO(n)·· bO(e)·· cO(n+e)·· dO(n*e)·考核邻接表的基本特点1.165.0设有一棵哈夫曼树的节点总数为35，则该哈夫曼树共有（A ）个叶子结点。您答对了· a18·· b20·· c35·· d30·具有n个叶子结点（外部结点）的哈夫曼树具有n-1

29、个内部结点。根据这个性质可以计算出本题的叶子结点数为18。1.175.0深度为k的二叉树至多有（C ）您答对了· a2k个结点·· b2k-1个结点·· c2k-1个结点·· d2k-1-1个结点·当二叉树为满二叉树时，具有最多的结点个数。1.185.0无向图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）。您答对了· aa,b,e,c,d,f··

30、; ba,c,f,e,b,d·· ca,e,d,f,c,b·· da,e,b,c,f,d·考核深度优先遍历的基本思想1.195.0按照二叉树的定义，具有三个结点的二叉树有（A ）。您答对了· a5种·· b4种·· c3种·· d6种·二叉树严格区分左、右子树，根据定义易知具有三个结点的二叉树共有5种。1.205.0在按层次遍历二叉树的算法中，需要借助的辅助数据结构是（A）。您答对了· a队列·· b栈·· c线性表

31、·· d有序表·层次遍历二叉树需要用到队列结构。数据结构-阶段测评41.单选题 1.15.0在下列各棵二叉树中，二叉排序树是(B)。您答对了· aA·· bB·· cC·· dD·1.25.0若需在O（nlogn）的时间内完成对数组的排序，且要求排序算法是稳定的，则可选择的排序方法是（B）。您答对了· a堆排序·· b归并排序·· c快速排序·· d直接插入排序·考核各种排序算法的稳定性与时间复杂度1.35

32、.0对关键字序列(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)·本题考核希尔排序的基本思想。1.45.0设二叉排序树中关键字由1至1000的整数构成，现要检索关键字为363的结点，下述关键字序列哪一个不可能是二叉排序树上搜索到的序列（

33、C ）。您答对了· a2， 252， 401， 398， 330， 344， 397， 363·· b924， 220， 911， 244， 898， 258， 362， 363·· c952， 202， 911， 240， 912， 245， 363·· d2， 399， 387， 219， 266， 382， 381， 278， 363·本题考核二分查找的基本思想。1.55.0在待排关键字序列基本有序的前提下，效率最高的排序方法是(A )。您答对了· a直接插入排序·· b快速排序

34、·· c直接选择排序·· d归并排序·直接插入排序在序列基本有序的情况下，具有较好的排序效率。本题答案选A。1.65.0希尔排序的增量序列必须是（ C）。您答对了· a递增的·· b随机的·· c递减的·· d非递减的·希尔排序是一种改进的插入排序，要求增量序列必须递减的。1.75.0有数据53，30，37，12，45，24，96，从空二叉树开始逐步插入数据形成二叉排序树，若希望高度最小，则应该选择下列（A）的序列输入。您答对了· a37,24,12,30

35、,53,45,96·· b45,24,53,12,37,96,30·· c12,24,30,37,45,53,96·· d30,24,12,37,45,96,53·考核二叉排序树的建立算法1.85.0查找运算主要是对关键字的（C ）。您答对了· a移位·· b交换·· c比较·· d定位·查找运算主要是通过比较判断是否查找成功。1.95.0已知一组关键字为25,48,36,72,79,82,23,40,16,35，其中每相邻两个为有序子序列。采用

36、归并排序对这些子序列进行一趟两两归并的结果是( C)。您答对了· a25,36,48,72,16,23,35,40,79,82·· b25,36,48,72,16,23,40,79,82,35·· c25,36,48,72,23,40,79,82,16,35·· d16,23,25,35,36,40,48,72,79,82·本题考核归并排序的基本思想。1.105.0对于哈希函数H(key)=key%13，被称为同义词的关键字是（C）。您答对了· a35和41·· b23和39·

37、;· c25和51·· d15和44·考核散列存储中同义词的基本概念1.115.0在下列算法中，（B）算法可能出现下列情况：在最后一趟开始之前，所有的元素都不在其最终的位置上。您答对了· a堆排序·· b插入排序·· c冒泡排序·· d快速排序·本题考核插入排序的基本思想。1.125.0适用于折半查找的表的存储方式及元素排列要求为（D）。您答对了· a链式方式存储，元素无序·· b链式方式存储，元素有序·· c顺序方式存储，元素无序