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

一、填空题

1． 设数组

数组中任一元素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。

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

【答案】4；2

3． 在进行入栈运算时应先判别栈是否_____:在进行出栈运算时应先判别栈是否_____:当栈中元素为n 个，进行入栈运算时发生上溢，则说明该栈的最大容量为_____。为了增加内存空间的利用率和减少溢出的可能性，由两个栈共享一片连续的空间时，应将两栈的_____分别设在内存空间的两端，这样只有当_____时才产生溢出。

【答案】满；空；n ；栈底；两栈顶指针相邻(即值之差的绝对值为1)

4．

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

【答案】5；96

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

第 2 页，共 35 页

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

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

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

6． 下列程序是快速排序的非递归算法，请填写适当的语句，完成该功能。

a 中存放待排序的关键字

【答案】

【解析】快速排序(quick sort)的基本思想是，通过一趟排序将待排记录分割成独立的两部分，其中一部分记录的关键字均比另一部分记录的关键字小，则可分别对这两部分记录继续进行排序，以达到整个序列有序。

7． 当线性表的元素总数基本稳定，且很少进行插入和删除操作，但要求以最快的速度存取线性表中的元素时，应采用_____存储结构。

【答案】顺序

【解析】顺序存储结构的存取操作比较方便，但插入和删除操作不如链式存储结构方便，而且需要连续的存储空间，由于该线性表的元素总数基本稳定，而且很少进行插入删除操作，为了更快的存取元素，顺序表更合适。

8．

【答案】5

第 3 页，共 35 页

＝_____

9． 设有一个10阶对称矩阵A 采用压缩存储方式(以行为主序存储:a 11＝l) ， 则a 85的地址为_____。

【答案】33

【解析】设存储的元素的行标为i ，列标为j 。若i ＞＝j ，则＝i(i﹣l)/2＋j 。若i ＜j 。则

10．

线性表

【答案】(n﹣1)/2

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

11．堆是一种有用的数据结构。堆排序是一种_____排序，堆实质上是一棵_____结点的层次序列。对含有N 个元素的序列进行排序时，堆排序的时间复杂度是_____，所需的附加存储结点是_____。关键码序列05, 23, 16, 68, 94, 72, 71, 73是否满足堆的险质_____ 。

【答案】选择；完全二叉树；

；O(1)；满足堆的性质

12．一个算法具有5个特性: _____、_____、_____、有零个或多个输入、有一个或多个输出。

【答案】有穷性；确定性；可行性

13．n 个顶点的有向图用邻接矩阵array 表示，下面是其拓扑排序算法，试补充完整。

注:(1)图的顶点号从0开始计；

(2)indegree是有n 个分量的一维数组，放顶点的入度， (3)函数crein 用于记算顶点入度； (4)有三个函数回1，否则0) 。

第 4 页，共 35 页

的地址为l ＋2＋... ＋i ﹣l ＋j

的地址为j(j﹣l)/2＋i 。将i ＝8，j ＝5代入得33。

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

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

其含义为数据data 入栈，出栈和测试栈是否空(不空返