哈尔滨工程大学计算机科学与技术学院816计算机专业基础综合历年考

1、哈尔滨工程大学计算机科学与技术学院816计算机专业基础综合【数据结构】2005年哈尔滨工程大学计算机科学与技术学院 816数据结构考研真题2004年哈尔滨工程大学计算机科学与技术学院816数据结构考研真题2003年哈尔滨工程大学计算机科学与技术学院816数据结构考研真题2002年哈尔滨工程大学计算机科学与技术学院816数据结构考研真题2001年哈尔滨工程大学计算机科学与技术学院816数据结构考研真题【计算机组成原理】2008年哈尔滨工程大学计算机科学与技术学院 819计算机组成原理考研真题2005年哈尔滨工程大学计算机科学与技术学院819计算机组成原理考研真题2004年哈尔滨工程大学计算机科学

2、与技术学院819计算机组成原理考研真题2003年哈尔滨工程大学计算机科学与技术学院819计算机组成原理考研真题说明：2016年公布的专业目录中，科目名称改为“816计算机专业基础综合（自命题数据结构，计算机组成原理）”，本书收录20012008年的真题，以供参考。2004年哈尔滨工程大学计算机科学与技术学院816数据结构考研真题2003年哈尔滨工程大学计算机科学与技术学院816数据结构考研真题哈尔滨工程大学 2003年数据结构试题一、判断题（每小题一分，共十分）1 数据结构，数据元素，数据项在计算机中的映象（表示）分别称为存储结构，结点，数据域。对2线性表的逻辑顺序与存储顺序总是一致的错3 广

3、义表的表头或是元素或是一-个广义表，而表尾总是一个广义表对4拓扑 排序 是 一种内部 排序的算 法错5 字符串是一种特殊的线性表，其特殊性体现在数据元素是一个字符 对6 若线索二叉树有n个结点，则必有n+1条不空的指向树中结点的线索 错7 稀疏矩阵的压缩存储方法一般有三元组和十字链表两种对8在AOE网中一疋有不止一条关键路径错9 二维数组 是其数据元素为线性表的线性表对10 , 一个栈的输入序列是 12345，则输出序列43512是可能的错二、 单项选择（每小题2分，共20分）1. 数据结构从逻辑上可以分成线性和非线性两种结构。2 哈希（Hash）法查找的基本思想是根据关键字值 来决定记录的存

4、储位置。3 利用栈求表达式（A-B ） -C） -（D-（E-F）,操作数栈须有丄项。4图的广度优先搜索算法类似于二叉树的按层遍历操作。5 在所有排序方法中关键字比较次数与记录初始排列次序有关的是插入排序。6.二维数组A的行下标从1到8,列下标从1到10,若每个元素占3个单元，则该数组按以列序为主序”存放时，A58的起始位置是 1807 表达式a*（b+c）-d的后缀表示（逆波兰式）是 abc+*d 8在一个具有n个结点的单链表中查找，查找成功时需要平均计较（n+1）/2结点。9 .设 Q0 n-1为循环队列，front,rear分别为队列的头，尾，则队列中的元素个数为（rear-fro nt

5、+n） MOD n10 在各种查找方法中，平均查找长度与结点个数无关的查找方法是二叉树查找三、计算题（每小题6分，共30分）1.一颗树有N1个度为1的结点，N2个度为2的结点，Nm个度为m的结点，求：该树中终端（叶）结点的个数 N02对长度为12的有序表进行折半查找，求查找成功与不成功时各平均比较次数。3 已知一颗3阶的B-树中含有25个关键字，求该 B -树的最小高度和最大高度（不包含叶子层）4 已知一棵平衡二叉树的深度为6，求树中最少可能的结点数和最多可能的结点数。5 对n个结点的平衡二叉树，请分别求岀当二叉树具有最小深度K和最大深度 K时，第K层上的结点数。四、综合题（每小题8分，共40

6、分）1广义表 A = （a）,（b,（c,d,e）,（）,请写岀其链式存储结构。设链表中有两类结点，表结点形式为 tag=1 hp tp ,其中指针hp和tp分别指向表头和表尾，元素（原子）结点形式为 tag= 0 元素值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 )，请画岀对应的编码哈夫曼树，并求出传送电文的总长度。4 已知一棵二叉树的中

