NOIP初赛复习（九）数据结构基础.docx

《NOIP初赛复习（九）数据结构基础.docx》由会员分享，可在线阅读，更多相关《NOIP初赛复习（九）数据结构基础.docx（32页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、NOIP初赛复习（九）数据结构基础基本信息：矩阵文本题 *姓名：_学校：_班级:_数据结构是计算机存储、组织数据的方式，是指相互之间存在一种或多种特定关系的数据元素的集合。许多算法的精髓就是在于选择了合适的数据结构作为基础。数据结构根据数据元素之间关系的不同特性，通常可以归类为下列四类基本结构：（1）集合结构：元素间关系仅是同属一个集合。（2）线性结构：元素间存在一对一的关系。（3）树形结构：元素间的关系是一对多的关系。（4）图形结构：元素间的关系是多对多的关系。一、线性结构线性结构是N个数据元素构成的有限序列。线性结构存储方式分为顺序存储结构和链式存储结构两种。顺序存储结构平时使用的数组就是

2、这种结构，比如Pascal：a:1.100 of longint; C+：int a100。当需要在顺序存储的线性表中插入一个数据元素时，需要顺序移动后续的元素以“腾”出某个合适的位置放置新元素。链式存储结构链式存储结构，又叫链接存储结构。在计算机中用一组任意的存储单元存储线性表的数据元素(这组存储单元可以是连续的,也可以是不连续的).线性表线性表是具有相同数据类型的n (n=0)个数据元素的有限序列。其中n为表长，当n=0 时该线性表是一个空表。若用L命名线性表，则其一般表示如下：L=(a1, a2, ., ai, ai+1, ., an)其中，a1是唯一的“第一个”数据元素，又称为表头元素

3、；an是唯一的“最后一个”数据元素，又称为表尾元素。除第一个元素外，每个元素有且仅有一个直接前驱。除最后一个元素外，每个元素有且仅有一个直接后继。以上就是线性表的逻辑特性，这种线性有序的逻辑结构正是线性表名字的由来。线性表的特点： 表中元素的个数有限。 表中元素具有逻辑上的顺序性，在序列中各元素排序有其先后次序。 表中元素都是数据元素，每一个表元素都是单个元素。 表中元素的数据类型都相同。这意味着每一个表元素占有相同数量的存储空间。 表中元素具有抽象性。就是说，仅讨论表元素之间的逻辑关系，不考虑元素究竟表示什么内容。顺序表线性表的顺序存储又称为顺序表。它是用一组地址连续的存储单元，依次存储线性

4、表中的数据元素，从而使得逻辑上相邻的两个元素在物理位置上也相邻。第1个元素存储在线性表的起始位置，第i个元素的存储位置后面紧接着存储的是第i+1个元素。因此，顺序表的特点是表中元素的逻辑顺序与其物理顺序相同。顺序表最主要的特点是可以进行随机访问特性，即通过首地址和元素序号可以在O(1)的时间内找到指定的元素。顺序表的存储密度高，每个结点只存储数据元素。顺序表逻辑上相邻的元素物理上也相邻，所以，插入和删除操作需要移动大量元素。单链表线性表的链式存储又称为单链表，它是指通过一组任意的存储单元来存储线性表中的数据元素。为了建立起数据元素之间的线性关系，对每个链表结点，除了存放元素自身的信息之外，还需

5、要存放一个指向其后继的指针。通常用“头指针”来标识一个单链表，如单链表L，头指针为“NULL”时则表示一个空表。此外，为了操作上的方便，在单链表第一个结点之前附加一个结点，称为头结点。头结点的数据域可以不设任何信息，但可以记录表长等信息。头结点的指针域指向线性表的第一个元素结点。头结点和头指针的区分：不管带不带头结点，头指针始终指向链表的第一个结点，而头结点是带头结点链表中的第一个结点，结点内通常不存储信息。双链表单链表结点中只有一个指向其后继的指针，这使得单链表只能从头结点依次顺序地向后遍历。若要访问某个结点的前驱结点（插入、删除操作时），只能从头开始遍历，访问后继结点的时间复杂度为O(1)

