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

一、填空题

1． 在单链表L 中，指针P 所指结点有后继结点的条件是_____

【答案】P ﹣＞next! ＝NULL

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

2． 高度为h 的堆中，最多有_____元素，最少有_____个元素。

【答案】

。当最后一层只有

【解析】当这个堆构成的是满二叉树时，元素的个数最多，元素个数为一个元素时，此时堆的元素个数最少，元素个数为。

3． 阅读下列程序，指出其功能，并写出空格处应填上的语句。

【答案】

【解析】本题是在哈希表中插入值为item 的元素，如该元素已在哈希表中，报告出错。

4． 在n 个顶点的非空无向图中，最多有_____个连通分量。

【答案】n

【解析】当n 个顶点之间没有边，都是孤立的顶点时，有n 个连通分量。

5． 无用单元是指_____，例_____

【答案】用户不再使用而系统没有回收的结构和变量；

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

【答案】2; 4; 3

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

查找100是找到115就停止了。 7． 已知；t) ，LEN(t)＋1))

:

【答案】

；ASSIGN(S，U) ；ASSIGN(V，SUBSTR(S，INDEX(S，，求REPLACE(S，V ，m) ＝_____。

8． —个有2001个结点的完全二叉树的高度是_____。

【答案】11

【解析】完全二叉树的高度

9． 对于一个具有n 个结点的二叉树，当它为一棵_____二叉树时具有最小高度, 当它为一棵_____时，具有最大高度。

【答案】完全；只有一个叶结点的二叉树

10．设为哈夫曼树的叶结点数目，则该哈夫曼树共有_____个结点。

【答案】

【解析】哈夫曼树只有度为0和2的节点。

11．栈是_____的线性表，其运算遵循_____的原则。

【答案】操作受限(或限定仅在表尾进行插入和删除操作) ；后进先出

12．对n 个记录的表

【答案】n (n－1) /2

【解析】第一次需要n －1次比较，第i 此需要n －i 此比较，所以共需要

。

进行简单选择排序，所需进行的关键字间的比较次数为_____。

二、单项选择题

13．当在一个有序的顺序存储表上查找一个数据时，既可用折半查找，也可用顺序查找，但前者比后者的查找速度（ ）。

A. 必定快 B. 不一定

C. 在大部分情况下要快 D. 取决于表递增还是递减 【答案】C

【解析】对于有序顺序存储表折半查找的效率较高，但是不是所有情况下都是如此，比如要查找的元素就是第一个时，用顺序查找比它就快的多了。这类情况外折半都高于顺序查找。

14．输入序列为ABC ，可以变为CBA 时，经过的栈操作为（ ）。

A.push ，pop ，push ，pop ，push ，pop B.push ，push ，push ，pop ，pop ，pop C.push ，push ，，pop ，pop ，push ，pop D.push ，pop ，push ，push ，pop ，pop

【答案】B

【解析】根据输入序列和输出序列可知，输入序列全部进找，然后再出找。从中可以看出，push 的数目始终大于等于pop 的数目。

15．某计算机主存地址空间大小为256MB , 按字节编址。虚拟地空间大小为4GB , 采用页式存储管理, 页面大小为4KB , TLB(快表) 采用全相联映射, 有4个页表项, 内容如下表所示。

则对虚拟地址03FFF180H 进行虚实地址变换的结果是（ ）

A.0153180H B.0035180H C.TLB 缺失 D. 缺页 【答案】A

【解析】虚拟地址为03FFF180H , 其中页号为03FFFH , 页内地址为180H , 根据题目中给出的页表项可知页标记为03FFFH 所对应的页框号为0153H ,

页框号与页内地址之和即为物理地址

。

16．某线性表中最常用的操作是在最后一个元素之后插入一个元素和删除第一个元素，则采用（ ）存储方式最节省运算时间。

A. 单链表

B. 仅有头指针的单循环链表 C. 双链表

D. 仅有尾指针的单循环链表