当前位置：文档之家 › 2016年考研终极冲刺800题——数据结构【完成版2】

2016年考研终极冲刺800题——数据结构【完成版2】

  • 格式：pdf
  • 大小：1.46 MB
  • 文档页数：100

梦享考研系列2016年考研终极冲刺800题数据结构最后50天了，再冲刺一次吧，为考研再努力一次！本资料改编自《2016年统考408核心题型》数据结构部分和近3年高校自主命题的数据结构真题。

战友们，让我们再冲锋一次吧！2017年本书拟改写成《2017年考研终极冲刺800题——数据结构》的部分内容。

目录第1章 算法的时间复杂度和空间复杂度 (5)第2章 线性表 (9)2.1 线性表的定义和基本操作 (9)2.2 线性表的实现 (13)第3章 栈、队列和数组 (18)3.1 栈和队列的基本概念 (18)3.2 栈和队列的顺序存储结构 (21)3.3 栈和队列的链式存储结构 (25)3.4 栈和队列的应用 (27)3.5 特殊矩阵的压缩存储 (29)第4章 树与二叉树 (32)4.1 树的概念 (32)4.2 二叉树 (33)4.3 树、森林 (43)4.4 树的应用 (45)第5章 图 (49)5.1 图的概念 (49)5.2 图的存储及基本操作 (51)5.3 图的遍历 (54)5.4 图的基本应用及其复杂度分析 (56)第6章 查找 (64)6.1 顺序查找法 (64)6.2 折半查找法 (64)6.3 B-树 (68)6.4 散列（Hash）表及其查找 (74)第7章 内部排序 (79)7.1 插入排序 (79)7.2 冒泡排序（bubble sort） (79)7.3 简单选择排序 (82)7.4 希尔排序（shell sort） (83)7.5 快速排序 (84)7.6 堆排序 (86)7.7 归并排序（merge sort） (93)7.8 基数排序 (94)7.9 各种内部排序算法的比较和应用 (96)“梦享考研系列”辅导书——答疑解惑 (99)第1章算法的时间复杂度和空间复杂度温馨提示：算法的时间复杂度和空间复杂度几乎在每一年的统考中都会命中一个题，基本的要求是考生能够根据算法来分析时间复杂度。

1.算法分析的主要内容是（）。

A.正确性B.可读性和稳定性C.简单性D.空间复杂性和时间复杂性【2014—武汉科技大学】【考查内容】算法分析的主要内容。

【解析】算法是对特定问题求解过程的描述，是指令的有限序列。

算法主要包括以下几个重要特性：(1).有穷性。

算法的执行步骤必须是有限的，每一步的执行时间也必须是有限的，即算法必须在经过有限的执行时间后完成。

(2).确定性。

算法中的每一条指令，必须有确切的含义，不能有一个或者多个含义。

对于相同的输入，其输出是相同的。

(3).可行性。

算法描述的操作，可以通过执行已经实现的基本运算执行有限次获得。

(4).输入和输出。

算法可以有零个或者多个输入，并且至少有一个输出。

值得注意的是，算法的主要性质，并不是算法分析的主要内容。

算法分析的主要内容是算法的效率，通常指算法的时间复杂度和空间复杂度两种度量方式。

所谓算法的时间复杂度，是指执行算法所需要的计算工作量。

一个算法的空间复杂度，一般是指执行这个算法所需要的内存空间。

【参考答案】D2.设n 是描述问题规模的非负整数，下面程序片段的时间复杂度是（）。

x=2；while(x<n/2)x=2*x；A.O(log2n)B.O(n)C.O(nlog2n)D.O(n2)【2011年统考——第1题】【考查内容】算法的时间复杂度。

【解析】首先，我们要找到程序中执行频率最高的语句，来计算算法的时间复杂度。

显然，语句“x=2*x”的执行频率最高。

假设该语句总共执行了k次，那么第k+1次执行时因为2k+1≥n/2而退出执行。

值得注意的是，在计算算法的时间复杂度时，通常我们都会忽略系数和抓大端。

比如某个算法的执行次数与n的关系为50n2+100n+10000，抓大端时我们只考虑阶最高的项，即50n2，然后再删除系数50，得到算法的时间复杂度为O(n2)。

这里一样的道理，有k+1≈log2(n/2)，程序的执行次数k约为log2(n/2)-1，算法的时间复杂度为O(log2n) 。

