数据结构习题

第一章 习题

一．填空题

１、数据结构被形式地定义为（D, R），其中D是 的有限集合，R是D上的 有限集合。 ２、数据结构按逻辑结构可分为两大类，它们分别是 和 。 ３、线性结构中元素之间存在 关系，树形结构中元素之间存在 关系，图形结构中元素之间存在 关系。

４、一个算法的效率可分为 效率和 效率。

５、简单地说，一个算法所进行的计算次数的多少称为 ，一个算法所需要辅助存储空间的多少称之为 。 ６、根据数据元素之间关系的不同特性，通常有四类基本结构，它们是集合、 、 、 。 二．选择题

１、算法分析的目的是（ ）

A、找出数据结构的合理性 B、 研究算法中的输入和输出的关系 C、分析算法的效率以求改进 D、分析算法的易懂性和文档性 ２、算法分析的两个主要方面是（ ）

A、空间复杂性和时间复杂性 B、 正确性和简明性

C、可读性和文档性 D、 数据复杂性和程序复杂性 ３、计算机算法指的是（ ）

A、计算方法 B、排序方法 C、 解决问题的有限运算序列 D、 调度方法 ４、计算机算法必须具备输入、输出和（ ）等5个特性。

A、可行性、可移植性和可扩充性 B、 可行性、确定性和有穷性 C、 确定性、有穷性和稳定性 D、 易读性、稳定性和安全性 ５、数据元素是数据的基本单位，其内（ ）数据项。

A、只能包含一个 B、不包含 C、可以包含多个 D、必须包含多个 ６、逻辑关系是指数据元素间的（ ） Ａ、类型 Ｂ、存储方式 Ｃ、结构 Ｄ、数据项 ７、数据结构有（ ）种基本逻辑结构。 A、１ B、２ C、３ D、４

８、下列四种基本的逻辑结构中，数据元素之间关系最弱的是（ ）。 A、集合 B、线性结构 C、树形结构 D、图状结构 ９、一个存储结构点存储一个（ ）。

A、 数据项 B、数据元素 C、数据结构 D、数据类型

10、某算法的时间复杂度为O(2n)，表明该算法的（ ）

A、问题规模是2n B、执行时间等于2n C、执行时间与2n成正比 D、问题规模与2n成正比 11、算法执行时间一般与（ ）无关。

