数据结构各章练习题

1、读书破万卷下笔如有神第一章练习现实性 D. 难度 这三个特性。C. 解决问题的步骤序列D.B.可执行性、确定性、有穷性D. 易读性、稳定性、安全性）两大类。.顺序结构、链式结构.初等结构、构造型结构选择题1. 算法的计算量的大小称为计算的（）A. 效率 B. 复杂性 C.2. 计算机算法指的是（），它必须具备（）（1）A.计算方法B.排序方法调度方法（2）A .可执行性、可移植性、可扩充性C.确定性、有穷性、稳定性3. 从逻辑上可以把数据结构分为（A. 动态结构、静态结构BC.线性结构、非线性结构D选择题答案：1.B 2. （1） C(2) B 3.C二、判断题1. 数据元素是数据的最小单位。

2、（）2. 数据的逻辑结构是指数据的各数据项之间的逻辑关系；（）3. 算法的优劣与算法描述语言无关，但与所用计算机有关。（）4 .健壮的算法不会因非法的输入数据而出现莫名其妙的状态。（）5. 程序一定是算法。（）6 .数据的物理结构是指数据在计算机内的实际存储形式。（）7. 数据结构的抽象操作的定义与具体实现有关。（）判断题答案：1.F 2.F 3.F 4.T 5.F 6.T 7.F三、填空1. 对于给定的n个元素，可以构造出的逻辑结构有 , 四种。2. 数据的逻辑结构是指 。3. 一个数据结构在计算机中 称为存储结构。4 .数据结构中评价算法的两个重要指标是和5. 数据结构是研讨数据的_和,并

3、对与这种结构定义相应的_ _，设 计出相应的。6 . 一个算法具有5个特性： 、，有零个或多个输入、有一个或多个输出。填空题答案：1. 集合线性结构树形结构图状结构2. 数据及相互之间的联系3. 的存储方式4. 时间复杂度 空间复杂度5. 逻辑结构 存储结构运算（操作） 算法6. 有穷性确定性可行性第二章练习一选择题1 .下述哪一条是顺序存储结构的优点？（）A存储密度大B .插入运算方便C .删除运算方便D .可方便地用于各 种逻辑结构的存储表示2. 下面关于线性表的叙述中，错误的是哪一个？（）A线性表采用顺序存储，必须占用一片连续的存储单元。B. 线性表采用顺序存储，便于进行插入和删除操作。

4、C. 线性表采用链接存储，不必占用一片连续的存储单元。D. 线性表采用链接存储，便于插入和删除操作。3. 线性表是具有门个（ ）的有限序列（n>0）。A表元素 B .字符 C .数据元素 D .数据项E .信息项4 .若某线性表最常用的操作是存取任一指定序号的元素和在最后进行插入和删除运算，则利用（）存储方式最节省时间。A. 顺序表B .双链表C .带头结点的双循环链表 D .单循环链表5 .某线性表中最常用的操作是在最后一个元素之后插入一个元素和删除第一个元素，则采用（ ）存储方式最节省运算时间。A.单链表 B .仅有头指针的单循环链表C .双链表D .仅有尾指针的单循环链表6. 设一

5、个链表最常用的操作是在末尾插入结点和删除尾结点，则选用（）最节省时间。A.单链表B.单循环链表C.带尾指针的单循环链表D.带头结点的双循环链表7. 静态链表中指针表示的是（）.D .左、右A.内存地址 B .数组下标 C .下一元素地址 孩子地址8. 链表不具有的特点是（）A插入、删除不需要移动元素 B .可随机访问任一元素C .不必事先估计存储空间 D .所需空间与线性长度成正比）i个元素的时间同 i个元素的时间同 i个元素的时间同 i个元素的时间同i的值成正比i的值无关i的值成正比i的值无关9. 下面的叙述不正确的是（A.线性表在链式存储时，查找第B. 线性表在链式存储时，查找第C. 线性

