题库试卷

【百年教育职业培训中心】数据结构-章节资料考试资料-河南大学 (2)

来源：百年教育职业培训中心　更新时间：2022-06-14 08:33:08

报名本机构合作学校，赠送复习资料，复习课程，确保录取。并且可以申请学校奖学金500元～1500元不等！答案：微信搜索【渝粤教育】公众号小测验：算法复杂度1、【单选题】下列函数中，哪个函数具有最快的增长

报名本机构合作学校，赠送复习资料，复习课程，确保录取。并且可以申请学校奖学金500元～1500元不等！

答案：微信搜索【渝粤教育】公众号

小测验：算法复杂度

1、【单选题】下列函数中，哪个函数具有最快的增长速度：

A、<img src="http://img-ph-mirror.nosdn.127.net/3z8yPzvrQFxdIOaMeX0VFw==/6619128168932814474.png" />

B、<img src="http://img-ph-mirror.nosdn.127.net/PtGLgFXasn-9Vjd9yHdOcw==/6619077591397938342.png" />

C、<img src="http://img-ph-mirror.nosdn.127.net/d35euJUBrlAwHRW476cfpA==/6608677310911164042.png" />

D、<img src="http://edu-image.nosdn.127.net/_PhotoUploadUtils_678b2235-695d-4ceb-b57e-5414488062d0.png" />

2、【单选题】下面一段代码的时间复杂度是？if ( A B ) {
for ( i=0; iN; i++ )
for ( j=N*N; ji; j-- )
A += B;
}
else {
for ( i=0; iN*2; i++ )
for ( j=N*2; ji; j-- )
A += B;
}

A、<img src="http://img-ph-mirror.nosdn.127.net/8BHTc-DfWY5qqM9sTW0T5Q==/6608445313957699465.png" />

B、<img src="http://img-ph-mirror.nosdn.127.net/WQ70TFdvAPED7PMCRH4nqg==/6608826844492543373.png" />

C、<img src="http://img-ph-mirror.nosdn.127.net/FwuImACjF6KP5pVJNcrXDw==/6619506400932769566.png" />

D、<img src="http://img-ph-mirror.nosdn.127.net/ngFJANrru5NouSiYjXIP4A==/6619177646956064258.png" />

测试1 数据结构概述

1、【单选题】从逻辑上可以把数据结构分成（）。

A、动态结构和静态结构

B、紧凑结构和非紧凑结构

C、线性结构和非线性结构

D、内部结构和外部结构

2、【单选题】与数据元素本身的形式、内容、相对位置、个数无关的是数据的（）。

A、存储结构

B、存储实现

C、逻辑结构

D、运算实现

3、【单选题】下面程序的时间复杂度是（）。x=0y=1for (i=1; i=n; ++i){ ++x; y=y*i }

A、O(1)

B、O(n)

C、O(1+n)

D、O(2+2n)

4、【单选题】在存储数据时，通常不仅要存储各数据元素的值，而且还要存储（）。

A、数据的处理方法

B、数据元素的类型

C、数据元素之间的关系

D、数据的存储方法

5、【单选题】下面程序段的时间复杂度是（）。 for（ i ＝0； i＜n； i＋＋） for（j＝0；j＜m；j＋＋） { A[i][j] ＝ 0； sum=sum+1； }

A、O（n*m）

B、O（2n*m）

C、O（n+m）

D、O（2n*2m）

6、【单选题】算法分析的目的是（）。

A、找出数据结构的合理性

B、研究算法中的输入和输出的关系

C、分析算法的效率以求改进

D、分析算法的易读性和文档性

7、【单选题】算法分析的两个主要方面是（）。

A、空间复杂度和时间复杂度

B、正确性和简明性

C、可读性和文档性

D、数据复杂性和程序复杂性

8、【单选题】计算机算法必须具备输入、输出和等5个特性。

A、可行性、可移植性和可扩充性

B、可行性、确定性和有穷性

C、确定性、有穷性和稳定性

D、易读性、稳定性和安全性

9、【单选题】以下与数据的存储结构无关的术语是（）。

A、链表

B、有序表

C、顺序栈

D、链队列

10、【单选题】关于算法，下面说法错误的是（）

