软件技术基础复习

软件技术基础复习2023/2/11、页式存储中，知道逻辑地址求对应物理地址。1.分页存储管理的基本思想

用户程序的地址空间被划分成若干固定大小的区域，称为“页”，相应地，内存空间分成若干个物理块，页和块的大小相等。可将用户程序的任一页放在内存的任一块中，实现了离散分配。2.

分页存储管理的地址机构

15

1211

0

页号P

页内位移量W

页号4位，每个作业最多24=16页，表示页号从0000~1111（24-1），页内位移量的位数表示页的大小，若页内位移量12位，则212=4k，页的大小为4k，页内地址从000000000000~111111111111

若给定一个逻辑地址为A，页面大小为L，则

页号P=INT[A/L]，页内地址W=A

MOD

L地址结构及页面大小设置页面的划分完全是一种系统硬件的行为。地址结构如下：页内地址页号3112110在这个完整的32位地址结构中，页号占10位、页内偏移量（也叫页内地址）占12位，页面大小为4KB。若给定某一个逻辑地址（或相对地址），通过下面式子可以得出页号和页内偏移量：

页号=逻辑地址DIV页面大小页内偏移量=逻辑地址MOD页面大小例如页面大小为4KB的系统中，若逻辑地址为28024由上式求得28024div4096=6（页号）

28024mod4096=3448（页内偏移量）00000000

0000

0000011011010111100028024页号6页内地址3448某采用分页存储管理的系统中，物理地址占20位，逻辑地址中页号占6位，页大小为1K，问：（1）该系统的内存空间大小是多少？每块的大小是多少？（2）逻辑地址共几位，每个作业最大长度是多少？(1)内存空间大小为220=1M。每块的大小为1K(2)逻辑地址16位。每个作业最大长度为64K实例：在采用页式存储管理的系统中，某作业J的的逻辑地址空间为4页（每页2048字节），且已知该作业的页面映象表如下：试借助地址变换图（画出地址变换图）求出有效逻辑地址4865所对应的物理地址。某分页式存储管理系统存放了一个具有5个页面的作业，页面按页号从小到大存放的块号分别为5，10，3，6，20设每页大小为4096字节。（1）请画出该作业的页表（2）每块页面在内存中的起始地址（3）作业中语句MOV[10000],2345中逻辑地址10000使用哪块页面，在内存的物理地址为多少？页号块号起始地址0520480110409602312288362457642081920逻辑地址10000对应的页号为10000/4096＝2，页内地址为10000％4096＝

1808，2号页面对应的块号为3，所以逻辑地址10000对应内存单元地址为12288＋1808＝14096

2、P,V操作信号量机制荷兰著名科学家，后来的计算机图灵奖获得者，E.W.Dijkstra于1965年提出了用作进程同步工具的信号量（semaphore）机制，这是一种卓有成效的进程互斥同步工具，已被广泛应用于现代计算机系统中。信号量的思想：两个或多个进程可以利用彼此间收发的简单的信号来实现“正确的”并发执行，一个进程在收到一个指定信号前，会被迫在一个确定的或者需要的地方停下来，从而保持同步或互斥。经典的整型信号量＝》经记录型信号量＝》信号量集机制CPU忙等造成死锁不易死锁，可能导致资源利用率低1.整型信号量最初由Dijkstra将信号量定义为一个整型量SS是个具有非负初值的整型变量，表示该信号量的值，且S的值只能由定义在信号量上的P操作原语和V操作原语来改变；2.记录型信号量

P（Passeren/proberen

）、V（Vrijgeren/verhogen

）是荷兰语，分别代表“通过/测试或等待”及“释放/增加或发信号”。信号量S值的物理含义：

当S≥0时，表示某类可用资源的数目，或者说表示可以执行P操作而不会被阻塞的进程的数目；当S＜0时，其绝对值表示信号量S的阻塞队列中的进程数，即系统中因请求该类资源而被阻塞的进程的数目，亦即被信号灯挡住的进程数目，这些进程需要别的进程发出相应的信号灯来唤醒。另外，S的值只能由P、V操作来改变。

