数据结构习题集附答案.doc

《数据结构习题集附答案.doc》由会员分享，可在线阅读，更多相关《数据结构习题集附答案.doc（28页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、数据结构习题集附答案数据结构习题集附答案 第一章 绪 论 一、选择题 1.组成数据的基本单位是（ ）A数据项 B数据类型 C数据元素 D数据变量 2.数据结构是研究数据的（ ）以及它们之间的相互关系。A理想结构，物理结构 B理想结构，抽象结构 C物理结构，逻辑结构 D抽象结构，逻辑结构 3.在数据结构中，从逻辑上可以把数据结构分成（ ）。A动态结构和静态结构 B紧凑结构和非紧凑结构 C线性结构和非线性结构 D内部结构和外部结构 4.数据结构是一门研究非数值计算的程序设计问题中计算机的 （）以及它们之间的（）和运算等的学科。A数据元素 B计算方法 C逻辑存储 D数据映像 A结构 B关系 C运算

2、D算法 5.算法分析p 的两个主要方面是（ ）。A数据复杂性和程序复杂性 B正确性和简明性 C可读性和简明性 D空间复杂性和时间复杂性 6.算法分析p 的目的是（ ）。A找出数据结构的合理性 B研究算法中的输入和输出的关系 C分析p 算法的效率以求改进 D分析p 算法的易懂性和文档性 7.计算机算法指的是（）,它必须具备输入、输出和（）等5个特性。A计算方法 B排序方法 C解决问题的有限运算序列 D调度方法 A可执行性，可移植性和可扩充性 B可行性，确定性和有穷性 C确定性、有穷性和稳定性 D易读性、稳定性和安全性 二、判断题 1.数据的机内表示称为数据的存储结构。（ ）2.算法就是程序。（

3、）3.数据元素是数据的最小单位。（ ）4.算法的五个特性为：有穷性、输入、输出、完成性和确定性。（ ）5.算法的时间复杂度取决于问题的规模和待处理数据的初态。（ ）三、填空题 1.数据逻辑结构包括_、_、_和_四种类型,其中树形结构和图形结构合称为_。2.在线性结构中,第一个结点_前驱结点,其余每个结点有且只有_个前驱结点；最后一个结点_后续结点,其余每个结点有且只有_个后续结点。3.在树形结构中,树根结点没有_结点,其余每个结点有且只有_个前驱结点；叶子结点没有_结点,其余每个结点的后续结点可以_。4.在图形结构中,每个结点的前驱结点数和后续结点数可以_。5.线性结构中元素之间存在_关系,树

4、形结构中元素之间存在_关系,图形结构中元素之间存在_关系。6.算法的五个重要特性是_、_、_、_、_。7.数据结构的三要素是指_、_和_。8.链式存储结构与顺序存储结构相比较,主要优点是_。9.设有一批数据元素,为了最快的存储某元素,数据结构宜用_结构,为了方便插入一个元素,数据结构宜用_结构。四、算法分析p 题 1.求下列算法段的语句频度及时间复杂度 for(i=1; ine_t=p;p-ne_t=s; Bs-ne_t=p-ne_t;p-ne_t=s; Cs-ne_t=p-ne_t;p=s; Dp-ne_t=s;s-ne_t=p; 5.在一个单链表中，若删除p所指结点的后续结点，则执行（ ）

5、。Ap-ne_t=p-ne_t-ne_t; Bp=p-ne_t; p-ne_t=p-ne_t-ne_t; Cp-ne_t=p-ne_t; Dp=p-ne_t-ne_t; 6.下列有关线性表的叙述中，正确的是（ ）。A线性表中的元素之间隔是线性关系 B线性表中至少有一个元素 C线性表中任何一个元素有且仅有一个直接前趋 D线性表中任何一个元素有且仅有一个直接后继 7.线性表是具有n个（ ）的有限序列（n0)。A表元素 B字符 C数据元素 D数据项 二、判断题 1.线性表的链接存储，表中元素的逻辑顺序与物理顺序一定相同。（ ）2.如果没有提供指针类型的语言，就无法构造链式结构。（ ）3.线性结构的特

