2018年北京市培养单位声学研究所866计算机原理之数据结构考研仿真模拟五套题
● 摘要
目录
2018年北京市培养单位声学研究所866计算机原理之数据结构考研仿真模拟五套题(一) ... 2 2018年北京市培养单位声学研究所866计算机原理之数据结构考研仿真模拟五套题(二) ... 8 2018年北京市培养单位声学研究所866计算机原理之数据结构考研仿真模拟五套题(三) . 14 2018年北京市培养单位声学研究所866计算机原理之数据结构考研仿真模拟五套题(四) . 23 2018年北京市培养单位声学研究所866计算机原理之数据结构考研仿真模拟五套题(五) . 31
第 1 页,共 38 页
一、算法设计题
1. 已知深度为h 的二叉树,以一维数组应的算法。
【答案】算法如下:
计算深度为h 、以一维数组BT 作为其存储结构的二叉树的叶结点数,n 为数组长度
记叶结点数
若结点无孩子,则
是叶子
存储在数组后一半的元素是叶结点
2. 已知二叉树T ,试写出复制该二叉树的算法(t→T) 。
【答案】算法如下:
复制二叉树t 的非递归算法
是二叉树的结点指针的队列,容量足够大
结束本题
3. 设排序二叉树中结点的结构为下述三个域构成:
Data :给出结点数据的值;left :给出本结点的左儿子结点的地址;right :给出本结点的右儿子结
第 2 页,共 38 页
作为其存储结构,试编写一算法,求该二叉
树中叶结点的个数,为简单起见,设二叉树中元素结点为非负整数,要求写出算法基本思想及相
点的地址。设data 域为正整数,该二叉树根结点地址为T 。现给出一个正整数x 。请编写非递归程序,实现将data 域之值小于等于x 的结点全部删除掉。
【答案】算法如下:
非递归删除以r 为根的二叉排序树
栈,容量足够大,栈中元素是二叉排序树结点的指针
沿左分枝向下
出栈,沿栈顶结点的右子树向下刪除,释放被删除结点空间
在二叉排序树T 中删除所有小于等于x
的结点
根结点的值小于等于
x
删除二叉树p ,删除持续到" 根" 结点值大于x 或T 为空树为止
沿根结点左分支向下,査小干等于x 的结点
q 记P 的双亲
结点的值小于等于
x
再査原P 的右子树中小于等于x 的结点
4. 已知指针P 指向带表头的中根次序线索二叉树中的某结点,试写一算法FFA(P,q) , 该算法寻找结点P 的父亲结点q 。设线索二叉树的结点结构、表头结点结构和空树结构分别为(LTAG,LLINK ,INFO , RL1NK ,RTAG) ,且规定线索树的最左下结点的LLINK 域和最右下结点的RLINKt 域指向表头。
【答案】算法如下:
在中序线索树t 上,求结点p 的双亲结点q
暂存
找P 的中序最右下的结点
顺右线索找到q 的后继(P的袓先结点
)
第 3 页,共 38 页
若后继是头结点,则转到根结点
根结点无双亲
找最右结点的过程中回找到
P
结束FFA
5. 给定(已生成) 一个带表头结点的单链表,设head 为头指针,结点的结构为(data,next) ,data 为整型元素,next 为指针,试写出算法:按递增次序输出单链表中各结点的数据元素,并释放结点所占的存储空间(要求:不允许使用数组作辅助空间) 。
【答案】算法如下:
//head是带头结点的单链表的头指针
//本算法按递增顺序输出单链表各结点的值,并释放结点所占的存储空间
//循环到仅剩头结点
//pre为元素最小值结点的前驱结点的指针
//P为工作指针
//记住当前最小值结点的前驱
//输出元素最小值结点的数据
//删除元素值最小的结点,释放结点
空间
//释放头结点
准备到左子树中找
P
二、应用题
6. 某程序中有如下循环代码段
P 起始地址为0804 8100H, 对应的汇编代码和机器代码如下表所示
。假设编译时变量sum 和i
分别分配在寄存器R1和R2中。常量N 在寄存器R6中, 数组A 的首地址在寄存器R3中, 程序段
第 4 页,共 38 页