徐士良《计算机软件技术基础》（第4版）笔记和课后习题详解

下载地址:http://free.100xuexi.com/Ebook/132091.html
目录                                                                                        封面
内容简介
目录
第1章　预备知识
　1.1　复习笔记
　1.2　课后习题详解
第2章　基本数据结构及其运算
　2.1　复习笔记
　2.2　课后习题详解
第3章　查找与排序技术
　3.1　复习笔记
　3.2　课后习题详解
第4章　资源管理技术
　4.1　复习笔记
　4.2　课后习题详解
第5章　数据库设计技术
　5.1　复习笔记
　5.2　课后习题详解
第6章　编译技术概述
　6.1　复习笔记
　6.2　课后习题详解
第7章　应用软件设计与开发技术
　7.1　复习笔记
　7.2　课后习题详解
                                                                                                                                                                                                    内容简介                                                                                            


徐士良所著的《计算机软件技术基础》（第4版，清华大学出版社）是我国高校采用较多的计算机软件技术基础优秀教材，也被众多高校指定为“计算机软件技术基础”专业考研参考书目。
作为该教材的辅导书，本书具有以下几个方面的特点：
1．整理名校笔记，浓缩内容精华。在参考了国内外名校名师讲授徐士良《计算机软件技术基础》的课堂笔记基础上，本书每章的复习笔记部分对该章的重难点进行了整理，同时对重要知识点进行点拨，因此，本书的内容几乎浓缩了配套教材的知识精华。
2．解析课后习题，提供详尽答案。本书参考大量计算机软件技术基础相关资料对该教材的重难点课（章）后习题进行了详细的分析和解答，并对相关重要知识点进行了延伸和归纳。
                                                                                                                                    本书更多内容>>
                                                                                                                                                                                                                    使用说明                                                                                                   
                                                                                    

