2017年东北林业大学数据结构与高级语言程序设计之数据结构复试实战预测五套卷
● 摘要
目录
2017年东北林业大学数据结构与高级语言程序设计之数据结构复试实战预测五套卷（一） . .... 2
2017年东北林业大学数据结构与高级语言程序设计之数据结构复试实战预测五套卷（二） . .. 10
2017年东北林业大学数据结构与高级语言程序设计之数据结构复试实战预测五套卷（三） . .. 16
2017年东北林业大学数据结构与高级语言程序设计之数据结构复试实战预测五套卷（四） . .. 25
2017年东北林业大学数据结构与高级语言程序设计之数据结构复试实战预测五套卷（五） . .. 31
一、应用题
1． 在堆排序、快速排序和合并排序中：
（1）若只从存储空间考虑，则应首先选取哪种排序方法，其次选取哪种排序方法，最后选取哪种排序方法？
（2）若只从排序结果的稳定性考虑，则应选取哪种排序方法？
（3）若只从平均情况下排序最快考虑，则应选取哪种排序方法？
（4）若只从最坏情况下排序最快并且要节省内存考虑，则应选取哪种排序方法？
【答案】（1）应首先选取堆排序方法，其次选取快速排序方法，最后选取归并排序方法。 （2）应选取归并排序方法
（3）应选取快速排序方法
（4）应选取堆排序方法
2． 给出模式串在KMP 算法中的next 和nextval 数组。
【答案】模式串的next 函数定义如下：
根据此定义，
可求解模式串的next 和nextval 值如下：
3． 某程序中有如下循环代码段p :
P 起始地址 为0804 8100H，对应的汇编代码和机器代码如下表所示
假设编译时变量sum 和i 分别分配在寄存器R1和R2中。常量N 在寄存器R6中，数组A 的首地址在寄存器R3中，程序段
执行上述代码的计算机M 采用32位定长指令字，其中分支指令Bne 采用如下格式，
Op 为操作码：Rs 和Rd 为寄存器编号：OFFSET 为偏移量，用补码表示。请回答下列问题，并说明理由。
（1）M 的存储器编址单位是什么？
（2）已知sll 指令实现左移功能，数组A 中每个元素占多少位？
（3）表中bne 指令的OFFSET 字段的值是多少？已知bne 指令采用相对寻址方式，当前PC 内容为bne 指令地址，通过分析表中指令地址和bne 指令内容，推断出bne 指令的转移目标地址计算公式。
（4）若M 采用如下“按序发射、按序完成”的5级指令流水线：IF （取指）、ID （译码及
，且硬件不采取任何转发措施，分取数）、EXE （执 行）、MEM （访存）、WB （写回寄存器）
支指令的执行均引起3个时钟周期阻塞，则P 中哪些指令的执行会由于数据相关而发生流水线阻塞？哪条指令的执行会发生控制冒险？为什么指令1 的执行不会因为与指令5的数据相关而发生阻塞？
【答案】（1）由题可知，指令为32为即4个字节，而程序执行时是以4为间隔逐条取指令的，故可知M 的存储器是采用字节编址。
（2）32位，因为sll 中实现左移，而（R2） <<2 R4即左移两位就是乘以4，所以是
位
（3）由Bne 的指令格式可知其OFFSET 为指令的后16位，而Bne 的机器码码为1446 FFFAH，所以Bne 的OFFSET 为FFFAH 即-6。
由题可知Bne 采用相对寻址方式，故有效地址
为当前Bne 指令的地址
即而取完Bne 而PC 的值指令后
，
而要跳转到指令1的地址08048100H ，两者相差了18H 也
就是24个字节，而OFFSET 是-6, 故转移目标地址计算公式为（PC
）
（4）由指令序列可知，指令1需写R4而指令2需读R4, 故指令2会因为数据相关而发生阻
塞，同理指令3、指令4也会因为数据相关而发生阻塞；而指令6为分支指令，故其存在控制冒险。因为分支指令会有3个时钟周期的阻塞，故指令1的执行不会因为指令5的数据相关而发生阻塞。
4． 文件F 由200条记录组成，记录从1开始编号，用户打开文件后，欲将内存中的一条记录插入文件F 中，作为其第30条记录，请回答下列问题，并说明理由。
（1）若文件系统为顺序分配方式，每个存储块存放一条记录，文件F 的存储区域前后均有足够空闲的存储空间，则要完成上述操作最少要访问多少存储块？ F 的文件控制区内容会有哪些改变？
（2）若文件系统为链接分配方式，每个存储块存放的一条记录和一个链接指针，则要完成上述操作最少要 访问多少存储块？若每个存储块大小为1KB ，其中4个字节存放指针，则该系统支撑文件的最大长度是多少？
【答案】（1）因为要最少访问，所以选择将前29块前移一个存储块单元，然后将要写入的记录写入到当前的第30条的位置上。由于前移都要先访问原存储块将数据读出，再访问目标存储块将数据写入，所以最少需要访问
块存储块
F 的文件区的文件长度加1，起始块号减1
（2）采用链接方式则需要顺序访问前29块存储块，然后将新纪录的存储块插入链中即可，把新的块存入磁盘要1次访存，然后修改第29
块的链接地址存回磁盘又一次访存。一共就是
次。
4个字节的指针的地址范围为 所以此系统支撑文件的最大长度为
5． 某16位计算机中，带符号整数用补码表示，数据Cache 和指令Cache 分离。题表给出了指令系统中部分指令格式，其中Rs 和Rd 表示寄存器，mem 表示存储单元地址，（X ）表示寄存器X 或存储单元X 的内容。
表 指令系统中部分指令格式
该计算机采用5段流水方式执行指令，各流水段分别是取指（IF ）、译码/读寄存器（ID ）、执行/计算有效地址（EX ）、访问存储器（M ）和结果写回寄存器（WB ）, 流水线采用“按序发射，按序完成”方式，没有采用转发技术处理数据相关，并且同一个寄存器的读和写操作不能在同一个时钟周期内进行。请回答下列问题。
（1）若int 型变量x 的值为-513, 存放在寄存器R1中，则执行指令“SHR R1”后，R1的内容
相关内容
相关标签