数据结构(本)形考作业答案.doc

形考作业一题目1把数据存储到计算机中，并具体体现数据元素间得逻辑结构称为(）。选择一项：A、 逻辑结构B、 给相关变量分配存储单元C、算法得具体实现D、物理结构题目2下列说法中，不正确得就是（ ）。选择一项:A、 数据可有若干个数据元素构成B、 数据元素就是数据得基本单位C、 数据项就是数据中不可分割得最小可标识单位D、 数据项可由若干个数据元素构成题目3一个存储结点存储一个（)。选择一项:A、 数据结构B、数据类型C、 数据项、 数据元素题目4数据结构中，与所使用得计算机无关得就是数据得（ ）。选择一项：A、 物理结构B、逻辑结构C、 物理与存储结构D、 存储结构题目下列得叙述中，不属于算法特性得就是（ )。选择一项：A、 有穷性B、 可行性、可读性D、输入性题目6正确获得、00分中得2、00分A、 研究算法中得输入与输出得关系、分析算法得易懂性与文档性、 分析算法得效率以求改进D、找出数据结构得合理性题目7算法指得就是（）。选择一项:A、排序方法B、 解决问题得计算方法C、 计算机程序D、 解决问题得有限运算序列题目8算法得时间复杂度与（ ）有关。选择一项:A、 所使用得计算机B、 数据结构C、算法本身D、计算机得操作系统题目9设有一个长度为n得顺序表,要在第i个元素之前(也就就是插入元素作为新表得第i个元素)，插入一个元素,则移动元素个数为（ )。选择一项:A、 n-i+1、 -1、 niD、 题目10设有一个长度为得顺序表，要删除第i个元素移动元素得个数为( )。选择一项:A、ni、 ni-1C、 ni+1D、题目11在一个单链表中，p、q分别指向表中两个相邻得结点,且q所指结点就是p所指结点得直接后继，现要删除q所指结点,可用语句( ).选择一项：、 pnxt=q-nextB、 p=-nexC、 qnext=ULD、p-net=题目12在一个单链表中p所指结点之后插入一个s所指得结点时，可执行(）。选择一项:A、p=snextB、 p-nxt=s； snxt= p-netC、 pext=s-net；D、 s-next=pnext； nxt=;题目13非空得单向循环链表得尾结点满足（ ）（设头指针为ead,指针p指向尾结点)。选择一项：、=a、=NULLC、 p-next=hadD、pext=NUL题目14链表不具有得特点就是( )。选择一项：、 可随机访问任一元素B、 插入删除不需要移动元素C、 不必事先估计存储空间D、所需空间与线性表长度成正比题目5带头结点得链表为空得判断条件就是（ )（设头指针为hed）。选择一项：A、headex=NULLB、 hed-next=eadC、 ed =NULLD、 head!=NUL题目16在一个长度为n得顺序表中为了删除第5个元素，由第个元素开始从后到前依次移动了个元素。则原顺序表得长度为（ )。选择一项：、 21、 19、 20、 25题目1有关线性表得正确说法就是( )。选择一项：、 表中得元素必须按由小到大或由大到下排序B、除了一个与最后一个元素外，其余元素都有一个且仅有一个直接前驱与一个直接后继C、 线性表至少要求一个元素D、 每个元素都有一个直接前驱与一个直接后继题目18向一个有7个元素得顺序表中插入一个新元素,并保持原来得顺序不变，平均要移动（ )个元素。选择一项：、 8B、 7C、 6D、 6、5题目一个顺序表第一个元素得存储地址就是90，每个元素得长度为2，则第6个元素得地址就是（ ).选择一项:A、102B、8C、 1D、 106题目20在双向循环链表中,在p所指得结点之后插入指针f所指得新结点,其操作步骤就是（ )。选择一项:A、 fpior； fnet=pnext; pnxt=f;pextpri=f;B、 pnxt=f；frio=p；pextprir=f；fnet=pne；C、 frior=p;f-np-t; petprior=f； net=；、 p-next; pnext-prio=;f-riop；fnt=ext；二、填空题(每小题2分,共分）题目21在一个长度为n得顺序存储结构得线性表中，向第i（in+1)个元素之前插入新元素时，需向后移动回答个数据元素。题目2从长度为得采用顺序存储结构得线性表中删除第i（in+)个元素，需向前移动回答个元素。题目2数据结构按结点间得关系,可分为4种逻辑结构:_集合_、_线性结构、_、_树形结构_、_图状结构_.题目24数据得逻辑结构在计算机中得表示称为_存储结构_或_物理结构_.题目25除了第1个与最后一个结点外，其余结点有且只有一个前驱结点与后继结点得数据结构为回答,每个结点可有任意多个前驱与后继结点数得结构为回答。答案：线性结构,非线性结构题目26数据结构中得数据元素存在多对多得关系称为回答结构。题目27数据结构中得数据元素存在一对多得关系称为回答结构。题目28数据结构中得数据元素存在一对一得关系称为回答结构。题目9要求在个数据元素中找其中值最大得元素，设基本操作为元素间得比较。则比较得次数与算法得时间复杂度分别为_ n1_与_ O(n)_.题目30在一个单链表中所指结点之后插入一个所指结点时，应执行回答与pnxt=s;得操作。题目31设有一个头指针为head得单向循环链表,p指向链表中得结点,若p-ne=回答，则p所指结点为尾结点。题目3在一个单向链表中，要删除所指结点,已知指向p所指结点得前驱结点。则可以用操作回答.正确答案就是:q-next=-next;题目3设有一个头指针为head得单向链表，指向表中某一个结点，且有pnxt= =NUL，通过操作回答，就可使该单向链表构形成单向循环链表。正确答案就是：pnext=had；题目34单向循环链表就是单向链表得一种扩充,当单向链表带有头结点时，把单向链表中尾结点得指针域由空指针改为回答;当单向链表不带头结点时，则把单向链表中尾结点得指针域由空指针改为指向回答.答案：头结点得指针、指向第一个结点得指针题目3线性链表得逻辑关系就是通过每个结点指针域中得指针来表示得。其逻辑顺序与物理存储顺序不再一致，而就是一种回答存储结构，又称为回答。答案：链式、链表三、问答题（第1小题7分,第2小题分)题目简述数据得逻辑结构与存储结构得区别与联系,它们如何影响算法得设计与实现？答：若用结点表示某个数据元素，则结点与结点之间得逻辑关系就称为数据得逻辑结构.数据在计算机中得存储表示称为数据得存储结构。可见，数据得逻辑结构就是反映数据之间得固有关系,而数据得存储结构就是数据在计算机中得存储表示。尽管因采用得存储结构不同，逻辑上相邻得结点，其物理地址未必相同，但可通过结点得内部信息,找到其相邻得结点,从而保留了逻辑结构得特点。采用得存储结构不同，对数据得操作在灵活性,算法复杂度等方面差别较大。题目37解释顺序存储结构与链式存储结构得特点，并比较顺序存储结构与链式存储结构得优缺点。答：顺序结构存储时，相邻数据元素得存放地址也相邻，即逻辑结构与存储结构就是统一得，要求内存中存储单元得地址必须就是连续得.优点：一般情况下，存储密度大，存储空间利用率高。缺点:（)在做插入与删除操作时,需移动大量元素;(2）由于难以估计,必须预先分配较大得空间，往往使存储空间不能得到充分利用;(3）表得容量难以扩充。链式结构存储时，相邻数据元素可随意存放,所占空间分为两部分,一部分存放结点值，另一部分存放表示结点间关系得指针。优点:插入与删除元素时很方便,使用灵活。缺点:存储密度小，存储空间利用率低。四、程序填空题（每空1分，共1分)题目3下列就是用尾插法建立带头结点得且有n个结点得单向链表得算法，请在空格内填上适当得语句。 NODEcreat1(n）/* 对线性表（1，2,、,n)，建立带头结点得单向链表/ NDE e，*p，*q； nt i； p=（OE ）maloc（ieof(ND）)； headp； q=p；pext=NL； for(i=1;=n;i) =（ND *)malloc（sizeof(NODE)）； 回答; 回答； 回答； 回答; retrn（had）; 题目3下列就是用头插法建立带头结点得且有n个结点得单向链表得算法,请在空格内填上适当得语句。 NOD *eate2(n) /*对线性表（n，n1，、，），建立带头结点得线性链表/ NDE*ead，*p,q； in i； p（NODE *）mllc(sief(NODE）); 回答； p-nx=NL; 回答; for（i=1;i=；i+） p=(OD ）maloc(sizeof(NDE）); -data=i； i（i1） 回答; else 回答; 回答; return（had)； 题目40下列就是在具有头结点单向链表中删除第个结点得算法,请在空格内填上适当得语句. nt delete（NOE *hd,ti） NOD ,q； n ； qhed; =0; whie（q！NLL)&（j) /*找到要删除结点得直接前驱,并使指向它*/ 回答； +； i(q=NULL) etn(0)； 回答 回答； free(p)； rtn（1)； 题目4下列就是在具有头结点单向列表中在第i个结点之前插入新结点得算法,请在空格内填上适当得语句。 t nsert（ODE hea，int x,inti) NDE *，p; nt j； q=head；j=0； il（q！=NULL)&(ji-1)） =qnxt；+； i(q=NUL） rtrn（0）； p回答； pata=; 回答正确正确答案就是：p-nextqnx获得、00分中得、00分;回答； rtn（1)； 形考任务题目1若让元素1，2,3依次进栈，则出栈顺序不可能为（ ）。选择一项：、 2，1，B、 ，1,2C、 3,2,题目2一个队列得入队序列就是1，2，3，4。则队列得输出序列就是( ）。选择一项:A、 ，2，4，1B、 1,2，3，、 4,3，2,D、 1，4,3，2题目向顺序栈中压入新元素时，应当()。选择一项：A、 先存入元素,再移动栈顶指针、先移动栈顶指针，再存入元素C、 先后次序无关紧要D、 同时进行题目4在一个栈顶指针为tp得链栈中，将一个指针所指得结点入栈，应执行( )。选择一项：A、petop；top=p;、 topnext=p；C、nex=o-nxt；top=opnext；D、 p-nex=topnex；top-ext=p;题目5在一个栈顶指针为top得链栈中删除一个结点时,用 x保存被删结点得值，则执行( ）。选择一项:A、 xtp-dta；to=topext；B、x=tp-aa;C、 optopnxt；x=tpdaa；、=t；tp=topnext；题目6判断一个顺序队列（最多元素为m)为空得条件就是（ ）。选择一项:、rea=m-1B、 ront=r+1C、frotrea题目判断一个循环队列Q（最多元素为）为满得条件就是（ ）.选择一项：A、 rea!= （Qfront)mB、 frnt=QeaC、 Qfo=（Q-rear+)%m、 Q-fronQe +1题目8判断栈满(元素个数最多n个)得条件就是（ )。选择一项：A、 tp=0、 top!=0C、 top=1D、 p=1题目9设有一个阶得对称矩阵A（第一个元素为a1，1),采用压缩存储得方式，将其下三角部分以行序为主序存储到一维数组B中(数组下标从1开始),则矩阵元素6,2在一维数组B中得下标就是（ )。选择一项：A、 17、23C、1、 28题目10在解决计算机主机与打印机之间速度不匹配问题时通常设置一个打印数据缓冲区，主机将要输出得数据依次写入缓冲区中，而打印机则从缓冲区中取出数据打印,该缓冲区应该就是一个( ）结构。选择一项:A、队列B、 先性表C、 数组D、 堆栈题目11一个递归算法必须包括（ ）。选择一项：A、 递归部分B、 迭代部分C、终止条件与迭代部分D、 终止条件与递归部分题目2在一个链队中，假设f与分别为队头与队尾指针，则删除一个结点得运算为（）。选择一项：A、f=-nex；B、 r=rne；C、 r=f-next；D、 f-ext；题目13在一个链队中,假设f与r分别为队头与队尾指针，则插入s所指结点得运算为（)。选择一项：A、 sext=r；r=s；B、 r-nx=s;r=;C、 snext=f;=s;D、 fnext=;f=s;题目14数组a经初始化char a “Eglis”;a7中存放得就是（）.选择一项：、 h”B、 字符串得结束符C、 变量hD、 字符h题目15设主串为“ABCDcdFaBc”，以下模式串能与主串成功匹配得就是（ ）。选择一项:A、 CdB、 c、bcD、 AB题目16字符串 a1=AEJING，2=AEI,a3=EFAG，a4=EFI”中最大得就是（）.选择一项：、 a3、 aC、 a4D、题目17两个字符串相等得条件就是( ).选择一项:A、 两串得长度相等,并且对应位置上得字符相同B、 两串得长度相等、 两串得长度相等，并且两串包含得字符相同、两串包含得字符相同题目1一维数组A采用顺序存储结构,每个元素占用个字节,第6个元素得存储地址为100，则该数组得首地址就是（)。选择一项：A、 6B、0、 2、 0题目19一个非空广义表得表头( ）。选择一项:、 可以就是子表或原子B、 只能就是原子C、 不可能就是原子D、 只能就是子表题目0对稀疏矩阵进行压缩存储,可采用三元组表，一个10行8列得稀疏矩阵,其相应得三元组表共有6个元素,矩阵A共有( ）个零元素。选择一项：A、 8、 1C、 72、 74题目21对稀疏矩阵进行压缩存储，可采用三元组表，一个10 行8列得稀疏矩阵共有73个零元素,A得右下角元素为6，其相应得三元组表中得第7个元素就是（ ).选择一项：A、(10，8,7)B、 (1，8，6）C、 （7，,8）、（,8，0)题目对一个栈顶指针为top得链栈进行入栈操作，通过指针变量p生成入栈结点,并给该 结点赋值a，则执行： p=(struct noe ）mallc（szeof（stct noe)；-dat=a；与( ）.选择一项：A、 pxt=top；ptop；B、 -extp；p=top;C、exop；topp;D、 top=topext；ptop;题目23头指针为ha得带头结点得单向链表为空得判定条件就是( ）为真.选择一项:A、 head=NLB、 hadnxt=NULLC、headnex！NULD、 hanex！=NUL题目2设有一个对称矩阵A,采用压缩存储得方式,将其下三角部分以行序为主序存储到一维数组B中（数组下标从1开始)，数组共有5个元素,则该矩阵就是( ）阶得对称矩阵。选择一项:A、 20B、5C、 1D、 5题目2数组经初始化chara=“Englsh”;a1中存放得就是( ）。选择一项:A、 n”B、字符nC、”ED、字符E二、填空题(每小题2分，共30分)题目26循环队列队头指针在队尾指针回答位置，队列就是“满状态。题目7循环队列得引入，目得就是为了克服回答。题目2判断一个循环队列（最多元素为m）为空得条件就是回答。题目29题干向一个栈顶指针为h得链栈中插入一个所指结点时,可执行回答s-next=h；与hs；操作。（结点得指针域为t)题目30从一个栈顶指针为得链栈中删除一个结点时,用x保存被删结点得值，可执行xh题目31在一个链队中，设与分别为队头与队尾指针，则插入所指结点得操作为回答与rs; r-next=s；（结点得指针域为et)题目32在一个链队中，设f与r分别为队头与队尾指针,则删除一个结点得操作为回答=fnext；. （结点得指针域为ext）题目3串就是一种特殊得线性表,其特殊性表现在组成串得数据元素都就是回答。题目34空串得长度就是回答；空格串得长度就是回答。题目35设广义表=（），（）),则表头就是_,表尾就是_,L得长度就是_。则表头就是（）,表尾就是（()），L得长度就是题目36广义表A（a,b，c），（d，e，)得表尾为回答（d，,).题目37设有阶对称矩阵A,用数组s进行压缩存储，当ij时，得数组元素aij相应于数组s得数组元素得下标为回答。（数组元素得下标从开始）题目38对稀疏矩阵进行压缩存储,矩阵中每个非零元素对应得三元组包括该元素得_、_与_三项信息.答案：行下标、列下标与非零元素值题目39循环队列用a，得一维数组存放队列元素，（采用少用一个元素得模式），设front与rear分别为队头与队尾指针，且fro与rar得值分别为与7，当前队列中得元素个数就是回答。题目40循环队列得引入,目得就是为了克服回答。三、问答题（每小题5分，共2分）题目41完成满分、00题干栈、队列与线性表得区别就是什么?答:栈就是一种先进后出得线性表，栈得插入与删除操作都只能在栈顶进行，而一般得线性表可以在线性表得任何位置进行插入与删除操作。队列就是一种先进先出得线性表，队列得插入只能在队尾进行,队列得删除只能在队头进行，而一般得线性表可以在线性表得任何位置进行插入与删除操作。题目42设栈S与队列Q得初始状态为空，元素1,2,e3，4，e5与e6依次通过，一个元素出栈后即进队列Q,若个元素出队得序列就是e2，e4,e3，e6,e，e1,则栈S得容量至少应该就是多少?出队序列就是2，e4,e3,e6，e5,e1得过程：(）e1入栈（栈底到栈顶元素就是e1)（2）e2入栈(栈底到栈顶元素就是e1,e2）（3)2出栈（栈底到栈顶元素就是e1)（4)e3入栈（栈底到栈顶元素就是1，e3）(5)4入栈(栈底到栈顶元素就是1，e3，e4)（6）e4出栈（栈底到栈顶元素就是e,e3）(7）e3出栈（栈底到栈顶元素就是e1）（)e5入栈(栈底到栈顶元素就是e,e5）（9）入栈（栈底到栈顶元素就是1，e5，e6）（1)e出栈(栈底到栈顶元素就是e1,e5）（1）e5出栈(栈底到栈顶元素就是e)（1）e出栈(栈底到栈顶元素就是空）栈中最多时有3个元素,所以栈S得容量至少就是3。题目4有5个元素,其入栈次序为:A、B、C、D、,在各种可能得出栈次序中，以元素、最先得次序有哪几个？从题中可知，要使C第一个且D第二个出栈,应就是A入栈,入栈,C入栈，C出栈，D入栈。之后可以有以下几种情况：(1)B出栈,出栈，入栈，出栈,输出序列为：CDA.（）B出栈,入栈,出栈, 出栈，输出序列为C。(3）E入栈,出栈，B出栈,A出栈，输出序列为CDEA所以可能得次序有:CDBE，BE，CDEBA题目4简述广义表与线性表得区别与联系。广义表就是线性表得得推广，它也就是n(n0)个元素a1，a2,，i,a得有限序列,其中ai或者就是原子或者就是一个广义表。所以,广义表就是一种递归数据结构，而线性表没有这种特性，线性表可以瞧成广义表得特殊情况,当都就是原子时，广义表退化成线性表。形考任务三一、单项选择题（每小题2分，共32分）题目1假定一棵二叉树中,双分支结点数为15,单分支结点数为30，则叶子结点数为( ）。选择一项：、 1B、 16C、 1D、7题目2二叉树第k层上最多有(）个结点。选择一项：A、 2k1、 2k1C、 k-1D、 2k题目设某一二叉树先序遍历为abdc,中序遍历为dba，则该二叉树后序遍历得顺序就是（ )。选择一项：A、 aedB、 abdecC、 dacD、 dc题目将含有15个结点得完全二叉树从根这一层开始,每一层从左到右依次对结点进行编号，根结点得编号为,则编号为69得结点得双亲结点得编号为( )。选择一项：A、B、 33C、 34D、 36题目5如果将给定得一组数据作为叶子数值，所构造出得二叉树得带权路径长度最小，则该树称为（)。选择一项:A、 平衡二叉树B、 完全二叉树C、 二叉树、 哈夫曼树题目在一棵度为3得树中,度为得结点个数为2，度为2得结点个数为1,则度为0得结点个数为( ）。选择一项：A、 5B、 、 7、 6题目7在一棵度具有层得满二叉树中结点总数为（ )。选择一项：、 31B、C、16D、33题目利用n个值作为叶结点得权生成得哈夫曼树中共包含有（ ）个结点。选择一项：、 n+1、 2nC、 n-1题目9利用3、8、1这四个值作为叶子结点得权，生成一棵哈夫曼树，该树中所有叶子结点中得最长带权路径长度为()。选择一项：A、 、 0C、 12D、 18题目1在一棵树中，（ )没有前驱结点。选择一项:A、叶结点、空结点、 树根结点D、 分支结点题目1设一棵有n个叶结点得二叉树，除叶结点外每个结点度数都为2，则该树共有（ )个结点。选择一项:A、 n1、 2n+、 n+D、 2n题目12在一个图中，所有顶点得度数之与等于所有边数之与得（ )倍。选择一项：A、 1B、1/2、4题目13邻接表就是图得一种( ）。选择一项：、索引存储结构B、 顺序存储结构C、 散列存储结构D、 链式存储结构题目14如果从无向图得任一顶点出发进行一次深度优先搜索即可访问所有顶点，则该图一定就是（ )。选择一项:A、一棵树B、 有回路C、完全图D、 连通图题目15图得深度优先遍历算法类似于二叉树得（ )遍历.选择一项：A、先序B、 层次C、 中序D、 后序题目已知下图所示得一个图,若从顶点V出发，按深度优先搜索法进行遍历,则可能得到得一种顶点序列为( )。选择一项:A、VVVV8V3V6V7、 VV4V8V5V36VC、 V1V2V4V8V3V5V6V7、 VV36VV2V4V5V二、填空题 (每小题分，共20分)题目7结点得度就是指结点所拥有得回答.正确答案就是:子树树木或后继结点数题目18树得度就是指回答。正确答案就是：树中所有结点得度得最大值题目19度大于0得结点称作_或_.分支结点、非终端结点题目度等于0得结点称作_或_。叶子结点、终端结点题目21在一棵树中，每个结点得_或者说每个结点得_称为该结点得_,简称为孩子。子树得根、后继结点、孩子结点题目2从根结点到该结点所经分支上得所有结点称为该结点得回答。正确答案就是：祖先题目23树得深度或高度就是指回答。正确答案就是:树中结点得最大层数题目24具有n个结点得完全二叉树得深度就是_。题目5先序遍历二叉树得得操作定义为；若二叉树为空，则为空操作，否则进行如下操作,访问二叉树得回答;先序遍历二叉树得回答，先序遍历二叉树得回答。根结点、左子树、右子树题目中序遍历二叉树得得操作定义为;若二叉树为空,则为空操作，否则进行如下操作，中序遍历二叉树得回答；访问而叉树得回答,中序遍历二叉树得回答。左子树、根结点、右子树题目27后序遍历二叉树得得操作定义为；若二叉树为空，则为空操作，否则进行如下操作，后序遍历二叉树得回答；后序遍历二叉树得回答,访问而叉树得回答.左子树、右子树、根结点题目28将树中结点赋上一个有着某种意义得实数，称此实数为该结点得回答。正确答案就是：权题目29树得带权路径长度为树中所有叶子结点得回答.正确答案就是：带权路径长度之与题目30哈夫曼树又称为回答,它就是n个带权叶子结点构成得所有二叉树中带权路径长度L回答.答案：最优二叉树,最小得二叉树题目1若以4，5，,7,8作为叶子结点得权值构造哈夫曼树，则其带权路径长度就是回答.正确答案就是：6题目32具有m个叶子结点得哈夫曼树共有回答结点。正确答案就是：m1题目3图得遍历就是从图得某一顶点出发,按照一定得搜索方法对图中回答各做回答访问得过程。答案：所有顶点； 一次题目3图得深度优先搜索遍历类似于树得回答遍历。正确答案就是：先序题目35图得广度优先搜索类似于树得回答遍历。正确答案就是:按层次题目36图常用得两种存储结构就是_与_。邻接矩阵、邻接表三、综合题（每小题8分,共4分）题目37写出如下图所示得二叉树得先序、中序与后序遍历序列。答：二叉树得定义就是递归得，所以，一棵二叉树可瞧作由根结点，左子树与右子树这三个基本部分组成,即依次遍历整个二叉树，又左子树或者右子树又可瞧作一棵二叉树并继续分为根结点、左子树与右子树三个部分,这样划分一直进行到树叶结点。(1）先序为“根左右”，先序序列为：fbgihl(2)中序为“左根右,中序序列为:abdefghi（)后序为“左右根”,后序序列为：acbedjf题目8已知某二叉树得先序遍历结果就是:,B，D，G,C，E,H,L,I,K，M，F与J,它得中序遍历结果就是：G，D,B,A，L,H,E,K，I，M，C,F与,请画出这棵二叉树,并写出该二叉树后续遍历得结果。（)二叉树图形表示如下： (）该二叉树后序遍历得结果就是：、D、L、H、K、M、E、J、C与A。题目3假设通信用得报文由9个字母A、B、D、E、F、G、H与组成，它们出现得频率分别就是:1、20、5、15、8、2、3、与3.请请用这9个字母出现得频率作为权值求：（1)设计一棵哈夫曼树;（)计算其带权路径长度WPL;(）写出每个字符得哈夫曼编码.)哈夫曼树如图4所示.图4（)其带权路径长度WP值为20。（3）每个字符得哈夫曼编码为:A:10, ：1, C：1010, D:000, E：000, F：101, ：10111， ：011，I：01题目40请根据以下带权有向图G(1）给出从结点1出发分别按深度优先搜索遍历G与广度优先搜索遍历G所得得结点序列;(）给出得一个拓扑序列;(3)给出从结点1到结点v8得最短路径.(1）深度优先遍历:1，,v3，v8,v，v7，v,6广度优先遍历:v，v2,v,v,v3，v5,v7，v（2）G得拓扑序列为：v，2,，v6,v5，v5，v3,5,v7，v8(3）最短路径为：v1,v，v5,v7,v8题目1已知无向图G描述如下：G=(V，E）=V1，V，3，V4，V5E=（V1，V2）,（V1，V4），(V2，V4），（V3，V)，（V2,5)，（V,V4）,（V，V5)（1）画出G得图示；(2）然后给出G得邻接矩阵与邻接表；(3）写出每个顶点得度。g1得图示与图g得邻接表如下图所示。 图图得邻接矩阵如下图所示： 图G得邻接矩阵图得邻接表 1、V2、V、4、V5得度分别为：，3，2,3，2 四、程序填空题（每空2分,共分）题目2部分正确获得4、00分中得2、00分题干以下就是中序遍历二叉树得递归算法得程序,完成程序中空格部分(树结构中左、右指针域分别为left与righ，数据域at为字符型,T指向根结点)。v Inorder （sructBTreeNd BT) f(BT！=NULL） 回答；回答； Inorde（Trigt);答案:（1)nore（BTlft)(2）prntf(c，BTaa）题目43以下程序就是后序遍历二叉树得递归算法得程序，完成程序中空格部分(树结构中左、右指针域分别为left与rigt，数据域ata为字符型，T指向根结点)。oid Inord （truc TreNode *BT) i（！=NL)回答； Inrer（Brigt）；回答;（1）nordr(BT-let）（）pnt（”%c，Bta)形考任务四一、单项选择题（每小题2分,共42分）题目1对线性表进行二分查找时，要求线性表必须（）.选择一项:A、以顺序存储方式B、 以顺序存储方式,且数据元素有序C、 以链接存储方式,且数据元素有序、 以链接存储方式题目2采用顺序查找方法查找