P(S)操作和V(S)操作的物理含义：P(S)操作表示“等信号”，即测试一个要等的信号是否到达；V(S)操作表示“发信号”。这个信号在实现同步时就是“合作者的伙伴进程已完成前趋任务”，在实现互斥时就是“临界资源可用”。另外，在互斥问题中，每执行一次P(S)操作的含义，也可理解为进程请求一个单位的S类资源；每执行一次V(S)操作的含义，也可理解为进程释放一个单位的S类资源。信号量应用1.利用P、V操作原语实现进程的互斥即保证进程互斥地进入各自的临界区。这里所用信号量的初值一般为1，表示临界资源未被占用，且其可用数目为1。

用P、V操作原语实现进程互斥的效率更高一些，因为P操作中引入了阻塞机制，所以消除了CPU忙等现象。三个进程互斥进入临界区P(S)V(S)临界区P(S)V(S)临界区P(S)V(S)临界区P1P2P3互斥区然后P1、P2同时竞争P操作，设P1先执行设P3先进入此时s-1->s于是s=0设P3退出后此时s+1->s于是s=1P1执行后此时s-1->s于是s=0P2执行此时s-1->s于是s=-1，阻塞P1退出：此时s+1->s于是s=0≤0，释放P2P2退出后此时s+1->s于是s=1P、V操作也都是配对出现，但对同一个信号量的P、V操作却不是同时出现在每一个进程的程序里，而是分别出现在一个进程和它的合作伙伴的代码中。解答这类进程同步问题的主要步骤也是有三步：(1)分析清楚题目涉及的进程间的制约关系(2)设置信号量（包括信号量的个数和初值及其物理含义），合作进程间需要收发几条消息相应就设置几个信号量。同步信号量的初值一般为0，表示得到合作进程的消息后才能向前推进。(3)给出进程相应程序的算法描述或流程控制，并把P、V操作加到程序的适当处。2.用P、V操作实现进程的同步例1:生产者—消费者问题公用缓冲池，有n个缓冲区一组生产者生产产品一组消费者取走产品【问题分析】①生产者—消费者之间的同步关系表现为：一旦缓冲池中所有缓冲区均装满产品时，生产者必须等待消费者提供空缓冲区；一旦缓冲池中所有缓冲区全为空时，消费者必须等待生产者提供满缓冲区。②生产者—消费者之间还有互斥关系：由于缓冲池是临界资源，所以任何进程在对缓冲区进行存取操作时都必须和其他进程互斥进行。生产者－消费者问题是相互合作进程关系的一种抽象【问题解答】①所用信号量设置如下：

Ⅰ）同步信号量empty，初值为n，表示消费者已把缓冲池中全部产品取走，有n个空缓冲区可用。

Ⅱ）同步信号量full，初值为0，表示生产者尚未把产品放入缓冲池，有0个满缓冲区可用。

Ⅲ）互斥信号量mutex，初值为1，以保证同时只有一个进程能够进入临界区，访问缓冲池。

②用信号量机制解决生产者—消费者问题的算法描述如下：生产者i

消费者j生产出一产品；

P（full）；P（empty）；

P（mutex）；P（mutex）；

从缓冲区取出一产品；将该产品放入缓冲区；

V（mutex）；V（mutex）；

V（empty）；V（full）；

消费该产品；

实例总结，可以得出这样的结论：实现进程的同步互斥实际就是给进程的并发执行增加一定的限制，以保证被访问的共享数据的完整性和进程执行结果的可再现性。用信号量机制解这类题的三个步骤：（1）分析进程间的制约关系（2）设置信号量（3）实施P、V操作。第一步是基础、关键，第三步是核心。掌握实现进程互斥与进程同步的第三步在形式上差异：即P、V操作总是配对出现的。但P,V在互斥问题中总是出现在同一个进程的代码中，且紧紧夹着临界区；而在同步问题中，却是分别出现在两个合作进程的代码中，需要等消息的一方用P操作，相应的对同一信号量的V操作则在发出此消息的另一方中。

3、查找

Hash函数

折半查找312726211916130911050102H(K)=int(K/3)+1121110987654321表项序号根据关键字直接计算出元素所在位置的函数。例如：设哈希函数为：

