数据结构抢分攻略 真题分类分级详解

版权信息

书名：数据结构抢分攻略真题分类分级详解

ISBN：978-7-115-61797-2

本书由人民邮电出版社发行数字版。版权所有，侵权必究。

您购买的人民邮电出版社电子书仅供您个人使用，未经授权，不得以任何方式复制和传播本书内容。

我们愿意相信读者具有这样的良知和觉悟，与我们共同保护知识产权。

如果购买者有侵权行为，我们可能对该用户实施包括但不限于关闭该帐号等维权措施，并可能追究法律责任。

版　　权

组编   海贼宝藏

著    胡 光 于方泽 汪诗豪

责任编辑 牟桂玲

人民邮电出版社出版发行　　北京市丰台区成寿寺路11号

邮编　100164 　电子邮件　315@ptpress.com.cn

网址　http://www.ptpress.com.cn

读者服务热线：(010)81055410

反盗版热线：(010)81055315

内容提要

本书面向参加计算机相关专业的硕士研究生招生考试（以下简称计算机考研）的考生，以全国硕士研究生招生考试计算机学科专业基础（以下简称全国统考）的考试大纲中“数据结构”部分的内容为依据，在研究、分析全国统考和院校自主命题考试的历年真题及其命题规律的基础上编写而成。

本书就全国统考的考试大纲进行了深入解读，提供了应试策略，并根据“数据结构”所涉及考点的知识体系分章讲解，每章以“知识点分类+经典例题精解”的形式，剖析了常考题型、命题特点及解题方法，帮助考生掌握解题思路与解题技巧。此外，章末提供了“过关练习”，供考生进行自测练习。本书还提供了面向“数据结构”的1套全真模拟题，供考生实战演练。

本书适合参加计算机考研（包括全国统考和院校自主命题考试）的考生备考学习，也适合作为计算机相关专业学生的学习用书和培训机构的辅导用书。

前  言

　本书主旨

“数据结构”是计算机学科的基础课程，也是计算机考研（包括全国统考和院校自主命题考试）涉及的重要内容。学好数据结构不仅有助于提高编程能力，以更好地应对计算机考研，更有助于提高解决问题的能力。这样对考生个人成长大有裨益！

在计算机考研中，由于题量大、涉及的知识点多，不少考生难以抓住重点，导致考试成绩不理想。因此，为了帮助莘莘学子在较短的时间内掌握复习要点及解题方法，提高应试分数，我们深入研究与剖析计算机考研中的历年考点与考题，以全国统考的考试大纲为蓝本，以计算机考研中的重点和难点为主线，精心编写了本书。

　主要学习目标

全国统考的考查内容包括4部分——数据结构、计算机组成原理、操作系统和计算机网络，重点考查考生掌握相关基础知识、基本理论的情况，以及分析问题、解决问题的能力。

其中，“数据结构”部分的考查内容占30%。根据全国统考的考试大纲，本书主要帮助考生达成以下学习目标。

（1）理解数据结构的基本概念和术语，掌握各种数据结构的定义方法和基本操作，能够准确地计算出算法的时间复杂度和空间复杂度。

（2）掌握各种数据结构的程序复现（如利用C语言复现），深刻理解各种数据结构在数据管理方面的优缺点，能够根据数据特性及需要解决的目标问题，选用合理的数据结构予以解决。

（3）能够综合运用数据结构和算法去解决实际问题，并能运用某一种编程语言（如C语言、C++语言）予以实现。

　本书主要特色

（1）紧扣全国统考的考试大纲，明确复习要点，减少复习时间。

本书深入研究全国统考和院校自主命题考试的相关真题，依据全国统考的考试大纲分类提炼考点，不仅有清晰的知识结构，而且准确地对各考点进行考情分析，归纳有效的学习方法，帮助考生抓住复习重点，提高复习效率。

（2）详细讲解大量真题和例题，揭示命题思路，点拨应试技巧。

