浙江大学07年计算机考研.doc

浙 江 大 学二O O 七年攻读硕士学位研究生入学考试试题 （由林子整理，:170479150）第一部分 操作系统（共40分）试题1（5分） ： 请简要比较进程（process）与程序（programs）试题2（5分） ： 请简要比较进程(process)与线程（threads）试题3（5分） ： 请简要比较请求实存管理(actual memory management)与虚存管理（virtual memory management）试题4（5分） ： 请简要比较请求页面调度(demand paging)与请求分段调度(demand segmentation)试题5（10分） ： 考虑某个系统在如下时刻的状态 Allocation Max Available A B C D A B C D A B C DP0 0 0 1 2 0 0 1 2 1 5 2 0 P1 1 0 0 0 1 7 5 0 P2 1 3 5 4 2 3 5 6 P3 0 0 1 4 0 6 5 6 使用银行家算法回答下面的问题：a. Need矩阵是怎样的？b. 系统是否处于安全状态？如安全，请给出一个安全序列。

c. 如果从进程P1发来一个请求(0,4,2,0)，这个请求能否立刻被满足？如安全，请给出一个安全序列试题6（10分） ： 理发店有一位理发师、一把理发椅及三把供等候理发的顾客做的椅子如果没有顾客，理发师就去睡觉如果顾客来时所有的椅子都有人，那么顾客就离去如果理发师在忙而有空闲的椅子，那么顾客就回坐在其中的一个空闲的椅子上如果理发师在睡觉，顾客会唤醒他请利用信号量(semaphores),写个程序来协调理发师和顾客进程第2部分 程序设计（共40分）一、 选择（每小题2分，共8分）1. 下列程序的运行结果是什么？Main ( ){ char s[]=”Zhejiang”;int x=3,y=3;printf(“%d,%d”,(++x,y++),sizeof(s));} A) 3 9 B) 4 9 C) 4 3 D) 3 82. 设x、y、z 均为int类型，若x&&y‖z的值为1，则A) 若z为0，则x和y必为1 B)若z为0，则x和y均不为0C)x、y、z必都为1 D)若x和y均为1，则z必为03. 下列程序的结果是什么？Main(){ int a[][4]={1,3,5,7,9,11,13,15,17,19,21,23};int(*p)[4];p=a;printf(“%d”,*(*p+2));}4. 下列程序prog.c编译后执行命令行“prog 123 456 ABC”,其运行结果是什么？Main( int argc,char*argv[]){printf(“%c”,*(++argv[2]));}A)3 B)4 C)5 D)6二、 程序填空。

下列函数inverse将一单向链表h就地逆转请将空缺的部分填上如，若h为a->b->c->d,调用h=inverse(h)后h为：d->c->b->a6分） struct node { int info; struct node *next;}; struct node *inverse(struct node *h){ struct node *p1,*p2,*p3;p1=NULL;while(_2A_){p3=p2->next;p2->next=_2B_;p1=p2;p2=p3;}return p1;}三、 程序理解（每题5分，共15分）1.写出下列程序的运行结果Int a[]={1,2,3,21.22,23,11,12,13}Int f(int a[] ,int n){if(n= =0)return(a[0]);else if(f(a,n-1)>a[n])return f(a,n-1);else return (a[n]);} main(){printf(“%d”,f(a,8))}2.写出下列程序的运行结果 Void f(char s[],int start,char t[]){int m,n,k,i,j;n=0;m=0;k=0;for(i=0;s[i]!=’\0’; i++)m++;for(i=0;t[i]!=’\0’;i++){n++;if(t[i]>=’0’&&t[i]<=’9’)k++;}for(i=m+n-k,j=m;i>start;i--,j--)s[i]=s[j];for(i=0;i’9’)s[start++]=t[i];}main(){char s[30]=”abc123d4ef”,t[]=”1a2b3c”;f(s,6,t);printf(“%s\n”,s);}3写出下列程序的运行结果。