int(K/3)+1则构造01、02、05、09、11、13、16、19、21、26、27、31、的散列表(哈希表）为：哈希函数：冲突：两个不同的关键字具有相同的存储位置。

2、

构造哈希函数的方法

（1）直接定址法——取关键字或关键字的某个线性函数值为散列地址，即H（K）=K或H（K）=A*K+B；（其中A、B为常数）直接定址哈希函数示例：某公司一险种投保费交纳表（20年），将年份作关键字，哈希函数取关键字本身，若查找第3年应交纳的保费，只要查找表的第3项即可。地址010203……20年份123…….20保费…….…….…….…………

（2）平方取中法——取关键字平方后的中间几位为哈希函数。如：K=308，K2=94864，H（K）=486（3）除后余数法——取关键字被不大于散列表表长m的数p除后所得的余数为哈希函数。即H（K）=KMODp（pm）3、处理冲突的方法

例已知一组关键字（19,14,23,1,68,20,84,27,55,11,10,79),哈希函数为：H(key)=keyMOD13,哈希

表长为m=16，设每个记录的查找概率相等用线性探测再散列处理冲突，即Hi=(H(key)+di)MODm（19,14,23,1,68,20,84,27,55,11,10,79)H(key)=keyMOD13H(55)=3冲突

H1=(3+1)MOD16=4冲突

H2=(3+2)MOD16=5H(79)=1冲突

H1=(1+1)MOD16=2冲突

H2=(1+2)MOD16=3冲突

H3=(1+3)MOD16=4冲突

H4=(1+4)MOD16=5冲突

H5=(1+5)MOD16=6冲突

H6=(1+6)MOD16=7冲突

H7=(1+7)MOD16=8冲突

H8=(1+8)MOD16=9H(19)=6H(14)=1H(23)=10H(1)=1冲突

H1=(1+1)MOD16=2H(68)=3H(20)=7H(84)=6冲突

H1=(6+1)MOD16=7冲突

H2=(6+2)MOD16=8H(27)=1冲突

H1=(1+1)MOD16=2冲突

H2=(1+2)MOD16=3冲突

H3=(1+3)MOD16=4H(11)=11H(10)=10冲突

H1=(10+1)MOD16=11冲突

H2=(10+2)MOD16=120123456789101112131415地址关键字探测次数191141231

12681201843274553111103799(2)用链地址法处理冲突012345678910111214^127796855198420231011^^^^^^^^^^^^关键字(19,14,23,1,68,20,84,27,55,11,10,79)折半查找(binarysearch)

折半查找,亦称二分查找。查找过程：每次将待查记录所在区间缩小一半。适用条件：采用顺序存储结构的有序表。算法实现：设表长为n，low、high和

mid分

别指向待查元素所在区间的下界、上界和中点,k为给定值。初始时，令

low=0,high=n-1,mid=(low+high)/2

让给定值k与mid指向记录的关键字相比较

若给定值k=s[mid].key，查找成功；midlowhighhighlow=mid+1k>s[mid].key

若给定值k>s[mid].key，则在区域

low=mid+1至high内查找元素；k<s[mid].keyhigh=mid-1low

若给定值k<s[mid].key，则在区域low至high=mid-1内查找元素；重复上述操作，直至low>high时，查找失败。解：①

low=0high=10mid=(low+high)/2=5k=21<s[mid].key=s[5].key=56

012345678910513192137566475808892②low=0high=mid-1=5-1=4mid=(low+high)/2=2k=21>s[2].key=19③low=mid+1=3high=4mid=(low+high)/2=3k=21=s[mid].key=s[3].key=21答：查找成功查找关键字等于给定值（k=21）的元素。

若给定值k<s[mid].key，则在区域low~high=mid-1内查找元素；

若给定值k>s[mid].key，则在区域

