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

《徐士良《计算机软件技术基础》（第4版）笔记和课后习题详解.docx》由会员分享，可在线阅读，更多相关《徐士良《计算机软件技术基础》（第4版）笔记和课后习题详解.docx（298页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、目录内容简介目录第1章预备知识1.1 复习笔记1.2 课后习题详解第2章基本数据结构及其运算2.1 复习笔记2.2 课后习题详解第3章查找与排序技术3.1 复习笔记3.2 课后习题详解第4章资源管理技术4.1复习笔记42课后习题详解第5章数据库设计技术5.1 复习笔记5.2 课后习题详解第6章编译技术概述6.1 复习笔记6.2 课后习题详解第7章应用软件设计与开发技术7.1 复习笔记7.2 课后习题详解第1章预备知识1.I复习笔记、集合基本概念集合是指若干个或无穷多个具有相同属性的元(元素)的集体。通常,个集合名称用大 写字母表示,而集合中的某个元素用小写字母表示。如果集合M由n (n0)个元

2、素a“& ，a”组成,则称集合M为有限集。如果个集合中有无穷多个元素,则称此集合为无 限集。不包括任何元素的集合称为空集。空集通常用表示。如果M是个集合,a是集 合M中的一个元素,则记作aGM,称元素a属于集合M;如果a不是集合M中的元素,则记 作aM,称元素a不属于集合M。(1)列举法用列举法表示一个集合是将此集合中的元素全部列出来，或者列出若干项但能根据规律可 知其所有的元素。例如:大于1而小于100的所有整数的集合A可以表示为A=2, 3, 4, ., 99(2)性质叙述法用性质叙述法表示一个集合是将集合中的元素所具有的属性描述出来。例如:大于1而小于100的所有整数的集合A可以表示为A

3、=a| la 10()的所有整数设M与N为两个集合,若M中的每个元素也为N的元素，则称M为N的子集,记作MUN, 若MUN且N中至少有一个元素aM,则称M为N的真子集，记作MuN。基本运算(1)两个集合的并设有两个集合M和N,它们的并集记作M UN,定义如下： MUN=a|aCM 或 aN(2)两个集合的交 设有两个集合M和N,它们的交集记作MAN,定义如下:MDN=a| aWM且aGN 两个集合M和N的并、交均满足交换律,即M U N=N U M MnN=NDM (3)两个集合的差设有两个集合M和N,它们的差集记作M-N,定义如下:M-N=a|aCNHllaN 两个集合的差不满足交换律,即M

4、-N 声N-M 对于集合的并、交、差有以下几点基本性质: 结合律(acib) nc=An (Bnc)(AUB) UC=AU (BUC)分配律AD (BUC) = (ACIB) U (AClC)AU (Bnc) = (AUB) n (AUC)(A-B)Uk)时,那么它含有所有的自然数，即M是自然数集。笛卡儿积0! x D2 X X D = (,)I d, e D,U = 1,2,”设有n个集合D“ D2, ., D,此n个集合的笛卡儿积定义为其中(4,d)称为n元组,d称为n元组的第i个分量。由笛卡儿积的定义可以看出,n个集合的笛卡儿积是以n元组为元素的集合,而每个n元 组中的第i个分量取自于第

5、i个集合D,。二元关系(1)笛卡儿积设M和N是两个集合,则其笛卡儿积MxN=(x, y)|xGNyGN)其中每个子集称为在MxN上的个二元关系。如果M = N,则其笛卡儿积MxM=(x, y) I x, yM其中每个子集称为在集合M上的个二元关系,简称为在集合M上的一个关系。(2)前后件、自反、对称与传递设R是集合M上的一个关系：如果(a, b) GR1则称a是b的关于R的前件,b是a的关于R的后件;如果对于每个aCM,都有(a, a) CR,则称关系R是自反的:如果对于任何aM, (a, a) GR均不成立,则称关系R是非自反的；如果（a, b） CR时必有（b, a） GR,则称关系R是对

6、称的;如果当（a, b） WR且（b, c） eR时必有（a, c） eR,则称关系R是传递的。（3）基与传递体设R是M上的个传递关系,且TUR,若对于任何（x, y） GR,在M中有元素x。,x., x2 ,x （nl）满足: Xo=X; xn=y；（x Xi） GT （i=l, 2, n）则称关系T是关系R的基,又称关系R是关系T的传递体。基本概念算法是指解题方案准确而完整的描述。算法具有如下基本特征:（1）能行性算法的能行性包括以下两个方面:算法中的每个步骤必须能够实现;算法执行的结果要能够达到预期的目的。（2）确定性算法的确定性,是指算法中的每一个步骤都必须有明确的定义，不允许有模棱两

