资源描述：
《数据结构1-3章习题课.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、习题课（1~3章）1一、填空题数据的逻辑结构被分为、、和4种.数据的存储结构被分为、2种.在线性结构、树形结构和图形结构中，直接前驱和直接后继结点之间分别存在着、和的联系。4.一个算法应具有、、输入和输出特性.5.一个算法的效率主要由和来度量。6.抽象数据类型包括___________和______________。2在顺序表中插入一个元素，需要平均移动元素，具体移动的元素个数与有关。8.在顺序表中逻辑上相邻的元素的物理位置紧邻。单链表中逻辑上相邻的元素的物理位置紧邻。9.在单链表中，除了首元结点外，任一结点的存储位置由指示。10.在单链表中设置头
2、结点的作用是。11.栈的特点是。12.队列的特点是。13.在能存放m个元素的循环队列中，允许最多存放个元素。3从一维数组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;}416.一维数组逻辑结构是,存储结构是.对于二维数组有和两种不同的存储方式.对于一个二维数组A[m]
3、[n],若采用行优先顺序存储的方式,则任一数组元素A[i][j]相对于A[0][0]的地址为. 17.栈的插入和删除操作是在进行.当利用大小为n的 数组顺序存储一个栈时,假定top==n表示栈空,则向这个栈插 入一个元素时,首先应执行语句修改top指针. 18.队列的插入操作在进行,删除操作在进行. 19.在循环队列中,队头指针指向队头元素的位置,队尾指针指向队尾元素的位置. 20.在一个顺序栈中,判断队空的条件为,判断队满的条件 为.5补充题:按增长率由小到大的顺序排列下列各函数：2100，(3/2)n，(2/3)n，(4/3)n，nn，n2/3
4、，n1/2，n!，n，log2n，n/logn2，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结点的语句序列是。在表尾插入
5、S结点的语句序列是。P->link=S;(2)p->link=p->link->link;P->link=S->link;(4)S->link=P->link;S->link=L;(6)S->link=NULL;Q=P;while(P->link!=Q)P=P->link;while(P->link!=NULL)P=P->link;P=Q;(11)P=L;(12)L=S;(13)L=P;8四、设有一个10*10的对称矩阵A[10][10]，采取按行压缩存储的方式存放于一个一维数组B[]中，则数组B[]的容量应有多大？若设A[0][0]为第一个元素，
6、存放于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)=439五、（1）画出执行下列各行语句后各指针及链表的示意图。ListNode*L=newListNode();P=L;for(i=1;i<=4;i++){ListNode*Q=newListNode();P->link=Q;P=P->li
7、nk;P->data=2*i-1;}P->link=NULL;for(i=4;i>=1;i--){Insert(2*i,i+1);for(i=1;i<=3;i++){Remove(i);}10六、简述以下算法的功能。（1）voidA(LinkL){//L是无表头结点的单链表if(L&&L->link){Q=L;L=L->link;P=L;while(P->link)P=P->link;P->link=Q;Q->link=NULL;}11(2)voidBB(ListNode*s;ListNode*q){p=s;while(p-link!=q)p-p-
8、>link;p->link=s;}voidAA(ListNode*pa;ListNode*pb){BB(pa,pb);//
