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

一、填空题

1． 实现字符串拷贝的函数strcpy 为：

【答案】

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

【答案】提高查找速度

3． 已知二维数组

为1000的连续存储区域时

，

【答案】1196

【解析】设元素的行标为i ，列标为j 。则它的存储位置为：

4． —棵左子树为空的二叉树在前序线索化后，其中的空链域的个数为 _____。

【答案】2

【解析】只有根结点的做指针为空和最右边的叶结点的右指针为空。

5． 中缀式对应的前缀式为_____，若则后缀式

运算结果为_____。 【答案】

【解析】中缀式相当于中序遍历，前缀式相当于前序遍历，后缀式相当于后序遍历。

6． 已知链队列的头尾指针分别是f 和r , 则将值x 入队的操作序列是_____。 【答案】

【解析】队列采用链式存储结构，先分配一个节点的内存，然后在队尾添加该节点。

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

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

中每个元素占4个单元，在按行优先方式将其存储到起始地址的地址是：_____。 的

8． 求图的最小生成树有两种算法，_____算法适合于求稀疏图的最小生成树e

【答案】克鲁斯卡尔

【解析】克鲁斯卡尔算法是一种按权值的递增次序选择合适的边来构造最小生成树的方法，这种算法中，采用堆来存放边的集合，适合于边稀疏而顶点较多的图。

9．

=_____

【答案】5

10．顺序存储结构是通过_____表示元素之间的关系的；链式存储结构是通过_____表示元素之间的关系的。

【答案】物理上相邻；指针

【解析】顺序存储结构是通过物理位置表示元素之间的关系的，链式存储结构通过指针表示元素之间的关系。

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

【答案】单链表；双链表；（动态）链表；静态链表

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

12．从平均时间性能而言，_____排序最佳。

【答案】快速

【解析】快速算法的平均时间复杂度为nlogn 。

13．文件由_____组成；记录由_____组成。

【答案】记录；数据项

14．在二叉树中，指针p 所指结点为叶结点的条件是_____。 【答案】

【解析】叶子节点的左右孩子都不存在。

15．当广义表中的每个元素都是原子时，广义表便成了_____。

【答案】线性表

【解析】如果每个元素都是原子，则元素不可分。此时的元素是只有一对一的关系，所以广义表变成了线性表。

二、判断题

16．树形结构中元素之间存在一对多的关系。（ ）

【答案】√

【解析】树形结构是非线性结构，存在一对多的关系。

17．健壮的算法不会因非法的输入数据而出现莫名其妙的状态。（ ） 【答案】

【解析】算法的健壮性是指当输入数据非法时，算法能作适当的处理并作出反应，而不应死机或输出异常结果。

18．稀疏矩阵压缩存储后，必会失去随机存取功能。（ ）

【答案】√

【解析】稀疏矩阵在压缩存储后，必回失去随机存储的功能。因为在这个矩阵中，非零元素的分布是没有规律的，为了压缩存储，就将每一个非零元素的值和它所在的行、列号做为一个结点存放在一起，这样的结点组成的线性表中叫三元组表，它已不是简单的向量，所以无法用下标直接存取矩阵中的元素。

19．广义表的取表尾运算，其结果通常是个表，但有时也可是个单元素值。（ ）

【答案】×

【解析】广义表的取表尾运算，是非空广义表除去表头元素，剩余元素组成的表，不可能是原子。

20．排序算法中的比较次数与初始元素序列的排列无关。（ ）

【答案】×

【解析】这个要看是哪个排序算法，比如快速排序，初始序列为有序的情况比较的次数就相对于无序的多。

21．倒排文件是对次关键字建立索引。（ ）

【答案】√

，将所有具有相同【解析】倒排文件是对每一个次关键字项建立次关键字索引（称为倒排表）

次关键字的记录的物理记录号都填入倒排表为此次关键字的表中。

22．在链队列中，即使不设置尾指针也能进行入队操作。（ ） 【答案】

【解析】因为存在头指针，根据链表的性质，根据头指针可以找到为指针。