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

一、算法设计题

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

试写出判断表达式中括号

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

【答案】算法如下:

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

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

//top用作栈顶指针

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

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

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

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

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

【答案】算法如下:

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

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

//循环到仅剩头结点

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

//P为工作指针

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

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

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

空间

//释放头结点

3． 有二叉排序树采用二叉链表方式存放，树中结点值各不相同，欲得到一个由大到小的结点值递减序列，简述处理方法思路，用非递归形式写出算法。

【答案】算法如下:

按递减次序输出二叉排序树结点的值

是元素为二叉树结点指针的栈，容量足够大

沿右子树向下

结束

4． 请用流程图或高级语言表示算法。已知有向图有n 个顶点，请写算法，根据用户输入的数对建立该有向图的邻接表。即接受用户输入的(以其中之一为0标志结束) ，对于每条这样的边，申请一个结点，并插入到的单链表中，如此反复，直到将图中所有边处理完毕。

提示:先产生邻接表的n 个头结点(其结点数值域从1到n) 。

【答案】算法如下:

建立有向图的邻接表存储结构

输入顶点信息

题目要求两顶点之一为0表示结束

5． 对给定关键字序号j(1

例如:给定无序关键字{7，5，1，6，2，8，9，3}，当j=4时，找到的关键字应是5。

【答案】算法如下；

在后半部分继续进行划分

在前半部分继续进行划分

二、应用题

6． 模式匹配算法是在主串中快速寻找模式的一种有效的方法，如果设主串的长度为m ，模式的长度为n ，则在主串中寻找模式的KMP 算法的时间复杂性是多少? 如果某一模式

，请给出它的next 函数值及next 函数的修正值nextval 之值。

【答案】KMP 算法的时间复杂性是O(m＋n) 。

p 的next 和nextval 值分别为01112212321和01102201320。

7． 某计算机主存按字节编址, 逻辑地址和物理地址都是32位, 页表项大小为4字节。请回答下列问题。

(1)若使用一级页表的分存储管理方式, 逻辑地址结构为:

则页的大小是多少字节？页表最大占用多少字节？

(2)若使用二级页表的分存储管理方式, 逻辑地址结构为:

设逻辑地址为LA , 请分别给出其对应的页目录号和表索引达式。

(3)采用(1)中的分页存储管理方式, 一个代码段起始逻辑地址为00008000H , 其长度为8KB , 被装载到从物理地址00900000H 开始的连续主存空间中。页表从主存开始的物理地址处连续存放, 如下图所示(地址大小自下向上递增) 。请计算出该代码段对应的两个页表项