复习题库答案

1、数据结构习题习题一一、选择题1、算法分析的两个主要方面是： （ B ） A正确性和简明性 B时间复杂度和空间复杂度C数据复杂性和程序复杂性D可读性和文档性2、在数据结构中，从逻辑上可以把数据结构分成（C）。 A动态结构和静态结构 B紧凑结构和非紧凑结构 C线性结构和非线性结构 D逻辑结构和存储结构3、计算机算法具备输入、输出和（C ）等5个特性：A有穷性、确定性和稳定性B可行性、可移植性和可扩充性 C有穷性、确定性和可行性D易读性、稳定性和安全性4、算法分析的目的是（C）。 A找出算法的合理性 B研究算法的输人与输出关系 C分析算法的有效性以求改进 D分析算法的易懂性二、填空题1、数据结构是一

2、门研究非数值计算的程序设计问题中计算机的 操作对象 以及它们之间的 关系 和运算等的学科。 2、线性结构中元素之间存在一对一 的关系，树形结构中元素之间存在一对多 的关系，图形结构中元素之间存在多对多 的关系。3、_数据项_是数据不可分割的最小单元，是具有独立含义的最小标识单位。例如构成一个数据元素的字段、域、属性等都可称之为_数据项_。4、数据的_存储结构_指数据元素及其关系在计算机存储器内的表示。存储结构_是逻辑结构在计算机里的实现，也称之为映像。5、所谓算法（Algorithm）是对特定问题求解方法和步骤的一种描述，它是指令的一组_有限序列_，其中每个指令表示一个或多个操作。 三、问答题

