第一章 数据结构与算法

1、聚创软件聚创软件第一章第一章数据结构与算法聚创软件聚创软件考点1 算法的基本特征（1）可行性）可行性 由于算法的设计是为了在某一个特定的由于算法的设计是为了在某一个特定的计算工具上解决某一个实际的问题而设计计算工具上解决某一个实际的问题而设计的，因此，它总是受到计算工具的限制，的，因此，它总是受到计算工具的限制，使执行产生偏差。使执行产生偏差。 如：计算机的数值有效位是有限的，当大如：计算机的数值有效位是有限的，当大数和小数进行运算时，往往会因为有效位数和小数进行运算时，往往会因为有效位数的影响而使小数丢失，因此，在算法设数的影响而使小数丢失，因此，在算法设计时，应该考虑到这一点。计时，应该考

2、虑到这一点。 聚创软件聚创软件考点1 算法的基本特征（2）确定性）确定性 算法的设计必须是每一个步骤都有明确算法的设计必须是每一个步骤都有明确的定义，不允许有模糊的解释，也不能有的定义，不允许有模糊的解释，也不能有多义性。多义性。 （3）有穷性）有穷性 算法的有穷性，即在一定的时间是能够算法的有穷性，即在一定的时间是能够完成的，即算法应该在计算有限个步骤后完成的，即算法应该在计算有限个步骤后能够正常结束。能够正常结束。 聚创软件聚创软件考点1 算法的基本特征（4）拥有足够的情报）拥有足够的情报 算法的执行与输入的数据和提供的初始算法的执行与输入的数据和提供的初始条件相关，不同的输入或初始条件会

3、有不条件相关，不同的输入或初始条件会有不同的输出结果，提供准确的初始条件和数同的输出结果，提供准确的初始条件和数据，才能使算法正确执行。据，才能使算法正确执行。 聚创软件聚创软件考点真题算法的有穷性是指算法的有穷性是指_。A)算法程序的运行时间是有限的算法程序的运行时间是有限的B)算法程序所处理的数据量是有限的算法程序所处理的数据量是有限的C)算法程序的长度是有限的算法程序的长度是有限的D)算法只能被有限的用户使用算法只能被有限的用户使用2008年年4月选择题第月选择题第5题题答案：答案：A5聚创软件聚创软件考点2 算法复杂度 算法复杂度包括算法时间复杂度和算法空算法复杂度包括算法时间复杂度和

4、算法空间复杂度。间复杂度。1.算法的时间复杂度算法的时间复杂度算法的时间复杂度是指执行算法所需要的计算法的时间复杂度是指执行算法所需要的计算工作量。算工作量。2.算法的空间复杂度算法的空间复杂度 指执行这个算法所需要的内存空间。指执行这个算法所需要的内存空间。6聚创软件聚创软件考点真题算法的时间复杂度是指算法的时间复杂度是指A)算法的执行时间算法的执行时间B)算法所处理的数据量算法所处理的数据量C)算法程序中的语句或指令条数算法程序中的语句或指令条数D)算法在执行过程中所需要的基本运算次数算法在执行过程中所需要的基本运算次数2010年年3月选择题第月选择题第2题题参考答案：参考答案：D7聚创软

5、件聚创软件考点真题算法的空间复杂度是指算法的空间复杂度是指_。A)算法在执行过程中所需要的计算机存储空算法在执行过程中所需要的计算机存储空间间B)算法所处理的数据量算法所处理的数据量C)算法程序中的语句或指令条数算法程序中的语句或指令条数D)算法在执行过程中所需要的临时工作单元算法在执行过程中所需要的临时工作单元数数 参考答案：参考答案：A8聚创软件聚创软件考点考点3 数据结构的定义数据结构的定义p数据结构是指相互之间存在一种或多种特数据结构是指相互之间存在一种或多种特定关系的数据元素的集合。定关系的数据元素的集合。9聚创软件聚创软件考点考点3 数据结构的定义数据结构的定义数据结构主要研究和讨

6、论以下三个方面：数据结构主要研究和讨论以下三个方面：（1）数据集合中个数据元素之间所固有的逻）数据集合中个数据元素之间所固有的逻辑关系，即数据的逻辑结构；辑关系，即数据的逻辑结构；（2）在对数据元素进行处理时，各数据元素）在对数据元素进行处理时，各数据元素在计算机中的存储关系，即数据的存储结在计算机中的存储关系，即数据的存储结构；构；（3）对各种数据结构进行的运算。）对各种数据结构进行的运算。10聚创软件聚创软件 数据的逻辑结构数据的逻辑结构 数据的存储结构数据的存储结构 数据的运算：检索、排序、插入、删除、修改等数据的运算：检索、排序、插入、删除、修改等 线性结构线性结构 非线性结构非线性结

7、构 顺序存储顺序存储 链式存储链式存储 线性表线性表栈栈队队树形结构树形结构图形结构图形结构数据结构的三个方面：数据结构的三个方面：聚创软件聚创软件考点考点3 数据结构的定义数据结构的定义q数据的逻辑结构有两个要素：一是数据元数据的逻辑结构有两个要素：一是数据元素的集合，通常记为素的集合，通常记为D；二是；二是D上的关系，上的关系，它反映了数据元素之间的前后件关系，通它反映了数据元素之间的前后件关系，通常记为常记为R。一个数据结构可以表示成。一个数据结构可以表示成B=（D，R）聚创软件聚创软件考点考点3 数据结构的定义数据结构的定义p其中其中B表示数据结构。为了反映表示数据结构。为了反映D中各

