3,4数据结构作业

第三章

3.5 假设以S和X分别表示入栈和出栈的操作，则初态和终态均为空栈的入栈和出栈的操作序列可以表示为仅由S和X组成的序列。称可以操作的序列为合法序列（例如，SXSX为合法序列，SXXS为非法序列）。试给出区分给定序列为合法序列或非法序列的一般准则，并证明：两个不同的合法（栈操作）序列（对同一输入序列）不可能得到相同的输出元素（注意：在此指的是元素实体，而不是值）序列。

解：

一般准则：任何前n个序列中S的个数一定大于或等于X的个数且整个序列中S的个数一定等于X的个数。

证明：设两个合法序列为：

T1=S……X……S……

T2=S……X……X……

假定前n个操作都相同，从第n+1个操作开始，为序列不同的起始操作点。由于前n 个操作相同，故此时两个栈（不妨为栈A、B）的存储情况完全相同，假设此时栈顶元素均为a。

第n+1个操作不同，不妨T1的第n+1个操作为S，T2的第n+1个操作为X。T1为入栈操作，假设将b压栈，则T1的输出顺序一定是先b后a；而T2将a退栈，则其输出顺序一定是先a后b。由于T1的输出为……ba……，而T2的输出顺序为……ab……，说明两个不同的合法栈操作序列的输出元素的序列一定不同。

3.9 试将下列递推过程改写为递归过程。

void ditui(int n)

{

int i;

i = n;

while(i>1)

cout<

}

解：

Void digui(int n){

if (n==2) printf(“%d”,n);

else {

printf(“%d”,n); digui(n-1);}

}

3.10 试将下列递归过程改写为非递归过程。

void test(int &sum)

{

int x;

cin>>x;

if(x==0) sum=0;

else

{

test(sum);

sum+=x;

}

cout<

}

解：

void test(int & sum){

sqstack s;

int x;

scanf("%d",&x);

initstack(s);

while(x!=0){

*s.front++=x;

scanf("%d",&x);

}

sum=0;

int e;

printf("%d",sum);

while(s.front!=s.base){

e=*(--s.front);

sum+=e;

printf("%d",sum);

}

}

3.15 假设以顺序存储结构实现一个双向栈，即在一维数组的存储空间中存在着两个栈，它们的栈底分别设在数组的两个端点。试编写实现这个双向栈tws的三个操作：初始化inistack(tws)、入栈push(tws,i,x)和出栈pop(tws,i)的算法，其中i为0或1，用以分别指示设在数组两端的两个栈，并讨论按过程(正/误状态变量可设为变参)或函数设计这些操作算法各有什么有缺点。

解：

程序源代码：

#include

#include

#define STACK_INIT_SIZE 100

#define TURE 1

#define FALSE 0

#define ok 1

#define error 0

#define INFEASIBLE -1

typedef int selemtype ;

typedef int status;

typedef struct{

int * base[2];

selemtype * top[2];

int stacksize;

}sqstack;

status INITstack(sqstack * s){

int * p;

p=(selemtype *) malloc (STACK_INIT_SIZE * sizeof(selemtype));

(*s).base[0]=(*s).top[0]=p;

(*s).base[1]=(*s).top[1]=p+STACK_INIT_SIZE-1;

if(!(*s).base[0]) exit(-2);

if(!(*s).base[1]) exit(-2);

return ok;

}

status Push(sqstack * s,int i,selemtype e){

if(i==0){

if ((*s).top[0]>=((*s).base[0]+(STACK_INIT_SIZE/2)-1)) return error;

else *(*s).top[0]++=e;

return ok;

}

if(i==1){

if((*s).top[1]<=((*s).base[1]-(STACK_INIT_SIZE/2)+1)) return error;

else *(*s).top[1]--=e;

return ok;

}

return error;

}

status Pop(sqstack * s,int i,selemtype * e){

if(i==0&&(*s).top[0]==(*s).base[0]) return error;

if(i==1&&(*s).top[1]==(*s).base[1]) return error;

if(i==0) {

*e=*(--(*s).top[0]);

return ok;

}

if(i==1) {

*e=*(--(*s).top[1]);

return ok;

}

}

void main()

{

sqstack sta;

selemtype e;

selemtype * p;

int i;

if(INITstack(& sta)) printf("双栈已被创建\n");

printf("请输入进栈端(0/1)及进栈元素：\n");

scanf("%d %d",&i,&e);

if(Push(&sta,i,e)) printf("元素已入栈\n");

printf("请输入进栈端(0/1)及进栈元素：\n");

scanf("%d %d",&i,&e);

if(Push(&sta,i,e)) printf("元素已入栈\n");

printf("请输入进栈端(0/1)及进栈元素：\n");

scanf("%d %d",&i,&e);

if(Push(&sta,i,e)) printf("元素已入栈\n");

printf("左端栈元素：");

p=sta.base[0];

while(sta.top[0]!=p){

printf("%d ",*p);

p++;

}

printf("右端栈元素：");

p=sta.base[1];

while(sta.top[1]!=p){

printf("%d ",*p);

p--;}

printf("\n请输入出栈端(0/1)：\n");

scanf("%d",&i);

if(Pop(&sta,i,&e)) printf("\n栈顶元素 %d 出栈\n",e); printf("左端栈元素：");

p=sta.base[0];

while(sta.top[0]!=p){

printf("%d ",*p);

p++;}

printf("右端栈元素：");

p=sta.base[1];

while(sta.top[1]!=p){

printf("%d ",*p);

p--;

}

}

运行结果：

