网站首页继续教育习题 正文

1.8单元测试

1、【单选题】根据数据元素之间关系的不同特性,以下解释错误的是( )
    A、集合中任何两个结点之间都有逻辑关系但组织形式松散
    B、线性结构中结点形成1对1的关系
    C、树形结构具有分支、层次特性,其形态有点像自然界中的树
    D、图状结构中的各个结点按逻辑关系互相缠绕,任何两个结点都可以邻接

2、【单选题】关于逻辑结构,以下说法错误的是( )。
    A、逻辑结构是独立于计算机的
    B、运算的定义与逻辑结构无关
    C、同一逻辑结构可以采用不同的存储结构
    D、一些表面上很不相同的数据可以有相同的逻辑结构
    E、逻辑结构是数据组织的某种"本质性"的东西

3、【单选题】下面关于算法说法正确的是( )。
    A、计算机程序一定是算法
    B、算法只能用计算机高级语言来描述
    C、算法的可行性是指指令不能有二义性
    D、以上几个都是错误的

4、【单选题】程序段 for(i=n-1;i>=0;i--) for(j=1;j<=n;j++) if A[j]>A[j+1] A[j]与A[j+1]对换; 其中n为正整数,则最后一行的语句频度在最坏情况下是( )。
    A、O(n)
    B、O(n2)
    C、O(n3)
    D、O(nlog2n)

5、【单选题】下面关于算法的说法正确的是( )。
    A、算法的时间效率取决于算法所花费的CPU时间
    B、B. 在算法设计中不能用牺牲空间代价来换取好的时间效率
    C、C. 算法必须具有有穷性、确定性等五个特性
    D、D. 通常用时空效率来衡量算法的优劣

6、【判断题】数据的逻辑结构是指数据的各数据项之间的逻辑关系。

7、【判断题】数据元素是数据的最小单位。

8、【判断题】程序一定是算法。

9、【判断题】数据的物理结构是指数据在计算机内的实际存储形式。

10、【判断题】数据结构的抽象操作的定义与具体实现有关。

2.7单元测试

1、【单选题】1.线性表是( )。
    A、一个有限序列,可以为空
    B、一个有限序列,不能为空
    C、一个无限序列,可以为空
    D、一个无序序列,不能为空

2、【单选题】2. 从一个具有n个结点的单链表中查找值为x的结点,在查找成功情况下,需平均比较( )个结点。
    A、n
    B、n/2
    C、(n-1)/2
    D、(n+1)/2

3、【单选题】3.线性表采用链式存储时,其各元素存储地址( )。
    A、必须是连续的
    B、部分地址必须是连续的
    C、一定是不连续的
    D、连续与否均可以

4、【单选题】4.用链表表示线性表的优点是( )。
    A、便于随机存取
    B、花费的存储空间较顺序存储少
    C、便于插入和删除
    D、数据元素的物理顺序与逻辑顺序相同

5、【单选题】删除速度快,但不能随机存取。
    A、链接表
    B、顺序表
    C、顺序有序表
    D、上述三项无法比较

6、【单选题】6.若希望从链表中快速确定一个结点的前驱,则链表最好采用( )方式。
    A、单链表
    B、循环单链表
    C、双向链表
    D、任意

7、【单选题】7.下面关于线性表的叙述错误的是( )。
    A、线性表采用顺序存储,必须占用一片地址连续的单元
    B、线性表采用顺序存储,便于进行插入和删除操作
    C、线性表采用链式存储,不必占用一片地址连续的单元
    D、线性表采用链式存储,便于进行插入和删除操作

8、【单选题】10.在循环双链表的p所指结点之后插入s所指结点的操作是( )。
    A、p->next=s; s->prior=p; p->next->prior=s; s->next=p->next;
    B、p->next=s; p->next->prior=s; s->prior=p; s->next=p->next;
    C、s->prior=p; s->next=p->next; p->next=s; p->next->prior=s;
    D、s->prior=p; s->next=p->next; p->next->prior=s; p->next =s;