【参考答案】A3.求整数n(n≥0)阶乘的算法如下，其时间复杂度是（）。

int fact(int n){if (n<=1) return 1;return n*fact(n-1);}A.O(log2n)B.O(n)C.O(nlog2n)D.O(n2)【2012年统考——第1题】【考查内容】算法的时间复杂度。

【解析】时间复杂度是由语句频度分析得来. 递归算法中重复执行的语句主要是调用. 所以递归算法的时间复杂度分析主要是分析递归算法中递归函数调用的次数。

对于本题，咱们给出一个递归的图解过程，如图1.1所示。

图1.1从图解可知，该递归过程是线性的。

总共递归执行了n次，时间复杂度为O(n)。

【参考答案】B4.已知两个长度分别为m 和n 的升序链表，若将它们合并为一个长度为m+n 的降序链表，则最坏情况下的时间复杂度是（）。

A.O(n)B.O(m×n)C.O(min(m,n))D.O(max(m,n))【2013年统考——第1题】【考查内容】两个升序链表合并成降序链表的时间复杂度。

【解析】我们假设两个升序链表A和B分别如下图所示。

图1.2会出现时间复杂度最大的情况（呵呵…请同学自己想想还有没有其他情况？），即B表全部插入之后，A表剩余的结点采用头插法插入到链表C中。

A表C表B表图1.2要将图1.2的A表和B表合并成C表，显然时间复杂度是O（m+n）。

但是没有这个选项，所以需要咱们再考虑一下哪一个更加接近这个答案。

我们再假设一种极端的情况，那就是我们上图的一个延伸。

假设A表的长度远比B表长（即m远大于n），那么时间复杂度O（m+n）等价于O（m）。

故而，将长度为m和n的升序链表合并成长度为m+n的降序链表，时间复杂度为O（max(m,n)）。

实际上，max(m, n)≤m + n ≤2max(m, n)，有O(m + n) 等价于O(max(m, n))。

这样可能便于大家理解一些。

【参考答案】D5.下列程序段的时间复杂度是（）。

count=0;for(k=1;k<=n;k*=2)for(j=1;j<=n;j++)count++;A.O(log2n)B.O(n)C.O(nlog2n)D.O(n2)【2014年统考——第1题】【考查内容】算法的时间复杂度。

【解析】从程序可以看出，执行频度最高的语句是“count++”。

内层循环的循环变量是j，与外层层循环的循环变量i显然没有半毛钱关系。

从内层循环“for(j=1;j<=n;j++)”来看，每一个内层循环都会导致“count++”执行n次。

接下来，我们再考虑外层循环“for(k=1;k<=n;k*=2)”。

每一次执行外层循环，k都是以2的倍数增加，假设执行了t次，则2t = n,显然有t=log2n。

那么，内外两层循环总共执行了n*t次，即nlog2n次。

【参考答案】C6.算法复杂度通常是表达算法在最坏情况下所需要的计算量。

一般不用来表达算法复杂度的表达式为（）。

A.O(n3)B.O(100)C.O(nlogn)D.O(1.5n)【2014年—中山大学】【考查内容】算法的时间复杂度。

【解析】时间复杂度一般指的是渐进时间复杂度，指当问题规模趋向无穷大时，该算法时间复杂度的数量级。

显然，B答案表示成O(1)就可以了。

常见的时间复杂度，按数量级递增排列依次为：常数阶O(1)、对数阶O(log2n)、线性阶O(n)、线性对数阶O(nlog2n)、k次方阶O(n k)、指数阶O(2n)等。

【参考答案】B7.下面程序的时间复杂度为（）。

For（i=0;i<m;i++）For (j=0;j<n;j++)A[i][j]=i*j;A.O(m2)B.O(n2)C.O(m*n)D.O(m+n)【2014年—华东交通大学】【考查内容】算法的时间复杂度。

【解析】分析算法的时间复杂度时，我们通常先找到执行得最频繁的执行语句，用该语句的执行频度，来度量算法的时间复杂度。

显然，语句“A[i][j]=i*j”的执行频度最高。

该语句在内层循环需执行n次，外层总共循环m次。

所以总共执行m*n次，时间复杂度可以表示成O(m*n)。

