数据结构习题PPT学习教案

1、会计学1数据结构习题数据结构习题第1页/共100页第2页/共100页第3页/共100页第4页/共100页第5页/共100页第6页/共100页第7页/共100页选手选手项目项目1 1 项目项目2 2 项目项目3 31 1A AB BE E2 2C CD D3 3C CE EF F4 4D DF FA A5 5B BF F求：如何在最短时间内安排所有比赛，且保证比赛不冲突。求：如何在最短时间内安排所有比赛，且保证比赛不冲突。计算机处理的对象：计算机处理的对象：6个项目个项目对象之间关系的描述：对象之间关系的描述：有冲突项目之间连一条线。有冲突项目之间连一条线。项目安排算法：项目安排算法：用尽量少的

2、颜色给图中每个结点着色，使任意两个有连线的相邻顶点涂上不同的颜色用尽量少的颜色给图中每个结点着色，使任意两个有连线的相邻顶点涂上不同的颜色ADCBEF第8页/共100页第9页/共100页第10页/共100页第11页/共100页第12页/共100页第13页/共100页第14页/共100页第15页/共100页第16页/共100页第17页/共100页第18页/共100页第19页/共100页第20页/共100页第21页/共100页第22页/共100页第23页/共100页1324不能，能不能，能第24页/共100页第25页/共100页第26页/共100页第27页/共100页第28页/共100页T第29页

3、/共100页T第30页/共100页T第31页/共100页 =(4-1)*6+(3-1)*2第32页/共100页a(b,c,d)(a,b)(d)(c,d)第33页/共100页n(n0)n(n0)个结点的树的高度个结点的树的高度: : 最低是多少？最低是多少？ 最高是多少？最高是多少？1n-1第34页/共100页n(n0)n(n0)个结点的二叉树的高度个结点的二叉树的高度: : 最低是多少？最低是多少？ 最高是多少？最高是多少？第35页/共100页第36页/共100页 有关二叉树下列说法正确的是（有关二叉树下列说法正确的是（ ）A A二叉树的度为二叉树的度为2 2 B B一棵二叉树的度可以小于一棵

4、二叉树的度可以小于2 2 C C二叉树中至少有一个结点的度为二叉树中至少有一个结点的度为2 2 D D二叉树中任何一个结点的度都为二叉树中任何一个结点的度都为2 2【南京理工大学南京理工大学 2000 2000 一一.11 .11 （1.51.5分）分）】第37页/共100页第38页/共100页第39页/共100页第40页/共100页第41页/共100页第42页/共100页1234567第43页/共100页第44页/共100页第45页/共100页第46页/共100页第47页/共100页第48页/共100页第49页/共100页第50页/共100页第51页/共100页第52页/共100页第53页/

5、共100页第54页/共100页第55页/共100页AGJBCDHIKEFLMNABGCEHFJKILMND第56页/共100页第57页/共100页第58页/共100页第59页/共100页第60页/共100页第61页/共100页第62页/共100页图中有关路径的定义是（图中有关路径的定义是（ ）。）。A A由顶点和相邻顶点序偶构成的边所形成的序列由顶点和相邻顶点序偶构成的边所形成的序列 B B由不同顶点所形成的序列由不同顶点所形成的序列C C由不同边所形成的序列由不同边所形成的序列 D D上述定义都不是上述定义都不是【北方交通大学北方交通大学 2001 2001 一一.24 .24 （2 2分）