low=mid+1~high内查找元素；4、二叉树的遍历及树、森林与二叉树的转换，生成排序二叉树的过程先序遍历定义：若二叉树为空，遍历结束，否则：（1）访问根结点；（2）按先序方式遍历根结点的左子树；（3）按先序方式遍历根结点的右子树。ABDEGCFHABGDFECH中序遍历定义：若二叉树为空，遍历结束，否则：（1）按中序方式遍历根结点的左子树；（2）访问根结点；（3）按中序方式遍历根结点的右子树。ABDEGCFHDGEBHAFC后序遍历定义：若二叉树为空，遍历结束，否则：（1）按后序方式遍历根结点的左子树；（2）按后序方式遍历根结点的右子树；（3）访问根结点。ABDEGCFHGDBECHFA根据遍历序列构造二叉树：

若给定一棵二叉树的中序遍历序列和另一种序列便可得到该二叉树。不失一般性，这里以一棵二叉树的中序遍历序列和先序遍历序列来构造该二叉树构造二叉树的步骤：1、从先序遍历序列中取第一个结点，为该二叉树的根结点，再从中序遍历序列中找到根结点，根结点之前的结点序列为根结点左子树的中序遍历序列，之后的结点序列为根结点右子树的中序遍历序列。2、再用递归的方法，分别重构根结点的左右子树，重复用第一步的方法，直到得到所有的结点序列为止。例：已知二叉树先序遍历序列为ABCDEFGHIJ，中序遍历序列为CBDEAFHIGJ，试构造此二叉树。ABCFAC、B、D、EF、H、I、G、JD、EH、IG、JABCDEFGJHIABCDEFGJH、I树转换成二叉树操作算法：保留一个结点的最左子结点；抹掉其余兄弟结点与上级结点的连线；将兄弟结点连在一起；以根为轴，顺时针旋转一个角度。举例：oooooooooooooo加线抹线ooooooo旋转ooooooo

第一步：k1作为二叉排序树的根。

第二步：若k2<k1，则k2所在结点应插在左子树上；否则，插入到k1的右子树上。第三步：读入ki，若ki〈k1（根），则进入左子树，否则，进入右子树，继续与子树之根比较，直到某结点kj，若有ki<kj

且结点kj的左子树为空,则结点ki插入道结点kj的左子树；若有ki≥kj

的右子树为空，则结点ki

插入到结点kj

的右子树。二叉排序树生成：对一序列{k1,k2,…,kn}，先设一棵空二叉树，然后将序列中的元素顺次生成结点后，逐个插入。插入步骤如下：

例有8个数构成的序列{10，18，3，8，12，2，7，3}，根据算法的基本思想构成一个二叉排序树。1010181018310183810183812101838122101838122710183812273中序遍历二叉排序树可得到一个关键字的递增有序序列：233781012185、排序的思想及其过程插入排序选择排序交换排序快速排序归并排序⑴插入排序基本思想：将n个元素的数列分为已有序和无序两个部分。

{{a1}，{a2，a3，a4，…,an}}{{a1(1)，a2(1)}，{a3(1)a4(1)

…,an(1)}}

…...{{a1(n-1)，a2(n-1)

，…},{an(n-1)}}

每次处理就是将无序数列的第一个元素与有序数列的元素从后往前逐个进行比较,找出插入位置,将该元素插入到有序数列的合适位置中。有序无序⑵选择排序基本思想：每次从待排序的记录中选出关键字最小（或最大）的记录，顺序放在已有序的记录序列的最后（或最前）面，直到全部数列有序。

{{a1}，{a2，a3，a4，…,an}}{{a1(1)，a2(1)}，{a3(1)，a4(1)…,an(1)}}

…...{{a1(n-1)，a2(n-1)

，…},{an(n-1)}}

有序无序3、交换排序（冒泡排序）指导思想：两两比较待排序记录的关键字，并交换不满足顺序要求的那些偶对元素，直到全部数列满足有序为止。冒泡排序（Bubblesort）是基于交换排序的一种算法。它是依次两两比较待排序元素；若为逆序（递增或递减）则进行交换，将待排序元素从左至右比较一遍称为一趟“冒泡”。每趟冒泡都将待排序列中的最大关键字交换到最后（或最前）位置。直到全部元素有序为止。…

a1a2a3…an-1an

