820怎么复习？ 立即推，放弃考研

820考纲

王道上面有但是820不考的有：数据结构：串，B，B+，外部排序，败者树，最佳归并树；操作系统：几乎都要考

王道上面没有但是820会考的有：数据结构：广义表（表头表尾 长度深度）；操作系统：伙伴系统

考试科目 820 计算机专业基础
考试形式 笔试（闭卷）
考试时间 180 分钟
考试总分 150 分

本科目包括《数据结构》和《计算机操作系统》两门课程，总分 150 分，两门课程各占 75 分

一、总体要求

《数据结构》是计算机程序设计的重要理论技术基础，是计算机科学与技术学科的核心课程。

要求：

  1. 理解数据结构的基本概念；掌握数据的逻辑结构、存储结构及其差异，以及各种基本操作的实现。
  2. 掌握基本的数据处理原理和方法的基础上，能够分析算法的时间复杂度与空间复杂度。
  3. 能够选择合适的数据结构和算法策略进行问题求解，具备采用 C 或 C++或 JAVA 语言设计与实现算法的能力。

二、内容

  1. 数据结构及算法的相关概念和术语

    （1）数据结构及算法的概念

    （2）数据的逻辑结构和存储结构

    （3）算法的定义及特性

    （4）算法时间复杂度和空间复杂度的分析方法

  2. 线性表

    （1）线性表的定义

    （2）线性表的基本操作及在顺序存储及链式存储上的实现

    （3）各种变形链表（循环链表、双向链表、带头结点的链表等）的表示和基本操作的实现

    （4）递归过程的特点及实现方法

    （5）栈和队列的基本概念；栈和队列的顺序存储结构、链式储存结构及其存储特点

    （6）栈和队列的应用

    （7）循环队列的判满、判空方法

    （8）特殊矩阵的压缩储存

  3. 广义表的基本概念、存储结构和基本操作

  4. 树和二叉树

    （1）树与森林的基本概念

    （2）树与森林的存储结构及遍历

    （3）二叉树的定义及 6 大性质

    （4）二叉树的顺序储存与链式储存结构

    （5）二叉树的先序、中序、后序三种遍历方式的关系以及实现；层序遍历的实现

    （6）线索二叉树的基本概念与构造方法

    （7）树与二叉树的应用：二叉排序树；二叉平衡树；哈夫曼树与哈夫曼编码

  5. 图

    （1）图的基本概念和术语

    （2）图的存储结构：邻接矩阵、邻接表、逆邻接表

    （3）遍历算法：深度优先搜索算法和广度优先搜索算法

    （4）应用：最小生成树；最短路径，拓扑排序和关键路径

  6. 查找

    （1）查找的基本概念；静态查找与动态查找

    （2）顺序查找、折半查找、索引查找

    （3）哈希查找

       哈希函数的基本构造方法，解决地址冲突的基本策略

    （4）各种查找算法的时间复杂度和空间复杂度

  7. 排序

    （1）排序的基本概念

    （2）插入排序

    （3）简单选择排序

    （4）希尔排序

    （5）快速排序

    （6）堆排序

    （7）归并排序

    （8）基数排序

    （9）排序算法的比较

其中算法题分为阅读、修改和编写算法三类：
(1)阅读算法：阅读指定算法，回答使用的数据结构、算法实现的功能或执行的结果；
(2)修改算法：阅读指定算法，指出算法的错误并修正；指出算法的不足并改进；按给定功能填写 算法空缺部分； (3)编写算法：根据算法功能要求，选择或者设计合适的数据结构，用程序设计语言编写算法，实 现指定功能。
以上皆可分析给定或者设计的算法时空复杂度。

一、总体要求

主要考察学生对操作系统基本概念、原理的理解程度，重点考察操作系统的设计方法与实现技术， 同时能够具备运用所学的操作系统原理、方法与技术分析问题和解决问题的能力。