6、点是只有一个结点没有前驱，只有一个结点没有后继，其余的结点只有一个前驱和后继。（ ）4.语句p=p-ne_t完成了指针负值并使p指针得到了p指针所指后继结点的数据域值。（ ）5.要想删除p指针的后继结点，我们应该执行q=p-ne_t ；p-ne_t=q-ne_t；free(q)。（ ）三、填空题 1.已知P为单链表中的非首尾结点，在P结点后插入S结点的语句为：_。2.顺序表中逻辑上相邻的元素物理位置( )相邻， 单链表中逻辑上相邻的元素物理位置_相邻。3.线性表L（a1，a2，an）采用顺序存储，假定在不同的n1个位置上插入的概率相同，则插入一个新元素平均需要移动的元素个数是_。4.在非空双向

7、循环链表中，在结点q的前面插入结点p的过程如下：p-prior=q-prior; q-prior-ne_t=p; p-ne_t=q; _; 5.已知L是无表头结点的单链表，是从下列提供的答案中选择合适的语句序列，实现：表尾插入s结点的语句序列是_。Ap-ne_t=s; Bp=L; CL=s; Dp-ne_t=s-ne_t; Es-ne_t=p-ne_t; Fs-ne_t=L; Gs-ne_t=null; Hwhile(p-ne_t!=0) p=p-ne_t; Iwhile(p-ne_t!=null) p=p-ne_t; 四、算法设计题 1.试编写一个求已知单链表的数据域的平均值的函数（数据域数

8、据类型为整型）。2.已知带有头结点的循环链表中头指针为head,试写出删除并释放数据域值为_的所有结点的c函数。3.某百货公司仓库中有一批电视机，按其价格从低到高的次序构成一个循环链表，每个结点有价格、数量和链指针三个域。现出库（销售）m台价格为h的电视机，试编写算法修改原链表。4.某百货公司仓库中有一批电视机，按其价格从低到高的次序构成一个循环链表，每个结点有价格、数量和链指针三个域。现新到m台价格为h的电视机，试编写算法修改原链表。5.线性表中的元素值按递增有序排列，针对顺序表和循环链表两种不同的存储方式，分别编写C函数删除线性表中值介于a与b（ab）之间的元素。6.设A=(a0,a1,a

9、2,an-1),B=(b0,b1,b2,bm-1)是两个给定的线性表,它们的结点个数分别是n和m,且结点值均是整数。若n=m，且 ai= bi （0iB。试编写一个比较A和B的C函数，该函数返回 -1或 0或 1，分别表示 AB。7.试编写算法,删除双向循环链表中第k个结点。8.线性表由前后两部分性质不同的元素组成(a0,a1,an-1,b0,b1,bm-1),m和n为两部分元素的个数,若线性表分别采用数组和链表两种方式存储,编写算法将两部分元素换位成(b0,b1,bm-1,a0,a1,an-1),分析p 两种存储方式下算法的时间和空间复杂度。9.用循环链表作线性表(a0,a1,an-1)和（

10、b0,b1,bm-1）的存储结构,头指针分别为ah和bh，设计C函数，把两个线性表合并成形如（a0,b0,a1,b1,）的线性表，要求不开辟新的动态空间,利用原来循环链表的结点完成合并操作,结构仍为循环链表,头指针为head,并分析p 算法的时间复杂度。10.试写出将一个线性表分解为两个带有头结点的循环链表，并将两个循环链表的长度放在各自的头结点的数据域中的C函数。其中,线性表中序号为偶数的元素分解到第一个循环链表中,序号为奇数的元素分解到第二个循环链表中。11.试写出把线性链表改为循环链表的C函数。12.己知非空线性链表中_结点的直接前驱结点为y,试写出删除_结点的C函数。第三章 栈和队列

