@数据结构复习题

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

2、ist)：integer；求以head为头指针的不带头结点的循环单链表的长度n:=0IF head<>NIL THENf:=head.link; n:=1;WHILE f <> head DOn:=n+l; f:=f.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） 单选题2链表不具备的特点是_。(1分) (1)可随机访问任一元素

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

4、PROC ins_linklist(1a：linklisttp；i：integer；b：elemp)； 1a为带头结点单链表的头指针，在i之前插入数据元素b p：=Lanext；j：=0； WHILE(循环控制条件) DO循环体部分； IF(判定条件) THEN ERROR(I非法) ELSEnew(s)；s1data：=b； 插入链表部分ENDP；ins linklist解答：WHILE (p<>nil AND j<i-1) DO p:=pnext；j：=j+1； IF(p=nil OR j>i-1) THEN ERROR(i ) ELSE new(s)；sdata：

5、=b； snext：= p next； pnext：=s 解答题4试设计一种链队列的存储结构，要求只用一个指针，并且使其插入和删除的时间复杂度均为O(1)。试画出存储结构，并指出队首和队尾。（5分）解答：采用仅有尾指针rear的循环单链表表示队列(如图)，队空时rear=nil，队首的第一个结点(front=rearnext)，队尾为最后一个结点(rear)。 填空题5在数据结构中，从逻辑上可以把数据结构分为 线性 结构和 非线性 结构。(2分) 算法题2设双端链表结构如下；头结点有俩个域，其中：firstlink指向第一个数据结点，lastlink 指向最后一个数据结点，链表空时，first

6、link=lastlink=NIL。阅读下面的算法，用适当的语句完成各画线的处理，使其能实现删除链表中的data域为x的所有结点功能。(10分) PROC DELETE(L，x)； p：=Lfirstlink； q：=L； WHILE p<>NIL DO IF p.data=x THEN CASE L=q： 第一个结点为x和只有一个结点且为x的处理 L 1astlink=p： 最后一个为x的处理 Others：其它结点为x的处理 ENDC ELSE不为x的处理 ENDP；DELETE算法：PROC DELETE(L，x)； p：=Lfirstlink； q=L； WHILE p&l

7、t;> NIL DO IF pdata=x THEN CASE L=q：Lfirstlink：=plink； IFplink=NIL THEN L lastlink：=NIL；p：=plink; Llastlink=p： Llastlink：=q; qlink：=p link；p：=plink Others：qlink：=p1ink；p：=plink ENDC ELSEq:=p;p:=plink ENDP;DELETE 算法题1、假设以下不带头结点的循环链表Q表示队列，并且只一个rear指针指向队尾元素结点，队列空时Q.rear=nil 试编写相应的出队函数FUNC delq(Q)：el

8、em和队列操作addq(Q，elem)的算法(10分)算法：PROC addq(Q，elem)； New(p)；Pdata：=elem：(1分) IF Q.rear=nil THEN plink：=p (1分) ELSE Plink：=Qrear1ink； Qrear1ink：=p；(2分) Q.rear：=p (1分) ENDP; FUNC delq(Q)：elem： IF Qrear=NIL THEN RETURN (NULL) (1分) ELSEp：=Qrearlink; (1分) IF p=Qrear THEN Qrear：=NIL /只有一个结点 ELSE Qrearlink:=p.

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

10、元素之间的逻辑关系由物理存储位置决定，链式结构中元素之间的逻辑关系由链指针决定。 算法题1、试编写算法，将一个带头结点的单循环链表A，按结点值分解为奇数和偶数两个具有相同结构的链表A和C，其中C的结点是原A中结点值为偶数的结点。要求利用原链表的结点。可用ODD(pdata)逻辑函数判断指针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.n

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

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

13、llink (P->llink)->llink)>rlink=PC) (P->llink)->llink)->rlink=P D) (P->rlink)->rlink)->llink=PP->llink=(P->llink)->llink P->rlink=(P->rlink)->rlink解：答案为A)。 考虑在P所指结点后或前插入一结点的应如何做？【经典考题】 根据线性表的链式存储结构形式，每个结点所含指针的个数，链表可分为A和B：而根据指针的连接方式，链表又可分为C和D。解：A：单链表； B：多重链

