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

一、填空题

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

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

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

2． 设二维数组A 的行和列的下标范围分别为

【答案】

当其值为

和每个元素占2个单元，按行优先顺处的元素为_____。

序存储，第一个元素的存储起始位置为b ，则存储位置为

【解析】令这个元素的行标为i ，列标为j 。则它的存储位置是

时，则i=2，j=3。

3． 在一棵m

阶树中，若在某结点中插入一个新关键字而引起该结点分裂，则此结点中原有的关键字的个数是_____；若在某结点中删除一个关键字而导致结点合并，则该结点中原有的关键字的个数是_____。

【答案】

【解析】m

阶树除根结点和叶子结点外，结点中关键字个数最多是最少

4． 设有一个10阶对称矩阵A 采用压缩存储方式， （以行为主序存储：）则的地址为_____。

【答案】33

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

则

的地址为

若

的地址为将代入得33。

5． 克鲁斯卡尔算法的时间复杂度为_____，它对_____图较为适合。

【答案】O （eloge ）; 边稀疏

6． 当两个栈共享一存储区时，栈利用一维数组当栈1空时

，

【答案】

为_____，栈2空时

，

表示，两栈顶指针为则

为_____，栈满时为_____。

【解析】共享栈的栈底在共享存储区的两端，当栈满时栈顶相邻。

7． 在双向循环链表中，向P 所指的结点之后插入指针f 所指的结点，其操作是_____、_____、_____、_____。

【答案】

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

【答案】

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

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

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

【答案】方便运算

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

【答案】m/2

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

11．在循环队列中，队列长度为n ，存储位置从0到，编号，以rear 指示实际的队尾元素，现要在此队列中插入一个新元素，新元素的位置是（ ）。

【答案】

12．下面程序的功能是用递归算法将一个整数按逆序存放到一个字符数组中。如123存放成321。请填空：

【答案】

【解析】通过递归算法，首先找到最高位的值，将其放到str 对应的数组中，依次反向获取从高位到地位的值，将其放到数组中，完成了将整数逆序放到一个字符数组中。

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

【答案】

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

14．文件可按其记录的类型不同而分成两类，即_____和_____文件。

【答案】操作系统文件；数据库

15．在n 个顶点的非空无向图中，最多有_____个连通分量。

【答案】n

【解析】当n 个顶点之间没有边，都是孤立的顶点时，有n 个连通分量。

二、算法设计题

16．已知一具有n 个结点的二叉树的中序遍历序列与后序遍历序列分别存放于数组

和

中（设该二叉树各结点的数据值均不相同）。请写一建立该二叉树的二叉链表结构的非

递归算法。该二叉链表的 链结点结构为（lchild ，data , rchild ）, 其中data 为数据域，lchild 与rhild 分别为指向该结点左、右孩子的指针域 （当孩子结点不存在时，相应指针域为空，用nil 表示）。

【答案】算法如下：

//由二叉树的中序序列IN[]和后序序列POSTt[]建立二叉树

分别是中序序列和后序序列第一和最后元素的下标，初始调用时

，

为栈，容量足够大

//初始化

//取出栈顶数据

//在中序序列中查等于

//根结点的值

无左子树

将建立左子树的数据人栈

无右子树

//右子树数据入

栈

的结点