数据结构自测卷答案 - 图文

第一章概论 自测题答案 姓名 班级

一、填空题（每空1分，共33分）

1. 一个计算机系统包括 硬件系统 和 软件系统 两大部分。

2. 一台计算机中全部程序的集合，称为这台计算机的 软件资源 /（系统） 。

3. 计算机软件可以分为 系统 软件和 应用 软件两大类。科学计算程序包属于 应用软件 ，诊断程序属于 系统软件（工具） 。

4. 一种用助忆符号来表示机器指令的操作符和操作数的语言是 汇编语言 。

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

6. 数据结构被形式地定义为（D, R），其中D是 数据元素 的有限集合，R是D上的 关系 有限集合。

7. 数据结构包括数据的 逻辑结构 、数据的 存储结构 和数据的 运算 这三个方面的内容。 8. 数据结构按逻辑结构可分为两大类，它们分别是 线性结构 和 非线性结构 。

9. 线性结构中元素之间存在一对一关系，树形结构中元素之间存在一对多关系，图形结构中元素之间存在多对多关系。

10． 在线性结构中，第一个结点 没有 前驱结点，其余每个结点有且只有 1个前驱结点；最后一个结点 没有 后续结点，其余每个结点有且只有1个后续结点。

11. 在树形结构中，树根结点没有 前驱 结点，其余每个结点有且只有 1 个前驱结点；叶子结点没有 后续 结点，其余每个结点的后续结点数可以任意多个 。

12. 在图形结构中，每个结点的前驱结点数和后续结点数可以 任意多个 。

13．数据的存储结构可用四种基本的存储方法表示，它们分别是顺序 、 链式 、 索引 和 散列 。 14. 数据的运算最常用的有5种，它们分别是插入 、 删除、修改、 查找 、排序。 15. 一个算法的效率可分为 时间 效率和 空间 效率。

16. 〖00年省统考〗任何一个C程序都由 一个主函数 和若干个被调用的其它函数组成。

17. 【00年省统考题】变量一经说明，就确定该变量的取值范围（即存储单元）及 确定变量所允许的运算 。

二、单项选择题（每小题1分，共15分） （ B ） 1. 通常所说的主机是指∶

A) CPU B) CPU和内存 C) CPU、内存与外存 D) CPU、内存与硬盘

（ C ）2. 在计算机内部，一切信息的存取、处理和传送的形式是∶

A) ACSII码 B) BCD码 C)二进制 D)十六进制

（ D ）3. 软件与程序的区别是∶

A) 程序价格便宜、软件价格昂贵；

B) 程序是用户自己编写的，而软件是由厂家提供的；

C) 程序是用高级语言编写的，而软件是由机器语言编写的； D) 软件是程序以及开发、使用和维护所需要的所有文档的总称，而程序只是软件的一部分。

（ C ）4. 所谓“裸机”是指∶

A) 单片机 B)单板机 C) 不装备任何软件的计算机 D) 只装备操作系统的计算

机

（ D ）5. 应用软件是指∶

A)所有能够使用的软件 B) 能被各应用单位共同使用的某种软件 C)所有微机上都应使用的基本软件 D) 专门为某一应用目的而编制的软件

（ ＊A ）6. 〖00年省统考〗C语言中的常量可分为整型常量、实型常量、字符型常量及 (枚举) 四种。

（A） 符号常量 （B）长整型常量 （C） 逻辑常量 （D）二进制整数

（ ＊C ）7. 编译程序的功能是∶

A)发现源程序中的语法错误 B)改正源程序中的语法错误

C)将源程序编译成目标程序 D)将某一高级语言程序翻译成另一种高级语言程序

（ A ）8. 系统软件中最重要的是∶

A) 操作系统 B) 语言处理系统 C) 工具软件 D) 数据库管理系统

1

（ C ）9. 可移植性最好的计算机语言是∶

A) 机器语言 B)汇编语言 C) 高级语言 D) 自然语言

（ B ）10. 非线性结构是数据元素之间存在一种：

A）一对多关系 B）多对多关系 C）多对一关系 D）一对一关系

（ C ）11. 数据结构中，与所使用的计算机无关的是数据的 结构；

A) 存储 B) 物理 C) 逻辑 D) 物理和存储

（ C ）12. 算法分析的目的是：

A) 找出数据结构的合理性 B) 研究算法中的输入和输出的关系 C) 分析算法的效率以求改进 D) 分析算法的易懂性和文档性

（ A ）13. 算法分析的两个主要方面是：

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

C) 可读性和文档性 D) 数据复杂性和程序复杂性

（ C ）14. 计算机算法指的是：

A) 计算方法 B) 排序方法 C) 解决问题的有限运算序列 D) 调度方法

（ B ）15. 计算机算法必须具备输入、输出和 等5个特性。

A) 可行性、可移植性和可扩充性 B) 可行性、确定性和有穷性 C) 确定性、有穷性和稳定性 D) 易读性、稳定性和安全性

三、简答题（每小题3分,共9分）

1．我们知道计算机只能执行机器指令，为什么它能运行用汇编语言和高级语言编写的程序？ 答：靠汇编程序将汇编语言或高级语言翻译转换为目标程序（即机器语言）。 2.【严题集1.2②】数据结构和数据类型两个概念之间有区别吗？

答：简单地说，数据结构定义了一组按某些关系结合在一起的数组元素。数据类型不仅定义了一组带结构的数据元素，而且还在其上定义了一组操作。 3. 简述线性结构与非线性结构的不同点。

答：线性结构反映结点间的逻辑关系是 一对一的，非线性结构反映结点间的逻辑关系是多对多的。 四、〖00年统考题〗阅读下列C程序段，写出相应的执行结果（每小题4分，共8分） 1. printf(“Input x”);

2. long int fact(n) scanf(“%d”,&x);

if (x<=30)

int n;

if(x>20) y=x;

{long f; else if (x>10) y=2*x;

if (x>0&&x<30)printf(“x=%d,y=%d”,x,y);

if(n>1)f=n*fact(n-1);

else printf(“输入数据错！”);

else f=1; 试写出当x分别为18，8时的执行结果。

答：运行结果为：x=18，y=36

return(f);

x=8，y=运行前的值， 且从x＝30开始为数据错

}

main()

{int n;

long y;

n=5;

y=fact(n);

printf(“%d,%ld\\n”,n,y); }

2

五、【严题集1.8④】分析下面各程序段的时间复杂度（每小题5分，共20分）

