@数据结构复习题要点

1、解答题2.阅读下面算法，指由其中所有的错误。(5分)FUNC length(head: linklist) : integer;求以head为头指针的不带头结点的循环单链表的长度f: =head;WHILE f <>head DO n : =n+1 ; p: =p T . 1ink;RETURN(n)ENDPF;length解答：(1)n未初始化为0(1分)(2)循环条件不对，应为 WHILE ft . 1ink<>head DO (2 分)(3)循环变量f的值应在循环体内改变，即p应改为f (1分)(4)未处理空表的情形。(1分)正确的算法是：FUNC length(

2、head : linklist) : integer；求以head为头指针的不带头结点的循环单链表的长度n:=0 IF head<>NIL THEN f:=head T .link; n:=1;WHILE f <> head DOn:=n+l; f:=f T .link ;RETURN(n)ENDF;length解答题4、在线形表的顺序和链式存储结构下，试分析下表各种基本运算时间复杂度，并填入相应的表 格中。（5分）运算求表长取儿系取前趋取后继插入顺序存储结构O (1):O (1)O (1)O (1)O (n)链式存储结构O (n)O (n)O (n)O (1)O (n

3、)单选题2.链表不具备的特点是 。（1分）（1）可随机访问任一元素（2）插入删除不需要移动元素（3）不必事先预分存储空间（4）所需空间与线形表长度成正比答案：（1）单选题4.若线性表最常用的操作是存取第i个元素及其前趋的值，则采用存储方式节省时间。（1分）（1）单链表（2）双链表（3）单循环链表（4）顺序表答案：（4）单选题5.若某链表最常用的操作是在最后一个元素之后插入一个结点和删除最后一个结点，则采用存储方式节省时间。（1分）（1）单链表 （2）双链表（3）单循环链表（4）顺序表答案：（4）判断题1.在顺序表中取出第i个元素所花费的时间与i成正比（X ） （1分）解答题2.将下面算法划线处