9、【单选题】9.若某线性表中最常用的操作是在最后一个元素之后插入一个元素和删除第一个元素,则采用( )存储方式最节省运算时间。
    A、单链表
    B、仅有头指针的单循环链表
    C、双链表
    D、仅有尾指针的单循环链表

10、【单选题】8.带头结点的单链表head为空的判定条件是( )。
    A、head==NULL
    B、head->next==NULL
    C、head->next==head
    D、head!=NULL

11、【判断题】1.链表中的头结点仅起到标识的作用。

12、【判断题】2.顺序存储的线性表可以按序号随机存取。

13、【判断题】3.线性表采用链表存储时,存储空间可以是不连续的。

14、【判断题】4.静态链表中地址相邻的元素具有前驱后继关系。

15、【判断题】5.对任何数据结构,链式存储结构一定优于顺序存储结构。

16、【判断题】7.循环链表可以在尾部设置头指针。

17、【判断题】6.在线性表的顺序存储结构中,逻辑上相邻的两个元素在物理位置上并不一定紧邻。

18、【判断题】8.为了方便插入和删除,可以使用双向链表存放数据。

19、【判断题】10.取线性表的第i个元素的时间同i的大小有关。

20、【判断题】9.在单链表中,要取得某个元素,只要知道该元素的指针即可,因此,单链表是随机存取的存储结构。

3.7单元测试

1、【单选题】1. 栈和队列的共同点是( )。
    A、都是先进先出
    B、都是先进后出
    C、只允许在端点处插入和删除元素
    D、没有共同点

2、【单选题】2. 若一个栈的输入序列为1,2,3,…,n,输出序列的第一个元素是n,则第i个输出元素是( )。
    A、n-i-1
    B、n-i
    C、n-i+1
    D、不确定

3、【单选题】3. 设abcdef以所给的次序进栈,若在进栈操作时,允许出栈操作,则下面得不到的序列为( )。
    A、fedcba
    B、bcafed
    C、dcefba
    D、cabdef

4、【单选题】4. 递归过程或函数调用时,处理参数及返回地址,要用一种称为( )的数据结构。
    A、队列
    B、多维数组
    C、栈
    D、线性表

5、【单选题】5. 若一个栈以向量V[1..n]存储,初始栈顶指针top为n+1,则下面x入栈的正确操作是( )。
    A、top=top+1; V[top]=x
    B、V[top]=x; top=top+1
    C、top=top-1; V[top]=x
    D、V[top]=x; top=top-1

6、【单选题】6. 用链式存储的队列,在进行删除运算时( )。
    A、仅修改头指针
    B、仅修改尾指针
    C、头、尾指针都要修改
    D、头、尾指针可能都要修改

7、【单选题】7. 栈应用在( )。
    A、递归调用
    B、子程序调用
    C、表达式求值
    D、A,B,C

8、【单选题】8.一个递归算法必须包括( )。
    A、递归部分
    B、终止条件和递归部分
    C、迭代部分
    D、终止条件和迭代部分

9、【单选题】9.假设以数组A[m]存放循环队列的元素,其头尾指针分别为front和rear,则当前队列中的元素个数为( )。
    A、(rear-front+m)%m
    B、rear-front+1
    C、(front-rear+m)%m
    D、(rear-front)%m

10、【单选题】10. 循环队列存储在数组A[0..m]中,则入队时队尾的操作为( )。
    A、rear=rear+1
    B、rear=(rear+1)%(m-1)
    C、rear=(rear+1) % m
    D、rear=(rear+1)%(m+1)

11、【判断题】1. 消除递归一定需要使用栈。

12、【判断题】2. 栈是实现过程和函数调用所必需的结构。

13、【判断题】3. 两个栈共享一片连续内存空间时,为提高内存利用率,减少溢出机会,应把两个栈的栈底分别设在这片内存空间的两端。