内容预览
第1章　预备知识
1.1　复习笔记
一、集合
（一）基本概念
集合是指若干个或无穷多个具有相同属性的元（元素）的集体。通常，一个集合名称用大写字母表示，而集合中的某个元素用小写字母表示。如果集合M由n（n≥0）个元素a1，a2，…，an组成，则称集合M为有限集。如果一个集合中有无穷多个元素，则称此集合为无限集。不包括任何元素的集合称为空集。空集通常用Φ表示。如果M是一个集合，a是集合M中的一个元素，则记作a∈M，称元素a属于集合M；如果a不是集合M中的元素，则记作a?M，称元素a不属于集合M。
1．列举法
用列举法表示一个集合是将此集合中的元素全部列出来，或者列出若干项但能根据规律可知其所有的元素。例如：
大于l而小于100的所有整数的集合A可以表示为
A = {2，3，4，…，99}
2．性质叙述法
用性质叙述法表示一个集合是将集合中的元素所具有的属性描述出来。例如：大于l而小于100的所有整数的集合A可以表示为
A = { a | 1-1。
定义1.3 若A、B两个集合有一一映射ｆ存在，使f（A）=B，则称Ａ与B成一一对应，Ａ与Ｂ对等，记作A~B。
集合的对等具有以下性质：
自反性：A~A
对称性：若A~B，则B~A
传递性：若A~B且B~C，则A~C
（三）自然数集与数学归纳法
由所有自然数组成的集合{1,2,3，…}称为自然数集。自然数集是一个无限集。
由自然数组成的集合均是自然数集的子集。自然数集的子集可以是有限集，也可以是无限集。
定理1.1 在自然数集的任一非空子集M中，必定有一个最小数。
定理1.2 设M是由自然数形成的集合，如果它含有l，2，…，k，并且当它含有数n-l， n-2，…，n-k（n>k）时，那么它含有所有的自然数，即M是自然数集。
（四）笛卡儿积
设有n个集合D1，D2，…，Dn，此n个集合的笛卡儿积定义为

其中（d1，d2，…，dn）称为n元组，di称为n元组的第i个分量。
由笛卡儿积的定义可以看出，n个集合的笛卡儿积是以n元组为元素的集合，而每一个
n元组中的第i个分量取自于第i个集合Di。
【例1.1】设有三个集合

则他们的笛卡尔积为

如果n个集合D1，D2，···，Dn中的元素个数分别为m1，m2，···，mn，则其笛卡尔积中共有m1×m2×···×mn个n元组。即n个集合的笛卡尔积是所有n元组组成的集合。
（五）二元关系
定义1.4设M和N是两个集合，则其笛卡儿积
M × N= {(x，y) | x ∈ M 且 y ∈N}
的每一个子集称为在M×N上的一个二元关系。
如果M=N，则其笛卡儿积
M ×M= {(x，y) | x，y∈ M }
的每一个子集称为在集合M上的一个二元关系，简称为在集合M上的一个关系。
【例1.2】设集合M为
M = { a，b，c，d，e，f}
则下列每一个二元组的集合是在集合M上的一个关系：

集合M上的一个关系实际上反映了集合M中各元素之间的联系。
定义1.5 设R是集合M上的一个关系。
（１）如果（a，b）∈R，则称a是b的关于R的前件，b是a的关于R的后件。
（２）如果对于每一个a∈M，都有（a，a）∈R，则称关系R是自反的；如果对于
任何a∈M，（a，a）∈R均不成立，则称关系R是非自反的。
（３）如果（a，b）∈R时必有（b，a）∈R，则称关系R是对称的。
（４）如果当（a，b）∈R且（b,，c）∈R时必有（a，c）∈R，则称关系R是传递的。
在【例1.2】中，关系R1是非自反的，但不是对称的，也不是传递的；关系R2是对称的，但不是自反的，不是非自反的，也不是传递的；关系R3是自反的，但不是对称的，也不是传递的；关系R4是传递的，且是非自反的，但不是对称的。
定义1.6设Ｒ是Ｍ上的一个传递关系，且Ｔ?Ｒ，若对于任何（x，y）∈Ｒ，在Ｍ中有元素

则称关系Ｔ是关系Ｒ的基，又称关系Ｒ是关系Ｔ的传递体。
二、算法
（一）基本概念
算法是指解题方案准确而完整的描述。
算法具有如下基本特征：
1．能行性
算法的能行性包括以下两个方面：
（1）算法中的每一个步骤必须能够实现。
（2）算法执行的结果要能够达到预期的目的。
2．确定性
算法的确定性，是指算法中的每一个步骤都必须有明确的定义，不允许有模棱两可的解释，也不允许有多义性。
3．有穷性
算法的有穷性，是指算法必须能在有限的时间内做完，即算法必须能在执行有限个步骤之后终止。算法的有穷性还应包括合理的执行时间的含义。
4．拥有足够的情报
一个算法是否有效，还取决于为算法所提供的情报是否足够。
综上所述，算法是一组严谨地定义运算顺序的规则，并且每一个规则都是有效的，且是明确的，此顺序将在有限的次数内终止。
（二）基本方法
1．列举法
列举法的基本思想是：根据提出的问题，列举所有可能的情况，并用问题中给定的条件检验哪些是需要的，哪些是不需要的。
列举法的特点是算法比较简单。但当列举的可能情况较多时，执行列举算法的工作量将会很大，因此需要对算法进行优化。
【例1.3】设每只母鸡值3元，每只公鸡值2元，两只小鸡值1元。现要用100元钱买100只鸡，设计买鸡方案。
假设买母鸡i只，公鸡j只，小鸡k只。根据题意，粗略的列举算法用C++描述如下：
//baiji1.cpp
#include
using namespace std;
int main()
{
int i,j,k;
for(i=0;i。但只要对问题进行分析，就会发现对这个算法还可进行优化，减少大量不必要的循环次数。
首先，考虑到母鸡为3元一只，因此，母鸡最多只能买33只，其次，考虑到公鸡为2元一只，因此，公鸡最多只能买50只。又考虑到对公鸡的列举是在算法的第二层循环中，此时已经买了i只母鸡，且买一只母鸡的价钱相当于买1.5只公鸡。因此，由第一层循环已经确定买i只母鸡的前提下，公鸡最多只能买50-1.5i只， 最后，考虑到买的总鸡数为l00，而由第一层循环已确定买i只母鸡，由第二层循环已确定买j只公鸡，因此，买小鸡的数量只能是K=100-i-j只，即第三层循环已经没有必要了。
经过以上分析，可以将上述算法进行修改。经修改后的算法用C++描述如下：
//baiji2.cpp
#include
using namespace std;
int main()
{
int i,j,k;
for(i=0;i<=33;i++)
for(j=0;j<=50-1.5*i;j++)
{
k=100-i-j;
if(3*i+2*j+0.5*k==100.0)
cout<<i<<""<<j<<" "<<k<<endl;
}
return 0;
}
程序运行结果如下：
2 30 68
5 25 70
8 20 72
11 15 74
14 10 76
17　 5 78
20　 0 80
2．归纳法
归纳法的基本思想是，通过列举少量的特殊情况，经过分析，最后找出一般的关系。
3．递推法
递推法是指从已知的初始条件出发，逐次推出所要求的各中间结果和最后结果。
4．递归法
递归法的基本思想是在解决了逐层分解到最后的那些最简单的问题后，再沿着原来分解的逆过程逐步进行综合。
递归分为直接递归与间接递归两种。如果一个算法P显式地调用自己则称为直接递归。如果算法P调用另一个算法Q，而算法Q又调用算法P，则称为间接递归调用。
5．分治法（减半递推技术）
分治法，即对问题分而治之。工程上常用的分治法是减半递推技术。“减半”是指将问题的规模减半，而问题的性质不变。“递推”是指重复“减半”的过程。
【例1.4】设方程f（z）=0在区间[a，b]上有实根，且f（a）与f（b）异号。利用二分法求该方程在区间[a，b]上的一个实根。
二分法求方程实根的减半递推过程如下：首先取给定区间的中点c=（a+b）／2。
然后判断f（c）是否为0。若f（c）=0，则说明c即为所求的根，求解过程结束；如果f（c）≠0，则根据以下原则将原区间减半。
若f（a）f（c）<0，则取原区间的前半部分；若f（b）f（c）<0，则取原区间的后半部分。最后判断减半后的区间长度是否已经很小。
若|a-b|<ε，则过程结束，取（a+b）／2为根的近似值；若|a-b|≥ε，则重复上述的减半过程。
6．回溯法
通过对问题的分析，找出一个解决问题的线索，然后沿着这个线索逐步试探。对于每一步试探，若试探成功，就得到问题的解；若试探失败，就逐步回退，换别的路线再进行试探。这种方法称为回溯法。
（三）复杂度分析
算法的复杂度主要包括时间复杂度和空间复杂度。
1．时间复杂度
（1）定义
算法的时间复杂度是指执行算法所需要的计算工作量。
客观地反应算法的效率可以用算法在执行过程中所需基本运算的执行次数来度量算法的工作量。而算法所执行的基本运算次数是问题规模的函数，即算法的工作量f（n）。其中n是问题的规模。
（2）方法
在同一问题规模下，如果算法执行所需的基本运算次数取决于某一特定输入时，可以用以下两种方法来分析算法的工作量。
①平均性态
平均性态分析是指用各种特定输入下的基本运算次数的带权平均值来度量算法的工作量。
设x是所有可能输入中的某个特定输入，P（x）是x出现的概率，t（x）是算法在输入为x时所执行的基本运算次数，则算法的平均性态定义为

②最坏情况复杂性
最坏情况分析是指在规模为n时，算法所执行的基本运算的最大次数。它定义为

【例1.5】采用顺序搜索法，在长度为n的一维数组中查找值为z的元素。即从数组的第一个元素开始，逐个与被查值z进行比较。基本运算为z与数组元素的比较。
首先考虑平均性态分析。
设被查项z在数组中的概率为q。当需要查找的z为数组中第i个元素时，则在查找过程中需要做i次比较。当需要查找的z不在数组中时，则需要和数组中所有的元素进行比较。即

其中i=n+1表示z不在数组中的情况。
如果假设需要查找的z出现在数组中每个位置上的可能性是一样的，则z出现在数组中每一个位置上的概率为q／n，而z不在数组中的概率为l-q。即

因此，用顺序搜索法在长度为n的一维数组中查找值为z的元素时，在平均情况下需要的比较次数为

如果已知需要查找的z一定在数组中，此时q=1，则A（n）=（n+1）／2。在这种情况下，用顺序搜索法在长度为n的一维数组中查找值为z的元素时，在平均情况下需要检查数组中一半的元素。
如果已知需要查找的z有一半的机会在数组中，此时q=1／2，则

在这种情况下，用顺序搜索法在长度为n的一维数组中查找值为z的元素，在平均情况下需要检查数组中3／4的元素。
再考虑最坏情况分析。
最坏情况发生在需要查找的z是数组中的最后一个元素或z不在数组中的时候，此时

2．空间复杂度
一个算法的空间复杂度是指执行这个算法所需要的内存空间。
一个算法所占用的存储空间包括算法程序所占的空间、输入的初始数据所占的存储空间以及算法执行过程中所需要的额外空间。其中额外空间包括算法程序执行过程中的工作单元以及某种数据结构所需要的附加存储空间。如果额外空间量相对于问题规模来说是常数，则称该算法是原地工作的。

下载地址:http://free.100xuexi.com/Ebook/132091.html