历年年哈工大计算机考研试题(无水印-)参考

《历年年哈工大计算机考研试题(无水印-)参考》由会员分享，可在线阅读，更多相关《历年年哈工大计算机考研试题(无水印-)参考（33页珍藏版）》请在金锄头文库上搜索。

1、XXXX大学二四年硕士研究生入学考试试题考试科目：计算机专业基础考试科目代码： 424 报考专业：计算机科学与技术 考生注意：答案务必写在答题纸上，并标明题号。答在试题上无效。第 1 页 共 5 页 / 题号一二三四五六七八九十十一总分分数109724252871030150分答题注意事项：数据结构的答案必须写在计算机原理答案的前面。.数据结构（含高级语言）部分（75分） 一、填空（每空 1 分，共 10 分）1用下标从 0 开始的n个元素的数组实现循环队列时，为实现下标变量m加 1 后，m仍在数组 有效下标范围内，则m= 。2若二元树的一个叶结点是某子树的中根遍历序列中的第一个结点，则它必然

2、是该子树的后 根遍历序列中的 个结点。3对具有 17 个元素有序表A1.17作折半查找，在查找其元素值等于A8的元素时，被比 较的元素下标依次是 。4快速分类的最大和最小递归深度分别是 和 。5外部分类过程主要分为两个阶段： 阶段和 阶段。6已知下面这些字母在某字典中A出现的概率为 0.08，B出现的概率为 0.04，I出现的概率为0.15，C出现的概率是 0.20，E出现的概率是 0.12，F出现的概率是 0.16，R出现的概率是0.15，K出现的概率是 0.10，若采用霍夫曼（Huffman）编码，则E的编码是 （要求 概率小的作为左分支）。7索引文件在存储器上分两个区，分别为 和 。 二

3、、单项选择（每题 1 分，共 9 分）1已知一算术表达式的中缀形式为 a-(b+c/d)*e，其后缀形式为（ ）。A. -a+b*c/dB. -a+b*cd/eC. -+*abc/deD. abcd/+e*-2在解决计算机主机与打印机之间速度不匹配问题时通常设置一个打印数据缓冲区,主机将 数据依次写入缓冲区,而打印机则从缓冲区中取出数据打印,该缓冲区是一个（ ）结构。 A. 栈 B. 队列 C. 线性表 D. 以上都不是3设栈和队列的初始状态为空，元素 e1，e2，e3，e4，e5 和 e6 依次通过栈，一个元素 出栈后即进入队列 Q，若 6 个元素出队的序列是 e2，e4，e3，e6，e5，

4、e1，则栈 S 的容量 至少应该是（ ）。A. 6B. 4C. 3D. 24在下列叙述中，不正确的是（ ）。A. 关键活动不按期完成就会影响整个工程的完成时间。B. 任何一个关键活动提前完成，将使整个工程提前完成。C. 某些关键活动若提前完成，则整个工程提前完成。D. 所有关键活动都提前完成，则整个工程将提前完成。第 2 页 共 5 页5若需在 O(n n)时间内完成对数组的分类，且要求分类是稳定的，则可选择的分类方法是：（ ）A. 快速分类 B. 堆分类 C. 归并分类 D. 插入分类6就分类算法所用的辅助空间而言，堆分类，快速分类和归并分类的关系是（ ）。A. 堆分类快速分类归并分类 B.

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

6、均查找长度而言，分块查找最小，折半查找次之，顺序查找最大。 （ ）2外部分类的 K 路平衡归并，采用选择树法时，归并效率与 K 有关。 （ ）3对于 n 个记录的集合进行归并分类，最坏情况下时间复杂性为 O（n2）。 （ ）4倒排文件与多重表文件的次关键字索引结构不同。（ ）5树的父链表示法其实就是用数组表示树的存储结构。（ ）6在 n 个结点的无向图中，若边数n-1，则该图必是连通图。（ ）7若一个有向图的邻接矩阵中对角线以下元素均为 0，则该图的拓扑有序序列一定存在。（ ）四、简答（每题 8 分，共 24 分）1已知散列函数 hash(k)=k%11，把一个整数值转换成散列表的下标，使用线

7、性探测再散列法 与链地址法构造散列表。分别画出所构造的两种散列表并把数据 1，13，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