14、【判断题】4. 用递归方法设计的算法效率高。

15、【判断题】5. 栈与队列是一种特殊的线性表。

16、【判断题】6. 队列逻辑上是一端既能增加又能减少的线性表。

17、【判断题】7. 循环队列通常浪费一个存储空间。

18、【判断题】8. 循环队列也存在空间溢出问题。

19、【判断题】9. 栈和队列的存储方式,既可以是顺序方式,又可以是链式方式。

20、【判断题】10. 任何一个递归过程都可以转换成非递归过程。

4.4单元测试

1、【单选题】1.如下陈述中正确的是( )。
    A、串是一种特殊的线性表
    B、串的长度必须大于零
    C、串中元素只能是字母
    D、空串就是空白串

2、【单选题】2.设有两个串p和q,其中q是p的子串,求q在p中首次出现的位置的算法称为( )。
    A、求子串
    B、联接
    C、匹配
    D、求串长

3、【单选题】3.串"ababaaababaa"的next数组为( )。
    A、012345678999
    B、012121111212
    C、011234223456
    D、012301232234

4、【单选题】4.串是( )。
    A、不少于一个字母的序列
    B、任意个字母的序列
    C、不少于一个字符的序列
    D、有限个字符的序列

5、【单选题】串的长度是指( )。
    A、串中所含不同字母的个数
    B、串中所含字符的个数
    C、串中所含不同字符的个数
    D、串中所含非空格字符的个数

6、【单选题】10.若串S="English",其子串的个数是( )。
    A、9
    B、16
    C、36
    D、28

7、【单选题】9.设S为一个长度为n的字符串,其中的字符各不相同,则S中的互异的非平凡子串(非空且不同于S本身)的个数为( )。
    A、2n-1
    B、n2
    C、(n2/2)+(n/2)
    D、(n2/2)+(n/2)-1

8、【单选题】8.若串S1="ABCDEFG", S2="9898" ,S3="###",S4="012345",执行StrConcat(StrRep(S1,SubStr(S1,StrLength(S2),StrLength(S3)),S3),SubStr(S4,StrIndex(S2, "8"),StrLength(S2)))其结果为( )。
    A、"ABC###G0123"
    B、"ABCD###2345"
    C、"ABC###G2345"
    D、"ABC###G1234"

9、【单选题】6.若s="1234ab567abcdab0",t="ab",r=""(空串),串替换StrRep(s,t,r)的结果是( )。
    A、"1234ab567abcdab0"
    B、"1234ab567abcd "
    C、"1234567cd0"
    D、"1234 567 cd 0"

10、【单选题】7.从顺序串中删除一个字符的时间复杂度为( )。
    A、O(1)
    B、O(n)
    C、O(1og2n)
    D、O(nlog2n)

11、【判断题】1.KMP算法的特点是在模式匹配时指示主串的指针不会变小。

12、【判断题】2.只要串采用定长顺序存储,串的长度就可立即获得,不需要用函数求。

13、【判断题】3.next函数值序列的产生仅与模式串有关。

14、【判断题】4.空格串就是由零个字符组成的字符序列。

15、【判断题】5.从串中取若干个字符组成的字符序列称为串的子串。

16、【判断题】6.串名的存储映象就是按串名访问串值的一种方法。

17、【判断题】7.两个串含有相等的字符,它们一定相等。

18、【判断题】8.在插入和删除操作中,链式串一定比顺序串方便。

19、【判断题】9.串的存储密度与结点大小无关。

20、【判断题】10.用堆结构存储串必须建立索引表。

5.5单元测试

1、【单选题】1.数组A[0..5,0..6]的每个元素占五个字节,将其按列优先次序存储在起始地址为1000的内存单元中,则元素A[5,5]的地址是( )。
    A、1175
    B、1180
    C、1205
    D、1210

