第一章 绪论第一章绪论单元测试1、______ 是数据的最小单位。
a、数据项
b、数据元素
c、信息项
d、表元素
2、以下说法不正确的是 ______。
a、数据可由若干个数据元素构成
b、数据项可由若干个数据元素构成
c、数据元素是数据的基本单位
d、数据项是不可分割的最小标识单位
3、数据结构是指 ______ 的集合以及它们之间的关系。
a、计算方法
b、数据元素
c、结构
d、数据
4、计算机所处理的数据一般具备某种内在联系，这是指 ______。
a、元素内部具有某种结构
b、数据项和数据项之间存在某种关系
c、元素和元素之间存在某种关系
d、数据和数据之间存在某种关系
5、在数据结构中，与所使用的计算机无关的是数据的 ______ 结构。
a、物理
b、逻辑和存储
c、存储
d、逻辑
6、数据的逻辑结构可以分为 ______ 两类。
a、紧凑结构和非紧凑结构
b、动态结构和静态结构
c、内部结构和外部结构
d、线性结构和非线性结构
7、数据的逻辑结构是指 ______ 关系的整体。
a、数据元素之间逻辑
b、数据项之间逻辑
c、数据类型之间
d、存储结构之间
8、以下是数据结构中 ______ 属非线性结构。
a、栈
b、串
c、队列
d、平衡二叉树
9、以下属于逻辑结构是 ______。
a、顺序表
b、有序表
c、双链表
d、单链表
10、以下不属于存储结构是 ______。
a、顺序表
b、单链表
c、邻接表
d、线性表
11、在计算机中存储数据时，通常不仅要存储各数据元素的值，而且还有存储 ______。
a、数据的处理方法
b、数据元素的类型
c、数据元素之间的关系
d、数据的存储方法
12、数据结构在计算机内存中的表示是指 ______。
a、数据的存储结构
b、数据结构
c、数据的逻辑结构
d、数据元素之间的关系
13、在数据的存储中，一个节点通常存储一个 ______。
a、数据结构
b、数据类型
c、数据元素
d、数据项
14、在决定选取任何类型的存储结构时，一般不多考虑 ______。
a、各节点的值如何
b、节点个数的多少
c、对数据有哪些运算
d、所用编程语言实现这种结构是否方便
15、数据在计算机的存储器中表示时，逻辑上相邻的两个元素对应的物理地址也是相邻的，这种存储结构称之为 ______。
a、路基结构
b、顺序存储结构
c、链式存储结构
d、以上都对
16、数据采用链式存储结构时，要求 ______。
a、每个节点占用一片连续的存储区域
b、所有节点占用一片连续的存储区域
c、节点的最后一个数据域是指针类型
d、每个节点有多少个后继就设多少个指针域
17、数据的运算 ______。
a、是根据存储结构来定义的效率
b、与采用何种存储结构有关
c、有算术运算和关系运算两大类
d、必须用程序设计语言来描述
18、_______ 不是算法的基本特性。
a、可行性
b、指令序列长度有限
c、在规定的时间内完成
d、确定性
19、计算机中算法指的是解决某一问题的有限运算序列，它必须具备输入、输出、_______。
a、可行性、可移植性和可扩充性
b、可行性、有穷性和确定性
c、确定性、有穷性和稳定性
d、易读性、稳定性和确定性
20、一个算法具有 ________ 等设计目标。
a、可行性
b、至少有一个输入
c、确定性
d、健壮性
21、以下关于算法的说法正确的是 ____________。
a、算法最终必须由计算机程序实现
b、算法等同于程序
c、算法的可行性是指指令不能有二义性
d、其他几个都是错误的
22、算法的时间复杂度与 _______ 有关。
a、问题规模
b、计算机硬件性能
c、编译程序质量
d、程序设计语言
23、算法分析的主要任务之一是分析 _______。
a、算法是否具有较好地可读性
b、算法中是否存在语法错误
c、算法的功能是否符合设计要求
d、算法的执行时间和问题规模之间的关系
24、算法的时间复杂度为o(n2)，表明该算法的 _______。
a、问题规模是
b、执行时间等于
c、执行时间与成正比
d、问题规模与成正比
25、算法分析的目的是 _______。
a、找出数据结构的合理性
b、研究算法中输入和输出的关系
c、分析算法的效率以求改进
d、分析算法的易读性和文档性
26、以下函数中时间复杂度最小的是 _______。
a、t1(n)=nlog2n 5000n
b、t2(n)=-8000n
c、t3(n)=-6000n
d、t4(n)=20000log2n
27、以下函数中时间复杂度最小的是 _______。
a、t1(n)=1000log2n
b、t2(n)=-1000log2n
c、t3(n)=- 1000log2n
d、t4(n)=2nlog2n-1000log2n
28、以下说法中错误的是 _______。 （1）原地工作算法的含义是指不需要任何额外的辅助空间 （2）在相同的问题规模下n下，时间复杂度为o(nlog2n)的算法在执行时间上总是优于时间复杂度为o()的算法 （3）时间复杂度通常是指最坏情况下，估计算法执行时间的一个上限 （4）一个算法的时间复杂度与实现算法的语言无关
a、（1）
b、（1）、（2）
c、（1）、（4）
d、（3）
29、以下数据结构中哪一个是非线性结构？
a、队列
b、栈
c、线性表
d、二叉树
30、下面程序的时间复杂为 _______。 for（i=1，s=0； i<=n； i ） {t=1；for(j=1；j<=i；j ) t=t*j；s=s t；}
a、o(n)
b、o()
c、o( )
d、o()
31、一个算法的时间复杂度为( log2n 14n)/，其数量级表示为 _______。
a、o(n)
b、o()
c、o()
d、o()
32、取算法的时间复杂度为o（），当n=5时执行时间为50s，当n=15时，执行时间为_______。
a、3375
b、1350
c、2025
d、675
33、下面程序的时间复杂度为 _______。 void fun( int n) { int i=1; while (i<=n) i=i*2}
a、o(n)
b、o()
c、o(log2n)
d、o(nlog2n)
34、下面程序的时间复杂度为 _______。 void fun( int n) { int i=1; while (i<=n) i=i*3}
a、o(n)
b、o()
c、o(nlog3n)
d、o(log3n)
35、下面程序的时间复杂度为 _______。 void fun( int n) { int i=1, k=100; while (i<=n) {k ; i =2;} }
a、o(n)
b、o()
c、o(log2n)
d、o(nlog2n)
36、数据元素是数据的最小单位。
37、数据对象就是一组任意数据元素的集合。
38、任何数据结构都具备3个基本运算：插入、删除、和查找。
39、数据的逻辑结构与数据元素在计算机中如何存储有关。
40、如果数据元素值发生改变，则数据的逻辑结构也随之改变。
41、逻辑结构相同的数据，可以采用多种不同的存储方法。
42、逻辑结构不相同的数据，必须采用多种不同的存储方法。
43、逻辑结构相同的数据，在设计存储结构时，它们的节点类型也一定相同。
44、数据的逻辑结构时指数据的各数据项之间的逻辑关系。
45、算法的优劣与算法描述语言无关，但与所用的计算机有关。
46、算法可以用不同的语言描述，如果用c或pascal语言等高级语言来描述，则算法实际上就是程序了。
47、程序一定是算法。
48、算法最终必须由计算机程序实现.
49、算法的可行性是指指令不能有二义性。
50、健壮的算法不会因非法输入数据而出现莫名其妙的状态。
第二章 线性表第二章线性表单元测试1、线性表是具有n个 ______ 的有限序列。
a、表元素
b、字符
c、数据元素
d、数据项
2、线性表是 _______。
a、一个有限序列，可以为空
b、一个有限序列不可以为空
c、一个无限序列，可以为空
d、一个无限序列，不可以为空
3、关于线性表的正确说法是 _______。
a、每个元素都有一个前驱和一个后继元素
b、线性表中至少有一个元素
c、表中元素的排序顺序必须是由小到大或由大到小
d、除第一个元素和最后一个元素外，其余元素有且仅有一个前驱和一个后继元素
4、线性表采用链表存储时，其存放各个元素的单元地址是 _______。
a、必须是连续的
b、一定是不连续的
c、部分地址必须是连续的
d、连续与否均可以
5、链表不具备的特点是 _______。
a、可随机访问任一节点
b、插入删除不需要移动元素
c、不必事先估计存储空间
d、所需空间与其长度成正比
6、线性表的静态链表存储结构与顺序存储结构相比，优点是 _______。
a、所有的操作算法实现简单
b、便于随机存取
c、便于插入和删除
d、便于利用零散的存储器空间
7、线性表的顺序存储结构和链式存储结构相比，优点是 _______。
a、所有的操作算法实现简单
b、便于随机存取
c、便于插入和删除
d、节省存储空间
8、设线性表有n个元素，以下操作中，_______在顺序表上实现比在链表上实现效率高。
a、输入第i（1<=i<=n）个元素值
b、交换第1个元素第2个元素的值
c、顺序输出这n个元素的值
d、输出与给定值x相等的元素在线性表中的符号
9、对于一个线性表，既要求能够较快地进行插入和删除操作，又要求存储结构能够反映数据元素之间的逻辑关系，则应采用 _______ 存储结构。
a、顺序
b、链式
c、散列
d、索引
10、设线性表中有n个元素，以下操作，_______ 在单链表上实现要比在顺序表上实现效率高。
a、删除指定位置元素的后一个元素
b、在第n个元素的后面插入一个新元素
c、顺序输出前k个元素
d、交换第i个元素和第n-i 1个元素的值
11、以下属于顺序表的优点是 _______。
a、插入元素方便
b、删除元素方便
c、存储密度大
d、以上都不对
12、要求线性表采用静态空间分配方式，且插入和删除操作时不需要移动元素，采用的存储结构是 _______。
a、单链表
b、静态链表
c、双链表
d、顺序表
13、如果最常用的操作时取第i个元素及前驱元素，则采用 _______ 存储方式最节省时间。
a、单链表
b、双链表
c、循环单链表
d、顺序表
14、与单链表相比，双链表的优点之一是 _______。
a、插入、删除操作更简单
b、可以进行随机访问
c、可以省略表头指针或表尾指针
d、访问前后相邻节点更方便
15、在长度为n的顺序表中插入一个元素的时间复杂度为 _______。
a、o(n)
b、o()
c、o(log2n)
d、o(1)
16、在长度为n的顺序表中删除一个元素的时间复杂度为 _______。
a、o(1)
b、o()
c、o(log2n)
d、o(n)
17、在两个各有n个元素的递增有序顺序表归并成一个有序顺序表，其最少的比较次数为_______。
a、n
b、2n-1
c、2n
d、n-1
18、将两个长度为n、m的递增有序表归并成一个有序顺序表，其最少的比较次数是_______。（min表示取最小值）
a、n
b、m
c、min(m, n)
d、不确定
19、在带头节点的单链表l为空的判定条件是 _______。
a、l==null
b、l->next==null
c、l->next==l
d、l!=null
20、对于一个具有n个元素的线性表，建立其单链表的时间复杂度为 _______。
a、o(log2n)
b、o(1)
c、o(n)
d、o()
21、在单链表中查找指定值的节点的时间复杂度是 _______。
a、o(log2n)
b、o(1)
c、o()
d、o(n)
22、以下关于单链表的叙述中，不正确的是 _______。
a、节点除自身信息外还包括指针域，因此存储密度小于顺序存储结构
b、逻辑上相邻的元素物理上不必相邻
c、可以通过头节点直接计算第i个节点的存储地址
d、插入、删除运算操作简单，不必移动节点
23、在单链表中，增加一个头节点的目的是为了 _______。
a、使单链表至少有一个节点
b、标识链表中重要节点的位置
c、方便运算的实现
d、说明单链表是线性表的链式存储结构
24、在一个具有n个节点的有序单链表中插入一个新节点并仍然保持有序的时间复杂度是 _______。
a、o(nlog2n)
b、o(1)
c、o(n)
d、o()
25、将长度为m的单链表链接在长度为n的单链表之后的算法时间复杂度为 _______。
a、o(1)
b、o(n)
c、o(m)
d、o(m n)
26、已知一个长度为n的单链表中所有节点是递增有序的，以下叙述中正确的是 _______。
a、插入一个节点使之有序的算法的时间复杂度为o(1)
b、删除最大值节点使之有序的算法的时间复杂度为 o(1)
c、找最小值节点的算法的时间复杂度为 o(1)
d、以上都不对
27、在一个长度为n（n>1）的带头节点的单链表上，另设有尾指针r（指向尾节点），执行_______操作与链表的长度有关。
a、删除单链表中的第一个元素
b、删除单链表的尾节点
c、在单链表中第一个元素前插入一个新节点
d、在单链表最后一个元素后插入一个新节点
28、在一个双链表中，在*p节点之后插入节点*q的操作是 _______。
a、q->prior = p；p-> next=q；p -> next -> prior =q； q ->next = p -> next；
b、q ->next = p -> next；p -> next -> prior =q；p-> next=q；q->prior = p；
c、p-> next=q；q->prior = p；q ->next = p -> next；p -> next -> prior =q；
d、p -> next -> prior =q；q->prior = p；p-> next=q；q ->next = p -> next；
29、在一个双链表中，在*p节点之前插入节点*q的操作是 _______。
a、p -> prior = q；q-> next=p；p -> prior ->next=q； q ->prior= p -> prior；
b、q ->prior= p -> prior；p -> prior ->next=q；q-> next=p；p -> prior = q->next；
c、q-> next=p；p -> next=q；q-> prior ->next= q；q-> next=p；
d、p -> prior ->next=q；q-> next=p；q -> prior = p->prior；p -> prior = q；
30、在一个双链表中， 删除*p节点的操作是 _______。
a、p -> prior –>next= p-> next；p ->next-> prior = p -> prior；
b、p ->prior= p -> prior -> prior；p -> prior ->prior = p；
c、p-> next -> prior = p；p-> next=p-> next-> next；
d、p -> next= p->prior -> prior；p-> prior = p->prior->prior；
31、在一个双链表中， 删除*p节点之后的一个节点，其时间复杂度为_______。
a、o(nlog2n)
b、o(1)
c、o(n)
d、o()
32、非空的循环单链表l的尾节点（由p所指向）满足 _______。
a、p-> next == null
b、p == null
c、p -> next == l
d、p==l
33、带表头结点的双循环链表l为空表的条件是 _______。
a、l== null
b、l-> next -> prior == null
c、l -> prior == null
d、l -> next == l
34、某线性表最常用的操作是在尾元素之后插入一个元素和删除尾元素，则采用 _______ 存储方式最节省运算时间。
a、单链表
b、循环单链表
c、双链表
d、循环双链表
35、如果对含有n（n>1）个元素的线性表的运算只有4种，即删除第一个元素、删除尾元素、在第一个元素前面插入新元素、在尾元素的后面插入新元素，则最好使用_______。
a、只有尾节点指针没有头节点的循环单链表
b、只有尾节点指针没有头节点的非循环双链表
c、只有开始数据节点指针没有尾节点指针的循环双链表
d、既有表头指针也有表尾指针的循环单链表
36、在某线性表最常用的操作是在尾元素之后插入一个元素和删除第一个元素。故采用_______ 存储方式最节省时间。
a、单链表
b、仅有头节点指针的循环单链表
c、双链表
d、仅有尾指针的循环单链表
37、两个表长都为n、不带表头结点的单链表，结点类型都相同，头指针分别为h1与h2，且前者是循环链表，后者是非循环链表，则 _______。
a、对于两个链表来说，删除首节点的操作，其时间复杂度都是o(1)
b、对于两个链表来说，删除尾节点的操作，其时间复杂度都是o(n)
c、循环链表要比非循环链表占用更多的内存空间
d、h1和h2是不同类型的变量
38、在长度为n的 _______ 上，删除第一个元素，其算法的时间复杂度为o(n)。
a、只有表头指针的不带表头节点的循环单链表
b、只有表尾指针的不带表头节点的循环单链表
c、只有表尾指针的带表头节点的循环单链表
d、只有表头指针的带表头节点的循环单链表
39、下面关于线性表的叙述错误的是 _______。
a、线性表采用顺序存储必须占用一片连续的存储空间
b、线性表采用链式存储不必占用一片连续的存储空间
c、线性表采用链式存储便于插入和删除操作的实现
d、线性表采用顺序存储便于插入和删除操作的实现
40、对于双链表，在两个节点之间插入一个新节点是，需要修改 _______ 个指针域。
a、1
b、2
c、3
d、4
41、在单链表中，要删除某一指定的节点，必须找到该节点的 _______ 节点。
a、后继
b、头节点
c、前驱
d、尾节点
42、求一个单链表长度的算法的时间复杂度为 _______。
a、o(log2n)
b、o(n)
c、o(1)
d、o()
43、线性表中每个元素都有一个前驱元素和一个后继元素。
44、线性表中所有元素的排列顺序必须从小到大或从大到小。
45、静态链表既有顺序存储结构的优点，又有动态链表的优点，所以，利用它存取第i个元素的时间与元素个数n无关。
46、静态链表与动态链表在元素的插入、删除方面类似，不需要做元素的移动。
47、线性表的顺序存储结构优于链式存储结构。
48、在循环单链表中，从表中任一节点出发都可以通过前后移动操作遍历整个循环链表。
49、在单链表中，可以从头节点开始查找任何一个节点。
50、在双链表中，可以从任一节点开始沿着同一方向查找到任何其他节点。
第三章 栈和队列第三章栈和队列单元测试1、元素a、b、c、d依次进栈后，栈顶元素是 _______。
a、a
b、b
c、c
d、d
2、经过以下运算后， x的值是 _______。 initstack (s); push(s, a); push(s, b); pop(s, x); gettop(s,x)
a、a
b、b
c、1
d、0
3、经过以下栈运算后，stackempty(s)的值是 _______。 initstack (s); push(s, a); push(s, b); pop(s, x); pop(s,y)
a、a
b、b
c、1
d、0
4、已知一个栈的进栈序列是abc，出栈序列为cba，经过栈的操作是 _______。
a、push,pop,push,pop,push,pop
b、push, push, push, pop, pop, pop
c、push, push,pop, pop,push,pop
d、push,pop,push, push,pop, pop
5、若元素a、b、c、d、e、f依次进栈，允许进栈、退栈的操作交替进行，但不允许连续3次退栈工作，则不可能得到的出栈序列是 _______。
a、dcebfa
b、cbdaef
c、bcaefd
d、afedcb
6、设一个栈的输入序列为a、b、c、d，则借助一个栈所得的输出序列不可能是_______。
a、abcd
b、dcba
c、acdb
d、dabc
7、一个栈的进栈序列是abcde，则栈的不可能的输出序列是 _______。
a、edcba
b、decba
c、dceab
d、abcde
8、已知一个栈的进栈序列是1，2，3，…n，其输出序列的第一个元素是i（1≤i≤n），则第j（1≤j≤n）个出栈元素是_______。
a、i
b、n-i
c、j-i 1
d、不确定
9、已知一个栈的进栈序列是1,2,3，…n，其输出序列是p1,p2,…pn，若p1=n,则pi的值是_______。
a、i
b、n-i
c、n-i 1
d、不确定
10、设n个元素的进栈序列是p1,p2,…pn，其输出序列是1,2,3，…n，若pn=1，则pi（1≤i≤n-1）的值是_______。
a、n-i 1
b、n-i
c、i
d、不确定
11、设n个元素的进栈序列是1,2,3，…n，其输出序列是p1,p2,…pn，若p1=3，则p2的值是_______。
a、一定是2
b、一定是1
c、不可能是1
d、以上都不对
12、设n个元素的进栈序列是p1,p2,…pn，其输出序列是1,2,3，…n，若p3=1，则p1的值是_______。
a、可能是2
b、一定是2
c、不可能是2
d、不可能是3
13、设n个元素的进栈序列是p1,p2,…pn，其输出序列是1,2,3，…n，若p3=3，则p1的值是_______。
a、可能是2
b、一定是2
c、不可能是1
d、一定是1
14、设有5个元素的进栈序列是a，b，c，d，e，其输出序列是c，e，d，b，a，则该栈的容量至少是 _______。
a、1
b、2
c、3
d、4
15、在数据处理过程中常需要保存一些中间数据，如果后保存的数据先处理，则使用_______来保存这些数据。
a、线性表
b、栈
c、队列
d、单链表
16、判定一个顺序栈st为（元素个数最多为maxsize）空的条件为 _______。
a、st.top==-1
b、st.top!=-1
c、st.top!=maxsize
d、st.top==maxsize
17、判定一个顺序栈st为（元素个数最多为maxsize）为栈满的条件为 _______。
a、st.top！==-1
b、st.top=-1
c、st.top!=maxsize-1
d、st.top==maxsize-1
18、表达式a*(b c)-d的后缀表达式是 _______。
a、a b c d * -
b、a b c * d -
c、a b c * d -
d、- * a b c d
19、若一个栈用数组data[1..n]存储，初始栈顶指针top为n 1，则以下元素x进入栈的正确操作是 _______。
a、top ; data[top]=x;
b、data[top]=x;top ;
c、top--; data[top]=x;
d、data[top]=x;top--;
20、若一个栈用数组data[1..n]存储，初始栈顶指针top为n，则以下元素x进入栈的正确操作是 _______。
a、top ; data[top]=x;
b、data[top]=x;top ;
c、top--; data[top]=x;
d、data[top]=x;top--;
21、若一个栈用数组data[1..n]存储，初始栈顶指针top为0，则以下元素x进入栈的正确操作是 _______。
a、top ; data[top]=x;
b、data[top]=x;top ;
c、top--; data[top]=x;
d、data[top]=x;top--;
22、若一个栈用数组data[1..n]存储，初始栈顶指针top为1，则以下元素x进入栈的正确操作是 _______。
a、top ; data[top]=x;
b、data[top]=x;top ;
c、top--; data[top]=x;
d、data[top]=x;top--;
23、链栈与顺序栈相比有一个明显的优点，即 _______。
a、插入操作更方便
b、通常不会出现栈满的情况
c、总是不会出现栈空的情况
d、删除操作更加方便
24、以下各链表均不带有头节点，其中最不合适用作链栈的链表是 _______。
a、只有表头指针没有表尾指针的循环双链表
b、只有表尾指针没有表头指针的循环双链表
c、只有表尾指针没有表头指针的循环单链表
d、只有表头指针没有表尾指针的循环单链表
25、如果以链表作为栈的存储结构，则退栈操作时 _______。
a、必须判断链栈是否为满
b、判断链栈元素的类型
c、必须判断链栈是否空
d、对链栈不做任何判断
26、向一个不带头节点的栈顶指针为lst的链栈中插入一个s所指向节点时，则执行 _______。
a、lst->next = s;
b、s->next=lst->next; lst->next=s;
c、s->next=lst; lst=s;
d、s->next=lst; lst->next=s;
27、从一个不带头节点的栈顶指针为lst的栈链中删除一个节点时，用x保存被删节点的值，则执行 _______。
a、x=lst; lst = lst->next ;
b、x=lst->data
c、lst=lst->next; x=lst->data;
d、x=lst->data; lst= lst->next;
28、栈和队列的不同点是 _______。
a、都是线性表
b、都不是线性表
c、栈只能在一端进行插入删除操作，而队列在不同端进行插入删除操作
d、没有不同点
29、经过下列运算后，队头的元素是 _______。 initqueue(qu); enqueue(qu, ‘a’); enqueue(qu, ‘b’); enqueue(qu, ‘c’); dequeue(qu);
a、a
b、b
c、1
d、0
30、若某循环队列有队首指针front和队尾指针rear，在队不满时进队操作仅会改变_______。
a、front
b、rear
c、front和rear
d、以上都不对
31、循环队列qu的队满条件（front队首指针指向队首元素的前一位置，rear队尾指针指向队尾元素）是 _______。
a、(qu.rear 1)%maxsize==(qu.front 1)%maxsize
b、(qu.rear 1)%maxsize==qu.front 1
c、(qu.rear 1)%maxsize==qu.front
d、qu.rear==qu.front
32、设循环队列中数组的下标是0~n-1，其队头、队尾指针分别为f和r（f指向队首元素的前一位置，r指向队尾元素），则元素个数为 _______。
a、r-f
b、r-f-1
c、(r-f)%n 1
d、(r-f n)%n
33、最适合用做链队列的不带表头节点的链表是 _______。
a、带首节点指针和尾节点指针的循环单链表
b、只带尾节点指针的非循环单链表
c、只带首节点指针的非循环单链表
d、只带尾节点指针的循环单链表
34、假设用一个不带表头节点的单链表表示队列，在进行删除操作时，_______。
a、仅修改头指针
b、仅修改尾指针
c、头、尾指针都要修改
d、头、尾指针可能都要修改
35、假设用一个不带头节点的单链表表示队列，队头和队尾指针分别为front和rear，则判断队空的条件是 _______。
a、front == rear
b、front!==null
c、rear!==null
d、front == null
36、最不合适用做链队的不带头节点的链表是 _______。
a、只带队首节点指针的非循环单链表
b、只带队首节点指针的循环双链表
c、只带队尾节点指针的循环双链表
d、以上都不合适
37、假设用qu[0..m]实现循环队列，f、r分别为队首元素的前一个位置和队尾位置。若用“(r 1)%(m 1)==f”作为队满的标志，则 _______。
a、可用“f==r”作为队空的标志
b、可用“f > r”作为队空的标志
c、可用“(f 1)%(m 1)==r”作为队空的标志
d、队列中最多可以有m 1个元素
38、若用一个大小为6的数组来实现循环队列，且当前rear 和front的值分别是0和3，当从队列中删除一个元素，再加入两个元素后，rear 和front的值分别是_______。
a、1和5
b、2和4
c、4和2
d、5和1
39、栈底元素是不能删除的元素。
40、顺序栈中元素值的大小是有序的。
41、n个元素依次进栈，它们的出栈顺序和进栈顺序一定正好相反。
42、栈顶元素和栈底有可能是同一元素。
43、若用s[0..m-1]表示顺序栈的存储空间，则对栈的进栈、出栈操作最多只能进行m次；
44、栈是一种对进栈、出栈操作总次数做了限制的线性表。
45、栈是一种对进栈、出栈操作的次序做了限制的线性表。
46、对顺序栈进行进栈、出栈操作，不涉及元素的前、后移动问题。
47、空栈没有栈顶指针。
48、栈和队列都是限制存取端的。
49、队列是一种对进队、出队操作的次序做了限制的线性表。
50、若用“队首指针的值和队尾指针的值相等”作为循环顺序队为空的标识，则在设置一个空队列时，只需给队首指针和队尾指针赋同一个值，在顺序表地址范围内不管什么值都可以。
第五章 数组与广义表第五章数组与广义表单元测试1、以行序优先顺序存储数组a[5][5]；假定a[0][0]的地址为1000, 每个元素占4个字节，下标变量a[4][3]的地址是____。
a、1023
b、1046
c、1069
d、1092
2、数组a[1．．6][1．．5] （无0行0列）以列序优先顺序存储，第一个元素a[1][1]的地址为1000，每个元素占2个存储单元，则a[3][4]的地址是____。
a、1026
b、1038
c、1040
d、1046
3、设有一个5行4列的矩阵a，采用行序优先存储方式，a[0][0]为第一个元素，其存储地址为1000，a[2][2]的地址为1040，则a[3][0]的地址为_________。
a、1024
b、1048
c、1060
d、1096
4、设有一个10行10列的矩阵a，采用行序优先存储方式，存储全部数据需要400个字节的空间。如果a[0][0]为第一个元素，其存储地址为1000，则a[3][6]的地址为_________。
a、1014
b、1144
c、1036
d、1056
5、设有一个10行10列的矩阵a，采用行序优先存储方式。如果a[0][0]为第一个元素，其存储地址为1000，a[2][3]的存储地址为1069，则存储一个元素需要的单元数是_________。
a、1
b、2
c、3
d、4
6、不能够对数据元素进行随机访问的物理结构是_________。
a、数组的顺序存储
b、对称矩阵的压缩存储
c、三元组顺序表
d、三对角矩阵的压缩存储
7、对特殊矩阵采用压缩存储的目的主要是_________。
a、表达变得简单
b、对矩阵元素的存储变得简单
c、去掉矩阵中的多余元素
d、减少不必要的存储空间
8、对n*n的对称矩阵进行压缩存储，需要保存的数据元素的个数是_________。
a、n
b、
c、n(n 1)
d、n(n 1)/2
9、设10*10的对称矩阵下三角保存sa[1．．55]中，其中a[1][1]保存在sa[1]中，a[5][3] 保存在sa[k]中，这里k等于_________。
a、12
b、13
c、14
d、15
10、对n行n列的三对角矩阵，需要保存的数据元素的个数是_________。
a、3n
b、
c、3n-2
d、n(n 1)
11、设10*10三对角矩阵保存sa[1．．28]中，其中a[1][1]保存在sa[1]中，a[5][5] 保存在sa[k]中，这里k等于_________。
a、10
b、11
c、12
d、13
12、某稀疏矩阵a采用三元组顺序表作为存储结构，对于矩阵元素的赋值运算assign(a,e,i,j)，不可能_________。（在assign(a,e,i,j)中，e是矩阵元素ai,j的值，i和j分别为矩阵元素的行号和列号）。
a、修改某个三元组的行号或列号
b、插入一个新的三元组
c、修改某个三元组的元素值
d、删除一个三元组
13、对稀疏矩阵进行压缩存储方法一般有两种，分别为________。
a、三元组和对称矩阵
b、对角矩阵和散列
c、散列和十字链表
d、三元组顺序表和十字链表
14、下列叙述中，不正确的是__________。
a、数组是一种线性结构
b、数组是一种定长的线性表
c、除了插入与删除操作外，数组的基本操作还有存取、修改、检索和排序等
d、数组的基本操作有存取、修改、检索和排序等，没有插入与删除操作
15、某稀疏矩阵a采用十字链表作为存储结构，对于矩阵元素的赋值运算assign(a,e,i,j)，不可能_________。（在assign(a,e,i,j)中，e是矩阵元素ai,j的值，i和j分别为矩阵元素的行号和列号）
a、修改稀疏矩阵的行列数
b、修改某个结点的值
c、增加一个新结点
d、删除一个结点
16、使用三元组来保存稀疏矩阵中的非零元素，三元组不包括非零元素的__________。
a、个数
b、行号
c、列号
d、元素值
17、使用三元组顺序表或十字链表作为稀疏矩阵中的物理结构，对元素的访问形式只能是__________。
a、随机访问
b、哈希访问
c、顺序访问
d、索引访问
18、使用三元组顺序表作为稀疏矩阵中的物理结构，要求对三元组按行序优先的顺序进行存放，原因是按行序优先能__________。
a、节省存储空间
b、方便稀疏矩阵的运算
c、提高元素的访问速度
d、使元素的摆放形式漂亮一些
19、表头和表尾均为空义表的广义表是__________。
a、( )
b、(( ),( ))
c、(( ))
d、((( )))
20、广义表 (a,(b,c),d) 的表长是______。
a、3
b、4
c、5
d、6
21、广义表((a,()),(b,(c)),(()))的深度是______。
a、3
b、4
c、5
d、6
22、广义表 ((a,b),(c),(d)) 的表头是______。
a、a,b
b、(a,b)
c、a
d、()
23、广义表((a,b),(c),(d))的表尾是______。
a、(d)
b、d
c、(a,b)
d、((c),(d))
24、对广义表g=((a, (( ),b)), ((( ),(c,d)),( )))执行tail(head(head(tail(g))))操作的结果是_________。
a、( )
b、c
c、(c,d)
d、((c,d))
25、下列叙述中，不正确的是______。
a、对称矩阵只需要存放包括对角线元素在内的下（或上）三角元素即可
b、对角矩阵只需要存放其值不一定为0的对角线上元素
c、稀疏矩阵中值为0的元素较多，因此可以采用三元组方法存储非零元素
d、稀疏矩阵中大量值为0的元素分布有规律，因此可以采用三元组表方法存储
26、在一维数组（向量）中，能很方便地通过增加数据元素使数组长度增加。
27、数组是一种复杂的数据结构，数据元素之间的关系既不是线性的，也不是树型的。
28、数组是一个定长的线性表，所以不能有元素的增加与删除操作。
29、数组的顺序存储结构中，按行序（或列序）优先次序存放数组元素，是为了方便寻址公式的分析。
30、通过数组的顺序存储结构，按行序优先次序保存了数组的全部数据元素，可以通过寻址公式对数组元素进行随机访问。
31、n维数组的存储方案中，每一个数组元素都有n个方向的关系（约束）。
32、对对称矩阵进行压缩存储，能提高存储效率，其压缩率可低至50%。（压缩率为压缩后的大小与压缩前的大小之比）
33、对特殊矩阵进行压缩存储后，无法实现对其元素进行随机访问。
34、在特殊矩阵中，有很多值相同的元素并且有规律地分布，所以没有必要重复存储值相同的元素。
35、元素a[i][j]在对称矩阵的下三角位置上的条件是i
36、元素a[i][j]在三对角矩阵的三对角位置上的条件是|i-j|≤1。
37、以三元组顺序表存储稀疏矩阵时，可以通过寻址公式对数据元素进行随机访问。
38、以三元组顺序表存储稀疏矩阵时，对元素a[i][j]赋值0，可能会在三元组顺序表中引起三元组（i，j，a[i][j]）后面的三元组向前面移动。
39、以三元组顺序表存储稀疏矩阵时，对元素a[i][j]赋值一个非零值，只需要三元组顺序表的最后添加新的三元组（i，j，a[i][j]）。
40、以十字链表存储稀疏矩阵时，只能对数据元素进行顺序访问。
41、以十字链表存储稀疏矩阵时，对元素a[i][j]赋值0，一定会在2个单链表中进行结点的删除操作。
42、以十字链表存储稀疏矩阵时，对元素a[i][j]赋值一个非零值，一定会在2个单链表中进行增加结点的操作。
43、当某稀疏矩阵经常进行元素的赋值运算时，十字链表比三元组表更适合作为其存储结构。
44、一个广义表的表头不一定是一个广义表。
45、一个非空广义表的表尾总是一个广义表。
46、广义表的长度是指广义表中括号嵌套的层数。
47、广义表(a,(b,(c,d,((),()))))的深度为5。
48、广义表(a,(b,(c,d,((),()))))的长度为6。
49、广义表中的元素既可以是原子，也可以是广义表。
50、通常广义表的物理结构是链式的。
第六章 树与二叉树
第六章树单元测试
1、树最适合用来表示 。
a、有序数据元素
b、无序数据元素
c、元素之间具有分支层次关系的数据
d、元素之间无联系的数据
2、在树结构中，若结点a有三个兄弟，且b是a的双亲，则b的度是 。
a、3
b、4
c、5
d、2
3、下列陈述中正确的是 。
a、二叉树是度为2的有序树
b、二叉树中结点只有一个孩子时无左右之分
c、二叉树中必有度为2的结点
d、二叉树中每个结点最多只有两棵子树，并且有左右之分
4、设深度为h的二叉树中只有度为0和度为2的结点，则此类二叉树中所包含结点数至少为 。
a、2h
b、2h-1
c、2h 1
d、h 1
5、设深度为h的二叉树中只有度为0和度为2的结点，则此类二叉树中所包含结点数至多为 。
a、
b、
c、
d、
6、具有n(n>0)个结点的完全二叉树的深度为 。
a、élog2(n)ù
b、ë log2(n)û
c、ë log2(n) û 1
d、élog2(n) 1ù
7、具有32个结点的完全二叉树有 个叶子结点。
a、14
b、15
c、16
d、17
8、一棵完全二叉树的第6层上有23个叶子结点，则此二叉树最多有 结点。
a、78
b、79
c、80
d、81
9、具有3个结点的二叉树有 种。
a、3
b、4
c、5
d、6
10、若一棵二叉树有9个度为2的结点，5个度为1的结点，则叶子结点的个数为 。
a、9
b、10
c、15
d、不确定
11、一棵二叉树有35个结点，则所有结点的度之和为 。
a、35
b、16
c、33
d、34
12、二叉树是非线性数据结构，所以 。
a、它不能用顺序存储结构存储
b、它不能用链式存储结构存储
c、顺序存储结构和链式存储结构都能存储
d、顺序结构和链式结构都不能使用
13、用顺序存储的方法将n个结点的完全二叉树中所有结点按层逐个依从左至右的次序存放在一维数组r[1:n]中，若结点r[i]有左孩子，则左孩子是 。
a、r[2i-1]
b、r[2i]
c、r[2i 1]
d、r[2i 2]
14、一棵深度为k且只有k个结点的二叉树按照完全二叉树顺序存储的方式存放于一个一维数组r[n]中，则n至少是 才能确保正确存储。
a、2k
b、2k 1
c、
d、
15、以下存储结构中，不是树的存储结构是 。
a、双亲表示法
b、孩子兄弟链表
c、孩子链表存储结构
d、广义表
16、用二叉链表表示具有n个结点的二叉树时，值为空的指针域的个数为 。
a、n-1
b、n
c、n l
d、2n
17、二叉树的先序遍历序列和后序遍历序列正好相反，则该二叉树一定满足的条件是 。
a、空或只有一个结点
b、高度等于其结点数
c、任一结点无左孩子
d、任一结点无右孩子
18、下列二叉树，其后序遍历序列与层次遍历序列相同的非空二叉树是 。
a、满二叉树
b、完全二叉树
c、单支树
d、只有根结点的二叉树
19、对二叉树的结点从1开始连续编号，要求每个结点的编号大于其左右子女的编号，同一结点的左、右子女中，其左子女的编号小于其右子女的编号，则可采用 遍历实现二叉树的这种结点编号。
a、先序
b、中序
c、后序
d、层序
20、在二叉树中有两个结点m和n，如果m是n的祖先，使用 非递归过程更方便找到从m到n的路径。
a、先序遍历
b、中序遍历
c、后序遍历
d、层次遍历
21、不使用栈实现二叉树后序遍历的非递归算法，最佳方案是二叉树的存储结构采用 表示。
a、二叉链表
b、广义表
c、三叉链表
d、顺序表
22、在一个非空二叉树的中序序列中，根结点的右边是 。
a、只有右子树上的所有结点
b、只有右子树上的部分结点
c、只有左子树上的部分结点
d、只有左子树上的所有结点
23、设某棵二叉树的中序遍历序列为abcd，先序遍历序列为cabd，则后序遍历该二叉树得到序列为 。
a、badc
b、bcda
c、cdab
d、cbda
24、先序遍历序列为abc，后序遍历序列为cba的二叉树共有 棵。
a、1
b、2
c、3
d、4
25、若二叉树采用二叉链表存储结构，要交换所有分支结点的左右子树的位置，利用基于 遍历的递归算法最合适。
a、逆中序
b、中序
c、后序
d、层次
26、一棵二叉树的先序遍历序列为efhigjk,中序遍历序列为hfiejkg,则该二叉树根结点的右孩子为 。
a、e
b、f
c、g
d、h
27、一棵二叉树采用二叉链表存储结构存储，根指针为t，下列递归算法求其先序序列中第k（1≦k≦二叉树中结点的个数）个结点的值，算法的画线处应填的语句是 。
a、k--
b、n
c、t = t->lchild
d、t = t->rchild
28、二叉树采用二叉链表存储结构存储，根指针为t，下列递归算法求其叶子结点的个数, 算法的画线处应填的语句是 。
a、t->lchild == null
b、t->lchild == null && t->rchild != null
c、t->rchild == null
d、t->lchild == null && t->rchild == null
29、判断线索二叉链表中*p结点有右孩子结点的条件是 。
a、p!=null
b、p->rchild!=null
c、p->rtag==0
d、p->rtag==1
30、将下图所示的二叉树按中序线索化，结点c的左指针与结点h的右指针分别指向 。
a、a, c
b、g, c
c、h, g
d、a, g
31、二叉树线索化后，仍不能有效求解的问题是 。
a、先序线索二叉树中求先序后继
b、中序线索二叉树中求中序后继
c、中序线索二叉树中求中序前驱
d、后序线索二叉树中求后序后继
32、基于中序线索化链表，其头结点指针为head，对应的二叉树为空的判断条件是 。
a、head==null
b、head->lchild==head && head->rchild==head
c、head->ltag==0
d、head->rtag==1
33、讨论树、森林和二叉树的关系，目的是________。
a、将树、森林按二叉树的存储结构进行存储，并利用二叉树的算法解决树与森林的有关问题
b、将树、森林转化成二叉树，统一逻辑表示形式
c、只是为了方便定义树、森林的遍历方法
d、体现一种技巧，没有什么实际意义
34、设森林f有3棵树，分别有9、8和7个结点，则f此排列次序转换成二叉树后根结点的右子树上结点的个数是 。
a、16
b、15
c、7
d、17
35、如果二叉树t2是由一棵树t1转换而来的二叉树，那么t1结点的先根遍历序列对应t2的 序列。
a、先序遍历
b、中序遍历
c、后序遍历
d、层次遍历
36、给定一棵树的二叉链表存储结构，把这棵树转换为二叉树后，这棵二叉树的形态是 。
a、唯一的
b、有多种
c、有多种，但根结点都没有左孩子
d、有多种，但根结点都没有右孩子
37、由树转换成的二叉树里，一个结点n的左孩子是n在原树里对应结点的 。
a、最左孩子结点
b、最右孩子结点
c、最邻近的右兄弟
d、最邻近的左兄弟
38、用13个权值构造哈夫曼树，则该哈夫曼树共有 个结点。
a、13
b、12
c、26
d、25
39、对n（n≧2）个权值不同的字符依哈夫曼算法构造哈夫曼树，下面关于该哈夫曼树的叙述中错误的是 。
a、树中一定没有度为1的结点
b、该树一定是一棵完全二叉树
c、树中两个权值最小的结点一定是兄弟结点
d、树中任何一个非叶结点的权值一定不小于下一层任意一个结点的权值
40、设一组权值集合w=(2，4，5，7)，要求根据这些权值集合构造一棵哈夫曼树，则这棵哈夫曼树的带权路径长度为 。
a、36
b、46
c、35
d、34
41、树中元素结点是多对多的关系。
42、树与二叉树是两种不同的树形结构。
43、一棵满二叉树中每棵子树都是完全二叉树。
44、完全二叉树适合使用顺序存储结构
45、对于任意的二叉树，如果其叶子结点数为n0，度为2的结点数为n2，则n2＝n0＋1。
46、对一棵树进行先根遍历与后根遍历，其中叶子结点出现的相对次序是相同的。
47、由二叉树的某种遍历方式产生的结果是一个线性序列。
48、用二叉树的先序序列和后序序列可以导出它的中序序列。
49、在某种遍历的线索二叉链表中，进行这种遍历时可以直接沿所有右指针一直搜索下去，从而访问所有结点。
50、可以不用栈实现基于中序线索二叉链表对二叉树进行中序遍历。
51、将一棵含有两个以上结点的树转换成二叉树后，该二叉树的根结点没有左子树。
52、树有先根遍历与中根遍历两种遍历方法。
53、树的孩子兄弟表示法是一种二叉链表表示法。
54、二叉树的先序遍历的递归算法的时间复杂度为线性级。
55、在哈夫曼树中，权值较大的叶子结点一般离根结点较远。
56、在哈夫曼编码中，当两个不同字符出现的频率相同时，其编码也相同。
第七章 图
第七章图单元测试
1、设有5个结点的无向图，该图至少应有_________条边才能确保是一个连通图。
a、5
b、6
c、7
d、8
2、设图g=(v,vr)，其中: v={a,b,c,d,g}，vr={(a,c),(a,d),( b,c),(b,d) ,(g,c),(b,g)}，则对应的图形为_________。
a、
b、
c、
d、
3、设某有向图中有n个顶点，则该有向图对应的邻接表中有_________个表头结点。
a、n-1
b、n
c、n 1
d、n 2
4、在一个无向图中所有顶点的度数之和等于所有边数的_________倍。
a、1
b、2
c、3
d、1/2
5、一个无向连通图的生成树是该连通图的_____。
a、极大连通子图
b、连通子图
c、极小连通子图
d、强连通子图
6、设某无向图中有n个顶点，则该无向图邻接矩阵的大小是_________。
a、
b、
c、
d、n(n 1)/2
7、设有n个顶点e条边的无向图，采用邻接矩阵作为物理结构，则删除与某顶点vi关联的所有边算法的时间复杂度为_________。
a、o()
b、o(n*e）
c、o(n e）
d、o(n）
8、设有n个顶点e条弧的有向图，采用邻接表作为物理结构，则求某顶点vi度的算法的时间复杂度为_________。
a、o()
b、o(n*e）
c、o(n e）
d、o(n）
9、设无向图g=(v,e)和g'=(v',e')，如果g'是g的生成树，则下列说法中错误的是_____。
a、g'是g的子图
b、g'是g的一个无环子图
c、g'是g的极小连通子图且v=v'
d、g'是g的连通分量
10、设g是一个非连通的无向图，共有10条边，则该图至少有_____个顶点。
a、5
b、6
c、7
d、8
11、n个顶点的有向图为强连通图时，至少含有________。
a、n-1条弧
b、n条弧
c、n(n-1)/2条弧
d、n(n-1)条弧
12、如果从无向图的一个顶点出发，进行一次深度优先搜索能访问所有顶点，则该无向图是一个________。
a、连通图
b、强连通图
c、完全图
d、dag图
13、如图所示的有向图，共有________个强连通分量。
a、1
b、2
c、3
d、4
14、在下图中，从顶点a出发进行深度优先遍历可得到的序列是_________。
a、adcbg
b、acdbg
c、adgbc
d、abdcg
15、对图进行深度优先搜索遍历，需要借助的数据结构为________。
a、栈
b、队列
c、线索二叉树
d、广义表
16、对图进行广度优先搜索遍历，需要借助的数据结构为________。
a、栈
b、队列
c、线索二叉树
d、广义表
17、最小生成树是指________。
a、连通网的所有生成树中权值之和最小的生成树
b、由连通网得到的边数最少的生成树
c、由连通网得到的顶点数相对较少的生成树
d、连通网的极小连通子图
18、在下图中，从顶点a出发进行广度优先遍历可得到的序列是_________。
a、adcbg
b、acdgb
c、adgbc
d、agbdc
19、对如图所示的无向连通网，从顶点a出发，使用prim算法得到的最小生成树是________。
a、
b、
c、
d、
20、可借助于_________判别有向图中是否存在回路。
a、迪杰斯特拉算法
b、floyd算法
c、拓扑排序算法
d、prim算法
21、如图所示的dag图，其拓扑排序序列为_________。
a、adbgc
b、acdgb
c、adgbc
d、agbdc
22、下列关于工程计划的aoe网的叙述中，不正确的是_________。
a、关键活动不按期完成，会影响整个工程的完成时间
b、任何一个关键活动的提前完成，整个工程的完成时间都会提前
c、所有关键活动都提前完成，会提前整个工程的完成时间
d、某个关键活动提前完成，可能会提前整个工程的完成时间
23、使用迪杰斯特拉最短路径算法，求一个源点到其它各顶点的最短路径，该算法的时间复杂度为________。
a、o()
b、o(n log n)
c、
d、
24、使用弗洛伊德算法，求任意2个顶点的最短路径，该算法的时间复杂度为________。
a、o()
b、o(n log n)
c、
d、
25、某无向图的邻接矩阵如下所示，可以得出，该图共有__________个顶点。
a、3
b、4
c、9
d、5
26、如果n（n>2）个顶点的有向图有二个强连通分量，则至少有n-1条弧。
27、n个顶点的无向图，至少需要n条边才可能是连通图。
28、连通分量是指无向图的极小连通子图。
29、无向图的邻接矩阵必然是对称矩阵。
30、有n（n>1）个顶点，-2n 2条弧的有向图不一定是强连通图。
31、图的邻接矩阵大小，不但与图的顶点数有关，而且与图的边数也有关。
32、使用有向图的十字链表，能非常方便地计算出任意一个顶点的出度和入度。
33、一个有n个顶点e条边的无向图的邻接表中，有2e个表结点。
34、一个有n个顶点e条边的无向图的邻接多重表中，有2e个表结点。
35、一个有n个顶点e条弧的有向图的逆邻接表中，有2e个表结点。
36、一个有向图的邻接表和逆邻接表中的表结点个数一定相等。
37、有向图有n个顶点e条弧，采用邻接表存储，则计算某顶点度的算法需要访问n e个单链表的表结点。
38、邻接表的空间复杂度为，与边（或弧）的条数无关。
39、对于一个连通图，通过一次深度优先遍历，能访问到所有顶点。
40、从无向图的任一顶点出发，进行一次广度优先搜素，都能访问到图的所有顶点。
41、对于一个连通图，有唯一的一棵深度优先遍历生成树。
42、当无向连通网中的边较少时，采用prim算法求其最小生成树效率较高。
43、kruskal算法适合求解边稠密图的最小生成树。
44、某无向连通网只有唯一的一棵最小生成树，则该无向连通网个边上的权值互不相同。
45、可以借助于拓扑排序算法来判断一个有向图是否有回路。
46、在某aov网中，顶点vi到顶点vj有路径，则该aov网的任何拓扑排序序列中，vi一定排在vj的前面。
47、需要借助于深度优先遍历算法来求得aoe网的关键路径。
48、在某aoe网中， ak是从顶点vi到顶点vj的活动，则活动ak的最早开始时间等于vi的最早发生时间。
49、使用迪杰斯特拉算法，能求出有向网中任意2个顶点的最短路径。
50、在求出有向网中任意2个顶点的最短路径时，floyed算法的时间效率优于使用迪杰斯特拉算法。
第九章 查找
第九章查找单元测试
1、对于查找表(13,27,38,49,50 ,65,76,97)采用顺序查找，在等概率情况下查找成功的平均查找长度是（ ）。
a、4.5
b、4
c、8
d、9
2、在关键字序列（10,20,30,40,50）中采用折半查找20，依次与（ ）关键字进行了比较。
a、30,20
b、30,10,20
c、40,20
d、20
3、在关键字序列（8,12,20,25,33）中，采用二分查找25，关键字之间比较需要（ ）次。
a、1
b、2
c、3
d、4
4、对于长度为11的有序表，按折半查找，在等概率情况下查找成功时，其平均查找长度是（ ）。
a、1
b、2
c、3
d、4
5、对于长度为11的有序表，按折半查找，在查找失败时，待查找值域表中关键字比较的次数是（ ）。
a、1次或2次
b、2次或3次
c、3次或4次
d、4次或5次
6、对于长度为n的有序表，按折半查找，在等概率情况下查找成功平均时间复杂度是（ ）。
a、o(1)
b、o(㏒n)
c、o(n)
d、o(n㏒n)
7、索引顺序查找也叫分块查找，其查找过程分为是（ ）个步骤。
a、1
b、2
c、3
d、4
8、对于长度为n的关键字序列创建一颗二叉排序树，该树可能的最大高度是（ ）。
a、n
b、㏒n
c、n 1
d、n-1
9、对于关键字序列(30,25,40,35,45)，按序列次序创建一颗二叉排序树，在等概率情况下查找成功时，其平均查找长度是（ ）。
a、8
b、8/3
c、11
d、11/5
10、影响散列查找时间效率的主要因素（ ）。
a、仅与散列表长相关
b、仅与散列表中实际元素个数相关
c、与散列表长和散列表中实际元素个数均相关
d、与散列表长和散列表中实际元素个数均不相关
11、一组关键字序列为(27，17，9，19，16，43，53，8，63)，用哈希函数h(key)=key mod 8和链地址法处理冲突，查找关键字43，与散列表中关键字进行了（ ）次比较。
a、3
b、4
c、5
d、6
12、设哈希表下标为0~15，哈希函数为h(key)=key mod 13，其中key为关键字，mod为取余数运算，处理冲突方法为线性探查法，对于关键字序列为(22，18，38，39，48，35，9，64，29)，建立哈希表后，关键字9的在哈希表的位置是（ ）。
a、9
b、11
c、13
d、15
13、对于关键字序列(14,26,38,54,91)，按序列次序创建一颗平衡二叉排序树，在等概率情况下查找成功时，其平均查找长度是（ ）。
a、7/5
b、9/5
c、11/5
d、13/5
14、对于关键字序列(63,72,88,68,66,38,43)，在按序列次序创建一颗平衡二叉排序树上，查找71时依次与（ ）关键字进行了比较。
a、66,72,68
b、63,72,68
c、66,43,38
d、63,38,43
15、对包含n个元素的散列表进行检索，平均查找长度为（ ）。
a、o(log n)
b、o(n)
c、o(n log n)
d、不直接依赖于n
16、折半查找有序表(5,15,25,35,40,65,70,75,80,85,88,90)，若查找元素75，与表中元素进行了（ ）次比较。
a、4
b、3
c、2
d、1
17、折半查找一个长度为56的有序表,若查找不成功,最少需要比较（ ）次关键字。
a、4
b、5
c、6
d、7
18、假设哈希函数h(k)=k mod 29，那么（ ）为7的同义词。
a、16
b、26
c、36
d、46
19、在下列查找算法中，（ ）属于动态表上的查找法。
a、顺序查找
b、折半查找
c、斐波那契查找
d、哈希查找
20、在二叉排序树查找中，创建平衡二叉排序的目的是提高（ ）。
a、查找时间效率
b、存储效率
c、查找时间效率和存储效率
d、插入和删除数据效率
21、高度为3的平衡二叉排序树的形态共有（ ）种。
a、13
b、14
c、15
d、16
22、在下列查找算法中，（ ）算法要求关键字序列是有序的。
a、顺序查找
b、折半查找
c、分块查找
d、二叉树查找
23、假设查找表长为n，对于分块查找，如过采用顺序查找确定待查值可能所在的块，那么每块的关键字个数为（ ）时，分块查找的平均查找长度可以达到最佳。
a、
b、
c、
d、
24、对于表长为n的查找表，如果采用顺序查找，查找失败时的平均查找长度是（ ）。
a、n/2
b、(n 1)/2
c、n-1
d、n
25、若根据查找表建立长度为m的哈希表，采用线性探测法处理冲突，假定对一个元素第一次计算的哈希地址为d，则下一次的哈希地址为（ ）。
a、d
b、d 1
c、(d 1)/m
d、(d 1)%m
26、对长度为n的顺序表做查找运算，在等概率条件下，查找成功的asl为n/2。
27、如果含有n个记录的hash表中没有同义词，则查找成功的asl为1。
28、高度为4的平衡二叉树至少有4个结点。
29、分块查找要求关键字序列一定是有序的。
30、对于二叉排序树，中序遍历的关键字序列一定是有序。
31、对于任何应用情况，如果采用哈希查找法，那么就无法避免冲突情况的发生。
32、分块查找需要额外的辅助存储空间。
33、含有n个关键字的二叉排序树，其高度可以达到n。
34、如果一颗二叉树的左右子树高度差的绝对值不大于2，则该二叉树是一颗平衡二叉树。
35、如果关键字序列是有序的，则可以提高顺序查找的效率。
36、在有序的单链表上不适合折半查找。
37、对于相同的关键字集，如果不同的初始序列，那么创建的二叉排序树也不相同。
38、假定有k个关键字互为同义词，若线性再散列处理冲突，查找这些同义词其中的任意一个关键字，那么比较次数不会超过k次。
39、二分查找过程所对应的判定树是一棵平衡的二叉排序树。
40、对于相同的关键字集，如果不同的初始序列，那么创建的平衡二叉排序树是相同的。
41、在二叉排序树中插入一个新结点，总是作为叶子结点插入。
42、当采用分快查找时，数据的组织方式为数据分成若干块，每块（除最后一块外）中数据个数需相同。
43、二叉排序树查找法能适应查找表中数据的动态变化的要求。
44、用线性探测法解决突出时，同义词在散列表中是相邻的。
45、一颗完全二叉树也是一颗平衡二叉树。
46、对于散列表进行检索，其平均查找长度取决于表中填入的记录数与哈希表长之比。
47、含有12个结点的平衡二叉树，其高度至多为5。
48、在hash表中进行查找运算，根据hash函数就能确定要查找的元素位置，不需要进行关键字的比较。
49、如果二叉树的中序遍历序列是递增有序的，那么该二叉树一定也是二叉排序树。
50、基于“比较”运算的查找算法，其时间复杂度的下界为o(㏒n)。
第十章 内部排序
第十章内部排序单元测试
1、对关键字序列（21,19,37,5,2），经直接插入排序法由小到大排序，第一趟后所得结果为（ ）。
a、(19，21，37，5，2)
b、(19，21，5，2，37)
c、(19，21，5，37，2)
d、(19，21，2，5，37)
2、对关键字序列（21,19,37,5,2），经冒泡排序法由小到大排序，第一趟后所得结果为（ ）。
a、(19，21，37，5，2)
b、(19，21，5，2，37)
c、(19，21，5，37，2)
d、(19，21，2，5，37)
3、对关键字序列（149,138,165,197,176,113,127），采用基数排序的第一趟之后所得结果为（ ）。
a、(149，138，165，197，176，113，127)
b、(113，165，176，197，127，138，149)
c、(113，165，176，127，197，138，149)
d、(113，127，138，149，165，176，197)
4、下列各项键值（ ）序列不是堆的。
a、(5，23，16，68，94)
b、(5，16，23，68，94)
c、(5，23，16，94，68)
d、(5，23，68，16，94)
5、假设一组待排序的关键字序列为（24,62,36,19），要求从小到大进行排序，（ ）是归并排序的过程。
a、(24，62，19，36) (19，24，36，62)
b、(62，24，36，19) (19，24，36，62)
c、(24，62，36，19) (24，36，62，19) (19，24，36，62)
d、(24，19，36，62) (24，19，36，62) (19，24，36，62)
6、在第一趟排序之后，不能确保将数据表中某一个元素放在其最终位置上的排序算法是（ ）。
a、冒泡排序
b、选择排序
c、快速排序
d、归并排序
7、对于下列排序，（ ）的时间效率与关键字初始序列有直接关系。
a、直接插入排序
b、冒泡排序
c、归并排序
d、基数排序
8、对于下列排序，（ ）的最坏时间复杂度是o(n㏒n)。
a、直接插入排序
b、直接选择排序
c、归并排序
d、冒泡排序
9、假设两个有序表长度分别为n和m，将其归并成一个有序表最少需要（ ）次关键字之间的比较。
a、n
b、m
c、min{n,m}
d、max{n,m}
10、对于下列排序，（ ）需要额外辅助存储空间达到o(n)。
a、直接插入排序
b、直接选择排序
c、归并排序
d、冒泡排序
11、.对于关键字序列(49,38,65,97,76,13,27,49)，完成创建的大根堆是（ ）。
a、(97,76,65,49,49,38,27,13)
b、(13,27,38,49,49,65,76,97)
c、(97,65,76,49,49,13,27,38)
d、(97,76,65,49,49,13,27,38)
12、对关键字序列（30，26，18，16，5，66），进行2遍（ ）排序后得到序列（5，16，18，26，30，66）。
a、选择
b、冒泡
c、插入
d、归并
13、在下列排序算法中，（ ）排序算法可能出现如下情况：在最后一趟排序之前，所有元素均不在其最终的位置上。
a、堆
b、快速
c、冒泡
d、插入
14、在下列排序方法中，（ ）排序方法的平均时间复杂度不是o（）.
a、直接选择
b、快速
c、直接插入
d、冒泡
15、假设两个有序表长度分别为n和m，将其归并成一个有序表最多需要（ ）次关键字之间的比较。
a、n m-2
b、n m-1
c、n m
d、n m 1
16、下列排序算法中，（ ）排序算法是稳定的。
a、冒泡
b、希尔
c、快速
d、堆
17、假设待排序的表长为n，那么下列排序算法中，（ ）排序算法需要o(n)的辅助空间。
a、简单选择
b、插入
c、冒泡
d、归并
18、假设待排序的表长为n，那么快速排序算法需要（ ）的辅助空间。
a、o(1)
b、o(㏒n)
c、o(n)
d、o(n㏒n)
19、在下列排序算法中，（ ）排序算法可以避免在排序过程中移动数据元素。
a、折半插入
b、表插入
c、2-路插入
d、希尔
20、假设待排序的表长为n，那么创建堆需要时间复杂度为（ ）。
a、o(1)
b、o(㏒n)
c、o(n)
d、o(n㏒n)
21、在下列排序算法中，在待排序序列为有序的情况下，（ ）的时间复杂度是o()，其中n为待排序序列的数据元素个数。
a、简单插入排序
b、堆排序
c、快速排序
d、归并排序
22、下列四种排序中，（ ）的辅助空间复杂度是最高的。
a、堆排序
b、快速排序
c、简单选择排序
d、直接插入排序
23、设哈希表为ht[0..16]，哈希函数h(key)=key，采用线性探测开放地址法处理冲突，且ht中已有关键字为11、28、47和18这4个数据元素，现插入关键字为24的数据元素，其实际存储的地址是（ ）。
a、3
b、6
c、9
d、12
24、对顺序表中的n个记录进行直接插入排序，在最好情况下需要比较（ ）次关键字。
a、n-1
b、n
c、n 1
d、n(n-1)
25、排序算法的稳定性是指（ ）。
a、经过排序后，能使原来关键字值相同的数据保持原有顺序中的相对位置不变
b、经过排序后，能使原来关键字值相同的数据保持原有顺序中的绝对位置不变
c、排序算法的性能和被排序的数据数量关系不大
d、排序算法的性能和被排序的数据数量关系密切
26、简单插入排序算法是不稳定的。
27、待排序记录关键字出现有序的初始排列时，快速排序的时间复杂性达到最坏情况。
28、相对于简单插入排序而言，半插入排序减少了关键字比较和移动的次数。
29、对顺序表中的n个记录进行直接插入排序，在初始关键字序列为逆序的情况下，需要关键字比较的次数最少。
30、对顺序表中的n个记录进行简单选择排序，至多需要关键字交换n-1次。
31、堆排序是一种选择排序。
32、对长度为8的表，作2路归并排序，关键字之间最多需要21次比较。
33、快速排序方法的每一趟都能将一个元素把它放到最终的位置上。
34、因为堆排序的算法时间复杂度为o(n㏒n)，冒泡排序的算法复杂度为o(n2 )，所以堆排序一定比冒泡排序的速度快。
35、对有n个记录的表作直接插入排序，在最坏的情况下，需比较关键字（不含与哨兵的比较）的次数为n(n-1)/2。
36、在快速排序、堆排序和归并排序中，快速排序需要的辅助空间最多。
37、如果冒泡排序的某趟过程中没有出现数据交换情况，那么说明关键字序列已经有序。
38、排序的稳定性是指排序算法中的比较次数保持不变，且算法能够终止。
39、在初始数据表已经有序时，快速排序算法的时间复杂度为o(n㏒n )。
40、如果关键字序列是堆，则关键字序列对应的二叉树是一棵二叉排序树。
41、在用堆排序算法排序时，如果要进行增序排序，则需要采用“大根堆”。
42、在任何情况下，归并排序都比简单插入排序快。
43、排序要求数据一定要以顺序方式存储。
44、直接选择排序的比较次数与关键字序列的初始状态无关。
45、因为接插入排序是稳定的，而shell 排序是调用若干趟直接插入排序，所以也是稳定的。
46、以中序方式遍历一个堆序列对应的二叉树，则得到一个有序序列。
47、二路归并排序的核心操作是把两个有序序列合并为一个有序序列。
48、如果关键字序列采用单链表存储，那么基数排序过程可以避免大量数据移动。
49、基数排序是一种基于最高位优先(msd)的多关键字排序法。
50、基于“比较”运算的排序算法，其时间复杂度的下界为o(n㏒n)。
猜你喜欢
- 2023-10-23 00:01
- 2023-10-22 23:48
- 2023-10-22 23:47
- 2023-10-22 23:33
- 2023-10-22 22:49
- 2023-10-22 22:48
- 2023-10-22 22:17
- 2023-10-22 21:59
- 2023-10-22 21:43
- 2023-10-22 21:23