7、可的解释 ,也不允许有多义性。（3）有穷性算法的有穷性,是指算法必须能在有限的时间内做完,即算法必须能在执行有限个步骤之 后终止。算法的有穷性还应包括合理的执行时间的含义。（4）拥有足够的情报个算法是否有效,还取决于为算法所提供的情报是否足够。综上所述，算法是组严谨地定义运算顺序的规则,并且每一个规则都是有效的,且是明 确的,此顺序将在有限的次数内终止。基本方法（1）列举法列举法的基本思想是:根据提出的问题,列举所有可能的情况,并用问题中给定的条件检 验哪些是需要的,哪些是不需要的。列举法的特点是算法比较简单。但当列举的可能情况较多时,执行列举算法的工作量将会 很大,因此需要对算法进行优化。(

8、2)归纳法归纳法的基本思想是,通过列举少量的特殊情况,经过分析，最后找出一般的关系。(3)递推法递推法是指从已知的初始条件出发,逐次推出所要求的各中间结果和最后结果。(4)递归法递归法的基本思想是在解决了逐层分解到最后的那些最简单的问题后,再沿着原来分解的 逆过程逐步进行综合。递归分为直接递归与间接递归两种。如果个算法P显式地调用自己则称为直接递归。如 果算法P调用另个算法Q,而算法Q又调用算法P,则称为间接递归调用。(5)分治法(减半递推技术)分治法,即对问题分而治之。工程上常用的分治法是减半递推技术。减半是指将问题的 规模减半,而问题的性质不变。递推是指重复减半的过程。(6)回溯法通过对问

9、题的分析,找出个解决问题的线索，然后沿着这个线索逐步试探。对于每步 试探,若试探成功,就得到问题的解;若试探失败,就逐步回退，换别的路线再进行试探。复杂度分析算法的复杂度主要包括时间复杂度和空间复杂度。(1)时间复杂度定义算法的时间复杂度是指执行算法所需要的计算工作量。客观地反应算法的效率可以用算法在执行过程中所需基本运算的执行次数来度量算法的 作量。而算法所执行的基本运算次数是问题规模的函数,即算法的工作量f (n)。其中n 是问题的规模。方法在同一问题规模下,如果算法执行所需的基本运算次数取决于某特定输入时,可以用以 下两种方法来分析算法的工作量。a.平均性态平均性态分析是指用各种特定输入

10、下的基本运算次数的带权平均值来度量算法的工作量。 设X是所有可能输入中的某个特定输入，P(X)是X出现的概率，t(X)是算法在输入为X 时所执行的基本运算次数,则算法的平均性态定义为A(n) = / pwd”b.最坏情况复杂性W(打)=max(x) 了最坏情况分析是指在规模为n时,算法所执行的基本运算的最大次数。它定义为:(2)空间复杂度个算法的空间复杂度是指执行这个算法所需要的内存空间。一个算法所占用的存储空间包括算法程序所占的空间、输入的初始数据所占的存储空间以 及算法执行过程中所需要的额外空间。其中额外空间包括算法程序执行过程中的工作单元 以及某种数据结构所需要的附加存储空间。如果额外空

11、间量相对于问题规模来说是常数, 则称该算法是原地工作的。1.2课后习题详解集合M = d” d2 d3,ds, 4上的一个关系R如下:R= (di, d2) , (d2, d&) , (d5, d4) , (di, d5) , (di, th) , (di, d6) , (di, d3 ),(d3, d6)试验证Ti= (d, d2) , (d2, 0(), (di, d3) , (&, &) , (d5, &) , (di, d5) 是 R的具有6个元素的基,而T2= (d2, d4) , (di, d3) , (di, d2) , (ds, ds) 不是R的 基。答:对于T”显然满足TR,

12、且对于关系R中的每一个二元组(x, y),在M中存在元素RX0，2（,）d , dz(di,dz)Ti(dz,)dz 9d4（,）6%（ds,）d$ 9 d4（,）6。(dltd5)di0,4)Ti(dt,d.)d 9 dz, d(.d ydz) Cdz ,d&) W T（,）（,），（,）er（,&）d !6?3（4，4）GT】（4，）4（,）Xo, Xi, X2, ., X,满足基的三个条件。验证过程如下：由上可知,是R的具有6个元素的基。对于T”由于（do, ds） 0R,因此,T2不是R的基。设给定三个整数a, b, c,试写出寻找其中数的个算法（用C/C+描述）,并分析在平 均情况与

