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

一、算法设计题

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

试写出判断表达式中括号

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

【答案】算法如下:

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

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

//top用作栈顶指针

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

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

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

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

2． 设有一头指针为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 的结点的指针

//算法结束

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

应的算法。

【答案】算法如下:

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

记叶结点数

若结点无孩子，则

是叶子

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

4． 假设以I 和0分别表示入栈和出栈操作。栈的初态和终态均为空，入桟和出找的操作序列可表示为仅由I 和0组成的序列，称可以操作的序列为合法序列，否则称为非法序列。

(1)下面所示的序列中哪些是合法的？

A.

B.

C.

D.

(2)通过对(1)的分析，写出一个算法，判定所给的操作序列是否合法。若合法，返回true ，否则返回false(假定被判定的操作序列已存入一维数组中) 。

【答案】(1)A和D 是合法序列，B 和C 是非法序列。

(2)设被判定的操作序列已存入一维数组A 中，算法如下:

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

//判断字符数组A 中的输入输出序列是否是合法序列。

//i为下标

//j和k 分别为I 和字母O 的个数

//入栈次数增

1

//不论A[i]是’I'或’〇' ，指针i 均后移

//算法结束

5． 写一算法找出n 个数的最大值和最小值，要求最坏条件下的元素比较次数为

。

【答案】算法如下:

用最多3n/2－2次比较在n 个元素r 中选出最大值和最小值

n 为偶数时

r 最小值

("最大值) ；

二、应用题

6． 某16位计算机中, 带符号整数用补码表示, 数据Cache 和指令Cache 分离。题44表给出了指令系统中部分指令格式, 其中Rs 和Rd 表示寄存器, mem 表示存储单元地址, (X)表示寄存器X 或存储单元X 的内容。

表 指令系统中部分指令格式