2、【单选题】2. 若对n阶对称矩阵A以行序为主序方式将其下三角形的元素(包括主对角线上所有元素)依次存放于一维数组B[1..(n(n+1))/2]中,a00存放于数组B[1]中,则在B中确定aij(i
    A、i*(i+1)/2+j
    B、j*(j+1)/2+i
    C、i*(i+1)/2+j+1
    D、j*(j+1)/2+i+1

3、【单选题】8.已知广义表: A=(a,b), B=(A,A), C=(a,(b,A),B), 求下列运算的结果: GetTail (GetHead (GetTail (C))) =( )。
    A、(a)
    B、A
    C、a
    D、(b)
    E、b
    F、(A)

4、【单选题】7.已知广义表LS=((a,b,c),(d,e,f)),运用GetHead和GetTail函数取出LS中原子e的运算是( )。
    A、GetHead (GetTail (LS))
    B、GetHead (GetTail (GetHead (GetTail (LS))))
    C、GetTail (GetHead (LS))
    D、GetHead (GetTail (GetTail (GetHead (LS))))

5、【单选题】4.对矩阵压缩存储是为了( )。
    A、方便压缩
    B、节省空间
    C、方便存储
    D、提高运算速度

6、【单选题】3.设二维数组A[1.. m,1.. n](即m行n列)按行存储在数组B[1.. m*n]中,则二维数组元素A[i,j]在一维数组B中的下标为( )。
    A、(i-1)*n+j
    B、(i-1)*n+j-1
    C、i*(j-1)
    D、j*m+i-1

7、【单选题】5.设广义表L=((a,b,c)),则L的长度和深度分别为( )。
    A、1和1
    B、1和3
    C、1和2
    D、2和3

8、【单选题】6.有一个100*90的稀疏矩阵,非0元素有10个,设每个整型数占2字节,则用三元组表示该矩阵时,所需的字节数是( )。
    A、60
    B、66
    C、18000
    D、33

9、【判断题】1.数组是一种复杂的数据结构,数组元素之间的关系既不是线性的,也不是树形的。

10、【判断题】2.二维以上的数组其实是一种特殊的广义表。

11、【判断题】3.稀疏矩阵压缩存储后,必会失去随机存取功能。

12、【判断题】4.一个稀疏矩阵Am*n采用三元组形式表示,若把三元组中有关行下标与列下标的值互换,并把m和n的值互换,则就完成了Am*n的转置运算。

13、【判断题】5.线性表可以看成是广义表的特例,如果广义表中的每个元素都是原子,则广义表便成为线性表。

14、【判断题】6.一个广义表可以为其它广义表所共享。

15、【判断题】7.广义表中原子个数即为广义表的长度。

16、【判断题】8.所谓取广义表的表尾就是返回广义表中最后一个元素。

17、【判断题】9.广义表是由零或多个原子或子表所组成的有限序列,所以广义表可能为空表。

18、【判断题】10.任何一个非空广义表,其表头可能是单个元素或广义表,其表尾必定是广义表。

6.13单元测试

1、【单选题】1. 如果T2是由树T转换而来的二叉树,那么对T中结点的后序遍历就是对T2中结点的( )遍历。
    A、先序
    B、中序
    C、后序
    D、层次序

2、【单选题】2. 设树T的度为4,其中度为1,2,3和4的结点个数分别为4,2,1,1 则T中的叶子数为( )。
    A、5
    B、6
    C、7
    D、8

3、【单选题】3. 由4个结点可以构造出多少种不同的二叉树?( )
    A、10
    B、12
    C、14
    D、16

4、【单选题】4. 二叉树在线索后,仍不能有效求解的问题是( )。
    A、先序线索二叉树中求先序后继
    B、中序线索二叉树中求中序后继
    C、中序线索二叉树中求中序前驱
    D、后序线索二叉树中求后序后继

5、【单选题】5. 一棵二叉树具有10个度为2的结点,5个度为1的结点,则度为0的结点个数是( )。
    A、9
    B、11
    C、15
    D、不确定

6、【单选题】6. 设高度为h的二叉树上只有度为0和度为2的结点,则此类二叉树中所包含的结点数至少为( )个。
    A、2h
    B、2h-1
    C、2h+1
    D、h+1

7、【单选题】7. 设给定权值的叶子总数有n 个,其哈夫曼树的结点总数为( )。
    A、不确定
    B、2n
    C、2n+1
    D、2n-1

8、【单选题】8. 某二叉树的先序遍历序列和后序遍历序列正好相反,则此二叉树一定是( )。
    A、空或只有一个结点
    B、完全二叉树
    C、单支树
    D、高度等于结点数

9、【单选题】9. 在二叉树结点的先序序列,中序序列和后序序列中,所有叶子结点的先后顺序( )。
    A、都不相同
    B、完全相同
    C、先序和中序相同,而与后序不同
    D、中序和后序相同,而与先序不同

10、【单选题】10. 根据使用频率,为5个字符设计的哈夫曼编码不可能是( )。
    A、111,110,10,01,00
    B、000,001,010,011,1
    C、100,11,10,1,0
    D、001,000,01,11,10

11、【判断题】1. 哈夫曼树的结点个数不可能是偶数。

12、【判断题】2. 二叉树中序线索化后,不存在空指针域。

13、【判断题】3. 二叉树线索化后,任一结点均有指向其前驱和后继的线索。

14、【判断题】4. 哈夫曼编码是前缀编码。

15、【判断题】5. 非空的二叉树一定满足:某结点若有左孩子,则其中序前驱一定没有右孩子。

16、【判断题】6. 必须把一般树转换成二叉树后才能进行存储。

17、【判断题】7. 由先序和后序遍历序列不能唯一确定一棵二叉树。

18、【判断题】8. 一棵树中的叶子数一定等于与其对应的二叉树的叶子数。

19、【判断题】9. 一个树的叶结点,在前序遍历和后序遍历下,皆以相同的相对位置出现。

20、【判断题】10. 在哈夫曼树中,权值相同的叶结点都在同一层上。

7.9单元测试

1、【单选题】1.无向图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)},对该图进行深度优先遍历,得到的顶点序列正确的是( )。
    A、a,b,e,c,d,f
    B、a,c,f,e,b,d
    C、a,e,b,c,f,d
    D、a,e,d,f,c,b

