@数据结构复习题

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

2、C length(head ： linklist) ： integer； 求以 head 为头指针的不带头结点的循环单链表的长度 n:=0IF head<>NIL THEN f:=headt .link; n:=1;WHILE f <> head DOn:=n+l; f:=ft.link ;RETURN (n)ENDF;le ngth。(1 分)(2)插入删除不需要移动元素(4)所需空间与线形表长度成正比 答案：单选题4.若线性表最常用的操作是存取第分)(1)单链表 双链表单循环链表答案：单选题2 .链表不具备的特点是(1)可随机访问任- 1兀素(3)不必事先预分存储空

3、间(1)i个元素及其前趋的值，则采用存储方式节省时间。(1(4)顺序表(4)解答题4、在线形表的顺序和链式存储结构下，试分析下表各种基本运算时间复杂度，并填入相应的表 格中。(5分)运算求表长取兀素取前趋取后继插入顺序存储结构O (1)O (1)O (1)O ( 1)O (n)链式存储结构O (n)O (n)O (n)O ( 1)O (n)单选题5.若某链表最常用的操作是在最后一个元素之后插入一个结点和删除最后一个结点，则采用 存储方式节省时间。(1分)(1)单链表双链表单循环链表顺序表答案：(4)判断题1 .在顺序表中取出第i个元素所花费的时间与i成正比(X ) (1分)解答题2 .将下面算

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

5、( p=nil OR j>i-1 )THEN ERROR( ' i')ELSE n ew(s) ； st. data: =b ； s t. n ext: = pt. n ext ； p t. next: =s解答题4 .试设计一种链队列的存储结构，要求只用一个指针，并且使其插入和删除的时间复杂度均为 O(1)。试画出存储结构，并指出队首和队尾。(5分)解答：采用仅有尾指针rear的循环单链表表示队列(如图)，队空时rear= nil , 队首的第一个结点(front=rear f. next)，队尾为最后一个结点(rear)。线性 结构和 非线性 结构。(2分)填空题5在

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

7、ink=p :最后一个为 x的处理Others: 其它结点为 x 的处理ENDCELSE不为x的处理ENDP ; DELETE算法：PROC DELETE(L , x); p: =L f. firstiink ; q=L ； WHILEIF pf.CASEL=q :p<> NIL DO data=x THENL f firstlink : =p f. link ; IFp f. link=NIL THEN lastlink=p : L fqf.Others: q f. link : =p f. ENDCELSEq:=p;p:=p f. linkEND P;DELETEL ?L f.

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

9、:Q.rear: =p （1 分）（1 分 ）Q. rear?, link : =p ; （2 分）THEN p ?. link : =p=Q. rear?. 1ink;FUNC delq（Q） : elem:IF Q. rear=NIL THENELSEp : =Q. rear?.IF p=Q . rear THEN Q . ELSE Q . rear?. link:=pRETURN（p ?. data） ENDF;RETURN （NULL）link;（1 分 ）（1 分） rear: =NIL ? .link; （2 分）（1 分）/只有一个结点ENDP;单项选择题 10循环链表的主要优点

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

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

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

13、存储结构。供选择的答案:A）存储物理逻辑物理和逻辑B）顺序网状星式链式C）顺序二分法顺序，也能二分法随机D）二分法查找快速查找顺序查找插入E）只适用于链式只适用于顺序既适用于顺序也适用于链式既不适用于顺序也不适用于链式解：本题旨在考察基本的概念。答案为：A）；B）；C）；D）；E）。【经典考题】 在双向链表存储结构中,删除P所指的结点时，需修改指针（）。A) ( P->lli nk)->rli nk二P->rli nkB) P->lli nk=( P->lli nk)->lli nk(P->rli nk)->lli nk二P->lli nk

14、(P->lli nk)->lli nk) >rlink二PC) (P->lli nk)->lli nk)->rli nk=PD) (P->rli nk)->rli nk)->lli nk二 PP->lli nk=( P->lli nk)->lli nkP->rli nk=( P->rli nk)->rli nk解：答案为A）。 考虑在P所指结点后或前插入一结点的应如何做?A和B :而根据【经典考题】 根据线性表的链式存储结构形式，每个结点所含指针的个数，链表可分为指针的连接方式，链表又可分为 解：A :单

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

16、案为A)将两个各有n个元素的有序表归并成一个有序表，其最少的比较次数是B)2 n-1C)2 nD) n-1)。栈和队列填空题3.递归过程实现时使用的数据结构是_栈，层次遍历二叉树时使用的数据结构是队列（2分）不定项选择题3、一个队列的入队序列是a，d， c， b， a a, d，c， ba， b，c，d c，b，d，ab, c, d,则它的所有可能的出队序列是（2分）解答题3、设循环队列cq的队首指针为front,队尾指针为rear,队列可容纳的最大元素个数为max，分别用下列三种方法来区分队满或队空，试在表中写入相应的处理。（5分）用记数变量 C记载兀素个 数用标志位牺牲一个兀素的存储单兀初

