数据结构阶段测评大全含答案(共57页).docx

《数据结构阶段测评大全含答案(共57页).docx》由会员分享，可在线阅读，更多相关《数据结构阶段测评大全含答案(共57页).docx（57页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

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的线性表采用顺序存储结构存储，在第i个位置上插入一个新元素的时间复杂度为（A）。您答对了 aO(n) bO(1) cO(n2) dO(n3)本题考核顺序表的插入运算的时间复杂度。1.45.0下面

2、程序段中aij=0语句执行的时间复杂度是( D)。for(i=0;in;i+)for(j=1;jm;j+)aij=0；您答对了 aO(n) bO(m+n+1) cO(m+n) dO(m*n)本题考核时间复杂度的计算方法1.55.0在一个具有n个结点的有序单链表中插入一个新结点并保持单链表仍然有序的时间复杂度是（B）。您答对了 aO(1) bO(n) cO(n2) dO(nlog2n)因要保持有序，所以需要查找插入结点的位置，而在链表中查找结点位置的时间复杂度为O(n)，所以本题选B。1.65.0在一个长度为n的顺序表中删除第i个元素（1=inext; bp-next=p-next-next;

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

4、K是数据元素的有限集合，则R是K上(D )。您答对了 a操作的有限集合 b映象的有限集合 c类型的有限集合 d关系的有限集合本题考核数据结构的基本概念1.175.0将长度为n的单链表链接在长度为m的单链表之后的算法的时间复杂度为（C ）。您答对了 aO（1） bO（n） cO（m） dO（m+n）本题考核单链表的基本特点1.185.0关于栈和队列的说法中正确的是（ A）。您答对了 a栈和队列都是线性结构 b栈是线性结构，队列不是线性结构 c栈不是线性结构，队列是线性结构 d栈和队列都不是线性结构栈和队列都是一种特殊的线性表。1.195.0判定“带头结点的链队列为空”的条件是(C )。您答对了

5、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,f,e,a,g，则栈S的容量至少是（C）。您答对了 a1 b2 c3 d4本题考核栈与队列的性质以及进栈、出栈、进队、出队等基本操作方法。数据结构-阶段测评21.单选题 1.15.0引起循环队列队头位置发生变化的操作是(A )。您答对了 a出队 b入队 c取队头元素 d取队尾元素本题考核循环队