8、数据中各数据元素之间的前后件关系，一般用二元组来元素之间的前后件关系，一般用二元组来表示。表示。p数据的逻辑结构在计算机存储空间中的存数据的逻辑结构在计算机存储空间中的存放形式称为数据的存储结构（也称数据的放形式称为数据的存储结构（也称数据的物理结构）。物理结构）。13聚创软件聚创软件考点4 线性表与顺序存储结构q根据数据结构中各数据元素之间前后件关根据数据结构中各数据元素之间前后件关系的复杂程度，一般将数据结构分为两大系的复杂程度，一般将数据结构分为两大类型：线性结构与非线性结构。线性结构类型：线性结构与非线性结构。线性结构又称线性表又称线性表,在一个线性结构中插入或删除在一个线性结构中插入

9、或删除任何一个结点后还应是线性结构。如果一任何一个结点后还应是线性结构。如果一个数据结构不是线性结构，则称之为非线个数据结构不是线性结构，则称之为非线性结构。性结构。14聚创软件聚创软件15考点4 线性表与顺序存储结构是是n n个个( (表长表长n0)n0)同类型数据元素同类型数据元素的有限序列。元素间是线性逻辑关系，排的有限序列。元素间是线性逻辑关系，排成线性序列。成线性序列。 记作：记作： v有且仅有一个根结点，它无前件；有且仅有一个根结点，它无前件；v有且仅有一个终端结点，它无后件；有且仅有一个终端结点，它无后件；v除根结点外，每个结点只有一个除根结点外，每个结点只有一个；v除尾结点外，

10、每个结点只有一个除尾结点外，每个结点只有一个。vn n0 0的线性表为的线性表为。 聚创软件聚创软件16线性表实例q (A(A，B B，C C，D D，X X，Y Y，Z)Z)q (50(50，100100，250250，300300，500500，1200)1200)q 体现在体现在顺序关系上顺序关系上记录排列为记录排列为顺序关系顺序关系聚创软件聚创软件17线性表的顺序存储结构顺序表 示 意 图聚创软件聚创软件18顺序表顺序表的插入的插入操作演示操作演示n-1聚创软件聚创软件19顺序表的删除 ai a0 ai-1。前移前移n-i-1个个元素元素 0 i-1 i i+1 n-1 m-1an-1

11、删除它删除它ai+1ain-1操作演示操作演示聚创软件聚创软件考点真题下列叙述中正确的是下列叙述中正确的是A)线性表的链式存储结构与顺序存储结构所线性表的链式存储结构与顺序存储结构所需要的存储空间是相同的需要的存储空间是相同的B)线性表的链式存储结构所需要的存储空间线性表的链式存储结构所需要的存储空间一般要多于顺序存储结构一般要多于顺序存储结构C)线性表的链式存储结构所需要的存储空间线性表的链式存储结构所需要的存储空间一般要少于顺序存储结构一般要少于顺序存储结构D)上述三种说法都不对上述三种说法都不对 20聚创软件聚创软件考点真题参考答案：参考答案：B【解析解析】线性表的顺序存储结构是把线性表

12、线性表的顺序存储结构是把线性表中相邻的元素存放在相邻的内存单元中，中相邻的元素存放在相邻的内存单元中，而链式存储结构是用一组任意存储单元来而链式存储结构是用一组任意存储单元来存放表中的数据元素，为了表示出每个元存放表中的数据元素，为了表示出每个元素与其直接后继元素之间的关系，除了存素与其直接后继元素之间的关系，除了存储元素本身的信息外，还需存储一个指示储元素本身的信息外，还需存储一个指示其直接后继的存储位置信息。故线性表的其直接后继的存储位置信息。故线性表的链式存储结构所需的存储空间一般要多于链式存储结构所需的存储空间一般要多于顺序存储结构，答案为顺序存储结构，答案为B）。）。21聚创软件聚创

13、软件考点真题在长度为在长度为n的顺序存储的线性表中插入一个元的顺序存储的线性表中插入一个元素，最坏情况下需要移动表中素，最坏情况下需要移动表中【2】个个元素。元素。 参考答案：参考答案：n【解析解析】在长度为在长度为n的顺序存储的线性表中插的顺序存储的线性表中插入一个元素，最坏的情况即插入在第一个入一个元素，最坏的情况即插入在第一个位置，线性表中所有元素均需要移动，因位置，线性表中所有元素均需要移动，因此需要移动此需要移动n次。次。22聚创软件聚创软件23考点考点5 栈与队列栈与队列 是限定在一端进行插入或删除操作的线性表。是限定在一端进行插入或删除操作的线性表。先进后出先进后出 (First

14、InLastOut) 的线性表的线性表 栈底栈顶a1a4a2a3NULLa5聚创软件聚创软件考点考点5 栈与队列栈与队列p栈的基本概念栈的基本概念 栈是限定只在一端进行插入与删除的线性表栈是限定只在一端进行插入与删除的线性表，通常称插入、删除的这一端为栈顶，另，通常称插入、删除的这一端为栈顶，另一端为栈底。当表中没有元素时称为空栈一端为栈底。当表中没有元素时称为空栈。栈顶元素总是后被插入的元素，从而也。栈顶元素总是后被插入的元素，从而也是最先被删除的元素；栈底元素总是最先是最先被删除的元素；栈底元素总是最先被插入的元素，从而也是最后才能被删除被插入的元素，从而也是最后才能被删除的元素。栈是按照

