当前位置:问答库>考研试题

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 页