数据结构1_2章节习题课解答.ppt

习 题 课（1~2章）;一、填空题 数据的逻辑结构被分为 、 、 和 4种. 数据的存储结构被分为 、 2种. 在线性结构、树形结构和图形结构中，直接前驱和 直接后继结点之间分别存在着 、 和 的联系。 4. 一个算法应具有 、 、 输 入和输出特性. 5. 一个算法的效率主要由 和 来度量。 6. 抽象数据类型包括___________和______________。 ;在顺序表中插入一个元素，需要平均移动 元素，具体移动的元素个数与 有关。 8. 在顺序表中逻辑上相邻的元素的物理位置 紧邻。 单链表中逻辑上相邻的元素的物理位置 紧邻。 9. 在单链表中，除了首元结点外，任一结点的存储位 置由 指示。 10. 在单链表中设置头结点的作用是 。 ;从一维数组A[n]中顺序找出一个最大值元素的时间复杂度 为 ,输出一个二维数组B[m][n]中所有元素值的时 间复杂度为 . ;16. 一维数组逻辑结构是 ,存储结构是 .对于二维数组有 和 两种不同的存储方式.对于一个二维数组A[m][n],若采用行优先顺序存储的 方式, 则任一数组元素A[i][j]相对于A[0][0]的地址为 .;;补充题答案: 答:按增长率由小到大的顺序各函数为： (2/3)n， 2100， log2(log2n) ， log2n， log22n， n1/2 ， n2/3， n/log2n， n，nlog2n, (4/3)n， (3/2)n， n!， nn ;二、已知L是无表头结点的单链表，且P结点既不是首 元结点，也不是尾结点，试从下列提供的答案中选  择合适的语句序列。;;五、（1）画出执行下列各行语句后各指针及链表的示意图。 Node *L=new Node( ); P=L; for(i=1; i=4; i++) { Node *Q=new Node( ); 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); } ;六、简述以下算法的功能。 （1）void A(next L ) { //L是无表头结点的单链表 if(L L-next) { Q=L; L=L-next; P=L; while(P-next) P=P-next; P-next=Q; Q-next=NULL; } ;(2) void BB(ListNode *s; ListNode *q) { p=s; while(p-next!=q) p-p-next; p-next=s; } void AA (ListNode *pa; ListNode *pb) { BB(pa,pb); //pa和pb分别指向单循环链表中的两个结点。 BB(pb,pa); };数据结构: 所研究内容的着重点主要体现在三个方面： 第一是数据间的逻辑关系，即数据元素之间的关系。 第二是数据的存储关系，即数据在计算机中的存储结构。 第三是算法，即定义在逻辑关系上的一组操作。 因此，简单说来，数据结构所研究的问题是如何将现实