2018年同济大学物理科学与工程学院408计算机学科专业基础综合之数据结构考研核心题库
● 摘要
一、算法设计题
1． 请编写完整的程序。如果矩阵A 中存在这样的一个元素A[i，j]满足条件:A[i，j]是第i 行中值最小的元素，且又是第j 列中值最大的元素，则称之为该矩阵的一个马鞍点。请编程计算出m*n的矩阵A 的所有马鞍点。
【答案】算法如下:
//A是的矩阵，本算法求矩阵A 中的马鞍点
//max数组存放各列最大值元素的行号，初始化为行号
//min数组存放各行最小值元素的列号，初始化为列号
0 //选各行最小值元素和各列最大值元素
//修改第j 列最大元素的
行号
" 修改第i 行最小元素的
列号
//第i 行最小元素的列号
是马鞍点，
元素值是
是马鞍点
2． —个有向图G=(V，E) 的平方图
，使得表示。
【答案】算法如下:
第 2 页，共 37 页
//
满足下述性质
:
2
当且仅当存在某个顶点
2
且
。写一个算法从给定的G 求出G , G 和G 可分别用两个邻接表
3． 编程:假设以数组Q[m]存放循环队列中的元素，同时以rear 和length 分别指示环形队列中的队尾位置和队列中所含元素的个数。试给出该循环队列的队空条件和队满条件，并写出相应的初始化(initqueue)，插入(enqueue)和删除(dequeue)元素的操作。
【答案】定义队列:
//循环队列占m 个存储单元
//rear指向队尾元素，length 为元素个数
(1)设cq 是seQueue 类型变量，则当(2)队列的初始化:
//cq为循环队列，本算法进行队列初始化
//算法结束 (3)队列的插入:
//cq是已如上定义的循环队列，本算法将元素x 入队
//队满
.
//计算插入元素位置
//将元素x 入队列
//修改队列长度
//算法结束
//cq是已如上定义的循环队列，本算法是出队算法，且返回出队元素
//队空
；//出队元素位置
//修改队列长度
//返回队头元素
第 3 页，共 37 页
时队列空，当 时队列满。
(4)队列的删除:
//算法结束
4． 编写对有序表进行顺序查找的算法，并画出对有序表进行顺序查找的判定树。假设每次查找时的给定值为随机值，又查找成功和不成功的概率也相等，试求进行每一次查找时和给定值进行比较的关键字个数的期望值。
【答案】算法如下:
在具有个元素的有序表R 中，顺序査找值为K 的结点，査找成功返回其位置
否则返回-1表示失败
元素序号
结束
，查找失败的平均查找
期望值分析:在等概率情况下，则查找成功的平均查找长度为
长度为(n+2)/2(失败位置除小于每一个，还存在大于最后一个) 。若查找成功和不成功的概率也相等，则查找成功时和关键字比较的个数的期望值约为。
5． 设有一头指针为L 的带有表头结点的非循环双向链表，其每个结点中除有pred(前驱指针) ，data(数据) 和next(后继指针) 域外，还有一个访问频度域freq 。在链表被启用前，其值均初始化为零。每当在链表中进行一次Locate(L，X) 运算时，令元素值为x 的结点中freq 域的值增1，并使此链表中结点保持按访问频度非增(递减) 的顺序排列，同时最近访问的结点排在频度相同的结点的最后，以便使频繁访问的结点总是靠近表头。试编写符合上述要求的Locate(L，x) 运算的算法，该运算为函数过程，返回找到结点的地址，类型为指针型。
【答案】算法如下:
//L是带头结点的按访问频度递减的双向链表
//本算法先査找数据x ，査找成功时结点的访问频度域增1，最后将该结点按频度递减插入链表中
//P为L 表的工作指针，q 为p 的前驱，用于査找插入位置
//查找值为x 的结点
("不存在所査结点\n”) ；exit(0)；
//令元素值为x 的结点的freq 域加
1
//将P 结点从链表上摘下
第 4 页，共 37 页
相关内容
相关标签