6、表在顺序存储时，查找第D. 线性表在顺序存储时，查找第10. （1）静态链表既有顺序存储的优点，又有动态链表的优点。所以，它存取表 中第i个元素的时间与i无关。(2) 静态链表中能容纳的元素个数的最大数在表定义时就确定了，以后不能 增加。(3) 静态链表与动态链表在元素的插入、删除上类似，不需做元素的移动。以上错误的是()A (1), (2) B . (1) C . (1), (2) ,(3) D.(2)11. 若长度为n的线性表采用顺序存储结构，在其第i个位置插入一个新元素的算法的时间复杂度为()(1<=i<=n+1)。A. 0(0) B. 0(1) C. 0( n) D. O(

7、n2)12. 对于顺序存储的线性表，访问结点和增加、删除结点的时间复杂度为()。A. 0(n) 0(n)B. 0(n) 0(1) C. 0(1) 0(n) D. 0(1)0(1)13. 线性表(a1,a2,an )以链接方式存储时，访问第i位置元素的时间复杂性为()A. 0 (i ) B . 0 (1) C . 0(n)D . 0 (i-1 )14 .非空的循环单链表head的尾结点p满足()。A. p->link=headB . p->link=NILC . p=NIL D . p= head15. 在双向链表指针p的结点前插入一个指针q的结点操作是()A. p->Lli

8、nk=q;q->Rli nk=p;p->Lli nk->Rli nk=q;q->Lli nk=q；B. p->Lli nk=q;p->Lli nk->Rli nk=q;q->Rli nk=p;q->Lli nk=p->Lli nk;C. q->Rli nk=p;q->Lli nk=p->Lli nk;p->Lli nk->Rli nk=q;p->Lli nk=q;D. q->Lli nk=p->Lli nk;q->Rli nk=q;p->Lli nk=q;p->Lli

9、nk=q;16. 在单链表指针为p的结点之后插入指针为s的结点，正确的操作是：()。A. p->next=s;s->next=p->next; B. s->next=p->next;p->next=s;C. p->next=s;p->next=s->next; D. p->next=s->next;p->next=s;17. 对于一个头指针为 head的带头结点的单链表，判定该表为空表的条件是( )A . head=NULL B . head next=NULL C . head next=head D. head!=NU

10、LL选择题答案1.A2.B3.C4.A 5.D6.D7.C8.B9.B,C10.B11.C12.C13.C14.A15.C :16.B17.B二、填空1 .当线性表的元素总数基本稳定，且很少进行插入和删除操作，但要求以最快 的速度存取线性表中的元素时，应采用 储结构。2. 线性表L= (a1,a2,an )用数组表示，假定删除表中任一元素的概率相同，则删除一个元素平均需要移动元素的个数是 。3. 设单链表的结点结构为(data,next) ，next为指针域，已知指针px指向单链 表中data为x的结点，指针py指向data为y的新结点,若将结点y插入结点 x之后，则需要执行以下语句：; ;4

11、 .在一个长度为n的顺序表中第i个元素(1<=i<=n)之前插入一个元素时，需向后移动元素。5 在单链表中设置头结点的作用是 。6对于一个具有n个结点的单链表，在已知的结点*p后插入一个新结点的时间 复杂度为,在给定值为x的结点后插入一个新结点的时间复杂度为。7根据线性表的链式存储结构中每一个结点包含的指针个数，将线性链表分成和; 而又根据指针的连接方式，链表又可分成 和。8. 在双向循环链表中，向p所指的结点之后插入指针f所指的结点，其操作是10 .链接存储的特点是利用 表示数据元素之间的逻辑关系。11顺序存储结构是通过 表示元素之间的关系的；链式存储结构是通过 示元素之间的关系

