《计算机统考数据结构算法部分精析.docx》由会员分享，可在线阅读，更多相关《计算机统考数据结构算法部分精析.docx（9页珍藏版）》请在三一文库上搜索。
1、计算机统考数据结构算法部分精析第一部分：历年真题解析09-13年算法题主要围绕数组，链表，排序为基础出题，一般都能想到解题方法，不过要得到最优算法较难14年算法考点为树这一章的内容，基础为求二叉树高度，由于和往年跨度较大，解题时可能会乱了阵脚，所以今年的复习应在线性表的基础上再辅以树这一章主要算法的掌握。2009年42.（15）已知一个带有表头结点的单链表，结点结构为datalink假设该链表只给出了头指针list。在不改变链表的前提下，请设计一个尽可能高效的算法，查找链表中倒数第k个位置上的结点（k为正整数）。若查找成功，算法输出该结点的data值，并返回1；否则，只返回0。要求：（1） 描
2、述算法的基本设计思想。（2） 描述算法的详细实现步骤。（3） 根据设计思想和实现步骤，采用程序设计语言描述算法（使用C或C+或JAVA语言实现），关键之处请给出简要注释。【分析】本题考查带头节点单链表的应用。【解答】（1） 算法的基本设计思想（5分）（2） 算法的详细实现步骤（5分）（3） 算法实现（5分）提示：算法程序题，如果能够写出数据结构类型定义、正确的算法思想都会至少给一半以上分数，如果能用伪代码写出自然更好，比较复杂的地方可以直接用文字表达。若所给出的算法采用一遍扫描方式就能得到正确结果，可给满分15分；若采用两遍或多遍扫描才能得到正确结果的，最高分10分。若采用递归算法得到正确结果
3、的，最高给10分；若实现算法的空间复杂度过高（使用了大小与k有关的辅助数组），但结果正确，最高给10分。2012年42.（13）假定采用带头结点的单链表保存单词，当两个单词有相同的后缀时，则可共享相同的后缀存储空间，例如，“loading”和“being”的存储映像如下图所示。daolstr1nigebstr2p设str1和str2分别指向两个单词所在单链表的头结点，链表结点结构为dataNext请设计一个时间上尽可能高效的算法，找出由str1和str2所指向两个链表共同后缀的起始位置（如图中字符i所在结点的位置p）。要求（1） 给出算法的基本思想。（2） 根据设计思想，采用C或C+或Java
4、语言描述算法，关键之处给出注释。（3） 说明你所设计算法的时间复杂度。【分析】单链表的应用【解答】（1） 算法的基本设计思想（5分）（2） 算法实现（6分）（3） 算法的时间复杂度（2分）2010年42.（13）设将n（n1）个整数存放到一位数组R中。试设计一个在时间和空间两方面都尽可能高效的算法。将R中保存的序列循环左移p（0pn）个位置，即将R中的数据由（X0, X1, X2, , Xn-1）变换为（Xp, Xp+1, , Xn-1, X1, , Xp-1）。要求：（1） 给出算法的基本思想。（2） 根据设计思想，采用C或C+或Java语言描述算法，关键之处给出注释。（3） 说明你所设计算
5、法的时间复杂度和空间复杂度。【分析】数组的应用【解答】2011年42(15分）一个长度为L（L1）的升序序列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的中位数。要求：（1） 给出算法的基本思想。（2） 根据设计思想，采用C或C+或Java语言描述算法，关键之处给出注释。（3） 说明你所设计算法的时间复杂度和空
6、间复杂度。【分析】考查顺序表的应用，查找【解答】2013年41.（13）已知一个整数序列A=（a0, a1, an-1），其中0=ain（0=in/2（0=pkn, 1=knext;L-next = NULL;while(p!=NULL)r = p-next;p-next = L-next;L-next = p;p = r;return L;【2】 数组或链表归并类型1. 两有序数组进行合并并按大小有序排列将两个有序顺序表合并成一个新的有序顺序表，并由函数返回结果顺序表。基本思想：联系归并排序思想，首先按顺序不断取下两个顺序表表头较小的结点存入新的顺序表中。然后，看哪个表还有剩余，将剩下的部分
7、加入到新的顺序表后面。即为Merge函数的实现算法代码：bool Merge(SeqList A, SeqList B, SeqList &C)if(A.length+B.lengthC.maxSize)return false;int i=0,j=0,k=0;while(iA.length&jB.length)if(A.datai=B.datai+);C.datak+ = A.datai+;elseC.datak+ = B.dataj+;while(iA.length)C.datak+ = A.datai+;while(jB.length)C.datak+ = B.dataj+;C.leng
8、th = k;Return true;2. 删除表中重复元素从有序顺序表中删除所有其值重复的元素，使表中所有元素的值均不同。算法思想：因为是顺序表，所以值相同的元素一定在连续的位置上，用类似于直接插入排序的思想，初始时将第一个元素看做是非重复的有序表。之后顺序依次判断后面的元素是否与前面非重复有序表的最后一个元素相同，如果相同则继续向后判断，如果不同则插入到前面的非重复有序表的最后，直至判断到整个表尾为止。算法代码：bool Delete_Same(SeqList &L)if(L.length=0)return false;int i,j; /i存储第一个不相同的元素，j工作指针for(i=0
9、, j=1; jL.length; j+)if(L.datailchild;elseGetTop(S,p);if(p-rchild&p-rchild!=r)p=p-rchild;push(S,p);p=p-lchild;elsepop(S,p);visit(p-data);r = p;p = NULL;4. 层次遍历（InOrder）【4】 折半查找（二分查找）仅适用于顺序表，可有效的将查找时间减半。基本思路是：首先将给定值key与表中中间位置元素的关键字比较，若相等，则查找成功，返回该元素的存储位置；若不等，则所需查找的元素只能在中间元素以外的前半部分或后半部分中，然后缩小范围，如此重复直到
10、找到为止，或者查找不成功（清楚如何设置结束条件）算法如下：Int Binary_Search(SeqList L,ElemType key)Int low=0,high=L.TableLen-1,mid;While(lowkey)high=mid-1;elselow = mid+1;return -1;【5】 插入排序5.1 直接插入排序（“哨兵”的应用）基本思想：将元素Li插入到前面已经有序的子序列L1i-1中，假定L1已经排好序，则将L(2)L(n)依次插入到前面即可。算法如下：Void InsertSort(ElemType A,int n)Int I,j;for(i=2;i=n;i+)
11、if(Ai.keyAi-1.key)A0=Ai;for(j=i-1;A0.keyAj.key;-j)Aj+1=Aj;Aj+1=A0;【6】 交换排序6.1 冒泡排序基本思想：假定带排序表长为n，从前往后（或从后往前）两两比较相邻元素的值，若为逆序，则交换它们，直到序列比较完。算法如下：Void BubbleSort(ElemType A, int n)for(i=0;ii; j-)if(Aj-1.keyAj.key)swap(Aj-1,Aj);flag=true;If(flag=false) /若未发生交换，说明表已经有序return;6.2 快速排序基本思想：基于分治法，每一趟排序都确定一个
12、元素的位置，并以此为界，将表划分为独立的两部分，然后再在各半部分上继续上述排序。算法如下：记划分算法为Partition()；每次返回确定的那个元素的位置，即以此为界可将表分成两半。主函数为：Void QuickSort(ElemType A, int loe, int high)If(lowhigh)int pivotpos = Partition(A, low, high);QuickSort(A,low,pivotpos-1);QuickSort(A,pivotpos+1,high);/Partition()函数int Partition(ElemType A, int low, int
13、 high)ElemType pivot = Alow;While(lowhigh)while(low=pivot)-high;Alow=Ahigh;while(lowhigh&Alow=pivot)+low;Ahigh=Alow;Alow = pivot;return low;思考题：荷兰国旗问题：设有一个仅由红、白、蓝三种颜色的条块组成的条块序列，请编写一个时间复杂度为O(n)的算法，使得这些条块按红、白、蓝的顺序排好，即排成荷兰国旗图案。算法思想：顺序扫描线性表，将红色条块交换到线性表的最前面，蓝色条块交换到线性表的最后面，为此设立三个指针，其中，j为工作指针表示当前扫描的元素，i以前的
14、元素全部为红色，k以后的元素全部为蓝色。根据j所指示元素的颜色，决定将其交换到序列的前部或者尾部。初始时i=0,k=n-1。【7】 选择排序7.1 简单选择排序算法思想：第i趟排序即从Lin中选择关键字最小的元素与L(i)交换，每一趟排序可以确定一个元素的最终位置算法如下：void SelectSort(ElemType A, int n)for(i=0;in-1;i+)min = i;for(j=i+1; jn; j+)if(AjAmin)min=j;If(min!=i)swap(Ai,Amin);【8】 归并排序Merge()的功能是将前后相邻的两个有序表归并为一个有序表的算法。设两段有序
15、表Alowmid、Amid+1high存放在同一顺序表中相邻的位置上，先将它们复制到辅助数组B中。每次从对应B中的两个段取出一个记录进行关键字的比较，将较小者放入A中，当数组B中有一段超出其表长时，将另一段中的剩余部分直接复制到A中。算法如下：ElemType *B = (ElemType *)malloc(n+1)*sizeof(ElemType); /辅助数组Bvoid Merge(ElemType A, int low, int mid, int high)for(int k=low; k=high; k+)Bk=Ak;for(i=low, j=mid+1,k=i; i=mid&j=high; k+)if(Bi=Bj)Ak=Bi+;elseAk=Bj+;while(i=mid)Ak+=Bi+; /若第一个表未检测完，复制while(j=high)Ak+=Bj+; /若第二个表未检测完，复制 9 / 9