数据结构 习题课2

习题课2

栈

1．设将整数1，2，3，4依次进栈，但只要出栈时栈非空，则可将出栈操作按任何次序加入其中，请回答下述问题：

(1)若入、出栈次序为push(1),pop(),push(2),push(3),pop(),pop(),push(4),pop(),出栈的数字序列为何(这里push(i)表示进栈pop()表示出栈)？

(2)能否得到出栈序列1423和1432？并说明为什么不能得到或者如何得到。

(3)请分析1，2，3，4的24中排列中，哪些序列是可以通过相应的入出栈操作得到的。 【答案】

（1）1，3，2，4；

（2）不能得到1423序列，因为要得到4必须2，3入栈，才能4入栈，然后4出栈，而这时，只能得到3而不能得到2；能得到1432,依照以下入、出栈序列即可得到：

push(1),pop(),push(2),push(3),push(4),pop(),pop(),pop() 2．链栈中为何不设置头结点？

【答案】栈的操作位置就是栈顶一个位置，不设置头结点，插入、删除更方便。 3．循环队列的优点是什么？如何判别它为空和满？ 【答案】

(1)循环队列结构解决了假溢出问题；

(2)采用少用一个存储单元的策略，让队头指针指向实际队头，队尾指针指向队尾元素的下一个位置。

队空的判定条件：Q->front＝＝Q->rear

队满的判定条件：Q->front＝＝（Q->rear+1）%Queuesize

4．设计长度为n的链队列用单循环链表表示，若只设头指针，则入队、出队的时间为何？若只设尾指针呢？

【答案】 若只设头指针，则出队的时间为O(1),入队时需要扫描整个链表，所用的时间为O(n)；若只设尾指针，则入队、出队的时间均为O(1)。

