智慧树知到《数据结构》章节测试答案.pdf

《智慧树知到《数据结构》章节测试答案.pdf》由会员分享，可在线阅读，更多相关《智慧树知到《数据结构》章节测试答案.pdf（30页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、第1章 单元测试1、算法的时间复杂度取决于_。 答案：A和B2、数据在计算机内存中的表示是指（）答案：数据的存储结构3、算法指的是（ ）答案：求解特定问题的指令有限序列4、在数据结构中，与所使用的计算机无关的数据结构是（）答案：逻辑7、某线性表采用顺序存储结构,每个元素占4个存储单元,首地址为100,则第12个元素的存储地址为( )。答案：1448、算法能正确地实现预定功能的特性称为算法的（）。答案：正确性第2章 单元测试1、链表不具备的特点是（ ）。答案：可随机访问任意一个结点3、线性表的顺序存储表示优于链式存储表示。答案：错4、顺序存储结构的缺点是不便于修改,插入和删除需要移动很多结点。答

2、案：对5、在设头、尾指针的单链表中,与长度n有关的操作是( )。答案：删除最后一个结点6、设指针q指向单链表中结点A,指针p指向单链表中结点A的后继结点B,指针s指向被插入的结点X,则在结点A和结点B间插入结点X的操作序列为( )。答案：q-next=s; s-next=p;7、对于只在表的首、尾两端进行插入操作的线性表,宜采用的存储结构为( )。答案：用尾指针表示的循环单链表8、在一个单链表中,若p所指节点不是最后节点,在p之后插入s所指节点,则执行( )。答案：s-link=p-link;p-link=s;9、在双向链表存储结构中，删除p所指的结点时须修改指针_。 答案：p-next-pr

3、ior=p-prior; p-prior-next=p-next;10、若事先不知道线性表的长度,则处理线性表时较好的存储结构是( )。答案：单链表11、向一个有127个元素的顺序表中插入一个新元素并保存,原来顺序不变,平均要移动( )个元素。答案：63.512、某线性表采用顺序存储结构,每个元素占4个存储单元,首地址为100,则第12个元素的存储地址为( )。答案：14413、在一个以 h 为头的单循环链表中,p 指针指向链尾的条件是( )。答案：p-next = h14、在表头指针为head 且表长大于1的单向循环链表中,指针p 指向表中的某个结点,若p-next-next=head,则(

4、 )。答案：*p的直接后继是尾结点15、线性表若采用链式存储结构时，要求内存中可用存储单元的地址_。 答案：连续或不连续都可以16、在单链表中,指针p指向元素为x的结点,实现“删除x的后继”的语句是( )。答案：p-next=p-next-next;17、可以用带表头结点的链表表示线性表，也可以用不带表头结点的链表表示线性表，前者最主要的好处是（）答案：使空表和非空表的处理统一18、与单链表相比,双向链表的优点之一是( )。答案：顺序访问相邻结点更加灵活19、如果最常用的操作是取第i个结点及其前驱,最节省时间的存储方式( )。答案：顺序表21、对顺序存储的线性表,设其长度为n,在任何位置上插入

5、或删除操作都是等概率的。插入一个元素时平均要移动表中的( )个元素。答案：n/222、链表是采用链式存储结构的线性表,进行插入、删除操作时，在链表中比在顺序存储结构中效率高。答案：23、在一个带头结点的双向循环链表中,若要在p所指向的结点之前插入一个新结点,则需要相继修改( )个指针域的值。答案：424、具有线性关系的集合中，若a，b是集合中的任意两个元素，则必有a答案：错第3章 单元测试1、设abcdef以所给次序进栈，若在进栈操作时允许退栈，则下列得不到的序列为（）答案：cabdef2、若已知一个栈的进栈序列是1，2，3n，其输出序列是p1，p2，p3，pn， 若p1=3， 则p2为（）答

