数据结构考研题库绪论【圣才出品】

数据结构考研题库绪论【圣才出品】哎呀，一提到数据结构考研题库的绪论，是不是感觉有点头大？别慌，咱们一起来瞅瞅这里面的门道。

我记得有一次，我去参加一个学术交流活动。

当时有个学生问一位资深的教授：“老师，数据结构到底是个啥？感觉好抽象啊！”教授笑了笑，指着旁边的书架说：“你看这书架上的书，有大有小，有薄有厚，我们为了方便找书，会按照一定的规则摆放，比如按照学科分类、按照作者名字的字母顺序等等。

这摆放的规则，就有点像数据结构。

”这就好比咱们的数据结构，它是一种组织和存储数据的方式，让我们能更高效地对数据进行操作和处理。

就像在一个图书馆里，如果书乱七八糟地堆着，找一本书得费老劲了；但有了合理的数据结构，就像给书都安排好了“座位”，找起来轻松多啦。

那咱们再来说说这考研题库里的绪论部分。

它就像是给咱们的一场热身运动，告诉我们数据结构这门课在考研中的地位和重要性。

比如说，它会告诉你，在历年的考研真题中，哪些知识点是经常出现的“常客”，哪些是偶尔露个面的“稀客”。

而且绪论还会给咱们讲讲学习数据结构的方法和技巧。

这就像是给你一把钥匙，告诉你怎么去打开这扇知识的大门。

比如说，要多做练习题，要善于总结归纳，还要学会举一反三。

再比如说，绪论里可能会提到一些常见的数据结构类型，像线性表、栈、队列、树、图等等。

这就像是给你介绍了一群“小伙伴”，让你先混个脸熟，知道它们的特点和脾气。

然后呢，考研题库的绪论还会告诉你，在考试的时候，要注意答题的规范和步骤。

不能想到啥就写啥，得有条有理，让阅卷老师能一眼看明白你的思路。

总之啊，这绪论就像是一个引路人，带着咱们走进数据结构考研的世界。

可别小看了它，认真琢磨琢磨，能让咱们后面的学习和复习少走好多弯路呢！就像开头说的那个书架的例子，只有先了解了规则，才能在知识的海洋里畅游，轻松找到我们想要的“宝藏”。

所以啊，同学们，一定要重视这数据结构考研题库的绪论部分，为我们的考研之路打下坚实的基础！。

第1章绪论一、选择题1. 算法的计算量的大小称为计算的〔〕。

【北京邮电大学2000 二、3 〔20/8分〕】A．效率 B. 复杂性 C. 现实性 D. 难度2. 算法的时间复杂度取决于〔〕【中科院计算所 1998 二、1 〔2分〕】A．问题的规模 B. 待处理数据的初态 C. A和B3.计算机算法指的是〔1〕，它必须具备〔2〕这三个特性。

(1) A．计算方法 B. 排序方法 C. 解决问题的步骤序列 D. 调度方法(2) A．可执行性、可移植性、可扩大性 B. 可执行性、确定性、有穷性C. 确定性、有穷性、稳定性D. 易读性、稳定性、平安性【南京理工大学 1999 一、1〔2分〕【武汉交通科技大学 1996 一、1〔 4分〕】4．一个算法应该是〔〕。

