2018年同济大学土木工程学院408计算机学科专业基础综合之数据结构考研核心题库
● 摘要
一、算法设计题
1． 试编写在带头结点的单链表中删除(一个) 最小值结点的(高效) 算法。delete(Linklist&L)
【答案】算法如下:
//L是带头结点的单链表，本算法删除其最小值结点
//P为工作指针。指向恃处理的结点。假定链表非空
//pre指向最小值结点的前驱
//q指向最小值结点，初始假定第一元素结点是最小值结点
//查最小值结点
//指针后移
//从链表上刪除最小值结点
//释放最小值结点空间
//结束算法Delete
2． 写一算法找出n 个数的最大值和最小值，要求最坏条件下的元素比较次数为
。
【答案】算法如下:
用最多3n/2－2次比较在n 个元素r 中选出最大值和最小值
n 为偶数时
r 最小值
("最大值) ；
3． 写出算法，求出中序线索二叉树中给定值为X 的结点之后继结点，返回该后继结点的指针。线索树中结点结构为；
。其中，data 存放结点的值；lc 、rc 为指向左、
右孩子或该结点前驱、后继的指针，ltag 、rtag 为标志域，若值为0, 则lc 、rc 为指向左、右孩子的指针；若值为1，则lc 、rc 为指向其前驱、后继结点的指针。
【答案】算法如下:
先在带头结点的中序线索二叉树T 中査找给定值为x 的结点，假定值为x 的结点存在
设P 指向二叉树的根结点
结束
在中序线索二叉树T 中,, 求给定值为x 的结点的
后继结点
首先在T 树上査找给定值为x 的结点，由p 指向
' 若P 的右标志为1, 则P 的rc 指针指向其后继
结点P 的右子树中最左边的结点是结点P 的中序后继
结库
.
4． 写算法将单链表11拆成二个链表，其中以11为头的链表保持原来向后的链接，另一个链表的头为12，其链接方向与11相反，11包含原链表的奇数序号的结点，12包含原链表的偶数序号的结点。
【答案】算法如下:
//本算法将链表L1拆成L1和L2两个链表，L2链接方向与L1相反
//空链表
//奇数序号结点在L1中
//偶数序号
结点逆置插入到L2中
//置L1
表尾
5． 请用流程图或高级语言表示算法。已知有向图有n 个顶点，请写算法，根据用户输入的数对建立该有向图的邻接表。即接受用户输入的
(以其中之一为0标志结束) ，对于每条这样的
边，申请一个结点，并插入到的单链表中，如此反复，直到将图中所有边处理完毕。
提示:先产生邻接表的n 个头结点(其结点数值域从1到n) 。 【答案】算法如下:
建立有向图的邻接表存储结构
题目要求两顶点之一为0表示结束
输入顶点信息
二、应用题
6． 某计算机存储器按字节编址, 虚拟(逻辑) 地址空间大小为16MB , 主存(物理) 地址空间大小为1MB , 页面大小为4KB ; Cache 采用直接映射方式, 共8行; 主存与Cache 之间交换的块大小为32B 。系统运行到某一时刻时, 页表的部分内容和Cache 的部分内容分别如图a 、图b 所示, 图中页框号及标记字段的内容为十六进制形式。
图a 页表的部分内容
图b Cache的部分内容
请回答下列问题。
(1)虚拟地址共有几位, 哪几位表示虚页号? 物理地址共有几位, 哪几位表示页框号(物理页