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

一、算法设计题

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

试写出判断表达式中括号

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

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

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

//top用作栈顶指针

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

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

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

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

2． 已知递增有序的单链表A ，B 分别存储了一个集合，请设计算法以求出两个集合A 和B 的差集A ﹣B(即仅由在A 中出现而不在B 中出现的元素所构成的集合) ，并以同样的形式存储，同时返回该集合的元素个数。

【答案】算法如下:

//A和B 均是带头结点递增有序的单链表，本算法求两集合的差集，*n是结果集合中元素个数，初始为

//p和q 分别是链表A 和B 的工作指针

//pre为A 中p 所指结点的前驱结点的指针

//A

链表中当前结点指针后移

//B链表中当前结点指针后移

//处理A , B 中元素值相同的结点，

应刪除 //删除结点

3． 编写算法，求二叉树的宽度。

【答案】算法如下:

求二叉树bt 的最大宽度

空二叉树宽度为

Q 是队列，元素为二叉树结点指针，容量

足够大

front 为队头指针，rear 为队尾指针

last 为同层最右结点在队列中的位置

temp 记当前层宽度，maxw 记最大宽度

根结点入队

同层元素数加

1

左子女入队

右子女入队

一层结束

指向下层最右元素

更新当前最大宽度

4． 已知两个链表A 和B 分别表示两个集合，其元素递增排列。编一函数，求A 与B 的交集，并存放于A 链表中。

【答案】算法如下:

//设工作指针pa 和pb ；

//结果表中当前合并结点的前驱的指针

//交集并入结果表中

//释放结点空

间

//释放结点空间

//释放结点空间

//置链表尾标记

//注:本算法中也可对B 表不作释放空间的处理

5． 设有两个栈S 1，S 2都采用顺序栈方式，并且共享一个存储区的操作算法。

【答案】找的定乂:

两栈共享顺序存储空间所能达到的最多元素数

//假设元素类型为整型

； //栈空间

//top为两个栈顶指针

//S是如上定义的结构类型变量，为全局变量

(1)入栈操作:

//入栈操作。i 为栈号，i ＝〇表示左栈Sl ，i ＝l 表示右栈s2，x 是入栈元素。入栈成功返回1，否则返回

(2)出栈操作

//出栈算法。i 代表栈号，i ＝0时为s1栈，i ＝l 时为s2栈。出栈成功返回出栈元素，否则返﹣

1

为了尽量利用

空间，减少溢出的可能，可采用栈顶相向，迎面增长的存储方式。试设计S 1，S 2有关入栈和出找

//算法结束