《计算机统考数据结构算法部分精析.docxVIP

第一部分：历年真题解析09-13年算法题主要围绕数组，链表，排序为基础出题，一般都能想到解题方法，不过要得到最优算法较难14年算法考点为树这一章的内容，基础为求二叉树高度，由于和往年跨度较大，解题时可能会乱了阵脚，所以今年的复习应在线性表的基础上再辅以树这一章主要算法的掌握。2009年42.（15’）已知一个带有表头结点的单链表，结点结构为datalink假设该链表只给出了头指针list。在不改变链表的前提下，请设计一个尽可能高效的算法，查找链表中倒数第k个位置上的结点（k为正整数）。若查找成功，算法输出该结点的data值，并返回1；否则，只返回0。要求：描述算法的基本设计思想。描述算法的详细实现步骤。根据设计思想和实现步骤，采用程序设计语言描述算法（使用C或C++或JAVA语言实现），关键之处请给出简要注释。【分析】本题考查带头节点单链表的应用。【解答】算法的基本设计思想（5分）算法的详细实现步骤（5分）算法实现（5分）提示：算法程序题，如果能够写出数据结构类型定义、正确的算?法思想都会至少给一半以上分数，如果能用伪代码写出自然更好，比?较复杂的地方可以直接用文字表达。?若所给出的算法采用一遍扫描方式就能得到正确结果，可给满分?15?分；若采用两遍或多遍扫描才能得到正确结果的，最高分?10?分。?若采用递归算法得到正确结果的，最高给?10?分；若实现算法的空间?复杂度过高（使用了大小与?k?有关的辅助数组），但结果正确，最高?给?10?分。2012年42.（13’）假定采用带头结点的单链表保存单词，当两个单词有相同的后缀时，则可共享相同的后缀存储空间，例如，“loading”和“being”的存储映像如下图所示。daolstr1nig^ebstr2p设str1和str2分别指向两个单词所在单链表的头结点，链表结点结构为dataNext请设计一个时间上尽可能高效的算法，找出由str1和str2所指向两个链表共同后缀的起始位置（如图中字符i所在结点的位置p）。要求给出算法的基本思想。根据设计思想，采用C或C++或Java语言描述算法，关键之处给出注释。说明你所设计算法的时间复杂度。【分析】单链表的应用【解答】算法的基本设计思想（5分）算法实现（6分）算法的时间复杂度（2分）2010年42.（13’）设将n（n1）个整数存放到一位数组R中。试设计一个在时间和空间两方面都尽可能高效的算法。将R中保存的序列循环左移p（0pn）个位置，即将R中的数据由（X0, X1, X2, …, Xn-1）变换为（Xp, Xp+1, …, Xn-1, X1, …, Xp-1）。要求：给出算法的基本思想。根据设计思想，采用C或C++或Java语言描述算法，关键之处给出注释。说明你所设计算法的时间复杂度和空间复杂度。【分析】数组的应用【解答】2011年42．(?15?分）一个长度为?L（L≥1）的升序序列?S，处在第?[L?/?2]??个位置的数称为?S?的中位数。例如，若序列?S1=（11,13,15,17,19），?则?S1?的中位数是?15，两个序列的中位数是含它们所有元素的升序?序列的中位数。例如，若?S2=（2,4,6,8,20），则?S1?和?S2?的中位?数是?11。现在有两个等长升序序列?A?和?B，试设计一个在时间和空?间两方面都尽可能高效的算法，找出两个序列?A?和?B?的中位数。要求：给出算法的基本思想。根据设计思想，采用C或C++或Java语言描述算法，关键之处给出注释。说明你所设计算法的时间复杂度和空间复杂度。【分析】考查顺序表的应用，查找【解答】2013年41.（13’）已知一个整数序列A=（a0, a1,…, an-1），其中0=ain（0=in）。若存在==…==x且mn/2（0=pkn, 1=k=m），则称x为A的主元素。例如A=（0,5,5,3,5,7,5,5），则5为主元素；又如A=（0,5,5,3,5,1,5,7），则A中没有主元素。假设A中的n个元素保存在一个一维数组中，请设计一个尽可能高效的算法，找出A的主元素。若存在主元素，则输出该元素；否则输出-1。要求：给出算法的基本思想。根据设计思想，采用C或C++或Java语言描述算法，关键之处给出注释。说明你所设计算法的时间复杂度和空间复杂度。【分析】顺序表的应用【解答】2014年41．（13’）二叉树的带权路径长度（WPL）是二叉树中所有叶结点的带权路径长度之和，给定一颗二叉树T，采用二叉链表存储，结点结构为：leftweightright其中叶节点的weight域保存该结点的非负权值。设root为指向T的根结点的指针，请设计求T的WPL的算法，要求：给出算法的基本设计思想。使用C或C++语言，给出二叉树结点的数据类型定义。根据设计思想，采用C或C++语言描述算法