精华1
威望50
K币65 元
注册时间2006-6-6
在线时间35 小时
最后登录2009-1-5
一般战友
- 精华
- 1
- 威望
- 50
- K币
- 65 元
- 注册时间
- 2006-6-6
|
北京理工大学
2006年攻读硕士学位研究生入学考试试题
计算机组织与结构部分
一、 单项选择题（10分，每题1分）
1.下列不同进位计数制的数中，最大的是（ ）
A.(0，101) B.(0,62) C.(0,52) D.(0,75)
2.在浮点数机中，判断补码规格化形式的原则是（ ）
A.尾数的第一位数1，数符任意 B.尾数的符号位与第一位数相同
C.尾数的符号位与第一位数不同 D.阶位与数符不同
3.设在数据舍己传送中采用偶校验，若接收到代码为10111011则表明在传送中（ ）
A.未出现错误 B.最低位出错
C.未出现错误或出现偶数位错 D.出现奇数位借
4.要想使8位寄存器A中的高4位变为0，低4位不变，可使用（ ）
A.上A v FOH -> A B.A ^ OFH -> A
C.A ^ FOH -> A D.A v OFH -> A
5.在加法器、寄存器的基础上增加部分控制电路实现乘除法时，用B寄存器存放（ ），这两个操作数的共同特点是在乘除运算过程中保持不变。
A.被乘数和被除数 B.被乘数和除数
C.乘数和被除数 D.乘数和除数
6.指令（ ）从主存中读出。
A.总是根据程序计数器PC B.有时根据PC，有时根据转移指令
C.根据地址寄存器 D.有时根据PC，有时根据地址寄存器
7.在中断周期中，由（ ）将允许中断触发器置0
A.关中断指令 B.中断隐指令 C.开中断指令 D.清0指令
8.以下四个步骤在通道工作过程中的正确顺序是（ ）
1）组织I/O操作 2）向CPU发中断请求
3）编制通道程序 4）启动I/0通道
A.1234 B.2314 C.4321 D.3412
9.RISC思想主要基于的是（ ）
A.减少指令的平均执行周期数 B.减少指令的复杂程度
C.减少硬件的复杂程度 D.便于编译器编写
10.指令优化编码方法，就编码的效率来讲，最好的方法是（ ）
A.固定长度编码 B.扩展编码法
C.huffman编码法 D.以上编码都不是
二、填空题（10分，每空1分）
1.浮点数为M 2 ，浮点加减运算首先要对阶，当 时，_____每右移一位，____加1。
2.寄存器寻址时，操作数在____中，寄存器间接寻址时，操作数在____中。
3.对于自顶向下生长的软堆栈，若栈指针总是指向栈顶满单元，出栈操作时，先____后____.
4.存储体系的主存—磁盘层次是为了弥补____，而cache--主存层次是为了弥补____.
5.超标量流水线采用的是____并行性，超流水线采用的是____并行性。
三、问答题（14分，每题7分）
1.什么是数据寻址和指令寻址？简述他们的区别。
2某流水线如下图所示，指出哪个是流水线的“瓶颈”段。简述解决流水线瓶颈的方法，并画出示意图。
S1 ----S2 ----S3 ----S4-----
T1=t T1=t T1=3t T1=t
四、（9分）设浮点数字长32位，其中阶码部分8位（含1位阶符），尾数部分24位（含1位数符），当阶码的基值分别是2和16时：
（1）说明基值2和16在浮点数中如何表示；
（2）当阶码和尾数均用补码表示，且尾数采用规格化形式时，给出两种情况下所能表示的最大正数真值和非零最小正数真值；
（3）在哪种基值情况下，数的表示范围最大?
(4)两种基值情况下，对阶和规格化操作有何不同？
五、（6分）设相对寻址的转移指令占三个字节，第一个字节是操作码，第二个字节是相对位移量（补码表示）的低8位，第三个字节是相对位移量（补码表示）的高8位，每当CPU从存储器取一个字节时，便自动完成（PC）+1—PC:
（1）若PC当前值为256（十进制），要求转移到290（十进制），则转移指令第二、三字节的机器代码是什么（十六进制）？
（2）若PC当前值为128（十进制），要求转移到110（十进制），则转移指令第二、三字节的机器代码又是什么（十六进制）？
六、（8分）某机采用微程序控制方式，水平型编码控制的微指令格式，断定方式。共有微命令30个，构成4个互斥类，各包含5个、8个、14个和3个微命令，外部条件共3个。
（1）若采用字段直接编码方式和直接控制方式，微指令的操作控制字段各取几位？
（2）假设微指令字长为24位，设计出微指令的具体格式。
（3）在（2）的情况下，控制存储器允许的最大容量为多少？
七、（10分）某计算机系统的CPU有20条地址线（A19~A0），8条数据线（D7~D0）和一条控制线（WE）,主存按字节编址，由16KB的ROM和64KB的RAM组成。拟采用8K*4的ROM芯片2片（编号1、2），8K*8的ROM芯片1片（编号3号），32K*2的RAM芯片4片（编号4~7号），32*8的RAM芯片1片（编号8号）。
1、2号芯片的地址范围为：18000H~19FFFH
3号芯片的地址范围为：F8000H~F9FFFH
4~7号芯片的地址范围为：98000H~9FFFFH
8号芯片的地址范围为：B8000H~BFFFFH
给出芯片|芯片组的片选逻辑，并画出CPU与各存储芯片的连接图。
八、（8分）假定磁盘传输数据以32位的字节为单位，传输速率为1MB/s，CPU的时钟频率为50MHz
（1）程序查询的输入输出方式，一个查询操作需要100个时钟周期，求CPU为1/0查询所花费的时间比率，假定进行足够的查询以避免数据丢失。
（2）用中断方式进行控制，每次传输的开销（包括中断处理）为100个时钟周期，求CPU为传输磁盘数据花费的时间比率。
（3）采用DMA控制进行输入输出操作，假定DMA的启动操作需要1000个时钟周期，DMA完成时处理中断需要500个时钟周期，如果平均传输的数据长度为4KB，问在磁盘工作时处理器将用多少时间比率进行输入输出操作，忽略DMA申请使用总线的影响
（4）根据以上计算，可以的出什么结论？
数据结构部分（75分）
九、单项选择题（每小题1分，共10分）
1、在数据结构中，数据的最小单位是（）
A.数据元素 B.字节 C.数据项 D.结点
2、数据元素之间的关系称为（）
A. 操作 B.结构 C.数据对象 D.数据集合
3、若经常需要在线性表的尾部插入数据，应采用的存储结构是（）
A. 顺序存储结构 B.链式存储结构 C.两种都合适 D.两种都不合适
4.在一个单链表中，已知指针p指向其中的某个结点，若在该节点前插入一个由指针s指向的结点，则需执行（）
A. s-﹥next = p-﹥next; p-﹥next = s B. p-﹥next=s; s-﹥next = p
C. s=p-﹥next, p-﹥next=s; s-﹥next=r; D.仅靠已知条件无法实现
5.静态链表与动态链表相比，其缺点是（）
A.插入删除时需移动较多的数据 B.有可能浪费较多的存储空间
C.不能随机存取 D.以上都不是
6.下列更合适表示队列的链表结构是（）
A．单向链表 B.单向循环链表 C.双向链表 D.双向循环链表
7.若L表示单项表的头指针，正确的表示是（）
A.ElemType L B.Elemtype *L C.Linklist *L D.Linklist L
8.设广义表L=（a,b,（）），则Getail（Getail（L））的结果是（）
A.(()) B.() C.(b,()) D.都不是
9.若用一堆数组表示一个深度为5，结点个数10的二叉数，数组的长度至少为（）
A.10 B.16 C.31 D.64
10.下面不能唯一确定一棵二叉树的两个遍历序列是（）
A.先序序列和中序序列 B.先序序列和后序序列
C.后序序列和中序序列 D.都不能
十、填空题（每空1分，共10分）
1.在一个单链表中，删除p所指结点的后继结点，需执行的语句序列如下：
_______;p-﹥next=q-﹥next;__________;
2. 在长度为n线性表中插入一个元素，采用顺序存储结构的复杂度为____;采用链式存储结构的复杂度为______.
3.在数的孩子兄弟表示法中，二叉链表的左指针指向_____,右指针指向¬¬¬______.
4.在图的数据结构中，顶点表示_____,边表示______.
5.在堆排序中，首先需要进行的操作是______.
6.在哈希造表中，不同的关键字产生同一哈希地址的现象，称为_____.
十一、简答题（每小题5分，共30分）
1. 在线性表和栈的顺序存储结构中，可以用realloc动态增加存储空间，问此方法不适合用于循环序列？
2. 请简要说明下列函数的主要功能。
Void func(Linklist L1, LinkList L2)
{ LNode *p, *q, *r;
q = L2-﹥next;
while (q) {
p = L1
while (p-﹥next) {
if (p-﹥next-﹥date == q-﹥date) {
r = p-﹥next;
p-﹥next = r-﹥next;
free(r);
}
P = p-﹥next;
}
q = q-﹥next;
}
Return;
}
3. 若有一个一堆数组A，它的元素下标从1开始到MAX。要在数组A中建立两个栈共享同一个空间，栈S1的栈顶指针为top1,栈S2的栈顶指针为top2,为了最大限度利用数组A的空间，则应该如何共享？栈满和栈空的条件是什么？
4. 在下列算法中，FindPath(Graph G, int v, int s, List &PATH)是求图中G中顶点v到s的一条路径PATH（用线性表示的一个顶点序列），请在空白处填入合适的语句或表达式。
提示：在此算法中，图的顶点均用顶点的编号表示。
Status FindPath (Graph G, int v,List &PATH )
{
Visited[v] = TRUE; //标示第v 个顶点已被访问
ListInsert(PATH,ListLength(PATH)+1,v);
If ( v -- a)
Return TRUE;
For(w = FirstAdjVex(G, v);w !=-1; w =NextAdjVex(G,v,w))
If (______)
If (FindPath(G, w, s, PATH)) return TRUE;
ListDelete(PATH,__________,e);
Return FALSE;
}
5. 当B-树作为文件的索引时，一个结点除了包含关键字和指向孩子结点的指针外，还包含指向文件记录的指针。假设一个结点占用的最大空间被限定为4096字节，每个关键字和每个指针都占2各字节，如果采用n阶B树作为文件的索引，则它的最大的阶数应该是多少？
6. 采用希尔排序法，对以下关键字序列按递增次序排序，使用的增量序列为5、3、1，请给出每趟排序的结果。 （8，6，3，4，2，9，7，5，1，0）
十二、算法设计（共25分）
1. 利用线性表的基本操作实现函数InsertInOrder(List&L, ElemType e),其功能是在非递减有序表L中插入数据元素e，插入后保持L仍是非递减有序。假设：
● LocateElem (List L,ElemType e, compare() ) 是在线性表L中查找第一个与e满足关系compare()的数据元素的位序。若元素不存在，返回值为0.
● Status ListInsert (List &L,ElemType)是在线性表L中第i位之前插入新的数据元素e,L的长度加1.
● ListLength (L)是返回线性表L中元素的个数。
● Status Greater (ElemType e1,ElemType e2)是比较两个数据元素的函数，当e1﹥e2时，返回值为真。
2. 在二叉链表的每个结点中添加一个域int depth,表示以该结点为根的子树的深度，即：
Typedef structBiTNode{ //结点结构
TElemType date;
Struct BiTNode *lchild,*rchild; //左右孩子指针
Int depth; //以该结点为根的子树的深度
}BiTNode,*BiTree;
a. 试编写一递归函数BiTreeDepth(BiTree T ),计算二叉树T 中每个结点的depth值，函数的返回值为树T的深度。
b. 在a 的基础上（即已求出二叉树中每个结点的depth值），编写一递归函数B iTreeBalance(BiTreeT),判断二叉序列树T是否为平衡二叉树，如果是平衡二叉树，则函数的返回值为真。
北京理工大学2003年攻读硕士研究生入学考试试题
计算机原理部分
一、 单项选择题（每小题1分共10分）
1.1 假定下列字符码中有奇偶检验位，但没有数据错误，采用奇检验的字符码是_______.
A.11001010 B.11010111 C.11001100 D.11001011
1.2 汉字“灯”的十进制区位码为“21-38”,它的十六进制国际码为______.
A.4158H B.C1D8H C.3546H D.B5C6H
1.3 执行一条一地址的加法指令共需要______此访问主存。
A.1 B.2 C.3 D.4
1.4 设相对寻址的转移指令占两个字节，第一个字节是操作码，第二个字解释相对位移量（用补码表示），每当CPU从存储器取出第一个字节时，即自动完成（PC）-1→PC,若当前PC的内容为3008H，要求转移到3000H,则还转移指令第二字节的内容应为¬_______.
A.08H B.09H C.F7H D.F6H
1.5 RISC的含义是_____.
A.Reduced instruction set computer B.Reproduced instruction set computer
C.Reduced instruction system computer D.Reproduced instruction system computer
1.6 字长为16位的两级先行进位加法器，若不考虑G 、P 的形成时间，从C →C 共需要_____时间。
A.2ty B.4ty C.6ty D.8ty
1.7 EPROM 是指¬¬______.
A.只读存储器 B.可编程的只读存储器 C.可擦除可编程的只读存储器 D.电可改写只读存储器
1.8 下列说法中_____是正确的。
A.指令周期等于机器周期 B.指令周期大于机器周期
C.指令周期时机器周期的两倍 D.两者之间无确定关系
1.9 一台显示器的图形分辨率为1024×768，要求显示256种颜色，显示存储器VRAM的容量至少为______.
A.512KB B.1MB C.3MB D.4MB
10 在DMA传送方式中，由_____发出总线请求。
A.外部设备 B.DMA控制器 C.CPU D.主存
二、（5分）在整数定点机中，机器数字长为8位（含1位符号位），当X=-0时，请分别写出其对应的二进制真值、原码、补码、反码和移码。
三、（7分）子程序调用指令和返回指令分别用在什么场合？试说明，如果返回地址被保存在堆栈中或被保存在子程序的第一个单元中这两种情况下，子程序调用指令和返回指令有无区别？如有区别，请指出区别之处。
四、（8分）设CPU共有16根地址线，8根数据线，并用 做访存控制信号（低电平有效），用 作为读写控制信号（高电平为读，低电平为写），现有下列芯片：1K×4位RAM,4K×8位RAM,2K×8位ROM，以及3-8译码器或其他门电路。主存地址空间分配：A000H～A7FFH为系统程序：A800H～AFFFH为用户程序区。要求：（1）合理选用上述芯片，说明各选几片？（2）画出CPU与存储芯片的连接图。
五、（10分）设有8条微指令，每条微指令所含的微命令控制信号如下所示：
微命令信号
微指令 a b c d e f g h i j k
I1 √ √ √ √
I2 √ √ √
I3 √ √ √
I4 √ √
I5 √ √ √ √
I6 √ √ √ √
I7 √ √ √
I8 √ √ √ √
(1) 微命令b与哪些为微命令兼容？与哪些微命令互斥？
（2）设计微命令的操作控制字段格式，要求所使用的控制位最少，而且要保持微命令本身内在的并行性。
六(10分)
(1)设某机配有A、B、C三台设备，其中断优先次序（响应次序）是A→B→C,为改变中断处理次序，将它们的中断级屏蔽字分别设置如下（“0”对应于开放，“1”对用于屏蔽），其中断处理次序是什么？
中断服务程序级别 中断屏蔽字
1 2 3
A
B
C 1
0
0 1
1
1 1
0
1
（2）设A、B、C的中断服务程序的执行时间均为20μs，在A设备发出请求后30μs时，B设备发出请求：40μs时，C设备发出请求，试画出CPU执行程序的轨迹。
操作系统部分
七、单项选择题（14分）
7.1 设计操作系统的时候需要关心许多方面的问题，其中不需要关心的是______
A. 计算机的裸机特性 B.操作系统今后的应用目标
C.计算机系统所具有的资源 D.高级程序设计语言的编译器
7.2 多道程序运行的特点之一就是宏观上并行，它的含义是 _______
A.多道程序交叉使用CPU，它的执行在时间上是重叠的
B.多道程序交叉使用内存，同一时刻内存中保存有多道程序
C.多道程序同时使用计算机系统中的各种资源
D.同一个程序可以有多个进程同时运行
7.3 纯代码的含义是______
A.一种允许多个进程同时访问的代码 B.一种同时只允许一个进程访问的代码
C.一种只包含运行程序的正文代码段而不包含数据段的代码
D.是用汇编语言编写出的程序
7.4 分时系统的一个重要性是系统的响应时间，对操作系统_____因素进行改进有利于改善系统的响应时间。
A.加大时间片 B.采用静态页式管理 C.优先级-非抢占式调度算法 D.代码可重入
7.5 批处理系统的主要缺点是_____
A.CPU利用率低 B.不能并发进行 C.缺少交互性 D.需要大量内存
7.6 在多进程系统中，为保证公共变量的完整性，各进程应互斥进入临界区，所谓的临界区是指_____.
A.一个缓冲区 B.一段数据区 C.一种同步机制 D.一段程序
7.7 若信号量S的初值为2，当前值为-3，则表示有_____等待进程。
A.1个 B.2个 C.3个 D.5个
7.8 产生死锁的根本原因是______
A.资源共享 B.并发执行的进程太多 C.进程推进顺序非法 D.以上三个原因都是
7.9 在一个操作系统中对内存采用页式存储管理方法，则所划分的页面大小_____
A.要依据内存大小而定 B.必须相同
C.要依据CPU的地址结构 D.要依据内存和外存而定
7.10 建立文件系统的主要目的是 ______
A.文件虚存储 B.实现文件的按名存取
C.提高外存的读写速度 D.将内存外存统一管理
7.11 虚拟设备是______
A.利用共享设备的一部分空间扩展原有的共享设备的使用范围，或为更多用户可以共享的一种I/O技术
B.利用共享设备的一部分空间将原为独享的设备改造成为多个用户可以共享的一种I/O技术
C.充分利用现有设备的功能，通过操作系统的软件扩展，增加了原有设备的功能，使之成为一种新的I/O设备
D.以上三个答案全是错误的
7.12 如果系统进行I/O操作所花费的时间比CPU处理时间短得多，则缓冲区_____.
A.使用效率最高 B.几乎无效
C.使用效率比较均衡 D .无法推断上述结论之一
7.13 产生内存抖动主要原因是______
A.内存空间太小 B.CPU运行速度太慢
C.CPU调度算法不合理 D.页面置换算法不合理
7.14 在关于SPOOLING的叙述中，错误的是______
A.SPOOLING系统中不需要独占设备
B.SPOOLING系统可以加快作业的执行速度
C.SPOOLING系统使独占设备变成了共享设备
D.SPOOLING利用了处理器与通道并行工作的能力
八、填空题（每空1分，共6分）
8.1 进程的3种基本状态是：运行态、_______和_______
8.2 有三种磁盘调度算法，它们的名称是：先来先服务调度（FCFS），_____和_____
8.3 UNIX系统中系统进程之间有4种通信方式，它们的名称是：管道（pipe）、消息缓冲机制、_________和__________
九、简答题（每小题7分，共21分）
9.1 页式虚拟存储管理中，执行指令发生缺页中断之后，系统怎样进行处理的？
9.2 为什么现在的操作系统中要引入特殊文件的概念？常见的特殊文件分为哪些类？
9.3 中心的机房有200台机器，实行按上机时间收费的制度，学生申请上机时如果有空的机器，就可以登记上机，如果没有空的机器，只能排队等候，学生上机的时候首先要在机房公用的1本上机记录本上进行登记，记录所使用的机器号码和上机开始时间之后才能上机。学生下机的时候，要在记录本上找到自己使用的机器，登记下机时间之后，其它学生才能登记使用这台机器，请给出学生上机和下机过程的算法描述。
十、应用题（9分）
要使用一台PC机进行生产过程的实时控制。要求整个系统在硬件配上8通路的AD/DA转换卡进行实时信号采集和控制，8个数据通路中，有2个是快速数据通路，可以处理时间要求比较高的数据。6个是一般的数据通道，整个机器配置1M内存，64M闪存（flash memory）作为外存（在这个系统中闪存的作用等同于一个一般的硬盘），只是在容量上相对小一点），整个系统加电后可以通过闪存直接启动。
如果系统要求的最短的数据采集周期1微秒：对于2个快速数据通路的数据要进行优先处理，对6个低速通路可以稍微滞后处理：系统对采集的数据进行电但处理后一方面要在屏幕上现实数据，另一方面要将原始数据存入内存中。
假设今后的应用系统有不超过8个数据采集或控制任务：有不超过16个相对不太紧急的计算处理任务，整个系统只有1个公用的后台数据保存任务和1个公用的数据显示任务。以上每个任务占用的内存不会超过64KB，整个系统的所有占用内存的总和不会超过512KB。
请按照以上应用系统的要求设计一个实时操作系统。请简要说明你所设计的实时操作系统都包括哪些模块？根据本应用的要求，给出每个模块所选择的主要算法？
数据结构部分
十一、单项选择题（10分）
11.1 下列数据结构中，______属于顺序访问的线性群体。
A.哈希表 B.表 C.数组 D.堆
11.2 折半查找算法的复杂度为_______
A.O B.O C.O D.O
11.3 如图所示的二叉树的中序序列是_______
A.V6 V3 V5 V1 V4 V7 V2 B.V1 V3 V6 V5 V2 V4 V7
C.V6 V5 V3 V7 V4 V2 V1 D.V1 V2 V3 V4 V5 V6 V7
11.4 在有理数类Rational中，实现实数转换为有理数的函数是______.
A.Rational(double x) B.operator double(void)const
C.Rational(long num,long denom) D.operator double(Rational r)const
11.5 在安全数组类中，重载的下标运算符“[]”返回的是______.
A.数组元素值 B.数组元素引用 C.数组元素指针 D.数组元素下标
11.6 在整型集合类Set中，数组成员setrange表示的是_______.
A.集合中元素的个数 B.位数组的字节数
C.集合中元素的个数的最大值 D.位数组字节数的最大值
11.7 包含77个结点的二叉树的最小深度是______.
A.3 B.4 C.5 D.6
11.8 在后缀表达式求值算法中，需要用______个栈。
A.0 B.1 C.2 D.3
11.9 若需要从1000个数中选出最小的10个数，_____ 算法最合适。
A.基数排序 B.归并排序 C.堆排序 D.快速排序
11.10 若有向图中任意两个结点之间有一条有向路径则称该有向图是_____
A.连通分量 B.强连通分量 C.弱连通图 D.强连通图
十二、填空题（10分）
12.1 我们把每种数据结构视为抽象类型，它不但定义了数据的_____方式，还给出了处理数据的_______.
12.2 数据结构的面向对象方法提供了对代码的______,即可将过去开发和测试过的代码“植入”新的应用中。
12.3 C-主要通过______和______来支持多态性。
12.4 数组的特点是可以_______访问数据元素。
12.5 在事件驱动银行模拟实例中，主要包括两种事件：______和_______.
12.6 在函数Push(const DataType&item)中，const的作用是_____.
12.7 在顺序表类Seqlist中，Find和Delete函数要求DataType上定义了____运算符。
十三、回答下列问题（每题4分，共16分）
13.1 用基数排序对下列序列排序：317、286、726、35、427、819、381，列出第二遍结束后表中内容。
13.2 请最多用两句话描述复制构造函数在处理带动态数据类中的作用。
13.3 在迭代算子类Iterator中，Reset和Next两个方法的作用是什么？
13.4 与竞赛排序相比，堆排序的主要优点是什么？
十四、算法题（14分）
14.1 （8分）InserSort(Node<T> & head)是一个利用插入排序算法对链表内容进行排序的函数，请在空缺处填入正确的内容。
Template<class T>
Viod InsertSort(Node<T> &head)
{
Node<T> newhead, oldhead;
Node<T> currPtr, prevPtr, tempPtr, newnode;
T item;
_________A___________
_________B___________
While(oldhead !=NULL)
}
prevPtr =NULL;
currPtr = newhead;
item = oldhead->NextNode();
tempPtr = oldhead;
oldhead = oldhead->NextNode();
delete tempPtr;
while(currPtr!=NULL)
{
If(item<currPtr->data>
Break;
prevPtr = currPtr;
currPtr = currPtr->NextNode();
{
If(prevPtr == NULL)
_____________C______________;
Else
}
Newnode = new Node<T>(item);
______________D______________;
}
}
Head = newhead;
}
14.2（6分）请编写一递归函数“viod Reverse(int a[],int s,int e)”,其功能是将数组a中从下标s开始到e结束的整数颠倒顺序，如：
执行前：a[] = {0,1,2,3,4,5,6} s=1 e=4
执行后：a[] = {0,4,3,2,1,5,6}
要求在该函数中不使用新的数组，没有循环。
注：本题可以使用C++ 或C语言编写。
北京理工大学2004年攻读硕士学位研究生入学考试
计算机原理部分
一、 单项选择题（每小题1分，共14分）
1. 计算机中表示地址时使用________.
A.无符号数 B.原码 C.反码 D.补码
2. 设浮点数的基数R=8，尾数用补码表示，则下列数_____为规格化的数。
A.1.111000 B.0.000111 C.1.101010 D.1.111101
3. ________方式对实现程序浮动提供了支持。
A.变址寻址 B.相对寻址 C.间接寻址 D.寄存器间接寻址
4. 在存储器堆栈中，保持不变的是_______.
A.栈顶 B.栈指针 C.栈底 D.栈中的数据
5. 组成一个运算器需要多少个部件，但下面所列_______不是组成运算器的部件。
A.状态寄存器 B.数据总线 C.ALU D.地址寄存器
6. ROM与RAM的主要区别是_______
A.断电后，ROM内的信息会丢失，RAM则可长期保存信息而不丢失
B.断电后，RAM内的信息会丢失，ROM则可长期保存信息而不丢失
C.ROM是辅助存储器，RAM是主存存储器
D.ROM是主存储器，RAM是辅助存储器
7. CPU组成中不包括_____.
A.指令寄存器 B.指令译码器 C.地址寄存器 D.地址译码器
8. 取指令操作______.
A.受到上一条指令的操作码控制 B.受到当前指令的操作码控制
C.受到下一条指令的操作码控制
D.是控制器固有的功能，不需要在操作码控制下进行
9. 在计算机中，存放微指令的控制存储器隶属于______.
A.辅助存储器 B.高速缓存 C.主存储器 D.CPU
10. 水平微指令与垂直微指令相比，_______.
A.前者一次只能完成一个操作 B.后者一次只能完成一个操作
C.两者都是一次只能完成一个操作 D.两者都能一次完成多个操作
11.磁盘存储器的等待时间通常是______.
A.磁盘旋转半周所需的时间 B.磁盘转2/3周所需的时间
C.磁盘转1/3周所需的时间 D.磁盘转一周所需的时间
12. 在采用_____对设备进行编址情况下，不需要专门的I/O指令组。
A.统一编址法 B.独立编址法 C.两者都是 D.两者都不是
13. 禁止中断的功能可以由_____来完成。
A. 中断触发器 B.中断允许触发器 C.中断屏蔽触发器 D.中断禁止触发器
14. I/O接口中数据缓冲器的作用是_____.
A.用来暂存外设和CPU之间传送的数据 B.用来暂存外设的状态
C.用来暂存CPU发出的命令 D.以上全部
二、（8分）某机指令格式如下:
15 10 9 8 7 0
OP MOD A
上图中OP表示操作码，MOD表示寻址方式，A表示形式地址，且MOD=0,直接寻址；MOD=1,变址寻址；MOD=2，相对寻址；MOD=3当前页面寻址。
设（PC）=1234H,(Rx)=113CH,请确定下列指令的有效地址（均用十六进制表示），要求写出中间过程。
（1）4C20H (2)2244H (3)3547H (4)6F23H
三、写出十进制数0～9的2421码（有权、自补码），指出一位2421码加法器的校正关系，写出逻辑表达式。
四、（8分）
主存储器的地址寄存器和数据寄存器各自的作用是什么？设有一个1MB容量的存储器，字长为32位，问：
（1） 按字节编址，地址寄存器、数据寄存器各为几位？编址范围为多大？
（2） 按字编址，地址寄存器、数据寄存器各为几位？编址范围为多大？
注：编址范围即存储器的最低地址和最高地址，用十六进制表示。
五、问答题（每小题6分，共12分）
1.浮点数的阶码通常用补码或移码表示，试分析这两种编码有何区别，哪一种更好，为什么？
2.主机与外设间的信息交换方式有很多种，哪一种方式适用于对高速外设进行数据传送？试写出外设进行操作的过程。
操作系统部分
六、判断题（正确打√，错误打×）
1.当作业对应的进程阻塞时，改作业处于等待状态。（ ）
2.打开文件的功能就是将文件复制到主存。（ ）
3.Windows操作系统完全继承了分时系统的特点。（ ）
4.在一个有N个进程的单处理机系统中，有可能出现N个进程都被阻塞的情况（ ）
5.所谓程序局部性原理是在进程的整个运行过程中，只访问一小段程序。（ ）
七、填空题（15分）
1.UNIX系统将通常的目录项划分成（ ）和（ ）两部分后，这无疑大大提高了（ ）。
2.实时操作系统与分时操作系统的主要区别是（ ）和（ ）。
3.在虚存管理系统中，虚拟地址空间是指程序的逻辑地址空间，实地址空间是指（ ），前者的大小受（ ）限制，后者的大小受（ ）限制。
4.常用的I/O传输控制方法有程序查询方法、程序中断方法、（ ）和（ ）。
5.访问磁盘一个数据块的时间由三部分组成，即（ ）、（ ）和数据传输时间。
6.索引文件在文件存储器中存放时，大体上由（ ）区和（ ）区构成，其中（ ）区一般按关键字的顺序存放的。
八、选择题（10分）
1.UNIX的文件系统采用（ ）结构存储文件信息的各个记录的。
A.链接结构 B.单级索引 C.多重索引 D.链接和索引相结合
2.若把操作系统看成计算机系统资源的管理者，下面的（ ）不属于操作系统所管理的资源。
A.程序 B.主存 C.CPU D.中断
3.资源的有序分配策略可以破坏死锁的（ ）条件。
A.互斥 B.请求和保持 C.不剥夺 D.循环等待
4.（ ）是操作系统中采用的以空间换取时间的技术。
A.SPOOLING技术 B.虚拟存储技术 C.覆盖与交换技术 D.通道技术
5.设主存的分配情况如图所示，当有一个进程需申请45K字节的存储区时，若采用最佳适应法，则所分到的分区首地址为（ ）。
A.100K B.190K C.330K D.410K
占用 占用 占用 占用
0 100k 180k 190k 280k 330k 390k 410k 512k-1
6.在页式存储管理中，页表内容如图所示，若页的大小为4K，则地址转换机构将逻辑地址12293转换成的物理地址为（ ）。
A.20485 B.32773 C.24581 D.12293
2 5 6 8 3 11
7. 如果文件采用直接存取方法使用，且文件大小不固定，则采用（ ）物理结构。
A.直接 B.索引 C.随机 D.顺序
8.UNIX系统中，（ ）用于把一个进程的输出连接到另一个进程的输入。
A.普通文件 B.索引文件 C.目录文件 D.管道文件
9. 既考虑作业的执行时间又考虑作业的等待时间的调度算法是（ ）。
A.短作业优先 B.先来先服务 C. 响应比高者优先 D.优先级调度
10.一个可共享的程序在执行过程中是不能被修改的，这样的程序代码应该是（ ）。
A.封闭的代码 B.可重入码 C.可再现码 D.可执行码
九、简答题（下面的第1和第2两题择一，第3题必做）（10分）
1.在请求页式管理系统中，需要几个数据结构，各包括几个字段及作用，试用实现一个不在主存的操作时的地址转换过程给以叙述。（5分）
2.打开一个UNIX系统的文件，需要几个数据结构，这几个结构之间如何建立联系的？试用一个打开文件命令给以叙述。（5分）
3.计算机系统是如何保护操作系统不受破坏，各用户程序之间也相互不被破坏的？（5分）
十、应用题（10分）
1.为了使公共汽车正常行驶，司机与售票员之间需要很好同步。在汽车不断地到站、停车、行驶过程中，叙述两者各自有些什么活动？哪些活动需要同步？并用信号量和PV操作描述两者之间的同步过程。（6分）
2.在请求页式存储管理系统中，页的大小为128个字节。有一个64*64的整形数组，系统进行存储，每个整数占用两个字节，若系统为它分配一个主存块来存放数据，且程序已经驻留在主存。试问实现为该数据清零操作时，可能产生多少次缺页中断。程序的代码编写如下。（4分）
int a[64][64];
int I.j;
for(I=0;I<=63;I++)
for(j=0;j<=63;j++)
A[I][j]=0;
数据结构部分
十一、单项选择题（每小题1分，共10分）
1. 在数据结构中，与所使用计算机无关的是数据的_______.
A.存储结构 B.逻辑和物理结构 C.逻辑结构 D.物理结构
2. 在对算法的时间复杂度进行估计的时候，下列最佳的时间复杂度是_____。
A. n B. nlogn C. n D. logn
3. 若线性表最常用的操作是存取第i个元素及前驱和后继元素的值，为节省时间应采用的存储方式是_______.
A.单链表 B.双向链表 C.单循环链表 D.顺序表
4.在表达式的算符优先求值算法中，从栈顶到栈底运算符栈中的运算符优先级是_____.
A.从高到低 B.从低到高 C.无序 D.无序有序均可以
5.若用一个大小为6的数组来实现循环队列，且当前rear和front的值分别为0和3，当从队列中删除一个元素，再加入两个元素后，rear和front的值分别为_______.
A.1和5 B.2和4 C.4和2 D.5和1
6.设m,n为一棵二叉树上的两个结点，在中序遍历时，n在m前的条件________.
A. n在m左方 B. n是m祖先 C. n在m右方 D. n是m子孙
7. 判断一个有向图是否有环（回路）的方法是_________.
A.求结点的度 B.拓扑排序 C.求关键路径 D.求最短路径
8. 在有向图的邻接表存储结构中，顶点v在连接表中出现的次数是________.
A.顶点的v的度 B.顶点v的出度 C.顶点v的入度 D.依附于顶点v的边数
9. 用邻接表表示图时，某个顶点个数为n，边的条数为e，在邻接表上执行有关图的遍历操作时，时间的代价是________.
A.O(n) B.O(n+e) C.O(n*e) D.O(max(n,e))
10.对下图所示的有向图，从顶点v0出发的深度优先序列是_______.
A.V0 V1 V2 V4 V6 V3 V5 B.V0 V1 V4 V6 V2 V5 V3
C.V0 V2 V5 V6 V1 V3 V4 D.V0 V1 V2 V3 V4 V5 V6
十二、填空题（每空1分，共10分）
1. 先序线索二叉树中的任意结点x，若x有左子树，则x的后继为x的______链所指的结点，否则为x的______链或_______线索所指的结点。
2. 深度为6的平衡二叉树最少应该_______结点。
3. 对于边稀疏的图，求解其最小生成树应该选用______算法。
4. 有n个顶点的无向连通图至少有_____条边，有n个顶点的有向连通图至少有_____条边说明。
5. 用邻接矩阵表示无向图时，若图中有100个顶点，100条边，则该矩阵有_____元素，有_______非零元素。
6. 从任一结点出发到根的路径上所经过的结点序列按其关键字有序，满足这样性质的二叉树是________.
十三、简答题（每小题5分，共15分）】
1. 请画出下列二叉排序树中依次删除节点50和60之后的二叉排序树
2. 请在下面m=3的B树中依次插入90和30，请画出B树的变化过程。
3. 对以下序列（7，3，1，10，2，4，5，8，9，6，11）按照升序进行排序，请写出一趟快速排序的过程及结果。
十四、算法设计（共15分）
1. 设用二叉链表存贮二叉树，结点的结构如下：
typedef struct BiTNode
{ ElemType data;
Struct BiTNode * lichild, *rchild;
}BiTNode,*BiTree;
试编写判断两棵二叉树是否相等的算法，函数结构如下：
Status equal(BiTree T1,BiTree T2)
{// 本算法判断两棵二叉树是否相等，若想等返回1，否则返回0；
………
}
请在equal函数中设计适当的算法，填写适当的语句完成规定的功能。请写明算法的基本思路，并在算法的主要步骤上加注释。
2. 对表达式可以采用前缀表示法，例如表达式：8+3*（2-7）-4/2,采用前缀表示法可以表示为：- + 8 * 3 -27 / 42.
假设表达式中包含的运算符号只有+、-、*和/.表达式中包含的操作数均是单个的数字形式（0～9）。
假设系统已经提供了两个现成的函数：two_result 和is_operator.
函数two_result 的基本功能如下：
Int two_result(char operator,int operand1,int operand2)
{ // 根据运算符operator,取operand1和operand2的值进行计算 //返回结果。
Return (operand1 operator operand2 );
}
函数is_operator 的基本功能如下：
int is_operator(char operator)
{ // 若operator是运算符，则return 1
// 否则，return 0
}
请使用类C语言（或伪语言）设计一个函数expression,计算一个前缀表达式的值。
int expression(char*string)
{ // string 指向一个前缀表达式，函数的返回值为前缀表达式的计算结果
………
}
请在expression 函数中设计适当的算法，填写适当的语句完成规定的功能，请写明算法的基本思路，并在算法的主要步骤上加注释。
2005年攻读硕士研究生入学统一考试
计算机原理部分（50分）
一、 单项选择题（每小题1分，共14分）
1. 8位原码能表示的不同数据有_______个。
A.15 B.16 C.255 D.256
2. 某数在计算机中用余3码表示为0111 1000 1001，其真值为_______。
A.456 B.456H C.789 D.789H
3. 一个计算机系统采用32位单字长指令，地址码为12位，如果定义了250条第二地址指令，那么还可以有______条单地址指令。
A.4K B.8K C.16K D.24K
4. 某计算机字长32位，其存储容量为4MB，若按字编址，它的寻址范围是________.
A.1M B.4MB C.4M D.1MB
5. 在统一编址方式下，存储单元和I/O设备是靠______来区分的。
A.不同的地址码 B.不同的地址线 C.不同的控制线 D.不同的数据线
6. 对于二进制数，若小数点左移一位，或小数点右移一位，则数值分别_____。
A.扩大一倍，扩大一倍 B.扩大一倍，缩小一倍
C.缩小一倍，扩大一倍 D.缩小一倍，缩小一倍
7. 在1K×8的存储器芯片中，采用双译码方式，译码器的输出信号有______条。
A.1024 B.64 C.32 D.10
8. 在字节编址的计算机中，一条指令长16位，当前指令地址为3000，在读取这条指令后，PC的值为_______。
A.3000 B.3001 C.3002 D.3016
9. 累加器中______。
A.没有加法器功能，也没有寄存器功能
B.没有加法器功能，有寄存器功能
C.有加法器功能，没有寄存器功能
D.有加法器功能，也有寄存器功能
10. 同步控制是______。
A.只适用于CPU控制的方式 B.只适用于外围设备控制的方式
C.有统一时序信号控制的方式 D.所有指令执行的时间都相同的方式
11.在采用断定方式的微指令中，下一条微指令的地址______.
A.在微指令计数器中 B.在程序计数器PC中
C.根据条件码产生 D.在当前的微指令中
12. 磁盘读写信息的最小单位是_____。
A.位 B.字节 C.扇区 D.磁道
13. 计算机所配置的显示器中，若显示控制卡上刷新存储器的容量1MB，则当采用800×600分辨模式时，每个像素最多可以有_____种不同颜色。
A.256 B.65536 C.16M D.4096
14. 在DMA方式传送数据的过程中，由于没有破坏_____的内容，所以CPU可以照常工作（访存除外）。
A.程序计数器 B.程序计数器和寄存器
C.指令寄存器 D.非以上答案
二、（8分）下图是某存储芯片的引脚图，请回答：
（1）这个存储芯片的类型（是RAM还是ROM）?这个存储芯片的容量？
（2）若地址线增加一根，存储芯片的容量将变为多少？
（3）这个芯片是否需要刷新？为什么？刷新和重写有什么区别。
（4）如果需要刷新，请指出芯片刷新一遍需要的时间（设存取周期为0.5μs）及你准备选择的刷新方式，需说明理由。
注：NC表示未用
三、（8分）利用74181（4位ALU）和74182（先行进位）芯片设计如下3种方案的32位ALU（指出需要的芯片数，画出简单连接图）。
（1）行波进位方案 （2）二级先行进位方案 （3）三级先行进位方案
同时写出二级先行进位方案中进位信号C 的逻辑表达式。
四、（8分）已知某运算器的基本结构如下图所示，它具有+、-、M（传送）3种操作。
（1）写出图中1～12表示的运算器操作的微命令。
（2）指出互斥性微命令。
（3）设计适合此运算器的微指令格式（只要求写出操作控制字段）。
（4）设某条机器指令的功能为计算：R1-2×R2→R3。试设计这条机器指令的微程序（不考虑取指微指令，要求微指令数最少），并将其代码化。
五、问答题（每小题6分，共12分）
1.常见的寻址方式有哪几种？其中寻找操作数速度最快的是哪一种？速度最慢的又是哪一种？若要进行主存中数据块的移动，可以选用哪两种寻址方式?它们各有什么特点？
2.试比较程序中断方式和I/O通道控制方式的特点。
操作系统部分（50分）
六、判断题（正确打√，错误打×）（8分）
1.在现代操作系统中，作业拥有的最大编址空间受CPU的地址结构和外存容量的限制。（ ）。
2.在批处理系统中，提交的批处理作业必须具有作业的控制信息。（ ）
3.并发执行的进程间必定具有相互制约关系。（ ）
4.处理机处于核心态时，只能执行特权指令。（ ）
5.采用虚拟存储技术后，内存就可以无限制地进行扩充。（ ）
6.共享设备是指在同一时刻内，允许多进程同时访问的设备。（ ）
7.存储型设备通常是直接存取的设备，而I/O型设备属于顺序存取的设备。（ ）
8.文件的存取方法依赖于文件的物理结构和存放文件的存储设备的特性。（ ）
七、填空题（12分）
1.现代操作系统的两个最基本的特性是_____和______.
2.在操作系统中，一种用空间换时间的资源转换技术是______.
3.为了有效地管理请求页式虚存系统，OS面临三个基本问题，它们是_____、________和_________。
4.地址转换机构的最基本任务是将________中的______变换为_______中的____.在分页管理系统中，为实现地址转换设置了控制寄存器，其中存放的是_____和_________.
5.在UNIX系统中，进程的正文段的代码具有_______特点。为了保证正被共享的正文段不被换出，应设置一个_________。
6.硬盘属于块设备，信息的存取单位是以________为单位进行的；磁盘的I/O控制主要采用_______控制方式。
7.打开文件的功能是把________从外存复制到内存中，并建立______和________之间的联系。
8.在UNIX系统中，创建一个新文件时，应先分配一个________和_________，之后将________和________写入_________。
八、选择题（10分）
1.为了使并发进程有效地进行输入输出，应该采用______结构的缓冲技术。
A.双缓冲 B.环形缓冲 C.缓冲池 D.多队列轮换
2.在可变式分区管理中，采用拼凑技术的目的是_______。
A.合并空闲区 B.合并分配区 C.增加主存容量 D.便于地址转换
3.实施虚拟存储器管理的依据是程序的_______.
A.局部性原理 B.动态性原理 C.并发性原理 D.一致性
4.火车站的售票系统属于_______系统。
A.单道批处理 B.多道批处理 C.分时 D.实时
5.一个作业8：00到达系统，其估计运行时间为1小时。若10：00开始运行该作业，其响应时间是________.
A.1 B.2 C.3 D.4
6.采用可重入程序是通过使用_______方法来改善系统性能的。
A.改变时间片长短 B.改变用户数
C.加速对换速度 D。减少对换信息量
7.若为每个作业只建立一个进程，为了照顾短作业用户，应采用_____;为了照顾紧急作业用户，应采用_______;为能实现人机交互，应采用______;而能使短作业、长作业和交互作业用户都满意，应采用_____.
A.FCFS调度算法 B.短作业优先调度算法
C.时间片轮转法 D.多级反馈队列调度算法
8.在设计分时操作系统时，首先要考虑的是____；在设计实时操作系统时，首先要考虑的是_____；在设计批处理系统时，首先要考虑的是______.
A.灵活性和适应性 B.交互性和响应时间
C.周转时间和系统吞吐量 D.实时性和可靠性
九、简答题（12分）
1.虚拟设备的概念及实现虚拟设备的主要条件和实现技术是什么？
2.死锁与饿死有什么区别？
3.什么是交换？交换的目的是什么？
4.引入线程的目的是什么？线程与其所在进程之间的关系是什么？
十、应用题（8分）
请用信号量解决一下的“独木桥”问题：同一方向的行人可连续过桥，当某一方向有人过桥时，另一方向的行人必须等待，直到某方向无人过桥或连续过了100个人时，另一方向的行人才可以过桥。
数据结构部分（50分）
十一、单项选择题（每小题1分，共10分）
1. 数据结构中数据元素之间的逻辑关系被称为_______。
A.数据的存储结构 B.数据的基本操作
C.程序的算法 D.数据的逻辑结构
2. 在定义ADT时，除数组对象和数据关系外，还需说明_____。
A.数据元素 B.算法 C.基本操作 D.数据项
3. 在链式存储结构中，数据之间的关系是通过______体现的。
A.数据在内存的相对位置 B.指示数据元素的指针
C.数据的存储地址 D.指针
4. 计算算法的时间复杂度是属于一种______。
A.事前统计的方法 B.事前分析估算的方法
C.事后统计的方法 D.事后分析估算的方法
5. 若对n个元素进行堆排序，则在初始建堆的过程中需要进行_____筛选。
A.1 B.n/2 C.(n-1)/2 D.n
6. 向一个栈顶指针为h的带头结点链栈中插入指针s所指的结点时，应执行_______。
A.h→next=s B.s->next=h
C.s→next=h;h=h→next D.s→next=h→next;h→next=s;
7. 对于循环队列_______。
A.无法判断队列是否为空 B.无法判断队列是否为满
C.队列不可能满 D.以上说法都不是
8. 根据______可以唯一地确定一棵二叉树。
A.先序遍历和后序遍历 B.先序遍历和层次遍历
C.中序遍历和层次遍历 D.中序遍历和后序遍历
9. 若要从1000个元素中选出前10个最小的元素，______是最合适的算法。
A.直接插入排序 B.归并排序
D.堆排序 D.快速排序
10．排序算法的稳定性是指______。
A.经过排序之后，能使值相同的数据保持原顺序中的相对位置不变
B.经过排序之后，能使值相同的数据保持原顺序中的绝对位置不变
C.算法的排序性与被排序元素的数量关系不大
D.算法的排序性与被排序元素的数量关系密切
十二、填空题（每小题2分，共10分）
1. 在栈的ADT定义中，除初始化操作外，其他基本操作的初始条件都要求_______。
2. 带头结点的双向循环链表L为空表的条件是______。
3. 在按算符优先法求解表达式3-1+5*2时，最先执行的运算是______,最后执行的运算是¬¬¬________。
4. 对于m=4(4阶)的B-树，如果根的层次为第1层，则高度为2的B-树最少要存储_____个关键字，最多可以保存______个关键字。
5. 哈希表用_______确定记录的存储位置。
十三、问答题（每小题4分，共20分）
1. 已知下图为广义表的头尾链表存储结构图，请给出该图表示的广义表。
2. 递归算法与非递归算法比较有哪些主要的优点和缺点。
3. 判断下图是否为-Huffman树，若是，请给出“CATS;”的编码。
4.设图的邻接表的类型定义如下，若待权图中的权值类型为整型，请对该邻接表的类型定义做出适当修改，使之能够用于表示边带权的图。
#define MAX_VERTEX_NUM 20
typedef struct AreNode{
Int adjvex;
Struct AreNode *nextarc;
}AreNode;
typedef struct Vnode{
VertexType data;
AreNode *finrstrc;
}Vnode,AdjList[MAX_VERTEX_NUM];
typedef struct{
AdjList vexs;
int vexnum,arcnum;
}ALGraph;
5.从空的平衡二叉排序树开始，按以下顺序插入关键字，请给出最终的平衡二叉树。假设6个关键字的查找概率相等，求该树的平均查找长度。
27，31，49，38，41，67
十四、算法题（每小题5分，共10分）
1.已知p是指向单向循环链表最后一个结点的指针，试编写只包含一个循环的算法，将线性表（a ,a ,……,a ,a ）改造为（a ,a ,……,a ,a ,a ,……,a ,a ）.
2.所有分支结点的度为2的二叉树称为正则二叉树，试用二叉链表做存储结构，编写一递归函数int FonnalTree(Bitree t)，判断二叉树是否为正则二叉树。 |
评分
-
查看全部评分
|
发表于 2007-12-8 13:25
收藏
分享
支持
反对