11、一、选择题 1.一个栈的入栈序列是a,b,c,d,e,则栈的不可能的输出序列是（ ）。Aedcba Bdecba Cdceab Dabcde 2.栈结构通常采用的两种存储结构是（ ）。A线性存储结构和链表存储结构 B散列方式和索引方式 C链表存储结构和数组 D线性存储结构和非线性存储结构 3.判定一个栈ST(最多元素为m0)为空的条件是（ ）。AST-!=0 BST-=0 CST-!=m0 DST-=m0 4.判定一个栈ST(最多元素为m0)为栈满的条件是（ ）。AST-!=0 BST-=0 CST-!=m0-1 DST-=m0-1 5.一个队列的入列序列是1,2,3,4,则队列的输出序列是（

12、 ）。A4,3,2,1 B1,2,3,4 C1,4,3,2 D3,2,4,1 6.循环队列用数组A0,m-1存放其元素值，已知其头尾指针分别是front和rear则当前队列中的元素个数是（ ）。A(rear-front+m)m Brear-front+1 Crear-front-1 Drear-front 7.栈和队列的共同点是（ ）A都是先进后出 B都是先进先出 C只允许在端点处插入和删除元素 D没有共同点 8.表达式a_(b+c)-d的后缀表达式是（ ）。Aabcd_+- Babc+_d- Cabc_+d- D-+_abcd 9.4个元素a1，a2，a3和a4依次通过一个栈，在a4进栈前，

13、栈的状态，则不可能的出栈序是（ ）。Aa4，a3，a2，a1 Ba3，a2，a4，a1 Ca3，a1，a4，a2 Da3，a4，a2，a1 10.以数组Q0.m1存放循环队列中的元素，变量rear和qulen分别指示循环队列中队尾元素的实际位置和当前队列中元素的个数，队列第一个元素的实际位置是（ ）。Arearqulen Brearqulenm Cmqulen D1（rearmqulen）m 二、填空题 1.栈的特点是_，队列的特点是_。2.线性表、栈和队列都是_结构,可以在线性表的_位置插入和删除元素，对于栈只能在_插入和删除元素，对于队列只能在_插入元素和_删除元素。3.一个栈的输入序列是

14、12345,则栈有输出序列12345是_。(正确/错误) 4.设栈S和队列Q的初始状态皆为空，元素a1，a2，a3，a4，a5和a6依次通过一个栈，一个元素出栈后即进入队列Q，若6个元素出队列的顺序是a3，a5，a4，a6，a2，a1则栈S至少应该容纳_个元素。三、算法设计题 1.假设有两个栈s1和s2共享一个数组stackM,其中一个栈底设在stack0处，另一个栈底设在stackM-1处。试编写对任一栈作进栈和出栈运算的C函数push（_,i)和pop(i),i=l,2。其中i=1表示左边的栈，,i=2表示右边的栈。要求在整个数组元素都被占用时才产生溢出。2利用两个栈s1,s2模拟一个队列

15、时,如何用栈的运算来实现该队列的运算?写出模拟队列的插入和删除的C函数。一个栈s1用于插入元素,另一个栈s2用于删除元素。第四章 串 一、选择题 1.下列关于串的叙述中，正确的是（ ）A一个串的字符个数即该串的长度 B一个串的长度至少是1 C空串是由一个空格字符组成的串 D两个串S1和S2若长度相同，则这两个串相等 2.字符串“abaaabab“的ne_tval值为( ) A(0,1,01,1,0,4,1,0,1) B(0,1,0,0,0,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) 3.字符串满足下式,其中head和tail的定义同