2、【单选题】2.一个n个顶点的连通无向图,其边的个数至少为( )。
    A、n-1
    B、n
    C、n+1
    D、nlog2n

3、【单选题】3. 在图采用邻接表存储时,求最小生成树的 Prim 算法的时间复杂度为( )。
    A、O(n)
    B、O(n+e)
    C、O(n2)
    D、O(n3)

4、【单选题】4. G是一个非连通的无向图,共有28条边,则该图至少有( )个顶点。
    A、6
    B、7
    C、8
    D、9

5、【单选题】5. 图的广度优先搜索类似于树的( )遍历。
    A、先序
    B、中序
    C、后序
    D、层次

6、【单选题】10.下列关于AOE网的叙述中,不正确的是( )。
    A、关键活动不按期完成就会影响整个工程的完成时间
    B、任何一个关键活动提前完成,整个工程将会提前完成
    C、所有的关键活动提前完成,整个工程将会提前完成
    D、某些关键活动提前完成,整个工程将会提前完成

7、【单选题】9. 在有向图G的拓扑序列中,若顶点Vi在顶点Vj之前,则下列情形不可能出现的是( )。
    A、G中有弧
    B、G中有一条从Vi到Vj的路径
    C、G中没有弧
    D、G中有一条从Vj到Vi的路径

8、【多选题】7. 在一个无向图中,所有顶点的度数之和等于所有边数( )倍,在一个有向图中,所有顶点的入度之和等于所有顶点出度之和的( )倍。
    A、1/2
    B、2
    C、1
    D、4

