数据结构1-2章习题课答案

1习题课（1~2章）2一、填空题1.数据的逻辑结构被分为、、和4种.2.数据的存储结构被分为、2种.3.在线性结构、树形结构和图形结构中，直接前驱和直接后继结点之间分别存在着、和的联系。4.一个算法应具有、、输入和输出特性.5.一个算法的效率主要由和来度量。6.抽象数据类型包括___________和______________。37.在顺序表中插入一个元素，需要平均移动元素，具体移动的元素个数与有关。8.在顺序表中逻辑上相邻的元素的物理位置紧邻。单链表中逻辑上相邻的元素的物理位置紧邻。9.在单链表中，除了首元结点外，任一结点的存储位置由指示。10.在单链表中设置头结点的作用是。414.从一维数组A[n]中顺序找出一个最大值元素的时间复杂度为,输出一个二维数组B[m][n]中所有元素值的时间复杂度为.15.在下面的程序中，s=s+p语句的执行次数为,p*=j语句的执行次数为,该程序段的时间复杂度为.inti=0;s=0;while(++i=n){intp=1;for(intj=1;j=i;j++)p*=j;s=s+p;}516.一维数组逻辑结构是,存储结构是.对于二维数组有和两种不同的存储方式.对于一个二维数组A[m][n],若采用行优先顺序存储的方式,则任一数组元素A[i][j]相对于A[0][0]的地址为.6补充题:按增长率由小到大的顺序排列下列各函数：2100，(3/2)n，(2/3)n，(4/3)n，nn，n2/3，n1/2，n!，n，log2n，n/log2n，log22n，log2(log2n)，nlog2n，nlog2n7补充题答案:答:按增长率由小到大的顺序各函数为：(2/3)n，2100，log2(log2n)，log2n，log22n，n1/2，n2/3，n/log2n，n，nlog2n,(4/3)n，(3/2)n，n!，nnnlogn28二、已知L是无表头结点的单链表，且P结点既不是首元结点，也不是尾结点，试从下列提供的答案中选择合适的语句序列。a.在P结点后插入S结点的语句序列是。b.在P结点前插入S结点的语句序列是。c.在表首插入S结点的语句序列是。d.在表尾插入S结点的语句序列是。(1)P-next=S;(2)p-next=p-next-next;(3)P-next=S-next;(4)S-next=P-next;(5)S-next=L;(6)S-next=NULL;(7)Q=P;(8)while(P-next!=Q)P=P-next;(9)while(P-next!=NULL)P=P-next;(10)P=Q;(11)P=L;(12)L=S;(13)L=P;9四、设有一个10*10的对称矩阵A[10][10]，采取按行压缩存储的方式存放于一个一维数组B[]中，则数组B[]的容量应有多大？若设A[0][0]为第一个元素，存放于B[0]，且数组A[][]的每一个数组元素在数组B[]中占一个数组元素位置，则A[8][5]在数组B[]中地址是多少？答案：数组B应有55个元素，对于下三角矩阵，LOC(A[8][5])=1+…+8+5=41对于上三角矩阵，LOC(A[8][5])=LOC(A[5][8])=10+9+8+7+6+(8-5)=4310五、（1）画出执行下列各行语句后各指针及链表的示意图。Node*L=newNode();P=L;for(i=1;i=4;i++){Node*Q=newNode();P-next=Q;P=P-next;P-data=2*i-1;}P-next=NULL;for(i=4;i=1;i--){Insert(2*i,i+1);for(i=1;i=3;i++){Delete(i);}11六、简述以下算法的功能。（1）voidA(nextL){//L是无表头结点的单链表if(L&&L-next){Q=L;L=L-next;P=L;while(P-next)P=P-next;P-next=Q;Q-next=NULL;}12(2)voidBB(ListNode*s;ListNode*q){p=s;while(p-next!=q)p-p-next;p-next=s;}voidAA(ListNode*pa;ListNode*pb){BB(pa,pb);//pa和pb分别指向单循环链表中的两个结点。BB(pb,pa);}13数据结构:所研究内容的着重点主要体现在三个方面：第一是数据间的逻辑关系，即数据元素之间的关系。第二是数据的存储关系，即数据在计算机中的存储结构。第三是算法，即定义在逻辑关系上的一组操作。因此，简单说来，数据结构所研究的问题是如何将现实世界中的事物合理描述为计算机世界中所研究的对象，并根据研究对象的特点，分析对象之间的关系、存储结构和操作的学科。1.试说明基本数据类型、数据结构和抽象数据类型的联系与差异。基本数据类型（DataType）：在程序设计高级语言中，数据类型用来说明一个数据在数据分类中的归属。它是数据的一种属性。这个属性限定了该数据的变化范围。高级语言中都有基本数据类型。例如在C、C++和Java语言中，有基本类型int（整型）、float（浮点型）和char（字符型），有构造类型数组、结构、联合、指针、枚举型和自定义等。数据类型仅局限于计算机中定义并实现了的数据类型;14抽象数据类型：是指一个数学模型以及定义在该模型上的一组操作。抽象数据类型的定义仅取决于抽象数据类型的逻辑特性，与它在计算机内部如何表示和实现无关。即不论其内部结构如何变化，只要数学特性不变，都不影响抽象数据类型外部的使用。抽象数据类型除了计算机中定义并实现了的数据类型；还包括用户在设计软件系统时自己定义的数据类型。151-5试说明数据的逻辑结构、存储结构和算法三者之间的关系。1个数据逻辑结构可有多种不同的存储结构；存储结构是对逻辑结构实现；算法是基于逻辑结构对操作的实现；函数是基于存储结构对算法的实现，是程序；答：数据的逻辑结构、存储结构和算法是数据结构所讨论的三个方面。161-6请给出下列函数的大O和Ω表示：nnnnnnnnnnnnn5log,log,2log,2100225.12O(n1/2logn²)O(n²)O(n1.5)O(n1/2)172-1．描述以下三个概念的区别：头指针、头结点、首结点（第一个元素结点）。在单链表中设置头结点的作用是什么？答：首结点就是存放数据元素的第一个元素结点，头结点是为了插入和删除的方便说增设的一个结点，头指针是指向链表中第一个结点的存储位置，在没有头结点的链表中，头指针指向链表中的首结点，在有头结点的链表中，头指针指向链表中的头结点。习题2（p55）182-4已知二维数组Am,m采用按行优先顺序存放，每个元素占K个存储单元，并且第一个元素的存储地址为Loc(a00)，请写出求Loc(aij)的计算公式。如果采用列优先顺序存放呢？答：行优先顺序存放时:Loc(aij)=Loc(a00)+(i*m+j)*K列优先顺序存放时:Loc(aij)=Loc(a00)+(j*m+i)*K192-5在链表类的实现中增加一个成员函数实现对表中元素置逆的操作（设原链表为a0,a1,…,an-2,an-1；则置逆后的序列为an-1,an-2,…,a1,a0）。对于有n个元素的线性表，你的算法的运行时间应为O(n)。voidLinkList::Inverse(){if(head-next==NULL)return;p=head-next;head-next=NULL;while(p!=NULL){q=p-next;p-next=head-next;head-next=p;p=q;}}202-10设计一个算法，将数组A(0..n-1)中的元素循环右移k位，假设原数组序列为a0,a1,…,an-2,an-1；移动后的序列为an-k,an-k+1,…,a0,a1,…,an-k-1。要求只用一个元素大小的附加存储，元素移动或交换次数为O(n)。voidyouyi(inta[],intn,intk){intb;for(inti=0;ik;i++){b=a[n-1];for(j=n-2;j=0;j--)a[j+1]=a[j];a[0]=b;}}21补充题1.数组置逆voidinverse(DataTypeA[],intn){for(i=0;in/2;i++){temp=A[i];A[i]=A[n-1-i];A[n-1-i]=temp;}}222:求鞍点:二维数组中行最小,列最大的元素voidminmax(intA[][],intm,intn){for(i=0;im;i++){row=A[i][0];k=0;for(j=1;jn;j++)if(A[i][j]row){k=j;row=A[i][j];}tag=1;h=0;while(tag&&hm){if(A[h][k]row)tag=0;elseh++;}if(tag)couti“”j“”rowendl;}23练习题：3.设数组A[n]中有多个零元素，是写一函数，将A中所有非零元素依次移动数组A的前端。4.设计一个算法，找单链表中值最大的结点。243：设数组A[n]中有多个零元素，是写一函数，将A中所有非零元素依次移动数组A的前端。voidcompact(intA[]，intn){k=0;for(i=0;in;i++){if(A[i]!=0){if(i!=k)A[k]=A[i];k++;}for(i=k;in;i++)A[i]=0;}25intMax(ListTypehead){if(!head-next)return-1;maxvalue=-9999;p=head-next;while(p){if(p-datamaxvalue){maxvalue=p-data;p=p-next;}returnmaxvalue;}4.设计一个算法，找单链表中值最大的结点。