5．指出下述程序段的功能是什么？ void demo(Seqstack *S) {

int i, arr[64],n＝0;

while (!stackempty(S)) arr[n++]＝pop(S); for (i＝0;i

【答案】程序段的功能是：利用工作数组arr[ ]将栈S中的元素序列逆置。 Seqstack S1,S2,temp; Datatype x;

? //假设已作过初始化

while(!Stackempty(&S1)) {x＝pop(&S1);push(&temp,x);

while(!Stackempty(&temp)) {x＝pop(&temp);push(&S1,x);push(&S2,x);} 【答案】程序段的功能是：利用工作栈temp将栈S1复制到栈S2。 (3) void demo2(Seqstack *S,int m) { Seqstack T; int i;

Initstack(&T);

while (!stackempty(S))

if (i＝pop(S))!＝m) push(&T,i) ;

while(!Stackempty(&T)) {i＝pop(&T);push(S,i);} }//demo2

【答案】程序段的功能是：利用工作栈t将栈S中的值为m的元素滤掉。 (4) void demo3(CirQueue *Q) { int x; Seqstack S; Initstack(&S);

while (!QueueEmpty(Q)){x＝Delqueue(Q); push(&S,x) ;} while(!Stackempty(&S)) {x＝pop(&S);Enqueue(Q,x);} }//demo3

【答案】见同步练习题。 CirQueue Q1,Q2; int x,i,m＝0;

??//假设Q1已有内容Q2已作过初始化

while (!QueueEmpty(&Q1)){x＝Delqueue(&Q1); Enqueue(Q2,x);m++ ;}

for (i＝0;i

【答案】算法如下： int revers(char t[ ]) {Seqstack *S; char ch; int k,n; Initstack(S) n＝strlen(t);

for(k＝0;k

while (!stackempty(S)) {ch＝pop(S);

if (ch＝＝t[k]) k++; else return 0; }

retuen 1; }

7．利用栈的基本操作，写一个将栈S中所有元素均出栈的算法void Clearstack(Seqstack *S)，并说明S为何要作为指针参数？

【答案】算法如下：

void Clearstack(Seqstack *S) {while(!stackempty(S))

pop(S); }

说明：出栈操作为加工型操作，需要将操作后的结果带回主调程序段，所以S要作为指针参数。

8．利用栈的基本操作，写一个返回栈S中结点个数的算法int stacksize(Seqstack S)，并说明S为何不用作为指针参数？

【答案】算法如下：

int stacksize(Seqstack S) {

return S.top+1; }

说明：统计结点个数操作为引用型操作，栈S的内容没有被修改，所以S不用作为指针参数。由于C语言数组下标从0开始，故结点个数为S.top+1。

9．设计算法判断一个算术表达式的圆括号是否正确配对 。 （提示：凡遇‘（‘就进栈，遇‘）’就退掉栈顶的‘（‘，表达式扫描完毕，栈应为空）

int bracketsmatch(char a[ ])

{//设算术表达式以字符串形式存储在数组中 Seqstack *S; Initstack(S); int k＝0;

while(a[k]!＝’\\0’)

if (a[k]＝＝＇(＇) Push(S,＇(＇); else if (a[k]＝＝＇)＇)

if (Stackempty(S)) return 0; else Pop(S);

if (Stackempty(S)) return 1; else return 0; } 10．一个双向栈S是在同一向量空间里实现的两个栈，它们的栈底分别设在向量空间的两端。试为此双向栈设计初始化Initstack(S)、入栈push(S,x,i)和出栈pop(i)算法，其中，i为0或1用于指示栈号。

【答案】

#defin maxsize 100 typedef struct node { datatype data[maxsize]; int top1,top2; }Seqstack;

（1）双向栈的初始化

viod Initstack(Seqstack *S) {

S->top1＝-1;S->top2＝maxsize; }

（2）双向栈入栈算法

viod push(Seqstack *S,datatype x,int i)

{if (S->top1+1＝＝S->top2) erroe(overflow); else

if(i＝＝0) {S->top1++;

S->data[S->top1]＝x;} else

{S->top2--;

S->data[S->top2]＝x;} }

（3）双向栈出栈算法

datatype pop(Seqstack *S,int i) {if (i＝＝0)

if(S->top1＝＝-1) error(downflow); else

{return S->data[S->top1]} else

if (S->top2＝＝maxsize) error(downflow ); else

return S->data[S->top2]; }

11．Ackerman函数的定义如下：

n+1 当m＝0 时 AKM(m,n)＝ AKM(m-1,1) 当m≠0,n＝0时 AKM(m-1,AKM(m,n-1)) 当m≠0, n≠0时 请写出递归算法。 【答案】算法如下： int akm(int n,int m) {if(m＝＝0) return n+1;

else if (n＝＝0&&m!＝0) return akm(m-1,1); else

return akm(m-1,akm(m,n-1)); }

12．用第二种方法，既少用一个元素空间的方法来区别循环队列的空和满，试为其设计置队空、判断队空、判断队满、出队、入队、取队头元素等六个基本操作的算法。

【答案】算法如下： #defin maxsize 100

typedef struct node { datatype data[maxsize]; int front,rear;

}Seqqueue;

（1） 置队空操作

void Initqueue(Seqqueue *Q) {Q->front＝0; Q->rear＝0; }

（2） 判断队空操作

int Queueempty(Seqqueue Q) {

return O.front＝＝Q.rear ; }

（3）判断队满操作

int Queuefull(Seqqueue Q) {

return O.front＝＝(Q.rear+1) %maxsize; }

（4）出队操作

datatype delquequ(Seqqueue *Q) {datatype temp;

if(O->front＝＝Q->rear) error(＂downflow＂); temp＝Q->data[Q->front];

Q->front＝(Q->front+1)%maxsize; return temp; }

（5）入队操作

void enqueue(Seqqueue *Q,datatype x) {if (Q->front＝＝(Q->rear+1)%maxsize) error(＂overflow＂); Q->data[Q->rear]＝x;

Q->rear＝(Q->rear+1)%maxsize; }

（6）取队头操作

datatype delquequ(Seqqueue *Q) {datatype temp;

if(O->front＝＝Q->rear) error(＂downflow＂);

return Q->data[Q->front]; }

13．假设以带头结点的循环链表表示队列，并且只是一个指针指向队尾元素结点，试编写相应的置队空、判断队空、出队和入队等算法。

typedef struct node { datatype data;

struct node *next; }Linknode;

typedef struct { Linknode *rear; }Linkqueue; （1） 置队空操作

void Initqueue(Linkqueue *Q)

{ Q->rear＝(linknode*)malloc(sizeof(Linknode)) Q->rear->next＝Q->reqr; }

（2） 判断队空操作

int Queueempty(Seqqueue Q) {

return Q.rear->next＝Q.reqr ; }

（3）出队操作

datatype delquequ(Linkqueue *Q) {datatype temp; Linknode *p;

if(O->rear->next＝＝Q->rear) error(＂downflow＂); p＝Q->rear->next->next; temp＝p->data;

Q->rear->next->next＝p->next;

if (p＝＝Q->rear) Q->rear＝Q->rear->next; free(p); return temp; }

（4）入队操作

void enqueue(Linkqueue *Q,datatype x) {Linknode *p;

p＝(Linknode*)malloc(sizeof(Linknode)); p->data＝x;

p->next＝Q->rear->next; Q->rear->next＝p; Q->rear＝p; }

14．对于循环向量中的循环队列，写出求队列长度的公式。 【答案】循环队列求队列长度的公式为： (Q.rear-Q.front+maxsize)%maxsize 15．假设循环队列中只设rear和quelen来分别指示队尾元素的位置和队中元素的个数，试给出循环队列的队满条件，并写出相应的入队和出队算法，要求出队时需返回队头元素。

【答案】

（1）队满条件：Q.quelen＝＝maxsize （2）入队算法：

void enqueue(cirqueue *Q,datatype x) {if (O->quelen＝＝maxsize) error(＂overflow＂);

Q->rear＝(Q->reae+1)%maxsize; Q->data[Q->rear]＝x; }

（3）出队算法：

datatype delqueue(cirqueue *Q) {datatype x; if (O->quelen＝＝0) error(＂downflow＂);

x＝Q->data[(Q->reae+maxsize-Q->quelen+1)%maxsize]; Q->quelen--; return x; }

串

一、选择题

1． 下所述中正确的是（ ）〖2001〗

A． 串是一种特殊的线性表 B． 串的长度必须大于零 C． 串中元素只能是字母 D． 空串就是空白串 〖答案〗A

2．若目标串的长度为n，模式串的长度为[n/3]，则执行模式匹配算法时，在最坏情况下的时间复杂度是（ ）〖2001〗

A．O(n/3) B．O(n) C．O(n2) D．O(n3)

〖分析〗最坏情况下模式匹配的时间复杂度为O((n-[n/3]+1)*[n/3]),由于n和[n/3]是同阶的，所以，时间复杂度可写为O(n2)。 〖答案〗C

3．设有两个串T和P，求P在T中首次出现的位置的串运算称作（ ）〖2003〗 A．联接 B．求子串 C．字符定位 D．子串定位 〖分析〗该题考核点是串的基本操作。 〖答案〗D

4．为查找某一特定单词在文本中出现的位置，可应用的串运算是（ ） 〖2002〗 A．插入 B．删除 C．串联接 D．子串定位 〖答案〗D

5．已知函数Sub(s,i,j)的功能是返回串s中从第i个字符起长度为j的子串，函数Scopy(s,t)的功能为复制串t到s。若字符串S=\，则调用函数Scopy(P,Sub(S,1,7))后得到( )〖2002〗 A．P=\ B．P=\ C．S=\ D．S=\

〖分析〗该题考核点是串的基本操作，函数Scopy(P,Sub(S,1,7))将串中子串″SCIENCE″复制到P中，而串S值未变。正确答案为A。 〖答案〗A

二、填空题

6．在串S=\中，以t为首字符的子串有 个。〖2001〗 〖分析〗该题考核点是子串的概念。其中存在两个长度为1的子串。 〖答案〗12

7．串S=\I am a worker\的长度是________。〖2002〗

〖分析〗该题考核点是串长度的概念。 〖答案〗13

8．设S1=\\，则S1，S2和S3依次联接后的结果是____________。〖2003〗

〖分析〗该题考核点是串的连接操作及空白串的概念。 〖答案〗\book\ 三、算法阅读题

9．下列算法的功能是比较两个链串的大小，其返回值为： -1 s1

1 s1>s2

请在空白处填入适当的内容。〖2001〗 int comstr(linkstring s1,linkstring s2)

{//s1和s2为两个链串的头指针 while(s1&&s2) {

if(s1->datadata) return –1; if(s1->data>s2->data) return 1; ① ② }

if( ③ ) return –1; if( ④ ) return 1; ⑤ ; }

〖分析〗该题考核点是串的比较操作。While型循环通过指针s1、s2将两个串中字符逐一比较，若发现不等字符，则不等字符的大小就是两个串的大小；若所比较字符均相等，直到有串被扫描完为止，退出循环。然后判断，若某个串未被扫描完，则其值大，若两个串同时被扫描完，则两个串相等。

〖答案〗① s1=s1->next; ② s2=s2->next; ③ s2(或s2!=NULL) ④ s1(或s1!=NULL) ⑤ return 0

同步练习题

一、 选择题

1．下列有关字符串的描述，正确的是（ ）

A. B. C. D.

字符串是0个或多个字符构成的有限序列； 字符串是0个或多个字母不同的有限序列； 字符串中最少要有一个子符； 字符串中不能有空格字符。

2． 字符串S=＂string＂中，包含的子串的个数是（ ）

A. 20 B. 21 C. 22 D. 23

3．目标串为T=＂this is a string＂,模式串P=＂string＂,进行模式匹配，有效位移是（ ）（起始位置为0）。 A. 9 B. 10 C. 11 D. 12 4．已知串S= ＂string＂，T=＂this＂,执行运算strlen(strcopy(S,T))的结果是（ ） A. 4 B. 6 C. 10 D. 2

5．目标串为T=＂this is a string＂,模式串P=＂string＂,进行模式匹配，所有的无效位移数是（ ） A. 6 B. 10 C. 16 D. 11 6．下列命题正确的是（ ）

A. 空串就是空白串； B. 空串不是串；

C. 空串是长度为0的字符串 D. 串相等指的是长度相等

7．若字符串采用链式存储，每个字符占用一个字节，每个指针在占用四个字节，则该字符串的存储密度为（ ）

A. 50% B. 25% C. 75% D. 20%

8．当目标串的长度为n，模式串的长度为m时，朴素的模式匹配算法最坏情况下字符的比较次数（ ） A . n B. n*m C. (n-m+1)*m D. m

9．当目，模式串的长度为m时，朴素的模式匹配算法最好情况下字符的比较次数（ ） A. n B. m C. n+m D n-m 10．字符串是一种特殊的线性表，它与一般线性表的区别是（ ）

A. 字符串是一种线性结构； B. 字符串可以进行复制操作；

C. 字符串由字符构成并且通常作为整体参与操作；

D. 字符串可以顺序存储也可以链式存储。

二、填空题

1．空串的长度为 ，空格串（空白串）的长度为 。

2．子串的定位运算又称为 ，通常把主串又称为 子串又称为 。 3．成功匹配的起始位置称为 ，匹配失败的起始位置称为 。 4．设目标串为T=＂abccdadeef＂，模式串P=＂ade＂，则第 趟匹配成功。 5．已知串T=＂abccdadeef＂，P=＂abccyde＂,函数strcmp(T,P)的运算结果是 。 6．串朴素的模式匹配算法在顺序串和链串上运行，时间复杂度 。 7． 已知串T=＂abccdadeef＂,T中包含以b打头的子串有 个。 8．通常在程序设计中，串分为 和 。 9．按存储结构通常分为 和 。

10．设s1=＂GOOD＂,s2=＂ ＂ ,s3=＂BYE!＂，则s1,s2,和s3连接后的结果是 。

三．阅读程序题

1． 指出程序功能

int stringcmp(Hstring S,Hstring T) {int i=0,tag=1;

if (S.length!=T.length) tag=0; else

while(i

if (S.ch[i]==T.ch[i]) i++; else tag=0;

return tag; }

2．阅读程序

int stringpatindex (Hstring S,Hstring T) {int i,j,k;

for(i=0;i

{for(j=i,k=0;k

break;

if(k>=T.length) return i; } return –1; }

（1）指出程序功能；

（2）设S中存储＂there are a string＂ ，T中存储＂??r＂函数的返回值是什么？ 3．阅读程序指出程序功能 void restring(Hstring S) {char *p,*q,c;

p=S.ch;q=S.ch+S.length-1; while(p

p++;q--; }

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