3.21 假设表达式有单字母变量和双目四则运算符构成。试写一个算法，将一个通常书写形式且书写正确的表达式转换为逆波兰表达式。

解：

程序源代码：

#include

#include

#define SIZE 100

typedef char selemtype ;

typedef struct{

selemtype * base;

selemtype * top;

int size;

} stack;

int Prior(char c1,char c2)

{

char ch[5]="#+-*/";

int i=0,j=0;

if(c1=='(') return 0;

while(ch[i] && ch[i]!=c1) i++;

if(i==2) i--; // 加和减可认为是同级别的运算符

if(i==4) i--; // 乘和除可认为是同级别的运算符

while(ch[j] && ch[j]!=c2) j++;

if(j==2) j--;

if(j==4) j--;

if(i>j) return 1;

else return 0;

}

void main(){

stack sta;

char ch=0,ct;

sta.base=(selemtype *)malloc(SIZE*sizeof(selemtype));

if(!sta.base ) exit(0);

sta.top=sta.base;

sta.size=0;

*sta.top++='#';

printf("please enter the expression:\n");

while(ch!='#'&&*sta.base=='#'){

ch=getchar();

if('a'<=ch&&ch<='z') printf(" %c ",ch);

else

if(ch=='#') {

ct=*(--sta.top);

while(ct!='#')

{printf(" %c ",ct);

ct=*(--sta.top);}

--sta.top;

}

else

if(ch=='(') *sta.top++=ch;

else

if(ch==')') {

ct=*(--sta.top);

while(ct!='(')

{printf(" %c ",ct);

ct=*(--sta.top);

}

}

else {

ct=*(sta.top-1);

if(Prior(ct,ch)==0) *sta.top++=ch;

else{

ct=*(--sta.top);

while(Prior(ct,ch))

{printf(" %c ",ct);

ct=*(--sta.top);}

*(++sta.top)=ch;

++sta.top;

}

}}}

运行结果：

3.22 如题3.21的假设条件，试写一个算法，对以逆波兰式表示的表达式求值。

解：

程序源代码：

#include

#include

#define max_size_stack 100

#define incre 10

#define ok 1

#define error -100

typedef int elemtype2;

typedef int status;

typedef struct{

elemtype2 * top;

elemtype2 * base;

int size;

}stack2;

status initstack2(stack2 & da){

da.base=(elemtype2*)malloc(max_size_stack*sizeof(elemtype2));

if(!da.base) cout<<"操作失败，程序执行无效!!!!!!"<

da.top=da.base;

da.size=max_size_stack;

return ok;

}

status pop2(stack2 & da, elemtype2 & e){

if(da.base==da.top) return error;

e=*(--da.top);

return ok;

}

status push2(stack2 & da,elemtype2 e){

if(da.top-da.base>=da.size) {

da.base=(elemtype2

*)realloc(da.base,(da.size+incre)*sizeof(elemtype2));

if(!da.base) cout<<"操作失败，程序执行无效!!!!!!"<

da.top=da.base+da.size;

da.size+=incre;

}

*da.top++=e;

return ok;

}

int coun(elemtype2 e1,elemtype2 e2,char cch){

switch(cch){

case '+': return e1+e2;

case '-': return e1-e2;

case '*': return e1*e2;

case '/': if(e2==0) return error;else return e1/e2;

case '#': return ok;break;

default: return error;

}

}

void main(){

char cch;

int i,count=0,e1,e2;

stack2 da;

initstack2(da);

cout<<"请输入表达式的逆波兰式：(#表结束)"<

for(cch='1',i=0;cch!='#'&&i<20;i++){

cin>>cch;

if(cch!='+'&&cch!='-'&&cch!='*'&&cch!='/'&&cch!='#')

push2(da,cch-48);

else if(cch!='#'){

pop2(da,e2);pop2(da,e1);

if(coun(e1,e2,cch)==-100) {

cout<<"表达是不合法："<

cout<<"操作失败，程序执行无效!!!!!!"<

}

else

push2(da,coun(e1,e2,cch));

}

else{

pop2(da,e1);

cout<<"表达式的值为："<

}

}

}

运行结果：

3.14 若以1234作为双端队列的输入序列，试分别求出满足以下条件的输出序列：

(1) 能由输入受限的双端队列得到，但不能由输出受限的双端队列得到的输出序列。

(2) 能由输出受限的双端队列得到，但不能由输入受限的双端队列得到的输出序列。

(3) 既不能由输入受限的双端队列得到，也不能由输出受限的双端队列得到的输出序列。

解：

1,2,3,4

4和2不可相连

1,2,3,4

1和2不可分开

4在1,3或2,3之间

由上分析可知：

输出受限不可得到：

1243，3412，1342，1432，3142，4132，1324，1423，

2143，3421，2341，2431，3241，4231，2314，2413．

输入受限不可得到：

1243，3241，

1423，3421

3.29 如果希望循环队列中的元素都能得到利用，则需设置一个标志域tag，并以tag的值为0和1来区分，尾指针和头指针值相同时的队列状态是“空”还是“满”。试编写与此结构相应的入队列和出队列的算法，并从时间和空间角度讨论设标志和不设标志这两种方法的使用范围（如当循环队列容量较小而队列中每个元素占的空间较多时，哪一种方法较好）。解：

程序源代码：

#include

#include

#define maxqsize 5

#define ok 1

#define error 0

typedef int qelemtype;

typedef int status;

typedef struct{

qelemtype * base;

int front;

int rear;

int tag;

}squeue;

status initqueue(squeue & sq){

sq.base=(qelemtype*)malloc(maxqsize*sizeof(qelemtype));

if(!sq.base) exit(-2);

sq.front=sq.rear=0;

sq.tag=0;

return ok;

}

