数据结构习题参考答案

Page1of471习题参考答案习题1一．名称解释（1）数据是信息的载体，是对客观事物的符号表示。通俗的说，凡是能被计算机识别、存取和加工处理的符号、字符、图形、图象、声音、视频信号等一切信息都可以称为数据。（2）数据结构是相互之间存在的一种或多种特定关系的数据元素的集合。简言之，数据结构是指数据之间的关系，即数据的组织形式。（3）数据元素之间的逻辑关系，称为数据的逻辑结构。（4）数据元素及其关系在计算机存储器内的表示，称为数据的存储结构。（5）线性结构是指数据元素之间存在“一对一”关系的逻辑结构。（6）非线性结构是指数据元素之间存在“一对一”或“一对多”关系的逻辑结构。（除了线性结构以外的树形结构和图形结构等统称为非线性结构）。二．判断题（正确的请在前面的括号内打√；错误的打ㄨ）（1）√（2）ㄨ（3）√（4）ㄨ（5）√（6）√三．填空题（1）集合线性结构树形结构图形结构非线性结构（2）顺序存储链式存储索引存储散列存储（3）一对一一对多多对多（4）没有一没有多个（5）任意多个任意多个（6）有穷性确定性可行性输入输出（7）操作对象关系（8）数据元素关系（9）逻辑结构存储结构算法（10）有穷指令事先估算法事后统计法四．选择题（1）A（2）C（3）C（4）D（5）D（6）B（7）A（8）B五．试分析下列程序段的时间复杂度（1）O(n*m)（2）O(n)（3）O(n2)（4）O(sqrt(n))（5）O(n)（6）O(n2)六．二元关系表示的数据结构如下，分别画出对应的逻辑图形，并指出它们属于何种数据Page2of472结构。（1）集合abcde（2）线性结构（3）图结构（4）树结构以后，凡不会对根结点引起误解的情况下，树形结构结点之间的关系一般不用带箭头线，而直接用直线画。习题2ABCEFD1263452540705782366864Page3of473一．名词解释（1）线性表——线性表是具有相同数据类型的n（n=0）个数据元素的有限序列。其逻辑特征反映了结点间一对一的关系，是一种线性结构。（2）顺序表——用一组地址连续的存储单元依次顺序存储线性表的数据元素（相邻结点存放在相邻的物理位置），称为顺序表。它是一种随机存取结构，可以通过公式来计算结点的存取地址。（3）单链表——单链表的每个结点都有两个域，一个数据域和一个指针域，称之为单链表。（4）双链表——以链表形式存储的线性表，其结点包含一个数据域和两个指针域，称之为双链表。（5）循环链表——若线性链表的最后一个结点的指针指向头结点，使得链表头尾结点相连，就构成了循环链表。（6）存储密度——存储密度定义为结点数据本身所占的存储量与结点结构实际分配的存储量的比值。顺序表的存储密度等于1；链表结构存储密度小于1。二．判断题（下列各题，正确的请在前面的括号内打√；错误的打ㄨ）（1）ㄨ（2）ㄨ（3）√（4）ㄨ（5）ㄨ（6）√（7）ㄨ（8）ㄨ（9）√（10）√三．填空题1．一定2．不必3．有限的一对一关系4．节省存储随机存取5．插入删除小6．n/2表长n和插入位置7．（n-1）/2表长n和删除位置8．O(1)9．直接前驱10．的直接前趋结点的地址O(n)11．O(1)12．*P的直接前驱结点的地址O(n)O(1)13．头指针四．选择题(1)B(2)A(3)B(4)C(5)A(6)A(7)B(8)B(9)D(10)B五．简答题1．顺序存储结构的长处是节约存储空间，可以随机存取。（缺点是插入、删除要作大量移Page4of474动，不易扩充）；链表存储结构优点是插入、删除操作容易，表的扩充方便。（缺点是存储密度低）。2．头指针——指向链表中第一个结点（头结点或无头结点时的开始结点）的指针。头结点——在开始结点之前附加的一个结点。开始结点——在链表中，存储第一个数据元素的结点。3．主要是简化操作。由于表的操作常在表的两端进行，所以对单循环链表，当知道其尾指针rear后，其另一端的头指针是rear-next-next（表中代头结点），仅改变两个指针值即可，运算时间为O(1)。六．（1）返回结点*p的直接前趋结点地址。（2）交换结点*p和结点*q（p和q的值不变）。七．程序设计题1．解：voidShow(ListNode*P){ListNode*t=P;do{printf(%c,t-data);t=t-rear;}while(t!=P);}2．解：voiddelete(ListNode*L){ListNode*p=L,*q;if(L-next-data==X){printf(“值为x的结点是第一个结点，没有直接前趋结点可以删除”);return;}for(;p-next-data!=X;q=p,p=p-next);//删除指针p所指向的结点q-next=p-next;deletep;}3．解voidDel(SeqList*L,inti,intk){intj=i-1+k;for(j=0;jk;j++)Page5of475{L-data[i-1+j]=L-data[i+k-2+j];if(i+k-2+jL-last)break;}}4．解：本题是遍历该链表的每个结点，每遇到一个结点，结点个数加1，结点个数存储在变量n中。实现本题功能的函数如下：intcounter(head)node*head；{node*p;intn＝0;p=head；while(p!=NULL){if(p-data==x)n++；p=p-next;}return(n);}5．解：本题的算法思想是：先找到两链表的尾指针，将第一个链表的尾指针与第二个链表的头结点链接起来，使之成为循环的。函数如下：node*link(head1,head2)node*head1,*head2;{node*p,*q;p=head1;while(p-next!=head1)p=p-next;q=head2;while(q-next!=head2)q=q-next;p-next=head2;q-next=head1;return(head1);}6．解：假设输入一组多项式的系数和指数，以输入系数为标志结束，在建立多项式链表时，总是按照指数从大到小顺序排列的。两个多项式链表A和B，其头指针分别是heada和headb，这两个多项的多项式链表为C，其头指针为headc。实现本题功能的函数如下：structpnode*padd(heada，headb)structpnode*heada,*headb；Page6of476{structpnode*headc,*p,*q,*s;intx;p=heada;q=headb;headc＝(structpnode*)malloc(sizeof(structpndoe));r=headc;while(p!=NULL&&q!=NULL){if(p-exp==q-exp)//两结点指数相等时，将两系数相加生成新结点插入C中{x=p-coef+q-coef;if(x!=0){s＝(structpnode*)malloc(sizeof(structpnode));s-coef＝s;s-exp=p-exp;r-link＝s;r=s;}p=p-link;q=q-link;}else//两结点的指数不相等时，将其中较小系数的结点复制成一新结点插入C中if(p-expq-exp){s=(structpnode*)malloc(sizeof(structpnode));s-coef=q-coef;s-exp=q-exp;r-link=s;r=s;q=q-link;}else{s＝(structpnode*)malloc(sizeof(structpnode));s-coef=p-coef;s-exp=p-exp;r-link=s;r=s;p=p-link;}}while(p!=NULL)//复制A的余下部分Page7of477{s=(structpnode*)malloc(sizeof(structpnode));//复制一个结点ss-coef=p-coef;s-exp=p-exp;r-link=s;//把s链接到C中r=s;p=p-link;}while(q!=NULL)//复制B的余下部分{s=(structpnode*)malloc(sizeof(structpnode));//复制一个结点ss-coef=q-coef;s-exp=q-exp;r-link=s;//把s链接到C中r=s;q=q-link;}r-link=NULL;//最后结点的link域置空s=headc;//删除C的头结点headc=headc-link;free(s);return(headc);}习题3一.名词解释（1）栈——只允许在一端进行插入或删除操作的线性表称为栈。其最大的特点是“后进先出”。（2）顺序栈——采用顺序存储结构的栈称为顺序栈。（3）链栈——采用链式存储结构的栈称为链栈。二．判断题（下列各题，正确的请在前面的括号内打√；错误的打ㄨ）Page8of478（1）√（2）√（3）ㄨ（4）ㄨ（5）ㄨ（6）ㄨ三.填空题（1）后进先出（2）栈顶栈底（3）栈空栈满（4）O（1）O（1）（5）必须一致（6）栈（7）栈空（8）p-next=toptop=p（9）--++（10）LS-next首四.单选题（1）B（2）C（3）A（4）D（5）B（6）C（7）D（8）B（9）A（10）A五.求下列表达式的后缀表达式（要求写出过程）（1）AB^C^D/（2）0A–BC*+DE/+（3）ABC+*D*E-（4）AB+C*EFGH/+/-D-（5）852+/6-六．算法设计题1．解：用一整型变量top表示栈顶指针，top为0时表示栈为空。栈中元素从S[1]开始存放元素。（1）入栈算法：voidpush(charx){if((top+M)MAXLEN-1)printf(“堆栈溢出！”);else{if(top==0){top++;S[top]=x;}else{top=top+M;Page9of479S[top]=x;}}}（2）出栈算法：voidpop(charx){if(top==0)printf(“堆栈为空栈！”);else{if(top==1){x=S[top];top––;}else{x=S[top];top=top–M;}}}2．解：设表达式在字符数组a[]中，使用一堆栈S来帮助判断。intcorrect(chara[]){stacks;InitStack(s);//调用初始化栈函数for(i=0;istrlen(a);i++)if(a[i]==’(’)Push(s,’(’);elseif(a[i]==’)’){ifStackEmpty(s)//调用判栈空函数return0;//若栈为空返回0；否则出栈elsePop(s);}Page10of4710if(StackEmpty(s))//调用判栈空函数printf(“配对正确！”);//若栈空，说明配对正确，并返回1elseprintf(“配对错误！”);//配对错误返回0}Page11of4711习题4一.名词解释（1）队列——只允许在一端进行插入，另一端进行删除操作的线性表称为队列。其最大的特点是“先进先出”。（2）顺序队列——采用顺序存储结构的队列称为顺序队列。（3）链队列——采用链式存储结构的称队列为链队列。（4）循环队列——为了解决顺序队列中“假溢出”现象，将队列的存储空间想象为一个首尾相链的环（即把队头元素与对尾元素链结起来），存储在其中的队列称为循环队列。二．判断题（下列各题，正确的请在前面的括号内打√；错误的打ㄨ）（1）√（2）√（3）ㄨ（4）√（5）ㄨ（6）ㄨ三．填空题1．先进先出2．队尾队头3．队列是否为空队列是否为满4．可变的5．-1NULL6．O(n)O(1)O(1)O(1)7．front==rearfront==(rear+1)%MAXLENMAXL