6、案：可能是23、假定循环队列的队首和队尾指针分别为front和rear，则判断队满的条件为（ ）。答案：(rear1) mod MAXSIZE = = front4、队列和栈都是运算受限的线性表，只允许在表的两端进行运算。答案：对6、两个栈共享一片连续内存空间时，为提高内存利用率，减少溢出机会，应把两个栈的栈底分别设在这片内存空间的两端。答案：7、循环队列A0.m-1存放其元素值，用front和rear分别表示队头和队尾，则当前队列中的元素数是( )。答案：(rear-front+m)%m8、不论栈是用数组实现，还是用链表实现，入栈和出栈的时间复杂度均为O(n)。答案：错9、若栈采用顺序存储方

7、式存储，两栈共享空间A1.m，top代表第i个栈（i=1, 2）的栈顶，栈1的底在A1，栈 2的底在Am，则栈满的条件是（）。答案：top1+1=top210、输入序列为ABC，若出栈的顺序为CBA时，经过的栈操作为（ ） 。答案：push,push,push,pop,pop,pop11、栈和队都是（ ）。答案：限制存取点的线性结构13、链栈与顺序栈相比，有一个比较明显的优点是（ ）。答案：通常不会出现栈满的情况14、设计一个判别表达式中左,右括号是否配对出现的算法,采用()数据结构最佳答案：线性表的顺序存储结构第4章 单元测试8、设有一个10阶的对称矩阵A，采用压缩存储方式，以行序为主存储，

8、a11为第1个元素，其存储地址为1，每个元素占用1个地址空间，则a85的地址为（）。答案：339、对于以行为主序的存储结构来说在数组Ac1.d1,c2.d2中，c1和d1分别为数组A的第一维下标的下、上界，c2和d2分别为第二维下标的下、上界每个数据元素占k个存储单元，二维数组中任一元素ai,j的存储位置可由（ ）确定。答案：Loci,j=Locc1,c2+(d2-c2+1)(i-c1)+(j-c2) k10、AN，N是对称矩阵，将下面三角（包括对角线）以行序存储到一维数组TN（N+1）/2中，则对任一上三角元素aj对应Tk的下标k是答案：j（j-1）/2+i11、对矩阵压缩存储是为了答案：减

9、少存储空间第5章 单元测试1、二叉树是非线性数据结构，所以（ ）。答案：顺序存储结构和链式存储结构都能存储4、二叉树中所有结点个数是2k-1-1，其中k是树的深度答案：错5、二叉树中每个结点有两棵非空子树或有两棵空子树答案：错6、在只有度为0和度为2的二叉树中 ,设度为0的结点有n0个,度为2的结点有n2个,则有n0=n2+1。答案：对7、树中所有结点的度之和等于所有结点数减1。答案：对8、设森林F中有4棵树,第1、2、3、4棵树的结点个数分别为n1、n2、n3、n4,当把森林F转换成一棵二叉树后,其根结点的左子树中有n1个结点。答案：错9、设Huffman树的叶子结点数为m,则结点总数为2m

10、-1。答案：对15、某二叉树中序序列为BDAECF,后序序列为DBEFCA,则二叉树对应的森林包括( )棵树。答案：316、若一棵二叉树具有10个度为2的结点,5个度为1的结点,则度为0的结点的个数是( )。答案：1117、任何一棵二叉树的叶子结点在前序、中序和后序遍历序列中的相对次序( )。答案：不发生改变18、设某棵二叉树的高度为9,则该二叉树上叶子结点最多有( )。答案：25619、若完全二叉树的结点个数为100,则第60个结点的度为( )。答案：020、树的基本遍历策略分为先根遍历和后根遍历;二叉树的基本遍历策略可分为先序遍历、中序遍历和后序遍历。这里,我们把由树转化得到的二叉树叫做这

11、棵树对应的二叉树,其中结论( )是正确的。答案：树的先根遍历序列与其对应的二叉树的先序遍历序列相同21、某二叉树的先序和后序遍历序列正好相反,则该二叉树一定是( )。答案：深度等于其结点数22、一棵二叉树的高度为h,所有结点的度或为0或为2,则这棵二叉树最少有( )个结点。答案：2h-123、如果一棵二叉树中所有结点的值都大于其左子树中的所有结点的值,且小于其右子树中所有结点的值,现欲得到各个结点的递增序列,采用的方法是( )。答案：中序遍历24、设n,m为一棵二叉树上的两个结点,在中序遍历中 ,n在m前的条件是( )。答案：n在m的左子树上25、深度为5的二叉树至多有 个结点( )答案：31