status enqueue(squeue & sq,qelemtype e){

if(sq.rear==sq.front&&sq.tag) return error;

sq.base[sq.rear]=e;

sq.rear=(sq.rear+1)%maxqsize;

if(sq.rear==sq.front) sq.tag=1;

return ok;

}

status dequeue(squeue & sq,qelemtype & e){

if(sq.rear==sq.front&&!sq.tag) return error;

e=sq.base[sq.front];

sq.front=(sq.front+1)%maxqsize;

if(sq.tag==1) sq.tag=0;

return ok;

}

void main(){

squeue sq;

qelemtype e;

int i;

initqueue(sq);

cout<<"请输入队列元素："<

cin>>e;

if(enqueue(sq,e)) cout<<"元素已插入"<

cout<<"请输入队列元素："<

cin>>e;

if(enqueue(sq,e)) cout<<"元素已插入"<

cout<<"请输入队列元素："<

cin>>e;

if(enqueue(sq,e)) cout<<"元素已插入"<

if(dequeue(sq,e)) cout<<"队头元素:"<

cout<<"队列中元素为："<

for(;dequeue(sq,e);)

cout<

cout<

}

运行结果：

3.30 假设将循环队列定义为:以域变量rear和length分别指示循环队列中队尾元素的位置和内含元素的个数。试给出此循环队列的队满条件，并写出相应的入队列和出队列的算法（在出队列的算法中要返回队头元素）。

解：

程序源代码：

#include

#include

#define max 3

#define ok 1

#define error 0

typedef int status;

typedef int selemtype;

typedef struct{

selemtype * base;

int rear;

int length;

}squeue;

status initqueue(squeue & sq){

sq.base=(selemtype *)malloc(max*sizeof(selemtype));

if(!sq.base) exit(-2);

sq.rear=0;

sq.length=0;

return ok;

}

status enqueue(squeue & sq,selemtype e){

if(sq.length>=max) return error;

sq.base[sq.rear]=e;

sq.rear=(sq.rear+1)%max;

sq.length++;

return ok;

}

status dequeue(squeue & sq,selemtype & e){

if(sq.length<=0) return error;

e=sq.base[(sq.rear+max-sq.length)%max];

sq.length--;

return ok;

}

void main(){

squeue sq;

selemtype e;

initqueue(sq);

cout<<"请输入队列元素："<

cin>>e;

if(enqueue(sq,e)) cout<<"元素已插入"<

else cout<<"队列已满元素未被插入"<

cout<<"请输入队列元素："<

cin>>e;

if(enqueue(sq,e)) cout<<"元素已插入"<

else cout<<"队列已满元素未被插入"<

cout<<"请输入队列元素："<

cin>>e;

if(enqueue(sq,e)) cout<<"元素已插入"<

else cout<<"队列已满元素未被插入"<

cout<<"请输入队列元素："<

cin>>e;

if(enqueue(sq,e)) cout<<"元素已插入"<

else cout<<"队列已满元素未被插入"<

if(dequeue(sq,e)) cout<<"队头元素:"<

cout<<"队列中元素为："<

for(;dequeue(sq,e);)

cout<

cout<

}

运行结果：

3.31 假设称正读和反读都相同的字符序列为“回文”，例如，…abba?和…abcba?是回文，…abcde?和…ababab?则不是回文。试写一个算法判别读入的一个以…@?为结束符的字符序列是否是“回文”。

解：

程序源代码：

#include

#include

#define max 10

typedef char elemtype;

typedef struct{

elemtype * base;

int front;

int rear;

}squeue;

void main(){

squeue sq;

char e1=0,e2=0,ch;

int i,n;

sq.base=(elemtype *)malloc(max*sizeof(elemtype));

sq.front=sq.rear=0;

cout<<"请输入字符序列："<

while(ch!='@'&&(sq.rear+1)%max!=sq.front){

cin>>ch;

sq.base[sq.rear]=ch;

sq.rear=(sq.rear+1)%max;

}

if(sq.base[sq.rear-1]=='@') sq.rear--;

if((sq.rear+1)%max==sq.front)

cout<<"队列已满"<

n=(sq.rear-sq.front+1);

for(i=1;i<=n/2&&e1==e2;i++){

e1=sq.base[sq.front+i-1];

e2=sq.base[sq.rear-i];

}

if(i>=n/2&&e1==e2) cout<<"该字符序列为回文"<

else cout<<"该字符序列不为回文"<

}

运行结果：

3.34 假设在如教科书3.

4.1节中图3.9所示的铁道转轨网的输入端有n节车厢：硬座、硬卧和软卧（分别以P,H和S表示）等待调度，要求这三种车厢在输出端铁道上的排列次序为：硬座在前，软卧在中，硬卧在后。试利用输出受限的双端队列对这n节车厢进行调度，编写算法输出调度的操作序列：分别以字符…E?和…D?表示对双端队列的头端进行入队列和出队列的操作；以字符A表示对双端队列的尾端进行入队列的操作。

解：

程序源代码：

#include

#include

#define max 10

#define ok 1

#define error 0

typedef int status;

typedef int elemtype;

typedef struct{

elemtype * base;

int front ;

int rear ;

int tag;

}xqueue;

status initqueue(xqueue & sq){

sq.base=(elemtype *)malloc(max *sizeof(elemtype));

if(!sq.base) exit(-2);

sq.front=sq.rear=0;

sq.tag=0;

return ok;

}

