数据结构复习题

1、数据结构复习题2009.12考试说明考试内容：一、 绪论数据结构的基本概念和分类、数据结构的逻辑结构、存储结构、算法、数据结构的选择 和评价二、 线性表线性表的类型定义、线性表的顺序表示和实现、线性表的链式表示和实现三、 栈和队列栈和队列的结构特性、两种存储结构上实现栈和队列的基本操作、栈和队列在程序设计 中的应用六、 树和二叉树树、二叉树的定义、性质和存储结构、二叉树的遍历和线索化、二叉树和森林转换、最 优树和哈夫曼编码。七、 图图的定义和术语、图的存储结构、图的遍历、最小生成树、拓扑排序、最短路径问题。 九、内部排序插入排序、交换排序、选择排序、归并排序和基数排序的基本思想、算法特点、排序

2、过 程、时间复杂度分析及其应用。试题类型及分值：选择题20分10题填空题10分10题 应用题30分5题算法设计题40分5题一选择题1.计算机算法指的是(1) A.计算方法(2) A.可执行性、1),它必须具备(B.排序方法可移植性、可扩充性2)C.这三个特性。解决问题的步骤序列B.C.确定性、有穷性、稳定性答案：D.D.调度方法可执行性、确定性、有穷性 易读性、稳定性、安全性2.下面说法错误的是(1)(2)(3)(4)A. 答案3.从逻辑上可以把数据结构分为A.动态结构、静态结构C.线性结构、非线性结构 答案4以下与数据的存储结构无关的术语是A循环队列B.链表答案5.连续存储设计时，存储单元的

