和鲸社区2022咸鱼打挺夏令营-数据结构·闯关-作业答案

第一关 - 线性表

题目

第 1 题

• 技能点：线性表的顺序和链式存储

下面关于线性表的叙述错误的是( )

A. 线性表采用顺序存储必须占用一片连续的存储空间

B. 线性表采用链式存储不必占用一片连续的存储空间

C. 线性表采用链式存储便于插入和删除操作的实现

D. 线性表采用顺序存储便于插入和删除操作的实现

第 2 题

• 技能点：线性表的前驱和后继

线性表L=(ai，a2,………an)，下列说法正确的是( )

A．每个元素都有一个直接前驱和一个直接后继

B. 线性表中至少有一个元素

C. 表中诸元素的排列必须是由小到大或由大到小

D. 除第一个和最后一个元素外，其余每个元素都有一个且仅有一个直接前驱和直接后继。

第 3 题

• 技能点：链式结构存储空间

链接存储的存储结构所占存储空间( )

A. 分两部分，一部分存放结点值，另一部分存放表示结点间关系的指针

B. 只有一部分，存放结点值

C. 只有一部分，存储表示结点间关系的指针

D. 分两部分，一部分存放结点值，另一部分存放结点所占单元数

第 4 题

• 技能点：链式存储结构的存储单元

线性表若采用链式存储结构时，要求内存中可用存储单元的地址( )

A. 必须是连续的

B. 部分地址必须是连续的

C. 一定是不连续的

D. 连续或不连续都可以

第 5 题

• 技能点：线性表链式存储结构

线性表L在( )情况下适用于使用链式结构实现.

A. 需经常修改L中的结点值

B. 需不断对L进行删除插入

C. L中含有大量的结点

D. L中结点结构复杂

第 6 题

• 技能点：单链表存储密度

单链表的存储密度( )

A. 大于1

B. 等于1

C. 小于1

D. 不能确定

第 7 题

• 技能点：线性表的顺序存储操作时间复杂度

在n个结点的顺序表中，算法的时间复杂度是O(1)的操作是( )

A. 访问第i个结点（1≤i≤n）和求第i个结点的直接前驱（2≤i≤n)

B. 在第i个结点后插入一个新结点（1≤i≤n)

C. 删除第i个结点（1≤i≤n)

D. 将n个结点从小到大排序

第 8 题

• 技能点：单链表时间复杂度

设一个有序的单链表中有n个结点，现要求插入一个新结点后使得单链表仍然保持有序，则该操作的时间复杂度为( )

A. O(log2n)

B. O(1)

C. O(n^2)

D. O(n)

第 9 题

• 技能点：有序单链表

若指定有n个元素的向量，则建立一个有序单链表的时间复杂性的量级是( )

A. O(1)

B. O(n)

C. O(n^2)

D. O(nlog2n)

第 10 题

• 技能点：顺序表的插入操作

向一个有127个元素的顺序表中插入一个新元素并保持原来顺序不变，平均要移动的元素个数为( )

A. 8

B. 63.5

C. 63

D. 7

In [12]:

1
answer.append('B')

第 11 题

• 技能点：顺序表的删除操作

设顺序线性表中有n个数据元素，则删除表中第i个元素需要移动( )个元素.

A. n-i

B. n+1-i

C. n-1-i

D. i

In [13]:

1
answer.append('A')

第 12 题

• 技能点：顺序表的插入操作

在一个长度为n的顺序表中，在第i个元素（1≤i≤n+1）之前插入一个新元素时须向后移动( )个元素.

A. n-i

B. n-i+1

C. n-i-1

D. i

In [14]:

1
answer.append('B')

第 13 题

• 技能点：双向循环链表的插入操作

在带头结点的双向循环链表中插入一个新结点，需要修改的指针域数量是( )

A. 2个

B. 3个

C. 4个

D. 6个

In [15]:

1
answer.append('C')

第 14 题

• 技能点：单链表的判空条件

设一条单链表的头指针变量为head且该链表没有头结点，则其判空条件是( )

A. head==0

B. head->next==0

C. head->next==head

D. head != 0

In [16]:

1
answer.append('A')

第 15 题

• 技能点：单链表的插入操作

在单链表中，要将s所指结点插入到p所指结点之后，其语句应为( )

A. s->next-p+1; p->next=s;

B. (*p).next=s; (*s).next=(*p).next;

C. s->next=p->next; p->next=s->next;

D. s->next=p->next; p->next=s;

第 16 题

• 技能点：双向链表的删除操作

在双向链表存储结构中，删除p所指的结点时须修改指针( )

A. p->next->prior = p->prior; 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;

第 17 题

• 技能点：双向链表的插入操作

在双向循环链表中，在p指针所指的结点后插入q所指向的新结点，其修改指针的操作是( )

A. p->next=q; q->prior=p; p->next->prior=q; q->next=q;

B. p->next=q; p->next->prior=q; q->prior=p; q->next=p->next;

C. q->prior=p; q->next=p->next; p->next->prior=q; p->next=q;

D. q->prior=p; q->next=p->next; p->next=q; p->next->prior=q;

第 18 题