二、内容

  1. 操作系统的基本概念

    （1) 批处理与多道程序设计

    （2) 分时系统与实时系统

    （3) 操作系统的基本类型与特征

    （4) 并发与并行的概念

    （5) 操作系统的层次结构与功能模块

    （6) 程序的并发执行与顺序执行

  2. 进程管理

    （1) 进程: 进程控制块、进程的几种基本状态与状态转换（进程的创建、进程的终止、进程的 阻塞与唤醒、进程的挂起与激活等）

    （2) 进程的同步与互斥：临界资源、临界区、进程同步与互斥问题、信号量机制以及 P、V 操 作、管程机制

    （3) 进程间通信：进程通信的类型（直接通信和间接通信方式）、消息传递系统中的几个问题、 消息缓冲队列通信机制

    （4) 线程与进程的调度:线程与进程的基本概念，调度的类型、调度队列模型、调度方式、进程调度算法（先来先服务、短进程优先、时间片轮转、基于优先级的调度算法等）

    （5) 死锁: 死锁的基本概念，死锁定理、死锁预防、死锁避免与处理死锁的基本方法、银行家算法

    （6) 综合应用：生产者消费者问题、读者和写者问题、哲学家进餐问题等

  3. 内存管理

    （1) 内存管理的需求：重定位、内存保护、内存共享

    （2) 程序的装入和链接：静态装入和可重定位装入、静态链接、动态链接、运行时动态链接。

    （3) 分区存储管理：分区方式（单一连续分区、固定分区、可变式分区）、分区分配算法（首次适应算法、循环首次适应算法、最佳适应法、最坏适应法等）

    （4) 段式管理与页式管理：段、页、碎片等基本概念、段式管理与页式管理机制

    （5) 虚拟内存：局部性原理、虚拟内存概念、请求分段与请求分页、段页式管理、段页式地址 结构与地址转换、页面置换算法（OPT、先进先出、LRU、Clock、改进型 Clock 置换）、 抖动

  4. 设备管理

    （1) I/O 系统的：基本概念、I/O 控制方式（程序 I/O、中断、DMA、通道）、相关数据结构、 缓冲管理（单缓冲、双缓冲、循环缓冲、缓冲池）

    （2) 磁盘管理与磁盘调度算法：SSTF 算法，SCAN 算法，CSCAN 算法，N-STEP-SCAN 算法，FSCAN 算法

    （3) 设备分配、设备处理、虚拟设备，Spooling 系统

  5. 文件系统

    （1) 基本概念：文件和文件系统、目录、文件结构的物理结构和逻辑结构（顺序文件、索引顺序文件、索引文件、HASH 文件）、文件共享（基于索引节点、基于符号链接实现文件共享）

    （2) 外存分配方法：连续分配、链接分配、索引分配

    （3) 目录管理：单级目录、二级目录、多级目录

    （4) 文件存储空间的管理技术：位示图、空闲链表、索引

数据结构

第一部分 数据结构及算法的相关概念和术语

知识点

考研分析

选择题、填空题、判断题、应用题

（2014）一个好的算法应该考虑达到以下目标：正确性，可读性，健壮性，高效性

（2015）数据的逻辑结构是对数据关系的描述，主要有 线性结构 与 非线性结构 两大类。

（2015）程序for(int i=0;i<n;i+=5);的时间复杂度为 O(n)

复习题

修正：同一个算法，实现语言的级别越高，执行效 率就越低 —— 这是对的，注意下面有个选择题答案错了

第二部分 线性表

1、线性表

---

2、栈和队列

汉诺塔

面试题 08.06. 汉诺塔问题 - 力扣（LeetCode）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
public:
    // -- 将 source 的 index盘 移动到 destination--
    void move(vector<int>& source, int index, vector<int>& destination) {
        printf("移动%d\n", source[index]);
        destination.push_back(source[index]);   // 加入destination
        source.pop_back();  // 
    }
    // -- hanio(n个盘, 原位置，辅助位置，目标位置);
    void hanoi(int n, vector<int>& A, vector<int>& B, vector<int>& C) {
        if (n == 1) { 
            move(A, A.size()-1, C);
        }
        else {
            hanoi(n-1, A, C, B);        // 将 A的n-1个盘移动到B盘
            move(A, A.size()-1, C);     // 将 A剩下的最顶上的快移动到C
            hanoi(n-1, B, A, C);        // 将 B盘的全部n-1移动到C盘
        }
    }
    void hanota(vector<int>& A, vector<int>& B, vector<int>& C) {
        hanoi(A.size(), A, B, C);
    }
};

