算法与基本数据结构1

算法与数据结构公共根底第一局部本章考核内容约占13%，主要包括一下几个方面：算法复杂度栈、队列、线性链表的根本概念树的结点计算和遍历排序的最坏次数计算考点1算法的根本概念1.算法是指解题方案的准确而完整的描述。对于一个问题，如果可以通过一个计算机程序，在有限的存储空间内运行有限的时间而得到正确的结果，那么称这个问题是可解的。2.算法特征：1)可行性2)确定性3)有穷性：即算法必须能在执行有限个步骤之后终止4)拥有足够的情报考点1算法的根本概念【2008年4月】：算法的有穷性是指〔〕A〕算法程序的运行时间是有限的B〕算法程序所处理的数据量是有限的C〕算法程序的长度是有限的D〕算法只能被有限的用户使用答案A考点1算法的根本概念3.算法的根本元素一个算法通常由两种根本要素组成：一是对数据对象的运算和操作；二是算法的控制结构。一般的计算机系统中，根本运算和操作包括以下4类：①算术运算：加、减、乘、除等运算；②逻辑运算：与、或、非等运算；③关系运算：等于、不等于、大于、小于等运算；④数据传输：赋值、输入、输出等操作。考点1算法的根本概念3.算法的根本元素算法的控制结构算法各操作之间的执行顺序称为算法的控制结构。算法的控制结构包括：顺序、选择〔分支〕和循环。考点1算法的根本概念4.算法设计的根本方法计算机解题的过程实际上是在实施某种算法,这种算法称为计算机算法。①列举法；②归纳法；③递推；④递归；⑤减半递推技术；⑥回溯法。考点2算法的复杂度☆算法的复杂度包括算法时间复杂度和算法空间复杂度。1.算法时间复杂度算法时间复杂度是指执行算法所需要的计算工作量。在度量一个算法的工作量时，用算法在执行过程中所需根本运算的执行次数来度量算法的工作量。分析算法工作量的方法：平均性态和最坏情况复杂性。考点2算法的复杂度☆2.算法空间复杂度一个算法的空间复杂度，一般是指执行这个算法所需要的内存空间大小。一个算法所占用的存储空间包括算法程序所占的空间、输入的初始数据所占的空间以及算法执行过程中所需要的额外空间。考点2算法的复杂度☆【2005年9月】：算法复杂度主要包括时间复杂度和_______复杂度。

【2006年9月】：以下表达中正确的选项是〔〕A〕一个算法的空间复杂度大，那么其时间复杂度也必定大B〕一个算法的空间复杂度大，那么其时间复杂度必定小C〕一个算法的时间复杂度大，那么其空间复杂度必定小D〕上述三种说法都不对答案D空间考点2算法的复杂度☆【2007年4月】：以下表达中正确的选项是〔〕A〕算法的效率只与问题的规模有关，而与数据的存储结构无关B〕算法的时间复杂度是指执行算法所需要的计算工作量C〕数据的逻辑结构与存储结构是一一对应的D〕算法的时间复杂度与空间复杂度一定相关答案B考点3数据结构1.根本概念1)数据：描述客观事物的数、字符以及所有能输入到计算机中并被计算机程序加工处理的符号的集合。2)数据元素：数据的根本单位，即数据集合中的个体。有时一个数据元素由假设干个数据项组成，在这种情况下，将数据元素称为记录，由记录所组成的线性表为文件。3)数据项：具有独立意义的最小数据单位。4)数据对象：具有相同特性的数据元素的集合，是数据的子集。5)结构：指数据元素之间的前后件关系。考点3数据结构1.根本概念6)数据结构：指相互关联的数据元素的集合。数据结构包含两方面信息：一是表示数据元素的信息；二是表示各数据元素之间的前后件关系。例如，描述一年四季的季节名春、夏、秋、冬，可以作为季节的数据元素；在考虑一年4个季节的顺序关系时，那么“春〞是“夏〞的前件，而“夏〞是“春〞的后件等。考点3数据结构2.数据的逻辑结构在以上所述的数据结构中，数据元素之间的前后件关系是指它们的逻辑关系，而与它们在计算机中的存储位置无关。因此，上面所述的数据结构实际上是数据的逻辑结构。1)概念：