12、26、由权值分别为 11、 8、 6、 2 、 5 的叶子结点生成一棵哈夫曼树,它的带权路径长度为( )。答案：7127、如果一个完全二叉树最底下一层为第六层(根为第一层)且该层共有8个叶结点,那么该完全二叉树共有多少个结点?( )答案：3928、某二叉树的前序遍历序列为ABDGCEFH,中序遍历序列为DGBAECHF,则后序遍历序列为（ )。答案：GDBEHFCA29、一个具有1025个结点的二叉树的高h为（ ）答案：11到1025之间30、设森林中有三棵树,第一、二、三棵树的结点个数分别为n1、n2、n3,那么将森林转换成二叉树后,其根结点的右子树上有( )个结点。答案：n2+n3第6章

13、单元测试1、任何一个无向连通图的最小生成树 （ ） 。答案：有一棵或多棵2、用邻接表表示图进行广度优先遍历时，通常是采用 来实现算法的。答案：队列3、在一个有向图中，所有顶点的入度之和等于所有顶点的出度之和的（）倍。答案：14、已知有向图G = (V, E)，其中V=V1，V2，V3，V4，V5，V6，V7,E=，,，G的拓扑有序序列是（）。答案：V1，V3，V4，V6，V2，V5，V75、对于含有n个顶点的带权连通图，它的最小生成树是指图中任意一个（）。答案：由n个顶点构成的边的权值之和最小的连通子图6、用邻接矩阵存储一个图时，在不考虑压缩存储的情况下，所占用的存储空间与图中结点的个数有关，

14、而与图的边数无关。答案：对7、如果有向图的所有顶点可以构成一个拓扑排序，则说明该有向图存在回路。答案：错8、一个非空图可以没有边，但不能没有顶点。答案：对9、有n-1条边的图肯定都是生成树。答案：错第7章 单元测试1、有一个有序表为1，3，9，12，32，41，45，62，75，77，82，95，100，当用二分法查找值82的结点时，（）次比较后查找成功。答案：27、若根据查找表建立长度为m的哈希表，采用线性探测法处理冲突，假定对一个元素第一次计算的哈希地址为d，则下一次的哈希地址为()。答案：(d+1)%m8、若根据查找表(23,44,36,48,52,73,64,58)建立哈希表，采用h(

15、K)=K%13计算哈希地址，则元素64的哈希地址为()。答案：129、从具有n个结点的二叉排序树中查找一个元素时，在最坏情况下的时间复杂度为()。答案：O(n)10、对具有 n 个元素的有序表采用折半查找，则算法的时间复杂度为( )。答案：O(log2n)11、对于长度为18的顺序存储的有序表，若采用折半查找，则查找第15个元素的比较次数为()。答案：412、二叉排序树的左右子树都是二叉排序树。答案：对13、1. 若查找每个元素的概率相等，则在长度为 n 的顺序表上查找任一元素的平均查找长度为( )。答案：n+1/2第8章 单元测试1、69、 如果对n个元素进行直接选择排序，则进行任一趟排序的

16、进程中，为寻找最小值元素所需要的时间复杂度为（）答案：O(n)3、下列排序算法中，其中（ ）是稳定的。答案：归并排序，冒泡排序4、下列序列中，（ ）是执行第一趟快速排序后所得的序列。答案：27，38，18 49 93，735、(15，9，7，8，20，-1，4)进行排序，第一趟排序后的序列变为(-1，9，7，8，20，15，4)，则采用的排序方法是（ ）。答案：简单选择排序8、从未排序序列中依次取出元素与已排序序列中的元素进行比较，将其放入已排序序列的正确位置上的排序方法称为（ ）。答案：插入排序9、从未排序序列中挑选元素，并将其依次放入已排序序列（初始时为空）的一端的方法，称为（ ）。答案：

