2018年扬州大学信息工程学院858程序设计与数据结构之数据结构考研核心题库
● 摘要
一、单项选择题
1． 假定有4个整数用8位补码分别表示为
放在一个8位寄存器中, 则下列运算会发生溢出的是（ ）。
A. B. C. D. 【答案】B
【解析】用补码表示时8位寄存器所能表示的整数范围为数
,
, 在4个选项中, 只有
。现在4个整数都是负
, 结果溢出, 其余3个算式结果
。若将运算结果存
都未超过127, 不发生溢出
2． 两台主机之间的数据链路层采用后退N 帧协议(GBN)传输数据, 数据传输速率为16kbps , 单向传播时延为270ms , 数据帧长度范围是
字节, 接收方总是以与数据帧等长的帧进行确认。
为使信道利用率达到最高, 帧序号的比特数至少为（ ）。
A.5 B.4 C.3 D.237
【答案】B 。
【解析】GBN 的工作原理如下图所示, 本题求解的是发送一个帧到接收到这个帧的确认期间最多可以发送多少数据帧, 要尽可能多发送帧, 应以短的数据帧计算, 注意帧的单位是字节, 因此首先计算出发送一帧的时
间为
;
,
这段时间总共可以发送
, 故发送一帧到收到确认为止的总时间
(帧) , 为了保证发送帧序号和确认帧
序号在此期间不重复, 因此桢序号的比特数至少为4, 答案为
B
3． 下列选项中, 描述浮点数操作速度指标的是（ ）。
A.MIPS B.CPI C.IPC
D.MFLOPS 【答案】D
【解析】MFLOPS(Million Floating-point Operations per Second)表示每秒执行多少百万次浮点运算, 用来描述计算机的浮点运算速度, 适用于衡量处理机的性能。
MIPS(Million Instructions per Second) 表示每秒执行多少百万条指令。对于一个给定的程序, MIPS 定义为
这里所说的指令一般是指加、减运算这类短指令。
CPI(Cycles per Instruction) 就是每条指令执行所用的时钟周期数。由于不同指令的功能不同, 造成指令执行时间不同, 也即指令执行所用的时钟数不同, 所以CPI 是一个平均值。
IPC(Instructions per Cycle)每个时钟周期执行的指令数。
4． 若一个栈以向量
存储，初始栈顶指针top 为n+1，则下面X 入栈的正确操作是（ ）。
A.top :＝top ＋l ；V[top]:＝x B.V[top]:＝x ；top :＝top ＋l C.top :＝top ﹣l ；V[top]:＝x D.V[top]:＝x ；top :＝top ﹣l 【答案】C
【解析】题中初始栈顶指针top 为n ＋1，而栈顶指针又位于最大下标以上，此时入栈应进行先减一操作。
5． 有向带权图如下图图所示, 若采用迪杰斯特拉(Dijkstta)算法求从源点a 到其他各顶点的最短路径, 则得到的第一条最短路径的目标顶点是b , 第二条最短路径的目标顶点是c , 后续得到的其佘各最短路径的目标顶点依次是（ ）。
图 有向带权图
A.d , e , f
B.e , d , f C.f , d , e
D.f , e , d 【答案】C 。
【解析】本题主要考查Dijkstta 算法的思想和解题步骤。题目执行算法过程中各步的状态如下表所示。执行Dijkstta 算法过程中各步的状态表, 故后续目标顶点依次为f , d , e 。
6． 要连通具有n 个顶点的有向图，至少需要（ ）条边。
A.n －1 B.n C.n+1 D.2n
【答案】B
【解析】对于有向图来说，两个顶点之间的边是具有方向的。如果是构成连通的无向图，需要n －1条边，而对于有向图来说，只需要再加上第一个顶点和最后一个顶点加上一条边，让其构成环状的图即可，因此最少需要n 条边。
7． 下列二叉排序树中查找效率最高的是（ ）。
A. 平衡二叉树 B. 二叉查找树
C. 没有左子树的二叉排序树 D. 没有右子树的二叉排序树 【答案】A
【解析】平衡二叉树的左子树和右子树的深度之差的绝对值不超过1。这就保证了二叉树的深度是
级别的。二叉查找树或者是一颗空数；或者是具有下列性质的二叉树:①若左子树不空，
则左子树上所有结点的值均小于它的根结点的值；②若右子树不空，则右子树上所有结点的值均大于它的根结点的值；③左、右子树也分别为二叉排序树。B 、C 、D 三项均不能保证左子树和右子树的深度之差的绝对值不超过1, 甚至很大，因此查找效率低。