2016最新广工anyview数据结构答案

/**********【习题4.011】关系表达式，if语句第一种形式在以下程序空缺处填写合适内容，使得程序判断用户输入的字符是否为'@'，若是则显示："输入正确"。

**********/#include<stdio.h>void main(){char c;scanf("%c",&c);if( c=='@' ) printf("输入正确\n");}/**********【习题4.012】关系表达式，if语句第一种形式在以下程序空缺处填写合适内容，使得程序输入一个整数赋给变量a，计算并输出a的绝对值a1。

**********/#include<stdio.h>#include<math.h>void main(){int a,a1;scanf("%d",&a);a1=abs(a);printf("|%d| = %d\n",a,a1);}/**********【习题4.013】逻辑表达式，if语句第一种形式在以下程序空缺处填写合适内容，使得程序对输入的整型变量x的值进行判断，若变量x值为“假”时输出“False”。

**********/#include<stdio.h>int main( ){int x;scanf("%d",&x);if(x==0 )printf("False!\n");return 0;}/**********【习题4.016】if语句的子句为复合语句在以下程序空缺处填写合适内容，使得程序将输入到变量a和b的两个整数按照由大到小的顺序输出。

**********/#include<stdio.h>void main( ){inta,b,t;scanf("%d %d",&a,&b);if(a<b){t=b;b=a;a=t;}printf("%d %d\n",a,b);}/**********【习题4.203】条件运算（3目运算）在以下程序空缺处填写合适内容，使得程序先令整型变量a取值0，b取值-20；然后用条件运算实现：若a>b成立则将b的平方值赋予c，否则将0赋予c；最后显示c的值。

2016广工Anyview试题答案-第六章【习题6.033】系统给定外部整型数组a、整型变量n、max、min 和实型变量avg（不需要自行定义）。

编写程序，求数组a中前n 个元素的最大值max、最小值min及平均值avg。

**********/void main(){inti,sum=0;max=min=a[0];for(i=0;i<n;i++)< bdsfid="69" p=""></n;i++)<>{if(a[i]>=max)max=a[i];if(a[i]<=min)min=a[i];sum+=a[i];}avg=sum/(float)n;}/**********【习题6.043】系统给定外部整型变量n和整型数组a（不需要自行定义）。

编写程序，找出数组a中前n个元素中的最小元素及其下标，然后把它和数组中最前面的元素a[0]交换位置。

**********/void main(){int b=a[0],temp,min,z;for(int i=1;i<n;i++)< bdsfid="87" p=""></n;i++)<>{if(b>a[i])b=a[i];}min=b;for(int j=0;j<n;j++)< bdsfid="94" p=""></n;j++)<>{if(a[j]==min)z=j;}temp=a[0];a[0]=min;a[z]=temp;}【习题6.050】系统给定外部字符串s和整型数组c[26]（不需要自行定义）。

编写程序，将字符串s中26个小写字母出现的次数依次统计到数组c中。

例如，当s=“abcijkabcdexyzuvwx”时，数组c的26个元素值依次为：2 2 2 1 1 0 0 0 1 1 1 0 0 00 0 0 0 0 0 1 1 1 2 1 1。

数据结构课后习题答案第1章绪论一、基础知识题1.1 简述下列概念数据，数据元素，数据类型，数据结构，逻辑结构，存储结构，算法。

【解答】数据是信息的载体，是描述客观事物的数、字符，以及所有能输入到计算机中并被计算机程序识别和处理的符号的集合。

数据元素是数据的基本单位。

在不同的条件下，数据元素又可称为元素、结点、顶点、记录等。

数据类型是对数据的取值范围、数据元素之间的结构以及允许施加操作的一种总体描述。

每一种计算机程序设计语言都定义有自己的数据类型。

“数据结构”这一术语有两种含义，一是作为一门课程的名称；二是作为一个科学的概念。

作为科学概念，目前尚无公认定义，一般认为，讨论数据结构要包括三个方面，一是数据的逻辑结构，二是数据的存储结构，三是对数据进行的操作（运算）。

而数据类型是值的集合和操作的集合，可以看作是已实现了的数据结构，后者是前者的一种简化情况。

数据的逻辑结构反映数据元素之间的逻辑关系（即数据元素之间的关联方式或“邻接关系”），数据的存储结构是数据结构在计算机中的表示，包括数据元素的表示及其关系的表示。

