南京航空航天大学-829计算机专业基础【2018】考研真题
2023-06-21
999+
282.08KB
5 页
侵权投诉
科目代码：829科目名称：计算机专业基础 第 1页 共 5页
南京航空航天大学
2018 年硕士研究生入学考试初试试题（
A 卷
）
科目代码:
829
满分:
150
分
科目名称:
计算机专业基础
注意: ①认真阅读答题纸上的注意事项；②所有答案必须写在答题纸上，写在本试题纸或草稿纸上均无
效；③本试题纸须随答题纸一起装入试题袋中交回！
数据结构部分（50 分）
1．（10 分）给定 n 个村庄之间的交通图，边上的值表示这条道路的长度，现在要从这 n 个
村庄中选择一个村庄建一所医院，问这所医院应建在哪个村庄，才能使离医院最远的村庄
到医院的路程最短？试选择或构造一种适当的数据结构并设计一个算法，并应用该算法解
答下图所示的实例，给出算法执行过程示意图。
2．（10 分）详细解释哈希表的工作原理。以此为例，将关键字序列（51，83，43，15，62，
59，74，61）存储在长度为 10 的哈希表中，使用哈希函数 H(key) = Key % 10 ，并采用链
地址法解决冲突，画出哈希表示意图。
3．（10 分）设有一批需实时处理的数据元素组成集合 S，实时处理开始后，每隔一秒钟收
到一个新的数据元素加入 S。现要求在每次接收一个新元素之前，找出 S 中现有的最小元素
并将其输出（从 S 中删除）。试选择或构造一种适当的数据结构并设计一个算法，尽可能高
效地完成上述任务。例如：S=(59,31,29,18,78,26,48,10,65,35)，新接受的数据为 39，12，
46….。以此为例说明算法执行过程示意图。
4．（10 分）设一个带头结点的单链表 L，数据元素为整数，其中大部分为正数，少数为负
数，编写函数，采用高效的算法调整链表，实现将负数结点移到链表尾部，并返回调整后
链表中的第一个负数结点位置。先给出算法思想，再写相应代码。
5.（10 分）设二叉树 T，用二叉链表结构存储，元素值为整数且互不相同。编写非递归函
数，对给定的 2 个整数，若 2 个都不是 T 的元素，输出-2；若 1 个不是 T 的元素，输出-1；
若 2 个都是 T 的元素，输出两者所在的层数的间隔数。要求先给出算法思想，再写代码。
V3
V2
V4
V1
3
4
6
10
2
科目代码：829科目名称：计算机专业基础 第 2页 共 5页
组成原理部分（50 分）
6.(8 分）如下为一流水和一非流水处理器的参数，请按要求计算：
Parameter
Pipelined
Non-Pipelined
Clock Rate
500MHZ
250MHZ
CPI for ALU instruction
1
1
CPI for Control instruction
2
1
CPI for Memory instruction
2.5
1
若一程序有 20%的 ALU 指令 , 10%的控制指令和 70%的访存指令，上述哪种设计更快？请
用合适的指标评估。
7.（10 分）若有一源程序 hello.c 文件：
1) 简述如何生成相应的可执行程序；
2）简述该可执行程序如何在计算机上执行的过程。
8.（10 分）对于一 n 位运算器，通常得到其运算结果 F 的同时也输出相应的标志信号如 ZF
（零标志位），SF（符号标志位），CF（进位标志位）和 OF（溢出标志位）等：
1）请用逻辑表达式表示出上述各标志信号如何根据运算结果 F 的相应位产生并做出解释；
2）若需完成两有符号数比大小，请问需采用何种运算且如何利用上述标志位判别；
9.（10 分）假定计算机系统主存空间大小为 32Kx16 位，且有一个 4K 字的 4 路组相联 Cache，
主存和 Cache 之间的数据交换块的大小为 64 字。假定 Cache 开始为空，处理器顺序地从存
储单元 0、1、…、4351 中取数，一共重复 10 次。设 Cache 比主存快 10 倍。采用 LRU 算法。
试分析 Cache 的结构和主存地址的划分。说明采用 Cache 后速度提高了多少？
10.(12 分）如图所示的单周期数据通路执行如下 MIPS 32 指令
Address (Byte) Instruction
100 beq $R2, $R4, 7 # The address of register Rn is n
执行上述指令前各寄存器的内容如下表：
Register
Value (10 进制)
R1
12
R2
16
R3
8
R4
16
标签： #南京航空航天大学
摘要：
展开>>
收起<<
科目代码：829科目名称：计算机专业基础第1页共5页南京航空航天大学2018年硕士研究生入学考试初试试题（A卷）科目代码:829满分:150分科目名称:计算机专业基础注意:①认真阅读答题纸上的注意事项；②所有答案必须写在答题纸上，写在本试题纸或草稿纸上均无效；③本试题纸须随答题纸一起装入试题袋中交回！数据结构部分（50分）1．（10分）给定n个村庄之间的交通图，边上的值表示这条道路的长度，现在要从这n个村庄中选择一个村庄建一所医院，问这所医院应建在哪个村庄，才能使离医院最远的村庄到医院的路程最短？试选择或构造一种适当的数据结构并设计一个算法，并应用该算法解答下图所示的实例，给出算法执行过程示意...
声明：研友网所有资料均为用户上传分享，仅供参考学习使用，版权归原作者所有。若侵犯到您的权益，请告知我们处理！任何个人或组织，在未征得本平台同意时，禁止复制、盗用、采集、发布本站内容到任何网站、书籍等各类媒体平台。