【参考答案】C第2章线性表2.1 线性表的定义和基本操作温馨提示：线性表的定义和基本操作部分，从历年统考和高校自主命题的真题来看，主要考察了两个问题：1、什么是线性表？2、线性表存储方式？3、线性表怎么样插入、删除。

请同学们围绕这三个问题，展开复习，其中第3个问题是本考点的重点。

1.在一个单链表中，已知*q结点是*p结点的前驱结点，若在*q和*p之间插入*s结点，则执行（）。

A.s->next=p->next;p->next=s;B.p->next=s->next;s->next=p;C.q->next=s;s->next=p;D.p->next=s;s->next=q;【2013年——昆明理工大学】【考查内容】在单链表中插入结点的正确操作。

【解析】单链表中插入和删除结点操作是常见的操作，希望大家要多练习，掌握这些基本的操作。

说透了，其实不同的题目中，这些操作都大同小异的，学会灵活应用，才是硬道理。

已知*q结点是*p结点的前驱结点，在*q结点和*p结点之间插入*s结点，如图2.1所示。

图2.1注意插入结点的过程中，要防止“掉链”的情况（即指针调整的过程中，后续指针出现错误）。

为了防止“掉链”，需要把q的指针先赋给s的指针，然后再调整q的指针指向结点*s。

即“s->next=q->next; q->next=s”。

当然，若3个结点的指针都很明确，像本题三个结点的指针p、q、s均已知的情况下，可以直接调整指针“q->next=s;s->next=p”。

A答案应该改成：“s->next=q->next; q->next=s”，B答案显然不正确，D答案可改成: “q->next=s;s->next=p”。

【参考答案】C2.在长度为n的顺序表中删除第i个元素（1≤i≤n）时，元素移动的次数为（）。

A.n-iB.n-i+1C.iD.i+1【2008年——太原科技大学】【考查内容】顺序表中删除元素需要移动元素的次数。

【解析】在长度为n的顺序表中删除第i个元素（1≤i≤n）时，将第i+1个位置的元素移动到第i个位置，将第i+2个位置的元素移动到第i+1个位置,…,将第n-1个位置的元素移动到第n-2个位置，将第n个位置的元素移动到第n-1个位置。

图2.2给出元素的移动示意图。

图2.2显然，除了从第i+1个元素到第n个元素总共n-i个元素都需要移动。

合集下载

2016年暨南大学数据结构考研试题答案

