计算机考研

计算机考研833组成原理和数据结构思维逻辑框图

计算机专业

组成原理

第一章 计算机系统概述

1.1计算机的发展历程

1.1.1 计算机硬件的发展

1.计算机的发展历程

第一代计算机

电子管

1946~1957年

第二代计算机

晶体管

1958~1964年

第三代计算机

中小规模集成电路

1965~1971年

第四代计算机

超大规模集成电路

1972~至今

第五代计算机

智能计算机

第六代计算机

生物计算机与量子计算机

2.计算机的分类

按用途

专用计算机

通用计算机

巨型机

大型机

中型机

小型机

微型机

单片机

按指令和数据流

单指令流单数据流SISD

传统的冯诺依曼结构

单指令流多数据流SIMD

阵列处理器和向量处理器系统

多指令流单数据流MISD

实际上不存在

多指令流多数据流MIMD

多处理器和多计算机系统

3.计算机硬件的更新换代

摩尔定律

半导体存储器的发展

微处理器的发展

1.1.2 计算机软件的发展

计算机软件

程序

文档

操作系统

DOS

UNIX

LINUX

WINDOWS

1.2 计算机系统层次结构

1.2.1 计算机系统的基本组成

计算机系统

硬件系统

CPU

存储器

外部设备

软件系统

计算机运行程序和相应的文档

1.2.2 计算机硬件的基本组成

硬件

存储器

主存（内存，内存储器）

CPU直接访问

主存储器有许多存储单元组成，每个存储单元包括多个存储元，每个存储元存储一位二进制代码。存储单元可存储一串二进制代码，称这串代码为存储字，这串代码的位数成为存储字长

许多存储单元共同构成存储体

地址寄存器

存放访存地址

数据寄存器

暂存从主存中读或写的信息

辅助存储器（辅存，外存储器）

必须调入主存，才能被CPU访问

运算器

包括若干通用寄存器

用于暂存操作数和中间结果

累加器ACC

乘商寄存器MQ

操作数寄存器X

变址寄存器IX

基址寄存器BR

程序状态字寄存器PSW

保留各类运算指令或测试指令的结果的各类状态信息

控制器

计算机有两种信息流动

控制信息

数据信息

包括

程序计数器PC

用来存放当前预执行指令的地址，可以自动+1形成下一条指令的地址，与主存的MAR之间有一条直接通路

指令寄存器IR

用于存放当前的指令，其内容来自主存的MDR

控制单元CU

指令中的操作码字段OP（IR）送至CU，用以分析指令并发出各种微操作命令序列

指令中的地址码字段Ad(IR) 送往MAR来取操作数

一条指令可分为

取指阶段

在取指阶段访问存储器取出的二进制代码是指令

执行阶段

在执行阶段访问存储器取出的二进制代码是数据

I/O设备

输入设备

输出设备

其中，运算器+控制器=CPU ，CPU+主存储器=主机 ，I/O设备又称为外部设备

1945年，冯诺依曼提出“存储程序”的概念，称为冯诺依曼机

1.计算机有运算器、控制器、存储器、输入设备、输出设备组成

2. 指令和数据以同等地位保存在存储器内，并可按地址访问存储器

3 指令和数据均用二进制代码表示

4 指令由

操作码

表示操作的性质

地址码

表示操作数在存储器中的位置

5 指令在存储器中按顺序存放。通常指令是顺序执行，在特定条件下，可根据运算结果或设定的条件改变执行顺序

6 机器以运算器为中心，输入\输出设备与存储器之间的数据传送通过运算器完成

1.2.3 计算机软件的分类

计算机软件

系统软件（系统程序）

应用软件（应用程序）

计算机编程语言

机器语言

用0和1描述不同的指令

汇编语言

直接对硬件操作

高级语言

需要经过编译程序编译成汇编语言程序，然后经过汇编操作得到机器语言程序，或者直接由高级语言程序翻译成机器语言程序。

高级语言翻译程序

编译执行方式

“用手来编译”

产生目标代码

解释执行方式

“用嘴来解释”

不产生目标代码

1.2.4 计算机的工作过程

就是不断从存储器中逐条取出指令，然后送至存储器，经分析后由CPU发出各种操作命令，指挥各部件完成各种操作，直至程序中全部指令执行结束

1.2.5 计算机系统的层次结构

第1级 微程序机器级

第2级 传统机器级

第3级 操作系统级

第4级 汇编语言机器级

第5级 高级语言机器级

1.3 计算机性能指标

吞吐量

主要取决于主存的存取周期

响应时间

响应时间越短，吞吐量越大

主频

CPU周期（机器周期）

指令周期>CPU周期（机器周期）>时钟周期

CPU时钟周期

主频的倒数，是CPU最小的时间单位

时钟周期数*时钟周期=时钟周期数/时钟频率

CPI、MIPS、FLOPS（衡量运算速度）

CPI

执行一条指令所需要的时钟周期数

MIPS

每秒可执行百万条指令数

FLOPS

每秒执行的浮点运算次数

CPU执行时间

第二章 数据的表示和运算

数据结构

第一章 绪论

1.1 C与C++语言基础

1.2 算法时间复杂度和空间复杂度

