数据结构习题-带答案-12-13-2讲解

1、习题一一、选择题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、储、加工和处理，_数据_是对能够有效的输人到计算机中并且能够被计算机处理的符号的总称。例如，数学中所用到的整数和实数，文本编辑所用到的字符串等。 2、数据元素是数据的_基本单位_，有些情况下也称为元素、结点、顶点、记录等。3、_数据项_是数据不可分割的最小单元，是具有独立含义的最小标识单位。例如构成一个数据元素的字段、域、属性等都可称之为_数据项_。 4、简而言之，数据结构是数据之间的_相互关系_，即数据的_组织关系_。 5、数据的逻辑结构是指数据之间的_逻辑关系_。逻辑结构是从_逻辑关系_上描述数据，它与具体存储无关，是独立于计算机的。因此逻辑结构可以看作是从具体问题抽象出来的_数学模型_。

3、 6、数据的_存储结构_指数据元素及其关系在计算机存储器内的表示。_存储结构_是逻辑结构在计算机里的实现，也称之为映像。 7、_数据的运算_是指对数据施加的操作。它定义在数据的逻辑结构之上，每种逻辑结构都有一个_数据的运算_。常用的有：查找、排序、插人、删除、更新等操作。 8、数据逻辑结构可以分为四种基本的类型，_集合_结构中的元素除了仅仅只是同属于一个_集合_，不存在什么关系。 9、数据逻辑结构的四种基本类型中，_线性结构_中的元素是一种一对一的关系，这种结构的特征是：若结构是非空集，则有且只有一个开始结点和一个终端结点，并且所有结点最多只能有一个直接前驱和一个直接后继。 10、数据逻辑结构

4、的四种基本类型中，_树型结构_中的元素是一种一对多的关系。 11、图型结构或图状结构是一种_多对多_的关系。在这种逻辑结构中，所有结点均可以有多个前驱和多个后继。 12、有时也可将树型结构、集合和图型结构称为_非线性结构_，这样数据的逻辑结构就可以分为_线性结构_和_非线性结构_两大类。 13、_顺序存储_方式是指逻辑上相邻的结点被存储到物理上也相邻的存储单元中。这种存储结构只存储结点的数值，不存储结点之间的关系，结点之间的关系是通过存储单元的相邻关系隐含的表示出来的。 14、_链接存储_方式是种存储方法，不要求逻辑上相邻的结点在物理上也相邻，即数据元素可以存储在任意的位置上。 15、索引存储

5、方式又可以分为_稠密索引_和_稀疏索引_。若每个结点在索引表中都有一个索引项，则该种索引存储方式称为_稠密索引_；若一组结点在索引表中只对应一个索引项，则索引存储方式称为_稀疏索引_。在_稠密索引中，索引项的地址指示结点所在的位置，而_稀疏索引_中，索引项的地址指示一组结点的起始位置。 16、_散列存储_方式是利用结点关键字的值直接计算出该结点存储单元地址，然后将结点按某种方式存人该地址的一种方法。 17、所谓算法（Algorithm）是对特定问题求解方法和步骤的一种描述，它是指令的一组_有限序列_，其中每个指令表示一个或多个操作。18、算法的_有穷 _性是指算法必须能够在执行有限个步骤之后结

6、束，并且每个步骤都必须在有穷的时间内完成。 19、算法的_确定 _性是指算法中的每一个步骤必须是有明确定义的，不允许有模棱两可的解释，也不允许有多义性。并且，在任何条件下，算法只能有惟一的一条执行路径，即只要输人是相同的就只能得到_相同_的输出结果。 20、算法的_可行_性又称为算法的能行性，是指算法中描述的操作是可以通过已经实现的基本运算执行_有限_次来实现，即算法的_具体实现_应该能够被计算机执行。 21、判断一个算法的好坏主要以下几个标准：_正确性_、_可读性_、_健壮性_、_效率_。 22、算法分析是对一种算法所消耗的计算机资源的估算，其中包括计算机_运行时间_的长短和_所占据空间_的

