计算机组成原理考研笔记

本文最后更新于:2024年12月27日 下午

树的遍历

递归

1
2
3
4
5
Void PreOrder(Tree T){
Visit(T);
PreOrder(T->lchild);
PreOrder(T->rchild);
}

非递归

层次遍历

1
2
3
4
5
6
7
8
9
10
11
Void LevelOrder(Tree T){
InitQueue(Q);
BiTree p;
EnQueue(Q,T);
while(!IsEmpty(Q)){
DeQueue(Q,p);
visit(p);
if(p->lchild!=NULL) EnQueue(Q,p->lchild);
if(p->rchild!=NULL) EnQueue(Q,p->rchild);
}
}

图的遍历

BFS

1
Void BFS()

DFS

图的应用

Prim

Kruskal

Dijkstra

拓扑排序

排序

插入排序

1
2
3
4
5
6
7
8
9
10
11
Void InsertSort(ElemType A[], int n){
for(int i = 2;i < n;i++){
for(int j = i - 1;j >= 0;j--){
if(A[j] < A[i]){
int swap = A[i];
A[i] = A[j];
A[j] = swap;
}
}
}
}

折半插入排序

1
2
3
void InsertSort(ElemType A[], int n){

}

希尔排序

冒泡排序

1
2
3
4
5
6
7
8
9
10
11
12
Void BubbleSort(ElemType A[], int n){
int swap = 0;
for(int i = 0;i < n;i++){
for(int j = i;j < n;j++){
if(A[i] > A[j]){
swap = A[i];
A[i] = A[j];
A[j] =swap;
}
}
}
}

快速排序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
Void QuickSort(ElemType A[], int low, int high){
if(low < high){
int pivotpos = Partition(A, low, high);
QuickSort(A, low, pivotpos - 1);
QuickSort(A, pivotpos, high);
}
else QuickSort(A, high, low);
}
int Partition(ElemType A[], int low, int high){
ElemType pivo = A[low];
while(low < high){ //循环跳出条件,其实就是保证遍历一遍
while(low < high && A[high] >= pivot) --high; //两边间隔这样找,好处是交换写的很方便,可以不用考虑太多写的很简洁
A[low] = A[high];
while(low<high && A[low] <= pivot) ++low;
A[high] = A[low];
}
}

简单选择排序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
Void SeletSort(ElemType A[],int n){
int swap = 0;
for(int i = 0;i < n;i++){
min = i;
for(j = i + 1;j < n;j++){
if(A[j] < A[min]) min = j;
}
if(min != i){
swap = A[i];
A[i] = A[min];
A[min] = swap;
}
}
}

归并排序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
Void Merge(ElemType A[], int low, int mid, int high){
int n = high - low + 1;
int k;
ElemType *B = (ElemType *)malloc((n+1) * sizeof(ElemType));
for(int i = low;i <= high;i++) B[i] = A[i];
for(int i = low, j = mid+1, k = i;i <= mid&&j <= high;k++){
if(B[i]<B[j]) A[k] = B[i++];
else A[k] = B[j++];
}
while(i<=mid) A[k++] = B[i++];
while(j<=high) A[k++] = B[j++];
}

void MergeSort(ElemType A[], int low, int high){
if(low < high){
int mid = (low + high) / 2;
MergeSort(A,low,mid);
MergeSort(A,mid,high);
Merge(A,low,mid,high);
}
else MerSort(A,high,low);
}

操作系统

semaphore

生产者消费者问题

一组生产者和一组消费者共享初始为空,大小为n的缓冲区

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
semaphore mutex = 1; //临界区互斥变量
semaphore empty = n; //空闲缓冲区
semaphore full = 0; //缓冲区初始为0
producer(){
while(1){
生产; //生产数据
P(empty); //获取缓冲区单元
P(mutex); //进入临界区
把数据放进缓冲区; //将数据放进缓冲区
V(mutex); //离开临界区,释放互斥信号量
V(full); //慢缓冲区数加1
}
}

consumer(){
while(1){
P(full);
P(mutex);
拿东西;
V(mutex);
V(empty);
消费;
}
}

读者写者问题

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
int count = 0;
semaphore mutex = 1;
semaphore rw = 1;
semaphore w = 1; //保证写进程优先,防止饿死
writer(){
while(1){
P(w);
P(rw);
writing;
V(rw);
V(w);
}
}
reader(){
while(1){
P(w);
P(mutex);
if(count == 0) P(rw); //阻止写进程写
count++;
V(mutex);
V(w);
reading;
P(mutex);
count--;
if(count == 0) V(rw);
V(mutex);
}
}

哲学家进餐问题

要同时拿起两个筷子才能吃,注意防止饥饿

1
2
3
4
5
6
7
8
9
10
11
12
13
14
semaphore chopsticks[5] = {1, 1, 1, 1, 1};
semaphore mutex = 1;
Pi(){
do{
P(mutex);
P(chopsticks[i]);
P(chopsticks[(i+1)%5]);
V(mutex);
eat;
V(chopsticks[i]);
V(chopsticks[(i+1)%5]);
think;
} while(1);
}

吸烟者问题

轮流抽烟,这个是个同步问题

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
int num = 0;
semaphore offer1 = 0; //分别对应三种组合
semaphore offer2 = 0;
semaphore offer3 = 0;
process P1(){ //提供者
while(1){
num++;
num = num % 3;
if(num == 0) V(offer1);
else if(num == 1) V(offer2);
else V(offer3);
P(finish); //保证抽了才放下一个
}
}
process P2(){ //三个吸烟者
while(1){
P(offer1);
抽;
V(finish);
}
}
process P3(){ //三个吸烟者
while(1){
P(offer2);
抽;
V(finish);
}
}
process P4(){ //三个吸烟者
while(1){
P(offer3);
抽;
V(finish);
}
}

根据指针p所指节点找双亲节点

1
2
3
4
5
6
7
8
BTree* getParent(BTree* t, Btree* p){
if(t == null) return NULL; //所指结点为空节点
if(t == p) return NULL; //所指节点是根节点
if(t->lchild == p || t->rchild == p) return p;
BTree* parent = getParent(t-lchild, p);
if(parent != NULL) return parent;
else return getParent(t-rchild, p);
}

循环移位

即把后p个移动到前面
$$
思路是这样的,目标是ab变成ba,所以先a^{-1}b,再a^{-1}b^{-1},然后整体交换变成ba
$$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
void Reverse(int R[], int from, int to){
int temp
for(int i = from;i<(to-from+1)/2;i++){
temp = R[from + i];
R[from + i] = R[to - i];
R[to - i] = temp;
}
}

void Converse(int R[], int n, int p){
Reverse(R, 0, p - 1);
Reverse(R, p, n - 1);
Reverse(R, 0, n - 1);
}

一定要注意标准化语言

给出将一个正整数字符串转化为对应的整数值的递归描述

递归出口:

  1. 若子串为空串,返回一个标记表示无法转化
  2. 若子串长度等于1,则直接返回对应的整数

递归:

  1. 将子串最末尾的字符转换为整数
  2. 递归地将除末尾字符的字符的子串转换为整数,并加转换结果乘10加上末尾字符整数返回。

计算机组成原理考研笔记
https://rorschachandbat.github.io/考研/数据结构&os代码/
作者
R
发布于
2021年12月24日
许可协议