2016年考研核心题型【数据结构部分】【第1章 算法的时间复杂度和空间复杂度】

第1章单元测试1、算法的时间复杂度取决于___。

答案：A和B2、数据在计算机内存中的表示是指（）答案：数据的存储结构3、算法指的是（）答案：求解特定问题的指令有限序列4、在数据结构中，与所使用的计算机无关的数据结构是（）答案：逻辑7、某线性表采用顺序存储结构,每个元素占4个存储单元,首地址为100,则第12个元素的存储地址为( )。

答案：1448、算法能正确地实现预定功能的特性称为算法的（）。

答案：正确性第2章单元测试1、链表不具备的特点是（）。

答案：可随机访问任意一个结点3、线性表的顺序存储表示优于链式存储表示。

答案：错4、顺序存储结构的缺点是不便于修改,插入和删除需要移动很多结点。

答案：对5、在设头、尾指针的单链表中,与长度n有关的操作是( )。

答案：删除最后一个结点6、设指针q指向单链表中结点A,指针p指向单链表中结点A的后继结点B,指针s指向被插入的结点X,则在结点A和结点B间插入结点X的操作序列为( )。

答案：q->next=s; s->next=p;7、对于只在表的首、尾两端进行插入操作的线性表,宜采用的存储结构为( )。

答案：用尾指针表示的循环单链表8、在一个单链表中,若p所指节点不是最后节点,在p之后插入s所指节点,则执行( )。

答案：s->link=p->link;p->link=s;9、在双向链表存储结构中，删除p所指的结点时须修改指针____。

答案：p->next->prior=p->prior; p->prior->next=p->next;10、若事先不知道线性表的长度,则处理线性表时较好的存储结构是( )。

答案：单链表11、向一个有127个元素的顺序表中插入一个新元素并保存,原来顺序不变,平均要移动( )个元素。

答案：63.512、某线性表采用顺序存储结构,每个元素占4个存储单元,首地址为100,则第12个元素的存储地址为( )。

数据结构时间复杂度总结在计算机程序设计中，数据结构是一种用来组织和存储数据的方式，它可以使数据的访问、插入、删除等操作更加高效。

而在进行数据结构的设计和实现时，时间复杂度是一个非常重要的指标，它可以衡量程序的性能和效率。

因此，本文将对常见的数据结构进行时间复杂度总结。

一、数组数组是一种最基本的数据结构，它可以存储相同类型的数据，并且可以通过下标来访问数组中的元素。

在数组中，访问元素的时间复杂度为O(1)，插入和删除的时间复杂度为O(n)。

二、链表链表是一种线性的数据结构，它由多个节点组成，每个节点包含一个数据元素和一个指向下一个节点的指针。

在链表中，访问元素的时间复杂度为O(n)，插入和删除的时间复杂度为O(1)。

三、栈栈是一种数据结构，它可以存储相同类型的数据，并且只能在栈顶进行插入和删除操作。

在栈中，访问栈顶元素的时间复杂度为O(1)，插入和删除的时间复杂度也为O(1)。

四、队列队列是一种线性的数据结构，它可以存储相同类型的数据，并且只能在队尾进行插入操作，在队首进行删除操作。

在队列中，访问队首元素的时间复杂度为O(1)，插入和删除的时间复杂度也为O(1)。

五、堆堆是一种特殊的树形数据结构，它可以快速找到最大或最小元素，并且可以在O(log n)的时间复杂度内插入和删除元素。

六、哈希表哈希表是一种使用哈希函数将键映射到值的数据结构，它可以在O(1)的时间复杂度内进行插入、删除和查找操作。

七、树树是一种类似于链表的数据结构，它由多个节点组成，每个节点包含一个数据元素和多个指向子节点的指针。

在树中，访问节点的时间复杂度为O(n)，插入和删除的时间复杂度为O(log n)。

综上所述，不同的数据结构在访问、插入和删除操作上都有不同的时间复杂度，我们在进行程序设计时需要根据实际情况选择合适的数据结构以及相应的算法，以达到最优的程序性能和效率。