17、始空队列各变 量初值cq.forn t:=cq.rear:=0C:=0cq.for nt:=cq.rear:=0tag:=0cq.for nt:=cq.rear:=0出队前判队空条 件C=0tag=0 AND cq.for nt=cq.rearcq.fornt=cq.rear入队前判队满条 件C=maxtag=1 AND cq.for nt=cq.rear(cq.rear+1)%max=cq .front出队时该方法的 特殊处理cq.fornt:=(cq.fornt+1)%maxC:=C-1cq.fornt:=(cq.fornt+1)%maxIF cq.fr on t=cq.rear THEN

18、Tag:=0cq.fornt:=(cq .fron t+1)%max入队时该方法的 特殊处理cq.rear:=(cq.rear+1)%maxC:=C+1cq.rear:=(cq.rear+1)%maxIF cq.fr on t=cq.rear THENTag:=1cq.rear:=(cq.rear+1)%max答案：算法题2利用两个栈S1和S2模拟一个队列，该队列如下图所示，试写出队空和队满条件，并编写出队 列的插入add和删除delete运算。 （10分）-mtop 仁fro ntJ S10S2top 2=rearPROC add(x: elementype)将x插入到队尾中IF top2=

19、n THEN ERROR( 队满'ELSE top 2:=to p2+1;IF top 2>0 THEN S2to p2:=xELSE S1to p2:=xENDP ; addPROC delete(var x : elementype)删除队首元素，并赋给XIF top 1>top2 THEN ERROR(队空'ELSE IF top1 <1 THEN x:=S1to p1 ELSE x:=S2t op 1;top1:=top1+1 ENDP;delete)。经典考题】 一般情况下，将递归算法转换成等价的非递归算法应该设置A)栈 B)队列C)堆栈或队列D)数

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

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

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

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

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