对于每一个考点，注重结合不同的题型，采取以题代点、以点代面的方式进行讲解。所用题目均为精选的历年真题或精心编写的典型例题，考生不仅能在学习解题的过程中巩固所学知识，而且能熟悉各种题型的解题思路与命题特点，从而有效提高应试能力。

（3）提供特色栏目，帮助考生掌握命题规律，提高应试能力。

书中提供“知识链接”“误区警示”“解题技巧”3个特色栏目。其中，“知识链接”主要给出题目涉及知识点的概念、理论，便于考生回顾考点，加深对知识的理解；“误区警示”主要用于提示考生易犯的答题错误；“解题技巧”主要提供快速解题的方法和答题技巧。

（4）章末提供“过关练习”，考生可加以练习，提高解题能力。

在章尾，按该章考点所涉及的不同题型提供“过关练习”。这些练习题是根据章内相应考点在计算机考研中的命题类型及命题方式精心设计的。考生通过完成这些高质量的练习题，并将自己的答案与书中所提供的参考答案进行对照和检验，不仅可以巩固所学知识点，还可进一步掌握重点、攻克难点，并举一反三。

　怎样使用本书

为了读者能更好地使用本书，建议读者阅读以下提示。

（1）充分了解计算机考研的要求，明确复习思路。建议考生在充分了解全国统考的考试大纲的考查要求后， 跟随本书复习考查重点，掌握解题思路和解题技巧，提高应试能力。

（2）抓住计算机考研重点，有的放矢。不主张考生采用题海战术，因为并不是练习题做得越多就越好。考题的要求虽然会千变万化，但是考查的重点与方式基本不变。考生应注意对各种知识点进行归纳总结，并全面提高自己的记忆能力，这样在复习时才能抓住重点，掌握解题要领，以不变应万变。

　说明

本书中例题，若无特殊说明，均为单项选择题。

尽管编者精益求精，但由于水平有限，书中难免有不足之处， 恳请广大读者批评指正，联系邮箱为muguiling@ptpress.com.cn。

最后，我们相信一分耕耘，一分收获。衷心祝愿使用本书的读者都能开卷有益，更上一层楼!

编　者

考纲分析与应试策略

一、考试简介

全国硕士研究生招生考试是指教育主管部门和招生机构为选拔研究生而组织的相关考试的总称。考试分初试和复试两个阶段进行。初试由国家统一组织，复试由招生单位自行组织。

初试一般设置4个考试科目，分别是思想政治理论、外语、业务课一和业务课二，满分分别为100分、100分、150分和150分。初试方式均为笔试，考试的第一天上午考查思想政治理论，下午考查外语；第二天上午考查业务课一（数学或专业基础课），下午考查业务课二（专业课）。每一科目考试时长均为180分钟。

对计算机考研而言，业务课一是数学，业务课二则根据学校或专业的不同，考查内容也会不同。目前来看，越来越多的学校对计算机或信息相关专业的业务课二，偏向于选择全国统考，也有少部分学校是自主命题。因此，考生在备考业务课二之前，要先明确所报考院校的考查科目和考查内容。例如，在北京航空航天大学2023年硕士研究生招生考试中，软件工程专业的业务课二考查的是软件工程基础综合。在电子科技大学2023年硕士研究生招生考试中，计算机科学与技术专业的业务课二考查的是计算机专业基础。

二、考试方式

对计算机考研来说，全国统考主要考查计算机科学与技术领域的核心知识和技能，旨在培养学生在该领域的研究和应用能力。考试内容较为广泛，包括计算机科学与技术的基础理论、专业知识和应用技术。一般而言，主要涉及数据结构、计算机组成原理、操作系统和计算机网络4部分内容。

答题方式为闭卷、笔试；考试时间为180分钟；试卷满分为150分，其中数据结构内容占45分，计算机组成原理内容占45分，操作系统内容占35分，计算机网络内容占25分；试卷题型结构为单项选择题80分（40题，每题2分），综合应用题70分。