A、算法原地工作的含义是指不需要任何额外的辅助空间

B、同一个算法，实现语言的级别越高，执行效率就越低

C、算法的时间复杂度通常用记作T（n）=O（f（n））

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、错误

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

A、正确

B、错误

18、【判断题】算法的优劣与算法描述语言无关，但与所用计算机有关。

A、正确

B、错误

19、【判断题】抽象数据类型和数据类型本质上是一个概念。

A、正确

B、错误

20、【判断题】数据结构是一门研究非数值计算的程序设计问题中计算机的操作对象以及它们之间的关系和操作等的学科。

A、正确

B、错误

小测验：线性表

1、【单选题】对于线性表，在顺序存储结构和链式存储结构中查找第k个元素，其时间复杂性分别是多少？

A、都是O(1)

B、都是O(k)

C、O(1)和O(k)

D、O(k)和O(1)

2、【单选题】在顺序结构表示的线性表中，删除第i个元素（数组下标为i-1)，需要把后面的所有元素都往前挪一位，相应的语句是：for (___________ ) PtrL-Data[j-1]=PtrL-Data[j]; 其中空缺部分的内容应该是

A、 j = i; j< = PtrL->Last; j++

B、 j =PtrL->Last; j>= i; j--

C、 j = i-1; j< = PtrL->Last; j++

D、j =PtrL->Last; j>= i-1; j--

3、【判断题】下列函数试图求链式存储的线性表的表长，是否正确？int Length ( List *PtrL ){ List *p = PtrL; int j = 0; while ( p ) { p++; j++; } return j;}

A、正确

B、错误

小测验：堆栈

1、【单选题】借助堆栈将中缀表达式A-(B-C/D)*E转换为后缀表达式，则该堆栈的大小至少为：

A、2

B、3

C、4

D、5

2、【单选题】设1、2、…、n–1、n共n个数按顺序入栈，若第一个出栈的元素是n，则第三个出栈的元素是：

A、3

B、n-2

C、n-3

D、任何元素均可能

3、【单选题】若用单向链表实现一个堆栈，当前链表状态为：1-2-3。当对该堆栈执行pop()、push(4)操作后，链表状态变成怎样？（1）4-2-3 (2) 1-2-4

A、只能是（1）

B、只能是（2）

C、（1）和（2）都有可能

D、（1）和（2）都不可能

4、【单选题】如果一堆栈的输入序列是aAbBc，输出为 abcBA，那么该堆栈所进行的操作序列是什么？设P代表入栈，O代表出栈。

A、PPPOOPOPOO

B、POOPPPOPOO

C、POPPOPPOOO

D、PPOPPOOOPO

小测验：队列

1、【单选题】在一个链表表示的队列中， f和r分别指向队列的头和尾。下列哪个操作能正确地将s结点插入到队列中：

A、f->next=s; f=s;

B、r->next=s; r=s;

C、s->next=r; r=s;

D、s->next=f; f=s;

2、【单选题】现采用大小为10的数组实现一个循环队列。设在某一时刻，队列为空且此时front和rear值均为5。经过若干操作后，front为8，rear为2，问：此时队列中有多少个元素？

A、4

B、5

C、6

D、7

测试2 线性表

1、【单选题】链式存储的存储结构所占存储空间（）。

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

B、只有一部分,存放结点值

C、只有一部分,存储表示节点间关系的指针

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

2、【单选题】在n个结点的顺序表中，算法的时间复杂度是O（1）的操作是：（）。

A、求第i个结点的直接前驱（2≤i≤n）和求第i个结点的直接后继（1≤i≤n-1）

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

C、删除第i个结点（1≤i≤n）

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

3、【单选题】线性表Ｌ在（）情况下适用于使用链式结构实现。

A、需经常修改Ｌ中的结点值且L中结点个数较多

B、需不断对Ｌ进行删除插入且L中的元素个数变化较大

C、Ｌ中含有大量的结点且结点结构复杂

D、Ｌ中结点结构复杂且需要经常求前驱和后继

4、【单选题】下面关于线性表的叙述中，错误的是哪一个（）。

A、线性表采用顺序存储，必须占用一片连续的存储单元

B、线性表采用顺序存储，便于进行插入和删除操作