9、【多选题】8. 下面( )方法可以判断出一个有向图是否有环(回路)。
    A、深度优先遍历
    B、拓扑排序
    C、求最短路径
    D、求关键路径

10、【多选题】6.一个有n个顶点的图,最少有( )个连通分量,最多有( )个连通分量。
    A、0
    B、1
    C、n-1
    D、n

11、【判断题】1. 当改变AOE网上某一关键路径上任一关键活动后,必将产生不同的关键路径。

12、【判断题】2. 在n个结点的无向图中,若边数大于n-1,则该图必是连通图。

13、【判断题】3. 在AOE网中,关键路径上某个活动的时间缩短,整个工程的时间也就必定缩短。

14、【判断题】4. 若一个有向图的邻接矩阵对角线以下元素均为零,则该图的拓扑有序序列必定存在。

15、【判断题】5. 一个有向图的邻接表和逆邻接表中结点的个数可能不等。

16、【判断题】6. 强连通图的各顶点间均可达。

17、【判断题】7. 带权的连通无向图的最小代价生成树是唯一的。

18、【判断题】8. 广度遍历生成树描述了从起点到各顶点的最短路径。

19、【判断题】9. 邻接多重表是无向图和有向图的链式存储结构。

20、【判断题】10.连通图上各边权值均不相同,则该图的最小生成树是唯一的。

8.7单元测试

1、【单选题】1.若查找每个记录的概率相等,则在具有n个的连续顺序文件中采用顺序查找法查找一个记录,其平均查找长度ASL为( )。
    A、(n-1)/2
    B、n/2
    C、(n+1)/2
    D、n

2、【单选题】2.具有12个关键字的有序表,折半查找的平均查找长度为( )。
    A、3.1
    B、4
    C、2.5
    D、5

3、【单选题】3.当采用分快查找时,数据的组织方式为 ( ) 。
    A、数据分成若干块,每块内数据有序
    B、数据分成若干块,每块内数据不必有序,但块间必须有序,每块内最大(或最小)的数据组成索引块
    C、数据分成若干块,每块内数据有序,每块内最大(或最小)的数据组成索引块
    D、数据分成若干块,每块(除最后一块外)中数据个数需相同

4、【单选题】4.在平衡二叉树中插入一个结点后造成了不平衡,设最低的不平衡结点为A,并已知A的左孩子的平衡因子为0,右孩子的平衡因子为1,则应作( ) 型调整以使其平衡。
    A、LL
    B、LR
    C、RL
    D、RR

5、【单选题】5.下面关于折半查找的叙述正确的是( ) 。
    A、表必须有序,表可以顺序方式存储,也可以链表方式存储
    B、表必须有序且表中数据必须是整型,实型或字符型
    C、表必须有序,而且只能从小到大排列
    D、表必须有序,且表只能以顺序方式存储

6、【单选题】6.既希望较快的查找又便于线性表动态变化的查找方法是 ( ) 。
    A、顺序查找
    B、折半查找
    C、索引顺序查找
    D、哈希法查找

7、【单选题】7.有关键字值的集合A={55,30,35,15,45,25,95},从空二叉树开始逐个插入每个关键字值,建立与集合A对应的二叉排序树,若希望得到的二叉排序树高度最小,应选择( )作为输入序列。
    A、45,25,55,15,35,95,30
    B、35,25,15,30,55,45,95
    C、15,25,30,35,45,55,95
    D、30,25,15,35,45,95,55

8、【单选题】13.哈希函数有一个共同的性质,即函数值应当以( )取其值域的每个值。
    A、最大概率
    B、最小概率
    C、平均概率
    D、同等概率

9、【单选题】12.下面关于B-树和B+树的叙述中,不正确的是( ) 。
    A、B-树和B+树都是平衡的多叉树
    B、B-树和B+树都可用于文件的索引结构
    C、B-树和B+树都能有效地支持顺序检索
    D、B-树和B+树都能有效地支持随机检索

