南京邮电大学计算机复试题,2016年南京邮电大学计算机学院(软件学院)数据结构复试笔试最后押题五套卷...

一、选择题

1． 下列选项中，描述浮点数操作速度指标的是( )。

A.MIPS B.CPI C.IPC

D.MFLOPS 答:D

【解析】

表示每秒执行多少百万次浮点

. 表示每秒执行多少百万条指令。对于一个给定的程序，

MIPS 定义为

这里所说的指令一般是指加、减运算这类短指令。

就是每条指令执行所用的时钟周期数。由于不同指令的功能不同，

造成指令执行时间不同，也即指令执行所用的时钟数不同，所以CPI 是一个平均值。

每个时钟周期执行的指令数。

2． 已知序列25, 13, 10, 12, 9是大根堆，在序列尾部插入新元素18, 将其再调整为大根堆，调整过程 中元素之间进行的比较次数是( )。

A.1 B.2 C.4 D.5 答:B

【解析】对堆插入或删除一个元素，有可能不满足堆的性质，堆被破坏，需要调整为新堆。 (1)为原堆， (2)为插入18后，

(3)比较10与18，交换后，

(4)比较25与18, 不交换，即为调整后的新的大根堆。 因此调整过程中元素之间进行的比较次数为2。

运算，用来描述计算机的浮点运算速度，适用于衡量处理机的性能。

3． 已知广义表用

和

数取出LS 中原子e 的运算是( )。

答:C 【解析】

操作就是得到广义表中第一个的原子。

得

到得到e 。

4． 有两个并发执行的进程P1和P2, 共享初值为1的变量x 。P1对x 加1, P2对x 减1。加1和减1操作的指令序列分别如下所示。

//取x 到寄存器R1中

两个操作完成后，2的值( )。 A. 可能为-1或3 B. 只能为1 C. 可能为0、1或2 D. 可能为-1、0、1或2 答:C

【解析】这是在数据库中常有的操作。为保证数据的正确，避免产生错误，系统必须保证数据的同步。而保证数据的同步一般采取加锁的方法，让进程P1和P2互斥访问共享变量X 。当然用信号量和P 、V 操作也是可以 保证互斥操作，达到数据同步的。本例中，由于没有采取保证数据同步的相应措施，则最后结果就会出现差错。 例如，当正常情况下，进程P1和P2先后对x 操作，可以看到x 值的变化为初始1→2→1的过程，若P2, P1先后操作，则x 值的变化为初始1→0→1，这是正确的。若考虑一种并发的情况，进程P1和P2先后执行了取数load 的操作，它们

操作就是得到除第一个原子外剩下元得

到

得

到

素构成的表

。

得到的x 值均为1，运算后，P1和P2的x 值分别为2和0, 此时要看哪个进程后执行存数store 的 操作了，哪个进程后操作，结果就是那个进程的x 值，所以可能的结果为0或2, 加上前面正确的x 值1, 则可能的结果就有3种了。

5． 每个结点的度或者为0或者为2的二叉树称为正则二叉树。n 个结点的正则二叉树中有( )个叶子。

答:D

【解析】二叉树结点总数

分别代表度为0，度为1，度为2的结点数)。

又在非空二叉树中

：且本题所给树为正则二叉树

，所

以因

此

6． 两台主机之间的数据链路层采用后退N 帧协议(GBN )传输数据，数据传输速率为16kbps ，单向传播时延为270ms ，数据帧长度范围是128〜512字节，接收方总是以与数据帧等长的帧进行确认。为使信道利用率达到最高，帧序号的比特数至少为( )。

A.5 B.4 C.3 D.237 答:B 。

【解析】GBN 的工作原理如下图所示，本题求解的是发送一个帧到接收到这个帧的确认期间最多可以发送多少数据帧，要尽可能多发送帧，应以短的数据帧计算，注意帧的单位是字节，因

此首先计算出发送一帧的时间

这段时间总共可以发送

故发送一帧到收到确认为止的总时间为

，为了保证发送帧序号和确认帧(帧)

序号在此期间不重复，因此帧序号的比特数至少为4, 答案为

B

7． 已知循环队列存储在一维数组rear 的值分别是( )。

A.0, 0 B.0, n-1 C.n-1, 0

中，且队列非空时front 和rear 分别指向队头元素和

队尾元素。若初始时队列为空，且要求第1个进入队列的元素存储在A[0]处，则初始时front 和