3、 1、用大O形式写出下面算法的时间复杂度： i0； s=0； while(sn） i+; s+=i; O（n） 2、写出以下算法的时间复杂度： for（i0; im; i）for（j0 ; jt; j） cij=0；for（i=0；im；i） for（j=o; j<t; j+） for（k=0；kn；k） cijaik*bkj; O(m×n×t)习题二一、选择题 1在一个长度为n的顺序表中删除第i个元素（0i<n）时，需要向前移动(A )个元素。 An-i Bn-i+1 Cn-i+1 Di+12从一个具有n个元素的线性表中查找其值等于x的结点时，在查找成功的情况

4、下，需平均比较( D )个元素结点。 An/2 Bn C(n-1)/2 D(n +1)/23若某表最常用的操作是在最后一个结点之后插入一个结点或删除最后一个结点，则下列存储方式最节省运算时间的是（A ）：A带头结点的双循环链表B双链表C给出表头指针的单循环链表D单链表4如果最常用的操作是取第i个结点及其前驱结点，那么下列存储方式最节省时间的是（C）：A单链表B单循环链表C顺序表D双链表5若某线性表最常用的操作是在最后一个结点之后插入一个结点或者删除最后一个结点，则下列存储方式最节省运算时间的是：（A ）A仅有尾指针的单循环链表B双链表C仅有头结点的单循环链表D单链表6线性表是(A )。 A一个

5、有限序列，可以为空 B一个有限序列，不可以为空 C一个无限序列，可以为空 D一个无限序列，不可以为空7在一个长度为n的顺序表中，向第i个元素（0一1n1）之前捕人一个新元素时，需要向后移动(B )个元素。 An-i Bn-i1 Cni1 Di18一个顺序存储线性表的第一个元素的存储地址是90，每个元素的长度是2，则第6个元素的存储地址是（B）。 A98 B100 C102 D1069. 在以下叙述中，正确的是：（D）A线性表的线性存储结构优于链式存储结构B栈的操作方式是先进先出C队列的操作方式是先进后出D二维数组是其数据元素为线性表的线性表二、填空题1线性表是具有n个数据元素的有限序列。2在单

6、链表中，要删除某一个指定的结点，必须找到该结点的 直接前趋 结点。3向一个长度为n的顺序表中的第i个数据元素（1in）之前插入一个元素时，需要向后移动 n-i+1 个数据元素。4在双向链表中，每个结点都具有两个指针域，一个指向直接前趋，另一个指向直接后继 。5线性表中有且仅有一个开始结点，表中有且仅有一个终端结点，除开始结点外，其他每个元素有巨仅有一个直接前趋_，除终端结点外，其他每个元素有且仅有一个直接后继_。6线性表的链式存储结构的每一个结点（Node）需要包括两个部分：一部分用来存放元素的数据信息，称为结点的数据域；另一部分用来存放元素的指向直接后继元素的指针(即直接后继元素的地址信息)

7、，称为指针域_或链域_。7写出带头结点的双向循环链表L为空表的条件(L=L->Next) && (L=L->Prior)。三、问答题1对链表设置头结点的作用是什么？（至少说出两条好处）由于开始结点的位置被存放在头结点的指针域中，所以在链表的第一个位置上的操作就和在表的其他位置上操作一致，无需进行特殊处理。 无论链表是否为空，其头指针是指向头结点的非空指针，因此空表和非空表的处理也就一致了。2在单链表、双链表中，如果仅知道指针p指向某结点，不知道头指针，能否将结点*p从相应的链表中删去？（不能）3如果频繁地对一个线性表进行插入和删除操作，那么该线性表应该采用何种存储结

8、构？为什么？（采取链式存储结构）顺序存储：插入或删除运算不方便，除表尾的位置外，在表的其它位置上进行插入或删除操作都必须移动大量结点，其效率较低；由于顺序表要求占用连续的存储空间，存储分配只能预先进行（静态分配），因此当表长变化较大时，难以确定合适的存储规模。若按可能达到的最大长度预先分配空间，则可能造成一部分空间长期闲置而得不到充分利用；若事先对表长估计不足，则插入操作可能使表长超过预先分配的存储空间而造成溢出。四、程序设计题1有一个带头结点的单链表（不同结点的数据域值可能相同），其头指针为head，编写一个函数计算数据域值为x的结点个数。int count_list(linklist *h

9、ead )/*在带头结点的单链表中计算所有数据域为x的结点的个数*/linklist *p;int n;p=head->next; /*p指向链表的第一个结点*/n=0;while (p!=NULL)if (p->data=x)n+;p=p->next;return(n);/*返回结点个数*/ /*count_list*/2设计一个算法，删除单链表L中值为x的结点的直接前驱结点。DeleteNode( Node* L, int x) Node* p,q,r; p = q = r = L; while(p->next ! = NULL) p = p ->next;

10、if(p->data = x) break; r = q; q = p; delete q; r->next = p; 3设计一个算法，将一个不带头结点的单链表L（至少有一个结点）逆置，即最后一个结点变成第一个结点，原来倒数第二个结点变成第二个结点，如此等等。void reverse_list( linklist * head )/*逆置带头结点的单链表*/linklist *s, *p;p=head->next;/*p指向线性表的第一个元素*/head->next=NULL; /*初始空表*/while ( p != NULL ) s=p;p=p->next;s

11、->next=head->next;head->next=s; /*将s结点插入逆表*/ /*reverse_list*/4在一个带头结点的单链表中，头指针为head，它的数据域的类型为整型，而且按由小到大的顺序排列，编写一个算法insertxlist（），在该链表中插人值为x的元素，并使该链表仍然有序。linklist *insertx_list(linklist *head, int x) /*在带头结点的单链表中插入值为x的元素，使该链表仍然有序*/linklist *s, *p, *q;s=(linklist *)malloc(sizeof(linklist); /*

12、建立数据域为x的结点*/s->data=x;s->next=NULL;if (head->next=NULL | x<head->next->data ) /*若单链表为空或x小于链表第一个结点的数据域*/ s->next=head->next;head->next=s;elseq=head->next;p=q->next;while( p != NULL && x>p->data )q=p;p=p->next;s->next=p;q->next=s; /*if*/ /*insert

13、x_list习题三一、选择题 l一个栈的序列是：a，b，c，d，e，则栈的不可能输出的序列是（C）。Aa，b，c，d，e Bd，e，c，b，a Cd，c，e，a，b De，d，c，b，a2判定一个栈S（最多元素为MaxSize）为栈满的条件是：（ D ）AStop!= -1 BStop=-1CStop=MaxSize-1DStop!=MaxSize-13若一进栈序列为1，2，3，n，其出栈序列为P1,P2,P3,Pn，如果Pn=n,则Pi （1i<n）的值为：（ A ）AiBn-i+1C不确定Dn-i4在一个链队中，假设f和r分别为队头和队尾指针，则插入s所指结点的运算是（A）Ar-&g

14、t;next=s；r=s；Br->next=s；f=s；Cs->next=r；r=s； Ds->next=f；f=s；5若用一个大小为8的一维数组来实现循环队列，且当前front和rear的值分别为4和1，当从队列中删除一个元素，再加入两个元素后，front和rear的值分别是（B）：A3和5B5和3C2和6 D6和26判断一个循环队列Q（最多元素为MaxSize）为空的条件是：（A ）AQ->front=Q->rear BQ->front=（Q->rear +1）%MaxSizeCQ->front!=Q->rearDQ->front

15、!=（Q->rear +1）%MaxSize 7向一个带头结点、栈顶指针为top的链栈中插人一个*S结点的时候，应当执行语句（ C ）。 Atop->next=S； BS->next=top；top=S； CS->next=top->next；top->next=S； DS->next=top；top=S->next；8在一个链队列中，假定front和rear分别为头指针和尾指针，则插入一个结点*S的操作是（ C ）。 Afrontfront->next BS->next=rear；rear=S Crear->next=S；re

16、ar=S DS->next=front；frontS9栈与队列都是（C ）。 A链式存储的线性结构 B链式存储的非线性结构 C限制存取点的线性结构 D限制存取点的非线性结构10若进栈序列为l，2，3，4，则（ C ）不可能是一个出栈序列。 A3，2，4，1 Bl，2，3，4 C4，2，3，1 D4，3，2，l11在解决计算机主机与打印机之间速度不匹配问题时通常设置一个打印数据缓冲区，主机将要输出的数据依次写人该缓冲区，而打印机则从该缓冲区中取走数据打印。该缓冲区应该是一个（ B ）结构。 A堆栈 B队列 C数组 D线性表二、填空题 1栈和队列的共同点是都是限制存取点的线性结构。2通常元素

17、进栈的操作是先进后出或后进先出 。3栈（stack）是限定在表尾 一端进行插人或删除操作的线性表。在栈中，允许插人和删除操作的一端称为栈顶_，而另一端称为栈底_。不含元素的栈称为_空栈_。4队列（Queue）也是一种特殊的线性表_，但它与栈不同，队列中所有的插人均限定在表的一端进行，而所有的删除则限定在表的另一端进行。允许插人的一端称为队尾_，允许删除的一端称为队头_。5队列中允许进行删除的一端称为队头_；允许进行插入的一端称为_队尾_。三、问答题1设有一个数列的输入顺序为abcdef，若采用栈结构，并以J和C分别表示进栈和出栈操作，试问下列输出序列是否是合法序列？如是，请用进栈和出栈操作表示

18、其合法序列。（1）能否得到输出顺序为cbefda的序列？J(a),J(b),J(c),C( ),C( ),J(d),J(e),C( ),J(f),C( ),C( ),C( )（2）能否得到输出顺序为aedfbc154623的序列？不能2设输入元素为4、5、6、B、A，入栈次序为456BA，元素经过栈后到达输出序列，当所有元素均到达输出序列后，有哪些序列可以作为高级语言的变量名？3假设Q010是一个线性队列，初始状态为front=rear=0，画出做完下列操作后队列的头尾指针的状态变化情况，若不能入队，请指出其元素，并说明理由。（1）d，e，b，g，h入队（2）d，e出队（3）i，j，k，l，m

19、入队（4）b 出队（5）n，o，p入队4设有4个元素A、B、C和D进栈，给出它们所有可能的出栈秩序。14种A、B、C、D A、B、D、C A、C、B、D A、C、D、B A、D、C、BB、A、C、D B、A、D、C B、C、A、D B、C、D、A B、D、C、AC、B、A、D C、B、D、A C、D、B、A D、C、B、A四、程序设计题1假设表达式中有三种括号：圆括号“（）”、方括号“ ”和花括号“ ”用C语言编写程序判断读人的表达式中不同括号是否正确配对，假定读人的表达式以”#”结束。#include "stdio.h"#include "stdlib.h&qu

20、ot;#define FALSE 0#define TRUE 1#define LEN sizeof( struct node )struct nodechar data;struct node *next;typedef struct node *stack;void push_stack(stack *, char );int pop_stack(stack *);void main()stack s;int valid=TRUE;char ch,symble;symble=getchar();s=NULL;push_stack(&s, '#');while (sy

21、mble != '#' ) && (valid =TRUE) )if ( symble !='(' && symble !=')' && symble != '' && symble != '' && symble !='' && symble != '' )symble=getchar();else if (symble='(' | symble='' |

22、 symble='' )push_stack(&s, symble );symble=getchar();else if ( s=NULL )valid=FALSE;elsech=pop_stack(&s);if ( (ch='(' && symble=')') | (ch='' && symble='') | ch=('' && symble='') )valid=TRUE;symble=getchar();elsev

23、alid=FALSE;if ( valid = TRUE )printf(" The string is valid. n");elseprintf("The string is valid. n");void push_stack( stack *topptr, char ch )stack newptr;newptr=(struct node * ) malloc( LEN );newptr->data=ch;newptr->next=*topptr;*topptr=newptr;int pop_stack( stack topptr )

24、stack tempptr;char popvalue;if (topptr!=NULL )tempptr=topptr;popvalue=topptr->data;topptr=topptr->next;free( tempptr );return popvalue;else return 0;习题四一、选择项4设有两个串 S2，S1，那么求串S2在S1 中首次出现的位置的运算称为：（ C ）A求子串B求串长C模式匹配D串连接4设有串S=Computer，则其子串的数目是（ B ）。 A36 B37 C8 D94下列是C语言中“ASDF567HJKL”子串的是：（ C ）AASD

25、FBDF56C“F567HJ”D“DFHJ”5空串与空格串（ B ）。 A相同 B不相同 C可能相同 D无法确定二、境空题1串是由零个或多个字符组成的有限序列。通常记作：s“c1，c2，cn”(n=>0)，其中，S称为串名_；串中的Ci（1<=i<=n）可以是字母、数字 字格或其他字符。用双引号括起来的部分是串值_即串S的内容。2串中字符的个数称为串的长度_。3不含有任何字符的串称为空串_，它的长度为_0_。4由一个或多个空格构成的串称为空白串_，它的长度为所含空格的个数_。5串中任意多个连续字符组成的子序列称为该串的字串_；包含字串_的串称为主串。三、问答题1、现有串s1=

26、ABCD123，s2=abcde，假设函数con(x,y)返回x和y串的连接串，函数subs(s,i,j) 返回串s的从序号i的字符开始的j个字符组成的子串，函数len(s)返回串s的长度，求：（1）L1=subs(s1,2,len(s2) ( BCD12）（2）L2=subs(s1,len(s2),2) ( 12)(3)con(L1,L2) (ABCD123abcde)四、程序设计题l编写算法实现将窜S1中的第 i个字符到第 j个字符之间的字符(不包括第 i个字符和第j个字符)之间的字符用串S2替换。假设串的存储结构为： define MAXSIZE 81 struct string int

27、 len； char chMAXSIZE； stringtype；void replace (stringtype s1, int i, int j, stringtype s2)stringtype s100;int h,k;if ( i<=h && i<s1.len && j<s1.len )for (h=1; h<=i; h+ )s.chh=s1.chh;/*把s1的前i个字符赋值给s*/s.len=i;h=1;while(h<s2.len)/*连接串s2*/s.chs.len+h=s2.chh;h+;s.len=s.len+

28、s2.len;for ( k=s.len+1; h=j; h<=s1.len; h+,k+ )s.chk=s1.chh; /*将s1串中从第j个字符开始到结束的字符连接到s串*/s.len=k;s.chs.len='0'return(s);习题五一、选择题 l数组常用的两种基本操作是（ D ）。A建立与查找 B删除与查找 C插人与索引 D查找与修改2对稀疏矩阵进行压缩存储，常用的两种方法是（ B ）。A二元组和散列表 B三元组和十字铸表 C三角矩阵和对角矩阵 D对角矩阵和十字链表3数组A中，每个数据元素的长度为2个字节，行下标m从1到10，列下标n从1到8，从首地址SA开

29、始连续存放在存储器内，存放该数组至少需要的单元数是：（D ）A20B80C240D1604数组A中，每个数据元素的长度为3个字节，行下标m从1到8，列下标n从1到10，从首地址SA开始连续存放在存储器内，该数组按行存储时，元素A83的起始地址是：（D） ASA+222BSA+141CSA+44DSA+2195若广义表L满足Head（L）= Tail（L），则广义表L为：（ A ）A（）B（）C（），（）D（），（），（）6广义表(a)的表头是（ C ）。 A（ ） Ba C（a） D（a）7广义表（a）的表尾是（ A ）。 A（） Ba C（a） D（a）8广义表（a），a）的表头是（ C ）

30、。 A（ ） Ba C（a） D（a）9广义表（a），a）的表尾是（ C ）。 A( ) Ba C（a） D（a）10广义表（a，b，c）的表头是（ A ）。 Aa B（a） Ca，b D（a，b）11广义表（a，b，c）的表尾是（ B ）。 Ab，c B（b，c） ab，c D（a，b，c）二、填空题9 head（），（）是 （） ，tail（），（）是 （） ，表的长度是2 。10 head（(a)，(b),c)，(d)）是 （a） ，tail（(a)，(b),c)，(d)）是(b),c),(d) 。11现有广义表L=（(a)，(b),c)，d，e,(i,j),k)），则该广义表的长度是