15、的元素。栈是按照先进后出先进后出或或后进先出后进先出的原则组织数据的。的原则组织数据的。24聚创软件聚创软件考点考点5 栈与队列栈与队列栈的基本运算有三种：入栈、退栈与读栈顶栈的基本运算有三种：入栈、退栈与读栈顶元素。元素。（1）入栈运算：入栈运算是指在栈顶位置插）入栈运算：入栈运算是指在栈顶位置插入一个新元素。首先将栈顶指针加一（即入一个新元素。首先将栈顶指针加一（即top加加1），然后将新元素插入到栈顶指针），然后将新元素插入到栈顶指针指向的位置。当栈顶指针已经指向存储空指向的位置。当栈顶指针已经指向存储空间的最后一个位置时，说明栈空间已满，间的最后一个位置时，说明栈空间已满，不可能再进行

16、入栈操作。这种情况称为栈不可能再进行入栈操作。这种情况称为栈上溢上溢错误。错误。25聚创软件聚创软件考点考点5 栈与队列栈与队列（2）退栈运算：退栈是指取出栈顶元素并赋）退栈运算：退栈是指取出栈顶元素并赋给一个指定的变量。首先将栈顶元素（栈给一个指定的变量。首先将栈顶元素（栈顶指针指向的元素）赋给一个指定的变量顶指针指向的元素）赋给一个指定的变量，然后将栈顶指针减一（即，然后将栈顶指针减一（即top减减1）。当）。当栈顶指针为栈顶指针为0时，说明栈空，不可进行退栈时，说明栈空，不可进行退栈操作。这种情况称为栈的操作。这种情况称为栈的下溢下溢错误。错误。26聚创软件聚创软件考点考点5 栈与队列栈

17、与队列（3）读栈顶元素：读栈顶元素是指将栈顶元）读栈顶元素：读栈顶元素是指将栈顶元素赋给一个指定的变量。这个运算不删除素赋给一个指定的变量。这个运算不删除栈顶元素，只是将它赋给一个变量，因此栈顶元素，只是将它赋给一个变量，因此栈顶指针不会改变。当栈顶指针为栈顶指针不会改变。当栈顶指针为0时，说时，说明栈空，读不到栈顶元素明栈空，读不到栈顶元素27聚创软件聚创软件28考点考点5 栈与队列栈与队列 是在一端进行插入，在另一端进行删是在一端进行插入，在另一端进行删除操作的线性表。除操作的线性表。First In First Out - FIFOa1a2a3a4a5聚创软件聚创软件29循环队列p把队列

18、空间从把队列空间从上看成是一个首尾相连的环。上看成是一个首尾相连的环。p队尾指针队尾指针rear指向队列中的队尾元素，排头指针指向队列中的队尾元素，排头指针front指向排头元素的前一个位置。指向排头元素的前一个位置。队列空队列空队列满队列满聚创软件聚创软件考点真题下列关于栈的叙述正确的是下列关于栈的叙述正确的是_。A)栈按栈按先进先出先进先出组织数据组织数据B)栈按栈按先进后出先进后出组织数据组织数据C)只能在栈底插入数据只能在栈底插入数据D)不能删除数据不能删除数据2008年年4月选择题第月选择题第7题题参考答案：参考答案：B30聚创软件聚创软件考点真题一个栈的初始状态为空。现将元素一个栈

19、的初始状态为空。现将元素1、2、3、4、5、A、B、C、D、E依次入栈，然后依依次入栈，然后依次出栈，则元素出栈的顺序是次出栈，则元素出栈的顺序是_。A) 12345ABCDE B) EDCBA54321C) ABCDE12345 D) 54321EDCBA2008年年9月选择题第月选择题第1题题 参考答案：参考答案：B31聚创软件聚创软件考点真题下列叙述中正确的是下列叙述中正确的是_。A)栈是栈是先进先出先进先出的线性表的线性表B)队列是队列是先进后出先进后出的线性表的线性表C)循环队列是非线性结构循环队列是非线性结构D)线性表既可以采用顺序存储结构，也可以线性表既可以采用顺序存储结构，也可

20、以采用链式存储结构采用链式存储结构2009年年3月选择题第月选择题第1题题 32聚创软件聚创软件考点真题参考答案：参考答案：D【解析解析】栈是栈是先进后出先进后出的线性表；队列是的线性表；队列是先进先出先进先出的线性表；循环队列是队列的一的线性表；循环队列是队列的一种顺序存储结构，因此是线性结构；线性种顺序存储结构，因此是线性结构；线性表既可以采用顺序存储结构，也可以采用表既可以采用顺序存储结构，也可以采用链式存储结构。链式存储结构。33聚创软件聚创软件考点真题下列数据结构中，能够按照下列数据结构中，能够按照先进后出先进后出原则原则存取数据的是存取数据的是_。A)循环队列循环队列 B)栈栈 C