2016年暨南大学数据结构考研试题答案

}
void traverse(Tree T,int deepth,int &ans){//递归遍历二叉树，累加计算带权路径长度
if(T == NULL) return;
if(T->lchild == NULL && T->rchild == NULL){
ans += T->weight*deepth;
7. X
8. √
9. √
10. X
四、
简答题
1. （1）画出二叉树如下：
（2）将该数转换为森林得：
2. 画出散列之后的 hash 表得：
0
1
48
71
2
3
4
5
6
7
8
9
23
73
14
55
33
43
89
成功查找的平均查找长度为：（1+1+2+2+2+1+5+6+3）/7=23/7
3. 平衡二叉树构造过程如下：
五、
算法填空
1. （1）p->next=L->next
（2）L->next=p
2.
（3）T->lchild
（4）p=p->lchild
（5）p->rchild!=T
（6）p=p->rchild
（7）p=p->rchild
3. （8）T==NULL
（9）T->lchid
（10）T->rchild
六、编写算法
a[low]=a[high];
while(low<high&&a[low]<key])
计算机学科2016考研真题

计算机学科2016考研真题

计算机学科2016考研真题计算机学科作为一门充满活力和不断发展的学科，其考研真题涵盖了多个重要的知识领域，旨在全面考察考生对于计算机专业知识的掌握程度、理解能力和应用水平。

以下将对 2016 年计算机学科考研真题进行详细的分析和探讨。

首先，在数据结构方面，真题考查了常见的数据结构如链表、栈、队列、树和图等。

例如，有一道题目要求考生实现一个基于链表的特定操作，需要考生对链表的基本结构和操作方法有清晰的理解，并能够熟练运用指针进行编程。

另外，关于树的遍历算法以及图的最短路径算法也是重点考查内容，这要求考生不仅要掌握算法的原理，还要能够在实际问题中灵活运用。

在计算机组成原理部分，真题涉及到计算机的硬件体系结构、指令系统、存储系统等方面。

比如，有题目要求考生分析某一特定指令在CPU 中的执行过程，这就需要考生对计算机的工作原理有深入的理解，包括指令的译码、执行、数据的流动等。

此外，存储系统的层次结构以及 Cache 替换算法等也是常见的考点，考查考生对计算机存储系统性能优化的认识。

操作系统的题目主要围绕进程管理、内存管理、文件系统和设备管理等方面展开。

像进程的同步与互斥问题，考生需要熟练掌握各种同步机制，并能够通过编程或理论分析解决实际的同步问题。

内存管理中的分页与分段存储管理方式，以及文件系统的目录结构和文件的读写操作等，都要求考生具备扎实的操作系统基础知识和分析问题的能力。

计算机网络部分的真题涵盖了网络体系结构、物理层、数据链路层、网络层、传输层和应用层等各个层次的内容。

例如，IP 地址的分配与子网掩码的计算，TCP 三次握手和四次挥手的过程，以及 HTTP 协议的工作原理等。

这些题目既考查了考生对网络基本概念的理解，也检验了他们在实际网络环境中分析和解决问题的能力。

总的来说，2016 年计算机学科考研真题具有以下特点：一是注重基础知识的考查。

无论是数据结构、计算机组成原理、操作系统还是计算机网络，都对基本概念、原理和算法进行了深入细致的考查，这要求考生在复习过程中要打牢基础，不能有任何的疏漏。

数据结构 排序 历年考研练习题库 试卷及答案

数据结构 排序 历年考研练习题库 试卷及答案

数据结构排序历年考研练习题库试卷及答案数据结构排序历年考研练习题库试卷及答案一、冒泡排序冒泡排序是一种基本的排序算法，它通过重复地交换相邻两个元素的位置来实现排序。

算法的基本思想是从待排序的元素中比较相邻的两个元素大小，并根据需要交换它们的位置，直到整个序列有序为止。

冒泡排序的原理如下：首先从序列的第一个元素开始，比较相邻的两个元素的大小，若前面的元素大于后面的元素，则交换它们的位置；否则，继续比较下一对相邻元素，直到比较到序列的最后一个元素。

这样一趟比较下来，序列中最大的元素就会被交换到最后一个位置。

接着，对序列中剩下的 n-1 个元素重复上述过程，执行 n-1 趟比较，直到整个序列有序。

在实践中，冒泡排序的时间复杂度为 O(n^2)，其中 n 为待排序序列的长度。

尽管冒泡排序存在其它更好的排序算法，但它具有编码简单、实现容易以及对小规模数据排序的优势。

二、选择排序选择排序也是一种简单直观的排序算法，它的思想是将待排序序列分为已排好序的部分和未排序的部分，每次选取未排序部分中最小（或最大）的元素，将其放置在已排好序的部分的末尾。

重复此过程，直到整个序列有序。

选择排序的具体步骤如下：首先从待排序序列中找到最小（或最大）的元素，然后将其与序列的第一个元素交换位置，将该元素视为已排序部分；接着，在剩下的未排序部分中找到最小（或最大）的元素，将其与第二个元素交换位置，将该元素视为已排序部分的最后一个元素；以此类推，每次选择序列中最小（或最大）的元素，并将该元素放置在已排序部分的末尾。

最终完成排序。

选择排序的时间复杂度同样为 O(n^2)，其中 n 为待排序序列的长度。

相比于冒泡排序，选择排序的交换操作较少，因此在实际应用中，选择排序的性能要优于冒泡排序。

三、插入排序插入排序是一种简单直观的排序算法，它的基本思想是将待排序的元素逐个插入已排好序的部分中，直到整个序列有序。

与冒泡排序和选择排序不同，插入排序是一种原地排序算法。

数据结构考研真题及其答案完整版

数据结构考研真题及其答案完整版

数据结构考研真题及其答案完整版数据结构是计算机科学与技术领域中的一门重要课程，也是计算机考研中必考的一门科目。

通过研究数据结构，可以帮助我们更好地理解和应用计算机算法，提高计算机程序的效率和性能。

为了帮助考生更好地备考数据结构，本文将分享一些数据结构考研真题及其答案，供考生参考。

一、选择题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) 从根节点到叶子节点的路径上，不同路径上黑节点的个数相同。