哈工大计算机考研真题2003-2008

哈尔滨工业大学2008年考研试题

Ⅰ数据结构部分 一填空题

1.已知一个线性表有n个元素，其中每个元素的数据占8个字节，假设一个指针的大小为 4个字节，如果采用有30个元素的数组存储，那么当数组中有效元素个数满足 1. 许多文献中认为常用的排序算法是快速排序算法，而不是归并排序，你是如何理解的？

2. 在包含n个关键字的线性表中进行顺序查找,若查找第i个关键字的概率为Pi且分布如下： P1=1/2, P2=1/4 ,…, Pn-1=1/2( n-1) , Pn=1/2n ； 求：（1）查找成功的平均查找长度。（2）查找失败情况下的平均查找长度。 ⑴ 条件时，数组的存储效率比不带头结点的单链表更高。

2. 给定14个字母，假设它们的权值都相等．采用huffman编码，则每个字母的平均代码长度是 ⑵ 。

3. 按C语言的运算符优先级，中缀表达式“A&&B||!(E>F)”的等价后缀形式为 ⑶ 。 4. 设按顺时针方向移动的循环队列Q[N]的头尾指针分别为F、R，头指针F总是指在队列中的第一个元素的前一位置，尾指针R在最后一个元素的位置，则队列中的元素个数为 ⑷ 。

