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

一、填空题

1． 有向图G=（V ，E ）, 其中V （G ）=[0, 1，2，3，4, 5}, 用三元组表示弧及弧上的权d 。 E （G ）为 E （G= {<0，5, 100>, <0，2，10>, <1，2，5>，<0，4, 30>，<4, 5, 60>，<3，5, 10>，<2. 3，50>， <4, 3, 20>}，则从源点0到顶点3的最短路径长度是_____，经过的中间顶点是_____。

【答案】50; 4

2． —个字符串中_____称为该串的子串。

【答案】任意个连续的字符组成的子序列

3． 下面描述的是一种构造最小生成树算法的基本思想。设要处理的无向图包括n

个顶点

用相邻矩阵A 表示，边的权全是正数。请在下列划线处填上正确叙述。

（1）若是边，则的值等于_____，若不是边，则的值是一个比任何边的权，矩阵的对角线元素全为0。

（2）构造最小生成树过程中，若顶点Vi 已包括进生成树，就把相邻矩阵的对角线元素A （i , i ）置成若

【答案】（1） 已包括进生成树，就把矩阵元素A （i ，j ）置成 边上的权值；都大的数；（2）1; 负值；（3）为负；边 （3）算法结束时，相邻矩阵中。

4． 从用户的观点看，文件的逻辑结构通常可以区分为两类：一类是如NdBASE 中数据库文件那样的文件组织结构，称为_____文件:另一种是诸如用各种文字处理软件编辑成的文本文件，称为_____文件。从文件在存储器上的存放方式来看，文件的物理结构往往可区分为三类，即_____，_____和_____。B+树适用于组织_____的索引结构，m

阶

个关键码。

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

5． VSAM （虚拟存储存取方法）文件的优点是：动态地_____，不需要文件进行_____，并能较快地_____进行查找。

【答案】分配和释放存储空间；重组；对插入的记录

树每个结点至多有_____个儿子，除根结点外每个结点至少有_____个儿子，根结点至少有_____个儿子，有k 个儿子的结点必有_____

6． 已知链队列的头尾指针分别是f 和r , 则将值x 入队的操作序列是_____。 【答案】

【解析】队列采用链式存储结构，先分配一个节点的内存，然后在队尾添加该节点。

7． 起始地址为480，大小为8的块，其伙伴块的起始地址是_____；若块大小为32，则其伙伴块的起始地址为_____。 【答案】

【解析】起始地址为P ，大小为的内存块，其伙伴块的起始地址计算公式如下：

根据上述公式起始地址就为488。

8． 设有个结点的完全二叉树顺序存放在向量

【答案】 中，其下标值最大的分支结点为_____。 【解析】最大的分支结点是最后一个叶子结点的父结点。

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

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

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

【答案】顺序存储结构

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

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

【答案】23; 100CH

12．在单链表L 中，指针P 所指结点有后继结点的条件是_____ 【答案】

【解析】指针所指节点的指针域所指向的元素非空，说明该指针所指节点有后继结点。

二、选择题

13．下列关于UDP 协议的叙述中，正确的是（ ）

I 提供无连接服务

II 提供复用/分用服务

III 通过差错校验，保障可靠数据传输

A. 仅I

B. 仅 I 、II

C. 仅 II 、III

D.I 、II 、III

【答案】B

【解析】UDP 无连接创建，提供多路复用服务。虽然有差错检验，但是不能保证可靠数据传输，所以III 错误。

14．float 型数据通常用IEEE754单精度浮点数格式表示。若编译器将float 型变量x 分配在一个32位浮点寄存器FR1中，且x=-8.25, 则FR1的内容是（ ）。

A.C1040000H

B.C2420000H

C.C1840000H

D.C1C20000H

【答案】A

【解析】首先将十进制数转换为二进制数-1000.01，接着把它写成规格化形式（按IEEE754标准），然后计算阶码的移码=偏置值+阶码真值=127+3 = 130, 最后短浮点数代码：数符位=1, 阶码= 10000010, 尾数00001000000000000000000, 写成十六进制为C1040000H 。选项D 是一

个很容易被误选的选项，其错误在于没有考虑IEEE754标准中隐含最高位1的情况，偏置值是128。

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

A. 快速排序

B. 堆排序

C. 归并排序

D. 直接插入排序

【答案】C

【解析】稳定排序有：插入排序、起泡排序、归并排序、基数排序。不稳定排序有：快速排序、堆排序、shell 排序。时间复杂度平均为的有：归并排序、堆排序、shell 排序、快速排序。

16．已知一个长度为16的顺序表L , 其元素按关键字有序排列。若采用折半查找法查找一个L 中不存在的元素，则关键字的比较次数最多是（ ）。

A.4

B.5

C.6

D.7

【答案】B