6、，访问前驱结点的时间复杂度为O(n)。为了克服单链表的上述缺点，引入了双链表，双链表结点中有两个指针prior和next，分别指向其前驱结点和后继结点循环链表循环链表和链表的区别在于，表中最后一个结点的指针不是NULL，而改为指向头结点，从而整个链表形成一个环。栈(Stack)栈(Stack)：只允许在一端进行插入或删除操作的线性表。首先栈是一种线性表，但是限定这种线性表只能在某一端进行插入和删除操作。栈顶(top)：线性表允许进行插入和删除的那一端。栈底(bottom)：固定的，不允许进行插入和删除的另一端。空栈：不含任何元素的空表。假设某个栈S= (a1, a2, a3, a4, a5)，

7、如图所示，则a1为栈底元素，a5为栈顶元素。由于栈只能在栈顶进行插入和删除操作，故进栈次序依次为a1、a2、a3、a4、a5，而出栈次序为a5、a4、a3、a2、al。由此可见，栈的一个明显的操作特性可以概括为后进先出(Last In First Out, LIFO)，故又称为后进先出的线性表。队列(Queue)队列(Queue)：队列简称队，也是一种操作受限的线性表，只允许在表的一端进行插入，而在表的另一端进行删除。向队列中插入元素称为入队或进队；删除元素称为出队或离队。这和我们日常生活中的排队是一致的，最早排队的也是最早离队的。其操作的特性是先进先出 (First In First Out

8、, FIFO)，故又称为先进先出的线性表队头(Front)：允许删除的一端，又称为队首。队尾(Rear)：允许插入的一端。空队列：不含任何元素的空表。二、树型结构树t是一个非空的有限元素的集合，其中一个元素为根，余下的元素组成t的子树。在画一棵树时，每个元素都代表一个节点。树根在上面，其子树画在下面。根又叫做根结点，一棵树有且只有一个根结点。根结点有时候也称为祖先。既然有祖先，理所当然就有父亲和儿子。比如上图这棵树中 3 号结点是 1、6 和 7 号结点的父亲，1、6 和 7 号结点是 3 号结点的儿子。同时 1 号结点又是 2 号结点的父亲，2 号结点是 1 号结点的儿子，2 号结点与 4、

9、5 号结点关系也显而易见了。父亲结点简称为父结点，儿子结点简称为子结点。2 号结点既是父结点也是子结点，它是 1 号结点的子结点，同时也是 4 和 5 号结点的父结点。另外如果一个结点没有子结点（即没有儿子）那么这个结点称为叶结点，例如 4、5、6 和 7 号结点都是叶结点。没有父结点（即没有父亲）的结点称为根结点（祖先）。如果一个结点既不是根结点也不是叶结点则称为内部结点。最后每个结点还有深度，比如 5 号结点的深度是 4。二叉树二叉树是一种特殊的树。二叉树的特点是每个结点最多有两个儿子，左边的叫做左儿子，右边的叫做右儿子，或者说每个结点最多有两棵子树。更加严格的递归定义是：二叉树要么为空，

10、要么由根结点、左子树和右子树组成，而左子树和右子树分别是一棵二叉树。二叉树的特点:1.每个节点最多有两棵子树,所以二叉树中不存在度大于2的结点。注意不是只有两棵子树,而是最多有两棵子树,所以说没有子树或者有一颗子树也是可以的.2.左子树和右子树是有顺序的,次序不能任意颠倒。3.即使树中的某一个节点只有一棵子树,也要区分他是左子树还是右子树.二叉树的五种基本形态:二叉树中还有连两种特殊的二叉树叫做满二叉树和完全二叉树。满二叉树如果二叉树中每个内部结点都有两个儿子，这样的二叉树叫做满二叉树。或者说满二叉树所有的叶结点都有同样的深度。满二叉树的严格的定义是一棵深度为 h 且有 2h-1 个结点的二叉

11、树。满二叉树的特点:(1) 满二叉树的叶子只能出现在最下一层,出现在其它层就不可能达成平衡.(2) 非叶子节点的度一定是2.(3) 在同样深度的热茶树中,满二叉树的节点个数最多,叶子数最多.完全二叉树如果一棵二叉树除了最右边位置上一个或者几个叶结点缺少外其它是丰满的，那么这样的二叉树就是完全二叉树。严格的定义是：若设二叉树的高度为 h，除第 h 层外，其它各层 (1h-1) 的结点数都达到最大个数，第 h 层从右向左连续缺若干结点，就是完全二叉树。也就是说如果一个结点有右子结点，那么它一定也有左子结点。例如下面这三棵树都是完全二叉树。其实你可以将满二叉树理解成是一种特殊的或者极其完美的完全二叉