7、大小。 23、空间复杂度（SPace ComPlexity）也是度量一个算法好坏的标准，它所描述的是算法在运行过程中所占用_存储空间_的大小。三、判断题 1、顺序存储方式只能用于存储线性结构。（）树形 2、数据元素是数据的最小单位。（）数据项 3、算法可以用不同的语言描述，如果用C语言或PASCAL语言等高级语言描述，则算法实际上就是程序了。（） 4、数据结构是带有结构的数据元素的集合。（）5、数据的逻辑结构是指各元素之间的逻辑关系，是用户根据需要而建立的。（） 6、数据结构、数据元素、数据项在计算机中的映像分别称为存储结构、结点、数据域。（） 7、数据的物理结构是指数据在计算机中实际的存储形

8、式。（） 8、具有存取任一元素的时间相等这一特点的存储结构称为随机存取结构。（）四、综合题 1、用大O形式表示下面算法的时间复杂度： for（i=0；im；i十十） for（j=0；jn；j） Aij=i*j； O（mn）S=0S=1S=1+2S=1+2+3.S=1+2+3+.+(m-1)m*(m-1)/2n 2、写出下面算法的时间复杂度： i0； s=0； while(sn） i+; s+=i; O() 3、写出以下算法的时间复杂度： for（i0; im; i）for（j0 ; jt; j） cij=0；for（i=0；im；i） for（j=o; jt; j+） for（k=0；kn；k

9、） cijaik*bkj; O(mnt)。i=1*(3m-1)n3mnO(log3(n)4、写出下面算法的时间复杂度：i=1;while（in） i=i*3; O（log3(n)）5、求下面函数中各条语句的频度和算法的时间复杂度：prime（int n） int i2； while (ni）！=0isqrt(n) ) i+; if（isqrt(n) ) printf（”d is a prime number.n”，n）； else printf（”d is not a prime number.n”，n）； O()6、fact(n) if(n=1) return 1; else return

10、(n*fact(n-1); O（n）习题二一、选择题 1在一个长度为n的顺序表中删除第i个元素（0in）时，需要向前移动( A )个元素。 An-i Bn-i+1 Cn-i+1 Di+12从一个具有n个元素的线性表中查找其值等于x的结点时，在查找成功的情况下，需平均比较( D )个元素结点。 An/2 Bn C(n-1)/2 D(n +1)/2 3对一个具有n个元素的线性表，建立其单链表的时间复杂度为( A )。 AO(n) BO(1) CO(n2） DO（long2n） 4线性表采用链式存储时，其地址( D )。 A 必须是连续的 B一定是不连续的 C部分地址必须连续 D连续与否均可以 5在

11、一个具有n个结点的有序单链表中插人一个新的结点，使得链表仍然有序，该算法的时间复杂度是(D )。 AO（long2n） BO（l） CO（n2） DO（n）6线性表是( A)。 A一个有限序列，可以为空 B一个有限序列，不可以为空 C一个无限序列，可以为空 D一个无限序列，不可以为空7在一个长度为n的顺序表中，向第i个元素（0next=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.

12、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）是线性表的_顺序存储

13、结构_，它是将线性表中的结点按其_逻辑顺序_依次存放在内存中一组连续的存储单元中，使线性表中相邻的结点存放在_地址相邻_的存储单元中。5单链表不要求逻辑上相邻的存储单元在物理上也一定要相邻。它是分配一些_任意_的存储单元来存储线性表中的数据元素，这些存储单元可以分散在内存中的_任意_的位置上，它们在物理上可以是一片连续的存储单元，也可以是_不连续_的。因此在表示线性表这种数据结构时，必须在存储线性表元素的同时，也存储线性表的 逻辑关系。6线性表的链式存储结构的每一个结点（Node）需要包括两个部分：一部分用来存放元素的数据信息，称为结点的_数据域_；另一部分用来存放元素的指向直接后继元素的指针

14、(即直接后继元素的地址信息)，称为_指针域_或_链域_。7线性链表的逻辑关系是通过每个结点指针域中的指针来表示的。其逻辑顺序和物理存储顺序不再一致，而是一种_非顺序_存储结构，又称为_非顺序映像_。8如果将单链表最后一个结点的指针域改为存放链表中的头结点的地址值，这样就构成了_循环链表_。9为了能够快速地查找到线性表元素的直接前驱，可在每一个元素的结点中再增加一个指向其前驱的指针域，这样就构成了_双向链表_。10双向链表某结点的指针P，它所指向结点的后继的前驱与前驱的后继都是_p所指向的结点本身_。11在单链表中，删除指针P所指结点的后继结点的语句是_ P-next=p-next-next _

15、。12在双循环链表中，删除指针P所指结点的语句序列是P-prior-nextp-next及_ P-next-prior=P-prior _。13单链表是_线性表_的链接存储表示。14可以使用_双链表_表示树形结构。15向一个长度为n的向量的第i个元素(lin+1）之前插人一个元素时，需向后移动_n-i+1_个元素。16删除一个长度为n的向量的第i个元素（lin）时，需向前移动_n-i_个元素。17在单链表中，在指针P所指结点的后面插人一个结点S的语句序列是_ S-next=P-next; P-next=S _。18在双循环链表中，在指针P所指结点前插人指针S所指的结点，需执行语句_ p-pri

16、or-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在具有头结点的链式存储结构中

17、，头指针指向链表中的第一个数据结点。( ) 3顺序存储的线性表不可以随机存取。（） 4单链表不是一种随机存储结构。（）5顺序存储结构线性表的插入和删除运算所移动元素的个数与该元素的位置无关。() 6顺序存储结构是动态存储结构，链式存储结构是静态存储结构。（）7线性表的长度是线性表所占用的存储空间的大小。（）数组描述的链表叫静态链表8双循环链表中，任意一结点的后继指针均指向其逻辑后继。（）9线性表的惟一存储形式是链表。（）四、综合题1编写一个将带头结点单链表逆置的算法。void reverse_list( LinkList L)/*逆置带头结点的单链表*/LinkList s, p;p=L-ne

18、xt;/*p指向线性表的第一个元素*/L-next=NULL; /*初始空表*/while ( p != NULL ) s=p;p=p-next;s-next=L-next;L-next=s; /*将s结点插入逆表*/ /*reverse_list*/2ha和hb分别是两个按升序排列的、带头结点的单链表的头指针，设计一个算法，把这两个单链表合并成一个按升序排列的单链表，并用hC指向它的头结点。void mergelist(LinkList *La,LinkList *Lb,LinkList *Lc)LinkList pa,pb,pc;pa=(*La)-next; pb=(*Lb)-next;*

19、Lc= *La ,pc =*La;while (pa&pb)if(pa-datadata) 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，编写一个算法countlist（）计算所有数据域为X的结点的个数（不包括头结点）。int count_list(LinkList L )/*在带头结点的单链表中计算所有数据域为x的结点的个数*/LinkList p;int n;p=L-next; /*p指向链表的第一个结点*/n=0;

20、while (p!=NULL)if (p-data=x)n+;p=p-next;return(n);/*返回结点个数*/ /*count_list*/4在一个带头结点的单链表中，头指针为L，它的数据域的类型为整型，而且按由小到大的顺序排列，编写一个算法insertxlist（），在该链表中插人值为x的元素，并使该链表仍然有序。void insert_list(LinkList L,int x)LinkList p,q,s;p=L-next;q=L;while(p&xp-data)q=p;p=p-next;s=(LinkList)malloc(sizeof(Lnode);s-data=x;s-n

21、ext=p;q-next=s;5在一个带头结点的单链表中，L为其头指针，p指向链表中的某一个结点，编写算法swapinlist（），实现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;els

22、e /*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为其头指针，编写算法deldylist（）将该链表中多余元素值相同的结点删除。void deldy_list(LinkList head)/*在带头结点的非递减有序单链表，将该链表中多余的元素值相同的结点删除*/L

23、inkList q;if (head-next!= NULL)/*判断链表是否为空*/p=head-next;while (p-next != NULL )if ( p-data != p-next-data )p=p-next;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

24、 head, int min, int max )LinkList p, q;q=head;p=head-next;while(p!=NULL) /*结点不空*/if (p-datadata=max) /*不满足删除条件*/q=p;p=p-next;else/*满足删除条件*/q-next=p-next;free(p);p=q-next; /*dellist_maxmin*/8设计一个将双链表逆置的算法invertdbLinkList（），其中头指针为L，结点数据域为data，两个指针域分别为prior和next。void invert_dblinklist(DLinkList head )/

25、不带头结点的双向链表/*将head指向的双链表逆置*/DLinkList p, q;p=head;while( p-next )q=p-next;.p-next=p-prior;p-prior=q;p=q;q=p;p-next=p-prior;p-next=NULL;head=q; /*invert_dblinklist*/习题三一、选择题 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，a 2若一个栈的输人序列是1，2，3，n，输出序列的第一个元素是n，则第k个输出元素是（ C ）。 A

26、k Bn-k-1 Cn-k+1 D不确定3判定一个栈S（最多有n个元素）为空的条件是（B ）。 AS-top！0 BS-top= =0 CS-top!=n DS-top= =n4判定一个栈S（最多有n个元素）为满的条件是（D）。 AS-top!=0 BS-top= =0 CS-top!=n DS-top= =n5向一个栈顶指针为top的链栈中插人一个*S结点的时候，应当执行语句（B）。 Atop-next=S； BS-next=top；top=S； CS-nexttop-next；top-nextS；DS-nexttop；topS-next；6向一个带头结点、栈顶指针为top的链栈中插人一个*

27、S结点的时候，应当执行语句（C）。 Atop-next=S； BS-next=top；top=S； CS-next=top-next；top-next=S； DS-next=top；top=S-next；7判定一个队列Q（最多有n个元素）为空的条件是（ C ）。 AQ-rear-Q-front= =n BQ-rear-Q-front+1= =n CQ-rear = = Q-front DQ-rear +1= = Q-front8判定一个队列Q（最多有n个元素）为满的条件是（A）。 AQ-rear-Q-front= =n BQ-rear-Q-front+1= =n CQ-rear = = Q-f

28、ront DQ-rear +1= = Q-front9判定一个循环队列Q（最多有n个元素）为空的条件是（A）。 AQ-rear = = Q-front BQ-rear = = Q-frontl CQ-front= =(Q-rear +1)n DQ-front= =(Q-rear -1)n10判定一个循环队列Q（最多有n个元素）为满的条件是（ C ）。 AQ-rear = = Q-front BQ-rear = = Q-frontl CQ-front= =(Q-rear +1)n DQ-front= =(Q-rear -1)n11在一个链队列中，假定front和rear分别为头指针和尾指针，则插

29、入一个结点*S的操作是（ C ）。 Afrontfront-next BS-next=rear；rear=S Crear-next=S；rear=S DS-next=front；frontS12在一个链队列中，假定front和rear分别为头指针和尾指针，删除一个结点的操作是（ A ）。 Afront=front-next Brear=rear-next Crear-next=front Dfront-nextrear 13栈与队列都是（ C ）。 A链式存储的线性结构 B链式存储的非线性结构 C限制存取点的线性结构 D限制存取点的非线性结构 14若进栈序列为l，2，3，4，则（ C）不可能是

30、一个出栈序列。 A3，2，4，1 Bl，2，3，4 C4，2，3，1 D4，3，2，l 15在解决计算机主机与打印机之间速度不匹配问题时通常设置一个打印数据缓冲区，主机将要输出的数据依次写人该缓冲区，而打印机则从该缓冲区中取走数据打印。该缓冲区应该是一个（ B ）结构。 A堆栈 B队列 C数组 D线性表二、填空1栈（stack）是限定在_表尾_一端进行插人或删除操作的线性表。在栈中，允许插人和删除操作的一端称为_栈顶_，而另一端称为_栈底_。不含元素的栈称为_空栈_。2在栈的运算中，栈的插人操作称为_进栈_或_入栈_，栈的删除操作称为_退栈_或_出栈_。3根据栈的定义，每一次进栈的元素都在原_

31、栈顶元素_之上，并成为新的_栈顶元素_；每一次出栈的元素总是当前的_栈顶元素_，因此最后进栈的元素总是_最后出栈_，所以栈也称为_后进先出_线性表，简称为_LIFO_表。4栈是一种操作受到限制的线性表，是一种特殊的线性表，因此栈也有_顺序_和_链式_两种存储结构，分别称为_顺序栈_和_链栈_。5当栈满的时候，再进行人栈操作就会产生_溢出_，这种情况的溢出称为_上溢_；当栈空的时候，如果再进行出栈操作，也会_溢出_，这种情况下的溢出称为_下溢_。6栈的链式存储结构简称为_链栈_，是一种_特殊的单链表_。7人们日常计算用到的表达式都被称为_中缀表达式_，这是由于这种算术表达式的运算符被置于两个操作

32、数中间。8计算机中通常使用_后缀表达式_，这是一种将运算符置于两个操作数后面的算术表达式。这种表达式是由波兰科学家谢维奇提出的，因此又称为_逆波兰式_。9队列（Queue）也是一种_特殊的线性表_，但它与栈不同，队列中所有的插人均限定在表的一端进行，而所有的删除则限定在表的另一端进行。允许插人的一端称为_队尾_，允许删除的一端称为_队头_。10队列的特点是_先进先出_，因此队列又被称为_先进先出_的线性表，或称为_FIFO_表。11队列的_顺序存储结构_又称为_数序队列_，是用一组地址连续的存储单元依次存放队列中的元素。12由于队列中的元素经常变化，对于队列的删除和插人分别在队头和队尾进行，因

33、此需要设置两个指针分别指向_队头元素_和_队尾元素_，这两个指针又称为_队头指针_和_队尾指针_。13循环顺序队列（CircuLar Sequence Queue）经常简称为_循环队列_，它是将存储顺序队列的存储区域看成是一个首尾相连的一个环，即将队首和队尾元素连接起来形成一个环形表。首尾相连的状态是通过数学上的_取模运算_来实现的。14在算法或程序中，当一个函数直接调用自己或通过一系列语句间接调用自己的时候，则称这个函数为递归函数，也称为_自调用函数_。函数直接调用自己，则称为_直接递归调用_；当一个函数通过另一个函数来调用自己则称为_间接递归调用_。15在循环队列中规定：当Q-rear=

34、=Q-front的时候循环队列为_空_， 当（Q-rear+1）MAXSIZEfront的时候循环队列为_满_。16用链表方式表示的队列称为_链队列_。17已知栈的输人序列为1，2，3，n，输出序列为a1，a2，an，符合a2= =n的输出序列共有_n-1_个_。18一个栈的输人序列是12345，则栈的输出序列为43512是_不可能_（填是否可能）。19一个栈的输人序列是12345，则栈的输出序列为12345是_可能的_（填是否可能）。20设sq1maxsize为一个顺序存储的栈，变量top指示栈顶元素的位置，则作入栈操作的条件是_top-1next!=NULL_。26已知循环队列用数组dat

35、a1.n存储元素值，用f，r分别作为头尾指针， 则当前元素个数为_(n+r-f）%n_。27在一个循环队列中，队首指针指向 队首元素。28队列中允许进行删除的一端称为_队头_。29链队列实际上是一个同时带有头指针和尾指针的单链表（1n），尾指针指向该单链表的第_n_个元素。30设双向链表链列为lq，lq的头指针为lq.Front，尾指针为lq.Rear，则队列为空的条件是_lq.Front=lq.Rear_。31从循环队列中删除一个元素，其操作是先取出一个元素，后移动_队头指针_。32队列中允许进行插入的一端称为_队尾_。三、判断题1栈和队列都是限制存取点的线性结构。（ ）2不同的人栈和出栈组

36、合可能得到相同输出序列。（ ）3消除递归一定要用栈。（ ）4循环队列是顺序存储结构。（ ）5循环队列不会产生溢出。（ ）6循环队列满的时候rear= =front。（ ）7在对链队列（带头结点）做出队操作时不会改变front指针的值。（）四、综合题1设有4个元素A、B、C和D进栈，给出它们所有可能的出栈秩序。A、B、C、DA、B、D、CA、C、B、DA、C、D、BA、D、C、BB、A、C、DB、A、D、CB、C、A、DB、C、D、AB、D、C、AC、B、A、DC、B、D、AC、D、B、AD、C、B、A2输入n个10以内的数，每输入k（0=k=9），就把它插人到第k号队列中。最后把10个队列中的

37、非空队列按队列序号以从小到大的顺序串接成一条链，并输出该链中的所有元素。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“回文”是指一个字符串从头读到尾和从尾读到头都一样。假设字

38、符串是从输人设备一次一个字节的读人，并且读到字符“”的时候表示结束。请用栈和队列编写一个算法判断一个字符串是否回文。5假设表达式中有三种括号：圆括号“（）”、方括号“ ”和花括号“ ”用C语言编写程序判断读人的表达式中不同括号是否正确配对，假定读人的表达式以”#”结束。6用C语言编写背包问题的算法。背包问题的描述是：假设有n件质量分别为w1，w2，wn的物品和一个最多能装载总质量是T的背包，问能否从这n件物品中选择若干件物品装人背包，并且使被选物品的总质量恰好等于背包所能装载的最大质量，即WxlWx2WxkT。若能，则背包问题有解，否则背包问题无解。7划分子集问题的求解。划分子集问题的实际例子

39、很多，如：某个运动会设立n个比赛项目，每个运动员可以参加一到三个项目，考虑到同一运动员参加的项目不能够在同一时间内进行，则如何安排比赛日程才能使总的日程最短。又如：学校开设m科课程，不同的同学可能选修多门不同的课程，在学期末要进行考试，则如何安排这m科课程的考试才能使考试时间最短而又不冲突。8写出汉诺塔问题的递归和非递归算法。汉诺塔问题描述为：有X、Y和Z三个柱子，n个大小不等且都能套进柱子的圆盘（编号为l、2、n），这n个圆盘已经按照自上至下、由小到大的顺序在其中的一根柱子X上，要求将这些圆盘按照如下规则由X柱子移动到Z柱子：(1) 每次只能移动柱子最上面的一个圆盘。(2) 任何圆盘都不能放

40、在比它小的圆盘之上。(3) 圆盘只能在X、Y和Z三根柱子之上放置。9假设CQ010是一个环形队列，初始状态为front=rear=0，画出做完下列操作后队列的头尾指针的状态变化情况，若不能入队，请指出其元素，并说明理由。(1) d,e,b,g,h入队 (2)d,e出队(3)i,j,k,l,m入队(4)b出队 (5) n,o,p入队习题四一、选择项l空串与空格串（B）。 A相同 B不相同 C可能相同 D无法确定2设有两个申S1与S2，求串S2在S1中首次出现位置的运算称作（ C ）。 A连接 B求子串 C模式匹配 D判子串3串与普通的线性表相比较，它的特殊性体现在（C）。 A顺序的存储结构 B链

41、接的存储结构 C数据元素是一个字符 D数据元素可以任意4设有串S=Computer，则其子串的数目是（ B ）。 (n *（n+1）/2+1) A36 B37 C8 D9二、境空题1串是由零个或多个字符组成的_有限序列_。通常记作：s“c1，c2，cn”(n=0)，其中，S称为_串名_；串中的Ci（1=i=n）可以是字母、数字 字格或其他字符。用双引号括起来的部分是_串值_即串S的内容。2串中字符的个数称为串的_长度_。3不含有任何字符的串称为_空串_，它的长度为_零_。4由一个或多个空格构成的串称为_空格串_，它的长度为_空格的个数_。5串中任意多个连续字符组成的子序列称为该串的_子串_；包

42、含_子串_的串称为主串。6字符在序列中的序号称为该字符在串中的_位置_。 7两个字符串相等是指两个字符串的 值相等 ，也就是说这两个字符串不仅_长度相等_，而且对应位置上的字符也 相等 。 8两个串的比较实际上是_ ASCII码_的比较。两个串从第一个位置上的字符开始进行比较，当第一次出现_ ASCII码_大的串为大，若比较过程中出现一个字符串结束的情况，则另一个串为_较大者_。 9串的_顺序存储_就是把串所包含的字符序列，依次存人连续的存储单元中去。 10有些计算机系统中为了充分利用存储空间，允许一个存储单元可以存放多个字符，串的这种存储方式是一种_紧缩式存储结构_。 11串的_非紧缩式存储结构_是以存储单元为存储单位，一个存储单元中只存放_一个字符_。在这种情况下，即使一个存储单元能存放多个字符，这时候也只存放_一个字符_。 12串在非紧缩方式下，串长度的存储是隐式的，_串所占用的存储单元的个数_即串的长度。 13一些计算机是以字节为存取单位，恰好一个字符占用一个字节，自然形成了每个存储单元存放_一个字符_的分配方式，这种方式就是一种_单字节存储方式_。这种方式一般不需要存放_串长_的存储单元，而需要以程序中各变量值所 不包含 的字符为结束符。