17、选择排序10、对m个不同的关键字由小到大进行冒泡排序，当（ ）时比较的次数最多。答案：从大到小排列11、69、 一组记录的关键码为（46，79，56，38，40，84），则利用快速排序的方法，以第一个记录为基准得到的一次划分结果为（）答案：40，38，46，56，79，8413、希尔排序又称缩小增量排序，其最后一趟排序的增量为（ ）。答案：114、希尔排序是稳定的排序算法。答案：错15、设有1000个无序的元素，希望用最快的速度的选出其中前10个最大的元素，最好选用（）的排序法。答案：堆排序16、对一组数据84,45,20,10,16排序，数据的排列次序在排序过程中的变化为: (1)84,45

18、,20,10,16 (2)10,45,20,84,16 (3)10,16,20,84,45 (4)10,16,20,45,84 该排序算法是以下哪种（）答案：简单选择排序第一章1、算法的时间复杂度取决于 。A:问题的规模B:待处理问题的初态C:问题的难度D:A 和B正确答案：问题的规模2、数据在计算机内存中的表示是指（）A:数据的存储结构B:数据结构C:数据的逻辑结构D:数据元素之间的关系正确答案：数据的存储结构3、算法指的是（）A:计算机程序B:解决问题的计算方法C:排序算法D:解决问题的有限运算序列正确答案：解决问题的有限运算序列4、在数据结构中，与所使用的计算机无关的数据结构是（）A:逻

19、辑B:存储C:逻辑和存储D:物理正确答案：逻辑7、某线性表采用顺序存储结构,每个元素占4个存储单元,首地址为100,则第12个元素的存储地址为( )。A:144B:145C:147D:148正确答案：1448、算法能正确地实现预定功能的特性称为算法的（）。A:正确性B:可读性C:健壮性D:高效性正确答案：正确性第二章1、链表不具备的特点是（ ）。A:可随机访问任意一个结点B:插入和删除不需要移动任何元素C:不必事先估计存储空间D:所需空间与其长度成正比正确答案：可随机访问任意一个结点3、线性表的顺序存储表示优于链式存储表示。A:对B:错正确答案：错4、顺序存储结构的缺点是不便于修改,插入和删除

20、需要移动很多结点。A:对B:错正确答案：对5、在设头、尾指针的单链表中,与长度n有关的操作是( )。A:删除第一个结点B:删除最后一个结点C:在第一个结点之前插入一个结点D:在p结点之后插入一个结点正确答案：删除最后一个结点6、设指针q指向单链表中结点A,指针p指向单链表中结点A的后继结点B,指针s指向被插入的结点X,则在结点A和结点B间插入结点X的操作序列为( )。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;正确答案：q-next=s; s-next=p

21、;7、对于只在表的首、尾两端进行插入操作的线性表,宜采用的存储结构为( )。A:顺序表B:用头指针表示的循环单链表C:用尾指针表示的循环单链表D:单链表正确答案：用尾指针表示的循环单链表8、在一个单链表中,若p所指节点不是最后节点,在p之后插入s所指节点,则执行( )。A:s-link=p;p-link=s;B:s-link=p-link;p-link=s;C:s-link=p-link;p=s;D:p-link=s;s-link=p;正确答案：s-link=p-link;p-link=s;9、在双向链表存储结构中,删除p所指的结点时须修改指针( )。A:p-next-prior=p-prio

22、r; p-prior-next=p-next;B:p-next=p-next-next; p-next-prior=p;C:p-prior-next=p; p-prior=p-prior-prior;D:p-prior=p-next-next; p-next=p-prior-prior;正确答案：p-next-prior=p-prior; p-prior-next=p-next;10、若事先不知道线性表的长度,则处理线性表时较好的存储结构是( )。A:单链表B:静态链表C:顺序表D:B和C正确答案：单链表11、向一个有127个元素的顺序表中插入一个新元素并保存,原来顺序不变,平均要移动( )个

