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

一、填空题

1． 设m 、n 均为自然数，m 可表示为一些不超过n 的自然数之和，f(m，n) 为这种表示方式的数目。例f(5，3) ＝5, 有5种表示方式:3＋2, 3＋1＋1，2＋2＋1，2＋1＋1＋1，1＋1＋1＋1＋1。

①以下是该函数的程序段，请将未完成的部分填入，使之完整。

_____

_____；

}

_____；

}

，

_____)

②执行程序，f(6，4) ＝_____。

【答案】①1; 1; f(m, n ﹣1) ; n ②9

2． 实现字符串拷贝的函数strcpv 为:

(_____)

【答案】s++＝*t++或(*s++＝*t++)!＝'\0’

3． 已知二维数组

【答案】1196

【解析】设元素的行标为i ，列标为j 。则它的存储位置为:l000＋[(i﹣l)*l0＋(j﹣0)]*4

4． 循环队列的引入，目的是为了克服_____。

【答案】假溢出时大量移动数据元素

【解析】用数组实现队列时，如果不移动，随着数据的不断读写，会出现假满队列的情况。即尾数组已满但头数组还是空的。循环队列也是一种数组，引入循环队列，有效克服假溢出大量

中每个元素占4个单元，在按行优先方式将其存储到起始地址为1000的连续存储区域时，A[5，9]的地址是: _____。

移动数据元素的问题。

5． 设有N 个结点的完全二叉树顺序存放在向量

【答案】 中，其下标值最大的分支结点为_____。

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

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

h 为附加头结点指针

(_____)

_____；

【答案】(1)p!＝NULL //链表未到尾就一直进行

(2)q //将当前结点作为头结点后的第一元素结点插入

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

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

8． 起始地址为480，大小为8的块，其伙伴块的起始地址是_____；若块大小为32, 则其伙伴块的起始地址为_____; 。

【答案】480+8=488，480－32=448

【解析】起始地址为P ，大小为的内存块，其伙伴块的起始地址计算公式如下:

根据上述公式起始地址就为488。

9． 根据线性表的链式存储结构中每一个结点包含的指针个数，将线性链表分成_____和_____；而又根据指针的连接方式，链表又可分成_____和_____。

【答案】单链表；双链表；(动态) 链表；静态链表

【解析】线性表的链式存储结构根据每个结点包含的指针个数分为单链表和双链表，单链表只包含一个指针，指向后续元素，双链表包括两个指针，指向前一个元素和后续元素。根据指针的连接方式，链表可分为动态链表和静态链表。静态链表的指针指向下一个元素的编号，动态链表的指针指向下一个元素的物理位置。

10．从用户的观点看，文件的逻辑结构通常可以区分为两类:一类是如NdBASE 中数据库文件那样的文件组织结构，称为_____文件; 另一种是诸如用各种文字处理软件编辑成的文本文件，称为_____文件。从文件在存储器上的存放方式来看，文件的物理结构往往可区分为三类，即_____， _____和_____。B+树适用于组织_____的索引结构，m 阶B+树毎个结点至多有_____个儿子，除根结点外每个结点至少有_____个儿子，根结点至少有_____个儿子，有k 个儿子的结点必有_____个关键码。

【答案】数据库；文本；顺序组织；随机组织；链组织；随机组织；m ;

；2；k

二、判断题

11．一个稀疏矩阵A m*n采用三元组形式表示，若把三元组中有关行下标与列下标的值互换，并把m 和n 的值互换，则就完成了A m*n的转置运算。（ ）

【答案】 ×

【解析】稀疏矩阵转置后，除行列下标及行列数互换外，还必须确定该元素转置后在新三元组中的位置。

12．哈希表的平均查找长度与处理冲突的方法无关。（ ）

【答案】×

【解析】常见的处理冲突的方法:开放地址法；再哈希法；链地址法；建立一个公共的溢出区。选取不同的处理冲突的方法，哈希表的平均查找长度可能不同。

13．完全二叉树肯定是平衡二叉树。（ ）

【答案】×

【解析】从平衡因子定义看，完全二叉树任一结点的平衡因子的绝对值确实是小于等于1。但是，平衡二叉树本质上是二叉排序树，完全二叉树不一定是排序树。故不能说完全二叉树是平衡二叉树。

14．为了很方便的插入和删除数据，可以使用双向链表存放数据。（ ）

【答案】 √

【解析】链式存储结构便于数据的插入和删除，但只能顺序访问表中的元素。

15．KMP 算法的特点是在模式匹配时指示主串的指针不会变小。（ ）

【答案】 √

【解析】KMP 算法是一种字符串匹配的算法，KMP 算法的关键是利用匹配失败后的信息，尽量减少模式串与主串的匹配次数以达到快速匹配的目的。具体实现就是实现一个next （ ）函数，函数本身包含了模式串的局部匹配信息。