【中山大学 1998 二、1〔2分〕】A．程序 B．问题求解步骤的描绘 C．要满足五个根本特性 D．A和C.5. 下面关于算法说法错误的选项是〔〕【南京理工大学 2000 一、1〔1.5分〕】A．算法最终必须由计算机程序实现B.为解决某问题的算法同为该问题编写的程序含义是一样的C. 算法的可行性是指指令不能有二义性D. 以上几个都是错误的6. 下面说法错误的选项是〔〕【南京理工大学 2000 一、2 〔1.5分〕】(1〕算法原地工作的含义是指不需要任何额外的辅助空间〔2〕在一样的规模n下，复杂度O(n)的算法在时间上总是优于复杂度O(2n)的算法〔3〕所谓时间复杂度是指最坏情况下，估算算法执行时间的一个上界〔4〕同一个算法，实现语言的级别越高，执行效率就越低A．(1) B.(1),(2) C.(1),(4) D.(3)7．从逻辑上可以把数据构造分为〔〕两大类。

【武汉交通科技大学 1996 一、4〔2分〕】A．动态构造、静态构造 B．顺序构造、链式构造C．线性构造、非线性构造 D．初等构造、构造型构造8．以下与数据的存储构造无关的术语是〔〕。

【北方交通大学 2000 二、1〔2分〕】A．循环队列 B. 链表 C. 哈希表 D. 栈9．以下数据构造中，哪一个是线性构造〔〕？【北方交通大学 2001 一、1〔2分〕】A．广义表 B. 二叉树 C. 稀疏矩阵 D. 串10．以下那一个术语与数据的存储构造无关？〔〕【北方交通大学 2001 一、2〔2分〕】A．栈 B. 哈希表 C. 线索树 D. 双向链表11．在下面的程序段中，对x的赋值语句的频度为〔〕【北京工商大学 2001 一、10〔3分〕】FOR i:=1 TO n DOFOR j:=1 TO n DOx:=x+1;A． O(2n) B．O(n) C．O(n2) D．O(log2n)12．程序段 FOR i:=n-1 DOWNTO 1 DOFOR j:=1 TO i DOIF A[j]>A[j+1]THEN A[j]与A[j+1]对换；其中 n为正整数，那么最后一行的语句频度在最坏情况下是〔〕A. O〔n〕B. O(nlogn)C. O(n3)D. O(n2) 【南京理工大学1998一、1(2分)】13．以下哪个数据构造不是多型数据类型〔〕【中山大学 1999 一、3〔1分〕】A．栈 B．广义表 C．有向图 D．字符串14．以下数据构造中，〔〕是非线性数据构造【中山大学 1999 一、4】A．树 B．字符串 C．队 D．栈15. 以下数据中，〔〕是非线性数据构造。

第1章绪论1.1 知识要点总结一、数据结构的基本概念1．基础概念和术语（1）数据（Data）：数据是客观事物的符号表示。

在计算机科学中指的是所有能输入到计算机中并被计算机程序处理的符号的总称。

（2）数据元素（Data Element）：数据元素是数据的基本单位，在程序中通常作为一个整体来进行考虑和处理。

（3）数据项（Data Item）：数据项是数据的不可分割的最小单位，数据项是对客观事物的某一方面的数据描述。

一个数据元素可由若干个数据项（Data Item）组成。

（4）数据对象（Data Object）：数据对象是性质相同的数据元素的集合，是数据的一个子集。

如字符集合C={‘A’,’B’,’C’ ,…}（5）数据结构（Data Structure）：数据结构是指相互之间存在一定联系（关系）的数据元素的集合。

元素之间的相互联系（关系）称为逻辑结构。

2．数据结构的形式定义数据结构的形式定义是一个二元组：Data Structure=（D, S）其中D是数据元素的有限集，S是D上关系的有限集。

数据元素之间的关系可以是元素之间本身代表的某种自然关系，也可以是为了处理问题方便而人为定义的关系，这种自然或人为定义的关系称为数据元素之间的逻辑关系，相应的结构称为逻辑结构。

3．数据结构的组成数据结构的三个组成部分：（1）逻辑结构数据元素之间的逻辑关系的描述。

数据元素之间的逻辑结构有四种基本类型：①集合：结构中的数据除了“同属于一个集合”外，没有其它关系。

②线性结构：结构中的数据元素之间存在一对一的关系。

③树形结构：结构中的数据元素之间存在一对多的关系。

④图形结构或网状结构：结构中的数据元素之间存在多对多的关系。

（2）存储结构数据结构在计算机中的实际表达方式，它包括对数据元素的表示和对关系的表示。

存储结构主要有：顺序存储、链式存储、索引存储和散列存储。

①顺序存储结构：用数据元素在存储器中的相对位置来表示数据元素之间的逻辑结构。

5.2 典型题（含历年真题）详解一、单项选择题1．设有向图G＝（V，E），顶点集V＝{V0，V1，V2，V3}，边集E＝{<V0，V1>，<V0，V2>，<V0，V3>，<V1，V3>}，若从顶点V0开始对图进行深度优先遍历，则可能得到的不同遍历序列个数是（）。

[2015年联考真题]A．2B．3C．4D．5【答案】D【解析】根据题意知有向图的结构如图所示。

深度优先遍历的特点是尽可能先对纵深方向进行搜索，所以可能得到的不同遍历序列分别是：①V0→V2→V1→V3；②V0→V2→V3→V1；③V0→V1→V3→V2；④V0→V3→V2→V1；⑤V0→V3→V1→V2。

2．对如下所示的有向图进行拓扑排序，得到的拓扑序列可能是（）。

[2014年联考真题] A．3，1，2，4，5，6B．3，1，2，4，6，5C．3，1，4，2，5，6D．3，1，4，2，6，5【答案】D【解析】拓扑排序方法如下：（1）从有向图中选择一个没有前驱（即入度为0）的顶点并且输出它；（2）从图中删去该顶点，并且删去从该顶点发出的全部有向边；（3）重复上述两步，直到剩余的网中不再存在没有前趋的顶点为止。

对于此有向图进行拓扑排序所有序列为：3，1，4，6，2，5和3，1，4，2，6，5。

所以选D3．设图的邻接矩阵A如下所示，各顶点的度依次是（）。

[2013年联考真题]A．1，2，1，2B．2，2，1，1C．3，4，2，3D．4，4，2，2【答案】C【解析】当图用邻接矩阵存储时，各顶点的度是矩阵中此结点对应的横行和纵列非零元素之和。

4．下列AOE网表示一项包含8个活动的工程。

通过同时加快若干进度可以缩短整个工程的工期。

下列选项中，加快其进度就可以缩短工程工期的是（）。

[2013年联考真题]A．c和eB．d和eC．f和dD．f和h【答案】C【解析】根据AOE网的定义可知，同时缩短几条关键路径上的活动时间，可以缩短整个工期。

第6章数组和广义表一、选择题1．设有一个10阶的对称矩阵A，采用压缩存储方式，以行序为主存储，a11为第一元素，其存储地址为1，每个元素占一个地址空间，则a85的地址为（）。

A．13B．33C．18D．40【答案】B【解析】对于对称矩阵,a i,j=a j,i。

为了节省存储空间，为多个相同的元素只分配一个存储空间。

对于对称矩阵，元素下表之间的对应关系为：当i>=j时，k=i(i-1)/2+j -1；当i< =j 时，k=j(j-1)/2+i-1。

其中k相当于地址空间的标号，i为行号，j为列号。

因为第一个元素存储地址为1，所以最后计算的k需要加1。

所以a85的存储位置为8*（8-1）/2+5=33。

2．设有数组A[i，j]，数组的每个元素长度为3字节，i的值为1到8，j的值为1到10，数组从内存首地址BA开始顺序存放，当用以列为主存放时，元素A[5，8]的存储首地址为（）。

A．BA+141B．BA+180C．BA+222D．BA+225【答案】B【解析】在计算中，可以考虑按照列存放时，A[5,8]在内存的位置，比较容易计算元素的首地址。

比如A[5，8]顺序存放时，它是第7*8+5=61个元素，由于首地址为BA，所以它的存储首地址为BA+（61-1）*3=180+BA。

3．数组通常具有的两种基本操作是（）。

A．查找和修改B．查找和索引C．索引和修改D．建立和删除【答案】A【解析】数组中的元素是顺序存放的，通过下标可以很好地查找数组元素，同时通过对应的指针可以修改数组元素的值，因此数组通常具有的两种基本操作是查找和修改。

根据数组的性质，数组通常具有的两种基本运算是排序和查找。

4．将一个A[1．.100，1．.100]的三对角矩阵，按行优先存入一维数组B[1．.298]中，A中元素A6665（即该元素下标i=66，j=65），在B数组中的位置K为（）。

A．198B．195C．197【答案】B【解析】将对角矩阵a[i][j]存入b[k]，三对角矩阵压缩地址计算公式如下：k=2i+j-2。

第二部分课后习题第1章绪论1．简述数据与数据元素的关系与区别。

答：凡是能被计算机存储、加工的对象统称为数据，数据是一个集合。

数据元素是数据的基本单位，是数据的个体。

数据与元素之间的关系是元素与集合之间的关系。

2．数据结构和数据类型有什么区别？答：数据结构是互相之间存在一种或多种特定关系的数据元素的集合，一般包括三个方面的内容，即数据的逻辑结构、存储结构和数据的运算。

而数据类型是一个值的集合和定义在这个集合上的一组运算的总称，如C语言中的int数据类型是由-32768~32767（16位机）的整数和+、-、*、/、%等运算符组成。

3．设3个表示算法频度的函数f、g和h分别为：f（n）=100n3+n2+1000g（n）=25n3+5000n2h（n）=n1.5+5000nlog2n求它们对应的时间复杂度。

答：f（n）=100n3+n2+1000=O（n3），g（n）=25n3+5000n2=O（n3），当n→∞时，√n>log2n，所以h（n）=n1.5+5000nlog2n=O（n1.5）。

4．用C／C++语言描述下列算法，并给出算法的时间复杂度。

（1）求一个n阶方阵的所有元素之和。

（2）对于输入的任意三个整数，将它们按从小到大的顺序输出。

（3）对于输入的任意n个整数，输出其中的最大和最小元素。

答：（1）算法如下：本算法的时间复杂度为O（n2）。

（2）算法如下：本算法的时间复杂度为O（1）。

（3）算法如下：本算法的时间复杂度为O（n）。

5．设n为正整数，给出下列各种算法关于n的时间复杂度。

（1）（2）（3）答：（1）设while循环语句执行次数为T（n），则：（2）算法中的基本运算语句是if（b[k]>b[j]）k=j，其执行次数T（n）为：（3）设while循环语句执行次数为T（n），则：则6．有以下递归算法用于对数组a[i．．j]的元素进行归并排序：求mergesort（a，0，n－1）的时间复杂度。

数据结构考研题库绪论【圣才出品】在计算机科学领域，数据结构是一门极其重要的基础课程，也是考研中的重点内容之一。

对于准备考研的同学来说，深入理解和掌握数据结构的相关知识，熟练解答各类题目，是取得优异成绩的关键。

数据结构研究的是数据的组织、存储和操作方式。

它不仅仅是一些理论概念，更是解决实际问题的有力工具。

通过合理选择和运用数据结构，可以提高程序的效率、降低存储空间的消耗，使计算机系统能够更高效地处理和管理数据。

在考研题库中，关于数据结构绪论部分的题目，通常涵盖了数据结构的基本概念、发展历程、研究内容以及其在计算机科学中的重要地位等方面。

首先，我们来谈谈数据结构的基本概念。

简单来说，数据结构就是数据元素之间的关系。

这些数据元素可以是数字、字符、图像、音频等各种信息。

而数据结构则规定了这些元素如何组织在一起，以及如何对它们进行操作。

数据结构的发展历程也是一个值得关注的点。

从早期的简单线性表、栈和队列，到后来的树、图等复杂结构，数据结构不断演进和完善，以适应日益复杂的计算机应用需求。

这种发展反映了计算机技术的不断进步和人们对更高效数据处理方式的追求。

数据结构的研究内容非常丰富。

它包括数据的逻辑结构、存储结构以及相应的操作算法。

逻辑结构指的是数据元素之间的逻辑关系，如线性结构、非线性结构等；存储结构则是数据在计算机中的存储方式，如顺序存储、链式存储等。

而操作算法则是针对不同的数据结构，设计的一系列操作方法，如插入、删除、查找、排序等。

数据结构在计算机科学中的地位举足轻重。

它是操作系统、数据库、编译原理等众多核心课程的基础。

一个优秀的程序员或计算机专业的学生，必须具备扎实的数据结构知识，才能写出高效、可靠的程序。

在考研的题目中，可能会要求考生分析不同数据结构的特点和适用场景。

比如，对于需要频繁进行插入和删除操作的数据集合，链表可能是一个更合适的选择；而对于需要快速随机访问的数据，数组则可能更具优势。

也可能会考查考生对数据结构基本概念的理解。

名校考研真题一、选择题1．已知程序如下：程序运行时使用栈来保存调用过程的信息，自栈底到栈顶保存的信息依次对应的是（）。

[2015年联考真题]A．main（）->S（1）->S（0）B．S（0）->S（1）->main（）C．main（）->S（0）->S（1）D．S（1）->S（0）->main（）【答案】A【解析】函数S（int n）是一个递归函数：①当实际参数小于等于零时则返回0，并终止递归；②当实际参数大于零时则递归调用S（n-1），并将S（n-1）的结果加上n作为返回值。

程序从main（）函数开始，首先调用main（）函数；在main（）函数中调用S（1）函数时，将main（）函数的上下文保存到栈中，并进入函数S（1）；由于函数S（1）的实际参数大于零，需要调用S（0），故将S（1）函数的上下文保存到栈中，进入S（0）；在S （0）中，实际参数小于等于零，递归终止。

2．算法分析的目的是（）。

[北京理工大学考研真题]A．找出数据结构的合理性B．研究算法中的输入和输出的关系C．分析算法的效率以求改进D．分析算法的易懂性和文档性【答案】C【解析】分析算法为的就是能对算法有更多、更好的改进。

3．先序序列为a，b，c，d的不同二叉树的个数是（）。

[2015年联考真题]A．13B．14C．15D．16【答案】B【解析】二叉树的先序遍历定义为：若二叉树为空，则空操作；否则，访问根节点，然后先序遍历左子树，最后先序遍历右子树。

本题中，结点a为二叉树的根节点，左右子树的先序遍历可能存在下面四种情况：①左子树为空，bcd为右子树；②b为左子树，cd为右子树；③bc为左子树，d为右子树；④bcd为左子树，右子树为空。

然后将左右子树继续分解，如第①种情况的右子树先序遍历（bcd）可能有：a．左子树为空，右子树为cd；b．左子树为c，右子树为d；c．左子树为cd，右子树为空。