2023年大学试题(计算机科学)-数据结构考试历年真题荟萃版附带答案

2023年大学试题(计算机科学)-数据结构考试历年真题荟萃版附带答案第一卷一.参考题库(共60题)1.对于下图G4和G5，按下列条件试分别写出从顶点v0出发按深度优先搜索遍历得到的顶点序列和按广度优先

2023年大学试题(计算机科学)-数据结 构考试历年真题荟萃版附带答案 第一卷 一.参考题库(共60题) 1.对于下图G4和G5，按下列条件试分别写出从顶点v0出发按深度优先搜索遍 历得到的顶点序列和按广度优先搜索遍历得到的顶点序列。（1）假定它们均采 用邻接矩阵表示；（2）假定它们均采用邻接表表示，并且假定每个顶点邻接 表中的结点是按顶点序号从大到小的次序链接的。 2.简述二路归并排序的具体步骤。 3.在程序设计中，可采用下列三种方法实现输出和输入：（1）通过scanf和 printf语句；（2）通过函数的参数显式传递；（3）通过全局变量隐式传 递。试讨论这三种方法的优缺点。 4.已知一个有向图的邻接表，编写算法建立其逆邻接表。 5.已知权值集合为{5，7，2，3，6，9}，要求给出哈夫曼树，并计算带权路径长 度WPL。 6.设以带头结点的双向循环链表表示的线性表L=（a1，a2，…，an）。试写一 时间复杂度O（n）的算法，将L改造为L=（a1，a3，…，an，…，a4，a2）。 （图片大小可任意调节）