2. s=0; 1. for (i=0; i

for i=0; i

for(j=0; j

s+=B[i][j]; 答：O（m*n）

sum=s;

2

答：O（n）

3. x=0; for(i=1; i

六、设有数据逻辑结构S=（D,R），试按各小题所给条件画出这些逻辑结构的图示，并确定相对于关系R，哪些结点是开始结点，哪些结点是终端结点？（每小题5分，共15分） 1. 【严蔚敏习题集P7 1.3②】

D={d1,d2,d3,d4} R={(d1,d2),(d2,d3),(d3,d4) }

答： d1→d2→d3→d4 d1—无直接前驱，是首结点 d4—无直接后继是尾结点 2. D={d1,d2,?,d9}

R={(d1,d2),(d1,d3),(d3,d4),(d3,d6),(d6,d8),(d4,d5), (d6,d7),(d8,d9) }

答： 此图为树形结构 d1—无直接前驱，是根结点 d2,d5,d7,d9—无直接后继是叶子结点 3. D={d1,d2,?,d9}

R={(d1,d3),(d1,d8),(d2,d3),(d2,d4),(d2,d5),(d3,d9), (d5,d6),(d8,d9),(d9,d7), (d4,d7), (d4,d6)}

答： 此图为图形结构 d1，d2—无直接前驱，是开始结点 d6,d7—无直接后继是终端结点

(2) (3)

第2章 自测卷答案 姓名 班级

一、填空（每空1分，共13分）

1. 【严题集2.2①】在顺序表中插入或删除一个元素，需要平均移动 表中一半元素，具体移动的元素个数与 表长和该元素在表中的位置 有关。

3

2. 线性表中结点的集合是 有限 的，结点间的关系是 一对一 的。

3. 向一个长度为n的向量的第i个元素(1≤i≤n+1)之前插入一个元素时，需向后移动 n-i+1 个元素。 4. 向一个长度为n的向量中删除第i个元素(1≤i≤n)时，需向前移动 n-i 个元素。

5. 在顺序表中访问任意一结点的时间复杂度均为 O(1) ，因此，顺序表也称为 随机存取 的数据结构。 6. 【严题集2.2①】顺序表中逻辑上相邻的元素的物理位置 必定相邻。单链表中逻辑上相邻的元素的物理位置 不一定 相邻。 7. 【严题集2.2①】在单链表中，除了首元结点外，任一结点的存储位置由 其直接前驱结点的链域的值 指示。

8． 在n个结点的单链表中要删除已知结点*p，需找到它的前驱结点的地址，其时间复杂度为O（n）。 二、判断正误（在正确的说法后面打勾，反之打叉）（每小题1分，共10分） （ × ）1. 链表的每个结点中都恰好包含一个指针。

答：错误。链表中的结点可含多个指针域，分别存放多个指针。例如，双向链表中的结点可以含有两个指针域，分别存放指向其直接前趋和直接后继结点的指针。

（ × ）2. 链表的物理存储结构具有同链表一样的顺序。错，链表的存储结构特点是无序，而链表的示意图有序。

（ × ）3. 链表的删除算法很简单，因为当删除链中某个结点后，计算机会自动地将后续的各个单元向

前移动。错，链表的结点不会移动，只是指针内容改变。

（ × ）4. 线性表的每个结点只能是一个简单类型，而链表的每个结点可以是一个复杂类型。

错，混淆了逻辑结构与物理结构，链表也是线性表！且即使是顺序表，也能存放记录

型数据。

（ × ）5. 顺序表结构适宜于进行顺序存取，而链表适宜于进行随机存取。

错，正好说反了。顺序表才适合随机存取，链表恰恰适于“顺藤摸瓜”

（ × ）6. 顺序存储方式的优点是存储密度大，且插入、删除运算效率高。

错，前一半正确，但后一半说法错误，那是链式存储的优点。顺序存储方式插入、删除运算效率较低，在表长为n的顺序表中，插入和删除一个数据元素，平均需移动表长一半个数的数据元素。

（ × ）7. 线性表在物理存储空间中也一定是连续的。

错，线性表有两种存储方式，顺序存储和链式存储。后者不要求连续存放。

（ × ）8. 线性表在顺序存储时，逻辑上相邻的元素未必在存储的物理位置次序上相邻。

错误。线性表有两种存储方式，在顺序存储时，逻辑上相邻的元素在存储的物理位置次序上也相邻。

（ × ）9. 顺序存储方式只能用于存储线性结构。

错误。顺序存储方式不仅能用于存储线性结构，还可以用来存放非线性结构，例如完全二叉树是属于非线性结构，但其最佳存储方式是顺序存储方式。（后一节介绍） （ × ）10. 线性表的逻辑顺序与存储顺序总是一致的。

错，理由同7。链式存储就无需一致。

三、单项选择题（每小题1分，共10分）

（ C ）1．数据在计算机存储器内表示时，物理地址与逻辑地址相同并且是连续的，称之为：

（A）存储结构 （B）逻辑结构 （C）顺序存储结构 （D）链式存储结构

（ B ）2.一个向量第一个元素的存储地址是100，每个元素的长度为2，则第5个元素的地址是

（A）110 （B）108 （C）100 （D）120

（ A ）3. 在n个结点的顺序表中，算法的时间复杂度是O（1）的操作是：

（A） 访问第i个结点（1≤i≤n）和求第i个结点的直接前驱（2≤i≤n） （B） 在第i个结点后插入一个新结点（1≤i≤n） （C） 删除第i个结点（1≤i≤n） （D） 将n个结点从小到大排序

（ B ）4. 向一个有127个元素的顺序表中插入一个新元素并保持原来顺序不变，平均要移动 个元素

（A）8 （B）63.5 （C）63 （D）7

（ A ）5. 链接存储的存储结构所占存储空间：

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

4

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

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

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

（ B ）6. 链表是一种采用 存储结构存储的线性表；

（A）顺序 （B）链式 （C）星式 （D）网状

（ D ）7. 线性表若采用链式存储结构时，要求内存中可用存储单元的地址:

（A）必须是连续的 （B）部分地址必须是连续的 （C）一定是不连续的 （D）连续或不连续都可以

（ B ）8． 线性表Ｌ在 情况下适用于使用链式结构实现。

（Ａ）需经常修改Ｌ中的结点值 （Ｂ）需不断对Ｌ进行删除插入 （Ｃ）Ｌ中含有大量的结点 （Ｄ）Ｌ中结点结构复杂

（ C ）9． 单链表的存储密度

（Ａ）大于1； （Ｂ）等于1； （Ｃ）小于1； （Ｄ）不能确定

（ B ）10． 设a1、a2、a3为3个结点，整数P0，3，4代表地址，则如下的链式存储结构称为

P0 3 4 ? A3 0 a2 4 P0 ? a1 3 ?

（Ａ）循环链表 （Ｂ）单链表 （Ｃ）双向循环链表 （Ｄ）双向链表

四、简答题（每小题5分，共10分）

1. 【严题集2.3②】试比较顺序存储结构和链式存储结构的优缺点。在什么情况下用顺序表比链表好？ 答：① 顺序存储时，相邻数据元素的存放地址也相邻（逻辑与物理统一）；要求内存中可用存储单元的地址必须是连续的。

优点：存储密度大（＝1？），存储空间利用率高。缺点：插入或删除元素时不方便。

②链式存储时，相邻数据元素可随意存放，但所占存储空间分两部分，一部分存放结点值，另一部分存放表示结点间关系的指针

优点：插入或删除元素时很方便，使用灵活。缺点：存储密度小（<1），存储空间利用率低。 顺序表适宜于做查找这样的静态操作；链表宜于做插入、删除这样的动态操作。 若线性表的长度变化不大，且其主要操作是查找，则采用顺序表；

若线性表的长度变化较大，且其主要操作是插入、删除操作，则采用链表。

2 .【严题集2.1①】描述以下三个概念的区别：头指针、头结点、首元结点（第一个元素结点）。在单链表中设置头结点的作用是什么？

答：首元结点是指链表中存储线性表中第一个数据元素a1的结点。为了操作方便，通常在链表的首元结点之前附设一个结点，称为头结点，该结点的数据域中不存储线性表的数据元素，其作用是为了对链表进行操作时，可以对空表、非空表的情况以及对首元结点进行统一处理。头指针是指向链表中第一个结点（或为头结点或为首元结点）的指针。若链表中附设头结点，则不管线性表是否为空表，头指针均不为空。否则表示空表的链表的头指针为空。这三个概念对单链表、双向链表和循环链表均适用。是否设置头结点，是不同的存储结构表示同一逻辑结构的问题。

头结点 ? head data link 头指针 首元结点 简而言之，

头指针是指向链表中第一个结点（或为头结点或为首元结点）的指针； 头结点是在链表的首元结点之前附设的一个结点；数据域内只放空表标志和表长等信息（内放头指针？那还得另配一个头指针！！！）

首元素结点是指链表中存储线性表中第一个数据元素a1的结点。 五、【软考题】线性表具有两种存储方式，即顺序方式和链接方式。现有一个具有五个元素的线性表L={23，17，47，05，31}，若它以链接方式存储在下列100～119号地址空间中，每个结点由数据（占2个字节）和指针（占2个字节）组成，如下所示：

5

05 U 17 X 23 V 31 Y 47 Z ^ ^ 100 120

其中指针X，Y，Z的值分别为多少？该线性表的首结点起始地址为多少？末结点的起始地址为多少？（10分）

答：X= 116 Y= 0 Z= 100 首址= 108 末址= 112 六、阅读分析题（10分）

【严题集2.10②】指出以下算法中的错误和低效（即费时）之处，并将它改写为一个既正确又高效的算法。

Status DeleteK(SqList&a, int i, int k){

//本过程从顺序存储结构的线性表a中删除第i个元素起的k个元素

if ( i<1 || k<0 || i+k> a.length ) return INFEASIBLE; //参数不合法

else{

for(count = 1; count

//删除一个元素

for ( j = a.length; j>=i+1; j--) a.elem[j-1] = a.elem[j];

a.length - -; }

return OK;

} // DeleteK

注：上题涉及的类型定义如下： # define LIST INIT SIZE 100 # define LISTINCREMENT 10 typedef struct { Elem Type *elem; //存储空间基址 Int length; //当前长度 Int listsize; //当前分配的存储容量 }SqList;

答：错误有两处：

① 参数不合法的判别条件不完整。例如表长为10，若从第一位置（i=1）删除10个元素（k=10）,要求合

理但会被判为非法。

合法的入口参数条件为（0 a.length ) return INFEASIBLE 改为：if (！（（0

第二个FOR语句中，元素前移的次序错误。应将for ( j = a.length; j>=i+1; j--) a.elem[j-1] = a.elem[j]; 改为for (j>=i+1; j = a.length; j++) a.elem[j-1] = a.elem[j]; 七、编程题（每题10分，共40分）

1. 【徐士良题集，2002年1月省统考题】写出在顺序存储结构下将线性表逆转的算法，要求使用最少的附加空间。

invsl(n,a) 解：输入：长度为n的线性表数组A(1:n)

int n; 输出：逆转后的长度为n的线性表数组A(1:n)。

ET a[]; C语言描述如下（其中ET为数据元素的类型）：

{int k;

ET t;

for (k=1; k<=n/2; k++)

{t=a[k-1]; a[k-1]=a[n-k]; a[n-k]=t;}

return;

2. 【严题集2.6②】已知L是无表头结点的单链表，} 且P

6 结点既不是首元结点，也不是尾元结点，请写出在P结点后插入S结点的核心语句序列。 答：此题答案不唯一，但若从已给定序列中挑选，则限制颇多。 (7) Q=P; (11) P=L; 已知P结点，则不必“顺藤摸瓜”，直接链(8) while(P->next!=Q)P=P->next; 接即可。 (10) P=Q; (4) S->next=P->next; (4) S->next=P->next; (1) P->next=S; P->next=S;

3. 编写程序，将若干整数从键盘输入，以单链表形式存储起来，然后计算单链表中结点的个数（其中指针P指向该链表的第一个结点）。 注：统计结点个数是【省统考样题】的要求，也是教材P60 4-6计算链表长度的要求，编程又简单，很容易作为考题。 解：编写C程序如下(已上机通过)： 全局变量及函数提前说明： --------------------------------- #include #include

typedef struct liuyu{int data;struct liuyu*link;}test; liuyu *p,*q,*r,*head; int m=sizeof(test);

void main () /*第一步，从键盘输入整数，不断添加到链表*/ {int i;

head=(test*)malloc(m); /*m=sizeof(test);*/ p=head; i=0;

while (i!=-9999)

{ printf(\ [stop by '-9999']:\scanf(\

p->data=i; /* input data is saved */ p->link=(test*)malloc(m); /*m=sizeof(test));*/ q=p;

p=p->link; }

q->link=NULL; /*原先用p->link=NULL似乎太晚！*/

p=head; i=0; /*统计链表结点的个数并打印出来*/ while (p->link!=NULL) {printf(\p=p->link; i++; }

printf(\ i-1); /*结点的个数不包括-9999*/ }

0301陈建武：

3.程序中统计结点数应是i个,而不是i-1.

假设链表表长为n,i从0开始,则在统计某一结点后 i 加一,此时p已指向下一个结点, 第一结点统计结束,i为1,p指向第二结点

即当p指向尾结点(第n个结点)时i的值为n-1,while循环条件不符(指针域为null),退出循环,即得统计的结点数,为n-1.所以 i 的值就是结点数,不必再减一

7

4. 请编写26个字母按特定字母值插入或删除的完整程序，可自行选用顺序存储或链表结构。 答：

#include /*全局变量及函数提前说明：*/ #include

typedef struct liuyu{char data;struct liuyu*link;}test; liuyu *p,*q,*r,*head;

int L; /*元素的个数*/ int m=sizeof(test);

void build(); /* 主函数中会被调用的函数应当预先说明 */ void display();

int insert_char(char,char); /*插入一个字母，在第字母Y之前，若无字母则加到末尾*/ int delet_char(char); /* 删除元素X，注意保存X的前趋元素指针！ */ /*---------------------------------------------------------*/

void build() /*字母链表的生成*/ {int i;

head=(test*)malloc(m); /*m=sizeof(test);*/ p=head;

for(i=1;i

{ p->data=i+'a'-1; /* 'a'也可用其ASCII码97来表示 */ p->link=(test*)malloc(m); /*m=sizeof(test));*/ p=p->link; } p->data=i+'a'-1; p->link=NULL; }

/*---------------------------------------------------------*/ void display() /*字母链表的输出*/ {p=head;

while (p->link!=NULL) { printf(\p=p->link; }

printf(\}

/*---------------------------------------------------------*/

int insert_char(char X,char Y) /*插入一个字母X在某个字母Y之前，若找不到Y字母则加到末尾*/ {p=head;

r=(test*)malloc(m); r->data=X;

if(head->data==Y) { head=r;

r->link=p; }

else{ while((p->data!=Y)&&(p->link!=NULL)) {q=p; p=p->link;} if(p->data==Y) { q->link=r; r->link=p; } else{p->link=r;r->link=NULL;} } L++;

return(0); }

/*---------------------------------------------------------*/

int delet_char(char X) /* 删除元素X，注意保存X的前趋元素指针！ */ { p=head;

8

if(head->data==X){head=head->link;free(p);} else{ while((p->data!=X)&&(p->link!=NULL)) {q=p; p=p->link;} if(p->data==X)

{ q->link=p->link; free(p); } else return(-1); } L--;

return(0); }

/*---------------------------------------------------------*/ void main(void) /*字母线性表的生成和输出*/ { L=26; build(); display();

printf(\display();

printf(\display(); }

附：屏幕上显示的执行结果是：

a b c d e f g h i j k l m n o p q r s t u v w x y z insert return value=0

a b c d 9 e f g h i j k l m n o p q r s t u v w x y z L delete return value=0

a b c d e f g h i j k l m n o p q r s t u v w x y L

0301陈建武修改意见：

一. display()函数代码可优化为四行

void display() /*字母链表的输出*/ {p=head;

while (p->link!=NULL)//改为while(p),因为当p指向尾结点时,p不为null,条件成立循环,

//printf(),然后p被赋值为null,此时循环条件不符退出,正好. { printf(\p=p->link; }

printf(\//用while(p),此行可删 }

二.对int insert_char(char X,char Y) ,若用带头结点的链表,代码可减为10行 我的程序如下(若参数没有slist p,代码要多一行,让q指向头指针)

void InsertFind(slist p,char insertchar,char insertpos)//字母insertpos前插入字母insertchar {

slist pprior,newnode; //newnode新结点,pprior为插入位置结点的直接前驱 newnode = new liuyu; //为新结点分配内存

newnode->data = insertchar; //对结点数据域初始化 while(p) //当p指向尾结点时最后一次循环 {

pprior = p; //pprior从头指针开始,指向p的直接前驱

9

p = p->next; //p从首元结点开始,不断前移 ,直至最后,p为null

if(p&&(p->data == insertpos)) //当p为null或者结点p的数据域为所要插入的字母, break; //则退出循环 }

newnode->next = pprior->next; //在找到的位置前插入 pprior->next = newnode; }

对删除结点的操作,若有头结点,同样可以减少代码,由此可见创建一个头结点对简化程序有很大的帮助. 上面的观点,仅供参考,不对之处,请指教!

第3章 栈和队列 自测卷答案 姓名 班级

一、填空题（每空1分，共15分）

1. 【李春葆】向量、栈和队列都是 线性 结构，可以在向量的 任何 位置插入和删除元素；对于栈只能在 栈顶 插入和删除元素；对于队列只能在 队尾 插入和 队首 删除元素。 2. 栈是一种特殊的线性表，允许插入和删除运算的一端称为 栈顶 。不允许插入和删除运算的一端称为 栈底 。

3. 队列 是被限定为只能在表的一端进行插入运算，在表的另一端进行删除运算的线性表。 4. 在一个循环队列中，队首指针指向队首元素的 前一个 位置。 5. 在具有n个单元的循环队列中，队满时共有 n-1 个元素。

6. 向栈中压入元素的操作是先 移动栈顶指针 ，后 存入元素 。

7. 从循环队列中删除一个元素时，其操作是 先 移动队首指针 ，后 取出元素 。 8. 〖00年统考题〗带表头结点的空循环双向链表的长度等于 0 。 解：

head L=head 头结点 R=head

二、判断正误（判断下列概念的正确性，并作出简要的说明。）（每小题1分，共10分）

（ × ）1. 线性表的每个结点只能是一个简单类型，而链表的每个结点可以是一个复杂类型。

错，线性表是逻辑结构概念，可以顺序存储或链式存储，与元素数据类型无关。

（ × ）2. 在表结构中最常用的是线性表，栈和队列不太常用。

错，不一定吧？调用子程序或函数常用，CPU中也用队列。

（ √ ）3. 栈是一种对所有插入、删除操作限于在表的一端进行的线性表，是一种后进先出型结构。 （ √ ）4. 对于不同的使用者，一个表结构既可以是栈，也可以是队列，也可以是线性表。

正确，都是线性逻辑结构，栈和队列其实是特殊的线性表，对运算的定义略有不同而已。

（ × ）5. 栈和链表是两种不同的数据结构。

错，栈是逻辑结构的概念，是特殊殊线性表，而链表是存储结构概念，二者不是同类项。

（ × ）6. 栈和队列是一种非线性数据结构。

错，他们都是线性逻辑结构，栈和队列其实是特殊的线性表，对运算的定义略有不同而已。

（ √ ）7. 栈和队列的存储方式既可是顺序方式，也可是链接方式。

（ √ ）8. 两个栈共享一片连续内存空间时，为提高内存利用率，减少溢出机会，应把两个栈的栈底

分别设在这片内存空间的两端。

（ × ）9. 队是一种插入与删除操作分别在表的两端进行的线性表，是一种先进后出型结构。 错，后半句不对。

（ × ）10. 一个栈的输入序列是12345，则栈的输出序列不可能是12345。

错，有可能。

三、单项选择题（每小题1分，共20分）

（ B ）1. 〖00年元月统考题〗栈中元素的进出原则是

Ａ．先进先出 Ｂ．后进先出 Ｃ．栈空则进 Ｄ．栈满则出

（ C ）2. 〖李春葆〗若已知一个栈的入栈序列是1，2，3，?，n，其输出序列为p1，p2，p3，?，

10

（基地址）为1000，则数组A的体积（存储量）为 288 B ；末尾元素A57的第一个字节地址为 1282 ；若按行存储时，元素A14的第一个字节地址为 (8+4)×6+1000=1192 ；若按列存储时，元素A47的第一个字节地址为 (6×7＋4)×6＋1000）＝1276 。

8. 〖00年计算机系考研题〗设数组a[1?60, 1?70]的基地址为2048，每个元素占2个存储单元，若以列序为主序顺序存储，则元素a[32,58]的存储地址为 9188 。 答：考虑0行0列，（58列×61行＋32行）×2字节＋基址2048=9188？？

9. 三元素组表中的每个结点对应于稀疏矩阵的一个非零元素，它包含有三个数据项，分别表示该元素 的 行下标 、 列下标 和 元素值 。 10.求下列广义表操作的结果：

（1） GetHead【((a,b),(c,d))】=== (a, b) ; //头元素不必加括号 （2） GetHead【GetTail【((a,b),(c,d))】】=== (c,d) ; （3） GetHead【GetTail【GetHead【((a,b),(c,d))】】】=== b ; （4） GetTail【GetHead【GetTail【((a,b),(c,d))】】】=== （d） ; 二、单选题（每小题1分，共15分）

（ B ）1. 〖李〗串是一种特殊的线性表，其特殊性体现在：

Ａ．可以顺序存储 Ｂ．数据元素是一个字符 Ｃ．可以链式存储 Ｄ．数据元素可以是多个字符

（ B ）2. 〖李〗设有两个串p和q，求q在p中首次出现的位置的运算称作：

Ａ．连接 Ｂ．模式匹配 Ｃ．求子串 Ｄ．求串长

（ D ）3. 〖李〗设串s1=?ABCDEFG?，s2=?PQRST?，函数con(x,y)返回x和y串的连接串，subs(s, i, j)返回串s的从序号i开始的j个字符组成的子串，len(s)返回串s的长度，则con(subs(s1, 2, len(s2)), subs(s1, len(s2), 2))的结果串是：

Ａ．BCDEF Ｂ．BCDEFG Ｃ．BCPQRST Ｄ．BCDEFEF

解：con(x,y)返回x和y串的连接串，即 con(x,y)＝‘ABCDEFGPQRST’； subs(s, i, j)返回串s的从序号i开始的j个字符组成的子串，则

subs(s1, 2, len(s2))＝subs(s1, 2, 5)=? BCDEF?; subs(s1, len(s2), 2)＝subs(s1, 5, 2)=? EF?;

所以con(subs(s1, 2, len(s2)), subs(s1, len(s2), 2))＝con(? BCDEF?, ? EF?)之连接，即BCDEFEF

（ A ）4. 〖01年计算机系考研题〗假设有60行70列的二维数组a[1?60, 1?70]以列序为主序顺序存储，其基地址为10000，每个元素占2个存储单元，那么第32行第58列的元素a[32,58]的存储地址为 。（无第0行第0列元素）

Ａ．16902 Ｂ．16904 Ｃ．14454 Ｄ．答案A, B, C均不对

答：（57列×60行＋31行）×2字节＋10000=16902(A)

( B )5. 设矩阵A是一个对称矩阵，为了节省存储，将其下三角部分（如下图所示）按行序存放在一维数组B[ 1, n(n-1)/2 ]中，对下三角部分中任一元素ai,j(i≤j), 在一维数组B中下标k的值是：

Ａ．i(i-1)/2+j-1 Ｂ．i(i-1)/2+j Ｃ．i(i+1)/2+j-1 Ｄ．i(i+1)/2+j

解：注意B的下标要求从1开始。 先用第一个元素去套用，可能有B和C； 再用第二个元素去套用B和C，B=2而C＝3（不符）； 所以选B ?a1,1?a2,1A??????an,1?a2,2an,2??? ???an,n??6. 【91初程P78】 从供选择的答案中，选出应填入下面叙述 ？ 内的最确切的解答，把相应编号写

在答卷的对应栏内。

有一个二维数组A，行下标的范围是0到8，列下标的范围是1到5，每个数组元素用相邻的4个字节存储。存储器按字节编址。假设存储数组元素A[0,1]的第一个字节的地址是0。

存储数组A的最后一个元素的第一个字节的地址是 A 。若按行存储，则A[3,5]和A[5,3]的第一个字节的地址分别是 B 和 C 。若按列存储，则A[7,1]和A[2,4]的第一个字节的地址分别是 D 和 E 。

供选择的答案

A～E：①28 ② 44 ③ 76 ④ 92 ⑤ 108

16

⑥ 116 ⑦ 132 ⑧ 176 ⑨ 184 ⑩ 188 答案：ABCDE=8, 3, 5, 1, 6

7.【94程P12】 从供选择的答案中，选出应填入下面叙述 ？ 内的最确切的解答，把相应编号写在答卷的对应栏内。

有一个二维数组A，行下标的范围是1到6，列下标的范围是0到7，每个数组元素用相邻的6个字节存储，存储器按字节编址。那么，这个数组的体积是 A 个字节。假设存储数组元素A[1,0]的第一个字节的地址是0，则存储数组A的最后一个元素的第一个字节的地址是 B 。若按行存储，则A[2,4]的第一个字节的地址是 C 。若按列存储，则A[5,7]的第一个字节的地址是 D 。 供选择的答案

A～D：①12 ② 66 ③ 72 ④ 96 ⑤ 114 ⑥ 120

⑦ 156 ⑧ 234 ⑨ 276 ⑩ 282 （11）283 （12）288 答案：ABCD=12, 10, 3, 9

三、简答题（每小题5分，共15分）

1. KMP算法的设计思想是什么？它有什么优点？

2. （软件技术？）已知二维数组Am,m采用按行优先顺序存放，每个元素占K个存储单元，并且第一个元素的存储地址为Loc(a11)，请写出求Loc(aij)的计算公式。如果采用列优先顺序存放呢？ 解：公式教材已给出，此处虽是方阵，但行列公式仍不相同；

按行存储的元素地址公式是： Loc(aij)= Loc(a11) +[ (i-1)*m+(j-1) ] * K 按列存储的元素地址公式是： Loc(aij)= Loc(a11) +[ (j-1)*m+(i-1) ] * K

3.【全国专升本资格考试】递归算法比非递归算法花费更多的时间，对吗？为什么？

答：不一定。时间复杂度与样本个数n有关，是指最深层的执行语句耗费时间，而递归算法与非递归算法在最深层的语句执行上是没有区别的，循环的次数也没有太大差异。仅仅是确定循环是否继续的方式不同，递归用栈隐含循环次数，非递归用循环变量来显示循环次数而已。

四、计算题（每题5分，共20分）

1. 设s=?I AM A STUDENT?, t=?GOOD?, q=?WORKER?, 求Replace(s,?STUDENT?,q) 和 Concat(SubString(s,6,2), Concat(t,SubString(s,7,8)))。 解：① Replace(s,?STUDENT?,q)＝’I AM A WORKER’ ② 因为 SubString(s,6,2)＝‘A ’；SubString(s,7,8)＝‘ STUDENT’ Concat(t,SubString(s,7,8))＝?GOOD STUDENT?

所以Concat(SubString(s,6,2), Concat(t,SubString(s,7,8)))＝‘A GOOD STUDENT’

2. 【严题集4.8②】 已知主串s=?ADBADABBAABADABBADADA?,模式串pat=?ADABBADADA?。写出模式串的nextval函数值，并由此画出KMP算法匹配的全过程。 解：（由演示程序得知）nextval函数值为0 1 0 2 1 0 1 0 4 0 在第12个字符处发现匹配！ s=?ADBADABBAABADABBADADA? pat=?ADABBADADA?

3. （P60 4-18）用三元组表表示下列稀疏矩阵：

17

?00000000??00000000??00000?2????000090??03000800?????00000000? (2)?000000? (1)????00060000?005000?????000000??00000000????00000005?000030?????20000000?解：参见填空题4. 三元素组表中的每个结点对应于稀疏矩阵的一个非零元素，它包含有三个数据项，分别表示该元素的 行下标 、 列下标 和 元素值 。 所以（1）可列表为： （2）可列表为： 8 8 5 6 6 4 3 2 3 1 6 -2 3 6 8 2 5 9 5 4 6 4 3 5 7 8 5 6 5 3 8 1 2 4. （P60 4-19）下列各三元组表分别表示一个稀疏矩阵，试写出它们的稀疏矩阵。

?646??455??122??111??????1?212??249???(1)?313? (2)??

328???444??356???536????437????6116??解：（1）为6×4矩阵，非零元素有6个，但其中一数下标有误？（2）为4×5矩阵，非零元素有5个 1 0 0 0 0 0 2 0 0 0 0 0 9 0 12 0 0 0 改为2,1,12 3 0 0 0 0 8 0 0 6 五、算法设计题（每题10分，共30分） 0 0 4 4.12 ③】 编写一个实现串的置换操作Replace(&S, T, V)0 0 7 0 的算法。 0 1.0 【严题集 0 0 6 0 解： 16 0 0 0 int Replace(Stringtype &S,Stringtype T,Stringtype V);//将串S中所有子串T替换为 V, 并返回置换次数 {

for(n=0,i=1;i<=Strlen(S)-Strlen(T)+1;i++) //注意i的取值范围

if(!StrCompare(SubString(S,i,Strlen(T)),T)) //找到了与T匹配的子串 { //分别把T的前面和后面部分保存为head和tail StrAssign(head,SubString(S,1,i-1));

StrAssign(tail,SubString(S,i+Strlen(T),Strlen(S)-i-Strlen(T)+1)); StrAssign(S,Concat(head,V));

StrAssign(S,Concat(S,tail)); //把head,V,tail连接为新串 i+=Strlen(V); //当前指针跳到插入串以后 n++;

18

n++; }//if return n; }//Replace

分析:i+=Strlen(V);这一句是必需的,也是容易忽略的.如省掉这一句,则在某些情况下, 会引起不希望的后果,虽然在大多数情况下没有影响.请思考:设S='place', T='ace', V='face',则省掉i+=Strlen(V);运行时会出现什么结果?

2. 【全国专升本资格考试】写出将字符串反序的递归或递推算法，例如字符串为“abcsxw”，反序为

“wxscba”(注：这也是严题集4.10③ 编写对串求逆的递推算法) 算法思路：

① 假定用单链表结构存储字符串；

if没有到尾部字符就不停调用自身函数，直至到达末尾，再从尾部返回并打印字符； 否则就打印当前字符并返回。 DLR(x*root) 递归算法的一般形式：（殷人凯题集P102） Invert(stringlistnode *p){

{if(!root)return(0); void p(参数表){ if(!p)return(0);

printf(“%d”,root->data); if （递归结束条件） else Invert(p->next);

可直接求解步骤； 基本项 DLR(root->lchild); printf(“%c”, p->data)

else p（较小的参数）； 归纳项 DLR(root->rchild); }

} }

如果当前串长为0,则return(-1) 否则开始递归：

if 串没有到末尾，则P=P->next; 再调用invert(s); else printf(p->data); return 4.10

void String_Reverse(Stringtype s,Stringtype &r)//求s的逆串r {

StrAssign(r,''); //初始化r为空串 for(i=Strlen(s);i;i--) {

StrAssign(c,SubString(s,i,1));

StrAssign(r,Concat(r,c)); //把s的字符从后往前添加到r中 /这是递推算法？ }

}//String_Reverse

3. 【严题集5.18⑤】试设计一个算法，将数组An 中的元素A[0]至A[n-1]循环右移k位，并要求只用一

个元素大小的附加存储，元素移动或交换次数为O(n) 解：5.18

分析:要把A的元素循环右移k位,则A[0]移至A[k],A[k]移至A[2k]......直到最终回到A[ 0].然而这并没有全部解决问题,因为有可能有的元素在此过程中始终没有被访问过,而是被跳了过去.分析可知,当n和k的最大公约数为p时,只要分别以A[0],A[1],...A[p-1]为起点执行上述算法,就可以保证每一个元素都被且仅被右移一次,从而满足题目要求.也就是说,A的所有元素分别处在p个\循环链\上面.举例如下: n=15,k=6,则p=3.

第一条链:A[0]->A[6],A[6]->A[12],A[12]->A[3],A[3]->A[9],A[9]->A[0]. /已“顺便”移动了A[6]、A[12]? 第二条链:A[1]->A[7],A[7]->A[13],A[13]->A[4],A[4]->A[10],A[10]->A[1]. 第三条链:A[2]->A[8],A[8]->A[14],A[14]->A[5],A[5]->A[11],A[11]->A[2]. 恰好使所有元素都右移一次.

虽然未经数学证明,但作者相信上述规律应该是正确的. 程序如下：

void RSh(int A[n],int k)//把数组A的元素循环右移k位,只用一个辅助存储空间

19

{

for(i=1;i<=k;i++)

if(n%i==0&&k%i==0) p=i;//求n和k的最大公约数p for(i=0;i

j=i;l=(i+k)%n;temp=A[i]; while(l!=i) {

A[j]=temp; temp=A[l]; A[l]=A[j]; j=l;l=(j+k)%n; }// 循环右移一步 A[i]=temp; }//for }//RSh

附加题： 利用C的库函数strlen, strcpy（或strncpy）写一个算法void StrDelete(char *S,int t,int m) ，删除串S中从位置i开始的连续的m个字符。若i≥strlen(S)，则没有字符被删除；若i+m≥strlen(S)，则将S中从位置i开始直至末尾的字符均被删去。

提示：strlen是求串长(length)函数：int strlen(char s); //求串的长度

strcpy是串复制(copy)函数：char *strcpy(char to,char from); //该函数将串from复制到串to中，并且返回一个指向串to的开始处的指针。

第6章 树和二叉树 自测卷解答 姓名 班级 一、下面是有关二叉树的叙述，请判断正误（每小题1分，共10分）

（ √ ）1. 若二叉树用二叉链表作存贮结构，则在n个结点的二叉树链表中只有n—1个非空指针域。 （ × ）2.二叉树中每个结点的两棵子树的高度差等于1。 （ √ ）3.二叉树中每个结点的两棵子树是有序的。

（ × ）4.二叉树中每个结点有两棵非空子树或有两棵空子树。

（ × ）5.二叉树中每个结点的关键字值大于其左非空子树（若存在的话）所有结点的关键字值，且小于

其右非空子树（若存在的话）所有结点的关键字值。 （应当是二叉排序树的特点）

（ × ）6.二叉树中所有结点个数是2k-1-1，其中k是树的深度。（应2i-1）

（ × ）7.二叉树中所有结点，如果不存在非空左子树，则不存在非空右子树。 （ × ）8.对于一棵非空二叉树，它的根结点作为第一层，则它的第i层上最多能有2i—1个结点。（应2i-1） （ √ ）9.用二叉链表法（link-rlink）存储包含n个结点的二叉树，结点的2n个指针区域中有n+1个为

空指针。

（正确。用二叉链表存储包含n个结点的二叉树，结点共有2n个链域。由于二叉树中，除根结点外，每一个结点有且仅有一个双亲，所以只有n-1个结点的链域存放指向非空子女结点的指针，还有n+1个空指针。）即有后继链接的指针仅n-1个。

（ √ ）10. 〖01年计算机系研题〗具有12个结点的完全二叉树有5个度为2的结点。

最快方法：用叶子数＝[n/2]＝6，再求n2=n0-1=5

二、填空（每空1分，共15分）

1． 由３个结点所构成的二叉树有 5 种形态。

2. 【计算机研2000】 一棵深度为6的满二叉树有 n1+n2=0+ n2= n0-1=31 个分支结点和 26-1 =32 个叶

20

}

main() /*先生成二叉排序树，再调用中序遍历递归函数进行排序输出*/ {int i,x; i=1;

root=NULL; /*千万别忘了赋初值给root!*/ do{printf(\i++;

scanf(\ /*从键盘采集数据，以-9999表示输入结束*/ if(x==-9999){ DLR(root);

printf(\ return(0); }

else insert_data(x);} /*调用插入数据元素的函数*/ while(x!=-9999); return(0);} 执行结果：

若一开始运行就输入-9999，则无叶子输出，sum=0。

2.【全国专升本统考题】写出求二叉树深度的算法，先定义二叉树的抽象数据类型。 （10分） 或【严题集6.44④】编写递归算法，求二叉树中以元素值为x的结点为根的子树的深度。

答；设计思路：只查后继链表指针，若左或右孩子的左或右指针非空，则层次数加1；否则函数返回。 但注意，递归时应当从叶子开始向上计数，否则不易确定层数。 int depth(liuyu*root) /*统计层数*/

{int d,p; /*注意每一层的局部变量d,p都是各自独立的*/ p=0;

if(root==NULL)return(p); /*找到叶子之后才开始统计*/ else{

d=depth(root->lchild);

if(d>p) p=d; /*向上回朔时，要挑出左右子树中的相对大的那个深度值*/ d=depth(root->rchild); if(d>p)p=d; }

p=p+1; return(p); }

法二：

26

int Get_Sub_Depth(Bitree T,int x)//求二叉树中以值为x的结点为根的子树深度 {

if(T->data==x) {

printf(\找到了值为x的结点,求其深度 exit 1; } } else {

if(T->lchild) Get_Sub_Depth(T->lchild,x);

if(T->rchild) Get_Sub_Depth(T->rchild,x); //在左右子树中继续寻找 }

}//Get_Sub_Depth

int Get_Depth(Bitree T)//求子树深度的递归算法 {

if(!T) return 0; else {

m=Get_Depth(T->lchild); n=Get_Depth(T->rchild); return (m>n?m:n)+1; }

}//Get_Depth

附：上机调试过程

步骤1 键盘输入序列12，8，17，11，16，2，13，9，21，4，构成一棵二叉排序树。层数应当为4

12 8 17 2 11 16 21 4 9 13

步骤2： 执行求深度的函数，并打印统计出来的深度值。 完整程序如下： #include #include

typedef struct liuyu{int data;struct liuyu *lchild,*rchild;}test; liuyu *root;

int sum=0;int m=sizeof(test);

void insert_data(int x) /*如何生成二叉排序树？参见教材P43C程序*/ { liuyu *p,*q,*s; s=(test*)malloc(m); s->data=x;

s->lchild=NULL; s->rchild=NULL;

if(!root){root=s; return;}

27

p=root;

while(p) /*如何接入二叉排序树的适当位置*/ {q=p;

if(p->data==x){printf(\else if(xdata)p=p->lchild; else p=p->rchild; }

if(xdata)q->lchild=s; else q->rchild=s; }

int depth(liuyu*root) /*统计层数*/

{int d,p; /*注意每一层的局部变量d,p都是各自独立的*/ p=0;

if(root==NULL)return(p); /*找到叶子之后才开始统计*/ else{

d=depth(root->lchild);

if(d>p) p=d; /*向上回朔时，要挑出左右子树中的相对大的那个深度值*/ d=depth(root->rchild); if(d>p)p=d; }

p=p+1; return(p); }

void main() /*先生成二叉排序树，再调用深度遍历递归函数进行统计并输出*/ {int i,x; i=1;

root=NULL; /*千万别忘了赋初值给root!*/ do{printf(\i++;

scanf(\ /*从键盘采集数据，以-9999表示输入结束*/ if(x==-9999){

printf(\ else insert_data(x);} /*调用插入数据元素的函数*/ while(x!=-9999); return;} 执行结果：

3. 【严题集6.47④】编写按层次顺序（同一层自左至右）遍历二叉树的算法。 或：按层次输出二叉树中所有结点；

28

解：思路：既然要求从上到下，从左到右，则利用队列存放各子树结点的指针是个好办法。 这是一个循环算法，用while语句不断循环，直到队空之后自然退出该函数。

技巧之处：当根结点入队后，会自然使得左、右孩子结点入队，而左孩子出队时又会立即使得它的左右孩子结点入队，??以此产生了按层次输出的效果。 level(liuyu*T)

/* liuyu *T,*p,*q[100]; 假设max已知*/ {int f,r;

f=0; r=0; /*置空队*/ r=(r+1)%max;

q[r]=T; /*根结点进队*/ while(f!=r) /*队列不空*/ {f=(f+1%max);

p=q[f]; /*出队*/

printf(\ /*打印根结点*/

if(p->lchild){r=(r+1)%max; q[r]=p->lchild;} /*若左子树不空，则左子树进队*/ if(p->rchild){r=(r+1)%max; q[r]=p->rchild;} /*若右子树不空，则右子树进队*/ }

return(0); }

法二：

void LayerOrder(Bitree T)//层序遍历二叉树 {

InitQueue(Q); //建立工作队列

EnQueue(Q,T);

while(!QueueEmpty(Q)) {

DeQueue(Q,p); visit(p);

if(p->lchild) EnQueue(Q,p->lchild); if(p->rchild) EnQueue(Q,p->rchild); }

}//LayerOrder

可以用前面的函数建树，然后调用这个函数来输出。

完整程序如下（已上机通过） #include #include #define max 50

typedef struct liuyu{int data;struct liuyu *lchild,*rchild;}test; liuyu *root,*p,*q[max];

int sum=0;int m=sizeof(test);

void insert_data(int x) /*如何生成二叉排序树？参见教材P43C程序*/ { liuyu *p,*q,*s; s=(test*)malloc(m); s->data=x;

s->lchild=NULL; s->rchild=NULL;

29

if(!root){root=s; return;} p=root;

while(p) /*如何接入二叉排序树的适当位置*/ {q=p;

if(p->data==x){printf(\else if(xdata)p=p->lchild; else p=p->rchild; }

if(xdata)q->lchild=s; else q->rchild=s; }

level(liuyu*T)

/* liuyu *T,*p,*q[100]; 假设max已知*/ {int f,r;

f=0; r=0; /*置空队*/ r=(r+1)%max;

q[r]=T; /*根结点进队*/ while(f!=r) /*队列不空*/ {f=(f+1%max);

p=q[f]; /*出队*/

printf(\ /*打印根结点*/

if(p->lchild){r=(r+1)%max; q[r]=p->lchild;} /*若左子树不空，则左子树进队*/ if(p->rchild){r=(r+1)%max; q[r]=p->rchild;} /*若右子树不空，则右子树进队*/ }

return(0); }

void main() /*先生成二叉排序树，再调用深度遍历递归函数进行统计并输出*/ {int i,x; i=1;

root=NULL; /*千万别忘了赋初值给root!*/ do{printf(\i++;

scanf(\ /*从键盘采集数据，以-9999表示输入结束*/ if(x==-9999){

printf(\ else insert_data(x);} /*调用插入数据元素的函数*/ while(x!=-9999); return;}

4. 已知一棵具有n个结点的完全二叉树被顺序存储于一维数组A中，试编写一个算法打印出编号为i的结点的双亲和所有的孩子。

答：首先，由于是完全二叉树，不必担心中途会出现孩子为null的情况。 其次分析：结点i的左孩子为2i，右孩子为2i+1;直接打印即可。

Printf(“Left_child=”, %d, v[2*i].data; “Right_child=”, %d, v[2*i+1].data;);

但其双亲是i/2，需先判断i为奇数还是偶数。若i为奇数，则应当先i-- ，然后再除以2。 If(i/2!=0)i--;

Printf(“Parents=”, %d, v[i/2].data;);

30

四、 【2001年计考研题】给定下列网G: （10分）

1 试着找出网G的最小生成树，画出其逻辑结构图； 2 用两种不同的表示法画出网G的存储结构图；

3 用C语言（或其他算法语言）定义其中一种表示法（存储结构）的数据类型。 解：1. 最小生成树可直接画出，如右图所示。 A B———————C 2. 可用邻接矩阵和邻接表来描述： ??12??4????12?20?89??????20?15??12?????15???10?? ?48???6?????9??6????????1210?????

邻接表为： a → b b → a c → b d → c e → a f → b g → c

E————F G————D 描述存储结构的数据类型可参见教材或电子教案： 注：用两个数组分别存储顶点表和邻接矩阵 #define INFINITY INT_MAX //最大值∞ #define MAX_VERTEX_NUM 20 //假设的最大顶点数（可取为7） Typedef enum {DG, DN, AG,AN } GraphKind; //有向/无向图，有向/无向网Typedef struct ArcCell{ //弧（边）结点的定义 VRType adj; //顶点间关系，无权图取1或0；有权图取权值类型 InfoType *info; //该弧相关信息的指针 }ArcCell, AdjMatrix [ MAX_VERTEX_NUM ] [MAX_VERTEX_NUM ]; Typedef struct{ //图的定义 VertexType vexs [MAX_VERTEX_NUM ] ; //顶点表，用一维向量即可 AdjMatrix arcs; //邻接矩阵 Int Vernum, arcnum; //顶点总数（7），弧（边）总数（9） GraphKind kind; //图的种类标志 }Mgraph; 12 12 20 15 4 9 12 → → → → → → → e c d g b e d 4 20 15 10 8 6 10 ^ → → ^ → ^ e g f 8 12 6 → ^ ^ f

36

9 ^

五、算法设计题（每题10分，共30分）

1. 【严题集7.14③】编写算法，由依次输入的顶点数目、弧的数目、各顶点的信息和各条弧的信息建立有向图的邻接表。

解：Status Build_AdjList(ALGraph &G) //输入有向图的顶点数,边数,顶点信息和边的信息建立邻接表 {

InitALGraph(G); scanf(\

if(v<0) return ERROR; //顶点数不能为负 G.vexnum=v; scanf(\

if(a<0) return ERROR; //边数不能为负 G.arcnum=a;

for(m=0;m

G.vertices[m].data=getchar(); //输入各顶点的符号 for(m=1;m<=a;m++) {

t=getchar();h=getchar(); //t为弧尾,h为弧头 if((i=LocateVex(G,t))<0) return ERROR;

if((j=LocateVex(G,h))<0) return ERROR; //顶点未找到 p=(ArcNode*)malloc(sizeof(ArcNode));

if(!G.vertices.[i].firstarc) G.vertices[i].firstarc=p; else {

for(q=G.vertices[i].firstarc;q->nextarc;q=q->nextarc); q->nextarc=p; }

p->adjvex=j;p->nextarc=NULL; }//while return OK; }//Build_AdjList

2. 【严题集7.15③】试在邻接矩阵存储结构上实现图的基本操作：DeleteArc(G,v,w) ，即删除一条边的操作。（如果要删除所有从第i个顶点出发的边呢？ 提示： 将邻接矩阵的第i行全部置0 ） 解：//本题中的图G均为有向无权图。

Status Delete_Arc(MGraph &G,char v,char w)//在邻接矩阵表示的图G上删除边(v,w) {

if((i=LocateVex(G,v))<0) return ERROR; if((j=LocateVex(G,w))<0) return ERROR; if(G.arcs[i][j].adj) {

G.arcs[i][j].adj=0; G.arcnum--; }

return OK; }//Delete_Arc

3. 【严题集7.22③】试基于图的深度优先搜索策略写一算法，判别以邻接表方式存储的有向图中是否存

37

在由顶点vi到顶点vj的路径（i≠j）。注意：算法中涉及的图的基本操作必须在此存储结构上实现。 int visited[MAXSIZE]; //指示顶点是否在当前路径上

int exist_path_DFS(ALGraph G,int i,int j)//深度优先判断有向图G中顶点i到顶点j 是否有路径,是则返回1,否则返回0 {

if(i==j) return 1; //i就是j else {

visited[i]=1;

for(p=G.vertices[i].firstarc;p;p=p->nextarc) {

k=p->adjvex;

if(!visited[k]&&exist_path(k,j)) return 1;//i下游的顶点到j有路径 }//for }//else

}//exist_path_DFS

解2：（以上算法似乎有问题：如果不存在路径，则原程序不能返回0。我的解决方式是在原程序的中引入一变量level来控制递归进行的层数。具体的方法我在程序中用红色标记出来了。） int visited[MAXSIZE]; //指示顶点是否在当前路径上 int level＝1;//递归进行的层数

int exist_path_DFS(ALGraph G,int i,int j)//深度优先判断有向图G中顶点i到顶点j 是否有路径,是则返回1,否则返回0 {

if(i==j) return 1; //i就是j else {

visited[i]=1;

for(p=G.vertices[i].firstarc;p;p=p->nextarc，level--) { level++;

k=p->adjvex;

if(!visited[k]&&exist_path(k,j)) return 1;//i下游的顶点到j有路径

}//for }//else

if (level==1) return 0; }//exist_path_DFS

附加题：【严题集7.27④】采用邻接表存储结构，编写一个判别无向图中任意给定的两个顶点之间是否存在一条长度为k的简单路径的算法。

（注1：一条路径为简单路径指的是其顶点序列中不含有重现的顶点。

注2：此题可参见严题集P207-208中有关按“路径”遍历的算法基本框架。） int visited[MAXSIZE];

int exist_path_len(ALGraph G,int i,int j,int k)//判断邻接表方式存储的有向图G 的顶点i到j是否存在长度为k的简单路径 { {

if(i==j&&k==0) return 1; //找到了一条路径,且长度符合要求 else if(k>0) {

visited[i]=1;

38

for(p=G.vertices[i].firstarc;p;p=p->nextarc) {

l=p->adjvex; if(!visited[l])

if(exist_path_len(G,l,j,k-1)) return 1; //剩余路径长度减一 }//for

visited[i]=0; //本题允许曾经被访问过的结点出现在另一条路径中 }//else

return 0; //没找到 }//exist_path_len

第8章 查找 自测卷答案 姓名 班级 A

一、填空题（每空1分，共10分）

1. 在数据的存放无规律而言的线性表中进行检索的最佳方法是 顺序查找（线性查找） 。

2. 线性有序表（a1，a2，a3，?，a256)是从小到大排列的，对一个给定的值k，用二分法检索表中与k相等的元素，在查找不成功的情况下，最多需要检索 8 次。设有100个结点，用二分法查找时，最大比较次数是 7 。

3. 假设在有序线性表a[20]上进行折半查找，则比较一次查找成功的结点数为1；比较两次查找成功的结点数为 2 ；比较四次查找成功的结点数为 8 ；平均查找长度为 3.7 。

5

解：显然，平均查找长度＝O（log2n）<5次（2）。但具体是多少次，则不应当按照公式

ASL?n?1m

log2(n?1)来计算（即（21×log221）/20＝4.6次并不正确！）。因为这是在假设n＝2-1的情况n下推导出来的公式。应当用穷举法罗列：

全部元素的查找次数为＝（1＋2×2＋4×3＋8×4＋5×5）＝74； ASL＝74/20=3.7 ！！！ 4．【计研题2000】折半查找有序表（4，6，12，20，28，38，50，70，88，100），若查找表中元素20，它将依次与表中元素 28，6，12，20 比较大小。

5. 在各种查找方法中，平均查找长度与结点个数n无关的查找方法是 散列查找 。 6. 散列法存储的基本思想是由 关键字的值 决定数据的存储地址。

7. 有一个表长为m的散列表，初始状态为空，现将n（n

二、单项选择题（每小题1分，共27分）

（ B ）1．在表长为ｎ的链表中进行线性查找，它的平均查找长度为

Ａ. ＡＳＬ＝ｎ; Ｂ. ＡＳＬ＝（ｎ＋１）／２;

Ｃ. ＡＳＬ＝n＋１; Ｄ. ＡＳＬ≈ｌｏｇ２（ｎ＋１）－１

（ A ）2．【计研题2001】折半查找有序表（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 （ C ）3．【计研题2001】对22个记录的有序表作折半查找，当查找失败时，至少需要比较 次

关键字。

A．3 B．4 C．5 D． 6 （ A ）4. 链表适用于 查找

A．顺序 B．二分法 C．顺序，也能二分法 D．随机

（ C ）5. 折半搜索与二叉搜索树的时间性能

A. 相同 B. 完全不同 C. 有时不相同 D. 数量级都是O（log2n）

39

6．【91程P3】从供选择的答案中，选出应填入下面叙述 ？ 内的最确切的解答，把相应编号写在答卷的对应栏内。 要进行线性查找，则线性表 A ；要进行二分查找，则线性表 B ；要进行散列查找，则线性表 C 。 某顺序存储的表格，其中有90000个元素，已按关键项的值的上升顺序排列。现假定对各个元素进行查找的概率是相同的，并且各个元素的关键项的值皆不相同。当用顺序查找法查找时，平均比较次数约为 D ，最大比较次数为 E 。 供选择的答案：

A~C：① 必须以顺序方式存储 ② 必须以链表方式存储 ③ 必须以散列方式存储 ④ 既可以以顺序方式，也可以以链表方式存储

⑤ 必须以顺序方式存储且数据元素已按值递增或递减的次序排好 ⑥ 必须以链表方式存储且数据元素已按值递增或递减的次序排好

D，E： ① 25000 ② 30000 ③ 45000 ④ 90000

答案： A= ④ B= ⑤ C= ③ D＝ ③ E＝ ④

7. （96初程P73）从供选择的答案中，选出应填入下面叙述 ？ 内的最确切的解答，把相应编号写在答卷的对应栏内。

数据结构反映了数据元素之间的结构关系。链表是一种 A ，它对于数据元素的插入和删除 B 。通常查找线性表数据元素的方法有 C 和 D 两种方法，其中 C 是一种只适合于顺序存储结构但 E 的方法；而 D 是一种对顺序和链式存储结构均适用的方法。 供选择的答案：

A：①顺序存储线性表 ②非顺序存储非线性表 ③顺序存储非线性表 ④非顺序存储线性表 B： ① 不需要移动结点，不需改变结点指针 ②不需要移动结点，只需改变结点指针

③只需移动结点，不需改变结点指针 ④既需移动结点，又需改变结点指针 C：① 顺序查找 ②循环查找 ③条件查找 ④二分法查找 D：① 顺序查找 ②随机查找 ③二分法查找 ④分块查找 E：① 效率较低的线性查找 ②效率较低的非线性查找

③ 效率较高的非线性查找 ④效率较高的线性查找

答案：A＝ ④ B＝ ② C＝ ④ D＝ ① E＝ ③

8. 【97程P18】 从供选择的答案中，选出应填入下面叙述 ？ 内的最确切的解答，把相应编号写在答卷的对应栏内。

在二叉排序树中，每个结点的关键码值 A ， B 一棵二叉排序，即可得到排序序列。同一个结点集合，可用不同的二叉排序树表示，人们把平均检索长度最短的二叉排序树称作最佳二叉排序，最佳二叉排序树在结构上的特点是 C 。 供选择的答案

A： ①比左子树所有结点的关键码值大，比右子树所有结点的关键码值小

②比左子树所有结点的关键码值小，比右子树所有结点的关键码值大 ③比左右子树的所有结点的关键码值都大

④与左子树所有结点的关键码值和右子树所有结点的关键码值无必然的大小关系 B: ①前序遍历 ② 中序（对称）遍历 ③ 后序遍历 ④ 层次遍历

C：① 除最下二层可以不满外，其余都是充满的 ②除最下一层可以不满外，其余都是充满的 ③ 每个结点的左右子树的高度之差的绝对值不大于1 ④ 最下层的叶子必须在最左边 答案：A＝ ① B＝ ② C＝ ②

9. 【92程 P6】 从供选择的答案中，选出应填入下面叙述 ？ 内的最确切的解答，把相应编号写在答卷的对应栏内。

散列法存储的基本思想是根据 A 来决定 B ，碰撞（冲突）指的是 C ，处理碰撞的两类主要方法是 D 。 供选择的答案

A，B： ①存储地址 ② 元素的符号 ③ 元素个数 ④ 关键码值

⑤ 非码属性 ⑥ 平均检索长度 ⑦ 负载因子 ⑧ 散列表空间

40

C: ①两个元素具有相同序号 ② 两个元素的关键码值不同，而非码属性相同

③ 不同关键码值对应到相同的存储地址 ④ 负载因子过大 ⑤ 数据元素过多 D： ① 线性探查法和双散列函数法 ② 建溢出区法和不建溢出区法 ③ 除余法和折叠法 ④ 拉链法和开地址法

答案：A＝ ④ B＝ ① C＝ ③ D＝ ④

10.【91程P4】考虑具有如下性质的二叉树：除叶子结点外，每个结点的值都大于其左子树上的一切结点的值。并小于等于其右子树上的一切结点的值。

现把9个数1，2，3，?，8，9填入右图所示的二叉树的9个结点中，并使之具有上述性质。此时，n1的值是 A ，n2的值是 B ，n9的值是 C 。现欲把10放入此树并使该树保持

前述性质，增加的一个结点可以放在 D 或 E 。 供选择的答案

A～C： ①1 ② 2 ③ 3 ④ 4 ⑤ 5

⑥ 6 ⑦ 7 ⑧ 8 ⑨ 9

D～E： ① n7下面 ② n8下面 ③ n9下面 ④ n6下面

⑤ n1与n2之间 ⑥ n2与n4之间 ⑦ n6与n9之间 ⑧ n3与n6之间

答案：A＝ ⑦ B＝ ④ C＝ ⑥ D＝ ② E＝ ⑥

三、简答题（每小题4分，共16分）

1.【全国专升本题】对分（折半）查找适不适合链表结构的序列，为什么？用二分查找的查找速度必然比线性查找的速度快，这种说法对吗？

答：不适合！虽然有序的单链表的结点是按从小到大（或从大到小）顺序排列，但因其存储结构为单链表，查找结点时只能从头指针开始逐步搜索，故不能进行折半查找。 二分查找的速度在一般情况下是快些，但在特殊情况下未必快。例如所查数据位于首位时，则线性查找快；而二分查找则慢得多。

2.【计研题1999】假定对有序表：（3，4，5，7，24，30，42，54，63，72，87，95）进行折半查找，试回答下列问题：

（1） 画出描述折半查找过程的判定树；

（2） 若查找元素54，需依次与哪些元素比较？ （3） 若查找元素90，需依次与哪些元素比较？

（4） 假定每个元素的查找概率相等，求查找成功时的平均查找长度。

解：

（1） 先画出判定树如下（注：mid=?(1+12)/2?=6）：

30

5 63

3 7 42 87

4 24 54 72 95

41

(2) 查找元素54，需依次与30, 63, 42, 54 等元素比较； (3) 查找元素90，需依次与30, 63,87, 95, 72等元素比较；

（4） 求ASL之前，需要统计每个元素的查找次数。判定树的前3层共查找1＋2×2＋4×3=17次；

但最后一层未满，不能用8×4，只能用5×4=20次， 所以ASL＝1/12（17＋20）＝37/12≈3.08

3. 【全国专升本题】用比较两个元素大小的方法在一个给定的序列中查找某个元素的时间复杂度下限是什么? 如果要求时间复杂度更小,你采用什么方法？此方法的时间复杂度是多少?

答：查找某个元素的时间复杂度下限，如果理解为最短查找时间，则当关键字值与表头元素相同时，比较1次即可。要想降低时间复杂度，可以改用Hash查找法。此方法对表内每个元素的比较次数都是O（1）。

4. 【计研题1999】设哈希（Hash）表的地址范围为0～17，哈希函数为：H（K）＝K MOD 16。

K为关键字，用线性探测法再散列法处理冲突，输入关键字序列： （10，24，32，17，31，30，46，47，40，63，49） 造出Hash表，试回答下列问题： （1） 画出哈希表的示意图；

（2） 若查找关键字63，需要依次与哪些关键字进行比较？ （3） 若查找关键字60，需要依次与哪些关键字比较？

（4） 假定每个关键字的查找概率相等，求查找成功时的平均查找长度。

解： （1）画表如下： 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 32 17 63 49 24 40 10 30 31 46 47 （2） 查找63,首先要与H(63)=63=15号单元内容比较，即63 vs 31 ,no; 然后顺移，与46,47,32,17,63相比，一共比较了6次！

（3）查找60,首先要与H(60)=60=12号单元内容比较，但因为12号单元为空（应当有空标记），所以应当只比较这一次即可。

（4） 对于黑色数据元素，各比较1次；共6次； 对红色元素则各不相同，要统计移位的位数。“63”需要6次，“49”需要3次，“40”需要2次，“46”需要3次，“47”需要3次，

所以ASL=1/11（6＋2＋3×3）＝17/11=1.5454545454≈1.55

四、分析题（每小题6分，共24分）

1. 【严题集9.3②】画出对长度为10的有序表进行折半查找的判定树，并求其等概率时查找成功的平均查找长度。

解：判定树应当描述每次查找的位置：

ASL＝1/10（1＋2×2＋3×4＋4×3） 5

2 8

＝1/10（1＋4＋12＋12） 1 3 6 9

＝29/10=2.9 4 7 10

2. 【全国专升本考题】在一棵空的二叉查找树中依次插入关键字序列为12，7，17，11，16，2，13，9，21，4，请画出所得到的二叉查找树。 答：

12

7 17

2 11 16 21

42

4 9 13

验算方法： 用中序遍历应得到排序结果： 2,4,7,9,11,12,13,16,17，21

3. 【严题集9.9③】已知如下所示长度为12的表：

（Jan, Feb, Mar, Apr, May, June, July, Aug, Sep, Oct, Nov, Dec）

(1) 试按表中元素的顺序依次插入一棵初始为空的二叉排序树，画出插入完成之后的二叉排序树，并求其

在等概率的情况下查找成功的平均查找长度。

(2) 若对表中元素先进行排序构成有序表，求在等概率的情况下对此有序表进行折半查找时查找成功的平

均查找长度。

(3) 按表中元素顺序构造一棵平衡二叉排序树，并求其在等概率的情况下查找成功的平均查找长度。 解：

43

4. 选取散列函数H（key）=（3*key），用线性探测法处理冲突，对下列关键码序列构造一个散列地址空间为0～10，表长为11的散列表，{22，41，53，08，46，30，01，31，66}。 解：由题意知，m=11(刚好为素数)

则(22*3)=6??0

链接指针 地址 值 (41*3)=11??2

0 22 1 (53*3)=14??5

1 66 (08*3)=2??2

2 41 3 (46*3)=12??6

3 08 4,7 (30*3)=8??2

4 30 (01*3)=0??3

5 53 (31*3)=8??5 6 46 (66*3)=9??0 7 01 8 31 9 22 66 41 8 30 53 46 1 31 0 1 2 3 4 5 6 7 8 9 10 7 1 3 4，

五、算法设计题（4中选3，第1题7分必选，其余每题8分，共23分）

1. 已知11个元素的有序表为（05 13 19 21 37 56 64 75 80 88 92）, 请写出折半查找的算

法程序，查找关键字为key的数据元素 (建议上机调试)。

解：折半查找的C程序有很多参考资料，注意此题要求是整型量。 折半查找的一个递归算法如下，形式非常简洁！

int Search_Bin_Recursive(SSTable ST, int key, int low, int high) //折半查找的递归算法 {

44

if(low>high) return 0; //查找不到时返回0 mid=(low+high)/2;

if(ST.elem[mid].key= =key) return mid; else if(ST.elem[mid].key>key)

return Search_Bin_Recursive(ST, key, low, mid-1); else return Search_Bin_Recursive(ST, key, mid+1, high); }

}//Search_Bin_Recursive

2. 【严题集9.31④】试写一个判别给定二叉树是否为二叉排序树的算法，设此二叉树以二叉链表作存储结构。且树中结点的关键字均不同。

解：注意仔细研究二叉排序树的定义。易犯的典型错误是按下述思路进行判别：“若一棵非空的二叉树其左、右子树均为二叉排序树，且左子树的根的值小于根结点的值，又根结点的值不大于右子树的根的值，则是二叉排序树” （刘注：即不能只判断左右孩子的情况，还要判断左右孩子与双亲甚至根结点的比值也要遵循（左小右大）原则）。

若要采用递归算法，建议您采用如下的函数首部：

bool BisortTree(BiTree T, BiTree&PRE)，其中PRE为指向当前访问结点的前驱的指针。 （或者直接存储前驱的数值，随时与当前根结点比较） 一个漂亮的算法设计如下：

int last=0, flag=1; // last是全局变量，用来记录前驱结点值，只要每个结点都比前驱大就行。 int Is_BSTree(Bitree T) //判断二叉树T是否二叉排序树，是则返回1，否则返回0 {

if(T->lchild&&flag) Is_BSTree(T->lchild);

if(T->datadata;

if(T->rchild&&flag) Is_BSTree(T->rchild); return flag; }//Is_BSTree

3. 【严题集9.22④】已知一个含有1000个记录的表，关键字为中国人姓氏的拼音，请给出此表的一个哈

希表设计方案，要求它在等概率情况下查找成功的平均查找长度不超过3。 解：设计哈希表的步骤为：

a) 根据所选择的处理冲突的方法求出装载因子a的上界； b) 由a值设计哈希表的长度m；

c) 根据关键字的特性和表长m选定合适的哈希函数。 刘注：要求ASL≤3，则m必然要尽量长，以减少冲突；

4. 【严题集9.44④】已知某哈希表的装载因子小于1，哈希函数H(key)为关键字（标识符）的第一个字

母在字母表中的序号，处理冲突的方法为线性探测开放定址法。试编写一个按第一个字母的顺序输出哈希表中所有关键字的算法。

解：注意此题给出的条件：装载因子a〈1, 则哈希表未填满。由此可写出下列形式简明的算法： void PrintWord(Hash Table ht)

{//按第一个字母的顺序输出哈希表ht中的标识符。哈希函数为表示符的第一个字母在字母表中的序号，处理冲突的方法是线性探测开放定址法。 for(i=1; i<=26; i++){ j=i;

While(ht.elem[j].key){

if(Hash(ht.elem[j].key==i)printf(ht.elem[j].key); j=(j+1)%m;

45

} }

}//PrintWord

第9章 排序 自测卷 答案 姓名 班级

一、填空题（每空1分，共24分）

1. 大多数排序算法都有两个基本的操作： 比较（两个关键字的大小） 和 移动（记录或改变指向记

录的指针） 。

2. 在对一组记录（54，38，96，23，15，72，60，45，83）进行直接插入排序时，当把第7个记录60插入到有序表时，为寻找插入位置至少需比较 3 次。(可约定为，从后向前比较)

3. 在插入和选择排序中，若初始数据基本正序，则选用 插入排序（到尾部） ；若初始数据基本反序，则选用 选择排序 。

4. 在堆排序和快速排序中，若初始记录接近正序或反序，则选用 堆排序 ；若初始记录基本无序，则最好选用 快速排序 。

5. 对于n个记录的集合进行冒泡排序，在最坏的情况下所需要的时间是 O(n2) 。若对其进行快速排序，在最坏的情况下所需要的时间是 O(n2) 。

6. 对于n个记录的集合进行归并排序，所需要的平均时间是 O(nlog2n) ，所需要的附加空间是 O(n) 。 7．【计研题2000】对于n个记录的表进行2路归并排序，整个归并排序需进行 log2n 趟（遍），共计移

动 n log2n 次记录。

(即移动到新表中的总次数！共log2n趟，每趟都要移动n个元素)

8.设要将序列（Q, H, C, Y, P, A, M, S, R, D, F, X）中的关键码按字母序的升序重新排列，则： 冒泡排序一趟扫描的结果是 H, C, Q, P, A, M, S, R, D, F, X ,Y ；

初始步长为4的希尔（shell）排序一趟的结果是 P, A, C, S, Q, D, F, X , R, H,M, Y ； 二路归并排序一趟扫描的结果是 H, Q, C, Y，A, P, M, S, D, R, F, X ； 快速排序一趟扫描的结果是 F, H, C, D, P, A, M, Q, R, S, Y，X ； 堆排序初始建堆的结果是 A, D, C, R, F, Q, M, S, Y，P, H, X 。 9. 在堆排序、快速排序和归并排序中， 若只从存储空间考虑，则应首先选取 堆排序 方法，其次选取 快速排序 方法，最后选取 归并排序 方法； 若只从排序结果的稳定性考虑，则应 选取归并排序方法； 若只从平均情况下最快考虑，则应选取快速排序方法；

若只从最坏情况下最快并且要节省内存考虑，则应选取堆排序方法。

二、单项选择题（每小题1分，共18分）

（ C ）1．将5个不同的数据进行排序，至多需要比较 次。

Ａ. 8 Ｂ. 9 Ｃ. 10 Ｄ. 25

（ C ）2． 排序方法中，从未排序序列中依次取出元素与已排序序列（初始时为空）中的元素进行比较，将其放入已排序序列的正确位置上的方法，称为

Ａ. 希尔排序 Ｂ. 冒泡排序 Ｃ. 插入排序 Ｄ. 选择排序

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

Ａ. 希尔排序 Ｂ. 归并排序 Ｃ. 插入排序 Ｄ. 选择排序

（ C ）4．对ｎ个不同的排序码进行冒泡排序，在下列哪种情况下比较的次数最多。

Ａ. 从小到大排列好的 Ｂ. 从大到小排列好的 Ｃ. 元素无序 Ｄ. 元素基本有序

（ D ）5．对ｎ个不同的排序码进行冒泡排序，在元素无序的情况下比较的次数为

Ａ. n+1 Ｂ. n Ｃ. n-1 Ｄ. n(n-1)/2

(前3个答案都太小了)

（ C ）6．快速排序在下列哪种情况下最易发挥其长处。

Ａ. 被排序的数据中含有多个相同排序码 Ｂ. 被排序的数据已基本有序

46

Ｃ. 被排序的数据完全无序 Ｄ. 被排序的数据中的最大值和最小值相差悬殊

（ B ）7． 【计研题2001】对有n个记录的表作快速排序，在最坏情况下，算法的时间复杂度是

A．O(n) B．O(n2) C．O(nlog2n) D．O(n3)

（ C ）8．若一组记录的排序码为（46, 79, 56, 38, 40, 84），则利用快速排序的方法，以第一个记录为基准得到的一次划分结果为

Ａ. 38, 40, 46, 56, 79, 84 Ｂ. 40,38, 46 , 79, 56, 84 Ｃ. 40, 38，46, 56, 79, 84 Ｄ. 40, 38,46, 84, 56, 79

（ A&D ）9．【计研题2001】在最好情况下，下列排序算法中 排序算法所需比较关键字次数最少。

A．冒泡 B．归并 C．快速 D．直接插入

(仅n—1次！)

（ C ）10． 【计研题2001】置换选择排序的功能是 。 （置换选择排序＝简单选择排序？）

A．选出最大的元素 B．产生初始归并段 C．产生有序文件 D．置换某个记录

（ A ）11．将5个不同的数据进行排序，至少需要比较 次。

Ａ. 4 Ｂ. 5 Ｃ. 6 Ｄ. 7

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

Ａ. 16,72,31,23,94,53 Ｂ. 94,23, 31, 72, 16, 53 Ｃ. 16, 53, 23,94,31, 72 Ｄ. 16, 23, 53,31, 94, 72 （ B ）13．堆是一种 排序。

Ａ. 插入 Ｂ.选择 Ｃ. 交换 Ｄ. 归并

（ C ）14．堆的形状是一棵

Ａ. 二叉排序树 Ｂ.满二叉树 Ｃ. 完全二叉树 Ｄ. 平衡二叉树

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

Ａ. 79, 46, 56, 38, 40, 84 Ｂ. 84, 79, 56, 38, 40, 46 Ｃ. 84, 79, 56, 46, 40, 38 Ｄ. 84, 56, 79, 40, 46, 38

（ B ）16． 下述几种排序方法中，平均查找长度（ASL）最小的是

Ａ. 插入排序 Ｂ.快速排序 Ｃ. 归并排序 Ｄ. 选择排序

（ C ）17． 下述几种排序方法中，要求内存最大的是

Ａ. 插入排序 Ｂ.快速排序 Ｃ. 归并排序 Ｄ. 选择排序

（ B ）18．目前以比较为基础的内部排序方法中，其比较次数与待排序的记录的初始排列状态无关的是

Ａ. 插入排序 Ｂ. 二分插入排序 Ｃ. 快速排序 Ｄ. 冒泡排序

三、简答题（每小题4分，共36分）

1. 【全国专升本题】已知序列基本有序，问对此序列最快的排序方法是多少，此时平均复杂度是多少？ 答：插入排序和冒泡应该是最快的。因为只有比较动作，无需移动元素。此时平均时间复杂度为O(n) 2. 设有1000个无序的元素，希望用最快的速度挑选出其中前10个最大的元素，最好采用哪种排序方法？ 答：用堆排序或锦标赛排序最合适，因为不必等全部元素排完就能得到所需结果，时间效率为O(nlog2n)；若用冒泡排序则需时n!/(n-10)!

3. 用某种排序方法对线性表（25, 84，21,47,15,27,68,35,20）进行排序时，元素序列的变化情况如下： 25, 84，21,47,15,27,68,35,20 → 20, 15, 21, 25，47, 27,68,35, 84 → 15, 20, 21, 25，35, 27, 47, 68, 84→ 15, 20, 21, 25，27, 35, 47, 68, 84， 问采用的是什么排序方法？

答：用的是快速排序方法。注意每一趟要振荡完全部元素才算一个中间结果。

4. 对于整数序列100，99，98，?3，2，1，如果将它完全倒过来，分别用冒泡排序和快速排序法，它们的比较次数和交换次数各是多少？

答：冒泡排序的比较和交换次数将最大，都是1+2+…+n-1=n(n-1)/2＝50×99=4545次 快速排序则看按什么数据来分子表。

如果按100来分，则很惨，也会是n(n-1)/2！ 若按中间数据50或51来分表，则：

第1轮能确定1个元素，即在1个子表中比较和交换了n－1个元素；n－（21-1） 第2轮能再确定2个元素，即在2个子表中比较和交换了n－3个元素；n－（22-1） 第3轮能再确定4个元素，即在4个子表中比较和交换了n－7个元素；n－（23-1） 第4轮能再确定8个元素，即在8个子表中比较和交换了n－15个元素；n－（24-1）

47

??

第6轮能再确定32个元素，即在32个子表中比较和交换了n－65个元素；n－（26-1） 第7轮则能全部确定，（因为27=128）， 在100个子表中比较和交换了n－（100－1）个元素；

1

比较和交换总次数为：7n－(2－1＋22－1＋23－1??＋26－1＋100－1) ＝7n+7－(1＋2＋4＋??＋64+100)=7n－(8+16+32+164)=700-220=480次

若从中间选择初始元素，则ASL=（n+1）log2n－(21＋22＋23+??＋2m)= nlog2n+log2n－(21＋22＋23+??＋n)≈O（nlog2n） 5.【全国专升本试题】【严题集10.15④】设有n个值不同的元素存于顺序结构中，试问能否用比2n-3少的比较次数选出这n个元素中的最大值和最小值？若能请说明如何实现（不需写算法）。在最坏情况下至少需进行多少次比较。（或问：对含有n个互不相同元素的集合，同时找最大元和最小元至少需进行多少次比较?） 答：若用冒泡排序法，求最大值需n-1次比较；第二趟改为从n-1开始求最小值，需n-2次比较，合计2n-3次。

显然本题意图是放弃冒泡排序，寻找其他方法。

法1 ：一个简单的办法是，在一趟比较时，将头两个元素分别作为最大和最小值的暂存内容，将其余n-2个元素与其相比，具体可设计为：

第1步：a1a2? YES则直接替换a2，NO则再比较a1， 1～2次； 第3步：a4>a2? YES则直接替换a2，NO则再比较a1， 1～2次； ??

第n-1步：an>a2? YES则直接替换a2，NO则再比较a1， 1～2次； 合计：（n-2）×（1～2）＋1=(n-1)~(2n-3 )≤2n-3 最好情况至少需要n-1次比较，最坏情况需2n-3次。

法2 ：借用快速排序第一趟思想：以a1为支点，将序列分成两个子表。这一趟需要n-1次比较； 然后，在左边的子表中求最小值，冒泡一趟需要y-1次； 在右边的子表中求最大值，冒泡一趟需要z-1次；

合计需要(n-1)+( y-1)+( z-1)=n+y+z-3 因为y+z+1=n, 所以总次数＝2n－4≤2n－3!!!!!!!!!!! 但最坏情况下仍为为2n-3次，即一趟完毕后仍为单子表的情况。怎么办？有无更好的办法？

法3 ：能否用锦标赛排序思路？求最大值等于求冠军，需要n—1次比较；但接着求最小值，等于在n/2个叶子中比较即可。

编程也不复杂：可设计为，

第一趟：n个数据两两比较（共n/2次），小者放偶数位，大者放奇数位； 第二趟：对奇数位元素继续两两比较（n/4次）；对偶数位元素也两两比较（n/4次）；合计n/2次；

33

第三趟：对奇数位元素继续两两比较（n/2次）；对偶数位元素也两两比较（n/2次）；合计n/22次； 第四趟：对奇数位元素继续两两比较（n/24次）；对偶数位元素也两两比较（n/24次）；合计n/23次； ??

第log2n趟：对奇数位元素继续两两比较（n/2log2n次＝1）；对偶数位元素也两两比较（1次）；合计2次； 全部比较次数为：2+4+8+??＋n/2次≤2n-3 （n>1）

用二进制性质即可证明？ 因为 20+21+?2k-2+2k-1<2k ，即21+?2k-2+2k-1<2k —1 < 2k —1 +2k —2 (n=2k, 当k＝1，即n=2时为极端情况，1＝1; n=3时，1.5<3 k=2时，即n=4时，2<5

6. 【成教考题】将两个长度为n的有序表归并为一个长度为2n的有序表，最小需要比较n次，最多需

要比较2n-1次，请说明这两种情况发生时，两个被归并的表有何特征?

答：最少的比较次数是这样一种情况：若A表所有元素都小于（或大于）B表元素，则A1比较完B1～Bn之后，直接拼接即可。

最多比较次数的情况应该是A、B两表互相交错，此时需要穿插重排。则A表的每个元素都要与B表元素相比，A1与B1相比，能确定其中一个元素的位置；剩下一个还要与另一表中下一元素再比较一次， 即：在表A或表B的n个元素中，除了最后一个元素外，每个元素都要比较2次！最坏情况总共为2n—1次。

7. 【严题集10.11②】试问：按锦标赛排序的思想，决出8名运动员之间的名次排列，至少需编排多少

48

场次的比赛（应考虑最坏的情况）？ 刘答：不能简单地用(n-1)+(n-2)log2n来计算比赛场次。要特别注意，随着n/2的叶子结点被调整完毕之后，树的深度会逐层减少！

分别n=8和n=7的情况推导并归纳，得到如下计算公式：

比赛场次＝（n-1）+n/2(k-1)+ (n/22)(k-2)+?+ n/2(k-1) ，其中k=?log2n?

当n＝8时，k=3, 比赛场次＝7＋8/2(2)＋8/4= 17场(这是最坏情况，即每次都先从叶子调整起)

8. 【严题集10.19④】假设某大旅店共有5000个床位，每天需要根据住宿旅客的文件制造一份花名册，

该名册要求按省（市）的次序排列，每一省（市）按县（区）排列，又同一县（区）的旅客按姓氏排列。请你为旅店的管理人员设计一个制作这份花名册的方法。

（提示）这是一个多关键字的排序问题。请思考对这个文件进行排序用哪一种方法更合适，是MSD法还是LSD法？

答：采用哪种排序方法，关键要看记录的结构是如何定义的，如果旅客填表如下：

省（市） 县（区） 姓名 床位号 则按题意要求，应当采用MSD法，否则无法满足。 但若“姓名”项在前，则必须用LSD才符合题意要求。

9. 【全国专升本题】【严题集10.6④】奇偶交换排序如下所述：第一趟对所有奇数i，将a[i]和a[i+1]进行比较；第二趟对所有的偶数i,将a[i]和a[i+1]进行比较，若a[i]>a[i+1]，则两者交换；第三趟对奇数i,第四趟对偶数i；??依次类推直至整个序列有序为止。 （1）试问这种排序方法的结束条件是什么？是否为稳定排序？

（2）分析当初始序列为正序或逆序两种情况下，奇偶交换排序过程中所需进行的关键字比较的次数。 （3）分析此种排序方法的平均复杂度及最坏复杂度。 答：（1） 这种算法其实是两两比较，第一趟很像锦标赛的“初赛”，将胜者（大数）置于偶数单元； 第二趟对偶数单元操作，即第一组大者与第二组小者战，大者后移。结果相当于冒泡排序的一趟； 所以结束条件应为偶数趟无交换。

结束条件是：若n为偶数时，奇数循环时i>n-1 ，偶数循环时i>n ， 若n为奇数时，奇数循环时i>n 偶数循环时i>n+1 似乎不稳定？因为交换没有依次进行。 四、【全国专升本类似题】【类严题集10.1①】以关键字序列（256，301，751，129，937，863，742，694，076，438）为例，分别写出执行以下算法的各趟排序结束时，关键字序列的状态，并说明这些排序方法中，哪些易于在链表（包括各种单、双、循环链表）上实现？ ① 直接插入排序 ② 希尔排序 ③冒泡排序 ④快速排序

⑤直接选择排序 ⑥ 堆排序 ⑦ 归并排序 ⑧ 基数排序 （8分） 解：先回答第2问： ① ⑤ ⑦ ⑧皆易于在链表上实现。

① 直接插入排序的中间过程如下： ② 希尔排序的中间过程如下：

49

③ 冒泡排序的中间过程如下： ④快速排序的中间过程如下：

⑤ 直接选择排序的中间过程如下： ⑥堆排序（大根堆）的中间过程如下：

⑦ 归并排序排序的中间过程如下：

⑧ 基数排序的中间过程如下：

五、算法设计题（4选2， 每题7分，共14分）

1. 【严题集10.25③】试编写教科书10.2.2节中所述链表插入排序的算法。 10.25

void SLInsert_Sort(SLList &L)//静态链表的插入排序算法 {

L.r[0].key=0;L.r[0].next=1;

L.r[1].next=0; //建初始循环链表 for(i=2;i<=L.length;i++) //逐个插入

50

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