21、)队列队列 D)二叉二叉树树2009年年9月选择题第月选择题第2题题答案：答案：B34聚创软件聚创软件考点真题下列叙述中正确的是下列叙述中正确的是A)在栈中，栈中元素随栈底指针与栈顶指针在栈中，栈中元素随栈底指针与栈顶指针的变化而动态变化的变化而动态变化B)在栈中，栈顶指针不变，栈中元素随栈底在栈中，栈顶指针不变，栈中元素随栈底指针的变化而动态变化指针的变化而动态变化C)在栈中，栈底指针不变，栈中元素随栈顶在栈中，栈底指针不变，栈中元素随栈顶指针的变化而动态变化指针的变化而动态变化D)上述三种说法都不对上述三种说法都不对35聚创软件聚创软件考点真题 参考答案：参考答案：C【解析解析】栈是限定在

22、一端进行插入与删除的栈是限定在一端进行插入与删除的线性表，允许插入与删除的一端称为栈顶线性表，允许插入与删除的一端称为栈顶，不允许插入与删除的另一端称为栈底。，不允许插入与删除的另一端称为栈底。当有新元素进栈时，栈顶指针向上移动；当有新元素进栈时，栈顶指针向上移动；当有元素出栈时，栈顶指针向下移动。在当有元素出栈时，栈顶指针向下移动。在栈中栈底指针不变，栈中元素随栈顶指针栈中栈底指针不变，栈中元素随栈顶指针的变化而动态变化，故答案为的变化而动态变化，故答案为C）。）。36聚创软件聚创软件考点真题下列关于栈叙述正确的是下列关于栈叙述正确的是A)栈顶元素最先能被删除栈顶元素最先能被删除B)栈顶元素

23、最后才能被删除栈顶元素最后才能被删除C)栈底元素永远不能被删除栈底元素永远不能被删除D)以上三种说法都不对以上三种说法都不对2011年年3月选择题第月选择题第1题题答案：答案：A37聚创软件聚创软件考点真题对于循环队列，下列叙述中正确的是对于循环队列，下列叙述中正确的是_。A)队头指针是固定不变的队头指针是固定不变的B)队头指针一定大于队尾指针队头指针一定大于队尾指针C)队头指针一定小于队尾指针队头指针一定小于队尾指针D)队头指针可以大于队尾指针，也可以小于队头指针可以大于队尾指针，也可以小于队尾指针队尾指针2009年年9月选择题第月选择题第3题题 38聚创软件聚创软件考点真题参考答案：参考答

24、案：D【解析解析】循环队列是将顺序队列首尾相连形循环队列是将顺序队列首尾相连形成的，随着插入元素或删除元素的进行，成的，随着插入元素或删除元素的进行，其队头指针及队尾指针是在不断变化的，其队头指针及队尾指针是在不断变化的，有时可能会出现队头指针大于队尾指针的有时可能会出现队头指针大于队尾指针的情况，也可能是队尾指针大于队头指针，情况，也可能是队尾指针大于队头指针，故答案为故答案为D)。39聚创软件聚创软件考点真题假设用一个长度为假设用一个长度为50的数组的数组(数组元素的下标从数组元素的下标从0到到49)作为栈的存储空间，栈底指针作为栈的存储空间，栈底指针bottom指向栈底指向栈底元素，栈顶

25、指针元素，栈顶指针top指向栈顶元素，如果指向栈顶元素，如果bottom49，top30(数组下标数组下标)，则栈中具有，则栈中具有_【1】_个元素。个元素。2009年年3月填空题第月填空题第1题题答案：答案：20【解析解析】与一般的线性表一样，在程序设计语言中，与一般的线性表一样，在程序设计语言中，用一维数组用一维数组S(1，m)作为栈的顺序存储空间，其中作为栈的顺序存储空间，其中m为栈的最大容量。通常，栈中的元素个数等于为栈的最大容量。通常，栈中的元素个数等于(栈底指针栈顶指针栈底指针栈顶指针1)，即，即4930120。40聚创软件聚创软件考点真题一个栈的初始状态为空。首先将元素一个栈的初

26、始状态为空。首先将元素5,4,3,2,1依次入栈，然后退栈一次，再将依次入栈，然后退栈一次，再将元素元素A，B，C，D依次入栈，之后将所有依次入栈，之后将所有元素全部退栈，则所有元素退栈元素全部退栈，则所有元素退栈(包括中间包括中间退栈的元素退栈的元素)的顺序为的顺序为【1】。 参考答案：参考答案：1DCBA2345【解析解析】栈是限定只在一端进行插入与删除栈是限定只在一端进行插入与删除的线性表，栈按照的线性表，栈按照先进后出先进后出或或后进先出后进先出的原则组织数据。当的原则组织数据。当54321入栈后，此时入栈后，此时执行退栈操作，出栈的元素是执行退栈操作，出栈的元素是1，然后，然后ABC

27、D入栈，再将所有元素退栈，故退栈入栈，再将所有元素退栈，故退栈顺序为：顺序为：1DCBA2345。41聚创软件聚创软件考点真题一个队列的初始状态为空。现将元素一个队列的初始状态为空。现将元素A,B,C,D,E,F,5,4,3,2,1依次入队依次入队,然后再依然后再依次退队次退队,则元素退队的顺序为则元素退队的顺序为【1】。2010年年3月填空题第月填空题第1题题 参考答案：参考答案：ABCDEF54321【解析解析】队列是先进先出的数据结构，所以队列是先进先出的数据结构，所以出队列的顺序与进度列的顺序一致。出队列的顺序与进度列的顺序一致。42聚创软件聚创软件考点真题设某循环队列的容量为设某循环

