数据结构考试必过宝典.docx

《数据结构考试必过宝典.docx》由会员分享，可在线阅读，更多相关《数据结构考试必过宝典.docx（22页珍藏版）》请在三一办公上搜索。

1、期末复习：1. 数据结构是一门研究非数值计算的程序设计问题中,数据元素的、数据信息在计算 机中的以及一组相关的运算等的课程。 A.操作对象B.计算方法C.逻辑结构 A.存储结构B.关系C.运算2. 数据结构DS(Data Struct)可以被形式地定义为DS= (D 合，R是D上的. A.算法 A.操作3. 在数据结构中A.动态结构和静态结构 C.线性结构和非线性结构4. 算法分析的目的是, A.找出数据结构的合理性 C.分析算法的效率以求改进 A.空间复杂性和时间复杂性 C.可读性和文档性5. 计算机算法指的是.C.D.D.R),数据映象算法其中D是的有限集_有限集合。B.数据元素C.数据操

2、作B.映象C.存储从逻辑上可以把数据结构分成。B.紧凑结构和非紧凑结构D.内部结构和外部结构算法分析的两个主要方面是。B.研究算法中的输入和输出的关系D.分析算法的易懂性和文档性:B.正确性和简明性D.数据复杂性和程序复杂性，它必具备输入、输出和等五个特性。B.排序方法D.调度方法B.可行性、确定性和有穷性D.易读性、稳定性和安全性D.数据对象 。.关系A.计算方法解决问题的有限运算序列A.可行性、可移植性和可扩充性C.确定性、有穷性和稳定性答案：1、C,A 2、B,D 3、C 4、C,A 5、C,B1. 数据逻辑结构包括、和 三种类型，树形结构和图形结构合称为。2. 在线性结构中，第一个结,

3、前驱结点，其余每个结点有且只有个前驱结点；最后一个结点 后续结点，其余每个结点有且只有 个后续结点。3. 在树形结构中，树根结点没 结点，其余每个结点有且只有个直接前驱结点，叶子结点没有 结点，其余每个结点的直接后续结点可以。4. 在图形结构中，每个结点的前驱结点数和后续结点数可以。5. 线性结构中元素之间存在关系，树形结构中元素之间存在关系，图形结构中元素之间存在关系。6. 算法的五个重要特性是,。7. 分析下面算法(程序段)，给出最大语句频度，该算法的时间复杂度是。for (i=0;in;i+)for (j=0;jn; j+)Aij=0;8. 分析下面算法(程序段)，给出最大语句频度，该算

4、法的时间复杂度是。for (i=0;in;i+)for (j=0; ji; j+)Aij=0;9. 分析下面算法(程序段)，给出最大语句频度，该算法的时间复杂度是。s=0;for (i=0;in;i+)for （j=0;jn;j+）for （k=0;knext= =NULLC. head-next= =headD. head!=NULL8. 带头结点的单链表head为空的判定条件是。A. head= =NULLB. head-next= =NULLC. head-next= =headD. head!=NULL9. 非空的循环单链表head的尾结点（由p所指向）满足_。A. p-next= =

5、NULLB. p= =NULLC. p-next= =headD. p= =head10. 在双向循环链表的p所指结点之后插入s所指结点的操作是。A. p-right=s; s-left=p; p-right-left=s; s-right=p-right;B. p-right=s; p-right-left=s; s-left=p; s-right=p-right;C. s-left=p; s-right=p-right; p-right=s; p-right-left=s;D. s-left=p; s-right=p-right; p-right-left=s; p-right=s;11.

6、 在一个单链表中，已知q所指结点是p所指结点的前驱结点，若在q和p之间插入s结 点，则执行_。A. s-next=p-next; p-next=s; B. p-next=s-next; s-next=p;C. q-next=s; s-next=p;D. p-next=s; s-next=q;12. 在一个单链表中，若p所指结点不是最后结点，在p之后插入s所指结点，则执行。A. s-next=p; p-next=s;B. s-next=p-next; p-next=s;C. s-next=p-next; p=s;D. p-next=s; s-next=p;13. 在一个单链表中，若删除p所指结点

