中北大学数据结构习题

1、算法与数据结构习题第一到三章习题选择题1 .对于顺序存储的线性表，访问结点和增加、删除结点的时间复杂度为(C)0A.O(n)O(n)B.O(n)O(1)C.O(1)O(n)D.O(1)O(1)2 .非空的循环单链表 head 的尾结点 p 满足(A)。A.P-next=headB.P-next=NILC,p=NILD,p=head3 .在单链表指针为 p 的结点之后插入指针为 s 的结点，正确的操作是：(B)oA.p-next=s;s-next=p-next;Bs-next=p-next;p-next=s;C.p-next=s;p-next=s-next;Dp-next=s-next;p-ne

2、xt=s;4 .在双向链表指针 p 的结点前插入一个指针 q 的结点操作是(C)注：双向链表的结点结构为(pre,data,next)。A. p-pre=q;q-next=p;p-pre-next=q;q-pre=q;B. p-pre=q;p-pre-next=q;q-next=p;q-pre=p-pre;C. q-next=p;q-pre=p-pre;p-pre-next=q;p-pre=q;D. q-pre=p-pre;q-next=q;p-pre=q;p-pre=q;5 .栈的特点是(B),队列的特点是(A)，栈和队列都是(AA)。若进栈序列为 1,2,3,4 则(C)不可能是一个出栈序