3、串

4、数组

考研分析

选择题、填空题、判断题、应用题

（2013）设一个链表最常用的操作是在末尾插入删除结点，则选用( D )最节省时间
A.单链表
B.单循环链表
C.带尾指针的单循环链表
D.带头结点的双循环链表
解析：A和B需要找到链尾的时间；C当只有一个元素的时候，删除需要修改尾指针=头指针；D相对C不需要注意这个问题

（2013）对于顺序存储的线性表，到某位置访问结点和增加结点的时间复杂度为( C )
A.O(n), O(n)
B.O(n), O(1)
C.O(1), O(n)
D.O(1), O(1)

（2013）设栈的初始状态为空，当字符序列 a3_作为栈的输入时，输出长度为3的且可以用作C语言标识符的字符序列有（ C ）个
A.4
B.6
C.3
D.5
解析：合法的有：a3_、a_3、_3a、_a3，但是_a3不可能由栈输出

（2013）下面（ C ）数据结构常用于函数调用
A.队列 B. 栈 C. 链表 D. 数组

（2013）算法题：线性表(a1,a2,…,an)中元素递增有序且按顺序存储于计算机内的数组a中，要求设计算法用函数实现下列功能：
(1)用最少的时间在表中查找值为x的元素
(2)如找到则将其与直接后继元素交换
(3)如找不到则将其插入链表中使表中元素仍然递增有序
算法描述：顺序存储且有序，可以顺序查找，也可以折半查找；查找最快则折半查找；查找成功则看是否最后一个元素，如果不是则与直接后继交换；否则查找失败，则将最后一个位置的元素到当前位置元素依次后移1位，最后将当前元素插入到空位

（2013）算法题：假设Header指向如下循环单链表，请问执行下列2个程序段后各自的输出结果是什么？

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
typedef struct node {
    int data;
    struct node *next;
}Node, *ptr, *List;
// 第一个程序段
ptr p = header;
for (int i = 0; i<5; i++) {
	printf("%d",p->data);
	p = p->next;
	p = p->next;
}
// 第二个程序段
ptr p = header;
for (int i = 0; i<5; i++) {
	printf("%d",p->data);
	p = p->next;
	p = p->next;
	p = p->next;
}

答案：13524和14253

(2014) 某线性表中最常用的操作是在最后一个元素后面插入和删除第一个元素，则采用（ D ）存储方式最节省运算时间。
A.单链表
B.仅有头指针的单循环链表
C.双链表
D.仅有尾指针的单循环链表

（2014）下述哪一条是链式存储结构的优点（ B ）
A.存储密度大
B.插入，删除方便
C.存储单元连续
D.随机存取第i个元素方便

（2014）一个栈的输入序列为 1 2 3 4 5，则下列序列中部不可能是栈的输出序列是( B )
A. 2 3 4 1 5
B. 5 4 1 3 2
C. 2 3 1 4 5
D. 1 5 4 3 2

（2014）最大容量为n的循环队列，队尾指针rear，队头front，则队满的条件是( A )
A. (rear+1) MOD n==front
B. rear==front
C. rear+1==front
D. (rear-1) MOD n ==front

（2014）算法题：设计一个算法，逆序单链表中的数据。

（2015）在单链表L中的p结点后插入q结点的操作是 q->next=p->next; p->next=q;

（2015）具有n个元素的线性表采用顺序存储结构，在第i个位置插入一个新元素的算法时间复杂度为( C )(1<=i<=n+1)
A. O(1)
B. O(i)
C. O(n)
D. O(n^2)

（2015）一个栈的输入序列为1，2，3….n，如输出序列的第一个元素是n，输出第i(1<=i<=n)个元素是（ A ）
A. n-i+1
B. n-i-1
C. n-i
D. i

（2015）算法题：给定2个升序线性表L1和L2，设计一个函数，将2个升序线性表合并成为1个升序线性表L，新线性表L中无重复数据。
算法思想：分别求出2个线性表L1，L2的长度；初始化L；i=j=k=0；只要L1或者L2都不空，则比较L1与L2当前元素值，存在如下三种情况： L1[i]>L2[j] → L[k++]=L2[j++]; L1[i]