• 技能点：散列表

设某散列表的长度为100，散列函数H(k) = k % P，则Р通常情况下最好选择( )

A. 99

B. 97

C. 91

D. 93

第 19 题

• 技能点：散列表的存储

设散列表中有m个存储单元，散列函数H(key)= key % p，则p最好选择( )

A. 小于等于m的最大奇数

B. 小于等于m的最大素数

C. 小于等于m的最大偶数

D. 小于等于m的最大合数

第 20 题

• 技能点：哈希表

设有n 个关键字具有相同的Hash函数值，则用线性探测法把这n个关键字映射到HASH表中需要做( )次线性探测.

A. n2

B. n(n+1)

C. n(n+1)/2

D. n(n-1)/2

第 21 题

• 技能点：有序表合并

将两个各有n个元素的有序表归并成一个有序表，其最少的比较次数是( )

A. n

B. 2n-1

C. 2n

D. n-1

第 22 题

• 技能点：数组顺序存储结构

设有一个10阶的下三角矩阵A(包括对角线)，按照从上到下、从左到右的顺序存储到连续的55个存储单元中,每个数组元素占1个字节的存储空间,则A[5][4]地址与A[0][0]的地址之差为( )

A. 10

B. 19

C. 28

D. 55

第 23 题

• 技能点：链表比较

设某链表中最常用的操作是在链表的尾部插入或删除元素，则选用下列( )存储方式最节省运算时间.

A. 单向链表

B. 单向循环链表

C. 双向链表

D. 双向循环链表

第 24 题

• 技能点：线性表顺序和链式存储比较

以下说法错误的是( )

A. 求表长、定位这两种运算在采用顺序存储结构时实现的效率不比采用链式存储结构时实现的效率低

B. 顺序存储的线性表可以随机存取

C. 由于顺序存储要求连续的存储区域，所以在存储管理上不够灵活

D. 线性表的链式存储结构优于顺序存储结构

第 25 题

• 技能点：线性表顺序和链式存储比较

在以下的叙述中，正确的是( ).

A. 线性表的顺序存储结构优于链表存储结构　

B. 线性表的顺序存储结构适用于频繁插入/删除数据元素的情况

C. 线性表的链表存储结构适用于频繁插入/删除数据元素的情况

D. 线性表的链表存储结构优于顺序存储结构

答案

D D A D B
C A D C B
A B C A D
A C B B C
A B D D C

a1,a5,a9,a14,a20,a23,a25

第二关 - 栈和队列

题目

第 1 题

• 技能点：递归算法

一个递归算法必须包括( )

A. 递归部分

B. 终止条件和递归部分

C. 迭代部分

D. 终止条件和迭代部分

第 2 题

• 技能点：递归算法

def fact(n):
    if(n <= 0):
        return 1
    else:
        return n*fact(n-1)

设有一个递归算法如上代码，则计算fact(n)需要调用该函数的次数为( )

A. n+1

B. n-1

C. n

D. n+2

第 3 题

• 技能点：进栈出栈

设输入序列为1、2、3、4、5、6，则通过栈的作用后可以得到的输出序列为( )

A. 5，3，4，6，1，2

B. 3，2，5，6，4，1

C. 3，1，2，5，4，6

D. 1，5，4，6，2，3

第 4 题

• 技能点：进栈出栈

若让元素1，2，3，4，5依次进栈，则出栈次序不可能出现在( )种情况.

A. 5，4，3，2，1

B. 2，1，5，4，3

C. 4，3，1，2，5

D. 2，3，5，4，1

第 5 题

• 技能点：进栈出栈

若已知一个栈的入栈序列是1，2，3，…，n，其输出序列为p1，p2，p3，…，pn，若p1=n，则pi为( )

A. i

B. n-i

C. n-i+1

D. 不确定

第 6 题

• 技能点：链栈的存储结构

设链表不带头结点且所有操作均在表头进行，则下列最不适合作为链栈的是( )

A. 只有表头结点指针，没有表尾指针的双向循环链表

B. 只有表尾结点指针，没有表头指针的双向循环链表

C. 只有表头结点指针，没有表尾指针的单向循环链表

D. 只有表尾结点指针，没有表头指针的单向循环链表

第 7 题

• 技能点：链栈的删除操作

链式栈结点为:(data,link)，top指向栈顶，若想摘除栈顶结点，并将删除结点的值保存到x中,则应执行操作( )

A. x=top->data;top=top->link;

B. top=top->link;x=top->link;

C. x=top;top=top->link;

D. X=top->link;

第 8 题

• 技能点：顺序栈

在一个具有n个单元的顺序栈中，假设以地址高端作为栈底，以top作为栈顶指针，则当作进栈处理时，top的变化为( )

A. top不变

B. top-0

C. top—

D. top++

第 9 题

• 技能点：队列的链式存储

用链接方式存储的队列，在进行插入运算时( )

A. 仅修改头指针

B. 头、尾指针都要修改

C. 仅修改尾指针

D. 头、尾指针可能都要修改

第 10 题

• 技能点：栈求表达式