23、元素。A:8B:63.5C:63D:7正确答案：63.512、某线性表采用顺序存储结构,每个元素占4个存储单元,首地址为100,则第12个元素的存储地址为( )。A:144B:145C:147D:148正确答案：14413、在一个以 h 为头的单循环链表中,p 指针指向链尾的条件是( )。A:p-next = hB:p-next = NULLC:p-next-next = hD:p-data = -1正确答案：p-next = h14、在表头指针为head 且表长大于1的单向循环链表中,指针p 指向表中的某个结点,若p-next-next=head,则( )。A:p指向头结点B:p指向尾结点C

24、:p的直接后继是头结点D:p的直接后继是尾结点正确答案：*p的直接后继是尾结点15、线性表若采用链式存储结构时,要求内存中可用存储单元的地址( )。A:必须是连续的B:部分地址必须是连续的C:一定是不连续的D:连续不连续都可以正确答案：连续不连续都可以16、在单链表中,指针p指向元素为x的结点,实现“删除x的后继”的语句是( )。A:p=p-next;B:p-next=p-next-next;C:p-next=p;D:p=p-next-next;正确答案：p-next=p-next-next;17、可以用带表头结点的链表表示线性表,也可以用不带表头结点的链表表示线性表,前者最主要的好处是( )

25、。A:可以加快对表的遍历B:使空表和非空表的处理统一C:节省存储空间D:可以提高存取元素的速度正确答案：使空表和非空表的处理统一18、与单链表相比,双向链表的优点之一是( )。A:插入、删除操作更加简单B:可以随机访问C:可以省略表头指针或表尾指针D:顺序访问相邻结点更加灵活正确答案：顺序访问相邻结点更加灵活19、如果最常用的操作是取第i个结点及其前驱,最节省时间的存储方式( )。A:单链表B:双向链表C:单循环链表D:顺序表正确答案：顺序表21、对顺序存储的线性表,设其长度为n,在任何位置上插入或删除操作都是等概率的。插入一个元素时平均要移动表中的( )个元素。A:n/2B:(n+1)/2C

26、:(n-1)/2D:n正确答案：n/222、链表是采用链式存储结构的线性表,进行插入、删除操作时,在链表中比在顺序存储结构中效率高。A:对B:错正确答案：对23、在一个带头结点的双向循环链表中,若要在p所指向的结点之前插入一个新结点,则需要相继修改( )个指针域的值。A:2B:3C:4D:5正确答案：424、具有线性关系的集合中，若a，b是集合中的任意两个元素，则必有aA:对B:错正确答案：错第三章1、设abcdef以所给次序进栈，若在进栈操作时允许退栈，则下列得不到的序列为（）A:fedcbaB:bcafedC:dcefbaD:cabdef正确答案：2、若已知一个栈的进栈序列是1，2，3n，

27、其输出序列是p1，p2，p3，pn， 若p1=3，则p2为（）A:可能是2B:一定是2C:可能是1D:一定是1正确答案：3、假定循环队列的队首和队尾指针分别为front和rear，则判断队满的条件为（ ）。A:front+1 = = rearB:(rear1) mod MAXSIZE = = frontC:front = = 0D:front= =rear正确答案：4、队列和栈都是运算受限的线性表，只允许在表的两端进行运算。A:对B:错正确答案：6、两个栈共享一片连续内存空间时，为提高内存利用率，减少溢出机会，应把两个栈的栈底分别设在这片内存空间的两端。A:对B:错正确答案：7、循环队列A0.

28、m-1存放其元素值，用front和rear分别表示队头和队尾，则当前队列中的元素数是( )。A:(rear-front+m)%mB:rear-front+1C:rear-front-1D:rear-front正确答案：8、不论栈是用数组实现，还是用链表实现，入栈和出栈的时间复杂度均为O(n)。A:对B:错正确答案：9、若栈采用顺序存储方式存储，两栈共享空间A1.m，top代表第i个栈（i=1, 2）的栈顶，栈1的底在A1，栈 2的底在Am，则栈满的条件是（）。A:|top2-top1|=0B: top1+1=top2C:top1+top2=mD:top1=top2正确答案：10、输入序列为AB

