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

一、填空题

1． 在双向循环链表中，向P 所指的结点之后插入指针f 所指的结点，其操作是_____、_____、_____、_____。 【答案】

2． —棵深度为k 的平衡二叉树， 其每个非终端结点的平衡因子均为0，则该树共有_____个结点。

【答案】

【解析】每个非终端结点都是0表示该平衡二叉树没有高度落差。也就是说它是一棵满二叉 树。故结点个数为

3． 二进制地址为011011110000，大小为【答案】011011110100；011011100000

011011110000是块的起始地址，【解析】大小分别为式如下：

当大小为4时，起始地址

为

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

【答案】提高查找速度

5． 设有两个算法在同一机器上运行，其执行时闻分别为

_____。

【答案】15

【解析】当时，而

，时，

6． 设有一个空找，栈顶指针为1000H （十六进制），现有输入序列为1，2，3, 4, 5，经过PUSH ，PUSH , POP , PUSH , POP ，PUSH ，PUSH 之后，输出序列是_____，而栈顶指针值是_____。设栈为顺序栈，每个元素占4个字节。

【答案】23; 100CH

和块的伙伴地址分别为：_____ 和其伙伴块的起始地址计算公当大小为16时，起始地址为

：要使前者快于后者，n 至少为

7． 数组的存储结构采用_____存储方式。

【答案】顺序存储结构

【解析】数组本身的存储结构是线性的，也就是说它是连续存储的。

8． 在下面的程序段中，对X 的赋值语句的时间复杂度为_____（表示为n 的函数）。

【答案】1＋（1＋2）＋（1＋2＋3）＋"•＋（l ＋2＋... ＋n ）=n（n ＋1）（n ＋2）/6，即

【解析】当i=l时，赋值语句就被执行了一次。当i=2时，赋值语句被执行了1＋2次。当i=3时，赋值语句被执行了1＋2＋3次。可以推出赋值语句总共被执行了1＋（1＋2）＋（1＋2＋3）＋…＋（l ＋2＋... ＋n ）=n（n ＋1）（n ＋2）/6次。

9． 对n 个记录的表r[l..n]进行简单选择排序，所需进行的关键字间的比较次数为_____。

【答案】n （n-1）/2

【解析】第一次需要n-1次比较，第i 此需要n-i 此比较，所以共需要、n-l+n-2+...+l=n（n-l ）/2。

10．顺序查找n 个元素的顺序表，若查找成功，则比较关键字的次数最多为_____次；当使用监视哨时，若查找失败，则比较关键字的次数为_____。 【答案】

视哨。

11．线性表

【答案】（n －1）/2

【解析】删除第一个元素需要移动n －i 次，以此类推，删除最后一个元素需要移动0次。平 均次数为

12．已知一循环队列的存储空间为环队列判满的条件是（ ） 【答案】

【解析】最多的情况就是把整个表遍历了一遍。使用监视哨时，需要多一个存储空间来存监用数组表示，假定删除表中任一元素的概率相同，则删除一个元素平均需要移动元素的个数是_____。 其中队头和队尾指针分别为front 和rear , 则此循

二、选择题

13．要连通具有n 个顶点的有向图，至少需要（ ）条边。

A.n-1

B.n

C.n+1

D.2n

【答案】B

【解析】对于有向图来说，两个顶点之间的边是具有方向的。如果是构成连通的无向图，需要n-1条边，而对于有向图来说，只需要再加上第一个顶点和最后一个顶点加上一条边，让其构成环状的图即可，因此最少需要n 条边。

14．—次总线事物中，主设备只需给出一个首地址，从设备就能从首地址开始的若干连续单元格读出或写入的个数，这种总线事务方式称为（ ）

A. 并行传输

B 串行传输

C. 突发

D. 同步

【答案】C

【解析】猝发数据传输方式：在一个总线周期内传输存储地址连续的多个数据字的总线传输方式

15．主机甲与主机乙之间使用后退N 帧协议（GBN ）传输数据，甲的发送窗口尺寸为1000, 数据帧长为1000字节，信道宽带为100Mbps ，乙每收到一个数据帧立即利用一个短帧（忽略其传输延迟）进行确认，若甲乙之间 的单向传播延迟是50ms ，则甲可以达到的最大平均数据传输速率约为（ ）

A .10 Mbps

B. 20 Mbps

C.80 Mbps

D.100 Mbps

【答案】C 【解析】

16．若线性表最常用的操作是存取第I 个元素及其前驱和后继元素的值，为节省时间应采用的存储方式（ ）。

A. 单链表

B. 双向链表

C. 单循环链表

D. 顺序表

【答案】D

【解析】线性表采用顺序表，便于进行存取任一指定序号的元素。