12、的。12. 对于双向链表,在两个结点之间插入一个新结点需修改的指针共 个，单链表为。13. 循环单链表的最大优点是： 。14. 已知指针p指向单链表L中的某结点，则删除其后继结点的语句是： 15. 带头结点的双循环链表L中只有一个元素结点的条件是： 16. 在单链表L中，指针p所指结点有后继结点的条件是：_填空答案：1. 顺序2. (n-1 ) /23. py->next=px->next; px->next=py4 . n-i+15. 主要是使插入和删除等操作统一，在第一个元素之前插入元素和删除第一 个结点不必另作判断。另外，不论链表是否为空，链表指针不变。6. 0(1)，

13、0(n)7. 单链表，多重链表，(动态)链表，静态链表8. f->next=p->next; f->prior=p; p->next->prior=f; p->next=f;9. pdprior sA.priorA.next10. 指针11. 物理上相邻指针12. 4213. 从任一结点出发都可访问到链表中每一个元素。14. u=p->next; p->next=u->next; free(u);15. L->next->next=L16. p->next!=null二、判断1. 链表中的头结点仅起到标识的作用。()2.

14、顺序存储结构的主要缺点是不利于插入或删除操作。()3. 线性表采用链表存储时，结点和结点内部的存储空间可以是不连续的。()4顺序存储方式插入和删除时效率太低，因此它不如链式存储方式好。（）5.对任何数据结构链式存储结构一定优于顺序存储结构。（）6 顺序存储方式只能用于存储线性结构。（）7 集合与线性表的区别在于是否按关键字排序。（）8. 所谓静态链表就是一直不发生变化的链表。（）9. 线性表的特点是每个元素都有一个前驱和一个后继。（）10. 取线性表的第i个元素的时间同i的大小有关（）11. 循环链表不是线性表.（）12. 线性表只能用顺序存储结构实现。（）13. 线性表就是顺序存储的表。（）

15、14为了很方便的插入和删除数据，可以使用双向链表存放数据。（）15. 顺序存储方式的优点是存储密度大，且插入、删除运算效率高。（）16. 链表是采用链式存储结构的线性表，进行插入、删除操作时，在链表中比在 顺序存储结构中效率咼。（）判断题答案1.X2. V3.V4. X5.X6.X7.X8.X9.X10.X11.X12.X13.X14.V15.X16.V部分答案解释如下。1、头结点并不“仅起”标识作用，并且使操作统一。另外，头结点数据域可写入链表长度，或作监视哨。4 两种存储结构各有优缺点，应根据实际情况选用，不能笼统说哪一个好。 7集合中元素无逻辑关系。9 非空线性表第一个元素无前驱，最后一

16、个元素无后继。13线性表是逻辑结构，可以顺序存储，也可链式存储。第三章练习一选择题1. 有一个100*90的稀疏矩阵，非0元素有10个，设每个整型数占2字节，则用三元组表示该矩阵时，所需的字节数是（）。A. 60B. 66C. 18000D. 332. 对稀疏矩阵进行压缩存储目的是（）。A.便于进行矩阵运算B 便于输入和输出C 节省存储空间D 降低运算的时间复杂度3. 广义表（a,b,c,d ）的表头是（），表尾是（）。A. aB.（）C.（a,b,c,d ） D. （b,c,d ）4. 广义表(a,(b,c),d,e)的表头为( )。A. a B. a,(b,c) C. (a,(b,c)D.

17、（a）5.设广义表L= （a,b,c ）,则L的长度和深度分别为（）A. 1和 1B. 1和3C. 1和2D. 2和36.F面说法不正确的是（)°表A.广义表的表头总是个广义表B.广义表的表尾总是一个广义C.广义表难以用顺序存储结构D.广义表可以是一个多层次的结构选择题答案1.B2.C3.C4.A5.C6.A、填空1. 所谓稀疏矩阵指的是。2. 当广义表中的每个元素都是原子时，广义表便成了 。3. 广义表的表尾是指除第一个兀素之外，。4. 广义表简称表，是由零个或多个原子或子表组成的有限序列，原子与表的差别仅在于（1）。为了区分原子和表，一般用表示表，用（3）表示原子。一个表的长度是