3、地址()算法原地工作的含义是指不需要任何额外的辅助空间在相同的规模n下，复杂度0(n)的算法在时间上总是优于复杂度0(2n)的算法所谓时间复杂度是指最坏情况下，估算算法执行时间的一个上界同一个算法，实现语言的级别越高，执行效率就越低(1) B.(1)，(2) C.(1),(4)D.(3)两大类。 顺序结构、 .初等结构、C.【武汉交通科技大学1996、4( 2分)】链式结构构造型结构)。哈希表D.A一定连续B.一定不连续C.不一定连续 答案6下面关于线性表的叙述中，线性表采用顺序存储，线性表采用顺序存储，线性表采用链接存储，线性表采用链接存储，A.B.部分连续，部分不连续错误的是哪一个？(必须

4、占用一片连续的存储单元。 便于进行插入和删除操作。不必占用一片连续的存储单元。 便于插入和删除操作。C.D.答案7若某表最常用的操作是在最后一个结点之后插入一个结点或删除最后一个结点。则采用()存储方式最节省运算时间。A.单链表B双链表C答案：8.下面的叙述不正确的是()A线性表在链式存储时，查找第B.线性表在链式存储时，查找第C.线性表在顺序存储时，查找第D.线性表在顺序存储时，查找第答案10.对于顺序存储的线性表，访问结点和增加、删除结点的时间复杂度为(A. 0(n) 0(n) B. 0(n) 0(1) C. 0(1) 0(n)D. 0(1) 0(1)答案：11.循环链表H的尾结点P的特点

5、是()。【中山大学1998二、2(2分)】A.PA.NEXT:=HB.PA.NEXT:= HT.NEXTC.P:=HD.P:=H.NEXT.单循环链表.带头结点的双循环链表iiii个 元 素 的 时 间 同个 元 素 的 时 间 同个 元 素 的 时 间 同个元素的时间同iiii的值成正比的值无关 的值成正比 的值无关答案：12.完成在双循环链表结点A.P之后插入s的操作是()pA.n ext:=s ; si priou :=p; pin ext .p riou:=s ; sin ext:=pA.n ext; pA.next .p riou:=s; pin ext:=s; sip riou :

6、=p; si next:=pA.n ext; sip riou :=p;sin ext:=pA.n ext; pin ext:=s; pin ext .p riou:=s ; sip riou :=p; sin ext:=pA.next; pin ext pnou:=s ; pin ext:=s;B.C.D.答案13.在非空双向循环链表中q所指的结点前插入一个由P所指的链结点的过程依次为J q; lli nk(p)lli nk(q); lli nk(q)p;I J P B .rlink(llink(q)J p C.J Prli nk(p)A.rlink(q)D. rlink(rlink(p)答

7、案14.在双向链表指针p-Lli nk=q;q-Rli nk=p;p-Lli nk-Rli nk=q;q-Lli nk=qp-Lli nk=q;p-Lli nk-Rli nk=q;q-Rli nk=p;q-Lli nk=p-Lli nk; q-Rlink=p;q-Lli nk=p-Lli nk;p-Lli nk-Rli nk=q;p-Lli nk=q; q-Lli nk=p-Llink;q-Rli nk=q;p-Lli nk=q;p-Lli nk=q;p的结点前插入一个指针q的结点操作是( )riin k(llink(p)A.B.C.D.答案15.在单链表指针为P的结点之后插入指针为A. p-

8、next=s;s-next=p-next; BC. p-next=s;p-next=s-next; D答案16.一个栈的输入序列为1 2 3 4 5A. 2 3 4 1 5 B. 5 4 1 3 2答案：设一个栈的输入序列是A. 5 1 2 3 4 B. 4 5 1答案：若一个栈以向量V1. .n17.18.()s的结点，正确的操作是：(.s-next=p-next;p-next=s;.p-n ext=s-n ext ;p-n ext=s;，则下列序列中不可能是栈的输出序列的是(C. 2 3 1 4 5 D. 1 5 4 3 21 ,2, 3, 4, 5,则下列序列中，是栈的合法输出序列的是3

9、 2 C. 4 3 1 2 5 D. 3 2 1 5 4存储，初始栈顶指针top为n+1,则下面x进栈的正确操作是B. V top :=x; top :=to p+1D. V top :=x; top:=top-1A. top:=top +1; V top:=xC. to p: =to p-1; V top :=x答案：若栈采用顺序存储方式存储，现两栈共享空间V1.m,topi代表第i个栈(19.栈顶，栈1的底在v1，栈2的底在Vm，则栈满的条件是(A. | top2-top1|=0B. top1+1=top2top 1=t op2答案：20.用链接方式存储的队列，在进行删除运算时(A.仅修改

10、头指针B.仅修改尾指针C.可能都要修改 答案21.用不带头结点的单链表存储队列时，其队头指针指向队头结点，其队尾指针指向队尾结点，则在进行删除操作时()。)OC. top1+top2=m)O头、尾指针都要修改D.头、i =1,2)D.尾指针A.仅修改队头指针B.C.队头、队尾指针都要修改 答案22.循环队列存储在数组A0.mD.仅修改队尾指针 队头，队尾指针都可能要修改中, 则入队时的操作为（A. rear=rear+1B. rear=（rear+1） mod （m-1）C. rear=（rear+1） mod m D. rear=（rear+1）mod（m+1）答案：23.若用一个大小为6的

11、数组来实现循环队列，且当前 当从队列中删除一个元素，再加入两个元素后，A. 1和5 B. 2和4 C. 4答案：24.二叉树在线索后，仍不能有效求解的问题是（A.前（先）序线索二叉树中求前（先）序后继C.中序线索二叉树中求中序前驱 答案25.若一棵二叉树具有10个度为2的结点，5个度为1的结点，则度为0的结点个数是（）A. 9 B.11 C答案26.在一棵三元树中度为3的结点数为 个，则度为0的结点数为（ ）个A. 4B.5 C答案27.有关二叉树下列说法正确的是（A.二叉树的度为2BC.二叉树中至少有一个结点的度为答案28.有n个叶子的哈夫曼树的结点总数为（A.不确定B答案29.利用二叉链表

12、存储树，A.指向最左孩子 答案30.对二叉树的结点从 同一结点的左右孩子中， 现编号。A.先序答案31.树的后根遍历序列等同于该树对应的二叉树的A.先序序列B.中序序列答案32.若二叉树采用二叉链表存储结构， 遍历方法最合适。A.前序B.中序C答案.2nB.rear和rear和front 2和front的值分别为0和3, 的值分别为多少？（）D. 5和1）。B.中序线索二叉树中求中序后继D.后序线索二叉树中求后序后继2个,度为.不确定2的结点数为1个，度为1的结点数为2.一棵二叉树的度可以小于2.二叉树中任何一个结点的度都为2)。.2n+1.2n-1则根结点的右指针是（B.指向最右孩子.非空开

13、始进行连续编号，要求每个结点的编号大于其左、其左孩子的编号小于其右孩子的编号，可米用（右孩子的编号，）次序的遍历实中序C.后序D.从根开始按层次遍历（C.后序序列D）.层次序列要交换其所有分支结点左、右子树的位置，利用（）.后序D.按层次33.在下列存储形式中，哪一个不是树的存储形式？（）A.双亲表示法B.孩子链表表示法C.孩子兄弟表示法D.顺序存储表示法 答案34. 一棵二叉树的前序遍历序列为ABCDEFG它的中序遍历序列可能是（）A. CABDEFG B.ABCDEFG C.DACEFBG D.ADCFEG答案35.已知一棵二叉树的前序遍历结果为为（ ）。A. CBEFDA B.FEDCB

14、A答案36.已知某二叉树的后序遍历序列是（ ）。A. acbed B.decab答案37.若X是二叉中序线索树中一个有左孩子的结点，且ABCDEF中序遍历结果为CBAEDF则后序遍历的结果CBEDFA D. 不定dabec,中序遍历序列是debac ,它的前序遍历是.deabc D.cedbaA.X的双亲B.X的右子树中最左的结点C.X的左子树中最右结点右叶结点答案38.引入二叉线索树的目的是（）A.加快查找结点的前驱或后继的速度C.为了能方便的找到双亲D答案39.下述编码中哪一个不是前缀码（A. （00,000,001）答案40.当一棵有Al. n中时，01,10,11)B. (0,X不为根

15、，则x的前驱为（）D.X的左子树中最B.为了能在二叉树中方便的进行插入与删除 .使二叉树的遍历结果唯一)。1,00,11)C. (0,10,110,111)D. (1,01,n个结点的二叉树按层次从上到下, 数组中第i个结点的左孩子为（同层次从左到右将数据存放在一维数组）A. A2i（2i= n） B. A2i+1（2i+1=n ext=L & L-p rior=L17.在单链表p结点之后插入s结点的操作是：答案：s-n ext =p-n ext ;p-n ext=s;18在作进栈运算时应先判别栈是否(1);在作退栈运算时应先判别栈是否;当栈中元素为n个，作进栈运算时发生上溢，则说明该

16、栈的最大容量为O为了增加内存空间的利用率和减少溢出的可能性，由两个栈共享一片连续的空间时，将两栈的分别设在内存空间的两端，这样只有当(5)时才产生溢出。答案：(1)满(2)空(3)n (4)栈底(5)两栈顶指针相邻(即值之差的绝对值为1)19.多个栈共存时，最好用 _ 作为存储结构。答案：链式存储结构20.顺序栈用data1.n存储数据，栈顶指针是top,则值为x的元素入栈的操作是 答案：data+to p=x;21.已知链队列的头尾指针分别是答案：s=(LinkedList)malloc(r=s;22.区分循环队列的满与空， 答案：牺牲一个存储单元23._设循环队列用数组A1.M表示，队首、

17、队尾指针分别是FRONT和TAIL,判定队满的条 件为O答案：(TAIL+1)MOD M=FRONT数组下标0到M-1，若一定使用1到M,则取模为0者，值 改取M24.设循环队列存放在向量sq.data0:M中，则队头指针sq.front在循环意义下的出队操答案：f-n ext =p-n ext; f-p rior= p; p-n ext-p rior=f; p-n ext=f;9.在双向链表结构中，若要求在P指针所指的结点之前插入指针为行下歹y语句：s .next:=p;s .prior:=_;.prior:=s答案：pA.p rior sip rior .n ext10._链接存储的特点是

18、利用来表示数据元素之间的逻辑关系。点是：_O答案： 指针、从任一结点出发都可访问到链表中每一个元素。11._顺序存储结构是通过表示元素之间的关系的；链式存储结构是通过 示元素之间的关系的。答案：物理上相邻指针12.对于双向链表,在两个结点之间插入一个新结点需修改的指针共 _个。答案：4、213.已知指针P指向单链表L中的某结点，则删除其后继结点的语句是：答案：u=p-n ext; p-n ext=u-n ext; free(u);14.带头结点的双循环链表 答案：L-n ext-n ext=L15.在单链表L中，指针 答案：P- next!=null16.带头结点的双循环链表L中只有一个元素结

19、点的条件是:p所指结点有后继结点的条件是:L为空表的条件是:s所指的结点，则需执；_：=s；循环单链表的最大优个，单链表为f和r，则将值x入队的操作序列是 _sizeof (LNode);s-data=x;s-next=r-next;r-next=s;只有两种方法，它们是 设标记作可表示为 _，若用牺牲一个单元的办法来区分队满和队空(设队尾指针sq.rear),则队满的条件为答 案 ：sq.fro nt=(sq.fro nt+1)%(M+1)；(sq.rear+1)%(M+1)=sq.fro nt；25.二叉树由_(1)_，_J2)_，_(3)_三个基本单元组成。答案：(1)根结点左子树右子树

20、26.树在计算机内的表示方式有_(1)_，o答案：(1)双亲链表表示法(2)孩子链表表示法(3)孩子兄弟表示法27.在二叉树中，指针P所指结点为叶子结点的条件是答案：P-lchild=null & p-rchlid=null28.具有256个结点的完全二叉树的深度为答案：929.已知一棵度为3的树有2个度为1的结点，3个度为2的结点，4个度为3的结点，贝9该树有个叶子结点。答案:1230.深度为k的完全二叉树至少有_个结点，至多有(2)_个结点。答案：(1)2k-1(2)2k-131.先根次序周游树林正好等同于按_(1)_周游对应的二叉树,后根次序周游树林正好等同 于按(2)_周游对应

21、的二叉树。答案：(1)先序(2)中序32.二叉树结点的对称序序列为A,B,C,D,E,F,G,后序序列为B,D,C,A,F,G,E,则该二叉树结点的前序序列为_(1)_,则该二叉树对应的树林包括_棵树。答案：(1)EACBDGF(2)233.二叉树的先序序列和中序序列相同的条件是 答案：任何结点至多只有右子女的二叉树。34.已知一棵二叉树的前序序列为abdecfhg,中序序列为dbeahfcg，则该二叉树的根为(1)，左子树中有,右子树中有 o答案：(1)a (2) dbe (3) hfcg35.一棵左子树为空的二叉树在先序线索化后，其中的空链域的个数为：_ 答案：236.若以4,5,6,7,

22、8作为叶子结点的权值构造哈夫曼树，则其带权路径长度是 答案：6937有数据WG=7 19,2,6,32,3,21,10，则所建Huffman树的树高是(1)，带权 路径长度WPL为_o答案：(1)6 (2)26138.有一份电文中共使用6个字符：a,b,c,d,e,f,它们的出现频率依次为2,3,4,7,8,9，试构造一棵哈夫曼树，则其加权路径长度WPL为(1)，字符c的编码是 o答案(1)80 (2)001return (sq.data(sq.front)(不唯一)39设n。为哈夫曼树的叶子结点数目，则该哈夫曼树共有答案：2n0-140.以下程序是二叉链表树中序遍历的非递归算法，型的定义如下

23、：typ edef struct node /*C语言/char data; struct node *lchild,*rchild;*bitree;void vst(bitree bt)/*bt bitree p; p=bt; in itstack(s); /*while(p II !emp ty(s)/*个结点。请填空使之完善。二叉树链表的结点类为根结点的指针*/初始化栈s为空栈*/栈s不为空*/if(p) push (s, p); (1); /*Pelse p=pop(s); prin tf(“%C ,p -data); (2)_答案：(1) p=p-lchild /沿左子树向下(2)p

24、=p-rchild41.二叉树存储结构同上题，以下程序为求二叉树深度的递归算法，请填空完善之。int depth(bitree bt) /*bt为根结点的指针*/int hl,hr;if (bt=NULL) return(1) _)_hl=de pth(bt-lchild); hr=de pth(bt-rchild);if(2)_ ) (3)_；return(hr+1);答案：(1)0(2)hlhr (3)hr=hl42.判断一个无向图是一棵树的条件是 _ 答案：有n个顶点，n-1条边的无向连通图43.有向图G的强连通分量是指 答案：有向图的极大强连通子图44.一个连通图的_ 是一个极小连通子

25、图。答案：生成树45.具有10个顶点的无向图，边的总数最多为答案：4546.若用n表示图中顶点数目则有 _答案：n(n-1)/247.G是一个非连通无向图，共有28条边，则该图至少有 _答案：948.在有向图的邻接矩阵表示中，计算第I个顶点入度的方法是答案：第I列非零元素个数49.对于一个具有n个顶点e条边的无向图的邻接表的表示，则表头向量大小为接表的边结点个数为答案：n 2e50.遍历图的过程实质上是 _,breath-first search遍历图的时间复杂度de pth-first search遍历图的时间复杂度 _，两者不同之处在于 _，反映在数据结构上的差别是_O答案：(1)查找顶点

26、的邻接点的过程0(n+e)0(n+e) (4)同(5)队列和栈51.已知一无向图G=(V,E),其中V=a,b,c,d,e E=(a,b),(a,d),(a,c),(d,c),(b,e)现用某一种图遍历方法从顶点a开始遍历图，得到的序列为abecd，则采用的是_方法。答案：深度优先52.一无向图G(V,E),其中V(G)=1,234,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

27、,3), (1,2),(1,5) , (2,4)，则采用的遍历方法是答案：宽度优先遍历入栈*/栈顶元素出栈*/条边的无向图成为完全图。个顶点。访问顶点的顺序不遍历53.为了实现图的广度优先搜索，存放被访问的结点以实现遍历。 答案：队列54.求图的最小生成树有两种算法，答案：克鲁斯卡尔55.Prim(普里姆)算法适用于求适用于求_的网的最小生成树。答案：边稠密边稀疏56克鲁斯卡尔算法的时间复杂度为 答案：O(eloge)边稀疏57.对于含N个顶点E条边的无向连通图，利用Prim算法生成最小代价生成树其时间复杂度为，利用Kruskal算法生成最小代价生成树其时间复杂度为答案：O(n2) O(elo

28、ge)58.有向图G可拓扑排序的判别条件是 答案：不存在环59.Dijkstra最短路径算法从源点到其余各顶点的最短路径的路径长度按产生，该算法弧上的权出现 _情况时，不能正确产生最短路径。答案：递增 负值60.有向图G=(V,E),其中V(G)=0,1,2,3,4,5,用三元组表示弧d.E(G)为从源点0到顶点3的最短路径长度是 _ ，经过的中间顶点是答案：50,经过中间顶点61.若不考虑基数排序，则在排序过程中，主要进行的两种基本操作是关键字的录的_O答案：比较，移动62.属于不稳定排序的有_O答案：希尔排序、简单选择排序、快速排序、堆排序等63分别采用堆排序，快速排序，冒泡排序和归并排序

29、，对初态为有序的表，则最省时间的 是算法，最费时间的是_ 算法答案：冒泡,快速64.不受待排序初始序列的影响，时间复杂度为O(Nf)的排序算法是_后一趟开始之前，所有元素都可能不在其最终位置上的排序算法是答案：(1)简单选择排序直接插入排序(最小的元素在最后时)65._直接插入排序用监视哨的作用是O答案：免去查找过程中每一步都要检测整个表是否查找完毕，提高了查找效率。66对n个记录的表r仁n进行简单选择排序，所需进行的关键字间的比较次数为 答案：7. n(n-1)/267.设用希尔排序对数组98,36,-9,0,47,23,1,8,10,7进行排序，给出的步长(也 称增量序列)依次是4,2,1

30、则排序需趟，写出第一趟结束后，数组中数据的排列次序_O答案：3,(10,7,-9,0,47,23,1,8,98,36)68从平均时间性能而言，_排序最佳。答案：.快速69.对于7个元素的集合1,2,3,4,5,6,7进行快速排序，具有最小比较和交换次数除了一个标志数组标志已访问的图的结点外，还需算法适合于求稀疏图的最小生成树。的网的最小生成树；kruskal(克鲁斯卡尔)算法图较为适合。,它对次序依次及弧上的权，则和记,在排序算法的最的初始排列次序为答案：14.(4,1,326,5,7)70._快速排序在的情况下最易发挥其长处。【长沙铁道学院1998二、5(2分)】答案：最好每次划分能得到两个

31、长度相等的子文件。设文件长度n=2k-1,第一遍划分得到两个长度n/2的子文件，第二遍划分得到4个长度n/4的子文件，以此类推，总共进行k=log2(n+1)遍划分，各子文件长度均为1,排序结束。71.堆是一种有用的数据结构。试判断下面的关键码序列中哪一个是堆_。16,72,31,23,94,5394,53,31,72,16,2316,53,23,94,31,7216,31,23,94,53,7294,31,53,23,16,72堆排序是一种_(1)_类型的排序，它的一个基本问题是如何建堆，常用的建堆算法是1964年Floyd提出的一一一一， 对含有n个元素的序列进行排序时，堆排序的时间复杂度

32、是， 所需要的附加结点是，。答案：(1)选择筛选法(3)O( nl og2n)(4)O(1)72.堆是一种有用的数据结构.堆排序是一种_(1)_排序，堆实质上是一棵结点的层次 序列。对含有N个元素的序列进行排序时，堆排序的时间复杂度是一一一一，所需的附加存储 结点是_ _梓梓)_)_。关键码序列05,23,16,68,94,72,71,73是否满足堆的性质5)_。答案：(1)选择(2)完全二叉树(3)O(Nlog73.设有字母序列Q,D,F,X,A,P,N,B,Y,M,C,W,趟扫描后的结果 _ 。答案：D,Q,F,X,A,P,B,N,M,Y,C,W三应用题1.若有100个学生，每个学生有学号

33、，姓名，平均成绩，采用什么样的数据结构最方便，写出这些结构？答案：将学号、姓名、平均成绩看成一个记录(元素，含三个数据项)的记录存于数组中。因一般无增删操作，故宜采用顺序存储。typ edefstructint num;/学号char name8;/姓名float score;/平均成绩n ode;node stude nt1OO;2.设一数列的输入顺序为123456,若采用堆栈结构，并以A和D分别表示入栈和出栈操作，试问通过入出栈操作的合法序列。(1)能否得到输出顺序为325641的序列。(2)能否得到输出顺序为154623的序列。答案：(1)能得到325641。在123依次进栈后，3和2出

34、栈，得部分输出序列32;然后4，5入栈，5出栈，得部分出栈序列325；6入栈并出栈，得部分输出序列3256；最后退栈，直到栈空。得输出序列325641。其操作序列为AAADDAADADDD(2)不能得到输出顺序为154623的序列。部分合法操作序列为ADAAAADDAD#到部分输出序列1546后，栈中元素为23,3在栈顶，故不可能2先出栈，得不到输出序列154623。3.设有下列递归算法：FUNCTION vol( n:in teger):i nteger;VAR x :in teger:2N) (4)O(1) (5)满足堆的性质请写出按2路归并排序方法对该序列进行一，将100个这样BEGIN

35、 IF n=0 THEN vol:=0ELSE BEGIN read(x);vol:=vol(n-1)+x;ENDEND;如该函数被调用时，参数n值为4,读入的x值依次为5,3,4,2，函数调用结束时返回值vol为多少？用图示描述函数执行过程中，递归工作栈的变化过程。答案：函数调用结束时vol=14。执行过程图示如下：vol(4)4.简述顺序存储队列的假溢出的避免方法及队列满和空的条件。答案：设顺序存储队列用一维数组qm表示，其中m为队列中元素个数，队列中元素在向量中的下标从0到m-1。设队头指针为front，队尾指针是rear，约定front指向队头元素 的前一位置，rear指向队尾元素。当

36、front等于-1时队空，rear等于m-1时为队满。由于 队列的性质(“删除”在队头而“插入”在队尾)，所以当队尾指针rear等于m-1时，若front不等于-1，则队列中仍有空闲单元， 所以队列并不是真满。这时若再有入队操作，“溢出”。其解决办法有二，一是将队列元素向前“平移”0)个结点的d度树，表示该树的多重链表中有多少个空链域 答案：n(n0)个结点的d度树共有 故该树的空链域有nd-( n-1)=n( d-1)+17.一棵二叉树中的结点的度或为0或为2,则二叉树的枝数为2(n0-1)，其中n0是度为0的结点的个数。答案：证明：设二叉树度为0和2的结点数及总的结点数分别为n0,n2和n