4、用具体语句表示，使其完成所要求的功能。(5分)PROC ins_linklist(1a ： linklisttp ; i： integer； b： elemp);.1a为带头结点单链表的头指针，在 i之前插入数据元素bp: =La T . next; j: =0;WHILE(循环控制条件)DO循环体部分；IF(判定条件)THEN ERROR( 'I 非法)ELSEnew(s) ; s1 T . data： =b;插入链表部分ENDP; ins linklist解答：WHILE (p<>nil AND j<i-1) DO p:=p T . next; j: =j+1;I

5、F(p=nil OR j>i-1 ) THEN ERROR( 'i') ELSE new(s) ; sT . data： =b;s T . next ： = p T . next; p T . next: =s解答题4.试设计一种链队列的存储结构，要求只用一个指针，并且使其插入和删除的时间复杂度均为0(1)。试画出存储结构，并指出队首和队尾。(5分)解答：采用仅有尾指针rear的循环单链表表示队列(如图)，队空时rear=nil , 队首的第一个结点(front=rear T . next),队尾为最后一个结点(rear)。填空题5.在数据结构中，从逻辑上可以把数据结构分

6、为线性结构和非线性结构。(2分)算法题2.设双端链表结构如下；头结点有俩个域，其中： firstlink指向第一个数据结点，lastlink 指向最后一个数据结点，链表空时， firstlink=lastlink=NIL 。阅读下面的算法，用适当的语句完成 各画线的处理，使其能实现删除链表中的data域为x的所有结点功能。(10分)PROC DELETE(L , x);p： =L T . firstlink ;q： =L ; WHILE p<>NIL DO IF p T . data=x THEN CASEL= q： 第一个结点为 x和只有一个结点且为 x的处理L T. 1astl

7、ink=p ： 最后一个为 x 的处理Others: 其它结点为 x的处理 ENDCELSE不为x的处理 ENDP; DELETE 算法： PROC DELETE(L , x); p: =L T . firstlink ; q=L; WHILE p<> NIL DO IF pT. data=x THEN CASEL=q ： L T firstlink : =p T . link ;IFp T . link=NIL THEN L T . lastlink ： =NIL ; p： =p T . link;L T . lastlink=p : LT. lastlink: =q;qT. l

8、ink ： =p T. link； p： =p T . linkOthers： q T . link ： =p T . 1ink； p： =p T . link ENDCELSEq:=p;p:=p T . link ENDP;DELETE算法题1、假设以下不带头结点的循环链表Q表示队列，并且只一个rear指针指向队尾元素结点，队列空时Q.rear=nil试编写相应的出队函数FUNC delq(Q) : elem和队列操作addq(Q, elem)的算法.(10分)算法：PROC addq(Q, elem);New（p）; PT. data： =elem ： （1 分）IF Q.rear=nil

9、 THEN p T . link ： =p （1 分）ELSE PT. link ： =Q. rear" 1ink; Q. rear" 1ink： =p; （2 分）Q.rear： =p （1 分）ENDP;FUNC delq（Q） : elem：IF Q. rear=NIL THEN RETURN （NULL） （1 分）ELSEp ： =Q. rear" link; IF p=Q . rear THEN Q . ELSE Q . rear" link:=p RETURN（p T . data）ENDF;（1分）rear： =NIL只有一个结点&quo

10、t;link;（2 分）（1 分 ）单项选择题10 .循环链表的主要优点是（）。（1分）A.已知某结点位置后能容易找到其直接前趋B.在进行插入、删除元素时能保证链表不断开C.不再需要头指针D .从表中任一个结点出发都能扫描整个链表答案：D填空题1.线性表、栈和队列都是 线性 结构，可以在线性表的任何位置插入和删除元素：而栈只能在 栈顶插入和删除元素；对于队列只能在队尾插入元素、在 队首删除元素。（5分）简答题4.线性表有哪两种存储结构？在这两种存储结构中元素之间的逻辑关系分别是通过什么决定的？（5分）答：有顺序和链式两种存储结构，顺序结构中元素之间的逻辑关系由物理存储位置 决定，链式结构中元素

11、之间的逻辑关系由 链指针 决定。算法题1、试编写算法，将一个带头结点的单循环链表A ,按结点值分解为奇数和偶数两个具有相同结构的链表A和C,其中C的结点是原A中结点值为偶数的结点。 要求利用原链表的结点。 可用ODD（p T . data） 逻辑函数判断指针 p的值data是否为奇数，是则返回true。（9分）PROC ODDEVEN（1a , lc： link）;New（lc）; pc:=lc; 建 C 的头结点 P:=la T .next; Q:=la;WHILE P<> la DOIF ODD（P T .data）THENQ:=P; P:=P T .nextELSEQ T .

12、next:=P T .next; / 删除pc T .next:=P; pc:=P; / 插入P:=Q T .next;pc T .next:=lc /lc 成循环链ENDP ; ODD_EVEN【经典考题】数据结构是研究数据的 和,以及它们之间的相互关系，并对这种结构定义相应的,设计出相应的 ,而确保经过这些运算后所得到的新结构是 结构类型。解：本部分基本上都是概念试题。参考答案依次为：物理结构、逻辑结构、运算、算法、原来的。【经典考题】 在数据结构中，与所使用的计算机无关的数据叫土结构：链表是一种采用B存储结构存储的线性表；链表适用于 C查找；在链表中进行 D操作的效率比在顺序 存储结构中

13、进行 d_操作效率高；二分查找 E存储结构。供选择的答案：A)存储 物理 逻辑物理和逻辑B)顺序 网状 星式链式C)顺序二分法顺序，也能二分法随机D)二分法查找 快速查找顺序查找插入E)只适用于链式只适用于顺序既适用于顺序也适用于链式既不适用于顺序也不适用于链式解：本题旨在考察基本的概念。【经典考题】在双向链表存储结构中,A)(P->llink)->rlink=P->rlink(P->rlink)->llink=P->llinkC) (P->llink)->llink)->rlink=PP->llink=(P->llink)-&

14、gt;llink答案为：A)；B)；C)；D)；E)。删除P所指的结点时，需修改指针()B)P->llink=(P->llink)->llink(P->llink)->llink) >rlink=PD) (P->rlink)->rlink)->llink=PP->rlink=(P->rlink)->rlink解：答案为A)。 考虑在P所指结点后或前插入一结点的应如何做?【经典考题】 根据线性表的链式存储结构形式，每个结点所含指针的个数，链表可分为指针的连接方式，链表又可分为C和Do解：A :单链表；B:多重链表；C:循环链

15、表；D:普通链表。【经典考题】在一个具有n个结点的有序单链表中插入一个新结点并仍然有序的时间复杂度为解：O(n)o【经典考题】(1)写出在双向链表中，在指针P所指结点前面插入一个结点*S的语句序列。(2)写出带头结点的双向循环链表L为空表的条件。解：(1) S->Prior=P->Prior ; P->Prior->Next=S ; S->Next=P ; P->Prior=S ;(2) (L= =L->Next)&&(L= =L->Pnor)考虑不带头结点的双向循环链表L为空表的条件?【经典考题】 将两个各有n个元素的有序表归并