利用栈求表达式的值时，设立运算数栈OPEN.假设OPEN只有两个存储单元，则在下列表达式中，不会发生溢出的是( )

A. A-B*(C-D)

B. (A-B)*C-D

C. (A-B*C)-D

D. (A-B)*(C-D)

第 11 题

• 技能点：共享栈的好处

采用共享栈的好处是( )

A. 减少存取时间，降低发生上溢的可能

B. 节省存储空间，降低发生上溢的可能

C. 减少存取时间，降低发生下溢的可能

D. 节省存储空间，降低发生下溢的可能.

第 12 题

• 技能点：链式队列的操作

设指针变量front表示链式队列的队头指针，指针变量rear表示链式队列的队尾指针指针变量s指向将要入队列的结点X，则入队列的操作序列为( )

A. front->next=s; front=s;

B. s->next=rear; rear=s;

C. rear->next=s; rear=s;

D. s->next=front; front=s;

第 13 题

• 技能点：双端队列的输入输出

若以1234作为双端队列的输入序列，则既不能由输入受限的双端队列得到，也不能由输出受限的双端队列得到的输出序列是( )

A. 1234

B. 4132

C. 4231

D. 4213

第 14 题

• 技能点：循环队列

已知循环队列的存储空间为数组A[21]，front指向队头元素的前一个位置，rear指向队尾元素，假设当前front和rear的值分别为8和3，则该队列的长度为( )

A. 5

B. 6

C. 16

D. 17

第 15 题

• 技能点：循环队列

设顺序循环队列Q[0:M-1]的头指针和尾指针分别为F和R，头指针F总是指向队头元素的前一位置，尾指针R总是指向队尾元素的当前位置，则该循环队列中的元素个数为( )

A.R-F

B.F-R

C.(F-R+M)%M

D.(R-F+M)%M

第 16 题

• 技能点：循环队列的入队操作

循环队列存储在数组A[0..m]中，则入队时的操作为( )

A. rear=rear+1

B. rear=(rear+1)%(n-1)

C. rear=(rear+1) %m

D. rear= (rear+1)%(m+1)

第 17 题

• 技能点：循环队列的删除操作

若用一个大小为6的数组来实现循环队列，且当前rear和front的值分别为0和3，当从队列中删除一个元素，再加入两个元素后，rear和front的值分别为多少？

A. 1和 5

B. 2和4

C. 4和2

D. 5和1

第 18 题

• 技能点：栈和队列的共同点

栈和队列的共同点是( )

A. 都是先进先出

B. 都是先进后出

C. 只允许在端点处插入和删除元素

D. 没有共同点

第 19 题

• 技能点：栈的应用

栈在( )中有所应用.

A．递归调用

B．函数调用

C．表达式求值

D. 前三个选项都有

第 20 题

• 技能点：线性表、栈、队列的比较

为解决计算机主机与打印机间速度不匹配问题，通常设一个打印数据缓冲区。主机将要输出的数据依次写入该缓冲区，而打印机则依次从该缓冲区中取出数据。该缓冲区的逻辑结构应该是( )

A．队列

B．栈

c．线性表

D．有序表

第 21 题

• 技能点：栈和队列

设栈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

第 22 题

• 技能点：栈和队列的应用

设计一个判别表达式中左，右括号是否配对出现的算法，采用( )数据结构最佳.

A．线性表的顺序存储结构

B．队列

C．线性表的链式存储结构

D. 栈

第 23 题

• 技能点：循环队列的判空条件

最大容量为n的循环队列，队尾指针是rear，队头是front，则队空的条件是( )

A. (rear+1)%n=front

B. rear==front

C. rear+1==front

D. (rear-l)%n==front

第 24 题

• 技能点：双向队列（注：本题为多选题）

已知输入序列为abcd经过输出受限的双向队列后能得到的输出序列有( )

A. dacb

B. cadb

C. dbca

D. bdac

E. 以上答案都不对

第 25 题

• 技能点：进栈出栈（注：本题为多选题）

依次读入数据元素序列{a，b，c，d，e，f，g}进栈,每进一个元素，机器可要求下一个元素进栈或弹栈，如此进行，则栈空时弹出的元素构成的序列是以下哪些序列？

A．{d ，e，c，f，b，g，a}

B. {f，e，g，d，a，c，b}

C. {e，f，d，g，b，c，a}

D. {c，d，b，e，f，a，g}

答案

B A B C C

C A C D B

B C C C D

D B C D A

B D B BD AD

a17,a23,a24

第三关 - 树和二叉树

第 1 题

• 技能点：树的存储形式

在下列存储形式中，（ ）不是树的存储形式?

A. 双亲表示法

B. 孩子链表表示法

C. 孩子兄弟表示法

D. 顺序存储表示法

第 2 题

• 技能点：普通树转二叉树

把一棵树转换为二叉树后，这棵二叉树的形态是（ ）

A．唯一的

B．有多种

C．有多种，但根结点都没有左孩子

D．有多种，但根结点都没有右孩子

第 3 题

• 技能点：二叉树的结点

由3个结点可以构造出多少种不同的二叉树?（ ）

A. 2

B. 3

C. 4

D. 5

第 4 题