数据结构时间复杂度的计算数据结构的时间复杂度是衡量算法性能的重要指标，它描述了算法执行所需的时间随输入规模增长而变化的规律。

在计算时间复杂度时，我们通常关注最坏情况下算法的执行时间。

以下是常见数据结构的时间复杂度计算方法及其分析：1. 数组（Array）：-访问指定位置的元素：O(1)-查找指定元素：O(n)-插入或删除元素：O(n)数组的访问和插入/删除元素的时间复杂度取决于元素的位置。

如果位置已知，访问和插入/删除元素的时间复杂度为常数；但如果需要查找元素的位置，时间复杂度为线性。

2. 链表（Linked List）：-插入或删除头节点：O(1)-插入或删除尾节点：O(n)-查找指定元素：O(n)链表的插入/删除头节点和访问指定元素的时间复杂度为常数，而插入/删除尾节点的时间复杂度为线性。

3. 栈（Stack）：-入栈：O(1)-出栈：O(1)-查看栈顶元素：O(1)栈的操作都是在栈顶进行，因此时间复杂度都为常数。

4. 队列（Queue）：-入队：O(1)-出队：O(1)-查看队首元素：O(1)队列操作也都是在固定的位置进行，所以时间复杂度为常数。

5. 哈希表（Hash Table）：-插入或删除元素：O(1)-查找指定元素：O(1)（平均情况），O(n)（最坏情况）哈希表的插入/删除操作的平均时间复杂度为常数，但在最坏情况下，哈希冲突可能导致查找元素的时间复杂度变为线性。

6. 二叉树（Binary Tree）：- 查找指定元素：O(log n)（平均情况），O(n)（最坏情况）- 插入或删除节点：O(log n)（平均情况），O(n)（最坏情况）二叉树的查找、插入和删除涉及到对树的遍历，所以时间复杂度与树的深度相关。

在平衡二叉树中，树的深度是对数级的；但在非平衡二叉树中，最坏情况下时间复杂度可能退化为线性。

7. 堆（Heap）：- 插入元素：O(log n)- 删除堆顶元素：O(log n)-查找堆中最大/最小元素：O(1)堆的插入和删除操作需要对堆进行调整以保持其性质，时间复杂度与堆的高度有关，因此为对数级。

《数据结构》习题第一章绪论一、单选或填空题1. 下列程序段中S语句的执行频度为。

for(i＝0；i＜n；i++ ）for(j＝0；j＜i；j++ ）S；2. 下列算法的时间复杂度是（）。

for(i＝0；i＜n；i++ ）c[i]＝i；3. 算法的时间复杂度可表示为O(1)、线性阶、平方阶O(n2)、对数阶O(logn)和指数阶O(2n)等。

4 以下关于数据结构的基本概念中，叙述正确的是A) 数据元素是数据不可分割的最小单位。

B) 数据是数据对象的子集。

C) 数据元素之间的关系在计算机中可用顺序映像和非顺序映像两种不同的方法表示。

D) 数据结构在计算机中的表示又称为逻辑结构。

5. 在数据结构中，数据的逻辑结构包括（）。

A) 线性结构和非线性结构B) 逻辑结构和物理结构C) 顺序结构和链式结构D) 虚拟结构和抽象结构6. 在数据结构中，数据的存储结构包括。

A) 线性结构和非线性结构B)逻辑结构和物理结构C) 顺序结构和链式结构D) 虚拟结构和抽象结构第二章线性表1.线性结构的数据元素之间存在一种( )。

A．一对多关系B．多对多关系C．多对一关系D．一对一关系2. 在长度为n的顺序表中插入一个元素，需要平均移动个元素。

A) n/2 B)nC) n(n-1) D) n(n+1)3. 在有n个元素的顺序表中做插入、删除运算，平均时间复杂度为。

4. 顺序表中逻辑上相邻的元素物理位置相邻，单链表中逻辑上相邻的元素的物理位置相邻。

A)必然、必然B)必然、不一定C)不一定、必然D)不一定、不一定5．相对于顺序存储而言，链式存储的优点是（）。