7、序序列为DAJFBGICEHK，后序序列为 DAFBJCIKHEG,请画岀该二叉树，并使其成为先序线索树。5 对于加权图1268151341610920105用克鲁斯卡尔(Kruskal)方法构造最小生成树，并写岀选边的次序。五、算法题 (1，2小题各13分，3，4小题各12分，共50分)1设用二叉链表表示的二叉树不空，其根指针为root，结点形式为：lchild data rchild请写出将二叉树中所有结点的左，右子树相互交换的非递归算法。2利用两个栈 S1和S2来模拟一个队列。若不存在栈溢岀问题，则请写岀用栈的操作来实现 队列的插入和删除的算法。3设计一个算法，在长度为n的(小顶)堆 R

8、1 n中删除一个元素 Rs ( s<=n)产生个长度为n 1的(小顶)堆，并将Rs存放于Rn中。4假设循环单链表不空，且无表头结点亦无表头指针，指针p指向链表中某结点。请设计一个算法，将p所指节点的前驱结点变为p所指结点的后继结点。答案：三、计算题(每小题6分，共30分)m1 n 0=1 + E (i-1)*n i)i=22 查找成功平均比较次数：37/12查找不成功平均比较次数：49/133 最小高度：3最大高度：4第 2 趟：13104938275155659776 移动 3 次第 3 趟：10132738495155657697 移动5次3.电文总度：870 10 1 010 10

9、14 .2002年哈尔滨工程大学计算机科学与技术学院816数据结构考研真题哈尔滨工程大学 2002年数据结构试题一、填空题 （13分）1 数据结构从逻辑上分（线性）结构和（非线性）结构。2. 若广义表中的每个元素都是（原子），则广义表变成为线性表。3 连通图的极小连通子图称为改图的（生成树）。4. 哈希（hash）法存储的基本思想是根据（关键字）来决定（存储地址）。5 迪杰斯特拉算法是按（路径长度递增）次序产生最短路径。6 两个字符串相等的充要条件是：两个串的（长度）相等，且（对应位置）的字符相等。7 哈夫曼树是叶子节点（带权路径长度）最短的二叉树。8 稀疏矩阵一般的压缩方法有两种（三元组表）

10、和（十字链表）。9. N个结点的线索树有（n+1 ）根线索。二、选择题 （12分）1 .一个栈的入栈序列是a,b,c,d,e，则栈的不可能的输入序列是dceab2 深度为h的4阶B-树（根在第一层，叶子在第h层），叶子结点的数目最少为213 .广义表（a,b,（c,（d,e）的尾是 （b,（c,（d,e）。4 具有5层结点的平衡二叉树至少有12个结点。5 设二叉树是由森林变换得来的，若森林中有n个非终端结点，则二叉树中无右孩子的结点有n+ 1个。6下列不属于内部排序的算法是BA归并排序B拓扑排序C树型排序D折半插入排序三、回答问题（20分）1对n个结点的二叉树进行中序遍历，算法中所设的栈，栈中

11、元素最少时可能是多少个？最 多时可能是多少个？答：2个 ，n+1个2对n个记录进行简单的插入排序，最少共需要比较多少次？最多共需要比较多少次？答：最少n 1次 最多1 + 2+ 3 + （ n1）次3 对13个有序记录进行折半查找，查找成功和不成功的平均查找长度各为多少？4 采用上三角压缩存储10阶对称矩阵 A，若以行序为主存储，且起始地址为d则A3，8的存储地址为多少？它与以列序为主序存储时的哪一个元素的起始位置一致？答：d+ 24.A4,75. 设循环队列最大空间为m （0，m 1），头，尾指针为front，rear。加入判别队列空的条件是（front + 1） MODm = rear，那

12、么判别队列满的条件是什么？front， rear的初值应是多少？答：front = rear 初值 front = 0. rear= 1四、应用题（25分）1 对一组记录的关键字（49，38，66，80，75，19，22）进行快速排序，请写岀各趟排序后 的状态，并说明总共比较了多少次？2 设哈希表的地址空间为0 6,哈希函数 H（K）=K MOD 7 。请对关键字序列 （32，13，49,18，22，38，21）按链地址法解决冲突的办法构造哈希表。并求岀查找成功的平均查找长度。3 已知二叉树的左，右子树各含3个结点。试分别构造满足如下要求的二叉树：（1）左子树的先序序列与中序序列相同，右子树的