7、的后续结点，则执行。A. p-next= p-next-next ；B. p= p-next; p-next= p-next-next；C. p-next= p-next;D. p= p-next-next ；14. 从一个具有n个结点的单链表中查找其值等于x结点时，在查找成功的情况下，需平均 比较 个结点。A. n B. n/2 C. (n-1)/2D, (n+1)/215. 在一个具有n个结点的有序单链表中插入一个新结点并仍然有序的时间复杂度是_。A. O(1) B. O(n) C. O (n2)D. O (nlog2n)16. 给定有n个元素的向量，建立一个有序单链表的时间复杂度是。A.

8、 O(1)B. O(n) C. O (n2)D. O (n*log2n)答案：1、B2、A,C 3、B 4、D 5、C6、A7、A 8、B 9、C 10、D11、C12、B 13、A 14、D 15、B 16、C1. 单链表可以做 的链接存储表示。2. 在双链表中，每个结点有两个指针域，一个指向，另一个指向。3. 在一个单链表中p所指结点之前插入一个s (值为e)所指结点时，可执行如下操作：q=head;while (q-next!=p) q=q-next;s= new Node; s-data=e;q-next=;填空s-next=;填空4. 在一个单链表中删除p所指结点的后继结点时，应执行

9、以下操作：q= p-next;p-next=;填空delete;填空5. 在一个单链表中p所指结点之后插入一个s所指结点时，应执行s-next= 和 p-next=的操作。6. 对于一个具有n个结点的单链表，在已知p所指结点后插入一个新结点的时间复杂度是 _；在给定值为x的结点后插入一个新结点的时间复杂度是。答案：1、线性结构表2、前驱结点，后继结点3、s，p 4、q-next，q 5、p-next，s 6、O(1)，O(n)1, 设顺序表va中的数据元数递增有序。试写一算法，将x插入到顺序表的适当位置上，以 保持该表的有序性。例1设线性表L是一个递增有序表，试写一算法，将x插入L中，并使L仍