C、线性表采用链接存储，不必占用一片连续的存储单元

D、线性表采用链接存储，便于插入和删除操作

5、【单选题】若某线性表最常用的操作是存取任一指定序号的元素和在最后进行插入和删除运算，则利用______存储方式最节省时间。

A、顺序表

B、双链表

C、带头结点的双循环链表

D、单循环链表

6、【单选题】某线性表中最常用的操作是在最后一个元素之后插入一个元素和删除第一个元素，则采用 _______存储方式最节省运算时间。

A、单链表

B、仅有头指针的单循环链表

C、双链表

D、仅有尾指针的单循环链表

7、【单选题】对于一个头指针为head的带头结点的单链表，判定该表为空表的条件是（）。

A、head==NULL

B、head→next==NULL

C、head→next==head

D、head!=NULL

8、【单选题】一个带头结点的空循环单链表head的尾结点p满足（）。

A、p->next==NULL

B、p==head

C、p==NULL

D、p->next!=head

9、【单选题】在单链表指针为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;

10、【单选题】静态链表中指针域中存储的是（）。

A、下一个元素的内存地址

B、双亲结点的数组下标

C、下一元素在数组中的下标

D、左、右孩子的地址

11、【单选题】在一个长度为n（n＞1）的单链表上，设有头和尾两个指针，执行（）操作与链表的长度有关。

A、删除单链表中的第一个元素

B、删除单链表中的最后一个元素

C、在单链表第一个元素前插入一个新元素

D、在单链表最后一个元素后插入一个新元素

12、【单选题】与单链表相比，双链表的优点之一是（）。

A、插入、删除操作更简单

B、可以进行随机访问

C、可以省略表头指针或表尾指针

D、顺序访问相邻结点更灵活

13、【单选题】对于顺序存储的线性表，访问结点和增加、删除结点的时间复杂度为（）。

A、O（n） O（n）

B、O（n） O（1）

C、O（1） O（n）

D、O（1） O（1）

14、【单选题】单链表中，增加一个头结点的目的是为了（）。

A、使单链表至少有一个结点

B、标识表结点中首结点的位置

C、方面运算的实现

D、说明单链表是线性表的链式存储

15、【判断题】线性表中的所有元素都有一个直接前驱元素和直接后继元素。

A、正确

B、错误

16、【判断题】顺序存储方式的优点是存储密度大，且插入、删除运算效率高。

A、正确

B、错误

17、【判断题】线性表采用链式存储必须占用一片连续的存储空间。

A、正确

B、错误

18、【判断题】非空的循环单链表head的尾结点p满足p-next==head。

A、正确

B、错误

19、【填空题】若线性表采用顺序存储结构，每个元素占用4个存储单元，第一个元素的存储地址为200，则第15个元素的存储地址是。

A、

20、【填空题】若线性表采用顺序存储结构，每个元素占用4个存储单元，第一个元素的存储地址为100，则第22个元素的存储地址是___________________。

A、

测试3 栈

1、【单选题】栈的插入和删除操作在（）。

A、栈底

B、栈顶

C、任意位置

D、指定位置

2、【单选题】一个栈的输入序列为：1,2,3,4，则栈的不可能输出的序列是（）。

A、1243

B、1432

C、2134

D、4312

3、【单选题】若已知一个栈的入栈序列是1,2,3，…,n，其输出序列为p1,p2,p3,…,pn，若p1=n,则pi为（）。

A、i

B、n-i

C、n-i+1

D、不确定

4、【单选题】若一个栈以向量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--;

5、【单选题】若元素a,b,c,d,e,f依次进栈，允许进栈退栈操作交替进行，但不允许连续三次进行退栈工作，则不可能得到的出栈序列是（）。

A、d,c,e,b,f,a

B、 c,b,d,a,e,f

C、b,c,a,e,f,d

D、a,f,e,d,c,b

6、【单选题】若一个栈输入序列为1,2,3，…,n,输出序列的第一个元素是i,则第j个输出元素是（）。

A、i-j-1

B、i-j

C、 j-i+1

D、不确定的

7、【单选题】栈的插入和删除操作在（）。

A、栈底

B、栈顶

C、任意位置

D、指定位置

8、【单选题】判定一个栈ST（最多元素为m0）为空的条件是（）