29、C，若出栈的顺序为CBA时，经过的栈操作为（ ） 。A:push,pop,push,pop,push,popB:push,push,push,pop,pop,popC:push,push,pop,pop,push,popD:push,pop,push,push,pop,pop正确答案：11、栈和队都是（ ）。A:顺序存储的线性结构B:链式存储的非线性结构C:限制存取点的线性结构D:限制存取点的非线性结构正确答案：13、链栈与顺序栈相比，有一个比较明显的优点是（ ）。A: 插入操作更方便B:删除操作更方便C:通常不会出现栈满的情况D:会出现栈空的情况正确答案：14、设计一个判别表达式中左，右括号

30、是否配对出现的算法，采用（ ）数据结构最佳。A:线性表的顺序存储结构B:队列C:线性表的链式存储结构D:栈正确答案：第四章8、设有一个10阶的对称矩阵A，采用压缩存储方式，以行序为主存储，a11为第1个元素，其存储地址为1，每个元素占用1个地址空间，则a85的地址为（）。A:13B:33C:18D:40正确答案：9、对于以行为主序的存储结构来说在数组Ac1.d1,c2.d2中，c1和d1分别为数组A的第一维下标的下、上界，c2和d2分别为第二维下标的下、上界每个数据元素占k个存储单元，二维数组中任一元素ai,j的存储位置可由（ ）确定。A:Loci,j=(d2-c2+1)(i-c1)+(j-c

31、2) kB:Loci,j=Locc1,c2+(d2-c2+1)(i-c1)+(j-c2) kC: Loci,j=Ac1,c2+(d2-c2+1)(i-c1)+(j-c2) kD: Loci,j=Loc0,0+(d2-c2+1)(i-c1)+(j-c2) k正确答案：10、AN，N是对称矩阵，将下面三角（包括对角线）以行序存储到一维数组TN（N+1）/2中，则对任一上三角元素aj对应Tk的下标k是A:i（i-1）/2+jB: j（j-1）/2+iC: i（j-i）/2+1D: j（i-1）/2+1正确答案：11、对矩阵压缩存储是为了A:方便运算B:方便存储C:提高运算速度D:减少存储空间正确答案

32、：第五章1、二叉树是非线性数据结构，所以 。A:它不能用顺序存储结构存储B:它不能用链式存储结构存储C:顺序存储结构和链式存储结构都能存储D:顺序存储结构和链式存储结构都不能使用正确答案：4、二叉树中所有结点个数是2k-1-1，其中k是树的深度。A:对B:错正确答案：5、二叉树中每个结点有两棵非空子树或有两棵空子树。A:对B:错正确答案：6、在只有度为0和度为2的二叉树中 ,设度为0的结点有n0个,度为2的结点有n2个,则有n0=n2+1。A:对B:错正确答案：7、树中所有结点的度之和等于所有结点数减1。A:对B:错正确答案：8、设森林F中有4棵树,第1、2、3、4棵树的结点个数分别为n1、n

33、2、n3、n4,当把森林F转换成一棵二叉树后,其根结点的左子树中有n1个结点。A:对B:错正确答案：9、设Huffman树的叶子结点数为m,则结点总数为2m-1。A:对B:错正确答案：15、某二叉树中序序列为BDAECF,后序序列为DBEFCA,则二叉树对应的森林包括( )棵树。A:1B:2C:3D:4正确答案：16、若一棵二叉树具有10个度为2的结点,5个度为1的结点,则度为0的结点的个数是( )。A:9B:11C:15D:不能确定正确答案：17、任何一棵二叉树的叶子结点在前序、中序和后序遍历序列中的相对次序( )。A:不发生改变B:发生改变C:不能确定D:以上都不对正确答案：18、设某棵二

