2018年北京市培养单位工程科学学院864程序设计之数据结构考研仿真模拟五套题
● 摘要
目录
2018年北京市培养单位工程科学学院864程序设计之数据结构考研仿真模拟五套题（一） ... 2 2018年北京市培养单位工程科学学院864程序设计之数据结构考研仿真模拟五套题（二） . 11 2018年北京市培养单位工程科学学院864程序设计之数据结构考研仿真模拟五套题（三） . 18 2018年北京市培养单位工程科学学院864程序设计之数据结构考研仿真模拟五套题（四） . 24 2018年北京市培养单位工程科学学院864程序设计之数据结构考研仿真模拟五套题（五） . 31
一、算法设计题
1． 设有顺序放置的n 个桶，每个桶中装有一粒砾石，每粒砾石的颜色是红、白、蓝之一。要求重新安排这些砾石，使得所有红色砾石在前，所有白色砾石居中，所有蓝色砾石居后。重新安排时，对每粒砾石的颜色只能察看一次，并且只允许交换操作来调整砾石的位置。
【答案】算法如下:
r 为含有n 个元素的线性表，元素是具有红、白和蓝色的砾石，用顺序存储结构存储
本算法对其排序，使所有红色栎石在前，白色居中，蓝色在最后
当前元素是红色
当前元素是白色
当前元素是蓝色
2． 已知一棵二叉树的前序遍历序列和中序遍历序列分别存于两个一维数组中，试编写算法建立该二叉树的二叉链表。
【答案】算法如下:
根据二叉树前序序列pre 和中序序列in 建立二叉树。元素下标
申请结点
是根
在中序序列中，根结点将树分成左右
子树
无左子树
递归建立左子树
无右子树
递归建立右子树
结束:
和是两个序列首、尾
3． 已知两个线性表A , B 均以带头结点的单链表作存储结构，且表中元素按值递增有序排列。设计算法求出A 与B 的交集C ，要求C 另开辟存储空间。，并同样以元素值的递增有序的单链表形式存储。
【答案】算法如下:
//线性表A 和B 以带头结点的单链表作为存储结构。本算法求A 和B 的交集C , C 另辟空间
//pa、pb 是两链表的工作指针
//监视哨
//pa指针后移
//pb指针后移
//处理交集元素
//删除重复元素
//交集元素并入结果表
//置结果链表尾
4． 对给定关键字序号j(1 中找到关键字从小到大排在第j 位上的记 录，写一个算法利用快速排序的划分思想实现上述查找(要求用最少的时间和最少的空间) 。 例如:给定无序关键字{7，5，1，6，2，8，9，3}，当j=4时，找到的关键字应是5。 【答案】算法如下； 在后半部分继续进行划分 在前半部分继续进行划分 5． 请运用快速排序思想，设计递归算法实现求n(n>1)个不同元素集合中的第f( 【答案】算法如下: 在后半部分继续进行划分 在前半部分继续进行划分 ) 小元素。 二、应用题 6． 某计算机的主存地址空间大小为256MB ，按字节编址，指令Cache 和数据Cache 分离，均有8个Cache 行，每个Cache 行大小为64B ，数据Cache 采用直接映射方式. 现有两个功能相同的程序A 和B ，其伪代码如下所示:程序A :程序B : 假定int 类型数据用32位补码表示，程序编译时i ，j ，sum 均分配在寄存器中，数组a 按行优先方式存放，首地址320(十进制数). 请回答下列问题，要求说明理由或给出计算过程. (1)若不考虑用于Cache 一致性维护和替换算法的控制位，则数据Cache 的总容量为多少？ (2)数组数据a[0][31]和a[l][1]各自所在的主存块对应的Cache 行号分别是多少(Cache行号从0开始）？ (3)程序A 和B 的数据访问命中率各是多少? 哪个程序的执行时间更短？ 【答案】(1)每个Cache 行对应一个标记项，标记项包括有效位、脏位、替换控制位以及标记
相关内容
相关标签