本书针对计算机考研中的“数据结构”部分的内容。在全国统考中，“数据结构”部分的单项选择题一般为10题左右，分值为20分左右；综合应用题一般为2题左右，分值为25分左右。一些自主命题的院校会有所不同。例如，在北京航空航天大学2023年硕士研究生招生考试软件工程专业的初试业务课二“软件工程基础综合”中，“数据结构”部分的总分是50分，具体的题型、题量与分值情况如下表所示。

而在中国农业大学2023年硕士研究生招生考试中，计算机科学与技术专业的初试业务课二为“数据结构”，总分是150分，具体的题型、题量与分值情况如下表所示。

再次强调，考生在备考前一定要了解自己心仪院校相关专业业务课二的考查内容以及分数的分配情况，从而协调分配自己的复习时间，以达到高效复习的目的。

三、考试大纲解读

在全国统考中，“数据结构”部分主要考查线性表、栈、队列、数组、树、二叉树、图、查找、排序等内容。参照全国统考的考试大纲要求和历年真题的命题特点，本书各章内容在考试中所占分值比例、复习重要程度如下表所示。

考生可以根据上表安排复习时间和侧重点。

四、应试经验与答题技巧

考生若想在考试中取得好成绩，除了需要牢固掌握知识点，还需要快速、准确地对一些题目做出判断和处理，因此，考生平时要善于归纳和总结一些通用的答题技巧，这有助于考生更好地应对考试，提高复习效率。

（1）直接挑选法。

对于考查概念或性质的试题，考生只要掌握相应的知识点就能直接做出正确的选择。

例1．下列对顺序存储的有序表 (长度为n)实现给定操作的算法中平均时间复杂度为 O(1)的是（  ）。【2023年全国统考】

A．查找包含指定值元素的值

B．插入包含指定值元素的算法

C．删除第i个元素的算法

D．获取第i个值的算法

【答案】D

  解题技巧

本题考查顺序表的基本性质。对于本题，考生只需要掌握顺序表的基本性质即可作答。由于顺序表的删除和插入元素操作，都需要移动元素，故直接排除B选项和C选项。又因为顺序表的存储结构在内存上是完全连续的，所以可以通过计算直接得到第i个元素的地址，故可以直接获取第i个元素的值。

（2）还原法。

类似于二叉树中遍历的题目，可以先根据已知条件，还原出满足条件的数据结构，最后再进行后续问题的求解。

例2．已知一棵二叉树的后序序列为DABEC，中序序列为DEBAC，则先序序列为（  ）。【模拟题】

A．ACBED

B．DECAB

C．DEABC

D．CEDBA

【答案】D

  解题技巧

本题考查的是二叉树的遍历。可以根据二叉树的后续遍历和中序遍历，还原出这棵二叉树的树形结构，然后再进行二叉树的先序遍历。

（3）带入模拟法。

对于类似于队列的入队、出队合法性问题，可以根据队列的性质，将选项依次带入进行模拟操作流程，进而找到满足或者违反该队列性质的答案。

例3．已知初始为空的队列Q的一端仅能进行入队操作，另外一端既能进行入队操作又能进行出队操作。若Q的入队序列是1,2,3,4,5，则不能得到的出队序列是（  ）。【2021年全国统考】

A．5, 4, 3, 1, 2

B．5, 3, 1, 2, 4

C．4, 2, 1, 3, 5

D．4, 1, 3, 2, 5

【答案】D

  解题技巧

本题考查队列的性质。可以根据队列的性质，将选项依次带入队列中进行模拟入队、出队过程。对于A选项，依次从右端入队1, 2，再从左端入队3, 4, 5，即可得到此出队序列。对于B选项,从右端入队1, 2，然后从左端入队3，再从右端入队4，最后从左端入队5，即可得到此出队序列。对于C选项,从左端入队1, 2,然后从右端入队3，再从左端入队4，最后从右端入队5，即可得到此出队序列。用排除法，可知D选项为本题答案。

五、复习策略

（1）熟悉考试大纲：全面了解考查范围和要求，明确复习的重点和难点，有的放矢地备考效率会更高。

（2）多做真题和模拟题：虽不建议题海战术，但多做典型的真题和模拟题，有助于熟悉考试的出题方式，掌握解题思路和答题技巧。同时，也可以发现自己的薄弱环节，有针对性地进行复习和提高。