最大值冒泡排序算法举例设有数列{65,97,76,13,27,49,58}比较次数第1趟{65，76，13，27，49，58}，{97}6

第2趟{65，13，27，49，58}，{76，97}5

第3趟{13，27，49，58}，{65，76，97}4

第4趟{13，27，49}，{58，65，76，97}3

第5趟{13，27}，{49，58，65，76，97}2

第6趟{13}，{27，49，58，65，76，97}1

总计：21次4、快速排序基本思想在待排序序列中按某种方法选取一个元素K，以它为分界点，用交换的方法将序列分为两个部分：比该值小的放在左边，否则在右边。形成

{左子序列}K{右子序列}

再分别对左、右两部分实施上述分解过程，直到各子序列长度为1，即有序为止。分界点元素值K的选取方法不同，将构成不同的排序法，也将影响排序的效率：取左边第1个元素为分界点；取中点A[（left+right）/2]为分界点；选取最大和最小值的平均值为分界点等。设有序列{a1，a2，…,An},选取中点元素K为分界点,分别从序列两头分别与K进行比较,小于K的元素交换到左边,否则交换到右边;一趟处理后,左边子序列的元素均小于分界点值K,右边子序列元素均大于等于K值。Step1分别从两端开始，指针i指向第一个元素A[left]，指针j指向最后一个元素A[right]，分界点取K；Step2循环（ij）从右边开始进行比较：若KA[j]，则将A[j]交换到左边；若K〈A[j]，则j=j-1，再进行比较；从左边开始进行比较：若K〉A[i]，则i=i+1，再进行比较；若KA[i]，则将A[i]交换到右边。当i=j时，一次分解操作完成。Step3在对分解出的左、右两个子序列按上述步骤继续进行分解，直到子序列长度为1（不可再分）为止，也即序列全部有序。快速排序算法举例对于数列{49，38，60，90，70，15，30，49}，采用中点分界法：初始状态:4938609070153049比较次数第1趟

493860907015304949386090701530495（i4、j1）

49386049701530905（i5、j2）

{49386049701530}90

小计：10

ik=90jijji5、归并排序

归并是将两个或两个以上的有序表合成一个新的有序表。用这种思想实现的排序称作归并排序(MergingSort)。假设初始序列有n个记录，可以看成是有n个有序的字序列，然后两两归并，得到n/2个有序的子序列，再两两归并，直到得到一个长度为n的有序序列为止，这种排序方法称为2-路归并排序。