14、表； C：循环链表； D：普通链表。【经典考题】 在一个具有n个结点的有序单链表中插入一个新结点并仍然有序的时间复杂度为 。 解：O(n)。【经典考题】 (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为空表的条件？【经典考题】将两个各有

15、n个元素的有序表归并成一个有序表，其最少的比较次数是 ( )。A)n B)2n-1 C)2n D)n-1解：答案为A)栈和队列 解答题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.fo

16、rnt=cq.rear入队前判队满条件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)%max IF cq.front=cq.rear THENTag:=0cq.fornt:=(cq.front+1)%max入队时该方法的特殊处理cq.rear:=(cq.rear+1)%max C:=C+1cq.rear:=(cq.rear+1)%maxIF cq.front=cq.rear THENTag:=1cq.r

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

18、队满)ELSE top2:=top2+1;IF top2>0 THEN S2top2:=x ELSE S1top2:=xENDP；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)数组解：栈的用途之一就是将递归转换为非递归，选择A)。 【经典考

19、题】若一个栈的输入序列是1，2，3，n，输出序列的第一个元素是n，则第i个输出元素是( )。A)n-i B)n-i+1 C)i D)n-i-1解：答案为B)。【经典考题】在用一维数组sequ0m-1存储循环队列的元素时，怎样另设一个标志tag来区分尾指针(rear)和头指针(front)相等时队列的状态是“空”还是“满”?解：设标志tag的初始值为“0”，如果由于元素入队列使得rear= =front时，则置tag为“1”：反之，如果由于元素出队列使得rear= =front成立，则可由标志tag的值来区别队列当前的状态是“满”还是“空”，即可决定其操作是否能进行。树和二叉树 解答题1设链域占

20、俩个单元，数据域占一个单元，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）只有一个根结点的二叉树；（1分） 算法题2试编写将二叉树转换成树林的算法(10

21、分)。设树林的各棵树用带头结点的单连表连接。连表头指针为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;WHILE p<>NIL DOnew(q); q.rootlink=p

22、; / 建树林单链表结点 p：=p.rchild;q.rootlink.rchild:=NIL; / 把一棵树分离出，P已指向下一棵的树根s.nextlink:=q; s:=q; / 树林单链表结点进链s.nextlink:=NILENDP;BttoForest 解答题5、对二叉树回答下列问题（5分）（1）在先序、中序和后序遍历结果中，那些结点的相应次序不发生改变？（2）若中序遍历某二叉树得到一个结点值递增的有序序列，则该二叉树为排序二叉树。该判断是否正确？为什么？（3）设二树中无度为1的结点，试用叶结点数表示二叉村的结点数。解答：（1）叶结点 （2）正确 （3）2n0-1 算法题2、试编写将

23、用二叉链表表示的具有N个结点的二叉树转换成用邻接存储二叉树的算法。（10分）设二叉链表的结点结构为：lchild data rchild邻接点的头接点数组为adjlist(l:n),数组结构为：data firstarc adjvex nextarc并假设算法中可以直接使用以下队列操作：初始化操作：INITQUEUE（Q）判队空函数：EMPTY（Q）入队操作：ENQUEUE（Q，X）出队操作：DLQUEUE（Q）PROC bt_to_adj(bt:bitreptr; n:integer; adjlist:ARRAYn OF vexnode):bt 为二叉树的根，n为结点数，adjlist为邻接

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