（3）掌握数据结构的基本原理和基本操作：理解各种数据结构的基本原理和基本操作是解题的基础。因此，考生要牢固掌握各种数据结构的特点、存储结构和基本操作，能够灵活运用它们解决问题。

（4）掌握常见的算法和操作：数据结构和算法是密不可分的，掌握一些常见的算法和操作，如排序、查找、遍历等，能够帮助你更好地解决与数据结构相关的问题。

（5）保持思路清晰，注意细节：在解题过程中，可以通过在纸上画图、列出关键点的方式，帮助自己厘清思路，避免遗漏。同时，要注意代码书写的正确性和规范性，避免因为细节问题失分。

记住，数据结构是一个需要理解和实践的学科，通过多做题、总结经验和不断提高解题能力，相信你能够在考试中取得好成绩！

第一章　绪论

考情分析

本章主要讲解数据结构的基础知识，在计算机考研中主要涉及的考查内容为数据结构与算法的基本概念。考生若能掌握本章所讲解的考点，就能对数据结构的整体知识框架有一个初步的认识，为之后的学习打下基础。历年计算机考研涉及本章内容的题型、题量、分值及高频考点如下表所示。

知识地图

第一节　数据结构与算法的基本概念

考点1　数据结构的基本概念

例1．数据结构是由具有一种或多种（  ）的若干数据元素组成的集合。【模拟题】

A．性质

B．运算方式

C．特定关系

D．数量

【答案】 C

【解析】本题考查数据结构的定义。数据结构是带有结构特性的若干数据元素的集合，它研究的是数据以及数据之间的相互关系。所以数据结构中的元素具有一种或多种特定关系。

例2．下列关于数据结构的说法中错误的是（  ）。【2016年北京工业大学】

A．数据结构相同，对应的存储结构也相同

B．数据结构涉及数据的逻辑结构、存储结构和施加在其上的操作

C．数据结构操作的实现与存储结构有关

D．定义逻辑结构时可以不考虑存储结构

【答案】 A

【解析】本题考查数据结构的逻辑结构与存储结构。此类考查重点放在概念上的题目陷阱比较多，需要考生细致地分析才能推出答案。很多时候可以通过举例来检验，例如对于两个线性表来说，其存储结构可能不一致（如链表与顺序表），因此A选项错误；逻辑结构、存储结构和数据结构的操作都是数据结构应该涉及的，因此B选项正确；对于线性表的插入操作，顺序表的插入实现和链表的插入实现明显不同，可以说操作的实现是和存储结构相关的，因此C选项正确；仍然使用线性表举例，具有同样逻辑结构的线性表可以使用不同的存储结构（如链表与顺序表），因此D选项正确。

例3．下列说法中，不正确的是（  ）。【2017年扬州大学】

A．数据元素是数据的基本单位

B．数据项是数据元素中不可分割的最小可标识单位

C．数据可由若干个数据元素构成

D．数据项可由若干个数据元素构成

【答案】 D

【解析】本题考查数据的定义。在计算机中，数据的基本单位是数据元素，数据元素可由若干个数据项构成，但是数据项是无法再次分割的。因此A、B、C选项正确，D选项错误。

例4．数组和（  ）属于不同逻辑结构的数据结构。【模拟题】

A．栈

B．队列

C．链表

D．二叉树

【答案】 D

【解析】本题考查逻辑结构。数组和链表都属于线性结构，栈和队列都可以被视为功能受限的线性表，也属于线性结构；而二叉树属于树形结构，是非线性的。

例5．数据的逻辑结构是（  ）关系的整体。【模拟题】

A．数据元素之间逻辑

B．数据项之间逻辑

C．数据类型之间

D．存储结构之间

【答案】 A

【解析】本题考查逻辑结构。解答本题的关键点是弄清数据项和数据元素哪个与逻辑结构有关。数据元素与数据项的关系为数据元素可以包含若干个数据项。而数据的基本单位是数据元素，因此数据的逻辑结构，指的是数据元素之间的逻辑关系，故本题选择A选项。