• 技能点：完全二叉树叶子结点

一棵完全二叉树上有1001个结点，其中叶子结点的个数是（ ）

A. 250

B. 500

C. 254

D. 501

第 5 题

• 技能点：二叉树的结点与高度关系

设某棵二叉树中有2000个结点，则该二叉树的最小高度为（ ）

A. 9

B. 10

C. 11

D. 12

第 6 题

• 技能点：满叉树的结点个数

深度为h的满叉树的第k层有(A)个结点。(1=<k=<h)

A. m^(k-1)

B. m^k-1

C. m^(h-1)

D. m^h-1

第 7 题

• 技能点：二叉链表存储树

利用二叉链表存储树，则根结点的右指针是（ ）

A．指向最左孩子

B．指向最右孩子

C．空

D．非空

第 8 题

• 技能点：完全二叉树

设按照从上到下、从左到右的顺序从1开始对完全二叉树进行顺序编号，则编号为i结点的左孩子结点的编号为（ ）

A. 2i+1

B. 2i

C. i/2

D. 2i-1

第 9 题

• 技能点：二叉树的先序和后序遍历

一棵非空的二叉树的先序遍历序列与后序遍历序列正好相反，则该二叉树一定满足（ ）

A．所有的结点均无左孩子

B．所有的结点均无右孩子

C．只有一个叶子结点

D．是任意一棵二叉树

第 10 题

• 技能点：二叉树的遍历方法

对二叉树的结点从1开始进行连续编号，要求每个结点的编号大于其左、右孩子的编号，同一结点的左右孩子中，其左孩子的编号小于其右孩子的编号，可采用（ ）遍历实现编号.

A. 先序

B. 中序

C. 后序

D. 从根开始按层次遍历

第 11 题

• 技能点：二叉树的遍历方法

若二叉树采用二叉链表存储结构，要交换其所有分支结点左、右子树的位置，利用（ ）遍历方法最合适.

A. 前序

B. 中序

C. 后序

D. 按层次

第 12 题

• 技能点：二叉树的前序和后序遍历

某二叉树的前序序列和后序序列正好相反，则该二叉树一定是（ ）的二叉树.

A. 高度等于其结点数

B. 任一结点无左子树

C. 空或只有一个结点

D. 任一结点无右子树

第 13 题

• 技能点：完全二叉树深度和结点关系

深度为k的完全二叉树中最少有（ ）个结点.

A. 2^(k-1)-1

B. 2^(k-1)

C. 2^(k-1)+1

D. 2^k-1

第 14 题

• 技能点：二叉中序线索树

若X是二叉中序线索树中一个有左孩子的结点，且X不为根，则X的前驱为（ ）

A. X的双亲

B. X的右子树中最左的结点

C. X的左子树中最右结点

D. X的左子树中最右叶结点

第 15 题

• 技能点：树的度数和结点的关系

设在一棵度数为3的树中，度数为3的结点数有2个，度数为2的结点数有1个，为1的结点数有2个，那么度数为0的结点数有（ ）

A. 4

B. 5

C. 6

D. 7

第 16 题

• 技能点：二叉树的度数和结点关系

设某棵二叉树中只有度数为0和度数为2的结点且度数为0的结点数为n，则这棵二叉树中共有（ ）个结点.

A. 2n

B. 2n-1

C. 2n+1

D. n+1

第 17 题

• 技能点：二叉树遍历方法的区别

设某棵二叉树的中序遍历序列为ABCD，前序遍历序列为CABD，则后序遍历该二叉树得到序列为（ ）

A. BADC

B. BCDA

C. CDAB

D. CBDA

第 18 题

• 技能点：二叉线索树

引入二叉线索树的目的是（ ）

A．加快查找结点的前驱或后继的速度

B．为了能在二叉树中方便的进行插入与删除

C．为了能方便的找到双亲

D．使二叉树的遍历结果唯一

第 19 题

• 技能点：二叉线索树的结构

线索二叉树是一种（ ）结构.

A. 逻辑

B. 逻辑和存储

C. 物理

D. 线性

第 20 题

• 技能点：哈夫曼树的二叉链表表示

设哈夫曼树中的叶子结点总数为m，若用二叉链表作为存储结构，则该哈夫曼树中总共有（ ）个空指针域.

A. 2m-1

B. 2m

C. 2m+1

D. 4m

第 21 题

• 技能点：哈夫曼树的结点个数

设某哈夫曼树中有199个结点，则该哈夫曼树中有（ ）个叶子结点.

A. 99

B. 100

C. 101

D. 102

第 22 题

• 技能点：哈夫曼树带权路径长度

设一组权值集合W=(15，3，14，2，6，9，16，17)，要求根据这些权值集合构造一棵哈夫曼树，则这棵哈夫曼树的带权路径长度为（ ）

A. 129

B. 219

C. 189

D. 229

第 23 题

• 技能点：树和森林的转换

设F是一个森林，B是由F变换得的二叉树。若F中有n个非终端结点，则B中右指针域为空的结点有（ ）个.

A. n-1

B. n

C. n+1

D. n+2

第 24 题

• 技能点：二叉树

下面的说法中正确的是（ ）