10、是一个有序表。void InsertIncreaseList(SqList *L ,DataType x)(int i;for(i=1;iLength & L-datai-1Length-1;j=i-1;j-)L-dataj+1 = L-dataj;/* 移动结点*/L-datai-1 = x;L-Length+;例2：有顺序表A和B,其元素均按从小到大的升序排列，编写一个算法将它们合并成一个 顺序表C,要求C的元素也是从小到大的升序排列。例如 A=(a,c,d,e,h,j,k)，B=(b,c,f,g),贝0，C=(a,b,c,d,e,f,g,h,j,k)void Merge(SqList *

11、La, SqList *Lb,SqList *Lc)int i,j,k;i=j=0;k=0;while (iLength-1 & jLength-1)if(La-dataidataj) InsertList(Lc,La-datai,k+1);i+;k+;elseInsertList(Lc,Lb-dataj,k+1);j+;k+;/ end while/*将La和Lb的元素插入到Lc中*/while (iLength-1) InsertList(Lc,La-datai,k+1);i+;k+;while (jLength-1) InsertList(Lc,Lb-dataj,k+1);j+;k+;例

12、3、已知L是无头结点的单链表的头指针，其中*p结点既不是首元结点，也不是尾元结 点，试写出下列操作的语句序列：(1) 在*?结点后插入*$结点；s-next=p-next;p-next=s;(2) 在*?结点前插入*结点；q=L;While(q-next!=p)q=q-next;s-next=q-next;q-next=s;(3) 在表首插入*$结点；S-next=L;L =S;(4) 在表尾插入*$结点。While(P-next!=null)P=P-next;P-next=S;S-next=null;例4、将顺序表原地逆置Typedef struct( datatype datalistsi

13、ze;Int length;Sqlist;VOid nizhi(SqList *q)int i,j; datatype x;for(i=0,j=q-length-1;idatai;q-datai=q-dataj;q-dataj=x;例5、将带头结点的单链表原地逆置Typedef struct node typedef data;Struct node *next;listnode;Typedef listnode * linklist;Vbid nizhi(linklist *L)listnode *p,*q;p=L-next;L-next=NULL;While(p)q=p-next;p-ne

14、xt=L-next;L-next=p;p=q;例6、删除顺序表中的多余元素(操作后每个元素值均不相同)Typedef struct datatype datalistsize;Int length;Sqlist;void delduoyu(SqList * L)int i,j,k;for (i=0;ilength;i+ )for(j=i+1;jlength;j+)if(L-datai=L-dataj)for(k=j+1;klength;k+)L-datak-1=L-datak;L-length-;j-;例7、删除单链表中的多余元素void DeleteListdy(linklist L)lis

15、tnode *p,*q,*r;if(p=NULL) printf(空链表！ );return;p=L-next;while(p) r=p;q=p-next;while(q) if(q-data=p-data) r-next=q-next; free(q); q=r-next; else q=q-next; r=r-next; p=p-next;_Status Delete_Between(Linklist &L,int mink,int maxk)/删除元素递增排列的链表 L 中值大于 mink且小于 maxk的所有元素 p=L;while(p-next-datanext; /p 是最后一个不

16、大于 mink 的元素if(p-next) /如果还有比mink更大的元素q=p-next;while(q-datanext; /q 是第一个不小于 maxk 的元素p-next=q;/Delete_Between2. 试写一算法，实现顺序表的就地逆置，即利用原表的存储空间将线性表(a1, a2,. an)逆 置为即,an-1, ., a1)。3. 已知线性表中的元素以值递增有序排列，并以单链表作存储结构。试写一算法，删除表 中所有大于x且小于y的元素(若表中存在这样的元素)同时释放被删除结点空间。4. 试写一算法，实现单链表的就地逆置(要求在原链表上进行)。1. 一个栈的入栈序列a, b,

17、c, d, e，则栈的不可能的输出序列是。A. edcba B. decba C. dceab D. abcde2. 若已知一个栈的入栈序列是1, 2, 3，n,其输出序列为pl, p2, p3,，pn,若p1=n, 贝0 pi为。A. i B. n=i C. n-i+1 D,不确定3. 栈结构通常采用的两种存储结构是。A.顺序存储结构和链式存储结构散列方式和索引方式链表存储结构和数组线性存储结构和非线性存储结构4. 判定一个顺序栈ST （最多元素为m0）为空的条件是。A. top !=0 B. top= =0 C. top !=m0 D. top= =m0-15. 判定一个顺序栈ST （最多

18、元素为m0）为栈满的条件是。A. top! =0 B. top= =0 C. top ! =m0 D. top= =m0-16. 栈的特点是，队列的特点是。A.先进先出B.先进后出7. 向一个栈顶指针为HS的链栈中插入一个s所指结点时，则执行。（不带空的头结点）A. HS一next=s;B. s 一next= HS一next; HS一next=s;C. s 一next= HS; HS=s;D. s 一next= HS; HS= HSnext;8. 从一个栈顶指针为HS的链栈中删除一个结点时，用x保存被删结点的值，则执行。 （不带空的头结点）A. x=HS; HS= HS-next;B. x=H

19、S-data;C. HS= HSnext; x=HSdata;D. x=HSdata; HS= HSnext;9. 一个队列的数据入列序列是1, 2, 3, 4,则队列的出队时输出序列是。A. 4, 3, 2, 1B. 1, 2, 3, 4C. 1, 4, 3, 2D. 3, 2, 4, 110. 判定一个循环队列QU （最多元素为m0）为空的条件是 。A. rear - front= =m0 B. rear-front-1= =m0C. front= = rearD. front= = rear+111. 判定一个循环队列QU （最多元素为m0, m0= =Maxsize-1）为满队列的条件

20、是。A. （rear- front）+ Maxsize）% Maxsize = =m0B. rear-front-1= =m0 C. front= =rear D. front= = rear+112. 循环队列用数组A0, m-1存放其元素值，已知其头尾指针分别是front和rear，则当前 队列中的元素个数是_。A. （rear-front+m）%mB. rear-front+1C. rear-front-1D. rear-front13. 栈和队列的共同点是。A.都是先进后出B.都是先进先出C.只允许在端点处插入和删除元素D.没有共同点答案：1、C 2、C 3、A 4、B 5、D 6、B

21、,A 7、C 8、D 9、B 10、C 11、A12、A 13、C1. 向量、栈和队列都是_结构，可以在向量的位置插入和删除元素；对于栈只能在 _插入和删除元素；对于队列只能在_插入元素和删除元素。2. 向一个长度为n的向量的第i个元素（1WiWn+1）之前插入一个元素时，需向后移动 个元素。3. 向一个长度为n的向量中删除第i个元素（IWiWn）时，需向前移动个元素。4. 向栈中压入元素的操作是。5. 对栈进行退栈时的操作是_。6. 在一个循环队列中，队首指针指向队首元素的。7. 从循环队列中删除一个元素时，其操作是_。8. 在具有n个单元的循环队列中，队满时共有 个元素。9. 一个栈的输入

22、序列是12345，则栈的输出序列43512是。10. 一个栈的输入序列是12345,则栈的输出序列12345是。答案：1、线性，任意，栈顶，队尾，队头2、n-i+1 3、n-i4、先移动栈顶指针，后存入元素5、先取出元素，后移动栈顶指针 6、前一个位置7、先移动队首元素，后取出元素8、n-1 9、不可能的10、可能的例题2、二维数组A0.7, 0.8的每个元素占6个字节，将其存储在起始地址为2000的内存 单元中，则：1）若按行优先存储，元素A6,6的地址是（）2）若按列优先存储，元素A6,6的地址是（） 答案： 例 2 （1）、 2360 （2）、 23241. 以下叙述中正确的是A. 串是

23、一种特殊的线性表B.串的长度必须大于零C.串中无素只能是字母D.空串就是空白串2. 空串与空格串是相同的，这种说法。A,正确B.不正确3. 串是一中特殊的线性表，其特殊性体现在。A. 可以顺序存储B.数据元素是一个字符C.可以链接存储D.数据元素可以是多个字符4. 设有两个串p和q，求q在p中首次出现的位置的运算称作A,连接B,模式匹配C.求子串D,求串长答案：1、A 2、B 3、B 4、B,C1. 串的两种最基本的存储方式是_。2. 两个串相等的充分必要条件是_。3. 空串是，其长度等于。4. 空格串是，其长度等于。5 .设 s= IAMATEACHER,其长度是。答案：1、顺序存储方式，链

24、式存储方式2、两个串的长度相等且对应位置的字符相同3、零个字符的串，零4、由一个或多个空格字符组成的串，其包含的空格个数 5、141. 常对数组进行的两种基本操作是_。A.建立与删除 B.索引和修改C.对数据元素的存取和修改D.查找与索引2. 二维数组M的成员是6个字符（每个字符占一个存储单元，即一个字节）组成的串，行 下标i的范围从0到8,列下标j的范围从0到9,则存放M至少需要_ _个字节；M数 组的第8列和第5行共占个字节。 A. 90B. 180C. 240D. 540 A. 108B. 114C. 54D. 603. 二维数组A中，每个元素的长度为3个字节，行下标i从0到7，列下标j

25、从0到9,从 首地址SA开始连续存放在存储器内，存放该数组至少需要的字节数是。A, 80B. 100C.240D. 2704. 二维数组A中，每个元素A的长度为3个字节，行下标i从0到7，列下标j从0到9, 从首地址SA开始连续存放在存储器内，该数组按行存放时，数组元素A74的起始地址 为。A. SA+141 B. SA+144 C. SA+222 D. SA+2255. 二维数组A中，每个元素A的长度为3个字节，行下标i从0到7，列下标j从0到9, 从首地址SA开始连续存放在存储器内，该数组按列存放时，元素A47的起始地址为。A. SA+141 B. SA+180 C. SA+222 D.

26、SA+225答案： 1、C 2、D,A 3、C 4、C 5、B1. 已知二维数组Amn采用行序为主方式存储，每个元素占k个存储单元，并且第一个元素的存储地址是LOC(A00),则Aij的地址是。2. 二维数组A1020采用列序为主方式存储，每个元素占一个存储单元并且A00的存储地址是200,则A612的地址是。3. 二维数组A10.205.10采用行序为主方式存储，每个元素占4个存储单元，并且A105的存储地址是1000,则A189的地址是。4. 求下列广义表操作的结果：(1) GetTailGetHead(a,b),(c,d);(2) GetTailGetHeadGetTail(a,b),(

27、c,d)答案：1.、 LOC (A00)+(n*i+j)*k 2、200+ (6*20+12) = 3263.、1000+(18-10)*6 +(9-5)*4 = 12084、(1). (b) , (2). (d)1、已知一棵完全二叉树有64个叶子结点，则该树可能达到的最大深度为()A. 7 B. 8C. 9 D. 102、若一棵二叉树有11个叶子结点，则该二叉树中度为2的结点个数是()A. 10 B. 11C. 12 D.不确定的3、已知一棵二叉树的顺序存储序列为：aeb$ fcd，则：1) e的左孩子是哪个结点？右孩子是哪个结点？2) d的双亲是哪个结点？答案：1、B 2、A 3、(1)无

28、 f (2) b4、假设一棵二叉树的顺序存储结构如图所示，请回答下列问题：(1) 哪个结点是根结点？A(2) 哪些结点是叶子结点？D,H(3) 哪些结点是H的祖先？A,C,E(4) 哪些结点是B的兄弟？C(5) 树的深度是多少？41 2 3 4 5 6 7 8 9 10 11 12 13 14先序遍历:中序遍历:后序遍历:ABDGCEHFBGDAHECFGDBHEFCAABC中DE中中中中中中H例题:+fab中序序列：B C AE D G H F I四已知一棵二叉树的先序序列和中序序列，请画出该二叉树。先序序列：A B C D E F G H I J中序序列：C B E D F AH G J

29、I中序遍历：(a + b *(c - d)- e / f 序遍历:- + a*b-cd/ef后序遍历：abed- * + e f / -把下面的树转化成二叉树。例题: 已知某系统在通信联系中只可能出现8种字符：abcdefgh,其概率分别为0.05, 0.29, 0.07,0.08,0.14，0.23,0.03，0.11，试据此构造哈夫曼树，要求:1）画出构造哈夫曼树的过程；2）求每个字符的哈夫曼编码。哈夫曼编码:a: 0110 b: 10 c:1110d:1111e: 110f: 00g:0111h: 010练习:设权值序列为8, 5, 3, 4, 7，据此构造棵哈夫曼树。画出构造哈夫曼树过

30、程。1. 假定在一棵二叉树中，双分支结点数为15,单分支结点数为30个，则叶子结点数为 个。A. 15 B. 16C. 17D. 472. 深度为5的二叉树至多有 个结点。A, 16 B. 32 C. 31 D. 103. 对一个满二叉树，m个树叶，n个结点，深度为h,则。A. n=h+m B. h+m=2nC. m=h-1D. n=2 h-14. 二叉树的前序遍历序列中，任意一个结点均处在其子女结点的前面，这种说法。A,正确B,错误5. 某二叉树的前序遍历结点访问顺序是abdgcefh，中序遍历的结点访问顺序是dgbaechf， 则其后序遍历的结点访问顺序是_。A. bdgcefhaB. g

31、dbecfhaC. bdgaechfD. gdbehfca6. 在一非空二叉树的中序遍历序列中，根结点的右边。A. 只有右子树上的所有结点B. 只有右子树上的部分结点C. 只有左子树上的部分结点D. 只有左子树上的所有结点7. 树的基本遍历策略可分为先根遍历和后根遍历；二叉树的基本遍历策略可分为先序遍历、中序遍历和后序遍历。这里，我们把由树转化得到的二叉树叫做这棵数对应的二叉树。结论 是正确的。A. 树的先根遍历序列与其对应的二叉树的先序遍历序列相同B. 树的后根遍历序列与其对应的二叉树的后序遍历序列相同C. 树的先根遍历序列与其对应的二叉树的中序遍历序列相同D. 以上都不对答案：1、B 2、

32、C 3、D 4、A 5、D 6、A 7、A8. 有一棵树如图所示，回答下面的问题： 这棵树的根结点是这棵树的叶子结点是 结点k3的度是:这棵树的度是； 这棵树的深度是 结点k3的子女是 结点k3的父结点是1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16179. 一棵二叉树的结点数据采用顺序 存储结构,存福于薮组t市，如囱 所示，则该二叉树的链接表示形式 另。10. 深度为k的完全二叉树至少有个结点。至多有个结点，若按自上而下，从左到 右次序给结点编号（从1开始），则编号最小的叶子结点的编号是_。答案：8、（1）k1 （2） k2,k5,k7,k4 2 3 4 k5,

33、k6 k110、2 k-1（2的K减一次幕）、2 K-1 （2的K次幕减一）、2 k-1（2的K减一次幕）11, 根据二叉树的定义，具有三个结点的二叉树有5种不同的形态，请将它们分别画出。12,假设一棵二叉树的先序序列为EBADCFHGIKJ和中序序列为ABCDEFGHIJK。请画出13.以数据集4, 5, 6, 7, 10, 12, 18为结点权值，画出构造Huffman树的每一步图示， 计算其带权路径长度为。14,假设用于通讯的电文仅有八个字母（a,b,c,d,e,f,g,h）组成，字母在电文中出现的频率分别为 0.07, 0.19, 0.02, 0.06, 0.32, 0.03, 0.2

34、1, 0.10。试为这八个字母设计哈夫曼编码。1. 三个结点的二叉树的基本形态有_5_种，三个结点的树的基本形态有_2_种。2. 一棵具有64个结点的完全二叉树的高度为 7。3. 设一棵二叉树的先序遍历序列为ABCDFEGH，中序遍历序列为BAFDCGEH，请完成下 列要求：1）画出该二叉树；2）写出该二叉树的后序遍历序列；3）将该二叉树转换成森林；4. 已知一棵二叉树的顺序存储结构如下图所示，图中“0”表示不存在的结点，1）画出该二叉树；2）求该二叉树的先序遍历序列和中序遍历序列；3）将该二叉树转换成一棵树。AB0CD00E0FG5. 设字符集为A, B, C, D, E,其对应的权值为7,

35、 5, 2, 4, 9,据此构造哈夫曼树，要求：1）画出构造哈夫曼树过程；2）求每个字符的哈夫曼编码；习题1. 在一个图中，所有顶点的度数之和等于所有边数的 倍。A. 1/2B. 1 C. 2 D. 42, 任何一个无向连通图的最小生成树。A.只有一棵B.有一棵或多棵C. 一定有多棵D.可能不存在3. 在一个有向图中，所有顶点的入度之和等于所有顶点的出度之和的 倍。A. 1/2B. 1 C. 2 D. 44. 一个有n个顶点的无向图最多有条边。A. nB. n(n-1) C. n(n-1)/2 D. 2n5. 具有4个顶点的无向完全图有 条边。A. 6 B. 12 C. 16 D. 206.

36、具有6个顶点的无向图至少应有条边才能确保是一个连通图。A. 5 B. 6 C. 7 D. 87. 在一个具有n个顶点的无向图中，要连通全部顶点至少需要 条边。A. n B. n+1 C. n-1 D. n/2答案：1、C 2、B 3、B 4、C 5、A 6、A 7、C例题：画出下图的邻接表例题 画出该有向图的邻接表和逆邻接表有向图的邻接表有向图的逆邻接表0123例深度遍历二 Vln V2 nV4 n VS nV5 nV3 nV6 nV73 广度遍历：VIn V2n V4=V8例题由U1, V2, U3, V4, U5, U6六个顶点构成的无向图的邻接矩阵如下表所示。1) 画出该无向图；2) 画

37、出该无向图的邻接表存储结构。3) 根据所画部接表，给出从定点U1出发的深度和广度优先遍历序列.VIV2V3V4V5V6VI011000V2100101V3100001V4010010V5000101V6011010例题深度遍历序列：V1 V2 V4 V5 V6 V3广度遍历结彩V1 V2 V3 V4 V6 V5一个有向图有5个项点，6条祗.点对展示为1,5个顶点编号为L L L 3, 4；其租用顶 0, , , ,要求:(1 )色出该有向图；(1)建主该有向图邻接表再储绻构；(3 )写出从。号顶点出发的深度优先牧索与广度牧索的序列.广度：0 1 2 43;10. 已知一个图如图7.1所示，若从