status enqueue(xqueue & sq,elemtype e){

elemtype a;

if(sq.front==sq.rear&&sq.tag) return error;

if(sq.front==sq.rear&&!sq.tag) {

sq.base[sq.rear]=e;

sq.rear=(sq.rear+1)%max;

if(sq.front==sq.rear) sq.tag=1;

}

else{

a=(sq.base[sq.front]+sq.base[(sq.rear+max-1)%max])/2;

if(e>=a){

sq.base[sq.rear]=e;

sq.rear=(sq.rear+1)%max;

if(sq.front==sq.rear) sq.tag=1;

}

else{

sq.base[(sq.front+max-1)%max]=e;

sq.front=(sq.front+max-1)%max;

if(sq.front==sq.rear) sq.tag=1;

}

}

return ok;

}

status dequeue(xqueue & sq,elemtype & e){

if(sq.front==sq.rear&&!sq.tag) return error;

else{

e=sq.base[sq.front];

sq.front=(sq.front+1+max)%max;

sq.tag=0;

}

return ok;

}

void main(){

xqueue sq;

elemtype e;

initqueue(sq);

cout<<"请输入作业预计时间："<

cin>>e;

if(enqueue(sq,e)) cout<<"元素已插入"<

else cout<<"队列已满元素未被插入"<

cout<<"请输入作业预计时间："<

cin>>e;

if(enqueue(sq,e)) cout<<"元素已插入"<

else cout<<"队列已满元素未被插入"<

cout<<"请输入作业预计时间："<

cin>>e;

if(enqueue(sq,e)) cout<<"元素已插入"<

else cout<<"队列已满元素未被插入"<

cout<<"请输入作业预计时间："<

cin>>e;

if(enqueue(sq,e)) cout<<"元素已插入"<

else cout<<"队列已满元素未被插入"<

if(dequeue(sq,e)) cout<<"队头元素:"<

cout<<"队列中元素为："<

for(;dequeue(sq,e);)

cout<

cout<

}

运行结果：

3.34 假设在如教科书3.

4.1节中图3.9所示的铁道转轨网的输入端有n节车厢：硬座、硬卧和软卧（分别以P,H和S表示）等待调度，要求这三种车厢在输出端铁道上的排列次序为：硬座在前，软卧在中，硬卧在后。试利用输出受限的双端队列对这n节车厢进行调度，编写算法输出调度的操作序列：分别以字符…E?和…D?表示对双端队列的头端进行入队列和出队列的操作；以字符A表示对双端队列的尾端进行入队列的操作。

解：

程序源代码：

#include

#include

#define max 10

#define ok 1

#define error 0

typedef int status;

typedef char elemtype;

typedef struct{

elemtype * base;

int front ;

int rear ;

int tag;

}xqueue;

status initqueue(xqueue & sq){

sq.base=(elemtype *)malloc(max *sizeof(elemtype));

if(!sq.base) exit(-2);

sq.front=sq.rear=0;

sq.tag=0;

return ok;

}

status enqueuerear(xqueue & sq,elemtype e){

if(sq.front==sq.rear&&sq.tag) return error;

sq.base[sq.rear]=e;

sq.rear=(sq.rear+1)%max;

if(sq.front==sq.rear) sq.tag=1;

return ok;

}

status enqueuetop(xqueue & sq,elemtype e){

if(sq.front==sq.rear&&sq.tag) return error;

sq.base[(sq.front-1+max)%max]=e;

sq.front=(sq.front-1+max)%max;

if(sq.front==sq.rear) sq.tag=1;

return ok;

}

status dequeue(xqueue & sq,elemtype & e){

if(sq.front==sq.rear&&!sq.tag) return error;

else{

e=sq.base[sq.front];

sq.front=(sq.front+1+max)%max;

sq.tag=0;

}

return ok;

}

status empty(xqueue sq){

if(sq.front==sq.rear&&!sq.tag) return ok;

else return error;

}

status gettop(xqueue sq,elemtype & e){

if(empty(sq)) return error;

e=sq.base[sq.front];

return ok;

}

void main(){

xqueue sq;

elemtype e;

char ch[25],cch;

int i,n;

initqueue(sq);

cout<<"请输入车厢节数："<

cin>>n;

cout<<"请输入车厢次序："<

for(i=1;i<=n;i++){

cin>>cch;

ch[i-1]=cch;

}

for(i=1;i<=n;i++){

if(empty(sq)) {enqueuetop(sq,ch[i-1]);cout<<" E ";}

else {

if(ch[i-1]=='H') {enqueuerear(sq,ch[i-1]);cout<<" A ";}

if(ch[i-1]=='P') {enqueuetop(sq,ch[i-1]);cout<<" E ";}

if(ch[i-1]=='S') {

gettop(sq,e);

if(e=='S'){

enqueuetop(sq,ch[i-1]);cout<<" E ";

}

else{

while(e=='P'){

dequeue(sq,e);

cout<<" D ";

gettop(sq,e);

}

enqueuetop(sq,ch[i-1]);

cout<<" E ";

}

}

}

}

if(!empty(sq)) {

for(;dequeue(sq,e);)

cout<<" D ";

cout<

}

}

运行结果：

第四章

4.11编写算法，求得所有包含在串s中而不包含在串t中的字符（s中重复的字符只选一个）构成的新串r，以及r中每个字符在s中第一次出现的位置。

解：

程序源代码：

#include

#include

#include

#define ok 1

typedef int status;

typedef struct{

char * ch;

int * pos;

int length;

}string;