18、指，而表的深度是指5. 广义表的定义为广义表中括弧的重数。填空答案：1. 非零元很少（t<<m*n）且分布没有规律2. 线性表3. 其余元素组成的表4. （1）原子（单元素）是结构上不可再分的，可以是一个数或一个结构；而 表带结构，本质就是广义表，因作为广义表的元素故称为子表。（2）大写字母（3）小写字母（4）表中元素的个数（5）表展开后所含括号 的层数5. 深度二、判断1. 稀疏矩阵压缩存储后，必会失去随机存取功能。（）2. 一个稀疏矩阵Am*n采用三元组形式表示，若把三元组中有关行下标与列下标的值互换，并把m和n的值互换，则就完成了 Am*n的转置运算。（）3. 广义表的取表尾

19、运算，其结果通常是个表，但有时也可是个单元素值。（）4. 若一个广义表的表头为空表，则此广义表亦为空表。（）5. 广义表中的元素或者是一个不可分割的原子，或者是一个非空的广义表。（ ）6. 所谓取广义表的表尾就是返回广义表中最后一个元素。（）7. 广义表的同级元素（直属于同一个表中的各元素）具有线性关系。（）8. 对长度为无穷大的广义表，由于存储空间的限制，不能在计算机中实现。（）9. 一个广义表可以为其它广义表所共享。（）判断题答案1. V 12. x3. x4. x5. x6. x7. V8. V J9. V部分答案解释如下。6. 错误。稀疏矩阵转置后，除行列下标及行列数互换外，还必须确定

20、该元素转 置后在新三元组中的位置。8. 错误。广义表的取表尾运算，是非空广义表除去表头元素，剩余元素组成的 表，不可能是原子。9. 错误。广义表的表头就是广义表的第一个元素。只有非空广义表才能取表头10. 错误。广义表中元素可以是原子，也可以是表（包括空表和非空表） 。11. 错误。广义表的表尾，指去掉表头元素后，剩余元素所组成的表。第四章练习一、填空1 栈是的线性表，其运算遵循 的原则。2. 限定仅在表尾进行插入或删除操作的线性表。3. 一个栈的输入序列是：1，2，3则不可能的栈输出序列是 。4用S表示入栈操作，X表示出栈操作，若元素入栈的顺序为1234，为了得到1342出栈顺序，相应的S和

21、X的操作串为。5. 顺序栈用datan存储数据，栈顶指针是top,则值为x的元素入栈的操作是。6 .表达式 23+（12*3-2）/4+34*5/7）+108/9的后缀表达式是 。7. 循环队列的引入，目的是为了克服 。8. 称作先进先出表。9. 队列是限制插入只能在表的一端，而删除在表的另一端进行的线性表，其特点是。10. 设循环队列用数组 AM表示，队首、队尾指针分别是 FRON和TAIL，判定队满的条件为。11. 表达式求值是 用的一个典型例子。12. 循环队列用数组Am存放其元素值，已知其头尾指针分别是front和rear ，则当前队列的元素个数是。填空题答案：1、操作受限（或限定仅在

22、表尾进行插入和删除操作）后进先出2、栈3、3124、 S x SS x S XX 5、data+top=x ;6、23.12.3*2-4/34.5*7/+108.9/+(注：表达式中的点 (.)表示将数隔开，如23.12.3是三个数)7、假溢出时大量移动数据元素。 8、队列 9、先进先出、(rear-front+m ) % m( )10、（TAIL+1） MOD M=FRONT、栈 13二、判断1. 栈是实现过程和函数等子程序所必需的结构。2. 栈与队列是一种特殊操作的线性表。（）3. 队列是一种插入与删除操作分别在表的两端进行的线性表，是一种先进后出 型结构。（4. 通常使用队列来处理函数或

