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

一、算法设计题

1． 已知一棵二叉树的前序遍历序列和中序遍历序列分别存于两个一维数组中，试编写算法建立该二叉树的二叉链表。

【答案】算法如下:

根据二叉树前序序列pre 和中序序列in 建立二叉树。元素下标

申请结点

是根

在中序序列中，根结点将树分成左右

子树

无左子树

递归建立左子树

无右子树

递归建立右子树

结束:

2． 己知两个定长数组，它们分别存放两个非降序有序序列，请编写程序把第二个数组序列中的数逐个插入到前一个数组序列中，完成后两个数组中的数分别有序(非降序) 并且第一数组中所有的数都不大于第二个数组中的任意一个数。注意，不能另开辟数组，也不能对任意一个数组进行排序操作。

例如:

第一个数组为:4，12，28 第二个数组为:1，7，9，29，45 输出结果为:

第一个数组

第二个数组

【答案】算法如下:

//A和B 是各有m 个和n 个整数的非降序数组，本算法将B 数组元素逐个插入到A 中 //使A 中各元素均不大于B 中各元素，且两数组仍保持非降序排列.

第 2 页，共 32 页

和是两个序列首、尾

" 交换A[m﹣1]和

B[0]

//寻找A[m﹣1]的插入位置

//寻找B[0]的插入位置

算法结束

3． 设A 和B 均为下三角矩阵，每一个都有n 行n 列。因此在下三角区域中各有n(n＋l)/2个无素。另设有一个二维数组C ，它有n 行n ＋1列。试设计一个方案，将两个矩阵A 和B 中的下三角区域元素存放于同一个C 中。要求将A 的下三角区域中的元素存放于C 的下三角区域中，B 的下三角区域中的元素转置后存放于C 的上三角区域中。并给出计算A 的矩阵元素矩阵元素

在C 中的存放位置下标的公式。

//本算法将n 阶方阵的下三角矩阵A 和B 置于C 中，矩阵B 要逆置

//算法结束

4． 已知指针P 指向带表头的中根次序线索二叉树中的某结点，试写一算法FFA(P，q) , 该算法寻找结点P 的父亲结点q 。设线索二叉树的结点结构、表头结点结构和空树结构分别为(LTAG，LLINK ，INFO , RL1NK ，RTAG) ，且规定线索树的最左下结点的LLINK 域和最右下结点的RLINKt 域指向表头。

【答案】算法如下:

在中序线索树t 上，求结点p 的双亲结点q

暂存

找P 的中序最右下的结点

顺右线索找到q 的后继(P的袓先结点

)

若后继是头结点，则转到根结点

第 3 页，共 32 页

和B 的

【答案】算法如下:

根结点无双亲

找最右结点的过程中回找到

P

结束FFA

准备到左子树中找

P

5． 输入一个字符串，内有数字和非数字字符，如:akl23x4561796073029ef4563。将其中连续的数字作为一个整体，依次存放到一数组a 中，例如123放入a[0]，456放入a[l]，...... 。编程统计其共有多少个整数，并输出这些数。

【答案】算法如下:

（ ）

//从键盘输入字符串，连续的数字字符算作一个整数，统计其中整数的个数

//整数存储到数组a ，i 记整数个数

//从左到右读入字符串

//'#'是字符串结束标记

//是数字字符

//数初始化

//拼数

//若拼数中输入了’#’，则不再输入

//输入非数字且非#时，继续输入字符

("共有

个整数，它们是:

)

//每10个数输出在一行上

//算法结束

二、应用题

6． 假定在一个8位字长的计算机中运行下列C 程序段:

第 4 页，共 32 页