1、计算机应用能力教学部1二级公共基础知识部分 计算机应用能力教学部2第第 1 章章 算法与数据结构算法与数据结构 计算机应用能力教学部3Point1：算法的基本概念：算法的基本概念 1、算法算法：是指解题方案的准确而完整的描述。(1)算法不等于程序，也不等计算机方法，程序的编制不可能优于算法的设计。程序也可以作为算法的一种描述，但程序通常还要考虑程序运行时的环境限制等。(2)算法，是一组严谨地定义运算顺序的规则，并且每一个规则都是有效的，是明确的，此顺序将在有限的次数下终止。2、算法的基本特征：(1)可行性，例如 10 +1-10 的问题(2)确定性，算法中每一步骤都必须有明确定义，不允许有模棱
2、两可的解释，不允许有多义性；例在特殊情况时，数学公式是正确的，但计算机就是无法操作。(3)有穷性，算法必须能在有限的时间内做完，即能在执行有限个步骤后终止，包括合理的执行时间的含义。例如 1/3 的无理数问题。(4)拥有足够的情报。所有的各种可能情况都要考虑到。计算机应用能力教学部4 3、一个算法的优劣将影响到算法乃至程序的效率。算法分析的目的在于选择合适算法和改进算法。一个算法的评价主要从时间复杂度和空间复杂度来考虑。(1)算法的时间复杂度是指执行算法所需要的计算工作量，可以执行算法的过程中所需要的基本运算的执行次数来度量。分析算法工作量的方法有：平均性态分析、最坏情况分析。(2)算法的空间
3、复杂度是指执行这个算法所需要的内存空间。主要包括：算法程序所占的空间；输入的初始数据所占的空间；算法执行过程中所需要的额外空间。计算机应用能力教学部5【真题 1】算法的有穷性是指算法的有穷性是指_。（2008 年 4 月）A)算法程序的长度是有限的 B)算法只能被有限的用户使用 C)算法程序的运行时间是有限的 D)算法程序所处理的数据量是有限的 解析解析：算法的有穷性，是指算法必须能在有限的时间内做完，即算法必须能在执行有限个步骤后终止。答案答案：C 计算机应用能力教学部6【真题 2】问题处理方案的正确而完整的问题处理方案的正确而完整的描述称为描述称为_【5】_。（2005 年 4 月）解析解
4、析：算法是问题处理方案正确而完整的描述。答案答案：算法 计算机应用能力教学部7【真题 3】算法的空间复杂度是指算法的空间复杂度是指_。（2009 年 9 月）A)算法程序中的语句或指令条数 B)算法在执行过程中所需要的临时工作单元数 C)算法在执行过程中所需要的计算机内部存储空间 D)算法所处理的数据量 解析解析：算法的空间复杂度是指执行这个算法所需要的计算机内部存储空间（简称内存空间）。答案答案：C 计算机应用能力教学部8【真题 4】下列叙述中正确的是下列叙述中正确的是_。（2007 年 3 月）A)数据的逻辑结构与存储结构是一一对应的 B)算法的时间复杂度与空间复杂度一定相关 C)算法的效
5、率只与问题的规模有关，而与数据的存储结构无关 D)算法的时间复杂度是指执行算法所需要的计算工作量 解析解析：算法的时间复杂度是指执行算法所需要的计算工作量。算法的工作量用算法所执行的基本运算次数来度量，而算法所执行的基本运算次数是问题规模的函数；算法的空间复杂度一般是指执行这个算法所需要的内存空间。算法的时间复杂度与空间复杂度并不相关。数据的逻辑结构就是数据元素间的逻辑关系，它是从逻辑上描述数据元素间的关系，是独立于计算机的；数据的存储结构是研究数据元素和数据元素间的关系如何在计算机中表示，它们并非一一对应。算法的执行效率不仅与问题的规模有关，还与数据的存储结构有关。答案答案：D 计算机应用能
6、力教学部9【真题 5】下列叙述中正确的是下列叙述中正确的是_。（2006 年 9 月）A)一个算法的时间复杂度大，则其空间复杂度必定小 B)三种说法都不对 C)一个算法的空间复杂度大，则其时间复杂度也必定大 D)一个算法的空间复杂度大，则其时间复杂度必定小 解析解析：1、时间复杂度是指一个算法执行时间的相对度量；空间复杂度是指算法在运行过程中临时占用所需存储空间大小的度量。2、人们都希望选择一个既省存储空间、又节省执行时间的算法。然而，有时为了加快算法的运行速度，不得不增加空间开销；有时为了能有效地存储算法和数据，又不得不牺牲运行时间。时间和空间的效率往往是一对矛盾，很难做到两全。但是，这不适
7、用于所有的情况，也就是说时间复杂度和空间复杂度之间虽然经常矛盾，但是二者不存在必然的联系。答案答案：B 计算机应用能力教学部10 真题 6】算法复杂度主要包括时间复杂度算法复杂度主要包括时间复杂度和和_【2】_复杂度。复杂度。（2005 年 9 月）解析解析：算法的复杂度主要包括时间复杂度和空间复杂度。所谓算法的时间复杂度，是指执行算法所需要的计算工作量。一个算法的空间复杂度，一般是指执行这个算法所需要的内存空间规模。答案答案：空间 计算机应用能力教学部11【真题 7】算法的时间复杂度是指算法的时间复杂度是指_。（2010 年 3 月）A)算法程序中的语句或指令条数 B)算法在执行过程中所需要
8、的基本运算次数 C)算法的执行时间 D)算法所处理的数据量 解析解析：算法复杂度包括时间复杂度和空间复杂度，是衡量一个算法好坏的度量。算法的时间复杂度主要是基本运算次数。答案答案：B 计算机应用能力教学部12Point2：数据结构的定义：数据结构的定义 、数据结构数据结构：是指相互有关联的数据元素的集合。(1)数据结构研究以下三个方面的问题：数据集合中各数据元素之间所固有的逻辑关系，即数据的逻辑结构；在对数据进行处理时，各数据元素在计算机中的存储关系，即数据的存储结构；对各种数据结构进行的运算。研究以上问题的主要目的是为了提高数据处理的效率（一是提高数据处理的速度，二是节省数据处理过程所占的空
9、间。）计算机应用能力教学部13(2)数据的逻辑结构数据的逻辑结构反映数据元素之间的逻辑关系，即前、后件关系，分为线性结构（线性表、栈和队列）和非线性结构（树和图）。包含：表示数据元素的信息；表示各数据元素之间的前后件关系。(3)数据的存储结构数据的存储结构，是指数据逻辑结构在计算机存储空间中的存放形式，也称数据的物理结构。一般来说，一种数据逻辑结构根据需要可以表示成多种存储结构，常用的数据的存储结构有顺序、链接、索引等。计算机应用能力教学部14 2、数据的逻辑结构与数据的存储结构不一定相同。一般来说，一种数据的逻辑结构根据需要可以表示成多种存储结构。常见的存储结构有顺序、链接、索引等。采用不同
10、的存储结构，数据处理的效率是不相同的。计算机应用能力教学部15【真题 1】下列数据结构中，属于非线性结构的下列数据结构中，属于非线性结构的是是_。（2009 年 9 月）A)二叉树 B)带链栈 C)循环队列 D)带链队列 解析解析：线性结构，是最简单最常用的一种数据结构。线性结构的特点是结构中的元素 间满足线性关系，按这个关系可以把所有元素排成一个线性序列，如：线性表、串、栈和队列都属于线性结构。而非线性结构是指在该类结构中至少存在一个数据元素，它具有两个或者两个以上的前件或后件，如树和二叉树等。答案答案：A 计算机应用能力教学部16【真题 2】下列叙述正确的是下列叙述正确的是_。（2007
11、年 9 月）A)程序执行的效率只取决于所处理的数据量 B)以上三种说法都不对 C)程序执行的效率与数据的存储结构密切相关 D)程序执行的效率只取决于程序的控制结构 解析解析：影响程序执行效率的因素有很多，如数据的存储结构、程序处理的数据量、程序的算法等。顺序存储结构和链式存储结构在数据插入和删除操作上的效率就存在差别，其中，链式存储结构的效率要高一些。答案答案：C 计算机应用能力教学部17（1）下列叙述中正确的是2010.9 A)线性表的链式存储结构与顺序存储结构所需要的存储空间是相同的B)线性表的链式存储结构所需要的存储空间一般要多于顺序存储结构C)线性表的链式存储结构所需要的存储空间一般要
12、少于顺序存储结构D)上述三种说法都不对计算机应用能力教学部18 下列叙述中正确的是A)顺序存储结构的存储空间一定是连续的，链式存储结构的存储空间不一定是连续的B)顺序存储结构只针对线性结构，链式存储结构只针对非线性结构C)顺序存储结构能存储有续表，链式存储结构不能存储有序表D)链式存储结构比顺序存储结构节省存储空间 2008.9计算机应用能力教学部19（6）下列叙述中正确的是 A）数据的逻辑结构与存储结构必定是一一对应的 B）由于计算机存储空间是向量式的存储结构，因此，数据的存储结构一定是线性结构 C）程序设计语言中的数组一般是顺序存储结构，因此，利用数组只能处理线线结构 D）以上三种说法都不
13、对 2007.9计算机应用能力教学部20（4）下列叙述中正确的是 A）一个逻辑数据结构只能有一种存储结构 B）数据的逻辑结构属于线性结构，存储结构属于非线性结构 C）一个逻辑数据结构可以有多种存储结构，且各种存储结构不影响数据处理的效率 D）一个逻辑数据结构可以有多种存储结构，且各种存储结构影响数据处理的效率 2005.9计算机应用能力教学部21(3)线性表的存储结构主要分为顺序存储结构和链式存储结构.队列是一种特殊的线性表,循环队列是队列的顺序存储结构.2007.9 （1）数据结构分为逻辑结构与存储结构，线性链表属于存储结构。2007.4 线性表是逻辑结构。（5）数据结构分为逻辑结构和存储结
14、构，循环队列属于【存储】结构。2005.9计算机应用能力教学部22Point3：线性表、线性链表和循环：线性表、线性链表和循环链表链表 1、如果在一个数据结构中一个数据元素都没有，则称为空的数据结构。根据数据结构中各数据元素 间的前后件关系的复杂程度，分为线性结构与非线性结构。2、如果一个非空的数据结构满足下列两个条件：有且只有一个根结点；每一个结点最多有一个前件，也最多有一个后件，则称该数据结构为线性结构。线性表是一个典型的线性结构。常见的有：线性表，栈，队列，循环队列和线性链表等。3、不满足线性结构条件的数据结构，就是非线性结构。常见的有：数组、广义表、树、二叉树和图都是非线性结构。4、在
15、计算机内，线性表的存储结构有两种：顺序存储（称为线性表线性表）和链式存储（线性链表）。线性表的链式存储结构所需要的存储空间一般要多于顺序存储结构。计算机应用能力教学部23【真题 1】下列叙述中正确的是下列叙述中正确的是_。（2009 年 3 月）A)循环队列是非线性结构 B)有序线性表既可以采用顺序存储结构，也可以采用链式存储结构 C)栈是“先进先出”的线性表 D)队列是“先进后出”的线性表 解析解析：主要考查了栈、队列、循环队列的概念，栈是“先进后出”的线性表，队列是“先进先出”的线性表。根据数据结构中各数据元素之间的前后件关系的复杂程度，一般将数据结构分为两大类型：线性结构与非线性结构。循
16、环队列也是线性结构。有序线性表既可以采用顺序存储结构，又可以采用链式存储结构。答案答案：B 计算机应用能力教学部24【真题 2】数据结构分为线性结构和非线性结构，数据结构分为线性结构和非线性结构，带链的队列属于带链的队列属于 _【5】_结结 构。构。（2006 年 9 月）解析解析：数据结构分为线性结构和非线性结构，其中队列属于线性结构。队列有两种存储结构，一种是顺序存储结构，称为顺序队列；另一种是链式存储结构，称为带链队列。题目中所说的带链的队列就是指带链队列。无论队列采取哪种存储结构，其本质还是队列，仍属于一种线性结构。因此，本题的正确答案是线性结构。答案答案：线性 计算机应用能力教学部2
17、5【真题 3】下列叙述中正确的是下列叙述中正确的是_。（2006 年 4 月）A)双向链表是非线性结构 B)只有根结点的二叉树是线性结构 C)线性链表是线性表的链式存储结构 D)栈与队列是非线性结构 解析解析：线性链表是线性表的链式存储结构。栈与队列是特殊的线性表，它们也是线性结构；双向链表是线性表的链式存储结构，其对应的逻辑结构也是线性结构，而不是非线性结构；二叉树是非线性结构，而不是线性结构。一个非空的数据结构如果满足下列两个条件：(1)有且只有一个根结点；(2)每一个结点最多有一个前件，也最多有一个后件，则称为线性结构。答案答案：C 计算机应用能力教学部26【真题 4】下列叙述中正确的是
18、下列叙述中正确的是_。（2010 年 9 月）A)线性表的链式存储结构所需要的存储空间一般要少于顺序存储结构 B)上述三种说法都不对 C)线性表的链式存储结构与顺序存储结构所需要的存储空间是相同的 D)线性表的链式存储结构所需要的存储空间一般要多于顺序存储结构 解析解析：可以从存储密度的角度，比较链式存储结构和顺序存储结构的存储空间，所谓存储密度是指结点数据本身所占的存储量除以结点结构所占的存储总量所得的值。这个值越大，存储空间利用率越高。顺序表是静态分配的，其存储密度为 1；而链式存储是动态分配的，其存储密度小于 1。答案答案：D 计算机应用能力教学部27(1)下列数据结构中，属于非线性结构
19、的是A)循环队列B)带链队列C)二叉树D)带链栈 2009.9计算机应用能力教学部28（2）下列叙述中正确的是A）有一个以上根结点的数据结构不一定是非线性结构B）只有一个根结点的数据结构不一定是线性结构C）循环链表是非线性结构D）双向链表是非线性结构 2011.3计算机应用能力教学部29Point4：栈、队列和循环队列：栈、队列和循环队列 1、栈栈（Stack）又称堆栈。(1)栈是一种运算受限的线性表，其限制是仅允许在表的一端进行插入和删除运算。人们把此端称为栈顶，栈顶的第一个元素被称为栈顶元素，相对地，把另一端称为栈底。向一个栈插入新元素又称为进栈或入栈，它是把该元素放到栈顶元素的上面，使之
20、成为新的栈顶元素；从一个栈删除元素又称为出栈或退栈，它是把栈顶元素删除掉，使其下面的相邻元素成为新的栈顶元素。(2)由于栈的插入和删除运算仅在栈顶一端进行，后进栈的元素必定先出栈，所以又把栈称为后进先出表（Last In First Out，简称 LIFO）；先进栈的元素必定后出栈，所以又把栈称为先进后出表（First In Last Out，简称 FILO）计算机应用能力教学部30 2、队列队列（Queue）简称队。(1)队列也是一种运算受限的线性表，其限制是仅允许在表的一端进行插入操作，而在表的另一端进行删除操作。我们把允许插入的一端称作队尾（rear），允许删除的一端称作队首（front
21、）。(2)向队列中插入新元素称为进队或入队，新元素进队后就成为新的队尾元素；从队列中删除队首元素称为离队或出队，该元素离队后，其后继元素就成为新的队首元素。(3)由于队列的插入和删除操作分别是在各自的一端进行的，每个元素必然按照进队的次序离队，所以又把队列称为先进先出表（First In First Out，简称 FIFO）。3、循环队列循环队列。就是将队列存储空间的最后一个位置绕到第一个位置，形成逻辑上的环状空间，供队列循环使用，其实质还是顺序存储结构。计算机应用能力教学部31【真题 1】对于循环队列，下列叙述中正确的是对于循环队列，下列叙述中正确的是_。（2009 年 9 月）A)队头指针
22、一定小于队尾指针 B)队头指针可以大于队尾指针，也可以小于队尾指针 C)队头指针是固定不变的 D)队头指针一定大于队尾指针 解析解析：循环队列中，由于入队时尾指针向前追赶头指针；出队时头指针向前追赶尾指针。所以队头指针可以大于队尾指针，也可以小于队尾指针。答案答案：B 计算机应用能力教学部32【真题 2】下列叙述中正确的是下列叙述中正确的是_。（2008 年 9 月）A)在循环队列中，只需要队尾指针就能反映队列中元素的动态变化 情况 B)循环队列中元素的个数是由队头指针和队尾指针共同决定 C)循环队列有队头和队尾两个指针，因此循环队列是非线性结构 D)在循环队列中，只需要队头指针就能反映队列中
23、元素的动态变化情况 解析解析：循环队列中元素的个数是由队头指针和队尾指针共同决定的，元素的动态变 也是通过队头指针和队尾指针来反映的。答案答案：B 计算机应用能力教学部33【真题 3】设某循环队列的容量为设某循环队列的容量为 50，头，头指针指针 front=5(指向队头元素指向队头元素)，尾指针，尾指针 rear=29(指向队尾元素指向队尾元素)，则该循环队列中，则该循环队列中共有共有_【3】_个元素。个元素。（2008 年 4 月）解析解析：在循环队列中因为头指针指向的是队头元素的前一个位置，所以是从第6 个位置开始有数据元素，即计算从 6 到 29之间有多少个元素，所以队列中的数据元素的
24、个数为：29-6+1=29-5=24。答案答案：24 计算机应用能力教学部34【真题 4】线性表的存储结构主要分为顺线性表的存储结构主要分为顺序存储结构和链式存储结构。队列是一种序存储结构和链式存储结构。队列是一种 特殊的线性表，循环队列是队列的特殊的线性表，循环队列是队列的 _【3】_ 存储结构。存储结构。（2007 年 9 月）解析解析：队列的顺序存储结构一般采用循环队列的形式。所谓循环队列，就是将队列存储空间的最后一个位置绕到第一个位置，形成逻辑上的环状空间，供队列循环使用，其实质还是顺序存储结构。答案答案：顺序 计算机应用能力教学部35【真题 5】下列对队列的叙述正确的是下列对队列的叙
25、述正确的是_。（2007 年 3 月）A)队列在队尾删除数据 B)队列按“先进先出”原则组织数据 C)队列属于非线性表 D)队列按“先进后出”原则组织数据 解析解析：队列(queue)是指允许在一端进行插入、而在另一端进行删除的线性表。允许插入的一端称为队尾；允许删除的一端称为队头。在队列这种数据结构中，最先插入的元素将最先能够被删除；反之，最后插入的元素将最后才能被删除。因此，队列又称“先进先出”或“后进后出”的线性表。答案答案：B 计算机应用能力教学部36 真题 6】一个队列的初始状态为空。现将一个队列的初始状态为空。现将元素元素 A,B,C,D,E,F,5,4,3,2,1 依次入队，然依
26、次入队，然后再依次退队，则元素退队的顺序为后再依次退队，则元素退队的顺序为_【1】_。（2010 年 3 月）解析解析：对于队列来讲，是先进先出。答案答案：A,B,C,D,E,F,5,4,3,2,1 计算机应用能力教学部37【真题 7】设某循环队列的容量为设某循环队列的容量为 50，如，如果头指针果头指针 front=45(指向队头元素的前一位指向队头元素的前一位置置)，尾指针，尾指针 rear=10(指向队尾元素指向队尾元素)，则该，则该循环队列中共有循环队列中共有_【2】_个元素。个元素。（2010 年 3 月）解析解析：这次头指针在尾指针之后，因为是循环队列，所以应该是从 46 到 50
27、，再从 1 到 10 构成了这个队列。答案答案：15 计算机应用能力教学部38【真题 8】下列数据结构中，能够按照下列数据结构中，能够按照“先进后先进后出出”原则存取数据的是原则存取数据的是 _。（2009 年 9 月）A)队列 B)二叉树 C)循环队列 D)栈 解析解析：由于栈的插入和删除运算仅在栈顶一端进行，后进栈的元素必定先出栈，所以栈被称为后进先出表(Last In First Out,简称 LIFO)；先进栈的元素必定后出栈，所以又把栈称为先进后出表(First In Last Out,简称 FILO)。答案答案：D 计算机应用能力教学部39【真题 9】假设用一个长度为 50 的数组
28、(数组元素的下标从 0 到 49 作为栈的存储空间，栈底指针 bottom 指向栈底元素，栈顶指针 top 指向栈顶元素，如果bottom=49，top=30(数组下标),则栈中具有_【1】_个元素。（2009 年 3 月）解析解析：栈底指针到栈顶指针就是当前栈中的所有元素的个数。(注意，此处最容易错误的算成 19)答案答案：20 计算机应用能力教学部40【真题 10】支持子程序调用的数据结构是支持子程序调用的数据结构是_。（2009 年 3 月）A)队列 B)二叉树 C)栈 D)树 解析解析：这个部分的知识超过了教材的范围，但考试也考到过。下面的解析很多同学反应不能理解，建议大家记住答案就可
29、以了。栈是一种限定在一端进行插入与删除的线性表。在主函数调用子函数时，要首先保存主函数当前的状态，然后转去执行子函数，把子函数的运行结果返回到主函数调用子函数时的位置，主函数再接着往下执行，这种过程符合栈的特点。所以一般采用栈式存储方式。答案答案：C 计算机应用能力教学部41【真题 11】一个栈的一个栈的 始状态为空，现将元素始状态为空，现将元素 1、2、3、4、5、A、B、C、D、E 依次入栈，然后依次入栈，然后再依次出栈，则元素出栈的顺序是再依次出栈，则元素出栈的顺序是_。（2008 年 9 月）A)ABCDE12345 B)54321EDCBA C)12345ABCDE D)EDCBA5
30、4321 解析解析：栈是按照“先进后出”或“后进先出”的原则组织数据的。所以出栈顺序是 EDCBA54321。答案答案：D 计算机应用能力教学部42【真题 12】下列关于栈的叙述正确的是下列关于栈的叙述正确的是_。（2008 年 4 月）A)只能在栈底插入数据 B)不能删除数据 C)栈按“先进先出”组织数据 D)栈按“先进后出”组织数据 解析解析：栈是限定在顶端进行数据插入和删除的线性表，允许进行插入和删除元素的一端称为栈顶，另一端称为栈底。栈是按照“先进后出”的原则组织数据的。答案答案：D 计算机应用能力教学部43【真题 13】按按“先进后出先进后出”原则组织数据原则组织数据的数据结构是的数
31、据结构是 _【4】_。（2006 年 9 月）解析解析：栈和队列是两种特殊的线性表，其特殊性在于对它们的操作只能在表的端点进行。栈中的数据按照后进先出的原则进行组织，而队列中的数据是按照先进先出的原则进行组织。答案答案：栈 计算机应用能力教学部44【真题 14】按照按照“后进先出后进先出”原则组织数据的原则组织数据的数据结构是数据结构是_。（2006 年 4 月）A)双向链表 B)二叉树 C)队列 D)栈 解析解析：“后进先出”表示最后被插入的元素最先能被删除。“后进先出”表示最后被插入的元素最先能被删除。答案答案：D 计算机应用能力教学部45【真题 15】下列关于栈的描述正确的是下列关于栈的
32、描述正确的是_。（2005 年 9 月）A)栈是特殊的线性表，只能在一端插入或删除元素 B)栈是特殊的线性表，只能在一端插入元素，而在另一端删除元素 C)在栈中只能插入元素而不能删除元素 D)在栈中只能删除元素而不能插入元素 解析解析：栈是一种特殊的线性表，其插入与删除运算都只在线性表的一端进行。答案答案：A 计算机应用能力教学部46【真题 16】下列关于栈的描述中错误的是下列关于栈的描述中错误的是_。（2005 年 4 月）A)栈具有记忆作用 B)对栈的插入与删除操作中，不需要改变栈底指针 C)栈是先进后出的线性表 D)栈只能顺序存储 解析解析：本题考核栈的基本概念，我们可以通过排除法来确定
33、本题的答案。1、栈是限定在一端进行插入与删除的线性表，栈顶元素总是最后被插入的元 素，从而也是最先能被删除的元素。2、栈底元素总是最先被插入的元素，从而也是最后才能被删除的元素，即栈是 按照“先进后出”或“后进先出”的原则组织数据的，这便是栈的记忆作用。3、对栈进行插入和删除操作时，栈顶位置是动态变 的，栈底指针不变。答案答案：D 计算机应用能力教学部47【真题 17】下列叙述中正确的是下列叙述中正确的是_。（2010 年 9 月）A)在栈中，栈底指针不变，栈中元素随栈顶指针的变化 而动态变 化 B)上述三种说法都不对 C)在栈中，栈中元素随栈底指针与栈顶指针的变化而动态变化 D)在栈中，栈顶
34、指针不变，栈中元素随栈底指针的变化 而动态变化 解析解析：栈是限定仅在一端进行插入和删除操作的线性表。允许插入和删除的一 端叫做栈顶，另一端叫做栈底，因此栈中元素随栈顶指针的变化而动态变化，而栈底指针不变。答案答案：A 计算机应用能力教学部48【真题 18】一个栈的初始状态为空。首先将元素 5，4，3，2，1 依次入栈，然后 退栈一次，再将元素 A,B,C,D 依次入栈，之 后将所有元素全部退栈，则所有元素退 栈 (包括中间退栈的元素)的顺序为_【1】_。（2010 年 9 月）解析解析：本题主要考查栈的出入操作。栈是一种先进后出的数据结构。题目告诉 我们将 5，4，3，2，1 依次入栈，然后
35、退栈一次，很显然这时退栈的是 1，接着将 A，B，C，D 入栈，然后全部退栈，其栈中各元素的退栈顺序是 DCBA2345。所以最后出栈的顺序应该是 1DCBA2345。答案答案：1DCBA2345 计算机应用能力教学部49（1）下列关于栈叙述正确的是A）栈顶元素最先能被删除B）栈顶元素最后才能被删除C）栈底元素永远不能被删除D）以上三种说法都不对 2011.3计算机应用能力教学部50（3）如果进栈序列为e1,e2,e3,e4，则可能的出栈序列是 Ae3,e1,e4,e2 Be2,e4,e3,e1 Ce3,e4,e1,e2 D任意顺序 2007.4计算机应用能力教学部51.(1)下列叙述中正确的
36、是A)栈是先进先出的线性表B)队列是先进后出的线性表C)循环队列是非线性结构D)有序线性表即可以采用顺序存储结构,也可以采用链式存储结构 2009.3计算机应用能力教学部52 5）下列叙述中正确的是A）线性链表是线性表的链式存储结构B）栈与队列是非线性结构C）双向链表是非线性结构D）只有根结点的二叉树是线性结构 2006.4计算机应用能力教学部53Point5：线性链表、双向链表与循：线性链表、双向链表与循环链表环链表 1、数据结构中，每个数据存储在一个存储单元中，这个存储单元称为结点。在链式存储方 式中，要求每个结点由两部分组成：部分用于存放数据元素值，称为数据域；另一部分 用于存放指针，称
37、为指针域。其中指针用于指向该结点的前一个或后一个结点(即前件或后 件 )。2、线性链表线性链表：线性表的链式存储结构，称为线性链表。(1)对于大的线性表，特别是元素变化频繁的线性表不宜采用顺序存储结构，而要用链 式存储结构。(2)数据结构中的每一个结点对应于一个存储单元，这种存储单元称为存储结点，简称 结点。(3)结点由两部分组成：(1)用于存储数据元素值，称为数据域；(2)用于存放指针，称之为指针域，用于指向前一个或后一个结点。(4)在链式存储结构中，存储数据结构的存储空间可以不连续，各数据结点的存储顺序 与数据元素之间的逻辑关系可以不一致，而数据元素之间的逻辑关系是由指针域来确定 的。(5
38、)链式存储方式既可用于表示线性结构，也可用于表示非线性结构。(6)线性链表，HEAD 称为头指针，HEAD=NULL(或 0)称为空表。线性链表的基本运算：查找、插入、删除。计算机应用能力教学部54 3、双向链表双向链表：两指针：左指针(Llink)指向前件结点，右指针(Rlink)指向后件结点。4、循环链表循环链表的两个特点：(1)增加了一个表头结点。(2)最后一个结点的指针域不是空，而是指向表头结点。计算机应用能力教学部55【真题 1】下列叙述中正确的是下列叙述中正确的是_。（2008 年 9 月）A)顺序存储结构能存储有序表，链式存储结构不能存储有序表 B)链式存储结构比顺序存储结构节省
39、存储空间 C)顺序存储结构的存储一定是连续的，链式存储结构的存储空间不一定是 连续的 D)顺序存储结构只针对线性结构，链式存储结构只针对非线性结构 解析解析：顺序存储方式主要用于线性的数据结构，它把逻辑上相邻的数据元素存 储在物理上相邻的存储单元里，结点之间的关系由存储单元的邻接关系来体现。而链式存储结构的存储空间不一定是连续的。链式结构的结点由两部分组成，一部分是数据信息，另一部分是地址域，因 此在存储空间上要多于顺序存储所占用的空间。答案答案：C 计算机应用能力教学部56【真题 2】下列叙述中正确的是下列叙述中正确的是_。（2007 年 9 月）A)程序设计语言中的数组一般是顺序存储结构，
40、因此，利用数组只能处理 线性结构 B)三种说法都不对 C)数据的逻辑结构与存储结构必定是一一对应的 D)由于计算机存储空间是向量式的存储结构，因此，数据的存储结构一定 是线性结构 解析解析：数据的逻辑结构是指反映数据元素 间逻辑关系的数据结构。数据的逻 辑结构在计算机存储空间中的存放形式称为数据的存储结构(也称数据的物理结 构 )。一般来说，一种数据的逻辑结构根据需要可以表示成多种存储结构，常用 的存储结构有顺序、链接、索引等。答案答案：B 计算机应用能力教学部57【真题 3】下列叙述中正确的是下列叙述中正确的是_。（2005 年 9 月）A)一个逻辑数据结构可以有多种存储结构，且各种存储结构
41、不影响数据处 理的效率 B)一个逻辑数据结构可以有多种存储结构，且各种存储结构影响数据处理 的效率 C)一个逻辑数据结构只能有一种存储结构 D)数据的逻辑结构属于线性结构，存储结构属于非线性结构 解析解析：一般来说，一种数据的逻辑结构根据需要可以表示成多种存储结构，常 用的存储结构有顺序、链接、索引等存储结构。而采用不同的存储结构，其数 据处理的效率是不同的。答案答案：B 计算机应用能力教学部58【真题 4】数据结构分为逻辑结构和存储数据结构分为逻辑结构和存储结构，循环队列属于结构，循环队列属于_【5】_结构。结构。（2005 年 9 月）解析解析：数据的逻辑结构在计算机存储空间中的存放形式称
42、为数据的存储结构(也 称数据的物理结构)。所谓循环队列，就是将队列存储空间的最后一个位置绕到 第一个位置，形成逻辑上的环状空间，供队列循环使用。可知，循环队列应当 是存储结构。答案答案：存储 计算机应用能力教学部59【真题 5】数据的存储结构是指数据的存储结构是指_。（2005 年 4 月）A)数据在计算机中的顺序存储方式 B)数据的逻辑结构在计算机中的表示 C)存储在外存中的数据 D)数据所占的存储空间量 解析解析：数据的逻辑结构在计算机存储空间中的存放形式称为数据的存储结构，也称数据的物理结构。答案答案：B 计算机应用能力教学部60【真题 6】下列对于线性链表的描述中正确的是下列对于线性链
43、表的描述中正确的是_。（2005 年 4 月）A)存储空间必须连续，且前件元素一定存储在后件元素的前面 B)存储空间必须连续，且各元素的存储顺序是任意的 C)存储空间不一定是连续，且各元素的存储顺序是任意的 D)存储空间不一定是连续，且前件元素一定存储在后件元素的前面 解析解析：在链式存储结构中，存储数据的存储空间可以不连续，各数据结点的存 储顺序与数据元素之间的逻辑关系可以不一致，数据元素之间的逻辑关系，是 由指针域来确定的。答案答案：C 计算机应用能力教学部61Point6：二叉树：二叉树 1、树树 树是一种简单的非线性结构，所有元素 间具有明显的层次特性。在树结构中，每一个结点只有一个前
44、件，称为父结点父结点，没有前件的结点只有一个，称 为树的根结点根结点，简称树的根。每一个结点可以有多个后件，称为该结点的子结点。没有后 件的结点称为叶子叶子结点结点。在树结构中，一个结点所拥有的后件的个数称为该结点的度，所有结点中最大的度称 为树的度树的度。树的最大层次称为树的深度树的深度。2、二叉树二叉树：度为 2 的树就是二叉树。(1)二叉树的特点：非空二叉树只有一个根结点；每一个结点最多有两棵子树，且 分别称为该结点的左子树与右子树。计算机应用能力教学部62 3、二叉树的性质 (1)在二叉树中，第 i 层的结点总数不超过 2 i-1(i 1)。(2)深度为 h 的二叉树总计最多有 2 h
45、-1个结点(h1)，最少有 h 个结点。(3)对于任意一棵二叉树，如果其叶子结点数为 N0，而度数为 2 的结点总数为 N2，则 N0=N2+1，即叶子数总比度为 2 的节点数多 1。(4)具有 n 个结点的完全二叉树的深度为 int(log 2n)+1。计算机应用能力教学部63 3、完全二叉树完全二叉树和满二叉树满二叉树 (1)完全二叉树：只有最下面的两层结点度小于 2，并且最下面一层的结点都集中在该 层最左边的若干位置的二叉树；(2)满二叉树：除了叶子结点外每一个结点都有左右子女且叶子结点都处在最低层的二 叉树。4、遍历遍历是对树的一种最基本的运算。所谓遍历二叉树，就是按一定的规则和顺序走
46、遍二叉 树的所有结点，使每一个结点都被访问一次，而且只被访问一次。由于二叉树是非线性结 构，因此，树的遍历实质上是将二叉树的各个结点转换成为一个线性序列来表示。计算机应用能力教学部64 设 L、D、R 分别表示遍历左子树、访问根结点和遍历右子树，则对一棵二叉树的遍历有三种情 况：DLR(称为先根次序遍历，简称前序遍历)，LDR(称为中根次序遍历，简称中序遍历)，LRD(称为后根次序遍历，简称后序遍历)。(1)前序遍历：访问根；按先序遍历左子树；按先序遍历右子树。(2)中序遍历：按中序遍历左予树；访问根；按中序遍历右子树。(3)后序遍历：按后序遍历左予树；按后序遍历右子树；访问根。计算机应用能力
47、教学部65【真题 1】某二叉树有某二叉树有 5 个度为个度为 2 的结点，则该的结点，则该二叉树中的叶子结点数是二叉树中的叶子结点数是 _。（2009 年 3 月）A)6 B)4 C)10 D)8 解析解析：根据二叉树的性质，在任意二叉树中，度为 0 的结点(即叶子结点)总是 比度为 2 的结点多一个。答案答案：A 计算机应用能力教学部66【真题 2】深度为深度为 5 的满二叉树有的满二叉树有_【2】_个叶子节点。个叶子节点。（2008 年 4 月）解析解析：在二叉树中，深度为 N 的满二叉树的叶子结点数目为：2(N-1)答案答案：16 计算机应用能力教学部67【真题 3】一棵二叉树中共有一棵
48、二叉树中共有 70 个叶子节点与个叶子节点与 80 个度为个度为 1 的结点，则该二叉树的结点，则该二叉树 总结点数为总结点数为_。（2007 年 9 月）A)229 B)231 C)219 D)221 解析解析：在二叉树中，叶子结点个数为 n 0，则度为 2 的结点数 n 2=n 0-1。本题 中叶子结点的个数为 70，所以度为 2 的结点个数为 69，因而总结点数=叶子 结点数+度为 1 的结点数+度为 2 的结点数=70+80+69=219。答案答案：C 计算机应用能力教学部68【真题 4】某二叉树中有某二叉树中有 n 个度为个度为 2 的结点，则的结点，则该二叉树中的叶子结点数为该二叉
49、树中的叶子结点数为 _。（2007 年 3 月）A)2n B)n/2 C)n+l D)n-1 解析解析：在任意一棵二叉树中，度为 0 的结点(即叶子结点)总是比度为 2 的结点 多一个。所以该二叉树的叶子结点数等于 n+1。答案答案：C 计算机应用能力教学部69【真题 5】在深度为在深度为 7 的满二叉树中，度的满二叉树中，度为为 2 的结点个数为的结点个数为_【1】_。（2007 年 3 月）解析解析：一棵深度为 7 的满二叉树，其结点个数为 2 7-1=127，又因为叶子结点 个数 N 0 和度为 2 的结点个数 N 2 的关系是 N 0=N 2+1，所以总结点数是 N 0+N 2=2N
50、2+1=127，所以度为 2 的结点个数等于 63。答案答案：63 计算机应用能力教学部70【真题 6】在深度为在深度为 7 的满二叉树中，叶子结点的满二叉树中，叶子结点的个数为的个数为_。（2006 年 4 月）A)64 B)63 C)32 D)31 解析解析：在二叉树的第 k 层上，最多有 2(k-1)(k1)个结点。对于满二叉树来 说，每一层上的结点数都达到最大值，即在满二叉树的第 k 层上有 2(k-1)个结 点。因此，在深度为 7 的满二叉树中，所有叶子结点在第 7 层上，即其结点数 为 2(k-1)=2 6 =64。答案答案：A 计算机应用能力教学部71【真题 7】一棵二叉树第六层
