浙江大学软件学院硕士研究生入学考试大纲


浙江大学软件学院 　

　
浙江大学计算机及其相关专业硕士研究生入学考试大纲

　

　 参考书目： Data Structures and Algorithm等
[美] Mark Allen Weiss

一、计算机系统概论
内容：了解编译系统的工作原理；了解程序在计算机上的执行过程；了解存储的层次结构；了解操作系统的作用和主要组成部分。

二、信息在计算机中的内部表示与处理
内容：2进制与16进制；字；数据的大小；寻址方式和字节顺序（little endian和big endian）；字符串的机器表示；代码的机器表示；C语言中的位运算，C语言中的逻辑运算，C语言中的移位运算；整数数据类型；有符号和无符号整数及其原码和补码表示；有符号整数和无符号整数的转换；C语言中的有符号整数和无符号整数；整数的位扩展；整数的位截断；无符号整数和有符号整数的加减法与溢出；整数的乘法、除法和移位运算；IEEE浮点数表示，浮点数的舍入。

三、程序的机器级表示
内容：数据格式；IA32寻址方式；IA32数据传送、算术、逻辑与控制指令；C语言条件分支、循环、switch结构与相应汇编代码的对应关系，使用跳转表实现switch结构；IA32过程调用的实现：程序栈帧的结构，过程调用和返回指令，寄存器使用惯例(Caller saved and Callee saved registers)，递归调用，对一个过程调用全部过程的整体把握和理解；数组的分配和访问，多维数组，动态分配数组，数组与循环；结构与联合；指针、指针运算、指针与数组、结构、联合；数据对齐（alignment）；缓冲区溢出的基本原理。

四、链接
内容：了解链接在编译系统中的作用；ELF可重定位目标文件格式，了解该格式中每个section的作用；理解ELF符号表条目的结构；理解链接器符号解析机制：强符号与弱符号，解析多重定义的规则，使用静态库解析引用的规则；理解链接器重定位机制：重定位的两个步骤，ELF重定位表目的结构，理解R_386_PC32和R_386_32两种符号引用类型的重定位算法，理解重定位时ELF符号表条目和ELF重定位表目的相互作用关系；了解ELF可执行目标文件格式，了解它与ELF可重定位目标文件的格式的异同；了解加载器的基本功能；了解共享库与动态链接的基本概念。

五、异常控制流机制
内容：异常机制的工作原理，作用与分类；使用进程实现多控制流，进程的虚拟地址空间，操作系统的用户模式与内核模式，进程的上下文切换，系统调用基本原理和作用；理解若干Unix系统调用:getpid，getppid，exit，fork，wait，waitpid，sleep，pause，execve，getenv，setenv，unsetenv；信号的概念及其基本实现原理，信号发送、信号接收与信号处理；非本地跳转。

六、存储器的层次结构
内容：了解基本存储技术；程序的局部性与存储器的层次结构；cache的结构及其工作原理；write through和wirte back cache；了解影响cache性能的基本因素，理解cahce对程序性能的影响，理解编写cache友好代码的基本技术。

七、虚存
内容：地址空间和虚存的概念；地址翻译：页表的作用与结构，页命中与缺页中断，TLB的作用与结构，多级页表；物理内存、cache、虚存、页表、TLB几者之间相互联系以及它们在地址翻译过程中的相互作用，地址翻译的流程；虚存的作用与重要性：使用虚存管理存储器，使用虚存实现存储器保护；Pentium地址翻译；Linux虚存系统：Linux虚存存储区域，Linux缺页异常处理；存储器映射：共享对象，copy-on-write，fork与execve系统调用与虚存和存储器映射相关的操作；使用mmap函数进行用户级存储器映射；存储器的动态分配；垃圾收集技术；常见的与存储器相关的错误。

八、系统I/O
内容：理解几个基本的Unix I/O系统调用的功能pen,read,write,stat,fstat,dup,dup2；unix内核用于I/O操作的主要数据结构：文件描述符表，打开文件表，V-node表；共享文件；使用Rio包进行健壮的读和写。

九、并发编程
内容：并发的概念；并发编程的主要模式：基于进程的并发编程，基于I/O多路复用的并发编程，基于线程的并发编程；多线程程序中的共享变量；用信号量同步线程；基于预线程化的并发服务器。

例题：

1．Data representation，Byte ordering，Alignment

Consider the following program:

struct s {

char c;

double d;

float f;

short s;

};

union u {

unsigned char buf[24];

struct s a;

int i;

} u1;

int main()

{

int i,j;

memset(&u1.a, 0, sizeof(struct s));

u1.a.c = 0xac;

u1.a.d = -3.3;

u1.a.f = 0x1;

u1.a.s = 0xbcde;

u1.i = 0x12345678;

/* print out the bytes of u1.buf as 2 digit hexidecimal numbers with a line break after every 8 bytes */

for(i = 0; i < 3; i++) {

for(j = 0; j < 8; j++)

printf("0x\%.2x ",u1.buf[i*8+j]);

printf("
";

}

}

This program is compiled and run on a Linux/x86 machine. Fill in the output below. Write “??” if the value cannot be determined from the information provided.

0x____ 0x____ 0x____ 0x____ 0x____ 0x____ 0x____ 0x____

0x____ 0x____ 0x____ 0x____ 0x____ 0x____ 0x____ 0x____

0x____ 0x____ 0x____ 0x____ 0x____ 0x____ 0x____ 0x____

Answer：

0x78 0x56 0x34 0x12 0x66 0x66 0x66 0x66

0x66 0x66 0x0a 0xc0 0x00 0x00 0x80 0x3f

0xde 0xbc 0x00 0x00 0x00 0x00 0x00 0x00

2．The representation of program

The following problem tests your understanding of how for loops in C relate to IA32 machine code. Consider the following IA32 assembly code for a procedure dog():

dog:

pushl %ebp

movl %esp, %ebp

movl 12(%ebp), %ecx

movl $1, %eax

movl 8(%ebp), %edx

cmpl %ecx, %edx

jge .L7

.L5:

imull %edx, %eax

addl $2, %edx

cmpl %ecx, %edx

jl .L5

.L7:

popl %ebp

ret

Based on the assembly code, fill in the blanks below in its corresponding C source code. (Note: you may only use symbolic variables x, y, i, and result, from the source code in your expressions below ― do not use register names.)

int dog(int x, int y)

{

int i, result;

result = ________;

for (i = ________; _____________; ________)

result = _________________;

return result;

}

Answer：

int dog(int x, int y)

{

int i, result;

result = 1;

for(i=x;i< y;i+=2)

result = result*i;

return result;

}