2-路归并排序是我们最经常使用的归并排序。其核心操作是将一维数组中前后相邻的2个有序序列归并成为一个有序序列。Step1把待排序的n个记录看作是长度为1的有序序列。将相邻子序列两两归并为长度为2的有序序列；Step2把得到的n/2个长度为2的有序子序列再归并为长度为2*2的有序序列；Step3按Step2的方式，重复对相邻有序子序列进行归并操作，直到成为一个有序序列为止。4949382713766597第一趟排序将每一个元素看成一个有序表两两归并3849492776136597第二趟排序3849659713274976第三趟排序13972776654938491397277665493849给定数列{513、87、512、61、908、170、897、275、653、462}，计算采用下列算法的比较次数：插入、选择、冒泡、快速、归并排序。(1)插入排序：1．{513}{87、512、61、908、170、897、275、653、462}02．{87，513}{512、61、908、170、897、275、653、462}13．{87，512，513}{61、908、170、897、275、653、462}24．{61，87，512，513}{908、170、897、275、653、462}35．{61，87，512，513、908}{170、897、275、653、462}16．{61，87，170、512，513、908}{897、275、653、462}47．{61，87，170、512，513、897、908}{275、653、462}28．{61，87，170、275、512，513、897、908}{653、462}59．{61，87，170、275、512，513、653、897、908}{462}310．{61，87，170、275、462、512，513、653、897、908}6比较次数=1+2+3+1+4+2+5+3+6=27(2)选择排序：1．{61}{87、512，513、908、170、897、275、653、462}92．{61，87}{512，513、908、170、897、275、653、462}83．{61，87，170}{513、908、512、897、275、653、462}74．{61，87，170，275}{908、512、897、513、653、462}65．{61，87，170，275，462}{512、897、513、653、908}56．{61，87，170，275，462，512}{897、513、653、908}47．{61，87，170，275，462，512，513}{897、653、908}38．{61，87，170，275，462，512，513、653}{897、908}29．{61，87，170，275，462，512，513、653、897}{908}110．{61，87，170，275，462，503、512、653、897，908}0比较次数=9+8+7+6+5+4+3+2+1=45（3）冒泡排序0．{513、87、512、61、908、170、897、275、653、462}1．{87，512，61，513，170，897，275，653，462，908}92．{87，61，512，170，513，275，653，462，896，908}83．{61，87，170，512，275，513，462，653，896，908}74．{61，87，170，275，512，462，513，653，896，908}65．{61，87，170，275，462，512，513，653，896，908}56．{61，87，170，275，462，512，513，653，896，908}4但没有交换，停止。7．{61，87，170，275，462，503，512，653，896，908}0比较次数=9+8+7+6+5+4+=39注意：如果采用没有改进的方法，比较次数为45（4）快速排序513、87、512、61、908、170、897、275、653、4621．{462、87、512、61、275、170}、513、{897、653、908}92．{170、87、275、61}、462、{512}、513、{653}、897、{908}73．{61、87}、170、{275}、462、{512}、513、{653}、897、{908}44．{61}、87、170、275、{462}、503、512、{653}、897、90825．61、87、170、275、462、503、512、653、897、9080比较次数=9+7+4+2=22（5）归并排序0．513、87、512、61、908、170、897、275、653、4621．{87、513}、{61、512}、{170、908}、{275、897}、{462、653}52．{61，87，512，513}、{170、275、897、908}、{462、653}63．{61，87，170，275，512，513，897，908}、{462、653}64．{61，87，170，275，462，503，512，653，897，908}8比较次数=5+6+6+8=256、通过邻接矩阵、邻接表写出其图的遍历70一、深度优先搜索二、广度优先搜索

图的遍历遍历定义：从已给的连通图中某一顶点出发，沿着一些边，访遍图中所有的顶点，且使每个顶点仅被访问一次，就叫做图的遍历，它是图的基本运算。遍历实质：找每个顶点的邻接点的过程。图的特点：图中可能存在回路，且图的任一顶点都可能与其它顶点相通，在访问完某个顶点之后可能会沿着某些边又回到了曾经访问过的顶点。解决思路：可设置一个辅助数组

visited[n]，用来标记每个被访问过的顶点。它的初始状态为0，在图的遍历过程中，一旦某一个顶点i

被访问，就立即改visited[i]为1，防止它被多次访问。图常用的遍历：怎样避免重复访问？71一、深度优先搜索(DFS)基本思想：——仿树的先序遍历过程。Depth_FirstSearchv1v1v2v3v8v7v6v4v5DFS结果例1：→→→→→→→v2v4v8v5v3v6v7例2：v2→v1→v3→v5→DFS结果v4

→v6起点起点遍历步骤应退回到V8，因为V2已有标记72深度优先搜索（遍历）步骤：详细归纳：在访问图中某一起始顶点

v

后，由

v出发，访问它的任一邻接顶点

w1；再从

w1出发，访问与

w1邻接但还未被访问过的顶点

w2；然后再从

w2出发，进行类似的访问，…

如此进行下去，直至到达所有的邻接顶点都被访问过的顶点

u为止。接着，退回一步，退到前一次刚访问过的顶点，看是否还有其它未被访问的邻接顶点。

如果有，则访问此顶点，之后再从此顶点出发，进行与前述类似的访问；

如果没有，就再退回一步进行搜索。重复上述过程，直到连通图中所有顶点都被访问过为止。简单归纳：访问起始点v;若v的第1个邻接点没访问过，深度遍历此邻接点；若当前邻接点已访问过，再找v的第2个邻接点重新遍历。73讨论1：计算机如何实现DFS？123456100000020000003000000400000050000006000000000000123456010000110000111000111010111110111111DFS结果邻接矩阵A辅助数组visited[n]起点——开辅助数组

visited[n]！例：1234561011100210001031000104100001501100060