16、成一个有序表，其最少的比较次数是()。A)n B)2n-1 C)2n D)n-1解：答案为A)K栈和队列力解答题3、设循环队列cq的队首指针为front,队尾指针为rear,队列可容纳的最大元素个数为max,分别用下列三种方法来区分队满或队空，试在表中写入相应的处理。（5分）用记数变量C记载兀素个数用标志位牺牲一个兀素的存储单兀初始空队列各变 量初值cq.fornt:=cq.rear:=0 C:=0cq.fornt:=cq.rear:=0 tag:=0cq.fornt:=cq.rear:=0出队前判队空条 件C=0tag=0 AND cq.fornt=cq.rearcq.fornt=cq.re

17、ar入队前判队满条 件C=maxtag=1 AND cq.fornt=cq.rear(cq.rear+1)%max=cq.front出队时该方法的 特殊处理cq.fornt:=(cq.fornt+1)%maxC:=C-1cq.fornt:=(cq.fornt+1)%maxIF cq.front=cq.rear THENTag:=0cq.fornt:=(cq.front+1)%max入队时该方法的 特殊处理cq.rear:=(cq.rear+1)%maxC:=C+1cq.rear:=(cq.rear+1)%max IF cq.front=cq.rear THEN Tag:=1cq.rear:=(

18、cq.rear+1)%max填空题3.递归过程实现时使用的数据结构是_栈，层次遍历二叉树时使用的数据结构是队列（2分）不定项选择题3、一个队列的入队序列是a, b, c, d,则它的所有可能的出队序列是（2分）d, c, b, a a, d, c, ba, b, c, dc, b, d, a答案：算法题2.利用两个栈S1和S2模拟一个队列，该队列如下图所示，试写出队空和队满条件，并编写出队列的插入add和删除delete运算。 （10分）-m0 1ntop1=front S1 S2 top2=rearPROC add(x ： elementype)将x插入到队尾中IF top2=n THEN

19、ERROR( 队满')ELSE top2:=top2+1;IF top2>0 THEN S2top2:=x ELSE S1top2:=x ENDP ; addPROC delete(var x ： elementype)删除队首元素，并赋给 xIF top1>top2 THEN ERROR(队空')ELSE IF top1 <1 THEN x:=S1top1 ELSE x:=S2top1;top1:=top1+1 ENDP;delete【经典考题】一般情况下，将递归算法转换成等价的非递归算法应该设置（）。A）栈 B）队列C）堆栈或队列D）数组解：栈的用途之一就

20、是将递归转换为非递归，选择 A）。【经典考题】 若一个栈的输入序列是 1, 2, 3,，n,输出序列的第一个元素是n,则第i个输出元素是（）。A）n-i B）n-i+1 C）i D）n-i-1解：答案为B）o【经典考题】在用一维数组sequ0m-1存储循环队列的元素时，怎样另设一个标志tag来区分尾指针（rear） 和头指针（front）相等时队列的状态是“空”还是“满”？解：设标志tag的初始值为“ 0”，如果由于元素入队列使得rear= =front时，则置tag为“1"：反之，如果由于元素出队列使得 rear= =front成立，则可由标志tag的值来区别队列当前的状态是“满”

21、还是“空”，即可决定其操作是否能进行。树和二叉树R解答题1.设链域占俩个单元，数据域占一个单元， N结点的M叉树比N个结点的二叉树多占用多少个 存储单元？ (5分)解答：m叉树占用2n*m+n个单元，二叉树占用2n*2+n个单元，故多占用2n(m-2)个单元。(5分)解答题4.对给定的非空二叉树回答下列问题：(共5分)(1)前序和中序遍利结果相同的二叉树具有什么形状？(2)后序和中序遍利结果相同的二叉树具有什么形状？(3)前序和后序遍利结果相同的二叉树具有什么形状？解答：(1)只有一个根结点的二叉树和右单枝二叉树；(2分)(2)只有一个根结点的二叉树和左单枝二叉树；(2分)(3)只有一个根结点

22、的二叉树；(1分)算法题2.试编写将二叉树转换成树林的算法(10分)。设树林的各棵树用带头结点的单连表连接。连表头指针为F,连表结点结构为rootlink和nextlink ,其中rootlink为指向树林中某棵树的根的指针，nextlink为指向下一棵树的指针，二叉树的结点结构为：lchild,data,rchild .过程定义如下： PROC BttoForest(bt: bittrepit,F ： linklist) ENDP ; BttoForest算法：PROC BttoForest(bt:bittrepit,F:linklist) New(s):F=s;树林单链表头结点p:=bt;