3、列(不一定全部进栈后再出栈)；若进队列的序列为 1,2,3,4 则(E)是一个出队列序列。，:A.先进先出 B.后进先出 C.进优于出 D.出优于进：A.顺序存储的线性结构 B.链式存储的线性结构C.限制存取点的线性结构 D.限制存取点的非线性结构，:A.3,2,1,4B.3,2,4,1C.4,2,3,1D.4,3,2,1E.1,2,3,4F.1,3,2,46 .一个栈的输入序列为 123,n,若输出序列的第一个元素是 n,输出第 i(1=inext;p2=pb-next;pa-next=null;s1=0;s2=0;Q.front=(Q.front+1)%Q.queuesize;Q.rear

4、=(Q.rear+1)%Q.queuesize;A.1 和 5B.2C.414.循环队列 A0.m-1存放其元素值，用则当前队列中的元素数是(A)0A.(rear-front+m)%mB.rear-front+1和 2D.5 和 1front 和 rear 分别表示队头和队尾,C.rear-front-1D.rear-frontWhile(p1&p2)if(p1-datadata)p=p1;p1=p1-next;s2=s2+1;delete(p);elseif(p1-datap2-data)p2=p2-next;else(p1-data=p2-data)p=p1;p1=p1-next;

5、p-next=pa-next;pa-next=p;p2=p2-next;s1=s1+1;While(p1)p=p1;p1=p1-next;delete(p);s2=s2+1解：本程序段功能是将 pa 和 pb 链表中的值相同的结点保留在 pa 链表中(pa 中与 pb中不同结点删除)，pa 是结果链表的头指针。链表中结点值与从前逆序。S1 记结果链表中结点个数(即 pa 与 pb 中相等的元素个数)。S2 记原 pa 链表中删除的结点个数。算法题1.写出下图双链表中对换值为 23 和 15 的两个结点相互位置时修改指针的有关语句。结点结构为：(pre,data,next)解：设 q=p-pre

6、;贝 Uq-next=p-next;p-next-pre=q;p-pre=q-pre;q-pre-next=p;p-next=q;q-pre=p2 .顺序结构线性表 LA 与 LB 的结点关键字为整数。LA 与 LB 的元素按非递减有序，线性表空间足够大。试给出一种高效算法，将 LB 中元素合到 LA 中，使新的 LA的元素仍保持非递减有序。高效指最大限度的避免移动元素。解：VoidUnion(seqlistLA,seqlistLB)m=LA.length;n=LB.length;k=m+n-2;i=m-1;j=n-1;while(i=0&j=0)if(LA.elemi=LB.elem

7、j)LA.elemk=LA.elemi;k=k-1;i=i-1;elseLA.elemk=LB.elemj;k=k-1;j=j-1;while(j=0)LA.elemk=LB.elemj;k=k-1;j=j-1;3 .给定一个带表头结点的单链表，设 head 为头指针，结点的结构为(data,next),data 为整型元素，next 为指针；试写出算法：按递增次序输出单链表中各结点的数据元素，并释放结点所占的存储空间。(要求；不允许使用数组作辅助空间)解：voidMiniDelete(LinkedListhead)LinkedList*pre,*p,*u;while(head-next!=n

8、ull)/循环到仅剩头结点。pre=head;p=pre-next;/p 为工作指针,pre 为最/4 值的前驱while(p-next!=null)if(p-next-datanext-data)pre=p；p=p-next;/记住当前最小值结点的前驱print(%2d,pre-next-data);/输出最小值。u=pre-next;pre-next=u-next;free(u);/删除最小结点free(head)；/释放头结点。4,试写一算法在带头结点的单链表结构上实现线性表操作 Locate(L,x);解：intLocateElem_L(LinkList&L,ElemTypex

9、)inti=0;LinkListp=L;while(p&p-data!=x)p=p-next;i+;if(!p)return0;elsereturni;5,已知单链表中的元素以值递增有序排列。试写一高效的算法，删除表中所有值大于mink 且小于 maxk 的元素，同时释放被删结点空间。解：voiddelete(LinkList&L,intmink,intmaxk)p=L-next;pre匚umaxk=maL?cldatanext;/查找第一个值mink 的结点if(P)while(p&p-datanext;/查找第一个值maxk 的结点q=pre-next;pre-ne

10、xt=p;/修改指针while(q!=p)s=q-next;deleteq;q=s;/释放结点空间/delete6.试写一高效的算法，删除表中所有值相同的多余元素(使得操作后的线性表中所有元素的值均不相同)，同时释放被删结点空间，并分析你的算法的时间复杂度。已知一个非纯集合 B,试构造一个纯集合 A,使 A中只包含 B中所有值各不相同的数据元素从集合 B 取出物件放入集合 A要求集合 A 中同样物件不能有两件以上因此，算法的策略应该和例 2-1 基本相同，差别仅在于集合 A 的初始状态是“空集”voidunion(List&La,ListLb)InitList(La);/构造(空的)线

11、性表 LALa_len=ListLength(La);Lb_len=ListLength(Lb);for(i=1;i=Lb_len;i+)GetElem(Lb,i,e);/取 Lb 中第 i 个数据元素赋给 eif(!LocateElem(La,e,equal()ListInsert(La,+La_len,e);/LaG 未存在和 e 相同的数据元素，则插入之/for/union例如：(2,3,3,5,6,6,6,8,12)对集合 B 而言，值相同的数据元素必定相邻对集合 A 而言，数据元素依值从小至大的顺序插入因此，数据结构改变了，解决问题的策略也相应要改变。voidpurge(List&a

12、mp;La,ListLb)InitList(LA);La_len=ListLength(La);Lb_len=ListLength(Lb);/求线性表的长度for(i=1;i=Lb_len;i+)GetElem(Lb,i,e);/取 Lb 中第 i 个数据元素赋给 eif(ListEmpty(La)|!equal(en,e)ListInsert(La,+La_len,e);en=e;/La 中不存在和 e 相同的数据元素，则插入之/for/purge第四章串习题1 .下面关于用的的叙述中，哪一个是不正确的？(B)A.用是字符的有限序列 B.空用是由空格构成的用C.模式匹配是用的一种重要运算 D

13、.用既可以采用顺序存储，也可以采用链式存储2 .设有两个用 p 和 q,其中 q 是 p 的子用，求 q 在 p 中首次出现的位置的算法称为(C)A.求子用 B.联接 C.匹配 D.求用长3 .用ababaaababaa的 next 数组为(C)。A.012345678999B.012121111212C.011234223456D.01230123223454 .字符用ababaabab的 nextval 为(A)A.(0,1,0,1,0,4,1,0,1)B.(0,1,0,1,0,2,1,0,1)C.(0,1,0,1,0,0,0,1,1)D.(0,1,0,1,0,1,0,1,1)5、设字符用

14、 S=aabaabaabaac,T=aabaac(1)给出 S 和 T 的 next 值和 nextval 值；(2)若 S 作主用，T 作模式用，试给出利用 BF 算法和 KMPJ 法的匹配过程。解：(1)S 的 next 与 nextval 值分另为 012123456789 和 002002002009;t 的 next 与 nextval 值分别为 012123 和 002003。(2)利用 BF 算法的匹配过程:第趟匹酉己：aabaabaabaacaabaac(i=6,j=6)aabaac(i=6,j=6)第二趟匹酉己：aabaabaabaacaa(i=3,j=2)(aa)baac第

15、三趟匹酉己：aabaabaabaaca(i=3,j=1)(成功)(aa)baac第四趟匹酉己：aabaabaabaacaabaac(i=9,j=6)第五趟匹酉己：aabaabaabaacaa(i=6,j=2)第六趟匹酉己：aabaabaabaaca(i=6,j=1)第七趟匹酉己：aabaabaabaac利用 KMPJ 法的匹配过程:第趟匹酉己：aabaabaabaac第二趟匹酉己：aabaabaabaac第三趟匹酉己：aabaabaabaac第6章树和二叉树习题选择题1、 已知一算术表达式的中缀形式为 A+B*C-D/E,后缀形式为 ABC*+DE/-,其前缀形式为（D）A. -A+B*C/D

16、EB.-A+B*CD/EC.-+*ABC/DED.-+A*BC/DE2、设森林 F 中有三棵树，第一，第二，第三棵树的结点个数分别为 M1,M2 和M3 与森林 F 对应的二叉树根结点的右子树上的结点个数是（D）。3、有关二叉树下列说法正确的是（A.二叉树的度为 2B. 一棵二叉树白度可以小于 2C.二叉树中至少有一个结点的度为D.二叉树中任何一个结点的度都为 4、二叉树的第 I 层上最多含有结点数为（C）A.2IB.2I-1-1C.2I-1D.2I-15、一个具有 1025 个结点的二叉树的高八为（C）A.11B.10C.11 至 1025 之间 D解析：具有 n6、高度为 K 的二叉树最大

17、的结点数为（C）。A.2kB.2k-1C.2k-1D.2k-1-17、利用二叉链表存储树，则根结点的右指针是（C）。A.指向最左孩子 B.指向最右孩子C.空 D.非空8、对二叉树的结点从 1 开始进行连续编号，要求每个结点的编号大于其左、右孩子的编号，同一结点的左右孩子中，其左孩子的编号小于其右孩子的编号，可采用（C）次序的遍历实现编号。A.先序 B.中序 C.后序 D.从根开始按层次遍历9、某二叉树中序序列为 A,B,C,D,E,F,G,后序序列为 B,D,C,A,F,G,E 则先序序列是：BA.E,G,F,A,C,D,BB.E,A,C,B,D,G,FC.E,A,G,C,F,B,DD.上面的

18、都不对10、上题的二叉树对应的森林包括多少棵树（B）A.lB.2C.3D.概念上是错误的11、一棵非空的二叉树的先序遍历序列与后序遍历序列正好相反，则该二叉树一定满足（C）A.所有的结点均无左孩子 B.所有的结点均无右孩子C.只有一个叶子结点 D.是任意一棵二叉树12、在二叉树结点的先序序列，中序序列和后序序列中，所有叶子结点的先后顺序（B）A.都不相同 B.完全相同成功）aabaac(i=13,j=7)A.M1B.M1+M2C.M2+M310 至 1024 之间C.先序和中序相同，而与后序不同 D.中序和后序相同，而与先序不同 13、在完全二叉树中，若一个结点是叶结点，则它没（C）。A.左子

19、结点 B.右子结点C.左子结点和右子结点 D.左子结点，右子结点和兄弟结点14、n 个结点的线索二叉树上含有的线索数为（C）A.2nB.n-lC.n+1D.n（解析：一棵 n 结点树包含 n-1 条边，而每个结点有两个指针域即总共 2n 个指针，减去表示边的指向关系（即左右子树）的 n-1 条边，剩下 n+1 条边即为线索。）15、下述编码中哪一个不是前缀码（B）。A.（00,01,10,11）B.（0,1,00,11）C.（0,10,110,111）D.（1,01,000,001）（解析：一组编码中任何一个编码均不为其他编码的前缀.避免了多义性，且缩短了报文总长）16、在下述结论中，正确的是

20、（D）只有一个结点的二叉树的度为 0；二叉树的度为 2;二叉树的左右子树可任意交换；深度为 K 的完全二叉树的结点个数小于或等于深度相同的满二叉树。A.B.C.D.17、若一棵二叉树具有 10 个度为 2 的结点，5 个度为 1 的结点，则度为 0 的结点个数是（B）A.9B.11C.15D.不确定（解析： 任意一棵二叉树， 度为零的节点即叶子节点的数比度为二的节点多一。 ） 18、具有 10 个叶结点的二叉树中有（B）个度为 2 的结点A.8B.9C.10D.1l19、一棵完全二叉树上有 1001 个结点，其中叶子结点的个数是（D）（1023 是满二叉树，有 512 片叶子。1001 比 1

21、023 少 22 个结点，所以有 512-22+22/2=501 片叶子。511 是满二叉树，有 256 片叶子。1001 比 511 多 490 个结点，所以有 256+490-（490+1）/2=501 片叶子。所以答案就是 501 了。）A.250B.500C.254D.50120、有 n 个叶子的哈夫曼树的结点总数为（D）。A,不确定 B.2nC.2n+1D.2n-121、二叉树的先序遍历和中序遍历如下：先序遍历：EFHIGJK 中序遍历:HFIEJKG。该二叉树根的右子树的根是（C）。A、EB、FC、GD、H22、设森林 F 对应的二叉树为 B,它有 m 个结点，B 的根为 p,p

22、的右子树结点个数为 n,森林 F 中第一棵树的结点个数是（A）A.m-nB.m-n-1C.n+1D.条件不足，无法确定23、用一维数组存储二叉树时，总是以（D）遍历顺序存储结点A.先序 B.中序 C.后序 D,按层次遍历24、对一棵二叉树进行层次遍历时，应借助于一个（D）。A.顺序表 B.数组 C.栈 D.队列25、某二叉树的先序序列和后序序列正好相反，则该二叉树一定是（C）的二叉树。A.空或只有一个结点 B.任一结点无左子树 C,高度等于其结点数 D.任一结点无右子树26、设树 T 的度为 4,其中度为 1,2,3 和 4 的结点个数分别为 4,2,1,1 则 T 中的叶子数为（D）A.5B

23、.6C.7D.8（设度为 0 的结点数为 n0,度为 1 的结点数为 n1,度为 2 的结点数为 n2,度为 3 的结点数为 n3,度为 4 的结点数为 n4,那么这棵树总的结点数为 n0+n1+n2+n3+n4;又因为树中的每个结点（除了根结点外）都有一个指针指向它，那么这棵树总的结点数为总的指针数加上 1;总的指针数=1*n1+2*n2+3*n3+4*n4;故有：1+1*n1+2*n2+3*n3+4*n4=n0+n1+n2+n3+n4;从而有n0=1+n2+2*n3+3*n4=1+2+2*1+3*1=8;）27、将一棵树 t 转换为孩子一兄弟链表表示的二叉树 h,则 t 的后根序遍历是 h

24、 的（B）A.先序遍历 B.中序遍历 C.后序遍历28、某二叉树 T 有 n 个结点，设按某种顺序对 T 中的每个结点进行编号，编号为 1,2,n,且有如下性质：T 中任一结点 V,其编号等于左子树上的最小编号减 1,而 V 的右子树的结点中，其最小编号等于 V左子树上结点的最大编号加 1。这时是按（B）编号的。A.中序遍历序列 B.先序遍历序列 C.后序遍历序列 D.层次顺序应用题1、从概念上讲，树，森林和二叉树是三种不同的数据结构，将树，森林转化为二叉树的基本目的是什么，并指出树和二叉树的主要区别。答：树的孩子兄弟链表表示法和二叉树二叉链表表示法，本质是一样的，只是解释不同，也就是说树（森

25、林的特例）可用二叉树唯一表示，并可使用二叉树的一些算法去解决树和森林中的问题。树和二叉树的区别有：一是二叉树的度至多为 2,树无此限制；二是二叉树有左右子树之分，即使在只有一个分枝的情况下，也必须指出是左子树还是右子树，树无此限制。2、试找出满足下列条件的二叉树1）先序序列与后序序列相同；2）中序序列与后序序列相同；3）先序序列与中序序列相同；1）、既不含左子树，也不含右子树的二叉树。2）、不含右子树的二叉树。3)、不含左子树的二叉树。3、已知一棵度为 k 的树中有 ni个度为 1 的结点，奥个度为 2 的结点，一个度为 k 的结点，问该树中有多少个叶子结点？解：根据树的定义，在一颗树中，除树

26、根结点外，每个结点有且仅有一个前驱结点，也就是说，每个结点与指向它的一个分支一一对应，所以除树根结点之外的结点树等于所有结点的分支数，即度数，从而可得树中的结点数等于所有结点的度数加 1。总结点数为1n12n23n3knk而度为 0 的结点数就应为总结点数减去度不为 0 的结点数的总和，即kn0=1n12n23n3.knk-(nn2n3nk)=1%(i1)ni-J5、用一维数组存放的一棵完全二叉树如下图所示:ABCDEFGHIJKL写出后序遍历该二叉树时访问结点的顺序。解析：用一维数组存储二叉树时，总是以层次遍历顺序存储结点答：HIDJKEBLFGCA6、对下图所示二叉树分别按先序、中序、后序

27、遍历，给出相应的结点序列，同时给二叉树加上中序线索。(1)先序序列：ABDEHCFG(2)中序序列：DHEBAFCG(3)后序序列：HEDBFGCAA7、设一棵二叉树的先序、中序遍历序列分别为先序遍历序列：CnullABDFCEGH中A序遍历 JWhBFDAGEHC(1)画出这棵二叉树。(2)将这棵二叉树转换成对应的树(或森林)尸Q(0(8、将森林转换成对应的二叉树 oa11i?J)cMJo)Pb9、一棵二叉树的先序、中序、后序序列如下，其中一部分未标出，请构造出该二叉树。先序序列：_CDE_GHI_K 中序序列：CB_FA_JKIG 后序序列：EFDBJIHA12345678910Lchil

28、d00237580101DataJHFDBACEGIRchild0009400000其中 BT 为树根结点的指针，具值为 6,Lchild,Rchild 分别为结点的左、右孩子指针域,data 为结点的数据域。试完成下列各题：(l)画出二叉树 BT 的逻辑结构；(2)写出按先序、中序、后序遍历该二叉树所得到的结点序列；(3)画出二叉树的后序线索树。先序序列：ABCEDFHGIJ中序序列：ECBHFDJIGA后序序列：ECHFJIGDBA11、给定集合15,3,14,2,6,9,16,17,(1)构造相应的 huffman 树，(2)计算它的带权路径长度，(3)写出它的 huffman 编码。编

29、码为：15:111,3:10101,14:110,2:101006:10119:10016:0017:01字符weightparentlchrch1A38002B1212003C710004D49005E28006F810007G11110012、已知下列字符 A、B、C、DE、F、G 的权值分别为 3、12、7、4、2、8,试填写出其对应哈夫曼树11,nullHT 的存储结构的初态和终859519911481015123611201397122713210134701112第七章图习题选择题1、设无向图的顶点个数为 n,则该图最多有（B）条边。_一_2A.n-1B.n（n-1）/2C.n（n

30、+1）/2D.0E.n2、一个 n 个顶点的连通无向图，其边的个数至少为（A）。A.n-1B.nC.n+1D.nlogn；3、要连通具有 n 个顶点的有向图，至少需要（B）条边。A.n-lB.nC.n+lD.2n4、一个有 n 个顶点的图，最少有（B）个连通分量，最多有（D）个连通分量。A.0B.1C.n-1D.n5、在一个无向图中，所有顶点的度数之和等于所有边数（B）倍，在一个有向图中，所有顶点的入度之和等于所有顶点出度之和的（C）倍。A.1/2B.2C,1D6、下列哪一种图的邻接矩阵是对称矩阵？（B）A.有向图 B.无向图 C.AOD.AO 如7、无向图 G=(V,E),E=(a,b),(

31、a,e),(a,c),(b,e),(c,f),(f,d),(e,d)历,得到的顶点序列正确的是(D)A.a,b,e,c,d,fBC.a,e,b,c,f,dD其中：V=a,b,c,d,e,f,对该图进行深度优先遍.a,c,f,e,b,d.a,e,d,f,c,b8、图中给出由 7 个顶点组成的无向图。从顶点1 出发，对它进行深度优先遍历得到的序列是（C）,而进行广度优先遍历得到的顶点序列是（C）.A,1354267B.1347652C.1534276D.1247653.A.1534267B.1726453C.l354276D.124765310、已知有向图 G=（V,E）,其中 V=V1,V2,V

32、3,V4,V5,V6,V7,E=,G 的拓扑序列是（A）。A.V1,V3,V4,V6,V2,V5,V7BC.V1,V3,V4,V5,V2,V6,V7D11、一个有向无环图的拓扑排序序列（A.一定 B.不一定出现的是(D)。A.G 中有弧B.G 中有一条从 Vi 到 Vj 的路径C.G 中没有弧D.G 中有一条从 Vj 到 Vi 的路径 13、 关键路径是事件结点网络中(A)。A.从源点到汇点的最长路径 B.从源点到汇点的最短路径C.最长回路 D.最短回路14、下列关于 AOEH 的叙述中，不正确的是(B)A.关键活动不按期完成就会影响整个工程的完成时间B.任何一个关键活动提前完成，那么整个工程

33、将会提前完成C.所有的关键活动提前完成，那么整个工程将会提前完成D.某些关键活动提前完成，那么整个工程将会提前完成填空题1、判断一个无向图是一棵树的条件是有(n 个顶点，n-1 条边的连通图)2、具有 10 个顶点的无向图，边的总数最多为(45)。3、BFS 遍历和 DFS 遍历图的不同之处在于(访问的次序不同)，反映在数据结构上的差别是(深度优先遍历采用递归算法，广度优先遍历采用队列算法)4、已知一无向图 G=(V,E),其中 V=a,b,c,d,eE=(a,b),(a,d),(a,c),(d,c),(b,e)现用某一种图遍历方法从顶点 a 开始遍历图，得到的序列为 abecd,则采用的是(

34、深度优先)遍历方法。5、一无向图 G(V,E),其中 V(G)=1,2,3,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),则采用的遍历方法是（广度优先遍历）6、为了实现图的广度优先搜索，除了一个标志数组标志已访问的图的结点外，还需（队.V1,V3,V2,V6,V4,V5,V7.V1,V2,V5,V3,V4,V6,V7B）是唯一的。12、在有

35、向图 G 的拓扑序列中，若顶点Vi 在顶点 Vj 之前，则下列情形不可能9、当各边上的权伯：(A)时，BFSlT 度优先)算法可用来解决单源最短路径问题A.均相等 B.均互不相等 C.不一定相等列）存放被访问的结点以实现遍历。7、构造连通网最小生成树的两个典型算法是（Prim/普里姆算法和 kruskal/克鲁斯卡尔算法）。8、Prim（普里姆）算法适用于求（偏稠密）网的最小生成树；kruskal（克鲁斯卡尔）算法适用于求（偏稀疏）网的最小生成树。9、有一个用于 n 个顶点连通带权无向图的算法描述如下：（1）设集合 T1 与 T2,初始均为空；（2）在连通图上任选一点加入 T1;（3）以下步骤

36、重复 n-1 次：a.在 i 属于 T1,j 不属于 T1 的边中选最小权的边；b.该边加入 T2。上述算法完成后，T2 中共有（n-1）条边，该算法称（Prim）算法，T2 中的边构成图的（最小生成边）。10、有向图 G 可拓扑排序的判别条件是（图中不存在环）。11、Dijkstra 最短路径算法从源点到其余各顶点的最短路径的路径长度按（递增）次序依次产生，该算法弧上的权出现（负值）情况时，不能正确产生最短路径。12、有向图 G=（V,E）,其中 V（G 尸0,1,2,3,4,5,用三元组表示弧及弧上的权 d.E（G）为,则从源点 0 到顶点 3 的最短路径长度是（50）,经过的中间顶点是（

37、4）0图去掉有向弧看成无向图则对应的最小生成树的边权之和为（75）。13、AOV3 中，顶点表示（事件），边表示（各事件的优先关系）。AO 刎中，顶点表小（事件），边表小（活动）。应用题1、设有数据逻辑结构为：B=（K,R）,K=k1,k2,kR=,（1） .画出这个逻辑结构的图示。（2） .相对于关系 r,指出所有的开始顶点和终端顶点。（3） .分别对关系 r 中的开始顶点，举出一个拓扑序列的例子。（4） .分别画出该逻辑结构的正向邻接表和逆向邻接表。9(2)开始顶点：K1,K2;终端顶点:K6,K7;(3)拓扑序列,K2,K3,K4,K5,K6,K8,K9,K1,K3,K4,K5,K6,K

38、8,K9,K1K2K3K4K5K6K7K8K92、已知某图的邻接表为(2)V1V2V5V3V4V612345(y7S9K1K2K3K4K5K6K7K8K9囚*O卡|6H7H1|6|A|-FTIAK7;(1).写出此邻接表对应的邻接矩阵；(2).写出由 v1 开始的深度优先遍历的序列;(3).写出由 v1 开始的深度优先的生成树；(4),写出由 v1 开始的广度优先遍历的序列;(5).写出由 v1 开始的广度优先的生成树；K1K2K7;23456789-2A|(3) V1V2V3V4V5V6(4)3、如下所示的连通图,(1) .以顶点为根的深度优先生成树；(2) .如果有关节点，请找出所有的关节

39、点(2)关节点有 3,1,8,7,24、 对图示的AOES络， 计算各活动弧的ee(Vi)和el(Vi)的函数值， 各事件(顶点)的ve(Vj)和 vl(Vj)的函数值，列出各条关键路径。课堂练习题Kruskal)算法构造下图的一棵最小生成树的过程。1、试写出用克鲁斯卡尔(请画出:03、试利用 Dijkstra 算法求下图中从顶点 a 到其他个顶点间的最短路径，写出执行算法过程中各步的状态第九、十章查找和内部排序习题1、对线性表进行二分查找时，要求线性表必须（B）A.以顺序方式存储B.以顺序方式存储,且数据元素有序C.以链接方式存储D.以链接方式存储,且数据元素有序2、用二分（折半）查找表的元

40、素的速度比用直接插入法（D）A 必然快 B.必然慢 C.相等 D.不能确定3、二叉查找树的查找效率与二叉树的（C）有关，在（C）时其查找效率最低（1）:A.高度 B.结点的多少 C.树型 D.结点的位置（2）:A.结点太多 B.完全二叉树 C.呈单枝树 D.结点太复杂。4、 设有一组记录的关键字为19,14,23,1,68,20,84,27,55,11,10,79,用链地址法构造散列表，散列函数为 H（key）=keyMOD11,散列地址为 1 的链中有（B）个记录。A.1B.2C.3D.45、下面关于哈希（Hash）查找的说法正确的是（C）A.哈希函数构造的越复杂越好，因为这样随机性好，冲突

41、小B.除留余数法是所有哈希函数中最好的C.不存在特别好与坏的哈希函数，要视情况而定D.若需在哈希表中删去一个元素，不管用何种方法解决冲突都只要简单的将该元素删去即可6、 设哈希表长为14,哈希函数是H （key尸key%11,表中已有数据的关键字为15,38,61,84共四个，现要将关键字为 49 的结点加到表中，用二次探测再散列法解决冲突，则放入的位置是（D）A.8B.3C.5D.97、散列表的地址区间为 0-17,散列函数为 H（K）=Kmod17。采用线性探测法处理冲突，助数组的各分量值并将关键字序列 26,25,72,38,8,18,59 依次存储到散列表中。（1）元素 59 存放在散列表中的地址是（D）。A.8B.9C.10D.11（2）存放元素 59 需要搜索的次数是（B）。A.2B.3C.4D.58、下面给出的四种排序法中（D）排序法是不稳定性排序法A、插入 B.冒泡 C.二路归并 D.堆9、 如果待排序序列中两个数据元素具有相同的值， 在排序前后它们的相互位置发生颠倒，则称该排序算法是不稳定的。（C）就是