A、ST->top<>0

B、ST->top=0

C、ST->top<>m0

D、ST->top=m0

9、【判断题】当栈的使用过程中元素个数变化较大时，用链栈是适宜的，反之，应该采用顺序栈。

A、正确

B、错误

10、【判断题】栈和队列的存储方式既可是顺序方式，也可是链接方式（）。

A、正确

B、错误

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

A、正确

B、错误

12、【判断题】一个栈的输入序列是12345，则栈的输出序列不可能是12345（）。

A、正确

B、错误

13、【判断题】对一个栈进行取栈顶元素操作后，该栈顶元素也被移出栈。（）

A、正确

B、错误

14、【判断题】栈是一种特殊的线性表，其特殊性在于其数据元素只能是字符类型。（）

A、正确

B、错误

15、【判断题】若输入序列为1,2,3,4,5,6,则通过一个栈可以输出序列3,2,5,6,4,1.。（）

A、正确

B、错误

16、【判断题】若输入序列为1，2，3，4，5，6，则通过一个栈可以输出序列1，5，4，6，2，3。（）

A、正确

B、错误

17、【判断题】在表结构中最常用的是线性表，栈和队列不太常用。（）

A、正确

B、错误

18、【判断题】栈是一种对所有插入、删除操作限于在表的一端进行的线性表，是一种后进先出型结构。（）

A、正确

B、错误

19、【判断题】对于不同的使用者，一个表结构既可以是栈，也可以是队列，也可以是线性表。（）

A、正确

B、错误

20、【判断题】栈和队列都是非线性数据结构。（）

A、正确

B、错误

小测验：树的表示

1、【单选题】在分量1~11的数组中按从小到大顺序存放11个元素，如果用顺序查找和二分查找分别查找这11个元素，哪个位置的元素在这两种方法的查找中总次数最少？

A、1

B、2

C、3

D、6

2、【单选题】在分量1~11的数组中按从小到大顺序存放11个元素，如果进行二分查找，查找次数最少的元素位于什么位置？

A、1

B、5

C、6

D、11

3、【单选题】一棵度为 m的树有n个节点。若每个节点直接用m个链指向相应的儿子，则表示这个树所需要的总空间是n*(m+1) (假定每个链以及表示节点的数据域都是一个单位空间).。当采用儿子/兄弟（First Child/Next Sibling）表示法时，所需的总空间是：

A、3n

B、2n

C、n*m

D、n*(m-1)

小测验：二叉树性质

1、【单选题】如果一个完全二叉树最底下一层为第六层（根为第一层）且该层共有8个叶结点，那么该完全二叉树共有多少个结点？

A、31

B、39

C、63

D、71

2、【单选题】若有一二叉树的总结点数为98，只有一个儿子的结点数为48，则该树的叶结点数是多少？

A、25

B、50

C、不确定

D、这样的树不存在

3、【判断题】设深度为d（只有一个根结点时，d为1）的二叉树只有度为0和2的结点，则此类二叉树的结点数至少为2d-1

A、正确

B、错误

小测验：树的遍历

1、【单选题】假定只有四个结点A、B、C、D的二叉树，其前序遍历序列为ABCD‍，则‍下面哪个序列是不可能的中序遍历序列？‍

A、ABCD

B、ACDB

C、DCBA

D、DABC

2、【单选题】对于二叉树，如果其中序遍历结果与前序遍历结果一样，那么可以断定该二叉树________‍

A、是完全二叉树

B、所有结点都没有左儿子

C、所有结点都没有右儿子

D、这样的树不存在

3、【单选题】已知一二叉树的后序和中序遍历的结果分别是FDEBGCA 和FDBEACG,那么该二叉树的前序遍历结果是什么？

A、ABDFECG

B、ABDEFCG

C、ABDFEGC

D、ABCDEFG

小测验：二叉搜索树

1、【单选题】已知一棵由1、2、3、4、5、6、7共7个结点组成的二叉搜索树（查找树），其结构如图所示，问：根结点是什么？ <img src="http://img2.ph.126.net/RLLZCcXh8TiwfmTAMV4Pdw==/6619318384444736930.jpg" />

A、1

B、4

C、5

D、不能确定