所谓数据的逻辑结构，是指反映数据元素之间逻辑关系的数据结构。考点3数据结构2.数据的逻辑结构2)表示：图形表示：集合、线性、树、图集合线性树图考点3数据结构2.数据的逻辑结构2)表示：二元关系表示数据的逻辑结构有两个要素：一是数据元素的集合，通常记为D；二是D上的关系，它反映了D中各数据元素之间的前后件关系，通常记为R，即一个数据结构可以表示成：B=(D，R)其中B表示数据结构。为了反映D中各数据元素之间的前后件关系，一般用二元组来表示。

考点3数据结构2.数据的逻辑结构2)表示：二元关系表示例如，一年四季的数据结构可以表示成：B=〔D，R〕D={春，夏，秋，冬}R={〔春，夏〕，〔夏，秋〕〔秋，冬〕}考点4数据的存储结构1.概念：数据的逻辑结构在计算机存储空间的存放形式称为数据的存储结构。考点4数据的存储结构2.存储形式：数据元素之间的关系在计算机中有两种不同的表示方法：顺序映像和非顺序映像，并由此得到两种不同的存储结构：顺序存储结构和链式存储结构。顺序映像的特点是借助元素在存储器中的相对位置来表示数据元素之间的逻辑关系；非顺序映像的特点是借助指示元素存储地址的指针(Pointer)表示数据元素之间的逻辑关系。考点4数据的存储结构注意：

数据元素在计算机存储空间中的位置关系可能与逻辑关系不同，数据的逻辑结构可以表示成多种存储结构。采用不同的存储结构，其数据处理的效率是不同的。考点4数据的存储结构【2005年4月】：数据的存储结构是指〔〕 A〕存储在外存中的数据 B〕数据所占的存储空间量C〕数据在计算机中的顺序存储方式 D〕数据的逻辑结构在计算机中的表示答案D考点4数据的存储结构【2005年9月】以下表达中正确的选项是〔〕A〕一个逻辑数据结构只能有一种存储结构B〕数据的逻辑结构属于线性结构，存储结构属于非线性结构C〕一个逻辑数据结构可以有多种存储结构，且各种存储结构不影响数据处理的效率D〕一个逻辑数据结构可以有多种存储结构，且各种存储结构影响数据处理的效率答案D考点4数据的存储结构【2007年9月】以下表达中正确的选项是〔〕A〕数据的逻辑结构与存储结构必定是一一对应的B〕由于计算机存储空间是向量式的存储结构，因此，数据的存储结构一定是线性结构C〕程序设计语言中的数组一般是顺序存储结构，因此，利用数组只能处理线性结构D〕以上三种说法都不对答案D考点4数据的存储结构【2008年9月】以下表达中正确的选项是〔〕A〕顺序存储结构的存储一定是连续的，链式存储结构的存储空间不一定是连续的B〕顺序存储结构只针对线性结构，链式存储结构只针对非线性结构C〕顺序存储结构能存储有序表，链式存储结构不能存储有序表D〕链式存储结构比顺序存储结构节省存储空间答案A考点5线性结构与非线性结构☆根据数据结构中各数据元素之间前后件关系的复杂程度，将数据结构分为两大类型：线性结构与非线性结构。如果一个非空的数据结构满足两个条件：一是有且只有一个根结点；二是每一个结点最多有一个前件，也最多有一个后件，那么称该数据结构为线性结构。线性结构又称线性表。注意：在一个线性结构中插入或删除任何一个结点后还应是线性结构。如果一个数据结构不是线性结构，那么称为非线性结构。考点6线性表的根本概念线性表是最简单，最常用的一种数据结构。线性表由一组数据元素构成的有限序列，如一年的四个季节。线性表中结点的个数n称为线性表的长度。n=0时，称为空表。非空线性表有如下一些结构特征：有且只有一个根结点，它无前件；有且只有一个终端结点，它无后件；除根结点与终端结点外，其他所有结点有且只有一个前件，也有且只有一个后件。考点7线性表的顺序存储在计算机中存放线性表的一种最简单的方法是顺序存储，也称为顺序分配。用顺序存储结构存储的线性表称作顺序表。线性表的顺序存储结构具有以下两个根本特点：1)线性表中所有元素所占的存储空间是连续的；2)线性表中各数据元素在存储空间中是按逻辑顺序依次存放的。注意：在线性表的顺序存储结构中，其前后件两个元素在存储空间中是紧邻的，且前件元素一定存储在后件元素的前面。考点8顺序表的操作1.插入向顺序表中插入一个新结点时，由于需要保持运算的结果仍然是顺序存储，所以可能要移动一系列结点。假设顺序表中结点个数为n，在向每个位置插入的概率相等的情况下，插入一个结点平均需要移动之结点个数为n/2，算法的时间复杂度是O(n)。2.删除从顺序表中删除一个结点可能需要移动一系列结点。在等概率的情况下，删除一个结点平均需移动结点个数为(n-1)/2，算法的时间复杂度也是O(n)。考点9线性表的链式存储☆为了适应线性表的链式存储结构，计算机的内存空间被划分为多个小块，每个小块占假设干个字节，通常称这些小块为存储结点。每个存储结点分为两局部：一局部用于存储数据元素的值，称为数据域；一局部用于存储下一个数据元素的存储序号〔即存储结点的地址〕，称为指针域。考点9线性表的链式存储☆1.线性链表〔单链表〕所谓线性链表就是链式存储的线性表，其结点中只含有一个指针域，用来指出其后继结点的存储位置。线性链表的最后一个结点无后继结点，它的指针域为空(记为NULL或^)。另外还要设置表头指针head，指向线性链表的第一个结点。Head指针data1