31、5 ，深度是 3 。1数组（array）是n（n1）个相同类型数据的有序组合，数组中的数据是按顺序存储在一块_地址连续_的存储单元中。2数组中的每一个数据通常称为数组元素_，_数组元素_用下标区分，其中下标的个数由数组的维数决定。3广义表是n（n>=0）个元素的序列。记作：A（a1，a2，an），其中，A是广义表的名称，n是它的长度_，当n=0的时候称为空表_。4广义表的深度一般定义为广义表元素最大的层数_，或者说是广义表括号的层数_。利用递归的定义，广义表的深度就是所有子表中最大深度加1_。三、问答题1现有一个稀疏矩阵如下图所示，写出其对应的三元组表示，并求出其转置矩阵的三元组表示。（

32、1,2,2），（2，3，-3），（3,1,1），（3,4,4）（1,3,1），（2,1,2）,(3,2,-3),(4,3,4)）2写一个创建稀疏矩阵相应三元组的算法。#define MAXSIZE 1000 /*假设非零元个数的最大值是1000*/typedef struct int i, j;elemtype v;triple;typedef structtriple dataMAXSIZE+1; /*data0用于存放稀疏矩阵行，列和非零元个数*/int mu, nu, tu; /*稀疏矩阵行、列和非零元的个数*/ spmatrix;spmatrix a;void CreatTripleT