34、叉树的高度为9,则该二叉树上叶子结点最多有( )。A:512B:511C:1023D:256正确答案：19、若完全二叉树的结点个数为100,则第60个结点的度为( )。A:2B:1C:0D:不确定正确答案：20、树的基本遍历策略分为先根遍历和后根遍历;二叉树的基本遍历策略可分为先序遍历、中序遍历和后序遍历。这里,我们把由树转化得到的二叉树叫做这棵树对应的二叉树,其中结论( )是正确的。A:树的先根遍历序列与其对应的二叉树的先序遍历序列相同B:树的后根遍历序列与其对应的二叉树的后序遍历序列相同C:树的先根遍历序列与其对应的二叉树的中序遍历序列相同D:以上都不对正确答案：21、某二叉树的先序和后序

35、遍历序列正好相反,则该二叉树一定是( )。A:空或只有一个结点B:完全二叉树C:二叉排序树D:深度等于其结点数正确答案：22、一棵二叉树的高度为h,所有结点的度或为0或为2,则这棵二叉树最少有( )个结点。A:2hB:2h-1C:2h+1D:h+1正确答案：23、如果一棵二叉树中所有结点的值都大于其左子树中的所有结点的值,且小于其右子树中所有结点的值,现欲得到各个结点的递增序列,采用的方法是( )。A:前序遍历B:后序遍历C:中序遍历D:层次遍历正确答案：24、设n,m为一棵二叉树上的两个结点,在中序遍历中 ,n在m前的条件是( )。A:n 在m右子树上B:n是m的祖先C:n在m的左子树上D:

36、n是m的子孙正确答案：25、深度为5的二叉树至多有( )个结点。A:16B:32C:31D:10正确答案：26、由权值分别为 11、 8、 6、 2 、 5 的叶子结点生成一棵哈夫曼树,它的带权路径长度为( )。A:24B:71C:48D:53正确答案：27、如果一个完全二叉树最底下一层为第六层(根为第一层)且该层共有8个叶结点,那么该完全二叉树共有多少个结点?( )A:31B:39C:63D:71正确答案：28、某二叉树的前序遍历序列为ABDGCEFH,中序遍历序列为DGBAECHF,则后序遍历序列为（ )。A:BDGCEFHAB:GDBECFHAC:BDGAECHFD:GDBEHFCA正确

37、答案：29、一个具有1025个结点的二叉树的高h为( )。A:11B:10C:11至1025之间D:10至1024之间正确答案：30、设森林中有三棵树,第一、二、三棵树的结点个数分别为n1、n2、n3,那么将森林转换成二叉树后,其根结点的右子树上有( )个结点。A:n1B:n1-1C:n2+n3D:其他情况正确答案：第六章1、任何一个无向连通图的最小生成树A:只有一棵B:一棵或多棵C:一定有多棵D:可能不存在正确答案：2、用邻接表表示图进行广度优先遍历时，通常是采用 来实现算法的。A:栈B:队列C:树D:图正确答案：3、在一个有向图中，所有顶点的入度之和等于所有顶点的出度之和的 倍。A:1/2

38、B:1C:2D:4正确答案：4、已知有向图G = (V, E)，其中V=V1，V2，V3，V4，V5，V6，V7,E=，,，G的拓扑有序序列是（）。A: V1，V3，V4，V6，V2，V5，V7B:V1，V3，V2，V6，V4，V5，V7C:V1，V3，V4，V5，V2，V6，V7D:V1，V2，V5，V3，V4，V6，V7正确答案：5、 对于含有n个顶点的带权连通图，它的最小生成树是指图中任意一个（）。A: 由n-1条权值最小的边构成的子图B:由n-1条权值之和最小的边构成的子图C:由n-1条权值之和最小的边构成的连通子图D:由n个顶点构成的边的权值之和最小的连通子图正确答案：6、用邻接矩阵

39、存储一个图时，在不考虑压缩存储的情况下，所占用的存储空间与图中结点的个数有关，而与图的边数无关。A:对B:错正确答案：7、如果有向图的所有顶点可以构成一个拓扑排序，则说明该有向图存在回路。A:对B:错正确答案：8、一个非空图可以没有边，但不能没有顶点。A:对B:错正确答案：9、有n-1条边的图肯定都是生成树。A:对B:错正确答案：第七章1、有一个有序表为1，3，9，12，32，41，45，62，75，77，82，95，100，当用二分法查找值82的结点时，（）次比较后查找成功。A:1B:2C:4D:8正确答案：7、若根据查找表建立长度为 m 的哈希表，采用线性探测法处理冲突，假定对一个元素第一