12、树。完全二叉树的特点:(1) 完全二叉树的叶子节点只能出现在最下面的两层.(2) 最下层的叶子一定集中在左部的连续位置.(3) 倒数二层,若有叶子节点,则一定在右部的连续位置(4) 如果结点度为1,则该结点只有有孩子,即不存在只有右子树的情况.(5) 同样结点数的二叉树,完全二叉树的深度最小.二叉树的性质性质1：在二叉树的第 i 层上有至多 2(i-1) 个结点 (i = 1).第一层是根节点,只有一个,所以是 2(1-1) = 20 = 1.第二层有两个,2(2-1) = 21 = 2.第三层有四个,2(3-1) = 22 = 4.性质2：深度为 k 的二叉树至多有 2k - 1 个节点(k

13、 = 1).如果有一层,至多有1 = 21 -1 个结点.如果有两层,至多有1 + 2 = 22 -1个结点.如果有三层,至多有1 + 2 + 4 = 23 -1个结点.二叉树的遍历前序遍历：首先访问根结点然后遍历左子树，最后遍历右子树。在遍历左、右子树时，仍然先访问根结点，然后遍历左子树，最后遍历右子树。中序遍历：首先遍历左子树，然后访问根结点，最后遍历右子树。在遍历左、右子树时，仍然先遍历左子树，再访问根结点，最后遍历右子树。后序遍历：首先遍历左子树，然后遍历右子树，最后访问根结点，在遍历左、右子树时，仍然先遍历左子树，然后遍历右子树，最后遍历根结点。三、图形结构图（Graph）是由顶点的

14、有穷非空集合和顶点之间边的集合组成，通常表示为：G(V,E)其中，G 表示一个图， V 是图 G 中顶点的集合，E 是图 G 中边的集合。无边图：若顶点Vi到Vj之间的边没有方向，则称这条边为无项边（Edge），用序偶对(Vi,Vj)标示。对于下图无向图G1来说，G1=(V1, E1)，其中顶点集合V1=A,B,C,D；边集合E1=(A,B),(B,C),(C,D),(D,A),(A,C):有向图：若从顶点Vi到Vj的边是有方向的，则成这条边为有向边，也称为弧（Arc）。用有序对（Vi，Vj）标示，Vi称为弧尾，Vj称为弧头。如果任意两条边之间都是有向的，则称该图为有向图。有向图G2中，G2=

15、（V2,E2），顶点集合（A,B,C,D）,弧集合E2=,B,A,.简单图: 在图中，若不存在顶点到其自身的边，且同一条边不重复出现，则称这样的图为简单图。 无向完全图: 在无向图中，如果任意两个顶点之间都存在边，则称该图为无向完全图。有向完全图: 在有向图中，如果任意两个顶点之间都存在方向互为相反的两条弧，则称该图为有向完全图。- 对于无向图 G = (V,E)，如果边 (v,v) E，则称顶点 v 和 v 互为邻接点（Adjacent），即 v 和 v 相邻接。边 (v,v) 依附（incident）于顶点 v 和 v，或者说 (v,v) 与顶点 v 和 v 相关联。顶点 v 的度（Deg

