习题一
一、选择题
1、数据结构是一门研究非数值计算的程序设计问题中的操作对象以及它们之间的（B）和运算的学科。
A．结构 B．关系 C．运算 D．算法 2、在数据结构中，从逻辑上可以把数据结构分成（C）。
A．动态结构和静态结构 B．紧凑结构和非紧凑结构 C．线性结构和非线性结构 D．逻辑结构和存储结构
3、线性表的逻辑顺序和存储顺序总是一致的，这种说法（B）。树形
A．正确 B．不正确 C．无法确定 D．以上答案都不对
4、算法分析的目的是（C）。
A．找出算法的合理性 B．研究算法的输人与输出关系 C．分析算法的有效性以求改进 D．分析算法的易懂性 二、填空题
1、__数据___是信息的载体，是对客观事物的符号表示，它能够被计算机识别、存储、加工和处理，___数据_____是对能够有效的输人到计算机中并且能够被计算机处理的符号的总称。例如，数学中所用到的整数和实数，文本编辑所用到的字符串等。
2、数据元素是数据的__基本单位_，有些情况下也称为元素、结点、顶点、记录等。
3、__数据项__是数据不可分割的最小单元，是具有独立含义的最小标识单位。例如构成一个数据元素的字段、域、属性等都可称之为__数据项_。
4、简而言之，数据结构是数据之间的__相互关系_，即数据的_组织关系_。 5、数据的逻辑结构是指数据之间的_逻辑关系_。逻辑结构是从_逻辑关系_上描述数据，它与具体存储无关，是独立于计算机的。因此逻辑结构可以看作是从具体问题抽象出来的_数学模型_。
6、数据的__存储结构_指数据元素及其关系在计算机存储器内的表示。__存储结构_是逻辑结构在计算机里的实现，也称之为映像。
7、_数据的运算__是指对数据施加的操作。它定义在数据的逻辑结构之上，每种逻辑结构都有一个__数据的运算___。常用的有：查找、排序、插人、删除、更新等操作。 8、数据逻辑结构可以分为四种基本的类型，_集合_结构中的元素除了仅仅只是同属于一个___集合__，不存在什么关系。
9、数据逻辑结构的四种基本类型中，_线性结构_中的元素是一种一对一的关系，这种结构的特征是：若结构是非空集，则有且只有一个开始结点和一个终端结点，并且所有结点最多只能有一个直接前驱和一个直接后继。
10、数据逻辑结构的四种基本类型中，__树型结构_中的元素是一种一对多的关系。 11、图型结构或图状结构是一种__多对多__的关系。在这种逻辑结构中，所有结点均可以有多个前驱和多个后继。
12、有时也可将树型结构、集合和图型结构称为__非线性结构_，这样数据的逻辑结构就可以分为_线性结构_和__非线性结构__两大类。 13、__顺序存储__方式是指逻辑上相邻的结点被存储到物理上也相邻的存储单元中。这种存储结构只存储结点的数值，不存储结点之间的关系，结点之间的关系是通过存储单元的相邻关系隐含的表示出来的。
14、_链接存储_方式是种存储方法，不要求逻辑上相邻的结点在物理上也相邻，即数据元素可以存储在任意的位置上。
15、索引存储方式又可以分为_稠密索引_和__稀疏索引_。若每个结点在索引表中都有
1
一个索引项，则该种索引存储方式称为_稠密索引_；若一组结点在索引表中只对应一个索引项，则索引存储方式称为_稀疏索引_。在_稠密索引中，索引项的地址指示结点所在的位置，而_稀疏索引_中，索引项的地址指示一组结点的起始位置。
16、_散列存储_方式是利用结点关键字的值直接计算出该结点存储单元地址，然后将结点按某种方式存人该地址的一种方法。
17、所谓算法（Algorithm）是对特定问题求解方法和步骤的一种描述，它是指令的一组___有限序列__，其中每个指令表示一个或多个操作。
18、算法的_有穷 _性是指算法必须能够在执行有限个步骤之后结束，并且每个步骤都必须在有穷的时间内完成。
19、算法的__确定 _性是指算法中的每一个步骤必须是有明确定义的，不允许有模棱两可的解释，也不允许有多义性。并且，在任何条件下，算法只能有惟一的一条执行路径，即只要输人是相同的就只能得到__相同__的输出结果。 20、算法的__可行__性又称为算法的能行性，是指算法中描述的操作是可以通过已经实现的基本运算执行__有限__次来实现，即算法的___具体实现_应该能够被计算机执行。 21、判断一个算法的好坏主要以下几个标准：__正确性_、__可读性_、__健壮性_、__效率__。
22、算法分析是对一种算法所消耗的计算机资源的估算，其中包括计算机__运行时间_的长短和___所占据空间__的大小。
23、空间复杂度（SPace ComPlexity）也是度量一个算法好坏的标准，它所描述的是算法在运行过程中所占用__存储空间___的大小。 三、判断题
1、顺序存储方式只能用于存储线性结构。（×）树形 2、数据元素是数据的最小单位。（×）数据项
3、算法可以用不同的语言描述，如果用C语言或PASCAL语言等高级语言描述，则算法实际上就是程序了。（×）
4、数据结构是带有结构的数据元素的集合。（√）
5、数据的逻辑结构是指各元素之间的逻辑关系，是用户根据需要而建立的。（√） 6、数据结构、数据元素、数据项在计算机中的映像分别称为存储结构、结点、数据域。（√）
7、数据的物理结构是指数据在计算机中实际的存储形式。（√）
8、具有存取任一元素的时间相等这一特点的存储结构称为随机存取结构。（√） 四、综合题
1、用大O形式表示下面算法的时间复杂度： for（i=0；i＜m；i十十） for（j=0；j＜n；j＋＋）
A[i][j]=i*j； O（m×n） 2、写出下面算法的时间复杂度： i＝0； S=0 S=1 s=0；
S=1+2 while(s＜n）
S=1+2+3 ｛ i++;
........ s+=i;
S=1+2+3+.....+(m-1) ｝ O(n) m*(m-1)/2 2 3、写出以下算法的时间复杂度： for（i＝0; i＜m; i＋＋） for（j＝0 ; j＜t; j＋＋） c[i][j]=0； for（i=0；i＜m；i＋＋） for（j=o; j for（k=0；k＜n；k＋＋） c［i］［j］＋＝a［i］［k］*b[k][j]; O(m×n×t)。 4、写出下面算法的时间复杂度： i=1*(3^m-1) 3^m O(log3(n)) i=i*3; O（log3(n)） 5、求下面函数中各条语句的频度和算法的时间复杂度： prime（int n） ｛ int i＝2； while ((n％i）！=0＆＆i＜sqrt(n) ) i++; if（i＞sqrt(n) ) printf（”％d is a prime number.＼n”，n）； else printf（”％d is not a prime number.＼n”，n）；｝ O(n) 6、fact(n) { if(n<=1) return 1; else return (n*fact(n-1)); } O（n） 3 习题二 一、选择题 1．在一个长度为n的顺序表中删除第i个元素（0＜i 2．从一个具有n个元素的线性表中查找其值等于x的结点时，在查找成功的情况下，需平均比较( D )个元素结点。 A．n/2 B．n C．(n-1)/2 D．(n +1)/2 3．对一个具有n个元素的线性表，建立其单链表的时间复杂度为( A )。 A．O(n) B．O(1) C．O(n2） D．O（long2n） 4．线性表采用链式存储时，其地址( D )。 A． 必须是连续的 B．一定是不连续的 C．部分地址必须连续 D．连续与否均可以 5．在一个具有n个结点的有序单链表中插人一个新的结点，使得链表仍然有序，该算法的时间复杂度是(D )。 A．O（long2n） B．O（l） C．O（n2） D．O（n） 6．线性表是( A)。 A．一个有限序列，可以为空 B．一个有限序列，不可以为空 C．一个无限序列，可以为空 D．一个无限序列，不可以为空 7．在一个长度为n的顺序表中，向第i个元素（0 A．n-i B．n-i＋1 C．n－i－1 D．i＋1 8．如果某链表中最常用的操作是取第i个结点及其前驱，则采用( B )存储方式最节省时间。 A．单链表 B．双向链表 C．单循环链表 D．顺序表 9．一个顺序存储线性表的第一个元素的存储地址是90，每个元素的长度是2，则第6个元素的存储地址是（B）。 A．98 B．100 C．102 D．106 10．下列排序方法中，某一趟结束后未必能选出一个元素放在其最终位置上的是( C )。 A．堆排序 B．冒泡排序 C．直接插人排序 D．快速排序 11．对线性表进行二分查找时，要求线性表必须（C）。 A．以顺序方法存储 B．以链接方法存储 C．以顺序方法存储，且结点接关键字有序排列 D．以链接方法存储，且结点接关键字有序排列 12．在顺序存储的线性表（a1??an）中，删除任意一个结点所需移动结点的平均移动次数为( C ) (n（n+1）)/2*1/n A．n B．n／2 C．(n-1)/2 D．（n＋l）/2 13．在线性表的下列存储结构中，读取元素花费的时间最少的是（ D）。 A．单链表 B．双链表 C．循环链表 D．顺序表 14．若某链表中最常用的操作为在最后一个结点之后插入一个结点和删除最后一个结点，则采用（D）存储方式最节省时间。 A．双链表 B．单链表 C．单循环链表 D．带头结点的双循环链表 15.已知L是没有头结点的单链表的头指针，且p所指向的结点既不是第一个结点，也不是最后一个结点，试从下列提供的语句中选取出合适的语句序列。（将语句序号填入横线 4 中） (1)在p所指向结点之后插入s所指向的结点： 。 (2)在p所指向结点之前插入s所指向的结点： 。 (3)在单链表L首插入s所指向的结点： 。 (4)在单链表L后插入s所指向的结点： 。 提供的语句： A. p->next=s; H. q=p; B. p->next=p->next->next; I. while(p->next!=q) p=p->next; C. p->next=s->next; J. while(p->next!=NULL) p=p->next; D. s->next=p->next; K. p=q; E. s->next=L; L. p=L; F. s->next=p; M. L=s; G. s->next=NULL; N. L=p; 二、填空题 1．线性表（Linear List）是最简单、最常用的一种数据结构。线性表中的元素存在着__一对一_的相互关系。 2．线性表中有且仅有一个开始结点，表中有且仅有一个终端结点，除开始结点外，其他每个元素有且仅有一个__直接前驱_，除终端结点外，其他每个元素有且仅有一个_直接后继_。 3．线性表是n（n>=0）个数据元素的__有限序列_。其中n为数据元素的个数，定义为线性表的__长度_。当n为零时的表称为__空表_。 4．所谓顺序表（Sequential LISt）是线性表的__顺序存储结构_，它是将线性表中的结点按其__逻辑顺序_依次存放在内存中一组连续的存储单元中，使线性表中相邻的结点存放在__地址相邻_的存储单元中。 5．单链表不要求逻辑上相邻的存储单元在物理上也一定要相邻。它是分配一些_任意__的存储单元来存储线性表中的数据元素，这些存储单元可以分散在内存中的__任意_的位置上，它们在物理上可以是一片连续的存储单元，也可以是__不连续__的。因此在表示线性表这种数据结构时，必须在存储线性表元素的同时，也存储线性表的 逻辑关系。 6．线性表的链式存储结构的每一个结点（Node）需要包括两个部分：一部分用来存放元素的数据信息，称为结点的_数据域_；另一部分用来存放元素的指向直接后继元素的指针(即直接后继元素的地址信息)，称为_指针域_或___链域__。 7．线性链表的逻辑关系是通过每个结点指针域中的指针来表示的。其逻辑顺序和物理存储顺序不再一致，而是一种__非顺序_存储结构，又称为__非顺序映像_。 8．如果将单链表最后一个结点的指针域改为存放链表中的头结点的地址值，这样就构成了__循环链表_。 9．为了能够快速地查找到线性表元素的直接前驱，可在每一个元素的结点中再增加一个指向其前驱的指针域，这样就构成了__双向链表_。 10．双向链表某结点的指针P，它所指向结点的后继的前驱与前驱的后继都是_p所指向的结点本身_。 11．在单链表中，删除指针P所指结点的后继结点的语句是__ P->next=p->next->next __。 12．在双循环链表中，删除指针P所指结点的语句序列是P->prior->next＝p->next及_ P->next->prior=P->prior _。 13．单链表是___线性表__的链接存储表示。 5 14．可以使用__双链表__表示树形结构。 15．向一个长度为n的向量的第i个元素(l≤i≤n+1）之前插人一个元素时，需向后移动__n-i+1__个元素。 16．删除一个长度为n的向量的第i个元素（l≤i≤n）时，需向前移动__n-i_个元素。 17．在单链表中，在指针P所指结点的后面插人一个结点S的语句序列是__ S->next=P->next; P->next=S __。 18．在双循环链表中，在指针P所指结点前插人指针S所指的结点，需执行语句_ p->prior->next=S; s->prior=p->prior;s->next=p;p->prior=s;_。 19．取出广义表A＝（（x，（a，b，c，d））中原子c的函数是__ L(tail(tail((L(tail(L(A))))))_。 20．在一个具有n个结点的有序单链表中插人一个新结点并使之仍然有序的时间复杂度为___ O(n)_。 21．写出带头结点的双向循环链表L为空表的条件__(L==L->Next) && (L==L->Prior)_。 22．线性表、栈和队列都是__线性__结构。 23．向栈中插人元素的操作是先移动栈__顶_针，再存人元素。 三、判断题 1．线性表采用链表存储时，结点和结点内部的存储空间可以是不连续的。（×） 2．在具有头结点的链式存储结构中，头指针指向链表中的第一个数据结点。(× ) 3．顺序存储的线性表不可以随机存取。（×） 4．单链表不是一种随机存储结构。（√） 5．顺序存储结构线性表的插入和删除运算所移动元素的个数与该元素的位置无关。(×) 6．顺序存储结构是动态存储结构，链式存储结构是静态存储结构。（×） 7．线性表的长度是线性表所占用的存储空间的大小。（×） 数组描述的链表叫静态链表 8．双循环链表中，任意一结点的后继指针均指向其逻辑后继。（×） 9．线性表的惟一存储形式是链表。（×） 四、综合题 1．编写一个将带头结点单链表逆置的算法。 void reverse_list( LinkList L) { /*逆置带头结点的单链表*/ LinkList s, p; p=L->next; /*p指向线性表的第一个元素*/ L->next=NULL; /*初始空表*/ while ( p != NULL ) { s=p; p=p->next; s->next=L->next; L->next=s; /*将s结点插入逆表*/ } } /*reverse_list*/ 2．ha和hb分别是两个按升序排列的、带头结点的单链表的头指针，设计一个算法， 6 把这两个单链表合并成一个按升序排列的单链表，并用hC指向它的头结点。 void mergelist(LinkList *La,LinkList *Lb,LinkList *Lc) { LinkList pa,pb,pc; pa=(*La)->next; pb=(*Lb)->next; *Lc= *La ,pc =*La; while (pa&&pb) if(pa->data<=pb->data) { pc->next=pa; pc=pa; pa=pa->next; } else { pc->next=pb; pc=pb; pb=pb->next; } pc->next=pa?pa:pb; free(*Lb); } 3．有一个带头结点的单链表，头指针为L，编写一个算法count．list（）计算所有数据域为X的结点的个数（不包括头结点）。 int count_list(LinkList L ) { /*在带头结点的单链表中计算所有数据域为x的结点的个数*/ LinkList p; int n; p=L->next; /*p指向链表的第一个结点*/ n=0; while (p!=NULL) { if (p->data==x) n++; p=p->next; } return(n); /*返回结点个数*/ } /*count_list*/ 4．在一个带头结点的单链表中，头指针为L，它的数据域的类型为整型，而且按由小到大的顺序排列，编写一个算法insertx＿list（），在该链表中插人值为x的元素，并使该链表仍然有序。 void insert_list(LinkList L,int x){ LinkList p,q,s; p=L->next; q=L; while(p&&x>p->data){q=p;p=p->next;} s=(LinkList)malloc(sizeof(Lnode)); s->data=x; s->next=p; q->next=s; } 7 5．在一个带头结点的单链表中，L为其头指针，p指向链表中的某一个结点，编写算法swapin．list（），实现p所指向的结点和p的后继结点相互交换。 int swapin_list(LinkList head, LinkList p) { /*在带头结点的单链表中，实现p所指向的结点和p的后继结点相互交换*/ LinkList q, r, s; q=p->next; /*q为p的后继*/ if (q !=NULL) /*若p有后继结点*/ { if (p==head) /*若p指向头结点*/ { head=head->next; s=head->next; head->next=p; p->next=s; } else /*p不指向头结点*/ { r=head; /*定位p所指向结点的前驱*/ while (r->next != p) r=r->next; r->next=q; /*交换p和q所指向的结点*/ p->next=q->next; q->next=p; } return OK; } else /*p不存在后继*/ return ERROR; }/*swapin_list*/ 6．有一个带头结点的单链表，所有元素值以非递减有序排列，L为其头指针，编写算法deldy．list（）将该链表中多余元素值相同的结点删除。 void deldy_list(LinkList head) { /*在带头结点的非递减有序单链表，将该链表中多余的元素值相同的结点删除*/ LinkList q; if (head->next!= NULL)/*判断链表是否为空*/ { p=head->next; while (p->next != NULL ) { if ( p->data != p->next->data ) p=p->next; 8 else { q=p->next;/*q指向p的后继*/ p->next=q->next; /*删除q所指向的结点*/ free(q); /*释放结点空间*/ } } /*while*/ } /*if*/ } /*deldy_list*/ 7．在带头结点的单链表中，设计算法dellistmaxmin，删除所有数据域大于min，而小于max的元素。 void dellist_maxmin(LinkList head, int min, int max ) { LinkList p, q; q=head; p=head->next; while(p!=NULL) /*结点不空*/ if ((p->data<=min) || (p->data>=max)) /*不满足删除条件*/ { q=p; p=p->next; } else /*满足删除条件*/ { q->next=p->next; free(p); p=q->next; } } /*dellist_maxmin*/ 8．设计一个将双链表逆置的算法invert．dbLinkList（），其中头指针为L，结点数据域为data，两个指针域分别为prior和next。 void invert_dblinklist(DLinkList head )//不带头结点的双向链表 { /*将head指向的双链表逆置*/ DLinkList p, q; p=head; while( p->next ) { q=p->next;. p->next=p->prior; p->prior=q; p=q; 9 } q=p; p->next=p->prior; p->next=NULL; head=q; } /*invert_dblinklist*/ 10 习题三 一、选择题 l．一个栈的序列是：a，b，c，d，e，则栈的不可能输出的序列是（C）。 A．a，b，c，d，e B．d，e，c，b，a C．d，c，e，a，b D．e，d，c，b，a 2．若一个栈的输人序列是1，2，3，?，n，输出序列的第一个元素是n，则第k个输出元素是（ C ）。 A．k B．n-k-1 C．n-k+1 D．不确定 3．判定一个栈S（最多有n个元素）为空的条件是（B ）。 A．S->top！＝0 B．S->top= =0 C．S->top!=n D．S->top= =n 4．判定一个栈S（最多有n个元素）为满的条件是（D）。 A．S->top!=0 B．S->top= =0 C．S->top!=n D．S->top= =n 5．向一个栈顶指针为top的链栈中插人一个*S结点的时候，应当执行语句（B）。 A．top->next=S； B．S->next=top；top=S； C．S->next＝top->next；top->next＝S；D．S->next＝top；top＝S->next； 6．向一个带头结点、栈顶指针为top的链栈中插人一个*S结点的时候，应当执行语句（C）。 A．top->next=S； B．S->next=top；top=S； C．S->next=top->next；top->next=S； D．S->next=top；top=S->next； 7．判定一个队列Q（最多有n个元素）为空的条件是（ C ）。 A．Q->rear-Q->front= =n B．Q->rear-Q->front+1= =n C．Q->rear = = Q->front D．Q->rear +1= = Q->front 8．判定一个队列Q（最多有n个元素）为满的条件是（A）。 A．Q->rear-Q->front= =n B．Q->rear-Q->front+1= =n C．Q->rear = = Q->front D．Q->rear +1= = Q->front 9．判定一个循环队列Q（最多有n个元素）为空的条件是（A）。 A．Q->rear = = Q->front B．Q->rear = = Q->front＋l C．Q->front= =(Q->rear +1)％n D．Q->front= =(Q->rear -1)％n 10．判定一个循环队列Q（最多有n个元素）为满的条件是（ C ）。 A．Q->rear = = Q->front B．Q->rear = = Q->front＋l C．Q->front= =(Q->rear +1)％n D．Q->front= =(Q->rear -1)％n 11．在一个链队列中，假定front和rear分别为头指针和尾指针，则插入一个结点*S的操作是（ C ）。 A．front＝front->next B．S->next=rear；rear=S C．rear->next=S；rear=S D．S->next=front；front＝S 12．在一个链队列中，假定front和rear分别为头指针和尾指针，删除一个结点的操作是（ A ）。 A．front=front->next B．rear=rear->next C．rear->next=front D．front->next＝rear 13．栈与队列都是（ C ）。 A．链式存储的线性结构 B．链式存储的非线性结构 C．限制存取点的线性结构 D．限制存取点的非线性结构 14．若进栈序列为l，2，3，4，则（ C）不可能是一个出栈序列。 A．3，2，4，1 B．l，2，3，4 C．4，2，3，1 D．4，3，2，l 15．在解决计算机主机与打印机之间速度不匹配问题时通常设置一个打印数据缓冲 11 区，主机将要输出的数据依次写人该缓冲区，而打印机则从该缓冲区中取走数据打印。该缓冲区应该是一个（ B ）结构。 A．堆栈 B．队列 C．数组 D．线性表 二、填空 1．栈（stack）是限定在__表尾_一端进行插人或删除操作的线性表。在栈中，允许插人和删除操作的一端称为__栈顶_，而另一端称为__栈底__。不含元素的栈称为_空栈__。 2．在栈的运算中，栈的插人操作称为__进栈_或__入栈_，栈的删除操作称为__退栈_或__出栈__。 3．根据栈的定义，每一次进栈的元素都在原__栈顶元素_之上，并成为新的__栈顶元素__；每一次出栈的元素总是当前的__栈顶元素_，因此最后进栈的元素总是__最后出栈__，所以栈也称为_后进先出_线性表，简称为__LIFO__表。 4．栈是一种操作受到限制的线性表，是一种特殊的线性表，因此栈也有_顺序_和__链式__两种存储结构，分别称为__顺序栈__和___链栈__。 5．当栈满的时候，再进行人栈操作就会产生___溢出_，这种情况的溢出称为__上溢_；当栈空的时候，如果再进行出栈操作，也会__溢出__，这种情况下的溢出称为__下溢___。 6．栈的链式存储结构简称为__链栈_，是一种___特殊的单链表__。 7．人们日常计算用到的表达式都被称为__中缀表达式__，这是由于这种算术表达式的运算符被置于两个操作数中间。 8．计算机中通常使用__后缀表达式_，这是一种将运算符置于两个操作数后面的算术表达式。这种表达式是由波兰科学家谢维奇提出的，因此又称为__逆波兰式__。 9．队列（Queue）也是一种__特殊的线性表_，但它与栈不同，队列中所有的插人均限定在表的一端进行，而所有的删除则限定在表的另一端进行。允许插人的一端称为_队尾_，允许删除的一端称为___队头__。 10．队列的特点是_先进先出_，因此队列又被称为___先进先出_．的线性表，或称为__FIFO__表。 11．队列的__顺序存储结构__又称为__数序队列_，是用一组地址连续的存储单元依次存放队列中的元素。 12．由于队列中的元素经常变化，对于队列的删除和插人分别在队头和队尾进行，因此需要设置两个指针分别指向_队头元素__和_队尾元素_，这两个指针又称为_队头指针__和__队尾指针__。 13．循环顺序队列（CircuLar Sequence Queue）经常简称为__循环队列_，它是将存储顺序队列的存储区域看成是一个首尾相连的一个环，即将队首和队尾元素连接起来形成一个环形表。首尾相连的状态是通过数学上的___取模运算__来实现的。 14．在算法或程序中，当一个函数直接调用自己或通过一系列语句间接调用自己的时候，则称这个函数为递归函数，也称为__自调用函数___。函数直接调用自己，则称为__直接递归调用_；当一个函数通过另一个函数来调用自己则称为___间接递归调用_。 15．在循环队列中规定：当Q->rear= =Q->front的时候循环队列为__空___， 当（Q->rear+1）％MAXSIZE＝front的时候循环队列为___满____。 16．用链表方式表示的队列称为___链队列___。 17．已知栈的输人序列为1，2，3，?，n，输出序列为a1，a2，?，an，符合a2= =n的输出序列共有___n-1_个_。 18．一个栈的输人序列是12345，则栈的输出序列为43512是__不可能__（填是否可能）。 19．一个栈的输人序列是12345，则栈的输出序列为12345是___可能的_（填是否可能）。 12 20．设sq[1．．maxsize]为一个顺序存储的栈，变量top指示栈顶元素的位置，则作入栈操作的条件是____top-1< maxsize 。 21．设sq[1．．maxsize]为一个顺序存储的栈，变量top指示栈顶元素的位置，如果把栈顶元素弹出并送到X中，则需执行语句___ x=sq[top]; top=top-1___。 22．栈的特性是___先进后出___。 23．对栈进行退栈时的操作是先移动___栈顶指针_，后 取出元素 。 24．设s[1．．max]为一个顺序存储的栈，变量top指示栈顶位置，栈为满的条件是_ top==max+1。 25．设链栈的栈顶指针为top（有头结点），则栈非空的条件是__top->next!=NULL__。 26．已知循环队列用数组data[1...n]存储元素值，用f，r分别作为头尾指针， 则当前元素个数为_(n+r-f）%n__。 27．在一个循环队列中，队首指针指向 队首元素。 28．队列中允许进行删除的一端称为___队头_。 29．链队列实际上是一个同时带有头指针和尾指针的单链表（1．．n），尾指针指向该单链表的第__n_个元素。 30．设双向链表链列为lq，lq的头指针为lq.Front，尾指针为lq.Rear，则队列为空的条件是_lq.Front==lq.Rear_。 31．从循环队列中删除一个元素，其操作是先取出一个元素，后移动___队头指针___。 32．队列中允许进行插入的一端称为_队尾__。 三、判断题 1．栈和队列都是限制存取点的线性结构。（ √） 2．不同的人栈和出栈组合可能得到相同输出序列。（ × ） 3．消除递归一定要用栈。（ × ） 4．循环队列是顺序存储结构。（ √ ） 5．循环队列不会产生溢出。（ × ） 6．循环队列满的时候rear= =front。（ × ） 7．在对链队列（带头结点）做出队操作时不会改变front指针的值。（√） 四、综合题 1．设有4个元素A、B、C和D进栈，给出它们所有可能的出栈秩序。 A、B、C、D A、B、D、C A、C、B、D A、C、D、B A、D、C、B B、A、C、D B、A、D、C B、C、A、D B、C、D、A B、D、C、A C、B、A、D C、B、D、A C、D、B、A D、C、B、A 2．输入n个10以内的数，每输入k（0＜=k＜=9），就把它插人到第k号队列中。最后 13 把10个队列中的非空队列按队列序号以从小到大的顺序串接成一条链，并输出该链中的所有元素。 3．假设用循环单链表实现循环队列，该队列只使用一个尾指针rear，其相应的存储结构和基本操作算法如下： (l) 初始化队列 initqueue (Q)：建立一个新的空队列 Q。 (2) 人队列enqueue (Q，x)：将元素 x插人到队列 Q中。 (3) 出队列delqueue (Q)：从队列Q中退出一个元素。 (4) 取队首元素getL (Q)：返回当前队首元素。 (5) 判断队列是否为空：emptyqueue (Q)。 (6) 显示队列中元素：dispqueue (Q)。 4．“回文”是指一个字符串从头读到尾和从尾读到头都一样。假设字符串是从输人设备一次一个字节的读人，并且读到字符“＃”的时候表示结束。请用栈和队列编写一个算法判断一个字符串是否回文。 5．假设表达式中有三种括号：圆括号“（）”、方括号“[ ]”和花括号“{ }”用C语言编写程序判断读人的表达式中不同括号是否正确配对，假定读人的表达式以”#”结束。 6．用C语言编写背包问题的算法。背包问题的描述是：假设有n件质量分别为w1，w2，?，wn的物品和一个最多能装载总质量是T的背包，问能否从这n件物品中选择若干件物品装人背包，并且使被选物品的总质量恰好等于背包所能装载的最大质量，即Wxl＋Wx2＋?Wxk＝T。若能，则背包问题有解，否则背包问题无解。 7．划分子集问题的求解。划分子集问题的实际例子很多，如：某个运动会设立n个比赛项目，每个运动员可以参加一到三个项目，考虑到同一运动员参加的项目不能够在同一时间内进行，则如何安排比赛日程才能使总的日程最短。又如：学校开设m科课程，不同的同学可能选修多门不同的课程，在学期末要进行考试，则如何安排这m科课程的考试才能使考试时间最短而又不冲突。 8．写出汉诺塔问题的递归和非递归算法。 汉诺塔问题描述为：有X、Y和Z三个柱子，n个大小不等且都能套进柱子的圆盘（编号为l、2、?、n），这n个圆盘已经按照自上至下、由小到大的顺序在其中的一根柱子X上，要求将这些圆盘按照如下规则由X柱子移动到Z柱子： (1) 每次只能移动柱子最上面的一个圆盘。 (2) 任何圆盘都不能放在比它小的圆盘之上。 (3) 圆盘只能在X、Y和Z三根柱子之上放置。 9．假设CQ[0…10]是一个环形队列，初始状态为front=rear=0，画出做完下列操作后队列的头尾指针的状态变化情况，若不能入队，请指出其元素，并说明理由。 (1) d,e,b,g,h入队 (2)d,e出队 (3)i,j,k,l,m入队 (4)b出队 (5) n,o,p入队 14 习题四 一、选择项 l．空串与空格串（B）。 A．相同 B．不相同 C．可能相同 D．无法确定 2．设有两个申S1与S2，求串S2在S1中首次出现位置的运算称作（ C ）。 A．连接 B．求子串 C．模式匹配 D．判子串 3．串与普通的线性表相比较，它的特殊性体现在（C）。 A．顺序的存储结构 B．链接的存储结构 C．数据元素是一个字符 D．数据元素可以任意 4．设有串S=‘Computer’，则其子串的数目是（ B ）。 (n *（n+1）/2+1) A．36 B．37 C．8 D．9 二、境空题 1．串是由零个或多个字符组成的__有限序列_。通常记作：s＝“c1，c2，?，cn”(n=>0)，其中，S称为__串名_；串中的Ci（1<=i<=n）可以是字母、数字 字格或其他字符。用双引号括起来的部分是_串值_．即串S的内容。 2．串中字符的个数称为串的__长度__。 3．不含有任何字符的串称为__空串_，它的长度为___零__。 4．由一个或多个空格构成的串称为__空格串__，它的长度为__空格的个数__。 5．串中任意多个连续字符组成的子序列称为该串的__子串__；包含_子串__的串称为主串。 6．字符在序列中的序号称为该字符在串中的__位置_。 7．两个字符串相等是指两个字符串的 值相等 ，也就是说这两个字符串不仅_长度相等_，而且对应位置上的字符也 相等 。 8．两个串的比较实际上是__ ASCII码_的比较。两个串从第一个位置上的字符开始进行比较，当第一次出现__ ASCII码__大的串为大，若比较过程中出现一个字符串结束的情况，则另一个串为__较大者__。 9．串的__顺序存储__就是把串所包含的字符序列，依次存人连续的存储单元中去。 10．有些计算机系统中为了充分利用存储空间，允许一个存储单元可以存放多个字 符，串的这种存储方式是一种___紧缩式存储结构__。 11．串的__非紧缩式存储结构__是以存储单元为存储单位，一个存储单元中只存放__一个字符_。在这种情况下，即使一个存储单元能存放多个字符，这时候也只存放___一个字符__。 12．串在非紧缩方式下，串长度的存储是隐式的，__串所占用的存储单元的个数_即串的长度。 13．一些计算机是以字节为存取单位，恰好一个字符占用一个字节，自然形成了每个存储单元存放__一个字符_的分配方式，这种方式就是一种_单字节存储方式_。这种方式一般不需要存放__串长_的存储单元，而需要以程序中各变量值所 不包含 的字符为结束符。 14．串的链式存储结构是将存储区域分成一系列大小相同的结点，每个结点有两个城：_ 数据 _域和___指针_域。其中___数据__域用于存放数据，__指针_域用于存放下一个结点的指针。 15．子串定位StrIndex (s，t)，也称为_模式匹配__，是返回串t在s主串中的位置。 三、判断回 1．子串是主串中字符构成的有限序列。（ × ） 2．KMP算法的最大特点是指示主串的指针不需要回溯。（ √ ） 15 3．串中的元素只能是字符。（ √ ） 4．串中的元素只可能是字母。（ × ） 5．串是一种特殊的线性表。（ √ ） 6．串中可以包含有空白字符。（ √ ） 7．串的长度不能为零。（ × ） 8．两个串相等必有串长度相同。（ √ ） 9．两个串相等则各位置上字符必须对应相等。（ √ ） 四、综合题 l．编写算法实现将窜S1中的第 i个字符到第 j个字符之间的字符(不包括第 i个字符和第j个字符)之间的字符用串S2替换。假设串的存储结构为： ＃define MAXSIZE 81 struct string{ int len； char ch［MAXSIZE］； ｝stringtype； 2．设计一个算法，测试一个串S是否回文（所谓回文是指从左面读起和从右面读起内容一样）。 3．写一个递归算法来实现字符的逆序存储，要求不另设存储空间。 4．一个仅由字母组成的字符串s，长度为n，其结构为单链表，每个结点的数据城只存放一个字母。设计一个算法，去掉字符串中所有值为X的字母。 16 习题五 一、选择题 l．数组常用的两种基本操作是（D）。 A．建立与查找 B．删除与查找 C．插人与索引 D．查找与修改 2．对稀疏矩阵进行压缩存储，常用的两种方法是（ B ）。 A．二元组和散列表 B．三元组和十字链表 C．三角矩阵和对角矩阵 D．对角矩阵和十字链表 3．采用稀疏矩阵的三元组表形式进行压缩存储，若要完对三元组表进行成转置，只要将行和列对换，这种说法（ B ）。 A．正确 B．错误 C． 无法确定 D．以上均不对 4．一个广义表的表头总是一个广义表，这种说法（ B ）。 A．正确 B．错误 C．无法确定 D．以上均不对 5．一个广义表的表尾总是一个广义表，这种说法（ A ）。 A．正确 B．错误 C．无法确定 D．以上均不对 6．广义表((a))的表头是（ C ）。 A．（ ） B．a C．（a） D．（（a）） 7．广义表（（a））的表尾是（ A ）。 A．（） B．a C．（a） D．（（a）） 8．广义表（（a），a）的表头是（ C ）。 A．（ ） B．a C．（a） D．（（a）） 9．广义表（（a），a）的表尾是（ C ）。 A．( ) B．a C．（a） D．（（a）） 10．广义表（a，b，c）的表头是（ A ）。 A．a B．（a） C．a，b D．（a，b） 11．广义表（a，b，c）的表尾是（ B）。 A．b，c B．（b，c） C．a．b，c D．（a，b，c） 12．广义表A满足Head（）= Tail（），则A为（B）。 A．（） B．（（）） C（（），（）） D．（（），（），（）） 二、填空题 1．数组（array）是n（n＞1）个__相同类型数据_的有序组合，数组中的数据是按顺序存储在一块___地址连续__的存储单元中。 2．数组中的每一个数据通常称为_数组元素_，__数组元素_用下标区分，其中下标的个数由数组的___维数__决定。 3．由于计算机内存中的存储单元是一个一维的存储结构，因此对于多维数组要想按顺 序存储到计算机存储单元中就必须有一个排列顺序问题。对于二维数组，有两种排列形式：一种是__以行序为主序_；另一种是___以列序为主序_。 4．对于需要压缩存储的矩阵可以分为特殊矩阵和___稀疏矩阵_。对那些具有相同值元素或零元素在矩阵中分布具有一定规律的矩阵，我们称之为__特殊矩阵__；而对于那些零元素数目远远多于非零元素数目，并且非零元素的分布没有规律的矩阵称为___稀疏矩阵__。 5．在一个n阶方阵 a中，若元素满足性质：aij＝aji（0<=i，j<=n-l），则称A为n阶__对称矩阵__。 6．采用顺序存储结构表示三元组表(Trope Table)，以实现对稀疏矩阵的一种压缩存储形式，称为__三元组顺序表_，简称____三元组__表。 7．___矩阵转置__运算是矩阵运算中最基本的一项，它是将一个m*n的矩阵变成另外 17 一个n*m的矩阵，同时使原来矩阵中元素的行和列的位置互换而值保持不变。 8．广义表是n（n>=0）个元素的序列。记作：A＝（a1，a2，?，an），其中，A是广义表的__名称_，n是它的__长度__，当n=0的时候称为__空表__。 9．在一个非空的广义表中，其元素ai可以是某一确定类型的单个元素，称为___原子__，也可以又是一个广义表，称为____子表___。 10．广义表的定义是一种递归的定义，广义表是一种递归的数据结构。当广义表非空的时候，称第一个元素al为广义表A的___表头__，称其余元素组成的表（a2，a3，?，an）是A的____表尾__。 11．广义表的深度一般定义为广义表元素___最大的层数__，或者说是广义表__括号的重数___。利用递归的定义，广义表的深度就是所有子表中_____最大深度加1____。 三、判断题 1．十字链表不是顺序存储结构。（ √ ） 2．三元组表不是一个随机存储结构。（ √） 3．稀疏矩阵压缩存储后，必然会失去随机存取功能。（ √ ） 4．若一个广义表的表头为空表，则此广义表也为空表。（ × ） 5．广义表是线性表的推广，是一类线性数据结构。（ × ） 6．任何一个非空广义表，其表头可能是单元素或广义表，其表尾必定是广义表。 （ √ ） 7．一个稀疏矩阵Am*n采用三元组形式表示，若把三元组中有关行下标与列下标的值互换，并把m和n的值互换，则就完成了Am*n的转置运算。（ × ） 8．数组中每个元素必定具有相同的数据类型。（ √ ） 9．线性表是广义表的特例。（ √ ） 10．如果广义表中的每个元素都是原子，则广义表便成为线性表。（√） 11．广义表中原子个数即为广义表的长度。（×） 12．广义表最大子表的深度为广义表的深度。（×） 13．广义表中元素最大的层数称为广义表的深度。（√） 14．广义表是一种多层次结构。（√） 15．广义表是一种线性结构。（×） 16．广义表是一种共享结构。（√） 17．广义表是一种递归结构。（√） 18．广义表是一种单链表结构。（√） 四、综合题 1．用二维数组实现“魔方阵”的打印，所谓“魔方降’是指满足每一行、每一列和对角线上的元素之和均相等的方阵。例如： 8 1 6 3 5 7 4 9 2 就是一个三阶的魔方阵。现在要求编程实现任意输人一个自然数n，打印出相应的n阶魔方阵。 2．找出并打印一个二维数组中的鞍点，所谓鞍点是指该位置上的元素在该行上最大，在该列上最小。 3．写一个创建稀疏矩阵相应三元组的算法。 4．假设三元组元素值为整型，写一个查找三元组元素值为n的算法。 5．有两个稀疏矩阵的三元组triple_a和triple_b，请写出利用三元组这种数据结构，实 18 现将两个稀疏矩阵相加，最后的和存入三元组表triple_c之中的算法。 6．有两个稀疏矩阵的三元组triple_a和triple_b，请写出利用三元组这种数据结构，实现将两个稀疏矩阵相乘，并将最后的乘积存人二元组表triple_c之中的算法。 7．现有稀疏矩阵A如图所示，要求画出以下各种表示法。 ?01400?5??0?700? 0?? ??3600280?? (1)三元组表示法 (2)十字链表表示法 习题六 一、选择题 l．在二叉树后序遍历中，任一个结点均在其子女结点后面，这种说法（ ）。 A．正确 B．不正确 C．无法判断 D．以上均不对 2．在二叉树先序遍历中，任一个结点均在其子女结点前面，这种说法（ ）。 A．正确 B．不正确 C．无法判断 D．以上均不对 3．设深度为h的二叉树上只有叶子结点和同时具有左右子树的结点，则此类二叉树中所包含的结点数目至少为（ ）。 A．2h B．2h C．2h＋1 D．2h-l 4．二叉村第k层上最多有（ ）个结点。 A．2k B．2k-1 C．2k-1 D．2k-1 5．二叉树的深度为k，则二叉树最多有（ ）个结点。 A．2k B．2k-1 C．2k-1 D．2k -1 6．设某一二叉树先序遍历为abdec，中序遍历为dbeac，则该二叉树后序遍历的顺序是（ ）。 A．abdec B．debac C．debca D．abedc 7．设某一二叉树中序遍历为badce，后序遍历为bdeca，则该三叉树先序遍历的顺序是（ ）。 A．adbec B．decab C．debac D．abode 8．设某一二叉树先序遍历为abdecf，后序遍历为debfca，则该二叉树中序遍历的顺序是（ ）。 A．adbecf B．dfecab C．dbeacf D．abcdef 9．将一棵树T转换为一棵二叉树T2，则T的先序遍历是T2的（ ）。 A．先序 B．中序 C．后序 D．无法确定 10．将一棵树T转换为一棵二叉树T2，则T的后序遍历是T2的（ ）。 A．先序 B．中序 C．后序 D．无法碉定 ll．树最适合于用来表示（ ）。 19 A．线性结构的数据 B．顺序结构的数据 C．元素之间无前驱和后继关系的数据 D．元素之间有包含和层次关系的数据 12．二叉树的叶于结点在先序、中序和后序遍历过程中的相对秩序（ ）。 A．发生改变 B．不发生改变 C．无法确定 D．以上均不正确 13． 设一棵二叉树度2的结点数是7，度为1的结点数是6，则叶子结点数是（ ）。 A．6 B．7 C．8 D．9 14．用顺序存储的方法，将完全二叉树中所有结点按层逐个从左到右的顺序存放在一维数组R[1．．n]中，若结点R[i]有左孩子，则其左孩子是（ ）。 A．R[2i-1] B．R[2i+1] C．R[2i] D．R[2/i] 15．用顺序存储的方法，将完全二叉树中所有结点按层逐个从左到右的顺序存放在一维数组R[1．．n]中，若结点R[i]有右孩子，则其右孩子是（ ）。 A．R[2i-1] B．R[2i＋l] C．R[2i] D．R[2/i] 16．一棵非空的二叉树，先序遍历与后序遍历正好相反，则该二叉树满足（ ）。 A．无左孩子 B．无右孩子 C．只有一个叶子结点 D．任意二叉树 17．设a、b为一棵二叉树的两个结点，在后序遍历中，a在b前的条件是（ ）。 A．a在b上方 B．a在b下方 C．a在b左方 D．a在b右方 18．线索二叉树是一种（ ）。 A．逻辑结构 B．线性结构 C．逻辑和线性结构 D．物理结构 19．N个结点的线索二叉树中，线索的数目是（ ）。 A．N-1 B．N＋1 C．2N D．2N－1 20．权值为｛l，2，6，8｝的四个结点构成的哈夫曼树的带权路径长度是（ ）。 A．18 B．28 C．19 D．29 21．实现任意二叉树的后序遍历的非递归算法而不使用栈结构，最佳方案是二叉村采用（ ）存储结构。 A．二叉链表 B．广义表存储结构 C．三叉链表 D．顺序存储结构 22．对一个满二叉树，m个树叶，k个分枝结点，n个结点，则（ ）。 A．n＝m＋1 B．m+1=2n C．m＝k-1 D．n=2k+1 23．具有五层结点的二叉平衡树至少有（ ）个结点。 A．10 B．12 C．15 D．17 24．设n，m为一棵二叉树上的二个结点，在中序遍历时，n在m前的条件是（ ）。 A．n在m右方 B．n是m祖先 C．n在m左方 D．n是m子孙 25．线索二又树是一种（ ）结构。 A．逻辑 B．逻辑和物理 C．物理 D．线性 26．将一棵有100个结点的完全二又树从根这一层开始，每一层上从左到有依次对结点进行编号，根结点的编号为1，则编号为49的结点的左孩子编号为（ ）。 A．98 B．99 C．50 D．48 二、填空题 1．树(Tree)是n(n≥0)个结点的_____________集。 20 2．任何一个非空树中：有且仅有一个特定的结点，称为该树的______________的结点，___________结点之外的其余结点可分为m(m≥0)个互不相交的有限集合T1，T2，?，Tm，且其中每一个结点又是一棵树，称之为__________的______________。 3．树的__________是指一个数据元素及指向其子树的分支。通常通过一个__________来描述，在树型表示中，用一个圆圈及短线表示。 4．结点的度是指结点所拥有的________________。 5．树内各结点度的___________________为树的度。 6．度大于0的结点称为________________或______________________。 7．____________称为叶子结点，简称为叶子，又称作终端结点。 8．一个结点的____________，或者说一个结点的____________称为该结点的孩子结点，简称为孩子。 9．一个结点称为其后继结点（即孩子结点）的______________。 10．一个结点的子树中的任一结点都称为该结点的___________________。 11．从根到该结点所经分支上的所有结点称为该结点的_______________。 12．具有_______________________的结点互称为兄弟结点，简称为兄弟。 13．从根结点开始定义，根为________层，根的孩子为__________层，依次往下类推，若某结点在第k层，则其子树的根就在_________________层。 14．其双亲在同一层次上的结点互称为___________________。 15．树中结点的___________称为树的深度，又称为树的高度。 16．如果树中各结点的各子树从左至右是有序排列，不可互换的，则称该树为______。 17．如果树中各结点的各子树无排列顺序，即可以互换位置，则称为该树为_________。 18．n(n≥0)棵互不相交的树的集合称为______________________。 19．二又树（Binary Tree）是结点的有限集合，这个集合或者是空，或者是由一个根结点和__________的称为______________和____________的二叉树构成。 20．二叉树第i层上最多有____________个结点。 21．深度为k的二又树最多有____________个结点(k≥l)。 22．在任意二叉树中，叶子结点的数目(即度为0的结点数)等于度为2的结点数____________。 23．一棵深度为k且具有2k-1个结点的二叉树称为__________。这类二叉树的特点是，二叉树中每一层结点的个数都是______________的个数。 24．_________是那种在一棵二叉树中，除最后一层外，若其余层都是满的，并且最后一层或者是满的，或者所缺少的结点都在右边。 25．具有n个结点的完全二叉树的深度是_______________。 26．对于一棵有n个结点的完全二叉树的结点进行编号（自上而下，子左至右），则对任一结点 i（l≤i≤n），如果结点i=l，则结点i是二叉树的____________，无双亲；如果结点i>l，则其双亲Parent(i)的序号是结点_______________；如果2i≤n，则结点i的左孩子Lchild(BT,，i）是_________，否则结点i无左孩子(结点i必为叶子结点)；如果2i＋l≤n，则结点i的右孩子 RChild（BT，i）的序号是____________；否则该结点无右孩子。 27．二叉树的顺序存储结构是用_________________存储二叉树的数据元素。 28．____________是指按照某条搜索路径访问树中的某个结点，使得树中每个结点均被访问一次，而且仅被访问一次。 29．先序遍历二叉树的操作定义为：若二叉树为空，则为空操作；否则进行如下操作：访问二叉树____________；先序遍历二叉树____________；先序遍历二叉树_________。 30．中序遍历二叉树的操作定义为：若二叉树为空，则为空操作；否则进行如下操作： 21 中序遍历二叉树__________；访问二又树__________；中序遍历二又树____________。 31．后序遍历二叉树的操作定义为：若二叉树为空，则为空操作；否则进行如下操作：后序遍历二叉树___________；后序遍历二叉树_________；访问二叉树_____________。 32．线索二叉树（Threaded Binary Tree）是充分利用二义链表的 n+1个空的指针域作为线索来标志每一个结点的________和__________信息。当某个结点有左孩子的时候，使其___________指向其左孩子，无左孩子的时候，使其左指针域指向该结点的___________；当某个结点有有孩子的时候，使其右指针域指向该结点的__________，无右孩子的时候，使其有指针域指向该结点的_____________。 33．线索二叉树的线索链表中，指向结点前驱和后继的指针称为___________；加上线索的二叉树称为_____________；对二叉树以某种次序进行遍历使其成为线索二叉树的过程称为_______________________。 34．树的存储结构常见的有____________、____________和________________。 35．树的先序遍历过程如下：若树为空，则进行空操作；若树非空，则：访问树 的＿；依次先序遍历树的＿。 36．树的后序遍历过程为：若树为空，则进行空操作；若树非空，则：依次后序遍历__________；访问_________________。 37．森林的先序遍历过程为：若森林非空，则： （1）访问森林中第一棵树的___________。 （2）先序遍历第一棵树中_____________。 （3）先序遍历_______________________。 38．森林的后序遍历过程为：若森林非空，则： （l）后序遍历森林中第一棵树的_______________。 （2）访问第一棵树的_________________________。 （3）后序遍历_______________________________。 39．从树中一个结点到另一个结点之间的_________称为这两个结点的路径。 40．路径上的分支数目称为______________。 41．树的路径长度是指从树根到每一结点的__________________。 42．将树中的结点赋上一个有着某种意义的实数，称此实数为该结点的____________。 43．树的带权路径长度为树中所有叶子结点的____________。 44．哈夫曼树（Huffman Tree）又称___________。它是n个带权叶子结点构成的所有二叉树中，带权路径长度WPL__________________。 45，所谓前缀编码是指在所有对字符的编码中，任何一个字符都不是____________。 46．已知完全二叉树的第八层有8个结点，则其叶子结点数是__________________。 47．在有n个叶子结点的哈夫曼树中，总结点数是___________。 48．已知完全二又树的第7层有10个叶子结点，则整个二又树的结点数最多是___。 49．已知二叉树中叶子数为50，仅有一个孩子的结点数为30，则总结点数为___。 50．一棵树T采用二叉链表BT存储，如果树T中某结点为叶子结点，则在二叉链表BT中所对应的结点一定满足___________________。 51．在二叉链表中，判断某指针P所指结点为叶子结点的条件是______________。 52．若以{4，5，6，7，8}作为叶子结点的权值构造哈夫曼树，则其带权路径长度是___________。 53．已知二叉树有50个叶子结点，则该二叉树的总结点数至少是______________。 54．3个结点可构成___________________棵不同形态的树。 55．已知完全二叉树的第七层有8个结点，则其叶子结点数是______________. 22 56．将一棵有100个结点的完全二叉树从根这一层开始，每一层上从左到右依次对结 点进行编号，根结点的编号为1，则编号为49的结点的左孩子编号为____________。 57．若要对某二叉排序树进行遍历，保证输出的所有结点序列按键值递增次序排列， 应对该二叉树采用_______________遍历法。 三、判断题 1．完全二叉树的某个结点若无左孩子，则它必然是叶结点。（ ） 2．存在这样一种二叉树，对它采用任何次序的遍历结果相同。（ ） 3．度为二的树称为二叉树。（ ） 4．二叉树中不存在度大于2的结点。（ ） 5．当二叉树中某个结点只有一棵子树的时候，无左右子树之分。（ ） 6．任何一棵二叉树都可以不用栈实现前序线索树的前序遍历。（ ） 7．哈夫曼编码是一种前缀编码，不允许出现两个字符编码相同的情况。（ ） 8．完全二叉树某结点有右子树，则必然有左子树。（ ） 9．前序遍历一棵二叉树的结点就可以得到排好序的结点序列。（ ） 10．将一棵拥有子树的树转换为二叉树后，根结点可能没有左子树。（ ） 11．根据二叉树的前序遍历和中序遍历可以得到二又树的后序遍历。（ ） 12．哈夫曼树是带权路径长度最短的树。（ ） 13．哈夫曼树的路径上权值较大的结点离根较远。（ ） 14．后序遍历森林与后序遍历与森林相对应的二叉树结果相同。（ ） 15．在二叉树中，具有一个孩子的结点，在中序遍历序列中，没有后继子女结点。 （ ） 16．前序遍历与森林相对应的二叉树结果不同。（ ） 17．若一棵二叉树的任一非叶子结点的度为2，则该二叉树为满二叉树。（ ） 18．二叉树只能采用二叉链表来存储。（ ） 19．给定结点数的平衡二叉树的高度是惟一的。（ ） 四、综合题 1．一棵树表达成如下形式： D＝{A，B，C，D，E，F，G， H，I，J，K，L，M，N，O} R=＜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结点的层次是多少？ (11)D结点的子孙有哪些？ (12) 以结点D为根的子树度是多少？ (13) 以结点D为根的子树层是多少？ 23 (14) 该树的层是多少？ (15) 该树的度是多少？ 2．画出图6-1中树的二叉树表示形式。 （a） （b） （c） 图6-l 3．已知某二叉树的先序遍历的结果是：A，B，D，QC，E，H，L，I，K，M，F和J，它的中序遍历的结果是：QD，B，A，L，H，E，K，LM，C，F和J，请画出这棵二叉树，并且写出该二叉树后序通历的结果。 4．写一个将一棵二叉树复制给另一棵二又树的算法。 5．已知—个二叉树用二叉链表表示，其根指针为t，请写一个算法，从根结点开始按层次通历该二叉树，同层的结点接从左到右的次序进行访问。 6．已知一棵二叉树的先序遍历序列和中序遍历序列，请写出根据二又树先序遍历序列和中序遍历序列构造一棵二叉树的算法。 7．假设一棵哈夫曼树共有n0个叶子结点，试证明树中共有2no-l个结点。 8．假设通信用的报文由9个字母A、B、C、D、E、F、G、H和I构成，它们出现的频率分别是：10、20、5、15、8、2、3、7和30。请用这9个字母出现得频率作为权值求： （l）设计一棵哈夫曼树。 （2）计算其带权路径长度WPL值。 （3）写出每个字符的哈夫曼编码。 24 习题七 一、选择题 1．在一个无向图G中，所有顶点的度数之和等于所有边数之和的（ ）倍。 A．l/2 B．1 C．2 D．4 2．在一个有向图中，所有顶点的入度之和等于所有顶点的出度之和的（ ）倍。 A．l/2 B．1 C．2 D．4 3．一个具有n个顶点的无向图包含（ ）条边。 A．n B．n＋1 C．n-1 D．n/2 4．一个具有n个顶点的无向完全图包含（ ）条边。 A．n(n-l) B．n(n+l) C．n(n-l)/2 D．n(n-l)/2 5 一个具有n个顶点的有向完全图包含（ ）条边。 A．n(n-1) B．n(n+l) C．n(n-l)/2 D．n(n+l)/2 6．对于具有n个顶点的图，若采用邻接矩阵表示，则该矩阵的大小为（ ）。 A．n B．n2 C．n-1 D．(n-l)2 7．对于一个具有n个顶点和e条边的无向图，若采用邻接表表示，则表头向量的大小为（ ）。 A．n B．e C．2n D．2e 8．对于一个具有n个顶点和e条边的无向图，若采用邻接表表示，则所有顶点邻接表中的结点总数为（ ）。 A．n B．e C．2n D．2e 9．在有向图的邻接表中，每个顶点邻接表链接着该顶点所有（ ）邻接点。 A．入边 B．出边 C．入边和出边 D．不是入边也不是出边 10．在有向图的逆邻接表中，每个顶点邻接表链接着该顶点所有（ ）邻接点。 A．入边 B．出边 C．入边和出边 D．不是人边也不是出边 11．下列说法中不正确的是（ ）。 A．无向图中的极大连通子图称为连通分量 B．连通图的广度优先搜索中一般要采用队列来暂存刚访问过的顶点 C．图的深度优先搜索中一般要采用栈来暂存刚访问过的顶点 D．有向图的遍历不可采用广度优先搜索方法 12．设无向图 G=(V, E) 和G’= (V’, E’)，如果 G’为G的生成树，则下列说法中不正确的是（ ）。 A．G’为G的连通分量 B．G’为G的无环子图 C．G’为G的子图 D．G’为G的极小连通子图且V’＝V 13．如果无向图G必须进行二次广度优先搜索才能访问其所有顶点，则下列说法中不正确的是（ ）。 A．G肯定不是完全图 B．G一定不是连通图 C．G中一定有回路 D．G有二个连通分量 14．邻接表是图的一种（ ）。 A．顺序存储结构 B． 链式存储结构 C．索引存储结构 D． 散列存储结构 15．如果从无向图的任一顶点出发进行一次深度优先搜索即可访问所有顶点，则该图一 25 定是（ ）。 A．完全图 B．连通图 C．有回路 D．一棵树 16．下列有关图遍历的说法不正确的是（ ）。 A．连通图的深度优先搜索是一个递归过程 B．图的广度优先搜索中邻接点的寻找具有“先进先出”的特征 C．非连通图不能用深度优先搜索法 D．图的遍历要求每一顶点仅被访问一次 17． 一个无向连通图的生成树是含有该连通图的全部顶点的（ ）。 A．极小连通子图 B．极小子图 C．极大连通子图 D．极大子图 18．无向图的邻接矩阵是一个（ ）。 A．对称矩阵 B．零矩阵 C．上三角矩阵 D．对角矩阵 二、填空题 1．在图中，任何两个数据元素之间都可能存在关系，因此图的数据元素之间是一种________________的关系。 2．在图G中，如果代表边的顶点偶对是_____________，则称G为无向图。 3．在图G中，如果代表边的顶点偶对是_____________，则称G为有向图。 4．在图G中，＜vi，vj＞表示从vi到vj的一条边，在有向图中又称为一条____，且称vi为______或_________，称vj为_________或__________。显然在有一向图中 5．具有n (n-1)/2条边的无向图称为__________，简称为_________，其中n表示无向图中顶点的个数，n(n-1)/2是具有n个顶点无向图所拥有边的___________。 6．具有n个定点的有向图，如果它同时具有n(n-1)条狐，则称该图为____________，其中n(n-1)是具有n个顶点有向图所拥有弧的___________________。 7． 有很少条边或弧（如边数少于nlogn）的图称为________________。 8． 如果图中的边或弧带有权，则称这种图为_______________。 9． 如果有两个网G=(V, E)，G’=(V’,E’)，若满足V(G’) V(G)，并且E(G’) E(G)，则称图G’为图G的__________。 10． 在无向图中，若存在一条边(v, w)，则称v和w这两个端点互为___________，同时称边(v,w)__________顶点v和w，或者说边(v,w)和顶点v和w_______________。 11．在有向图中，若存在一条弧 12．顶点v的度定义为_________________的数目，记为D(v)。 13．在有向图中，顶点v的度又分为_____________和_________，__________是以顶点v为头的弧的数目，或者说是以该顶点为终点的边的数目，记为ID(v)；____________是以顶点v为尾的弧的数目，或者说是以顶点为起点的边的数目，记为OD(v)；顶点v的度是它的___________和__________之和，即D(v)=ID(v)＋OD(v)。 14．____________是指一条路径上所经过的边或弧的数目。 15．若一条路径上除开始结点和结束结点外(开始结点和结束结点也可以为不同顶点），其余顶点均不相同，则称该路径为_____________。 16． 若一条路径上的开始结点和结束结点为同一个顶点，则称该路径为________或_______。同时除了第一个顶点和最后一个顶点之外，其余顶点不重复出现的回路称_________或__________。 17．在无向图G中，如果从顶点v到顶点v’有路径，则称v和v’是______________的。 26 如果对于图中任意两个顶点v和v’都是连通的，则称图G是________，否则称为__________。无向图中，极大的连通子图称为___________________。 18．在有向图中，若任意两个顶点vi，vj∈V，vi≠vj，从vi到vj和从vj到vi都存在路径，则称该图是____________。有向图中的极大强连通子图称为有向同的___________。 19．一个连通图的生成树是一个__________，它含有图中全部以点，但只有构成一棵树的__________条边。如果在一棵生成树添加一条边，必定构成一个___________，因为新添加的这条边使得依附在它两端的两个顶点有了____________。 20．如果有一个有向图恰有一个顶点的人度_______，其余以顶点的人度均________，则该有向图是一棵有向树。一个有向图的___________由若干棵有向树构成，含有图中全部顶点，但只有构成若干棵不相交的有向树的弧。 21．图的邻接矩阵（Adjacency Matrix）表示法是用一个________来表示图中顶点之间的相邻关系。 22．邻接表(Adjacency List)是图的一种_______存储结构。在邻接表中，对图中每个顶点建立一个_________，第i个单链表中的结点表示依附于顶点vi的边(对无向图)或弧（对有向图）。 23．逆邻接表只有______图才具有。是为了便于确定有向图中顶点的_______而建立的。 24．一个图的邻接矩阵的表示是_________，但是图的邻接表的表示并_____________。这是因为邻接表中各边结点的连接次序取决于建立邻接表时输入的次序，由于输入的时候是随机的，所以图的邻接表建立的结果也有可能____________。 25．从邻接表的定义可以看到，若无向图有n个结点和e条边，则它的邻接表需要________个头结点和______________个表结点。 26．图的遍历(Traversing Graph)是从图的某一顶点出发访问图中___________，并且使每一个顶点___________________的过程。 27．图的深度优先搜索的基本思想是：从中某个顶点v出发，首先访问_________，然后访问_________顶点w，接着访问一个_____________的顶点，依此类推，直到图中所有和v有路径相通的顶点都被访问到；若此时图中仍有顶点未被访问，则选择图中未被访问的顶点作为___________，重复上述过程，直到图中所有顶点_______________为止。 28．图的深度优先搜索遍历类似于树的__________________遍历。 29．图的广度优先搜索的基本思想是：从某个顶点v出发，首先访问此顶点，然后按广度优先搜索依次访问所有v的__________，接着从这些___________出发仍然进行广度优先搜索依次访问其他结点，直至图中所有已被访问的顶点的_________全部被访问到。若此时图中依然有未被访问的顶点。则另选一个图中____________作为起始点，重复上述过程，直到图中所有顶点___________为止。 30．图的广度优先搜索类似于树的_______________遍历。 31．如果连通图是一个网络，生成树的_______称为这棵生成树的代价，则称该网络中所有生成树中权值最小的生成树为____________，简称为__________。 32．构造一棵最小生成树往往都要利用最小生成树的一种简称为MST的性质。常见的构造最小生成树的______________算法和___________算法都利用了MST性质。 33． 路径上的第一个顶点称为____________，最后一个顶点称为____________。 34． 迪杰斯特拉算法是求____________的最短路径，弗洛伊德（Floyd）算法是求_________的最短路径。 35．一个____________称为有向无环图，简称为DAG图。 36．DAG图比有向树更一般，因为在有向树中不允许出现____________的结点，而在DAG图中则可以；另外DAG图不允许_____________，因此又是一种特殊的图。 27 37．用顶点表示_________，用弧表示活动之间________的有向图，称为顶点表示活动的网（Activity On Vertex Network），简称 AOV网。 38．在AOV网中不可以出现有向环或回路，如果出现环或回路，这意味着某项活动是_________，这样的工程无法进行，对于计算机中的程序流程图来说就是_____________，也相当于操作系统中的______________。 39．检测AOV网是否有回路的方法是构造_________。从构造拓扑序列过程中可以发现是否有______________。 40．拓扑排序是对AOV网构造一个__________，使得所有结点的________在序列中得以体现，即在序列中某个结点的前驱必须在后继之前。拓扑排序的序列__________。 41．如果用数学上的术语进行描述，拓扑排序是由某个集合上的一个__________关系得到该集合上的一个__________的操作。 42．构造拓扑有序序列的过程可以发现有向图中________，同时构造拓扑有序序列的过程就是利用拓扑排序算法进行________________的过程。 43．拓扑排序的结果使得当前图中_________全部被输出，但仍然有结点未被输出，这说明有向图中存在_______________。 44．如果含n个顶点的图形成一个环，则它有___________棵生成树。 45．有n个结点的无向图的边数最多为____________。 46．有n个顶点的强连通有向图G至少有___________条边。 47．用邻接矩阵存储有向图G，其第i行的所有元素之和等于顶点i的_________。 48．设有向图G的邻接矩阵为 A，图中i和j之间不存在弧，则A[i,j］的值为______。 49．有n个顶点的连通图的边数至少为____________。 50．在有n个顶点的有向图中，每个顶点的度最大可达___________。 51．在无向图G的邻接矩阵A中，若(vi,vj)属于图G的边集，则对应元素A[i,j]为______，否则等于_____________（用逗号分开）。 52．已知一个有向图用邻接矩阵表示，计算第i个结点的人入度的方法是__________。 53．对于一个具有n个顶点和e条边的无向图，若采用邻接表表示，则表头向量的大小为________________，所有邻接表中的结点总数是________________。 三、判断题 1．有n个结点的无向图中，若边数大于n-1，则该图是连通的。 （ ） 2．若一个有向图的邻接矩阵中对角线以下元素均为零，则该图的拓扑有序序列必定存在。 （ ） 3．AOV网拓扑排序的结果是惟一的。 （ ） 4．图的广度优先搜索序列是惟一的。 （ ） 5．具有n个顶点的无向图采用邻接矩阵表示，图中的边数等于邻接矩阵中非零元素之和的一半。 （ ） 6．若连通图上各边权值均不相同，则该图的最小生成树是惟一的。 （ ） 7．无向图的邻接矩阵一定是对称的。（ ） 8．有向图的邻接矩阵一定是非对称的。（ ） 9．用邻接矩阵存储图的时候，占用空间大小不但与图的结点个数有关还与图的边数有关。（ ） 10．图的连通分量是无向图的极小连通子图。（ ） 11．图的强连通分量是无向图的极大连通子图。（ ） 12．对任意一个图从它的某个顶点出发进行一次深度优先或广度优先搜索遍历可访问到该图的每个顶点。（ ） 28 13．一个有向图的邻接表和逆邻接表中的节点个数一定相等。（ ） 14．有向图用邻接矩阵表示后，顶点i的出度等于第i行中非0且非无穷的元素个数。 （ ） 15．图G的某一最小生成树的代价一定小于其他生成树的代价。（ ） 四、综合题 l．请写出如图7-1所示无向图的邻接矩阵和邻接表两种存储结构。 2．依据无向图7-1，请写出： （1）从顶点1出发图的深度优先搜索序列。 （2）从顶点回出发图广度优先搜索的序列。 （3）写出图的深度优先搜索算法。 （4）写出图的广度优先搜索算法。 3．使用Prim算法，依据无向图7-2做以下问题； 图7-2 （l）写出构造该图的最小生成树的过程。 (2) 写出相应的构造最小生成树算法。 4．使用Kruskal算法，依据无向图7-2做以下问题： （l）写出构造该图的最小生成树的过程。 (2) 写出相应的构造最小生成树算法的形式描述。 5． 假设图采用邻接表表示，写出一个从顶点v0对图按深度优先搜索遍历的非递归算法。 6．有一个无向图采用邻接表的存储结构，请编写算法，以遍历的形式输出从顶点v到顶点w的路径中长度为len的简单路径。 7．以邻接表作为存储结构，编写一个算法，利用深度优先搜索法，求出在无向图中通过给定点w的简单回路的算法。 29 习题八 一、选择题 1.顺序查找方法适合于存储结构为（ ）的线性表 A.散列存储 B.索引存储 C.散列存储或索引存储 D.顺序存储或链接存储 2.对线性表进行二分查找的时候，要求线性表必须（ ）。 A.以顺序存储方式 B.以链接存储方式 C.以顺序存储方式，且数据元素有序 D.以链接存储方式，且数据元素有序 3. 如果要求一个线性表既能较快地查找，又能动态适应变化要求，可以采用（ ）查找方法。 A.顺序 B.分块 C.折半 D.散列 4. 对于一个线性表，若要求既能进行较快地插入和删除，又要求存储结构能够反映数据元素之间的逻辑关系，则应该( ) 。 A.以顺序存储方式 B.以链接存储方式 C.以索引存储方式 D.以散列存储方式 5. 在线性表的存储结构中,（ ）查找、插入和删除速度慢，但顺序存储和随机存取第i个元素速度快。 A.顺序表 B.链接表 C.散列表 D.索引表 6. 在( )上查找和存取速度快,但插入和删除速度慢。 A.顺序表 B.链接表 C.顺序有序表 D.散列表 7. 在( )上查找、插入和删除速度快,但不能进行顺序存取。 A.顺序表 B.链接表 C.顺序有序表 D.散列表 8. 在( )上插入、删除和顺序存取速度快,但查找速度慢。 A.顺序表 B.链接表 C.顺序有序表 D.散列表 9. 采用顺序查找方法查找长度为n的线性表,查找每个元素的平均比较次数为( ) A. n B. n/2 C. (n+1)/2 D.(n-1)/2 10.顺序查找具有n个元素的线性表,其时间复杂度为( ) 。 A.O(n) B.O(log2n) C.O(n2) D.O(nlog2n) 11.折半查找具有n个元素的线性表,其时间复杂度为( ) 。 A.O(n) B.O(lOg2n) C.O(n2) D.O(nlog2n) 12.己知一个有序表为(11,22,33,44,55,66,77, 88,99), 则折半查找元素55需要比较( )次。 A.1 B.2 C.3 D.4 13.已知一个有序表为(11,22,33,44,55,66,77,88,99), 则顺序查找元素 55 需要比较( )次。 A.3 B.4 C.5 D.6 14.顺序查找法与二分查找法对存储结构的要求是( ) 。 A. 顺序查找与二分查找均只是适用于顺序表 B. 顺序查找与二分查找均既适用于顺序表 , 也适用于链表 C. 顺序查找只是适用于顺序表 D. 二分查找适用于顺序表 15.在对查找表的查找过程中,若被查找的数据元素不存在,则把该数据元素插到集言中。这种方式主要适合于( ) 。 A.静态查找表 B. 动态查找表 C.静态查找表与动态查找表 D. 两种表都不适合 16.若用二分查找取得的中间位置元素关键字值大于被查找值，则说明被查找值位于中间值 30 的前面,下次的查找区间为从原开始位置至( ) 。 A.该中间位置 B.该中间位置-1 C.该中间位置+1 D.该中间位置1/2 二、填空题 1.查找表是由同一类型的数据元素 ( 或记录 ) 组成的 , 是查找所依赖 。 2. 如果对查找表只进行查询某个\特定的\数据元素是否在查找表中, 以及查找某\特定的\数据元素的各种属性两种类型的基本操作,而不进行插入和删除数据元素的查找表称为 。 3. 如果在查找表中进行查找的过程中，同时插入查找表中不存在的数据元素，或者查找表中删除已存在的某个数据元素，则称此类查找表为 。 4. 关键字是数据元素(或记录)中某个 ，用它可以标识(识别)一个查表中 5. 在一个查找表中，能够惟一的标识一个数据元素(或记录)的关键字称为 。 6. 次关键字也称为 或 ，是在查找表中可以标识 的关键字。 7. 查找又称 ，它是根据给定的某个值，在查找表中确定是否有元素(或记 录)的关键字的操作。若操作之后确定表中存在这样的记录，则称为查找 的，否则称为 。 8. 平均查找长度是指为确定所查找的记录在查找表中的位置，需要与给定值进行比较关键字个数的 。 9. 最大查找长度是指为确定所查找的记录在查找表中的位置，需要与给定值进行比较关键字个数的 。最大查找长度随所查找的 、 和 都有关系。最大查找长度通常是在考虑查找给定值在查找表中的情况。 10. 是一种最简单、最基本的查找方法，它的基本思想是：从表的一端开始，依次顺序扫描线性表，将扫描到记录的关键字逐个与给定值进行比较，若某个记录的关键字和给定的值相等，则说明找到所要的记录，查找成功；若扫描结束后，仍未找到关键字等于给定值的记录，则说明表中没有所查找的记录，查找不成功。 11. 折半查找( Binary Search)又称为 ， 是一种效率较高的一种查找算法。 12. 折半查找的思路是：每次将给定值与查找表中所要查找区域 的关键字进行比较，而不是查找表中的第一条或最后一条。 13. 分析折半查找的性能可以用二叉树来进行描述。把当前查找区间的中间位置上的结点作为根结点，左半区间和右半区间中结点分别作为左子树和右子树，由此得到的二叉可称为 。 14.分块查找(Blocking Search)又称为 ，是一种以 的形式来来进行的查找方法。分块查找是 的一种改进，它是一种介于 和折半查找之间的查找方法。 15. 二叉排序树(Binary Sort Tree)，又称为 ，它或者是一棵空树，或者是具有下列性质的一棵二叉树： (1) 若左子树不空，则左子树上所有结点的值 。 (2) 若右子树不空，则右子树上所有结点的值 。 (3) 左右子树又分别是 。 16.平衡二叉树定义为：它或者是一棵空树；或者是具有这样性质的二叉树:它的左子树 31 和右子树都是 且左子树和右子树的深度之差的绝对值 。 17. 我们称在构造平衡二叉排序树的过程中，离插入结点最近，且以平衡因子绝对值大 于1 的结点作为根结点的子树为 。 18. 哈希表查找就是一种通过某种映射建立起 之间的对应关系，希望 或经过很少次比较即可获得所要查找的记录。 19. 哈希(Hash)表查找又称为 查找，它是一种重要的查找技术。哈希表查找因使用哈希函数(又称为 ) 而得名。哈希函数是一种 的函数。 20. 利用哈希函数可以实现记录关键字和关键字所对应记录存储地址的转换或映像，这种映像过程称为 或 ，映像结果产生的哈希函数值h (key)作为存储位置称为 或 ，利用哈希函数映像哈希地址，所得到的存储表称为 21. 有时候在向哈希表中存储关键字的时候，会出现一个待插入关键字的记录已经被占用的情况，这种 的现象称为冲突 ( Collision) 。 22. 具有相同哈希函数值的关键字对相应的哈希函数来说称为 ，由同义词产生的冲突称为 。 23. 构造哈希函数的 是取关键字或关键字的某个线性函数作为哈希地址。 24. 构造哈希函数的 是对关键字中数字进行分析，然后用提取其中一部分分布较为均匀的数字位作为哈希地址的方法。 25. 构造哈希函数的 是用关键字key除以某个正整数p，所得余数作为哈希地址的方法。 26. 构造哈希函数的 是取关键字平方的中间几位作为哈希地址的方法。 27. 构造哈希函数的 是先将关键字分割成位数相等的几段(其中最后一段的位数可以不相等)，然后取这几位的叠加和作为哈希地址。 中数位的叠加可以分为移位叠加和间界叠加两种。所谓移位叠加是 ，然后相加；间界叠加是 然后对齐相加。 28. 构造哈希函数应当尽量减少冲突，但是还是无法避免冲突的发生。一旦冲突发生了， 就必须寻求合适的方法来解决冲突。通常解决冲突可以采用 和 。 29. 开放定址法(Open Addressing)是指将哈希表中的空单元向处理冲突开放。开放定址法解决冲突，形成下一个地址的形式是：Hi=(h(key)+di)%m, i=1,2, … ,k(k≤m-l)其中，h (key) 为哈希函数，m为哈希表长，di为增量序列。根据上式形成增量序列di的不同，开放定址法又可以分成如下三种形式： 、 、 。 30. 分析哈希表的查找过程可以知道，造成哈希表冲突的首要因素是 ，第二个因素是 ，第三个因素是 。 31. 在有序表A[1..18]中，采用二分查找算法查找元素值等于A[7]的元素，所比较过的元素的下标依次为 。 32. 有17个元素的有序表A[1..17]作二分查找，在查找其等于A[8]的元素时，被比较的元素的下标依次是 。 33. 假定有K个关键字互为同义词，若用线性探测再散列法把这K个关键字存入散列表中，至少要进行 次探测。 34. 一个无序序列可以通过构造一个 树而变成一个有序序列，构造树的过程即为对无序序列进行排序的过程。 35. 在有序表a [1..20]中，采用二分查找算法查找元素值等于a[12]的元素，所比较过的元素的下标依次为 。 36. 对于长度为 n 的线形表 , 若进行顺序查找 , 则时间复杂性为 ；若用二 32 分法查找，则复杂性为 ；若用分块法查找(假定总块数和每块长度均接近 )，则时间复杂性为 。 37. 对长度为 L 的顺序表，采用设置岗哨方式顺序查找，若查找不成功，其查找程 为 。 38. 对有序表 (25,30,32,38,47,54,62,68,90,95) 用二分查找法查找32，则所需的比较次数为 。 三、判断题 1. 用向量表示的有序表可以使用折半查找。 2. 用单链表表示的有序表可以使用折半查找。 3. 顺序查找的平均查找长度ASL与数据的排列有关。 ( )( )( ) 4. 在任意非空的二叉排序树中，删除某个结点之后，再将该结点插入在二叉排序树中，则所得到的二叉排序树与原二叉排序树相同。 ( ) 5. 哈希表的装载因子越小则发生冲突的可能性越大。 ( ) 6. 二叉排序树中，关键字最小的结点必然无右孩子，关键字最大的结点必然无左孩子。 ( ) 7. 在分块查找、折半查找和顺序查找中，分块查找平均查找长度最大、折半查找平均查找长度最小。 ( ) 8. 顺序查找的方法适合于顺序存储结构而不适合于链接存储结构。 ( ) 9. 前序遍历一棵二叉排序树的结点 , 就可以得到排好序的结点序列。 ( ) 10. AVL树是一棵二叉树，该树上的任意一个结点的平衡因子的绝对值均不大于1。 （ ） 11. 在索引顺序表上实现分块查找，在等概率查找情况下，其平均查找长度不仅与表的个数有关，而且与每一块中的元素的个数有关。 ( ) 12. 对一个堆按层次遍历，不一定能得到一个有序序列。 （ ） 四、综合题 l. 用 C 语言写出顺序查找算法。 2. 用 C 语言写出折半查找算法。 3. 用 C 语言写出分块查找算法。 4. 写出二叉排序树的插入结点的递归算法，并利用插入算法写出建立一个有n个结点的二叉排序树算法。 5. 简述平衡二叉树调整平衡的具体方法。 6. 关键字序列A=(36,27,68,33,97,40,81,24,23,90,32,14)共12个数据，哈希表长为13，采用的哈希函数为：h (key) = key % 13。如果采用开放定址的线性探测再散列方法解决冲突，请构造哈希表并求其平均查找长度。 7. 写出折半查找的递归算法。 8. 编写算法，用折半查找算法在一个有序的顺序表中插入 x 结点，并保持结点的有序性。 9. 编写判定给定的二叉树是否是二叉排序树的算法。 10. 设哈希函数为 h (key)=key % 19，编写一个用链接表解决冲突的哈希表插入函数。 11. 设哈希函数为h (key)=key ，解决冲突的方法是链地址方法，编写一个从哈希表中删除关键字为 key 的一个记录的算法。 33 习题九 一、选择题 1．在所有的排序方法中，关键字比较的次数与记录初始排列秩序无关的是（）。 A．冒泡排序 B．希尔排序 C．直接选择排序 D．直接插人排序 2．从未排序序列中依次取出元素与已经排好序的序列中的元素作比较，将其放入已排序序列的正确位置上，此方法称为（）。 A．插人排序 B．选择排序 C．交换排序 D．归并排序 3．从未排序序列中挑选元素，并将其放人已排序序列的一端，此方法称为（）。 A．插入排序 B．交换排序 C．选择排序 D．归并排序 4．依次将每两个相邻的有序表合并成一个有序表的排序方法称为（）。 A．插人排序 B．交换排序 C．选择排序 D．归并排序 5．当两个元素出现逆序的时候就交换位置，这种排序方法称为（）。 A．插人排序 B．交换排序 C．选择排序 D．归并排序 6．每次把待排序的区间划分为左、右两个子区间，其中左区间中的记录的关键字均 小于等于基准记录的关键字，右区间中记录的关键字均大于等于基准记录的关键字，这种 排序称为（）。 A 插人排序 B．快速排序 C．堆排序 D．归并排序 7．在正常情况下，直接插人排序的时间复杂度为（）。 A．O(log2n) B．O(n) C．O(n log2n) D．O(n2) 8．在正常情况下，冒泡排序的时间复杂度为（）。 A．O(log2n) B．O(n) C．O(nlog2n) D．O(n2) 9．在归并排序中，归并趟数的数量级为（）。 A．O(log2n） B．O(n) C．O(nlog2n) D．O(n2) 10．在归并排序中，每趟需要进行的记录比较和移动次数的数量级为（）。 A．O(log2n） B．O(n) C．O(nlog2n) D．O(n2) 11．归并排序算法时间复杂度为（）。 A．O(log2n） B．O(n) C．O(nlog2n) D．O(n2) 12．平均情况下，快速排序的时间复杂度为（）。 A．O(log2n） B．O(n) C．O(nlog2n) D．O(n2) 13．最坏情况下，快速排序的时间复杂度为（）。 A．O（log2n） B．O(n) 34 C．O(nlog2n) D．O(n2) 14．堆排序中，在每次筛运算中，记录比较和移动次数的数量级为（）。 A．O（log2n） B．O(n) C．O(nlog2n) D．O(n2) 15．堆排序算法时间复杂度为（）。 A．O（log2n） B．O(n) C．O(nlog2n) D．O(n2) 16．设有 800条记录，希望用最快的方法挑选出其中前10个最大的元素，最好选用（）。 A．插人排序 B．快速排序 C．堆排序 D．归并排序 17 在待排序元素基本有序的情况下，效率最高的排序方法是（）。 A．插入排序 B．快速排序 C．堆排序 D．归并排序 18．下面几种排序方法中，要求内存量最大的是（）。 A 插人排序 B．交换排序 C．选择排序 D．归并排序 19．在下列排序方法中，关键字比较的次数与记录的初始排列秩序无关的是（）方法。 A．希尔排序 B．冒泡排序 C．插人排序 D．选择排序 20．快速排序方法在（）情况下最不利于发挥其长处。 A．要排序的数据量大大 B．要排序的数据中含有多个相同值 C．要排序的数据已基本有序 D．要排序的数据个数为奇数 21．下述几种排序方法中，平均情况下占用内存量最大的是（）方法。 A．插人排序 B．选择排序 C．快速排序 D．归并排序 22．若构造一棵具有n个结点的二又树排序，在最坏的情况下，其深度不会超过（）。 A．n/2 B．n C．（n＋l）/2 D．n＋l 二、填空题 1．假设对记录的次关键字进行排序，记录之中有两条记录Ri和Rj，它们的关键字Ki 和 Kj相等，在排序之前记录 Ri在 Rj之前，若排序之后记录 Ri仍在Rj之前，则称排序方法是___________; 相反，若经过某种排序之后 Ri在Rj之后，则称所用的排序方法是____________。 2．根据所排序过程中所用存储器的不同，可以将排序方法分为__________和__________。 3．如果按排序过程中所需要的工作量来分，又可以分为__________、__________ 和__________，其中__________的时间复杂度为 O(n2),__________的时间复杂度为O(nlogn)，__________时间复杂度为O（d·n）。 4．__________的基本思想是：每一趟将一个待排序的记录按其关键字的大小，插入到已经排好序的部分记录之中，使之构成一个新的有序序列，直到所有记录全部插入完成，所有待排记录的关键字都成为一个有序序列。 5．直接插人排序是一种__________．（填是否稳定）的排序算法。 6．希尔排序（Shell’s Sort）又称__________，它是由 D．L．Shell于 1959年提出来的一种改进的插入排序方法。希尔排序属于__________的一种，但比普通的插人排序效率要 35 高。 7．希尔排序是一种__________（填是否稳定）的排序算法. 8．__________是通过两两比较待排序记录的关键字，若发现两个记录关键字的大小次序相反，即进行交换，直到所有记录关键字全部满足排序要求为止。 这种排序方法可以包括有__________和__________两种交换排序方法。 9．__________是通过无序区中相邻记录关键字之间相互比较和交换位置，使之关键字 较小的记录在关键字较大的记录之上，从下标较大的单元逐步向下标较小的位置移动。 10．冒泡排序是一种__________（填是否稳定）的排序算法。 11．快速排序（Quick Soft）又称___________是由霍尔 (Hoare) 提出的的一种对冒泡 排序改进的交换排序。 因其排序速度快，故而称为快速排序。 12．快速排序是一种__________（填是否稳定）的排序算法。 13．__________的基本思想是：每一趟排序在待排序的记录中选关键字最小的记录，依次放在已经排序记录序列的最后，直至全部记录的关键字成为一个有序序列为止。 这种排序方法又可以分为：__________和__________。 14．堆排序的关键是构造堆。R．W．FIOyd提出了一个__________算法来建堆。 15．归并就是将两或两个或两个以上的有序数据序列合并成一个有序数据序列的过程。归并排序有__________和__________，可以用于__________，也可以用于__________，但一般情况下说归并排序都是指__________．它是最简单也是最基础的一种归并排序方法。 16．归并排序是一种__________（填是否稳定）的排序算法。 17.是利用关键字本身的结构，借助于多关键字排序的思想，通过“分配”和“收集”的方法实现排序。 18．基数排序是一种__________（填是否稳定）的排序方法。 19．对于多关键字排序，可以有两种方法。一种称为__________法，简称__________法，另一种方法称为__________法。 20．当排序的记录数量很多，可能出现正序或逆序情况的时候，并且要求排序方法稳定的时候，则要选择__________。 21．直接选择排序算法在最好情况下所作的交换元素的次数为__________。 22．简单选择排序方法所执行的元素交换次数最多为__________。 23．简单选择排序方法在最好的情况下所做的交换元素的次数为__________。 24．冒泡排序方法在最好情况下的元素交换次数为__________。 25．有n个求队参加的足球联赛按主、客场进行比赛，共需进行__________场比赛。 26．在对一组记录（54，38，96，23，15，72，60，45，83）进行直接插入排序若干趟后，当需要把第7个记录60插入到有序表时，为寻找60的插入位置需比较__________次。 27．分别采用选择排序、堆排序、快速排序和归并排序方法对初始状态为递增序列按递增顺序排序，最省时间的是__________排序，最浪费时间的是__________排序。 三、判断题 1．快速排序在所有排序方法中最快，而且所需要的附加空间也最少。 （ ） 2．外部排序是把外存文件调入内存，可利用内部排序方法进行排序，冈此排序所花 费的时间取决于内部排序的时间。 （ ） 3．一般来说，外排序所需要的时问取决于内部排序时间、外存信息读写时间和内部 归井所需要的时间。 （ ） 4．外排序过程主要分为两个阶段：生成初始归并段和对归并段进行逐趟归并的时间 （ ） 5．快速排序方法在任何情况下均可以得到最快的排序效果。 （ ） 36 6．基数排序的设计思想是依照对单个关键字值的比较来实施的。 （ ） 7．用希尔（Shell）排序方法进行排序的时候，关键字越是有序效率越高，关键字越是杂乱则排序效率越低。 （ ） 8．减少初始归并数量，可以使外部排序的时间缩短。 （ ） 9．直接插入排序是一种稳定的排序算法。 （ ） 10．希尔排序是一种稳定的排序算法。 （ ） 11．冒泡排序是一种稳定的排序算法。 （ ） 12．冒泡排序算法的时间复杂度最佳情况下为O(n2)。 （ ） 13．快速排序是一种稳定的排序算法。 （ ） 14．直接选择排序是一种稳定的排序算法。 （ ） 15．堆排序是一种稳定的排序算法。 （ ） 16．快速排序、堆排序和归并排序平均时间复杂度为O(nlog2n)。 （ ） 17．归并排序是一种稳定的排序算法。 （ ） 18．基数排序是一种稳定的排序算法。 （ ） 19．目前归并排序在内部排序和外部排序中都广为使用。 （ ） 20．当排序的记录数量很多，可能出现正序或逆序情况的时候，可以选择堆排序，如果进一步要求排序方法稳定的时候，则要选择归并排序。 （ ） 21．在执行某个排序算法过程中，出现了排序码朝着最终排序序列位置相反方向移动，则该算法是不稳定的。 （ ） 22．二路归并排序的核心操作是将两个有序序列归并为一个有序序列。 （ ） 四、综合题 1．已知一组记录的关键字序列为{41，60，39，72，25，44，90，31}，请写出直接插入排序的每一趟过程。 2．已知一组记录的关键字序列为{36，55，31，28，79，66，12，07，89}，请写出进行冒泡排序的每一趟过程。 3．已知一组记录的关键字序列为{35，27，60，72，50，40，17，81，29，69，30}，请写出以第一个记录为基准记录，一趟快速排序时记录的移动情况。 4．已知一组记录的关键字序列为{76，98，23，65，40，39，52，65，87，11}，请写出直接选择排序的每一趟过程。 5．已知一组记录的关键字序列为{22，96，15，37，10，68，44，85，70，20，11}，请写出用归并排序进行排序的每一趟过程。 6．设计一个函数，实现冒泡排序的双向排序，即每一趟通过每两个相邻的关键字进行比较，产生最小和最大的关键字值的元素。 7．用递归的方法实现一趟归并排序，并写出完整的归并算法。 8．有一种算法称为奇偶转换排序，它的思路是：第一趟对所有的奇数i将a[i]和a[i+l]进行比较，第二趟对所有的偶数的i将a[i]和a[i+l]进行比较，每次比较时，若a[i]＞a［i＋l］，则将二者进行交换，直至所有记录关键字有序。试写出此算法。 37