下载文档原格式
研考数据结构真题答案解析数据结构是计算机科学中重要的一门课程，它探索了在计算机内部存储、组织和操作数据的方法和技术。
研究数据结构的目的是设计出高效、稳定和可扩展的算法和数据存储方案。
在研究生招考中，数据结构也是一个常见的考点。
今天，我们将对一道数据结构的真题进行解析，帮助大家更好地理解和应用数据结构。
考题如下：给定一个整数数组nums，我们需要将数组中所有的零元素移动到数组的末尾，同时保持非零元素的相对顺序不变。
例如，给定输入数组nums=[0, 1, 0, 3, 12]，函数应该在不返回任何东西的情况下，修改输入数组为[1, 3, 12, 0, 0]。
要求：只能对输入数组进行直接的操作，不能使用额外的数组。
解析：这是一道经典的数组操作题，目标是将数组中的零移到末尾，同时保持非零元素的相对顺序不变。
题目要求不能使用额外的数组，因此我们需要在原数组上进行操作。
最简单的方法是遍历整个数组，在遇到零元素时，将其后面的所有元素向前移动一位，然后将零元素放在最后。
这个方法的时间复杂度为O(n^2)，其中n是数组长度。
但是这个方法显然不是最优解。
我们可以通过使用两个指针来解决这个问题，一个指针用来遍历整个数组，另一个指针用来指向下一个非零元素应该放置的位置。
我们可以称这两个指针为“当前指针”和“插入指针”。
我们从头开始遍历数组，如果遇到非零元素，则将其插入到插入指针的位置，并将插入指针右移一位。
遍历完整个数组后，我们将插入指针后面的位置都置零。
为了更好地理解这个过程，我们来模拟一下。
将输入数组nums=[0, 1, 0, 3, 12]分解为当前指针和插入指针两个变量，初始时都指向第一个元素0：当前指针：0 -> 1 -> 0 -> 3 -> 12插入指针：0 -> 0 -> 0 -> 0 -> 0遍历过程中，遇到第一个非零元素1，将其插入到插入指针的位置，同时插入指针右移一位：当前指针：0 -> 1 -> 0 -> 3 -> 12插入指针：1 -> 0 -> 0 -> 0 -> 0继续遍历，遇到第二个非零元素3，将其插入到插入指针的位置，插入指针右移一位：当前指针：0 -> 1 -> 0 -> 3 -> 12插入指针：1 -> 3 -> 0 -> 0 -> 0遍历完所有的元素后，将插入指针后面的位置都置零：当前指针：0 -> 1 -> 0 -> 3 -> 12插入指针：1 -> 3 -> 12 -> 0 -> 0最终得到的数组为[1, 3, 12, 0, 0]，与题目要求相符。
2010年考研计算机专业综合考试数据结构试题点评2010年考研计算机专业综合考试是统一命题后的第二次考试。
本次考试统考科目仍然包括四门计算机专业课：数据结构、计算机组成原理、操作系统和计算机网络，这四门课程合在一起称为计算机科学专业基础综合，共150分。
其中数据结构仍然占45分。
总体上来看，2010年的考研数据结构试题仍然注重对基础知识的考察。
重点考察的是对基本知识点、基本概念的理解及应用。
题目的难度适中，没有出现超出考试大纲的题目，也没有一眼就能看出答案的题目；在基础题中又有拔高，本次考试并非考查基本概念的填空，考题比较灵活，重点考察了对基础知识的应用能力、应变能力和实际动手能力。
与2009年的考研数据结构试题相比，难度略有提高，考察的内容更加深入、灵活，并且有针对性。
下面我们对2010的考研计算机专业综合考试进行简要的分析。
一、单项选择题这部分共有40个选择题，每题2分，共80分。
单选题覆盖了大纲列出的各章的知识点，主要考察对各种数据结构、基本查找和排序算法的基本概念和特点的理解以及灵活运用。
1-11题是数据结构部分的试题。
1.若元素a、b、c、d、e、f依次进栈，允许进栈、退栈操作交替进行。
但不允许连续三次进行退栈工作，则不可能得到的出栈序列是（）A.dcebfaB.cbdaefC.bcaefdD.afedcb点评：此题考察对栈的基本操作（进栈、退栈）的理解和应用。
栈的特点是后进先出。
若元素a、b、c、d、e、f依次进栈，要得到出栈序列afedcb，需要进行的操作为：a进栈，a 出栈，b，c，d，e，f分别进栈，然后f，e，d，c，b分别依次出栈，连续出栈操作超过3次。
故答案为D。
2.某队列允许在其两端进行入队操作，但仅允许在一端进行出队操作，则不可能得到的顺序是（）A.bacdeB.dbaceC.dbcaeD.ecbad点评：此题考察对可以两端入队，一端出队的队列的操作。
一般教材中讨论的队列都是一端入队，一端出队，而本题中的队列可以两端入队，一端出队，入队出队操作要复杂一些，是对教材内容的深化。
数据结构考研真题与答案解析【数据结构考研真题与答案解析】数据结构是计算机科学与技术中的重要学科，也是考研中不可或缺的一部分。
在考研中，掌握数据结构的相关知识对于顺利通过考试至关重要。
本文将为大家介绍一些历年考研真题，并对答案进行解析，希望对大家备考有所帮助。
一、堆排序相关问题1. 2014年考研真题（题目描述）给定n个整数的序列S，其中$n \leq 10^6$且没有相同元素，并且给定另外的一个元素x，输出S中小于x的最大的数，如果不存在则输出“-1”。
（解析）这是一道关于堆排序的问题。
我们可以利用大顶堆来解决这个问题。
首先建立一个大顶堆，然后依次将序列S中的元素插入到堆中。
在插入的过程中，我们可以通过比较当前元素和x的大小，找到小于x的最大的数。
最后输出即可。
若不存在小于x的元素，则输出“-1”。
二、图的遍历问题2. 2016年考研真题（题目描述）对于一个无向图G，设计一个算法，判断图G是否连通，并给出详细的算法描述和复杂度分析。
（解析）对于这个问题，我们可以使用深度优先搜索（DFS）或广度优先搜索（BFS）来解决。
我们可以从图中的任意一个节点开始进行深度或广度遍历，然后标记遍历过的节点。
最后判断所有的节点是否都被遍历到，若是，则图G是连通的，否则不连通。
若使用邻接表表示图，则DFS和BFS的时间复杂度均为O(|V|+|E|)，其中|V|和|E|分别代表图中的节点数和边数。
三、二叉搜索树相关问题3. 2018年考研真题（题目描述）给定一个二叉搜索树，请设计一个算法，找出其中第k大的节点。
（解析）对于这个问题，我们可以利用二叉搜索树的性质。
由于二叉搜索树的中序遍历结果是有序的，我们可以进行中序遍历，并将遍历结果保存到一个有序数组中。
然后根据数组中第k个位置的元素找到对应的节点即可。
算法的时间复杂度为O(n)，其中n为二叉搜索树中节点的个数。
四、哈夫曼编码问题4. 2017年考研真题（题目描述）给定一段文字，编写一个算法，根据字符出现的频率构建哈夫曼编码。
数据结构考研真题与解析数据结构考研真题与解析数据结构是计算机科学中非常重要的一门课程，也是考研中的必考科目之一。
掌握好数据结构的知识，对于提高编程能力和解决实际问题具有重要意义。
在备考过程中，了解历年的考研真题并进行解析是很有帮助的。
本文将通过对数据结构考研真题的解析，帮助读者更好地理解数据结构的知识点和解题技巧。
第一道题目是关于树的遍历的。
题目要求给定一棵二叉树的前序遍历和中序遍历序列，求出该二叉树的后序遍历序列。
这是一道经典的树的遍历问题，解题的关键在于找到根节点的位置，并将问题划分为子问题进行递归求解。
通过观察前序遍历和中序遍历序列，我们可以发现前序遍历序列的第一个元素一定是根节点，而在中序遍历序列中，根节点的左边是其左子树的中序遍历序列，右边是其右子树的中序遍历序列。
因此，我们可以通过递归的方式求解左子树和右子树的后序遍历序列，然后将根节点放在最后，即可得到整棵树的后序遍历序列。
第二道题目是关于图的最短路径的。
题目给定一个有向带权图，要求从图中的一个顶点出发，找到到达其他所有顶点的最短路径。
这是一个经典的图算法问题，可以使用Dijkstra算法来解决。
Dijkstra算法的思想是从起点开始，依次找到离起点最近的顶点，并更新其他顶点的最短路径。
具体实现时，可以使用一个数组来记录每个顶点的最短路径长度，以及一个优先队列来选择最短路径最小的顶点进行扩展。
通过不断更新最短路径长度，直到所有顶点都被访问到，即可得到最短路径。
第三道题目是关于排序算法的。
题目给定一个整数数组，要求使用快速排序算法对其进行排序。
快速排序是一种高效的排序算法，其基本思想是通过一趟排序将待排序序列分割成独立的两部分，其中一部分的元素都比另一部分的元素小，然后再对这两部分分别进行排序。
具体实现时，可以选择一个基准元素，将小于基准元素的放在左边，大于基准元素的放在右边，然后递归地对左右两部分进行排序。
通过不断地划分和排序，最终整个序列就会有序。
数据结构题库及答案详解一、选择题1. 在数据结构中，线性结构的特点是什么？A. 结构中存在唯一的开始结点和终端结点B. 结构中所有结点的前驱和后继都存在C. 结构中所有结点都只有一个直接前驱和一个直接后继D. 结构中存在多个开始结点和终端结点答案：C2. 栈是一种特殊的线性表，其特点是：A. 先进先出B. 先进后出C. 可以同时在两端进行插入和删除操作D. 只能在一端进行插入和删除操作答案：D3. 在二叉树的遍历算法中，先序遍历的顺序是：A. 先访问根结点，然后遍历左子树，最后遍历右子树B. 先遍历左子树，然后访问根结点，最后遍历右子树C. 先遍历右子树，然后访问根结点，最后遍历左子树D. 先遍历左右子树，最后访问根结点答案：A二、填空题4. 在图的遍历中，______算法可以避免重复访问同一顶点。
5. 哈希表的冲突可以通过______方法来解决。
答案：4. 深度优先搜索（DFS）5. 链地址法或开放地址法三、简答题6. 简述排序算法中的快速排序算法的基本原理。
答案：快速排序算法是一种分治算法，它通过选择一个元素作为“基准”，然后将数组分为两个子数组，一个包含小于基准的元素，另一个包含大于基准的元素。
然后对这两个子数组递归地应用快速排序算法。
7. 解释什么是递归，并给出一个递归函数的例子。
答案：递归是一种在函数中调用自身的编程技术。
递归函数必须有一个明确的终止条件，以避免无限递归。
例如，计算阶乘的递归函数如下：```int factorial(int n) {if (n == 0) return 1; // 终止条件return n * factorial(n - 1); // 递归调用}```四、编程题8. 编写一个函数，实现单链表的反转。
答案：```c// 假设ListNode是链表节点的定义ListNode* reverseList(ListNode* head) {ListNode* prev = NULL;ListNode* curr = head;ListNode* next = NULL;while (curr != NULL) {next = curr->next; // 保存下一个节点curr->next = prev; // 反转指针prev = curr; // 移动prevcurr = next; // 移动curr}return prev; // 新的头节点}```9. 给定一个整数数组，请实现一个函数来找到数组中的最长连续子序列的长度。
数据结构考研真题及其答案完整版数据结构是计算机科学与技术领域中的一门重要课程，也是计算机考研中必考的一门科目。
通过研究数据结构，可以帮助我们更好地理解和应用计算机算法，提高计算机程序的效率和性能。
为了帮助考生更好地备考数据结构，本文将分享一些数据结构考研真题及其答案，供考生参考。
一、选择题1. 下列关于栈的叙述中，错误的是（）A. 栈是一种线性数据结构，具有后进先出（LIFO）的特点B. 栈可以用数组实现，也可以用链表实现C. 栈的插入和删除操作都是在同一端进行的D. 栈的插入和删除操作的时间复杂度都是O(1)答案：C解析：栈的插入操作叫做入栈，删除操作叫做出栈。
入栈和出栈操作都是在栈顶进行的，而不是同一端。
2. 假设要对n个整数关键字进行排序，以下排序算法中，平均时间复杂度最小的是（）A. 冒泡排序B. 快速排序C. 归并排序D. 直接插入排序答案：C解析：归并排序的时间复杂度是O(nlogn)，平均时间复杂度最小。
二、填空题1. 下列关于图的遍历顺序的说法中，正确的是：深度优先搜索访问的顺序是________，广度优先搜索访问的顺序是________。
答案：前序遍历，层次遍历解析：深度优先搜索即前序遍历，广度优先搜索即层次遍历。
2. 给定一个最小堆，若删除堆顶元素后，需要对堆进行调整，所采用的操作是________。
答案：下滤解析：删除堆顶元素后，将最后一个叶子节点放到堆顶，然后进行下滤操作。
三、简答题1. 请简要说明动态规划算法的基本思想和应用场景。
答：动态规划算法的基本思想是将问题分解为多个子问题，通过求解子问题的最优解来得到原问题的最优解。
它通常适用于具有重叠子问题和最优子结构性质的问题。
动态规划算法可以大大减少问题的重复计算，提高算法的效率和性能。
它在求解最短路径、最长公共子序列、背包问题等具有广泛的应用。
2. 请简要介绍红黑树的特点和应用场景。
答：红黑树是一种自平衡的二叉查找树，它具有以下特点：1) 每个节点都有一个颜色，红色或黑色；2) 根节点是黑色的；3) 叶子节点（NIL节点）都是黑色的；4) 如果一个节点是红色的，则它的两个子节点都是黑色的；5) 从根节点到叶子节点的路径上，不同路径上黑节点的个数相同。
1、给出年、月、日，计算该日是该年的第几天。
（本题15分）#include<stdio.h>Int get_days_of_month(int year,int month){if(month==1||month==3||month==5||month==7||month==8||month==10||month==12) return31;else if(month==2)if(year%400==0|| (year%4==0&& year%100!=0))return29;elsereturn28;elsereturn30;}Void main(){int i,year,month,day,sum=0,flag=1;while(flag){printf("please input the date(for example:2005,6,9):");scanf("%d,%d,%d",&year,&month,&day);if(year>0)if(month>=1&& month<=12)if(day>=1&& day<=get_days_of_month(year,month))flag = 0;}for(i=1;i<month;i++){sum +=get_days_of_month(year,i);}sum += day;printf("The date is %d day.\n",sum);}2、有几个学生，每个学生考m门课，要求编一函数，能检查n个学生有无不及格的课程，如果有某一学生有一门或一门以上课程不及格，就输出该学生的学号（学号从0开始）和其全部课程成绩。
（本题15分）#include<stdio.h>#define N 100void main(){Int a[N][N];int i,j,m,n,flag;printf("please input the number of students:");printf("please input the number of courses:");scanf("%d",&m);for(i=0;i<n;i++){printf("please input No.%d scores:",i);for(j=0;j<m;j++)scanf("%d",&a[i][j]);}printf("students who have failed their courses as follows:");for(i=0;i<n;i++){flag = 0;for(j=0;j<m;j++){if(a[i][j]<60){flag=1;break;}}if(flag){printf("No.%d ",i);for(j=0;j<m;j++)printf("%d ",a[i][j]);}printf("\n");}}3、用二分法求方程“(2*X^3)-(4*x^2)+(3*x)-6 = 0”在(-10,10)之间的根。
数据结构试题与答案及解析导语：本文为广大数据结构学习者提供一些经典试题的答案及详细解析，帮助读者更好地理解与掌握数据结构的知识点。
以下是一些常见的试题以及对应的答案与解析。
1. 试题：请简述什么是数据结构？答案及解析：数据结构是计算机科学中研究和应用各种数据元素之间关系的一门学科，涉及到数据的组织、存储、管理和操作等方面。
数据结构为算法的设计与实现提供了基础，并在解决实际问题时起到了重要的作用。
因此，数据结构的学习对于编程能力的提升非常重要。
2. 试题：请解释什么是哈希表（Hash Table）？并简述其原理。
答案及解析：哈希表是一种常用的数据结构，其基本原理是通过将键（Key）通过哈希函数（Hash Function）映射到数组的某个位置上，实现将键与值（Value）建立一一对应关系的数据结构。
哈希表的原理比较简单，首先我们需要一个合适的哈希函数，该函数能够将键映射到数组的某个位置上。
当我们需要插入或查找键值对时，首先根据键经过哈希函数得到其对应的数组下标，然后将值存储在该位置上。
当发生冲突时（即多个键映射到同一个位置），可使用链表或其他解决冲突的方法来处理。
3. 试题：请说明线性表的定义及其特点。
答案及解析：线性表是数据结构中最基本且最常见的一种形式，其由n个数据元素构成的有序序列，特点如下：1) 元素之间呈线性关系，即每个元素只有一个直接前驱和一个直接后继。
2) 线性表的长度是固定的，且有序排列。
3) 线性表中任意两个元素之间的关系是确定的，不会发生变化。
4. 试题：请解释树的概念及其基本特点。
答案及解析：树是一种非常重要的数据结构，由n个节点组成，其中有且仅有一个特定的节点称作根节点，其余节点分成m个互不相交的子集，每个子集自身又是一个树。
树的基本特点如下：1) 树中的节点具有层次关系，从根节点开始，每个节点可以有若干子节点。
2) 每个节点有且仅有一个父节点，除了根节点。
3) 树中的任意两个节点之间都存在唯一的路径。
算法与数据结构考研试题精析算法与数据结构是计算机科学考研中的重要内容，掌握算法与数据结构的基本理论和实践能力对于考研的成功至关重要。
以下是算法与数据结构考研试题的精析，同时给出相应的参考内容。
1. 解释什么是算法和数据结构，并举例说明它们在实际应用中的重要性。
算法是解决特定问题或执行特定任务的一系列步骤。
它对输入数据进行处理，得到期望的输出结果。
数据结构是存储和组织数据的方式，为算法提供数据的存储和访问方式。
算法和数据结构是相互关联的，好的数据结构可以支持高效的算法。
参考内容：- 算法：算法是有限的、确定的、可行的步骤集合，用于解决问题或执行任务。
例如，排序算法（如冒泡排序、快速排序）用于对一组数据进行排序，查找算法（如二分查找）用于在有序数据集中查找特定元素。
- 数据结构：数据结构是一种组织和存储数据的方式。
例如，链表是一种常见的数据结构，它可以用于存储和操作一系列元素。
栈和队列是数据结构的特殊形式，它们分别支持先进后出和先进先出的数据访问方式。
- 应用重要性：算法和数据结构在计算机科学和软件工程中有广泛应用。
好的算法和数据结构可以提高程序的性能和效率。
例如，在大规模数据集上使用合适的算法和数据结构可以显著减少计算时间，提高系统的响应速度。
2. 请解释什么是时间复杂度和空间复杂度，并给出它们的计算方法。
时间复杂度是算法执行所需的时间量度，它表示算法运行时间与问题规模的增长速度。
空间复杂度是算法在执行过程中所需的存储空间的量度。
参考内容：- 时间复杂度：时间复杂度可以用大O符号（O）来表示。
计算方法包括统计算法的基本操作数、忽略常数项和低阶项，只考虑最高阶项。
常见的时间复杂度分类包括O(1)（常数时间复杂度）、O(log n)（对数时间复杂度）、O(n)（线性时间复杂度）、O(n^2)（平方时间复杂度）等。
- 空间复杂度：空间复杂度可以用大O符号（O）来表示。
计算方法包括统计算法使用的额外存储空间和输入规模的关系。
考研计算机数据结构常考题精讲一、概述数据结构是计算机科学中非常重要的基础知识，它涉及到数据的组织、存储和操作方法。
在考研计算机专业的学习过程中，数据结构也是常考的重点内容。
本文将对考研计算机数据结构中的常考题进行深入解析，帮助考生更好地理解和掌握这一重要知识点。
二、线性结构1. 数组数组是一种线性结构，它是一系列连续的内存单元，用于存储相同类型的数据。
常考题包括数组的创建、访问、插入和删除等操作。
考生需要掌握数组的基本概念和操作方法，并理解数组的内存分配方式。
2. 链表链表也是一种线性结构，它由一系列节点组成，每个节点包含数据和指向下一个节点的指针。
常考题包括链表的创建、插入、删除和逆序等操作。
考生需要了解链表的结构特点和基本操作，掌握链表的插入和删除方法。
三、树形结构1. 二叉树二叉树是一种特殊的树形结构，每个节点最多有两个子节点。
常考题包括二叉树的遍历方法，包括前序、中序和后序遍历。
考生需要熟悉二叉树的遍历算法，并能够灵活运用。
2. 平衡二叉树平衡二叉树是一种特殊的二叉树，它的左右子树高度差不超过1。
常考题包括平衡二叉树的插入和删除操作。
考生需要了解平衡二叉树的构造和调整方法，掌握平衡二叉树的插入和删除算法。
四、图形结构图是一种非线性结构，它由节点和边组成。
常考题包括图的遍历方法，包括深度优先搜索和广度优先搜索。
考生需要了解图的基本概念和遍历算法，掌握图的深度优先搜索和广度优先搜索方法。
五、查找和排序1. 顺序查找顺序查找是一种简单的查找方法，逐个比较待查找元素和数组中的元素，直到找到或遍历完所有元素。
常考题包括顺序查找的实现和性能分析。
考生需要了解顺序查找的基本思想和性能特点。
2. 二分查找二分查找是一种高效的查找方法，要求待查找的数组必须是有序的。
常考题包括二分查找的实现和性能分析。
考生需要了解二分查找的基本思想和性能特点，掌握二分查找的实现算法。
3. 快速排序快速排序是一种常用的排序算法，它基于分治的思想，通过将数组分为较小和较大的两个子数组，递归地排序子数组。
一、总体分析
计算机科学与技术学科全国硕士研究生统一入学考试已经进行了两次。
数据结构部分的考试范围要求掌握：
1，基本数据结构的知识
2，算法设计和编程的能力
3，综合应用算法和数据结构的技能
从考试的命题来看，2010年比2009年的题目难度要大一些。
在这里，我对2009年考题与2010年考题的考试范围进行了简单的比较：
A, 选择题部分，请参考表1
表1
2010年选择题还有一道题（11题）是对几种排序方法的考察。
由表1我们可以总结出，在选择题部分，各主要知识点分布如下，请参考表2：
表2
B ，综合应用题部分的试题范围如下：
总体上讲，2009年的试题较简单，2010年的试题比较复杂，且难度稍大，但平时教学中应当都教过，或练习都做过。
二、2010 年考试改卷的基本情况
2010年考试改卷的大概情况如下：
客观题是机改，数据结构部分总分22分，平均得分约为17分，失分较多的是
第2题（双端队列）
第5题（K叉树叶结点的计算）
第8题（拓扑排序的序列个数）
第10题（快速排序递归次数）；
主观题是人改，数据结构部分总分23分
第41题10分，平均得分5分，失分最多的是
计算散列表长度（2分），多数考生未得分。
将给定元素存储到散列表中（6分），平均得3分。
如果第1问错了，不影响第2问得分；但可惜散列函数有不少同学选择不完全对。
计算平均查找长度（2分），平均得1分。
第42题是算法设计题13分，平均得6～8分，失分最多的是算法效率达不到要求。
许多考生成绩差的主要原因：
1，本科数据结构课程学习不够扎实；
2，考前复习不够充分；
3，考试时审题不仔细，急于给出答案，未严格推导。
三、2010年考试试卷分析
由于篇幅有限，在此只例举综合题两道大题进行分析。
二、综合应用题
41题：（10分）将关键字序列{ 7, 8, 30, 11, 18, 9, 14 } 散列存储到散列表中，散列表的存储空间是一个下标从 0 开始的一个一维数组散列，函数为：
H(key) = (key´3) MOD 7
处理冲突采用线性探测再散列法，要求装载因子为 0.7
问题：
(1) 请画出所构造的散列表。
(2) 分别计算等概率情况下，查找成功和查找不成功的平均查找长度。
解答：这是一道常规的数据结构题目。
实际上要做三步工作：计算表的长度，从而将 7 个数据存储到散列表中，最后计算等查找概率情形下，查找成功和查找不成功的平均查找长度。
(1) 根据题意，表的装载因子为a = n/m = 0.7，n = 7，因此有m = n/a = 10，即表长度为m = 10。
分别计算各个数据元素的散列地址：
H(7) = (7*3) mod 7 = 0，一次比较到位
H(8) = (8*3) mod 7 = 3，一次比较到位
H(30) = (30*3) mod 7 = 6，一次比较到位
H(11) = (11*3) mod 7 = 5，一次比较到位
H(18) = (18*3) mod 7 = 5，冲突，= 6，冲突，
= 7，三次比较到位
H(9) = (9*3) mod 7 = 6，冲突，= 7，冲突，
= 8，三次比较到位
H(14) = (14*3) mod 7 = 0，冲突，= 1，二次比较到位
根据以上得到的各数据元素的散列地址，可以得到如下散列表：图1
图1
42题：（13分）设将n (n > 1) 个整数存放到一维数组 R中。
设计一个在
时间和空间两方面尽可能高效的算法。
将 R 中的序列循环左移 p（0 < p < n）个位置，即将 R 中的数据由 (a0, a1, ……an-1) 变换为(ap, ap-1, …an-1, a0, a1, …, ap-1)。
要求：
(1) 给出算法的基本设计思想。
(2) 根据设计思想，采用C或C++或JaVa语言描述算法，关键之处给出注释。
(3) 说明你所设计算法的时间复杂度和空间复杂度。
解答：此算法即有名的海豚算法。
解法一（标准答案）
算法基本思路是首先把序列{ a0, a1, ..., ap, …, an-1 }逆转为{an-1, an-2, ..., ap, …,a0 }，再分别逆转{ an-1, an-2, ..., ap }和{ ap-1, ap-2, …,a0 }，最后得到{ ap, ap+1, …, an-1, a0, …, ap-1}。
(1) 逆转算法
void reverse ( int A[ ], int left, int right ) {
int n = right-left+1;
if ( n <= 1 ) return;
if ( n <= 1 ) return;
for ( int i = 0; i < n/2; i++ ) {
int temp = A[i];
A[i] = A[n-i-1];
A[n-i-1] = temp;
}
}
(2) 循环左移算法
void sift_Left ( int a[ ], int n, int p ) {
reverse ( a, 0, n-1 );
reverse ( a, 0, n-p-1 );
reverse ( a, n-p, n-1 );
}
第一个 reverse 函数执行了3n/2次数据移动，使用了一个辅助存储；第二个 reverse 函数执行了3(n-p)/2次数据移动，使用了一个辅助存储；第三个reverse 函数执行了3p/2次数据移动，使用了一个辅助存储；总共执行了3n次数据移动，使用了1个辅助存储。
解法二（利用最大公约数）清华阅卷组给出
如果n与p不互质，一次循环左移只涉及间隔为p
如果n与p不互质，一次循环左移只涉及间隔为p的部分数据元素，可先求n与p的最大公约数m,再做m次循环左移，每次比上次右错一位，从而实现所有数据元素的循环左移。
例如，n = 10，p = 4，m = 2，做 2 次循环左移。
第1次涉及位置0-4-8-2-6，第2次涉及位置1-5-9-3-7。
(1) 求n与p的最大公约数的算法
int GCD( int n, int p ) {
//函数用辗转相除法计算n与p的最大公约数, 若n
//与p互质, 则函数返回1.
if ( n < p ) { int temp = n; n = p; p = temp; }
int r = n % p;
while ( r != 0 ) { n = p; p = r; r = n % p; }
return p;
}
(2) 循环左移算法
void sift_k ( int a[ ], int n, int p ) {
if ( !p ) return;
int i, j, m, k, temp;
m = GCD(n, p);
for ( k = 0; k < m; k++ ) {
temp = a[k]; i = k; j = (i +p) % n;
while ( j != k ) {
a[i] = a[j]; i = j; j = ( j+p ) % n;
}
a[i] = temp;
}
}
解法三（解法二的改进型）清航考研给出
调用子程序需要花费较多的时间和空间代价，本算法省去了计算最大公约数，仅利用一个控制变量控制循环左移的次数，效果更好。
void siftLeft_p ( int a[ ], int n, int p ) {
if ( !p ) return;
int i, j; int temp; int count = 0, k = 0;
while ( count < n ) {
i = k; temp = a[i]; j = (i+p) % n;
while ( j != k ) {
a[i] = a[j]; i = j; j = (i+p) % n;
count++;
}
a[i] = temp; count++;
k++;
}
}
设m为n与p的最大公约数，则最内层while循环执行m次，每次循环执行n/m+1次数据移动，包括与temp的相互传送2次，总的数据移动次数为m*(n/m+1) = n+m。
特别地，当p = n时，m = n，最内层while循环不执行，总的数据移动次数2n，做了n次与temp的传出和传入；当p = 0时，总的数据移动次数为0。
算法用了一个附加存储temp。
解法四（被扣了分的算法）
很多考生使用了一个附加数组，先暂存子序列
{ a0, a1, ..., ap }，再把序列中后面的n-p个数据元素前移，得{ ap, …, an-1 }；最后把暂存到临时数组中的子序列拷贝到an-1后面，得到结果： { ap, …, an-1, a0, a1, ..., ap }
由于使用的附加空间较多，相应也扣了一些分。
算法移动元素的次数为n+p；特别地，当n = p 时，算法移动元素的次数为2n。
