清华大学清华05计算机 考研真题

1、2005 cs数据结构：第一题：(15分)1、什麽是线性表，线性表的每一个表元素是否必须类型相同？为什么？2、线性表有两种存储形式：顺序表和单链表。线性表(Class LinearList): Class SeqList: Public LinearList (顺序表)(抽象基类)(派生类)Class Lin kedList: Public Lin earlist (单链表)如果需要定义和使用一个线性表对象，试问在程序中如何选用某种存储表示？3、二叉树给定前序和中序序列，求后序序列。其中前序序列为ABDEGCFHJ,中序序列为DBGEAHFJC。4、利用B树做文件索引时，设磁盘页块的大小是4,

2、 000字节(实际也许是4096字节，为了计算方便，就取成4000字节)， 指示磁盘地址的指针需要5个字节。现在有20，000，000个记录构成的文件，每个记录为200字节，其中包括关键码5个字 节。试问在此采用B树作索引的文件中，B树的阶数应为多少？假定文件数据部分未按关键码有序排列，则索引部分需要占用 多少磁盘页块。5、把关键码key散列到有n个表项(从0到n-1编址)的散列表中。对于下面函数H(key)(key为整数)，H(Key)=Key/n；H(Key)=1;H(Key)=(Key+ra ndom( n)%n;H(Key)=Key%p(n)，其中p(n)是不大于n的最大整数，而ran

3、dom (n)函数返回一个0到n-1之间的随机整数(包括0与 n-1)。问：这些函数能够做散列函数吗？(即对于插入和查找，散列程序能正常进行吗？)若能，它是一个好的散列函数吗？请讲明理由。 第2题：(5分)试证明:在同一棵二叉树的前序序列、中序序列和后序序列中所有叶结点都按相同的(先后)相对位置出现。第3题：(15分)在AVL树的插入和删除过程中，每插入一个结点都要判断从插入结点到树根的路径上是否有失去平衡的结点，如果有，就要 做平衡化旋转。平衡化旋转有四种类型：左单旋转、右单旋转、先左后右双旋转、先右后左双旋转。若关键码的输入序列为20，9, 3，12，13，27, 22，16，17，15，

4、18，10，试从空树开始顺序输入各关键码建立AVL树。 画出每次插入时树的形态。若需要平衡化旋转则做旋转并注明旋转的类型。基于上面建树的结果，画出从树中删除22,删除10与9后树的形态和旋转的类型。要求以被删关键码的中序下的直接前驱替 补该被删关键码。第4题：(15分)设Graph是一个带权有向图，可以直接使用的操作有int Number of Vertices。； |函数返回图中顶点个数int Number of Edges();|函数返回图中边数T GetValue( int i );|函数返回第i个顶点上的数据值Float GetWeight( int u, int v ); |函数返回

5、边的权值int GetFirstNeighbour(int v);|函数返回顶点v的第一个邻接顶点int GetNextNeighbour(int v, int w); |函数返回顶点v的相对于邻接顶点w的下一邻接顶点(1)下面是一个函数，利用Dijkstra算法在图G中求从顶点v到图中其它各顶点的最短路径和最短路径长度。函数中有5条语句 缺失，请阅读程序并将它们补上。(5分)template void ShortestPath( Graph G, int v, float dist,int path)/数组dist存放求到的从顶点v到各顶点的最短路径长度，数组path存放求到的最短路径。其中

6、，常量maxWeight是float类型数据在机器中能够表示的最大数，代表无穷边。int n=G.NumberOfVertices();int *S=new intn;int i,j;float w;for(j=0;j n; j+)distj=G.Getweight(v,j);Sj=0;if( j!=v & distjmaxWeight ) 1; |记路径上顶点 j 的前一顶点else pathj=-1; /* end of for */Sv = 1;distv=0;for( i=1;in;i+) float min = maxWeight; int u=v;for( j=0;j n ;j+

7、) if(2& distjmin ) u=j; min= distj;3;for(j=0;jn;j+) w=G.GetWeight(v,j);if(4& wmaxWeight & dist+wdistj)distj=dist+w;5; /* end of if */* end of for */* end of for */delete s;/* end of ShortestPath */ 设有一个带权有向图G=(V,E),w是G的一个顶点,w的偏心距定义为max从u到w的最短路径长度|u V.其中的路径长度指的是路径上各边权值的和。将G中偏心距最小的顶点移为G的中心，试设计一个函数返回带权

8、有向图的中心(如有多个中心，可任取其中之一)。函 数的首部为template int cen tre( Graph G, float & biasdist )参数表中的引用型参数biasdist返回最小偏心距的值，函数返回该中心的顶点号。(10分)操作系统：第一题：(15分)TLB快表的结构、原理、作用内存能放1024页,CPU访问一个页表项用100ns,TLB有32个页表项,CPU访问TLB里的一个页表项需要5ns,现在CPU访问一个页表项的时间是25ns,求快表的命中率.第二题：(10分)反置页表(In verted Page Table)的工作原理，同样的逻辑地址空间，主存空间，用一般的

9、页表和反置页表各需要多少项(反置的 表项是以主存空间来分的;比一般页表项少得多)(这个题的表述记不太清了，大概是这样的吧把反置页表的结构作用弄明白就没 有问题了)外存有2八64字节存储空间，主存有256MB(2八28字节)，一个页面有4KB(2八12字节),计算一个进程可能的最大页表项数(用2八*表示)，如果用反置页表表示，最大有多少页表项.第三题：(10分)1)写出unix(UFS)文件系统的结构2）计算一个包含10个直接索引、一个一级间接索引、一个二级间接索引的最大文件大小，要写出计算过程（UNIX的文件组织方式，磁块地址4BYTE,索引结点前10个直接，一个一级，二个二级的最大文件长度）

