数据结构复习题4A

1数据结构复习题第1章绪论一、单选题（共有题目8题）1从一维数组AN中顺序查找出一个最大值元素的时间复杂度为（）。AO1BONCON2DON标准答案B2输出一个二维数组BMN中所有元素值的时间复杂度为（）。AOMNBOMNCOM2DON2标准答案B3下面程序段的时间复杂度是（）。FORINTI0IHRETURN1ELSERETURN0请问该算法的功能是什么它的时间复杂度数量级是哪个标准答案判断整数N是不是素数；ON三、填空题（共有题目14题）1在线性结构中，前驱结点和后继结点之间存在着1对111或一对一的联系。2对算法评价一般从正确性、健壮性、可读性、简单性、时间复杂度、空间复杂度六个方面进行的。3在图形结构中，前驱和后继结点之间存在着多对多MN的联系。4数据结构研究的内容主要包括数据的逻辑结构、数据的存储结构（数据的物理结构）和数据的操作三部分。5数据的物理结构又名存储结构_，它主要有顺序存储、链接存储、索引和散列4种方式。6在树形结构中，前驱和后继结点之间存在着1对多（1N）联系。7数据的逻辑结构被分为集合结构、线性结构、树形结构、图形结构4种。8算法是指对特定问题求解步骤的一种描述，是一组指令的有限序列；也可以说是解决特定问题的方法步骤。9在一个算法的程序描述中，不同的语句重复执行的次数不同，某语句重复执行的次数称为该语句的频度（频次）。10记录（数据记录）是数据处理领域组织数据的基本单位。11依据视点的不同，数据结构分为数据的逻辑结构和物理结构。数据的逻辑结构是面向问题的，数据的物理结构（数据的存储结构）是面向计算机的。12算法应具备有穷性、确定性、可行性、输入和输出五个特性。13在下面程序段中，SSP语句的执行次数是N，PJ语句的执行次数是NN1/2，该程序段的时间复杂度为ON2。INTI0,S0WHILEINEXTBLNEXTLNEXTNEXTCLLDLNEXTL标准答案B4给定有N个元素的数组，建立一个有序单链表的时间复杂度是（）AO1BONCON2DONLOG2N标准答案B5在一个单链表HL中，若要删除由指针Q所指向结点的后继结点，则执行（）。APQNEXTPNEXTQNEXTBPQNEXTQNEXTPCPQNEXTQNEXTPNEXTDQNEXTQNEXTNEXTQNEXTQ标准答案C6在一个长度为N的顺序表中删除第I个元素（0IN1）时，需要从前向后依次前移（）个元素。ANIBNI1CNI1DI标准答案C7若线性表最常用的操作是存取第I个元素及其前驱的值，则采用存储方式节省时间。A单链表B双链表C单循环链表D顺序表标准答案D8不带头结点的单链表FIRST为空的判定条件是（）。AFIRSTNULLBFIRSTNEXTNULLCFIRSTNEXTFIRSTDFIRSTNULL标准答案A9执行下面程序段时，执行S语句的次数为。FORINTI1ILINK所指向的结点，则应执行的操作是（）。APLINKPLINKLINKBPPLINKPLINKPLINKLINKCPLINKPDPPLINKLINK标准答案A11一个数组元素AI与的表示等价。AAIBAICAIDBFIRSTNEXTNULLCFIRSTNEXTFIRSTDFIRSTNULL标准答案B16一个算法的时间复杂度为3N22NLOG2N4N7/5N，其数量级形式的复杂度表示为。AONBONLOG2NCON2DOLOG2N标准答案A17某算法仅含程序段1和程序段2，程序段1的执行次数3N2，程序段2的执行次数为001N3，则该算法的时间复杂度为（）。AONBON2CON3DO1标准答案C19有一个含头结点的单链表，头指针为HEAD，则判断其是否为空的条件为。AHEADNULLBHEADNEXTNULLCHEADNEXTHEADDHEADNULL标准答案B20设有一个NN的对称矩阵A，将其上三角部分按行存放在一个一维数组B中，A00存放于B0中，那么第I行的对角元素AII存放于B中（）处。AI3I/2BI1I/2C2NI1I/2D2NI1I/2标准答案C21在一个单链表中，若Q结点是P结点的前驱结点，若在Q与P之间插入结点S，则执行（）。ASNEXTPNEXTPNEXTSBPNEXTSSNEXTQCPNEXTSNEXTSNEXTPDQNEXTSSNEXTP标准答案D22在一个长度为N的顺序存储的线性表中，删除第I个元素（1IN）时，需要从前向后依次前移（）个元素。ANIBNI1CNI1DI标准答案A23设单链表中结点的结构为（DATA,LINK）。已知指针Q所指结点是指针P所指结点的直接前驱，若在Q与P之间插入结点S，则应执行的操作是（）。ASLINKPLINKPLINKSBQLINKSSLINKPCPLINKSLINKSLINKPDPLINKSSLINKQ标准答案B24在一个长度为N的有序顺序表中搜索值为X元素的时间效率最高的算法的渐进时间复杂度为（）。AO1BO1COLOG2NDON标准答案C25在一个单链表HL中，若要在指针Q所指向结点的后面插入一个由指针P所指向的结点，则执行（）。AQNEXTPNEXTPNEXTQBPNEXTQNEXTQPCQNEXTPNEXTQNEXTPDPNEXTQNEXTQNEXTP5标准答案D26已知L是一个不带表头的单链表，在表首插入结点P的操作是（）。APLPNEXTLBPNEXTLPLCPNEXTLLPDLPPNEXTL标准答案C27设单循环链表中结点的结构为（DATA,LINK），且REAR是指向非空的带表头结点的单循环链表的尾结点的指针。若想删除链表第一个结点，则应执行的操作是（）。ASREARREARREARLINKDELETESBREARREARLINKDELETEREARCREARREARLINKLINKDELETEREARDSREARLINKLINKREARLINKLINKSLINKDELETES标准答案D28某算法的时间代价为TN100N10NLOG2NN210，其时间复杂度为（）。AONBONLOG2NCON2DO1标准答案C29在一个长度为N的顺序表中向第I个元素（0IN1）位置插入一个新元素时，需要从后向前依次后移（）个元素。ANIBNI1CNI1DI标准答案A30在一个长度为N的顺序表的任一位置插入一个新元素的时间复杂度为（）。AONBON/2CO1DON2标准答案A31多维数组实际上是由嵌套的（）实现的。A一维数组B多项式C三元组表D简单变量标准答案A32设有一个NN的对称矩阵A，将其下三角部分按行存放在一个一维数组B中，A00存放于B0中，那么第I行的对角元素AII存放于B中（）处。AI3I/2BI1I/2C2NI1I/2D2NI1I/2标准答案A33利用双向链表作线性表的存储结构的优点是（）。A便于单向进行插入和删除的操作B便于双向进行插入和删除的操作C节省空间D便于销毁结构释放空间标准答案B34在数据结构的讨论中把数据结构从逻辑上分为（）。A内部结构与外部结构B静态结构与动态结构C线性结构与非线性结构D紧凑结构与非紧凑结构标准答案C35单链表A长度为M，单链表B长度为N，若将B联接在A的末尾，其时间复杂度应为（）。AO1BOMCONDOMN标准答案B36带表头的双向循环链表的空表满足（）。AFIRSTNULLBFIRSTRLINKFIRSTCFIRSTLLINKNULLDFIRSTRLINKNULL标准答案B37一个记录R理论上占有的存储空间的大小等于所有域类型长度之和，实际上占有的存储空间的大小即记录长度为。6A所有域长度之和B最大域所占字节长度C任意一个域长度DSIZEOFR的值标准答案D38采用顺序搜索方法查找长度为N的顺序表时，搜索成功的平均搜索长度为（）。ANBN/2CN1/2DN1/2标准答案D39在二维数组中，每个数组元素同时处于（）个向量中。A0个B1个C2个DN个标准答案C40设单链表中结点的结构为（DATA,LINK）。已知指针P所指结点不是尾结点，若在P之后插入结点S，则应执行的操作是（）。ASLINKPPLINKSBPLINKSSLINKPCSLINKPLINKPSDSLINKPLINKPLINKS标准答案D41非空的循环单链表FIRST的尾结点（由P所指向）满足的条件是（）。APLINKNULLBPNULLCPLINKFIRSTDPFIRST标准答案C42从一个具有N个结点的单链表中查找其值等于X结点时，在查找成功的情况下，需要平均比较的结点数是（）。ANBN/2CN1/2DN1/2标准答案D43采用线性链表表示一个向量时，要求占用的存储空间地址（）。A必须是连续的B部分地址必须是连续的C一定是不连续的D可连续可不连续标准答案D44在一个具有N个结点的有序单链表中插入一个新结点并仍然保持有序的时间复杂度是（）。AO1BONCON2DONLOG2N标准答案B45在一个长度为N的顺序存储的线性表中，向第I个元素（1IN1）位置插入一个新元素时，需要从后向前依次后移（）个元素。ANIBNI1CNI1DI标准答案B46在一个单链表HL中，若要向表头插入一个由指针P指向的结点，则执行（）。AHLPPNEXTHLBPNEXTHLHLPCPNEXTHLPHLDPNEXTHLNEXTHLNEXTP标准答案B47下面程序段的时间复杂度为。FORINTI0INEXTNULL和HLNEXTHL。2线性表的链接存储只能通过链接指针顺序访问。3链表是一种采用链式（或链接_）存储结构存储的线性表。4在线性表的单链接存储结构（结点）中，若一个元素所在结点的地址为P，则其后继结点的地址为PNEXT，后继结点的值为PNEXTDATA。5若设L是指向带表头的单链表,语句LLINKLLINKLINK的作用是删除单链表中的第一个结点。6在单链表中除了表头结点外，任意结点的存储位置由其直接前驱结点的指针域的值所指示。7在双向链表中，每个结点包含两个指针域，一个指向其前驱（双亲、父）结点，另一个指向其后继（孩子、子）结点。8链接存储表示的结点存储空间一般在程序的运行过程中进行动态地分配_和释放。9在链表中进行插入和删除操作的效率比在顺序存储结构中进行相同操作的效率高。10在线性表的单链接存储结构（结点）中，若一个元素所在结点的地址为P，P为一个数组A中的下标，则其后继结点的地址为CHARANEWCHARMAXSIZE错9线性表若采用链式存储表示,在删除时不需要移动元素。对10数据的逻辑结构与数据元素本身的内容和形式无关。对11如果采用如下方式定义一维字符数组CONSTINTMAXSIZE30CHARAMAXSIZE则这种数组在程序执行过程中不能扩充。对12算法和程序原则上没有区别，在讨论数据结构时二者是通用的。错13顺序表和一维数组一样，都可以按下标随机（或直接）访问。对14在线性链表中删除中间的结点时，只需将被删结点释放。错四、程序填空题（共有题目3题）1下面程序段实现的功能是向单链表的表头插入一个元素X，请补充完整程序。VOIDINSERTFIRSTLISTSTRUCTSNODEHL,ELEMTYPEXSTRUCTSNODENEWPNEWPMALLOCSIZEOFSTRUCTSNODEIFNEWPNULLPRINTF“内存动态空间用完，退出运行N“EXIT1NEWPDATAXNEWPNEXTHLHLNEWP2下面程序段实现的功能是向单链表的表尾插入一个元素X，请补充完整程序。VOIDINSERTLASTLISTSTRUCTSNODEHL,ELEMTYPEXSTRUCTSNODENEWPNEWPMALLOCSIZEOFSTRUCTSNODEIFNEWPNULLPRINTF“内存动态空间用完，退出运行N“EXIT1NEWPDATAXNEWPNEXTNULL或0IFHLNULLHLNEWPELSESTRUCTSNODEPHLWHILEPNEXTNULL9PPNEXTPNEXTNEWP3欲向线性表L的表头插入元素X，完成下面程序段中的部分语句VOIDINSERTFIRSTLISTSTRUCTLISTL,ELEMTYPEXINTIIF_LSIZELMAXSIZEAGAINMALLOCLFORILSIZE1I0ILLISTI1LLISTILLIST0XLSIZE第3章稀疏矩阵和广义表一、单选题（共有题目4题）1设一个具有T个非零元素的MN大小的稀疏矩阵采用顺序存储，求其转置矩阵的普通转置算法的时间复杂度为（）。AOMBONCONTDONT标准答案D2在稀疏矩阵的带行指针向量的链接存储中，每个行单链表中的结点都具有相同的（）。A行号B列号C元素值D地址标准答案A3广义表的表头是。AB没有表头CD0标准答案B4广义表的表尾是。A没有表尾BCD0标准答案A二、填空题（共有题目16题）1在一个稀疏矩阵中，每个非零元素所对应的三元组包括该元素的行号、列号和元素值3项。2,E,A,B,C,D的表头是或空表。3一个广义表中的元素分为单（原子）元素和表（子表）元素两类。4在广义表的存储结构中，单元素结点与表元素结点有一个域对应不同，各自分别为值域和子表指针域。5一个广义表的深度等于括号嵌套的最大层次数。6稀疏矩阵是一种非零元素的个数远远小于零元素的个数，且非零元素的分布没有规律的矩阵。7广义表的表头是或空表。8在稀疏矩阵的顺序存储中，利用一个数组来存储非零元素，该数组的长度应大于对应三元组线性表的长度。9广义表E,A,B,C,D的深度是3。10广义表的表尾是或空表。11,E,A,B,C,D的表尾是E,A,B,C,D。12在一个广义表的存储结构中，每个结点均包含有_3个域。1013广义表E,A,B,C,D的长度是2。14在稀疏矩阵的带行指针向量的链接存储中，每个结点包含有4个域，在相应的十字链接存储中，每个结点包含有5个域。15在稀疏矩阵的十字链接存储中，每个结点的DOWN指针域指向列号相同的下一个结点，RIGHT指针域指向行号相同的下一个结点。16在稀疏矩阵所对应的三元组线性表中，每个三元组元素按行号为主序列号为辅序的次序排列。三、判断题（共有题目1题）1使用三元组表示稀疏矩阵中的非零元素能节省存储空间。对第4章栈和队列一、单选题（共有题目9题）1在一个顺序队列中，队首指针指向队首元素的（）位置。A前一个B后一个C当前D后面标准答案A2假定利用数组AN循环顺序存储一个队列，用F和R分别表示队首和队尾指针，并已知队未空，当进行出队并返回队首元素时所执行的操作为。ARETURNARNBRETURNARNCRETURNAFNDRETURNAFN标准答案C3一个链栈的栈顶指针用TOP表示，当进行退栈时所进行的指针操作为（）。ATOPNEXTTOPBTOPTOPDATACTOPTOPNEXTDTOPNEXTTOPNEXTNEXT标准答案C4一个链栈的栈顶指针用TOP表示，当P所指向的结点进栈时，执行的操作为（）。APNEXTTOPTOPTOPNEXTBTOPPPNEXTTOPCPNEXTTOPNEXTTOPNEXTPDPNEXTTOPTOPP标准答案D5栈的插入和删除操作在（）进行。A栈顶B栈底C任意位置D指定位置标准答案A6当利用大小为N的数组顺序存储一个队列时，若没设有队列长度的变量，则该队列的最大长度为（）。AN2BN1CNDN1标准答案B7若让元素1、2、3依次进栈，则出栈次序不可能出现（）情况。A3，2，1B2，1，3C3，1，2D1，3，2标准答案C8从一个顺序队列删除元素时，首先需要（）。A队首指针循环加1B队首指针循环减1C取出队首指针所指位置上的元素D取出队尾指针所指位置上的元素标准答案A9假定一个链队的队首和队尾指针分别为FRONT和REAR，则判断队空的条件为。AFRONTREARBFRONTNULLCREARNULLDFRONTNULL标准答案D二、填空题（共有题目7题）1后缀表达式“4532”的值为15。2栈又称为后进先出表，队列又称为先进先出_表。113队列的插入操作在队尾进行，删除操作在队首进行。4中缀表达式3X25所对应的后缀表达式为3X25。5在一个链队中，若队首指针与队尾指针的值相同，则表示该队为空或该队只含有一个结点。6在一个不设队列长度变量的顺序队列Q中，判断队空的条件为QFRONTQREAR，判断队满的条件为QREAR1QMAXSIZEQFRONT。7向一个栈顶指针为HS的链栈中插入一个新结点P时，应执行PNEXTHS和HSP操作。第5章树和二叉树一、单选题（共有题目17题）1在一棵完全二叉树中，若编号为I的结点存在左孩子，则左孩子结点的编号为（）。A2IB2I1C2I1D2I2标准答案A2在一棵树中，每个结点最多有（）个前驱结点。A0B1C2D任意多个标准答案B3在一棵具有N个结点的二叉树的第I层上，最多具有（）个结点。A2IB2I1C2I1D2N标准答案C4在一棵具有35个结点的完全二叉树中，该树的深度为（）。A6B7C5D8标准答案A5在一棵具有N个结点的完全二叉树中，树枝结点的最大编号是（）。AN1/2BN1/2CN/21DN/2标准答案D6在一棵二叉树的二叉链表中，空指针域数等于非空指针域数加（）。A2B1C0D1标准答案A7在一棵完全二叉树中，对于编号为II1的结点，其双亲结点的编号为（）。AI1/2BI1/2CI/21DI/2标准答案B、D8一棵二叉树的广义表表示为ABC,DE,GH,F，则该二叉树的高度为（）。A3B4C5D6标准答案C9一棵树的广义表表示为ABC,DE,FGH,I,J，该树的深度为（）。A3B4C5D6标准答案C10在一棵深度为H的完全二叉树中，所含结点个数不大于（）。A2HB2H1C2H1D2H1标准答案C11树中所有结点的度等于所有结点数加（）。A0B1C1D2标准答案C12一棵二叉树的广义表表示为ABC,DE,GH,F，则该二叉树所含的单分支结点数为（）。A2B3C4D5标准答案B13在一棵完全二叉树中，若编号为I（1IN）的结点存在右孩子，则右孩子结点的编号为（）。A2IB2I1C2I1D2I212标准答案C14在一棵深度为H的完全二叉树中，所含结点个数不小于（）。A2HB2H1C2H1D2H1标准答案D15对于一棵具有30个结点的三叉树，则其最小深度为（）。A3B4C5D6标准答案B16对于一棵深度为4的三叉树，最多具有（）个结点。A30B36C40D54标准答案C17在一棵二叉树中，叶子结点数等于双分支结点数加（）。A0B1C1D2标准答案B二、填空题（共有题目12题）1对于一棵具有N个结点的树，则树中所有结点的度数之和为N1。2对于一棵含有40个结点的理想平衡树，它的高度为6_。3在一棵二叉树中，第5层上的结点数最多有16个。4一棵高度为3的四叉树中，最多含有21_结点。5在一棵二叉树中，若双分支结点数为5个，单分支结点数为6个，则叶子结点数为6个。6一棵三叉树的结点个数为50，则它的最小深度为5，最大深度为50。7在一棵高度为5的理想平衡树中，最少含有16个结点，最多含有31个结点。8一棵树的广义表表示为ABC,DE,F,G,HI,J，则结点H的双亲结点是B，孩子结点有I、J。9一棵二叉树顺序存储在一维数组A中，则AI（1IN）元素的左孩子元素为A2I，右孩子元素为A2I1。10已知一棵二叉树的先根和中根序列如下先根序列A，B，C，D，E，F，G，H，I，J中根序列C，B，A，E，F，D，I，H，J，G则其后根序列为CBFEIJHGDA。11在一棵三叉树中，度为3的结点数有2个，度为2的结点数有1个，度为1的结点数有2个，则度为0的结点数有6个。12一棵深度为5的满二叉树中的结点数为31个。第6章二叉树的应用一、单选题（共有题目10题）1对二叉搜索树进行中序遍历得到的结点序列一定是一个有序序列。对2利用N个值作为叶子结点的权生成的哈夫曼树中共包含（）结点。ANBN1C2ND2N1标准答案D3有四个带权叶子结点，其权值分别为2、4、5、9，则由其构成的哈夫曼树的带权路径长度是（）。A50B40C37D20标准答案C4向二叉搜索树中插入一个元素时，其时间复杂度大致为（）。AO（1）BO（LOG2NCONDONLOG2N标准答案B5从二叉搜索树中查找一个元素时，其时间复杂度大致为。AONBO1COLOG2NDON2标准答案C6根据N个元素建立一棵二叉搜索树时，其时间复杂度大致为（）。AO（NBOLOG2NCON2DONLOG2N13标准答案D7利用N个值作为叶子结点的权生成的哈夫曼树中共包含（）个双分支结点。ANBN1CN1D2N1标准答案B8从堆中删除一个元素的时间复杂度为（）。AO1BONCOLOG2NDONLOG2N标准答案C9利用3、6、8、12为4个值作为叶子结点的权，生成一棵哈夫曼树，该树中所有叶子的最短带权路径长度为（）。A18B16C12D30标准答案A10向堆中插入一个元素的时间复杂度是（）。AO1BOLOG2NCONDONLOG2N标准答案B二、填空题（共有题目18题）1堆的存储结构适宜采用顺序存储，这样能够充分利用存储空间。2若有两棵树T1和T2均为小根堆，当以它们作为一棵树T的左、右子树，并用一个比这两棵子树的根都小的值作为整个树T的根结点，则树T是一个堆小根堆。3在一棵非空的二叉搜索树中，以每个分支结点为根的子树都是一棵二叉搜索树。4有7个带权结点，其权值分别为3、7、8、2、6、10、14，若依它们为叶子结点构造一棵哈夫曼树，给出其广义表，并计算出其带权路径长度WPL134。5堆是一棵完全二叉树。6在一棵树中，结点的带权路径长度规定为从树根结点到该结点之间的路径长度与该结点上权的乘积。7在一棵二叉搜索树中，其左子树上结点的关键字值小于根结点的关键字值。8在一棵树中，两个结点之间如果有路径的话，路径的个数是唯一的。9在一棵二叉搜索树中查找一个元素时，若元素的值等于根结点的值，则表明查找成功；若元素的值小于根结点的值，则继续向左子树查找；若元素的值大于根结点的值，则继续向右子树查找。10当向一个小根堆插入一个具有最小值的元素时，该元素需要逐层向上调整，直到被调整到堆顶位置为止。11当从一个小根堆中删除一个元素时，需要把堆尾元素填补到堆顶位置，然后再按条件把它逐层向下调整。12二叉搜索树又名二叉排序树。13在一个堆中，除编号为0的堆顶结点外，对于其他编号为I的结点，其双亲结点的编号为。2/1I14在一个堆的顺序存储结构中，堆中结点的编号是从0开始的，若一个元素的下标为I，则它的左孩子元素的下标是2I1，右孩子元素的下标是2I2。15在一个小根堆中，堆顶结点的值是所有结点中的最小值；在一个大根堆中，堆顶结点的值是所有结点中的最大值。16在任何一棵哈夫曼树中，单支结点的个数为0。17对一棵二叉搜索树进行中序遍历时，得到的结点序列是一个有序序列。18不管一棵哈夫曼树中有偶数或奇数个叶子结点，则树中总结点的个数必为奇数个。第7章图一、单选题（共有题目18题）1对于一个具有N个顶点的无向连通图，它包含的连通分量的个数为（）。A0B1CNDN114标准答案B2已知一个无向图的边集为0,13,0,24,0,38,1,410,2,32,2,412,3,48，则利用普里姆算法从顶点0出发求其最小生成树的过程中，得到的第条边是（）。A0,13B0,24C2,32D3,45标准答案C3在一个具有N个顶点和E条边的无向图的邻接表中，边结点的个数为（）。ANBECNED2E标准答案D4若要把N个顶点连接为一个连通图，则至少需要（）条边。ANBN1CN1D2N标准答案C5由一个具有N个顶点的连通图生成的最小生成树中，具有（）条边。ANBN1CN1D2N标准答案B6若一个图中包含有K个连通分量，若要按照深度优先搜索的方法访问所有顶点，则必须调用（）次深度优先搜索遍历的算法。A1BK1CKDK1标准答案C7若一个图的边集为（A,B）,（A,C）,（B,D）,（C,F）,（D,E）,（D,F），则从顶点A开始对该图进行深度优先搜索，得到的顶点序列可能为（）。AA，B，C，F，D，EBA，C，F，D，E，BCA，B，D，C，F，EDA，B，D，F，E，C标准答案B8在一个具有N个顶点的无向图中，若具有E条边，则所有顶点的度数之和为（）。ANBECNED2E标准答案D9若一个图的边集为（A,B）,（A,C）,（B,D）,（C,F）,（D,E）,（D,F），则从顶点A开始对该图进行广度优先搜索，得到的顶点序列可能为（）。AA，B，C，D，E，FBA，B，D，E，F，CCA，B，D，C，E，FDA，C，B，F，D，E标准答案D10在一个具有N个顶点的有向完全图中，所含的边数为（）。ANBNN1CNN1/2DNN1/2标准答案B11已知一个无向图的边集为0,13,0,25,0,36,1,410,2,32,2,49,3,48，则该图的最小生成树的边集为（）。A0,13,0,25,0,36,3,48B0,13,0,25,0,36,2,32C2,32,0,25,3,48,0,36D2,32,0,25,3,48,0,13标准答案D12在一个具有N个顶点的无向完全图中，所含的边数为（）。ANBNN1CNN1/2DNN1/2标准答案C13在一个具有N个顶点和E条边的有向图的邻接矩阵中，表示边存在的元素的个数为（）。ANBECNED2E标准答案B14在一个具有N个顶点的有向图中，若所有顶点的出度之和为S，则所有顶点的入度之和为（）。15ASBS1CS1DN标准答案A15已知一个无向图的边集为0,13,0,24,0,38,1,410,2,32,2,412,3,45，则利用克鲁斯卡尔算法求其最小生成树的过程中，得到的第条边是（）。A0,13B0,24C2,32D3,45标准答案B16在一个具有N个顶点和E条边的无向图的邻接矩阵中，表示边存在的元素（又称为有效元素）的个数为（）。ANBECNED2E标准答案D17在一个无权图中，若两顶点之间的路径长度为K，则该路径上的顶点数为（）。AKBK1CK2D2K标准答案B18在一个具有N个顶点的有向图中，若所有顶点的出度数之和为S，则所有顶点的度数之和为（）。ASBS1CS1D2S标准答案D二、填空题（共有题目13题）1一个图的边集为A,C,A,E,B,E,C,D,D,E,从顶点A出发进行深度优先搜索遍历得到的顶点序列为ACDEB（AEBDC或AEDCB），从顶点A出发进行广度优先搜索遍历得到的顶点序列为ACEDB（AECBD或AECDB）。2已知一个连通图的边集为1,23,1,36,1,48,2,34,2,510,3,512,4,52，若从顶点V1出发，按照普里姆算法生成的最小生成树的过程中，被选取的第3条边为1,48。3对于具有N个顶点和E条边的连通图，普里姆算法和克鲁斯卡尔算法的时间复杂度分别为ON2和ON2。4一个连通图中存在着1个连通分量。5已知一个连通图的边集为1,23,1,36,1,48,2,34,2,510,3,512,4,52，则度为3的顶点个数有_4个。6若一个连通图中每个边上的权（权值）均不同，则得到的最小生成树是唯一的。7在一个图中，所有顶点的度数之和等于所有边数的2倍。8若一个图的顶点集为A,B,C,D,E,F，边集为A,B,A,C,B,C,D,E，则该图含有3个连通分量。9在一个具有