数据结构习题及答案

数据结构习题 习题一 一、选择题

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、索引存储方式又可以分为稠密索引和稀疏索引。若每个结点在索引表中都有一个索引项，则该种索引存储方式称为稠密索引_；若一组结点在索引表中只对应一个索引项，则索引存储方式称为稀疏索引。在稠密索引中，索引项的地址指示结点所在的位置，而稀疏索引中，索引项的地址指示一组结点的起始位置。 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；

while(s＜n） ｛ i++; s+=i;

｝ O(n)

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]; 4、写出下面算法的时间复杂度：

i=1;

while（i＜＝n）

i=i*3; 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(m×n×t)。

O(n)

习题二

一、选择题

1．在一个长度为n的顺序表中删除第i个元素（0＜i

A．n-i B．n-i+1 C．n-i+1 D．i+1

2．从一个具有n个元素的线性表中查找其值等于x的结点时，在查找成功的情况下，需平均比较(C )个元素结点。

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一1＜n＋1）之前捕人一个新元素时，需要向后移动( B )个元素。

A．n-i B．n-i＋1 C．n－i－1 D．i＋1

8．如果某链表中最常用的操作是取第i个结点及其前驱，则采用( D)存储方式最节省时间。

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 )

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．带头结点的双循环链表 二、填空题

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．单链表是线性表的链接存储表示。 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的函数是head(tail(tail((head(tail(head(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 * head ) { /*逆置带头结点的单链表*/ linklist *s, *p; p=head->next; /*p指向线性表的第一个元素*/ head->next=NULL; /*初始空表*/ while ( p != NULL ) { s=p; p=p->next; s->next=head->next; head->next=s; /*将s结点插入逆表*/ }

} /*reverse_list*/

2．ha和hb分别是两个按升序排列的、带头结点的单链表的头指针，设计一个算法，把这两个单链表合并成一个按升序排列的单链表，并用hC指向它的头结点。

linklist *combine_list( linklist *ha,

linklist *hb ) { /*ha, hb分别是两个按升序排列的,带有头结点的单链表的头指针，设计一个算法，把这两个单链表合并成一个按升序排列的单链表,并用hc指向它的头结点*/ linklist *hc, *pa, *pb, *pc, *p, *q, *r; hc=(linklist

*)malloc(sizeof(linklist)); /*建立hc头结点*/ p=hc; pa=ha->next; free(ha); /*释放ha头结点*/ pb=hb->next; free(hb); /*释放hb头结点*/ while (pa!=NULL && pb!=NULL ) { q=(linklist *)malloc (sizeof (linklist)); /*产生新结点*/ if (pb->datadata) { q->data=pb->data; pb=pb->next; } else { q->data=pa->data; pa=pa->next; if (pa->data==pb->data) /*将相同的元素删除*/ { r=pb;

pb=pb->next; free(r); } } p->next=q; /*将结点链入c链表*/ p=q; } while(pa!=NULL) /*a链表非空*/ { q=(linklist *)malloc (sizeof (linklist)); q->data=pa->data; pa=pa->next; p->next=q; p=q; } while(pb!=NULL) /*b链表非空*/ { q=(linklist *)malloc (sizeof (linklist)); q->data=pb->data; pb=pb->next; p->next=q; p=q; } p->next=NULL; return(hc); /*返回*/ }

3．有一个带头结点的单链表，头指针为head，编写一个算法count．list（）计算所有数据域为X的结点的个数（不包括头结点）。

int count_list(linklist *head ) {

/*在带头结点的单链表中计算所有数据域为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*/

head，它的数据域的类型为整型，

而且按由小到大的顺序排列，编写一个算法insertx＿list（），在该链表中

4．在一个带头结点的单链表中，头指针为

linklist *insertx_list(linklist *head, int x) { /*在带头结点的单链表中插入值为x的元素，使该链表仍然有序*/ linklist *s, *p, *q; s=(linklist

*)malloc(sizeof(linklist)); /*建立数据域为x的结点*/ s->data=x; s->next=NULL; if (head->next==NULL || xnext->data ) /*若单链表为空或x小于链表第一个结点的数据域*/ { s->next=head->next;

插人值为x的元素，并使该链表仍然有序

head->next=s; } else { q=head->next; p=q->next; while( p != NULL && x>p->data ) { q=p; p=p->next; } s->next=p; q->next=s; } /*if*/

} /**insertx_list*/ 。

5．在一个带头结点的单链表中，head为其头指针，p指向链表中的某一个结点，编写算法swapin．list（），实现p所指向的结点和p的后继结点相互交换。

linklist *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;

操作的条件是top!=maxsize。

21．设sq[1．．maxsize]为一个顺序存储的栈，变量top指示栈顶元素的位置，如果把栈顶元素弹出并送到X中，则需执行语句x=sq[top]; top=top-1。

22．栈的特性是先进后出。

23．对栈进行退栈时的操作是先取出元素，后移动栈顶指针。 24．设s[1．．max]为一个顺序存储的栈，变量top指示栈顶位置，栈为满的条件是top==max。

25．设链栈的栈顶指针为top，则栈非空的条件是top!=nil 。

26．已知循环队列用数组data[1...n]存储元素值，用f，r分别作为头尾指针， 则当前元素个数为(n+r-f)mod 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号队列中。最后把10个队列中的非空队列按队列序号以从小到大的顺序串接成一条链，并输出该链中的所有元素。

#include #define MAX 10 #define N 100 struct node {

int data;

struct node *next; };

struct hnode {

struct node *link; } queue[MAX]; main() {

int A[N],n,i,first=1; struct node *p,*s,*head; printf(\数值个数n:\ scanf(\

for (i=0;i

for (i=0;i9);

for(i=0;i

{

s=(struct node *)malloc (sizeof (struct node)); /*建立结点*/ s->data=A[i]; s->next=NULL; if (queue[A[i]].link==NULL) /*是相应队列的第一个结点*/ queue[A[i]].link=s;

else /*不是相应队列的第一个结点*/ { p=queue[A[i]].link; while (p->next!=NULL) p=p->next; /*p指向该链表的最后一个结点*/ p->next=s; } }

head=(struct node *)malloc (sizeof (struct node)); /*建立新的总链表头结点*/

head->next=NULL; for (i=0;i

if (first) /*是链入总链表的第一个链表*/

{ head->next = queue[i].link; first=0; p=head; while (p->next!=NULL)

p=p->next; /*p指向最后结点*/ }

else /*不是链入总链表的第一个链表*/

{

p->next=queue[i].link; p=queue[i].link; while (p->next!=NULL) p=p->next; } } }

printf(\显示所有元素:\\n\

if (head->next!=NULL) /*p指向总链表的首结点*/ p=head->next; while (p!=NULL) { printf(\ p=p->next; } }

3．假设用循环单链表实现循环队列，该队列只使用一个尾指针rear，其相应的存储结构和基本操作算法如下：

(l) 初始化队列 initqueue (Q)：建立一个新的空队列 Q。 (2) 人队列enqueue (Q，x)：将元素 x插人到队列 Q中。 (3) 出队列delqueue (Q)：从队列Q中退出一个元素。 (4) 取队首元素gethead (Q)：返回当前队首元素。 (5) 判断队列是否为空：emptyqueue (Q)。 (6) 显示队列中元素：dispqueue (Q)。

/*只有一个指针rear的链式队的基本操作*/ #include

typedef char elemtype;

struct node /*定义链队列结点*/ { elemtype data; struct node *next; };

typedef struct queue /*定义链队列数据类型*/ { struct node *rear; } LinkQueue;

void initqueue(LinkQueue *Q)/*初始化队列*/ {

Q=(struct queue *)malloc(sizeof(struct queue)); Q->rear=NULL; }

void enqueue(LinkQueue *Q,elemtype x) /*入队算法*/ {

struct node *s,*p; s=(struct node *)malloc(sizeof(struct node)); s->data=x;

if (Q->rear==NULL) /*原为空队时*/ { Q->rear=s; s->next=s; }

else /*原队不为空时*/

{

p=Q->rear->next; /*p指向第一个结点*/ Q->rear->next=s; /*将s链接到队尾*/ Q->rear=s; /*Q->rear指向队尾*/ s->next=p; } }

void delqueue(LinkQueue *Q) /*出队算法*/ {

struct node *t; if (Q->rear==NULL) { printf(\队列为空!\\n\ return(0); }

else if (Q->rear->next==Q->rear) /*只有一个结点时*/ { t=Q->rear; Q->rear=NULL; }

else /*有多个结点时*/ { t=Q->rear->next; /*t指向第一个结点*/ Q->rear->next=t->next; /*引成循环链*/

}

free(t); }

elemtype gethead(LinkQueue *Q) /*取队首元素算法*/ {

if (Q->rear==NULL) printf(\队列为空!\\n\ else return(Q->rear->next->data); }

int emptyqueue(LinkQueue *Q) /*判断队列是否为空算法*/ { if (Q->rear==NULL) return(1); /*为空,则返回true*/

else return(0); /*不为空,则返回flase*/ }

void dispqueue(LinkQueue *Q) /*显示队列中元素算法*/ {

struct node *p=Q->rear->next; printf(\队列元素:\ while (p!=Q->rear) { printf(\ p=p->next; }

printf(\}

4．“回文”是指一个字符串从头读到尾和从尾读到头都一样。假设字符串是从输人设备一次一个字节的读人，并且读到字符“＃”的时候表示结束。请用栈和队列编写一个算法判

断一个字符串是否回文。

int isPalindrome( ) { /*回文判定算法*/ InitStack(S); InitQueue(Q); While((c=read())!='#') { push(S,c); /*读入字符分别保存在栈和队列中*/ EnQueue(Q,c); } While( !QmptyStack( S ) && ! EmptyQueue( Q ) ) { if (pop(S) != DelQueue(Q)) /*正序和逆序字符的比较*/ return (FALSE); } if ( !EmptyStack(S) || ! EmptyQueue( Q ) return (FALSE); return( TRUE ); } /*isPalindrome*/

5．假设表达式中有三种括号：圆括号“（）”、方括号“[ ]”和花括号“{ }”用C语言编写程序判断读人的表达式中不同括号是否正确配对，假定读人的表达式以”#”结束。

#include \#include \#define FALSE 0 #define TRUE 1

#define LEN sizeof( struct node ) struct node { char 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 ((symble != '#' ) && (valid ==TRUE) ) { if ( symble !='(' && symble !=')' && symble != '[' && symble != ']' && symble !='{' && symble != '}' ) { symble=getchar(); } else if (symble=='(' || symble=='[' || symble=='{' ) { push_stack(&s, symble ); symble=getchar(); } else if ( s==NULL ) { valid=FALSE; } else { ch=pop_stack(&s); if ( (ch=='(' && symble==')') || (ch=='[' && symble==']') || ch==('{' && symble=='}') ) { valid=TRUE; symble=getchar(); } else valid=FALSE; }

} if ( valid == TRUE ) printf(\ else printf(\}

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 ) { stack tempptr; char popvalue; if (topptr!=NULL ) { tempptr=topptr; popvalue=topptr->data; topptr=topptr->next; free( tempptr ); return popvalue; } else return 0; }

6．用C语言编写背包问题的算法。背包问题的描述是：假设有n件质量分别为w1，w2，?，wn的物品和一个最多能装载总质量是T的背包，问能否从这n件物品中选择若干件物品装人背包，并且使被选物品的总质量恰好等于背包所能装载的最大质量，即Wxl＋Wx2＋?Wxk＝T。若能，则背包问题有解，否则背包问题无解。

#include \

#define NUMBER 20 /*定义物品个数*/ #define TRUE 1 #define FALSE 0

int stack[NUMBER];

int top; void main() { int knapproblem( int, int, int[]); int weight[NUMBER]; /*存放物品质量的数组*/ int n, i; int maxweight; /*包所能承受的最大重量*/ printf(\ scanf(\ printf(\ scanf(\ printf( \ Please input every object's weight :\\n\ for (i=1; i<=n; i++ ) scanf(\if (knapproblem(n, maxweight, weight ) == TRUE ) /*调用背包处理函数*/ { printf(\ printf(\ for ( ;top>0;top-- ) printf(\stack[top],weight[stack[top]]); /*pop stack and print every weight*/ printf(\ } else printf(\} /*main*/

int knapproblem( int n, int maxweight, int weight[] ) /*背包问题处理函数*/ { /*func kanpstack*/ int i=1; top=0; while ((maxweight>0)&&(i<=n)) { if ((maxweight-weight[i]==0) || ((maxweight-weight[i] >0 )&& (i

/*Push No.i stack*/ stack[ ++top ]=i; maxweight = maxweight-weight[i]; } if ( maxweight==0) /*能够装入包中*/ { return( TRUE ); } else if (( i==n )&& (top>0)) /*继续试探*/ { i=stack[top]; top=top-1; maxweight = maxweight+weight[i]; } i++; } /*while*/ return( FALSE ); } /*knapproblem*/

7．划分子集问题的求解。划分子集问题的实际例子很多，如：某个运动会设立n个比赛项目，每个运动员可以参加一到三个项目，考虑到同一运动员参加的项目不能够在同一时间内进行，则如何安排比赛日程才能使总的日程最短。又如：学校开设m科课程，不同的同学可能选修多门不同的课程，在学期末要进行考试，则如何安排这m科课程的考试才能使考试时间最短而又不冲突。

#include \

#define MAX 10 /*元素数目*/

int r[MAX][MAX]; /*存放关系矩阵*/ int n;

int result[MAX]; /*存放分组结果*/

void main() { void division( int [MAX][MAX] ); /*声明划分子集函数*/ int i, j; printf(\ scanf(\ printf(\matrix,1 rash, 0 no rash:\\n\/*输入冲突矩阵,1冲突,0不冲突*/ for ( i=1; i<=n; i++ )

for( j=1; j<=n; j++ ) scanf(\ division(r); /*调用子集划分函数*/ for( i=1; i<=n; i++ ) /*输出分组结果*/ printf(\i, result[i]); }

void division ( int r[MAX][MAX]) { /*子集划分函数*/ int newr[MAX]; /*记录所有以入组的元素发生冲突的元素信息*/ int cq[MAX]; /*循环队列*/ int i, k; int front, rear; /*循环队列头尾指针*/ int group, pre; for (k=0; k<=n-1; k++ ) /*n个元素依此入队列*/ cq[k]=k+1; for ( k=0; k<=n; k++)/*初始状态,均不冲突*/ newr[k]=0; group=1; pre=0; while (( rear != front ) || (rear != 0 )) { front=(front+1)%n; i=cq[front]; if (i

else /*可以分在当前组*/ { result[i]=group; for (k=1; k<=n; k++ ) newr[k]=newr[k]+r[i][k]; /*补充产生冲突的元素*/ } pre=i; }

} /*division*/

8．写出汉诺塔问题的递归和非递归算法。

汉诺塔问题描述为：有X、Y和Z三个柱子，n个大小不等且都能套进柱子的圆盘（编号为l、2、?、n），这n个圆盘已经按照自上至下、由小到大的顺序在其中的一根柱子X上，要求将这些圆盘按照如下规则由X柱子移动到Z柱子：

(1) 每次只能移动柱子最上面的一个圆盘。 (2) 任何圆盘都不能放在比它小的圆盘之上。 (3) 圆盘只能在X、Y和Z三根柱子之上放置。

/*汉诺塔问题的递归算法*/ void move( from, to ) char from, to; { /*汉诺塔移动过程*/ printf(\输出移动过程*/ }/*move*/

void hanoi( n,x,y,z ) /*递归执行过程*/ char x,y,z; int n; { if ( n==1 ) move( x,z ); else { hanoi( n-1,x,z,y ); move( x,z ); hanoi( n-1,y,x,z ); }

}/*hanoi*/

main() { int n; printf(\input the nmmber of diskes:\\n\ scanf(\ printf(\ hanoi( n,'A','B','C' ); }

/*汉诺塔问题的非递归算法*/ #include \struct node { char x; char y; char z; int id;

}stack[30];

main() { int i=1; int n; char s; printf(\ scanf(\ printf(\ if( n==1 ) printf(\ else { stack[1].id=n; stack[1].x='A'; stack[1].y='B'; stack[1].z='C'; do { while( n>1 ) { n--;

i++; stack[i].id=n; stack[i].x=stack[i-1].x; stack[i].y=stack[i-1].z; stack[i].z=stack[i-1].y; } printf(\ printf(\ printf(\ printf(\ printf(\ i--; do { if( i>=1 ) { printf(\ printf(\ printf(\ printf(\ printf(\ } stack[i].id = stack[i].id-1; n=stack[i].id; if( n>=1 ) { s=stack[i].x; stack[i].x = stack[i].y; stack[i].y=s; } if( n==1 ) { printf(\ printf(\ printf(\ printf(\stack[i].z); i--; } }while( (n<=1)&&(i>0) ) }while( i>0 )

} getch(); }

习题四 一、选择项

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’，则其子串的数目是（ A ）。

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算法的最大特点是指示主串的指针不需要回溯。（正确 ）

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；

void replace (stringtype s1[], int i, int j, stringtype s2[]) { stringtype s[100]; int h,k; if ( i<=h && i

2．设计一个算法，测试一个串S是否回文（所谓回文是指从左面读起和从右面读起内容一样）。

int invert(stringtype *s) { /*判断是否回文*/ int i, j; j=length(s)%2; for ( i=0; i

3．写一个递归算法来实现字符的逆序存储，要求不另设存储空间。

SubStr(s,

void reverse ( stringtype *s ) { char c; int i; i=1; printf(\ do { scanf(\ Reverse(s); s.ch[i]=c; i++; }while(c!='#'&&i

4．一个仅由字母组成的字符串s，长度为n，其结构为单链表，每个结点的数据城只存放一个字母。设计一个算法，去掉字符串中所有值为X的字母。

void sjt4( linklist *s, char x ) { linklist *p,*q,*r; int w; p=s; w=1; while ( p!=NULL ) { if ( w==1 ) /*处理第一个结点*/

本文来源：https://www.bwwdw.com/article/09og.html