6、分）】第63页/共100页 设无向图的顶点个数为设无向图的顶点个数为n n，则该图最多有（，则该图最多有（ ）条边。）条边。 A An-1 n-1 B Bn(n-1)/2 n(n-1)/2 C Cn(n+1)/2 n(n+1)/2 D D0 0 E EN2N2【清华大学清华大学19981998一一.5(.5(分）分）】【编者：编者： 最少多少条边？最少多少条边？】最少最少0条边条边第64页/共100页一个有一个有n n个结点的图，最少有（个结点的图，最少有（ ）个连通分量，最）个连通分量，最多有（多有（ ）个连通分量。）个连通分量。 A A0 0 B B1 1 C Cn-1 n-1 D Dn

7、n【北京邮电大学北京邮电大学 2000 2000 二二.5 .5 （20/820/8分）分）】BD第65页/共100页 要连通具有要连通具有n n个顶点的有向图，至少需要（个顶点的有向图，至少需要（ ）条边）条边。 A An-l n-l B Bn n C Cn+l n+l D D2n2n【北京航空航天大学北京航空航天大学20002000一一.6(2.6(2分）分）】第66页/共100页 G G是一个非连通无向图，共有是一个非连通无向图，共有2828条边，则该图至少条边，则该图至少有有_个顶点。个顶点。【西安电子科技大学西安电子科技大学20012001软件软件 一一.8 .8 （2 2分）分）】

8、9第67页/共100页 用邻接表存储图所用的空间大小用邻接表存储图所用的空间大小 。A.A. 与图的顶点数和边数都有关与图的顶点数和边数都有关 B.B. 只与图的边数有关只与图的边数有关C.C. 只与图的顶点数有关只与图的顶点数有关 D.D. 与边数的平方有关与边数的平方有关【北京交通大学北京交通大学20042004一一.7(2.7(2分分) )】第68页/共100页 图图G G是是n n个顶点的无向完全图，则下列说法正确的有：个顶点的无向完全图，则下列说法正确的有：A. GA. G的邻接多重表需要的邻接多重表需要n(n-1)n(n-1)个边结点和个边结点和n n个顶点结个顶点结点；点； B.

9、 GB. G的连通分量个数最少；的连通分量个数最少；C. GC. G为连通图；为连通图； D. GD. G所有顶点的度的总和为所有顶点的度的总和为n(n-1);n(n-1);【电子科技大学电子科技大学20032003一一.6(20/8.6(20/8分分) )】 第69页/共100页 在有向图的邻接表存储结构中，顶点在有向图的邻接表存储结构中，顶点v v在链表中出现在链表中出现的次数是的次数是( )( )。A. A. 顶点顶点v v的度的度 B. B. 顶点顶点v v的出度的出度 C. C. 顶点顶点v v的入度的入度 D. D. 依附于顶点依附于顶点v v的边数的边数【北京理工大学北京理工大学

10、20042004一一.7(1.7(1分分) )】第70页/共100页深度优先搜索：深度优先搜索：V1-V2-V4-V8-V5-V6-v3-v7V1-V2-V4-V8-V5-V6-v3-v7广度优先搜索广度优先搜索V1-V2-V3-V4-v5-v6-v7-v8V1-V2-V3-V4-v5-v6-v7-v8v2v4v1v5v3v6v7v8假定以邻接表存储，邻接点按编号升序排列。遍历序列如下：假定以邻接表存储，邻接点按编号升序排列。遍历序列如下：第71页/共100页0011000010010000000001110深度优先搜索：深度优先搜索：V1-V2-V3-V4-V5V1-V2-V3-V4-V5宽

11、度优先搜索：宽度优先搜索：V1-V2-V3-V4-V5V1-V2-V3-V4-V5第72页/共100页V1143V2V3V4V5V6245352012345深度优先遍历：深度优先遍历：V1-V2-V3-V6-V5-V4V1-V2-V3-V6-V5-V4宽度优先遍历：宽度优先遍历：V1-V2-V5-V4-V3-V6V1-V2-V5-V4-V3-V6第73页/共100页v2v4v1v5v3v616211114336191865v2v4v1v5v3v6第74页/共100页42104952812981105121V2V3V1V4V58112102549第75页/共100页123546142548323

12、45671235461232347第76页/共100页求查找成功时的平均查找长度求查找成功时的平均查找长度求查找失败时的平均查找长度求查找失败时的平均查找长度第77页/共100页第78页/共100页第79页/共100页第80页/共100页10,5,2,3,410,5,2,3,4 第81页/共100页303031.531.5第82页/共100页自测题自测题 7 7 设关键码序列为：设关键码序列为：6363，9090，7070，5555，6767，4242，9898，8383，则构造一棵二叉排序树的过程如下：，则构造一棵二叉排序树的过程如下：6363907063905570639067557063

13、90426755706390984267557063908398426755706390第83页/共100页5845439832405570639010第84页/共100页 将将 for, case, while, switch, break, do, for, case, while, switch, break, do, define, const, if, intdefine, const, if, int中的关键字依次插入初态为中的关键字依次插入初态为空的二叉排序树（按字母在字母表中的序号排序）中空的二叉排序树（按字母在字母表中的序号排序）中，请画出所得到的树，请画出所得到的树T T。

14、然后画出删除。然后画出删除forfor之后的二叉之后的二叉排序树排序树T T。自测题自测题 9 9 构造二叉排序树构造二叉排序树第85页/共100页15152121271521154327 RR型型152127RR第86页/共100页RLRL型型2127154336212715368432127154336第87页/共100页LRLR型型 1521113682743(j)(i)1521362711843第88页/共100页01613125031251251631002(a) B(a) BL L、B BR R、A AR R 都是空树都是空树 (b) B(b) BL L、B BR R、A AR R

15、 都是非空树都是非空树9281631254728925163147281631254701010000010000210第89页/共100页(a) A(a) AL L、B BL L、B BR R 都是空树都是空树69-1314703147-1473169000-20025470-1-2-100473169254700-100000-1031766940402576316940(b) A(b) AL L、B BL L、B BR R 都是非空树都是非空树第90页/共100页312547-102302816-1003125470012816000301628253147001000(c) LR(R)(c) LR(R)型调整型调整第91页/共100页(a) RL(0)(a) RL(0)型调整型调整40-13147031471403147000-20(b) RL(L)(b) RL(L)型调整型调整31254701-236406910031254700-169400003625403147690000-10第92页/共100页 (c) RL(R) (c) RL(R)型调整型调整312