哈尔滨工程大学计算机科学与技术学院计算机专业基础综合自命题数据结构计算机组成原理历年考研真题汇

1、第1页哈尔滨工程大学计算机科学与技术学院816计算机专业基础综合（自命题数据结构，计算机组成原理）历年考研真题汇编最新资料，WORD 格式，可编辑修改!【数据结.错误!未定义书签第2页2004 年哈尔滨工程大学计算机科学与技术学院816 数据结构考研真题 .9.2003年哈尔滨工程大学计算机科学与技术学院816 数据结构考研真题 . 132002 年哈尔滨工程大学计算机科学与技术学院816 数据结构考研真题. 172001 年哈尔滨工程大学计算机科学与技术学院816 数据结构考研真题. 19【计算机组成原理】 .232008 年哈尔滨工程大学计算机科学与技术学院819 计算机组成原理考研真题.

2、232005 年哈尔滨工程大学计算机科学与技术学院819 计算机组成原理考研真题.282004 年哈尔滨工程大学计算机科学与技术学院819 计算机组成原理考研真题.312003 年哈尔滨工程大学计算机科学与技术学院819 计算机组成原理考研真题.35说明：2016 年公布的专业目录中，科目名称改为“ 816 计算机专业基础综合（自命题数据结 构，计算机组成原理）”，本书收录20012008 年的真题，以供参考。2005 年哈尔滨工程大学计算机科学与技术学院816 数据结构考研真题.错误!未定义书签第3页哈尔滨工程大学 2005 年数据结构考研试题一. 判断题毎小醫1分.共1D分1.苦 个Iff

3、憩中的痔句攧宦之和为T(n) =1024n+4ntogn,则算法的时间复朵度为0 (nlogn)2.串是种耕殊的线性3.两个找共李一个向号空问的优点定其中一个找 E 用谄空何一丁威一半以上4.广文表是II线件姻结构+因为我屮的兀索可以是子表5.:叉讲的中序序列中，结点A在结点B之陥的务件足AAlBKf祖先*6.苦个有向帕的押抻措序沒有包拱仝部顶点則说明该闾存任有向冋賂”7.貝冉儿个顶鱼条边的尢向图，若用邻按紙阵作为行皓紹构，I则求任一顼点的厦数的 时间复朶度为0(& 呛希法既址 种査找力法，又旻 供存储方法臥9希尔非用壯属于捆入寸I疗啲改进力法.10-在单色涯上町以实观葡笊选择排序.征

4、以丈现堆选弄)排轨二. 填空題I每小題2分共20分1.在宁符串-Structure中，以t为首字符的了串有_个.2.N阶的卜角阵战行序为丄序存陽每个朮黍 4L个尊元.若U知首迪址为iOc(A00 ),则疋素Aij(OWJWiWn-l)的存储哋址kx (Aij为_ .3C知一个栈的入找序列是b 2* 3,九其输出序列Pl* P2, P3, PH*若Pl=n.则Pi为_ .4乙知广义善L5= b,cfd), e)运用hed fllEl曲哉取出LS中的帝子b的运亀定_ 乩 在一慄具有h层的满一叉梢中，箱点总敎为_ “& 己储瓷一慄會梧门亍姑点的树 5、只含度为3和度为0的结点*MJM I1度

5、为0的結点 数为 .呱听众叶了瑕个结方10貉构30m+r)的绘点B B丛迪猖上町以把数摇站枸分成就态和静态紧凄和|紧變 统性抑非绒性内部和护部瑤M0牛记录分成5坎进行芬块杳找半竭廿找底交是的顒宇循坏肽列呻，front fn rear分别拾示仏莒和仏尾*判断臥処菇的叉树第 4 页将长度为n的单誹表莊覆在怪涯舟m的单蜓袤之拓的法的时何 fe 朶度为1（1）占 设齐更知玄门牛结点则別于mwm不可能存在 亍变为0& 在含有20个吴桂字的4附B书中进行直找.至欹访问&菜口0亍給点的，灵时的先用序列疋好和反*则谏叉树定不址A.任一结点无左撷子B-任一結点无右按子9将 E 个互为冲宪（貝舟相