33、able (int array_aMN,spmatrix a)/*array_a是一个稀疏矩阵,a是产生的相对应的三元组存储*/int i,j,k=1;for (i=0;i<M;i+) /*按行优先顺序扫描array_a的元素,不为0者存入B中*/for (j=0;j<N;j+)if (array_aij!=0)a.datak.i=i;a.datak.j=j;a.datak.v = array_aij; k+;a.data00=M; a.data01=N;a.data02=k-1;/*存入非0元素个数*/ 四、程序设计题1假设三元组元素值为整型，写一个查找三元组元素值为n的算法。习

34、题六一、选择题1设高度为h的二叉树上只有度为0和度为2的结点，则此类二叉树中所包含节点数至少有：（ D ）A2hB2h+1 Ch+1 D2h-12现有一二叉树，若其先序遍历序列为ABCDE，中序遍历序列为CBDAE，那么其后序遍历序列为：（ D ）ABDAECBEDCBACDABECDCDBEA3在线索化二叉树中，t所指结点没有左子树的充要条件是：（ D ）At->left=NULLBt->left=0Ct->ltag=1 Dt->left=NULL且 t->ltag=14设深度为h的二叉树上只有叶子结点和同时具有左右子树的结点，则此类二叉树中所包含的结点数目至少

35、为（ D ）。 A2h B2h C2h1 D2h-l5二叉村第k层上最多有（ C ）个结点。 A2k B2k-1 C2k-1 D2k-16二叉树的深度为k，则二叉树最多有（ D ）个结点。 A2k B2k-1 C2k-1 D2k -17设某一二叉树先序遍历为abdec，中序遍历为dbeac，则该二叉树后序遍历的顺序是（ C ）。 Aabdec Bdebac Cdebca Dabedc8设某一二叉树中序遍历为badce，后序遍历为bdeca，则该三叉树先序遍历的顺序是（D ）。 Aadbec Bdecab Cdebac Dabode9N个结点的线索二叉树中，线索的数目是（B ）。 AN-1 BN