status strassign(string & r,char * chars){ int i,j,k;

char * c,* cc;

if(r.ch) free(r.ch);

i=0;c=chars;

while(*c){

if(*c!='*'){

i++;

c++;

}

c++;

}

if(!i){r.ch=0;r.pos=0;}

else{

if(!(r.ch=(char *)malloc(i*sizeof(char)))) exit(-2);

if(!(r.pos=(int *)malloc(i*sizeof(int))))

exit(-2);

j=k=i=1;

c=chars;

cc=r.ch;

while(c[j-1]){

if(c[j-1]!='*'){

cc[i-1]=c[j-1];

r.pos[k-1]=j-1;

i++;k++;

r.length++;

}

j++;

}

return ok;

}

}

void main(){

int i,j,m,n;

string r={0,0,0};

char s[20],t[20];

cout<<"请输入串s:"<

cin>>s;

cout<<"请输入串t:"<

cin>>t;

for(n=0;s[n];n++);

for(m=0;t[m];m++);

for(i=1;i<=n;i++){

if(s[i-1]!='*')

for(j=i+1;j<=n;j++){

if(s[i-1]==s[j-1]) s[j-1]='*';

}

}

for(i=1;i<=m;i++){

if(t[i-1]!='*')

for(j=i+1;j<=m;j++){

if(t[i-1]==t[j-1]) t[j-1]='*';

}

}

for(i=1;i<=n;i++){

if(s[i-1]!='*')

for(j=1;j<=m&&s[i-1]!=t[j-1];j++);

if(s[i-1]==t[j-1]) s[i-1]='*';

}

strassign(r,s);

cout<<"新串r为："<

for(i=0;i<=r.length-1;i++) cout<

cout<

for(i=0;i<=r.length-1;i++) cout<

cout<

}

运行结果：

4.13 编写算法，从串s中删除所有和串t相同的字串。

解：

程序源代码：

#include

数据结构--重修作业题

第一章绪论 一、选择题 3.在数据结构中，从逻辑上可以把数据结构分成（） （A）动态结构和静态结构（B）紧凑结构和非紧凑结构 （C）线性结构和非线性结构（D）内部结构和外部结构 5.算法分析的目的是（）。 （A）找出数据结构的合理性（B）研究算法中的输入和输出的关系 （C）分析算法的效率以求改进（D）分析算法的易懂性和文档性 二、判断题 1.数据的机内表示称为数据的存储结构。（） 2.算法就是程序。（） 5.算法的时间复杂度取决于问题的规模和待处理数据的初态。（） 三、填空题 1.数据逻辑结构包括________、________、_________ 和_________四种类型,其中树形结构和图形结构合称为_____。 2.在线性结构中,第一个结点____前驱结点,其余每个结点有且只有______个前驱结点；最后一个结点______后续结点,其余每个结点有且只有_______个后续结点。 3.在树形结构中,树根结点没有_______结点,其余每个结点有且只有_______个前驱结点；叶子结点没有________结点,其余每个结点的后续结点可以 _________。 4.在图形结构中,每个结点的前驱结点数和后续结点数可以_________。 5.线性结构中元素之间存在________关系,树形结构中元素之间存在______关系,图形结构中元素之间存在_______关系。 8.链式存储结构与顺序存储结构相比较,主要优点是 ________________________________。 9.设有一批数据元素,为了最快的存储某元素,数据结构宜用_________结构,为了方便插入一个元素,数据结构宜用____________结构。

第4章 数据结构与算法 习题与答案

第四章习题（P111-113） 一、复习题 1、试述数据和数据结构的概念及其区别。 数据是对客观事物的符号表示，是信息的载体；数据结构则是指互相之间存在着一种或多种关系的数据元素的集合。（P93） 2、列出算法的五个重要特征并对其进行说明。 算法具有以下五个重要的特征：有穷性：一个算法必须保证执行有限步之后结束。确切性：算法的每一步骤必须有确切的定义。输入：一个算法有0个或多个输入，以刻画运算对象的初始情况，所谓0个输入是指算法本身定除了初始条件。输出：一个算法有一个或多个输出，以反映对输入数据加工后的结果。没有输出的算法没有实际意义。可行性：算法原则上能够精确地运行，而且人们用笔和纸做有限次运算后即可完成。（P95） 3、算法的优劣用什么来衡量？试述如何设计出优秀的算法。 时间复杂度空间复杂度（P97-98） 4、线性和非线性结构各包含哪些种类的数据结构？线性结构和非线性结构各有什么特点？ 线性结构用于描述一对一的相互关系，即结构中元素之间只有最基本的联系，线性结构的特点是逻辑结构简单。所谓非线性结构是指，在该结构中至少存在一个数据元素，有两个或两个以上的直接前驱（或直接后继）元素。树型和图型结构就是其中十分重要的非线性结构，可以用来描述客观世界中广泛存在的层次结构和网状结构的关系。（P99-105） 5、简述树与二叉树的区别；简述树与图的区别。 树用来描述层次结构，是一对多或多对一的关系；二叉树（Binary Tree）是个有限元素的集合，该集合或者为空、或者由一个称为根(root)的元素及两个不相交的、被分别称为左子树和右子树的二叉树组成。二叉树是有序的，即若将其左、右子树颠倒，就成为另一棵不同的二叉树。图也称做网，是一种比树形结构更复杂的非线性结构。在图中，任意两个节点之间都可能相关，即节点之间的邻接关系可以是任意的，图表示的多对多的关系。（P102-P104） 6、请举出遍历算法在实际中使用的例子。 提示：根据实际生活中需要逐个访问处理的情况举例。 7、编写一个算法，统计在一个输入字符串中各个不同字符出现的频度。用适当的测试数据来验证这个算法。 提示：根据查找算法和串中求子串的算法，查找输入串中以单个字符形式的子串。 8、若对有n个元素的有序顺序表和无序顺序表进行顺序搜索，试就下列三种情况分别讨论两者在等搜索概率时的平均搜索长度是否相同? (1) 搜索失败； (2) 搜索成功，且表中只有一个关键码等于给定值k的对象； (3) 搜索成功，且表中有若干个关键码等于给定值k的对象，要求一次搜索找出所有对象。