6、同的哈帑地址）的记录存入哈希表,处舞冲突采用伪蘭机探 眦沈虽多需焼探鼬_机.7-设制T的度为去 其中度为1. 2生4的结点禍分射为4为*4.股度为n (1n的条件为_ -单注題t每小程2分，rt30分）第5页U 深3T为riD.存在度为2的紹点7.二义树用二臾链表表朮.若吏将扎所有姑.也的石*右子嗣相兀交換位置则兼舟下列 爲历的方法较为件适A-先用氐屮序U 后序D.枝泾8.对r二更网的两个結点X fll Y,应该选弄一两个序列來畀IfiiX星否曲祖先.A.先用和后丿节&先序刖中序U 中宇和后序D.任意两个序列都行9.最小主成桶描的是连通附中_ A.边救0少的生成剂B顶点相对技少的牛成禅

7、U 极小连逊子年D.所有生成持中权值之和id小的生成榭10.具有nm点的强连谊图至少有_ 董弧.A* n-1B.nU 2nDrn cn-1)11.对20个有序记录进行折半査找，査找战功的平均査找怅度为_ ,A. 5民37/10C 39/10D 411012.哈曲粳也度为 E 哈榕函数H K) =K%P.圾*说P应取小丁m的Jg玄_A.奇数B.鳩数匕盍数D.合数13.对幼杰奁找有鬲效率的査找袁殂飯结枸是_A,有斥衣B.分块育序表U 韬坏锂表第6页D B-W14.当初始数据育乍时不庙采用_*A+堆排序B+怏速排序C,基数序D.希尔推序15.在T1个丘常中找已两个显小的元索当门很左时.釆用_ 力法比

8、麓次数校少.A.材塑选择排序B*简单逸择博序U HOWD.快遽排Jf四.繚舍題（每小題10分*共40分）i+一機二艮树的先序*中石序序姚分别如卜：it中育戢分结点*显示出来） 先序序列，&_F_ICEH_G屮序序列*D _KFIA_EJC_后宇岸外_K_FBHJ,G_A1+将光I件 中帀，后用序列窕整写亦来.2X曲出该二艾树.2”对关谜字序列hnFebMaGApMayLineuiyjAugSeprOctpNov,Dec（1）-枸邀一操平術二义（掙厢）M勺2打求ttSftJft功的平均査找长度ASL3-对尤向加权图:：1）用驚里婢爲链从顶点出发求K最小牛成榊，并劉出施点顺序用ftfija

9、i k；j算法求其蚤小主战虬 川吗岀逸边,顷序4.給出的3附第7页（1L写出对给出的次描人关雉爭2弘25- 84. 6馬的B树.4）.写出对络出的B-埠依次剧侏关鍵字1仁49, S2* 36 t的B树”乩 算沆题f第b 2. 3题各12分，第4 14分，共50分）1対用.叉琏衣衣示的又岗，设讣个算袪，求梵脣斥厅列旳第个络点2一克仝二更側噸序存站机数纽A1n中，请右一算法：求卜标A I fiij的两个诙点的所 有公战根先结点.井按下标从人訓小的撕闻将它们前值打印出来.事I3-长1度为n的字符串存囂住绪点大小为1的单琏表中，试弓一算法.丸断字笹串足否中心 对称例如*abccba*兄中心对称人4.

10、C知一棵满二叉树腹序存緒奁数组B1n中，谏计一个算沈.产主二更诃前二更进董第8页第9页氐 M 翕壬雷药容2004 年哈尔滨工程大学计算机科学与技术学院816 数据结构考研真题第10rr阀.饶亠可鼻勺讪MfPt讥苕竺L年招收研究生入学考试试题共3页鄭】页 科目名称：数据结构试題编号：439本试的符案裁殖写在規崔的答JS卡成答愿水上.写在卓祥上无效.I6河历二叉树的护述畀溥法.可以用找件列助穿他.也可烘用欧列作舗助莖何:匸匸无向图的翠按呂籲左我承比邻接农农示H看的Ws空间.7& “拓扑排序舜法中&入度为*的顶点町以用tft.也可以用从列/ 也顺序盘找氏厦为n的线性表，英平均件找长度

11、大任何-稷门个结卢的二义 排序树的平均誉找长度爪也廉定的搏用方法优于不昆定的朴序方法.这是因为粉定的扌时执辻倉高*二. 離攻选祥變(毎小愿2扎共20分)r1*數据结构4UI青_的敌据无家的裳合/扎性质相间B.特定关系G相互关系D.敵韬顼2毆那仔储线性农的插入諒法中， 当H个咬间己斎时*可申谜再増側分配血个空側若屮请先戏*则说明系册没有_可井IK仔储空他儿尬个Bm个连续的C* n + m个D, n + m个*连挨的卜五节车期以嵋号1. 2. 3.人5M2入铁昭调度鮎().可以得虬_0 也匕 h. 34612L曹:义衣L心bX (c.d)hHead ft Tail别为对广文我的取头和脱思 操作.J