23、过程的调用。（）5. 循环队列也存在空间溢出问题。（6. 栈和队列的存储方式，既可以是顺序方式，又可以是链式方式。（）判断题答案：1. V， 2. V， 3. X 4. X 5. V，6. V第五、六章练习选择题1. 设树T的度为4,其中度为1, 2, 3和4的结点个数分别为4, 2，1，1则T中的叶子数为（）（提示：结点总数=度总数+1）A. 5 B . 6 C . 7 D . 82. 在下述结论中，正确的是（）只有一个结点的二叉树的度为 0;二叉树的度为2;二叉树的左右子树可任意交换；深度为K的完全二叉树的结点个数小于或等于深度相同的满二叉树。A. B . C . D .3. 设森林F对应

24、的二叉树为B，它有m个结点，B的根为p,p的右子树结点个数为n,森林F中第一棵树的结点个数是（）A. m-n B . m-n-1 C . n+1 D .条件不足，无法确定4 .若一棵二叉树具有10个度为2的结点，5个度为1的结点，则度为0的结点 个数是（）A. 9 B . 11 C . 15 D .不确定5. 设森林F中有三棵树，第一，第二，第三棵树的结点个数分别为M1, M2和M3与森林F对应的二叉树根结点的右子树上的结点个数是（）。A. M1 B . M1+M2 C . M3 D . M2+M36. 棵完全二叉树上有1001个结点，其中叶子结点的个数是（）A. 250 B . 501 C

25、. 254 D . 5057. 设给定权值总数有n个，其哈夫曼树的结点总数为（）A.不确定 B . 2n C . 2n+1D . 2n-18. 有n个叶子的哈夫曼树的结点总数为（）。A.不确定 B . 2n C . 2n+1 D . 2n-19. 有关二叉树下列说法正确的是（）A.二叉树的度为2B.一棵二叉树的度可以小于 2C.二叉树中至少有一个结点的度为 2 D .二叉树中任何一个结点的度都为210. 二叉树的第I层上最多含有结点数为（）A. 21B . 21-1 -1 C . 21-1D . 21 -111. 一个具有1025个结点的二叉树的高h为（ ）A. 11 B . 10 C . 1

26、1 至 1025 之间 D . 10 至 1024 之 间12 .一棵二叉树高度为h,所有结点的度或为0,或为2,则这棵二叉树最少有（） 结点A. 2h B . 2h-1 C . 2h+1 D . h+113 .对于有n个结点的二叉树，其高度为（）A. nlog 2n B . log 2nC .og 2n |+1 D .不确定14. 一棵具有n个结点的完全二叉树的树高度（深度）是（）A.og 2n +1 B . log 2n+1C .og 2n D . log 2n-115 .深度为h的满m叉树的第k层有（）个结点。（1=<k=<h）a. m-1b . m-1 c . m-1d .

27、 m-116 .在一棵高度为k的满二叉树中，结点总数为（）A. 2k-1B . 2kC. 2k-1D .og2k +117 .高度为K的二叉树最大的结点数为（）。A. 2kB . 2k-1 C . 2k -1D . 2k-1-118. 一棵树高为K的完全二叉树至少有（）个结点A. 2k - 1 B. 2k-1 - 1 C. 2k-1 D. 2 k19 .对二叉树的结点从1开始进行连续编旦 孩子的编号，同一结点的左右孩子中， 采用（）次序的遍历实现编A.先序B.中序层次遍历20 .已知一棵二叉树的前序遍历结果为遍历的结果为（）A. CBEFDA B . FEDCBA '21.二叉树的先序

28、遍历和中序遍历如下： HFIEJKG。该二叉树根的右子树的根是：B 、F C 、22 .在下列情况中，可称为二叉树的是（A .每个结点至多有两棵子树的树 多有两棵子树的有序树D.每个结点只有一棵右子树23 .由3个结点可以构造出多少种不同的二叉树?'号,号,要求每个结点的编号大于其左、 其左孩子的编号小于其右孩子的编旦号,C.后序D.从根开始按ABCDEF中序遍历结果为CBAEDR则后序.CBEDFA先序遍历:) B.D .不定EFHIGJK中序遍历：哈夫曼树 C .每个结点至.以上答案都不对（ ）A. 2 B . 3 C . 4 D . 5选择题答案1.D2.D3.A4.B5.D6.