A．随机存取B．节约空间C．增、删操作方便D．节点间关系简单6. 以下关于头结点的描述中，叙述错误．．的是A) 头结点是对链表首元结点的别称B) 若链表中附设头结点，则头指针一定不为空C) 头结点中不存储链表的数据元素，而是一些诸如表长之类的辅助信息D) 在单链表中附设头结点，插入或删除首元素时不必进行特殊处理7．已知L是无表头结点的单链表，且P所指结点既不是首元结点，也不是尾元结点，则在P之后插入S所指结点，则执行（）。

第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). 算法采⽤的策略、⽅法；(2). 编译产⽣的代码质量；(3). 问题的输⼊规模；(4). 机器执⾏指令的速度。

⼀个算法是由控制结构（顺序、分⽀和循环3种）和原操作（指固有数据类型的操作）构成的，则算法时间取决于两者的综合效果。

为了便于⽐较同⼀个问题的不同算法，通常的做法是，从算法中选取⼀种对于所研究的问题（或算法类型）来说是基本操作的原操作，以该基本操作的重复执⾏的次数作为算法的时间量度。

1、时间复杂度（1）时间频度⼀个算法执⾏所耗费的时间，从理论上是不能算出来的，必须上机运⾏测试才能知道。

但我们不可能也没有必要对每个算法都上机测试，只需知道哪个算法花费的时间多，哪个算法花费的时间少就可以了。

数据结构时间复杂度总汇数据结构时间复杂度总汇一、线性结构1.数组（Array）- 查找：O(1)- 插入：O(n)- 删除：O(n)2.链表（Linked List）- 查找：O(n)- 插入：O(1)- 删除：O(1)3.栈（Stack）- 查找：O(n)- 插入：O(1)- 删除：O(1)4.队列（Queue）- 查找：O(n)- 插入：O(1)- 删除：O(1)二、树形结构1.二叉树（Binary Tree）- 查找：O(log n) - O(n)- 插入：O(log n) - O(n)- 删除：O(log n) - O(n)2.二叉搜索树（Binary Search Tree）- 查找：O(log n) - O(n)- 插入：O(log n) - O(n)- 删除：O(log n) - O(n)3.平衡二叉树（Balanced Binary Tree）- AVL树：查找、插入、删除均为 O(log n) - 红黑树：查找、插入、删除均为 O(log n) 4.堆（Heap）- 查找：O(n)- 插入：O(log n)- 删除：O(log n)三、散列表（Hash Table）- 查找：平均 O(1)，最坏 O(n)- 插入：平均 O(1)，最坏 O(n)- 删除：平均 O(1)，最坏 O(n)四、图（Graph）- 邻接矩阵：查找、插入、删除均为 O(1)- 邻接表：查找 O(log n) - O(n)，插入 O(1)，删除O(log n) - O(n)附件：本文档未涉及附件。

法律名词及注释：1.时间复杂度（Time Complexity）：描述算法在解决问题时所需的计算时间。

2.数组（Array）：由相同数据类型的元素按照一定顺序排列而成的数据结构。

3.链表（Linked List）：由一系列节点（Node）组成的数据结构，每个节点包含数据和指向下一个节点的指针。

4.栈（Stack）：一种特殊的线性表，只能在表尾进行插入和删除操作的数据结构。

数据结构与算法（⼀）时间复杂度、空间复杂度计算⼀、时间复杂度计算1、时间复杂度的意义复杂度分析是整个算法学习的精髓，只要掌握了它，数据结构和算法的内容基本上就掌握了⼀半1. 测试结果⾮常依赖测试环境2. 测试结果受数据规模的影响很⼤所以，我们需要⼀个不⽤具体的测试数据来测试，就可以粗略地估计算法的执⾏效率的⽅法，即时间、空间复杂度分析⽅法。