（1）任何一棵二叉树的叶子结点在三种遍历中的相对次序不变；
（2）按二叉树定义，具有三个结点的二叉树共有6种。

A．(1)(2)

B．(1)

C．(2)

D．(1)(2)都错

第 25 题

• 技能点：线索二叉树

二叉树在线索后，仍不能有效求解的问题是（ ）

A．前（先）序线索二叉树中求前（先）序后继

B．中序线索二叉树中求中序后继

C．中序线索二叉树中求中序前驱

D．后序线索二叉树中求后序后继

答案

D A D D C

A C B C C

C A B C C

B A A C B

B D C B D

a10,a11,a13,a14,a23,a25

第四关 - 图

题目

第 1 题

• 技能点：图的顶点和边

在一个图中，所有顶点的度数之和等于图的边数的（ ）倍。

A. 1/2

B. 1

C. 2

D. 4

第 2 题

• 技能点：有向图

在一个有向图中，所有顶点的入度之和等于所有顶点的出度之和的（ ）倍。

A. 1/2

B. 1

C. 2

D. 4

第 3 题

• 技能点：有向图

具有n个顶点的有向图最多有（ ）条边。

A. n

B. n(n-1)

c. n(n+1)

D. n^2

第 4 题

• 技能点：图的邻接矩阵

n个顶点的连通图用邻接距阵表示时，该距阵至少有（ ）个非零元素。

A. n

B. 2(n-1)

C. n/2

D. n^2

第 5 题

• 技能点：无向图

G是一个非连通无向图，共有28条边，则该图至少有（ ）个顶点。

A. 7

B. 8

C. 9

D. 10

第 6 题

• 技能点：无向图、深度优先搜索

若从无向图的任意一个顶点出发进行一次深度优先搜索可以访问图中所有的顶点，则该图一定是（ ）图。

A. 非连通

B. 连通

C. 强连通

D. 有向

第 7 题

• 技能点：图的最小生成树

下面（ ）算法适合构造一个稠密图G的最小生成树。

A. Prim算法

B. Kruskal算法

C. Floyd算法

D. Dijkstra算法

第 8 题

• 技能点：图的广度优先遍历

用邻接表表示图进行广度优先遍历时，通常借助（ ）来实现算法。

A. 栈

B. 队列

C. 树

D. 图

第 9 题

• 技能点：图的深度优先遍历

用邻接表表示图进行深度优先遍历时，通常借助（ ）来实现算法。

A. 栈

B. 队列

C. 树

D. 图

第 10 题

• 技能点：图的深度优先遍历

深度优先遍历类似于二叉树的（ ）

A．先序遍历

B．中序遍历

C．后序遍历

D．层次遍历

第 11 题

• 技能点：图的广度优先遍历

广度优先遍历类似于二叉树的（ ）

A. 先序遍历

B. 中序遍历

C. 后序遍历

D. 层次遍历

第 12 题

• 技能点：图的广度优先遍历和深度优先遍历

图的BFS生成树的树高比DFS生成树的树高（ ）

A．小

B．相等

C．小或相等

D．大或相等

第 13 题

• 技能点：有向图判断是否有环

下面（ ）方法可以判断出一个有向图是否有环。

A. 深度优先遍历

B. 拓扑排序

C. 求最短路径

D. 求关键路径

第 14 题

• 技能点：完全无向图

设某完全无向图中有n个顶点，则该完全无向图中有（ ）条边。

A. n(n-1)/2

B. n(n-1)

C. n^2

D. n^2-1

第 15 题

• 技能点：无向图的邻接表

设无向图G中有n个顶点e条边，则其对应的邻接表中的表头结点和表结点的个数分别为（ ）

A. n，e

B. e，n

C. 2n，e

D. n，2e

第 16 题

• 技能点：图的深度优先遍历

设连通图G中的边集E={(a，b)，(a，e)，(a，c)，(b，e)，(e，d)，(d，f)，(f，c)}，则从顶点a出发可以得到一种深度优先遍历的顶点序列为（ ）

A. abedfc

B. acfebd

C. aebdfc

D. aedfcb

第 17 题

• 技能点：稀疏无向图的表示方法

下面结构中最适于表示稀疏无向图的是（ ）

A．邻接矩阵

B．逆邻接表

C．邻接多重表

D．十字链表

第 18 题

• 技能点：有向图顶点度数

在一个具有n个顶点的有向图中，若所有顶点的出度数之和为s，则所有有顶点的度数之和为（ ）

A. s

B. s-1

C. s+1

D. 2s

第 19 题

• 技能点：无向图的邻接表

设某无向图中有n个顶点e条边，则建立该图邻接表的时间复杂度为（ ）

A. O(n+e)

B. O(n^2)

C. O(ne)

D. O(n^3)

第 20 题

• 技能点：有向图的邻接矩阵

设用邻接矩阵A表示有向图G的存储结构，则有向图G中顶点i的入度为（ ）

A. 第i行非0元素的个数之和

B. 第i列非0元素的个数之和

C. 第i行0元素的个数之和

D. 第i列0元素的个数之和

第 21 题