38、顶点a出发按深度搜索法进行遍历，则可能得到 的一种顶点序列为_;按宽度搜索法进行遍历，则可能得到的一种顶点序列 为_。B. e,c,f,e,b,dD. a,e,d,f,c,bB. a,b,c,e,f,dD. a,c,f,d,e,b A. a,b,e,c,d,fC. a,e,b,c,f,d A. a,b,c,e,d,fC. a,e,b,c,f,d11已会有向图的令表存储结构如图7.晰示 根据有向图的深度优先遍历算法，从顶点E 出发，所得到的顶点序列是_。虬 vlj v3j v5jB. vljv2jv3jv4jv5C. vlj v3j v5j v2D. vljv4jv3jv5jv2根据有向图的宽度

39、优先遍历算法，从顶点v 出发，所得到的顶点序列是_。虬 vljv3j v5B. vljv3jv2jv4jv5C. vljv3j v5j v4D. vljv4jv3jv5jv212. 采用邻接表存储的图的深度优先遍历算法类似于二叉树的。A.先序遍历B.中序遍历C,后序遍历D.按层遍历13. 采用邻接表存储的图的宽度优先遍历算法类似于二叉树的。A.先序遍历B.中序遍历C,后序遍历D.按层遍历14. 判定一个有向图是否存在回路除了可以利用拓扑排序方法外，还可以利用A.求关键路径的方法B.求最短路径的Dijkstra方法C,宽度优先遍历算法D.深度优先遍历算法15. 关键路径是事件结点网络中。A.从源

40、点到汇点的最长路径B.从源点到汇点的最短路径C.最长的回路D.最短的回路16. 下面不正确的说法是。(1) 在AOE网中，减小一个关键活动上的权值后，整个工期也就相应减小;(2) AOE网工程工期为关键活动上的权之和；(3) 在关键路径上的活动都是关键活动，而关键活动也必在关键路径上。A, (1)B, (2)C, (3)D. (1)、(2)18. 在图7.3所示的拓朴排列的结果序列为。B,516234A,12563419. 一个有n个顶点的无向连通图，它所包含的连通分量个数为。A.0B.1 C.nD.n+120. 对于一个有向图，若一个顶点的入度为k1,、出度为k2,则对应邻接表中该顶点单链表 中的结点数为。A.k1 B.k2 C.k1-k2 D.k1+k221. 对于一个有向图，若一个顶点的入度为k1,、出度为k2,则对应逆邻接表中该顶点单链 表中的结点数为。A.k1 B.k2 C.k1-k2 D.k1+k21. n个顶点的连通图至少 条边。2. 在无权图G的邻接矩阵A中，若(vi,vj域Vvi,vj属