考点2　算法的基本概念

例．算法是指为解决某一问题的有限指令序列，它必须具有输入、输出以及（  ）等特性。【2015年武汉大学】

A．易读性、稳定性、确定性

B．易读性、稳定性、可移植性

C．有穷性、可行性、确定性

D．有穷性、可行性、可扩充性

【答案】 C

【解析】本题考查算法的特性。算法的5个特性包括有穷性、确定性、可行性、输入、输出，因此本题选择C选项。其中有穷性指的是算法必须在有限的步骤内结束；确定性指的是算法的每个步骤都不能存在二义性；可行性指的是算法的每个步骤都可以通过基本运算实现。

第二节　算法的时间复杂度与空间复杂度

考点3　时间复杂度

例1．下面这段代码中，执行函数func的时间复杂度为（  ）。【模拟题】

void func(int n){
    int i=0,j=0,sum=0;
    for(i=0;i<n;i++){
        while(j<=i){
            j++;
            sum++;
        }
    }
}

A．O(n)

B．O(n²)

C．O(nlogn)

D．以上均错误

【答案】 A

【解析】本题考查时间复杂度的计算。在函数一开始，i和j均为0，i每次循环加1，而j每次循环的结果为j+1，因此整个函数的执行过程中，每次for循环实际上只会执行3次操作，分别为j和sum的自增操作，以及循环后的i++操作，因此执行时间约为3n，时间复杂度为O(n)。

  知识链接

时间复杂度描述的是算法执行时间随着输入规模的增长而增加的趋势。它通常以执行基本操作的次数作为度量，用来评估算法的执行效率。常见记号为O。

以下是常见的时间复杂度的定义。

O(1)：常数时间，无论输入规模增大多少，算法执行时间都固定。

O(logn)：对数时间，算法执行时间随输入规模呈对数增长，即增长缓慢。

O(n)：线性时间，算法执行时间随输入规模呈线性增长。

O(nlogn)：线性对数时间，算法执行时间随输入规模呈线性对数增长。

O(n²)：平方时间，算法执行时间随输入规模呈平方增长。

O(n³)：立方时间，算法执行时间随输入规模呈立方增长。

O(2ⁿ)：指数时间，算法执行时间随输入规模呈指数增长。

上述时间复杂度的比较关系为：

O(1) ≤ O (log n)≤O(n) ≤O(n²) ≤ O(n³) ≤O(2ⁿ)。

例2．设n为描述问题规模的非负整数，下列程序段的时间复杂度是（  ）。【2019年全国统考】

x=0;
while(n>=(x+1)*(x+1)){
    x=x+1;
}

A．O(logn)

B．O(n^1/2)

C．O(n)

D．O(n²)

【答案】 B

【解析】本题考查时间复杂度的计算。此程序段主要耗时在循环上，循环共执行了x次，需要根据n求得x。根据式子n = (x+1) (x+1)求解x，最终求得循环执行次数x≈，即n^1/2，所以此程序段的时间复杂度为O(n^1/2)。

例3．一个算法的时间复杂度为O(n²)，则下列说法中哪个是正确的（  ）。【模拟题】

A．该算法的执行时间为n²

B．该算法的执行时间与n²成正比

C．该算法的问题规模是n²

D．该算法的问题规模与n²成正比

【答案】 B

【解析】本题考查时间复杂度的分析。首先算法的时间复杂度是对时间的考量，而不是对问题规模的考量，时间复杂度和问题规模无关（但和数据规模有关），因此C、D选项不正确；其次时间复杂度是一种渐进表示方式，其省略了最高项的系数以及所有的其他项，因此大多数问题的执行时间都不会恰好为n²，但可能和n²成正比，例如执行时间可能为2n²。故A选项不正确，B选项正确。

例4．下列关于算法时间复杂度的说法中，正确的是（  ）。【模拟题】

A．算法的时间复杂度与问题规模有关

B．算法的时间复杂度与程序设计语言有关

C．算法的时间复杂度与算法解决问题的策略有关