13、最坏情况下,算法分别要进行多少次比较?答:算法的C+描述如下:/chl.qjpincludeciostreanusing namespace std;int mid(int a,int b,int c)(intm;m=a;,吁页设a为中数if(m=b)(if(m=c)(if(b=c) m=b; /b 为中数else m=c; c 为中数)else(if(m-c) m=ci c 为中数else m=b; /b 为中数)return (m);j返回中数假设a, b, c中的每一个数为中数的概率相等(均为1/3)。由于当a为中数时需要比较2次2X(l/3)+3X(l/3)+3X(l/3) = 8/3

14、,b或c为中数时均需要比较3次,因此,在平均情况下上述算法所需要的比较次数为即在平均情况下，上述算法需要比较(8/3)次。在最坏情况下,上述算法需要比较3次(当b或c为中数时)。主函数例如下:intmain()(int a,b,c;cout input 丄 b,c=；cinabc;coutm=mid(a,b,c)endl;return 0;运行结果如下(带有下划线的为键盘输入)：input a,b,c=4 8 3m=4利用减半递推技术,写出求长度为n的数组中最大元素的递归算法(用C/C+描述)。设n =2k,其中kNl。答:利用减半递推技术,求数组中最大元素的递归过程如下:如果数组中只有一个元

15、素, 则该元素即是数组中最大的元素。否则将数组对分为前半部分和后半部分：用同样的方法求数组前半部分的最大值maxi。用同样的方法求数组后半部分的最大值max 2若maxlmax2,则maxi为数组中的最大值;否则max2为数组中的最大值。算法的C+描述如下：chl_2.cpp?mcludeusing namespace std;int maxa(int a,int m,int n)(intd5dl,d2;if(m=n) return (am-l);else(d 1 =maxa( a1ms (m-n) 2);d2=maxa(a,(m*n),2+l sn);if(dld2)d=dl;elsed=d

16、2;return (d);主函数例如下：int main()(mt a( 16 卜15,6,4“ 521,737851.40 6,43,49,6327; coutmax-maxa(i, 1,16)ajdl,return 0;)运行结果如下:max=78编写二分法求方程实根的减半递推算法(用C/C+描述)。/chl_3.cpp include mclude using namespace std;double root(double a,double bdouble eps, double (*f)(double) (doublewhile( fabs( a-b)=eps) (c=(a*b) 2

17、;n(*fXc)；if(fl+1.01.0)答:算法的C+描述如下:retum(c);if(f0*fl0)a=c;取区间后半部分elseb=c;。取区间前半部分)c=(a*b) 2;retum(c);)主函数例如下:int main。(double a=0.0,b=3.0;double f( double);coutroot(丄 b,0.0000IQvvendl;return 0;)double f(double x)(return(x*x*x-x*x-1.0);)运行结果如下:1.46557编写用回溯法求解皇后问题的算法（用C/C+描述）。 答:算法的C+描述如下:chl_4 cpp#inc

18、lude2?include#includeusing namespace std;void queen(int n)(inti,j,k,jt,*q;q=nexv intn;for(i=0;in;i-Hh)qi=0；i-0;jt=l；coutn?,queen problem?,endl;while(jt=l)(k-0;while(kfabs(k-i)!M) kfif(ki)砒 else i-i+1;(for(j=0jA(12),则 A (12)坏且轻若 A(l) A(10) +A(11), 则A (9)坏目重或A (10)与A (11)中有坏且轻若 A (10) =A (11),则 A (9)坏

19、目重若 A (10) A (11),则 A (11)坏且轻若 A (10) A (11),则 A (10)坏且轻若 A(l) +A(9) A (11),则 A (11)坏且重若 A (10) A(5) +A(6) +A +A(8)则A，A， A (3), A (4) 中有坏且重或 A(5), A(6), A (7), A (8) 中有坏且轻若 A (1) +A (2) +A (6) =A (3)+A (4) +A (5),贝 A (7), A (8)中有坏且轻若A(l) =A(7),则A (8)坏且轻若A (1)卢A (7),则A (7)坏且轻若 A +A (2) +A (6) A (3)+A

20、 (4) +A (5),则 A (1), A 中有坏且重,或A (5)坏且轻若A(l) =A (2),则A (5)坏且轻若A(l) A(2),则A (1)坏且重若A(l) A(2),则A (2)坏且重若 A (1) +A (2) +A (6) A(4),则A (3)坏目重若A (3) A(4),则A (4)坏且重若 A(l)+A(2) +A (3) +A (4) A (3)+A (4) +A (5),则 A (3), A (4)中有坏且轻,或A (6)坏且重若A (3) =A (4),则A (6)坏且重若A(3) A(4),则A (4)坏且轻若A (3) A(4),则A (3)坏且轻若 A (

21、1) +A (2) +A (6) A (2),则A (2)坏且轻若AA(2),则A (1)坏且轻根据表1-1所示的比较过程,可以写出算法的C+描述如下:,chl_5-cpp?rincludeusmg namespace std;int al2(int afl)(if(al+a2亠a3-a4=a5卜a6-a7卜a8) ，a9, a10, all, a12中有坏 if(alha9=a10-all) 间12坏if(ala12)retum(-12); al2坏且轻elseretum(12); 间12坏且重elseif(al-a9a10-all)a9坏且重,或 a10与 aU中有坏且轻if(a10=al

22、l)retuni(9);a9坏且重&seiallDretum(-ll);a 11 坏且轻elseretum(-10);坏目轻else，司9坏且轻,或a10与屮1中有坏且重if(a10=aH)retum(-9);a9坏且轻elseif(a10all)retum(lO);a10坏且重elseretum(ll);a 11 坏目重&seif(al+a2+a3+a4a习+a6+a7+a8D/al, a2, a3a4中有坏且重,或a5,旳切,a8中有坏且轻if(al-a2+a6=43-14卜a5)，a7, a8中有坏且轻if(al=a7)retum(-8);a8坏且轻elseretum(-7);旬T坏且轻

23、elseif(ala(2-a643-a4-a5Dal a2中有坏且重,或-5坏且轻if(al=a2)retam(-5); a5坏且轻elseif(ala2)retum(l);al坏且重elseretum(2);，a2坏目重else /闻3, a4冲有坏且重,或a6坏且轻if(a3=a4)retuni(-6);间6坏且轻else if(a3a4)retum(3); h a3坏且重elseretum(4);a4坏且重else /a(l, a2, a3皿中有坏且轻,或a6明,晒中有坏且重国a-a2-a6=a3-a4卜a习)Za7, a8中有坏且重if(al-a7)retum(8); / a8坏且重e

24、lsereturn;厶a7坏且重else if(al-a2 +aa3-a4 +a习)/闻3 a4中有坏且轻,或 a6坏且重 if(a3=a4)retuni(6); / a(习坏且重else if(a(3a4)retum(-4);a4坏且轻elseretum(-3)ia3坏且轻else间1, a2中有坏且轻,或a坏且重if(al=a2)retuni(5);a5坏且重elseif(ala2)retum(-2);a2坏且轻elseretum(-l);询1坏且轻)在上述C程序中,为了直观起见,定义的数组长度为13,其中数组元素a0在程序中不用。主函数例如下:intmainO(im a口 3=0,5,5

25、,5,555545555;coutf,k=0)个数据元素4, a”，a”组成的个有限序列。矩阵也是个线性 表,在矩阵中,既可以把每一行看成是一个数据元素，也可以把每一列看成是一个数据元 素。其中,每个数据元素实际上又是个简单的线性表。非空线性表有如下些结构特征:有且只有一个根结点a”它无前件;有且只有一个终端结点,它无后件;除根结点与终端结点外,其他所有结点有且只有一个前件,也有且只有一个后件。(2)顺序存储结构线性表的顺序存储结构具有以下两个基本特点:线性表中所有元素所占的存储空间是连续的;线性表中各数据元素在存储空间中是按逻辑顺序依次存放的。在程序设计语言中,通常定义个维数组来表示线性表的

26、顺序存储空间。在用维数组 存放线性表时,该维数组的长度通常要定义得比线性表的实际长度略大,以便对线性表 进行各种运算,特别是插入运算。建立一个容量为m的空线性表的顺序存储空间的C+描述如下:templatecnpename T模板声明,T为类型参数void init_sq_LList(T * v,int msmt *n)new Tm;动态申请存储空间*n=0i线性表长度置为return; ）在上述描述中,T为线性表中元素的虚拟数据类型。要释放线性表的顺序存储空间时,可以用“deletev； （3）顺序存储下的插入运算假设线性表的存储空间为V （1： m）,线性表的长度为n （nn时，认为在最后

27、个元素之后插入;c,当il时,认为在第1个元素之前插入;从最后个元素开始,直到第i个元素,其中每个元素均往后移动个位置;最后将新元素b插入到第i个位置,并且将线性表的长度增加1。线性表在顺序存储结构下插入算法的C+描述如下:Iinclude using namespace std;template模板声明,T为类型参数void ins_sq_LLi8t (T * v, int m, int * n, int i, T b) iint k;if (*n-m)存储空间已満,上溢错误 coutMoverflow!nw;return; if (i * n) i- n+1;默认为在最后个元素之后插入if

28、C)，7,蒙认为在第一个元章之前揄入for (k* n; k-l； k-)vkvlk-i;从最后个元米开始,直到第i个元索均往后移动个位臂v(i-lj-b;插入新元素* n- n*l;线性或长度增加1return;（4）顺序存储下的删除运算假设线性表的存储空间为V （1： m）,线性表的长度为n （nm）,删除的位置为i,则删 除的过程如下:首先处理以下两种异常情况。a.当线性表为空时为“下溢”错误,不能进行删除,算法结束;b,当in时,认为在最后个元素之后删除。从第i+1个元素开始,直到最后个元素，其中每个元素均依次往前移动个位置;最后将线性表的长度减1。（5）顺序表类下面的描述是将顺序表的

29、数据和基本操作（初始化、输出、插入与删除操作）封装成一个 sq丄List 类:/模板声明,数据元索虚拟类型为T顺序表类数据成员存储空间容依顺序表长度顺序表存储空间首地址成员函数return;)建立空顺序表,申请存储空间順序输出順序表中的元素与顺序表长度检测顺序表的状态/在表的指定元索前插入新元素/sq_LList.h#include using namespace std; template class sq_LList private: int mm; int nn; T * v;public:sq_LList() mm=O; nnO; sq_LList(int);void prt_sq_L

30、List (); int flag_sq_LList ();void ins sq_LList (int, T);void del-SqList(int);在表中B(除指定元素建立空顺序表存储空间容置动态申请存储空间顺序衰长度为。,即建立空顺序表template sq_LList :sq_LList(int m) m/n-m;vnew TfmmJ;nn0;recurn;顺序输出廡序表中的元素与顺序表长度tempiatevoid sq_LList ： :prt_sq_LLlst () int i;cout nnn- nn endl ；for (t0; inn； i+ + ) coutv(1 en

31、d 1; return;检测顺序表的状态template存储空间已満,返回一】 顺序表为空，返回0 正常返回1int sq_LLiSt : flag_sq List ()(if (nnmn) return(-1)； if (nn-0) return(0); return ;在表的指定元素前插入新元素templatevoid sq_LList : ins_sq tList (int i, T b) (int k;if (nn*iwn)( coutoverfLowHendl;if nZ1;if i*i; k-) vjk)*vjk-l);vim ;nn-nn*l;存储空间已需，上溢槍误return；

32、）跃认为在敷后个元素之后捕人默认为在第一个元素之前插入从最后个元家直到第i个元素均后移个位置摘入新元素顺序表长度加1return；在翔洋表中髭除指定元素templatevoid sqLList :del_sg_LList (int i) I int k;if (nn0)顺用表为空，下溢幡谈I coutunderflow!endl; return; if顺序表中没有这个元案( coutNot this element in the list!Mendl; return;)for (ki; knn; k+ + )vk-l)-vk;从第i个元素直到最后个元素均前移个位置nnnn-l;顺序表氏度减!return;利用顺序表类中的成员函数flag_sq_LList ()可以解决上溢错误信息没有返回给调用程序 ，调用程序无法处理的情况。成员函数flag.sq.LList ()的功能是检测顺序表的当前状态 若顺序表满,则返回函数值1；若顺序表空,则返回函数值;正常情况则返回函数值1。栈及(1)定义栈实际上也是线性表,只不过是种特殊的线性表。其插入和删除运算都只在线性表的 端进行。在栈中,将允许插入与删除的一端称为栈顶,将不允许插入与删除的一端称为栈底。栈顶 元素总是最后被插入的元素,也是最先被删除的元素;栈底元素总是最先被插入的元素, 也是最后被删除的元素。即栈是按照“先进后