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

一、填空题

1． VSAM 系统是由_____、_____、_____构成的。

【答案】索引集；顺序集；数据集

2． 如下的算法分别是后序线索二叉树求给定结点node 的前驱结点与后继结点的算法，

请在算法空格处填上正确的语句。 设线索二叉树的结点数据结构为其中:

left 指向其左孩子，

【答案】

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

【答案】

第 2 页，共 78 页

，

left 指向其前驱；，

right 指向其右孩子，，

，

right 指向其后继。

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

4． 设T 是一棵结点值为整数的二叉排序树，A 是一个任意给定的整数。在下面的算法中，free_tree(T)在对二叉排序树丁进行后序遍历时释放二又排序树T 的所有结点

；

，首先在二叉排序树T 中查找值为A 的结点，根据查找情况分别进行如下

处理:(1)若找不到值为A 的结点，则返回根结点的地址(2)若找到值为A 的结点，则删除以此结点为根的子树，并释放此子树中的所有结点，若值为A 的结点是查找树的根结点，删除后变成空的二叉树，则返NULL ; 否则返回根结点的地址。

【答案】

5． 在一个具有n 个单元的顺序栈中，假定以地址高端(即下标为n 的单元) 作为栈底，以top 作为栈顶指针，则当向栈中压入一个元素时，top 的变化是top ＝_____。

【答案】top ﹣1

【解析】由于栈底在地址高端，栈中压入一个元素时，栈顶向地址底端移动一个单位，所以top ﹣1。

6． 设单链表的结点结构为(data，next) ，next 为指针域，已知指针px 指向单链表中data 为x 的结点，指针py 指向data 为y 的新结点，若将结点y 插入结点x 之后，则需要执行以下语句: _____；_____；

【答案】py ﹣＞next ＝px ﹣＞next ；px ﹣＞next ＝py

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

【答案】顺序存储结构

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

8． 设有N 个结点的完全二叉树顺序存放在向量 中，其下标值最大的分支结点为_____。

【答案】

第 3 页，共 78 页

【解析】最大的分支结点是最后一个叶子结点的父结点。

9． 已知链队列的头尾指针分别是f 和r ，则将值x 入队的操作序列是_____。

【答案】S ＝(LinkedList*)malloc(sizeof (LNode))；s ﹣＞data ＝x ；s ﹣＞next ＝r ﹣＞next ；r ﹣＞next ＝s ；r ＝s ；

【解析】队列采用链式存储结构，先分配一个节点的内存，然后在队尾添加该节点。 10．已知；；ASSIGN(S，U) ；ASSIGN(V，SUBSTR(S，INDEX(S，t) ，LEN(t)＋1))

:

【答案】

，求REPLACE(S，V ，m) ＝_____。

二、单项选择题

11．某计算机采用二级页表的分页存储管理方式，按字节编址，页大小为2字节，逻辑地址结构为:

逻辑地址空间大小为（ ）.

A.64 B.128 C.256 D.512

【答案】B

【解析】地址空间分为逻辑地址空间和物理地址空间. 页的大小为采用二级页表，

一页可存放

个页面来保存页表项，故本题答案为B.

12．对进行基数排序，一趟排序的结果是:（ ）

A. 05， 46， 13， 55， 94， 17， 42 B. C. 42，13， 94，05， 55， 46，17 D. 05，13， 46，55，17，42，94

【答案】C

【解析】基数排序有两种:最低位优先和最高位优先。 ①最低位优先的过程

先按最低位的值对记录进行排序，在此基础上，再按次低位进行排序，依此类推。由低位向高位，每趟都是 根据关键字的一位并在前一趟的基础上对所有记录进行排序，直至最高位，则完成了基数排序的整个过程。

②以r 为基数的最低位优先排序的过程

第 4 页，共 78 页

字节，页表项大小为

页，则表示整个逻辑地址空间的页目录表中包含表项的个数至少是

字节，页表项大小为2B ，

字节，

故最少需要

个页表项，本题中逻辑地址空间大小为