2、⼤ O 复杂度表⽰法1)、可以将计算时间复杂度的⽅式和计算代码执⾏次数来进⾏类别int cal(int n) {int sum = 0;int i = 1;for (; i <= n; ++i) {sum = sum + i;}return sum;}第 2、3 ⾏代码分别需要 1 个 unit_time 的执⾏时间，第 4、5 ⾏都运⾏了 n 遍，所以需要 2n * unit_time 的执⾏时间，所以这段代码总的执⾏时间就是(2n+2) * unit_time。

可以看出来，所有代码的执⾏时间 T(n) 与每⾏代码的执⾏次数成正⽐。

2)、复杂⼀点的计算int cal(int n) { ----1int sum = 0; ----2int i = 1; ----3int j = 1; ----4for (; i <= n; ++i) { ----5j = 1; ----6for (; j <= n; ++j) { ----7sum = sum + i * j; ----8} ----9} ----10} ----11T(n) = (2n^2+2n+3)unit_timeT(n)=O(f(n))⼤ O 时间复杂度实际上并不具体表⽰代码真正的执⾏时间，⽽是表⽰代码执⾏时间随数据规模增长的变化趋势，所以，也叫作渐进时间复杂度（asymptotic time complexity），简称时间复杂度2、时间复杂度计算法则1. 只关注循环执⾏次数最多的⼀段代码2. 加法法则：总复杂度等于量级最⼤的那段代码的复杂度如果 T1(n)=O(f(n))，T2(n)=O(g(n))；那么 T(n)=T1(n)+T2(n)=max(O(f(n)), O(g(n))) =O(max(f(n), g(n))).3. 乘法法则：嵌套代码的复杂度等于嵌套内外代码复杂度的乘积T(n) = T1(n) * T2(n) = O(n*n) = O(n2)3、常见的是时间复杂度复杂度量级（递增）排列公式常量阶O(1)对数阶O(logn)线性阶O(n)线性对数阶O(nlogn)平⽅阶、⽴⽅阶...K次⽅阶O(n2),O(n3),O(n^k)指数阶O(2^n)阶乘阶O(n!)①. O(1)：代码的执⾏时间和n没有关系，⼀般情况下，只要算法中不存在循环语句、递归语句，即使有成千上万⾏的代码，其时间复杂度也是Ο(1)；②. O(logn)、O(nlogn)i=1;while (i <= n) {i = i * 2;}通过 2x=n 求解 x 这个问题我们想⾼中应该就学过了，我就不多说了。

习题练习第一章1. 算法的计算量的大小称为计算的（）。

A．效率 B. 复杂性 C. 现实性 D. 难度2. 算法的时间复杂度取决于（）A．问题的规模 B. 待处理数据的初态 C. A和B3.计算机算法指的是（1），它必须具备（2）这三个特性。

(1) A．计算方法 B. 排序方法 C. 解决问题的步骤序列 D. 调度方法(2) A．可执行性、可移植性、可扩充性 B. 可执行性、确定性、有穷性C. 确定性、有穷性、稳定性D. 易读性、稳定性、安全性4．一个算法应该是（）。

A．程序 B．问题求解步骤的描述 C．要满足五个基本特性 D．A和C.5、下面属于逻辑结构的是（）A 顺序表B哈希表 C 有序表D 单链表6、某算法的时间复杂度为O(n2)，表明该算法的（）A 问题规模是n2 B执行时间等于n2C 执行时间与n2成正比D问题规模与n2成正比7、下面关于算法说法错误的是（）A．算法最终必须由计算机程序实现B.为解决某问题的算法同为该问题编写的程序含义是相同的C. 算法的可行性是指指令不能有二义性D. 以上几个都是错误的8．从逻辑上可以把数据结构分为（）两大类。

A．动态结构、静态结构 B．顺序结构、链式结构C．线性结构、非线性结构 D．初等结构、构造型结构9．以下与数据的存储结构无关的术语是（）。

A．循环队列 B. 链表 C. 哈希表 D. 栈10．以下数据结构中，哪一个是线性结构（）？A．广义表 B. 二叉树 C. 稀疏矩阵 D. 串11．以下那一个术语与数据的存储结构无关？（）A．栈 B. 哈希表 C. 线索树 D. 双向链表12．在下面的程序段中，对x的赋值语句的频度为（）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)14．以下数据结构中，（）是非线性数据结构A．树 B．字符串 C．队 D．栈15. 下列数据中，（）是非线性数据结构。