数据的运算是对数据定义的一组操作，运算是定义在逻辑结构上的，和存储结构无关，而运算的实现则依赖于存储结构。

数据结构在计算机中的表示称为物理结构，又称存储结构。

是逻辑结构在存储器中的映像，包括数据元素的表示和关系的表示。

逻辑结构与计算机无关。

算法是对特定问题求解步骤的一种描述，是指令的有限序列。

其中每一条指令表示一个或多个操作。

一个算法应该具有下列特性：有穷性、确定性、可行性、输入和输出。

1.2数据的逻辑结构分哪几种，为什么说逻辑结构是数据组织的主要方面？【解答】数据的逻辑结构分为线性结构和非线性结构。

（也可以分为集合、线性结构、树形结构和图形即网状结构）。

逻辑结构是数据组织的某种“本质性”的东西：（1）逻辑结构与数据元素本身的形式、内容无关。

（2）逻辑结构与数据元素的相对位置无关。

（3）逻辑结构与所含数据元素的个数无关。

2016广工AnyView数据结构-第1-5章答案2016广工AnyView数据结构-第1-5章答案/**********【题目】试写一算法，如果三个整数a，b和c 的值不是依次非递增的，则通过交换，令其为非递增。

***********/void Descend(int &a, int &b, int &c)/* 通过交换，令 a >= b >= c */{if(c<=b&&b<=a) return;else {if(a<="">if(a<="">if(b<="">}}void swap(int &a,int &b){int temp;temp=a;a=b;b=a;}/**********【题目】试编写算法求一元多项式P(x) = a0 + a1x + a2x^2 + ... + anx^n 的值P(x0)，并确定算法中每一语句的执行次数和整个算法的时间复杂度。

**********/float Polynomial(int n, int a[], float x) /* 求一元多项式的值P(x)。

*//* 数组a的元素a[i]为i次项的系数，i=0,...,n */{float answer =a[0];float temp= 1.0;for(int i=1;i<=n;i++){temp*=x;answer+=a[i]*temp;}return answer;}/**********【题目】已知k阶裴波那契序列的定义为f(0)=0, f(1)=0, ..., f(k-2)=0, f(k-1)=1;f(n)=f(n-1)+f(n-2)+...+f(n-k),n=k,k+1,...试编写求k阶裴波那契序列的第m项值的函数算法，k和m均以值调用的形式在函数参数表中出现。

广东工业大学数据结构Aniview第三章参考答案◆3.17③试写一个算法，识别依次读入的一个以@为结束符的字符序列是否为形如'序列1&序列2'模式的字符序列。

其中序列1和序列2中都不含字符'&'，且序列2是序列1的逆序列。

例如，'a+b&b+a'是属该模式的字符序列，而'1+3&3-1'则不是。

实现下列函数:Status match(char *str);/* 若str是属该模式的字符序列，*//* 则返回TRUE，否则返回FALSE */Stack是一个已实现的栈。

可使用的相关类型和函数：typedef char SElemType; // 栈Stack的元素类型Status InitStack(Stack &s);Status Push(Stack &s, SElemType e);Status Pop(Stack &s, SElemType&e);Status StackEmpty(Stack s);Status GetTop(Stack s, SElemType&e);Status match(char *str)/* 若str是属该模式的字符序列，*//* 则返回TRUE，否则返回FALSE */{ Stack S;inti;SElemType e;InitStack(S);for(i=0;str[i]!='&';i++){ Push(S,str[i]); }for(i=i+1;!StackEmpty(S)&&str[i]!='@';i++){Pop(S,e);if(e!=str[i]){ return FALSE;}}if(StackEmpty(S)&&str[i]=='@'){ return TRUE;}}3.18②试写一个判别表达式中开、闭括号是否配对出现的算法。

第1章绪论1 •简述下列概念：数据、数据元素、数据项、数据对象、数据结构、逻辑结构、存储结构、抽象数据类型。

答案：数据：是客观事物的符号表示，指所有能输入到计算机中并被计算机程序处理的符号的总称。

如数学计算中用到的整数和实数，文本编辑所用到的字符串，多媒体程序处理的图形、图像、声音、动画等通过特殊编码定义后的数据。

数据元素：是数据的基本单位，在计算机中通常作为一个整体进行考虑和处理。

在有些情况下，数据元素也称为元素、结点、记录等。

数据元素用于完整地描述一个对象，如一个学生记录，树中棋盘的一个格局（状态）、图中的一个顶点等。

数据项：是组成数据元素的、有独立含义的、不可分割的最小单位。

例如，学生基本信息表中的学号、姓名、性别等都是数据项。

数据对象：是性质相同的数据元素的集合，是数据的一个子集。

例如：整数数据对象是集合N={0，士1，士2,…}，字母字符数据对象是集合C={ ‘ A', ‘ B…，‘ Z，‘ a'b '，…，‘ z ' }，学生基本信息表也可是一个数据对象。

数据结构：是相互之间存在一种或多种特定关系的数据元素的集合。

换句话说，数据结构是带“结构”的数据元素的集合，“结构”就是指数据元素之间存在的关系。

逻辑结构：从逻辑关系上描述数据，它与数据的存储无关，是独立于计算机的。

因此，数据的逻辑结构可以看作是从具体问题抽象出来的数学模型。

存储结构：数据对象在计算机中的存储表示，也称为物理结构。

抽象数据类型：由用户定义的，表示应用问题的数学模型，以及定义在这个模型上的一组操作的总称。

具体包括三部分：数据对象、数据对象上关系的集合和对数据对象的基本操作的集合。

2 •试举一个数据结构的例子，叙述其逻辑结构和存储结构两方面的含义和相互关系。

答案：例如有一张学生基本信息表，包括学生的学号、姓名、性别、籍贯、专业等。

每个学生基本信息记录对应一个数据元素，学生记录按顺序号排列，形成了学生基本信息记录的线性序列。

广工数据结构anyview答案第4章//03******************************************************************/******* ***【题目】试写一算法，同时实现链栈的判空操作方式。

链栈的类型定义为：typedefstructlsnode{elemtypedata;//数据域structlsnode*next;//指针域}lsnode,*lstack;//结点和链栈类型***********/statusstackempty_l(lstacks)/*对链栈s判空。

若s就是空栈，则回到true；否则回到false*/{if(null==s)returntrue;elsereturnfalse;}//05******************************************************************/******* ***【题目】试写一算法，同时实现链栈的挑栈顶元素操作方式。

链栈的类型定义为：typedefstructlsnode{elemtypedata;//数据域structlsnode*next;//指针域}lsnode,*lstack;//结点和链栈类型***********/statusgettop_l(lstacks,elemtype&e)/*取链栈s的栈顶元素到e，并返回ok;*//*若s是空栈，则失败，返回error。

*/{if(null==s)returnerror;elsee=s->data;returnok;}//31******************************************************************/******* ***【题目】试写一算法，同时实现链队列的判空操作方式。

链队列的类型定义为：typedefstructlqnode{elemtypedata;structlqnode*next;}lqnode,*queueptr;//结点和结点指针类型typedefstruct{queueptrfront;//队头指针queueptrrear;//队尾指针}lqueue;//链队列类型***********/statusqueueempty_lq(lqueueq)/*认定链队列q与否为空队列。

数据结构课后习题标准答案————————————————————————————————作者：————————————————————————————————日期：7_1对于图题7.1（P235）的无向图，给出：（1）表示该图的邻接矩阵。

（2）表示该图的邻接表。

（3）图中每个顶点的度。

解：（1）邻接矩阵：0111000100110010010101110111010100100110010001110（2）邻接表：1：2----3----4----NULL;2: 1----4----5----NULL;3: 1----4----6----NULL;4: 1----2----3----5----6----7----NULL;5: 2----4----7----NULL;6: 3----4----7----NULL;7: 4----5----6----NULL;（3）图中每个顶点的度分别为：3，3，3，6，3，3，3。

7_2对于图题7.1的无向图，给出：（1）从顶点1出发，按深度优先搜索法遍历图时所得到的顶点序（2）从顶点1出发，按广度优先法搜索法遍历图时所得到的顶点序列。

（1）DFS法：存储结构：本题采用邻接表作为图的存储结构，邻接表中的各个链表的结点形式由类型L_NODE规定，而各个链表的头指针存放在数组head中。

数组e中的元素e[0],e[1],…..,e[m-1]给出图中的m条边，e中结点形式由类型E_NODE规定。

visit[i]数组用来表示顶点i是否被访问过。

遍历前置visit各元素为0，若顶点i被访问过,则置visit[i]为1.算法分析：首先访问出发顶点v.接着，选择一个与v相邻接且未被访问过的的顶点w访问之，再从w 开始进行深度优先搜索。

每当到达一个其所有相邻接的顶点都被访问过的顶点，就从最后访问的顶点开始，依次退回到尚有邻接顶点未曾访问过的顶点u,并从u开始进行深度优先搜索。

这个过程进行到所有顶点都被访问过，或从任何一个已访问过的顶点出发，再也无法到达未曾访问过的顶点，则搜索过程就结束。

【题目】若两棵二叉树T1和T2皆为空，或者皆不空且T1的左、右子树和T2的左、右子树分别相似，则称二叉树T1和T2相似.试编写算法,判别给定两棵二叉树是否相似.二叉链表类型定义:typedef struct BiTNode ｛TElemType data;struct BiTNode *lchild， *rchild；} BiTNode， *BiTree;＊****＊＊＊*＊/Status Similar（BiTree T1, BiTree T2)/＊判断两棵二叉树是否相似的递归算法＊/｛if(!T1＆＆！T2）//同为空时,两树相似return TRUE；else if(T1&＆T1)｛if(Similar（T1 -> lchild，T2 -> lchild）＆& Similar(T1 -> rchild,T2 —> rchild）)//两树都不为空时,判断左右子树是否相似return TRUE；elsereturn FALSE；}else//以上两种情况都不符合,就直接返回FALSEreturn FALSE;}/**＊*＊＊＊***【题目】编写递归算法,求对二叉树T先序遍历时第k个访问的结点的值。

二叉链表类型定义：typedef struct BiTNode ｛TElemType data;struct BiTNode *lchild, *rchild;} BiTNode, *BiTree;＊*＊*＊*＊**＊/TElemType PreOrder（BiTree T， int &k) ｛TElemType x=’＃’;if（T==NULL）return '#'；if（k==1）return T-〉data;if（T—>lchild!=NULL)｛k--；x=PreOrder(T—>lchild,k）；｝if（T->rchild!=NULL＆&x==’#’)｛k—-;x=PreOrder(T-〉rchild， k）;}return x；｝TElemType PreOrderK(BiTree T, int k）/* 求对二叉树T先序遍历时第k个访问的结点的值。

广工数据结构anyview 80道上机题1.void Descend(int &x, int &y, int &z)/* 按从大到小顺序返回x，y和z的值*/ {int t;if(x<z){t=z;z=x;x=t;}if(y<z){t=y;y=z;z=t;}if(y>x){t=x;x=y;y=t;}}2.Status Fibonacci(int k, int m, int &f)/* 求k阶斐波那契序列的第m项的值f */ {int *a;int i=1;if(k<2||m<0) return ERROR;if(m<k){if(m==k-1) f=1;else f=0;return OK;}a=(int*)malloc((m+1)*sizeof(int));for(i=0;i<k-1;i++) a[i]=0;i=k+1;a[k-1]=1;a[k]=1;while(i<=m){a[i]=2*a[i-1]-a[i-k-1];i++;}f=a[m];return OK;}3.void Scores(ResultType *result, ScoreType *score)/* 求各校的男、女总分和团体总分, 并依次存入数组score *//* 假设比赛结果已经储存在result[ ]数组中, *//* 并以特殊记录{"", male, ' ', "", 0 }（域scorce=0）*//* 表示结束*/{int i;for(i=0;result[i].score!=0;i++){score[result[i].schoolname-'A'].totalscore+=result[i].score;if(result[i].gender==male)score[result[i].schoolname-'A'].malescore+=result[i].score;elsescore[result[i].schoolname-'A'].femalescore+=result[i].score;}}4Status Series(int ARRSIZE, int a[])/* 求i!*2^i序列的值并依次存入长度为ARRSIZE的数组a；*//* 若所有值均不超过MAXINT，则返回OK，否则返回OVERFLOW */{int i=1,b=1,na=1;while(i<=ARRSIZE){na*=i;b*=2;if(na*b>MAXINT) return OVERFLOW;a[i-1]=na*b;i++;if(i>ARRSIZE+1) return OVERFLOW;}return OK;}5float Polynomial(int n, int a[], float x)/* 求一元多项式的值P(x)。