13、先序序列与中序序列相同。（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 将二叉树的结点按层编号（从根还是往下，同层自左至右）。请设计一算法，将该二叉树 的结点按编号从小到大顺序输出。设二叉树用二叉链表表示。2001年哈尔滨工程大学计算机科学与技术学院816数据

14、结构考研真题哈尔滨工程大学 2001年数据结构试题一、 填空（每空一分，共14分）1 数据元素是数据结构的基本单位，数据项是数据的不可分割的最小单位。2 深度是k的完全二叉树至少有 2人（k 1）个结点，至多有 2*1个结点。3 哈希表的查找效率主要取决于造表时选取的哈希函数和处理冲突的方法。4 对100个记录进行折半查找，最多比较7次，最少比较 1次。5有n个顶点的无向图，最少有 0条边，最多有n（n-1）/2条边。6. AOE网中，从源点到汇点的最长路径上的活动叫做关键活动。有环的图不能进行拓扌卜排 序。7 对于堆排序，常用的建堆算法是筛选法，堆的形状是一棵完全二叉树。二、判断题（每小题

15、1分，共5分）1 线性表的链式存储结构优于顺序存储结构。错2.链表的每个节点中都帢包含一个指针。错例如双向链表3.栈和队列都是顺序存储结构的线性结构。错链栈4.若数的度为2时，则该树为二叉树。错5.若广义表中的每个元素都是原子，则广义表为线性表。对三、问答题（每小题 4分，共16分）1 一棵3阶4层（根为第一层，叶子为第四层）的 B 树，至少有多少个关键字，至多有多 少个关键字？答：7个26个2 利用栈秋表达式（A-B ） -C） -（D-（E-F）的值，运算符栈和操作数栈各必须具有多少项？答：5项4项3 以行序为主序存储10阶对称矩阵 A，采用下三角的压缩存储方式，若起始地址是d，则A85的

16、存储地址是多少？答：32+ d4 设哈希表中以存在无个记录（如图一所示）。哈希函数为 H（K）=K MOD 11 ，用二次探测再散列处理冲突。请问关键字为94的记录的存储地址是多少？012345678910匚储地址是45216 :旧6276四、综合题（每小题5分，共35分）1 给定一组权值9，6，14，17，2，15，3，16，请构造哈夫曼树，并计算其带权路径长 度。答：带权路径长度1862 已知二叉树的先序遍历的结果为ABCDEFGHIJ，中序遍历的结果为 CBEDAHGIJF，请画出这颗二叉树。3对图二所示的无向图，（1 ）请用邻接表表示，且顶点链接按序号从小到大链接。（2）请写岀从 V0

17、岀发的深度优先遍历和广度优先遍历的结果。 图二：5对关键字序列44 , 12, 53,6已知一个OE网，如图四所示, 时间？图四：N88, 24,求其关键路径，13, 37,61构造一棵平衡二叉树。 并给出时间4的最迟发生时间和事件5最早发生451110146358'算法求每个结57卩始堆。法，删除链表中值为98, 39, 12结点单,则输出“不存在”信息邻接表，试编写8,4o?457 对序列50 ,五（8分）设指 结点，若X结点不六（10分）已知一个有向77,64,4,35创建初试设一算七（ 12分）已知一个二叉树存储。试编写一个叉链表中，其结点结构为勺出度和入度。lc datarc

18、其中lc和rc分别为指向左子树和右子树 非递归算法，求二叉树的结点总数及其深度。【计算机组成原理】2008年哈尔滨工程大学计算机科学与技术学院 819计算机组成原理考研真题2005年哈尔滨工程大学计算机科学与技术学院819计算机组成原理考研真题哈尔滨工程大学研究生入学考试2005计算机组成原理真题一、判断题（20分）1某浮点机用补码、尾数用原码表示，则判断结果是否为规格化数的方法是：数符与尾数 小数点后第1位的数字相异即为规格化数。2由真值求移码的简单方法可以归纳为：对于正数，符号位为1,各数位不变；对于负数，符号位为0,各数位变反后，在末位加1。3常规内存是按地址访问的随机方式，所以不便于信