…Data2

Datan⋀图1.3链式存储结构考点9线性表的链式存储☆1.线性链表〔单链表〕对线性链表可以进行插入、删除等运算。注意：做删除运算时改变的是被删结点的前一个结点中指针域的值。因此，假设要查找且删除某一结点，那么应在查找被删结点的同时记下它前一个结点的位置。考点9线性表的链式存储☆2.双向链表线性单链表中，每个结点只有一个指针域，由此指针只能找到后件节点。为了弥补线性单链表的这个缺点，在某些应用中，对线性单链表的每个结点设置两个指针，一个称为左指针〔Llink〕用以指向其前件结点；另一个称为右指针〔Rlink〕用以指向其后件结点，这样的线性链表称为双向链表。Head指针data1

…data2

datan⋀图1.7双向链表⋀

考点9线性表的链式存储☆3.循环链表所谓循环链表是指链表的最后一个结点的指针值指向第一个结点，整个链表形成一个环。data1

…Data2

Datan●图1.8循环链表考点9线性表的链式存储☆

注意：在链式存储结构中，存储数据结构的存储空间可以不连续，各数据结构的存储顺序与数据元素之间的逻辑关系可以不一致，而数据元素之间的逻辑关系是由指针域来确定的。

考点9线性表的链式存储☆【2005年4月】：对于线性链表的描述中正确的选项是〔〕A〕存储空间不一定是连续，且各元素的存储顺序是任意的B〕存储空间不一定是连续，且前件元素一定存储在后件元素的前面C〕存储空间必须连续，且前件元素一定存储在后件元素的前面D〕存储空间必须连续，且各元素的存储顺序是任意的答案A考点10栈及其根本运算☆1.栈的定义栈是一种特殊的线性表。栈是限定仅在表尾〔表的一端〕进行插入和删除运算的线性表，表尾称为栈顶〔top〕，表头叫做栈底〔bottom〕。栈中无元素时称为空栈。栈遵守“后进先出〞〔LIFO〕的操作原那么，具有记忆功能。a1a2⋮an栈顶栈底进栈出栈图1.9栈结构考点10栈及其根本运算☆2.栈的存储栈的既可以用顺序存储结构，也可用链式存储结构。在程序设计语言中，用一维数组S〔1：m〕作为栈的顺序存储空间，其中m为栈的最大容量。通常，栈底指针指向栈空间的低地址一端〔即数组的起始地址这一端〕。栈用链式存储结构：带链的栈称为可利用栈。考点10栈及其根本运算☆3.栈的运算1)入栈运算：指在栈顶位置插入一个新元素，其方法是先将栈顶指针top进一〔即top加1〕，然后将新元素插入到栈顶指针指向的位置。注意：栈“上溢〞错误。(栈顶指针为m)2)退栈运算：指取出栈顶元素并赋给一个指定的变量。其方法是先将栈顶元素赋给一个指定的变量，然后将栈顶指针top退一〔即top减1〕。注意：栈“下溢〞错误。(栈顶指针为0)3)读栈顶元素：指将栈顶元素赋给一个指定的变量。注意，此元素不删除栈顶元素，只是将其赋给一个变量，因此在这个运算中，栈顶指针不会改变。考点10栈及其根本运算☆【2005年4月】：以下关于栈的描述中错误的选项是〔〕A〕栈是先进后出的线性表 B〕栈只能顺序存储C〕栈具有记忆作用 D〕对栈的插入与删除操作中，不需要改变栈底指针