D．算法的时间复杂度与算法中语句的执行次数无关

【答案】 C

【解析】本题考查时间复杂度的分析。规模很大的问题的解决策略的时间复杂度可能很小，故A选项错误。时间复杂度是一种多项式，程序设计语言不会影响多项式的系数和项数，故B选项错误。对于同一个问题，不同解决策略的时间复杂度可能不同。例如，不同的排序算法，虽然都是为了排序，但是时间复杂度不完全一致，故C选项正确。对时间复杂度的分析实际上就是对最内层循环语句的分析，因此关键的语句执行次数多出一个量级后，时间复杂度自然会变大，故D选项错误。

考点4　空间复杂度

例．某算法的空间复杂度为O(1)，则（  ）。【2015年四川大学】

A．该算法执行不需要任何辅助存储空间

B．该算法执行所需辅助存储空间的大小与问题规模n无关

C．该算法执行不需要任何存储空间

D．该算法执行所需存储空间的大小与问题规模n无关

【答案】 B

【解析】本题考查空间复杂度的分析。空间复杂度与时间复杂度相似，它们都是数学上的渐进表示方式。空间复杂度的意义为在算法执行过程中，不需要大于常数级别的辅助存储空间，而不是不需要大于常数级别的存储空间。这里考生应清楚存储空间与辅助存储空间的易混淆之处。

  误区警示

空间复杂度描述的是算法执行期间所需辅助存储空间的大小。它通常以数据结构的存储空间和程序使用空间的度量来评估算法的空间性能。

过关练习

单项选择题

1．以下名称表示物理结构的是（  ）。【模拟题】

①线性表　②二叉树　③集合　④图　⑤单链表　⑥散列表

A．①②

B．③④

C．①⑤

D．⑤⑥

2．在各类存储结构中，（  ）查找（按关键字查找）、插入、删除速度慢，但顺序存取和随机存取第i个元素速度快；（  ）查找和存取速度快，但插入、删除速度慢；（  ）查找、插入和删除速度快，但不能进行顺序存取；（  ）插入、删除和顺序存取速度快，但查找速度慢。【2016年昆明理工大学】

A．散列表；顺序有序表；顺序表；单链表

B．顺序表；顺序有序表；散列表；单链表

C．单链表；顺序有序表；散列表；顺序表

D．顺序有序表；顺序表；单链表；散列表

3．数据的4种基本存储结构是指（  ）。【2018年昆明理工大学】

A．顺序存储结构、索引存储结构、直接存储结构、链式存储结构

B．顺序存储结构、索引存储结构、链式存储结构、散列存储结构

C．顺序存储结构、非顺序存储结构、指针存储结构、树形存储结构

D．顺序存储结构、链式存储结构、树形存储结构、图存储结构

4．一个算法具有（  ）5个重要特性。【模拟题】

A．确定性、有穷性、稳定性、输入、输出

B．易读性、稳定性、安全性、输入、输出

C．有穷性、确定性、可行性、输入、输出

D．可行性、可移植性、可扩充性、输入、输出

5．下列关于算法的说法正确的是（  ）。【模拟题】

A．算法最终必须由计算机程序实现

B．一个算法执行所花时间等于该算法中每条语句的执行时间之和

C．算法的可行性是指指令不能有二义性

D．算法的有穷性指的是程序所处理的数据量是有限的

6．下面关于算法的描述，错误的是（  ）。【2018年四川大学】

A．算法必须是正确的

B．算法必须能够结束

C．一个问题可以由多种算法解决

D．算法的某些步骤可以有二义性

7．计算机算法指的是（  ）。【2017年上海海事大学】

A．计算方法

B．排序方法

C．调度方法

D．解决问题的步骤序列

8．下面程序段的时间复杂度是（  ）。【2017年广东工业大学】

x=0;
for(i=0;i<n;i++){
    for(j=i;j<n;j++){
        x++;
    }
}

A．O(logn)

B．O(n)

C．O(nlogn)

D．O(n²)

9．时间复杂度O(1)的含义是（  ）。【2016年广东工业大学】