28、队列的容量为50，头指针，头指针front5(指向队头元素的前一位置指向队头元素的前一位置)，尾指针，尾指针rear29(指向队尾元素指向队尾元素)，则该循环队列中共有，则该循环队列中共有_【3】_个元素。个元素。 2008年4月填空题第3题参考答案：参考答案：24【解析解析】 实现循环队列时，头指针指向第一实现循环队列时，头指针指向第一个元素的前一个空间，尾指针指向最后一个元素的前一个空间，尾指针指向最后一个元素。个元素。 因此，此时队列中因此，此时队列中6,7,8，.,29这这24个空间存有元素，即队列中有个空间存有元素，即队列中有29524个元素。个元素。43聚创软件聚创软件考点真题设某

29、循环队列的容量为设某循环队列的容量为50,如果头指针如果头指针front=45(指向队头元素的前一位置指向队头元素的前一位置),尾指尾指针针rear=10(指向队尾元素指向队尾元素),则该循环队列中则该循环队列中共有共有【2】个元素。个元素。2010年年3月填空题第月填空题第2题题答案：答案：15解析：元素个数为解析：元素个数为50-45+10=1544聚创软件聚创软件考点6 线性链表的基本概念q在链式存储方式中，要求每个结点由两部在链式存储方式中，要求每个结点由两部分组成：一部分用于存放数据元素值，称分组成：一部分用于存放数据元素值，称为数据域，另一部分用于存放指针，称为为数据域，另一部分用

30、于存放指针，称为指针域。其中指针用于指向该结点的前一指针域。其中指针用于指向该结点的前一个或后一个结点（即前件或后件）。个或后一个结点（即前件或后件）。q链式存储方式既可用于表示线性结构，也链式存储方式既可用于表示线性结构，也可用于表示非线性结构。可用于表示非线性结构。45聚创软件聚创软件46p表示每个数据元素的两部分信息组合在一起被表示每个数据元素的两部分信息组合在一起被称为称为结点结点；其中表示数据元素内容的部分被称；其中表示数据元素内容的部分被称为为数据域数据域（data）；表示直接后继元素存储地）；表示直接后继元素存储地址的部分被称为址的部分被称为指针指针或或指针域指针域（next）p

31、指针指针head指向链表中第一个元素的节点，最指向链表中第一个元素的节点，最后一个结点的指针域为空，表示链表终止后一个结点的指针域为空，表示链表终止 单链表简化为下图描述形式单链表简化为下图描述形式headd cba 单链表结构示意图单链表结构示意图考点考点6 线性链表的基本概念线性链表的基本概念聚创软件聚创软件考点6 线性链表的基本概念 线性表的链式存储结构称为线性链表。线性表的链式存储结构称为线性链表。 在某些应用中，对线性链表中的每个结点在某些应用中，对线性链表中的每个结点设置两个指针，一个称为左指针，用以指设置两个指针，一个称为左指针，用以指向其前件结点；另一个称为右指针，用以向其前件

32、结点；另一个称为右指针，用以指向其后件结点。这样的表称为双向链表指向其后件结点。这样的表称为双向链表47聚创软件聚创软件考点真题下列关于线性链表的叙述中，正确的是下列关于线性链表的叙述中，正确的是。A)各数据结点的存储空间可以不连续，但它各数据结点的存储空间可以不连续，但它们的存储顺序与逻辑顺序必须一致们的存储顺序与逻辑顺序必须一致B)各数据结点的存储顺序与逻辑顺序可以不各数据结点的存储顺序与逻辑顺序可以不一致，但它们的存储空间必须连续一致，但它们的存储空间必须连续C)进行插入与删除时，不需要移动表中的元进行插入与删除时，不需要移动表中的元素素D)以上三种说法都不对以上三种说法都不对2011年

33、9月选择题第2题48聚创软件聚创软件考点真题 参考答案：参考答案：C【解析解析】线性表的链式存储结构称为线性链线性表的链式存储结构称为线性链表。在线性链表中，各元素结点的存储空表。在线性链表中，各元素结点的存储空间可以是不连续的，且各数据元素的存储间可以是不连续的，且各数据元素的存储顺序与逻辑顺序可以不一致。在线性链表顺序与逻辑顺序可以不一致。在线性链表中进行插入与删除，不需要移动链表中的中进行插入与删除，不需要移动链表中的元素。因此元素。因此C)选项正确。选项正确。49聚创软件聚创软件考点真题下列叙述中正确的是下列叙述中正确的是_。A) 顺序存储结构的存储一定是连续的，链式顺序存储结构的存储

34、一定是连续的，链式存储结构的存储空间不一定是连续的存储结构的存储空间不一定是连续的B) 顺序存储结构只针对线性结构，链式存储顺序存储结构只针对线性结构，链式存储结构只针对非线性结构结构只针对非线性结构C) 顺序存储结构能存储有序表，链式存储结顺序存储结构能存储有序表，链式存储结构不能存储有序表构不能存储有序表D) 链式存储结构比顺序存储结构节省存储空链式存储结构比顺序存储结构节省存储空间间2008年9月选择题第4题 50聚创软件聚创软件考点真题参考答案：参考答案：A【解析解析】顺序存储方式是把逻辑上相邻的结顺序存储方式是把逻辑上相邻的结点存储在物理上相邻的存储单元里，结点点存储在物理上相邻的存

