2018年北京市培养单位国家天文台862计算机学科综合(非专业)之数据结构考研核心题库
● 摘要
一、算法设计题
1． 给出以十字链表作存储结构，建立图的算法，输入(i, j , V) , 其中i , j 为顶点号，v 为权值。
【答案】算法如下:
建立有向图的十字链表存储结构
假定权值为整型
建立顶点向量
当输入i 、j 、v 之一为0时，结
束算法运行
申请结点
弧结点中权值域
算法结束
2． 编写算法打印出由指针Hm 指向总表头的以十字链表形式存储的稀疏矩阵中每一行的非零元的个数。注意:行、列及总表头结点的形式为:
它们已用val 域链接成循环链表。非零元的结点形式也同上，每一行(列) 的非零元由right(down)域把它们链接成循环链表，该行(列) 的表头结点即为该行(列) 循环链表的表头。
【答案】算法如下:
//输出由Hm 指向的十字链表中每一行的非零元素个数
//数组A 记各行非零元个数，i 记行号
//循环完各行列表头
//P是稀疏矩阵行内工作指针，num 记该行非零个
数
//完成行内非零元的查找
//指针后移
//存该行非零元个数
//移到下一行列表头
//输出各行非零元个数
第
}算法结束
3． 请运用快速排序思想，设计递归算法实现求n(n>1)个不同元素集合中的第f(
【答案】算法如下:
在后半部分继续进行划分
在前半部分继续进行划分
4． 设有一头指针为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 结点从链表上摘下
//以下査找P 结点的插人位置
//将P 结点插人
//返回值为x 的结点的指针
//算法结束
5． 叙述基数排序算法，并对下列整数序列图示其基数排序的全过程。(179，208，93，306，55，859，984，9，271，33)
【答案】算法如下:
待排序记录的个数
关键字由d 个分量组成
静态链域
记录的其他数据域
存放n 个记录
.
用队列表示桶，共m 个
进行基数排序，返回收集用的链头指针
将
进行d 趟排序
初始化桶
按关键字的第j 个分量进行分配
队列的头、尾指针
对
链成一个静态链表
将初始链表的终端结点指针置空，P 指向链表的第一个结点