6、列的基本操作。1.25.0从广义表L=(e),c,d)中分解得到原子c的操作为(B )。您答对了 ahead(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，当从队列中删除1个元素，再插入2个元素后，front和rear的值分别为（D）。您答对了 a5

7、和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本题考核栈与队列的性质以及进栈、出栈、进队、出队等基本操作方法。1.65.0队列和栈的主要区别是（ A）。您答对了 a限定插入和删除的位置不同 b存储结构不同 c所包含的运算个数不同 d逻辑结构不同本题考核栈与队列的基本特点1.75.0表达式a*(b+c)-d的后缀表达式是(B)。您答对了 aabc*d+-

8、babc+*d- cabc*+d- d-+*abcd本题考核中缀表达式转后缀表达式的基本方法。1.85.0栈是一种特殊的线性表，具有（B）性质。您答对了 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 c4312 d1432本题考核栈的进栈与出栈特点，根据先进后出、后进先出的特点，可知本题答

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

10、ar=NULL cQ.front=Q.rear dQ.front!=Q.rear本题考核链队列的基本概念，答案选C。1.145.0关于栈和队列的说法中正确的是（ A）。您答对了 a栈和队列都是线性结构 b栈是线性结构，队列不是线性结构 c栈不是线性结构，队列是线性结构 d栈和队列都不是线性结构栈和队列都是一种特殊的线性表。1.155.0已知循环队列的存储空间为数组data21，且当前队列的头指针和尾指针的值分别为8和3，则该队列当前长度为(C)您答对了 a5 b6 c16 d17考核顺序循环队列的特点1.165.0从广义表LS（(p, q), r, s）中分解出原子q的运算是（B）。您答对了

11、atail (head (LS) bhead (tail (head (LS) chead (tail (LS) dtail (tail (head (LS)本题考核广义表的基本操作。1.175.0链栈与顺序栈相比，比较明显的优点是( D)。您答对了 a插入操作更加方便 b删除操作更加方便 c不会出现下溢的情况 d不会出现上溢的情况链栈采用动态内存分配，一般不会出现栈满的情况，即一般不会出现上溢的情况。所以答案选D。1.185.0将长度为n的单链表链接在长度为m的单链表之后的算法的时间复杂度为（ C）。您答对了 aO（1） bO（n） cO（m） dO（m+n）本题考核单链表的基本特点1.19

12、5.0在一个具有n个结点的有序单链表中插入一个新结点并保持单链表仍然有序的时间复杂度是（B）。您答对了 aO(1) bO(n) cO(n2) dO(nlog2n)因要保持有序，所以需要查找插入结点的位置，而在链表中查找结点位置的时间复杂度为O(n)，所以本题选B。1.205.0下面程序段中aij=0语句执行的时间复杂度是( D)。for(i=0;in;i+)for(j=1;j0），空链域的个数为（ B）。您答对了 a2n-1 bn+1 cn-1 d2n+1n个结点的二叉树共有n-1条边，所以空链域的个数为n+1。1.25.0若邻接表中有奇数个表结点，则一定（D）。您答对了 a图中有奇数个顶点

13、b图中有偶数个顶点 c图为无向图 d图为有向图本题考核图的邻接表存储结构及其特点。1.35.0一棵完全二叉树有999个结点，它的深度为（B）。您答对了 a9 b10 c11 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无向图中一个顶点的度是指图中( B)。您答对了 a通过该顶点的简单

14、路径数 b与该顶点相邻接的顶点数 c通过该顶点的回路数 d与该顶点连通的顶点数本题考核顶点的度的基本概念。1.75.0下列哪一个选项不是图所示有向图的拓扑排序结果（C）。您答对了 aAFBCDE bFABCDE cFACBDE dFADBCE本题考核图的拓扑排序基本思想。1.85.0设有一个有向图如图所示，请指出下列哪个序列不是该图的拓扑排序序列（C ）。您答对了 aEAFBGDC bAEBCGFD cABCGEFD dEABGFCD本题考核图的拓扑排序基本思想。1.95.0无向图的邻接矩阵是一个（ A）您答对了 a对称矩阵 b零矩阵 c上三角矩阵 d对角矩阵由于是无向图，所以该图的邻接矩阵是

15、对称矩阵。1.105.0如果某图的邻接矩阵是对角线元素均为零的上三角矩阵，则此图是（D）。您答对了 a有向完全图 b连通图 c强连通图 d有向无环图本题考核图的邻接矩阵存储结构的基本特点。1.115.0设有向图的邻接链表如图所示，则该图的边的数目是（ A）。您答对了 a6 b7 c8 d12本题考核图的邻接表存储结构的基本特点。1.125.0下列陈述中正确的是( D)您答对了 a二叉树是度为2的有序树 b二叉树中结点只有一个孩子时无左右之分 c二叉树中必有度为2的结点 d二叉树中最多只有两棵子树，并且有左右之分本题考核二叉树与度为二的树的区别，答案选D。1.135.0对于一棵具有n个节点，度为

16、4的树来说，（ A）。您答对了 a树的高度至多是n-3 b树的高度至多是n-4 c第i层至多有4（i-1）个节点 d至少在某一层上正好有4个节点本题考核树的基本性质。1.145.0一棵含18个结点的二叉树的高度至少为( C)。您答对了 a3 b4 c5 d6当二叉树为完全二叉树时该树具有最小高度。本题考核二叉排序树的基本概念。1.155.0假设一个有n个顶点和e条弧的有向图用邻接表表示，则删除与某个顶点vi相关的所有弧的时间复杂度是（B）。您答对了 aO(n) bO(e) cO(n+e) dO(n*e)考核邻接表的基本特点1.165.0设有一棵哈夫曼树的节点总数为35，则该哈夫曼树共有（A ）

17、个叶子结点。您答对了 a18 b20 c35 d30具有n个叶子结点（外部结点）的哈夫曼树具有n-1个内部结点。根据这个性质可以计算出本题的叶子结点数为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 ba,c,f,e,b,d c

18、a,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线性表 d有序表层次遍历二叉树需要用到队列结构。数据结构-阶段测评41.单选题 1.15.0在下列各棵二叉树中，二叉排序树是(B)。您答对了 aA bB cC dD1.25.0若需在O（nlogn）的时间内完成对数组的排序，且要求排序算法是稳定的，则可选

19、择的排序方法是（B）。您答对了 a堆排序 b归并排序 c快速排序 d直接插入排序考核各种排序算法的稳定性与时间复杂度1.35.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的结点，下述关键字序列哪一个不可能

20、是二叉排序树上搜索到的序列（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快速排序 c直接选择排序 d归并排序直接插入排序在序列基本有序的情况下，具有较好的排序效率。本题答案选A。1.6

21、5.0希尔排序的增量序列必须是（ C）。您答对了 a递增的 b随机的 c递减的 d非递减的希尔排序是一种改进的插入排序，要求增量序列必须递减的。1.75.0有数据53，30，37，12，45，24，96，从空二叉树开始逐步插入数据形成二叉排序树，若希望高度最小，则应该选择下列（A）的序列输入。您答对了 a37,24,12,30,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定位查找运算主要

22、是通过比较判断是否查找成功。1.95.0已知一组关键字为25,48,36,72,79,82,23,40,16,35，其中每相邻两个为有序子序列。采用归并排序对这些子序列进行一趟两两归并的结果是( 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

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

24、数。 c二路归并排序需要借助O（n）的存储空间。 d基数排序适合于实型数据的排序。考核各种排序的基本思想1.145.0线性表适合于顺序查找的存储结构是（C ）。您答对了 a索引存储 b压缩存储 c顺序存储或链式存储 d散列存储顺序存储或链式存储都可以采用顺序查找。1.155.0排序算法中，第一趟排序后，任一元素都不能确定其最终位置的算法是（ D）。您答对了 a选择排序 b快速排序 c冒泡排序 d插入排序选择排序，快速排序和冒泡排序在一趟排序后有一个元素可以确定其最终位置。而插入排序是将一个数据插入到有序树的适当位置，这个位置不一定是最终的位置。1.165.0如果在排序过程中，每次均将一个待排序

25、的记录按关键字大小加入到前面已经有序的子表中的适当位置，则该排序方法称为（A）。您答对了 a插入排序 b归并排序 c冒泡排序 d堆排序本题考核直接插入排序的基本概念。1.175.0一个序列中有10000个元素，若只想得到其中前10个最小元素，最好采用（A）方法。您答对了 a快速排序 b堆排序 c插入排序 d二路归并排序本题考核堆排序的基本特点。1.185.0设有一棵哈夫曼树的节点总数为35，则该哈夫曼树共有（ A）个叶子结点。您答对了 a18 b20 c35 d30具有n个叶子结点（外部结点）的哈夫曼树具有n-1个内部结点。根据这个性质可以计算出本题的叶子结点数为18。1.195.0若邻接表中有奇数个表结点，则一定（D）。您答对了 a图中有奇数个顶点 b图中有偶数个顶点 c图为无向图 d图为有向图本题考核图的邻接表存储结构及其特点。1.205.0一棵完全二叉树有999个结点，它的深度为（B）。您答对了 a9 b10 c11 d12本题考核完全二叉树的性质。专心-专注-专业