36、1 C2N D2N110将一棵树T转换为一棵二叉树T2，则T的先序遍历是T2的（ A ）。A先序 B中序 C后序 D无法确定11将一棵树T转换为一棵二叉树T2，则T的后序遍历是T2的（B ）。A先序 B中序 C后序 D无法碉定12 设一棵二叉树度2的结点数是7，度为1的结点数是6，则叶子结点数是（C ）。A6 B7 C8 D913一棵非空的二叉树，先序遍历与后序遍历正好相反，则该二叉树满足（ C ）。 A无左孩子 B无右孩子 C只有一个叶子结点 D任意二叉树 14线索二叉树是一种（ D ）。 A逻辑结构 B线性结构 C逻辑和线性结构 D物理结构 15权值为l，2，6，8的四个结点构成的哈夫曼树

37、的带权路径长度是（ A ）。 A29 B31 C17 D20二、填空题 1树(Tree)是n(n0)个结点的_有限_集。 2深度为5的二叉树至多有31 个结点。3树中任意结点允许有零个或多个孩子结点，除根结点以外,其余结点都有 双亲结点。4在一棵二叉树中，度为零的结点个数为n0，度为2的结点个数为n2,那么n0=n2+1 。 5结点的度是指结点所拥有的子树的数目_。 6一个结点的子树中的任一结点都称为该结点的子孙结点_。 7从根到该结点所经分支上的所有结点称为该结点的祖先结点_。 8具有同一双亲_的结点互称为兄弟结点，简称为兄弟。9从根结点开始定义，根为_第一_层，根的孩子为_第二_层，依次往