23、WHILE p<>NIL DOnew(q); q T .rootlink=p; /建树林单链表结点 p： =p T .rchild; q T .rootlink T .rchild:=NIL; /把一棵树分离出，P已指向下一棵的树根s T .nextlink:=q; s:=q;/树林单链表结点进链sT .nextlink:=NIL ENDP;BttoForest解答题5、对二叉树回答下列问题(5分)(1)在先序、中序和后序遍历结果中，那些结点的相应次序不发生改变？(2)若中序遍历某二叉树得到一个结点值递增的有序序列，则该二叉树为排序二叉树。 该判断是否正确?为什么？(3)设二树中无

24、度为1的结点，试用叶结点数表示二叉村的结点数。解答：(1)叶结点(2)正确(3) 2n0-1(10 分)算法题2、试编写将用二叉链表表示的具有 N个结点的二叉树转换成用邻接存储二叉树的算法。 设二叉链表的结点结构为：Ichilddatarchild邻接点的头接点数组为 adjlist(l:n),数组结构为:data firstarcadjvexnextarc并假设算法中可以直接使用以下队列操作：初始化操作：INITQUEUE (Q)判队空函数：EMPTY (Q)入队操作：ENQUEUE (Q, X)出队操作：DLQUEUE (Q)PROC bt_to_adj(bt:bitreptr; n:in

25、teger; adjlist:ARRAYn OF vexnode):bt为二叉树的根，n为结点数，adjlist为邻接表头接点数组 参考算法：INITQUEUE(Q);i:=1;DO /建好数组，填充数组data域，并把结点在数组中位置i存进设二叉链表的结点data域，T .data:=i; i:=i+1;ENQUEUE(Q,bt);/ 树根进队WHILE i<n+1 AND (NOT EMPTY(Q)T .data; pp:=DLQUEUE(Q); adjlisti.data:=pT .lchild); childiIF p T .lchild<>NIL THEN ENQU