8、（指向其后继结点）三个域外，还有一个访问频度域 freq，在链表被起用之前，其值均初 始化为零。每当在链表进行一次 LocateNode（L,x）运算时，令元素值为 x 的结点中 freq 域的值加 1，并调整表中结点的 次序，使其按访问频度的递减序排列，以便使频繁访问的结 点总是靠近表头。试写一符合上述要求的 LocateNode 运算的算法。（9 分）.计算机组成原理部分（共75分）第 3 页 共 5 页六、填空（28 分，每空 1 分）1Cache的命中率是指 A ，命中率与 B 有关。2为了协调 CPU 和 DMA 访问主存的冲突，DMA 与主存交换数据时可采用三种方法，分别是 A 、

9、 B 和 C 。3某计算机采用微程序控制，微指令字中操作控制字段共 12 位，若采用直接控制，则此时 一条微指令最多可同时启动 A 个微操作。若采用字段直接编码控制，并要求一条微 指令需同时启动 3 个微操作，则微指令孚中的操作控制字段应分 B 段。若每个字段 的微命令数相同，这样的微指令格式最多可包含 C 个微操作命令。4利用访存指令与设备交换信息，这在 1/O编址方式中称为 A 。5每个总线部件一般都配有 A 电路，以避免总线访问冲突，当某个部件不占用总线时， 由该电路禁止向总线输出信息。61/O与主机交换信息的控制方式中， A 方式CPU和设备是串行工作的，而 B 和 C 方式CPU和设

10、备是并行工作的，前者传送和主程序是并行进行的，后者传送和主 程序是串行进行的。7如果CPU处于开中断状态，一旦接受了中断请求，CPU就会自动 A ，防止再次接受中 断。同时为了返回程序断点，CPU必须将 B 内容存至 C 中。为了在中断结束后 返回主程序，并且允许接受新的中断，必须 D 和 E 。8依次从控制器、运算器、存储器和 1/O系统四个方面,可采用 A 、 B 、 C 和 D 措施来提高计算机的整机速度。932 位字长的浮点数，其中阶码 8 位（含 1 位阶符），数符 1 位，尾数 23 位，其对应的最大 负数为 A ，最小的绝对值为 B ，若机器数采用补码规格化表示，则对应的最大 负

11、数为 C 。（均用十进制表示）10设指令字长等于存储字长，均为 16 位，若指令系统共有 120 种操作，操作码位数固定， 且具有直接、间接、变址、基址、相对、立即等寻址方式，则直接寻址的最大范围是 A ， 一次间址的范围是 B ，立即数（补码）的范围是 C 。七、选择题（7 分，每题 1 分）1采用DMA方式传送数据时，每传送一个数据要占用 的时间。A一个存取周期； B一个指令周期； C一个机器周期； D一个中断周期。2在程序的执行过程中，Cache与主存的地址映射是由 。A操作系统来管理的； B程序员调度的； C由操作系统和程序员共同协调完成的； D由硬件自动完成的。3存取周期是指 。A存

12、储器的写入时间和读出时间的最小值； B存储器进行连续写操作允许的最短间隔时间； C存储器进行连续读或写操作所允许的最短间隔时间； D以上说法都不对。4下列叙述中 是正确的。A程序中断方式和 DMA 方式中实现数据传送都需中断请求； B程序中断方式中有中断请求，DMA 方式中没有中断请求； C程度中断方式和 DMA 方式中都有中断请求，但目的不同； DDMA 要等指令周期结束时才可进行周期窃取。5下列叙述中 是正确的。 A虚拟存储器实际上就是辅存； B一条指令中可以包含多个操作码；C1/O 接口是负责主存与外设交换信息的部件；D由于定点乘法运算时不会出现溢出，所以浮点乘法运算时也不会出现溢出。6

13、某机指令系统共有 101 种操作，采用微程序控制方式时，控制存储器中相应有 个程 序。A101； B102； C103； D104。7采用变址寻址可扩大寻址范围，且 。 A变址寄存器内容由用户确定，且在程度执行过程中不可变； B变址寄存器内容由操作系统确定，且在程度执行过程中不可变； C变址寄存器内容由用户确定，且在程序执行过程中可变； D变址寄存器内容由操作系统确定，且在程序执行过程中可变。八、简答与计算（10 分，每题 5 分）1总线管理包括哪些内容？简要说明各种管理措施。2设机器数字长为 8 位（含 1 位符号位）。设 A=-11/32，B=95/128，列出竖式计算A-B补。 七、综合

14、题（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 根数据线，并用 作访存控制信号（低电平访存），用 作读写控制信号（高电平为读，低电平为写），存储器按奇偶分体，按字节方式访问。现 有下列芯片：（）74138（）门电路自定（）ROM 芯片 64K8 位； 32K8 位； 32K16 位。（）RAM 芯片 64K