A．问题规模为1

B．执行时间为1s

C．问题规模为1的常数倍

D．执行时间与问题规模无关

10．下列程序段的时间复杂度为（  ）。【2015年常州大学】

i=1,x=0;
do {
    x++;
    i=2*i;
} while(i<n)

A．O(logn)

B．O(n²)

C．O(n)

D．O(1)

11．下列程序段的时间复杂度为（  ）。【2016年昆明理工大学】

j=0,s=0;
while(s<n){
    j++;
    s+=j;
}

A．O(n^1/2)

B．O(n)

C．O(n²)

D．O(1)

答案与解析

1．【答案】 D

【解析】本题考查物理结构。数据的存储结构包括顺序、链式、索引、散列。题目中的单链表是链式存储结构，散列表是散列存储结构，因此选择D选项。

2．【答案】 B

【解析】本题考查数据结构的效率分析。单链表的按关键字查找速度较慢，需要从头依次比较，但是插入和删除只需要改变指针的方向，速度快；顺序表的随机存取第i个元素很快，但是插入和删除需要挪动大量元素的位置，速度慢；顺序有序表由于其有序的特征，可以使用二分查找进行加速，因此查找速度比较快，但是插入和删除速度没有提升，都比较慢；散列表是一种查找、插入、删除都很快的数据结构，但由于其散列存储的特点，无法进行顺序存取。综上，本题的答案为B选项。

3．【答案】 B

【解析】本题考查存储结构。数据的存储结构包括顺序存储结构、索引存储结构、链式存储结构、散列存储结构，因此选择B选项。

  知识链接

顺序存储意味着连续的存储空间存放逻辑连续的数据；索引存储意味着对每个数据元素附加索引进行存储；链式存储意味着不连续的存储空间存放逻辑连续的数据，但需要额外的数据项来指向下一个元素；散列存储意味着使用关键字直接计算出结点的存储地址。

4．【答案】 C

【解析】本题考查算法的特性。算法具有5个特性：有穷性、确定性、可行性、输入、输出，因此选择C选项。

  知识链接

有穷性指的是算法必须在有限的步骤内结束；确定性指的是算法的每个步骤都不能存在二义性；可行性指的是算法中的每个步骤都可以通过基本运算实现；一个算法存在零个或多个输入，输入是取自某个特定的对象的集合；一个算法存在一个或多个输出，输出是算法运行后的集合。

5．【答案】 B

【解析】本题考查算法的特性。算法是对特定问题求解步骤的一种描述，因此A选项错误；算法的确定性指的是每个步骤都不能存在二义性，可行性指的是每个步骤都可以通过基本运算实现，因此C选项错误；算法的有穷性指的是程序处理问题的步骤（运行时间）是有限的，因此D选项错误。

6．【答案】 D

【解析】本题考查算法的特性。算法的5个特性中，确定性指的是算法中的每个步骤不能有二义性，因此D选项错误。

7．【答案】 D

【解析】本题考查算法的定义。算法是对特定问题求解步骤的一种描述。

8．【答案】 D

【解析】本题考查时间复杂度的计算。题目中程序段的外层循环共执行n次，内层循环每次执行n−i次，因此总共执行的次数约为n+(n−1)+(n−2)+…+1 = n(n+1)/2，时间复杂度为O(n²)。

9．【答案】 D

【解析】本题考查时间复杂度的计算。O(1)复杂度指的是算法可以在常数级别时间内对任何规模的数据量进行处理，因此本题的答案为D选项。

10．【答案】 A

【解析】本题考查时间复杂度的计算。题目中程序段的while循环退出条件为i小于n，而循环中的i每次都乘2，因此时间复杂度为O(logn)。

11．【答案】 A

【解析】本题考查时间复杂度的计算。此程序段主要耗时在循环上，循环共执行了j次，需要根据n求得j。j在循环时为等差数列1，2，3，4，…，s为j的累加，由等差数列求和公式可以求得s = (1+j) j/2，再根据s=n，解得j≈n^1/2，所以此程序段的时间复杂度为O(n^1/2)。