清华大学严蔚敏数据结构课后习题答案第三章（栈与队列） [引用2009-10-23
21:22:35]
主人：孤独追梦字号：大中小3.15
typedef struct{
Elemtype *base[2];
Elemtype *top[2];
}BDStacktype; //双向栈类型
Status Init_Stack(BDStacktype &tws,int m)//初始化一个大小为m的双向栈tws {
tws.base[0]=(Elemtype*)malloc(sizeof(Elemtype));
tws.base[1]=tws.base[0]+m;
tws.top[0]=tws.base[0];
tws.top[1]=tws.base[1];
return OK;
}//Init_Stack
Status push(BDStacktype &tws,int i,Elemtype x)//x入栈,i=0表示低端栈,i=1表示高端栈
{
if(tws.top[0]>tws.top[1]) return OVERFLOW; //注意此时的栈满条件
if(i==0) *tws.top[0]++=x;
else if(i==1) *tws.top[1]--=x;
else return ERROR;
return OK;
}//push
Status pop(BDStacktype &tws,int i,Elemtype &x)//x出栈,i=0表示低端栈,i=1表示高端栈
{
if(i==0)
{
if(tws.top[0]==tws.base[0]) return OVERFLOW;
x=*--tws.top[0];
}
else if(i==1)
{
if(tws.top[1]==tws.base[1]) return OVERFLOW;
x=*++tws.top[1];
}
else return ERROR;
return OK;
}//pop
3.16
void Train_arrange(char *train)//这里用字符串train表示火车,'H'表示硬席,'S'表示软席
{
p=train;q=train;
InitStack(s);
while(*p)
{
if(*p=='H') push(s,*p); //把'H'存入栈中
else *(q++)=*p; //把'S'调到前部
p++;
}
while(!StackEmpty(s))
{
pop(s,c);
*(q++)=c; //把'H'接在后部
}
}//Train_arrange
3.17
int IsReverse()//判断输入的字符串中'&'前和'&'后部分是否为逆串,是则返回1,否则返回0
{
InitStack(s);
while((e=getchar())!='&')
push(s,e);
while((e=getchar())!='@')
{
if(StackEmpty(s)) return 0;
pop(s,c);
if(e!=c) return 0;
}
if(!StackEmpty(s)) return 0;
return 1;
}//IsReverse
3.18
Status Bracket_Test(char *str)//判别表达式中小括号是否匹配
{
count=0;
for(p=str;*p;p++)
{
if(*p=='(') count++;
else if(*p==')') count--;
if (count<0) return ERROR;
}
if(count) return ERROR; //注意括号不匹配的两种情况
return OK;
}//Bracket_Test
3.19
Status AllBrackets_Test(char *str)//判别表达式中三种括号是否匹配
{
InitStack(s);
for(p=str;*p;p++)
{
if(*p=='('||*p=='['||*p=='{') push(s,*p);
else if(*p==')'||*p==']'||*p=='}')
{
if(StackEmpty(s)) return ERROR;
pop(s,c);
if(*p==')'&&c!='(') return ERROR;
if(*p==']'&&c!='[') return ERROR;
if(*p=='}'&&c!='{') return ERROR; //必须与当前栈顶括号匹配
}
}//for
if(!StackEmpty(s)) return ERROR;
return OK;
}//AllBrackets_Test
3.20
typedef struct {
. int x;
int y;
} coordinate;
void Repaint_Color(int g[m][n],int i,int j,int color)//把点(i,j)相邻区域的颜色置换为color
{
old=g[i][j];
InitQueue(Q);
EnQueue(Q,{I,j});
while(!QueueEmpty(Q))
{
DeQueue(Q,a);
x=a.x;y=a.y;
if(x>1)
if(g[x-1][y]==old)
{
g[x-1][y]=color;
EnQueue(Q,{x-1,y}); //修改左邻点的颜色
}
if(y>1)
if(g[x][y-1]==old)
{
g[x][y-1]=color;
EnQueue(Q,{x,y-1}); //修改上邻点的颜色
}
if(x if(g[x+1][y]==old) { g[x+1][y]=color; EnQueue(Q,{x+1,y}); //修改右邻点的颜色 } if(y if(g[x][y+1]==old) { g[x][y+1]=color; EnQueue(Q,{x,y+1}); //修改下邻点的颜色 } }//while }//Repaint_Color 分析:本算法采用了类似于图的广度优先遍历的思想,用两个队列保存相邻同色点的横坐标和纵坐标.递归形式的算法该怎么写呢? 3.21 void NiBoLan(char *str,char *new)//把中缀表达式str转换成逆波兰式new { p=str;q=new; //为方便起见,设str的两端都加上了优先级最低的特殊符号InitStack(s); //s为运算符栈 while(*p) { if(*p是字母)) *q++=*p; //直接输出 else { c=gettop(s); if(*p优先级比c高) push(s,*p); else { while(gettop(s)优先级不比*p低) { pop(s,c);*(q++)=c; }//while push(s,*p); //运算符在栈内遵循越往栈顶优先级越高的原则 }//else }//else p++; }//while }//NiBoLan //参见编译原理教材 3.22 int GetValue_NiBoLan(char *str)//对逆波兰式求值 { p=str;InitStack(s); //s为操作数栈 while(*p) { if(*p是数) push(s,*p); else { pop(s,a);pop(s,b); r=compute(b,*p,a); //假设compute为执行双目运算的过程 push(s,r); }//else p++; }//while pop(s,r);return r; }//GetValue_NiBoLan 3.23 Status NiBoLan_to_BoLan(char *str,stringtype &new)//把逆波兰表达式str转换为波兰式new { p=str;Initstack(s); //s的元素为stringtype类型 while(*p) { if(*p为字母) push(s,*p); else { if(StackEmpty(s)) return ERROR; pop(s,a); if(StackEmpty(s)) return ERROR; pop(s,b); c=link(link(*p,b),a); push(s,c); p++; }//while pop(s,new); if(!StackEmpty(s)) return ERROR; return OK; }//NiBoLan_to_BoLan 分析:基本思想见书后注释.本题中暂不考虑串的具体操作的实现,而将其看作一种抽象数据类型stringtype,对其可以进行连接操作:c=link(a,b). 3.24 Status g(int m,int n,int &s)//求递归函数g的值s { if(m==0&&n>=0) s=0; else if(m>0&&n>=0) s=n+g(m-1,2*n); else return ERROR; return OK; }//g 3.25 Status F_recursive(int n,int &s)//递归算法 { if(n<0) return ERROR; if(n==0) s=n+1; else { F_recurve(n/2,r); s=n*r; } return OK; }//F_recursive Status F_nonrecursive(int n,int s)//非递归算法 { if(n<0) return ERROR; if(n==0) s=n+1; else { InitStack(s); //s的元素类型为struct {int a;int b;} while(n!=0) { a=n;b=n/2; push(s,{a,b}); n=b; s=1; while(!StackEmpty(s)) { pop(s,t); s*=t.a; }//while } return OK; }//F_nonrecursive 3.26 float Sqrt_recursive(float A,float p,float e)//求平方根的递归算法 { if(abs(p^2-A)<=e) return p; else return sqrt_recurve(A,(p+A/p)/2,e); }//Sqrt_recurve float Sqrt_nonrecursive(float A,float p,float e)//求平方根的非递归算法 { while(abs(p^2-A)>=e) p=(p+A/p)/2; return p; }//Sqrt_nonrecursive 3.27 这一题的所有算法以及栈的变化过程请参见《数据结构(pascal版)》,作者不再详细写出. 3.28 void InitCiQueue(CiQueue &Q)//初始化循环链表表示的队列Q { Q=(CiLNode*)malloc(sizeof(CiLNode)); Q->next=Q; }//InitCiQueue void EnCiQueue(CiQueue &Q,int x)//把元素x插入循环链表表示的队列Q,Q指向队尾元素,Q->next指向头结点,Q->next->next指向队头元素 { p=(CiLNode*)malloc(sizeof(CiLNode)); p->data=x; p->next=Q->next; //直接把p加在Q的后面 Q->next=p; Q=p; //修改尾指针 } Status DeCiQueue(CiQueue &Q,int x)//从循环链表表示的队列Q头部删除元素x { if(Q==Q->next) return INFEASIBLE; //队列已空 p=Q->next->next; x=p->data; Q->next->next=p->next; free(p); return OK; }//DeCiQueue 3.29 Status EnCyQueue(CyQueue &Q,int x)//带tag域的循环队列入队算法 { if(Q.front==Q.rear&&Q.tag==1) //tag域的值为0表示"空",1表示"满" return OVERFLOW; Q.base[Q.rear]=x; Q.rear=(Q.rear+1)%MAXSIZE; if(Q.front==Q.rear) Q.tag=1; //队列满 }//EnCyQueue Status DeCyQueue(CyQueue &Q,int &x)//带tag域的循环队列出队算法 { if(Q.front==Q.rear&&Q.tag==0) return INFEASIBLE; Q.front=(Q.front+1)%MAXSIZE; x=Q.base[Q.front]; if(Q.front==Q.rear) Q.tag=1; //队列空 return OK; }//DeCyQueue 分析:当循环队列容量较小而队列中每个元素占的空间较多时,此种表示方法可以节约较多的存储空间,较有价值. 3.30 Status EnCyQueue(CyQueue &Q,int x)//带length域的循环队列入队算法 { if(Q.length==MAXSIZE) return OVERFLOW; Q.rear=(Q.rear+1)%MAXSIZE; Q.base[Q.rear]=x; Q.length++; return OK; }//EnCyQueue Status DeCyQueue(CyQueue &Q,int &x)//带length域的循环队列出队算法 { if(Q.length==0) return INFEASIBLE; head=(Q.rear-Q.length+1)%MAXSIZE; //详见书后注释 x=Q.base[head]; Q.length--; }//DeCyQueue 3.31 int Palindrome_Test()//判别输入的字符串是否回文序列,是则返回1,否则返回0 { InitStack(S);InitQueue(Q); while((c=getchar()!='@') { Push(S,c);EnQueue(Q,c); //同时使用栈和队列两种结构 } while(!StackEmpty(S)) { Pop(S,a);DeQueue(Q,b)); if(a!=b) return ERROR; } return OK; }//Palindrome_Test 3.32 void GetFib_CyQueue(int k,int n)//求k阶斐波那契序列的前n+1项 { InitCyQueue(Q); //其MAXSIZE设置为k for(i=0;i Q.base[k-1]=1; //给前k项赋初值 for(i=0;i for(i=k;i<=n;i++) { m=i%k;sum=0; for(j=0;j Q.base[m]=sum; //求第i项的值存入队列中并取代已无用的第一项 printf("%d",sum); } }//GetFib_CyQueue 3.33 Status EnDQueue(DQueue &Q,int x)//输出受限的双端队列的入队操作 { if((Q.rear+1)%MAXSIZE==Q.front) return OVERFLOW; //队列满 avr=(Q.base[Q.rear-1]+Q.base[Q.front])/2; if(x>=avr) //根据x的值决定插入在队头还是队尾 { Q.base[Q.rear]=x; Q.rear=(Q.rear+1)%MAXSIZE; } //插入在队尾 else { Q.front=(Q.front-1)%MAXSIZE; Q.base[Q.front]=x; } //插入在队头 return OK; }//EnDQueue Status DeDQueue(DQueue &Q,int &x)//输出受限的双端队列的出队操作 { if(Q.front==Q.rear) return INFEASIBLE; //队列空 x=Q.base[Q.front]; Q.front=(Q.front+1)%MAXSIZE; return OK; }//DeDQueue 3.34 void Train_Rearrange(char *train)//这里用字符串train表示火车,'P'表示硬座,'H'表示硬卧,'S'表示软卧,最终按PSH的顺序排列 { r=train; InitDQueue(Q); while(*r) { if(*r=='P') { printf("E"); printf("D"); //实际上等于不入队列,直接输出P车厢 } else if(*r=='S') { printf("E"); EnDQueue(Q,*r,0); //0表示把S车厢从头端入队列 } else { printf("A"); EnDQueue(Q,*r,1); //1表示把H车厢从尾端入队列 } }//while while(!DQueueEmpty(Q)) { printf("D"); DeDQueue(Q); }//while //从头端出队列的车厢必然是先S后H的顺序}//Train_Rearrange 数据结构（C语言版）（第2版） 课后习题答案 李冬梅 目录 第1章绪论...................................................................................... 错误!未定义书签。第2章线性表 .................................................................................. 错误!未定义书签。第3章栈和队列 .............................................................................. 错误!未定义书签。第4章串、数组和广义表 ............................................................... 错误!未定义书签。第5章树和二叉树 .......................................................................... 错误!未定义书签。第6章图 ........................................................................................... 错误!未定义书签。第7章查找...................................................................................... 错误!未定义书签。第8章排序...................................................................................... 错误!未定义书签。 第1章绪论 1.1 简述下列术语：数据，数据元素、数据对象、数据结构、存储结构、数据类型和抽象数据类型。 解：数据是对客观事物的符号表示。在计算机科学中是指所有能输入到计算机中并被计算机程序处理的符号的总称。 数据元素是数据的基本单位，在计算机程序中通常作为一个整体进行考虑和处理。 数据对象是性质相同的数据元素的集合，是数据的一个子集。 数据结构是相互之间存在一种或多种特定关系的数据元素的集合。 存储结构是数据结构在计算机中的表示。 数据类型是一个值的集合和定义在这个值集上的一组操作的总称。 抽象数据类型是指一个数学模型以及定义在该模型上的一组操作。是对一般数据类型的扩展。 1.2 试描述数据结构和抽象数据类型的概念与程序设计语言中数据类型概念的区别。 解：抽象数据类型包含一般数据类型的概念，但含义比一般数据类型更广、更抽象。一般数据类型由具体语言系统内部定义，直接提供给编程者定义用户数据，因此称它们为预定义数据类型。抽象数据 类型通常由编程者定义，包括定义它所使用的数据和在这些数据上所进行的操作。在定义抽象数据类型中的数据部分和操作部分时，要求只定义到数据的逻辑结构和操作说明，不考虑数据的存储结构和操作的具体实现，这样抽象层次更高，更能为其他用户提供良好的使用接口。 1.3 设有数据结构(D,R)，其中 {}4,3,2,1d d d d D =，{}r R =，()()(){}4,3,3,2,2,1d d d d d d r = 试按图论中图的画法惯例画出其逻辑结构图。 解： 1.4 试仿照三元组的抽象数据类型分别写出抽象数据类型复数和有理数的定义（有理数是其分子、分母均为自然数且分母不为零的分数）。 解： ADT Complex{ 数据对象：D={r,i|r,i 为实数} 数据关系：R={ 第一章绪论 选择题 1.组成数据的基本单位是（） （A）数据项（B）数据类型（C）数据元素（D）数据变量 2.数据结构是研究数据的（）以及它们之间的相互关系。 （A）理想结构，物理结构（B）理想结构，抽象结构 （C）物理结构，逻辑结构（D）抽象结构，逻辑结构 3.在数据结构中，从逻辑上可以把数据结构分成（） （A）动态结构和静态结构（B）紧凑结构和非紧凑结构 （C）线性结构和非线性结构（D）内部结构和外部结构 4.数据结构是一门研究非数值计算的程序设计问题中计算机的（①）以及它们之间的（②）和运算等的学科。 ①（A）数据元素（B）计算方法（C）逻辑存储（D）数据映像 ②（A）结构（B）关系（C）运算（D）算法 5.算法分析的目的是（）。 （A）找出数据结构的合理性（B）研究算法中的输入和输出的关系 （C）分析算法的效率以求改进（D）分析算法的易懂性和文档性 6.计算机算法指的是（①）,它必须具备输入、输出和（②）等5个特性。 ①（A）计算方法（B）排序方法（C）解决问题的有限运算序列（D）调度方法 ②（A）可执行性、可移植性和可扩充性（B）可行性、确定性和有穷性 （C）确定性、有穷性和稳定性（D）易读性、稳定性和安全性 二、判断题 1.数据的机内表示称为数据的存储结构。（） 2.算法就是程序。（） 3.数据元素是数据的最小单位。（） 4.算法的五个特性为：有穷性、输入、输出、完成性和确定性。（） 5.算法的时间复杂度取决于问题的规模和待处理数据的初态。（） 三、填空题 1.数据逻辑结构包括________、________、_________ 和_________四种类型,其中树形结构和图形结构合称为_____。 2.在线性结构中,第一个结点____前驱结点,其余每个结点有且只有______个前驱结点；最后一个结点______后续结点,其余每个结点有且只有_______个后续结点。 3.在树形结构中,树根结点没有_______结点,其余每个结点有且只有_______个前驱结点；叶子结点没有________结点,其余每个结点的后续结点可以_________。 4.在图形结构中,每个结点的前驱结点数和后续结点数可以_________。 5.线性结构中元素之间存在________关系,树形结构中元素之间存在______关系,图形结构中元素之间存在_______关系。 6.算法的五个重要特性是_______、_______、______、_______、_______。 7.数据结构的三要素是指______、_______和________。 8.链式存储结构与顺序存储结构相比较,主要优点是________________________________。 9.设有一批数据元素,为了最快的存储某元素,数据结构宜用_________结构,为了方便插入一个元素,数据结构宜用____________结构。 四、算法分析题 1.求下列算法段的语句频度及时间复杂度参考答案： 选择题1. C 2.C 3. C 4. A、B 5. C 6.C、B 人生难得几回搏，此时不搏更待何时？ 第1章绪论 1.1 简述下列术语：数据 数据元素、数据对象、数据结构、存储结构、数据类型和抽象数据类型 解：数据是对客观事物的符号表示 在计算机科学中是指所有能输入到计算机中并被计算机程序处理的符号的总称 数据元素是数据的基本单位 在计算机程序常作为一个整体进行考虑和处理 数据对象是性质相同的数据元素的集合 是数据的一个子集 数据结构是相互之间存在一种或多种特定关系的数据元素的集合 存储结构是数据结构在计算机中的表示 数据类型是一个值的集合和定义在这个值集上的一组操作的总称 抽象数据类型是指一个数学模型以及定义在该模型上的一组操作 是对一般数据类型的扩展 1.2 试描述数据结构和抽象数据类型的概念与程序设计语言中数据类型概念的区别 解：抽象数据类型包含一般数据类型的概念 但含义比一般数据类型更广、更抽象 一般数据类型由具体语言系统部定义 直接提供给编程者定义用户数据 因此称它们为预定义数据类型 抽象数据类型通常由编程者定义 包括定义它所使用的数据和在这些数据上所进行的操作 在定义抽象数据类型中的数据部分和操作部分时 要求只定义到数据的逻辑结构和操作说明 不考虑数据的存储结构和操作的具体实现 这样抽象层次更高 更能为其他用户提供良好的使用接口 1.3 设有数据结构(D R) 其中 试按图论中图的画法惯例画出其逻辑结构图 解： 1.4 试仿照三元组的抽象数据类型分别写出抽象数据类型复数和有理数的定义（有理数是其分子、分母均为自然数且分母不为零的分数） 解： ADT Complex{ 数据对象：D={r i|r i为实数} 数据关系：R={ 16 void Descend(int &x, int &y, int &z) { int t; if(x while(result[i].sport!=NULL) { switch(result[i].schoolname) { case 'A': score[0].totalscore+=result[i].score; if(result[i].gender==male) score[0].malescore+=result[i].score; else score[0].femalescore+=result[i].score; break; case 'B': score[1].totalscore+=result[i].score; if(result[i].gender==male) score[1].malescore+=result[i].score; else score[1].femalescore+=result[i].score; break; case 'C': score[2].totalscore+=result[i].score; if(result[i].gender==male) score[2].malescore+=result[i].score; else score[2].femalescore+=result[i].score; break; case 'D': score[3].totalscore+=result[i].score; if(result[i].gender==male) score[3].malescore+=result[i].score; else score[3].femalescore+=result[i].score; break; case 'E': score[4].totalscore+=result[i].score; if(result[i].gender==male) score[4].malescore+=result[i].score; else score[4].femalescore+=result[i].score; break; } i++; } for(s='A';s<='E';s++) { printf("School %c:\n",s); printf("Total score of male:%d\n",score[i].malescore); printf("Total score of female:%d\n",score[i].femalescore); printf("Total score of all:%d\n\n",score[i].totalscore); } } 19 Status Series(int ARRSIZE, int a[]) 第一章绪论 一、选择题 1.组成数据的基本单位是（） （A）数据项（B）数据类型（C）数据元素（D）数据变量 2.数据结构是研究数据的（）以及它们之间的相互关系。 （A）理想结构，物理结构（B）理想结构，抽象结构 （C）物理结构，逻辑结构（D）抽象结构，逻辑结构 3.在数据结构中，从逻辑上可以把数据结构分成（） （A）动态结构和静态结构（B）紧凑结构和非紧凑结构 （C）线性结构和非线性结构（D）内部结构和外部结构 4.数据结构是一门研究非数值计算的程序设计问题中计算机的（①）以及它们之间的（②）和运算等的学科。 ① （A）数据元素（B）计算方法（C）逻辑存储（D）数据映像 ② （A）结构（B）关系（C）运算（D）算法 5.算法分析的目的是（）。 （A）找出数据结构的合理性（B）研究算法中的输入和输出的关系 （C）分析算法的效率以求改进（D）分析算法的易懂性和文档性 6.计算机算法指的是（①）,它必须具备输入、输出和（②）等5 个特性。 ① （A）计算方法（B）排序方法（C）解决问题的有限运算序列（D）调度方法 ② （A）可执行性、可移植性和可扩充性（B）可行性、确定性和有穷性 （C）确定性、有穷性和稳定性（D）易读性、稳定性和安全性 二、判断题 1.数据的机内表示称为数据的存储结构。（） 2.算法就是程序。（） 3.数据元素是数据的最小单位。（） 4.算法的五个特性为：有穷性、输入、输出、完成性和确定性。（） 5.算法的时间复杂度取决于问题的规模和待处理数据的初态。（） 三、填空题 1.数据逻辑结构包括________、________、_________ 和_________四种类型,其中树形结构和图形结构合称为_____。 2.在线性结构中,第一个结点____前驱结点,其余每个结点有且只有______个前驱结点；最后一个结点______后续结点,其余每个结点有且只有_______个后续结点。 3.在树形结构中,树根结点没有_______结点,其余每个结点有且只 有_______个前驱结点；叶子结点没有________结点,其余每个结点的后续结点可以_________。 4.在图形结构中,每个结点的前驱结点数和后续结点数可以 _________。 5.线性结构中元素之间存在________关系,树形结构中元素之间存 在______关系,图形结构中元素之间存在_______关系。 6.算法的五个重要特性是_______、_______、______、_______、 第2章线性表 1．选择题 （1）顺序表中第一个元素的存储地址是100，每个元素的长度为2，则第5个元素的地址是（）。 A．110 B．108 C．100 D．120 答案：B 解释：顺序表中的数据连续存储，所以第5个元素的地址为：100+2*4=108。 （3）向一个有127个元素的顺序表中插入一个新元素并保持原来顺序不变，平均要移动的元素个数为（）。 A．8 B．63.5 C．63 D．7 答案：B 解释：平均要移动的元素个数为：n/2。 （4）链接存储的存储结构所占存储空间（）。 A．分两部分，一部分存放结点值，另一部分存放表示结点间关系的指针 B．只有一部分，存放结点值 C．只有一部分，存储表示结点间关系的指针 D．分两部分，一部分存放结点值，另一部分存放结点所占单元数 答案：A （5）线性表若采用链式存储结构时，要求内存中可用存储单元的地址（）。 A．必须是连续的B．部分地址必须是连续的 C．一定是不连续的D．连续或不连续都可以 答案：D （6）线性表Ｌ在（）情况下适用于使用链式结构实现。 A．需经常修改Ｌ中的结点值Ｂ．需不断对Ｌ进行删除插入 C．Ｌ中含有大量的结点Ｄ．Ｌ中结点结构复杂 答案：B 解释：链表最大的优点在于插入和删除时不需要移动数据，直接修改指针即可。 （7）单链表的存储密度（）。 A．大于1 B．等于1 C．小于1 D．不能确定 答案：C 解释：存储密度是指一个结点数据本身所占的存储空间和整个结点所占的存储空间之比，假设单链表一个结点本身所占的空间为D，指针域所占的空间为N，则存储密度为：D/(D+N)，一定小于1。 （8）将两个各有n个元素的有序表归并成一个有序表，其最少的比较次数是（）。 A．n B．2n-1 C．2n D．n-1 答案：A 清华数据结构习题集答案(C语言版严蔚敏) 第1章绪论 简述下列术语：数据，数据元素、数据对象、数据结构、存储结构、数据类型和抽象数据类型。 解：数据是对客观事物的符号表示。在计算机科学中是指所有能输入到计算机中并被计算机程序处理的符号的总称。 数据元素是数据的基本单位，在计算机程序中通常作为一个整体进行考虑和处理。 数据对象是性质相同的数据元素的集合，是数据的一个子集。 数据结构是相互之间存在一种或多种特定关系的数据元素的集合。 存储结构是数据结构在计算机中的表示。 数据类型是一个值的集合和定义在这个值集上的一组操作的总称。 抽象数据类型是指一个数学模型以及定义在该模型上的一组操作。是对一般数据类型的扩展。 试描述数据结构和抽象数据类型的概念与程序设计语言中数据类型概念的区别。 解：抽象数据类型包含一般数据类型的概念，但含义比一般数据类型更广、更抽象。一般数据类型由具体语言系统内部定义，直接提供给编程者定义用户数据，因此称它们为预定义数据类型。抽象数据类型通常由编程者定义，包括定义它所使用的数据和在这些数据上所进行的操作。在定义抽象数据类型中的数据部分和操作部分时，要求只定义到数据的逻辑结构和操作说明，不考虑数据的存储结构和操作的具体实现，这样抽象层次更高，更能为其他用户提供良好的使用接口。 设有数据结构(D,R)，其中 {}4,3,2,1d d d d D =，{}r R =，()()(){}4,3,3,2,2,1d d d d d d r = 试按图论中图的画法惯例画出其逻辑结构图。 解： 试仿照三元组的抽象数据类型分别写出抽象数据类型复数和有理数的定义（有理数是其分子、分母均为自然数且分母不为零的分数）。 解： ADT Complex{ 数据对象：D={r,i|r,i为实数} 数据关系：R={ )。 第2章线性表 1 .选择题 (1)顺序表中 第一个 元素的存储 地址是100，每个元素的 长度为2，则第5个元素的 地址是( )。 A . 110 答案： B 解释：顺序表中的数据连续存储，所以第 D . 120 5个元素的地址为： 100+2*4=108。 (3)向一个有127个元素的顺序表中插入一个新元素并保持原来顺序不变，平均要移 动的元 素个数为( )。 C . 63 A . 8 B . 答案：B 解释：平均要移动的元素个数为： (4) 链接存储的存储结构所占存储空间( n/2。 ）。 A .分两部分，一部分存放结点值，另一部分存放表示结点间关系的指针 B .只有一部分，存放结点值 C .只有一部分，存储表示结点间关系的指针 D .分两部分，一部分存放结点值，另一部分存放结点所占单元数 答案：A (5) 线性表若采用链式存储结构时，要求内存中可用存储单元的地址( A .必须是连续的 C . 一定是不连续的 答案：D (6) 线性表1在( B ?部分地址必须是连续的 D ?连续或不连续都可以 )情况下适用于使用链式结构实现。 B.需不断对L 进行删除插入 D.L 中结点结构复杂 A .需经常修改L 中的结点值 C . L 中含有大量的结点 答案：B 解释：链表最大的优点在于插入和删除时不需要移动数据，直接修改指针即可。 (7) 单链表的存储密度( )。 A .大于1 B .等于1 答案：C 解释：存储密度是指一个结点数据本身所占的存储空间和整个结点所占的存储空 间之比，假设单链表一个结点本身所占的空间为 D ，指针域所占的空间为 N ，则存储密 度为：D/(D+N)，—定小于 1。 (8) 将两个各有 n 个元素的有序表归并成一个有序表，其最少的比较次数是( C ?小于1 D ?不能确定 B . 2n-1 C . 2n D . n-1 C . 100 《一定能摸到红球吗？》说课稿 林银花 一、教材说明： １、课题：《一定能摸到红球吗？》 ２、本节内容的地位和作用 在现代社会中，人们面临着更多的机会和选择，常常需要在不确定情境中作出合理的决策,概率正是通过对不确定现象和事件发生的可能性的刻画,来为人们更好的制定决策提供依据和建议.本节内容又是义务教育阶段,唯一培养学生从不确定的角度来观察世界的数学内容,让学生了解可能性是普遍的,有助于他们理解社会,适应生活. ３、教学目标设计： (１)认知目标： （Ａ）经历猜测．实验．收集与分析试验结果等过程 （Ｂ）体会事件的发生的不确定性知道事情发生的可能性有多大。 （２）、能力目标： (Ａ)经历游戏等的活动过程，初步认识确定事件和不确定事件 （Ｂ）在与其它人交流的过程中，能合理清晰地表达自己的思维过程； （３）、情感目标： （Ａ）通过创设游戏情境，让学生主动参与，做“数学实验”，激发学生学习的热情和兴趣，激活学生思维。 （Ｂ）在与他人的合作过程中，增强互相帮助、团结协作的精神。 （Ｃ）体会到在生活中我们可以从确定和不确定两方面分析一件事情. ４、本课重点、难点分析： 学习的重点是初步体验事情发生的确定性和不确定性. 学习的难点是确定事件发生的可能性大小. 学习本节知识应注意猜测,试验,收集与分析实验结果,从中体会事件发生的可能性及大小. 二、教学对象分析： 1、初一学生性格开朗活泼，对新鲜事物特别敏感，且较易接受，因此，教学过程中创设的问题情境应较生动活泼，直观形象，且贴近学生的生活，从而引起学生的有意注意。 2、初一学生的概括能力较弱，推理能力还有待不断发展，所以在教学时，可让学生充分试验,收集，分析,帮助他们直观形象地感知。 3、初一学生已经具备了一定的学习能力，所以本节课中，应多为学生创造自主学习、 、 清华数据结构习题集答案(C 语言版严蔚敏) 第1章 绪论 简述下列术语：数据，数据元素、数据对象、数据结构、存储结构、数据类型和抽象数据类型。 解：数据是对客观事物的符号表示。在计算机科学中是指所有能输入到计算机中并被计算机程序处理的符号的总称。 数据元素是数据的基本单位，在计算机程序中通常作为一个整体进行考虑和处理。 数据对象是性质相同的数据元素的集合，是数据的一个子集。 数据结构是相互之间存在一种或多种特定关系的数据元素的集合。 存储结构是数据结构在计算机中的表示。 ： 数据类型是一个值的集合和定义在这个值集上的一组操作的总称。 抽象数据类型是指一个数学模型以及定义在该模型上的一组操作。是对一般数据类型的扩展。 试描述数据结构和抽象数据类型的概念与程序设计语言中数据类型概念的区别。 解：抽象数据类型包含一般数据类型的概念，但含义比一般数据类型更广、更抽象。一般数据类型由具体语言系统内部定义，直接提供给编程者定义用户数据，因此称它们为预定义数据类型。抽象数据类型通常由编程者定义，包括定义它所使用的数据和在这些数据上所进行的操作。在定义抽象数据类型中的数据部分和操作部分时，要求只定义到数据的逻辑结构和操作说明，不考虑数据的存储结构和操作的具体实现，这样抽象层次更高，更能为其他用户提供良好的使用接口。 设有数据结构(D,R)，其中 {}4,3,2,1d d d d D =，{}r R =，()()(){}4,3,3,2,2,1d d d d d d r = 试按图论中图的画法惯例画出其逻辑结构图。 解： ： 试仿照三元组的抽象数据类型分别写出抽象数据类型复数和有理数的定义（有理数是其分子、分母均为自然数且分母不为零的分数）。 解： ADT Complex{ 数据对象：D={r,i|r,i 为实数} 数据关系：R={ 1.16 void print_descending(int x,int y,int z)//按从大到小顺序输出三个数 { scanf("%d,%d,%d",&x,&y,&z); if(x 严蔚敏 数据结构C 语言版答案详解 第1章 绪论 1.1 简述下列术语：数据，数据元素、数据对象、数据结构、存储结构、数据类型和抽象数据类型。 解：数据是对客观事物的符号表示。在计算机科学中是指所有能输入到计算机中并被计算机程序处理的符号的总称。 数据元素是数据的基本单位，在计算机程序中通常作为一个整体进行考虑和处理。 数据对象是性质相同的数据元素的集合，是数据的一个子集。 数据结构是相互之间存在一种或多种特定关系的数据元素的集合。 存储结构是数据结构在计算机中的表示。 数据类型是一个值的集合和定义在这个值集上的一组操作的总称。 抽象数据类型是指一个数学模型以及定义在该模型上的一组操作。是对一般数据类型的扩展。 1.2 试描述数据结构和抽象数据类型的概念与程序设计语言中数据类型概念的区别。 解：抽象数据类型包含一般数据类型的概念，但含义比一般数据类型更广、更抽象。一般数据类型由具体语言系统内部定义，直接提供给编程者定义用户数据，因此称它们为预定义数据类型。抽象数据类型通常由编程者定义，包括定义它所使用的数据和在这些数据上所进行的操作。在定义抽象数据类型中的数据部分和操作部分时，要求只定义到数据的逻辑结构和操作说明，不考虑数据的存储结构和操作的具体实现，这样抽象层次更高，更能为其他用户提供良好的使用接口。 1.3 设有数据结构(D,R)，其中 {}4,3,2,1d d d d D =，{}r R =，()()(){}4,3,3,2,2,1d d d d d d r = 试按图论中图的画法惯例画出其逻辑结构图。 解： 1.4 试仿照三元组的抽象数据类型分别写出抽象数据类型复数和有理数的定义（有理数是其分子、分母均为自然数且分母不为零的分数）。 解： ADT Complex{ 数据对象：D={r,i|r,i 为实数} 数据关系：R={ 第一章绪论 1.16 void print_descending(int x,int y,int z)//按从大到小顺序输出三个数 { scanf("%d,%d,%d",&x,&y,&z); if(x 清华大学严蔚敏数据结构课后习题答案第三章（栈与队列） [引用2009-10-23 21:22:35] 主人：孤独追梦字号：大中小3.15 typedef struct{ Elemtype *base[2]; Elemtype *top[2]; }BDStacktype; //双向栈类型 Status Init_Stack(BDStacktype &tws,int m)//初始化一个大小为m的双向栈tws { tws.base[0]=(Elemtype*)malloc(sizeof(Elemtype)); tws.base[1]=tws.base[0]+m; tws.top[0]=tws.base[0]; tws.top[1]=tws.base[1]; return OK; }//Init_Stack Status push(BDStacktype &tws,int i,Elemtype x)//x入栈,i=0表示低端栈,i=1表示高端栈 { if(tws.top[0]>tws.top[1]) return OVERFLOW; //注意此时的栈满条件 if(i==0) *tws.top[0]++=x; else if(i==1) *tws.top[1]--=x; else return ERROR; return OK; }//push Status pop(BDStacktype &tws,int i,Elemtype &x)//x出栈,i=0表示低端栈,i=1表示高端栈 { if(i==0) { if(tws.top[0]==tws.base[0]) return OVERFLOW; x=*--tws.top[0]; } else if(i==1) { if(tws.top[1]==tws.base[1]) return OVERFLOW; x=*++tws.top[1]; } else return ERROR; return OK; }//pop 第1章 绪论 简述下列术语：数据，数据元素、数据对象、数据结构、存储结构、数据类型和抽象数据类型。 解：数据是对客观事物的符号表示。在计算机科学中是指所有能输入到计算机中并被计算机程序处理的符号的总称。 数据元素是数据的基本单位，在计算机程序中通常作为一个整体进行考虑和处理。 数据对象是性质相同的数据元素的集合，是数据的一个子集。 数据结构是相互之间存在一种或多种特定关系的数据元素的集合。 存储结构是数据结构在计算机中的表示。 数据类型是一个值的集合和定义在这个值集上的一组操作的总称。 抽象数据类型是指一个数学模型以及定义在该模型上的一组操作。是对一般数据类型的扩展。 试描述数据结构和抽象数据类型的概念与程序设计语言中数据类型概念的区别。 解：抽象数据类型包含一般数据类型的概念，但含义比一般数据类型更广、更抽象。一般数据类型由具体语言系统内部定义，直接提供给编程者定义用户数据，因此称它们为预定义数据类型。抽象数据类型通常由编程者定义，包括定义它所使用的数据和在这些数据上所进行的操作。在定义抽象数据类型中的数据部分和操作部分时，要求只定义到数据的逻辑结构和操作说明，不考虑数据的存储结构和操作的具体实现，这样抽象层次更高，更能为其他用户提供良好的使用接口。 设有数据结构(D,R)，其中 {}4,3,2,1d d d d D =，{}r R =，()()(){}4,3,3,2,2,1d d d d d d r = 试按图论中图的画法惯例画出其逻辑结构图。 解： 试仿照三元组的抽象数据类型分别写出抽象数据类型复数和有理数的定义（有理数是其分子、分母均为自然数且分母不为零的分数）。 解： ADT Complex{ 数据对象：D={r,i|r,i 为实数} 数据关系：R={ 清华数据结构习题集答案(C 语言版严蔚敏) 第1章 绪论 简述下列术语：数据，数据元素、数据对象、数据结构、存储结构、数据类型和抽象数据类型。 解：数据是对客观事物的符号表示。在计算机科学中是指所有能输入到计算机中并被计算机程序处理的符号的总称。 数据元素是数据的基本单位，在计算机程序中通常作为一个整体进行考虑和处理。 数据对象是性质相同的数据元素的集合，是数据的一个子集。 数据结构是相互之间存在一种或多种特定关系的数据元素的集合。 存储结构是数据结构在计算机中的表示。 数据类型是一个值的集合和定义在这个值集上的一组操作的总称。 抽象数据类型是指一个数学模型以及定义在该模型上的一组操作。是对一般数据类型的扩展。 试描述数据结构和抽象数据类型的概念与程序设计语言中数据类型概念的区别。 解：抽象数据类型包含一般数据类型的概念，但含义比一般数据类型更广、更抽象。一般数据类型由具体语言系统内部定义，直接提供给编程者定义用户数据，因此称它们为预定义数据类型。抽象数据类型通常由编程者定义，包括定义它所使用的数据和在这些数据上所进行的操作。在定义抽象数据类型中的数据部分和操作部分时，要求只定义到数据的逻辑结构和操作说明，不考虑数据的存储结构和操作的具体实现，这样抽象层次更高，更能为其他用户提供良好的使用接口。 设有数据结构(D,R)，其中 {}4,3,2,1d d d d D =，{}r R =，()()(){}4,3,3,2,2,1d d d d d d r = 试按图论中图的画法惯例画出其逻辑结构图。 解： 试仿照三元组的抽象数据类型分别写出抽象数据类型复数和有理数的定义（有理数是其分子、分母均为自然数且分母不为零的分数）。 解： ADT Complex{ 数据对象：D={r,i|r,i 为实数} 数据关系：R={ 第1章 绪论 1.1 简述下列术语：数据，数据元素、数据对象、数据结构、存储结构、数据类型和抽象数据类型。 1.2 试描述数据结构和抽象数据类型的概念与程序设计语言中数据类型概念的区别。 1.3 设有数据结构(D,R)，其中 {}4,3,2,1d d d d D =，{}r R =，()()(){}4,3,3,2,2,1d d d d d d r = 试按图论中图的画法惯例画出其逻辑结构图。 1.4 试仿照三元组的抽象数据类型分别写出抽象数据类型复数和有理数的定义（有理数是其分子、分母均为自然数且分母不为零的分数）。 1.5 试画出与下列程序段等价的框图。 (1) product=1; i=1; while(i<=n){ product *= i; i++; } (2) i=0; do { i++; } while((i!=n) && (a[i]!=x)); (3) switch { case x 《数据结构》第二版严蔚敏课后习题作业参考答案(1-7 章) -标准化文件发布号：（9456-EUATWK-MWUB-WUNN-INNUL-DDQTY-KII 第1章 4．答案： （1）顺序存储结构 顺序存储结构是借助元素在存储器中的相对位置来表示数据元素之间的逻辑关系，通常借助程序设计语言的数组类型来描述。 （2）链式存储结构 顺序存储结构要求所有的元素依次存放在一片连续的存储空间中，而链式存储结构，无需占用一整块存储空间。但为了表示结点之间的关系，需要给每个结点附加指针字段，用于存放后继元素的存储地址。所以链式存储结构通常借助于程序设计语言的指针类型来描述。 5. 选择题 (1)~(6)：CCBDDA 6． （1）O(1) （2）O(m*n) （3）O(n2) （4）O(log3n) （5）O(n2) （6）O(n) 第2章 1．选择题 （1）~（5）：BABAD （6）~（10）： BCABD （11）~（15）：CDDAC 2．算法设计题 （1）将两个递增的有序链表合并为一个递增的有序链表。要求结果链表仍使用原来两个链表的存储空间, 不另外占用其它的存储空间。表中不允许有重复的数据。 [题目分析] 合并后的新表使用头指针Lc指向，pa和pb分别是链表La和Lb的工作指针,初始化为相应链表的第一个结点，从第一个结点开始进行比较，当两个链表La 和Lb均为到达表尾结点时，依次摘取其中较小者重新链接在Lc表的最后。如果两个表中的元素相等，只摘取La表中的元素，删除Lb表中的元素，这样确保合并后表中无重复的元素。当一个表到达表尾结点，为空时，将非空表的剩余元素直接链接在Lc表的最后。 void MergeList(LinkList &La,LinkList &Lb,LinkList &Lc) {//合并链表La和Lb，合并后的新表使用头指针Lc指向 pa=La->next; pb=Lb->next; //pa和pb分别是链表La和Lb的工作指针,初始化为相应链表的第一个结点 Lc=pc=La; //用La的头结点作为Lc的头结点 while(pa && pb) { if(pa->data数据结构(C语言版)第2版习题答案解析-严蔚敏
严蔚敏版数据结构课后习题答案-完整版
数据结构习题及答案——严蔚敏_课后习题答案 精品
数据结构复习题集答案(c语言版严蔚敏)
数据结构题集c语言版答案严蔚敏吴伟民[1]
数据结构习题及答案——严蔚敏
数据结构(C语言版)第2版习题答案—严蔚敏(简化版)
清华数据结构习题集答案(C语言版严蔚敏)
数据结构第2版习题答案—严蔚敏
严蔚敏《数据结构(c语言版)习题集》答案第四章串
清华数据结构习题集答案(C语言版严蔚敏)
数据结构习题集答案(c版)(清华大学 严蔚敏)
严蔚敏数据结构题集(C语言版)完整答案.doc
严蔚敏数据结构习题集答案
清华大学严蔚敏数据结构课后习题答案 第三章(栈与队列)
数据结构-习题集答案-(C语言版严蔚敏)
清华数据结构习题集答案C语言版严蔚敏
数据结构习题集(C语言版严蔚敏)第一二三章
《数据结构》第二版严蔚敏课后习题作业参考答案(1-7章)
相关主题
文本预览