2003年黑龙江哈尔滨工业大学数据结构考研真题.doc-资料库

第1页 / 共5页

第2页 / 共5页

第3页 / 共5页

第4页 / 共5页

第5页 / 共5页

2003 年黑龙江哈尔滨工业大学数据结构考研真题考生注意：答案务必写在答题纸上，并标明题号。答在试题上无效。 I、数据结构（含高级语言）部分（共 75 分）一、填空题（每个空 1 分，共 11 分） 1. 在循环链表中，可根据任意一个结点的地址遍历整个链表，而在单向链表中需要知道巡 —才能遍历整个链表。 2. 对一个序列 F, B, W, A, E, H 按字母表顺序从小到大进行分类。请回答：三路归并（two-waymerge sort）的第一遍结果是（）；插入（insertion）分类的第一遍结果是（）少_;堆（heap）分类的第一遍结果是（）：选择（selection）分类的第一遍结果是（）。 3.要想提高磁盘文件的分类效率，一般釆用（）、（）、（）等技术。 4.哈夫曼（Huffinan）树是加权路径长度（）的二元树。 5.对 n 个顶点的连通无向图，其生成树有且仅有（）条边。 6.在拓扑分类（Topological sort）中，拓扑序列的最后一个顶点必定是 QD 的顶点。二、单项选择与判断（共 9 分）（一）单项选择题（每小题 1 分，共 4 分） 1.在 n 个结点的线性表的数组实现中，算法的时间复杂性是 0（1）的操作是（）。 A.访问第 i 个结点（iWiWn）和求第 i 个结点的直接前趋（2WiWn） B.在第 i 个结点后插入一个新结点（IWiWn） C.删除第 i 个结点（iWiWn） D. 以上都不对 2.森林 T 中有 4 株树，第 1、2、3、4 株树的结点个数分别是 nl、n2、n3、n4,那么当把森林 T 转化成一株二元树后，其根结点的右子树上有（）个结点。 A. nl-1 B. nl C. nl+n2+n3 D. n2+n3+n4 3.要求内存量最大的分类算法是（）。 A.插入分类 B. 选择分类 C. 快速分类 D.归并分类 4. 索引非顺序文件是指（）。 A.主文件无序，索引表有序 B.主文件有序，索引表无序. C.主文件有序，索引表有序 D. 主文件无序, 索引表无序（二）判断下列叙述是否正确，若正确, 请画"J ”；否则，画“ X ”（每小题 1 分，共 5 分） 1. 二元树按某种遍历顺序线索化后，任意一个结点均有指向其前趋和后继的线索。（）

2. 完全二元树中，若某个结点没有左儿子，则该结点一定是终结结点。（） 3.在索引顺序表进行分块査找，在等概率情况下，平均查找长度不仅与表中元素个数有关，而且与每一块中元素个数有关。（） 4.基数分类只适用于以数字为关键字的情况，不适用于以字符串为关键字的情况。（） 5.索引顺序存取方法是一种专门为磁盘存取而设计的索引顺序文件的组织方法。（）三、简答题（共 21 分）简述堆与二元查找树的区别与联系。（5 分）已知某加权连通无向图边的个数远远小于顶点的个数，若求其最小生成树用哪种算法最好？简述该算法。（7 分）用两个栈 SI, S2 模拟一个队列时，如何用栈的操作实现队列的插入，删除以及判队空操作。请简述算法思想。（9 分）四、已知散列（hash）函数为 h（K）, K 为待査找的关键字。用开放定址法处理冲突，试写出删除一个指定关键字 W 的算法。（8 分）五、设一株二元树 T,按图 1 所示形式存放在内存中，试写出一个求 T 的高度和对每个结点赋予一个层号的算法» （14 分）六、试设计一个算法，判断一个无环路有向图 G 中是否存在这样的顶点，该顶点到其它任意顶点都有一条有向路。（12 分） II.计算机组成原理部分（共 75 分）七. 填空（20 分） 1.（2 分）在做手术过程中，医生经常将手伸出，等护士将手术刀递上，待医生握紧后，护士才松手。如果把医生和护士看作是两个通信模块，上述一系列动作相当丁•通信过程中 A 通信中的 B 方式。 2.（3 分）设机器数字长 16 位，其阶符、数符各 1 位，阶码 4 位，尾数 10 位。两个阶码相等的数按补码浮点加法完成后，由于规格化操作可能出现的最大误差的绝对值是 3. （2 分）微指令操作控制的编码方式有 A 、 B 、 C 等,其中控制速度最快的是 Do 4. （3 分）I/O 接口通过 A 总线（地址/数据，二选一填空）将中断向量地址送至 CPU,不通过另一种总线传送向量的原因是 B 。