16、ree）是和 v 相关联的边的数目，记为 TD(v)。边数是各顶点度数和的一半。- 对于有向图G = (V,E)，如果弧 E，则称顶点 v 邻接到顶点 v，顶点 v 邻接自顶点 v。弧 和顶点 v 和 v 相关联。以顶点 v 为头的弧的数目称为 v 的入度（InDegree），记为 ID(v)；以 v 为尾的弧的数目称为 v 的出度（OutDegree），记为 OD(v)；顶点 v 的度为 TD(v) = ID(v) + OD(v)。弧数 = 各顶点入度之和 = 各顶点出度之和。- 无向图 G = (V,E) 中从顶点 v 到顶点 v 的路径（Path）是一个顶点序列 (v = v(i,0),

17、v(i,1),.,v(i,m) = v )，其中(v(i,j-1),v(i,j) E， 1 j m。- 路径的长度是路径上的边或弧的数目。图的存储结构图的邻接矩阵（Adjacency Matrix）存储方式是用两个数组来表示图。一个一维数组存储图中顶点信息，一个二维数组（称为邻接矩阵）存储图中的边或弧的信息。图的邻接表（Ad-jacency List）：使用数组与链表相结合的存储方式。邻接矩阵对于边数相对顶点较少的图，存在对存储空间的极大浪费的现象。因此这种存储方式对于稀疏图来说不是很合适。借鉴于线性表的解决方案，可以考虑对边或弧使用链式存储的方式来避免空间浪费的问题。1. 图中顶点用一个一维

18、数组存储，当然，顶点也可以用单链表来存储，不过数组可以较容易地读取顶点信息，更加方便。另外，对于顶点数组中，每个数据元素还需要存储指向第一个邻接点的指针，以便于查找该顶点的边信息。 2. 图中每个顶点vi的所有邻接点构成一个线性表，由于邻接点的个数不定，所以用单链表存储，无向图称为顶点vi的边表，有向图则称为顶点vi作为弧尾的出边表。图的遍历图的遍历：从图中某一顶点出发访遍图中其余顶点，且使每一个顶点仅被访问一次，这一过程就叫做图的遍历（Traversing Graph）。深度优先遍历（Depth_First_Search），也有称为深度优先搜索，简称为DFS。 它的基本思想是：从图G的某个顶

19、点v0出发，访问v0，然后选择一个与v0相邻且没被访问过的顶点vi访问，再从vi出发选择一个与vi相邻且未被访问的顶点vj进行访问，依次继续。如果当前被访问过的顶点的所有邻接顶点都已被访问，则退回到已被访问的顶点序列中最后一个拥有未被访问的相邻顶点的顶点w，从w出发按同样的方法向前遍历，直到图中所有顶点都被访问。广度优先遍历（Breadth_First_Search），又称为广度优先搜索，简称BFS。它的基本思想是：首先访问初始点vi，并将其标记为已访问过，接着访问vi的所有未被访问过的邻接点vi1,vi2, vi t，并均标记已访问过，然后再按照vi1,vi2, vi t的次序，访问每一个顶

20、点的所有未被访问过的邻接点，并均标记为已访问过，依次类推，直到图中所有和初始点vi有路径相通的顶点都被访问过为止。练习题目1、一个向量第一个元素的存储地址是100,每个元素的长度是2,则第5个元素的地址是( ) 。 单选题 *110108(正确答案)1001092、设有一个含有13个元素的Hash表(012),Hash函数是:H(key)=key% 13,其中% 是求余数运算。用线性探查法解决冲突,则对于序列(2、31、20、19、18、53、27),18应放在第几号格中( ) 。 单选题 *59(正确答案)403、在一个有向图中,所有顶点的入度之和等于所有顶点的出度之和的( ) 倍。 单选题

21、 *1/21(正确答案)244、设栈S和队列Q的初始状态为空,元素e1,e2,e3,e4,e5,e6依次通过栈S,一个元素出栈后即进入队列Q,若出队的顺序为e2,e4,e3,e6,e5,e1,则栈S的容量至少应该为( ) 。 单选题 *23(正确答案)455、若已知一个栈的入栈顺序是1，2，3，n，其输出序列为P1，P2，P3，Pn，若P1是n，则Pi是( ) 单选题 *in-1n-i+1(正确答案)不确定6、以下哪一个不是栈的基本运算( ) 单选题 *删除栈顶元素删除栈底的元素(正确答案)判断栈是否为空将栈置为空栈7、无向图G=(V，E)，其中V=a,b,c,d,e,f，E=(a,b),(a

22、,e),(a,c),(b,e),(c,f),(f,d),(e,d)对该图进行深度优先遍历，得到的顶点序列正确的是( )。 单选题 *a,b,e,c,d,fa,c,f,e,b,da,e,b,c,f,da,b,e,d,f,c(正确答案)8、线性表若采用链表存储结构，要求内存中可用存贮单元地址（） 单选题 *必须连续部分地址必须连续一定不连续连续不连续均可(正确答案)9、下列叙述中，正确的是（） 单选题 *线性表的线性存贮结构优于链表存贮结构队列的操作方式是先进后出栈的操作方式是先进先出二维数组是指它的每个数据元素为一个线性表的线性表(正确答案)10、表达式(1+34)*5-56/7 的后缀表达式为

23、（ ）。 单选题 *1+34*5-56/7-*+1 34 5/56 71 34 +5*56 7/-(正确答案)1 34 5* +56 7/-1 34+5 56 7-*/11、已知元素（8，25，14，87，51，90，6，19，20），问这些元素以怎样的顺序进入栈，才能使出栈的顺序满足：8在51前面；90在87的后面；20在14的后面；25在6的前面；19在90的后面。（ ）。（题意是全部进栈，再依次出栈） 单选题 *20，6，8，51，90，25，14，19，8751，6，19，20，14，8，87，90，2519，20，90，7，6，25，51，14，876，25，51，8，20，19，9

24、0，87，14(正确答案)25，6，8，51，87，90，19，14，2012、完全二叉树的结点个数为4 * N + 3，则它的叶结点个数为（ ）。 单选题 *2 * N2 * N - 12 * N + 12 * N - 22 * N + 2(正确答案)历年真题1、链表不具备的特点是（ ）。 单选题 *可随机访问任何一个元素(正确答案)插入、删除操作不需要移动元素无需事先估计存储空间大小所需存储空间与存储元素个数成正比2、线性表若采用链表存储结构，要求内存中可用存储单元地址（ ）。 单选题 *必须连续部分地址必须连续一定不连续连续不连续均可(正确答案)3、链表不具有的特点是（ ）。 单选题 *

25、不必事先估计存储空间可随机访问任一元素(正确答案)插入删除不需要移动元素所需空间与线性表长度成正比4、（ ）是一种先进先出的线性表。 单选题 *栈队列(正确答案)哈希表（散列表）二叉树5、某个车站呈狭长形，宽度只能容下一台车，并且只有一个出入口。已知某时刻该车站状态为空，从这一时刻开始的出入记录为：“进，出，进，进，出，进，进，进，出，出，进，出”。假设车辆入站的顺序为 1，2，3，则车辆出站的顺序为（ ）。 单选题 *1, 2, 3, 4, 51, 2, 4, 5, 71, 3, 5, 4, 61, 3, 5, 6, 71, 3, 6, 5, 7(正确答案)6、设栈 S的初始状态为空，元素a

26、, b, c, d, e, f, g依次入栈，以下出栈序列不可能出现的是（ ）。 单选题 *a, b, c, e, d, f, gb, c, a, f, e, g, da, e, d, c, b, f, gd, c, f, e, b, a, gg, e, f, d, c, b, a(正确答案)7、设栈S的初始状态为空，元素a, b, c, d, e 依次入栈，以下出栈序列不可能出现的有（ ）。 单选题 *a, b, c, e, db, c, a, e, da, e, c, b, d(正确答案)d, c, e, b, a8、地面上有标号为 A、B、C 的 3 根细柱，在 A 柱上放有 10 个直

27、径相同中间有孔的圆盘，从上到下依次编号为 1，2，3，将 A 柱上的部分盘子经过 B 柱移入 C 柱，也可以在 B 柱上暂存。如果 B 柱上的操作记录为：“进，进，出，进，进，出，出，进，进，出，进，出，出”。那么，在 C 柱上，从下到上的盘子的编号为（ ）。 单选题 *2 4 3 6 5 72 4 1 2 5 72 4 3 1 7 62 4 3 6 7 5(正确答案)9、设栈 S 的初始状态为空，元素 a，b，c，d，e，f 依次入栈 S，出栈的序列为 b，d，f，e，c，a，则栈 S 的容量至少应该是（ ）。 单选题 *654(正确答案)310、有六个元素 FEDCBA 从左至右依次顺序进

28、栈，在进栈过程中会有元素被弹出栈。问下列哪一个不可能是合法的出栈序列？ 单选题 *EDCFABDECABFCDFEBA(正确答案)BCDAEF11、如果一个栈初始时为空，且当前栈中的元素从栈底到栈顶依次为 a, b, c（如右图所示），另有元素 d 已经出栈，则可能的入栈顺序是（ ）。单选题 *a, d, c, bb, a, c, da, c, b, dd, a, b, c(正确答案)12、下图中所使用的数据结构是（）。单选题 *哈希表栈(正确答案)队列二叉树13、今有一空栈 S，对下列待进栈的数据元素序列 a,b,c,d,e,f 依次进行进栈，进栈，出栈，进栈，进栈，出栈的操作，则此操作完成

29、后，栈 S 的栈顶元素为（ ）。 单选题 *fc(正确答案)ab14、在程序运行过程中，如果递归调用的层数过多，会因为（ ）引发错误。 单选题 *系统分配的栈空间溢出(正确答案)系统分配的堆空间溢出系统分配的队列空间溢出系统分配的链表空间溢出15、递归过程或函数调用时，处理参数和返回地址，通常使用一种称为（ ）的数据结构。 单选题 *队列多维数组线性表栈(正确答案)16、满二叉树的叶结点个数为 N，则它的结点总数为（ ）。 单选题 *N2 * N2 * N 1(正确答案)2 * N + 1.2N 117、在关系数据库中，存放在数据库中的数据的逻辑结构以（ ）为主。 单选题 *二叉树多叉树哈希表

30、二维表(正确答案)18、完全二叉树共有 2*N-1 个结点，则它的叶节点数是（ ）。 单选题 *N-1N(正确答案)2*N.2N-119、设 T 是一棵有 n 个顶点的树，下列说法不正确的是（ ）。 单选题 *T 有 n 条边(正确答案)T 是连通的T 是无环的T 有 n-1 条边20、二叉树T的宽度优先遍历序列为A B C D E F G H I，已知A是C的父结点，D 是G 的父结点，F 是I 的父结点，树中所有结点的最大深度为3（根结点深度设为0），可知F的父结点是（ ）。 单选题 *无法确定BC(正确答案)DE21、已知一棵二叉树有 10 个节点，则其中至多有（ ）个节点有 2 个子节

31、点。 单选题 *4(正确答案)56722、一棵具有 5 层的满二叉树中结点数为（ ）。 单选题 *31(正确答案)32331623、如果根的高度为 1，具有 61 个结点的完全二叉树的高度为（ ）。 单选题 *56(正确答案)7824、一棵二叉树如右图所示，若采用顺序存储结构，即用一维数组元素存储该二叉树中的结点（根结点的下标为 1，若某结点的下标为 i ，则其左孩子位于下标 2i 处、右孩子位于下标(2i+1)处），则图中所有结点的最大下标为（ ）。单选题 *6101215(正确答案)24、前序遍历序列与中序遍历序列相同的二叉树为（ ）。 单选题 *根结点无左子树的二叉树根结点无右子树的二叉

32、树只有根结点的二叉树或非叶子结点只有左子树的二叉树只有根结点的二叉树或非叶子结点只有右子树的二叉树(正确答案)25、二叉树的（）第一个访问的节点是根节点。 单选题 *先序遍历(正确答案)中序遍历后序遍历以上都是26、如果一棵二叉树的中序遍历是 BAC，那么它的先序遍历不可能是（ ）。 单选题 *ABCCBAACB(正确答案)BAC27、一个包含 n 个分支结点（非叶结点）的非空二叉树，它的叶结点数目最多为（）。 单选题 *2n + 12n - 1n - 1n + 1(正确答案)28、二叉树 T，已知其先根遍历是 1 2 4 3 5 7 6（数字为结点的编号，以下同），中根遍历是 2 4 1 5

33、 7 3 6，则该二叉树的后根遍历是（ ）。 单选题 *4 2 5 7 6 3 14 2 7 5 6 3 1(正确答案)7 4 2 5 6 3 14 2 7 6 5 3 129、已知 7 个结点的二叉树的先根遍历是 1 2 4 5 6 3 7（数字为结点的编号，以下同），中根遍历是 4 2 6 5 1 7 3，则该二叉树的后根遍历是（ ）。 单选题 *4 6 5 2 7 3 1(正确答案)4 6 5 2 1 3 74 2 3 1 5 4 74 6 5 3 1 7 230、已知 6 个结点的二叉树的先根遍历是 1 2 3 4 5 6（数字为结点的编号，以下同），后根遍历是3 2 5 6 4 1，

34、则该二叉树的可能的中根遍历是（ ）。 单选题 *3 2 1 4 6 53 2 1 5 4 6(正确答案)2 1 3 5 4 62 3 1 4 6 531、二叉树 T，已知其前序遍历序列为 1 2 4 3 5 7 6，中序遍历序列为 4 2 1 5 7 3 6，则其后序遍历序列为（ ）。 单选题 *4 2 5 7 6 3 14 2 7 5 6 3 1(正确答案)4 2 7 5 3 6 14 7 2 3 5 6 14 5 2 6 3 7 132、在下图中，从顶点（ ）出发存在一条路径可以遍历图中的每条边一次，而且仅遍历一次。单选题 *A 点B 点C 点D 点E 点(正确答案)33、平面上有五个点

35、A(5, 3), B(3, 5), C(2, 1), D(3, 3), E(5, 1)。以这五点作为完全图 G 的顶点，每两点之间的直线距离是图 G 中对应边的权值。以下哪条边不是图 G 的最小生成树中的边（ ）。 单选题 *ADBDCDDE(正确答案)EA34、已知 n 个顶点的有向图，若该图是强连通的（从所有顶点都存在路径到达其他顶点）， 则该图中最少有多少条有向边？ 单选题 *n(正确答案)n+1n-1n*(n-1)35、无向完全图是图中每对顶点之间都恰有一条边的简单图。已知无向完全图 G有 7个顶点，则它共有（ ）条边。 单选题 *721(正确答案)424936、对一个有向图而言，如果

36、每个节点都存在到达其他任何节点的路径，那么就称它是强连通的。例如，右图就是一个强连通图。事实上，在删掉边（ ）后，它依然是强连通的。单选题 *a(正确答案)bcd37、在一个无向图中，如果任意两点之间都存在路径相连，则称其为连通图。下图是一个有4 个顶点、6 条边的连通图。若要使它不再是连通图，至少要删去其中的（ ）条边。单选题 *123(正确答案)438、以 A0 作为起点，对下面的无向图进行深度优先遍历时，遍历顺序不可能是（ ）。单选题 *A0, A1, A2, A3(正确答案)A0, A1, A3, A2A0, A2, A1, A3A0, A3, A1, A239、有向图中每个顶点的度等

37、于该顶点的（ ）。 单选题 *入度出度入度与出度之和(正确答案)入度与出度之差40、6 个顶点的连通图的最小生成树，其边数为（ ）。 单选题 *65(正确答案)7441、Lucia 和她的朋友以及朋友的朋友都在某社交网站上注册了账号。下图是他们之间的关系图，两个人之间有边相连代表这两个人是朋友，没有边相连代表不是朋友。这个社交网站的规则是：如果某人 A 向他（她）的朋友 B 分享了某张照片，那么 B 就可以对该照片进行评论；如果 B 评论了该照片，那么他（她）的所有朋友都可以看见这个评论以及被评论的照片，但是不能对该照片进行评论（除非 A 也向他（她）分享了该照片）。现在 Lucia 已经上传

38、了一张照片，但是她不想让 Jacob 看见这张照片，那么她可以向以下朋友（ ）分享该照片。单选题 *Dana, Michael, Eve(正确答案)Dana, Eve, MonicaMichael, Eve, JacobMicheal, Peter, Monica42、设简单无向图 G 有 16 条边且每个顶点的度数都是 2，则图 G 有（）个顶点。 单选题 *1012816(正确答案)43、约定二叉树的根节点高度为 1。（1）一棵结点数为 2016 的二叉树最少有_个叶子结点； 填空题 *_(答案：1)（2）一棵结点数为 2016 的二叉树最小的高度值是_。 填空题 *_(答案：11)44、一棵结点数为 2015 的二叉树最多有_个叶子结点。 填空题 *_(答案：1008)45、如图所示，图中每条边上的数字表示该边的长度，则从A到E 的最短距离是_。填空题 *_(答案：11)46、有 6 个城市，任何两个城市之间都有一条道路连接，6 个城市两两之间的距离如下表所示，则城市 1 到城市 6 的最短距离为_。填空题 *_(答案：7)47、广度优先搜索时，需要用到的数据结构是（ ）。 单选题 *链表队列(正确答案)栈散列表