• 技能点：图中的路径定义

图中有关路径的定义是（ ）

A. 由顶点和相邻顶点对构成的边所形成的序列

B. 由不同顶点所形成的序列

C. 由不同边所形成的序列

D. 上述定义都不是

第 22 题

• 技能点：无向图的入度和出度

在一个无向图中，在一个有向图中所有顶点的入度之和等于所有顶点出度之和的（ ）倍

A. 1/2

B. 2

C. 1

D. 4

第 23 题

• 技能点：无环有向图，深度优先遍历

用DFS遍历一个无环有向图，并在DFS算法退栈返回时打印相应的顶点，则输出的顶点序列是（ ）

A. 逆拓扑有序

B. 拓扑有序

C. 无序的

D. 不确定

第 24 题

• 技能点：图的邻接矩阵

下列哪一种图的邻接矩阵是对称矩阵?（ ）

A. 有向图

B. 无向图

C. AOV网

D. AOE网

第 25 题

• 技能点：图的关键路径

关键路径是事件结点网络中（ ）

A. 从源点到汇点的最长路径

B. 从源点到汇点的最短路径

C. 最长回路

D. 最短回路点

答案

C B B B C

B A B A A

D C B A D

B(平台有误，应该是A) C D A B

A C A B A

a3,a5,a6,a16

关卡五 查找

题目

第 1 题

• 技能点：顺序查找

对n个元素的表做顺序查找时，若查找每个元素的概率相同，则平均查找长度为（ ）

A. (n-1)/2

B. n/2

C. (n+1)/2

D. n

第 2 题

• 技能点：折半查找

适用于折半查找的表的存储方式及元素排列要求为（ ）

A. 链接方式存储，元素无序

B. 链接方式存储，元素有序

C. 顺序方式存储，元素无序

D. 顺序方式存储，元素有序

第 3 题

• 技能点：折半查找、顺序查找

当在一个有序的顺序表上查找一个数据时，既可用折半查找，也可用顺序查找，但前者比后者的查找速度（ ）

A. 必定快

B. 不一定

C. 在大部分情况下要快

D. 取决于表递增还是递减

第 4 题

• 技能点：折半查找

折半查找有序表(4，6，10，12，20，30，50，70，88，100)。若查找表中元素58，则它将依次与表中（ ）比较大小，查找结果是失败。

A. 20，70，30，50

B. 30，88，70，50

C. 20，50

D. 30，88，50

第 5 题

• 技能点：折半查找

对22个记录的有序表作折半查找，当查找失败时，至少需要比较（ ）次关键字。

A. 3

B. 4

C. 5

D. 6

第 6 题

• 技能点：折半查找

设有序表中有1000个元素，则用二分查找查找元素X最多需要比较（ ）次。

A. 25

B. 10

C. 7

D. 1

第 7 题

• 技能点：顺序查找

顺序查找不论在顺序线性表中还是在链式线性表中的时间复杂度为（ ）

A. O(n)

B. O(n^2)

C. O(n/3)

D. O(log2n)

第 8 题

• 技能点：折半查找

设一组初始记录关键字序列为(13，18，24，35，47，50，62，83，90，115，134),则利用二分法查找关键字90需要比较的关键字个数为（ ）

A. 1

B. 2

C. 3

D. 4

第 9 题

• 技能点：折半查找

设一个顺序有序表A[1:14]中有14个元素，则采用二分法查找元素A[4]的过程中比较元素的顺序为（ ）

A. A[1]，A[2]，A[3]，A[4]

B. A[1]，A[14]，A[7]，A[4]

C. A[7]，A[3]，A[5]，A[4]

D. A[7]，A[5] ，A[3]，A[4]

第 10 题

• 技能点：分块查找

设顺序线性表的长度为30，分成5块，每块6个元素，如果采用分块查找，则其平均查找长度为（ ）

A. 6

B. 11

C. 5

D. 6.5

第 11 题

• 技能点：折半搜索和二叉排序树

折半搜索与二叉排序树的时间性能（ ）

A．相同

B．完全不同

C．有时不相同

D．数量级都是O(log2n)

第 12 题

• 技能点：二叉排序树

分别用以下列序列构造二叉排序树，与用其它三个序列所构造的结果不同的是（ ）

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 题

• 技能点：分块查找

当采用分块查找时，数据的组织方式为（ ）

A．数据分成若干块，每块内数据有序

B．数据分成若干块，每块内数据不必有序，但块间必须有序，每块内最大（或最小）的数据组成索引块

C. 数据分成若干块，每块内数据有序，每块内最大（或最小）的数据组成索引块

D. 数据分成若干块，每块（除最后一块外）中数据个数需相同

第 14 题

对线性表进行二分查找时，要求线性表必须（ ）

A. 以顺序方式存储

B. 以链表方式存储

C. 以顺序方式存储，且结点按关键字有序排列

D. 以链表方式存储，且结点按关键字有序排列

第 15 题

• 技能点：哈希查找

下面关于哈希(Hash)查找的说法正确的是（ ）

A．哈希函数构造的越复杂越好，因为这样随机性好，冲突小

B．除留余数法是所有哈希函数中最好的