38、下类推，若某结点在第k层，则其子树的根就在_第k+1_层。 10如果树中各结点的各子树无排列顺序，即可以互换位置，则称为该树为无序树 11二又树（Binary Tree）是结点的有限集合，这个集合或者是空，或者是由一个根结点和两棵互不相交_的称为_左子树_和_右子树_的二叉树构成。 12二叉树第i层上最多有_2*i-1_个结点。 13深度为k的二又树最多有_个结点(kl)。 14在任意二叉树中，叶子结点的数目(即度为0的结点数)等于度为2的结点数加1_。15一棵深度为k且具有2k-1个结点的二叉树称为满二叉树 ，这类二叉树的特点是，二叉树中每一层结点的个数都是_最大结点的个数。16_完全二叉树

39、是那种在一棵二叉树中，除最后一层外，若其余层都是满的，并且最后一层或者是满的，或者所缺少的结点都在右边。 17具有n个结点的完全二叉树的深度是_。 18先序遍历二叉树的操作定义为：若二叉树为空，则为空操作；否则进行如下操作：访问二叉树根结点_；先序遍历二叉树左子树_；先序遍历二叉树_右子树_。 19中序遍历二叉树的操作定义为：若二叉树为空，则为空操作；否则进行如下操作：中序遍历二叉树_左子树_；访问二又树_根结点_；中序遍历二又树_右子树_。 20后序遍历二叉树的操作定义为：若二叉树为空，则为空操作；否则进行如下操作：后序遍历二叉树_左子树_；后序遍历二叉树_右子树_；访问二叉树_根结点_。

