精华1
威望97
K币202 元
注册时间2006-1-22
在线时间359 小时
最后登录2016-8-15
一般战友
- 精华
- 1
- 威望
- 97
- K币
- 202 元
- 注册时间
- 2006-1-22
|
3
楼主 |
发表于 2007-8-26 23:02
|
只看该作者
回复 #1 xjMatrix 的帖子
2005 cs
数据结构：
第一题：（15分）
1、什麽是线性表，线性表的每一个表元素是否必须类型相同？为什么？
2、线性表有两种存储形式：顺序表和单链表。
线性表(Class LinearList): Class SeqList: Public LinearList（顺序表）
（抽象基类） （派生类）
Class LinkedList: Public Linearlist（单链表）
如果需要定义和使用一个线性表对象，试问在程序中如何选用某种存储表示？
3、二叉树给定前序和中序序列，求后序序列。其中前序序列为ABDEGCFHIJ，中序序列为DBGEAHFIJC。
4、利用B树做文件索引时，设磁盘页块的大小是4，000字节（实际也许是4096字节，为了计算方便，就取成4000字节），指示磁盘地址的指针需要5个字节。现在有20，000，000个记录构成的文件，每个记录为200字节，其中包括关键码5个字节。试问在此采用B树作索引的文件中，B树的阶数应为多少？假定文件数据部分未按关键码有序排列，则索引部分需要占用多少磁盘页块。
5、把关键码key散列到有n个表项（从0到n-1编址）的散列表中。对于下面函数H(key)（key为整数），
1) H(Key)=Key/n；
2) H(Key)=1;
3) H(Key)=(Key+random(n))%n;
4) H(Key)=Key%p(n)，其中p(n)是不大于n的最大整数，而random（n）函数返回一个0到n-1之间的随机整数（包括0与n-1）。
问：这些函数能够做散列函数吗？(即对于插入和查找，散列程序能正常进行吗？)若能，它是一个好的散列函数吗？请讲明理由。
第2题：（5分）
试证明:在同一棵二叉树的前序序列、中序序列和后序序列中所有叶结点都按相同的（先后）相对位置出现。
第3题：（15分）
在AVL树的插入和删除过程中，每插入一个结点都要判断从插入结点到树根的路径上是否有失去平衡的结点，如果有，就要做平衡化旋转。平衡化旋转有四种类型：左单旋转、右单旋转、先左后右双旋转、先右后左双旋转。
1) 若关键码的输入序列为20，9，3，12，13，27，22，16，17，15，18，10，试从空树开始顺序输入各关键码建立AVL树。画出每次插入时树的形态。若需要平衡化旋转则做旋转并注明旋转的类型。
2) 基于上面建树的结果，画出从树中删除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 ); ||函数返回边<u，v>上的权值
int GetFirstNeighbour(int v); ||函数返回顶点v的第一个邻接顶点
int GetNextNeighbour(int v, int w); || 函数返回顶点v的相对于邻接顶点w的下一邻接顶点
(1)下面是一个函数，利用Dijkstra算法在图G中求从顶点v到图中其它各顶点的最短路径和最短路径长度。函数中有5条语句缺失，请阅读程序并将它们补上。（5分）
template <class T>
void ShortestPath( Graph <class T> G, int v, float dist[],int path[])
{//数组dist[]存放求到的从顶点v到各顶点的最短路径长度,数组path[]存放求到的最短路径。
//其中，常量maxWeight是float类型数据在机器中能够表示的最大数，代表无穷边 。
int n=G.NumberOfVertices();
int *S=new int[n];
int i,j;
float w;
for(j=0;j<n;j++){
dist[j]=G.Getweight(v,j);
S[j]=0;
if( j!=v && dist[j]<maxWeight ) __1___; ||记路径上顶点j的前一顶点
else path[j]=-1; } /* end of for */
S[v]=1;
dist[v]=0;
for( i=1;i<n;i++){ float min = maxWeight; int u=v;
for( j=0;j<n;j++ ) if( ___2____ && dist[j]<min )
{ u=j; min=dist[j];}
____3____;
for(j=0;j<n;j++){ w=G.GetWeight(v,j);
if(____4____ && w<maxWeight && dist+w<dist[j])
{dist[j]=dist+w;___5___;} /* end of if */
}/* end of for */
}/* end of for */
delete []s;
}/* end of ShortestPath */
(2) 设有一个带权有向图G=(V,E),w是G的一个顶点,w的偏心距定义为
max{从u到w的最短路径长度|u V}.
其中的路径长度指的是路径上各边权值的和。
将G中偏心距最小的顶点移为G的中心，试设计一个函数返回带权有向图的中心（如有多个中心，可任取其中之一）。函数的首部为
template <class T> int centre( Graph<T> G, float & biasdist )
参数表中的引用型参数biasdist返回最小偏心距的值，函数返回该中心的顶点号。（10分）
操作系统：
第一题：（15分）
1) TLB快表的结构、原理、作用
2) 内存能放1024页,CPU访问一个页表项用100ns,TLB有32个页表项,CPU访问TLB里
的一个页表项需要5ns,现在CPU访问一个页表项的时间是25ns,求快表的命中率.
第二题：（10分）
1) 反置页表(Inverted Page Table)的工作原理，同样的逻辑地址空间,主存空间,用一般的页表和反置页表各需要多少项.(反置的表项是以主存空间来分的;比一般页表项少得多.) (这个题的表述记不太清了,大概是这样的吧.把反置页表的结构作用弄明白就没有问题了)
2) 外存有2^64字节存储空间,主存有256MB(2^28字节),一个页面有4KB(2^12字节
),计算一个进程可能的最大页表项数(用2^*表示),如果用反置页表表示,最大有多
少页表项.
第三题：（10分）
1) 写出unix(UFS)文件系统的结构
2) 计算一个包含10个直接索引、一个一级间接索引、一个二级间接索引的最大文
件大小,要写出计算过程
（UNIX的文件组织方式,磁块地址4BYTE,索引结点前10个直接,一个一级,二个二级的最大文件长度.）
第四题：（15分）
学生选课最多可以选3们，但是如果王同学选了3门C1C2C3后，想把C3换成C4，王同
学就得先退选C3再申请选修C4.但是这个时候可能C4已经选满了,而王同学想再选回
C3的时候可能已经被人选满,不能再选了.为了解决这个问题,使用一个函数
TradeCourse(user,course1,course2)将课程course1换成course2.下面给出一种实
现.如果有不正确,给出所有错误的执行情况,并给出你认为正确的实现.要有适当注
释.15分.
TradeCourse（user，course1，course2）{
course1->p(); //申请课程course1数据结构的互斥信号量
course1->drop(user); //退选课程course1
course2->p(); //申请课程course2数据结构的互斥信号量
if(course2->isFull()==false){//课程course2没有选满
course2->add(user);//申请选修课程course2
course2->v(); //释放课程course2数据结构的互斥信号量
course1->v(); //释放课程course1数据结构的互斥信号量
}
}
(答案是错误.若课程2选满,即c2-full==1,会死锁)
计算机原理：
第一题：填空，每空1.5分，共18分
1、举出构成网络存储系统的两种方式：_____和_____
2、举出3种用于构建并行集群系统的高速互联网________________________
3、举出硬盘接口的两种类型_________和___________
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、1011011 B、******* C、******* D以上均不对
2、cache用组相联映射，一块大小为128字节，cache共64块，4块分一组。主存有
4096块。地址共需多少位：
A、19 B、18 C、17 D、****
3、指令的执行分为取指令用时△t，译址用时2△t，执行用时3△t。当流水执行的
时，指令执行所需最短时间为：
A 1n△t B、2n△t C、3n△t D、6n△t
4、总线分同步总线和异步总线，其中同步总线具备的性质是：
①成本高、②成本低、③逻辑复杂、④逻辑简单、⑤适应设备类型广泛、⑥对设备要求严格
A、2、3、6 B、1、3、5 C、1、4、5 D、2、4、6
[ 本帖最后由 xjMatrix 于 2007-8-27 20:45 编辑 ] |
|
发表于 2007-8-26 22:58
收藏
分享
支持
反对