数据结构课后习题答案第四章

第四章 一、简述下列每对术语的区别： 空串和空白串；串常量和串变量；主串和子串；静态分配的顺序串和动态分配的顺序串；目标串和模式串；有效位移和无效位移。 答： ●空串是指不包含任何字符的串，它的长度为零。 空白串是指包含一个或多个空格的串，空格也是字符。 ●串常量是指在程序中只可引用但不可改变其值的串。 串变量是可以在运行中改变其值的。 ●主串和子串是相对的，一个串中任意个连续字符组成的串就是这个串的子串，而包含子串的串就称为主串。 ●静态分配的顺序串是指串的存储空间是确定的，即串值空间的大小是静态的，在编译时刻就被确定。 动态分配的顺序串是在编译时不分配串值空间，在运行过程中用malloc和free等函数根据需要动态地分配和释放字符数组的空间(这个空间长度由分配时确定，也是顺序存储空间)。 ●目标串和模式串:在串匹配运算过程中，将主串称为目标串，而将需要匹配的子串称为模式串，两者是相对的。 ●有效位移和无效位移：在串定位运算中，模式串从目标的首位开始向右位移，每一次合法位移后如果模式串与目标中相应的字符相同，则这次位移就是有效位移(也就是从此位置开始的匹配成功)，反之，若有不相同的字符存在，则此次位移就是无效位移(也就是从此位置开始的匹配失败)。 二、假设有如下的串说明： char s1[30]="Stocktom,CA", s2[30]="March 5 1999", s3[30], *p; (1)在执行如下的每个语句后p的值是什么? p=stchr(s1,'t'); p=strchr(s2,'9'); p=strchr(s2,'6'); (2)在执行下列语句后，s3的值是什么? strcpy(s3,s1); strcat(s3,","); strcat(s3,s2); (3)调用函数strcmp(s1,s2)的返回值是什么?

数据结构课后习题第四章

第四章串 习题4 一、选择题 1.串是一种分外的线性表，其分外性体现在（）。 A.可以顺序存储 B.数据元素是一个字符 C.可以连接存储 D.数据元素可以是多个字符 2.有两个串P和Q，求P在Q中首次出现的位置的运算称为（）。 A.模式匹配 B.联接 C.求子串 D.求串长 3.设S为一个长度为n的字符串，其中的字符各不相同，则S中的互异的非通俗子串（非空且例外于S本身）的个数为（）。 A.n2 B.（n2/2）+（n/2） C.（n2/2）+（n/2）-1 D.（n2/2）-（n/2）-1 4.设串s1=“ABCDEFG”,s2=“PQRST”，函数concat（x，y）返回x和y串的连接串，subString（s，i，j）返回串s的从序号i的字符开始的j个字符组成的子串，Strlength（s）返回串s的长度，则concat（subString（s1，2，Strlength （s2）），subString(s1，Strlength（s2），2)））的结果串是（）。 A.BCDEF B.BCDEFG C.BCPQRST D.BCDEFEF 5.顺序串中，根据空间分配方式的例外，可分为（）。 A.直接分配和间接分配 B.静态分配和动态分配 C.顺序分配和链式分配 D.随机分配和不变分配 6.设串S=“abcdefgh”，则S的所有非通俗子串（除空串和S自身的串）的个数是（）。

A.8 B.37 C.36 D.35 7.设主串的长度为n，模式串的长度为m，则串匹配的KMP算法时间复杂度是（）。 A.O(m) B.O（n） C.O（m+n） D.O（n*m） 8.已知串S=“aaab”，其next数组值为（）。 A.0123 B.1123 C.1231 D.1211 二丶填空题 1.在空串和空格串中，长度不为0的是（）。 2.空格串是指（），其长度等于（）。 3.按存储结构的例外，串可分为（）、（）和（）。 4.C语言中，以字符（）表示串值的终结。 5.在块链串中，为了提高存储密度，应该增大（）。 6.假设每个字符占1个字节，若结点大小为4个字节的链串的存储密度为50％，则其每个指针占（）个字节。 7.串操作虽然较多，但都可以通过五中基本操作（）、（）、（）、（）和（）构成的最小子集中的操作来实现。 8.设串S=“Ilikecomputer.”，T=“com”，则Length（S）=（），Index（S,T,1）=（）。 9.在KMP算法中，next[j]只与（）串有关，而与（）串无关。 10.字符串“ababaaab”的nextval函数值为（）。 11.两个字符串相等的充分必要条件是（）。 12.实现字符串复制的函数strcpy为：

数据结构课后习题及解析第四章

