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

一、填空题

1． 己知有序表为（12，18，24，35，47，50，62，83，90，115，134）当用二分法查找90时，需_____次查找成功，查找47时_____成功，查找100时，需_____次才能确定不成功。

【答案】2；4；3

【解析】二分法查找元素次数列表

查

找100是找到115就停止了。

2． 在顺序存储的二叉树中，编号为i 和j 的两个结点处在同一层的条件是_____。

【答案】要加“虚结点”。

设编号为

和

的结点在顺序存储中的下标为

和

。

3． 克鲁斯卡尔算法的时间复杂度为_____，它对_____图较为适合。

【答案】O （eloge ）; 边稀疏

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

【答案】由空格字符（

值32）所组成的字符串；空格个数

5． 假定有k 个关键字互为同义词，若用线性探测再哈希法把这k 个关键字存入哈希表中，至少要进行_____次探测。

【答案】

【解析】当该关键字发生冲突时，用线性探测不会遇到别的关键字冲突，这个时候需要探测 的次数最小。总次数为

6． 对于双向链表，在两个结点之间插入一个新结点需修改的指针共_____个，单链表为_____个。

【答案】4; 2

，

则结点

和

在同一层上的条件是

【解析】用顺序存储结构存储二叉树时，要按完全二叉树的形式存储，非完全二叉树存储时，

7． 有向图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

8． 设广义表

则

是_____tail（L ）是_____；L 的长度是_____；深度是_____。

；；2；2 【答案】（ ）（（ ））

【解析】广义表的表头是表的第一个元素，表尾是除了第一个元素外其余的所有的元素构成的表；表的长度指表中元素的个数；表的深度指展开后括号的层数。

9． 若用n 表示图中顶点数目，则有_____条边的无向图成为完全图。

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

【解析】无向完全图中任意一个顶点都和其他n-1个顶点都有一条边，即为n （n-l ）。又因为每条边重复出现两次，所有无向完全图的边数为n （n-l ）/2。

10．二叉树由_____，_____，_____三个基本单元组成。

【答案】根结点；左子树；右子树

二、选择题

11．循环两列放在一维数组

中，endl 指向队头元素，end2指向队尾元素的后一个位置。

假设队列两端均可进行入队和出队操作，队列中最多能容纳M-1个元素。初始时为空，下列判断队空和队满的条件中，正确的是（ ）

A. 队空

：B. 队空：C. 队空：D. 队空：【答案】A

【解析】在循环队列中，在少用一个元素空间的前提下，可约定入队前，测试尾指针在循环意义下加1后是否等于头指针，若相等，则队满。而队空的条件还是首尾指针是否相等。

12．下列关于无向连通图特性的叙述中，正确的是（ ）。

I. 所有的顶点的度之和为偶数 II. 边数大于顶点个数减1 III. 至少有一个顶点的度为1 A. 只有I B. 只有II

队满：队满

：

队满：

modM ; 队满：

C.I 和II D.I 和III 【答案】A

【解析】在图中，顶点的度TD 点数，

e 为总边数），因此，I 项正确。对于II 、III 项中的特性不是一般无向连通图的特性，可以轻松地举出反例。“至少有一个顶点的度为1”的反例如下图（1）所示，“边数大于顶点个数减1”的反例如下图（2）所示。

之和与边的数目满足关系式：

（n 为图的总结

图

13．下列选项中，对正确接收到的数据帧进行确认的MAC 协议是（ ）。

A.CSMA B.CDMA C.CSMA/CD D.CSMA/CA 【答案】D

【解析】可采用排除法。CDMA 是码分多址复用，是物理层的内容；CSMA/CD即带冲突检测的载波监听多 路访问，接收方并不需要确认；CSMA/CD是CSMA 的加强版，故CSMA 也无确定；CSMA/CD是802.11中的 协议，其利用ACK 信号来避免冲突的发生，也就是说，只有当 客户端收到网络上返回的ACK 信号后才确认送 出的数据已经正确到达目的地址，因此答案是D 。

14．在文件的索引节点中存放直接索引指针10个，一级二级索引指针各1个，磁盘块大小为1KB 。每个索引指针占4个字节。若某个文件的索引节点已在内存中，到把该文件的偏移量（按字节编址）为1234和307400 处所在的磁盘块读入内存。需访问的磁盘块个数分别是（ ）。

A.1, 2 B.1, 3 C.2, 3 D.2, 4

【答案】B

【解析】文件的索引结点的直接索引指针有10个，因此直接索引的偏移量范围是级索引的偏移量范围是

二级索引访问的偏移量范围是

一

偏移量1234

可以通过直接索引得到在磁盘块的地址，因此需要一次访问，307400需要通过二级索引查找其在