5. 从空二叉树开始,严格按照BST（二又查找树）的插入算法，逐个插入关键字{18,73,10，5，68，99，27，41,32，25）构造出一颗BST ，对该BST按照先根遍历得到的序列为 ⑸ 。

6. 将两个长度为m的有序序列归并为一个有序序列，最少需要做 ⑹ 次关键字比较，最多需要做 ⑺ 次关键字比较。

7. 散列查找中， ⑻ 现象称为冲突， ⑼ 现象称为聚集。

8. 设可用的内存单元可处理4个记录，采用4 路归并的选择树法生成由小到大的初始归并段，对有12个记录在案的文件，产生的第一个初的归并段长度为 ⑽ 个。 9. 在两种求图的最小生成树的算法中， ⑾ 算法适合于边稀疏的图的最小生成树。 10. 已知一个序列为{21，39，35，12，17，43}，则利用堆排序方法建立的初始堆为： ⑿ 。

二、判断（每题1分．共9分）

1. 倒排文件只能按关键字的顺序存储。（ ① ）

2. 堆的存储表示可能是链接式的，也可以是顺序的。（ ② ） 3. 在AOE网中，任何一个关键活动的延迟，都会使整个工程延迟。（ ③ ） 4. 有环路的有向图不能进行拓扑排序。（ ④ ）

5. 对无向图进行一次深度优先搜索可以访问到图中的所有顶点。（ ⑤ ） 6. 大根堆的最大元素应该在堆顶，即根结点。（ ⑥ ）

7. 归并排序的平均时间复杂度为O（n㏒n）,最坏为O（n2）。（ ⑦ ） 8. 栈总是在栈底删除元素。（ ⑧ ）

9. 分块查找只适合静态查找，不适合动态查找。（ ⑨ ） 三、问答题（每题8分．共16分） 四、算法设计题(每题15分．共30分)

1. 设二叉树结点表示的数据元素类型为Elementtype,二叉树用左右链表示。一棵二叉树的最大枝长和最小枝长分别如下定义： 最大枝长就是二叉树的层数；最小枝长就是离根结点距离最近的叶结点到根路径上的边数。 请设计一个算法，同时求出一棵二叉树的最大和最小枝长。

2. 设计一查找无环路有向图第对顶点间“最长简单路径“（所谓最长简单路径是指该简单路径包含边最多）的算法，即以一个无环路有向图作为输入，对于每个顶点如果它们之间存在简单路径，则输出其中最长的，否则输出为空。 Ⅱ.计算机组成原理部分（共75分） 五、填空题（每空1分．共15分）

1. 总线控制主要解决 ⑴ 问题。集中式仲裁有 ⑵ 、 ⑶ 、 ⑷ 三种。 2. 若数据在存储器中采用以低字节地址的存放方式，则十六进制数12,34,56,78H按字节地址由小到大依次为 ⑸ 。

3. 总线 ⑹ 技术是指不同的信号（如地址信号和数据信号）共用一组物理线路，分时使用，此时需要配置相应的电路。

4. 一个四级流水的处理器，共有12条指令连续输入此流水线，则在12个时钟周期结束时执行完 ⑺ 条指令。

5. CPU在 ⑻ 时刻采样中断请求信号（在开中断情况下）。而在 ⑼ 时刻采样DMA的总线请求信号。

6. 32位字长的浮点数，其中阶码8位（含1位阶符），基值为2，尾数为24位（含1位数符）。当机器数采用原码表示，则其对应的最小正数是 ⑽ ，最小负数是 ⑾ ；当机器数采用补码表示，尾数为规格化形式，则其对应的最大正数是 ⑿ ，最大负数是 ⒀ 。（均用十进制表示）

7. 定点原码除法和定点补码除法均可采用 ⒁ 法，但补码除法中 ⒂ 参与运算.

六、问答题(每题8分．共32分) 1. 什么是DMA（特点）,简述采用DMA方式实现主机与I/O交换信息的数据

传递过程。

2. 右图为某SRAM的写入时序图，R/W(W反)线为读写信号线，CS(反)线为片选信号线，要求写入地址为2450H的存储单元中，指出图中的错误，并把相应的正确的时序图画出来。

3. 什么是单重分组和双重分组跳跃进位链？一个按3、5、3、5分组的双重分组跳跃进位链（最低为第0位）。试问大组中产生的是哪几位进位？与按4444分组的双重分组跳跃进位链相比，试问产生全部进位的时间是否一致？为什么？

4. 若某机采用微程序控制方式，微指令字长24位，共有微指令30个，一条微指令允许同时启动4个微操作命令，可判定的外部条件共3个，画出微指令格式，并指出控制存储器的容量为多少?

七、设某计算机机器字长为16位，共有16个通用寄存器，4种寻址方式（寻址模式只需用一个字段表示），采用扩展操作码技术，指令字长可变，主存容量为1M*16位，存储器按字编址。

（1） 设计单字长寄存器---寄存器型指令格式，并指出这类指令最多允许几条。 （2） 在（1）的基础上，扩展成单操作数的指令，设计指令格式，并指出这类指令最多允许几条。

（3） 设计允许直接访问主存单元的“寄存器—存储器”指令格式。 （4） 若可指定任一通用寄存器作为变址寄存器，设计变址寻址的“寄存器—存储器”型指令格式。

八、设CPU有18根地址线和16根数据线，并用作访存控制信号，为读命令，为写命令，已知： （1）下列芯片及各种电路（门电路自定）

（2）存储芯片地址空间分配为：0—32767为系统程序区，32768---98303为用户程序区，最大16K地址空间为系统程序工作区； 要求： （1） 指出选用的存储器芯片类型及数

量；

（2） 写出每片存储芯片的二进制地址范围； （3） 画出CPU与存储器的连接图。 九、（1）什么是多级时序系统？

（2）假设CU为组合逻辑控制，且采用控制和局部控制相结合的办法，写出完

成乘法指令MUL a指令（a为主存地址）的全部微操作命令及节拍安排（包括取指阶段）。设机器数字长为N位，（不包括符号位），机器数形式自定。假设在乘法开始前，被乘数已存在于X寄存器中，并用A//Q寄存器存放乘积。

（3）指出哪些节拍属于控制节拍，哪些节拍属于局部控制节拍，局部控制最多需要几拍？

哈尔滨工业大学2007年考研试题

Ⅰ.数据结构（含高级语言）部分（75分） 一、填空题（每空1分，共10分） 1. 设图G有n个顶点e条边，采用邻接表存储，则拓扑排序算法的时间复杂性为 ① 。 2. 线索二元树的左线索指向 ② ，右线索指向 ③ 。

3. 若分别以实数4，5，6，7，8作为叶结点的权值来构造哈夫曼（Huffman）树，则该哈夫曼树的带权路径长度是 ④ 。

4. n个顶点的连通图用邻接矩阵表示时，该矩阵至少有 ⑤ 个非零元素。 5. 设只包含根结点的二元树的高度为0，则高度为K的二元树的最多结点数为 ⑥ ，最少结点数 ⑦ 。

6. 任意一个有n个结点的二元树，已知它有m个叶结点，则度数为2的结点有 ⑧ 。 7. 对n个记录的表进行选择排序，在最坏情况下所需要进行的关键字的比较次数为 ⑨ 。

8. 在 ⑩ 情况下，等长编码是最优前缀码。 二、选择题（每题1分，共8分）

1. 若结点的存储地址是其关键字的某个函数，则称这种存储结构为 ① 。 A. 顺序存储结构 B. 链式存储结构 C. 索引存储结构 D. 散列存储结构 2. 对于一个索引顺序文件，索引表中的每个索引项对应主文件中的 ② 。 A. 一个记录 B. 多条记录 C. 所有记录 D. 以上都不对

3. 将两个各有n个元素的已排序表归并成一个排好序的表，其最少的比较次数是 ③ 。

A. n B. 2n-1 C. 2n D. n-1

4. 假定有K个关键字且散列地址相同，若用线性探测法（步长为1）把K个关键字存入散列表中，至少要进行 ④ 次探测。 A. K-1 B. K C. K+1 D. K(K+1)/2

5. 在关键字随机分布的情况下，用二元查找树的方法进行查找，其平 均查找长度与 ⑤ 量级相当。 A. 顺序查找 B. 折半查找 C. 分块查找 D. 散列查找

6. 对于一个有向图，若某顶点的入度为K1，出度为K2，则在该图的逆邻接表中，

关于该顶点链表的结点个数为 ⑥ 。 A. K1 B. K2 C. K1-K2 D. K1+K2

7. 下列说法正确的是 ⑦ 。 A.最小生成树也是哈夫曼（Haffman）树 B.最小生成树唯一 C.对于n个顶点的连通无向图，Prim算法的时间复杂性为O（n2） D.Kruskal算法比Prim算法更适合边稠密的图 8. 一个有n个顶点的连通无向图，它所包含的连通分量个数为 ⑧ 。 A. 0 B. 1 C. n 1. 某机有五级中断，优先级从高到低为1→2→3→4→5。若将优先级顺序修改，改后1级中断的屏蔽字为11111，2级中断的屏蔽字为01010，3级中断的屏蔽字为01111，4级中断的屏蔽字为00001，5级中断的屏蔽字为01011，则修改后的处理优先级顺序从高到低为 A 。

2. 已知74181是4位的ALU芯片，其4位进位是同时产生的，74182是先行进位D. n+1 三、判断题（每题1分，共10分） 1. 顺序存储的线性表可以随机存取。（ ① ）

2. 单源最短路径的Dijkstra算法中要求边上的权值不能为负的原因是实际应用无意义。（ ② ）

3. 若无向图G的顶点度数的最小值大于或等于2，则G必然存在环路。（ ③ ） 4. 在二元树中，具有一个儿子的父结点，在中根遍历序列中没有后继结点。（ ④ ） 5. 广义表中原子的个数即为广义表的长度。（ ⑤ ） 6. 有环路的有向图不存在拓扑序列。（ ⑥ ）

7. 快速排序的速度在所有以比较为基础的排序方法中是最快的，且所需附加空间最小。（ ⑦ ）

8. 对于n个记录的集合进行归并排序，在最坏情况下所需要的时间是O（n2）（。 ⑧ ） 9. 外排序过程主要分为两个阶段：生成初始归并段和对归并段进行逐趟归并。（ ⑨ ）

10. 一个连通的无向图是双连通的，当且仅当它没有关节点。（ ⑩ ） 四、简答题（14分）

1.（7分）举例说明4×3的稀疏矩阵的两种存储方法。

2.（7分）一组关键字（46，79，56，38，40，84）所对应的完全二元树是否为堆，如果是堆，请给出堆排序的前两步的图示；如不是，则给出建立初始堆（大顶堆）及堆排序的前两步的图示。

五、算法设计题（33分） 队列和栈的基本操作可以直接使用。

1.（11分）设二元树的存储结构为左右链形式，设计按层次遍历该二元树的算法并输出结点序列。

2.（11分）对于给定的一个排好序的整数序列。设计一个算法构造 一棵二元树，使得在该二元树中，以任意结点为根的子树的高度之差的绝对值不大于1。

3.（11分）可以使用“破圈法”求解带权连通无向图的一棵最小生成树。所谓“破圈法”就是任取一个圈并去掉圈上权最大的边，反复执行这一步骤，直到没圈为止。请设计该算法求解给定带权连通无向图的最小生成树。（注：图即为环路）。 Ⅱ.计算机组成原理部分（共75分） 六、填空（23分，每空1分） 芯片，现用8片74181和2片74182可组成 A 。

3. 在集中式总线仲裁中， A 方式响应时间最快， B 方式对电路故障最敏感。 4. 有一主存-Cache层次的存储器，其主存容量1MB，Cache容量16KB，每字块有8个字，每字32位，采用直接地址映像方式，若主存地址为35301H，且CPU访问Cache命中，则在Cache的第 A （十进制表示）字块中（Cache起始字块为第0字块）。

5. 对于某些指令（如乘法指令），控制器通常采用 A 控制方式来控制指令的执行，但 这种控制中的节拍宽度与 B 控制的节拍宽度是相等的，而且这两种控制是 C 。 6. 一个DMA接口可采用周期窃取方式把字符传送到存储器，它支持的最大批量为200个字节，若存取周期为0.2us，每处理一次中断需4us，现有的字符设备的传输率为9600位/秒。假如字符之间的传输是无间隙的，试问DMA方式每秒因数据传输占用处理器 A 时间，如果完全采用中断方式，又需占处理器 B 时间。（忽略预处理所需的时间）。

7. 设相对寻址的转移指令占2个字节，第一字节为操作码，第二字节为位移量（用补码表示），每当CPU从存储器取出一个字节时，即自动完成（pc）+1→pc。设当前指令地址为3008H，要求转移到300FH，则该转移指令第二字节的内容应为 A 。若当前指令地址300FH，要求转移到3004H，则该转移指令第二字节的内容为 B 。 8. 二进制数在计算机中常用的表示方法有原码、补码、反码和移码等多种。表示定点整数，若要求数值0在计算机中唯一表示为全“0”，应采用 A ；表示浮点数时，若要机器零（即尾数为零，且阶码最小的数）在计算机中表示为全“０”，则阶码应采用 B 。某计算机中，浮点数的阶码占８位（含1位阶符），尾数占40位（含1位数符），都采用补码，则该机器中所能表达的最大浮点数是 C 。

9. 在浮点机中，设尾数采用双符号位，当补码运算结果的尾数部分不是 A 的形式应进行规格化处理，当尾数符号位为 B 时，需要右规。 10. 除了采用高速芯片外，从计算机的各个子系统的角度分析，可采用 A 、 B 、 C 、 D 、 E 、 F 等措施提高整机速度。

七、简答与计算（18分）

1. （5分）为了减轻总线负载，总线上的部件应具备什么特点？什么 是总线通信控制？总线通信控制有几种方式？

2. （7分）设计中断系统需考虑哪些主要问题？分别可用哪些技术解决？ 3. （6分）已知二进制数x=-0.1111，y=0.1101，用补码一位乘Booth算法计算x×y。 八、（8分）假设某机有8个16位的通用寄存器，主存容量为256K字，共能完成种操作，且有4种寻址方式，试回答： ⑴ 设计一个三地址格式的寄存器－存储器型指令，可完成（Ri）OP（M）→Rj。 ⑵ 若采用直接寻址方式访问主存中的任一地址，上述三地址格式指令中的地址码域应分配多少位？指令字长应为几位？ ⑶ 5．同一棵二元查找树中插入一个元素时，若元素的值小于根结点的元素值，则应把它插入到根结点的 ⑥ 上。

6．举出两种磁带文件的分类方法： ⑦ 和 ⑧ 。

7．按二元树的定义，具有三个结点的二元树共有 ⑨ 种形态。 二、单项选择（每题1分，共9分）

1．已知一个序列为{21，39，35，12，17，43}，则利用堆分类方法建立的初试堆若采用基址寻址方式，上述指令格式应如何修改？ ⑷ 若指令字长等于存储字长，假设主存容量扩充到4G字，在不改变硬件结构的前提下，可采用什么寻址方式使指令能访问主存空间中的任一位置？ 九、（12分）设CPU有18根地址线和8根数据线，并用IO/M(M反)作访存控制信号，作读写命令，存储器采用四体低位交叉结构，画出CPU和存储芯片的连接图。要求： ⑴ 合理选用下列芯片，门电路自定。 ⑵ 写出每片存储芯片的二进制地址范围。 ⑶ 详细画出存储芯片的片选逻辑。 ⑷ 该存储器在一个存取周期内可向CPU提供多少位信息？ 十、（14分）已知带返转指令的含义如下图所示：

⑴ 写出机器在完成带返转指令时，组合逻辑控制取指阶段和执行阶段所需的全部微操作命令及节拍安排。 ⑵ 若采用微程序控制，还需增加哪些微操作？ ⑶ 假设该机指令系统采用6位定长操作码格式，共对应多少个微程序？ ⑷ 微指令的操作控制方式有几

种？各有何特点？ ⑸ 微指令的下地址字段位数如何确定？

哈尔滨工业大学2006年考研试题

Ⅰ.数据结构（含高级语言）部分（75分） 一、填空题（每空1分，共9分）

1．由二元树的前序和后序序列 ① 唯一确定这棵二元树。

2．在一个堆的顺序存储中，若一个结点的下标为i(0＜i≤n-1)，则它的左儿子的下标为 ② ，右儿子的下标为 ③ 。

3．以折半查找方法从长度为10的有序表中查找一个元素时，查找成功的平均长度为 ④ 。 4．高度为K的完全二元树中，结点数n和K之间的关系是 ⑤ 。 为（ ① ）。 A．39，21，35，12，17，43 B．43，39，35，12，17，21 C．43，39，35，21，17，12 D．43，35，39，17，21，12 2．算法性能分析的两个主要方面是（ ② ）。 A．数据复杂性和程序复杂性 B．可读性和健壮性 C．时间复杂性和空间复杂性 D．正确性和简单性

3．已知一个栈的输入序列顺序为1，2，3，4，…，n，输出序列为P1，P2，P3，…，Pn。若Pn ＝n，则Pi（1＜i＜n）为（ ③ ）。 A．i B．n－i C．n－i－1 D．不确定 4．在（ ④ ）算法中，第一趟排序后，最大的或最小的数一定在其最终位置上。 A．归并排序 B．插入排序 C．快速排序 D．冒泡排序

5．从二元查找树中查找一个元素时，其平均时间复杂性为（ ⑤ ）。 A．O(n) B．O(1) C．O(㏒n) D．O(n2)

6．设结点X和结点Y的二元树T中的两个结点，若在前序序列中X在Y之前，而在后序序列中X在Y之后，则X与Y的关系是（ ⑥ ）。

A．X是Y的左兄弟 B．X是Y的右兄弟 C．Y是X的祖先 D．Y是X的后代 7．在一个长度为n的线性表中的第i个元素(0＜i≤n-1)之前插入一个新元素时，需向后移动（ ⑦ ）个元素。 A．n-1 B．n-i+1 C．n-i-1 D．i

8．对于一组权值都相等的16个字母，构造相应的哈夫曼树，这棵哈夫曼树是一棵（ ⑧ ）。 A．完全二元树 B．一般二元树 C．满二元树 D．以上都不正确 9．若要尽可能快地完成对实型数组的排序，且要求排序是稳定的，则应选择（ ⑨ ）。 A．快速排序 B．堆排序 C．归并排序 D．基数排序 三、判断题（每题1分，共10分）

1．折半查找只适合用于有序表，包括有序的顺序表和有序的链接。（ ① ） 2．拓扑分类适合于无环路有向图且拓扑序列唯一。（ ② ）

3．在n个结点的无向图中，若边数大于n-1，则该图必是连通图。（ ③ ） 4．散列法存储的基本思想是由关键字的值确定关键字的存储地址。（ ④ ） 5．用邻接矩阵存储一个图，所需的存储单元数目与图的边数有关。（ ⑤ ）

6．在磁盘分类中，对于能容纳P个记录的缓冲区，不能产生出长度大于P的初始归并段。 （ ⑥ ）

7．倒排文件与多重链表文件相似，都是用来处理多关键字查找。（ ⑦ ）

8．中序线索二元树的优点是便于在中序遍历时查找任意结点的前驱结点和后继结点。（ ⑧ ）

9．外部排序过程主要分为两个阶段：生成初始归并段和对归并段进行逐趟归并。C ，后者需配有 D 。 5．某计算机采用微程序控制，微指令字中操作控制字段共20位，若采用直接控制，则可以定义 A 种微操作，此时一条微指令最多可同时启动 B 个微操作。若采用编码控制，并要求一条微指令需同时启动4个微操作，则微指令字中的操作控制字段（ ⑨ ）

10．索引顺序文件是一种特殊的顺序文件，因此通常存放在磁带上。（ ⑩ ） 四、简答题（共20分） 1．（10分） 已知一个边带权无向图的顶点集V和边集E分别为： V＝{0，1，2，3，4，5，6，7}； E＝{（0，1）8，（0，2）5，（0，3）2，（1，5）6，（2，3）25，（2，4）13，（3，5）9， （3，6）10，（4，6）4，（5，7）20，（6，7）30}。边集E中的一条边表示成（x，y）z的形式，其中x，y代表边的两个顶点，z代表该边的权值。 要求（1）简述Kruskal算法求最小生成树的基本思想； （2）按该算法写出构造最小生成树的每一步。 2．（6分）简述用循环数组实现队列时队列满与队列空的区别方法，并给出判断队列满和队列空的条件。 3．（4分）试举例说明，如果允许带权有向图中某些边的权为负实数，则Dijkstra算法不能正确地求出从源点到每个顶点的最短路径。 五、算法设计题（共27分） 1．（13分）已知A、B、C是三个线性表且其元素按递增顺序排列，每个表中元素均无重复。在表A删去既在表B中出现又在表C中出现的元素。试设计实现上述删除操作的算法Delete，并分析其时间复杂性。 2．（14分）设图中各边的权值都相等，以邻接表为存储结构，试设 计求任意两个不同顶点之间最短距离的算法ShortPath（可以直接使用栈或队列的存储结构和操作）。

Ⅱ.计算机组成原理部分（共75分） 六、填空（15分，每空1分）

1．当机器零用全0表示时，其阶码为 A 码。

2．设CPU的主频为16MHz，若每个机器周期包含4个时钟周期，该机的平均指令执行速度为0.8MIPS，则该机的时钟周期为 A μS，平均指令周期为 B μS，每个指令周期含 C 个机器周期。

3．一个四路组相联的Cache容量为8KB，主存容量为4MB，每字块有16个字，每个字32位，则主存地址中的主存子快标记为 A 位，组地址为 B 位，字块内地址为 C 位。

4．CPU响应中断后可通过 A 或 B 转至中断服务程序的入口地址，前者需配有 应分 C 段，若每个字段的微命令数相同，这样的微指令格式最多可包含 D 个微操作命令。

七、简答与计算（30分）

1．说明总线通信中半同步通信的特点，若想提高总线带宽，可采取什么措施？（5分）

2．试从五个方面比较程序中断方式和DMA方式。（5分） 3．假设阶码取3位，尾数取6位（均不包括符号位），按浮点补码运算步骤计算 (2^5*(11/16)(2^4*(-9/(16)))。如何判断其结果是否溢出。（6分） 4．今有五级流水线，分别完成取指（IF），译码并取数（ID），执行（EX），访存（MEM），写结果（WR）五个阶段。假设完成各个阶段操作的时间依次位90ηS，60ηS，70ηS，100ηS，50ηS。试问流水线的时钟周期应取何值？若第一和第二条指令发生数据相关，试问第二条指令需推迟多少时间才能不发生错误？若相邻两指令发生数据相关，而不推迟第二条指令的执行，可采取什么措施？（3分）

5．设某机有四个中断源，优先顺序按1→2→3→4降序排列，若1、2、3、4中断源的服务程序中对应的屏蔽字分别为1110、0100、0110、1111。试写出这四个中断处理次序（按降序排列）。若四个中断源同时有中断请求，画出CPU执行程序的轨迹。（5分）

6．试比较补码除法和原码除法。设寄存器为16位（含1位符号位），试问两种除法分别作多少次加法和多少次移位?（6分） 八、（14分）设CPU有16根地址线，8根数据线，并用MERQ(反)作访存控制信号，IORO(反)作访问I/O端口的控制信号，RD(反)为读命令，WR(反)为写命令， I/O编址采用单独编址，现有下列芯片及各种门电路（自定）。

画出CPU和存储芯片及CPU的I/O接口芯片的连接图，要求： （1）主存除最大地址空间存放系统BIOS程序（约4KB）外，其余地址空间均为用户所用。 （2）接口芯片的地址范围为80H—87H。 （3）指出选用的芯

片类型、数量及地址范围。 （4）详细画出存储器芯片和接口芯片的片选逻辑。 九、（16分）某模型机共有种操作，操作码位数固定，且具有以下特点： （1）采用一地址或二地址格式； （2）有寄存器寻址，基址寻址（通用寄存器作基址寄存器）和相对寻址（位移量为－128～＋128）； （3）有16个通用寄存器，算术运算和逻辑运算的操作数均在寄存器中，结果也在寄存器中； （4）取数/存数指令在通用寄存器和存储器之间传送数据； （5）CPU的数据线为16位，存储器按字节编址； （6）有效地址的形成可通过地址加法器及相应的硬件（自定）完成。 要求： C．{0,10,110,111} D．{000,001,010,101}

4．当n足够大时，下述函数中渐近时间最小的是（ ④ ）。 A．T(n)=n㏒n-1000㏒n B．T(n)=n㏒3-1000㏒n C．T(n)=n2-1000㏒n D．T(n)=2n㏒n -1000㏒n 5．设有一个n行n列的对称矩阵A，将其下三角部分按行存放在一个一维数组B中，A[0][0]存放在B[0]中，那么第i行对角元素A[i][i] 存放于B中（ ⑤ ）处。 A（．i+3）*i/2 B．（i+1）*i/2 C．（2n-i+1）*i/2 D．（2n-i-1）*i/2 6．已知一个线性表（1，13，12，34，38，33，27，22），假定采用h(k)=k%11 计算（1）设计算术逻辑指令、取数/存数指令和相对转移指令的格式，并简单说明。 （2）以基址寻址的取数指令为例，按序画出完成该指令的信息流程（如→） （3）以基址寻址的取数指令为例，写出完成该指令由组合逻辑控制单元所发出的微操作命令及节拍安排。 （4）如果采用微程序控制，需增加哪些微操作命令？

哈尔滨工业大学2005年考研试题

Ⅰ.数据结构（含高级语言）部分（75分） 一、填空题（每空1分，共10分）

1．设有两个算法在同一机器上运行，其执行时间分别为100n2和2n，要使前者快于后者，n至少为 ① 。

2．在AOE（Activity On Edge）网中，从原点到汇点路径上各个活动的时间总和最长的路径 称为 ② 。

3．在等概率情况下，对具有n个元素的顺序表进行顺序查找，查找成功（即表中有关键字等于给定值K的记录）的平均查找长度为 ③ ；查找不成功（即表中无关键字等于给定值K的记录）的平均查找长度为 ④ 。

4．高度为h的堆中，最多有 ⑤ 个元素；最少有 ⑥ 个元素。

5．求具有最小带权外路径长度的扩充二元树的算法称为 ⑦ 算法。

6．每次使用两个有序表合并成一个有序表，这种排序方法叫做 ⑧ 排序。

7．若一个具有n个顶点，e条边的无向图是一个森林，则该森林中比有 ⑨ 棵树。 8．设森林F对应的二元树B，它有m个结点，B的根为P，P的右子树结点个数为n，则森林F中第一棵树的结点个数是 ⑩ 。 二、单项选择（每题1分，共8分）

1．将长度为n的单向链表链接在长度为m的单向链表之后的算法的时间复杂性为（ ① ）。 A．O(1) B．O(n) C．O(m) D．O(m+n)

2．对于一个线性表既要求能够进行较快速的插入和删除，又要求存储结构能反映数据之间的逻辑关系，则应该用（ ② ）。 A．顺序存储方式 B．链式存储方式 C．散列存储方式 D．以上均可以

3．下述编码哪一组不是前缀码（ ③ ）。 A．{00,01,10,11} B．{0,1,00,11} 散列抵制进行散列存储，若用链地址法处理冲突，则查找成功的平均查找长度为（ ⑥ ）。 A．1 B．9/8 C．13/11 D．13/8 7．设有向图G是有10个顶点的强连通图，则G至少有（ ⑦ ）条边。 A．45 B．90 C．10 D．9

8．倒排文件包含有若干个倒排表，倒排表的内容是（ ⑧ ）。 A．一个关键字值和该关键字的记录地址 B．一个属性值和该属性的一个记录地址 C．一个属性值和该属性的全部记录地址 D．多个关键字和它们相对应的某个记录的地址 三、判断题（每空1分，共8分）

1．有环路的有向图不能进行拓扑分类。（ ① ）

2．对给定的关键字集合，以不同的次序插入初试为空的二元树中，不可能得到同一棵二元排序树。（ ② ）

3．在外部排序中，使用选择树法可以减少初试归并段的数量。（ ③ ） 4．若在磁盘上的顺序文件中插入新的记录，不一定要复制整个文件。（ ④ ） 5．顺序存储方式只能用于存储线性结构。（ ⑤ ）

6．折半查找与二元查找树的时间性能在最坏的情况下是相同的。（ ⑥ ） 7．稀疏矩阵压缩存储后，还可以进行随机存取。（ ⑦ ）

8．对一个无向图进行先深搜索时，得到的先深序列是唯一的。（ ⑧ ） 四、简答题（共22分）

1．画出对长度为18的有序顺序表进行折半查找的判定树，并计算出在等概率时查找成功的平均查找长度，以及查找失败时所需的最多的关键字比较次数。（8分） 2．假设以I和O分别表示入栈和出栈的操作，栈的初态和终态均为空。入栈和出栈的操作序列表示为仅由I和O组成的序列。 （1）下面所示的序列中哪些是合法的？（2分） A．IOIIOIOO B．IOOIOIIO C．IIIOIOIO D．IIIOOIOO （2）通过对（1）的分析，给出判断一个给定序列是否合法的算法思想。（4分）

3．已知某图的邻接表如图4-1，以V1为起点分别给出先深搜索序列和先广搜索序列，并简述先深搜索算法的基本思想。（8分） 五、算法设计题（共27分）

1．试设计一个HeapInsert(R，key)算法，将关键字key插入到堆R中去，并保证插入后R仍是堆。并分析你的算法的时间复杂性。（15分） 2．结点类型和存储结构如下： typedef struct{ int key;

datatype data; int count;

}node;node R[n];

试设计一个排序算法，要求不移动结点的存储位置，只在结点的count字段记录结点在排序中的序号，并将排序结果按升序输出。（12分） Ⅱ.计算机组成原理部分（共75分） 六、填空题（30分，每空1分）

1．总线上信息传送的管理是通过 A 主要包括 B 、 C 两个方面，前者主要解决总线使用权问题，后者主要解决 D 的问题，其中需增设一条“等待”（WAIT）响应信号线的控制方式是 E 。

2．CPU从主存中取出一条指令并执行该指令的时间叫做 A ，它通常包含若干个 B ，而后者又包含若干个 C 。

3．主机与I/O交换信息时，通常可用 A 、 B 、 C 、通道和I/O处理机等五种控制方式。

4．某计算机字长32位，存储容量8MB，若按半字编址，它的寻址范围是 A ，若按双字编址，其寻址范围是 B 。

5．假设机器字长为31位（不含符号位），若一次移位需10μS，一次加法需10μS，则原码一位乘最多需要 A 时间，补码Booth算法最多需要 B 时间。

6．除了采用高速芯片外，存储器还可以采用 A 提高速度，运算器可采用 B 提高运算速度，控制器可采用 C 提高处理机速度。

7．设相对寻址的转移指令占3个字节，第一字节为操作码，第2字节是相对位移量（补码表示）的低8位，第3字节是相对位移量（补码表示）的高8位。 每当CPU从存储器中取出一个字节时，即自动完成(PC)＋1→PC， 若PC当前值为2005H，要求转移到200CH，依次写出该转移指令 第2、第3字节的机器代码为A H。若PC当前值为200AH， 要求转移到2003H，则依次写出该转移指令的第2、第3字节的机器代码为 B H。

8．设浮点数阶码为8位（含1位阶符），基值为2，用移码表示，尾数为24位（含1位数符），用补码规格化表示，则对应其最大正数的机器数形式为 A ，真值为 B （十进制表示）；对应其最大负数的机器数形式为 C ，真值为 D （十进制表示）。

9．控制单元CU是提供完成机器全部指令操作的微操作命令序列部件。其形式方

法有两种，一种是 A 设计方法，为 B 逻辑；另一种是 C 设计方法，为 D 逻辑。 10．某机共有32个32位的通用寄存器，且能完成130种操作，假设指令字长等于机器字长。

若采用通用寄存器作为变址寄存器，设计一种变址寻址的“寄存器—寄存器”型指令格式，则指令的形式地址为 A 位，操作数的寻址范围是 B 。 七、选择题（5分，每题1分）

1．在补码定点加法运算中，若采用1位符号位，则当 时，表示结果溢出。 A．符号位有进位 B．符号位进位和最高数位进位异或结果为0 C．符号位为1 D．符号位进位和最高数位进位异或结果为1

2．指令系统中采用不同寻址方式的目的主要是 。 A．可直接访问外存 B．提供扩展操作码并降低指令译码难度 C．缩短指令长度，扩大寻址空间 D．实现存储程序和程序控制

3．CPU内通用寄存器的位数取决于 。 A．存储器的容量 B．机器字长 C．指令的长度 D．CPU的管脚数

4．某计算机有四级中断，优先级从高到低为1→2→3→4，假定将优先级顺序修改，改后1级中断的屏蔽字为1011，2级中断的屏蔽字为1111，3级中断的屏蔽字为0011，4级中断的屏蔽字为0001，则修改后的优先级顺序从高到低为 。 A．3→2→1→4 B．2→1→3→4 C．1→3→4→2 D．4→3→2→1

5．一个组相联地址映像Cache由个存储块构成，每组包含4个存储块，主存包含4096个存储块，每块由8字组成，每字为32位，存储器按字节编址。试问主存地址18AB9H映像到Cache的 组的任一字块中。 A．第一组 B．第二组 C．第三组 D．第四组

八、简答与计算（20分）

1．假设计算机A和计算机B采用相同的操作系统，现用同一基准程序P测试这两台机器的速度，如果测得A的速度为MIPSA，B的速度为MIPSB，且MIPSA＞MIPSB，试问是否可以认为，在执行程序P时，计算机A的速度比计算机B的速度快？为什么？（3分）

2．DMA接口电路中需有几个寄存器？若主存容量为1M×16位，外设的地址空间为256，传送的最大批量为512字节，写出每个寄存器的名称、作用和位数。（4分） 3．已知x＝0.1010，y＝0.1101，按机器运算步骤计算x÷y并还原 成真值（机器数形式自定）。（5分）

4．CPU进入中断响应周期要完成什么操作？这些操作由谁来完成？ （4分）

5．什么是双重分组跳跃进位链？设机器字长为32位，最高位为第0位， 采用双

重分组跳跃进位链，要求大组内按5、3、5、3分组，写出每个大组内的全部进位Ci。（4分） 九、（8分）设CPU共有16根地址线，8根数据线，并用MERQ(反)作访存控制信号，用RD(反)为读控制信号，WR(反)为写控制信号。要求最大8K地址空间为系统程序区，与其相邻的16K地址空间为用户程序区，最小4K地址空间为系统程序工作区。R出现的概率是0.15，K出现的概率是0.10，若采用霍夫曼（Huffman）编码，则E

的编码是 ⑧ （要求概率小的作为左分支）。

7．索引文件在存储器上分两个区，分别为 ⑨ 和 ⑩ 。 二、单项选择（每题1分，共9分） 1．已知一算术表达式的中缀形式为a-(b+c/d)*e，其后缀形式为（ ① ）。 A. -a+b*c/d 现有下列芯片： ROM芯片：①2K×8位 ②4K×8位 ③8K×8位 RAM芯片：①4K×8位 ②8K×8位 ③16K×8位 74138 门电路自定

ROM信号定义: OE(反)允许输出，CS(反)片选, PGM(反)允许编程。 RAM信号定义：OE(反)允许输出，CS(反 )片选，WE(反)允许写 画出

CPU与存储芯片的连接图，要求： （1）画出每片存储芯片的地址范围（用二进制表示） （2）指出存储芯片的类型和数量 （3）详细画出存储芯片的片选逻辑 十、综合题（12分）

1．画出执行ADD @M(@为间接寻址特征)指令的信息流程图（2分）

2．假设CPU中有PC、IR、ID、MAR、MDR、ACC、ALU和CU，写出完成该指令所需的全部微操作命令及节拍安排。（5分）

3．如果CU采用微程序设计，画图说明CU中应包含哪些硬件，并指出完成上述指令还需增加哪些微操作命令？（4分）

哈尔滨工业大学2004年考研试题

Ⅰ.数据结构（含高级语言）部分（75分） 一、填空（每空1分，共10分） 1．用下标从0开始的n个元素的数组实现循环队列时，为实现下标变量m加1后，m仍在数组有效下标范围内，则m= ① 。

2．若二元树的一个叶结点是某子树的中根遍历序列中的第一个结点，则它必然是该子树的后根遍历序列中的 ② 个结点。

3．对具有17个元素有序表A[1...17]作折半查找，在查找其元素值等于A[8]的元素时，被比较的元素下标依次是 ③ 。

4．快速分类的最大和最小递归深度分别是 ④ 和 ⑤ 。 5．外部分类过程主要分为两个阶段： ⑥ 阶段和 ⑦ 阶段。

6．已知下面这些字母在某字典中A出现的概率为0.08，B出现的概率为0.04，I出现的概率为0.15，C出现的概率是0.20，E出现的概率是0.12，F出现的概率是0.16，B. -a+b*cd/e C. -+*abc/de D. abcd/+e*- 2．在解决计算机主机与打印机之间速度不匹配问题时通常设置一个打印数据缓冲区,主机将数据依次写入缓冲区,而打印机则从缓冲区中取出数据打印,该缓冲区是一个（ ② ）结构。 A. 栈 B. 队列 C. 线性表 D. 以上都不是

3．设栈Ｓ和队列Ｑ的初始状态为空，元素e1，e2，e3，e4，e5和e6依次通过栈，一个元素出栈后即进入队列Q，若6个元素出队的序列是e2，e4，e3，e6，e5，e1，则栈S的容量至少应该是（ ③ ）。 A. 6 B. 4 C. 3 D. 2 4．在下列叙述中，不正确的是（ ④ ）。 A. 关键活动不按期完成就会影响整个工程的完成时间。B. 任何一个关键活动提前完成，将使整个工程提前完成。 C. 某些关键活动若提前完成，则整个工程提前完成。 D. 所有关键活动都提前完成，则整个工程将提前完成。

5．若需在O(n㏒n)时间内完成对数组的分类，且要求分类是稳定的，则可选择的分类方法是：（ ⑤ ） A. 快速分类 B. 堆分类 C. 归并分类 D. 插入分类 6．就分类算法所用的辅助空间而言，堆分类，快速分类和归并分类的关系是（ ⑥ ）。 A. 堆分类＜快速分类＜归并分类 B. 堆分类＜归并分类＜快速分类 C. 堆分类＞归并分类＞快速分类 D. 堆分类＞快速分类＞归并分类

7．将两个具有n个整数的有序表归并成一个有序表，其最少的比较次数是（ ⑦ ） A. n B. 2n-1 C. 2n D. n-1 8．快速分类在（ ⑧ ）的情况下不利于发挥其长处。 A. 待分类的数据量太大 B. 待分类的数据相同值过多 C. 待分类的数据已基本有序 D. 待分类的数据值差过大 9．倒排文件的主要优点为（ ⑨ ）。 A. 便于进行文件的插入和删除操作 B. 便于节省空间 C. 便于进行文件合并操作 D. 能大大提高基于非关键字的检索速度 三、判断下列叙述是否正确

1．就平均查找长度而言，分块查找最小，折半查找次之，顺序查找最大。 （ ① ） 2．外部分类的K路平衡归并，采用选择树法时，归并效率与K有关。 （ ② ） 3．对于n个记录的集合进行归并分类，最坏情况下时间复杂性为O（n2）。 （ ③ ） 4．倒排文件与多重表文件的次关键字索引结构不同。（ ④ ） 5．树的父链表示法其实就是用数组表示树的存储结构。（ ⑤ ） 6．在n个结点的无向图中，若边数＞n-1，则该图必是连通图。（ ⑥ ）

7．若一个有向图的邻接矩阵中对角线以下元素均为0，则该图的拓扑有序序列一定存在。（ ⑦ ）

四、简答（每题8分，共24分）

1．已知散列函数hash(k)=k%11，把一个整数值转换成散列表的下标，使用线性探测再散列法与链地址法构造散列表。分别画出所构造的两种散列表并把数据1，13，7．如果CPU处于开中断状态，一旦接受了中断请求，CPU就会自动 A ，防止再次接受中断。同时为了返回程序断点，CPU必须将 B 内容存至 C 中。为了在中断结束后返回主程序，并且允许接受新的中断，必须 D 和 E 。

8．依次从控制器、运算器、存储器和1/O系统四个方面,可采用 A 、 B 、 C 和 D 措施来提高计算机的整机速度。

12，34，38，33，27，22依次插入到散列表中。 2．简述堆的定义及堆分类算法的思想。

3．已知某数列输入顺序为10，5，7，14，3，1，18，12，15，16，按输入顺序画出其二元查找树并画出删除结点14后的二元查找树。 五、算法设计（共25分）

1．试写一个算法建立有向图的邻接表，并保存每个结点的入度和出度。（8分） 2．试写一个算法，在中根线索二元树中求任意结点P的中根顺序的前导结点SP。（8分）

3．设有一个双向链表，每个结点中除有prior（指向其前导结点）、data（数据域）和next（指向其后继结点）三个域外，还有一个访问频度域freq，在链表被起用之前，其值均初始化为零。每当在链表进行一次LocateNode（L,x）运算时， 令元素值为x的结点中freq域的值加1，并调整表中结点的 次序，使其按访问频度的递减序排列，以便使频繁访问的结

点总是靠近表头。试写一符合上述要求的LocateNode运算的算法。（9分） Ⅱ.计算机组成原理部分（共75分） 六、填空（28分，每空1分）

1．Cache的命中率是指 A ，命中率与 B 有关。

2．为了协调CPU和DMA访问主存的冲突，DMA与主存交换数据时可采用三种方法，分别是 A 、 B 和 C 。

3．某计算机采用微程序控制，微指令字中操作控制字段共12位，若采用直接控制，则此时一条微指令最多可同时启动 A 个微操作。若采用字段直接编码控制，并要求一条微指令需同时启动3个微操作，则微指令孚中的操作控制字段应分 B 段。若每个字段的微命令数相同，这样的微指令格式最多可包含 C 个微操作命令。 4．利用访存指令与设备交换信息，这在1/O编址方式中称为 A 。

5．每个总线部件一般都配有 A 电路，以避免总线访问冲突，当某个部件不占用总线时，由该电路禁止向总线输出信息。 6．1/O与主机交换信息的控制方式中， A 方式CPU和设备是串行工作的，而 B 和 C 方式CPU和设备是并行工作的，前者传送和主程序是并行进行的，后者传送和主程序是串行进行的。 9．32位字长的浮点数，其中阶码8位（含1位阶符），数符1位，尾数23位，其对应的最大负数为 A ，最小的绝对值为 B ，若机器数采用补码规格化表示，则对应的最大负数为 C 。（均用十进制表示）

10．设指令字长等于存储字长，均为16位，若指令系统共有120种操作，操作码位数固定，且具有直接、间接、变址、基址、相对、立即等寻址方式，则直接寻址的最大范围是 A ，一次间址的范围是 B ，立即数（补码）的范围是 C 。 七、选择题（7分，每题1分）

1．采用DMA方式传送数据时，每传送一个数据要占用 ① 的时间。 A．一个存取周期； B．一个指令周期； C．一个机器周期； D．一个中断周期。

2．在程序的执行过程中，Cache与主存的地址映射是由 ② 。 A．操作系统来管理的； B．程序员调度的； C．由操作系统和程序员共同协调完成的； D．由硬件自动完成的。

3．存取周期是指③ 。A．存储器的写入时间和读出时间的最小值； B．存储器进行连续写操作允许的最短间隔时间； C．存储器进行连续读或写操作所允许的最短间隔时间； D．以上说法都不对。

4．下列叙述中 ④ 是正确的。 A．程序中断方式和DMA方式中实现数据传送都需中断请求； B．程序中断方式中有中断请求，DMA方式中没有中断请求； C．程度中断方式和DMA方式中都有中断请求，但目的不同； D．DMA要等指令周期结束时才可进行周期窃取。

5．下列叙述中 ⑤ 是正确的。 A．虚拟存储器实际上就是辅存； B．一条指令中可以包含多个操作码； C．1/O接口是负责主存与外设交换信息的部件； D．由于定点乘法运算时不会出现溢出，所以浮点乘法运算时也不会出现溢出。 6．某机指令系统共有101种操作，采用微程序控制方式时，控制存储器中相应有 ⑥ 个程序。 A．101； B．102； C．103； D．104。

7．采用变址寻址可扩大寻址范围，且 ⑦ 。 A．变址寄存器内容由用户确定，且在程度执行过程中不可变； B．变址寄存器内容由操作系统确定，且在程度执行过程中不可变； C．变址寄存器内容由用户确定，且在程序执行过程中可变； D．变址寄存器内容由操作系统确定，且在程序执行过程中可变。 八、简答与计算（10分，每题5分）

1．总线管理包括哪些内容？简要说明各种管理措施。 2．设机器数字长为8位（含1位符号位）。设A=-11/32，B=95/128，列出竖式计算[A-B]补。 七、综合题（30分，共2题，第1题18分，第2题12分） 1．假设X，Y，Z寄存器均为16位（最高位为第0位），在乘法指令开始前，被乘数已存于X中，并用Y//Z存放乘积。 要求： ⑴画出实现补码Booth算法的运算器框图。（4分） ⑵假设CU为组合逻辑控制，且采用控制和局部控制 相结合的办法，写出完成MUL a指令（a为主存地址） 的全部微操作及节拍安排（包括取指阶段）。（10分） ⑶指出哪些节拍属于控制节拍，哪些节拍属于局部 控制节拍，局部控制最多需几拍？（4分）

2．设CPU共有20根地址线，8根数据线，并用作访存控制信号（低电平访存），用作读写控制信号（高电平为读，低电平为写），存储器按奇偶分体，按字节方式访问。

现有下列芯片：

ROM、RAM信号定义：i根地址线，j根数据线，

OE(反)允许输出，WE(反)允许写， CS(反)片选，PGM(反)允许编程。

哈尔滨工业大学2003年考研试题

I数据结构(含高级语言部分) 一、填空题

1.在循环链表中，可根据任意一个结点地址遍历整个链表，而在单向链表 中需要知道（1）才能遍历整个链表。

2.对一个序列F,B,W,A,E,H按字母表顺序从小到大进行分类。请回答：二路归并的第一遍结果是（2）插入分类的第一遍结果是（3）;堆分类的第一遍结果是（4）;选择分类的第一遍结果是（5）.

3.想要提高磁盘文件的分类效果，一般采用（6）（7）（8）等技术 4.哈夫曼树是加权路径长度（9）的二叉树

5.对n个顶点的连通无向图其生成树有且仅有（10）条边

6.在拓扑分类中，拓扑序列的最后一个顶点必定是（11）的顶点 二、单项选择与判断 ,单项选择题

1.在n 个结点的线性表的数组实现中，算法的时间复杂度是O（1）的操作是（（1）） A.访问第i个结点（1≤i≤n）和求i的第I 个直接前驱（2≤i≤n） B.在第i个结点后插入一个新结点（1≤i≤n） C.删除第i个结点（1≤i≤n）

D.以上都不对

2.森林T中有4株树，第1.2.3.4株树的结点个数的结点个数分别是n1,n2,n3,n4那么当把森林T转化成一株二叉树后,其根结点的右子树上有((2))个结点 A.n1-1 B.n1 C.n1+n2+n3 D.n2+n3+n4 3.要求内存是最大的分类算法是((3))

A.插入分类 B.选择分类 C.快速分类 D.归并分类 4.索引非顺序文件是指((4))

A.主文件无序,索引表有序 B.主文件有序,索引表无序 C.主文件有序,索引表有序 D.主文件无序,索引表无序 (二)判断下列叙述是否正确

5.二叉树按某种遍历顺序线索化后,任意一个结点均有指向其前驱和后继的线索 6.完全二叉树中若某个结点没有左儿子,该结点一定是终结结点

7.在索引顺序表进行分块查找,在等概率情况下平均查找长度不仅与表中元素个数有关而且与第一块中元素个数有关

8.基数分类只适用于以数字为关键字的情况,不适用于以字符串为关键字的情况 9.索引顺序存取方法是一种专门为磁盘存取而设计的索引顺序文件的组织方法 三.简答题

1.简述堆与二叉查找树的区别与联系

2.已知某加权连通无向图的个数远远小于顶点的个数,若求其最小 生成树用哪种算法最好?并简述该算法

3.用两个栈S1,S2模拟一个队列时,如何用栈的操作实现队列的插入,删除以及判队空操作.请简述算法思想

四、已知散列函数为h(K)，K为待查找的关键字，用开放定址法处理冲突，度写出删除一个指定关键字W的算法

五、设一株二叉树T按图1所示形式存放在内存中，试写出一个求T的高度和对每个结点赋予一个层号的算法

六、试设计一个算法，判断一个无环有向图G中是否丰硕这样的顶点，该顶点到其它任意顶点都有一条有向路 Ⅱ.计算机组成原理部分（共75分）

七、填空题（20分）

1．（2分）在做手术过程中，医生经常将手伸出，等护士将手术刀递上，待医生握紧后，护士才松手，如果把医生和护士看作是两个通信模块，上述一系列动作相当于通信过程中 A 通信中的 B 方式。 2．（3分）设机器数字长16位，其阶符、数符各一位，阶码4位，尾数10位。两个阶码相等的数按补码浮点加法完成后，由于规格化操作可能出现的最大误差的绝对值是 A 。 3．（2分）微指令操作控制的编码方式有 A 、 B 、 C 等，其中控制速度最快的是 字节，存于存储器最高端地址，用户程序30K字节，存于最低端地址。现有下列芯

片： （1）ROM芯片：①8K×4位 ②8K×8位 ③16K×4位 ④16K×8位 （2）RAM芯片：①16K×8位 ②4K×8位 ③K×8位 ④8K×8位

（ROM、RAM信号定义：i根地址线，j根数据线，允许输出，允许写，片选, 允许编程）

（3）74138 （4）门电路自定 画出满足上述要求的CPU和存储芯片的连接图，要求指出存储器的类型及数量。 D 。 4．（3分）I/O接口通过 A 总线（地址/数据，二选一填空）将中断向量地址送至CPU。不通过另一种总线传送向量的原因是 B 。 5．（3分）设某机共有30个通用寄存器，变址寄存器和基址寄存器各一个。该机指令系统共能完成180种操作。操作码位数固定，并具有立即、直接、间接、变址、基址、相对这几种寻址方式。假设指令字长等于存储字长，均为32位，设计一种“寄存器—存储器”型指令的格式。则可直接寻址的最大范围是 A ，一次间址的范围是 B 。上述寻址方式中 C 寻址的执行时间最快。 6．（2分）总线同步通信影响总线效率的原因是 A 。 7．（2分）影响流水线性能的因素包括 A 、 B 。 8．（3分）Intel80486有一个统一的片内Cache。Cache的容量为8K字节，且采用组相联结构，每组含4个字块，字块的大小是4个32位字，则需用 A 位地址码表示组地址。

八、简答题（18分） 1．（6分）设机器数阶码取3位（含1位阶符），尾数取5位（含1位数符），两数X、Y以二进制真值表示为X＝2-01×0.1101，Y＝2-10×（-0.1001），计算[X×Y]补。 2．（6分）一个CPU的指令周期包含取指、间址、执行和中断四个不同的阶段，采用组合逻辑设计控制器时，是否需要标志位来指定当前的阶段，为什么？微程序设计情况下是否需要这些标志，为什么？ 3．（6分）一个DMA接口可以采用周期窃取的方式把字符传到存储器，它支持的最大的批量为20个字节，而处理每个中断的平均时间为3.5微秒（1微秒=10-6秒）。现有一字符设备的传输率为9600bps（位/秒），CPU正常执行的速度为1×106条指令/秒，平均一条指令需要5个机器周期，一次存储器访问需要一个机器周期。假设字符之间的传送是无间隙的，试问采用中断方式和DMA方式，每秒因数据传输占用处理器的时间各为多少？如何能够进一步提高处理器效率？ 九、（12分）设CPU有16根地址线，8根数据线，并用（低电平有效）作访存控制信号，作读写命令信号（高电平为读，低电平为写）。有一系统程序编译后为6.592

十、（15分）设CPU中各部件及其相互连接关系如下图所示。

图中 W是写控制标志 R是读控制标志 R1、R2是暂存器 1．写出指令ADD #a（#为立即寻址特征，隐含的操作数在ACC寄存器中）在执行阶段所完成的微操作命令及节拍安排。 2．假设要求在取指周期实现PC＋1→PC，且由ALU完成此操作（即ALU可以对它的一个源操作数完成加1的运算）。要求以最少的节拍写出取指周期全部微操作命令及节拍安排。 十一、（10分）设机器字长为12位，按3、3、3、3分组，数据源A和B可采用双重分组的并行进位方式完成加法运算。设与门、或门、与非门的延迟时间为30微秒，与或非门的延迟时间为45微秒。假定A\\B数据的每一位Ai、Bi在t＝0时刻同时到来，计算Ai、Bi成立后每个进位的产生时间。