37、,则n=n0+n2(1)再设二叉树的分支数为B,除根结点外，每个结点都有一个分支所指，则n=B+1 (2)度为零的结点是叶子，没有分支，而度为2的结点有两个分支，因此(2)式可写为若用多重链表表示，树中每个结点都有d个链域，则在?为什么？nd个链域，除根结点外，每个结点均有一个指针所指， 个。n=2*n2+1.由（1）、（3）得n2=nO-1,代入（1），并由（1）和（2）得B=2*（n0-1）。证毕。&将下列由三棵树组成的森林转换为二叉树。（只要求给出转换结果）答案：森林转为二叉树的三步：（1）连线（将兄弟结点相连，各树的根看作兄弟）；（2）切线（保留最左边子女为独生子女，将其它子女

38、分枝切掉）（3）旋转（以最左边树的根为轴，顺时针向下旋转 其实经过（1）和（2），已转为二叉树， 执行（3）只是为了与平时的二叉树的画法一致。9.设一棵二叉树的先序、中序遍历序列分别为先序遍历序列：（1）（2）（3） 答案：略10.设某二叉树的前序遍历序列为：ABCDEFGGJ中序遍历序列为：BCAEDGHFI（1）试画出该二叉树；（2）写出由给定的二叉树的前序遍历序列和中序遍历序列构造出该二叉树的算法。（3）设具有四个结点的二叉树的前序遍历序列为abcd;S为长度等于四的由a, b,c,d排列构成的字符序列，若任取S作为上述算法的中序遍历序列，试问是否一定能45度）。A B D F C E