40、21线索二叉树（Threaded Binary Tree）是充分利用二义链表的 n+1个空的指针域作为线索来标志每一个结点的前驱_和_后继_信息。当某个结点有左孩子的时候，使其_左指针域_指向其左孩子，无左孩子的时候，使其左指针域指向该结点的直接前驱结点_；当某个结点有有孩子的时候，使其右指针域指向该结点的右孩子_，无右孩子的时候，使其有指针域指向该结点的直接后继结点_。 22线索二叉树的线索链表中，指向结点前驱和后继的指针称为线索_；加上线索的二叉树称为线索二叉树_；对二叉树以某种次序进行遍历使其成为线索二叉树的过程称为线索化_。 23哈夫曼树（Huffman Tree）又称最优二叉树 。它

41、是n个带权叶子结点构成的所有二叉树中，带权路径长度WPL_最小的二叉树_。 三、问答题1一棵树表达成如下形式：DA，B，C，D，E，F，G， H，I，J，K，L，M，N，OR=A，B，A，C，A，D，B，E，B，F，C，G，D，H，D，I，D，J，K，F，K，L，F，M，I，N，I，O其中D为结点集合，R为边的集合。请根据以上内容回答以下问题：(1) 画出这棵树。(2) 该树的根结点是哪一个？(3) 哪些是叶子结点？(4) F结点的双亲是谁？(5) F结点的祖先是哪些？(6) F结点的孩子是哪些？(7) F结点的兄弟是哪些？(8) F结点的堂兄弟是哪些？(9) F结点的度是多少？(10)F结点

42、的层次是多少？(11)D结点的子孙有哪些？(12) 以结点D为根的子树度是多少？(13) 以结点D为根的子树层是多少？(14) 该树的层是多少？(15) 该树的度是多少？2画出图6-1中树的二叉树表示形式。 （a） （b） （c） 图6-l3已知某二叉树的先序遍历的结果是：A，B，D，QC，E，H，L，I，K，M，F和J，它的中序遍历的结果是：QD，B，A，L，H，E，K，LM，C，F和J，请画出这棵二叉树，并且写出该二叉树后序通历的结果。4设A、B、C、D、E、F六个字母出现的概率分别为7,19,2,6,32,3，构建哈夫曼树（请按左子树根结点的权小于等于右子树根结点的权的次序构造），计算出