时间复杂度

空间复杂度

1.3 数据结构和算法的基本概念

1.3.1 数据结构的基本概念

1. 数据

2. 数据元素

数据的基本单位

最小单位

3 数据对象

是性质相同的数据元素的集合，是数据的一个子集

4 数据结构

逻辑结构

存储结构

对数据的运算

5 数据的逻辑结构

线性结构

有序

前驱后继

非线性结构

一对一

树形结构

图形结构

6 数据的物理结构（存储结构）

当数据元素是由若干数据项构成的时候，数据项的表示称为数据域

常用存储方法

顺序存储方法

链式存储方法

索引存储方法

散列存储方法

1.3.2 算法的基本概念

1 算法

2 算法的特性

有穷性

一个算法必须保证执行有限步之后结束

确定性

算法的每一步骤必须有确定的含义

输入

一个算法有0个或多个输入

输出

一个算法有一个或多个输出

可行性

3 算法的设计目标

正确性

可读性

健壮性

高效率与低存储量需求

第二章 线性表

2.1 线性表的基本概念与实现

1 线性表的定义

线性表是具有相同特性数据元素的一个有限序列

该序列所含元素个数叫做线性表的长度（n)

n 可以等于零，表示线性表是一个空表

2 线性表的逻辑特性

只有一个表头元素，只有一个表尾元素

除表头和表尾外，其他元素只有一个直接前驱，也只有一个直接后继

3 线性表的存储结构

1 顺序表

2 链表

3 两种存储结构的比较

顺序表

随机访问

连续的占用一片空间

顺序表做插入操作的时候需要移动多个元素

链表

不支持随机访问

进行插入操作时无需移动元素

链表的5种形式

1 单链表

每个结点中除了包含数据域外，还包含一个指针域

有无头结点

带头结点

头指针head指向头结点

head->next==NULL时，链表为空

不带头结点

头指针head直接指向开始结点

head==NULL时，链表为空

两者区别

带头结点的单链表中有一个结点不存储信息

不带头结点的单链表的所有结点都存储信息

2 双链表

单链表只能由开始结点走到终端结点，而不能由终端节点反向走向走到开始结点

双链表在单链表结点上增添一个指针域，指向当前结点的前驱

有无头结点

带头结点

head->next==NULL时，链表为空

不带头结点

head==NULL时，链表为空

3 循环单链表

只要将单链表的最后一个指针域（空指针）指向链表的第一个结点即可

带头结点

指向头结点

不带头结点

指向开始结点

有无头结点

带头结点

head->next==NULL时，链表为空

不带头结点

head==NULL时，链表为空

4 循环双链表

类似与双链表

有无头结点

带头结点

因为带头结点的循环双链表中没有空指针

head->next==head

head->prior==head

head->next==head&&head->prior==head

head->next==head || head->prior==head

不带头结点

head==NULL时，链表为空

5 静态链表

静态链表借助一维数组来表示

每个结点含有两个分量

一个是数据元素分量data

另一个是指针分量

顺序表和链表的比较

基于空间的比较

1 存储分配的方式

顺序表的存储空间是一次性分配的

链表的存储空间是多次分配的

2 存储密度（存储密度=结点值域所占的存储量/结点结构所占的存储量）

顺序表的存储密度=1

链表的存储密度<1（因为结点中有指针域）

基于时间的比较

1 存取方式

顺序表可以随机存取，也可以顺序存取

链表只能顺序存取

2 插入/删除时移动元素的个数

顺序表平均需要移动一半元素（移动元素的期望E为 E=n-1/2）

链表不需要移动元素，只需要修改指针

2.2 线性表的结构体定义和基本操作

2.2.1 线性表的结构体定义

#define maxsize 100//这里定义一个整型变量maxsize，值为100

1 顺序表的结构体定义

typedef sturct { int data[maxsize] // int length }sqlist;

int A[maxsize]； int n;

常用

2 单链表结点定义

typedef struct LNode { int data; struct LNode *next; }LNode;

3 双链表结点定义

typedef struct DLNode { int data; struct DLNode *prior; stuct DLNode *next; }DLNode;

2.2.2 顺序表的操作

例2.1 已知一个顺序表L，其中的元素递增有序排列，设计一个算法， 插入一个元素x(x为int型)后保持该顺序表仍然递增有序排列 （假设插入操作总能成功）

本函数返回第一个比x大的元素的位置

int findElem(Sqlist L，int x) { int i; for(i=0;i<L.length;++i) { if(x<L.data[i] ) { return i; } } return i；

移动并插入元素

void insertElem(Sqlist &L,int x) { int p,i; p=findElem(L,x)； for(i=L.length-1;i>=p;--i） L.data[i+1]=L.data[i]； L.data[p]=x； ++(L.length)； }

例2.2 删除顺序表L中下标为P（0<=P<=lenrth-1）的元素，成功返回1，否则返回0，并将被删除元素的值赋给e

int deletElem(Sqlist &L,int P,int &e) { int i； if(P<0||P>L.length-1) return 0; e=L.data[P]; for(i=P;i<L.length-1;++i) L.data[i]=L.data[i+1}; --(L.length); return 1; }

2.2.3 单链表的操作