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

一、填空题

1．

线性表

【答案】(n﹣1)/2

【解析】删除第一个元素需要移动n ﹣1次，以此类推，删除最后一个元素需要移动0次。平均次数为(n﹣l)*n/n/2＝(n﹣l)/2。

2． 一棵有11个结点的满二叉树有_____个度为1的结点、有_____个分支(非终端) 结点和_____个叶子，该满二叉树的深度为_____。

【答案】

或

【解析】满二叉树没有度为1的结点，度为0的结点等于度为2的结点个数+1。

3． 在一个无向图的的邻接表中，若表结点的个数是m ，则图中边的条数是_____条。

【答案】

【解析】对于无向图，在邻接表中，如果存在n 条边，则会有2n 个表结点。

4． 设数组数组中任一元素A[i，j]均占内存48个二进制位，从首地址2000开始连续存放在主内存里，主内存字长为16位，那么

(1)存放该数组至少需要的单元数是_____；

(2)存放数组的第8列的所有元素至少需要的单元数_____； (3)数组按列存储时，元素A[5，8]的起始地址是_____。 【答案】270；27；2204

【解析】数组的元素个数为9*10＝90，因为每个元素占内存48个二进制位，即6个字节。故总需要90*6＝540个字节，因为主内存字长为16位，即2个字节，所以至少需要540/2＝270个单元数。第8列有9个元素，共占9*6＝54个字节，因此至少需要54/2＝27个单元数。由题知，每个元素占3个单元。按列存储时，A[5，8]的起始地址为2000＋[(8﹣1)*9＋(5﹣0)]*3＝2204。

5． 建立索引文件的目的是_____。

【答案】提高查找速度

用数组表示，假定删除表中任一元素的概率相同，则删除一个元

素平均需要移动元素的个数是_____。

6．

给定一组数据WPL 的值为_____。

【答案】5；96

以它构造一棵哈夫曼树，则树高为_____，带权路径长度

【解析】每次找两个最小的权值构建哈夫曼树:

7． 阅读下列程序说明和程序，填充程序中的_____。

【程序说明】本程序完成将二叉树中左、右孩子交换的操作。交换的结果如下所示。 本程序采用非递归的方法，设立一个堆栈stack 存放还没有转换过的结点，它的栈顶指针为tp 。交换左、右子树的算法为:

(1)把根结点放入堆栈。

(2)当堆栈不空时，取出栈顶元素，交换它的左、右子树，并把它的左、右子树分别入栈。 (3)重复(2)直到堆栈为空时为止。

【答案】

【解析】本题主要使用堆栈完成了二叉树左右子树交换的操作。首先根结点进栈，然后判断栈是否为空，如果不为空，则取栈顶元素，交换取出结点的左右指针。并将左右指针分别进栈，重复这一操作。完成二叉树左右孩子的交换。

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

【答案】索引集；顺序集；数据集 9． 假定查找有序表

【答案】

表

中每个元素的概率相等，则进行折半查找时的平均查找长度为_____。

【解析】折半查找时每个的次数如表所示:

平均查找次数为。

10．设正文串长度为n ，模式串长度为m ，则串匹配的KMP 算法的时间复杂度为_____。

【答案】O(m＋n)

11．在哈希函数

中，p 值最好取_____。

【答案】小于等于表长的最大素数或不包含小于20的质因子的合数

【解析】在使用除留余数法时，对除数P 的选择很重要。若P 选的不好，容易产生同义词。一般情况下，可以选P 为质数或不包含小于20的质因素的合数。

12．以下程序的功能是实现带附加头结点的单链表数据结点逆序连接，请填空完善之。

h 为附加头结点指针

(_____)

_____；

【答案】(1)p!＝NULL //链表未到尾就一直进行 (2)q //将当前结点作为头结点后的第一元素结点插入

二、单项选择题

13．B 、C 通过CDMA 共享链路, A 、B 、C 的码片序列(chippingsequence)分别是(1, 1, 1, 1) 、站点A 、(1, -1, 1, -1) 和(1, 1, -1, -1) , 若C 从链路上收到的序列是(2, 0, 2, 0, 0, -2, 0, -2, 0, 2, 0, 2) , 则C 收到A 发送的数据是（ ）

A.000 B.101 C.110 D.111

【答案】B

【解析】用A 的码片与信息做内积运算

14．下列关于RISC 的叙述中，错误的是（ ）.

A.RISC 普遍采用微程序控制器

B.RISC 大多数指令在一个时钟周期内完成 C.RISC 的内部通用寄存器数量相对CISC 多

D.RISC 的指令数、寻址方式和指令格式种类相对CISC 少