43、带权路径长度WPL，并设计每个字母的哈夫曼编码5假设一棵二叉树的后序序列为DCEGBFHKJIA，中序序列为DCBGEAHFIJK，请完成下列操作：（1）画出该二叉树；(2)写出该二叉树的先序遍历序列；（3）画出该二叉树的中序遍历线索二叉树。6假设一棵二叉树的先序序列为ABDGCEHLIKMFJ，中序序列为GDBALHEKIMCFJ，请完成下列操作。(1)画出该二叉树；(2)写出该二叉树的后序遍历序列；(3)画出该二叉树的中序遍历线索二叉树。7假设通讯电文中只用到A，B，C，D，E，F六个字母，它们在电文中出现的相对频率分别为：7，2，15，9，4，19，要求画出哈夫曼树（请按左子树根结点的权

44、小于等于右子树根结点的权的次序构造），并计算出带权路径长度WPL，试设计每个字母的哈夫曼编码。8有七个带权结点,其权值分别为2,6,7,1,5,9,13,试以它们为叶子结点构造一棵哈夫曼树（请按照每个结点的左子树根结点的权小于等于右子树根结点的权的次序构造）,并计算出带权路径长度WPL。9假设一棵哈夫曼树共有n0个叶子结点，试证明树中共有2no-l个结点。10假设通信用的报文由9个字母A、B、C、D、E、F、G、H和I构成，它们出现的频率分别是：10、20、5、15、8、2、3、7和30。请用这9个字母出现得频率作为权值求：（l）设计一棵哈夫曼树。（2）计算其带权路径长度WPL值。（3）写出每

45、个字符的哈夫曼编码。四、程序设计题 1. 自己设计一棵二叉树，编写一个完整的程序，输出该二叉树的先序、中序和后序序列。（程序中应包括二叉树的生成函数，先序、中序、后序遍历函数）。2已知一棵二叉树的先序遍历序列和中序遍历序列，请写出根据二又树先序遍历序列和中序遍历序列构造一棵二叉树的算法。习题七一、选择题 1在一个无向图G中，所有顶点的度数之和等于所有边数之和的（ C ）倍。 Al/2 B1 C2 D42对某个无向图的邻接矩阵来说：（A ）A第i行上的非零元素的个数和第i列上的非零元素的个数一定相等B矩阵中的非零元素的个数等于图中的边数C第i行上、第i列上非零元素的总数等于顶点Vi的度数D矩阵中

46、非全零行的行数等于图中的顶点数3采用邻接表存储的图的深度优先遍历算法类似于二叉树的： （ A ）A先序遍历 B中序遍历 C后序遍历 D按层遍历4在一个具有n个顶点的无向图中，要连通全部顶点至少需要 条边： （ A ）An-1BnCn+1Dn/25在一个有向图中，所有顶点的入度之和等于所有顶点的出度之和的（B ）倍。 Al/2 B1 C2 D4 6一个具有n个顶点的无向图包含（ C ）条边。 An Bn1 Cn-1 Dn/2 7一个具有n个顶点的无向完全图包含（ C ）条边。 An(n-l) Bn(n+l) Cn(n-l)/2 Dn(n-l)/2 8. 一个具有n个顶点的有向完全图包含（ A ）

47、条边。 An(n-1) Bn(n+l) Cn(n-l)/2 Dn(n+l)/2 9无向图的邻接矩阵是一个（ A ）。 A对称矩阵 B零矩阵 C上三角矩阵 D对角矩阵二、填空题1在图中，任何两个数据元素之间都可能存在关系，因此图的数据元素之间是多对多的关系。2在有n个顶点的有向图中，至多有 N(N-1) 条边。3具有10个顶点的无向图，边的总数最多为 45 。4在一个具有n个顶点的无向图中，要连通全部顶点至少需要 n-1 条边。 5具有n (n-1)/2条边的无向图称为_无向完全图_，简称为完全图_，其中n表示无向图中顶点的个数，n(n-1)/2是具有n个顶点无向图所拥有边的最大数目_。 6具有n个顶点的有向图，如果它同时具有n(n-1)条弧，则称该图为有向完全图_，其中n(n-1)是具有n个顶点有向图所拥有弧的最大数目_。 7 如果图中的边或弧带有权，则称这种图为网络_。8顶点v的度定义为_