10、【单选题】11.下列关于m阶B-树的说法错误的是( ) 。
    A、根结点至多有m棵子树
    B、所有叶子都在同一层次上
    C、非叶结点至少有m/2 (m为偶数)或m/2+1(m为奇数)棵子树
    D、根结点中的数据是有序的

11、【单选题】9.具有5层结点的AVL树至少有( )个结点。
    A、10
    B、12
    C、15
    D、17

12、【单选题】8.分别以下列序列构造二叉排序树,与用其它三个序列所构造的结果不同的是( ) 。
    A、(100,80,90,60,120,110,130)
    B、(100,120,110,130,80,60,90)
    C、(100,60,80,90,120,110,130)
    D、(100,80,60,90,120,130,110)

13、【单选题】10.在一棵平衡二叉树中,每个结点的平衡因子取值范围是( )。
    A、-1~1
    B、-2~2
    C、1~2
    D、0~1

14、【单选题】16.将10个元素哈希到100000个单元的哈希表中,则( )产生冲突。
    A、一定会
    B、一定不会
    C、仍可能会

15、【单选题】15.下面关于哈希查找的说法正确的是( ) 。
    A、哈希函数构造的越复杂越好,因为这样随机性好,冲突小
    B、除留余数法是所有哈希函数中最好的
    C、不存在特别好与坏的哈希函数,要视情况而定
    D、若需在哈希表中删去一个元素,不管用何种方法解决冲突都只要简单的将该元素删去即可

16、【单选题】14.假定有k个关键字互为同义词,若用线性探测法把这k个关键字存入哈希表中,至少要进行多少次探测?( )
    A、k-1次
    B、k次
    C、k+1次
    D、k(k+1)/2次

17、【判断题】1.折半查找法的查找速度一定比顺序查找快。

18、【判断题】2.就平均查找长度而言,分块查找最小,折半查找次之,顺序查找最大。

19、【判断题】3.对一棵二叉排序树按先序遍历得出的结点序列是从小到大的序列。

20、【判断题】5.将线性表中的信息组织成平衡二叉树,其优点之一是无论线性表中数据如何排列总能保证平均查找长度均为log2n量级(n为线性表中的结点数目)。

21、【判断题】4.哈希查找不需要任何比较。

22、【判断题】6.在平衡二叉树中,向某个平衡因子不为零的结点的树中插入一新结点,必引起平衡旋转。

23、【判断题】7.有序的线性表无论如何存储,都能采用折半查找。

24、【判断题】8.B+树既能索引查找也能顺序查找。

25、【判断题】9.Hash表的平均查找长度与处理冲突的方法无关。

26、【判断题】10.装填因子是哈希表的一个重要参数,它反映了哈希表的装满程度。

9.8单元测试

1、【单选题】1. 下列排序算法中,其中( )是稳定的。
    A、堆排序,冒泡排序
    B、快速排序,堆排序
    C、简单选择排序,归并排序
    D、归并排序,冒泡排序

2、【单选题】2. 对n个元素进行快速排序,如果初始数据已经有序,则时间复杂度为( )。
    A、O(1)
    B、O(n)
    C、O(n2)
    D、O(log2n)

3、【单选题】3. 以下时间复杂度不是O(nlog2n)的排序方法是( )。
    A、堆排序
    B、直接插入排序
    C、二路归并排序
    D、快速排序

4、【单选题】4. 若需在O(nlog2n)的时间内完成对数组的排序,且要求排序是稳定的,则可选择的排序方法是( )。
    A、快速排序
    B、堆排序
    C、直接插入排序
    D、归并排序

5、【单选题】5. 一组记录的关键字为{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}

6、【单选题】6. 一组记录的关键字为{45,80,55,40,42,85},则利用堆排序方法建立的初始大根堆为( )。
    A、{80,45,50,40,42,85}
    B、{85,80,55,40,42,45}
    C、{85,80,55,45,42,40}
    D、{85,55,80,42,45,40}

