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

一、填空题

1． 从用户的观点看，文件的逻辑结构通常可以区分为两类:一类是如NdBASE 中数据库文件那样的文件组织结构，称为_____文件; 另一种是诸如用各种文字处理软件编辑成的文本文件，称为_____文件。从文件在存储器上的存放方式来看，文件的物理结构往往可区分为三类，即_____， _____和_____。B+树适用于组织_____的索引结构，m 阶B+树毎个结点至多有_____个儿子，除根结点外每个结点至少有_____个儿子，根结点至少有_____个儿子，有k 个儿子的结点必有_____个关键码。

【答案】数据库；文本；顺序组织；随机组织；链组织；随机组织；m ;

2． 组成串的数据元素只能是_____。

【答案】字符

3． 求图的最小生成树有两种算法，_____算法适合于求稀疏图的最小生成树e

【答案】克鲁斯卡尔

【解析】克鲁斯卡尔算法是一种按权值的递增次序选择合适的边来构造最小生成树的方法，这种算法中，采用堆来存放边的集合，适合于边稀疏而顶点较多的图。

4． 空格串是指_____，其长度等于_____。

【答案】由空格字符(ASCII值32) 所组成的字符串；空格个数

5． G 是一个非连通无向图，共有28条边，则该图至少有_____个顶点。

【答案】9

【解析】求该非连通无向图的最少顶点数，则该图为一个孤立的顶点和一个完全连通图。

6． 对于一个具有n 个结点的单链表，在已知的结点半p 后插入一个新结点的时间. 复杂度为_____，在给定值为x 的结点后插入一个新结点的时间复杂度为_____。

【答案】O(1)；O(n)

【解析】第一种情况只需直接修改指针的指向。第二种情况必须从头结点遍历找到x 的结点。

；2；k

7． 检索是为了在文件中寻找满足一定条件的记录而设置的操作。检索可以按_____检索。也可以按_____检索；按_____检索又可以有 检索和_____检索。

【答案】关键字；记录号；记录号；顺序；直接

8． 文件由_____组成；记录由_____组成。

【答案】记录；数据项

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

【答案】出度为0

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

10．已知二维数组中每个元素占4个单元，在按行优先方式将其存储到起始地址为1000的连续存储区域时，A[5，9]的地址是: _____。

【答案】1196

【解析】设元素的行标为i ，列标为j 。则它的存储位置为:l000＋[(i﹣l)*l0＋(j﹣0)]*4

11．下面程序的功能是用递归算法将一个整数按逆序存放到一个字符数组中。如123存放成321。请填空:

(_____i)；

＝

_____.

_____

【答案】a ＋l ；n%10

【解析】通过递归算法，首先找到最高位的值，将其放到str 对应的数组中，依次反向获取从高位到地位的值，将其放到数组中，完成了将整数逆序放到一个字符数组中。

12．设用希尔排序对数组{98，36，-9，0，47，23，1，8，10，7}进行排序，给出的步长(也称增

量序列) 依次是4， 2， 1则排序需_____趟，写出第一趟结束后，数组中数据的排列次序_____。

【答案】3; (10，7，-9，0，47，23，1，8，98，36)

二、单项选择题

13．主机甲和乙已建立了TCP 连接, 甲始终以MSS=1KB大小的段发送数据, 并一直有数据发送; 乙每收到一个数据段都会发出一个接收窗口为10KB 的确认段。若甲在t 时刻发生超时时拥塞窗口为8KB , 则从t 时刻起, 不再发生超时的情况下, 经过10个RTT 后, 甲的发送窗口是（ ）

A.10KB

B.12KB

C.14KB

D.15KB

【答案】A

【解析】发送窗口是接受窗口和拥塞窗口的最小值, 这里接收窗口总是10KB 。拥塞窗口到那个时候是大于10KB 的, 取最小值。

14．设n 是描述问题规模的非负整数, 下面程序片段的时间复杂度是（ ）。

A. B. C. D.

【答案】A

【解析】其中, 以基本的原操作重复执行的次数作为算法的时间度量。题目中的基本运算是语

句, 设其执行时间为, 则有即。

15．下列关于IP 路由器功能的描述中, 正确的是（ ）。

Ⅰ. 运行路由协议, 设置路由表;

Ⅱ. 监测到拥塞时, 合理丢弃IP 分组;

Ⅲ. 对收到的IP 分组头进行差错校验, 确保传输的IP 分组不丢失;

Ⅳ. 根据收到的IP 分组的目的IP 地址, 将其转发到合适的输出线路上。

A. 仅Ⅲ、Ⅳ

B. 仅Ⅰ、Ⅱ、Ⅲ

C. 仅Ⅰ、Ⅱ、Ⅳ

D. Ⅰ、Ⅱ、Ⅲ、Ⅳ

【答案】C 。

【解析】路由器的主要功能是路由和转发, 因此Ⅰ和Ⅳ是正确的, 而针对Ⅱ和Ⅲ, 可以从ICMP 协议的差错控制出发, 注意检测到拥塞时, 合理丢弃IP 分组, 并回传ICMP 源抑制报文, Ⅱ是正确的, 而Ⅲ对收到的IP 分组头进行差错校验, 确保传输的IP 分组不丢失, 差错校验是正确的, 但网络层不

保证IP 分组不丢失, 也就是不可靠的, 因此Ⅲ的说法错误, 正确的说法仅Ⅰ、Ⅱ、Ⅳ, 因此答案是C 。