25、dj(bt:bitre ptr;n:i nteger; adjlist:ARRAY n OF vexn ode):bt为二叉树的根，n为结点数，adjlist为邻接表头接点数组 参考算法：INITQUEUE(Q);i:=1;ENQUEUE(Q,bt);/ 树根进队WHILE i<n+1 AND (NOT EMP TY(Q)p :=DLQUEUE(Q);adjlisti.data:=pt .data; pIF p t .IchildoNIL THEN ENQUEUE(Q,pIF p t .rchildoNIL THEN ENQUEUE(Q,p DO/建好数组，填充数组data域，并把结点在

26、数组中位置i存进设二叉链表的结点data域，t .data:=i; i:=i+1;t .Ichild);chtd.)ri:=1;WHILE i<n+1 AND (NOT EMP TY(Q) p :=DLQUEUE(Q);CASEp t .IchildoNIL AND pDo建立链表，从子女的data域中取出其在数组中的位置i,存入 adjvexp t .IchiId=NIL AND pp t .IchildoNIL AND pt .rchiId=NIL: NEW(q); adjlisti.firstarc:=q;q t .adjvex:=Pt .Ichild t .data;q t .n

27、extarc:=NILt .rchildoNIL: NEW(q); adjlisti.firstarc:=q;q t .adjvex:=Pt .rchild t .data;q t .nextarc:=NILt .rchiId<>NIL:NEW(q); adjlisti.firstarc:=q;q t .adjvex:=Pt .IchildNEW(q); adjlisti.firstarcq t .adjvex:=Pt .rchildt .data;t .nextarc:=q;t .data;q t . nextarc:=NILOthers: adjlisti.firstarc:=

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

29、。(1分)(3)p t 1tag=O (4)pt rtag=l 答案： (3)50，仅有一个孩子的结点数为30，则总结点数为(4) 120答案： (2)。(1分)解答题先序序列为：中序序列为：后序序列为：5 分)1 一棵二叉数的先序、中序和后序如下，其中有部分未标出，试构造出该二叉树。AB CDE FGHI JKCB ED FAH JK I G CEFDBKJIHGA(9 分)算法题 1修改下面中序遍利二叉树的算法，使其能判定所输出的序列是否有序。 PROC inorder(bt ： bitrep)； bt 为二叉树根结点指针 IF bt<>nil THENinorder(bt t

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

31、Predata:=btt .data;Inorder(btt .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 f. data);IF pf . 1child <> nil IF p f .rchild <&

32、gt; nilEND P;levelTHEN ENQUEUE(Q , p f. Ichild);THEN ENQUEUE(Q , pf. rchild);算法思想：完全二叉树中，若某结点无左孩子，也不能有右孩子；若某结点缺少孩子，其后的所有结 点就不能有右孩子。一旦出现“无左有右”一一则为非完全树第一次出现(“无左无右”或“有左无右”)后一旦出现有子结点一一则为非完全树。填空题2对下列给出的每组遍历序列判断是否可以唯一的确定一个二叉树，用"表示可以。(1)先序遍历序列和中序遍历序列(V)(2)先序遍历序列和后序遍历序列()(3)先序遍历序列和层次遍历序列()(4)中序遍历序列和后序遍

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

34、L=Wa*La+Wb*Lb+othersOthers为除a,b外其他叶结点的权值与路径长度乘积之和。 现交换结点a和bo则新树NewT的带权路径长度 WPL1=Wa*Lb+Wb*La+othersWPL-WPL仁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 leveltrav(t : bitre);IF

35、t<> NIL THENinitqueue(Q); enqueue(Q, t);DOWHILE NOT EMP TY(Q) p: =dequeue(Q); write(p t. data);IF pt. 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 THEN initqueue(Q);enqueue(

36、Q, t);tag:=ture;WHILE NOT EMP TY(Q)DOp： =dequeue(Q);IF tag THEN IF p t . child=NIL AND p t. rchild=NILTHEN write(p t. data 是第一个叶结点);tag:=falseIF p f. Ichild <> NIL THEN enqueue(Q,p t . child);IF p t. rchild <> NIL THEN enqueue(Q,p t. rchild);write(p t. data是取后一个叶结点)ENDP ; 1eveltrav不定项选择题

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

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

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

40、完成释放二叉树中的所有结点的功能。设二叉树用二叉链表表示，其结点结构为： 指针为 bt. (10 分)算法：PROC releaseBT(bt) ；IF bt<>nil THENrleaseBT(bt t. Ichild); releaseBT(bt t. rchild); dispose(bt)ENDP单项选择题 3.设根结点的高度为 0,则高度为 k 的二叉树的最大结点数为( 1 分) A .2kB.2k+1 1C.2k-1D. 2k-1-1答案： B单项选择题 6.下列关于哈夫曼树的叙述错误的是 ()。( 1 分)A. 哈夫曼树的根结点的权值等于所有叶结点的权值之和B. 具有

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

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

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

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

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

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

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

48、前序和后序遍历。【经典考题】证明：森林的遍历方法中无后序遍历 证明：实际上一个森林可以分成三个部分，如图。I和II实际上是森林中第一棵树的根及根的子树森林，III为除了第一棵树其余树所形成的子树森林。那么按三种遍历思想 应该得到三种遍历序列：先序I、II、 III，中序II、丨、山，后序II、山、I。遍历的基本要求要保证每一棵树遍历的完整性。在上面的后序遍历中，首先访问II部分，其次访问III部分，最后访问I部分，那么就把第一棵树给分离开了。同样的，再递归地也把II和III部分分离开了，这样每一棵树都不完整。而其它两种方法则保证了树的完整性，所以在森林的遍历中无后 序遍历方法。图V的的入度和出

49、度函数，其函数分别定算法题1.在有N个顶点的有向图的邻接表上，试编写求某顶点义为：（各5分）FUNCindegree(v: vexptr) : integer ；求V的入度ENDF ； “ ndegreeFUNC outdegree(v: vexptr) : integer；求V的出度ENDF ； outdegree头结点数组为a(1： n),数据结构为：data firstarcadjvex n extarc算法:FUNC indegree(v:vexptr):integer;求V的入度temp :=0FOR i:=1To n DOp :=ai.firstarc;WHILE p NIL DO

50、IF p t .adjvex=v THEN temp:= temp +1;p:=NIL/在每条链中找 V 结点ELSEp:=p t .nextarc;RETURN(te mp)ENDF; in degreeFUNC outdegree(v:vex ptr):i nteger;求V的出度i:=1;WHILE ai.data v DO i:=i+1;/找到 V 结点Temp:=0; p:=ai.firstarc;WHILE NIL DO temp:=temp+1; p:=p t .nextarc;RETURN(te mp)ENDF;outdegree求最短路径判定有向图是否存在回路求连通分量个数拓

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

52、中的边数？ 如何判断任意顶点i和j是否有边相连？ 如何求任意一个顶点的度？(1)答：图中边数等于邻接矩阵的非零元素个数之和的一半。 答：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 V5V1V2V3V4V5深度优先搜索遍历：V2 、V4、V5、V3 、V1单项选择题图一定是 （A. 完全图C .有回路的图1如果从无向图）。（1分）B.连通图D.树G 的任何一个顶点出发进行一次深度优先搜索可以访问图的每个顶点单项选择题 2A n+l答案： n 个顶点的连通图至少有 （）条边。（1 分）BnC n1Dn(n1)答案：单项选择题 4.采用邻接表存储的图的深度优先遍历算法类似于二义树的（A. 先序遍历 B. 中序遍历c.后序遍历D .层次遍历C1 分）单项选择题 5 判定一个有向图是否存在回路，可以用A. 关键路径算法C.最短路径Dijkstra算法B BFS 算法D DFS 算法答案：）。（1 分）单项选择题 14设网中顶点数为A.普里姆（Prim）算法C.弗洛伊德（Floyed）算法答案：n边数为e,则适合边稀疏的网的最小生成树算法是（B 克鲁斯卡尔 （