2、【单选题】在上题的搜索树中删除结点1，那么删除后该搜索树的后序遍历结果是：

A、243765

B、432765

C、234567

D、765432

3、【判断题】若一搜索树（查找树）是一个有n个结点的完全二叉树，则该树的最大值一定在叶结点上

A、正确

B、错误

4、【判断题】若一搜索树（查找树）是一个有n个结点的完全二叉树，则该树的最小值一定在叶结点上

A、正确

B、错误

小测验：平衡二叉树

1、【单选题】将1、2、3、4、5、6顺序插入初始为空的AVL树中，当完成这6个元素的插入后，该AVL树共有多少层？

A、2

B、3

C、4

D、5

2、【单选题】若一AVL树的结点数是21，‍则该树的高度至多是多少？注：只有一‍个根节点的树高度为0

A、4

B、5

C、6

D、7

小测验：堆

1、【单选题】下列序列中哪个是最小堆？

A、2, 55, 52, 72, 28, 98, 71

B、2, 28, 71, 72, 55, 98, 52 ‍

C、2, 28, 52, 72, 55, 98, 71‍

D、28, 2, 71, 72, 55, 98, 52

2、【单选题】在最大堆 {97,76,65,50,49,13,27}中插入83后，该最大堆为：

A、{97,76,65,83,49,13,27,50}

B、{97,83,65,76,49,13,27,50}

C、{97,83,65,76,50,13,27,49}

D、{97,83,65,76,49,50,13,27}

3、【单选题】对由同样的n个整数构成的二叉搜索树（查找树）和最小堆，下面哪个说法是不正确的:

A、二叉搜索树（查找树）高度大于等于最小堆高度

B、对该二叉搜索树（查找树）进行中序遍历可得到从小到大的序列

C、从最小堆根节点到其任何叶结点的路径上的结点值构成从小到大的序列

D、对该最小堆进行按层序（level order）遍历可得到从小到大的序列

小测验：哈夫曼树

1、【单选题】如果哈夫曼树有67个结点，则可知叶结点总数为：

A、22

B、33

C、34

D、不确定

2、【单选题】为五个使用频率不同的字符设计哈夫曼编码，下列方案中哪个不可能是哈夫曼编码？

A、00，100，101，110，111

B、000，001，01，10，11

C、0000，0001，001，01，1

D、000，001，010，011，1

3、【单选题】一段文本中包含对象{a,b,c,d,e}，其出现次数相应为{3,2,4,2,1}，则经过哈夫曼编码后，该文本所占总位数为：

A、12

B、27

C、36

D、其它都不是

小测验：集合

1、【单选题】已知a、b两个元素均是所在集合的根结点，且分别位于数组分量3和2位置上，其parent值分别为-3,-2。问：将这两个集合按集合大小合并后，a和b的parent值分别是多少？

A、-5，2

B、-5，3

C、-3，3

D、2，-2

小测验：邻接矩阵表示法

1、【单选题】有<img src="http://img0.ph.126.net/1GL-r_RuliLOaVseUKAQuA==/6608583852422168811.png" />个顶点的无向完全图有多少条边？

A、<img src="http://img2.ph.126.net/TN-qb79Vxw_luIzYw-hq-A==/664280945054857358.png" />

B、<img src="http://img0.ph.126.net/rTMIMN6MxvZZM6DANrG27g==/2447987872469792097.png" />

C、<img src="http://img2.ph.126.net/Z6PsHp8eLhbbKBEEuwoLtA==/2877518686930831706.png" />

D、<img src="http://img2.ph.126.net/dReH4YGpYK9hOW1a_avehQ==/1040331513940462469.png" />

2、【单选题】给定有向图的邻接矩阵如下：<img src="http://nos.netease.com/edu-image/C8852D587F94E63025F32669013A461F.jpg?imageView顶点2（编号从0开始）的出度和入度分别是：

A、3, 1

B、1, 3

C、0, 2

D、2, 0

3、【判断题】有向图的邻接矩阵一定是不对称的

A、正确

B、错误

4、【判断题】用一维数组G[ ]存储有4个顶点的无向图如下：G[ ] = { 0, 1, 0, 1, 1, 0, 0, 0, 1, 0 }则顶点2和顶点0之间是有边的。

