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

一、选择题

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

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

【答案】B

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

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

一

偏移量1234

可以通过直接索引得到在磁盘块的地址，因此需要一次访问，307400需要通过二级索引查找其在磁盘的位置，需要分别访问存放二级索引的两个索引块以及对应的数据块。

2． 设图的邻接矩阵A 如下所示，各顶点的度依次是（ ）

A.1, 2, 1, 2 B.2, 2, 1, 1 C.3, 4, 2, 3 D.4, 4, 2, 2 【答案】C

【解析】当图用邻接矩阵存储时，各顶点的度是矩阵中此结点对应的横行和纵列非零元素之和。

3． 若将关键字1，2, 3, 4, 5, 6, 7依次插入到初始为空的平衡二叉树T 中，则T 中平衡因子为0的分支结点的个数是（ ）

A.0

B.1 C.2 D.3

【答案】D

【解析】将图中给定的关键字序列依次插入到平衡树中，构成的平衡树如下图所示，由图可知平衡因子为0的分支结点为3个叶子结点，故答案为D 。

4． 折半查找的时间复杂性为（ ）。

【答案】D

【解析】顺序查找的事件复杂度为 度为

5． 引入二叉线索树的目的是（ ）。

A. 加快查找结点的前驱或后继的速度 B. 为了能在二叉树中方便地进行插入与删除 C. 为了能方便地找到双亲 D. 使二叉树的遍历结果唯一 【答案】A

【解析】二叉线索树有指向前驱和后继的指针，因此加快了查找前驱和后继结点的速度。

6． 在物理层接口特性中，用于描述完成每种功能的事件发生顺序的是（ ）。

A. 机械特性 B. 功能特性 C. 过程特性 D. 电气特性 【答案】C 。

【解析】物理层的主要任务描述为确定与传输媒体接口的一些特性；机械特性：主要定义物理连接的边界点，即接插装置；电气特性：规定传输二进制位时，线路上信号的电压高低、阻抗匹配、传输速率和距离限制；功能特性：主要定义各条物理线路的功能；规程特性：主要定义各条物理线路的工作规程和时序关系。而从题干可以 分析描述事件先后顺序的就是规程，也就是过程特性，答案是C 。

因为折半查找是查找效率最高的算法，它的事件复杂

7． 下列选项中，降低进程优先级的合理时机是（ ）。

A. 进程的时间片用完

B. 进程刚完成1/0, 进入就绪队列 C. 进程长期处于就绪队列 D. 进程从就绪状态转为运行态 【答案】A

【解析】进程时间片用完可以降低其优先级，完成

的进程应该提升其优先级，处于就绪队

列等待调度的进程一般不会改变其优先级。进行这样的操作主要是为了改善交互式系统的响应时间，并均衡各个作业的公平性。采用时间片轮转技术主要为改善交互式用户的感受，使其觉得是，时间片用完后降低其优独享计算机（时间片轮转可以有效地防止计算繁忙型的进程独占计算机）先级是为了改善新进程的响应时间（新进程优先级较高，老进程降低优先级可以保证新进程具有，对于刚进入就绪队列的新进程，往往在创建时已经根据其特点和要求确定好优先级，不优先权）

会随意改变。而对于从阻塞状态唤醒的进程，由于阻塞带来了较长时间的等待，一般会根据阻塞队列的不同适当地提高优先级，以改善用户响应时间。

8． 为提高散列（Hash ）表的查找效率，可以采用的正确措施是（ ）。

I .增大装填（载）因子

II. 设计冲突（碰撞）少的散列函数

III. 处理冲突（碰撞）时避免产生聚集（堆积）现象 A. 仅I B. 仅 II C. 仅 I 、II D. 仅 II 、III 【答案】D

【解析】散列表的查找效率（比较次数）取决于：散列函数、处理冲突的方法和散列表的装填因子a 。CX 标 志着散列表的装满程度，通常情况下，（X 越小，发生冲突的可能性越小；反之，a 越大，表示已填入的记录越多， 再填入记录时，发生冲突的可能性越大。因此选项I 错误，越是增大装填因子，发生冲突的可能性就越大，查找 效率也越低。选项II 正确。选项III 正确。采用合适的处理冲突的方法避免产生聚集现象，也将提高查找效率。例如，用拉链法解决冲突时不存在聚集现象，用线性探测法解决冲突时易引起聚集现象。

9． 栈和队的共同点是（ ）。

A. 都是先进后出 B. 都是后进先出

C. 只允许在端点处插入和删除元素 D. 没有共同点 【答案】C

【解析】栈和队列的区别是栈是先进后出的数据结构，队列是先进先出的数据结构，栈和队列的共同点是都只能在端点处插入和删除元素。