《数据结构》考研真题及解答目录2009 年试题 (1)填空题 (1)解答题 (2)2010 年试题 (2)填空题 (2)解答题 (4)2011 年试题 (4)填空题 (4)解答题 (5)2012 年试题 (6)填空题 (6)解答题 (7)2013 年试题 (8)填空题 (8)解答题 (9)2014 年试题 (10)填空题 (10)解答题 (11)2015 年试题 (12)填空题 (12)解答题 (14)2009 年试题填空题1.为解决计算机与打印机之间速度不匹配的问题，通常设置一个打印数据缓冲区，主机将要输出的数据依次写入该缓冲区，而打印机则依次从该缓冲区中取出数据。

该缓冲区的逻辑结构应该是A.栈B.队列C.树D.图2.设栈 S 和队列 Q 的初始状态均为空，元素 abcdefg 依次进入栈 S。

若每个元素出栈后立即进入队列 Q，且7 个元素出队的顺序是 bdcfeag，则栈 S 的容量至少是A．1 B.2 C.3 D.43.给定二叉树图所示。

设 N 代表二叉树的根，L代表根结点的左子树，R代表根结点的右子树。

若遍历后的结点序列为 3，1，7，5，6，2，4，则其遍历方式是A．LRN B.NRL C.RLN D.RNL4.下列二叉排序树中，满足平衡二叉树定义的是5.已知一棵完全二叉树的第 6 层（设根为第 1 层）有8 个叶结点，则完全二叉树的结点个数最多是A．39 B.52 C.111 D.1196.将森林转换为对应的二叉树，若在二叉树中，结点u 是结点v 的父结点的父结点，则在原来的森林中，u 和v 可能具有的关系是I．父子关系II.兄弟关系III.u 的父结点与v 的父结点是兄弟关系A.只有IIB.I 和IIC.I 和IIID.I、II 和III7.下列关于无向连通图特性的叙述中，正确的是I．所有顶点的度之和为偶数II.边数大于顶点个数减1 III.至少有一个顶点的度为1A.只有IB.只有IIC.I 和IID.I 和III8.下列叙述中，不符合 m 阶B 树定义要求的是A．根节点最多有m 棵子树 B.所有叶结点都在同一层上C．各结点内关键字均升序或降序排列 D.叶结点之间通过指针链接9.已知关键序列 5，8，12，19，28，20，15，22 是小根堆（最小堆），插入关键字 3，调整后得到的小根堆是A．3，5，12，8，28，20，15，22，19B.3，5，12，19，20，15，22，8，28C．3，8，12，5，20，15，22，28，19D.3，12，5，8，28，20，15，22，1910.若数据元素序列 11，12，13，7，8，9，23，4，5 是采用下列排序方法之一得到的第二趟排序后的结果，则该排序算法只能是A．起泡排序 B.插入排序 C.选择排序 D.二路归并排序解答题41.（10 分）带权图（权值非负，表示边连接的两顶点间的距离）的最短路径问题是找出从初始顶点到目标顶点之间的一条最短路径。

第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. 下列数据中，（）是非线性数据结构。

【数据结构】时间复杂度和空间复杂度计算时间复杂度AND空间复杂度专项时间维度：是指执⾏当前算法所消耗的时间，我们通常⽤「时间复杂度」来描述。

空间维度：是指执⾏当前算法需要占⽤多少内存空间，我们通常⽤「空间复杂度」来描述。

时间复杂度⼀个算法花费的时间与算法中语句的执⾏次数成正⽐例，哪个算法中语句执⾏次数多，它花费时间就多。

⼀个算法中的语句执⾏次数称为语句频度或时间频度。

记为 T(n)。

