计算机考研知识点（一）

心已赠人 2023-07-19 05:00 32阅读 0赞

### 计算机考研知识点（一） ###

*   *   *  AOV和AOE
         *  散列表
         *  堆
         *  管程
         *  小知识点
         *  参考博客

### AOV和AOE ###

*  **顶点活动网(AOV网)** ：将顶点表示活动，边表示活动之间的次序关系的网称为顶点活动网。
 *  **拓扑序列**：把AOV网中的所有顶点排成一个线性序列，该序列满足如下条件：若AOV网中存在从 v i v\_i vi到 v j v\_j vj的路径，则在该序列中， v i v\_i vi必位于 v j v\_j vj之前。
 *  **AOE网**：带权的有向图,顶点表示事件,边表示活动，权表示活动持续的时间。只有一个入度为零的顶点(称作**源点**),表示整个活动开始;只有一个出度为零的顶点(称作**汇点**)表示整个活动结束。  
    ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxMTQ2NjUw_size_16_color_FFFFFF_t_70]
    
     *  **关键路径**：在AOE 网中，有些活动可以同时进行，完成一个工程所需的最短时间是从源点到汇点的最长路径长度。长度最长的路径称为关键路径。
     *  **关键活动**：关键路径上的活动称作关键活动。
     *  **事件 v i v\_i vi的最早发生时间**：是从源点 v 1 v\_1 v1到 v i v\_i vi的最长路径长度，记作 v e ( i ) v\_e(i) ve(i)。
     *  **事件 v i v\_i vi的最迟发生时间**：是汇点 v n v\_n vn的最早发生时间 v e ( n ) v\_e(n) ve(n)减去 v i v\_i vi到 v n v\_n vn的最长路径长度，记作  v l ( k ) v\_l(k) vl(k)。
     *  **活动 < v i , v j > <v\_i,v\_j> <vi,vj>的最早开始时间**：是 v i v\_i vi的最早开始时间，记作 e ( i ) e(i) e(i)。
     *  **活动 < v i , v j > <v\_i,v\_j> <vi,vj>的最迟开始时间**：是 v j v\_j vj的最迟开始时间减去 < v i , v j > <v\_i,v\_j> <vi,vj>的持续时间，记作 l ( i ) l(i) l(i)
     *  **活动的最早完工时间**：等于当前边指向结点的最早发生时间。
     *  **活动的最晚完工时间**：等于当前边指向结点的最迟发生时间。
     *  性质：最早发生时间与最迟发生时间相等的活动为关键活动。

### 散列表 ###

*  **定义**： 用散列法存储的线性表叫散列表（Hash table）,又称杂凑表，哈希表，对应的函数称为散列函数、杂凑函数或哈希函数。
 *  **散列函数(哈希函数)**：选取某个函数，依该函数按关键字计算元素的存储位置，并按此存放；查找时，由同一个函数对给定值k计算地址，将k与地址单元中元素关键码进行比较，确定查找是否成功。
 *  **装填因子**：设散列表空间大小为n，填入表中的结点数为 m,则称 α = m / n \\alpha =m/n α=m/n为散列表的装填因子。
 *  **成功查找的平均长度**=查找次数总和/关键字总个数
 *  **失败的查找的平均长度**=不成功总次数/查找位置长度，比如在线性探测再散列法中，mod表示模数 ，不成功总次数=\[0,mod-1\]位置到空位置的长度(此时代表查找失败) ,查找位置长度=mod
 *  **冲突**：若H(k1) = H(k2), 则称为冲突，发生冲突的两个关键字k1和k2称为**同义词**。
 *  **散列函数的构造方法**：
    
     *  **直接定址法**：取关键字的某个线性函数值为哈希地址。即: H(key) = a\*key + b  
        其中a、b为常数。又称H(key)为自身函数。
     *  **质数除余法**：如果表长为n，取小于或等于n的最大质数m作模，关键字通过m取模运算，所得值作为散列地址。
     *  **平方取中法**：在不知道关键字的全部情况时，可通过求关键字的平方值扩大差别，然后取中间几位作为哈希地址
     *  **折叠法**：将关键码自左到右分成位数相等的几部分（最后一部分位数可以短些），然后将这几部分叠加求和，并按哈希表表长，取后几位作为哈希地址。
 *  常见的**冲突处理方法**：下面的平均查找长度是经过大量的数据实验，得出以下的经验公式
    
     *  开放定址法（开地址法） ：在顺序存储结构中用一定方法进行散列存取的方法,  
        若 H ( k e y ) = d H(key) = d H(key)=d的单元发生冲突， 则按下面几种方法进行探查：
        
         *  **线性探测再散列法**：若 H ( k e y ) = d H(key) = d H(key)=d的单元发生冲突， 则按下述方法进行探查：  
             h i ( k ) = ( h ( k ) + i ) % n h\_i(k) = (h(k)+i)\\%n hi(k)=(h(k)\+i)%n, n是散列表的长度， 1 ≤ i ≤ n − 1 1≤i≤n-1 1≤i≤n−1  
            线性探测再散列平均查找长度 ≈ 1 2 ( 1 + 1 1 − α ) \\approx \\frac \{1\}\{2\}(1+\\frac\{1\}\{1-\\alpha \}) ≈21(1\+1−α1)
         *  **二次探测再散列法**:  h i ( k ) = ( h ( k ) + d i ) % n h\_i(k) = (h(k)+d\_i)\\%n hi(k)=(h(k)\+di)%n n是散列表的长度，  
             d i = 1 2 , − 1 2 , 2 2 , − 2 2 , … , k 2 , − k 2 ( k ≤ n / 2 ) d\_i = 1^2, -1^2, 2^2, -2^2,…, k^2, -k^2 (k ≤ n/2) di=12,−12,22,−22,…,k2,−k2(k≤n/2)
         *  **伪随机探测再散列**，取 d i d\_i di=伪随机序列（种子一样，随机一样，不会变）
     *  链地址法（拉链法） :平均查找长度 ≈ 1 + α 2 \\approx 1+\\frac\{\\alpha\}\{2 \} ≈1\+2α
     *  再哈希法（双哈希函数法）
     *  建立一个公共溢出区