25、;n+1 AND (NOT EMPTY(Q) Do /建立链表, 从子女的data域中取出其在数组中的 p:=DLQUEUE(Q); /位置i,存入adjvex CASE p.lchild<>NIL AND p.rchild=NIL: NEW(q); adjlisti.firstarc:=q; q.adjvex:=P.lchild.data; q.nextarc:=NIL p.lchild=NIL AND p.rchild<>NIL: NEW(q); adjlisti.firstarc:=q; q.adjvex:=P.rchild.data; q.nextarc:=NI

26、L p.lchild<>NIL AND p.rchild<>NIL:NEW(q); adjlisti.firstarc:=q; q.adjvex:=P.lchild.data; NEW(q); adjlisti.firstarc.nextarc:=q; q.adjvex:=P.rchild.data; q.nextarc:=NIL Others: adjlisti.firstarc:=NIL ENDC IF p.lchild<>NIL THEN ENQUEUE(Q,p.lchild); IF p.rchild<>NIL THEN ENQUEUE(

27、Q,p.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)p1child<>nil (3)p1tag=O (4)prtag=l答案：(3) 单选题7已知二叉树中叶结点数为50，仅有一个孩子的结点数为30，则总结点数为_。(1分) (1) 81 (2) 129 (3) 110 (4) 120 答案：(2) 解答题1一棵二叉数的先序、中序和后序如下，其中

28、有部分未标出，试构造出该二叉树。（5分） 先序序列为： ABCDEFGHIJK 中序序列为： CBEDFAHJKIG 后序序列为： CEFDBKJIHGA 算法题1修改下面中序遍利二叉树的算法，使其能判定所输出的序列是否有序。(9分) PROC inorder(bt：bitrep)； bt为二叉树根结点指针 IF bt<>nil THEN inorder(bt1child)； visit(btdata)； inorder(btrchild) ENDP；inorder算法:思想：用一个变量predata作为前趋结点的值，初值为最小值Maxint，遍历中判断，当某结点的值小于其前趋时，

29、输出序列为无序列，逻辑变量B为False。 PROC inorder(bt：bitreptr)； bt为二叉树根结点指针，初次调用时predata=Maxint,B为true， IF bt<>nil THENinorder(bt.lchild);IF bt.data<predata THEN B:=False; Predata:=bt.data;Inorder(bt.rchild) ENDP；inorder 算法题2修改下面层次遍利二叉树的算法使其能判断该二叉树是否为完全二叉树。 (8分) PROC level(bt：bitreptr)； IF bt<>nil T

30、HENINITQUEUE(Q)；ENQUEUE(Q，bt)；初始化队列Q，并将根入队列 WHILE NOT EMPTY(Q) DO队列非空进入循环 p：=DEQUEUE(Q)；出队列 visit(pdata)； IF p.1child <> nil THEN ENQUEUE(Q，p1child)；IF p.rchild <> nil THEN ENQUEUE(Q，prchild)；ENDP;level算法思想：完全二叉树中，若某结点无左孩子，也不能有右孩子；若某结点缺少孩子，其后的所有结点就不能有右孩子。参考思想： 一旦出现“无左有右”则为非完全树第一次出现（“无左无右

31、”或“有左无右”）后一旦出现有子结点则为非完全树。 填空题2对下列给出的每组遍历序列判断是否可以唯一的确定一个二叉树，用表示可以。(3分) (1) 先序遍历序列和中序遍历序列 () (2) 先序遍历序列和后序遍历序列 ( ) (3) 先序遍历序列和层次遍历序列 ( ) (4) 中序遍历序列和后序遍历序列 () (5) 中序遍历序列和层次遍历序列 () (6) 后序遍历序列和层次遍历序列 ( ) 填空题6有n (n>0)个结点的d度树，若用d个链域的多重链表表示，则只有_n-1_非空链域。(2分)分析：有n-1条边，也就有n-1个指针，所以非空链域为n-1个。空链域数M=nd-(n-1)=

32、(d-1)n-1。n个结点的树的二叉链表存储的空指针域个数为n+1,非空为n-1。 解答题1设HT为哈夫曼树，叶结点a的路径长度La比叶结点b的路径长度Lb长，试证明：叶结点b的权值Wb不小于叶结点a的权值Wa(5分)证明：反证法：设WbWaHT的带权路径长度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)

33、>0 与HT为哈夫蔓树矛盾。 故Wb>Wa 算法题1修改下面层次遍历二叉树算法使其能输出按层次遍历顺序所访问的第一个和最后一个叶结点。(10分)lchilddatarchild 二叉链表的结点结构 PROC leveltrav(t：bitre)； IF t<> NIL THEN initqueue(Q)； enqueue(Q，t)； WHILE NOT EMPTY(Q) DO p：=dequeue(Q)； write(pdata)； IF p1child <> NIL THEN enqueue(Q,p.child)； IF prchild <>

