1、哈尔滨工程大学计算机科学与技术学院86计算机专业基础综合自命题数据结构计算机组成原理历年考研目录【数据结构】 52005年哈尔滨工程大学计算机科学与技术学院816数据结构考研真题 52004年哈尔滨工程大学计算机科学与技术学院816数据结构考研真题 102003年哈尔滨工程大学计算机科学与技术学院816数据结构考研真题 132002年哈尔滨工程大学计算机科学与技术学院816数据结构考研真题 162001年哈尔滨工程大学计算机科学与技术学院816数据结构考研真题 18【计算机组成原理】 212008年哈尔滨工程大学计算机科学与技术学院819计算机组成原理考研真题 212005年哈尔滨工程大学计算
2、机科学与技术学院819计算机组成原理考研真题 252004年哈尔滨工程大学计算机科学与技术学院819计算机组成原理考研真题 272003年哈尔滨工程大学计算机科学与技术学院819计算机组成原理考研真题 30说明：2016年公布的专业目录中，科目名称改为“816计算机专业基础综合（自命题数据结构，计算机组成原理）”，本书收录20012008年的真题，以供参考。2004年哈尔滨工程大学计算机科学与技术学院816数据结构考研真题2003年哈尔滨工程大学计算机科学与技术学院816数据结构考研真题哈尔滨工程大学2003年数据结构试题一、判断题(每小题一分，共十分)1数据结构，数据元素，数据项在计算机中的
3、映象（表示）分别称为存储结构，结点，数据域。 对2线性表的逻辑顺序与存储顺序总是一致的。 错3广义表的表头或是元素或是一个广义表，而表尾总是一个广义表。 对4拓扑排序是一种内部排序的算法。 错5字符串是一种特殊的线性表，其特殊性体现在数据元素是一个字符。 对6若线索二叉树有n个结点，则必有n+1条不空的指向树中结点的线索。 错7稀疏矩阵的压缩存储方法一般有三元组和十字链表两种。 对8在AOE网中，一定有不止一条关键路径。 错9二维数组是其数据元素为线性表的线性表。 对10一个栈的输入序列是12345，则输出序列43512是可能的。 错二、单项选择（每小题2分，共20分）1数据结构从逻辑上可以分
4、成 线性和非线性 两种结构。2哈希（Hash）法查找的基本思想是根据 关键字值 来决定记录的存储位置。3利用栈求表达式（A-B）-C）-(D-(E-F),操作数栈须有 4 项。4图的广度优先搜索算法类似于二叉树的 按层 遍历操作。5在所有排序方法中关键字比较次数与记录初始排列次序有关的是 插入排序。6二维数组A的行下标从1到8，列下标从1到10，若每个元素占3个单元，则该数组按“以列序为主序”存放时，A58的起始位置是 1807表达式a*(b+c)-d的后缀表示（逆波兰式）是 abc+*d8在一个具有n个结点的单链表中查找，查找成功时需要平均计较 (n+1)/2 结点。9设Q0n-1为循环队列
5、，front,rear分别为队列的头，尾，则队列中的元素个数为 (rear-front+n) MOD n10在各种查找方法中，平均查找长度与结点个数无关的查找方法是 二叉树查找三、计算题（每小题6分，共30分）1一颗树有N1个度为1的结点，N2个度为2的结点，Nm个度为m的结点，求：该树中终端（叶）结点的个数N02对长度为12的有序表进行折半查找，求查找成功与不成功时各平均比较次数。3已知一颗3阶的B树中含有25个关键字，求该B树的最小高度和最大高度（不包含叶子层）4已知一棵平衡二叉树的深度为6，求树中最少可能的结点数和最多可能的结点数。5对n个结点的平衡二叉树，请分别求出当二叉树具有最小深度
6、K和最大深度K时，第K层上的结点数。四、综合题 （每小题8分，共40分）1广义表A(a),(b,(c,d,e),(),请写出其链式存储结构。设链表中有两类结点，表结点形式为 tag=1 hp tp ,其中指针hp和tp分别指向表头和表尾，元素（原子）结点形式为 tag0 元素值2对关键字序列（49，38，65，97，75，13，27，51，55，10）进行希尔排序。若排序三趟，各趟的增量分别为 d1=5 ,d2=3 ,d3=1 ，则请写出每趟的结果及元素移动次数。3电文中使用字符a,b,c,d,e,f,他们出现的频率为（4,7,5,2,9,8）,请画出对应的编码哈夫曼树，并求出传送电文的总长度
7、。4已知一棵二叉树的中序序列为DAJFBGICEHK，后序序列为DAFBJCIKHEG,请画出该二叉树，并使其成为先序线索树。5对于加权图 12 6 8 15 13 4 16 10 9 20 10 5用克鲁斯卡尔(Kruskal)方法构造最小生成树，并写出选边的次序。五、算法题 （1，2小题各13分，3，4小题各12分，共50分）1 设用二叉链表表示的二叉树不空，其根指针为root，结点形式为：lchild data rchild 请写出将二叉树中所有结点的左，右子树相互交换的非递归算法。2 利用两个栈S1和S2来模拟一个队列。若不存在栈溢出问题，则请写出用栈的操作来实现队列的插入和删除的算法
8、。3 设计一个算法，在长度为n的（小顶）堆R1n中删除一个元素Rs（s=n）产生一个长度为n1的(小顶)堆，并将Rs存放于Rn中。4 假设循环单链表不空，且无表头结点亦无表头指针，指针p指向链表中某结点。请设计一个算法，将p所指节点的前驱结点变为p所指结点的后继结点。答案：三、计算题（每小题6分，共30分） m1n0=1 + (i-1)*ni) i=22查找成功平均比较次数：37/12查找不成功平均比较次数：49/133最小高度：3 最大高度：44最少结点数：20 最多结点数：635最小深度时：n+1-2k-1 最大深度时：1四、综合题（每小题8分，共40分）1111A 11110d0a0c0
9、b2第1趟：13 27 51 55 10 49 38 65 97 76 移动5次 第2趟：13 10 49 38 27 51 55 65 97 76 移动3次 第3趟：10 13 27 38 49 51 55 65 76 97 移动5次3 电文总度：87 0 1 0 1 0 1 0 1 0 1 4 2002年哈尔滨工程大学计算机科学与技术学院816数据结构考研真题哈尔滨工程大学2002年数据结构试题一、填空题 （13分）1数据结构从逻辑上分（线性）结构和（非线性）结构。2若广义表中的每个元素都是（原子），则广义表变成为线性表。3连通图的极小连通子图称为改图的（生成树）。4哈希（hash）法存储
10、的基本思想是根据（关键字）来决定（存储地址）。5迪杰斯特拉算法是按（路径长度递增）次序产生最短路径。6两个字符串相等的充要条件是：两个串的（长度）相等，且（对应位置）的字符相等。7哈夫曼树是叶子节点（带权路径长度）最短的二叉树。8稀疏矩阵一般的压缩方法有两种（三元组表）和（十字链表）。9N个结点的线索树有（n+1）根线索。二、选择题 （12分）1一个栈的入栈序列是a,b,c,d,e,则栈的不可能的输入序列是dceab2深度为h的4阶B-树（根在第一层，叶子在第h层），叶子结点的数目最少为 2h-13广义表(a,b,(c,(d,e) 的尾是 （b,(c,(d,e)）。4具有5层结点的平衡二叉树至
11、少有12个结点。5设二叉树是由森林变换得来的，若森林中有n个非终端结点，则二叉树中无右孩子的结点有n1个。6下列不属于内部排序的算法是BA 归并排序 B 拓扑排序 C 树型排序 D 折半插入排序三、回答问题（20分）1对n个结点的二叉树进行中序遍历，算法中所设的栈，栈中元素最少时可能是多少个？最多时可能是多少个？答：2个 ，n+1个2对n个记录进行简单的插入排序，最少共需要比较多少次？最多共需要比较多少次？答：最少n1次 最多123（n1）次3对13个有序记录进行折半查找，查找成功和不成功的平均查找长度各为多少？4采用上三角压缩存储10阶对称矩阵A，若以行序为主存储，且起始地址为d则A3，8的
12、存储地址为多少？它与以列序为主序存储时的哪一个元素的起始位置一致？答：d24 A4,75设循环队列最大空间为m（0，m1），头，尾指针为front，rear。加入判别队列空的条件是（front1）MODmrear，那么判别队列满的条件是什么？front，rear的初值应是多少？答：frontrear 初值front0rear1四、应用题（25分）1对一组记录的关键字（49，38，66，80，75，19，22）进行快速排序，请写出各趟排序后的状态，并说明总共比较了多少次？2设哈希表的地址空间为06，哈希函数H(K)=K MOD 7。请对关键字序列（32，13，49，18，22，38，21）按链地
13、址法解决冲突的办法构造哈希表。并求出查找成功的平均查找长度。3已知二叉树的左，右子树各含3个结点。试分别构造满足如下要求的二叉树：（1）左子树的先序序列与中序序列相同，右子树的先序序列与中序序列相同。（2）左子树的中序序列与后序序列相同，右子树的先序序列与中序序列相同。4对关键字（67，49，80，14，22，31，95，38，43，56，73）构造平衡二叉树。5请写出表达式a+b*(c-d)-e/f的二叉树表示，并使其成为后序线索树。五、算法题（30分）1设计一算法，在单链表中删除数据元素的值相同的多余结点。2设计一算法，在中序线索树上求指针P所指结点的前驱结点。3将二叉树的结点按层编号（从
14、根还是往下，同层自左至右）。请设计一算法，将该二叉树的结点按编号从小到大顺序输出。设二叉树用二叉链表表示。2001年哈尔滨工程大学计算机科学与技术学院816数据结构考研真题哈尔滨工程大学 2001年数据结构试题一、填空（每空一分，共14分）1数据元素是数据结构的基本单位，数据项是数据的不可分割的最小单位。2深度是k的完全二叉树至少有2（k1）个结点，至多有2k-1个结点。3哈希表的查找效率主要取决于造表时选取的哈希函数和处理冲突的方法。4对100个记录进行折半查找，最多比较7次，最少比较1次。5有n个顶点的无向图，最少有0条边，最多有n(n-1)/2条边。6AOE网中，从源点到汇点的最长路径上
15、的活动叫做关键活动。有环的图不能进行拓扑排序。7对于堆排序，常用的建堆算法是筛选法，堆的形状是一棵完全二叉树。二、判断题（每小题1分，共5分）1线性表的链式存储结构优于顺序存储结构。 错2链表的每个节点中都帢包含一个指针。 错 例如双向链表3栈和队列都是顺序存储结构的线性结构。 错 链栈4若数的度为2时，则该树为二叉树。 错5若广义表中的每个元素都是原子，则广义表为线性表。 对三、问答题（每小题4分，共16分）1一棵3阶4层（根为第一层，叶子为第四层）的B树，至少有多少个关键字，至多有多少个关键字？答：7个 26个2利用栈秋表达式（A-B）-C）-(D-(E-F) 的值，运算符栈和操作数栈各必
16、须具有多少项？答：5项 4项3以行序为主序存储10阶对称矩阵A，采用下三角的压缩存储方式，若起始地址是d，则A85的存储地址是多少？答：32d4设哈希表中以存在无个记录（如图一所示）。哈希函数为H(K)=K MOD 11，用二次探测再散列处理冲突。请问关键字为94的记录的存储地址是多少？ 0 1 2 3 4 5 6 7 8 9 10图一 45 16 39 62 76答：存储地址是 2 四、综合题（每小题5分，共35分）1给定一组权值9，6，14，17，2，15，3，16，请构造哈夫曼树，并计算其带权路径长度。答：带权路径长度1862已知二叉树的先序遍历的结果为ABCDEFGHIJ，中序遍历的结
17、果为CBEDAHGIJF，请画出这颗二叉树。3对图二所示的无向图，（1）请用邻接表表示，且顶点链接按序号从小到大链接。（2）请写出从V0出发的深度优先遍历和广度优先遍历的结果。图二： 0 1 2 3 4 5 6 74 将图三所示的树转换为二叉树，并使其成为后序线索树。图三: A B C D E F G H I J K L MN5 对关键字序列44，12，53，13，37，88，24，61构造一棵平衡二叉树。6 已知一个OE网，如图四所示，求其关键路径，并给出时间4的最迟发生时间和事件5最早发生时间？图四： 1 4 4 12 5 2 6 911 5 100? 9 1814 6 3 5 3 5 7
18、 7 88 7对序列50，77，64，98，39，12，26，48，44，35创建初始堆。五（8分）设指针head 指向无表头结点单链表的首结点。试设一算法，删除链表中值为X的结点，若X结点不存在，则输出“不存在”信息。六（10分）已知一个有向图的邻接表，试编写一个算法求每个结点的出度和入度。七（12分）已知一个二叉树存储于二叉链表中，其结点结构为 lc data rc其中lc和rc分别为指向左子树和右子树根的指针域。试编写一个非递归算法，求二叉树的结点总数及其深度。【计算机组成原理】2008年哈尔滨工程大学计算机科学与技术学院819计算机组成原理考研真题2005年哈尔滨工程大学计算机科学与技
19、术学院819计算机组成原理考研真题哈尔滨工程大学研究生入学考试2005计算机组成原理真题一、判断题（20分）1某浮点机用补码、尾数用原码表示，则判断结果是否为规格化数的方法是：数符与尾数小数点后第1位的数字相异即为规格化数。2由真值求移码的简单方法可以归纳为：对于正数，符号位为1，各数位不变；对于负数，符号位为0，各数位变反后，在末位加1。3常规内存是按地址访问的随机方式，所以不便于信息检索。4由于单地址的运算类指令中只提供一个操作数地址，因此它不能用于双操作数的运算。5双端口存储器之所以能高速地进行读写，是因为采用了两套相互独立的读写电路。6决定计算机计算精度的主要技术指标是计算机的字长。7
20、组成总线不仅要有传输信息的传输线，还应有实现总线传输控制的器件，即总线缓冲器和总线控制器。8I/O设备是处于主机之外的输入/输出设备，所以应为外围设备分配独立的设备码而不能与主存单元统一进行编址。9中断级别最高的中断是不可屏蔽的中断。10一个指令周期由若干工作周期组成，每个工作周期又包含若干时钟周期，由此构成了常用的三级时序系统。二、单选题（20分）1数位每左移1位相当于原数乘以2，为防止左移操作造成溢出，补码左移的前提条件是：其原最高有效位（）。为0 为1 与原符号位相同 与原符号位相异2下列存储设备中，（）的存取数据速度最快。RAM 磁带 光盘 硬盘3原码不恢复余数定点小数除法，要求被除数
21、绝对值小于除数绝对值，其目的是（）。商为规格化小数 商为正数 商不溢出 不必恢复余数4利用分段直接编译法对微指令进行编码时，应将（）微命令归为一组。控制同一部件的 使用频度相近的 相容的 互斥的5某校验码码长为n（有效信息位数冗余位数），合法码字数量为m种，则必有（）。mn mn m2n m2n6条件转移指令执行时，需对（）的内容进行测试。PC PSW IR SP7在定点数运算中产生溢出的原因是（）。运算过程中最高位产生了进位或借位 运算的结果超出了机器的表示范围 参加运算的操作数超出了机器的表示范围 寄存器的位数太少，不得不舍弃最低有效位8下列描述中，不符合RISC指令系统特点是（）。指令长
22、度固定，指令种类少 寻址方式种类尽量减少，指令功能尽可能强 增加寄存器的数目，以尽量减少访存次数 选取使用频率最高的一些简单指令，以及很有用但不复杂的指令9下列不属于微指令结构设计所追求的目标的是（）。提高微程序的执行速度 提高微程序设计的灵活性 缩短微指令的长度 增大控制存储器的容量10中断向量地址是（）。中断源服务程序入口地址 子程序入口地址 中断服务程序入口地址 中断返回地址三、填空题（20分）1在估算加法器运算时间（即加法器速度）时，各位全加器本身的求和延迟并不是主要因素，关键在于 。2浮点加减法的对阶规则是使 对齐。3一个全补码浮点数的格式为：阶符1位，阶码6位；数符1位，尾数8位。
23、则该浮点数所能表示数的范围是 ，分辨率是 。4十进制数183.5的8421BCD码是 ，相应的十六进制数是 。5自底向上生成的堆栈，若栈顶单元是待存元素的空单元，则压入操作时，首先；然后。6I/O设备的编址可分为 和 两种方式。7在计算机系统中，多个系统部件之间信息传送的公共通路称为 。就其所传送的信息的性质而言，在公共通路上传送的信息包括 、和 信息。8DRAM的刷新一般有 、和 三种方式，之所以刷新是因为 。9直接存储器存取（DMA）方式是一种简单中断，而不是 中断。10多体交叉存储技术中，每个存储体均是 编址的。四、简答题（30分）1冯?诺依曼提出的计算机的概念和思想是什么?2奇偶校验码
24、的码距为几?有无纠错能力?查错率能否达到100%，为什么?若偶校验位放在第一位，则7位信息代码0111000的偶校验码是什么?3计算机时序控制方式分为哪两大类?试比较它们的优缺点及应用场合。4中断系统之所以要设定中断优先级，主要是为了解决哪两方面的问题?5高速硬盘与主机之间的信息交换采用程序中断控制方式有何不妥?五、计算题（24分）1某计算机系统的内存储器由Cache和主存构成，Cache的存取周期为45ns，主存的存取周期为200ns。已知在一段给定的时间内，CPU共访问内存4500次，而Cache的未命中率为10%，问：（1）CPU访问Cache和主存各多少次?（2）CPU访问内存的平均时
25、间是多少?（3）Cache主存系统的效率是多少?2已知某计算机的指令字长为16位且按字节编址，其双操作数指令的格式如下：其中OP为操作码，R为通用寄存器地址，试说明在下列各种情况下能访问的最大主存区域为多少字?（1）D为直接操作数；（2）D为直接主存地址；（3）D为间接地址（一次间址）；（4）D为变址的形式地址，假定变址寄存器为R1（字长为16位）。3已知：X2-100.0110，Y2100.1001（除底2以外，其余均是二进制表示）。设在浮点机中，阶码4位（补码表示，含2位符号）；尾数6位（原码表示，含2位符号）。试按照机器的浮点运算步骤，计算X/Y?六、分析题（18分）1如图（a）所示采用
26、不归零1（NRZ1）制写入磁表面存储器的一组信息的电流变化情况，据此分析说明：2004年哈尔滨工程大学计算机科学与技术学院819计算机组成原理考研真题2003年哈尔滨工程大学计算机科学与技术学院819计算机组成原理考研真题哈尔滨工程大学 2003年计算机组成原理试题一、判断题 （每小题1分，共10分）1在用分段直接编译法为微指令编码时，须将互斥微命令归为一组，而将相容命令归为不同组。2定点机不支持浮点运算功能。3子程序技术可以有效降低程序所占资源开销。4中断向量地址指中断服务程序的入口地址。5N位二进制的全码编码系统（即n个“0”至n个“1”）不具备自校验能力。6负数的源码，补码，反码互不相同
27、。7补码数所对应的真值范围在数轴上完全对称于零点。8中断指令作为一种指令，可以用编制程序。9串行进位加法器实际上是一种并行加法器。10大型机不宜采用总线型系统结构。二、填空题（每空1分，共20分）1采用隐式I/O指令系统，须使外围设备的接口寄存器与主存单元_；而采用专用I/O指令系统，则应使外围设备的接口寄存器与主存单元_。2定点整数的字长n只要影响其_指标；而定点小数的字长n主要影响其_指标。3一般而言，一条指令由_字段和_字段两部分组成；而一条指令则由_字段和_字段两部分组成。4奇偶校验校验从功能上看，只具有一定的_功能，而不具有_功能。5在原码两位乘的规则中，需要设置一个_触发器。6各种
28、外围设备均需通过_电路，才能挂接到系统总线上。7在一个三级存储器中，如果访问命中率足够大，则存储系统所表现出的性能将接近于_的容量和_的速度。8在转移型指令中，地址形成部件按指定寻址方式所形成的有效地址是_地址，应将其传送给_。9目的地址单元在执行指令过程中应承但_和_双重任务。10在时序控制方式中，_方式是时序关系比较简单，而_方式的优点是时间利用安排上较为紧凑。三、单项选择 （每小题2分 共20分）1四位机器内的数值代码，它所表示的十进制真值为（ ）（1）9 （2）-1 （3）-7 （4） 以上三者均有可能2常用的分组校验（n，k）码中，冗余位的位数为（ ）位（1）n+k (2) n-k (3) n (4) k3间接寻址第一次访问内存所得到的是操作数的有效地址，该地址经系统总线的（ ）传送到CPU(1) 数据总线 (2) 地址总线 （3）控制总线 （4）总线控制器4下列 （ ）是不合法的BCD码（1）01111001 （2） 11010110 （3）00000100 （4）100001015动态存储器DRAM 的刷新原则是（ ）（1）各DRAM芯片轮流刷新 （2）各DRAM芯片同时刷新，片内逐位刷新（3）各DRAM 芯片同时刷新，片内逐字刷 （4）各DRAM芯片同时刷新，片内逐行刷新6在向上生成（地址码减小方向）
