《2017年南通大学数据结构复试实战预测五套卷.doc》由会员分享，可在线阅读，更多相关《2017年南通大学数据结构复试实战预测五套卷.doc（4页珍藏版）》请在金锄头文库上搜索。
1、2017年南通大学数据结构复试实战预测五套卷一、应用题1 数据类型和抽象数据类型是如何定义的? 二者有何相同和不同之处? 抽象数据类型的主要特点是什么? 使用抽象数据类型的主要好处是什么？【答案】（1）数据类型的定义数据类型是程序设计语言中的一个概念，它是一个值的集合和操作的集合。如c 语言中的整，其操作有加、减、乘、除、型、实型、字符型等。整型值的范围（对具体机器都应有整数范围）求余等。实际上数据类型是厂家提供给用户的已实现了的数据结构。（2）抽象数据类型的定义“抽象数据类型（ADT ）”指一个数学模型及定义在该模型上的一组操作。“抽象”的意义在于数据类型的数学抽象特性。抽象数据类型的定义仅
2、取决于它的逻辑特性，而与其在计算机内部 如何表示和实现无关。无论其内部结构如何变化，只要它的数学特性不变就不影响它的外部使用。（3）两者的不同抽象数据类型和数据类型实质上是一个概念。此外，抽象数据类型的范围更广，它已不再局限于机器已定义和实现的数据类型，还包括用户在设计软件系统时自行定义的数据类型。（4）抽象数据类型的主要特点，而是向“科学”迈进了一步。 抽象数据类型的出现使程序设计不再是“艺术”（5）使用抽象数据类型的好处使用抽象数据类型定义的软件模块含定义、表示和实现三部分，封装在一起，对用户透明（提，而不必了解实现细节。 供接口）2 某16位计算机中，带符号整数用补码表示，数据Cache
3、 和指令Cache 分离。题表给出了指令系统中部分指令格式，其中Rs 和Rd 表示寄存器，mem 表示存储单元地址，（X ）表示寄存器X 或存储单元X 的内容。表 指令系统中部分指令格式 该计算机采用5段流水方式执行指令，各流水段分别是取指（IF ）、译码/读寄存器（ID ）、执行/计算有效地址（EX ）、访问存储器（M ）和结果写回寄存器（WB ）, 流水线采用“按序发射，按序完成”方式，没有采用转发技术处理数据相关，并且同一个寄存器的读和写操作不能在同一个时钟周期内进行。请回答下列问题。（1）若int 型变量x 的值为-513, 存放在寄存器R1中，则执行指令“SHR R1”后，R1的内容
4、是多少？（用十六进制表示）（2）若某个时间段中，有连续的4条指令进入流水线，在其执行过程中没有发生任何阻塞，则执行这4条指令所需的时钟周期数为多少？（3）若高级语言程序中某赋值语句为址分别表示为和b 均为int 型变量，它们的存储单元地该语句对应的指令序列及其在指令流水线中的执行过程如题图所示。则这4条指令执行过程中，的ID 段和的IF 段被阻塞的原因各是什么？ 图 指令序列及其执行过程示意图（4）若高级语言程序中某赋值语句为储单元地址分别表示为【答案】 （1）x 的机器码为1110 1111 1111B, 即指令执行后（2）至少需要即指令执行前（Rl ） =FDFFH, 右移lwei 后为1
5、111个时钟周期数。x 和a 均为unsigned int 类型变量，它们的存则执行这条语句至少需要多少个时钟周期? 要求模仿题图画出这条语句对应的指令序列及其在流水线中的执行过程示意图。（3）的ID 段被阻塞的原因：因为与和都存在数据相关，需等到和将结果写回寄存器后，才能读寄存器内容，所以的ID 段被阻塞。 的IF 段被阻塞的原因：因为14的前一条指令在ID 段被阻塞，所以，的IF 段被阻塞。（4）对应的指令序列为： 这5条指令在流水线中的执行过程如下图所示，执行语句最少需要17个时钟周期。 3 有A 、B 两人通过信箱进行辩论，每人都从自己的信箱中取得对方的问题。将答案和向对方B 的信箱最
6、多放N 提出的新问题组成一个邮件放入对方的邮箱中，设A 的信箱最多放M 个邮件，个邮件。初始时 A 的信箱中有x 个邮件邮件数减1. 。A 、B 两人操作过程： 从A 的信箱中取出一个邮件； 回答问题并提出一个新问题； 将新邮件放入B 的信箱； 从B 的信箱中取出一个邮件； 回答问题并提出一个新问题； 将新邮件放入A 的信箱； 当信箱不为空时，辩论者才能从信箱中取邮件，否则等待。 当信箱不满时，辩论者才能将新邮件放入信箱，否则等待。请添加必要的信号量和P 、V （或wait signed ）操作，以实现上述过程的同步，要求写出完整过程，并说明信号量的含义和初值。【答案】首先定义两个互斥信号量：mutexA 和mutexB , 初始时为1，分别用来实现对A 的邮箱和B 的邮箱的互斥使用；然后针对A 的邮箱再定义两个信号量emptyA 和fullA ，初值分别为和X ，分别表示信箱中仍能存放信的数量和已经存放的信的数量，同理设置emptyB 和fullB , 初值为和y 。 B 中有y 个辩论者每取出一个邮件，初始代码： 一、应用题考研试题
