2018年北京市培养单位声学研究所866计算机原理之数据结构考研强化五套模拟题
● 摘要
目录
2018年北京市培养单位声学研究所866计算机原理之数据结构考研强化五套模拟题（一） ... 2 2018年北京市培养单位声学研究所866计算机原理之数据结构考研强化五套模拟题（二） ... 8 2018年北京市培养单位声学研究所866计算机原理之数据结构考研强化五套模拟题（三） . 15 2018年北京市培养单位声学研究所866计算机原理之数据结构考研强化五套模拟题（四） . 21 2018年北京市培养单位声学研究所866计算机原理之数据结构考研强化五套模拟题（五） . 29
一、算法设计题
1． 假设一个仅包含二元运算符的算术表达式以链表形式存储在二叉树BT 中，写出计算该算术表达式值的算法。
【答案】算法如下:
以后序遍历算法求以二叉树表示的算术表达式的
值
.
2． 写出一个递归算法来实现字符串逆序存储。
【答案】算法如下:
//字符串逆序存储的递归算法
r
//需要使用静态变量
//
规定
是字符串输入结束标志
//字符串逆序存储
求左子树表示的子表达式的值
求右子树表示的子表达式的值
//字符串结尾标记
//结束算法InvertStore
3． 给定nxm 矩阵
并设
设计一算法判定x 的值是否在A 中，要求时间复杂度
为O(m＋n) 。
【答案】算法如下:
//n*m矩阵A ，行下标从a 到b ，列下标从c 到d ，本算法査找x 是否在矩阵A 中
//flag是成功査到x 的标志
//假定x 为整型
(“矩阵A 中无
算法search 结束。
4． 试为二叉树写出一个建立三叉链表的算法，并在此三叉链表中删去每一个元素值为x 的结点，以及以它为根的子树，且释放相应存储空间。二叉树的三叉链表的描述为:
{二叉树根结点的指针}
【答案】算法如下:
生成三叉链表的二叉树(题目给出PASCAL 定义，下面用类C 语言书写
)
是二叉树结点指针的一维数组，容量足够大
一维数组最后元素的下标
元素或虚结点
根结点
双亲结点和子女结点用指针链上
结束
元素\n"，x) ；
5． 已知指针P 指向带表头的中根次序线索二叉树中的某结点，试写一算法FFA(P，q) , 该算法寻找结点P 的父亲结点q 。设线索二叉树的结点结构、表头结点结构和空树结构分别为(LTAG，LLINK ，INFO , RL1NK ，RTAG) ，且规定线索树的最左下结点的LLINK 域和最右下结点的RLINKt 域指向表头。
【答案】算法如下:
在中序线索树t 上，求结点p 的双亲结点q
暂存
找P 的中序最右下的结点
顺右线索找到q 的后继(P的袓先结点
)
若后继是头结点，则转到根结点
根结点无双亲
找最右结点的过程中回找到
P
结束FFA
准备到左子树中找
P
二、应用题
6． 为什么文件的倒排表比多重表组织方式节省空间？
【答案】倒排表有两项，一是次关键字值，二是具有相同次关键字值的物理记录号，这些记录号有序且顺序存储，不使用多重表中的指针链接，因而节省了空间。
7． 设某计算机的逻辑地址空间和物理地址空间均为64KB ，按字节编址. 若某进程最多需要6页(Page)数据存储空间，页的大小为1KB ，操作系统采用固定分配局部置换策略为此进程分配4个页框(PageFrame).在时刻260前的该进程访问情况如下表所示(访问位即使用位).
表
当该进程执行到时刻260时，要访问的逻辑地址为17CAH 的数据，请回答下列问题: (1)该逻辑地址对应的页号是多少？
(2)若采用先进先出(FIFO)置换算法，该逻辑地址对应的物理地址是多少? 要求给出计算过程. (3)若采用时钟(CLOCK)置换算法，该逻辑地址对应的物理地址是多少? 要求给出计算过程.(设搜索下一页的指针沿顺时针方向移动，且当前指向2号页框，如图所示）