2018年北京联合大学计算机科学与技术801计算机综合之数据结构考研核心题库
● 摘要
一、填空题
1． 在循环队列中，队列长度为n ，存储位置从0到，n ﹣1编号，以rear 指示实际的队尾元素，现要在此队列中插入一个新元素，新元素的位置是_____。
【答案】
2． 设m 、n 均为自然数，m 可表示为一些不超过n 的自然数之和，f(m，n) 为这种表示方式的数目。例f(5，3) ＝5, 有5种表示方式:3＋2, 3＋1＋1，2＋2＋1，2＋1＋1＋1，1＋1＋1＋1＋1。
①以下是该函数的程序段，请将未完成的部分填入，使之完整。
_____
_____；
}
_____；
}
，
_____)
②执行程序，f(6，4) ＝_____。 【答案】①1; 1; f(m, n ﹣1) ; n ②9
3． 顺序查找n 个元素的顺序表，若查找成功，则比较关键字的次数最多为_____次；当使用监视哨时，若查找失败，则比较关键字的次数为_____。
【答案】n ; n+1
【解析】最多的情况就是把整个表遍历了一遍。使用监视哨时，需要多一个存储空间来存监视哨。
4． 对单链表中元素按插入方法排序的C 语言描述算法如下，其中L 为链表头结点指针。请填充算法中标出的空白处，完成其功能。
:_____:
{_____)
(_____、
:_____；_____；p ＝u ；
【答案】(1)L﹣＞next ＝NULL //置空链表，然后将原链表结点逐个插入到有序表中 (2)p!＝NULL //当链表尚未到尾，p 为工作指针
(3)q!＝NULL //查P 结点在链表中的插入位置，这时q 是工作指针 (4)p﹣＞next ＝r ﹣＞next //将P 结点链入链表中
(5)r﹣＞next ＝p //r是q 的前驱，u 是下个待插入结点的指针
5． 阅读下列程序，指出其功能，并写出空格处应填上的语句。
【答案】
【解析】本题是在哈希表
中插入值为item 的元素，如该元素已在哈希表中，报告出错。
二、单项选择题
6． 某容量为256M 的存储器, 由若干4M*8位的DRAM 芯片构成, 该DRAM 芯片的地址引脚和数据引脚总数是:（ ）
A.19 B.22 C.30 D.36
【答案】A
【解析】DREAM 地址线复用, 4M 为2的22次方, 因此除2为11根, 数据线8根。因此地址引脚和数据引脚总数为19根
7． 主机甲和主机乙之间已建立了一个TCP 连接，TCP 最大段长度为1000字节，若主机甲的当前拥塞窗口为4000字节，在主机甲向主机乙连续发送两个最大段后，成功收到主机乙发送的对第一个段的确认段，确认段中通告的接收窗口大小为2000字节，则此时主机甲还可以向主机乙发送的最大字节数是（ ）.
A.1000 B.2000 C.3000 D.4000 【答案】A
【解析】发送方的发送窗口的上限值应该取接收方窗口和拥塞窗口这两个值中较小的一个，于是此时发送方的发送窗口为min{4000，2000) ＝2000字节，由于发送方还没有收到第二个最大段的确认，所以此时主机甲还可以向主机乙发送的最大字节数为2000－1000＝1000字节，正确选项为A.
8． 一棵3阶B-树中含有2047个关键字，包括叶结点层，该树的最大深度为（ ）。
A.11 B.12 C.13 D.14
【答案】B
9． float 类型(即IEEE754单精度浮点数格式) 能表示的最大正整数是（ ）。
A. B. C. D. 【答案】D 。
【解析】IEEE754单精度浮点数尾数采用隐藏位策略的原码表示, 且阶码用移码表示的浮点数。规格化的短浮点数的真值为:
故float 类型能表示的最大整数是
。
10．循环队列存储在数组A[0..m]中，则入队时的操作为（ ）。
A.rear ＝rear ＋l
B.rear ＝(rear＋1)mod(m﹣1) C.rear ＝(rear＋1)modm D.rear ＝(rear＋1)mod(m＋1) 【答案】D
, S 为符号位, E 的取值为
, f 为23位;