答案B考点10栈及其根本运算☆【2005年9月】以下关于栈的描述正确的选项是〔〕A〕在栈中只能插入元素而不能删除元素B〕在栈中只能删除元素而不能插入元素C〕栈是特殊的线性表，只能在一端插入或删除元素D〕栈是特殊的线性表，只能在一端插入元素，而在另一端删除元素

答案C考点10栈及其根本运算☆【2006年4月】：按照“后进先出〞原那么组织数据的数据结构是〔〕 A〕队列 B〕栈 C〕双向链表 D〕二叉树【2006年9月】：按“先进后出〞原那么组织数据的数据结构是___。

答案栈B考点10栈及其根本运算☆【2008年4月】：以下关于栈的表达正确的选项是〔〕A〕栈按“先进先出〞组织数据 B〕栈按“先进后出〞组织数据C〕只能在栈底插入数据 D〕不能删除数据

答案B考点10栈及其根本运算☆【2008年9月】：一个栈的初始状态为空，现将元素1、2、3、4、5、A、B、C、D、E依次入栈，然后再依次出栈，那么元素出栈的顺序是〔〕 A〕12345ABCDE B〕EDCBA54321 C〕ABCDE12345 D〕54321EDCBA答案B考点11队列及其根本运算☆1.队列的定义队列是一种特殊的线性表。队列是限定所有的插入都在表的一端进行，所有的删除都在表的另一端进行的线性表。允许插入的一端称为队尾，通常用一个称为尾指针〔rear〕的指针指向队尾元素；允许删除的一端称为队头，通常用一个称为头指针〔front〕的指针指向排头元素的前一个位置。考点11队列及其根本运算☆1.队列的定义队列遵守“先进先出〞〔FIFO〕的操作原那么，队尾指针和队头指针共同反映了队列中元素的动态变化情况。2.队列的存储队列的既可以用顺序存储结构〔一般采用循环队列〕，也可用链式存储结构。3.队列的运算入队运算、退队运算、取队头元素、检查队列是否为空、去除等。考点11队列及其根本运算☆4.循环队列〔顺序存储结构〕循环队列就是将队列存储空间的最后一个位置绕到第1个位置，形成逻辑上的环状空间，供队列循环使用。考点11队列及其根本运算☆4.循环队列入队运算：入队运算是指在循环队列的队尾参加一个新元素，rear加1。当rear=m+1时，那么置rear=1。退队运算：退队运算是指在循环队列的排头位置退出一个元素，front加1。当front=m+1时，那么置front=1。当循环队列满时有front=rear，而当循环队列为空时也有front=rear。为了那个区分队列是满还是队列空，通常需要增加一个标示s，s=0表示队列空；s=1表示队列非空。由此可得队列满与空的条件：队列空的条件为s=0；队列满的条件为s=1且front=rear。考点11队列及其根本运算☆【2008年4月】：设某循环队列的容量为50，头指针Front=5(指向队头元素的前一位置)，尾指针rear=29〔指向队尾元素〕，那么该循环队列中共有个元素。 答案24考点11队列及其根本运算☆【2008年9月】：以下表达中正确的选项是〔〕A)循环队列中有队头和队尾两个指针，因此，循环队列是非线性结构B)在循环队列中，只需要队头指针就能反映队列中元素的动态变化情况C)在循环队列中，只需要队尾指针就能反映队列中元素的动态变化情况D)循环队列中元素的个数是由队头指针和队尾指针共同决定答案D考点11队列及其根本运算☆【2005年9月】：数据结构分为逻辑结构和存储结构，循环队列属于结构。【2006年9月】：数据结构分为线性结构和非线性结构，带链的队列属于________。 答案存储线性考点11队列及其根本运算☆【2007年4月】：以下对队列的表达正确的选项是〔〕A〕队列属于非线性表 B〕队列按“先进后出〞原那么组织数据C〕队列在队尾删除数据 D〕队列按“先进先出〞原那么组织数据【2007年9月】：线性表的存储结构主要分为顺序存储结构和链式存储结构。队列是一种特殊的线性表，循环队列是队列的存储结构。 答案D顺序考点12树的根本概念1.树树是一种简单的非线性结构。在树这种结构中，所有数据元素之间的关系具有明显的层次特性。一般认为，直线连接起来的两端结点中，上端结点是前件，下端结点是后件。(具有层次关系的数据都可以用树来表示)RPEBDHKTONYXQCWZSA考点12树的根本概念2.常用术语根结点：没有前件的结点〔只有一个〕。叶子结点：没有后件的结点。父结点：每一个结点只有一个前件，该前件结点称为父结点。子结点：每一个结点可以有多个后件，它们都称为该结点的子结点。兄弟〔Sibling〕：具有相同亲结点的结点互为兄弟。结点的度〔Degree〕：一个结点所拥有的后件的个数。树的度：树中各结点的度的最大值。考点12树的根本概念2.常用术语结点的层数：根结点的层数为1，同一层上所有结点的所有子结点都在下一层。树的深度：树的最大层次。子树：以某结点的一个子结点为根构成的树称为该结点的一棵子树〔叶子结点没有子树〕。考点13二叉树及其根本性质☆1.二叉树定义二叉树是一种很有用的非线性结构。二叉树具有以下两个特点：1)非空二叉树只有一个根结点；2)每一个结点最多有两棵子树，且分别称为该结点的左子树与右子树。二叉树的5种根本形态。考点13二叉树及其根本性质☆2.二叉树的性质①在二叉树的i层上，最多有2i-1个结点〔i≥1〕。②深度为k的二叉树最多有2k-1个结点〔k≥1〕。③对任何一棵二叉树T，如果叶子结点的数为n0，度为2的结点数为n2，那么n0=n2+1。④具有n个结点的二叉树的深度至少为。考点13二叉树及其根本性质☆2.二叉树的性质【2005年4月】：某二叉树中度为2的结点有18个，那么该二叉树中有______个叶子结点。【2005年9月】：一棵二叉树第六层〔根结点为第一层〕的结点数最多为结构。【2007年4月】：某二叉树中有n个度为2的结点，那么该二叉树中的叶子结点数为〔〕。 A〕n+1 B〕n-1 C〕2n D〕n/2答案19A32考点13二叉树及其根本性质☆2.二叉树的性质【2007年9月】：一棵二叉树共有70个叶子结点与80个度为1的结点，那么该二叉树中的总结点数为〔〕。A〕219 B〕221 C〕229 D〕231答案A考点13二叉树及其根本性质☆3.满二叉树满二叉树与完全二叉树是两种特殊形态的二叉树。所谓满二叉树是指除最后一层外，每一层上的所有结点都有两个子结点。在满二叉树中，每一层上的结点数都到达最大值。考点13二叉树及其根本性质☆3.满二叉树【2006年4月】：在深度为7的满二叉树中，叶子结点的个数为〔〕。A〕32 B〕31 C〕64 D〕63【2007年4月】：在深度为7的满二叉树中，度为2的结点个数为。