A、 问题规模大小 B、计算机的档次 C、程序设计语言的种类或版本D、算法设计者的水平 12、算法分析的主要任务是分析算法（ ） A、 是否具有较好的可读性 B、是否存在语法错误 C、功能是否符合设计要求 D、执行时间和问题规模之间的关系。 13、下列时间复杂度中最坏的是（ ） A、O(1) B、O(n) C、O(log2n) D、O(n2) 14、下列算法的时间复杂度是（ ） D for(i=0;i

A、 O(1) B、O(n) C、O(log2n) D、O(n2) 15、算法的可读性是指（ ）

A、算法所含语句数较少 B、算法较简单，计算机容易编译 C、算法较简单，很容易看出它的执行结果 D、算法结

1

构清晰，容易被算法设计者及其他人看懂 三．简答题

1.数据结构中有哪几类数据结构？哪种关系最简单？哪种关系最复杂？

2.简述顺序存储结构与链式存储结构在表示数据元素之间关系上的主要区别。 3.数据与数据元素有何区别？二者有什么关系？

第二章 习题

一．判断题。

1.存储一个线性表所需的内存空间大小与线性表的元素类型无关。（ ） 2.顺序表的长度等于元素个数与每个元素所占内存单元数之乘积。（ ） 3.分配给顺序表的内在单元地址一定是连续的。（ ）

4.长度是n的顺序表中删除一个元素，所需的时间都是O(n)。（ ） 5.往顺序表中插入一个元素，平均要移动大约一半的元素。（ ） 6.分配给单链表各结点的内存单元地址必须是连续的。（ ） 7.单链表中的结点只有后继，没有前驱。（ ） 8.在链式结构存储的线性表上不能实现随机访问。（ ） 9.空单链表表示的是长度为零的线性表。（ ）

10.在对带头结点的单链表进行插入操作时，永远不会改变头指针的值。（ ） 11. 在描述链表的结点类型时，必须先描述数值字段，再描述指针字段。（ ） 12. 在循环单链表中，任何一个结点的指针字段值都不可能为空（ ） 二．填空题。

1.链表中逻辑上相邻的元素的物理位置（ ）相连。

2.单链表中，除头结点外，任何结点的存储位置都由其（ ）结点的指针指示。

3.已知带表头结点的单链表L，指针p指向L链表中的某个结点，指针q是指向L链表外的一个结点，则：

①在指针p所指结点后插入q所指结点的语句序列是（ ）； ②在指针p所指结点前插入q所指结点的语句序列是( )； ③将q所指结点插入在链表首结点的语句序列是（ ）； ④将q所指结点插入在链表尾结点的语句序列是（ ）； 4.已知带头结点的单链表L，指针p指向L链表中的一个结点（非首结点，非尾结点）则：

①删除指针p所指结点的直接后继结点的语句是（ ）； ②删除指针p所指结点的直接前驱结点的语句序列是（ ）； ③删除指针p所指结点的语句序列是（ ）； ④删除第一个结点的语句序列是（ ）； ⑤删除最后一个结点的语句序列是（ ）；

5.线性表的存储结构有（ ）和（ ）存储两种。

6.线性表的每个元素需4个字节存储，在顺序存储结构下LOC(ai)=1000,则LOC(ai+2)=( )。 7.往长度为n的顺序表中插入一个新元素，最多需要移动（ ）个元素。

8.若用带头结点的单向链表来表示长度为n的线性表，则需要为链表分配（ ）个结点的存储空间。 9.在顺序表的（ ）之后插入新元素，不需要移动任何元素。

10.线性表的元素长度为L，在顺序存储结构下LOC（ai）=LOC(a1)+( ) 11.在单链表中，删除指针q所指结点的直接后继结点，需要执行以下语句序列：p=q->next;( );free(p); 12.在删除每个元素的概率相等的情况下，从长度为n的顺序表中删除一个元素平均要移动（ ）个元素。 13.在长度为n的顺序表中实现定位操作，其算法的时间复杂度为（ ）

14.逻辑上相邻的元素在存储位置上也相邻，这是（ ）结构存储结构的特点。 三．选择题

2

1.一个顺序表所占存储空间的大小与（ ）无关。

A.顺序表长度 B.结点类型 C.结点中各字段的类型 D.结点的存放顺序 2.在程序中，为了设置一个空的顺序表，必须（ ）。

A.给各数组元素赋空值 B.给各顺序表元素赋空值 C.给表示顺序表长度的变量赋初始值 D.给数组变量名赋初始值 3.线性表中有2n个元素，以下算法中，在顺序表上实现比在链表上实现效率高的是（ ）。

A.输出第i个元素的值 B.交换第1个和第二个元素的值 C.顺序输出这2n个元素的值 D.输出与某个给定值x相等的元素在线性表中的序号

4.单链表所占用的内在单元地址一定是（ ）。 A.无序的 B.连续的 C.不连续的 D.部分连续的 5.以下说法正确的是（ ）。

A.线性表的逻辑顺序与存储顺序总是一致的 B.线性表的链式存储结构中，内存中可用的存储单元可以是连续的，也可以不连续 C.线性表的顺序存储结构优于链式存储结构 D.每种数据结构具有插入、删除和查找三种基本运算。 6.L是线性表，已知ListLength(L)的值是5，经过运算DeleteList(L,2)后ListLength(L)的值是（ ）。 A. 5 B. 3 C. 4 D. 6

7.线性表中有一个直接前驱和直接后继的是（ ）。 A. 首元素 B.尾元素 C.中间的元素 D.所有的元素 8.指针p指向循环链表L的首元素的条件是（ ）。 A.p==L B.p->next==L C.L->next==p D.p->next==NULL 9.线性表中各元素的关系是（ ）。 A.序偶关系 B.层次关系 C.网状关系 D.集合

10.单链表中每个结点中有（ ）个指针。 A. １ B. ２ C. ０ D. ３

11.指针p和q分别指向单链表的两个元素，p指针所指向元素是q所指向元素的前驱的条件是（ ）。 A. p->next==q B. q->next==p C. p==q D. p->next==q->next

12.指针p和q分别指向双向链表的两个元素，p指针所指向元素是q所指向元素的后继的条件是（ ）。 A. p==q B. q->next==p C. p->next==q D.q->next==p->next

13.在长度为n的顺序表的第i个(1≤i≤n+1)个位置上插入一个元素，元素的移动次数为（ ）。 A.i-1 B. i C. n-i D.n-i+1

14.对于只在表的首尾两端进行插入操作的线性表，宜采用的存储结构为（ ）。 A.顺序表B.用头指针表示的单循环链表C.用尾指针表示的单循环链表D.单链表 15. 在单链表中，增加头结点的目的是为了（）。

A.使单链表至少有一个结点 B.表示表结点中首结点的位置 C.方便运算的实现D.说明单链表是线性表的链式存储实现 四．简答题

1.什么情况下使用顺序表比使用链表好？

顺序表适宜于做查找这样的静态操作；链表宜于做插入、删除这样的动态操作。若线性表的长度变化不大，且其主要操作是查找，则采用顺序表；若线性表的长度变化较大，且其主要操作是插入、删除操作，则采用链表。 2.已知带头结点的单链表H，简述下列算法的功能。

Int func(LinkNode *H) {

if(H->next&&H->next->next) {

q=H->next; H=q->next; p =q;

while(p->next) p=p->next; p->next=q; q->next=NULL;

3

}

return OK; }

将第一个结点变成最后一个结点，去掉头结点。 3.已知线性表L＝（A，B，C，D），请画出该线性表存储在顺序表、单链表、循环链表、双向循环链表的示意图。 4.线性表的主要操作有哪些？

5.请给出求单链表H的长度的算法。

6.请给出依次输出单链表H中各结点值的算法。

7.若A和B是两个按结点值升序排列的有序循环链表，试给出将A、B按升序存储合并成循环链表C的算法。 8.线性表的顺序存储和链式存储各有什么特点？

9.若顺序表A中的数据元素按降顺排列，要将x插入到顺序表中的合适位置，以保证表的有序性，试给出其算法。 10.请给出删除单链表H中值为K的结点的算法。

第三章 栈和队列

一． 判断题

1.顺序栈中元素值的大小是有序的。（）

2.栈是一种对删除和插入位置做了限制的线性表。（） 3.进栈越早的元素出栈越晚。（）

4.顺序栈的最大容量是m，则对栈的进栈、出栈操作最多只能进行m次。（） 5.对顺序栈进行进栈、出栈操作，不会涉及元素的前、后移动问题。（） 6.栈顶元素和栈底元素有可能是同一个元素。（） 7.空栈没有栈顶指针。（）

8.对于非空栈来说，栈顶元素和栈底元素都是唯一的。（） 9.栈底元素是不能删除的元素。（）

10.与顺序栈相比，链栈通常不会出现栈满的情况。（）

11.队列是一种先进后出的线性表，栈是一种先进先出的线性表。（） 12.n个元素进队的顺序和出队的顺序总是一致的。（）

13.无论是顺序队还是链队，插入、删除操作的时间复杂度都是O(1)。（）

14.若用不带头结点的非循环单链表来表示链式队列，则可以用“队首指针和队尾指针相等”作为队空的标志。（） 15.队列中的元素个数，可以根据队首指针和队尾指针的值来计算。（） 16.循环队列是顺序结构，不会产生上溢或下溢。（）

17.循环队列队空的条件是头指针和尾指针都指向头结点。（） 18.循环队列满的条件是：q->rear - q->front==maxsize。（） 19.链队列队空的条件是：q->rear==q->front。（） 20.循环队列没有队头元素和队尾元素。（） 二． 填空题

1.栈是一种具有（ ）特性的线性表，队列是一种具有（ ）特性的线性表。 2.如果栈的长度难以估计，最好使用（ ）存储结构。

3.若用带头结点的单链表来表示栈，则栈空的标志是（ ）

4.若用s[0]~s[m-1]作为顺序栈的存储空间，栈空的标志是栈指针top的值等于m,则每进行一次（ ）操作，需将top的值加１，每进行一次（ ）操作，将top的值减一。

5.若用带头结点的单链表来表示链式栈，由创建一个空栈所要执行的操作是（ ）。 6.栈和队列的区别仅在于（ ）。

7.若用q[0]~q[99]作为循环队列的存储空间，q[f]、q[r]分别表示队首元素和下一个插入位置，则当f=80,r=30时，队列中共有（ ）个元素。

4

8.顺序队列在实现的时候，通常将数组看成是一个首尾相连的环，这样做的目的是为了避免产生（ ）现象。

9.栈的存储结构主要有（ ）和（ ）。

10.即使知道队首指针和队尾指针，也无法计算得出元素个数的队列，一定是（ ）存储结构的队列。

11.如果程序处理的数据是逐步产生的，如果要求处理数据元素的顺序和产生的数据元素的顺序正好相反，则通常用（ ）暂存待处理的数据。

12.顺序栈和链栈的区别仅在于（ ）的不同。

13.对栈执行删除操作时，只有在（ ）的情况下，才会将栈底元素删除。

14.若用带头结点的单向链表来表示链接栈，则创建一个空栈所要执行的操作是（ ）。 15.若用q[0]~q[m-1]表示非循环队列的存储空间，则最多只能执行（ ）入队操作。

16.若用q[0]~q[99]表示循环队列的存储空间，q[r]表示队尾元素，q[f]表示队首元素的前一个位置，则当f=60,r=0时，队列中共有（ ）元素。

17. 若用q[0]~q[m-1]表示循环队列的存储空间，q[r]表示队尾元素，q[f]表示队首元素的前一个位置，则可以（ 作为队空的标志，与此相对应，可用（ ）作队满的标志。 18.在队列的顺序存储结构中当插入一个新的元素时，队尾指针（ ），当删除一个队列元素时，队首指针（ 19.已知顺序栈S，入栈操作之前应判断（ ），出栈操作之前需要判断（ ）。 20.s[0]~s[m-1]表示栈的存储空间，栈顶指针为top=0表示栈空，则栈满的条件是（ ）。 三． 选择题

1.栈是限定在 处进行插入或删除操作的线表。 A.端点 B.栈底 C.栈顶 D.中间

2.在栈顶一端可以进行的全部操作是 。 A. 插入 B.删除 C.插入和删除 D.进栈

3.有４个元素按Ａ、B、C、D顺序连续进栈，执行pop(s,x)后，x的值是 。 A. A B. B C. C D. 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.设有一个栈，元素依次进栈的顺序为abcde。下面是不可能的出栈序列。 A. abcde B.bcdea C.eabcd D.edcba

12.如果以链表作为栈的存储结构，则退栈操作时 。

A.必须判断栈是否为满 B.判断栈元素的类型C.必须判断栈是否为空D.不作任何判断

13.设S[m]为循环队列的存储空间，f为队头指针，r为队尾指针，则执行出队操作的语句是 。 A.f=f+1 B.f=(f+1)%m C.r=(r+1)% m D.r=r+1

14.一个队列的入队顺序是abcd，则离队的顺序是 。 A.adcb B.abcd C.dcba D.cbda

15. 设S[m]为顺序栈的存储空间，则判断栈满的条件是 。

）。 5

）

10a58b7912c17103f114de16g

8.根据下图回答问题：

v2v5aaa4=3a1=33=28=1v1va7=24v6a2=2a5=4a6=3v3 （1）给出该图的一个序列。

（2）给出从V1到V8的关键路径。

9.有如下图所示AOE网，权值表示活动所需天数，回答问题问题：

2a5=4036=a8a46a1==631a2==181a111a3=14a7=1258a2=aa8=110=240520=36a9=127a1 （1）给出该图的一个拓扑序列。 （2）求从1出发到8的关键路径。 （3）完成工程至少需要多少天？

（4）提高哪些活动的速度可缩短工期？ 答：

10．对如图所示的有向网，试利用狄杰斯特拉算法求出从源点v0到其它各顶点的最短路径，并写出求解过程。

16

v0514258329v1v2v321v4

答：求解过程如下表所示，其中I为循环次数，k为加入集合S的顶点，S为已求得最短路径的顶点集合，shortest为最短路径的长度，path为最短路径。

shortest path

i k S 0 1 2 3 4 0 1 2 3 4

初态

1 1

2 2

3 4

4 3

11. 对如图所示的有向网，试利用狄杰斯特拉算法求出从源点v0到其它各顶点的最短路径，并写出求解过程。

答：求解过程如下表所示，其中i为循环次数，k为加入集合S的顶点，S为已求得最短路径的顶点集合，shortest为最短路径的长度，path为最短路径。

v37243v513357v0241v278v61v410v1

v7 i 0 1 2 3 4 5 6 7

k S shortest path 17

0 1 2 3 4 5 6 7 0 1 2 3 4 5 6 7

12.已知带权有向图如下如示，请用弗洛伊德算法(floyd)算法求出每对顶点之间的最短路径。

4v011362v2v1D 0 1 2 P 0 1 2

D(-1) 0 0 1 P(-1) 1 2 0 2 0 D(0) 1 P(0) 1 2 0 2 0 1 D(1) 2 2 0 0 D(2) 1 P(2) 1 2 2 P(1) 1 第八章 查找

一．判断题

1.顺序查找适用于顺序或链式存储的线性表。（） 2. 二叉排序树和二分法查找的时间性能是一样的。（）

3.AVL树是一棵二叉树，该树上任一结点的平衡因子都不大于1。（） 4.中序遍历一棵二叉排序树的结点就可得到排好序的结点序列。（） 5.顺序查找方法只能在顺序存储结构下进行。（） 6.二叉排序树中，新插入的结点总是在最底层。（）

7.平衡二叉排序树中，以每个分支结点为根的子树都是平衡的。（）

8.每个结点的关键字值都大于左子小于右子关键字值，这样的二叉树就是二叉排序树（） 9.哈希冲突是指同一个关键字对应多个不同的哈希地址。（） 10.二叉排序树的查找效率和其高度有关。（） 二．选择题

1.在二叉排序树中，新插入的结点，都是没有 的。 A.孩子 B.关键字 C.平衡因子 D.赋值

2.在数据元素有序，元素个数较多而固定不变的情况下，宜采用 法查找。 A.二叉排序树 B.分块查找 C.二分法 D.顺序查找

3.对有18个元素的有序表作二分查找，则查找A[3]的比较序列下标可能为 。 A.1、2、3 B.9、5、2、3 C.9、5、3 D.9、4、2、3

4.若在线性表中采用二分查找法查找元素，该线性表应该。

A.元素按值有序 B.采用顺序存储结构 C.元素按值有序，且采用顺序存储结构D.元素按值有序，且采用链式存储结构 5.采用顺序检索的方法检索长度为n的线性表，则检索每个元素的平均比较次数为 。 A.n B.n/2 C.(n+1)/2 D.(n-1)/2

6.有一个有序表为{2，3，10，12，32，41，45，62，75，78，83，94，99}，当用二分法查找83时，经过 次比较后查找成功。

18

A.1 B.2 C.4 D.8

7.设Hash表长m=14，Hash函数H(key)=key。表中已有4个结点。addr(15)=4,addr(38)=5,addr(61)=6,addr(81)=7，如用二次探测再Hash处理冲突，关键字为49的结点的地址是 。 A.8 B.9 C.3 D.5

8.分块查找的时间效率 。

A.低于二分查找B.高于顺序查找但低于二分查找C.高于顺序查找D.低于顺序查找但高于二分查找

9.有数据{52,29,36,11,44,23,95}，从空二叉树开始逐个插入数据来形成二叉排序树，若希望高度最小，则应该选择下面哪个序列插入 。

A.44,23,52,11,36,95,29 B.36,23,11,52,44,95 C.11,23,29,36,44,52,95 D.29,23,11,36,44,96,52. 10.散列表的平均查找长度 。

A.与处理冲突方法有关而与表的长度无关B.与处理冲突方法无关而与表的长度有关C.与处理冲突方法有关且与表的长度有关D.与处理冲突填色关且与表的长度无关 三．填空题

1.衡量查找算法性能好坏的主要标准是 。

2.对二叉排序树进行 遍历，可得到按关键字从小到大排列的序列。 3.在Hash函数H(key)=k%p中，p应取 。

4.对于二叉排序树的查找，若根结点元素的键值大于被查找元素的值，则应该在二叉排序树的 上继续查找。 5.评价Hash函数的标准是 。

6.在各种查找方法中，其平均查找长度与结点个数n无关的查找方法是 。

7.设在有序表A[0..19]中进行二分法查找，比较一次查找成功的结点数是 。比较二次查找成功的结点为数 。比较三次查找成功的结点数为 ，比较四次查找成功的结点数为 。比较五次查找成功的结点数为 。平均查找长度为 。 8.采用二分法查找，应选择 方式的存储结构。

9.在线性表的Hash存储中，处理冲突有 和 两类。当装填因子一定时，采用链地址法解决冲突比采用开放定址处理冲突的平均检索长度要 。

10.二叉排序树的查找效率与树的形态有关。当二叉排序树退化为单支树时，查找算法退化为 查找，其中平均查找长度为 。 四．简答题

1.将整数序列{4，5，7，2，1，3，6}中的数依次插入到一棵空的平衡二叉树中，试构造相应的平衡二叉树，要求用图形给出构造过程，不需编写程序。

2.已知一个有序表{12,17,23,34,46,49,61,82,89,114,133}，写出利用二分法查找89的过程。

3.线性表关键字集合{87,25,310,8,27,132,68,95,187,123,70,63,47}，共13个元素，已知Hash函数为：H(k)=k，采用链地址法处理冲突，设计出链表结构。

4.设关键值集合为{19,7,8,23,16,25,12,26,38,3}，Hash表的长度为13，用线性探测法解决冲突，画出其Hash表。

5.设有一组关键字{19,1,23,14,55,20,84,27,68,11,10,77}，设Hash函数为hash(key)=key mod 13。采用开放定址法的二次探测再hash方法解决冲突，试在0-18的hash地址空间中对该关键字序列构造hash表。 6.编写一算法，实现在带头结点的单链表上顺序查找功能。

7.利用二分查找算法在一个有序表中插入一个元素，并保持表的有序性。 8.编写一递归算法，从大到小输出二叉排序树中所有其值不小于x的关键字。

第九章 习题

一。判断题

1.如果某种排序算法是不稳定的，则该方法无实际价值。（） 2.对n个记录进行冒泡排序，所需的平均时间是O(nlog2n)。（） 3.对n个采用冒泡法排序，最坏情况下所需要的时间为O(n2)。（） 4.{101,88,46,70,34,39,45,58,66,10}是大顶堆。（）

5.在所有排序算法中，快速排序的速度最快，所需的辅助存储空间也最少。（）

19

6.在一个小顶堆中，最大值的结点一定是一个叶子结点。（） 7.若关键字的初始排序杂乱无序，则排序效率低。（）

8.只有在线性表的初始状态为逆序排列的情况下，冒泡排序过程中元素的移动次数才会达到最大值。（） 9.对n个元素进行快速排序，在进行第一次分组时，关键字的比较次数n-1次。（） 10.对一个堆，按二叉树层次进行遍历就可以得到一个有序序列。（） 二．选择题

1.以下排序方法中，某一趟结束后未必能选出一个元素放在其最终位置上的是 。 A.堆排序 B.冒泡排序 C.直接插入排序 D.快速排序

2.依次将待排序序列中的元素和有序子序列合并为一个新的有这辈子子序列的排序方法是 。 A.快速排序 B.插入排序 C.冒泡排序 D.堆排序

3.若表R在排序前已按键值递增顺序排序，则 排序法的比较次数最少。 A.直接插入排序 B.快速排序 C.归并排序 D.选择排序

4.在下列排序中，关键字的比较次数与记录的初始排列次序无关的是 。 A.希尔排序 B.冒泡排序 C.插入排序 D.选择排序 5.快速排序法在 情况下不利于发挥其特点。

A.待排序序列数据量太大 B.待排序序列中含有多个相同值 C.待排序序列基本有序 D.待排序序列数据个数为奇数 6.待排序数据序列中有100个元素，仅要求求出其中最小的十个元素，采用 排序方法最节省时间。 A.堆排序 B.希尔排序C.快速排序 D.直接选择排序

7.若一组记录的排序码为{46,79,56,38,40,84}，则利用堆排序方法排序时建立的初堆为 。 A.79,46,56,38,40,80 B.84,79,56,38,40,46 C.84,79,56,46,40,38 D.84,56,79,40,46,38

8. 若一组记录的排序码为{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

9.稳定排序方法是指在排序过程中，关键字值相同的不同记录间的前后相对位置 。 A.保持不变 B.变为相反 C.不定 D.无关 10.以下排序方法中， 是不稳定的。

A. 折半插入排序 B.直接插入排序 C.冒泡排序 D.快速排序 11.以下排序方法中， 是稳定的。

A.选择排序 B. 折半插入排序 C. 快速排序 D. 堆排序 12.直接插入法排序的时间复杂度为 。 A.O(log2n) B.O(n) C.O(nlog2n) D.O(n2)

13.待排序记录基本有序的情况下，以下排序方法中，效率最高的是 。 A.插入排序 B.选择排序 C.快速排序 D.归并排序

14.下述几种排序方法中，要求内存量最大的是 。 A.插入排序 B.归并排序 C.选择排序 D.冒泡排序 15.在对n个元素进行快速排序的过程中，第一次划分最多需要移动 次元素（包括开始将基准元素移到临时变量的那一次）。

A.n/2 B.n-1 C.n D.n+1

三．填空题

1.在排序前后，关键字值相等的不同记录间的前后相对位置 的排序方法称之为稳定的排序方法。

2.在堆排序、快速排序和归并排序中，若只从存储空间考虑，则应首先选取 方法，其次选取 方法，最后选取 方法。若只从排序结果的稳定性考虑，则应选取 方法；若只从平均情况下排序最快考虑，则应选择取 方法；若只从最坏情况下排序最快并且要节省内存考虑，则应选取 方法。

3.对n个元素进行冒泡排序时，最少的比较次数是 。 4.归并排序的时间复杂度是 。

5.每次从无序表中取出一个元素，把它插入到有序子表中的适应位置，此种排序方法叫做

20

排序；每次从无序子表中挑选一个最小或最大元素，把它交换到有序表的一端， 此种方法叫做排序 。

6.每次直接或通过基准元素间接比较两个元素，若出现逆序排列时就交换它们的位置，此种方法做 排序；每次使两个相邻的有序表合并成一个有序表的排序方法叫做 排序。

7.在内部排序中，平均比较次数最少的是 ，要求附加存储空间最大的是 ，排序时不稳定的是 、 、 、 。

8. 排序是对序列中的元素通过适当的位置交换将有关元素一次性地放置在其最终位置上。

9.在对一组记录{50,40,95,20,15,70,60,45,80}进行直接选择排序时，第4次交换和选择后，未排序记录（即无序表）为 。

10. 在对一组记录{50,40,95,20,15,70,60,45,80}进行直接插入排序时，当把第7个记录60插入到有序表时，为寻找插入位置需要比较 次。

11.在堆排序和快速排序中，若原始记录接近正序，则选用 。若原始记录无序，则最好选用 。 12.在直接插入和直接选择排序中，若初始数据基本有序，则选用 ，若初始数据基本反序，则选用 。 四．简答题

1.某整型数组R的10个元素依次为{6,2,9,7,3,8,4,5,0,10}。用下列各排序方法，将R中元素从小到大排序。 （1）取第一个元素6作为划分数据，试写出快速排序第一次划分操作后R中的结果。 （2）用堆排序（大顶堆），试写出将第一个选出的数据交换到R的最后位置上，再将其余元素调整成堆后R中的结果。 2.已知序列{70,83,100,105,10,32,7,9}，请给出采用直接插入排序法对该序列作升序排序时的每一趟结果。 3.已知序列{10,18,4,3,6,12,1,9,15,8},请给出采用希尔排序法对该序列做升序排序的每一趟结果。 4. 已知序列{10,18,4,3,6,12,1,9,15,8},请给出采用归并排序法对该序列做升序排序的每一趟结果。 5.判断下列序列是否为堆（小根或大根堆），若不是，则将其调整为堆： （1）（100,86,73,66,39,42,57,35,21） （2）（12,70,33,65,24,56,48,92,86,33）

6.已知序列{57,40,38,11,13,34,48,75,6,19,9,7}，采用堆排序法对该序列做降序排序时的每一趟过程。 7.设计一个直接选择排序算法，将数组中的元素按降序排列。 8.设计一个算法，在n个元素的堆中增加一个元素且调整为堆。

21

排序；每次从无序子表中挑选一个最小或最大元素，把它交换到有序表的一端， 此种方法叫做排序 。

6.每次直接或通过基准元素间接比较两个元素，若出现逆序排列时就交换它们的位置，此种方法做 排序；每次使两个相邻的有序表合并成一个有序表的排序方法叫做 排序。

7.在内部排序中，平均比较次数最少的是 ，要求附加存储空间最大的是 ，排序时不稳定的是 、 、 、 。

8. 排序是对序列中的元素通过适当的位置交换将有关元素一次性地放置在其最终位置上。

9.在对一组记录{50,40,95,20,15,70,60,45,80}进行直接选择排序时，第4次交换和选择后，未排序记录（即无序表）为 。

10. 在对一组记录{50,40,95,20,15,70,60,45,80}进行直接插入排序时，当把第7个记录60插入到有序表时，为寻找插入位置需要比较 次。

11.在堆排序和快速排序中，若原始记录接近正序，则选用 。若原始记录无序，则最好选用 。 12.在直接插入和直接选择排序中，若初始数据基本有序，则选用 ，若初始数据基本反序，则选用 。 四．简答题

1.某整型数组R的10个元素依次为{6,2,9,7,3,8,4,5,0,10}。用下列各排序方法，将R中元素从小到大排序。 （1）取第一个元素6作为划分数据，试写出快速排序第一次划分操作后R中的结果。 （2）用堆排序（大顶堆），试写出将第一个选出的数据交换到R的最后位置上，再将其余元素调整成堆后R中的结果。 2.已知序列{70,83,100,105,10,32,7,9}，请给出采用直接插入排序法对该序列作升序排序时的每一趟结果。 3.已知序列{10,18,4,3,6,12,1,9,15,8},请给出采用希尔排序法对该序列做升序排序的每一趟结果。 4. 已知序列{10,18,4,3,6,12,1,9,15,8},请给出采用归并排序法对该序列做升序排序的每一趟结果。 5.判断下列序列是否为堆（小根或大根堆），若不是，则将其调整为堆： （1）（100,86,73,66,39,42,57,35,21） （2）（12,70,33,65,24,56,48,92,86,33）

6.已知序列{57,40,38,11,13,34,48,75,6,19,9,7}，采用堆排序法对该序列做降序排序时的每一趟过程。 7.设计一个直接选择排序算法，将数组中的元素按降序排列。 8.设计一个算法，在n个元素的堆中增加一个元素且调整为堆。

21

本文来源：https://www.bwwdw.com/article/qmig.html