常见的算法时间复杂度由⼩到⼤依次为：Ο(1)＜Ο(log2n)＜Ο(n)＜Ο(nlog2n)＜Ο(n2)＜Ο(n3)＜Ο(nk)＜Ο(2n) ，随着问题规模 n 的不断增⼤，上述时间复杂度不断增⼤，算法的执⾏效率越低常见的时间复杂度：常见的时间复杂度：常数阶 O(1)对数阶 O(log2n)线性阶 O(n)线性对数阶 O(nlog2n)平⽅阶 O(n^2)⽴⽅阶 O(n^3)k 次⽅阶 O(n^k)指数阶 O(2^n)常见阶数串讲常数阶 O（1）没有循环结构，代码上万⾏都可以，消耗并不伴随某个的增长⽽增长，都是O（1）对数阶O（log2n）举个例⼦int n=1000;int i=1;while(i<=n){i=i*2;}cout<<"啦啦啦啦i="<<i<<endl;看在while循环中执⾏了多少次：while终⽌条件是i>n的时候，即当2的x次⽅等于n时结束循环，那么显然x=log2n。

也就是说while循环执⾏了log2n次后就结束了，那么这个算法的时间复杂度就是log2n。

从这个例⼦可以看出，如果将循环改成i=i*3;那么复杂度⾃然就变成了log3n。

线性阶O（n）现在你已经基本⼊门啦，我们直接上例⼦，线性阶很好理解，就是在循环中变量增长从倍数变成了单个增长。

int n=1000;int i=1;while(i<=n){i++;}cout<<"啦啦啦啦i="<<i<<endl;显然i需要增加n次才可以执⾏结束，故时间复杂度为O（n）线性对数阶O（nlogN）套娃！外层循环执⾏n次，内部循环需要执⾏logN次，那么⼀共就是n*logN啦，故时间复杂度为O（nlogN）。

第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. 下列数据中，（）是非线性数据结构。

2016年山东青岛大学数据结构考研真题一、单项选择题（本大题共10道小题，每小题2分，共20分）1．一个算法具有（）等特点。

A．快速性B．至少有一个输入量C．确定性D．健壮性2．下列函数中渐近时间复杂度T(n)最小的是（）。

A．T(n)=B．T(n)=C．T(n)=D．T(n)=3．在计算机的存储器中表示时，物理地址和逻辑地址相同并且是连续的，称之为（）。

A．逻辑结构B．顺序存储结构C．链式存储结构D．以上都对4．若让元素1，2，3，4，5依次进栈，则出栈次序不可能出现在（）种情况。

A．5，4，3，2，1B．2，1，5，4，3C．4，3，1，2，5D．2，3，5，4，15．设栈S用顺序存储结构表示，则栈S为空的条件是（）。

A．S.top-S.base!=0B．S.top-S.base==0C．S.top-S.base!=nD．S.top-S.base==n6．一棵完全二叉树上有1001个结点，其中叶子结点的个数是（）。

A．500B．501C．250D．2517．任何一棵二叉树的叶子结点在先序、中序和后序遍历中的相对次序（）。

A．不发生改变B．发生改变C．不能确定D．以上都不对8．用邻接表表示图进行广度优先遍历时，通常借助（）来实现算法。

A．栈B.队列C.树D．图9．折半查找法和二叉排序树的时间性能（）。

A．与处理数据量有关B．相同C．不相同D．不确定10．对n个不同的关键字由小到大进行冒泡排序，在下列（）情况下比较的次数最多。

A．从小到大排列好的B．从大到小排列好的C．元素无序D．元素基本有序二、简答题（本大题共6道小题，每题5分，共30分）1．一般情况下，线性表可以采用哪几种存储结构？请分别叙述每一种存储结构的构造原理与特点。

2．内存中一片连续空间（不妨假设地址从0到m-1）提供给两个栈S1与S2使用，怎样分配这部分存储空间，使得对任一个栈仅当这部分空间全满时才发生上溢。

3．简述遍历二叉树的含义及常见的方法。

