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

《数据结构1-2章习题课答案.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、习题课（1~2章）1一、填空题数据的逻辑结构被分为、、和4种.数据的存储结构被分为、2种.在线性结构、树形结构和图形结构中，直接前驱和直接后继结点之间分别存在着、和的联系。4.一个算法应具有、、输入和输出特性.5.一个算法的效率主要由和来度量。6.抽象数据类型包括___________和______________。2在顺序表中插入一个元素，需要平均移动元素，具体移动的元素个数与有关。8.在顺序表中逻辑上相邻的元素的物理位置紧邻。单链表中逻辑上相邻的元素的物理位置紧邻。9.在单链表中，除了首元结点外，任一结点的存储位置由指示。10.在单链表中设置头结点的作用是。3从一维数组A[n]中顺序

2、找出一个最大值元素的时间复杂度为,输出一个二维数组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;}416.一维数组逻辑结构是,存储结构是.对于二维数组有和两种不同的存储方式.对于一个二维数组A[m][n],若采用行优先顺序存储的方式,则任一数组元素A[i][j]相对于A[0][0]的地址为.5补充题:按增长率由小到大的顺序排列下列各函数：2100，(3/2)n，(2/

3、3)n，(4/3)n，nn，n2/3，n1/2，n!，n，log2n，n/log2n，log22n，log2(log2n)，nlog2n，nlog2n6补充题答案:答:按增长率由小到大的顺序各函数为：(2/3)n，2100，log2(log2n)，log2n，log22n，n1/2，n2/3，n/log2n，n，nlog2n,(4/3)n，(3/2)n，n!，nn7二、已知L是无表头结点的单链表，且P结点既不是首元结点，也不是尾结点，试从下列提供的答案中选择合适的语句序列。在P结点后插入S结点的语句序列是。在P结点前插入S结点的语句序列是。在表首插入S结点的语句序列是。在表尾插入S结

4、点的语句序列是。P->next=S;(2)p->next=p->next->next;P->next=S->next;(4)S->next=P->next;S->next=L;(6)S->next=NULL;Q=P;while(P->next!=Q)P=P->next;while(P->next!=NULL)P=P->next;P=Q;(11)P=L;(12)L=S;(13)L=P;8四、设有一个10*10的对称矩阵A[10][10]，采取按行压缩存储的方式存放于一个一维数组B[]中，则数组B[]的容量应有多大？若设A[0][0]为第一个元素，存放于B[0]，且数组A[][]的每一个数组

5、元素在数组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)=439五、（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*

6、i,i+1);for(i=1;i<=3;i++){Delete(i);}10六、简述以下算法的功能。（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;}11(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分别指向单循环链表中的两

7、个结点。BB(pb,pa);}12数据结构:所研究内容的着重点主要体现在三个方面：第一是数据间的逻辑关系，即数据元素之间的关系。第二是数据的存储关系，即数据在计算机中的存储结构。第三是算法，即定义在逻辑关系上的一组操作。因此，简单说来，数据结构所研究的问题是如何将现实世界中的事物合理描述为计算机世界中所研究的对象，并根据研究对象的特点，分析对象之间的关系、存储结构和操作的学科。试说明基本数据类型、数据结构和抽象数据类型的联系与差异。