数据结构课后习题答案合集

1. 数据结构课程研究的内容是什么？其中哪个方面和计算机无关？ 答：非数值计算，包括数据的 逻辑结构、存储结构，操作的实现

2. 数据结构按逻辑结构可分为哪几类？（不要简单答线性和非线性） 3．为什么要进行算法分析？（分析算法的效率以求改进），算法分析主要研究哪几个方面？（ 时间效率和空间效率，即：空间复杂性和时间复杂性）

4．分析下面各程序段的时间复杂度。

1. for (i=0; ifor (j=0; jA[i][j]=0;

2. s=0;

for i=0; ifor(j=0; j3. x=0; for(i=1; i4. i=1;

while(i<=n) i=i*3; 答：O（log3n）

5、数据结构被形式地定义为（D, R），其中D是 数据元素 的有限集合，R是D上的 关系 有限集合。设有数据逻辑结构S=（D,R），试按各小题所给条件画出这些逻辑结构的图示，并确定相对于关系R，哪些结点是开始结点，哪些结点是终端结点？

1. 【严蔚敏习题集P7 1.3②】

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

答： d1→d2→d3→d4 d1—无直接前驱，是首结点 d4—无直接后继是尾结点

1

1. 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—无直接后继是叶子结点

2. 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、 向一个长度为n的向量的第i个元素(1≤i≤n+1)之前插入一个元素时，需向后移动 n-i+1 个元素。 向一个长度为n的向量中删除第i个元素(1≤i≤n)时，需向前移动 n-i 个元素。. 2、 顺序表中插入或删除一个元素，需要平均移动 表中一半元素，具体移动的元素个数与 表长和该元素

在表中的位置 有关。 在顺序表中访问任意一结点的时间复杂度均为 O(1) ，因此，顺序表也称为 随机存取 的数据结构。.一个向量第一个元素的存储地址是100，每个元素的长度为2，则第5个元素的地址是 108 ；向一个有127个元素的顺序表中插入一个新元素并保持原来顺序不变，平均要移动 63.5 个元素；

3、在n个结点的单链表中要删除已知结点*p，需找到它的前驱结点的地址，其时间复杂度为O（n）。

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

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

100 120

其中指针X，Y，Z的值分别为多少？该线性表的首结点起始地址为多少？末结点的起始地址为多少？（10分） 答：X= 116 Y= 0 Z= 100 首址= 108 末址= 112 （小心）

二、简答题

1. 试比较顺序存储结构和链式存储结构的优缺点。在什么情况下用顺序表比链表好？

答：① 顺序存储时，相邻数据元素的存放地址也相邻（逻辑与物理统一）；要求内存中可用存储单元的地址必须是连续的。

优点：存储密度大（用动态分配的方法，一般都情况下都接近1），存储空间利用率高。缺点：插入或删除元素时不方便。顺序表才适合随机存取；

②链式存储时，相邻数据元素可随意存放，但所占存储空间分两部分，一部分存放结点值，另一部分存放表示结点间关系的指针;优点：插入或删除元素时很方便，使用灵活。缺点：存储密度小（<1），存储空间利用率低。

顺序表适宜于做查找这样的静态操作；链表宜于做插入、删除这样的动态操作。 若线性表的长度变化不大，且其主要操作是查找，则采用顺序表；

若线性表的长度变化较大，且其主要操作是插入、删除操作(尤其是这些操作主要发生在线性表的靠表头)，则采用链表。

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

答：

首元结点是指链表中存储线性表中第一个数据元素a1的结点。

为了操作方便，通常在链表的首元结点之前附设一个结点，称为头结点，该结点的数据域中不存储线性表的数据元素，其作用是为了对链表进行操作时，可以对空表、非空表的情况以及对首元结点进行统一

3

处理。

头指针是指向链表中第一个结点（或为头结点或为首元结点）的指针。

若链表中附设头结点，则不管线性表是否为空表，头指针均不为空。算法中首元节点统一操作。否则表示空表的链表的头指针为空。这三个概念对单链表、双向链表和循环链表均适用。

头结点 Head 

data link 头指针 首元结点

简而言之，

头指针是指向链表中第一个结点（或为头结点或为首元结点）的指针；

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

首元素结点是指链表中存储线性表中第一个数据元素a1的结点。

===================================================================

《数据结构》学习讨论：要注重实践

上次课结束的时候，有个同学找到我，说上课的时候总是在强调结构与算法，但是没有用C语言真正地写出来，总觉得心里“不舒服”。有这种感觉就好了。《数据结构》是一门强调动手的课程，希望同学们能把自己感兴趣的算法改写成能正确执行的C语言算法。 很多同学刚开始写程序的时候很困难，这是正常的。因为这时候你既要考虑算法的思路，又要复习自己不怎么熟练的C语言，编译器也不太熟悉。其实，只要坚持一段时间，就能突破这个关口了。

第三章 堆栈与队列

一、填空：向量、栈和队列都是 线性 结构，可以在向量的 任何 位置插入和删

除元素；栈是一种特殊的线性表，允许插入和删除运算的一端称为 栈顶 。不允许插入和删除运算的一端称为 栈底 。所以又称为 后 进 先 出型表 。对于队列是只能在 队尾 插入和 队首 删除元素的特殊线性表达。先进先出型结构

二、问答

1、把教材第页的例3-1重新做一遍。要求在自己阅读懂的基础上重复填写该表。不要抄书上的答案。

2、.设有编号为1，2，3，4的四辆列车，顺序进入一个栈式结构的车站，具体写出这四辆列车开出车站的所有可能的顺序。

答：至少有14种。

① 全进之后再出情况，只有1种：4，3，2，1

② 进3个之后再出的情况，有3种，3,4,2,1 3,2,4,1 3,2,1,4

③ 进2个之后再出的情况，有5种，2,4,3,1 2,3,4,1 2,1, 3,4 2,1,4,3 2,1,3,4 ④ 进1个之后再出的情况，有5种，1,4,3,2 1,3,2,4 1,3,4,2 1, 2,3,4 1,2,4,3

3. 画图说明：顺序队的“假溢出”是怎样产生的？（答案见修改后的讲义） 画图说明如何用循环队列解决？

使用循环队列之后，队列的初始化，判断队列满，判断队列空，寻找入队时的位置，寻找出队列元素的位置的C语言语句以及表达式都怎么写？算循环队列中目前有多少个元素？

4

注意变量名称按照教材上的约定。

4． 述以下算法的功能（栈和队列的元素类型均为int）。 void algo3(Queue &Q) {

Stack S; int d; InitStack(S);

while(!QueueEmpty(Q)){ DeQueue (Q,d); Push(S,d); }; while(!StackEmpty(S)){ Pop(S,d); EnQueue (Q,d); } }

答：该算法的功能是：利用堆栈做辅助，将队列中的数据元素进行逆置。

第四章 串

注：本章习题很少，也很简单。，但是本章内容是比较多，比较复杂的。所以习题的目的仅仅是主要是督促同学们阅读教材和电子讲义，而不是查着书把下面的题目做出来就算掌握了。所以要尽力阅读完教材和电子讲义内容后再回答。看看在不回头再翻教材的前提下，能不能都做对。

1. 串有什么特殊性？串的操作有什么特殊性？ 2. 简述空串和空格串的区别。

答：数据元素是一个字符；常常以一串元素为操作对象，而不是一个。

3．对求子串操作：SubString (&Sub, S, pos, len) ，推导pos和len的合法范围。 答：串 S 存在，1≤pos≤StrLength(S) 且 0≤len≤StrLength(S)-pos+1。 4．什么是存储密度 ？

答：数据元素所占存储位/实际分配的存储位

5．讨论题：打开windows的记事本，和同学讨论如何实现一个类似的文本编辑器。主要讨论以下问题：（1）如何在内存存储文本？即：你将使用什么样的结构。（4）键盘输入字符的时候，你的存储结构如何变化？（3）如何实现“文件菜单”中的新建，打开，和保存。（3）如何实现“编辑菜弹”中的撤消，剪切，复制，粘贴，删除，查找和替换功能？觉得思考比较完整的同学可以到讲台上来给大家讲解自己的思路，非常欢迎。 -------------------

学习方法讨论：

在学习数据结构的时候，没有必要把所有的算法背诵下来，有一些算法是非常烦琐的，如果暂时不开发相关软件，没有必要把细节记得，而是要记得思路。会推导当中的一些。

另外一定要注意应用，学习的时候，一定要常常想，这个结构可以拿来干什么？比如：学习栈和队列的时候，就要想想平时使用的软件什么时候会用到这两个工具；学习串的时候要思考怎样利用串来实现文本编辑。从某个角度上来说，软件开发就是围绕几个数据结构展开开发工作的，

面对一个实际的问题，要对其编程，首先就要思考“如何抽象问题”，“如何存储”，“在这个存储结构上如何实现操作功能”，“怎样才能提高效率”。总之在编码之前首先要有一个

5

全面的思考，而不是想想写写，写写想想，发现结构不好，效率不高又改来改去。----这恰恰是很多软件公司亏本的原因，这样导致了结构混乱，编码混乱，难以维护，完全推倒从来又浪费了人力。有兴趣的同学可以浏览《软件工程》的教材，看看应该如何对软件开发的过程进行控制和管理。不过大部分《软件工程》教材上写的东西大多是“学院派”的，实际的开发中根本没有那样做。浏览《软件工程》的目的是了解基本的概念和软件开发中的注意事项。

总的来说，是“想好了再写”。一个小型软件如果需要三个月来开发，往往编码本身只需要15天左右，前面的时间主要用在分析用户的需求（了解用户心目中软件成品是怎样的），可行性的调查和结构设计。可见结构的设计在软件开发中的重要性。

杨华 谨识

第五章 数组

1. 假设有二维数组A6×8，每个元素用相邻的6个字节存储，存储器按字节编址。已知A的起始存储位置（基地址）为1000，则数组A的体积（存储量）为 288 B ；末尾元素A57的第一个字节地址为 1282 ；若按行存储时，元素A14的第一个字节地址为 1000 +(1*8+4)×6=1072 。

(注：数组是从0行0列还是从1行1列计算起呢？由末单元为A57（57！！！）可知，是从0行0列开始！)

2若将一个n阶对称方阵压缩存储到一维数组sa[n(n+1)/2+1]中，将一维数组的0号单元用来存储矩阵中下三角元素的个数，推导sa[k]和矩阵元素aij的对应关系。

3思考题：如何将对角矩阵压缩存储到一维数组中？也就是推导矩阵中元素的下标和数组中元素的下标的对应关系。（不要求详细推导过程和结果，此题不交，自己画草稿叙述清楚） 4自己用C语言定义稀疏矩阵的三元组顺序表，如果定义与书上不同，你看看你丢失的是矩阵的什么信息，没有一次写对的同学一定要因为这次错误而牢记你犯了什么错误。（不要抄书。此题不交）

5、对三元组顺序表存储的矩阵进行转置操作时，是怎样确定原三元组顺序表的元素在转置后的矩阵的位置的？（此题不交，自己画草稿叙述清楚）

6、在行逻辑连接的顺序表存储结构下，自己画图演示p101的（5-5式）中两个矩阵的乘法的实现过程。（此题不交，自己画草稿叙述清楚）

7、用十字链表存储稀疏矩阵的时候，如果两个矩阵A，B相加，实现A=A+B，则最终在A上实现的是那些操作？

8.求下列广义表操作的结果：

（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） ; ====================

注：广义表的操作主要使用递归来实现。课堂上暂时没有详细讲。对感兴趣的同学，建议学完树和图以后再学习，因为在那里会对递归有更深刻的理解。

6

第六章 树

注：习题不能覆盖所有的知识点，先阅读完电子讲义和教材再开始做练习。 一、填空

先记忆关于二叉树和完全二叉树的5个重要性质的结论，做1，2，3题。

1.一棵深度为6的满二叉树有 n1+n2=0+ n2= n0-1=31 个分支结点和 26-1 =32 个叶子。 注：满二叉树没有度为1的结点，所以分支结点数就是二度结点数。 2． 一棵具有２５７个结点的完全二叉树，它的深度为 9 。 （ 注：用 log2(n) +1=  8.xx +1=9 3. 设一棵完全二叉树具有1000个结点，则此完全二叉树有 500 个叶子结点，有 499 个度为2的结点，有 1 个结点只有非空左子树，有 0 个结点只有非空右子树。 答：最后一层叶子为：1000 – (29-1)=4 这些接点共245双亲，而倒数第二层是256接点，叶子是256-245=11.

2+11=500; 或者有个公式叶子数＝[n/2]＝500； n2=n0-1=499。 n1=1000-500-499=1

0: 完全二叉树没有这种接点。

答：最快方法：用叶子数＝[n/2]＝500 ，n2=n0-1=499。 另外，最后一结点为2i属于左叶子，右叶子是空的，所以有1个非空左子树。完全二叉树的特点决定不可能有左空右不空的情况，所以非空右子树数＝0.

4．把一棵树转换为二叉树后，这棵二叉树的形态是 唯一的 (唯一的 / 有多种)

二、简答题

1. 一棵度为2的树与一棵二叉树有何区别？ 答：度为2的树从形式上看与二叉树很相似，但它的子树是无序的，而二叉树是有序的。即，在一般树中若某结点只有一个孩子，就无需区分其左右次序，而在二叉树中即使是一个孩子也有左右之分。

2．.给定二叉树的两种遍历序列，分别是：

前序遍历序列：D，A，C，E，B，H，F，G，I； 中序遍历序列：D，C，B，E，H，A，G，I，F，

试画出二叉树B，写出后序遍历的序列。并简述由任意二叉树B的前序遍历序列和中序遍历序列求二叉树B的思想方法。

解：方法是：由前序先确定root，由中序可确定root的左、右子树。然后由其左子树的元素集合和右子树的集合对应前序遍历序列中的元素集合，可继续确定root的左右孩子。将他们分别作为新的root，不断递归，则所有元素都将被唯一确定，问题得解。

7

D A C F E G B H I

3.把如图所示的树转化成二叉树。

答：注意全部兄弟之间都要连线（包括度为2的兄弟）,并注意原有连线结点一律归入左子树，新添连线结点一律归入右子树。 A B

E C

K F H D L G I

M J

4.画出和下列二叉树相应的森林。

答：注意根右边的子树肯定是森林， 而孩子结点的右子树均为兄弟。

5．假设用于通信的电文仅由8个字母组成，字母在电文中出现的频率分别为0.07，0.19，0.02，0.06，0.32，0.03，0.21，0.10。试为这8个字母设计哈夫曼编码，计算平均编码长度（带权路径长度）。使用0～7的二进制表示形式是另一种编码方案。计算哈夫蔓编码相对于这种方案的压缩比。 解：方案1；哈夫曼编码

先将概率放大100倍，以方便构造哈夫曼树。 w={7,19,2,6,32,3,21,10}，按哈夫曼规则：【[（2,3），6], (7,10)】, ……19, 21, 32

（100）

0 1 （40） （60）

0 1 0 1 19 21 32 （28）

19 21 32 （17） （11）

0 1 7 10 6 （5）

0 1 0 1 2 3 7 10 6 0 1

2 3

8

方案比较：

字母编号 对应编码 出现频率 字母编号 对应编码 出现频率 1 1100 0.07 1 000 0.07 2 00 0.19 2 001 0.19 3 11110 0.02 3 010 0.02 方案1的WPL＝2(0.19+0.32+0.21)+4(0.07+0.06+0.10)+5(0.02+0.03)=1.44+0.92+0.25=2.61 4 1110 0.06 4 011 0.06 方案2的WPL＝3(0.19+0.32+0.21+0.07+0.06+0.10+0.02+0.03)=3 5 10 0.32 5 100 0.32 结论：哈夫曼编码优于等长二进制编码 11111 0.03 6 101 0.03 6 7 110 0.21

三、算法设计题

1.编写递归算法，计算二叉树中叶子结点的数目。

解：思路：输出叶子结点比较简单，用任何一种遍历递归算法，凡是左右指针均空者，则为叶子，将其打印出来。

int LeafCount_BiTree(Bitree T)//求二叉树中叶子结点的数目 {

if(!T) return 0; //空树没有叶子

else if(!T->lchild&&!T->rchild) return 1; //叶子结点

else return Leaf_Count(T->lchild)+Leaf_Count(T->rchild);//左子树的叶子数加 上右子树的叶子数 }//LeafCount_BiTree

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

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

技巧之处：当根结点入队后，会自然使得左、右孩子结点入队，而左孩子出队时又会立即使得它的左右孩子结点入队，……以此产生了按层次输出的效果。 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

9

第七章 图

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

2. 在一个有向图中，所有顶点的入度之和等于所有顶点的出度之和的 1 倍。 3. 有8个结点的无向图最多有 28 条边。 4. 有8个结点的有向完全图有 56 条边。 5. 有8个结点的无向连通图最少有 7 条边。

6. 有向图G用邻接表矩阵存储，其第i行的所有元素之和等于顶点i的 出度 。 7. 设有一稀疏图G，则G采用 邻接表 存储较省空间。 设有一稠密图G，则G采用 邻接矩阵 存储较省空间。（（选填邻接表/邻接矩阵））

8. 如果n个顶点的图是一个环，则它有 n 棵生成树。 （以任意一顶点为起点，得到n-1条边）9. 已知图的邻接矩阵如下，根据算法思想，则从顶点0出发按深度优先遍历的结点序列是 0 1 3 4 2 5 6 ，按广度优先遍历的结点序列是 0 1 2 3 4 6 5 。

011110111110100100100010010011001101000110110001010. 已知图的邻接表如下所示，根据算法，则从顶点0出发按深度优先遍历的结点序列是 0

1 2 3 。

11. 已知图的邻接表如下所示，根据算法，则从顶点0出发按广度优先遍历的结点序列是 0 3 2 1 。

12. 用邻接表表示图进行广度优先遍历时，通常是采用 队列 来辅助实现算法的。 13. 拓扑排序算法是通过重复选择具有 0 个前驱顶点的过程来完成的。 14. 请对下图的无向带权图，

(1)按普里姆算法求其最小生成树，计算生成树权值和；

(2)按克鲁斯卡尔算法求其最小生成树，计算生成树

10

权值和。

(3)根据上面两问，你可能猜测什么出什么结论?

解：设起点为a。可以直接由原始图画出最小生成树，而且最小生成树只有一种（类）!

最小生成树→

15.复习电子讲义中利用Dijkstra算法求图中从顶点a到其他各顶点间的最短路径的算法。（此题不交）

第八章 查找

1. 在数据的存放无规律而言的线性表中进行检索的最佳方法是 顺序查找（线性查找） 。 2. 假设在有序线性表a[20]上进行折半查找，则比较一次查找成功的结点数为1；比较两次查找成功的结点数为 2 ；比较四次查找成功的结点数为 8 ；平均查找长度为 3.7 。设有100个结点，用二分法查找时，最大比较次数是 7 。对22个记录的有序表作折半查找，当查找失败时，至少需要比较 5 次关键字。

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

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

全部元素的查找次数为＝（1＋2×2＋4×3＋8×4＋5×5）＝74； ASL＝74/20=3.7 ！！！ 3.设哈希（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）画表如下：

11

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

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

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

所以ASL=1/11（6+6＋2＋3×3）＝23/11=2.09

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

12

7 17

2 11 16 21 4 9 13

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

5.设在整形数据中进行折半查找，分别写出非递归与递归的查找算法。（可以在别的教材上找到递归算法。此题不交，请自己上机调试。）

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

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

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

原来的文件上没有写快速排序，这里补上。

注意：不要抄书，一定要自己画出结果。有余力的同学请阅读复杂度分析，否则只需要了解第8题结论。电子讲义上的程序还是要尽量读懂。

1． 直接插入排序：重复p266图10.1的排序过程；阅读复杂度分析。

2． Shell排序：见p271图10.5的关键字。先画第一趟排序过程（就使用直接选择排序），

然后，以趟为单位画出每一趟排序的排序结果。阅读复杂度分析。

3． 冒泡排序：见p273图10.6,对初始关键字，先画第一趟排序过程，然后，以趟为单位画

出每一趟排序的排序结果。阅读复杂度分析。

12

4． 快速排序：见p275图10.7，先画第一趟排序过程，然后，以趟为单位画出每一趟排序

的排序结果。阅读复杂度分析。

5． 直接选择排序：利用上题的关键字，先画第一趟排序过程，然后，以趟为单位画出每一

趟排序的排序结果。阅读复杂度分析。（直接插入法的核心操作是寻找插入位置，而直接选择法的核心操作是寻找无序中最小的一个。）

6． 堆排序：对p280末的关键字序列，重复p281图10.12的建堆过程；重复图10.11的过

程，输出堆顶元素，即最小元素以后，将剩余部分整理成堆的过程。阅读时间复杂度分析。注意结论：堆排序的效率是比较高的，但是首先有一个建堆的过程，所以在数据量很大的时候使用效果才好。

7． 归并排序：重复p283图10.13的排序过程（每一次都使用二路）。阅读时间复杂度分析。 8． 基数排序（桶排序）：对关键字序列：710，342，014，686，006，841，429，134，068，

2，使用低关键字优先的方法进行排序。画出排序的逻辑过程（暂时不考虑存储）。提示：建立0到9十个桶（10个桶：数的进制数）。经过3次分配与收集（3次：关键字序列中的最大位数<若关键字位数不一样，则将位数不够的前面添加0>），则完成整个排序过程。

9． 记忆p2，10.7节的表格。注意以下结论1)理论上已经证明：O(n log n)是排序算法的

最底线，不要花时间去发明时间复杂度更低的算法，只能在已知道数据的某些特性的情况下，做一些的改进，但产生数量级上差别不太可能。2）快速排序在数据已经基本有序的情况下，退化为冒泡排序O(n2)，而冒泡排序加上一定检测机制后可做到O(n)，所以排序算法的选择要根据数据的特征来做，若无法提前得知数据特点，则按平均情况选择。 10． 了解外部排序的概念：当数据量很大，不能完全在内存中完成的时候，需要和外存

交换数据，比如每个段内部排序，再归并。而归并会使用到败者树，置换-选择过程，最佳归并树等等技术。将来如果工作遇到很大量的数据要排序的时候，碰到这几个名词的时候，记得回来阅读这里就可以了。如果暂时不用，是没有必要阅读的，除非你感兴趣。（不要偏执，老师我本人就没有仔细阅读过，可见同学们现在是在打基础，但是如果能学来致用是最好的了）

--------------------------------------------- 关于软件技术的学习 一、数据结构是软件技术中基础的基础，希望大家考试以后继续多学习。更不要把教材扔了。你做过笔记的书扔掉是非常可惜的，因为你自己的笔记会帮助你将来迅速想起过去学过的内容。如果你的教材上密密麻麻地写满了阅读中的标志，疑问，心得，那真是一本不可多得的好参考书。

二、严老师的教材是中国《数据结构》教材里写的最严谨的，也是最难的教材，实现的效率相对其他教材比较高，缺点是语言非常简练形式化（即：公式化，数学化）的语言比较多，初学的时候难以阅读。但是经过一个学期的学习，大家应该习惯了。当然，如果还有困难的地方，可以参考比较浅显的教材。而教材中的参考书目[2]更是一本（分三本很厚的卷）算法大全，作者是Donald E．Knuth，号称算法的宗师。该书是一本更难更全的书。完整阅读是不太可能了，但可以当很好的工具书。

三、徐士良的《常用算法程序集》是一本比较全的算法集，已经完全用C语言实现，也是可以常常查阅的工具书。

四、其实谁也不可能平时把教材上的所有算法都记得，所以学的好的标准应该是：认真琢磨

13

了教材中的算法了吗？想通了吗？读懂了吗？重要的结论而记得了吗？另外就是要选一些自己喜欢的，你觉得比较实用的算法来上机调试通过。希望假期同学们能做这件事情。曾经有一个同学花了一个假期留在学校通过上机的方式深入学习数据结构，我想他现在一定已经很熟练了。

五、数据结构中的一大重要概念是抽象数据类型，所以在后来的算法中，大家看到函数参数不在是学习C语言的时候都是基本类型，比如整型，字符型等等。中常常有一抽象到一个层次的结构作为参数，比如，队列来作为一个函数的参数辅助实现其他算法。在实际工作中，如果不是特别的要求，需要自己设计结构，很多经典结构可以使用别人实现好的。所以，C++中的继承机制可以帮助你很好地使用别人的算法。所以，特别介绍一本书：潘爱民等翻译的《C++ primer》，这本书里讲了很多泛型程序设计，教你如何使用别人的结构，虽然它是一本C++教材，而且翻译过来叫“初步入门”的教材，但是它是一本很难的教材，学完数据结构以后再看才会觉得轻松。象队列，链表，二叉树等结构在标准的C++库中已经有很好的实现，一般不用自己写了，那么为什么要学习数据结构呢，因为只有经历这个过程，你才懂得去选择使用别人的结构，比如什么时候选用链表，什么时候使用顺序表，捅排序为什么不使用数组等等。只有深入学习过，你曾经沧海，才能不轻易忘记。而在标准C++库和其他公司的库中，我觉得大家要尽量使用标准，这样才有比较好的移植性。 在非标准的库中，经过若干年的竞争，微软的MFC占了绝对的优势，而Borland 的OWL几乎消失了（但它确实是很优秀的，只是因为boland商业运作不如微软成功，Borland C++ 4.0错过了进入32位程序的最佳时机，当然，MFC组织得也很好） 。

六、如果你想解决更深入的问题，而不是熟练的程序员而已，算法值得一读。Sartaj Sahni写的《数据结构算法与应用——C++语言描述》，在各大网上书店都被评价为五星级。书的前一半写了数据结构，后一半写了经典算法，包括模拟退火，贪心算法，货郎担问题等等。建议你在在图书管借来，做一个略读。算法部分的目录如下：

第13章 贪婪算法13.1 最优化问题13.2 算法思想13.3 应用13.3.1 货箱装船13.3.2 0/昔背包问题13.3.3 拓扑排序13.3.4 二分覆盖13.3.5 单源最短路径13.3.6 最小耗费生成树13.4 参考及推荐读物

第 14章分而治之算法14.1 算法思想14.2 应用14.2.1 残缺棋盘14.2.2 归并排序14.2.3 快速排序14.2.4 选择14.2.5距离最近的点对14.3 解递归方程14.4 复杂性的下限14.4.1 最小最大问题的下限14.4.2 排序算法的下限

第 15章动态规划 15.1 算法思想15.2 应用15.2.1 0/l背包问题15.2.2 图像压缩15.2.3 矩阵乘法链

15.2.4 最短路径15.2.5 网络的无交叉子集15.2.6 元件折叠15.3 参考及推荐读物

第 16章回溯16.1 算法思想16.2 应用16.2.1 货箱装船16.2.2 0/1背包问题16.2.3 最大完备子图16.2.4 旅行商问题16.2.5 电路板排列

第17章分枝定界17.1 算法思想17.2 应用17.2.1 货箱装船17.2.2 0/1背包问题17.2.3 最大完备子图17.2.4 旅行商问题17.2.5 电路板排列

书里提供了50多个应用实例，从上面的目录看到，这本教材很注重在实际应用。

七、软件工程的教材：清华大学的张海藩写的教材薄而经典，可以使你短期内就能了解软件开发的基本过程和要点，另外，有一本书叫《敏捷软件开发》，写得实战性更强。

八、以上提到的书，大多都很贵，如果你喜欢C++，C++ primer值得买一本，可以去旧书店找找，我那本花了元（原价128），全新的，感谢那个看不下去而放弃的人让我这么便宜就买到了。呵呵。你学过了数据结构，你也该看得懂这本书了，你也去买那些看不懂而放弃的人卖到旧书点的全新的“旧书”吧。上面提到的其他书，实在太贵了，而且那些内容你现

14

在只需要了解，而不需要深入，还是去图书管借吧。

九、如果你喜欢高效率，工作涉及系统编程，或者对速度要求很高。使用C++。如果你要开发的是网络程序，电子商务平台，使用java.（国家已经决定大力投入电子商务建设，我认识的java程序员已经纷纷被挖到沿海大公司，并且身价越来越高）。这是两种应用场合很不太相同的语言,C++优势在于系统应用，而Java优势在于网络应用（因为他能跨平台）。我一直都在翻C++的书，但是我现在更喜欢使用Java，因为他很容易学，容易用，没有内存泄露（不需要你自己千万记得用C语言中的free函数或者C++中的delete），而且java是纯面向对象的，在java中，再也没有令人恶心的”全局变量”了。无论选哪一种，我建议你首先学（意思是：使用）一种语言，对另一种语言，只是常常翻一翻得到一些灵感，比如我看了C++primer以后，又去用里面告诉我的办法写java程序。事实上，当你熟悉其中一种，令一种基本上也算会了，只是熟练程度相对差一点，实在需要使用另一种的时候，你也会很快就熟练了。 杨华

15