35、储单元里，结点之间的关系由存储单元的邻接关系来体现之间的关系由存储单元的邻接关系来体现。其优点是占用最少的存储空间，所以选。其优点是占用最少的存储空间，所以选项项D)错误。顺序存储结构可以存储如二叉错误。顺序存储结构可以存储如二叉树这样的非线性结构，所以选项树这样的非线性结构，所以选项B)错误。错误。链式存储结构也可以存储线性表，所以选链式存储结构也可以存储线性表，所以选项项C)错误。错误。51聚创软件聚创软件下列叙述中正确的是下列叙述中正确的是A)线性表的链式存储结构与顺序存储结构所线性表的链式存储结构与顺序存储结构所需要的存储空间是相同的需要的存储空间是相同的B)线性表的链式存储结构所需要

36、的存储空间线性表的链式存储结构所需要的存储空间一般要多于顺序存储结构一般要多于顺序存储结构C)线性表的链式存储结构所需要的存储空间线性表的链式存储结构所需要的存储空间一般要少于顺序存储结构一般要少于顺序存储结构D)上述三种说法都不对上述三种说法都不对2010年9月选择题第1题52聚创软件聚创软件考点真题 参考答案：参考答案：B【解析解析】线性表的顺序存储结构是把线性表线性表的顺序存储结构是把线性表中相邻的元素存放在相邻的内存单元中，中相邻的元素存放在相邻的内存单元中，而链式存储结构是用一组任意存储单元来而链式存储结构是用一组任意存储单元来存放表中的数据元素，为了表示出每个元存放表中的数据元素，

37、为了表示出每个元素与其直接后继元素之间的关系，除了存素与其直接后继元素之间的关系，除了存储元素本身的信息外，还需存储一个指示储元素本身的信息外，还需存储一个指示其直接后继的存储位置信息。故线性表的其直接后继的存储位置信息。故线性表的链式存储结构所需的存储空间一般要多于链式存储结构所需的存储空间一般要多于顺序存储结构，答案为顺序存储结构，答案为B）。）。53聚创软件聚创软件考点真题数据结构分为线性结构与非线性结构，带链的栈属数据结构分为线性结构与非线性结构，带链的栈属于于【1】。2011年9月填空题第1题 参考答案：线性结构参考答案：线性结构【解析解析】数据结构分线性结构和非线性结构，其中数据结

38、构分线性结构和非线性结构，其中线性表、栈、队列、串都是线性结构，线性表、栈、队列、串都是线性结构， 线性结构线性结构的特点是的特点是(当数据元素非空时当数据元素非空时)：存在唯一的：存在唯一的第一第一个个数据元素，存在唯一的数据元素，存在唯一的最后一个最后一个数据元素，数据元素，除第一个元素之外，集合中的每一个数据元素都除第一个元素之外，集合中的每一个数据元素都只有一个直接前驱；除最后一个元素之外，集合只有一个直接前驱；除最后一个元素之外，集合中的每一个数据元素都只有一个后继。中的每一个数据元素都只有一个后继。54聚创软件聚创软件考点考点7 树与二叉树及其基本性质树与二叉树及其基本性质树的基本

39、概念树的基本概念q树是一种简单的非线性结构。在树结构中树是一种简单的非线性结构。在树结构中，数据元素之间有着明显的层次结构。在，数据元素之间有着明显的层次结构。在树的图形表示中，用直线连接两端的结点树的图形表示中，用直线连接两端的结点，上端点为前件，下端点为后件。，上端点为前件，下端点为后件。55聚创软件聚创软件56树示意图RKDYGHUJOPL根结点叶结点子树UO前后件关系父结点叶结点子结点聚创软件聚创软件57与树相关的术语某结点拥有的后件结点个数。所有结点中最大的度。KDYGHUJOPLRU结点的度2R结点的度3叶结点的度0本树的度3聚创软件聚创软件58与树相关的术语是树的最大层次RKDY

40、GHUJOPL层次结构1234本树的深度 4兄弟结点KYU聚创软件聚创软件59 二叉树及其性质q非空二叉树只有一个根结点；q每一个结点最多有两棵子树（左、右子树）。KDYGHUJOPLR左子树右子树聚创软件聚创软件60图：二叉树的5种基本形态 (a) 空二叉树 (b) 仅有一个根结点的二叉树 (c) 右子树为空的二叉树 (d) 左子树为空的二叉树 (e) 左、右子树均非空的二叉树KDUJOPLR(a)(b)(c)(d)(e)聚创软件聚创软件61二叉树性质q二叉树第二叉树第 （k1）层上）层上 有有 个结点；个结点； q深度为深度为的二叉树的二叉树 ，有有 个结点个结点；q在任意一棵二叉树中，度

