智慧树知到《数据结构（山东联盟-临沂大学）》章节测试答案
智慧树知到《数据结构（山东联盟-临沂大学）》章节测试答案
第一章单元测试
1、下列叙述中正确的是（）
A.所谓算法就是计算方法
B.程序可以作为算法的一种描述方法
C.算法设计只需考虑得到计算结果
D.算法设计可以忽略算法的运算时间
正确答案：程序可以作为算法的一种描述方法
2、数据的最小单位是数据项（）。
A.正确
B.错误
正确答案：正确
3、在数据结构中，从逻辑上可以把数据结构分成（）
A.动态结构和静态结构
B.紧凑结构和非紧凑结构
C.线性结构和非线性结构
D.内部结构和外部结构
正确答案：线性结构和非线性结构
4、与数据元素本身的形式、内容、相对位置、个数无关的是数据的（）
A.存储结构
B.存储实现
C.逻辑结构
D.运算实现
正确答案：逻辑结构
5、以下说法正确的是（）
A.数据元素是数据的最小单位
B.数据项是数据的基本单位
C.数据结构是带有结构的各数据项的集合
D.一些表面上很不相同的数据可以有相同的逻辑结构
正确答案：一些表面上很不相同的数据可以有相同的逻辑结构
6、下面代码段的时间复杂度是（）。
s=0；for（i=0； i<；n； i++ ） ； for（j=0； j<；n； j++ ）； s+=B[i][j]；sum=s。
A.O（1）
B.O（logn）
C.O（n）
D.O（n²；）
正确答案：O（n²；）
7、下面代码段的时间复杂度是（）。
x=0；for（i=1； i<；n； i++ ） ； for（j=1； j<；=n-i； j++ ） ； x++。
A.O（n）
B.O（n²）
C.O（n³）
D.O（logn）
正确答案：O（n²）
8、NlogN²和NlogN具有相同的增长速度。（）
A.正确
B.错误
正确答案：正确
9、N²logN²和NlogN²具有相同的增长速度。（）
A.正确
B.错误
正确答案：错误
10、斐波那契数列FN的定义为：F0=0，F1=1，FN=FN−1+FN−2，N=2，3，...。用递归函数计算FN的时间复杂度是O（N!）。
A.正确
B.错误
正确答案：错误
第二章单元测试
1、下面关于线性表的叙述中，错误的是哪一个（）
A.线性表采用顺序存储，必须占用一片连续的存储单元
B.线性表采用顺序存储，便于进行插入和删除操作
C.线性表采用链接存储，不必占用一片连续的存储单元
D.线性表采用链接存储，便于插入和删除操作
正确答案：线性表采用顺序存储，便于进行插入和删除操作
2、在具有n个结点的单链表中，实现下列哪个操作，其算法的时间复杂度是O（n）？
A.在地址为p的结点之后插入一个结点
B.删除开始结点
C.遍历链表和求链表的第i个结点
D.删除地址为p的结点的后继结点
正确答案：遍历链表和求链表的第i个结点
3、链表不具有的特点是（）
A.可随机访问任一个元素
B.插入删除不需要移动元素
C.不必事先估计存储空间
D.所需空间与线性表长度成正比
正确答案：可随机访问任一个元素
4、带头结点的单链表L为空的条件是（）
A.L==NULL
B.L->；next==NULL
C.L->；next==L
D.L->；next->；next==NULL
正确答案：L->；next==NULL
5、在单链表指针为p的结点之后插入指针为s的结点，正确的操作是（）
A.p->；next=s；s->；next=p->；next
B.s->；next=p->；next；p->；next=s
C.p->；next=s；p->；next=s->；next
D.p->；next=s->；next；p->；next=s
正确答案：s->；next=p->；next；p->；next=s
6、在长度为n的顺序表的表尾插入一个新元素的时间复杂度为（）
A.O（n；）
B.O（1；）
C.O（n²；）
D.O（logn；）
正确答案：O（1；）
7、单链表中，增加头结点的目的是为了（）
A.使单链表至少有一个结点
B.标示表结点中首结点的位置
C.方便运算的实现
D.说明单链表是线性表的链式存储实现
正确答案：方便运算的实现
8、线性表的逻辑顺序与物理顺序总是一致的（）。
A.正确
B.错误
正确答案：错误
9、取线性表的第i个元素的时间同i的大小有关（）。
A.正确
B.错误
正确答案：错误
10、线性表的长度是线性表所占用的存储空间的大小（）。
A.正确
B.错误
正确答案：错误
第三章单元测试
1、设有六列火车，编号为1，2，3，4，5，6，顺序开进一个栈式结构的站台，问下列输出序列中，哪个是不可能出现的（）。
A.1，2，3，4，5，6
B.6，5，4，3，2，1
C.3，1，2，6，5，4
D.3，2，1，6，5，4
正确答案：3，1，2，6，5，4
2、栈和队列都是运算受限的线性表。（）
A.正确
B.错误
正确答案：正确
3、当用长度为N的数组顺序存储一个栈时，假定用top==N表示栈空，则表示栈满的条件是top==1。（）
A.正确
B.错误
正确答案：错误
4、元素a， b， c， d， e依次进入初始为空的栈中，若元素进栈后可停留、可出栈，直到所有元素都出栈，则在所有可能的出栈序列中，以元素d开头的序列个数是（）。
A.3
B.4
C.5
D.6
正确答案：4
5、已知循环队列存储在一维数组A[0..n-1] 中，且队列非空时front和rear分别指向队头元素和队尾元素。若初始时队列为空，且要求第1个进入队列的元素存储在A[0]处，则初始时front和rear的值分别是（）。
A.0， 0
B.0， n-1
C.n-1， 0
D.n-1， n-1
正确答案：0， n-1
6、数组Q[n]用来表示一个循环队列，f为当前队列头元素的前一位置，r为队尾元素的位置，假定队列中元素的个数小于n，计算队列中元素个数的公式为（）。
A.r-f
B.（n+f-r）%n
C.n+r-f
D.（n+r-f）%n
正确答案：（n+r-f）%n
7、若一个栈以向量V[1..n]存储，初始栈顶指针top设为n+1，则元素x进栈的正确操作是（）。
A.top++； V[top]=x
B.V[top]=x； top++
C.top--； V[top]=x
D.V[top]=x； top--
正确答案：top--； V[top]=x
8、设栈S和队列Q的初始状态为空，元素e1、e2、e3、e4、e5和e6依次进入栈S，一个元素出栈后即进入Q，若6个元素出队的序列是e2、e4、e3、e6、e5和e1，则栈S的容量至少应该是（）。
A.2
B.3
C.4
D.6
正确答案：3
9、循环队列放在一维数组A[0…M-1]中，end1指向队头元素，end2指向队尾元素的后一个位置。假设队列两端均可进行入队和出队操作，队列中最多能容纳M-1个元素。初始时为空，下列判断队空和队满的条件中，正确的是（）。
A.队空：end1 == end2； 队满：end1 ==（end2+1） mod M
B.队空：end1 == end2； 队满：end2 ==（end1+1） mod（M-1）
C.队空：end2 ==（end1+1）mod M； 队满：end1 ==（end2+1） mod M
D.队空：end1 ==（end2+1）； 队满：end2 ==（end1+1） mod（M-1）
正确答案：队空：end1 == end2； 队满：end1 ==（end2+1） mod M
10、用链接方式存储的队列，在进行删除运算时（）。
A.仅修改头指针
B.仅修改尾指针
C.头、尾指针都要修改
D.头、尾指针可能都要修改
正确答案：头、尾指针可能都要修改
第四章单元测试
1、由3 个结点可以构造出多少种不同的树（）
A.2
B.3
C.4
D.5
正确答案：2
2、一棵树高为K的完全二叉树至少有（）个结点
A.
3、将含有83个结点的完全二叉树从根结点开始编号，根为1号，按从上到下、从左到右顺序结点编号，那么编号为41的双亲结点编号为（）
A.42
B.40
C.21
D.20
正确答案：20
4、对于有n 个结点的二叉树， 其高度为（）
A.
D.不确定
正确答案：不确定
5、给定二叉树如下图所示。设N代表二叉树的根，L代表根结点的左子树，R代表根结点的右子树。若遍历后的结点序列为3、1、7、5、6、2、4，则其遍历方式是（）
A.NRL
B.RNL
C.LRN
D.RLN
正确答案：RNL
6、如果T2是由有序树T转化而来的二叉树，那么T中结点的先序就是T2中结点的（）
A.先序
B.中序
C.后序
D.层次
正确答案：先序
7、下面几个符号串编码集合中，不是前缀编码的是（）
A.{0，10，110，1111}
B.{11，10，001，101，0001}
C.{00，010，0110，1000}
D.{b，c，aa，ac，aba，abb，abc}
正确答案：{11，10，001，101，0001}
8、二叉树先序遍历：EFHIGJK；中序遍历：HFIEJKG 。该二叉树根的右子树的根是（）
A.E
B.F
C.G
D.H
正确答案：G
9、以下说法错误的是（）
A.一般在哈夫曼树中，权值越大的叶子离根结点越近
B.哈夫曼树中没有度数为1的分支结点
C.若初始森林中共有N棵二叉树，最终求得的哈夫曼树中共有2N-1个结点
D.若初始森林中共有N棵二叉树，进行2N-1次合并后才能剩下最终的哈夫曼树
正确答案：若初始森林中共有N棵二叉树，进行2N-1次合并后才能剩下最终的哈夫曼树
10、若一棵二叉树的任一非叶子结点的度为2，则该二叉树为满二叉树（）。
A.正确
B.错误
正确答案：错误
11、若某二叉树的叶子结点数为1，则其先序序列和后序序列一定相反（）。
A.正确
B.错误
正确答案：正确
12、完全二叉树中，若一个结点没有左孩子，则它必是树叶。（）
A.正确
B.错误
正确答案：正确
13、利用二叉链表存储树，则根结点的右指针是（）
A.指向最左孩子
B.指向最右孩子
C.空
D.非空
正确答案：空
第五章单元测试
1、用邻接矩阵法存储图，占用的存储空间数只与图中结点个数有关，而与边数无关。（）
A.正确
B.错误
正确答案：正确
2、有向图的邻接矩阵是对称的。（）
A.正确
B.错误
正确答案：错误
3、设无向图的顶点个数为n，则该图最多有（）条边。
A.n-1
B.n（n-1）/2
C.n（n+1）/2
D.0
正确答案：n（n-1）/2
4、下列关于无向连通图特征的叙述中，正确的是：（）
1.所有顶点的度之和为偶数
2.边数大于顶点个数减1
3.至少有一个顶点的度为1
A.只有1
B.只有2
C.1和2
D.1和3
正确答案：只有1
5、对于一个具有n个顶点和e条边的无向图，若采用邻接表表示，所有顶点邻接表的边结点总数为（）。
A.e/2
B.e
C.2e
D.n+e
正确答案：2e
6、给定一有向图的邻接表如下。从顶点V1出发按深度优先搜索法进行遍历，则得到的顶点序列为（）。
A.V1，V2，V3，V4，V7，V6，V5
B.V1，V5，V4，V7，V6，V2，V3
C.V1，V5，V6，V4，V7，V2，V3
D.V1，V5，V4，V7，V6，V3，V2
正确答案：V1，V5，V4，V7，V6，V3，V2
7、在图中自a点开始进行广度优先搜索算法可能得到的结果为（）。
A.a， e， d， f， c， b
B.a， c， f， e， b， d
C.a， e， b， c， f， d
D.a， b， e， c， d， f
正确答案：a， b， e， c， d， f
8、任何一个带权无向连通图的最小生成树（）。
A.是唯一的
B.是不唯一的
C.有可能不唯一
D.有可能不存在
正确答案：有可能不唯一
9、对于下列的网，使用克鲁斯卡尔算法求最小生成树，依次得到的边集是（）。
A.{（A，D），（B，C），（E，A），（C，E）}
B.{（A，D），（D，E），（B，C），（C，E）}
C.{（A，D），（D，E），（E，C），（C，B）}
D.{（A，D），（A，B），（A，E），（E，C）}
正确答案：{（A，D），（D，E），（B，C），（C，E）}
10、使用迪杰斯特拉（Dijkstra）算法求下图中从顶点1到其它各顶点的最短路径，依次得到的各最短路径的目标顶点是（）。
A.5， 2， 3， 4， 6
B.5， 2， 3， 6， 4
C.5， 2， 4， 3， 6
D.5， 2， 6， 3， 4
正确答案：5， 2， 3， 6， 4
第六章单元测试
1、二叉排序树或者是一棵空树；或者是具有如下特性的二叉树：（1）若它的左子树不空，则左子树上所有结点的值均小于根结点的值；（2）若它的右子树不空，则右子树上所有结点的值均大于根结点的值。（）
A.正确
B.错误
正确答案：错误
2、查找相同结点的效率折半查找总比顺序查找高。（）
A.正确
B.错误
正确答案：错误
3、在查找树（二叉排序树）中插入一个新结点，总是插入到叶结点下面。（）
A.正确
B.错误
正确答案：错误
4、采用线性探测法处理散列时的冲突，当从哈希表删除一个记录时，不应将这个记录的所在位置置空，因为这会影响以后的查找。（）
A.正确
B.错误
正确答案：正确
5、对一棵二叉排序树按先序方法遍历得出的结点序列是从小到大的序列。（）
A.正确
B.错误
正确答案：错误
6、已知一个长度为16的顺序表L，其元素按关键字有序排列，若采用折半查找法查找一个不存在的元素，则比较次数最多的是（）。
A.4
B.5
C.6
D.7
正确答案：5
7、对于下列关键字序列，不可能构成某二叉排序树中一条查找路径的序列是（）。
A.95，22，91，24，94，71
B.92，20，91，34，88，35
C.21，89，77，29，36，38
D.12，25，71，68，33，34
正确答案：95，22，91，24，94，71
8、在任意一棵非空二叉排序树T1 中，删除某结点v 之后形成二叉排序树T2，再将v 插入T2 形成二叉排序树T3。下列关于T1 与T3 的叙述中，正确的是（）。
I.若v 是T1 的叶结点，则T1 与T3 不同
II.若v 是T1 的叶结点，则T1 与T3 相同
III.若v 不是T1 的叶结点，则T1 与T3 不同
IV.若v 不是T1 的叶结点，则T1 与T3 相同
A.仅I、III
B.仅I、IV
C.仅II、III
D.仅II、IV
正确答案：仅II、III
9、对于线性表（7，34，77，25，64，49，20，14）进行散列存储时，若选用H（K）=K %7作为散列函数，则哈希地址为0的元素有（）个
A.1
B.2
C.3
D.4
正确答案：4
10、适用于折半查找的查找表存储方式及元素排列要求为（）
A.链接方式存储，元素无序
B.链接方式存储，元素有序
C.顺序方式存储，元素无序
D.顺序方式存储，元素有序
正确答案：顺序方式存储，元素有序
11、有一个有序表为｛1， 3， 9， 12， 32， 41，45， 62， 75， 77， 82， 95， 100｝，当用折半查找方法查找值82的结点时，（）次比较后查找成功。
A.8
B.1
C.4
D.2
正确答案：4
12、将{5， 2， 7， 3， 4， 1， 6}依次插入初始为空的二叉排序树。则该树的后序遍历结果是：（）
A.1， 2， 3， 4， 6， 7， 5
B.1， 4， 2， 6， 3， 7， 5
C.1， 4， 3， 2， 6， 7， 5
D.5， 4， 3， 7， 6， 2， 1
正确答案：1， 4， 3， 2， 6， 7， 5
13、有数据{53，30，37，12，45，24，96}，从空二叉树开始逐步插入数据形成二叉排序树，若希望高度最小，应选择下列（）的序列输入。
A.37，24，12，30，53，45，96
B.45，24，53，12，37，96，30
C.30，24，12，37，45，96，53
D.12，24，30，37，45，53，96
正确答案：37，24，12，30，53，45，96
14、下面关于哈希查找的说法，不正确的是（）
A.采用链地址法处理冲突时，查找每个元素的时间是相同的
B.采用链地址法处理冲突时，若插入规定总是在链首，则插入任一个元素的时间是相同的
C.用链地址法处理冲突，不会引起二次聚集现象
D.用链地址法处理冲突，适合表长不确定的情况
正确答案：采用链地址法处理冲突时，查找每个元素的时间是相同的
第七章单元测试
1、快速排序的速度在所有排序方法中为最快，而且所需附加空间也最少。
A.正确
B.错误
正确答案：错误
2、堆排序是稳定的排序方法。
A.正确
B.错误
正确答案：错误
3、在初始数据表已经有序时，快速排序算法的时间复杂度为O（nlog2n）。
A.正确
B.错误
正确答案：错误
4、在用堆排序算法排序时，如果要进行增序排序，则需要采用“大根堆”。
A.正确
B.错误
正确答案：正确
5、比较次数与排序的初始状态无关的排序方法是（）
A.直接插入排序
B.冒泡排序
C.快速排序
D.简单选择排序
正确答案：简单选择排序
6、下列排序方法中，哪一个是稳定的排序方法？（）；
A.直接选择排序
B.希尔排序
C.归并排序
D.快速排序
正确答案：归并排序
7、从未排序序列中依次取出一个元素与已排序序列中的元素依次进行比较，然后将其放在已排序序列的合适位置，该排序方法称为（）排序法。
A.插入
B.选择
C.希尔
D.快速
正确答案：插入
8、对序列{15，9，7，8，20，-1，4}进行排序，进行一趟后数据的排列变为{4，9，-1，8，20，7，15}；则采用的是（）排序。
A.选择
B.快速
C.希尔
D.冒泡
正确答案：希尔
9、假定对元素序列（7，3，5，9，1，12）进行堆排序，并且采用小根堆，则由初始数据构成的初始堆为（）
A.1，3，5，7，9，12
B.1，3，5，9，7，12
C.1，5，3，7，9，12
D.1，5，3，9，12，7
正确答案：1，3，5，9，7，12
10、假定一个初始堆为（1，5，3，9，12，7，15，10）则进行第一趟堆排序后得到的结果为（）
A.3，5，7，9，12，10，15，1
B.3，5，9，7，12，10，15，1
C.3，7，5，9，12，10，15，1
D.3，5，7，12，9，10，15，1
正确答案：3，5，7，9，12，10，15，1
11、一组记录的关键码为（46，79，56，38，40，84），则利用快速排序的方法，以第一个记录为基准得到的一次划分结果为（）。
A.38，40，46，56，79，84
B.40，38，46，79，56，84
C.40，38，46，56，79，84
D.40，38，46，84，56，79
正确答案：40，38，46，56，79，84
第一章单元测试
1、下列叙述中正确的是（）
A.所谓算法就是计算方法
B.程序可以作为算法的一种描述方法
C.算法设计只需考虑得到计算结果
D.算法设计可以忽略算法的运算时间
正确答案：程序可以作为算法的一种描述方法
2、数据的最小单位是数据项（）。
A.正确
B.错误
正确答案：正确
3、在数据结构中，从逻辑上可以把数据结构分成（）
A.动态结构和静态结构
B.紧凑结构和非紧凑结构
C.线性结构和非线性结构
D.内部结构和外部结构
正确答案：线性结构和非线性结构
4、与数据元素本身的形式、内容、相对位置、个数无关的是数据的（）
A.存储结构
B.存储实现
C.逻辑结构
D.运算实现
正确答案：逻辑结构
5、以下说法正确的是（）
A.数据元素是数据的最小单位
B.数据项是数据的基本单位
C.数据结构是带有结构的各数据项的集合
D.一些表面上很不相同的数据可以有相同的逻辑结构
正确答案：一些表面上很不相同的数据可以有相同的逻辑结构
6、下面代码段的时间复杂度是（）。
s=0；for（i=0； i<；n； i++ ） ； for（j=0； j<；n； j++ ）； s+=B[i][j]；sum=s。
A.O（1）
B.O（logn）
C.O（n）
D.O（n²；）
正确答案：O（n²；）
7、下面代码段的时间复杂度是（）。
x=0；for（i=1； i<；n； i++ ） ； for（j=1； j<；=n-i； j++ ） ； x++。
A.O（n）
B.O（n²）
C.O（n³）
D.O（logn）
正确答案：O（n²）
8、NlogN²和NlogN具有相同的增长速度。（）
A.正确
B.错误
正确答案：正确
9、N²logN²和NlogN²具有相同的增长速度。（）
A.正确
B.错误
正确答案：错误
10、斐波那契数列FN的定义为：F0=0，F1=1，FN=FN−1+FN−2，N=2，3，...。用递归函数计算FN的时间复杂度是O（N!）。
A.正确
B.错误
正确答案：错误
第二章单元测试
1、下面关于线性表的叙述中，错误的是哪一个（）
A.线性表采用顺序存储，必须占用一片连续的存储单元
B.线性表采用顺序存储，便于进行插入和删除操作
C.线性表采用链接存储，不必占用一片连续的存储单元
D.线性表采用链接存储，便于插入和删除操作
正确答案：线性表采用顺序存储，便于进行插入和删除操作
2、在具有n个结点的单链表中，实现下列哪个操作，其算法的时间复杂度是O（n）？
A.在地址为p的结点之后插入一个结点
B.删除开始结点
C.遍历链表和求链表的第i个结点
D.删除地址为p的结点的后继结点
正确答案：遍历链表和求链表的第i个结点
3、链表不具有的特点是（）
A.可随机访问任一个元素
B.插入删除不需要移动元素
C.不必事先估计存储空间
D.所需空间与线性表长度成正比
正确答案：可随机访问任一个元素
4、带头结点的单链表L为空的条件是（）
A.L==NULL
B.L->；next==NULL
C.L->；next==L
D.L->；next->；next==NULL
正确答案：L->；next==NULL
5、在单链表指针为p的结点之后插入指针为s的结点，正确的操作是（）
A.p->；next=s；s->；next=p->；next
B.s->；next=p->；next；p->；next=s
C.p->；next=s；p->；next=s->；next
D.p->；next=s->；next；p->；next=s
正确答案：s->；next=p->；next；p->；next=s
6、在长度为n的顺序表的表尾插入一个新元素的时间复杂度为（）
A.O（n；）
B.O（1；）
C.O（n²；）
D.O（logn；）
正确答案：O（1；）
7、单链表中，增加头结点的目的是为了（）
A.使单链表至少有一个结点
B.标示表结点中首结点的位置
C.方便运算的实现
D.说明单链表是线性表的链式存储实现
正确答案：方便运算的实现
8、线性表的逻辑顺序与物理顺序总是一致的（）。
A.正确
B.错误
正确答案：错误
9、取线性表的第i个元素的时间同i的大小有关（）。
A.正确
B.错误
正确答案：错误
10、线性表的长度是线性表所占用的存储空间的大小（）。
A.正确
B.错误
正确答案：错误
第三章单元测试
1、设有六列火车，编号为1，2，3，4，5，6，顺序开进一个栈式结构的站台，问下列输出序列中，哪个是不可能出现的（）。
A.1，2，3，4，5，6
B.6，5，4，3，2，1
C.3，1，2，6，5，4
D.3，2，1，6，5，4
正确答案：3，1，2，6，5，4
2、栈和队列都是运算受限的线性表。（）
A.正确
B.错误
正确答案：正确
3、当用长度为N的数组顺序存储一个栈时，假定用top==N表示栈空，则表示栈满的条件是top==1。（）
A.正确
B.错误
正确答案：错误
4、元素a， b， c， d， e依次进入初始为空的栈中，若元素进栈后可停留、可出栈，直到所有元素都出栈，则在所有可能的出栈序列中，以元素d开头的序列个数是（）。
A.3
B.4
C.5
D.6
正确答案：4
5、已知循环队列存储在一维数组A[0..n-1] 中，且队列非空时front和rear分别指向队头元素和队尾元素。若初始时队列为空，且要求第1个进入队列的元素存储在A[0]处，则初始时front和rear的值分别是（）。
A.0， 0
B.0， n-1
C.n-1， 0
D.n-1， n-1
正确答案：0， n-1
6、数组Q[n]用来表示一个循环队列，f为当前队列头元素的前一位置，r为队尾元素的位置，假定队列中元素的个数小于n，计算队列中元素个数的公式为（）。
A.r-f
B.（n+f-r）%n
C.n+r-f
D.（n+r-f）%n
正确答案：（n+r-f）%n
7、若一个栈以向量V[1..n]存储，初始栈顶指针top设为n+1，则元素x进栈的正确操作是（）。
A.top++； V[top]=x
B.V[top]=x； top++
C.top--； V[top]=x
D.V[top]=x； top--
正确答案：top--； V[top]=x
8、设栈S和队列Q的初始状态为空，元素e1、e2、e3、e4、e5和e6依次进入栈S，一个元素出栈后即进入Q，若6个元素出队的序列是e2、e4、e3、e6、e5和e1，则栈S的容量至少应该是（）。
A.2
B.3
C.4
D.6
正确答案：3
9、循环队列放在一维数组A[0…M-1]中，end1指向队头元素，end2指向队尾元素的后一个位置。假设队列两端均可进行入队和出队操作，队列中最多能容纳M-1个元素。初始时为空，下列判断队空和队满的条件中，正确的是（）。
A.队空：end1 == end2； 队满：end1 ==（end2+1） mod M
B.队空：end1 == end2； 队满：end2 ==（end1+1） mod（M-1）
C.队空：end2 ==（end1+1）mod M； 队满：end1 ==（end2+1） mod M
D.队空：end1 ==（end2+1）； 队满：end2 ==（end1+1） mod（M-1）
正确答案：队空：end1 == end2； 队满：end1 ==（end2+1） mod M
10、用链接方式存储的队列，在进行删除运算时（）。
A.仅修改头指针
B.仅修改尾指针
C.头、尾指针都要修改
D.头、尾指针可能都要修改
正确答案：头、尾指针可能都要修改
第四章单元测试
1、由3 个结点可以构造出多少种不同的树（）
A.2
B.3
C.4
D.5
正确答案：2
2、一棵树高为K的完全二叉树至少有（）个结点
A.
3、将含有83个结点的完全二叉树从根结点开始编号，根为1号，按从上到下、从左到右顺序结点编号，那么编号为41的双亲结点编号为（）
A.42
B.40
C.21
D.20
正确答案：20
4、对于有n 个结点的二叉树， 其高度为（）
A.
D.不确定
正确答案：不确定
5、给定二叉树如下图所示。设N代表二叉树的根，L代表根结点的左子树，R代表根结点的右子树。若遍历后的结点序列为3、1、7、5、6、2、4，则其遍历方式是（）
A.NRL
B.RNL
C.LRN
D.RLN
正确答案：RNL
6、如果T2是由有序树T转化而来的二叉树，那么T中结点的先序就是T2中结点的（）
A.先序
B.中序
C.后序
D.层次
正确答案：先序
7、下面几个符号串编码集合中，不是前缀编码的是（）
A.{0，10，110，1111}
B.{11，10，001，101，0001}
C.{00，010，0110，1000}
D.{b，c，aa，ac，aba，abb，abc}
正确答案：{11，10，001，101，0001}
8、二叉树先序遍历：EFHIGJK；中序遍历：HFIEJKG 。该二叉树根的右子树的根是（）
A.E
B.F
C.G
D.H
正确答案：G
9、以下说法错误的是（）
A.一般在哈夫曼树中，权值越大的叶子离根结点越近
B.哈夫曼树中没有度数为1的分支结点
C.若初始森林中共有N棵二叉树，最终求得的哈夫曼树中共有2N-1个结点
D.若初始森林中共有N棵二叉树，进行2N-1次合并后才能剩下最终的哈夫曼树
正确答案：若初始森林中共有N棵二叉树，进行2N-1次合并后才能剩下最终的哈夫曼树
10、若一棵二叉树的任一非叶子结点的度为2，则该二叉树为满二叉树（）。
A.正确
B.错误
正确答案：错误
11、若某二叉树的叶子结点数为1，则其先序序列和后序序列一定相反（）。
A.正确
B.错误
正确答案：正确
12、完全二叉树中，若一个结点没有左孩子，则它必是树叶。（）
A.正确
B.错误
正确答案：正确
13、利用二叉链表存储树，则根结点的右指针是（）
A.指向最左孩子
B.指向最右孩子
C.空
D.非空
正确答案：空
第五章单元测试
1、用邻接矩阵法存储图，占用的存储空间数只与图中结点个数有关，而与边数无关。（）
A.正确
B.错误
正确答案：正确
2、有向图的邻接矩阵是对称的。（）
A.正确
B.错误
正确答案：错误
3、设无向图的顶点个数为n，则该图最多有（）条边。
A.n-1
B.n（n-1）/2
C.n（n+1）/2
D.0
正确答案：n（n-1）/2
4、下列关于无向连通图特征的叙述中，正确的是：（）
1.所有顶点的度之和为偶数
2.边数大于顶点个数减1
3.至少有一个顶点的度为1
A.只有1
B.只有2
C.1和2
D.1和3
正确答案：只有1
5、对于一个具有n个顶点和e条边的无向图，若采用邻接表表示，所有顶点邻接表的边结点总数为（）。
A.e/2
B.e
C.2e
D.n+e
正确答案：2e
6、给定一有向图的邻接表如下。从顶点V1出发按深度优先搜索法进行遍历，则得到的顶点序列为（）。
A.V1，V2，V3，V4，V7，V6，V5
B.V1，V5，V4，V7，V6，V2，V3
C.V1，V5，V6，V4，V7，V2，V3
D.V1，V5，V4，V7，V6，V3，V2
正确答案：V1，V5，V4，V7，V6，V3，V2
7、在图中自a点开始进行广度优先搜索算法可能得到的结果为（）。
A.a， e， d， f， c， b
B.a， c， f， e， b， d
C.a， e， b， c， f， d
D.a， b， e， c， d， f
正确答案：a， b， e， c， d， f
8、任何一个带权无向连通图的最小生成树（）。
A.是唯一的
B.是不唯一的
C.有可能不唯一
D.有可能不存在
正确答案：有可能不唯一
9、对于下列的网，使用克鲁斯卡尔算法求最小生成树，依次得到的边集是（）。
A.{（A，D），（B，C），（E，A），（C，E）}
B.{（A，D），（D，E），（B，C），（C，E）}
C.{（A，D），（D，E），（E，C），（C，B）}
D.{（A，D），（A，B），（A，E），（E，C）}
正确答案：{（A，D），（D，E），（B，C），（C，E）}
10、使用迪杰斯特拉（Dijkstra）算法求下图中从顶点1到其它各顶点的最短路径，依次得到的各最短路径的目标顶点是（）。
A.5， 2， 3， 4， 6
B.5， 2， 3， 6， 4
C.5， 2， 4， 3， 6
D.5， 2， 6， 3， 4
正确答案：5， 2， 3， 6， 4
第六章单元测试
1、二叉排序树或者是一棵空树；或者是具有如下特性的二叉树：（1）若它的左子树不空，则左子树上所有结点的值均小于根结点的值；（2）若它的右子树不空，则右子树上所有结点的值均大于根结点的值。（）
A.正确
B.错误
正确答案：错误
2、查找相同结点的效率折半查找总比顺序查找高。（）
A.正确
B.错误
正确答案：错误
3、在查找树（二叉排序树）中插入一个新结点，总是插入到叶结点下面。（）
A.正确
B.错误
正确答案：错误
4、采用线性探测法处理散列时的冲突，当从哈希表删除一个记录时，不应将这个记录的所在位置置空，因为这会影响以后的查找。（）
A.正确
B.错误
正确答案：正确
5、对一棵二叉排序树按先序方法遍历得出的结点序列是从小到大的序列。（）
A.正确
B.错误
正确答案：错误
6、已知一个长度为16的顺序表L，其元素按关键字有序排列，若采用折半查找法查找一个不存在的元素，则比较次数最多的是（）。
A.4
B.5
C.6
D.7
正确答案：5
7、对于下列关键字序列，不可能构成某二叉排序树中一条查找路径的序列是（）。
A.95，22，91，24，94，71
B.92，20，91，34，88，35
C.21，89，77，29，36，38
D.12，25，71，68，33，34
正确答案：95，22，91，24，94，71
8、在任意一棵非空二叉排序树T1 中，删除某结点v 之后形成二叉排序树T2，再将v 插入T2 形成二叉排序树T3。下列关于T1 与T3 的叙述中，正确的是（）。
I.若v 是T1 的叶结点，则T1 与T3 不同
II.若v 是T1 的叶结点，则T1 与T3 相同
III.若v 不是T1 的叶结点，则T1 与T3 不同
IV.若v 不是T1 的叶结点，则T1 与T3 相同
A.仅I、III
B.仅I、IV
C.仅II、III
D.仅II、IV
正确答案：仅II、III
9、对于线性表（7，34，77，25，64，49，20，14）进行散列存储时，若选用H（K）=K %7作为散列函数，则哈希地址为0的元素有（）个
A.1
B.2
C.3
D.4
正确答案：4
10、适用于折半查找的查找表存储方式及元素排列要求为（）
A.链接方式存储，元素无序
B.链接方式存储，元素有序
C.顺序方式存储，元素无序
D.顺序方式存储，元素有序
正确答案：顺序方式存储，元素有序
11、有一个有序表为｛1， 3， 9， 12， 32， 41，45， 62， 75， 77， 82， 95， 100｝，当用折半查找方法查找值82的结点时，（）次比较后查找成功。
A.8
B.1
C.4
D.2
正确答案：4
12、将{5， 2， 7， 3， 4， 1， 6}依次插入初始为空的二叉排序树。则该树的后序遍历结果是：（）
A.1， 2， 3， 4， 6， 7， 5
B.1， 4， 2， 6， 3， 7， 5
C.1， 4， 3， 2， 6， 7， 5
D.5， 4， 3， 7， 6， 2， 1
正确答案：1， 4， 3， 2， 6， 7， 5
13、有数据{53，30，37，12，45，24，96}，从空二叉树开始逐步插入数据形成二叉排序树，若希望高度最小，应选择下列（）的序列输入。
A.37，24，12，30，53，45，96
B.45，24，53，12，37，96，30
C.30，24，12，37，45，96，53
D.12，24，30，37，45，53，96
正确答案：37，24，12，30，53，45，96
14、下面关于哈希查找的说法，不正确的是（）
A.采用链地址法处理冲突时，查找每个元素的时间是相同的
B.采用链地址法处理冲突时，若插入规定总是在链首，则插入任一个元素的时间是相同的
C.用链地址法处理冲突，不会引起二次聚集现象
D.用链地址法处理冲突，适合表长不确定的情况
正确答案：采用链地址法处理冲突时，查找每个元素的时间是相同的
第七章单元测试
1、快速排序的速度在所有排序方法中为最快，而且所需附加空间也最少。
A.正确
B.错误
正确答案：错误
2、堆排序是稳定的排序方法。
A.正确
B.错误
正确答案：错误
3、在初始数据表已经有序时，快速排序算法的时间复杂度为O（nlog2n）。
A.正确
B.错误
正确答案：错误
4、在用堆排序算法排序时，如果要进行增序排序，则需要采用“大根堆”。
A.正确
B.错误
正确答案：正确
5、比较次数与排序的初始状态无关的排序方法是（）
A.直接插入排序
B.冒泡排序
C.快速排序
D.简单选择排序
正确答案：简单选择排序
6、下列排序方法中，哪一个是稳定的排序方法？（）；
A.直接选择排序
B.希尔排序
C.归并排序
D.快速排序
正确答案：归并排序
7、从未排序序列中依次取出一个元素与已排序序列中的元素依次进行比较，然后将其放在已排序序列的合适位置，该排序方法称为（）排序法。
A.插入
B.选择
C.希尔
D.快速
正确答案：插入
8、对序列{15，9，7，8，20，-1，4}进行排序，进行一趟后数据的排列变为{4，9，-1，8，20，7，15}；则采用的是（）排序。
A.选择
B.快速
C.希尔
D.冒泡
正确答案：希尔
9、假定对元素序列（7，3，5，9，1，12）进行堆排序，并且采用小根堆，则由初始数据构成的初始堆为（）
A.1，3，5，7，9，12
B.1，3，5，9，7，12
C.1，5，3，7，9，12
D.1，5，3，9，12，7
正确答案：1，3，5，9，7，12
10、假定一个初始堆为（1，5，3，9，12，7，15，10）则进行第一趟堆排序后得到的结果为（）
A.3，5，7，9，12，10，15，1
B.3，5，9，7，12，10，15，1
C.3，7，5，9，12，10，15，1
D.3，5，7，12，9，10，15，1
正确答案：3，5，7，9，12，10，15，1
11、一组记录的关键码为（46，79，56，38，40，84），则利用快速排序的方法，以第一个记录为基准得到的一次划分结果为（）。
A.38，40，46，56，79，84
B.40，38，46，79，56，84
C.40，38，46，56，79，84
D.40，38，46，84，56，79
正确答案：40，38，46，56，79，84