A、正确

B、错误

小测验：邻接表表示法

1、【单选题】用邻接表表示有<img src="http://img0.ph.126.net/1GL-r_RuliLOaVseUKAQuA==/6608583852422168811.png" />个顶点、<img src="http://img2.ph.126.net/ZHa27NCWDzmhFkZ_jIGjZA==/6598288025542037564.png" />条边的图，则遍历图中所有边的时间复杂度为：

A、<img src="http://img2.ph.126.net/WQ70TFdvAPED7PMCRH4nqg==/6608826844492543373.png" />

B、<img src="http://img0.ph.126.net/SeV5fbyC0hZhnSJBAx7FeQ==/1051027563055467921.png" />

C、<img src="http://img1.ph.126.net/XG1wVtSi7km-JC7j5UiCSQ==/16325548666410520.png" />

D、<img src="http://img1.ph.126.net/8BHTc-DfWY5qqM9sTW0T5Q==/6608445313957699465.png" />

小测验：DFS

1、【单选题】已知一个图如下图所示，从顶点a出发按深度优先搜索法进行遍历，则可能得到的一种顶点序列为<img style="width: 192px; height: 176px;" src="http://img0.ph.126.net/N6PBsEBWmpfU1cB8C25qGw==/2833890065540764263.jpg" />

A、a,e,b,c,f,d

B、a,b,e,c,d,f

C、a,c,f,e,b,d

D、a,e,d,f,c,b

小测验：BFS

1、【单选题】已知一个图如下图所示，从顶点a出发按广度优先搜索法进行遍历，则可能得到的一种顶点序列为<img style="width: 193px; height: 182px;" src="http://img0.ph.126.net/N6PBsEBWmpfU1cB8C25qGw==/2833890065540764263.jpg" />

A、a,b,c,e,d,f

B、a,b,c,e,f,d

C、a,e,b,c,f,d

D、a,c,f,d,e,b

小测验：连通性

1、【单选题】具有<img src="http://img2.ph.126.net/YcoTL3PQbCwAXia2f2iGMw==/33495522246440321.png" />个顶点的无向图至多有多少个连通分量

A、0

B、1

C、<img src="http://img0.ph.126.net/Rn17g-ATPxGbtDEaOO8QyA==/6619294195188912132.png" />

D、<img src="http://img0.ph.126.net/1GL-r_RuliLOaVseUKAQuA==/6608583852422168811.png" />

2、【单选题】如果从无向图的任一顶点出发进行一次深度优先搜索可访问所有顶点，则该图一定是

A、有回路的图

B、完全图

C、连通图

D、一棵树

3、【单选题】具有<img src="http://img2.ph.126.net/YcoTL3PQbCwAXia2f2iGMw==/33495522246440321.png" />个顶点的无向图至少有多少个连通分量

A、0

B、1

C、<img src="http://img0.ph.126.net/Rn17g-ATPxGbtDEaOO8QyA==/6619294195188912132.png" />

D、<img src="http://img0.ph.126.net/1GL-r_RuliLOaVseUKAQuA==/6608583852422168811.png" />

小测验：最小生成树

1、【单选题】给定下图，其最小生成树的总权重是<img src="http://img2.ph.126.net/jDSSMmRW6dcIsr6gFqO8ZA==/6619537187258713706.jpg" />

A、21

B、30

C、34

D、35

2、【判断题】连通图的最小生成树一定是唯一的

A、正确

B、错误

小测验：拓扑排序

1、【判断题】拓扑序一定是唯一的。

A、正确

B、错误

小测验：关键路径

1、【单选题】下图给定了一个项目的AOE。整个项目最早完工需要的时间是<img src="http://img0.ph.126.net/W6uCjomzeNw1GWuIB6EoEg==/3358840897189137675.jpg" />

A、17

B、19

C、20

D、23

2、【判断题】在上图中，如果0,2组能加快进度，整个项目就能提前完工。

A、正确

B、错误

小测验：冒泡排序

1、【单选题】对于7个数进行冒泡排序，最坏情况下需要进行的比较次数为

A、7

B、14

C、21

D、49

小测验：插入排序

