《名校计算机网络历年真题》由会员分享，可在线阅读，更多相关《名校计算机网络历年真题（43页珍藏版）》请在金锄头文库上搜索。
1、2008年北京航空航天大学961计算机专业综合考研试题一、简答题（45）1、写出影响算法执行的时间效率的主要因素，并指出哪些因素与算法的时间效率直接相关。2、已知元素的入栈顺序为A,B,C,D,E，在所有可能的出栈顺序中，写出第一个出栈的元素为C且第二个出栈的元素为D的所有组合。3、根据单词（Nov, Jul, Sept, Feb, Oct, Mar, May, Jun, Jan, Dec, Aug, Apr）的第一个字母在字母表中的顺序建立二叉排序树，当每个元素的查找概率相等时，求查找成功时的平均查找长度ASL。4、证明：具有n个顶点的无向图最多有n(n-1)/2条边。5、有人说，折半查找的
2、时间效率一定比顺序查找的时间效率高，你怎么看待这种说法？为什么？二、算法设计题（10）已知一非空完全二叉树存放于数组BT0.n-1中，请写出中序遍历该二叉树的非递归算法。三、算法设计题（10）写出不带头结点的双向链表的插入排序算法。四、简答题（45）1、数据传输控制方式有哪些？2、引入线程的目的是什么？3、P, V操作是如何实现互斥的的？4、什么是死锁？产生死锁的原因是什么？5、什么是文件系统？五、判断题（110）略。（基本上来自于历年真题）六、解答题（10）某机器字长为16位，采用段页式存储管理算法，页内偏移为12位，段表和页表内容如下，给出4个虚拟地址（二进制形式），问哪个地址产生缺段中断
3、，哪个地址产生缺页中断，哪些地址可以转换为物理地址，并求转换后的物理地址。（地址格式中段号占1位，段内页号占3位，页内偏移为12位，另外，在给出的页表中，物理块号占6位，最后又问该机器的最大物理内存是多少（答案：256 KB）。）七、简答题（44）1、利用等值演算的方法，写出求命题逻辑公式的主范式的方法。2、谓词逻辑中的永假式、可满足式、重言式、永真式之间的关系是什么？3、之间的真值关系是什么？4、如何判断公式中某个变元是约束变元还是自由变元？举例说明一个变元可以既是约束的又是自由的。八、判断下列结论是否成立，并至少用两种方法证明你的判断（6 + 8）1、 2、 九、填空题（18）1、冯诺依曼
4、计算机体系包括存储器、运算器、控制器和输入输出设备。2、在总线同步控制方式种，哪一种速度最快，哪一种对电路故障最敏感？3、在程序查询方式、程序中断方式和DMA方式中，哪一种方式主存与设备间有数据通路，哪一种方式使CPU与外设串行化？4、指令中的操作数分别为立即寻址和寄存器直接寻址时CPU访问主存的次数分别为多少次？5、存储器分层体系是根据程序访问的局部性原理提出的。十、存储器扩展的题（6）某机器字长为16位，最大物理内存为64 KB，最低地址的8 KB存放BIOS程序，其他空间存放用户程序，现有4K4的ROM和4K4的SRAM，问各需要多少片？十、Cache题（8）主存大小为2 MB，Cach
5、e大小为8 KB，采用2路组相联方式，每个Cache块大小为128字节。（1）求主存地址格式及各字段的位数和含义（2）Cache的格式（3）Cache的Tag需多少位？十二、指令系统的设计（8）某机器字长为16位，有8个16位的通用寄存器，请设计一指令系统，要求：（1）共有128条双操作数指令，且必有一操作数为寄存器直接寻址，另一个操作数有4种寻址方式，可以是立即寻址、寄存器直接寻址、寄存器间接寻址或变址寻址，其中立即寻址和变址寻址的偏移量均为16位；（2）指令所占的位数必须是16的倍数且要尽可能地短。要求：（1）写出影响指令系统设计的因素；（2）设计该机器的指令系统，写出各字段的位数和含义。
6、十三、微程序设计题（10）指令为SUB R0, (R1)，其中R0为目的操作数，采用寄存器直接寻址，R1为源操作数，寻址方式为寄存器间接寻址，每个机器周期包含4个节拍周期，写出该指令执行的详细微操作流程和对应处于有效状态的控制信号。北邮计算机网络2005年期末试题计算机网络期末试题（2005年1月）1 填空（11分）(1) IEEE802协议的数据链路层可分为 MAC和LLC 。(2) 请举出两个特殊的IP 地址（255.255.255.255）（127.0.0.1）。(3) 局域网中通常采用同轴电缆、双绞线和光纤作为传输介质。(4) 对一无限用户分隙ALOHA信道的测量表明10的时隙是空闲的
7、。信道载荷G是2.3，吞吐率是0.23。(5) 某局域网主机分配的IP地址为130.1.2.3,掩码为255.255.192.0,该IP地址属（B）类，该局域网可分配 16382 个IP地址。2 单项选择（9分）(1)关于TCP协议的描述，（b）是错误的a) 建立连接需要三次握手b) 能够保持上层消息的边界c) 接收方可以缓存错序的报文d)重传时延动态改变(2)下述协议中，（d）是物理层的标准a)IEEE802.3 b) rfc791 c) ISO8473 d) V.24(3)以太网中使用的成帧方法是(d)。a) 字符计数法 b) 字符填充法 c) 比特填充法 d) 物理层编码违例法(4)下述
8、协议中，（a）不是链路层的标准a) ARP b) SDLC c) PPP d) SLIP(5)下列不是数据报方式特点的是(c)a)每个分组自身携带有足够的信息，它的传送是被单独处理的b)在整个传送过程中，不需建立虚电路c)使所有分组按顺序到达目的端系统d)网络节点要为每个分组做出路由选择(6)下列选项中是以太网特点的是（b）a)不需要竞争信道 b)轻负载时时延低 c) 采用差分曼彻斯特编码 d)可分配优先级(7)关于链路状态协议的描述，（a）是错误的a) 相邻路由器需要交换各自的路由表b) 全网路由器的拓扑数据库是一致的c) 采用flood技术更新链路变化信息d) 具有快速收敛的优点(8) T
9、CP的拥塞控制方法如下：拥塞窗口从1开始（ c ），到达门限值时（a ）；如果出现超时门限值减半，拥塞窗口降为1。a) 按线性规律增长 b) 按对数规律增长 c) 按指数规律增长 d) 保持不变3 判断对错（5分）(1)（O ）面向连接的服务不一定是可靠的服务。(2)（X ）使用令牌桶和漏桶算法时，都会有突发数据输出。(3)（X）使用透明网桥联接局域网，所有的网桥都参与数据帧的转发。(4)（X）数据链路层和传输层都是采用固定大小的滑动窗口来进行流量控制。(5)（X）每个IP报文所能携带的用户数据为65535个字节4(12分)某传输层协议采用Tomlinson的时钟驱动方法设置TPDU初始序号，
10、假定序号比特数为10比特，主机时钟计数器为32比特，且每100ms发出一次时钟脉冲，分组的最大生命周期为30s. (1)最坏情况下,画图说明并计算多长时间需重新同步一次？102.4-30=72.4s(2)当主机每分钟发送180个TPDU时,多长时间需重新同步一次？3t=10(t-70.4)t=103s(3)TPDU长度为 128 Byte，不考虑报头开销,一个传输连接的最大传输速率为多少？10*128*8=10240 bps5（8分）下图拓扑结构中网桥为透明网桥，每个网桥有两个端口1和2，依据各主机的工作次序，分析并写出网桥bridge1，bridge2和bridge3的站表（开始时每个网桥站
11、表均为空，表项均不超时），其中A,B,C,D,E,F,G各站的MAC地址分别为 a,b,c,d,e,f和g。(1)A发送帧到Gbridge1, bridge2, bridge2均含表项a(2)B发送帧到Abridge1增加表项b(3)A 移动到 G所在的局域网 无变化(4) A发送帧到Ebridge1, bridge2, bridge2表项a更新6（12分）下图网络采用距离向量路由选择算法，路由器C收到邻居A、B、E、F的路由向量分别为(0,6,5,12,8,11)、(4,0,4,5,9,10)、(5,10,4,9,0,6) 、(10,10,4,6,6,0)，若测得C到A、B、E、F的当前距离
12、为3、4、3和4。(1) 请计算C的新路由表（要求给出目的路由器、下一跳路由器以及距离）。(3,4,0,9,3,4) (A,B,-,B,E,F)(2) 若不使用水平分割且无穷大值设为65535，当路由器D故障时, 分析路由器C经过两次路由信息的交换能否发现这一状况? 不能7（8分）一台有令牌桶控制的主机的网络接入速率为10Mbps,若令牌产生速率为2Mbps,桶初始容量为3Mbytes，问该主机能以峰值速率发送多长时间？ S=c/(m-p)=3*8/(10-2)=3*8/8=38（8分）已知host1 和 host2间的链路间有关特性如下：host1 和 host2距离为2000公里；电磁波的
13、传播速度为 200000公里/秒；链路的速率为1M bps; 数据帧的大小为 1500字节：计算： (1)停等协议线路的利用率；(2)发送窗口为10 时滑动窗口协议的利用率。Tf=1500*8/1000000=12 msTp=2000/200000=10msa=Tp/Tf=5/61)U=1/(2a+1)=37.5%2)W=10(2a+1)=8/3, U=100%9(15分)一个网络的拓扑结构如图11.1,网络层的协议数据单元格式如图11.2;其中ID,LENGTH,OFFSET,More Flag ,Address共计18字节;ID为数据包的标识号, LENGTH为数据包的长度(含数据包头18
14、字节)且计数单位为字节, OFFSET为分片的偏移量(计数单位为字节), More Flag=0 表示是最后一个分片; 分片采用非透明分片. 已知:host1和路由器1间的链路允许通过的最大数据包尺寸为1024字节;路由器1和路由器2间的链路允许通过的最大数据包尺寸为512字节;路由器2和host1间的链路允许通过的最大数据包尺寸为256字节;图11.1 网络的拓扑结构ID(2 Byte)LENGTH(2 Byte)OFFSET(2 Byte)More Flag(2 Byte)ADDRESS(10 Byte)UserData(X BYTE)图11.2 协议数据单元格式host1的产生的数据包头
15、如下: ID=65301,LENGTH=1018,OFFSET=0和More Flag=0;请分析该数据包在路由器1和路由器2间,路由器2 和host2间传输时的分片情况并写出各分片的数据包头(ID,LENGTH,OFFSET,More Flag).路由器1和路由器2间：分片1:ID=65301,LENGTH=512,OFFSET=0和More Flag=1分片2:ID=65301,LENGTH=512,OFFSET=494和More Flag=1分片3:ID=65301,LENGTH=30,OFFSET=988和More Flag=0host2和路由器2： 分片1:ID=65301,LENGTH=256,OFFSET=0和More Flag=1分片2:ID=65301,LENGTH=256,OFFSET=238和More Flag