【2008年4月】：深度为5的满二叉树有个叶子结点。答案16C63考点13二叉树及其根本性质☆4.完全二叉树1)定义：所谓完全二叉树是指除最后一层外，每一层上的结点数均到达最大值；在最后一层上只缺少右边的假设干结点。

考点13二叉树及其根本性质☆4.完全二叉树2)性质：①具有n个结点的完全二叉树的深度为。②设完全二叉树共有n个结点。如果从根结点开始，按层序〔每一层从左到右〕用自然1，2，…，n给结点进行编号，那么对于编号为k〔k=1，2，…，n〕的结点有以下结论：假设是k=1，那么该结点为根结点，它没有父结点；假设k>1，那么该结点的父结点编号为INT〔k/2〕；假设2k<=n，那么编号为k的结点的左子结点编号为2k，否那么该结点无左子结点；假设2k+1<=n，那么编号为k的结点的右子结点编号为2k+1；否那么该结点无右子结点考点14二叉树的存储结构二叉树的存储通常采用链接方式。每个结点除存储结点自身的信息外再设置两个指针域llink和rlink，分别指向结点的左子女和右子女，当结点的某个指针为空时，那么相应的指针值为空(NULL)。考点15二叉树的遍历☆遍历〔或称周游〕是树形结构的一种重要运算。不重复访问二叉树中的所有结点。可以按多种不同的次序遍历树形结构。二叉树的根本组成局部是：根〔N〕、左子树〔L〕、右子树〔R〕，因此可有NLR，LNR，LRN，NRL，RNL，RLN六种遍历次序。以下着重介绍前序遍历、中序遍历、后序遍历。考点15二叉树的遍历☆遍历规那么：前序遍历：先访问根结点，然后遍历左子树，最后遍历右子树。中序遍历：先访问左子树，然后遍历根结点，最后遍历右子树。后序遍历：先访问左子树，然后遍右子树，最后遍历根结点。考点15二叉树的遍历☆【2007年4月】：对以下二叉树进行前序遍历的结果为〔〕A〕DYBEAFCZXB〕YDEBFZXCAC〕ABDYECFXZD〕ABCDEFXYZ答案C考点15二叉树的遍历☆【2006年9月】：对以下二叉树进行中序遍历的结果是〔〕 A〕ACBDFEG B〕ACBDFGEC〕ABDCGEF D〕FCADBEG答案A考点15二叉树的遍历☆【2008年9月】：对以下二叉树进行中序遍历的结果是：。答案DBXEAYFZC考点15二叉树的遍历☆【2006年4月】：对如下二叉树进行后序遍历的结果为〔〕A〕ABCDEF B〕DBEAFC C〕ABDECF D〕DEBFCA答案D考点16顺序查找☆顺序查找〔顺序搜索〕是指在线性表中查找指定的元素。查找方法：从第一个元素开始，逐个比较，假设相等那么查找成功，假设找遍所有结点都不相等，那么查找失败。优点：对线性表的结点逻辑次序没有要求〔不必排序〕，对线性表的存储结构也没有要求〔顺序存储、链式存储皆可〕。缺点：平均检索长度大。

对于长度为n的有序线性表，在最坏的情况下，顺序查找需要比较n次；平均查找次数为n/2。考点16顺序查找☆【2005年4月】：对长度为n的线性表进行顺序查找，在最坏情况下所需要的比较次数为〔〕。 A〕log2n B〕n/2 C〕n D〕n+1【2006年9月】：在长度为64的有序线性表中进行顺序查找，最坏情况下需要比较的次数为〔〕。A〕63 B〕64 C〕6 D〕7

答案CB考点17二分法查找☆二分法查找是一种效率较高的查找方法。二分法查找只适用于顺序存储的有序表。☆查找方法：首先用要查找的元素与线性表中间项比较，这个中间项把线性表分成了两个子表，比较相等那么查找完成，不等那么根据比较结果确定下一步的查找应在哪一个子表中进行，如此进行下去，直到找到满足条件的结点，或确定表中没有这样的结点为止。对于长度为n的有序线性表，在最坏的情况下，二分查找需要比较次。考点17二分法查找☆【2005年9月】：能用二分法进行查找的是〔〕 A〕顺序存储的有序线性表 B〕线性链表C〕二叉链表 D〕有序线性链表【2008年9月】：在长度为n的有序线性表