### 堆 ###

*  建立堆
    
     *  先建一个完全二叉树
     *  从最后一个非叶子结点开始建堆，n个结点,最后一个非终端结点的下标是 ⌊ n / 2 ⌋ \\lfloor n/2 \\rfloor ⌊n/2⌋(从1开始编号)
     *  然后继续检查i-2,1-3,i-4等

### 管程 ###

*  管程由四部分**组成**：
    
     *  ① 管程的名称；
     *  ② 局部于管程的共享数据结构说明；
     *  ③ 对该数据结构进行操作的一组过程；
     *  ④ 对局部于管程的共享数据设置初始值的语句。  
        ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxMTQ2NjUw_size_16_color_FFFFFF_t_70 1]
 *  **条件变量**
    
     *  某进程通过管程请求获得临界资源而未能满足时，管程便调用**wait原语**使该进程等待，并将其排在**等待队列**上
     *  仅当另一进程访问完成并释放该资源之后，管程才又调用**signal原语**，**唤醒**等待队列中的队首进程。

### 小知识点 ###

*  对于k路平衡归并，m为初始归并段的个数，当(m-1)%(k-1)=0时不需要添加虚段，否则添加附加虚段个数k-1-((m-1)%(k-1))
 *  在首次适应算法,最佳适应算法,最坏适应算法，循环首次适应算法中**最容易产生碎片**的是最佳适应算算法（由于选择接近的内存块，容易产生小的碎片，不利于被利用）
 *  **100BaseT**快速以太网使用的导向传输介质是双绞线（100表示传输速率为100Mbps，Bas表示基带传输，T表示双绞线）
 *  在选择重传协议中，发送窗体大小+接受窗体大小 ≤ 2 n \\leq 2^n ≤2n（采用n比特编号）
 *  CSMA/CD协议中，在冲突域中两个站点的单向传播时延最多为满足 **最小帧长=总线传播时延\*传输速率\*2**
 *  将簇号转换成磁盘物理地址的过程由**磁盘驱动程序**完成。
 *  当定时器产生**时钟中断**后,由**时钟中断服务程序更新**的部分内容
    
     *  内核中时钟变量的值
     *  当前进程占用 CPU 的时间
     *  当前进程在时间片内的剩余执行时间
 *  IEEE 802.11无线局域网的**MAC协议CSMA/CA**进行**信道预约**的方法是：**交换RTS与CTS帧**
 *  **UDP协议实现分用**（demultiplexing）时所依据的头部字段是：**目的端口号**

### 参考博客 ###

*  [AOE网活动的最早、最迟发生时间及关键路径问题][AOE]
 *  [哈希表查找——成功和不成功时的平均查找长度][Link 1]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxMTQ2NjUw_size_16_color_FFFFFF_t_70]: /images/20230528/fc7eefaa4a2a431cbe8c931642cc697b.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxMTQ2NjUw_size_16_color_FFFFFF_t_70 1]: /images/20230528/b0677f7101664a888154fe3907fa450d.png
[AOE]: https://blog.csdn.net/qq_38071429/article/details/80407544
[Link 1]: https://blog.csdn.net/longlovefilm/article/details/78009782