29、B7.D8.D9.B10.C11.C12.B13.D14.A15.A16.C17.C18.C19.C20.A21.C22.B23.D二、判断题1. 二叉树是度为2的有序树.2. 完全二叉树一定存在度为1的结点。3. 对于有N个结点的二叉树，其高度为log 2n。4深度为K的二叉树中结点总数w 2k-1。5.对一棵二叉树进行层次遍历时，应借助于一个栈。6 用树的前序遍历和中序遍历可以导出树的后序遍历。7. 中序遍历一棵二叉排序树的结点就可得到排好序的结点序列8. 完全二叉树中，若一个结点没有左孩子，则它必是树叶。9. 二叉树只能用二叉链表表示。10. 在二叉树的第i层上至少有2i-1个结点(i&

30、gt;=1)11. 完全二叉树的存储结构通常采用顺序存储结构。12. 度为二的树就是二叉树。13. 霍夫曼树的结点个数不能是偶数。14. 一棵哈夫曼树的带权路径长度等于其中所有分支结点的权值之和。15. 哈夫曼树是带权路径长度最短的树，路径上权值较大的结点离根较近。、判断题答案1. X2. X3. X4. V5. X6. X7. V8. V9. X10. X11. V：12. X13. V：14. X15. V三、填空题1. 二叉树由(1)， 三个基本单元组成。2 .中缀式 a+b*3+4* (c-d )对应的前缀式为 _(1)_，若 a=1，b=2，c=3，d=4， 则后缀式db/cc*a-

31、b*+的运算结果为 。3.具有256个结点的完全二叉树的深度为 。4 .已知一棵度为3的树有2个度为1的结点，3个度为2的结点，4个度为3的结点，则该树有叶子结点。5 .深度为k的完全二叉树至少有_(1)_个结点，至多有丄2)_个结点。6. 假设根结点的层数为1,具有n个结点的二叉树的最大高度是 。7. 在一棵二叉树中，度为零的结点的个数为N0,度为2的结点的个数为N2,则有N0 =8 .高度为8的完全二叉树至少有 叶子结点。9 .已知二叉树有50个叶子结点，则该二叉树的总结点数至少是10完全二叉树中，结点个数为n,则编号最大的分支结点的编号为 。11 具有N个结点的二叉树，采用二叉链表存储，

32、共有_个空链域。12. 哈夫曼树是。13若以4 , 5, 6, 7, 8作为叶子结点的权值构造哈夫曼树，贝U其带权路径长 度是。14 .有一份电文中共使用 6个字符：a,b,c,d,e,f, 它们的出现频率依次为 2,3,4,7,8,9 ，试构造一棵哈夫曼树，则其加权路径长度WPL为_(1)_，字符c的编码是_J2)_。15. 设n°为哈夫曼树的叶子结点数目，则该哈夫曼树共有个结点。三. 填空题答案1. (1)根结点 左子树 右子树2. (1) +a*b3*4-cd (2)183. 94. 125. (1)2 k-1 (2)2 k-16. n7. N2+18. 649. 9910.

