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

一、填空题

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

【答案】

2． 若用n 表示图中顶点数目，则有_____条边的无向图成为完全图。

【答案】n （n-l ）/2

【解析】无向完全图中任意一个顶点都和其他n-1个顶点都有一条边，即为n （n-l ）。又因为每条边重复出现两次，所有无向完全图的边数为n （n-l ）/2。

3． 已知二维数组中每个元素占4个单元，在按行优先方式将其存储到起始地址为1000的连续存储区域时

，

【答案】1196

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

4． 模式串的next 函数值序列为_____。

【答案】01122312

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

【答案】顺序存储结构

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

6． 以下是用类C 语言写山的算法，该算法将以二叉链表存储的二叉树中的叶结点按从左到右的顺序链成一个带头结点的双向循环链表，链接时，结点的Lchild 域作为前链域，指向结点的直接前驱，结点的Rchild 域作为后链域，指向结点的直接后继。算法中，使用一个顺序栈stack , 栈顶head 为双向循坏链表的头指针。 指针为top , P , t 为辅助指针，试填充算法中的空格，使算法完整。

void leafchain（BiTree Abt）

{p={BiTree）malloc （sizeof （BiTNode ））; If （!p ）{print£（“OVERFLOW\n”; exit （1）; }

head=p; top=0; if （bt ）

第 2 页，共 50 页

的地址是：_____。

{top++; stack[top]=bt; while （top ）

{t=stack[top]; top--;

if （it->Lchild && !t->Rchild）{ （1） ; （2） ; （3） ; } else {if（ （4） ）{top++; stack[top]= （5） ; } if （ （6） ）{top++; stack[top]= （5） ; } } }

（8） ; （9） ; } } 【答案】

p->Rchild=t:t->Lchild=p:p=t: t->Rchild!=null:t->Rchild: t->Lchild!=null: t->Lchild: p->Rchild=head:head->Lchild=p 7． 设有一个10阶对称矩阵A 采用压缩存储方式， （以行为主序存储：）则的地址为_____。

【答案】33

【解析】设存储的元素的行标为i ，列标为j 。若则

的地址为

将

代入得33。

则

的地址为

若

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

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

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

【程序说明】本程序完成将二叉树中左、右孩子交换的操作。交换的结果如下所示（编科略）本程序采用非递归的方法，设立一个堆栈交换左、右子树的算法为：

（1）把根结点放入堆栈。

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

存放还没有转换过的结点，它的栈顶指针为

。

（1）

{（2）

If （ （3） ）

}

}}

第 3 页，共 50 页

【答案】

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

10．抽象数据类型的定义仅取决于它的一组_____，而与_____无关, 即不论其内部结构如何变化，只要它的_____不变，都不影响其外部使用。

【答案】逻辑特性；在计算机内部如何表示和实现；数学特性

11．若不考虑基数排序，则在排序过程中，主要进行的两种基本操作是关键字的_____和记录的_____，

【答案】比较；移动

12．己知有序表为（12，18，24，35，47，50，62，83，90，115，134）当用二分法查找90时，需_____次查找成功，查找47时_____成功，查找100时，需_____次才能确定不成功。

【答案】2；4；3

【解析】二分法查找元素次数列表

查

找100是找到115就停止了。

13．在单链表中设置头结点的作用是_____。

【答案】方便运算

14．完善算法：求KMP 算法.next 数组。

END ； 【答案】

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

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

【解析】线性表的链式存储结构根据每个结点包含的指针个数分为单链表和双链表，单链表只包含一个指针，指向后续元素，双链表包括两个指针，指向前一个元素和后续元素。根据指针

第 4 页，共 50 页