41、为在任意一棵二叉树中，度为0的结点（叶子结的结点（叶子结点），总是比度为点），总是比度为2的结点多一个的结点多一个q具有具有n个结点的二叉树，其深度个结点的二叉树，其深度 为：为： 取整聚创软件聚创软件62 满二叉树与完全二叉树 若第 层有 个结点，则称此层的结点数是满的；当二叉树中的每一层都是满的时，称为。q深度为 的满二叉树有个结点。KDYGHUJOALRSFPB24-1=151234聚创软件聚创软件63满二叉树与完全二叉树如果一个二叉树各层都是的，只是最下面一层从右边起连续缺若干个结点，这种二叉树叫做完全二叉树。248593671101312111514满二叉树完全二叉树聚创软件聚创软件

42、64完全二叉树性质q具有具有n个结点的完全二叉树的深度个结点的完全二叉树的深度 为：为： 聚创软件聚创软件65完全二叉树性质q若若k=1，则它是根结点，无，则它是根结点，无父结点；父结点； 若若k1，其，其编号为编号为 。q如果如果2kn，则其，则其结点编结点编号为号为2k； 若若2kn，则无，则无左子左子结点。结点。q 如果（如果（2k+1）n，则其，则其结点编号为（结点编号为（2k+1）；）； 若（若（2k+1)n,则无则无右子右子结点结点。24859367110K=15父结点父结点4左子左子6右子右子根结点根结点K=5K=4K=6无左子无左子K=6无右子无右子聚创软件聚创软件考点真题下列

43、关于二叉树的叙述中，正确的是下列关于二叉树的叙述中，正确的是。A)叶子结点总是比度为叶子结点总是比度为2的结点少一个的结点少一个 B)叶子结点总是比度为叶子结点总是比度为2的结点多一个的结点多一个C)叶子结点数是度为叶子结点数是度为2的结点数的两倍的结点数的两倍 D)度为度为2的结点数是度为的结点数是度为1的结点数的两倍的结点数的两倍2011年年9月选择题第月选择题第3题题 参考答案：参考答案：B【解析解析】根据二叉树的性质根据二叉树的性质3，在任意一棵二，在任意一棵二叉树中，度为叉树中，度为0的结点的结点(即叶子结点即叶子结点)总是比总是比度为度为2的结点多一个。故答案为的结点多一个。故答案

44、为B)。66聚创软件聚创软件考点真题某二叉树有某二叉树有5个度为个度为2的结点，则该二叉树中的结点，则该二叉树中的叶子结点数是的叶子结点数是_。A)10 B)8 C)6 D)42009年3月选择题第3题 参考答案：参考答案：C【解析解析】对于任何一棵二叉树对于任何一棵二叉树T，如果其终端，如果其终端结点结点(叶子叶子)数为数为n1，度为，度为2的结点数为的结点数为n2，则则n1n21。所以该二叉树的叶子结点。所以该二叉树的叶子结点数等于数等于516。67聚创软件聚创软件某二叉树共有某二叉树共有7个结点，其中叶子结点只有个结点，其中叶子结点只有1个，则个，则该二叉树的深度为该二叉树的深度为(假设

45、根结点在第假设根结点在第1层层)A)3B)4C)6D)72011年3月选择题第3题 参考答案：参考答案：D【解析解析】叶子结点个数叶子结点个数=度为度为2的结点个数的结点个数+1，在此，在此题中叶子结点个数为题中叶子结点个数为1，说明度为，说明度为2的结点数为的结点数为0，即二叉树中不存在度为，即二叉树中不存在度为2的结点，只有度为的结点，只有度为1的的结点和叶子结点，那么此二叉树就是一棵单支树结点和叶子结点，那么此二叉树就是一棵单支树，树中结点个数即为树的深度，所以答案为，树中结点个数即为树的深度，所以答案为D)。68聚创软件聚创软件某二叉树有某二叉树有5个度为个度为2的结点及的结点及3个度

46、为个度为1的结的结点，则该二叉树中共有点，则该二叉树中共有_【1】_个结点。个结点。 2009年年9月填空题第月填空题第1题题 参考答案：参考答案：14【解析解析】 在二叉树中，度为在二叉树中，度为0的结点数是度的结点数是度为为2的结点数加的结点数加1，故二叉树中结点数的总，故二叉树中结点数的总和为度为和为度为0的结点数、度为的结点数、度为1的结点数及度的结点数及度为为2的结点数三者相加，得出结果为的结点数三者相加，得出结果为14个结个结点。点。69聚创软件聚创软件一棵二叉树有一棵二叉树有10个度为个度为1的结点，的结点，7个度为个度为2的结点，则该二叉树共有的结点，则该二叉树共有【3】个结点

47、个结点。2010年年9月填空题第月填空题第3题题 参考答案：参考答案：25【解析解析】在二叉树中，根据性质在二叉树中，根据性质3，度为，度为0的的结点是度为结点是度为2的结点个数的结点个数+1，故二叉树中结，故二叉树中结点总和为度为点总和为度为0的结点数、度为的结点数、度为1的结点数的结点数以及度为以及度为2的结点数三者相加，即的结点数三者相加，即8+10+7，共，共25个结点。个结点。70聚创软件聚创软件71深度为深度为5的满二叉树有的满二叉树有_【2】_个叶子结点个叶子结点。2008年年4月填空题第月填空题第2题题 参考答案：参考答案：16【解析解析】 在满二叉树中，叶子结点数目的计在满二