复习题

第三部分 广义表

知识点

第四部分 树

知识点

复习题

第五部分 图

知识点

复习题

第六部分 查找

知识点

第七部分 排序

知识点

填空题汇总

  1. 数据的物理结构包括 数据元素 的表示和 数据元素间关系 的表示
  2. 数据结构是研讨数据的 逻辑结构 和 物理结构 ，以及它们之间的相互关系，并对与这种结构定义相应的操作（运算） ，设计出相应的 算法
  3. 线性结构中元素之间存在 1:1 关系，树形结构中元素之间存在 1:m 关系，图形结构中元素之间存在 m:n 关系。
  4. 向量、栈和队列都是 线性 结构，可以在向量的 任意 位置插入和删除元素；对于栈只能在 栈顶 插入和删除元素；对于队列只能在 队尾 插入元素和 队头 删除元素
  5. 数据逻结构包括 线性结构 、树形结构 和 图形结构 这三种类型，树形结构和图形结构合称为 非线性结构
  6. 算法的五个特性是：有穷性、确定性、可行性、输入、输出
  7. (2013) 对二叉排序树 中序遍历 可以得到线性有序序列

判断题汇总

  1. 数据元素是数据的最小单位。x ，是数据项
  2. 数据的物理结构是指数据在计算机内的实际存储形式。√

简答题汇总

  1. 在数据结构课程中，数据的逻辑结构，数据的存储结构及数据的运算之间存在着怎样的关系？
答：数据的逻辑结构反映数据元素之间的逻辑关系（即数据元素之间的关联方式或“邻接关系”），数据的存储结构是数据结构在计算机中的表示，包括数据元素的表示及其关系的表示。数据的运算是对数据定义的一组操作，运算是定义在逻辑结构上的，和存储结构无关，而运算的实现则是依赖于存储结构。
  1. 若逻辑结构相同但存储结构不同，则为不同的数据结构。这样的说法对吗？举例说明之。
答：逻辑结构相同但存储不同，可以是不同的数据结构。例如，线性表的逻辑结构属于线性结构，采用顺序存储结构为顺序表，而采用链式存储结构称为线性链表。
  1. 在给定的逻辑结构及其存储表示上可以定义不同的运算集合，从而得到不同的数据结构。这样说法对吗？举例说明之。
答：栈和队列的逻辑结构相同，其存储表示也可相同（顺序存储和链式存储），但由于其运算集合不同而成为不同的数据结构。
  1. 评价各种不同数据结构的标准是什么？
答：数据结构的评价非常复杂，可以考虑两个方面，一是所选数据结构是否准确、完整的刻划了问题的基本特征；二是是否容易实现（如对数据分解是否恰当；逻辑结构的选择是否适合于运算的功能，是否有利于运算的实现；基本运算的选择是否恰当。）

操作系统

课后习题

一到六章的答案

第一章

1、4、5、6、8、9、11、13、14、15、16、17、18

第二章

2、3、4、5、6、7、8、10、11、12、13、20、21、22、23、24、25、26

第三章

1、5、8、9、13、21、22、24、25、26、28、31

第四章

2、3、4、5、7、9、10、11、13、14、16、20、21、25、26、27

第五章

1、2、3、4、5、7、8、10、14、15、16、17、18、19、20、21、22、25、26

第六章

1、2、4、5、7、8、10、14、15、16、17、18、21、24、29

第七章

5、6、7、8、9、10、11、12、13、14、15、17、21、23

PV信号量

分析资源有什么（特别注意：来了几个车，几个人，那车和人也是资源），再看看进程是啥

先判断是哪一种基本类型，再开始写

最后可以用样例检验

对于同步关系的分析，是一前一后发生的，要当做两个事件来看。

  • 生产者消费者问题

（1）找到谁是“消费者”，谁是“生产者”
（2）确定生产和消费的关系，两个对象，互相之间会有制约，最好画图辅助理解，抓住他们的关系资源
（3）确定信号量，写代码

多个满就对应多个空

tips：能V就V，注意顺序

  • 读者写者问题

（1）要把if语句和count（可能多个，eg：南北桥）变量变化部分都加锁（多个就用多个互斥量）
（2）要实现读写公平