19、息检索。4由于单地址的运算类指令中只提供一个操作数地址，因此它不能用于双操作数的运算。5双端口存储器之所以能高速地进行读写，是因为采用了两套相互独立的读写电路。6 决定计算机计算精度的主要技术指标是计算机的字长。7组成总线不仅要有传输信息的传输线，还应有实现总线传输控制的器件，即总线缓冲器 和总线控制器。8. I/O设备是处于主机之外的输入/输岀设备，所以应为外围设备分配独立的设备码而不能与 主存单元统一进行编址。9. 中断级别最高的中断是不可屏蔽的中断。10一个指令周期由若干工作周期组成，每个工作周期又包含若干时钟周期，由此构成了常 用的三级时序系统。二、单选题（20分）1 数位每左移1位相

20、当于原数乘以 2,为防止左移操作造成溢岀，补码左移的前提条件是： 其原最高有效位（）。为0为1与原符号位相同 与原符号位相异2下列存储设备中，（）的存取数据速度最快。RAM 磁带 光盘 硬盘3原码不恢复余数定点小数除法，要求被除数绝对值小于除数绝对值，其目的是（）。商为规格化小数商为正数商不溢岀不必恢复余数4利用分段直接编译法对微指令进行编码时，应将（）微命令归为一组。控制同一部件的 使用频度相近的相容的互斥的5. 某校验码码长为 n （有效信息位数+冗余位数），合法码字数量为m种，则必有（）。m > n m v n m > 2n m v 2n6条件转移指令执行时，需对（）的内容进

21、行测试。PC PSW IR SP7在定点数运算中产生溢岀的原因是（）。运算过程中最高位产生了进位或借位运算的结果超出了机器的表示范围参加运算的操作数超出了机器的表示范围寄存器的位数太少，不得不舍弃最低有效位8下列描述中，不符合RISC指令系统特点是（）。指令长度固定，指令种类少寻址方式种类尽量减少，指令功能尽可能强增加寄存器的数目，以尽量减少访存次数选取使用频率最高的一些简单指令，以及很有用但不复杂的指令9下列不属于微指令结构设计所追求的目标的是（）。提高微程序的执行速度提高微程序设计的灵活性缩短微指令的长度 增大控制存储器的容量10中断向量地址是（）。中断源服务程序入口地址子程序入口地址 中

22、断服务程序入口地址中断返回地址三、填空题（20分）1 在估算加法器运算时间（即加法器速度）时，各位全加器本身的求和延迟并不是主要因 素，关键在于 。2 浮点加减法的对阶规则是使对齐。3一个全补码浮点数的格式为：阶符1位，阶码6位；数符1位，尾数8位。则该浮点数所能表示数的范围是，分辨率是。4十进制数183.5的8421BCD码是，相应的十六进制数是。5 .自底向上生成的堆栈，若栈顶单元是待存元素的空单元，则压入操作时，首先；然后。6. I/O设备的编址可分为和 两种方式。7 在计算机系统中，多个系统部件之间信息传送的公共通路称为。就其所传送的信息的性质而言，在公共通路上传送的信息包括、和 信息

23、。8. DRAM的刷新一般有 、和三种方式，之所以刷新是因为。9直接存储器存取（DMA ）方式是一种简单中断，而不是中断。10. 多体交叉存储技术中，每个存储体均是编址的。四、简答题（30分）1冯？诺依曼提岀的计算机的概念和思想是什么？2奇偶校验码的码距为几？有无纠错能力？查错率能否达到100%，为什么？若偶校验位放在第一位，则7位信息代码0111000的偶校验码是什么 ？3 计算机时序控制方式分为哪两大类？试比较它们的优缺点及应用场合。4中断系统之所以要设定中断优先级，主要是为了解决哪两方面的问题？5 高速硬盘与主机之间的信息交换采用程序中断控制方式有何不妥？五、计算题（24分）1. 某计算

24、机系统的内存储器由 Cache和主存构成，Cache的存取周期为45ns，主存的存取周 期为200ns。已知在一段给定的时间内， CPU共访问内存4500次，而Cache的未命中率为10%， 问：（1）CPU访问Cache和主存各多少次 ？（2） CPU访问内存的平均时间是多少 ？（3）Cache主存系统的效率是多少 ？2 已知某计算机的指令字长为16位且按字节编址，其双操作数指令的格式如下：其中0P为操作码，R为通用寄存器地址，试说明在下列各种情况下能访问的最大主存区域为 多少字？（1）D为直接操作数；（2）D为直接主存地址；（3）D为间接地址（一次间址）；（4） D为变址的形式地址，假定变

