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

一、算法设计题

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

【答案】算法如下:

（ ）

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

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

//从左到右读入字符串

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

//是数字字符

//数初始化

//拼数

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

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

("共有个整数，它们是:

)

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

//算法结束

2． 已知深度为h 的二叉树，以一维数组

应的算法。

【答案】算法如下:

作为其存储结构，试编写一算法，求该二叉树中叶结点的个数，为简单起见，设二叉树中元素结点为非负整数，要求写出算法基本思想及相

计算深度为h 、以一维数组BT 作为其存储结构的二叉树的叶结点数，n 为数组长度

记叶结点数

若结点无孩子，则

是叶子

存储在数组后一半的元素是叶结点

3． 给定(已生成) 一个带表头结点的单链表，设head 为头指针，结点的结构为(data，next) ，data 为整型元素，next 为指针，试写出算法:按递增次序输出单链表中各结点的数据元素，并释放结点所占的存储空间(要求:不允许使用数组作辅助空间) 。

【答案】算法如下:

//head是带头结点的单链表的头指针

//本算法按递增顺序输出单链表各结点的值，并释放结点所占的存储空间

//循环到仅剩头结点

//pre为元素最小值结点的前驱结点的指针

//P为工作指针

//记住当前最小值结点的前驱

//输出元素最小值结点的数据

//删除元素值最小的结点，释放结点

空间

//释放头结点

4． 设表达式以字符形式己存入数组E 中，'#'为表达式的结束符，

试写出判断表达式中括号

是否配对的C 语言描述算法:EXYX(E)(注:算法中可调用栈操作的基本算法) 。

【答案】算法如下:

//E[ ]是有n 字符的字符数组，存放字符串表达式，以'#'结束。本算法判断表达式中圆括号是否匹配

//s是一维数组，容量足够大，是用于存放括号的栈

//top用作栈顶指针

//'#先入栈，用于和表达式结束符号'#'匹配

//字符数组E 的工作指针

//逐字符处理字符表达式的数组

//读人其他字符，不进行处理

5． 设有一头指针为L 的带有表头结点的非循环双向链表，其每个结点中除有pred(前驱指针) ，data(数据) 和next(后继指针) 域外，还有一个访问频度域freq 。在链表被启用前，其值均初始化为零。每当在链表中进行一次Locate(L，X) 运算时，令元素值为x 的结点中freq 域的值增1，并使此链表中结点保持按访问频度非增(递减) 的顺序排列，同时最近访问的结点排在频度相同的结点的最后，以便使频繁访问的结点总是靠近表头。试编写符合上述要求的Locate(L，x) 运算的算法，该运算为函数过程，返回找到结点的地址，类型为指针型。

【答案】算法如下:

//L是带头结点的按访问频度递减的双向链表

//本算法先査找数据x ，査找成功时结点的访问频度域增1，最后将该结点按频度递减插入链表中

//P为L 表的工作指针，q 为p 的前驱，用于査找插入位置

//查找值为x 的结点

("不存在所査结点\n”) ；exit(0)；

//令元素值为x 的结点的freq 域加

1

//将P 结点从链表上摘下

//以下査找P 结点的插人位置

//将P 结点插人

//返回值为x 的结点的指针

//算法结束

二、应用题