1、浙江大学研究生入学考试计算机浙江大学研究生入学考试-计算机-2008浙 江 大 学二八年攻读硕士学位研究生入学考试试题考试科目 计算机专业基础 编号 864 注意:答案必须写在答题纸上,写在试卷或草稿纸上均无效。特别说明:本卷共5部分,其中13部分为必答题(各为40分)、45部分为限选部分(各为30分)。报考软件工程(MSE)的考生必须完成第四部分(数据库),报考计算机系统结构、软件与理论、应用技术的考生必须完成第5部分(计算机组成)。第1部分 操作系统 (共40分)试题1(5分):请简要比较操作系统调用(system call)与普通函数调用(function call)。试题2(5分):请
2、简要比较死锁防止(process prevention)与死锁避免(process avoidance)。试题3(5分):请简要比较fork with COW(fork with copy-on-write,带有写时复制的fork)与vfork(virtual fork,虚拟fork)。试题4(5分):请简要比较文件系统的文件实现 Achar s20,t20;t=”program”;strcpy(s,t); Bchar s20,*t=”program”;s=t; C. char *s,*t=”program”; strcpy(s,t); D. char s20,t20=”program”;st
3、rcpy(s,t);3. 下列程序的运行结果是 char str=”abc0def0ghi”,*p=str; printf(“%s”,p+5);4. 下列语句若想输出2 5 8 11 14 17 20 23 26,其中空缺的部分应该是什么? for(i=9;i=1;i-) printf(“%3d”, );二、程序填空。下列带命令行参数的程序运行形式为:prog fil1 fil2 fil3 .filen。该程序顺序读入各文本文件fil1 fil2 fil3 . filen 的内容,并将其中的内容输出,要求:若遇大写字母则转换为对应的小写字母输出,其他字符原样输出。(6分)#include #i
4、nclude main(int argc,char*argv) FILE *fp; char c; while(-argc0) if(fp=fopen( ,”r”)=NULL)printf(”Cannot open file!n”);exit(1);elsewhile( )if(isupper(c) /*判别c是否为大写字母*/putchar( );else putchar(c);fclose(fp);三、程序理解 (每题5分,共15分)1.写出下列程序的运行结果 。Int f(int a,int n) int s1,s2,i,j;S2=2;for(i=0;in;i+)s1+0;for(j=i
5、;js2)s2=s1;return s2;main() int a=4,-3,5,-2,-1,2,6,-2;printf(“%d“,f(a,8);1.写出下列程序的运行结果 。int f(int x,int y) if(y=1)return x;else return f(x,y-1)+x;main() printf(“%d“,f(21,12);2.写出下列程序运行结果 。#include#define LEN sizeof(struct line)struct line int mun; struct line *next;main() int k;struct line *p,*head,
6、*tail;head=tail=NULL;for(k=1;knum=k;if(head=NULL)head=p; tail=p;else if (k%2)tail-next=p; tail=p;elsep-next=head; head=p; if(tail)tail-next=NULL;for(p=head;p!=NULL;p=p-next)printf(“%d“,p-num);四、C语言编程(11分)数组 int a中存放若干段整数,每一个段由相同的整数组成。请编写函数 int max(int a,int n)求最长段的整数个数,其中n为数组大小(即所有整数的总数)。例如,a=1,1,2,
7、2,2,3,4,4,5,5,5,5,6,8,8,8,max(a,16)将返回4(最长段为“5,5,5,5”)。第3部分 数据结构 (共40分)一、单选题(每题1.5分,共6分)(1) 给定一个单向链表,若要删除一个指针p所指的节点,下列哪一个操作是正确的。 p-next=p-next-next p=p-next p-next-next=p-next p=p-next-next(2) 从理论上讲,将数据以下哪种结构存放,则查找一个数据所用时间不依赖于数据个数N。 二叉树查找 链表 二叉树 哈希表(3) 有n个结点的无向图的边数最多为下列哪一种? n+1 n(n-1)/2 n(n+1) 2n(n+
8、1)(4) 某二叉树的前序遍历序列为IJKLMNO,中序遍历序列为JLKINMO,则后序遍历序列为下列哪个选项。 JLKMNOI LKNJOMI LKJNOMI LKNOJMI二、简答题(共20分) (1) 二分查找算法的时间复杂度为(填空A) (请统一写在答题纸上) (2分)(2) 给定一个整数序列:25、84、21、47、15、27、68、35、20,请写出采用堆排序算法(Heapsort)初始建立的一个最小堆的整数序列(按照数组元素下标从小到大)。(5分)(3) 若文本中文字仅由5种字符a,b,c,d,e组成,它们出现的频率分别为21次、3次、9次、12次、55次,画出Huffman树,
9、并列出Huffman编码。(5分)(4) 在用于表示有向图的邻接矩阵中,对第I行的元素进行累加,可得到第I个定点的(填空B)度,而对第J列的元素进行累加,可得到第J个顶点的(填空C)度。(请统一写在答题纸上)(3分)(5) 将整数序列12、25、80、99、90、85、15 按序插入一个初始为空的AVL树,画出插入完毕后的AVL树(至少要写其中的三个步骤)。(5分)三、已知二叉树中的节点类型用BinTreeNode表示,被定义为:struct BinTreeNodechar data;BinTreeNode *leftChild, *rightChild;其中data为节点值域;leftChi
10、ld和rightChild分别为指向左、右孩子的指针域,根据下面函数声明写出求一棵二叉树高度的算法,该高度由函数返回。参数BT初始指向这棵二叉树的根节点。(8分)int BtreeHeight (BinTreeNode *BT);四、下面算法主要完成任务如下:给定一个单向链表,将其反序。请将该算法补充完整。(6分)/*Assuming no header and L is not empty.*/List ReverseList(List L)PositionCurrent,NextPos,PrewiousPos;PreviousPos=NULL; (填空E) ;(请统一写在答题纸上)Next
11、Pos=L-Next;while(NextPos!=NULL)CurrentPos-Next=PreviousPos;PreviousPos=CurrentPos; (填空F) ;(请统一写在答题纸上)NextPos=NextPos-Next; (填空G) ;(请统一写在答题纸上)return CurrentPos;第4部分 数据库(共30分)一下列E-R图表示销售数据库中客户(customer)、订单(order)、和产品(product)之间的联系。(共10分)有人将此E-R图转换成如下的关系模式:POC(oid,date,discount,cid,cname,address,pid,pn
12、ame,price,quality)请回答下列问题:1)关系POC的码(关键字,Key)是什么?(2分)2)关系POC属于BCNF吗?为什么?(2分)3)关系POC存在哪些缺陷?(3分)4)如何消除关系POC的缺陷?(3分)二图书数据库中有关系模式Book(ISBN,title,author,publisher,price,year),Book的每一行表示一种图书的信息。请用SQL语言实现如下查询:(共10分) 1)找出价格最贵的图书(3分) 2)统计每个出版社的图书数(3分) 3)找出在同一出版社出版了两种以上图书的著者(4分)三数据库系统中发生事物级别的故障的原因有哪些?数据库管理系统是如
13、何回滚(rollback)故障事物的?(共10分)第5部分 计算机组成(共30分)一、基础知识题(14分)1.在多层次结构的存储体系中,高速缓冲存储器CACHE的功用是解决什么问题?(2分)2.计算机硬件指令子程序调用JAL的功用是什么?(2分)3.在当今计算机中都有PC相对寻址模式,为程序条件转移提供很大方便。请给出你所学到的PC相对寻址的条件转移地址计算公式。(2分)4.CPI的含义是什么?(2分)5.设字长为32位的寄存器存放数N,请对照下列要求,用不等式指明N的表示范围: 1. 5A。N表示无符号整数;(3分) 2. 5B。N为补码表示的整数,设符号位在最高位;(3分)二、程序及计算题
14、(10分)1.加法器的相对性能可以通过进位延时量化计算。设与门AND、或门OR的时延为T,c0为最低进位输入,g0,g1,g2,g3分别为本地进位输入,p0,p1,p2,p3分别为传送进位,在采用4位先行(并行)进位链时,(1).写出向高位进位C4的逻辑表达式;(2)计算向高位进位C4的时延时间。(6分)2.写一个MIPS指令条数最少的汇编程序,实现$t2=$t3的绝对值,即$t2=|$t3|,$t2、$t3都用补码整数表示。(4分)三、设$S1,$S3为寄存器文件中的寄存器,指令MOV $S1,$S3功能是以$S3中值作为存储器地址,取出该存储器单元的值送给寄存器$S1。现给定构建数据通路的下列功能单元,和该指令格式:说明:第2125位为寄存器第一源操作数地址;第2016位为寄存器第二源操作数地址,本指令用MIPS零号寄存器$ZERO表示,意为第2016位为0,从零号寄存器$ZERO取值也是0。第1511位为目的寄存器。第100位对本指令不起作用。要求完成: (1).定义第2631位指令操作码。(1分) (2).用适当的连线完成能实现指令MOV $S1,$S3功能的多时钟周期数据通路。(5分)