5.（3 分）设某机共有 30 个通用寄存器，变址寄存器和基址寄存器各一个。该机指令系统共能完成 180 种操作。操作码位数固定，并具有立即、直接、间接、变址、基址、相对这几种寻址方式。假设指令字长等于存储字长，均为 32 位，设计一种寄存器-存储器型指令格式，则可直接寻址的最大范围是 A , 一次间址的范围是 B 。上述寻址方式中 C 寻址的执行时间最快。 6.（2 分）总线同步通信影响总线效率的原因是 A 。 7.（2 分）影响流水线性能的因素包括 A 、 B 等。 8.（3 分）Intel 80486 有一个统一的片内 Cache。Cache 的容量为 8K 字节，且采用组相联结构, 每组含 4 个字块，字块的大小是 4 个 32 位字。则需用 A 位地址码表示组地址。八. 简答题（18 分） 1.（6 分）设机器数阶码取 3 位（含 1 位阶符），尾数取 5 位（•含 1 位数符），两数 X、Y 以 — 进制真值表示为 X=2°X0.1101, Y=2'l0X （-0.1001）,计算[XXY]tt 2.（6 分）一个 CPU 的指令周期包含取指、，间址、执行和中断四个不同阶段，采用组合逻辑设计控制器时，是否需要标志位来指定当前的阶段，为什么？微程序设计情况下是否需要这些标志，为什么？ 3.（6 分）一个 DMA 接口可以采用周期窃取的方式把字符传到存储器，它支持的最大批量为 20 个字节。而处理每个中断的平均时间为 3.5 微秒（1 微秒=1（/6 秒）。现有一字符设备的传输率为 9600bps （位/秒），CPU 正常执行的速度为 1 X if 条指令/秒，平均一条指令需要 5 个机器周期，一次存储器访问需要一个机器周期。假设字符之间的传送是无间隙的，试问釆用中断方式和 DMA 方式，每秒因数据传输占用处理器的时间各为多少？如何能够进一步提高处理器效率？

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 成立后每个进位的产生时间。 2003 年研究生入学试题数据结构答案（仅供参考）一、填空： 1. 头指针 2. BFAWEH BFWAEH FBHAEW AFBWEH 3. K 路归并、并行操作的缓冲处理、初始归并段 4. 最小 5. n-1 6. 没有后继二、单项选择与判断：（一）1. A 2.D 3. D 4. A （二）5. 错误 6. 正确 7.正确 8.错误 9. 错误三、简答题：

1. 堆与二元查找树均满足任一节点的元素值小于其左右儿子的值，但是若按中根顺序遍历一颗二元查找树，将得到最终结果既递增顺序，而堆无此性质，需经过整理才得到最终结果。 2. 用克鲁斯卡尔(Kruskal)算法较好。该算法假设 G＝（V，E）是一个具有 n 个顶点的连通图，T＝（V，TE）是 G 的最小生成树，U 的初值等于 V，即包含有 G 中的全部顶点，TE 的初值为空集。该算法的基本思想是：将 G 中的边按权值从小到大的顺序依次选取，若选取的边使生成树 T 形成回路，则将其舍弃，如此进行下去，直到 TE 中包含 n-1 条边为止，此时的 T 即为最小生成树。 3. 算法思想：由于栈的特点是先进后出，为了模拟先进先出的队列，必须用两个栈，一个栈（S1）用于插入元素，另一个栈（S2）用于删除元素，每次删除元素时应将前一个栈的所有元素读出然后进入第二个栈中，这样才能达到模拟队列的效果。

资料库

2003年黑龙江哈尔滨工业大学数据结构考研真题.doc

相关推荐

考研

热门标签

最新资料