39、G H中序遍历序列：B F D A G E H C画出这棵二叉树。画出这棵二叉树的后序线索树。将这棵二叉树转换成对应的树（或森林）。M构造出相应的二叉树，为什么？试列出具有四个结点二叉树的全部形态及相应的中序遍历序列。答案：(1)略(2)设二叉树的前序遍历序列为P1,P2,，Pm中序遍历序列为S1,S2,，Sm因为前序遍历是“根左右”，中序遍历是“左根右”，则前序遍历序列中第一个结点是根结点( 到中序序列中查询到Si=P1,根据中序遍历时根结点将中序序列分成两部分的原则，有：若i=1，即S1= P1,则这时的二叉树没有左子树；否则，S1,S2,Si -1是左子树的中序遍历序列，用该序列和前序序

40、 列P2,P3，Pi去构造该二叉树的左子树。若i=m,即Sm=P1则这时的二叉树没有右子树；否则,Si+1,Si+2,，Sm是右子树的中序遍历序列，用该序列和前序序列中Pi+1,Pi+2,Pm,去构造该二叉树的右子树。(3)若前序序列是abed，并非由这四个字母的任意组合(4!=24)都能构造出二叉树。因为以abed为输入序列，通过栈只能得到1/(n+1)*2n!/(n!*n!)=14种，即以abed为前序序列的二叉树的数目是14。任取以abed作为中序遍历序列，并不全能与前序的abed序列构成二叉树。例如：若取中序列deab就不能。该14棵二叉树的形态及中序序列略。11.用一维数组存放的一棵

41、完全二叉树如下图所示：ABCDEFGHIJKL写出后序遍历该二叉树时访问结点的顺序。答案：HIDJKEBLFGCA12.已知二叉树采用二叉链表方式存放，要求返回二叉树T的后序序列中的第一个结点的指针，是否可不用递归且不用栈来完成？请简述原因。答案：后序遍历的顺序是“左子树一右子树一根结点” 遍历的第一个结点。下面的语句段说明了这一过程(设if (p!=null)while (p-lehild!=null | p-rchild!=null)while (p-lchild!=null) p=p-lchild;if (p-rehild!=null) p=p-rehild; return (p); /

42、返回后序序列第一个结点的指针；13.对于二叉树T的两个结点n1和n2,我们应该选择树T结点的前序、中序和后序中哪两 个序列来判断结点n1必定是结点n2的祖先，并给出判断的方法。不需证明判断方法的正确 性。答案：采用前序和后序两个序列来判断二叉树上结点在前序序列中某结点的祖先都排在其前。若结点而在后序序列中，某结点的祖先排在其后，即若结点根据这条规则来判断若结点必是结点n2的祖先。14.在二叉树的L lin k-Rli nk存储表示中，引入“线索”的好处是什么？答案：在二叉链表表示的二叉树中，引入线索的目的主要是便于查找结点的前驱和后继。因为若知道各结点的后继，二叉树的遍历就变成非常简单。二叉链

43、表结构查结点的左右子女非常方便，但其前驱和后继是在遍历中形成的。为了将非线性结构二叉树的结点排成线性序列，利用结点的空链域，左链为空时用作前驱指针，右链为空时作为后继指针。再引入左右标记ltag和rtag，规定ltag=O,lehild指向左子女,ltag=1时,lehild指向前驱；当rtag=0时，rchild指向右子女，rtag=1时，rehild指向后继。这样，在线索二叉树(特别是中序线索二叉树)上遍历就消除了递归，也不使用栈(后序线索二叉树查后继仍需 要栈。)P1）。因此，二叉树最左下的叶子结点是P是二叉树根结点的指针)。n1必定是结点n2的祖先。n1是n2的祖先，则n1必定在n2之

44、前。n1是n2的祖先，则n1必在n2之后。n1在前序序列中在n2之前，在后序序列中又在n2之后，则它15.假设一个二叉树的两种遍历如下：前序：ABFGCHDEIJLK中序：FGBHCDILJKEA(1)画出这棵二叉树以及它的中序线索树；(2)写出在中序线索树的情况下，找到结点N的前驱结点的算法INORDER-PRIOR(N,X)答案：(1)略(2)BiTree INORDER-PRIOR(N,X) /在中序线索二叉树上查找结点N的前驱 结点Xif (n-ltag=1)X=N-lchild; elsep=N-lchild;while (p-rtag=0) p=p-rchild;X=p;retur

45、n (p); 16.设有正文AADBAACACCDACACAA符集为A,B,C,D,设计一套二进制编码，使得上述正文 的编码最短。答案：字符A,B, C, D出现的次数为9,1,5,3。其哈夫曼编码如下A:1,B:000,C:01,D:001 17给定集合15,3,14,2,6,9,16,17(1)用表示外部结点，用O表示内部结点，构造相应的(2)计算它的带权路径长度：(3)写出它的huffman编码：(4)huffman编码常用来译码，请用语言叙述写出其译码的过程。答案：(1)略,.(2)wpl=(2+3)*5+6*4+(9+14+15)*3+(16+17)*2=229,(3)编码为：15:

46、111,3:10101, 14:110, 2:10100, 6:1011,9:100, 16:00, 17:01(4)常用哈夫曼树为通讯用的字符编码，本题中集合的数值解释为字符发生的频率(次数)。由哈夫曼树构造出哈夫曼编码。译码时，进行编码的“匹配”，即从左往右扫描对方发来的“编码串”，用字符编码去匹配，得到原来的元素(本题中的数)。18.已知下列字符A B、C、DE、F、G的权值分别为3、12、7、4、2、8,11,试填写出其对应哈夫曼树HT的存储结构的初态和终态。答案：略19.什么是前缀编码？举例说明如何利用二叉树来设计二进制的前缀编码。答案：前缀码是一编码不是任何其它编码前缀的编码。例如

47、，0和01就不是前缀码，因为编码0是编码01的前缀。仅从编码来看，0和01是前缀码，但因历史的原因，它不被称为 前缀码，而是把一编码不是另一编码前缀的编码称为前缀码。利用二叉树可以构造前缀码，例如，以A,为0,右分枝解释成1,从根结点到叶子结点的造出最优二叉树，使编码长度最短。20.如果一棵huffman树T有no个叶子结点，程。答案：哈夫曼树只有度为0的叶子结点和度为的结点数n为n=n0+n2。另根据二叉树性质：任意二叉树中度为结点数n2间的关系是n2=n0-1,代入上式，则n=n0+n2=2n0-1。21请回答下列关于图(Graph)的一些问题：(1)有n个顶点的有向强连通图最多有多少条边

48、？最少有多少条边？(2) .表示有1000个顶点、l000条边的有向图的邻接矩阵有多少个矩阵元素？是否稀疏矩阵？(3).对于一个有向图，不用拓扑排序，如何判断图中是否存在环？return (X);huffman树:B,C,D为叶子可构成二叉树，将左分枝解释0、1串就是叶子的前缀码。用哈夫曼树可构那么，树T有多少个结点，要求给出求解过2的分枝结点，设数量分别为n0和n2,则树0的结点数n0和度为2的答案：(1)n(n-1)，n(2)106，不一定是稀疏矩阵(稀疏矩阵的定义是非零个数远小于该矩阵元素个数，且分 布无规律)(3) 使用深度优先遍历，按退出dfs过程的先后顺序记录下的顶点是逆向 若在执

49、行dfs(v)未退出前，出现顶点U到v的回边，则说明存在包含顶点22.解答问题。设有数据逻辑结构为：B = (K, R), K = k1, k2,k9R=, , , , ,k5, , (1) .画出这个逻辑结构的图示。(2) .相对于关系r,指出所有的开始接点和终端结点。(3) .分别对关系r中的开始结点，举出一个拓扑序列的例子。(4) .分别画出该逻辑结构的正向邻接表和逆向邻接表。答案：(1)拓扑有序序列。v和顶点U的环。k6, .(2)开始结点(3)拓扑序列K2，K，32586794，K2,终端结点(出度为0)K6，K7。K5，K6，K8，K9，K7KB，K9，冷入度：K2，K3，K，Ks

50、，K,或K2,之后，若遇多个入度为K1，K3，规则：开始结点为(4)略23.已知无向图(3，4)试画出点j?答案：图略。已知顶点i，找与i相邻的顶点j的规则如下：在顶点向量中，找到顶点i，顺其指针找到第一个边结点(若其指针为空，则顶点i无邻接点)。在边结点中，取出两顶 点信息，若其中有j，则找到顶点j;否则，沿从i发出的另一条边的指针(ilink)找i的下一邻接点。在这种查找过程中，若边结点中有j，则查找成功；若最后ilink为空，则顶点i无邻接点j。24.下面是求无向连通图最小生成树的一种方法。将图中所有边按权重从大到小排序为(e1,e2,em)i:=1WHILE (所剩边数=顶点数)BEG

51、IN从图中删去ei若图不再连通，则恢复eii:=i+1K4,0的顶点，按顶点编号顺序选择。G, V(G)=1,2,3,4,E(G)G的邻接多表，并说明，若已知点=(1，2)，(1，3)，(2，3)，(2，4)，I，如何根据邻接多表找到与I相邻的END.试证明这个算法所得的图是原图的最小代价生成树。答案：无向连通图的生成树包含图中全部n个顶点，以及足以使图连通的n-1条边。而最小生成树则是各边权值之和最小的生成树。从算法中WHILE (所剩边数=顶点数)来看，循环到边数比顶点数少1(即n-1)停止，这符合n个顶点的连通图的生成树有n-1条边的定义;由于边是按权值从大到小排序，删去的边是权值大的边

52、，结果的生成树必是最小生成树；法中“若图不再连通，则恢复ei”，含义是必须保留使图连通的边，这就保证了是生成树，否则或者是有回路，或者成了连通分量，均不再是生成树。25.已知一个无向图如下图所示，要求分别用Prim和Kruskal算法生成最小树(假设以为起点，试画出构造过程)。答案：略26.已知图的邻接矩阵为:V1 V2 V3 V4 V5 V6 V7 V8 V9 V10当用邻接表作为图的存储结构，(1).以顶点V1为出发点的唯一的深度优先遍历；(2).以顶点V1为出发点的唯一的广度优先遍历；(3).该图唯一的拓扑有序序列。答案：略27.在各种排序方法中，哪些是稳定的？哪些是不稳定的？并为每一种

53、不稳定的排序方法举 出一个不稳定的实例。答案：V1V2V3V4V5V6V7V8V9V1000000000100000000100000000111000000010000000001100000000110000000001000000101100000000011且邻接表都按序号从大到小排序时，试写出:排序方法平均时间最坏情况辅助空间稳定性直接插入排序O(n2)O(n2)O (1)稳定折半插入排序O(n2)O(n2)O (1)稳定二路插入排序O(n2)O(n2)O(n)稳定表插入排序O(n2)O(n2)O (1)稳定起泡排序O(n2)O(n2)O (1)稳定直接选择排序O(n2)O(n2)O

54、 (1)不稳定希尔排序_, 1.3 .O(n)O(n1.3)O (1)不稳定快速排序O (nlog2n)O(n2)O(log2n)不稳定堆排序O (nlog2n)O(nlog2n)O (1)不稳定2-路归并排序O (nlog2n)O(nlog2n)O(n)稳定不稳定排序举例2,2,13,2,2,1(d=2,d=1)2,2,12,1,1(极大堆)基数排序0(d*(rd+n)0(d*(rd+n)0 (rd )稳定28.设有5个互不相冋的兀素a、b、c、d、e,能否通过7次比较就将其*排好序？如果能，请列出其比较过程；如果不能，则说明原因。答案：可以做到。取a与b进行比较，c与d进行比较。设ab,c

55、d(ab和cd，则有序abd;若bdb，此时已 进行了3次比较。再把另外两个元素按折半插入排序方法，插入到上述某个序列中共需 次比较，从而共需7次比较。29.利用比较的方法进行排序，在最坏的情况下，能达到的最好时间复杂性是什么？请给出详细证明。答案：假定待排序的记录有n个。由于含n个记录的序列可能出现的状态有n!个，则描述个记录排序过程的判定树必须有n!个叶子结点。因为若少一个叶子，则说明尚有两种状态没有分辨出来。我们知道，若二叉树高度是h则叶子结点个数最多为2h-1;反之，若有个叶子结点，则二叉树的高度至少为Iog2u+1。这就是说，描述n个记录排序的判定树必定存在一条长度为log2(n!)

56、的路径。即任何一个籍助“比较”进行排序的算法，在最坏情况=0(niog2n)。即0(nIog2n)。证毕。点连接的弧来确定顶点序列；冒泡排序是借助交换思想通过比较相邻结点关键字大小进行 排序的算法。31.简述直接插入排序，简单选择排序，2-路归并排序的基本思想以及在时间复杂度和排序稳定性上的差别。答案：直接插入排序的基本思想是基于插入，开始假定第一个记录有序，然后从第二个记录开始，依次插入到前面有序的子文件中。即将记录Ri(2=i=n)插入到有序子序列R1.i-1中，使记录的有序序列从R1.i-1变为R1.i，最终使整个文件有序。共进行n-1趟插入。最坏时间复杂度是0(n2)，平均时间复杂度是

57、0(n2)，空间复杂度是O(1),是稳定排序。简单选择排序的基本思想是基于选择，开始有序序列长度为零，第i(1=i n)趟简单选择排序是，从无序序列Ri.n的n-i+1记录中选出关键字最小的记录，和第i个记录交换，2使有序序列逐步扩大，最后整个文件有序。共进行n-1趟选择。最坏时间复杂度是0(n ),平均时间复杂度是0(n2)，空间复杂度是O(1)，是不稳定排序。二路并归排序的基本思想是基于归并，开始将具有n个待排序记录的序列看成是n个长度为1的有序序列，然后进行两两归并，得到n/2个长度为2的有序序列，再进行两两归并，得到n/4个长度为4的有序序列。如此重复，经过log2n趟归并，最终得到一

58、个长度为n的有序序列。最坏时间复杂度和平均时间复杂度都是0(niog2n)，空间复杂度是O(n),是稳定排序。32.快速排序，堆排序和希尔排序是时间性能较好的排序方法，也是稳定的排序方法。 正误并改错。答案：错误。快速排序，堆排序和希尔排序是时间性能较好的排序方法， 序方法。33.对于堆积排序法，快速排序法和归并排序法，若仅从节省存储空间考虑，则应该首先选取其中哪种方法？其次选取哪种方法？若仅考虑排序结果的稳定性，则应该选取其中哪种方下所需进行的比较次数至少是log2(n!)。根据斯特林公式，有log2(n!)籍助于“比较”进行排序的算法在最坏情况下能达到的最好时间复杂度为30.以下概念的区别

59、：拓扌卜排序与冒泡排序。答案：拓扑排序，是有向图的顶点依照弧的走向，找出一个全序集的过程，主要是根据与顶判断但都是不稳定的排法？若仅从平均情况下排序最快这一点考虑，则应该选取其中哪些方法？ 答案：从节省存储空间考虑：先选堆排序，再选快速排序，最后选择归并排序；从排序结果的稳定性考虑：选择归并排序。堆排序和快速排序都是不稳定排序； 从平均情况下排序最快考虑：先选择快速排序。34.在堆排序、快速排序和合并排序中：(1).若只从存储空间考虑，则应首先选取哪种排序方法，其次选取哪种排序方法，最后 选取哪种排序方法？若只从排序结果的稳定性考虑，则应选取哪种排序方法？.若只从平均情况下排序最快考虑，则应选

60、取哪种排序方法？.若只从最坏情况下排序最快并且要节省内存考虑，则应选取哪种排序方法？(1)堆排序，快速排序，归并排序Shell(2)(3)(4)答案：35.快排序、堆排序、合并排序、 空间最多，哪几种排序算法是不稳定的？答案： 平均比较次数最少 序、 堆排序、 希尔排序。36.欲求前k个最大元素， 法是否是稳定分类算法，:快速排序；(2)归并排序(3)快速排序(4)堆排序 排序中哪种排序平均比较次数最少，哪种排序占用占用空间最多：归并排序；不稳定排序算法：快速排用什么分类方法好？为什么？什么是稳定分类？分别指出下列算 或易于改成稳定分类算法？B.快速分类C.合并分类D.堆分类E.基数分类答案：求前k个最大元素选堆排序较好。因为在建含 比较次数不