11． 写算法，实现顺序串的基本操作 StrReplace(&s,t,v) r1 中第 index 个字符起求出首次与串 r2 相同的子串的起始位置。 写一个函数将顺序串 s1 中的第 i 个字符到第 j 个字符之间的字符用 s2 串替换。 写算法，实现顺序串的基本操作 StrCompare(s,t) 。 第四章习题 1. 设 s=' I AM A STUDENT , t= ' GOO D, q=' WORKER 给出下列操作的结果: StrLength(s); SubString(sub1,s,1,7); SubString(sub2,s,7,1); StrIndex(s, ' A ' ,4); StrReplace(s, ' STUDEN 'T,q); StrCat(StrCat(sub1,t), StrCat(sub2,q)); 2. 编写算法，实现串的基本操作 StrReplace(S,T,V) 。 3. 假设以块链结构表示串，块的大小为 1，且附设头结点。 试编写算法，实现串的下列基本操作： StrAsign(S,chars) ； StrCopy(S,T) ； StrCompare(S,T) ； StrLength(S) ； StrCat(S,T) ； SubString(Sub,S,pos,len) 。 4． 叙述以下每对术语的区别：空串和空格串；串变量和串常量；主串和子串；串变量的名字和串变 量的值。 5． 已知：S=”(xyz)* ” ,T= ”(x+z)*y ”。试利用联接、求子串和置换等操作，将 S 转换为T. 6． S 和T 是用结点大小为1的单链表存储的两个串，设计一个算法将串 S 中首次与T 匹配的子串逆 置。 7． S 是用结点大小为4的单链表存储的串，分别编写算法在第k 个字符后插入串T ,及从第k 个字符 删除 len 个字符。 以下算法用定长顺序串： 8． 编写下列算法： 1) 将顺序串 r 中所有值为 ch1 的字符换成 ch2 的字符。 2) 将顺序串 r 中所有字符按照相反的次序仍存放在 r 中。 3) 从顺序串 r 中删除其值等于 ch 的所有字符。 5) 从顺序串 r 中删除所有与串 r1 相同的子串。 从顺序串 9． 10．

数据结构作业系统_第四章答案

4.10③编写对串求逆的递推算法。 要求实现以下函数： void Reverse(StringType &s); /* Reverse s by iteration. */ StringType是串的一个抽象数据类型，它包含以下6种基本操作： void InitStr(StringType &s); // 初始化s为空串。 void StrAssign(StringType &t, StringType s); // 将s的值赋给t。s的实际参数是串变量。 int StrCompare(StringType s, StringType t); // 比较s和t。若s>t，返回值>0；若s=t，返回值=0；若s=pos ;j--){ *(p+x)=*p; p--;}//串s的pos后的子串右移，空出串t的位置 q--; //指针q回退到串t的最后一个字符 for(j=1;j<=x;j++) *p--=*q--; //将t串插入到s的pos位置上 [算法讨论] 串s的结束标记('\0')也后移了，而串t的结尾标记不应插入到s中。

数据结构第四章习题答案