10、 第四题：（15分）学生选课最多可以选3们，但是如果王同学选了 3门C1C2C3后，想把C3换成C4,王同学就得先退选C3再申请选修C4但是这个时候可能C4已经选满了，而王同学想再选回C3的时候可能已经被人选满，不能再选了为了解决这个问题，使用一个函数TradeCourse（user,course1,course2）将课程 coursel 换成 course2.下面给出一种实现如果有不正确，给出所有错误的执行情况，并给出你认为正确的实现要有适当注释.15分.TradeCourse（user，course1，course2） course1-p（）;申请课程course1数据结构的互斥信号量co

11、urse1-drop（user）; 退选课程 course1course2-p（）;申请课程course2数据结构的互斥信号量if（course2-isFull（）=false）课程 course2 没有选满course2-add（user）; 申请选修课程 course2course2-v（）;释放课程course2数据结构的互斥信号量course1-v（）;释放课程course1数据结构的互斥信号量（答案是错误若课程2选满，即c2-full=1,会死锁）计算机原理：第一题：填空，每空1.5分，共18分1、 举出构成网络存储系统的两种方式：和2、举出3种用于构建并行集群系统的高速互联网3、

12、举出硬盘接口的两种类型和4、 举出两种显卡与计算机主板相联所使用的总线类型和5、 举出两种利用程序局部性原理构建的系统和6、IA32系统中单个进程所能访问的最大内存空间的大小第二题：20分1、什么叫Disk Array,它的原理和目标。（3分）2、 什么叫SMP,它和Cluster （集群系统）比较有什么区别和联系。（6分）3、什么叫Cache，它的原理和作用。（3分）4、嵌入式cpu和通用cpu相比有哪些特点？ （3分）5、 写出RISC、CISC、VLIW的基本思想。（5分）第三题：选择，每个3分，共12分。选择题基本上都是历年出过的真题，去核对一下就知道了。1、浮点数的尾数3位，符号为1位，用补码表示；阶数2位，符号1位。x的尾数是-0.875,阶数为1。y的尾数是0.625，阶数是2。则z=x-y规格化后的结果是：A、1011011B、*c、*D 以上均不对2、cache用组相联映射，一块大小为128字节，cache共64块，4块分一组。主存有4096块。