1、【单选题】对一组包含10个元素的非递减有序序列，采用插入排序排成非递增序列，其可能的比较次数和移动次数分别是

A、45, 44

B、54, 63

C、100, 54

D、100, 100

小测验：希尔排序

1、【判断题】希尔排序是稳定的。

A、正确

B、错误

小测验：堆排序

1、【单选题】对N个记录进行堆排序，最坏的情况下时间复杂度是

A、<img src="http://img1.ph.126.net/8BHTc-DfWY5qqM9sTW0T5Q==/6608445313957699465.png" />

B、<img src="http://img0.ph.126.net/l0QALzMGT0dBE9giRahiOQ==/983192093667873840.png" />

C、<img src="http://img0.ph.126.net/BE5mtopQJXx5BlCjo5AOOA==/6619441529746744401.png" />

D、<img src="http://img2.ph.126.net/WQ70TFdvAPED7PMCRH4nqg==/6608826844492543373.png" />

2、【单选题】有一组记录（46,77,55,38,41,85），用堆排序建立的初始堆为

A、38,77,55,46,41,85

B、38,41,46,77,55,85

C、85,55,77,38,41,46

D、85,77,55,38,41,46

3、【判断题】堆排序是稳定的。

A、正确

B、错误

小测验：快速排序

1、【判断题】快速排序是稳定的算法。

A、正确

B、错误

小测验：表排序

1、【单选题】给定A[]={46, 23, 8, 99, 31, 12, 85}，调用非递归的归并排序加表排序执行第1趟后，表元素的结果是：

A、0, 1, 2, 3, 4, 5, 6

B、1, 0, 3, 2, 6, 5, 4

C、1, 0, 2, 3, 5, 4, 6

D、0, 2, 1, 4, 3, 5, 6

2、【单选题】给定A[]={23, 46, 8, 99, 31, 12, 85}，调用表排序后，表元素的结果是：

A、1, 2, 3, 4, 5, 6, 7

B、2, 0, 3, 5, 1, 4, 6

C、3, 6, 1, 5, 2, 7, 4

D、2, 5, 0, 4, 1, 6, 3

小测验：基数排序

1、【判断题】基数排序是稳定的算法。

A、正确

B、错误

小测验：排序综合

1、【单选题】请选择下面四种排序算法中最快又是稳定的排序算法：

A、希尔排序

B、堆排序

C、归并排序

D、快速排序

2、【单选题】下列排序算法中，哪种算法可能出现：在最后一趟开始之前，所有的元素都不在其最终的位置上

A、堆排序

B、插入排序

C、冒泡排序

D、快速排序

3、【单选题】当待排序列已经基本有序时，下面哪个排序算法效率最差

A、快速排序

B、直接插入

C、选择排序

D、堆排序

4、【单选题】数据序列（3,2,4,9,8,11,6,20）只能是下列哪种排序算法的两趟排序结果

A、冒泡排序

B、插入排序

C、选择排序

D、快速排序

小测验：散列冲突

1、【单选题】设有一组记录的关键字为 {19，14，23，1，68，20，84，27，55，11，10，79}，用分离链接法构造散列表，散列函数为H(key)= key mod 13。问：散列地址为1的链中有几个记录？

A、1

B、2

C、3

D、4

2、【单选题】设一个散列表的大小是11, 散列函数是H(key)=key mod 11. 若采用平方探测（<img src="http://img2.ph.126.net/7-JqsZPN0NsBXEkeFJV6aA==/6630549895721824529.png" />)冲突解决方法，将4个元素{14，38，61，86}顺序插入散列表中。如果再插入元素49，则该元素将被放在什么位置？

A、4

B、6

C、9

D、10

3、【单选题】假设一散列表的大小是11,散列函数是H(key)=key mod 11，用线性探测法解决冲突。先将4个元素{14，38，61，86}按顺序插入初始为空的散列表中。如果再插入元素49，则该元素被插入到表中哪个位置（下标）？

A、4

B、5

C、6

D、7

小测验：散列性能

1、【单选题】一个大小为11的散列表，散列函数为H(key)=key mod 11，采用线性探测冲突解决策略。如果现有散列表中仅有的5个元素均位于下标为奇数的位置，问：该散列表的平均不成功查找次数是多少？

A、6/11