7、【单选题】7. 在待排序的元素序列基本有序的前提下,效率最高的排序方法是( )。
    A、直接插入排序
    B、快速排序
    C、简单选择排序
    D、归并排序

8、【单选题】10. 设有字符序列{Q,H,C,Y,P,A,M,S,R,D,F,X},新序列{D,H,C,F,P,A,M,Q,R,S,Y,X}是下列( )排序算法一趟排序的结果。
    A、冒泡排序
    B、初始步长为4的Shell排序
    C、二路归并排序
    D、快速排序

9、【单选题】9. 一个序列有10000个元素,若只想得到其中前10个最小元素,最好采用( )方法。
    A、二路归并排序
    B、直接选择排序
    C、Shell排序
    D、堆排序

10、【单选题】快速排序、归并排序的关系是( )。
    A、堆排序
    B、堆排序
    C、堆排序>归并排序>快速排序
    D、堆排序>快速排序>归并排序

11、【判断题】1.快速排序在所有排序方法中最快,而且所需附加空间也最少。

12、【判断题】2.在大根堆中,最大元素在根的位置,最小元素在某个叶结点处。

13、【判断题】3.排序算法中的比较次数与初始元素序列的排列无关。

14、【判断题】4.用Shell 方法排序时,若关键字的初始排序越杂乱无序,则排序效率就越低。

15、【判断题】5.对n个记录进行堆排序,在最坏情况下的时间复杂度是O(n2)。

16、【判断题】6.在任何情况下,快速排序方法的时间性能总是最优的。

17、【判断题】7.堆是满二叉树。

18、【判断题】8.快速排序和归并排序在最坏情况下的比较次数都是O(nlog2n)。

19、【判断题】10.简单选择排序算法的时间复杂性不受数据的初始状态影响,为O(n2)。

20、【判断题】9.只有在初始数据表为逆序时,直接插入排序所执行的比较次数最多。

10.5单元测试

1、【单选题】下列关于算法的说法,正确的是( )。
    A、程序一定是算法。
    B、算法的可行性是指指令不能有二义性。
    C、算法可以没有输入但必须有1个以上的输出。
    D、算法必须是用计算机语言描述的。

2、【单选题】循环队列存储在数组A[0..m]中,则入队时的操作为( )。
    A、rear=rear+1
    B、rear=(rear+1) mod (m-1)
    C、rear=(rear+1)mod m
    D、rear=(rear+1)mod(m+1)

3、【单选题】表达式a*(b+c)-d的后缀表达式是( )。
    A、abcd*+-
    B、abc+*d-
    C、abc*+d-
    D、-+*abcd

4、【单选题】设n阶方阵A是一对称矩阵,为节省存储空间,将其下三角(包括对角线)以行序为主序存储在一维数组B(1: n(n+1)/2)中,则对任一上三角元素aij(i<j,1≤i≤n,1≤j≤n),其在一维数组B中的下标位置k是( )。
    A、i(i-1)/2+j
    B、j(j-1)/2+i
    C、i(j-1)/2+1
    D、j(i-1)/2+1

5、【单选题】在一个不带头结点单链表H中,若要向表头插入一个由指针p指向的结点,则执行( )。
    A、H=p; p->next=H;
    B、p->next=H; H=p;
    C、p->next=H; p=H;
    D、p->next=H->next; H->next=p;

6、【判断题】顺序存储方式插入和删除时效率太低,因此它不如链式存储方式好。

7、【判断题】抽象数据类型(ADT)包括定义和实现两方面,其中定义是独立于实现的,定义仅给出一个ADT的逻辑特性,不必考虑如何在计算机中实现。

8、【判断题】在决定选取何种存储结构时,一般不考虑各结点的值如何。

9、【判断题】对任何数据结构链式存储结构一定优于顺序存储结构。

10、【判断题】循环链表不是线性表。