考研数据结构测试题及答案### 考研数据结构测试题及答案#### 一、选择题1. 在数据结构中，以下哪种结构不是线性结构？A. 栈B. 队列C. 树D. 图答案：C2. 一个长度为n的有序数组，使用二分查找算法查找一个元素，最多需要比较几次？A. nB. log₂nC. n/2D. nlog₂n答案：B3. 以下哪个是链表的优点？A. 随机访问B. 插入和删除不需要移动元素C. 存储空间利用率高D. 所有都是答案：B#### 二、简答题1. 简述堆栈（Stack）的基本操作，并说明它们的特点。

答案：堆栈的基本操作包括：- Push：向栈顶添加一个元素。

- Pop：移除栈顶的元素，并返回该元素。

- Peek/Top：查看栈顶元素，但不移除它。

- IsEmpty：判断栈是否为空。

特点：- 遵循后进先出（LIFO）原则。

- 插入和删除操作都在栈顶进行，时间复杂度为O(1)。

2. 描述二叉搜索树（BST）的插入操作。

答案：二叉搜索树的插入操作如下：1. 从根节点开始，如果待插入节点的值小于当前节点的值，则移动到左子树。

2. 如果待插入节点的值大于当前节点的值，则移动到右子树。

3. 重复步骤1和2，直到找到一个空位置，将新节点插入。

4. 如果新节点的值等于当前节点的值，根据具体实现，可以选择不插入或覆盖现有节点。

#### 三、编程题1. 编写一个函数，实现单链表的反转。

```cstruct ListNode {int val;struct ListNode *next;};void reverseList(struct ListNode head) {struct ListNode *prev = NULL, *curr = *head, *next = NULL;while (curr != NULL) {next = curr->next;curr->next = prev;prev = curr;curr = next;}*head = prev;}```2. 给定一个整数数组，编写一个函数，找出数组中最长的连续子数组的长度。

计算机科学考研必备数据结构与算法题型解析数据结构和算法是计算机科学考研的重要内容，掌握好这些知识对于提高考试成绩至关重要。

本文将对计算机科学考研必备的数据结构和算法题型进行解析，帮助考生更好地理解和应对考试中的这些题目。

一、线性表线性表是最基本的数据结构之一，常见的线性表包括数组、链表和栈等。

考研中常出现与线性表相关的题目，要求考生熟练掌握线性表的基本操作和应用。

1. 数组数组是一种连续存储数据的线性表，具有随机访问的特性。

考研中可能出现与数组相关的题目，如数组的逆序、元素的插入和删除等操作。

2. 链表链表是一种动态存储数据的线性表，通过节点之间的指针链接起来。

考研中可能出现与链表相关的题目，如链表的逆序、节点的插入和删除等操作。

3. 栈栈是一种特殊的线性表，具有后进先出的特性。

考研中可能出现与栈相关的题目，如栈的应用、栈的实现等。

二、树与图树和图是常见的非线性数据结构，具有丰富的应用场景。

考研中涉及树与图的题目较多，要求考生掌握树和图的基本操作和相关算法。

1. 二叉树二叉树是一种特殊的树结构，每个节点最多只有两个子节点。

考研中可能出现与二叉树相关的题目，如二叉树的遍历、节点的插入和删除等操作。

2. 图图是由节点（顶点）和边组成的数据结构，用于描述各种实际问题的模型。

考研中可能出现与图相关的题目，如最短路径、最小生成树等算法的应用。

三、排序与查找排序和查找是算法中的经典问题，也是考研中常见的题型。

考生需要熟练掌握各种排序和查找算法，并能够分析其时间复杂度和空间复杂度。

1. 排序算法考研中常考察各种排序算法，如冒泡排序、选择排序、插入排序、快速排序等。

考生需要理解这些算法的原理和步骤，并能够分析其时间复杂度和空间复杂度。

2. 查找算法考研中可能出现与查找算法相关的题目，如二分查找、哈希查找、二叉查找树等。

考生需要了解这些算法的原理和应用场景，并能够分析其时间复杂度和空间复杂度。

四、动态规划与贪心算法动态规划和贪心算法是算法设计中的重要方法，也是考研中常见的题型。