34、NIL THEN enqueue(Q,prchild)； ENDP；1eveltrav算法：PROC leveltrav(t：bitre)； IF t<> NIL THEN initqueue(Q)； enqueue(Q，t)； tag:=ture; WHILE NOT EMPTY(Q) DO p：=dequeue(Q)； IF tag THEN IF p.child=NIL AND prchild=NIL THEN write(pdata是第一个叶结点); tag:=false IF p1child <> NIL THEN enqueue(Q,p.child)； IF

35、 prchild <> NIL THEN enqueue(Q,prchild)； ;write(pdata是取后一个叶结点) ENDP；1eveltrav 不定项选择题1下列二叉树中，哪些二叉树的所有非叶子结点的度均为2。(3分)完全二叉树 满二叉树 平衡二又树 哈夫曼树 二叉排序树答案：思考：完全二叉树度为一的结点有几个? 不定项选择题5有关线索二叉树不正确的描述是：(3分) 当ltag=0时，该结点的lchild指向其直接前趋 从任意结点出发沿着指针可以遍历该棵二叉树 线索二叉树中任一结点均有指向其前趋和后继的线索 线索二叉树头结点的ltag=0，rtag=l答案： 解答题1、

36、回答满足后序序列和前序序列正好相同的二叉树的树型和正好相反的二叉树的树型各是什么?(5分)解答：相同：只有一个根结点的二叉树； 相反：任意结点均无左孩子的二叉树（仅有右孩子的二叉树）或者任意结点均无右孩子的二叉树（仅有左孩子的二叉树） 解答题6、以权值分别为3、4、7、9 、20的a，b，c，d，e五个元素作为结点构造二又树，回答：(5分)(1)如何构造路径长度最短的二叉树， 图示出棵路径长度最短的二叉树，并计算出路径长度：(2)如何构造带权路径长度最短的二叉树， 图示一一棵权路径长度最短的解答：(1)9个结点的完全二叉树，一定是路径长度最短的二叉树；或前三层占满，第四层只有两个结点的二叉树其

37、路径长度也为最短。路径长度为：1+1+2+2+2+2+3+3=16 (2)哈夫曼树一定是带权路径长度最短的二叉树，其带权路径长度为：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、从先序、中序、后序和层次遍历算法中，选择一种合适

38、的算法，修改使其用dispose（）操作完成释放二叉树中的所有结点的功能。设二叉树用二叉链表表示，其结点结构为：lchild、data、rchild,头指针为bt. (10分) 算法：PROC releaseBT(bt)； IF bt<>nil THEN rleaseBT(bt1child);releaseBT(btrchild)；dispose(bt)ENDP 单项选择题3设根结点的高度为0，则高度为k的二叉树的最大结点数为（1分） A 2k B 2k+11 C 2k-1 D2k-1-1答案：B 单项选择题6下列关于哈夫曼树的叙述错误的是( )。（1分） A.哈夫曼树的根结点的权

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

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

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

42、方法对左右子树的遍历都是按左子树在前、右子树在后的顺序进行遍历的，所以在三种遍历序列中叶结点的相对次序是不会发生改变的。 【经典考题】设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。请写出后序遍历该二叉树的访问结点序列。解：因为在数组中存放的是一棵完全二叉树，所以很容易得到

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

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

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

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

47、函数分别定义为：(各5分)FUNC indegree(v：vexptr)：integer；求V的入度 ENDF；“ndegreeFUNC outdegree(v：vexptr)：integer；求V的出度ENDF；outdegree头结点数组为a(1：n)，数据结构为：data firstarc adjvex nextarc算法: FUNC indegree(v:vexptr):integer;求V的入度temp:=0FOR i:=1To n DOp:=ai.firstarc;WHILE pNIL DOIF p.adjvex=v THEN temp:= temp+1;p:=NIL /在每条链中找V结点ELSEp:=p.nextarc;RETURN(temp)ENDF;indegreeFUNC ou