16、广义表类似,如head(_yz)=_,tail(_yz)= yz,则s=( )。concat(head(tail(s),head(tail(tail(s)= dc。Aabcd Bacbd Cacdb Dadcb 4.串是一种特殊的线性表,其特殊性表现在（ ）A可以顺序存储 B数据元素是一个字符 C可以链式存储 D数据元素可以是多个字符 5设串S1=ABCDEFG,s2=PQRST,函数CONCAT（_，Y）返回_和Y串的连接串，SUBSTR（S，I，J）返回串S从序号I开始的J个字符组成的字串，LENGTH（S）返回串S的长度，则CONCAT（SUBSTR（S1，2，LENGTH（S2），SU

17、BSTR（S1，LENGTH（S2），2）的结果串是（ ）。ABCDEF BBCDEFG CBCPQRST DBCDEFEF 二、算法设计 1.分别在顺序存储和一般链接存储两种方式下,用C语言写出实现把串s1复制到串s2的串复制函数strcpy(s1,s2)。2.在一般链接存储(一个结点存放一个字符)方式下,写出采用简单算法实现串的模式匹配的C语言函数int L_inde_(t,p)。第五章 数组与广义表 一、选择题 1常对数组进行的两种基本操作是（ ）A建立与删除 B索引和修改 C查找和修改 D查找与索引 2.二维数组M的元素是4个字符(每个字符占一个存储单元)组成的串,行下标i的范围从0到

18、4,列下标j的范围从0到5,M按行存储时元素M35的起始地址与M按列存储时元素( )的起始地址相同。AM24 BM34 CM35 DM44 3.数组A810中,每个元素A的长度为3个字节,从首地址SA开始连续存放在存储器内,存放该数组至少需要的单元数是（ ）。A80 B100 C240 D270 4.数组A810中,每个元素A的长度为3个字节,从首地址SA开始连续存放在存储器内,该数组按行存放时,元素A74的起始地址为（ ）。ASA+141 BSA+144 CSA+222 DSA+225 5.数组A810中,每个元素A的长度为3个字节,从首地址SA开始连续存放在存储器内,该数组按列存放时,元素

19、A47的起始地址为（ ）。ASA+141 BSA+180 CSA+222 DSA+225 6.稀疏矩阵一般的压缩存储方法有两种,即（ ）。A二维数组和三维数组 B三元组和散列 C三元组和十字链表 D散列和十字链表 7.若采用三元组压缩技术存储稀疏矩阵,只要把每个元素的行下标和列下标互换,就完成了对该矩阵的转置运算,这种观点（ ）。A正确 B错误 8.设矩阵A是一个对称矩阵,为了节省存储,将其下三角部分按行序存放在一维数组B1,n(n-1)/2中,对下三角部分中任一元素ai,j(itag=1; h-dd.sublist=creat_GL(s); Else h-tag=0; h-dd.data=c

20、h; else h=NULL; ch=_(_s); (_s)+; if(h!=NULL) if(ch=,) h-link =creat_GL(s); else h-link=NULL; return(h); void prn_GL(NODE _p) if(p!=NULL) if(p-tag=1) printf(“(“); if(p-dd.sublist =NULL) printf(“ “); else prn_GL(p-dd.sublist ); else printf(“c“,p-dd.data); if(p-tag=1) printf(“)“); if(p-link!=NULL) prin

21、tf(“,“); prn_GL(p-link); NODE _copy_GL(NODE _p) NODE _q; if(p=NULL) return(NULL); q=(NODE _)malloc(sizeof(NODE); q-tag=p-tag; if(p-tag) q-dd.sublist =copy_GL(p-dd.sublist ); else q-dd.data =p-dd.data; q-link=copy_GL(p-link); return(q); NODE _head(NODE _p) /_求表头函数 _/ return(p-dd.sublist); NODE _tail(

22、NODE _p) /_求表尾函数 _/ return(p-link); int sum(NODE _p) /_求原子结点的数据域之和函数 _/ int m,n; if(p=NULL) return(0); else if(p-tag=0) n=p-dd.data; else n=sum(p-dd.sublist); if(p-link!=NULL) m=sum(p-link); else m=0; return(n+m); int depth(NODE _p) /_求表的深度函数 _/ int h,ma_dh; NODE _q; if(p-tag=0) return(0); else if(p

23、-tag=1p-dd.sublist=NULL) return 1; else ma_dh=0; while(p!=NULL) if(p-tag=0) h=0; else q=p-dd.sublist; h=depth(q); if(hma_dh)ma_dh=h; p=p-link; return(ma_dh+1); main NODE _hd,_hc; char s100,_p; p=gets(s); hd=creat_GL(p); prn_GL(head(hd); prn_GL(tail(hd); hc=copy_GL(hd); printf(“copy after:“); prn_GL(

24、hc); printf(“sum:dn“,sum(hd); printf(“depth:dn“,depth(hd); 第六章 树 一、选择题 1.在线索化二叉树中,t所指结点没有左子树的充要条件是（ ）。At-left=NULL Bt-ltag=1 Ct-ltag=1且t-left=NULL D以上都不对 2.二叉树按某种顺序线索化后,任一结点均有指向其前趋和后继的线索,这种说法（ ）。A正确 B错误 C不同情况下答案不确定 3.二叉树的前序遍历序列中,任意一个结点均处在其子女结点的前面,这种说法（ ）。A正确 B错误 C不同情况下答案不确定 4.由于二叉树中每个结点的度最大为2,所以二叉树是

25、一种特殊的树,这种说法（ ）。A正确 B错误 C不同情况下答案不确定 5.设高度为h的二叉树上只有度为0和度为2的结点,则此类二叉树中所包含的结点数至少为（ ）。A2h B2h-1 C2h+1 Dh+1 6.已知某二叉树的后序遍历序列是dabec。中序遍历序列是debac,它的前序遍历序列是（ ）。Aacbed Bdecab Cdeabc Dcedba 7.如果T2是由有序树T转换而来的二叉树,那么T中结点的前序就是T2中结点的（ ）A前序 B中序 C后序 D层次序 8.某二叉树的前序遍历结点访问顺序是abdgcefh,中序遍历的结点访问顺序是dgbaechf,则其后序遍历的结点访问顺序是（

26、）。Abdgcefha Bgdbecfha Cbdgaechf Dgdbehfca 9.二叉树为二叉排序树的充分必要条件是其任一结点的值均大于其左孩子的值、小于其右孩子的值。这种说法（ ）。A正确 B错误 C不同情况下答案不确定 10.按照二叉树的定义,具有3个结点的二叉树有（ ）种。A3 B4 C5 D6 11.在一非空二叉树的中序遍历序列中,根结点的右边（ ）。A只有右子树上的所有结点 B只有右子树上的部分结点 C只有左子树上的部分结点 D只有左子树上的所有结点 12.树最适合用来表示（ ）。A有序数据元素 B无序数据元素 C元素之间具有分支层次关系的数据 D元素之间无联系的数据 13.任

27、何一棵二叉树的叶结点在先序、中序和后序遍历序列中的相对次序（ ）。A不发生改变 B发生改变 C不能确定 D以上都不对 14.实现任意二叉树的后序遍历的非递归算法而不使用栈结构,最佳方案是二叉树采用（ ）存储结构。A二叉链表 B广义表存储结构 C三叉链表 D顺序存储结构 15.对一个满二叉树,m个树叶,n个结点,深度为h,则（ ）。An=h+m Bh+m=2n Cm=h-1 Dn=2h-1 16.如果某二叉树的前序为stuwv,中序为uwtvs,那么该二叉树的后序为（ ）。Auwvts Bvwuts Cwuvts Dwutsv 17.具有五层结点的二叉平衡树至少有（ ）个结点。A10 B12 C

28、15 D17 二、判断题 1.二叉树中任何一个结点的度都是2。（ ）2.由二叉树结点的先根序列和后根序列可以唯一地确定一棵二叉树。（ ）3.一棵哈夫曼树中不存在度为1的结点。（ ）4.平衡二叉排序树上任何一个结点的左、右子树的高度之差的绝对值不大于2（ ）三、填空题 1.指出树和二叉树的三个主要差别_,_,_。2.从概念上讲,树与二叉树是两种不同的数据结构,将树转化为二叉树的基本目的是_。3.若结点A有三个兄弟(包括A本身),并且B是A的双亲结点,B的度是_。4.若一棵具有n个结点的二叉树采用标准链接存储结构,那么该二叉树所有结点共有_个空指针域。5.已知二叉树的前序序列为ABDEGCFHIJ

29、,中序序列为DBGEAHFIJC,写出后序序列_。6.已知二叉树的后序序列为FGDBHECA,中序序列为BFDGAEHC ,并写出前序序列_。7.找出满足下列条件的二叉树 1）先序和中序遍历，得到的结点访问顺序一样。_。2）后序和中序遍历，得到的结点访问顺序一样。_。3）先序和后序遍历，得到的结点访问顺序一样。_。8.一棵含有n个结点的k叉树，可能达到的最大深度和最小深度各是多少？_。9.一棵二叉树有67个结点，这些结点的度要么是0，要么是2。这棵二叉树中度为2的结点有_个。10.含有100个结点的树有_条边。四、问答题 1.一棵深度为h的满m叉树具有如下性质:第h层上的结点都是叶结点,其余各

30、层上每个结点都有m棵非空子树。若按层次从上到下,每层从左到右的顺序从1开始对全部结点编号,试计算: (1)第k层结点数(1kh)。(2)整棵树结点数。(3)编号为i的结点的双亲结点的编号。(4)编号为i的结点的第j个孩子结点(若有)的编号。2.证明：一个满k叉树上的叶子结点数n0和非叶子结点数n1之间满足以下关系：n0=（k-1）n1+1 3.已知一组元素为(50,28,78,65,23,36,13,42,71）,请完成以下操作: (1)画出按元素排列顺序逐点插入所生成的二叉排序树BT。(2)分别计算在BT中查找各元素所要进行的元素间的比较次数及平均比较次数。(3)画出在BT中删除(23后的二

31、叉树。4.有七个带权结点,其权值分别为3,7,8,2,6,10,14,试以它们为叶结点构造一棵哈夫曼树(请按照每个结点的左子树根结点的权小于等于右子树根结点的权的次序构造,并计算出带权路径长度WPL及该树的结点总数。5.有一电文共使用五种字符a,b,c,d,e,其出现频率依次为4,7,5,2,9。(1)试画出对应的编码哈夫曼树(要求左子树根结点的权小于等于右子树根结点的权)。(2)求出每个字符的晗夫曼编码。(3)求出传送电文的总长度。(4)并译出编码系列1100011100001的相应电文。五、算法设计 已知一棵具有n个结点的完全二叉树被顺序存储在一维数组An中,试编写一个算法输出Ai结点的双

32、亲和所有孩子。二叉树其他运算的算法（只作参考）#include “stdio.h“ #include “malloc.h“ typedef struct node char data; struct node _lchild,_rchild; NODE; NODE _T; void create(NODE _T) /创建二叉树 char ch; ch=getchar; if(ch= ) _T=NULL; else _T=(NODE _)malloc(sizeof(NODE); (_T)-data=ch; create(_T)-lchild); create(_T)-rchild); void

33、inorder(NODE _p) /中序编历二叉树 if(p!=NULL) inorder(p-lchild); printf(“c “,p-data); inorder(p-rchild); int num=0; void count(NODE _p) /统计出二叉树中单孩子的结点数方法1 if(p!=NULL) count(p-lchild); if(p-lchild!=NULLp-rchild=NULL|p-lchild=NULLp-rchild!=NULL) num+; count(p-rchild); void count1(NODE _p,int _num1) if(p!=NULL

34、) count1(p-lchild,num1); if(p-lchild!=NULLp-rchild=NULL|p-lchild=NULLp-rchild!=NULL) (_num1)+; count1(p-rchild,num1); int onechild(NODE _t) /统计出二叉树中单孩子的结点数方法2 int num1,num2; if(t=NULL) return(0); else if(t-lchild=NULLt-rchild!=NULL|t-lchild!=NULLt-rchild=NULL) return(onechild(t-lchild)+onechild(t-rc

35、hild)+1); else num1=onechild(t-lchild); num2=onechild(t-rchild); return(num1+num2); int sum(NODE _t) /统计出二叉树中所有结点数 if(t=NULL) return(0); else return(sum(t-lchild)+sum(t-rchild)+1); int leaf(NODE _t) /统计出二叉树中叶子结点数 if(t=NULL) return(0); else if(t-lchild=NULLt-rchild=NULL) return(leaf(t-lchild)+leaf(t-

36、rchild)+1); else return(leaf(t-lchild)+leaf(t-rchild); void preorder1(NODE _root) /非递归二叉树前序编历 NODE _p,_s100,_q; /q为p的双亲结点 int =0; /为栈顶指针 p=root;q=p; while(p!=NULL)|(0) while(p!=NULL) printf(“d “,p-data); s+=p; p=p-lchild; p=s-; p=p-rchild; void delk(NODE _root,char k) /删去并释放数据值为k的叶结点 NODE _p,_s100,_

37、q; /q为p的双亲结点 int =0; /为栈顶指针 if(_root)=NULL)return; if(_root)-lchild=NULL (_root)-rchild=NULL(_root)-data=k) _root=NULL;return; p=_root;q=p; while(p!=NULL)|(0) while(p!=NULL) if(p-lchild=NULLp-rchild=NULL p-data=k) if(q-lchild=p) q-lchild=NULL; else q-rchild=NULL; free(p); return; s+=p; q=p; p=p-lchi

38、ld; p=s-; q=p;p=p-rchild; void lev_traverse(NODE _T) /按层次从上到下,每层从右到左的顺序列出二叉树所有结点的数据信息 NODE _q100,_p; int head,tail; q0=T;head=0;tail=1; while(headdata); if(p-rchild!=NULL) qtail+=p-rchild; if(p-lchild!=NULL) qtail+=p-lchild; int depth(NODE _t) /求二叉树的深度 int num1,num2; if(t=NULL) return(0); if(t-lchil

39、d =NULLt-rchild =NULL) return(1); else num1=depth(t-lchild ); num2=depth(t-rchild ); if(num1num2) return(num1+1); else return(num2+1); int onechild3(NODE _root) /非递归统计出二叉树共有多少个度为1的结点 NODE _p,_s100; int =0,num=0; /为栈顶指针 p=root; while(p!=NULL)|(0) while(p!=NULL) if(p-lchild!=NULLp-rchild=NULL |p-lchil

40、d=NULLp-rchild!=NULL) num+; s+=p; p=p-lchild; p=s-; p=p-rchild; return num; int like(NODE _t1,NODE _t2) /判定两颗二叉树是否相似 int like1,like2; if(t1=t2t2=NULL) return(1); else if(t1=NULL t2!=NULL|t1!=NULLt2=NULL) return(0); else like1=like(t1-lchild,t2-lchild); like2=like(t1-rchild ,t2-rchild ); return(like1

41、like2); char a100; /数组顺序存储二叉树 void change(NODE _t,int i) /将二叉树的链接存储转换为顺序存储 if(t!=NULL) ai=t-data; change(t-lchild,2_i); change(t-rchild,2_i+1); int plete(NODE _t) /判断二叉树是否为完全二叉树 int i,flag=0; change(t,1); for(i=1;iadjlisti.verte_;/访问vi for(p=G-adjlisti.firstedge;p;p=p-ne_t) /依次搜索vi的邻接点vj(不妨设p-adjve_

42、=j) if(!visitedp-adjve_)/若vj没有访问过 EnQueue(Q,p-adjve_);/vj入队 /endofwhile /BFS 3.试以邻接表和邻接矩阵为存储结构，分别写出基于DFS和BFS遍历的算法来判别顶点vi和vj(ij)之间是否有路径。4.试分别写出求DFS和BFS生成树(或生成森林)的算法，要求打印出所有的树边。5.写一算法求连通分量的个数并输出各连通分量的顶点集。6.设图中各边的权值都相等，试以邻接矩阵和邻接表为存储结构，分别写出算法：(1)求顶点vi到顶点vj(ij)的最短路径 (2)求点vi到其余各顶点的最短路径 要求输出路径上的所有顶点(提示：利用BFS遍历的思想) 7.以邻接表为存储结构，写一个基于DFS遍历策略的算法，求图中通过某顶点vk的简单回路(若存在)。8.写一算法求有向图的所有根(若存在)，分析p 算法的时间复杂度。第八章 排 序 一、选择题 1.在所有排序方法中，关键字比较的次数与记录得初始排列次序无关的是（ ）A希尔排序 B起泡排序 C插入排序 D选择排序 2.设有1000个无序的元素,希望用最快的速度挑选出其中前10个最大的元素,最好（ ）排序法。A起泡排序 B快速排序 C堆排序 D基数排序 3