09计算机专业课大题(原题展现)

09计算机专业课大题回忆
数据结构：
1、题中给出了一种求最短路径的方法，要求证明其正确性，或者举反例证明其不正确。 这题反例比较容易举出，不难。
2、单链表L中只知道头结点指针，要求设计尽可能高效的算法，查找链表倒数第K个结点，并输出数据域的值，要求是不能对链表作出任何改动。
计组：
1、中断和DMA中CPU服务I/O所占CPU的时间比例，计算题。
2、数据通路的题，题中给出了一条加法指令的取指周期的时钟安排，要求写出执行周期的时钟安排，功能和信号序列。
操作系统：
1、PV操作题。 生产者消费者问题，生产者向缓冲区中放一正整数，两个消费者一个取奇数并统计其个数，一个取偶数并统计其个数。
2、虚拟存储器中的题目，告诉了页表内容，快表和页表的访问时间，缺页的处理时间，工作集大小和LRU置换方法，求三个虚存地址的访问时间，求一个虚存地址的物理地址。
网络：
路由方面的，给了个网络图，第一问要求划分子网，第二问要求写出某路由器的路由表，第三问是路由聚合的问题。








==================================================


恩,大概就怎么多了!!![s:2]

[ 本帖最后由 pikachu 于 2009-1-12 15:56 编辑 ]

下面是最短路径算法，问是否能够求的最短路径，如果可以请证明，如果不可以请举例说明
a 取u加入最短路径
b 将与u最近的节点v，如果不在路径内加入最短路径，另v等于u
c 重复b步骤  直到找到最短路径

现在是大题第二道

一个链表 头指针为list  链表结构为data   
link     请用最高效的方法找到倒数第k个节点
第一问  描述算法思想
第二问  描述算法详细解法
第三问  用c语言或c++或java根据算法思想和解法写出程序代码

第三题没法说  有一个图  反正是写算法流程的  

第四题  很长也没法说  计算的

三四题是组成原理的

第五题 有一个空缓冲区 容量是N 有三个进程p1，p2，p3 ，p1进程produce（）产生一个正整数， put（）将这个数放入缓冲区，p2进程getodd（）从缓冲区中取一个奇数并用countodd（）计数，p3进程geteven（）从缓冲区中取一个偶数，并用counteven计数，请用信号量机制描述算法（用为代码）   

第六题  请求分页存储器分配，页面大小为4KB，（下面有一个表 101H   1；-  0；
245H  1；）  具体不记得了

从TLB快表中取数是10ns ，从内存取数是多少秒忘了，中断缺页处理时间10的八次方ns（好像是）  快表TLB初始为空
先访问快表 再访问内存  如果都没有产生缺页中断  有三个虚地址1562H  2542H 还有一个数（三个数记不清了）  问访问这三个地址各需要多少时间
第二问  1526H（好像是这个数）的物理地址是多少

最后一题是网络  ip地址分配的 也有一个图  然后几个ip地址

路由器R1和两个局域网E1和E2相连通过路由器R2链接域名服务器和互联网  分别都有ip地址的 都花在图上

第一问  108.112.1.0/24 分配给E1 E2两个局域网 每个局域网至少120台主机  问ip地址怎么分配

楼主真是强人啊，一直在等这个啊。。

谢谢楼主~~~

谢谢了啊!

谢谢LZ我学习一下

学习一下 很好

十分佩服，十分感谢，先顶

xiexie

谢谢楼主……