C．不存在特别好与坏的哈希函数，要视情况而定

D．若需在哈希表中删去一个元素，不管用何种方法解决冲突都只要简单的将该元素删去即可

第 16 题

• 技能点：二分查找

设有序顺序表中有n个数据元素，则利用二分查找法查找数据元素X的最多比较次数不超过（ ）。（2：均表示以2为底）

A. log2n+1

B. log2n-1

C. log2n

D. log2(n+1)

第 17 题

• 技能点：哈希查找

下面关于哈希查找的说法，正确的是（ ）

A．哈希函数构造的越复杂越好，因为这样随机性好，冲突小

B．除留余数法是所有哈希函数中最好的

C．不存在特别好与坏的哈希函数，要视情况而定

D. 哈希表的平均查找长度有时也和记录总数有关

第 18 题

• 技能点：哈希查找

下面关于哈希查找的说法，不正确的是（ ）

A．采用链地址法处理冲突时，查找一个元素的时间是相同的

B．采用链地址法处理冲突时，若插入规定总是在链首，则插入任一个元素的时间是相同的

C．采用链地址法处理冲突，不会引起二次聚集现象

D．采用链地址法处理冲突，适合表长不确定的情况

第 19 题

• 技能点：哈希查找

设哈希表长为14，哈希函数是 H(key)=key%11，表中已有数据的关键字为15，38，61，84共四个，现要将关键字为49的元素加到表中，用二次探测法解决冲突，则放入的位置是（ ）

A. 8

B. 3

C. 5

D. 9

第 20 题

• 技能点：线性探测法

采用线性探测法处理冲突，可能要探测多个位置，在查找成功的情况下，所探测的这些位置上的关键字（ ）

A. 不一定都是同义词

B. 一定都是同义词

C. 一定都不是同义词

D. 都相同

第 21 题

• 技能点：比较不同查找法

如果要求一个线性表既能较快的查找，又能适应动态变化的要求，最好采用（ ）查找法。

A. 顺序查找

B. 折半查找

C. 分块查找

D. 哈希查找

第 22 题

• 技能点：顺序查找

由n个数据元素组成的两个表: 一个递增有序，一个无序。采用顺序查找算法，对有序表从头开始查找，发现当前元素已不小于待查元素时，停止查找，确定查找不成功，已知查找任一元素的概率是相同的，则在两种表中成功查找（ ）

A. 平均时间后者小

B. 平均时间两者相同

C. 平均时间前者小

D. 无法确定

第 23 题

• 技能点：顺序查找

对长度为3的顺序表进行查找，若查找第一个元素的概率为1/2，查找第二个元素的概率为1/3,查找第三个元素的概率为1/6, 则查找任一元素的平均查找长度为（ ）

A. 5/3

B. 2

C. 7/3

D. 4/3

第 24 题

• 技能点：散列函数

用散列函数求元素在散列表中的存储位置时，可能会出现不同的关键字得到相同散列函数值的冲突现象，可用于解决上述问题的是（ ）

A. 线性探测法

B. 除留余数法

C. 平方取中法

D. 折叠法

第 25 题

• 技能点：散列查找

采用开放定址法解决冲突的散列查找中，发生聚集的原因主要是（ ）

A. 数据元素过多

B. 负载因子过大

C. 散列函数选择不当

D. 解决冲突的方法选择不当

答案

C D C A B

B A B C D

C C B C C

A C A D A

C B A A D

a5,a19,a20

第六关 - 排序

题目

第 1 题

• 技能点：快速排序

设一组初始记录关键字序列(5，2，6，3，8)，以第一个记录关键字5为基准进行一趟快速排序的结果为（ ）

A. 2，3，5，8，6

B. 3，2，5，8，6

C. 3，2，5，6，8

D. 2，3，6，5，8

第 2 题

• 技能点：快速排序

设一组初始关键字记录关键字为(20，15，14，18，21，36，40，10)，则以20为基准记录的一趟快速排序结束后的结果为（ ）

A. 10，15，14，18，20，36，40，21

B. 10，15，14，18，20，40，36，21

C. 10，15，14，20，18，40，36，2l

D. 15，10，14，18，20，36，40，21

第 3 题

• 技能点：快速排序的适用情况

快速排序在下列（ ） 情况下最易发挥其长处。

A．被排序的数据中含有多个相同排序码

B．被排序的数据已基本有序

C．被排序的数据完全无序

D．被排序的数据中的最大值和最小值相差悬殊

第 4 题

• 技能点：快速排序的时间复杂度

对n个关键字作快速排序，在最坏情况下，算法的时间复杂度是（ ）

A. O(n)

B. O(n^2)

C. O(nlog2n)

D. O(n^3)

第 5 题

• 技能点：插入排序

设一组初始记录关键字的长度为8，则最多经过（ ） 趟插入排序可以得到有序序列。

A. 6

B. 7

C. 8

D. 9

第 6 题

• 技能点：冒泡排序适用情况

对n个不同的关键字由小到大进行冒泡排序，在下列（ ） 情况下比较的次数最多。

A. 从小到大排列好的

B. 从大到小排列好的