25、址寄存器为R1 （字长为16位）。3已知：X = 2-10 >0.0110，Y = 210X0.1001 （除底2以外，其余均是二进制表示）。设在浮点机中，阶码4位（补码表示，含 2位符号）；尾数 6位（原码表示，含 2位符号）。试按照机器 的浮点运算步骤，计算X/Y = ?六、分析题（18分）1 如图（a）所示采用不归零一1 （ NRZ1 ）制写入磁表面存储器的一组信息的电流变化情况， 据此分析说明：2004年哈尔滨工程大学计算机科学与技术学院819计算机组成原理考研真题2003年哈尔滨工程大学计算机科学与技术学院819计算机组成原理考研真题哈尔滨工程大学 2003年计算机组成原理试题

26、一、判断题(每小题1分，共10分)1 在用分段直接编译法为微指令编码时，须将互斥微命令归为一组，而将相容命令归为不 同组。2. 定点机不支持浮点运算功能。3 子程序技术可以有效降低程序所占资源开销。4中断向量地址指中断服务程序的入口地址。5. N位二进制的全码编码系统(即 n个“0”至n个“ 1”)不具备自校验能力。6 负数的源码，补码，反码互不相同。7 补码数所对应的真值范围在数轴上完全对称于零点。8 中断指令作为一种指令，可以用编制程序。9 串行进位加法器实际上是一种并行加法器。10 大型机不宜采用总线型系统结构。二、填空题(每空 1分，共20分)1 采用隐式I/O指令系统，须使外围设备的

27、接口寄存器与主存单元 ;而采用专用I/O指令系统，则应使外围设备的接口寄存器与主存单元 。2 定点整数的字长 n只要影响其 指标；而定点小数的字长n主要影响其 指标。3 一般而言，一条指令由 字段和字段两部分组成；而一条指令则由 字段和字段两部分组成。4 奇偶校验校验从功能上看，只具有一定的 功能，而不具有 功能。5 在原码两位乘的规则中，需要设置一个 触发器。6 各种外围设备均需通过 电路，才能挂接到系统总线上。7在一个三级存储器中，如果访问命中率足够大，则存储系统所表现岀的性能将接近于的容量和的速度。8 在转移型指令中，地址形成部件按指定寻址方式所形成的有效地址是地址，应将其传送给。9 目

28、的地址单元在执行指令过程中应承但 和双重任务。10.在时序控制方式中， 方式是时序关系比较简单，而 方式的优点是时间利用安排上较为紧凑。三、 单项选择(每小题2分 共20分)1 四位机器内的数值代码，它所表示的十进制真值为()(1) 9(2) -1 ( 3) -7 (4) 以上三者均有可能2 常用的分组校验(n , k)码中，冗余位的位数为( )位(1) n+k (2) n-k (3) n Wk3 间接寻址第一次访问内存所得到的是操作数的有效地址，该地址经系统总线的()传送至U CPU(1)数据总线 (2)地址总线(3)控制总线(4)总线控制器4 下列()是不合法的 BCD码(1) 0111

29、1001(2) 1101 0110(3) 0000 . 0100 .( 4) 1000. 01015 动态存储器DRAM 的刷新原则是()(1)各DRAM芯片轮流刷新(2)各DRAM芯片同时刷新，片内逐位刷新(3) 各DRAM 芯片同时刷新，片内逐字刷(4)各DRAM芯片同时刷新，片内逐行刷新6 在向上生成(地址码减小方向)堆栈中，若约定为实顶栈(即堆栈指针随时指向实有数据的堆顶)，则正确的弹出数据操作为()(1)先使(SP) +1,再读岀数据(2)先读岀数据，再使(SP) + 1(3)先使(SP) -1再读岀数据(4)先读岀数据，再使(SP) 17. ()不是常用三级时序系统中的一级(1)指令周期(2) 工作周期 (3)时钟周期(4)定时脉冲8. ()存储结构对程序员是透明的(1)通用寄存器(2)主存 (3)控制寄存器(4)堆栈9 相对寻址方式中，指令所提供的相对地址实质上是一种()(1)立即数(2 )内存地址(3)以本条指令在存中首地址为基准位置的偏移量(4) 以下指令在存中首地址为基准位置的偏移量10.程序状态字 PSW中一般设