当前位置：问答库＞考研试题

一、填空题

1． 在一个具有n 个单元的顺序栈中，假定以地址高端(即下标为n 的单元) 作为栈底，以top 作为栈顶指针，则当向栈中压入一个元素时，top 的变化是top ＝_____。

【答案】top ﹣1

【解析】由于栈底在地址高端，栈中压入一个元素时，栈顶向地址底端移动一个单位，所以top ﹣1。

2． 建立索引文件的目的是_____。

【答案】提高查找速度

3． 从平均时间性能而言，_____排序最佳。

【答案】快速

【解析】快速算法的平均时间复杂度为nlogn 。

4． 在拓扑分类中，拓扑序列的最后一个顶点必定是_____的顶点。

【答案】出度为0

【解析】如果最后一个顶点的出度不为0, 则必定还有顶点存在，与题目所说的最后一个顶点矛盾，所有最后一个顶点的出度必定为零。

5． 设数组的基地址为2000，每个元素占2个存储单元，若以行序为主序顺序存储，则元素a[45，68]的存储地址为_____；若以列序为主序顺序存储，则元素a[45，68]的存储地址为_____。

【答案】9174；8788

【解析】设一个元素的行标为i ，列标为j 。若以行序为主存储顺序，则它的存储地址为2000＋((i﹣l)*80＋j ﹣

1) 2。若以列序为主存储顺序，则它的存储地址为2000＋((j﹣l)*50＋i ﹣l)*2。

6． 模式串的next 函数值序列为_____。

【答案】01122312

二、单项选择题

7． 若元素a , b , c , d , e , f 依次进栈, 允许进栈、退栈操作交替进行, 但不允许连续三次进行退栈操作, 则不可能得到的出栈序列是（ ）。

A.d , c , e , b , f , a

B.c , b , d , a , e , f

C.b , c , a , e , f , d

D.a , f , e , d , c , b

【答案】D

【解析】4个选项所给序列的进、出栈操作序列分别为:

选项A.

选项B.

选项C.

选项D.

序。

8． 对于栈操作数据的原则是（ ）

A. 先进先出

B. 后进先出

C. 后进后出

D. 不分顺序

【答案】B

【解析】先进先出是队列操作数据的原则。先进后出是栈操作数据的原则，栈限定在表尾进行插入和删除。

9． 在一个采用CSMA/CD协议的网络中，传输介质是一根完整的电缆，传输速率为1Gbps ，电缆中的信号传播速度是200000km/s.若最小数据帧长度减少800bit ，则最远的两个站点之间的距离至少需要（ ）.

A. 增加160m

B. 增加80m

C. 减少160m

D. 减少80m

【答案】D

【解析】以太网采用CSMA/CD访问协议，在发送的同时要进行冲突检测，这就要求在能检测出冲突的最大时间内数据包不能够发送完毕，否则冲突检测不能有效地工作。所以，当发送的数据包太短时必须进行填充。最小帧长度＝碰撞窗口大小×报文发送速率，本题最小数据帧长度

89减少800b , 那么碰撞的窗口也要减少，因此距离也要减少，从而(800×2×l0)/(l×l0) ＝160m ，由于 按照题目要求, 不允许连续三次进行退栈操作, 所以选项D 所给序列为不可能得到的出栈顺

时间延时存在两倍的关系，因此减少的距离为80m 。

10．假定用若干个

是（ ）。

A.0000H

B.0600H

C.0700H

D.0800H

【答案】D 位的芯片组成一个8K ×8位的存储器, 则地址0B1FH 所在芯片的最小地址

【解析】由若干芯片构成存储器, 采用字和位同时扩展方法。8片

组2个芯片, 各组芯片的地址分配分别为:

第1组,

第3组, ; 第2组, ; 第4组, ; 。 位的芯片分成4组, 每

地址0BIFH 处于第2组内, 其芯片的最小地址为0800H 。

11．若需在的时间内完成对数组的排序，且要求排序是稳定的，则可选择的排序方法是（ ）。

A. 快速排序

B. 堆排序

C. 归并排序

D. 直接插入排序

【答案】C

【解析】稳定排序有:插入排序、起泡排序、归并排序、基数排序。不稳定排序有:快速排序、

堆排序、shell 排序。时间复杂度平均为的有:归并排序、堆排序、shell 排序、快速排序。

12．Y 和z ，一个C 语言程序在一台32位机器上运行. 程序中定义了3个变量x 、其中x 和z 为int

Y 为short 型. 当x ＝127，Y ＝-9时，x 、Y 和z 的值分别是. 型，执行赋值语句z ＝x ＋Y 后，（ ）

A.x ＝0000007FH ， Y ＝FFF9H ， z ＝00000076H

B.x ＝0000007FH ， Y ＝FFF9H ， z ＝FFFF0076H

C.x ＝0000007FH ， Y ＝FFF7H ， z ＝FFFF0076H

D.x ＝0000007FH ， Y ＝FFF7H ， z ＝00000076H

【答案】D

【解析】当两个不同长度的数据，要想通过算术运算得到正确的结果，必须将短字长数据转换成长字长数据，这被称为“符号扩展”.例如，x 和z 为int 型，数据长32位，Y 为short 型，数据长16位，因此首先应将y 转换成32位的数据，然后再进行加法运算.

运算采用补码的形式，而x 的补码是0000007FH ，Y 的补码是FFFFFFF7H ，所以x ＋Y ＝00000076H.