C. 元素无序

D. 元素基本有序

第 7 题

• 技能点：冒泡排序的比较次数

对n个不同的排序码进行冒泡排序，在元素无序的情况下比较的次数最多为（ ）

A. n+1

B. n

C. n-1

D. n(n-1)/2

第 8 题

• 技能点：冒泡排序

设一组初始记录关键字序列为(Q，H，C，Y，P，A，M，S，R，D，F，X)，则按字母升序的第一趟冒泡排序结束后的结果是（ ）

A. F，H，C，D，P，A，M，Q，R，S，Y，X

B. P,A，C，S，Q，D，F，X，R，H，M，Y

C. A，D，C，R，F，Q，M，S，Y，P，H，X

D. H，C，Q，P，A，M，S，R，D，F，X，Y

第 9 题

• 技能点：希尔排序

设一组初始记录关键字序列为(50，40，95，20，15，70，60，45)，则以增量d=4的一趟希尔排序结束后前4条记录关键字为（ ）

A. 40，50，20，95

B. 15，40，60，20

C. 15，20，40，45

D. 45，40，15，20

第 10 题

• 技能点：二路归并排序时间复杂度

二路归并排序的时间复杂度为（ ）

A. O(n)

B. O(n^2)

C. O(nlog2n)

D. O(1og2n)

第 11 题

• 技能点：二叉排序树的遍历方法

（ ） 二叉排序树可以得到一个从小到大的有序序列。

(A)先序遍历

(B)中序遍历

(C)后序遍历

(D)层次遍历

第 12 题

• 技能点：二叉排序树的根结点

二叉排序树中左子树上所有结点的值均（ ） 根结点的值。

A. <

B. >

C. =

D. !=

第 13 题

• 技能点：二叉排序树的深度

设有一组初始记录关键字序列为(34，76，45，18，26，54，92)，则由这组记录关键字生成的二叉排序树的深度为（ ）

A. 4

B. 5

C. 6

D. 7

第 14 题

• 技能点：拓扑排序

设有向无环图G中的有向边集合E={，<2，3>，<3，4>，}，则下列属于该有向图G的一种拓扑排序序列的是（ ）

A. 1，2，3，4

B. 2，3，4，1

C. 1，4，2，3

D. 1，2，4，3

第 15 题

• 技能点：堆的关键字序列

下列关键字序列中，（ ） 是堆。

A. 16，72，31，23，94，53

B. 94，23，31，72，16，53

C. 16，53，23，94，31，72

D. 16，23，53，31，94，72

第 16 题

• 技能点：堆排序

若一组记录的排序码为（46，79，56，38，40，84)，则利用堆排序的方法建立的初始堆为（ ）

A. 79，46，56，38，40，84

B. 84，79，56，38，40，46

C. 84，79，56，46，40，38

D. 84，56，79，40，46，38

第 17 题

• 技能点：排序方法比较

从未排序序列中依次取出元素与已排序序列中的元素进行比较，将其放入已排序序列的正确位置上的方法，这种排序方法称为（ ）

A. 归并排序

B. 冒泡排序

C. 插入排序

D. 选择排序

第 18 题

• 技能点：排序方法比较

从未排序序列中挑选元素，并将其依次放入已排序序列（初始时为空）的一端的方法，称为（ ）

A. 归并排序

B. 冒泡排序

C. 插入排序

D. 选择排序

第 19 题

• 技能点：排序方法的时间复杂度比较

下列各种排序算法中平均时间复杂度为O(n^2)是（ ）

A. 快速排序

B. 堆排序

C. 归并排序

D. 冒泡排序

第 20 题

• 技能点：排序方法的空间复杂度比较

下列四种排序中（ ） 的空间复杂度最大。

A. 插入排序

B. 冒泡排序

C. 堆排序

D. 归并排序

第 21 题

• 技能点：排序方法比较

设有5000个待排序的记录关键字，如果需要用最快的方法选出其中最小的10个记录关键字，则用下列（ ） 方法可以达到此目的。

A. 快速排序

B. 堆排序

C. 归并排序

D. 插入排序

第 22 题

• 技能点：排序方法的时间复杂度比较

时间复杂度不受数据初始状态影响而恒为O(nlog2n)的是（ ）

A. 堆排序

B. 冒泡排序

C. 希尔排序

D. 快速排序

第 23 题

• 技能点：最稳定的排序方法

下述几种排序方法中，（ ） 是稳定的排序方法。

A. 希尔排序

B. 快速排序

C. 归并排序

D. 堆排序

第 24 题

• 技能点：排序方法比较

下列排序算法中，（ ） 不能保证每趟排序至少能将一个元素放到其最终的位置上。

A. 希尔排序

B. 快速排序

C. 冒泡排序

D. 堆排序

第 25 题

• 技能点：排序方法比较

数据表中有10000个元素，如果仅要求求出其中最大的10个元素，则采用（ ） 算法最节省时间。

A. 冒泡排序

B. 快速排序

C. 简单选择排序

D. 堆排序

答案

C A C B B

B D D B C

B A A A D

B C D D D

B A C A C(平台错了，应选D)

a5,a11,a25