北航2003年计算机专业硕士研究生入学考试基础真题
一、1、数据的存储结构通常可以有（）。
A、两种，它们分别是：顺序存储结构和链式存储结构
B、三种，它们分别是：顺序存储结构、链式存储结构与索引结构
C、三种，它们分别是：顺序存储结构、链式存储结构与散列结构
D、四种，它们分别是：顺序存储结构、链式存储结构、索引结构与散列结构
2、删除非空线性链表中由指针p 所指链结点的直接后继结点的过程是依次执行动作（）。
（设链结点的构造为[data|link])。
A、r<-link(p); link(p)<-r; call RET(r)
B、r<-link(p); link(p)<-link(r); call
RET(r)C、r<-link(p); link(p)<-r; call RET(p) D、link(p)<-link(link(p)); call
RET(p)
3、已知二维数组A[1：4，1：6]采用列序为主序方式存储，每个元素占用4 个存储单元，并且A[3，4]的存储地址为1234，元素A[1，1]的存储地址是（）。
A、1178
B、1190
C、1278
D、1290
4、某堆栈的输入序列为1，2，3，4，下面四个序列中的（）不可能是它的输出序列。
A、1，3，2，4
B、2，3，4，1
C、4，3，1，2，
D、3，4，2，1
5、若某完全二叉树的深度为h,则该完全二叉树中至少有（）个结点。
A、2 的h 次幂
B、2 的h+1 次幂
C、2 的h-1 次幂-1
D、2 的h-1 次幂+1
6、若一棵深度为6 的完全二叉树的第6 层有3 个也结点，则该二叉树共有（）个也结点。
A、17
B、18
C、19
D、20
7、已知带权连通无向图G=（V，E），其中
V={v1,v2,v3,v4,v5,v6,v7},E={(v1,v2)10,(v1,v3)2,(v3,v6)11,(v2,v5)1,(v4,v5)4,
(v4,v6)6,(v5,v7)7,(v6,v7)3}(注：顶点偶对右的数据为边上的权值），从源点v1 到顶点v7 的最短路径上经过的顶点序列是（）。
A、v1,v2,v5,v7
B、v1,v3,v4,v6,v7
C、v1,v3,v4,v5,v7
D、v1,v2,v5,v4,v6,v7
8、下面的说法中，不正确的是（）。
A、折半查找方法不适用于按值有序链接的链表的查找
B、折半查找方法适用于
按值有序的顺序表的查找
C、折半查找方法适用于按关键字值有序排列的顺序文件的查找
D、折半查找方法适用于排列连续顺序文件的查找
9、将数据元素2，4，6，8，10，12，14，16，18，20，22 依次存放于一个一维数组中，然后采用折半查找方法查找数组元素16，被比较
过的数组元素的轨迹（数组下标）依次为（）。
A1
A2
An
B
……
A、12，18，14，16
B、12，14，18，16
C、6，9，7，8
D、6，7，9，8
10、从未排序序列中选择一个元素，该元素将当前参加排序的那些元素分成前后
两个部分，前一部分中所有元素都小于等于所选元素，后一部分中所有元素都大于等于所选元素，而所选元素处在排序的最终位置。
这种排序法称为（）。
A、插入排序法
B、泡排序法
C、谢尔排序法
D、快速排序法
二、1、下列限制条件下，如何从前至后依次输出非空线性表中的最后k 个数据元素？
限制1：线性表的长度未知，也不允许采用先求出线性表的长度的方法；
限制2：线性表中每个数据元素只允许作一次输入操作。
2、在散列地址范围与散列函数都分别相同的前提下，通常采用链地址法比采用
开放地址法处理冲突的时间效率要高，为什么？
三、已知长度为n 的线性表A 采用顺序存储结构，并且元素按值的大小非递减
排列，请写一算法，删除线性表中值相同的多余元素。
（该算法完成以后，线性表中数据元素严格按值递增排列）
四、已知非空二叉树的中序序列与后序序列分别存放于数组INOD[1：n]与POSTOD[1：n]中，并且各个结点的数据信息均不相同，请写一非递归算法，生成该二叉树的二叉链表存储结构（设链结点的构造为[lchild|data|rchild],根结点地址有T 给出）。
五、1、一般情况下，计算机硬件系统有（）、（）和（）三部分组成。
2、用1 位比较法进行两个16 位定点整数补码的乘法运算，共需要进行（）次右移运算。
3、从总体上来看，总线的仲裁方式可以分为（）和（）两种。
其中前者又分为链式查询、（）和（）三种优先权仲裁方式。
4、下列指令格式的寻址方式为变址间接寻址，其格式为：[OP|I|X|disp]，其中I 为间接寻址位，I=1 表示间接寻址，I=0 表示直接寻址；X 为变址寄存器号；disp 为位移量。
寻址过程为先变址后间接，当I=0 时，操作数有效地址EA=（）；当I=1 时，操作数有效地址EA=（）。
六、1、某计算机主频为800M，每个机器周期平均包含2 个时钟周期，每条指令平均包括2.5 个机器周期，求该计算机的平均指令执行速度为多少MIPS。
2、什么是DRAM 的刷新？为什么DRAM 需要刷新？
3、详细叙述中断响应和中断处理的过程。
七、1、某机字长为16 位，采用16 位定长指令格式，机器格式如题七图所示，指令：ADD R1，（R2）；加法指令，R1<-(R1)+((R2))。
写出执行该指令的取指周期、取数周期和执行周期的详细微操作。
__
2、某微程序控制器采用水平型微指令格式，控制存储器36 位宽，微指令格式包括控制字段、地址选择字段和次地址字段三部分，控制字段需要表示的微操作共有24 个，地址选择字段用来指明引起微指令转移的条件，这些条件基于8 个不同的标志来建立。
1）设计该微程序控制器的微指令格式，指出各字段各占多少位。
2）控制存储器的容量有多大。
八、某计算机存储系统包括16KB 结构为4 路组相联的Cache,主存容量为16MB，假设Cache 每块大小 2003 –2008年北航计算机专业考研真题1 0
1)Cache 和主存各分为多少组？
2）写出主存的地址格式。
3）Cache 的地址标记（Tag）至少应为多少位？
4）主存地址23E4F8H 将映射到Cache 的哪一组？
九、1、临界区2、系统调用3、文件系统4、重定位5、SPOOLing 技术
十、1、进程在运行中，可以自行修改自己的进程控制块。
2、进程申请CPU 得不到满足时，其状态变为等待态。
3、在虚存系统中只要磁盘空间无限大，作业就能拥有任意大的编址空间。
4、在内存为M 的分时系统中，当注册的用户有N 个时，每个用户拥有M/N 的
内存空间。
5、特殊文件是指其用途由用户特殊规定的文件。
6、信号量机制控制进程同步、互斥的能力与通信机制是等价的。
7、在作业调用时，采用最高响应比优先的作业调度算法可以得到最短的作业平均周转时间。
8、实时系统中的作业周转时间有严格的限制。
9、当前目录的引入，提高了访问文件的效率。
10、打印机是一类典型的块设备。
十一、考虑有三个吸烟者进程和一个经销商进程的系统。
每个吸烟者连续不断地吸他做好的烟卷。
做一支烟卷需要烟草，纸和火柴三种原料。
这三个吸烟者分别掌握有烟草，纸和火柴。
经销商源源不断地提供上述三种原料，但他只将其中的两种原料放在桌上，具有另一种原料的吸烟者就可做烟卷并吸烟，且在做完后给经销商发信号，然后经销商再拿出两种原料放在桌上，如此重复。
1、请给出P、V 操作的定义及信号量的物理意义。
2、试设计一个使经销商和吸烟者同步的算法。
十三、有一个虚拟存储系统，一个程序共分为5 页，刚开始时数据区为空，其执行时页面走向为：4，3，2，1，4，3，5，4，3，2，1，5。
试给出下列情形下的缺页次数。
1、系统采用先进先出（FIFO）淘汰算法，存储块为3。
2、系统采用先进先出（FIFO）淘汰算法，存储块为4。
3 比较缺页次数，从中得到什么结论？。