|
|
楼主 |
发表于 2007-8-6 23:26
|
显示全部楼层
以下给出浙大考研辅导半的笔记。
注：这是两年前的（新的没有），只能参考，而且不是十分全。文字版入群问
计算机组成复习提纲
1.计算机系统的层次结构,核心层为硬件->系统->外层应用软件
2．软件系统的分类:系统软件和应用软件.
系统软件:编译、os、汇编、应用软件：edit,cad…
3．计算机硬件组成：alu（数据通路datapath）、存储器、控制器、输入、输出
数据通道和控制器称为cpu或processor
4．机器指令格式及其分类
分类：算术运算指令、访问存储器指令（传送）、转移指令、移位指令、输入、 输出指令
格式：无址、三地址
mips指令：三地址与二地址
5．用汇编指令进行程序设计
g=h+A #寄存器分配
add $t1,$s4,$s4 #i->$s4,i*2->$t1
add $t1,$t1,$t1 #i*4->$t1
add $t1,$t1,$s3 #$s3为A数组首址,$t1为A的地址
lw $t0,0($t1) #$t0=A的值
add $s1,$s2,$t0 #g=$s1=h+A
详见英文书p114
循环程序练习：转移指令应用 p126
loop: g=g+A;
i=i+j;
if(i!=h) goto loop;
(bne $s3,$s2,loop用法)
while(SAVE==k) P127
i=i+j;
(j loop用法)
case/switch statement P129
switch(k){//其中k取0,1,2,3
case 0:f=i+j;break;
case 1:f=g+h;break;
case 2:f=g-h;break;
case 3:f=i-j;break;
}
用beq，jr，j等指令给编写，开关语句要用汇编指令设计、编写，需要一张跳转表
k*4+首址（跳转表），从表中取出跳转表地址
6．寻址方式
lw $t1,0($t2) #基地址寻址
add $t1,$t2,$t3 #寄存器寻址
addi $t1,$t2,100b #立即
beq $t1,$t2,l1 #pc相对寻址
j mm #j型寻址，相当于直接存储寻址
jr $t #寄存器寻址
重点掌握寻址方式、常用指令用于循环、当循环和开关语句汇编程序编程方法
7．数组与指令+编程设计（了解编程方法） P174
基于MIPS架构CPU及指令设计不要求
8．机器数的表示，补码，原码和标准的浮点数表示及运算
重点掌握串行加法、并行进行加法的设计，及进位时间的计算，并行进位链及串行进位的电路的设计方法，补码，浮点数表示（IE754标准）
原码乘法器（除法器）补码的设计原理及原理及逻辑框图设计
补码乘法，一位Booth’s P259,P257,加减交替法
IEEE 754标准：
e=E-127 e:真值 E:机器表示（移码）
1 8 23
E用移码表示，其中1位符号位
(-1)S×(1+Significant)×2E
|M|=0.1XX......
9．掌握多时钟周期计算机数据通路的结构，掌握指令执行过程（能画出指令执行的状态转换图）了解位程序的设计方法和基本工作原理
10．存储系统的体系结构，多级存储系统Cache----直接地址映射或组相联地址映射，全相联地址映射，地址映射的原理设计虚拟地址、实地址、页表、页表寄存器，含义必须搞清楚，能计算页表容量=页表单元数×（标志位+实页号位长）
虚页号数=虚拟地址-页内地址 P545-549,P569-570
缺页中断、命中、失效，写通，回写术语概念
重点掌握抵制变换结构的工作原理，变换逻辑设计及给定虚地址，主存容量，页面大小，能计算，页表单元数，实页号长度，实地址位数及寻找到的实页号
段表不要求
11．I/O系统
磁盘系统，平均旋转时间，平均寻道时间
记录格式，地址表示：头号（页号），道号，扇区号
串行接口，并行接口（按位宽传输分）
中断分类，中断处理过程，中断请求，中断响应，中断处理，中断返回，中断屏蔽，开/关中断概念，多重中断
英文版P647-649
按控制方式分：
程序控制查询接口
程序控制中断方式，软件排队找中断源，矢量中断找中断源
DMA 直接存储器接口访问控制
通道 接口编址方式：单独编址方式（存储器统一编址）
重点掌握：向量中断，中断响应，执行中断隐指令，中断处理，中断返回等详细过程
英文版：第8章
王爱英：P332,P338 338-343
中断隐指令
题型：名词解释，计算题，若需要也可画图，编程（总分不少于30分）
友情提示：Computer Organization&Design The Hardware/Software Interface(2th Edition)机械工业出版社 ，即为文中所指英文版，为本校教学用书。
复习时应该以英文版为主，再辅以其它中文参考书即可，另请参考往年试题。
数据结构复习
第一部分 数据结构复习大纲
复习目标
1) 掌握基本数据结构的概念及其应用，2) 如：堆栈、队列、链表、树、堆、图等
3) 掌握基本的sorting,Hashing和Searching算法
基本考试类型
证明题（如树的特性）出题概率不高
填空题 可能会有英文书的例子
问答题（含数据结构设计、算法结构等）
如图的表示方法、最小生成树、最短路径等
编程题（含算法设计）
注意思路清晰
数据结构的基本要素
链表，单向链表，双向链表、循环单双向链表、广义表
队列、堆栈：循环条件判断、数组表示
树
i. 树的二叉树表示
ii. 二叉树的特性（层次、结点等）
iii. 二叉树的表达
iv. 二叉树的周游（如已知先、中序，v. 求后序）
vi. 线索二叉树（如已知中序线索，vii. 求遍历）、哈夫曼树
viii. 堆（Heap）---用数组表达，ix. 基本操作（插入、删除）
x. 二叉搜索树（查找树）
xi. 森林（森林的二叉树表达）
出题层次类型：
▲三种基本类型（线性表、树、图）的对象定义与操作实现---属于概念层次
▲应用问题（如最短路径）---属于方法层次
▲查找与排序---属于算法层次
查找：①静态查找（顺序、二分）
②动态查找（查找树、哈希）
查找树：平衡树，B+树，B-树）
排序：①选择排序......堆排序
②交换排序......快速排序
③插入排序......SHELL排序
图
1) 图的定义和表达(4种基本表达方法)
2) 图的操作：深度遍历、广度遍历、连通分量、生成树等
3) 最小生成树（两种算法）
4) 最短路径
迪杰斯特算法、动态规划法
5) AOV、AOE网
典型例子：拓扑排序、求关键路径
排序
i. 插入
ii. 快速
iii. 归并
iv. 堆
v. 拓扑
vi. 基数
查找
Hashing(构造、冲突解决)
最优二叉查找树（概念即可）
AVL树（四种情况，如何维护即可）--->B+树
算法设计基本方法
回溯法
分治法（典型例子：归并排序）
贪心法（如：选择排序）
动态规划法
第二部分 复习内容
一、链表
1．单向链表就地逆转
q0 q1
q0 q1 q2
while(q1!=Null){
q2=q1->next;
q1->next=q0;
q0=q1;
q1=q2;}
初始：q0=Null
q1=L->next
广义链表
二、堆栈和队列
循环队列（判断满和空条件）
三、树
树的二叉树表达
二叉树的特性
a) 第i层二叉树最多节点数 性质1
b) 深度为k的二叉树最多节点数 性质2
c) 性质3（向上边的角度与向下边的角度结合
d) 2i,2i+1......
数组表示二叉树
二叉树的遍历
遍历算法
由前/中（后/中）推导后（或前）来构造树
线索二叉树（加了一个结点，为了方便遍历实现）
中序线索（用此来实现遍历）
给出一棵树线索化
堆
插入元素、删除元素的算法
图
1．图的表示方法
数组表示：矩阵表示法（有向/无向）
邻接表（逆邻接表）表示法（有向/无向）
十字链表（有向）
多重链表（无向）
2．图的操作
深度搜索、广度搜索
最小生成树
a) Kruskal算法
b) Prim算法
最短路径
AOV和AOE
拓扑排序、关键路径
排序
插入排序，基本插入排序方法，希尔排序
交换排序：基本交换排序（冒泡、快速排序）
归并排序：循环、递归
选择排序：堆排序
快速排序（算法思想）
两种思路：①单向扫描；②双向扫描
堆排序
Adjust（从n/2开始调，保证左边是堆，右边是堆，往上调）
查找
1．Hashing
基本思想
构造方法
冲突解决（开放地址、线性探测、链表）
链表（关于其操作来实现冲突解决）
exp. Insert_LinkHashing(...)
2．AVL树
首先判别各种平衡旋转方法（找平衡因子被破坏的及谁破坏它的）
实现旋转来维护（简单的就是旋转后满足排序二叉树）
这里没有c部分的，其实c只需看我们学校的教材再做浙大真题就可以了，不过c这部分一定要小心，切记，里面有许多陷阱的。 |
|
IP卡
狗仔卡
显身卡
发表于 2007-7-27 18:02
发表于 2007-7-28 20:17