33、Hn/211. N+112. 带权路径长度最小的二叉树，又称最优二叉树13.6914.(1)80 (2)001 (不唯一)15.2 n(r1第七章练习A . n-1B. nC.n+1D.nlogn ；3.要连通具有n个顶点的有向图，至少需要( :)条边。A . n-1B. nC.n+lD.2n4. n个结点的完全有向图含有边的数目()。A . n*nB . n (n +1)C.n/ 2D.n* (n-2.O一个有n个结点的图,最少有()个连通分量，最多有D).0 E、选择题设无向图的顶点个数为n,则该图最多有()条边A. n-1 B . n(n-1)/2 C . n(n+1)/2 一个n个顶点

34、的连通无向图，其边的个数至少为(5 .分量。l )个连通.n-1D. n倍，在一个有A. 0B6 .在一个无向图中，所有顶点的度数之和等于所有边数(向图中，所有顶点的入度之和等于所有顶点出度之和的（）倍。A. 1/2 B . 2C . 1D. 4其 中 ：，对该图C . a,e,b,c,f,d7 无 向 图G=(V,E),V=a,b,c,d,e,f,E=(a,b),(a,e),(a,c),(b,e),(c,f),(f,d),(e,d) 进行深度优先遍历，得到的顶点序列正确的是()A . a,b,e,c,d,fB . a,c,f,e,b,dD. a,e,d,f,c,b8. 已知有向图 G=(V,

35、E)，其中 V=Vi,V2,V3,V4,V5,V6,V7,E=vVi,V2>,vVi,V3>,vVi,V4>,vV2,V5>,vV3,V5>,vV3,V6>,vV4,V6>,vV5,V7>,vV6,V7>,G 的拓扑序列是（）0A. V1,V3,V4,V6,V2,V5,V7B. V1,V3,V2,V6,V4,V5,V7C. V1,V3,V4,V5,V2,V6,V7D. V1,V2,V5,V3,V4,V6,V79. 一个有向无环图的拓扑排序序列（）是唯一的。A. 一定B .不一定10. 在有向图G的拓扑序列中，若顶点Vi在顶点Vj之前，则下列

36、情形不可能出现的是（0。A. G中有弧<Vi，Vj>B. G中有一条从Vi到Vj的路径C. G中没有弧<Vi,Vj>D. G中有一条从Vj到Vi的路径三、填空题1. 判断一个无向图是一棵树的条件是 o2. 有向图G的强连通分量是指 o3. 一个连通图的 一个极小连通子图。4. 具有10个顶点的无向图，边的总数最多为 o5. 若用n表示图中顶点数目，则有 边的无向图成为完全图。6. 在有n个顶点的有向图中，若要使任意两点间可以互相到达，贝U至少需要 条弧。7. 在有n个顶点的有向图中，每个顶点的度最大可达 o8. 设G为具有N个顶点的无向连通图，贝U G中至少有 边。9

37、. N个顶点的连通图的生成树含有 条边。10 .有N个顶点的有向图，至少需要量 弧才能保证是连通的。11 .右图中的强连通分量的个数为（0个12 .在图G的邻接表表示中，每个顶点邻接表中所含的结点数， 对于无向图来说 等于该顶点的 ；对于有向图来说等于该顶点的 o13. 在有向图的邻接矩阵表示中，计算第I个顶点入度的方法是 o14. 对于一个具有n个顶点e条边的无向图的邻接表的表示，则表头向量大小为，邻接表的边结点个数为o15. 已知一无向图 G= （ V， E ），其中 V=a,b,c,d,e E=(a,b),(a,d),(a,c),(d,c),(b,e)现用某一种图遍历方法从顶点 a开始遍

38、历图，得到的序列为abecd，贝U采用的是_遍历方法。16. 一无向图 G( V, E),其中 V( G) =123,4,5,6,7,E(G)=( 1,2 ) ,(1,3 ),(2,4 ), (2,5 ), (3,6 ), (3,7 ), (6,7 ) (5,1 ) ,对该图从顶点 3 开始进行遍历，去掉遍历中未走过的边，得一生成树G (V ,E'),V( G)=V( G),E( G')=( 1,3 ), (3,6 ), (7,3 ), (1,2 ), (1,5 ), (2,4 ) ，则采用的遍历方法是 。17. 为了实现图的广度优先搜索，除了一个标志数组标志已访问的图的结点外，还需 放被访问的结点以实现遍历。18 构造连通网最小生成树的两个典型算法是。19. 有一个用于n个顶点连通带权无向图的算法描述如下:(1) .设集合T1与T2,初始均为空；(2) .在连通图上任选一点加入 T1;(3) .以下步骤重复n-1次：a. 在i属于T1, j不属于T1的边中选最小权的边；b. 该边加入T2。上述算法完成后，T2中共有 边，该算法称 法，T2中的边构成图的。20 . AOV网中，结