12、 Tail HeadTai|Lj的结果是_鸟鸟K bB-dc. d)D. n一判欲世(正确的打心皤谀的打江，毎小翹1分衣共泊分)|】数撫的构是用户機便用需赛而建立的与实际的钿雇式无关M二顺顺库库书书側側址址桂桂零零求求连续陆存储区域在存赫骨理上不够灵活.闵此K常用73-忙琏駅弭中除了队头WMt还必须设ftSSffifr.沖則无法进行典列的的扌扌: :入it作 24申订符优先法求去达式的值，应设阿个工作栈”分别用来普存操件蛙和远匕字苻弗既小处线性站构.也不地松线性铭构*它绘一神特睞的如側构旷5. 24135 C 35421D. 13521第11扎M2乩前不字釈 fi 码 2r、”A. 2用两种不

13、同的方法构造图的绘小生战列.选边的顺序打逸点时输出边的 -年同.所得到的绘小生成轲_匕，“V lifflIKJfttj B.住不阿的C.可能足相同/njf|E&dDHIk不同的A? JKfna字的鼻阶B W- 4：一一个叶子(宜找不成功：结血AA.n * 1B. n*lC n*nD.pn/2|*ri.0.当-组特JI记锻已经有序时.使用快瑞挥序时的效奉与排序相囤A.选样0C归井必希尔久计黨曲分共30分)対仃堺农进行鮒睜僧找I?济中设矍监 ftw.请分别求出咋概率卅 僅找成功和不璇功时的平均.将二对诽砌岸 如 的 亲对他线匕的兀索逐卑存于数组Al-J( |b ftAEUCl和A3n为空.

14、A(uv au，诫给出山管的下卿 (用i. j来表示片L己知一棵弓阶1出(根为3ft 1 W.叶F为笫4定的 玄少料多4 IK字？至多有多少个关憶字？L杠n个结点的二叉树进行垢序遍历芳在與法中使用則栈中多中 少強？堆少时有多少项？L对长桂为丁的有序农进行折半査我的芳比牧爭少次？査找失败的平E次載为爭少？, 综合腔C毎小眩8分.共机分已般一个农达式的15绍展示为abed *-ef/-.谓页出该表达式的二叉ftP按-以屮”J r存伽IB A的廿地址为_0A go& 72C 120U 150轉聊孩子兄弟袈示法每乍錯点询购个播针城分别折向粥一个孩子 刊下一个兄弟二若捋向“卜个兄弟的ffittY

15、f菲终須第点*EnDn + 1.显侯2編码的长电年趙过几若已对两个字符编码为1和o】刪还可 对个丫捋编码 2I*A, 2第12之先序线責化2对关键字环列(41, 40 66IX 70. 60. 55, 22, 99- 88. 77. 33)平會二Jtit.3设吩希(Hash)为11 0-10)呛常前数为K MOD U.社理冲 姑机掇测叫敢列法.竹个的机数为九请依次梅序列W弘 d 九30XL、MA J4 I tin第13从ISAdtfl发*用普甲禺(Prim)算法求出最小生脚.井写出选点 的次序E. 克法邃(35 1小題16分2、3小JS各17分共50分)I.设口个结点的二叉轲用两个一織敷组L卜

16、叩奉R【l-fJ存為存為IJklffiRW分别播示结点k前左孩子和右搂子0农示空试弓一个算法判别结点u腿皆足结点v的子孙*2.设计 个算法，对带裟头结点的非空双脚链袤*用简怖插入拆序的AWo ft 1C按结点从卜覚氏金援设结山形式为I叭诃壮rxxL为head.婴求作结点的插入而不蜓交域的值父设-棵非空的】叉掛序树用二叉链衣农bt为tttJftet, K7r.7R的结点林小丁右f树的站点请芻一评法，从小到大输出所科大于冥的叶子结点.结艾3页第3 51前关K字序列(48. 39. 66, 87P75. 12* 28, 52 . 56fL0, 23)创建初始 (小顶)堆*対給出比较次数和空換次數.5

17、.对无向加权用ilchilddata, rchl Id点形式为:P第142003 年哈尔滨工程大学计算机科学与技术学院 816 数据结构考研真题哈尔滨工程大学 2003 年数据结构试题一、判断题（每小题一分，共十分）1 数据结构，数据元素，数据项在计算机中的映象（表示）分别称为存储结构，结点，数据域。对2 线性表的逻辑顺序与存储顺序总是一致的。错3 .广义表的表头或是兀素或是一个广义表，而表尾总是一个广义表。对4 .拓扑排序是一种内部排序的算法。错5 .字符串是一种特殊的线性表，其特殊性体现在数据元素是一个字符。对6 .若线索二叉树有 n 个结点，则必有 n+1 条不空的指向树中结点的线索。错

18、7 .稀疏矩阵的压缩存储方法一般有三元组和十字链表两种。对8 .在 AOE 网中，一定有不止一条关键路径。错9 .二维数组是其数据元素为线性表的线性表。对10 .一个栈的输入序列是 12345，则输出序列 43512 是可能的。错二、单项选择（每小题 2 分，共 20 分）1 .数据结构从逻辑上可以分成 线性和非线性 两种结构。2 .哈希（Hash ）法查找的基本思想是根据 关键字值 来决定记录的存储位置。3 .利用栈求表达式（A-B ） -C） -（D-（E-F）,操作数栈须有_4_项。4 .图的广度优先搜索算法类似于二叉树的按层 遍历操作。5 .在所有排序方法中关键字比较次数与记录初始排列

19、次序有关的是插入排序。6 .二维数组 A 的行下标从 1 到 8，列下标从 1 到 10，若每个元素占 3 个单元，则该数组按第15以列序为主序”存放时，A58的起始位置是1807 表达式 a*(b+c)-d 的后缀表示(逆波兰式)是 abc+*d 8 在一个具有 n 个结点的单链表中查找，查找成功时需要平均计较(n+1)/2 结点。9 .设 Q0 n-1为循环队列，front,rear 分别为队列的头，尾，则队列中的元素个数为 (rear-fr ont+n)MOD n10 .在各种查找方法中，平均查找长度与结点个数无关的查找方法是二叉树查找三、计算题(每小题 6 分，共 30 分)1 .一颗

20、树有 N1 个度为 1 的结点，N2 个度为 2 的结点.，Nm 个度为 m 的结点，求：该树中终端(叶)结点的个数 N02 .对长度为 12 的有序表进行折半查找，求查找成功与不成功时各平均比较次数。3 .已知一颗 3 阶的 B-树中含有 25 个关键字，求该 B-树的最小高度和最大高度(不包含叶 子层)4 .已知一棵平衡二叉树的深度为 6，求树中最少可能的结点数和最多可能的结点数。5 .对 n 个结点的平衡二叉树，请分别求出当二叉树具有最小深度K 和最大深度 K 时，第 K 层上的结点数。四、综合题(每小题 8 分，共 40 分)1 .广义表 A = (a),(b,(c,d,e),(),请

21、写出其链式存储结构。设链表中有两类结点，表结点形式为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 .已知一棵二叉树的中序序列为 DAJFBGICEHK，后序序列为 DAFBJCIKHEG,请画

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

23、=n ）产生一个长度为 n 1 的（小顶）堆，并将 Rs存放于 Rn中。4 假设循环单链表不空，且无表头结点亦无表头指针，指针p 指向链表中某结点。请设计一个算法，将 p 所指节点的前驱结点变为 p 所指结点的后继结点。答案：三、计算题（每小题 6 分，共 30 分）m1 . n0=1 + 刀（i-1）*ni）i=22 .查找成功平均比较次数：37/12查找不成功平均比较次数：49/133 .最小高度：3最大高度：44 .最少结点数：20最多结点数：635 .最小深度时：n+1-2k-1最大深度时：1 四、综合题（每小题 8 分，共 40 分）E E n第170d2 .第 1 趟：132751

24、55104938659776移动 5 次第 2 趟： 13104938275155659776移动 3 次第 3 趟： 10132738495155657697移动 5 次电文总度：87第182002 年哈尔滨工程大学计算机科学与技术学院816 数据结构考研真题哈尔滨工程大学 2002 年数据结构试题一、填空题 （13 分）1 数据结构从逻辑上分（线性）结构和（非线性）结构。2 若广义表中的每个元素都是（原子），则广义表变成为线性表。3 连通图的极小连通子图称为改图的（生成树）。4 .哈希（hash ）法存储的基本思想是根据（关键字）来决定（存储地址）。5 迪杰斯特拉算法是按（路径长度递增）次

25、序产生最短路径。6 两个字符串相等的充要条件是：两个串的（长度）相等，且（对应位置）的字符相等。7 哈夫曼树是叶子节点（带权路径长度）最短的二叉树。8 稀疏矩阵一般的压缩方法有两种（三元组表）和（十字链表）。9 N 个结点的线索树有（n+1 ）根线索。二、选择题 （12 分）1一个栈的入栈序列是 a,b,c,d,e,则栈的不可能的输入序列是 dceab2 深度为 h 的 4 阶 B-树（根在第一层，叶子在第 h 层），叶子结点的数目最少为 2F-13 广义表（a,b,（c,（d,e）的尾是 （b,（c,（d,e）。4 具有 5 层结点的平衡二叉树至少有 12 个结点。5 设二叉树是由森林变换得

26、来的，若森林中有n 个非终端结点，则二叉树中无右孩子的结点有n +1 个。6下列不属于内部排序的算法是旦A 归并排序旦拓扑排序C 树型排序D 折半插入排序三、回答问题（20 分）1对 n 个结点的二叉树进行中序遍历，算法中所设的栈，栈中元素最少时可能是多少个？最多 时可能是多少个？答：2 个，n+1 个第192对 n 个记录进行简单的插入排序，最少共需要比较多少次？最多共需要比较多少次？答：最少 n 1 次 最多 1 + 2 + 3. +（1 1）次第203对 13 个有序记录进行折半查找，查找成功和不成功的平均查找长度各为多少?4 采用上三角压缩存储 10 阶对称矩阵 A，若以行序为主存储，

27、且起始地址为 d 则 A3 , 8 的存 储地址为多少？它与以列序为主序存储时的哪一个元素的起始位置一致？答：d + 24 .A4,75 .设循环队列最大空间为 m （0，m 1），头，尾指针为 front , rear。加入判别队列空 的条件是（front + 1） MODm = rear，那么判别队列满的条件是什么？ front ，rear 的初值应是多 少？答：front = rear 初值 front = 0. rear = 1四、应用题（25 分）1 .对一组记录的关键字（49，38，66，80，75，19，22 ）进行快速排序，请写出各趟排序后 的状态，并说明总共比较了多少次？2

28、.设哈希表的地址空间为 0 6，哈希函数 H（K）=K MOD 7。请对关键字序列（32，13， 49，18，22，38，21）按链地址法解决冲突的办法构造哈希表。并求出查找成功的平均查找长度。3 .已知二叉树的左，右子树各含 3 个结点。试分别构造满足如下要求的二叉树：（1）左子树 的先序序列与中序序列相同，右子树的先序序列与中序序列相同。（ 2）左子树的中序序列与后序序 列相同，右子树的先序序列与中序序列相同。4 .对关键字（67，49，80，14，22，31，95，38，43，56，73）构造平衡二叉树。5 .请写出表达式 a+b*（c-d）-e/f 的二叉树表示，并使其成为后序线索树。

29、五、算法题（30 分）1 .设计一算法，在单链表中删除数据元素的值相同的多余结点。2 .设计一算法，在中序线索树上求指针P 所指结点的前驱结点。3 .将二叉树的结点按层编号（从根还是往下，同层自左至右）。请设计一算法，将该二叉树的 结点按编号从小到大顺序输出。设二叉树用二叉链表表示。第21哈尔滨工程大学 2001 年数据结构试题一、填空（每空一分，共 14 分）1 数据元素是数据结构的基本单位，数据项是数据的不可分割的最小单位。2 .深度是 k 的完全二叉树至少有 2 八（k 1）个结点，至多有 2*1 个结点。3 .哈希表的查找效率主要取决于造表时选取的哈希函数和处理冲突的方法。4 .对 1

30、00 个记录进行折半查找，最多比较 7 次，最少比较 1 次。5 .有 n 个顶点的无向图，最少有 匕条边，最多有 n（n-1）/2 条边。6 . AOE 网中，从源点到汇点的最长路径上的活动叫做关键活动。有环的图不能进行拓扑排序。7 .对于堆排序，常用的建堆算法是筛选法，堆的形状是一棵完全二叉树。二、判断题（每小题 1 分，共 5 分）1 .线性表的链式存储结构优于顺序存储结构。2 .链表的每个节点中都帢包含一个指针。错错例如双向链表3 .栈和队列都是顺序存储结构的线性结构。错链栈4 .若数的度为 2 时，则该树为二叉树。错5 .若广义表中的母个兀素都是原子，则广义表为线性表。对三、问答题（

31、每小题 4 分，共 16 分）1 .一棵 3 阶 4 层（根为第一层，叶子为第四层）的 个关键字？答：7 个26 个2 .利用栈秋表达式（A-B ） -C） -（D-（E-F）的值，运算符栈和操作数栈各必须具有多少项？答：5 项4 项3 .以行序为主序存储 10 阶对称矩阵 A，采用下三角的压缩存储方式，若起始地址是 d，则 A85 的存储地址是多少？答: 32 + d4 .设哈希表中以存在无个记录（如图一所示）。哈希函数为 H（K）=K MOD 11 ，用二次探测再 散B-树，至少有多少个关键字，至多有多少2001 年哈尔滨工程大学计算机科学与技术学院 816 数据结构考研真题第22列处理冲

32、突。请问关键字为 94 的记录的存储地址是多少？012345678910第 24516396276答：存储地址是 2四、综合题（每小题 5 分，共 35 分）1 给定一组权值9, 6 , 14 , 17, 2 , 15 , 3, 16，请构造哈夫曼树，并计算其带权路径长 度。答：带权路径长度 1862 已知二叉树的先序遍历的结果为 ABCDEFGHIJ，中序遍历的结果为 CBEDAHGIJF，请画出 这颗二叉树。3 对图二所示的无向图，（1 ）请用邻接表表示，且顶点链接按序号从小到大链接。（2 ）请写出从 V0 出发的深度优先遍历和广度优先遍历的结果。图二：4 将图三所示的树转换为二叉树，并使

33、其成为后序线索树图三：ABCDO O O图一0第24EFGHIJKLM5 对关键字序列44 , 12 , 53 , 13 , 37, 88 , 24 , 61构造一棵平衡二叉树。6 已知一个 0E 网，如图四所示，求其关键路径，并给出时间4 的最迟发生时间和事件 5 最早发生时间？第257 对序列50, 77, 64 , 98 , 39 , 12 , 26 , 48 , 44 , 35创建初始堆五（8 分）设指针 head 指向无表头结点单链表的首结点。试设一算法，删除链表中值为X 的结点，若 X 结点不存在，则输出“不存在”信息。六（10 分）已知一个有向图的邻接表，试编写一个算法求每个结点

34、的出度和入度。七（ 12 分）已知一个二叉树存储于二叉链表中，其结点结构为lc data rc其中 lc 和 rc 分别为指向左子树和右子树根的指针域。试编写一非递归算法，求二叉树的结点总数及其深度。第262008 年哈尔滨工程大学计算机科学与技术学院 819 计算机组成原理考研真题【计算机组成原理】第27组成原理哈尔淀】屮人洋200列汕算机细成瓯理试趣刿斷题（毎小iffiiih共10分）L在用分段宜按觸译法为微掏令編码时*须将互斥at命令归为一HL而将相容命令归丸不同組.2.定点札不艾持浮点迄算功亞匚3 -子程序技术可以仃敢降低和IF所占资iSJFffi4.屮断向塑地址描中断服隽评序的入口地

35、址一5*N嵐二进制的金码编码浆统（即n个“旷至n个*J1不員备FI校軽能力&负数凶源码.补码.应码互不相冏=1.补码蠡所对应的宜值范用在数轴匕尢金对祢干尊点机 屮断指令作为一种折令，町以用編制代序，*m冇进位加沈擀实际匕是一种神行加汰楷.10人邛机牛代只用总线则眾统结构二填空BI（每空1*共腱分1采用I/O指令系St须使外币设务的按门寄存器与 4 存单远_：而采舟站川IW指令系総 则应使外憎谡备船接口WIS与主存单元_P第282定点弊數的亍Kn只耍影响蔓_指林：血定点小数的字性11建腿响其3一般而言.一条指令由_ 字段和_ 宇段脚部分组成：而一条措習则由_字段和_字段两郎分爼成a4奇偶

36、校验校验从力能上看，只具自一定轴_切能而不具育_功能弓亦原侶两付嫌的规灿屮，隔鏗设買一个触发踹b存种外川设备均需通过电路才能扯接別系统总线上。7圧个二级仔储器屮，如果访问命屮率足站人，则存福系统所衣现出的性能将接近于 的容疑和的速厘”8在转移址指令屮地址形成部件按指定寻址方式折形咸的有效地址是_ 地址，破将其隹送给C9ti 的地址单元在执仃指令过籾中应承但一和_ 双璽任务口川存时序捽制方式中.方式是时序关系比较简牡.而方黃的优虫是时问利用左井上较九囁撥.三 取硕选择晦屮题乂分丿幅U分1PI位机器内的数值代码*它所表示的卜进制真値为1)(1) 9(2) -17(4)也上三舌均育诃腿2常用的分爼校

37、验Cm k)码中，缸氽位第他敘为【)何(1) n十Xn-kn (4) ki由1个5亿.进側码字构成的含汎策如2t算与分析题 每打 共即分）2浮点加城运易为什么首先要对阶？对阶的原则是什么？对阶时，对其尾数和阶稠分别竝什仇操作？（1）分别求出两两码7之间的“即离四越答漣【毎小题各分.共盹介）工机9外用设备2耐宵琢几种信息亿送时控制方式?2）谨码集的码距为鑫少?5筒娈做迩二种不同的刿斷溢出的方法， 井仆别写出具刈镒附方袪， 汗分别写出其刘溢 的逻辑表迖式。3已知X -0. IKHJL Y=U. II IIIL闿壞阳加减交替法求X/Y的商及余数(1)1100(2) 0010(31000 A4A3A2

38、AIA0试用异或门实现HffJJR验的海明编码电略。 若 匸IS 11（，则其海明码是什么?2试用7418L（74182等中规模柴成电路细织一个组间并行进仲的32價ALff:要感衷而ff储常巧1续写入代110001.设初始电濂原为正向+1弭试画出：（）小片零-L制（2）凋相制（3）凋期制（4）改进型调翩制n mvn m2n mv2n6 .条件转移指令执行时，需对（）的内容进行测试。 PC PSW IR SP2005 年哈尔滨工程大学计算机科学与技术学院819 计算机组成原理考研真题第337 在定点数运算中产生溢出的原因是（）。运算过程中最高位产生了进位或借位 运算的结果超出了机器的表示范围 参

39、加运算的操作数超出了机器的表示范围寄存器的位数太少，不得不舍弃最低有效位8 .下列描述中，不符合 RISC 指令系统特点是（）。指令长度固定，指令种类少 寻址方式种 类尽量减少，指令功能尽可能强 增加寄存器的数目，以尽量减少访存次数 选取使用频率最高的一 些简单指令，以及很有用但不复杂的指令9 .下列不属于微指令结构设计所追求的目标的是（）。提高微程序的执行速度 提高微程序设计的灵活性缩短微指令的长度增大控制存储器的容量10 .中断向量地址是（）。中断源服务程序入口地址 子程序入口地址 中断服务程序入口地址 中断返回地址三、填空题（20 分）1 .在估算加法器运算时间（即加法器速度）时，各位全

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

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

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

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

44、科H名称：计算机组成原理试题编号：440注込木试题的答案必须写在规定的答拠卡或答題本匕写在本卷上无效一、判断题 （每小题1分， 共10分对下列叙述， 认为正确的打“ J ”,认为错溟的打“XS1.组成主存的各存储芯片的片选逻软对CFI丿是透明”的戶2人.中型计算机为了衙化内部逋粘鉛构，莎采用总线丟统 结构*3”不能用逻辑运卽描令处埋数值型敎据1.在循环校验码（TRC屮.余数的出借模式只与生成多埋式G（X）的选择有）G而与待编信息MX）无关。5.础囱盘向匕各磁道的付密復小同，而磁道总容址相同。海明码.5所谓随机存取的含乂有网个要点：其- 是_，It二是 一 _ _ 。6.个字节的机器数，若为无符

45、号数则表亦数的范因 为 若为补码定点整数，则表示数的范用为_；若为补码定点小数，则我示数的范国为）7.扩展型变址寻址初式可有_和_两类.& 描述磁盘的工作速度，可以用三个焉标分别反映三种工作 阶段的速度。三个指标分别是_ 、_ 和_9大多数主存储器采用的衩验方法是_,它的码距“为_二 单向选择题（毎小题2分.共20分）1.十进制数7和9的8421码之闾的“距离”为（）.！2342.堆栈的操作原则足（ 儿单端固定双端固定 H * 4 - B4jLa f - J - J 9第38该指令的转移空间可以从哪_到哪里？2. ixlOHOl, y-）11010,原码两位乘算达计算尸?31设机器字长

46、“位，其浮点数以2为底，尾数规格化英 中阶码8位（含1位阶荷人补码表肩尾数X位（含1位数符原码表示出问：它所能表示的非零星小止数、 最大止数、绝对值最小负数、绝对值最大负数各是什么？ 分别写出16位机器数及十进制真值“4.育五数A、B.C, D、E,分别为101101 011001,111011.1001】1,001110,用CSA/CPA组合算法,列竖式计算匕五 数之和。5.微指令少编码方式有挪儿神？役某机微指令格式如题图5$所示，具中Q 0和Q二分别扌醫明两种互斥大类的微慄 作。iff说明英微嫌作控制宇段都分的第几位到胡几付为诃 柯编码方法？最多可是义多少种不同含文（空操作除外） 的微命令

47、？ 一条这样的微指令垠多町同时发岀几个微命 令？澈命令7,9.10.四、下溢左浮点表在溢 负谥 上溢 浮点丧示法本质上長一种二述制的指数记数法. 示中，对数符指数卞列为&位移码机器数材的 当求罔移时，（尘溢出卓11111111 1000（1000 011U111址毎条指令的三个阶段（取指、取数运算）各需1 At时间。今仃段程序山i00条指令构成采用双存储体的 軍叠处理方式，则该程序的运行共耗时（）个占 X100102201300若x4=XoXiXzXm其中Xo为符号位.X】为最高数位一若（儿则当补码左移时，賀会发生溢出。 X&=Xi XMX: XiO Xi二1问答题（每小題6分

48、，共和分1.如果堆栈采取口底向上生成力式，对于下述两种情况，分 别讨论压入和弹出时，应先后做哪些操作？栈顶单元是已存元素的实单元）采用了隐含约定技术。数位基数 00000000将第39共5贞第1.以波形图形式画出个-.级时序於St图。要求:押令周期 山3个匸作周期纽成，每个工作周期包含4个时钟周期（或 谓旅拍,时钟闾期中包含1个丄柞脉冲，而丄作脉冲由 上振荡器的输出m经4分频后获得。2.设慕指令系统指令了艮16位，其二地址、二地址、单地 址描令格式如题图62所利其中AJ地址3悅、A2地址6位、Ai地址3位.试提出种方案，使该指令系统具有】0条三地址指令、45条-：地址指令、160条单地址指令。

49、三地址I OPA3ZA,二地址OPA；AnM l.iL P.111第40哈尔滨工程大学 2003 年计算机组成原理试题一、判断题（每小题 1 分，共 10 分）1 在用分段直接编译法为微指令编码时，须将互斥微命令归为一组，而将相容命令归为不同 组。2 .定点机不支持浮点运算功能。3 .子程序技术可以有效降低程序所占资源开销。4 .中断向量地址指中断服务程序的入口地址。5 . N 位二进制的全码编码系统（即 n 个“0”至 n 个“1”）不具备自校验能力。6 .负数的源码，补码，反码互不相同。7 .补码数所对应的真值范围在数轴上完全对称于零点。8 .中断指令作为一种指令，可以用编制程序。9 .串

50、行进位加法器实际上是一种并行加法器。10 .大型机不宜采用总线型系统结构。二、填空题（每空 1 分，共 20 分）1 .采用隐式 I/O 指令系统，须使外围设备的接口寄存器与主存单元 _ ;而采用专用 I/O 指令系统，则应使外围设备的接口寄存器与主存单元 _ 。2 .定点整数的字长 n 只要影响其_指标；而定点小数的字长 n 主要影响其_指标。3 .一般而言，一条指令由_ 段和_段两部分组成；而一条指令则由 _段和_段两部分组成。4 .奇偶校验校验从功能上看，只具有一定的 _ 能，而不具有_能。5.在原码两位乘的规则中，需要设置一个 _ 虫发器。6 .各种外围设备均需通过 _路，才能挂接到系统总线上。7 .在一个三级存储器中，如果访问命中率足够大，则存储系统所表现出的性能将接近于 _的容量和_ 勺速度。8 .在转移型指令中，地址形成部件按指定寻址方式所形成的有效地址是 _ 址，应将其传送给_09 .目的地址单元在执行指令过程中应承但 _ 和_重任务。10 .在时序控制方式中，_ 式是时序关系比较简单，而_ 式的优点是时间利用安排上较为紧凑。2003 年哈尔滨工程大学计算机科学与技术学院819 计算机组成原理考研真题第41三、单项选择 （每小题 2 分 共 20 分）1 四位机器内的数值代码，它所表示的十进制真值为（）（1）9.（2） -1