48、叉树中，叶子结点数目的计算公式为算公式为2n1，如果是计算节点的总数计，如果是计算节点的总数计算公式为算公式为2n-1其中其中n为树的深度。为树的深度。聚创软件聚创软件72考点8 二叉树的遍历(Traversal) 指按一定规律访问二叉树的每个结点，且每个结点只被访问一次的过程。 左、左、右；、右；、左、右；、左、右； 左、右、左、右、；q按左先右后的原则，常采用上述 、遍历，分称、和。聚创软件聚创软件考点8 二叉树的遍历q (1）前序遍历：先访问根结点、然后遍历）前序遍历：先访问根结点、然后遍历左子树，最后遍历右子树；并且，在遍历左子树，最后遍历右子树；并且，在遍历左、右子树时，仍然先访问根

49、结点，然后左、右子树时，仍然先访问根结点，然后遍历左子树，最后遍历右子树。遍历左子树，最后遍历右子树。73聚创软件聚创软件考点8 二叉树的遍历（2）中序遍历：先遍历左子树、然后访问根）中序遍历：先遍历左子树、然后访问根结点，最后遍历右子树；并且，在遍历左结点，最后遍历右子树；并且，在遍历左、右子树时，仍然先遍历左子树，然后访、右子树时，仍然先遍历左子树，然后访问根结点，最后遍历右子树。问根结点，最后遍历右子树。（3）后序遍历：先遍历左子树、然后遍历右）后序遍历：先遍历左子树、然后遍历右子树，最后访问根结点；并且，在遍历左子树，最后访问根结点；并且，在遍历左、右子树时，仍然先遍历左子树，然后遍、

50、右子树时，仍然先遍历左子树，然后遍历右子树，最后访问根结点。历右子树，最后访问根结点。74聚创软件聚创软件75BDHEICFGA聚创软件聚创软件对下列二叉树进行中序遍历的结果是_【1】_ 。 2008年9月填空题第1题参考答案：DBXEAYFZC【解析】二叉树中序遍历的顺序为先遍历左子树，然后访问根结点，最后遍历右子树。76聚创软件聚创软件设二叉树如下：设二叉树如下：对该二叉树进行后序遍历的结果为对该二叉树进行后序遍历的结果为【3】。2010年年3月填空题第月填空题第3题题 参考答案：参考答案：EDBGHFCA【解析解析】后序遍历二叉树的定义为：先遍历左子树后序遍历二叉树的定义为：先遍历左子树

51、，后序遍历右子树，访问根结点。根据该规则，后序遍历右子树，访问根结点。根据该规则，遍历结果应为遍历结果应为EDBGHFCA。77聚创软件聚创软件考点考点9 顺序查找顺序查找q查找是指在一个给定的数据结构中查找某查找是指在一个给定的数据结构中查找某个指定的元素。从线性表的第一个元素开个指定的元素。从线性表的第一个元素开始，依次将线性表中的元素与被查找的元始，依次将线性表中的元素与被查找的元素相比较，若相等则表示查找成功；若线素相比较，若相等则表示查找成功；若线性表中所有的元素都与被查找元素进行了性表中所有的元素都与被查找元素进行了比较但都不相等，则表示查找失败。比较但都不相等，则表示查找失败。7

52、8聚创软件聚创软件考点考点9 顺序查找顺序查找在下列两种情况下也只能采用顺序查找：在下列两种情况下也只能采用顺序查找：（1）如果线性表为无序表，则不管是顺序存）如果线性表为无序表，则不管是顺序存储结构还是链式存储结构，只能用顺序查储结构还是链式存储结构，只能用顺序查找。找。（2）即使是有序线性表，如果采用链式存储）即使是有序线性表，如果采用链式存储结构，也只能用顺序查找。结构，也只能用顺序查找。79聚创软件聚创软件考点10 二分法查找q二分法只适用于顺序存储的，按非递减排二分法只适用于顺序存储的，按非递减排列的有序表，其方法如下：列的有序表，其方法如下：设有序线性表的长度为设有序线性表的长度为

53、n，被查找的元素为，被查找的元素为i（1）将）将i与线性表的中间项进行比较；与线性表的中间项进行比较；（2）若）若i与中间项的值相等，则查找成功；与中间项的值相等，则查找成功；（3）若）若i小于中间项，则在线性表的前半部小于中间项，则在线性表的前半部分以相同的方法查找；分以相同的方法查找；（4）若）若i大于中间项，则在线性表的后半部大于中间项，则在线性表的后半部分以相同的方法查找。分以相同的方法查找。80聚创软件聚创软件考点真题在长度为在长度为n的有序线性表中进行二分查找，最的有序线性表中进行二分查找，最坏情况下需要比较的次数是坏情况下需要比较的次数是_。A) O(n) B) O(n2)C) O(log2n) B) O(nlog2n)参考答案：参考答案：C81聚创软件聚创软件考点真题下列叙述中正确的是下列叙述中正确的是A)对长度为对长度为n的有序链表进行查找的有序链表进行查找,最坏情况最坏情况下需要的比较次数为下需要的比较次数为nB)对长度为对长度为n的有序链表进行对分查找的有序链表进行对分查找,最坏最坏情况下需要的比较次数为情况下需要的比较次数为(n2)C)对长度为对长度为n的有序链表进行对分查找的有序链表进行对分查找,最坏最坏情况下需要的比较次数为情况下需要的比较次数为(log2n)D)对长度为对长度为n的有序链表进行对分查找的有序链表进行对分查