#include int f(int n,int m) { int n1,m1,result=0;if(n&&m){n1=n%10;m1=m%10;if(nl= =m1)result=f(n/10,m/10)*10;else result = f(n/10,m/10)*10+((n1>m1)?n1:m1);return result;}else return n+m;}void main(){printf(“%d\n”,f(12345,3333));}四、 C语言编程（11分）有一个整数序列代表一电梯在运行过程中所需要停的楼层顺序（楼层号为非负整数）若该电梯上移一层需要6秒，下移一层需要4秒，在楼层中停需要5秒假定电梯开始时在第0层，且电梯满足申请要求后不必回到第0层请编写C程序，输入整数系列，输出电梯满足该系列的请求共需要多少时间（设用-1代表整数序列结束）如输入2 3 1 –1，将输出 41第3部分 数据结构1. 将5个字母‘ooops’按此顺序入栈，则有几种不同的出栈顺序可以仍然得到‘ooops’3分）A. 1 B. 3 C. 5 D. 62. 下面哪一个方法可以判断出一个有向图中是否有环（回路）？（3分）A.深度优先遍历 B.拓扑顺序 C.求最短路径 D.求关键路径3. 在下列查找的方法中，平均查找长度与结点个数n无关的查找方法是哪种？（3分）A．顺序查找 B.二分法 C.利用二叉搜索树 D.利用哈希(hash)表。

4．一个三叉树有度(degree) 为1的结点5个，度为2的结点为3个，度为3的结点有2个，则这棵三叉树的叶子结点的个数有多少3分） A. 10 B. 12 C. 13 D. 85. 给定一个整数序列 25、84、21、47、15、27、68、35、20，请给出用步长为3的希尔排序(shell sorting)算法进行第一轮排序后的结果5分）6. 右图所示为一有向图，请给出该图的下述要求：1） 每个顶点的入/出度2分）2） 邻接矩阵2分）3） 逆邻接表2分） 4） 强连通分量2分）7. 下面是将任意序列调整为最大堆(max heap)的算法，将空白部分补充完整：（6分）将任意序列调整为最大堆通过不断调用adjust函数，即：for(I=n/2;I>0;I--) adjust(list ,I,n);其中list为待调整序列所在数组（从下标1开始），n为序列元素个数，adjust函数为： void adjust(int list[],int root ,int n ){ int child ,rootkey; rootkey=list[root]; child=2*root; while (child <=n){if((childlist[child]) break;else{list[____]=list[child];chuld*=2;}}_________=rootkey;}8用C语言完成一个在二叉搜索树中删除关键字为X的结点的程序（9分）第5部分 计算机组成（共30分）1. 写出你所学的符合下列要求的机器汇编符号指令实例（6分，每小题1.5分）例如，寄存器寻址方式指令：add $s1,$t1,$t2 1A 基地址寻址方式（Base addressing）指令1B 立即数寻址方式（Immediate addressing）指令1C PC相对数寻址方式（PC Relative addressing）指令1D. (伪)直接寻址方式(Pseudodirect addressing)指令2 已知二进制表示的机器数1000 0000 （字长8位），分别求出表示下列要求的真值。

答案用十进制表示3分，每小题1.5分）2A. 该数表示补码，其真值是多少？2B.该数表示原码，其真值是多少？3. 设磁盘的扇区大小为512字节，盘转速为12000转/每分钟，磁盘平均寻道时间5.6ms，传输速率为20MB/每秒，磁盘控制器开销时为1ms，计算读写一个扇区所需平均时间假设读写磁盘时不要等待7分)4. 设CPU与打印机以中断控制方式进行数据传送，CPU中断响应时，打印机接口控制器送给CPU的中断矢量表（中断矢量表存放中断矢量）指针是1200H，1200H单元中的值为2000H，问CPU响应打印机中断请求时，程序计数器PC的值是多少4分)5. 在多级存储系统中，由地址变换机制解决小cache与大内存的影射问题，问影射方式有哪三种？___5A___, _____5B______, ______5C_________. （3分）6. 给定下列单时钟周期数据通路的功能模块，为能执行ADD $1,$2$3,(1)请添加上必需的控制器及信号连线（3分），（2）说明执行这条指令的几个步骤（2分）3）下图还能执行哪几类MIPS指令（2分）（共7分）（图是5.3.1节 图5.10） （注：素材和资料部分来自网络，供参考。