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

一、算法设计题

1． 设从键盘输入一整数的序列:a 1，a 2，a 3，... ，a n ，试编写算法实现:用栈结构存储输入的整数，

当

时，将

入栈；当

时，输出栈顶整数并出栈。算法应对异常情况(入栈满等) 给

出相应的信息。

【答案】算法如下

:

栈空间容量

//s是元素为整数的栈，本算法进行入栈和出栈操作

//top为栈顶指针，定义top ＝0时为栈空

//n个整数序列进行处理

//从键盘读入整数序列

//读入的整数不等于﹣1时人栈

//读入的整数等于﹣1时出栈

//算法结束。

2． 若x 和y 是两个采用顺序结构存储的串，编写一个比较两个串是否相等的函数。

【答案】算法如下:

//本算法判断两个顺序存储的串x 和y 是否相等，相等返回1，否则返回

//对应字符相等，指针后移

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

【答案】算法如下:

求二叉树bt 的最大宽度

空二叉树宽度为0

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

足够大

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

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

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

根结点入队

同层元素数加

1

左子女入队

右子女入队

一层结束

指向下层最右元素

更新当前最大宽度

4． 试编写在带头结点的单链表中删除(一个) 最小值结点的(高效) 算法。delete(Linklist&L)

【答案】算法如下:

//L是带头结点的单链表，本算法删除其最小值结点

//P为工作指针。指向恃处理的结点。假定链表非空

//pre指向最小值结点的前驱

//q指向最小值结点，初始假定第一元素结点是最小值结点

//查最小值结点

//指针后移

//从链表上刪除最小值结点

//释放最小值结点空间

//结束算法Delete

5． 元素集合已存入整型数组树T 的非递归算法:CSBT(r，A)

【答案】算法如下:

以存储在数组K 中的n 个关键字，建立一棵初始为空的二叉排序树

中，试写出依次取A 中各值构造一棵二叉排序

在调用

时，

T=null

f 是P 的双亲

申请结点空间

根结点

左子女

右子树根结点的值大于等于根

结点的值

算法结束

二、应用题

6． 设某文件经内排序后得到100个初始归并段(初始顺串) ，若使用多路归并排序算法，并要求三趟归并完成排序，问归并路数最少为多少？

【答案】设归并路数为k ，归并趟数为s ，则

，因

，且k 为整数，故k=5，

即最少5-路归并可以完成排序。

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

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

则页的大小是多少字节？页表最大占用多少字节？ (2)若使用二级页表的分存储管理方式, 逻辑地址结构为:

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

(3)采用(1)中的分页存储管理方式, 一个代码段起始逻辑地址为00008000H , 其长度为8KB , 被装载到从物理地址00900000H 开始的连续主存空间中。页表从主存

开始的

物理地址处连续存放, 如下图所示(地址大小自下向上递增) 。请计算出该代码段对应的两个页表项物理地址、这中框号以及计算出该代码段对应的两个页表项物理地址、这中框号以及计算出该代码段对应的两个页表项物理地址、这两个页表项中的框号以及代码页面2的起始物理地址。