26、EUE(Q,pIF p T .rchild<>NIL THEN ENQUEUE(Q,p i:=1;WHILE i<n+1 AND (NOT EMPTY(Q) Do/建立链表，从子女的data域中取出其在数组中的p:=DLQUEUE(Q);位置 i,存入 adjvexCASEp T .lchild<>NIL AND pp T .lchild=NIL AND pp T .lchild<>NIL AND pT .rchild=NIL: NEW(q); adjlisti.firstarc:=q;q T .adjvex:=P T .lchild T .data;

27、q T .nextarc:=NILT .rchild<>NIL: NEW(q); adjlisti.firstarc:=q;q T .adjvex:=P T .rchild T .data;q T .nextarc:=NILT .rchild<>NIL:NEW(q); adjlisti.firstarc:=q;q T .adjvex:=P T .lchild T .data;NEW(q); adjlisti.firstarcT .nextarc:=q;q T .adjvex:=P T .rchild T .data;q T .nextarc:=NILOthers: ad

28、jlisti.firstarc:=NILENDCIF p T .lchild<>NIL THEN ENQUEUE(Q,pT .lchild);IF p T .rchild<>NIL THEN ENQUEUE(Q,pT .rchild)ENDP ; bt_to_adj单选题3.在有N个叶结点的哈夫曼树中，其结点总数为 。(1分) (1)不确定(2)2N (3)2N+l(4)2N-1答案：(4)单选题6.判断线索二叉树中某结点P有左孩子的条件是 。(1分)(1) P <> NIL (2)p T . 1child<>nil (3)p T . 1tag=

29、O (4)p T . rtag=l 答案：(3)单选题7.已知二叉树中叶结点数为50,仅有一个孩子的结点数为30,则总结点数为 。 (1分)(1) 81(2) 129(3) 110(4) 120答案：(2)解答题1 . 一棵二叉数的先序、中序和后序如下，其中有部分未标出，试构造出该二叉树。(5分)先序序列为：AB CDE FGHI JK中序序列为：CBED FAHJKIG后序序列为：CEFDBKJIHGA算法题1.修改下面中序遍利二叉树的算法，使其能判定所输出的序列是否有序。(9分)PROC inorder(bt : bitrep); bt为二叉树根结点指针 IF bt<>nil

30、THENinorder(bt T . 1child);visit(bt T . data);inorder(bt T . rchild) ENDP; inorder算法：思想：用一个变量predata作为前趋结点的值，初值为最小值 Maxint ,遍历中判断，当某结点的值小于其前趋时，输出序列为无序列，逻辑变量B 为 False。PROC inorder(bt: bitreptr);bt为二叉树根结点指针， 初次调用时predata=Maxint,B为true, IF bt<>nil THENinorder(bt T .lchild);IF bt T .data<predat

31、a THEN B:=False;Predata:=btT .data; Inorder(bt T .rchild)ENDP; inorder算法题2 .修改下面层次遍利二叉树的算法使其能判断该二叉树是否为完全二叉树。(8分)PROC level(bt: bitreptr);IF bt<>nil THENINITQUEUE(Q) ; ENQUEUE(Q , bt); 初始化队列 Q,并将根入队列WHILE NOT EMPTY(Q) DO队列非空进入循环p： =DEQUEUE(Q) ; 出队列 visit(p T . data);IF p "child <> ni

32、l THEN ENQUEUE(Q , pT. 1child);IF pf.rchild <> nil THEN ENQUEUE(Q , pT. rchild);ENDP;level算法思想：完全二叉树中，若某结点无左孩子，也不能有右孩子；若某结点缺少孩子，其后的所有结 点就不能有右孩子。参考思想：一旦出现“无左有右”一一则为非完全树第一次出现(“无左无右”或“有左无右”)后一旦出现有子结点一一则为非完全树。填空题2.对下列给出的每组遍历序列判断是否可以唯一的确定一个二叉树，用，表示可以。(3分)(1)先序遍历序列和中序遍历序列(，)(2)先序遍历序列和后序遍历序列()(3)先序遍历

33、序列和层次遍历序列()(4)中序遍历序列和后序遍历序列(，)(5)中序遍历序列和层次遍历序列(，)(6)后序遍历序列和层次遍历序列()填空题6.有n (n>0)个结点的d度树，若用d个链域的多重链表表示，则只有_n-1非空链域。(2分)分析：有n-1条边，也就有n-1个指针，所以非空链域为 n-1个。空链域数 M=nd-(n-1)=(d-1)n-1 。n个结点的树的二叉链表存储的空指针域个数为n+1,非空为n-1。解答题1.设HT为哈夫曼树，叶结点 a的路径长度La比叶结点b的路径长度Lb长，试证明：叶结 点b的权值 Wb不小于口t结点 a的权值 Wa. (5分)证明：反证法：设 Wb

34、< WaHT 的带权路径长度 WPL=Wa*La+Wb*Lb+othersOthers为除a,b外其他叶结点的权值与路径长度乘积之和。现交换结点a和b。则新树NewT的带权路径长度 WPL1=Wa*Lb+Wb*La+othersWPL-WPL1=Wa*La+Wb*Lb-(Wa*Lb+Wb*La)=Wa*(La-Lb) Wb*(La-Lb)=（Wa-Wb）*（La-Lb）>0与HT为哈夫蔓树矛盾。故 Wb>Wa算法题1.修改下面层次遍历二叉树算法使其能输出按层次遍历顺序所访问的第一个和最后一个叶结点。（10分）二叉链表的结点结构IchilddatarchildPROC leve

35、ltrav(t : bitre); IF t<> NIL THEN initqueue(Q); enqueue(Q, t);DOWHILE NOT EMPTY(Q) p： =dequeue(Q); write(p T . data);IF p T . 1child <> NIL THEN enqueue(Q,p T . child);IF pT. rchild <> NIL THEN enqueue(Q,p T. rchild); ENDP; 1eveltrav算法：PROC leveltrav(t : bitre); IF t<> NIL TH

36、EN initqueue(Q);enqueue(Q, t);tag:=ture;WHILE NOT EMPTY(Q) DOp： =dequeue(Q);IF tag THEN IF p T . child=NIL AND p T. rchild=NILTHEN write(p T. data 是第一个叶结点);tag:=falseIF p T . 1child <> NIL THEN enqueue(Q,p T . child);IF p T . rchild <> NIL THEN enqueue(Q,p T . rchild); ;write(p T . data是

37、取后一个叶结点)ENDP; 1eveltrav不定项选择题1 .下列二叉树中，哪些二叉树的所有非叶子结点的度均为2。（3分）完全二叉树满二叉树平衡二又树哈夫曼树二叉排序树答案：思考：完全二叉树度为一的结点有几个不定项选择题5 .有关线索二叉树不正确的描述是：（3分）当ltag=0时，该结点的Ichild指向其直接前趋从任意结点出发沿着指针可以遍历该棵二叉树.线索二叉树中任一结点均有指向其前趋和后继的线索线索二叉树头结点的ltag=0, rtag=l答案：解答题1、回答满足后序序列和前序序列正好相同的二叉树的树型和正好相反的二叉树的树型各是什么？(5分)解答：相同：只有一个根结点的二叉树；相反：

38、任意结点均无左孩子的二叉树(仅有右孩子的二叉树)或者任意结点均无右孩子的二叉树(仅有左孩子的二叉树)解答题6、以权值分别为3、4、7、9、20的a, b, c, d, e五个元素作为结点构造二又树，回答： (5分) (1)如何构造路径长度最短的二叉树，图示出一一棵路径长度最短的二叉树，并计算出路径长度：(2)如何构造带权路径长度最短的二叉树，图示一一棵权路径长度最短的解答：(1)9个结点的完全二叉树，一定是路径长度最短的二叉树；或前三层占满，第四层只有两个结点的二叉树其路径长度也为最短。路径长度为：1+1+2+2+2+2+3+3=16(2)哈夫曼树一定是带权路径长度最短的二叉树，其带权路径长度

39、为：20+9*2+7*3+(3+4)*4=87解答题7、试画出满足下列条件的所有可能的二叉树.(5分)(1)树的高度为3,中序访问第一个结点为C,先序序列为 A、B、C、D, E,(2)中序和先序序列为 A、B、C、D、E(3)树的高度为5,先序序列为 A、B、C、D、E解答：(1)有三棵满足条件的树(2)A, B, C, D, E为序的右单支树(3)A, B, C, D, E为序的右单支树和 A, B, C, D, E为序的 左单支树。算法题2、从先序、中序、后序和层次遍历算法中，选择一种合适的算法，修改使其用dispose ()操作完成释放二叉树中的所有结点的功能。设二叉树用二叉链表表示，

40、其结点结构为：lchild、data、rchild,头指针为bt. (10分)算法： PROC releaseBT(bt); IF bt<>nil THEN rleaseBT(bt T . 1child); releaseBT(bt T . rchild); dispose(bt)ENDP单项选择题3.设根结点的高度为 0,则高度为k的二叉树的最大结点数为(1分)._ kA .2C. 2k-1B.2k+1 -1D. 2k-1-1答案：B单项选择题6.卜列关于哈夫曼树的叙述错误的是()。(1分)A.哈夫曼树的根结点的权值等于所有叶结点的权值之和B.具有n个叶结点的哈夫曼树共有 2n

41、1个结点C.哈夫曼树是带权路径长度最短的二叉树D.哈夫曼树一个结点的度可以是0、1或2 /答案：D单项选择题13.在下列遍历算法中，在遍历序列中叶结点之间的次序可能与其它算法不同的算法是（1分）（）。A.先序遍历算法B.中序遍历算法C.后序遍历算法D.层次遍历算法/2 .给定n个值构造哈夫曼树，经过 n-1次合并才能得到最终的哈夫曼树。11分）简答题2.设n0为哈夫曼树的叶子结点数目，则该哈夫曼树共有多少个结点。若以 3、4、5、6、7作为叶子结点的权值构造哈夫曼树，则其带权路经长度是多少？ （5分）答：结点数有2n0-1个。带权路径长度是（5+6） *2+ （3+4） *3+7*2=57简答

42、题3.什么样的二叉树，对它采用任何次序的遍历，结果都相同？ （5分）答：空二叉树，或只有一个根结点的二叉树。【经典考题】 若以4, 5, 6, 7, 8作为叶子结点的权值构造哈夫曼树，则其带权路径长度是 。解：答案为69。【经典考题】 从概念上讲，树、森林和二叉树是三种不同的数据结构，将树、森林转化为二叉树的基本目 的是什么，并指出树和二叉树的主要区别。解：其目的是：树和森林采用二叉树的存储结构并利用二叉树的已有算法解决树和森林的有关问题。主要区别：树中结点的最大度数没有限制，而二叉树结点的最大度数为2;树的结点无左右之分，而二叉树的结点有左右之分。【经典考题】一棵非空的二叉树其先序序列和后序

43、序列正好相反，画出这棵二叉树的形状。解：因为先序遍历是“根左右”，后序遍历是“左右根”。根结点在两个序列中的位置分别在最前和最 后，正好相反。若二叉树左右子树均存在，那么接下来在先序遍历中要访问左子树的根结点，在后序遍历 相反对应的则是右子树的根结点，左右子树的根结点是不可能相同的。若要两个序列正好相反，那么左或 右子树必有一棵不存在，这对于每个结点是相同的，也就是每个结点的度为1或0（叶结点）。【经典考题】 请说明一棵二叉树进行前序、中序和后序遍历，其叶结点的相对次序是否会发生改变？为什么？解：二叉树中叶结点必在某结点的左或右子树中，三种遍历方法对左右子树的遍历都是按左子树在前、右子树在后的

44、顺序进行遍历的，所以在三种遍历序列中叶结点的相对次序是不会发生改变的。【经典考题】 设no为哈夫曼树的叶子结点数目。简要推导出该哈夫曼树共有多少个结点？解：设度为1和2的结点的个数为n1和n2,结点的总个数为 n,则有n=no+nl+n2根据二叉树的性质有no=n2+1依据哈夫曼树的构造原理可知，哈夫曼树没有度为1的结点存在，即n1=0,所以有n=no+n2=no+no-1=2n0-1【经典考题】用一维数组存放的一棵完全二叉树：ABCDEFGHIJKL。请写出后序遍历该二叉树的访问结点序列。解：因为在数组中存放的是一棵完全二叉树，所以很容易得到该二叉树的树形结构。对其进行后序遍 历得到后序序列

45、为：HIDJKEBLFGCA 。【经典考题】 如果二叉树有n个结点，试问：当执行中序遍历的递归程序时，在最坏情况下为处理递归调 用所设的单元至少要有多少个才行？解：在遍历二叉树算法中，所需的辅助空间为遍历过程中栈的最大容量，即树的深度，最坏情况下为n。【经典考题】 设有如图所示的中序线索树，现要在图中所指位置插入一个新结点h,使其成为c的右儿子，请写出完成插入结点h的具体操作。(指针pt、指针s和指针t所指内容如图中所示，图中虚线表示线索。)/一 昼、解：在线索二叉树中插入结点要进行指针和线索两方面的修改。具1 体修改如下：-X又 ，匕)；修改指针：t->rchild=s->rch

46、ild ；'I， s->rchild=t ;修改线索：t->lchild=s ;(三；二二 t->ltag=l ;t->rchild->lchild->lchild=t ;【经典考题】 若一个具有N个顶点、K条边的无向图是一个森林 (N>K),则该森林中必有 棵树。解：设此森林中有 m棵树，每棵树具有的顶点数为vi(1wiwm),则V1+V2+ -+Vm=N 顶点数(V1-1)+(V2-1)+ -+(Vm-1)=K 边数两式相减得m=N-K【经典考题】 若度为m的哈夫曼树中，其叶结点个数为n,则非叶结点的个数为 。A) n-1E)一5-1m +

47、 1答案：C)解：在构造度为m的哈夫曼树的过程中， 每次把m个子树合并成一棵树， 每次合并减少 m1个结点,从n个叶结点减少到最后只剩一棵树为止，每次合并增加一个非叶结点。【经典考题】证明：树的遍历方法中无中序遍历证明：在树的遍历方法中若有中序遍历，那么对树根的访问就要在某些子树之间进行，但由于树中每个结 点子树可以有多个，把根放在哪两个子树间来访问是无法确定的，算法实现上不易统一，所以对于树是没 有中序遍历的。其实，在对树的遍历算法中，是将树看成是由树根和树根的子树森林两部分组成的，对根 的访问只能在子树森林前或后访问，即就是树的前序和后序遍历。【经典考题】证明：森林的遍历方法中无后序遍历工

48、证明：实际上一个森林可以分成三个部分，如图。 I和II实际上是森林中第一棵树的根/及根的子树森林，III为除了第一棵树其余树所形成的子树森林。那么按三种遍历思想/ 尸丁应该得到三种遍历序列：先序I、II、 III ,中序II、I、III,后序II、III、I。 粤遍历的基本要求要保证每一棵树遍历的完整性。在上面的后序遍历中，首先访问II部分，其次访问III部分，最后访问I部分，那么就把第一棵树给分离开了。同样的，再递归地也把 II和III 部分分离开了，这样每一棵树都不完整。而其它两种方法则保证了树的完整性，所以在森林的遍历中无后 序遍历方法。算法题1 .在有N个顶点的有向图的邻接表上，试编写

49、求某顶点V的的入度和出度函数，其函数分别定义为：(各5分)FUNC indegree(v： vexptr) ： integer;求V的入度ENDF ; " ndegreeFUNC outdegree(v： vexptr) : integer;求V的出度ENDF ; outdegree头结点数组为a(1: n),数据结构为：data firstarcadjvex nextarc算法：FUNC indegree(v:vexptr):integer;求V的入度temp:=0FOR i:=1To n DOp:=ai.firstarc;WHILE p ONIL DOIF p T .adjvex

50、=v THEN temp:= temp+1;p:=NIL/在每条链中找 V 结点ELSEp:=p T .nextarc;RETURN(temp)ENDF;indegreeFUNC outdegree(v:vexptr):integer;求V的出度i:=1;WHILE ai.dataOv DO i:=i+1; 找到 V 结点Temp:=0; p:=ai.firstarc;WHILE pO NIL DO temp:=temp+1; p:=p T .nextarc;RETURN(temp)ENDF;outdegree求最短路径判定有向图是否存在回路求连通分量个数拓扑排序算法V深度优先搜索算法VV迪杰

51、特拉算法V佛洛伊德算法V解答题1、在利用某算法能解决某应用问题的相应表格中打上对号。（5分）判断题2 .一个有向图的邻接表和逆邻接表中的结点个数一定相等(，)(1分)解答题3.对有向图和无向图，分别描述如何判定图中是否存在回路。(5分)解答：对有向图，可以用拓扑排序算法来判定是否存在回路。当输出顶点数小于顶点数时，图中存在回路，否则，图中无回路。对无向图，若边数大于等于顶点数时，则存在回路，否则无回路。填空题4.有向图用邻接矩阵表示，删除所有从第i个结点出发的边的方法是将第i行全置为0 (2分)解答题3.对于n个顶点的无向图，采用邻接矩阵表示，回答下列问题：(6分)(1)如何确定图中的边数？(

52、2)如何判断任意顶点i和j是否有边相连？(3)如何求任意一个顶点的度 ？(1)答：图中边数等于邻接矩阵的非零元素个数之和的一半。(2)答：i和j有边相连的条件是 Ai,j<>0 ,且Aj,i<>0 。(3)答：顶点j的度为第j行中非零元素的个数不定项选择题6。图G是n个顶点的无向完全图，则下列说法正确的有(2分)G的邻接多重表需要 n(n 1)个边结点和n个顶点结点：G的连通分量个数最少：G为连通图；G所有顶点的度的总和为 n(n 1)答案：? （5 分）解答题3.下图既可以看成一棵二叉树，又可以看成是一个无向图，试回答俩者有何差异 解答：二叉树无向图有根，叶和层次概念

53、无后左右子树之分无度的概念不同：子树个数与顶点连能的边数解答题5.无向.图G如下图所示，给出 G的邻接矩阵，若对邻接矩阵中每行的访问顺序从右到左，写出该图从顶点V2开始的深度优先搜索遍历的顶点序列。(5分)解答： V1 V2 V3 V4 V5V101V210V310V401V510101010011101110深度优先搜索遍历： V2、V4、V5、V3、V1单项选择题1 .如果从无向图G的任何一个顶点出发进行一次深度优先搜索可以访问图的每个顶点该图一定是（）。（1分）A.完全图B.连通图C.有回路的图D.树答案：B单项选择题2. n个顶点的连通图至少有（）条边。（1分）A. n+l B. nC

54、.n1D . n（n1）答案：C单项选择题4.采用邻接表存储的图的深度优先遍历算法类似于二义树的（1分）A.先序遍历B.中序遍历c.后序遍历D .层次遍历答案： A单项选择题5.判定一个有向图是否存在回路，可以用 （）。（1分）A.关键路径算法B . BFS算法C.最短路径Dijkstra算法 D. DFS算法答案：D单项选择题14.设网中顶点数为 n,边数为e,则适合边稀疏的网的最小生成树算法是（）。（1分）A.普里姆（Prim）算法B .克鲁斯卡尔（Kruskal）算法C.弗洛伊德（Floyed）算法 D.拓扑排序（Topological sort）算法答案：B4.弗洛依德（Floyed）

55、最短路经算法中，A ® i, j表示从顶点Vi到顶点Vj中间顶点序号不大于k的最短路经长度。（2分）5.设图中顶点数为 n,则其生成树有n-1条边：若图的边数大于 n-1,则一定是 有环（回路）图。若图 的边数小于n-1,则一定是 非连通图。（3分）简答题l.DFS和BFS遍历各采用什么样的数据结构来暂存顶点？当要求连通图的生成树的高度最小，应采用何种遍历？ （5分）答：DFS遍历采用栈来暂存顶点。BFS采用队列来暂存顶点。当要求连通图的生成树的高度最小时，应采用BFS遍历。简答题6. Xn n个顶点的无向图，采用邻接表表示时，如何判别下列有关问题？ （5分）（1）图中有多少条边？答：邻接表结点总数的一半。（2）任意两个顶点i和j是否有边相连？答：可看其中一个顶点的邻接表，若链表中的adjvex域有另一个顶点位置的结点，则表示有边相连。(3)任意一个顶点的度是