8．请用SQL的GRANT 和REVOKE语句(加上视图机制)完成以下授权定义或存取控制功能: ( a ）用户王明对两个表有SELECT 权力。 GRANT SELECT ON 职工,部门 TO 王明 ( b ）用户李勇对两个表有INSERT 和DELETE 权力。 GRANT INSERT,DELETE ON 职工,部门 TO 李勇 ( c ) 每个职工只对自己的记录有SELECT 权力。 GRANT SELECT ON 职工 WHEN USER()=NAME TO ALL; ( d ）用户刘星对职工表有SELECT 权力，对工资字段具有更新权力。 GRANT SELECT,UPDATE(工资) ON 职工 TO 刘星 ( e ）用户张新具有修改这两个表的结构的权力。 GRANT ALTER TABLE ON 职工,部门 TO 张新; ( f ）用户周平具有对两个表所有权力（读，插，改，删数据），并具有给其他用户授权的权力。 GRANT ALL PRIVILIGES ON 职工,部门 TO 周平 WITH GRANT OPTION; ( g ）用户杨兰具有从每个部门职工中SELECT 最高工资、最低工资、平均工资的权力，他不能查看每个人的工资。 CREATE VIEW 部门工资AS SELECT 部门.名称,MAX(工资),MIN(工资),AVG(工资) FROM 职工,部门 WHERE 职工.部门号=部门.部门号 GROUP BY 职工.部门号 GRANT SELECT ON 部门工资 TO 杨兰; 9 ．把习题8 中（1）---（7）的每一种情况，撤销各用户所授予的权力 (1) REVOKE SELECT ON 职工，部门FROM 王明； (2) REVOKE INSERT , DELETE ON 职工，部门FROM 李勇； (3) REOVKE SELECT ON 职工 WHEN USER ( ) =NAME FROM ALI ; (4) REVOKE SELECT , UPDATE ON 职工 FROM 刘星； (5) REVOKE ALTER TABLE ON 职工，部门 FROM 张新； (6) REVOKE ALL PRIVILIGES ON 职工，部门

数据结构书面作业练习题

数据结构书面作业练习 题 公司内部档案编码：[OPPTR-OPPT28-OPPTL98-

习 题 六 树 和 二 叉 树 单项选择题 1. 如图所示的4棵二叉树，_C ___不是完全二叉树。 2. 如图所示的4棵二叉树，__B_是平衡二叉树。 3. 在线索化二叉树中，t 所指结点没有左子树的充要条件是B __。 A. t —＞left=NULL B. t —＞ltag=1 （A）（B）（C）（D） 图8.7 4棵二叉树 （A）（B） 图8.8 4棵二叉树

C. t—＞ltag=1且t—＞left=NULL D. 以上都不对 4. 二叉树按某种顺序线索化后，任一结点均有指向其前驱和后续的线索，这种说法_B__。 A. 正确 B. 错误 5. 二叉树的前序遍历序列中，任意一个结点均处在其子女结点的前面，这种说法__A__。 A. 正确 B. 错误 6. 由于二叉树中每个结点的度最大为2，所以二叉树是一种特殊的树，这种说法___B_。 A. 正确 B. 错误 7. 设高度为h的二叉树上只有度为0和度为2的结点，则此类二叉树中所包含的结点数至少为__B__。 A. 2h B. 2h-1 C. 2h+1 D. h+1 a 8. 如图所示二叉树的中序遍历序列___B_。

图8.9 一棵二叉树 A. abcdgef B. dfebagc C. dbaefcg D. defbagc 9. 已知某二叉树的后序遍历序列是dabec，中序遍历序列是debac，它的前序遍历序列是D____。 A. acbed B. decab C. deabc D. cedba 10．设a,b为一棵二叉树上的两个结点，在中序遍历时，a在b前的条件是 B 。 A．a在b的右方B．a在b的左方 C．a是b的祖先D．a是b的子孙 11. 假定在一棵二叉树中，双分支结点数为15，单分支结点数为30个，则叶子结点数为个。B A．15 B．16 C．17 D．47

数据结构习题(456章)

第四章串 一．选择题 1．若串S='software',其子串的数目是（） A．8 B．37 C．36 D．9 2．设有两个串p和q,求q在p中首次出现的位置的运算称作（） A．连接B．模式匹配C．求串长D．求子串 3．设字符串S1=“ABCDEFG”，S2=“PQRST”，则运算： S=CONCAT（SUBSTR（S1，2，LEN（S2））；SUBSTR（S1，LEN（S2），2））；后的串值为（） A．A BCDEF B．BCDEFG C．BCDPQRST D． BCDEFEF 4．下面的说法中，只有（）是正确的 A．串是一种特殊的线性表B．串的长度必须大于零 C．串中元素只能是字母D．空串就是空白串 5．两个字符串相等的条件是（） A．两串的长度相等 B．两串包含的字符相同 C．两串的长度相等，并且两串包含的字符相同 D．两串的长度相等，并且对应位置上的字符相同 二．填空题 1．串“ababcbaababd”的next函数值为，nextval函数值为。2．子串的长度为。 第五章数组和广义表 一．选择题 1．设有数组A[i,j]，数组的每个元素长度为3字节，i的值为1 到8 ，j的值为1 到10，数组从内存首地址BA开始顺序存放，当用以列为主存放时，元素A[5，8]的存储首地址为( ) A. BA+141 B. BA+180 C. BA+222 D. BA+225 2．假设以行序为主序存储二维数组A=array[1..100，1..100]，设每个数据元素占2个存储单元，基地址为10，则LOC[5，5]=（） A. 808 B. 818 C. 1010 D. 1020 3．对稀疏矩阵进行压缩存储目的是（） A．便于进行矩阵运算B．便于输入和输出C．节省存储空间D．降低运算的时间复杂度 4．假设以三元组表表示稀疏矩阵，则与如图所示三元组表对应的4×5的稀疏矩阵是（注：矩阵的行列下标均从1开始）（）

《数据结构》第四章习题参考答案

《数据结构》第四章习题 一、判断题（在正确说法的题后括号中打“√”，错误说法的题后括号中打“×”） 1、KMP算法的特点是在模式匹配时指示主串的指针不会变小。( √) 2、串是一种数据对象和操作都特殊的线性表。( √) 3、只包含空白字符的串称为空串（空白串）。( ×) 4、稀疏矩阵压缩存储后，必会（不会）失去随机存取功能。( ×) 5、使用三元组表示稀疏矩阵的非零元素能节省存储空间。( √) 6、插入与删除操作是数据结构中最基本的两种操作，因此这两种操作在数组中也经常使用。（×） 7、若采用三元组表存储稀疏矩阵，只要把每个元素的行下标和列下标互换（错的），就完成了对该矩阵的转置运算。（×） 二、单项选择题 1．下面关于串的的叙述中，哪一个是不正确的？（ B ） A．串是字符的有限序列B．空串是由空格构成的串（空串是长度为零的串）C．模式匹配是串的一种重要运算D．串既可以采用顺序存储，也可以采用链式存储2．有串S1=’ABCDEFG’，S2 = ’PQRST’，假设函数con(x,y)返回x和y串的连接串，subs(s,i,j)返回串s的从序号i的字符开始的j个字符组成的子串，len(s)返回中s的长度，则con(subs(s1,2,len(s2)),subs(s1,len(s2),2))的结果串是（ D ）。 A．BCDEF B．BCDEFG C．BCPQRST D．CDEFGFG 3、串的长度是指（ B ） A．串中所含不同字母的个数B．串中所含字符的个数 C．串中所含不同字符的个数D．串中所含非空格字符的个数 三、填空题 1、串是一种特殊的线性表，其特殊性表现在_数据元素为字符，操作集也不同__；串的两种最基本的存储方式是_顺序存储_、__ 链式存储_；两个串相等的充分必要条件是__两串的长度相等且两串中对应位置的字符也相等__。 2、设正文串长度为n，模式串长度为m，则串匹配的KMP算法的时间复杂度为_O(m+n)__。 3、模式串P=‘abaabcac’的next函数值序列为_{-1,0,0,1,1,2,0,1}___。 4、已知数组A[0..9,0..9]的每个元素占5个存储单元，将其按行优先次序存储在起始地址为1000的连续的内存单元中，则元素A[6，8]的地址为__1340___。 四、综合题 1、KMP算法较Brute-Force算法有哪些改进? 【解答】 朴素的模式匹配（Brute－Force）时间复杂度是O（m*n），KMP算法有一定改进，时间复杂度达到O（m＋n）。KMP算法主要优点是主串指针不回溯。当主串很大不能一次读入内存且经常发生部分匹配时，KMP算法的优点更为突出。 2、课本P183 4.1题 【解答】 A[2][2] = 644+2*n+2 = 676 A[3][3] = 644+3*n+3 = 692 3、课本P184 4.7题