40、次计算的哈希地址为 d，则下一次的哈希地址为( )。A:dB:d+1C:(d+1)/mD:(d+1)%m正确答案：8、若根据查找表(23,44,36,48,52,73,64,58)建立哈希表，采用 h(K)=K%13 计算哈希地址，则元素 64 的哈希地址为( )。A:4B:8C:12D:13正确答案：9、从具有 n 个结点的二叉排序树中查找一个元素时，在最坏情况下的时间复杂度为( )。A:O(n)B:O(1)C:O(log2n)D:O(n2)正确答案：10、对具有 n 个元素的有序表采用折半查找，则算法的时间复杂度为( )。A:O(n)B:O(n2)C:O(1)D:O(log2n)正确答案：

41、11、对于长度为 18 的顺序存储的有序表，若采用折半查找，则查找第 15 个元素的比较次数为( )。A:3B:4C:5D:6正确答案：12、二叉排序树的左右子树都是二叉排序树。A:对B:错正确答案：13、1. 若查找每个元素的概率相等，则在长度为 n 的顺序表上查找任一元素的平均查找长度为( )。A:nB:n+1C:n-1/2D:n+1/2正确答案：第八章1、69、 如果对n个元素进行直接选择排序，则进行任一趟排序的进程中，为寻找最小值元素所需要的时间复杂度为（）A:O(1)B:O(logn)C:O(n2)D:O(n)正确答案：3、下列排序算法中，其中（ ）是稳定的。A:快速排序，冒泡排序B

42、:简单选择排序，归并排序C:快速排序，堆排序D: 归并排序，冒泡排序正确答案：4、下列序列中，（ ）是执行第一趟快速排序后所得的序列。A:27，38，73 49 93，18B:27，38，93 49 18，73C:27，38，18 49 93，73D:93，38，18 49 27，73正确答案：5、(15，9，7，8，20，-1，4)进行排序，第一趟排序后的序列变为(-1，9，7，8，20，15，4)，则采用的排序方法是（ ）。A:简单选择排序B:直接插入排序C:希尔排序D:快速排序正确答案：8、从未排序序列中依次取出元素与已排序序列中的元素进行比较，将其放入已排序序列的正确位置上的排序方法称

43、为（ ）。A:选择排序B:希尔排序C:堆排序D:插入排序正确答案：9、从未排序序列中挑选元素，并将其依次放入已排序序列（初始时为空）的一端的方法，称为（ ）。A:快速排序B:直接插入排序C:选择排序D:冒泡排序正确答案：10、对m个不同的关键字由小到大进行冒泡排序，当（ ）时比较的次数最多。A:从大到小排列B:从小到大排列C:元素基本有序D:元素无序正确答案：11、69、 一组记录的关键码为（46，79，56，38，40，84），则利用快速排序的方法，以第一个记录为基准得到的一次划分结果为（）A:38，40，46，56，79，84B:40，38，46，79，56，84C:40，38，46，56

44、，79，84D:40，38，46，84，56，79正确答案：13、希尔排序又称缩小增量排序，其最后一趟排序的增量为（ ）。A:1B:2C:3D:0正确答案：14、希尔排序是稳定的排序算法。A:对B:错正确答案：15、设有1000个无序的元素，希望用最快的速度的选出其中前10个最大的元素，最好选用（）的排序法。A:冒泡排序B:快速排序C:堆排序D:选择排序正确答案：16、对一组数据84,45,20,10,16排序，数据的排列次序在排序过程中的变化为: (1)84,45,20,10,16 (2)10,45,20,84,16 (3)10,16,20,84,45 (4)10,16,20,45,84 该排序算法是以下哪种（）A:简单选择排序B: 冒泡排序C: 快速排序D: 直接插入排序正确答案：