数据结构作业3

1、数据结构第三次作业一 选择题1在下列序列中，不是线性表的是（）。A）(a,b,c) B）(AB,CD) C）(a,true,c)） D)(a,b,c,d)2线性链表中各链结点之间的地址（）。A）必须连续B）部分地址必须连续C）不一定连续D）连续与否无所谓3如某链表中最常用的操作是在最后一个结点后插入一个结点和删除最后一个结点，则（）存储方式最节省运行时间。A）单链表B）带头结点的单链表C）单循环链表D）带头结点的双循环链表5线性表的顺序存储结构具有的特点是（ ）。A）可直接随机访问任一元素B）插入删除不需要移动元素C）不必事先估计元素个数D）所需空间与线性表长度成正比ADCD 1.设A是一个线

2、性表（al，a2，,an），采用顺序存储结构，则在等概率的前提下，平均每插入一个元素需要移动的元素个数为多少？ 2. 在单链表和双向链表中，能否从当前结点出发访问到任一结点？2)2)1(110)1(11E)1(pE11nnnnnnninniii二 综合题分析：假设 pi 是在第i个元素之前插入元素的概率，则在长度为n的线性表中插入一个元素所需移动元素次数的平均次数为：单链表不能,单链表中只有后继节点，只能访问到当前节点后面的节点;双向链表中可以实现，原因在于双向链表有前驱节点和后继节点，可以访问当前节点前后位置的任一节点。3线性表可用顺序表或链表存储。试问：(1) 两种存储表示各有哪些主要优缺

3、点?(2) 如果有n个表同时并存，并且在处理过程中各表的长度会动态发生变化，表的总数也可能自动改变、在此情况下，应选用哪种存储表示？为什么？(3) 若表的总数基本稳定，且很少进行插入和删除，但要求以最快的速度存取表中的元素，这时，应采用哪种存储表示？为什么？Answer:(1)顺序表需要提前估计线性表的大小并且插入删除效率低需要移动大量结点，优点在于表中节点没有浪费存储空间，并且可以按位置随机访问；链表优点在于插入删除效率高， 无需提前估计表的大小，表中元素个数没有限制，缺点在于访问结点需要从表头遍历查找并且每个节点除了储存元素还需要附加空间存储指针。(2)链表 表的大小不固定(3)顺序表，表

4、大小固定，插入删除操作少，按位置随机存取速度快4针对带表头结点的单链表，试编写下列函数。(1) 定位函数Locate：在单链表中寻找第i个结点。若找到，则函数返回第i个结点的地址；若找不到，则函数返回NULL。Node *LinkLocate(int i) if ( i next; int j=0; while(p & j!=i) p=p-next; j+; if(p = null) return -1; else return p; 4针对带表头结点的单链表，试编写下列函数。(2) 求最大值函数max：通过一趟遍历在单链表中确定值最大的结点。template E LinkMax()

5、Node * p; p=head-next; E j=p-data; while(p -next & p-data next-data) p=p-next; j=p-next-data; return j; 4针对带表头结点的单链表，试编写下列函数。(3) 统计函数number：统计单链表中具有给定值x的所有元素。template int LinkCount(E a) Node * p; p=head-next; int count=0; while(p) if(p-data=a) count+; p=p-next; return count; 4针对带表头结点的单链表，试编写下列函数

6、。(4) 建立函数create：根据一维数组an建立一个单链表，使单链表中各元素的次序与an中各元素的次序相同，要求该程序的时间复杂性为O(n)。template void LinkCreate(E a,int n) Node * p; p=head-next;/尾指针 尾插法 for(int i=0;inext=temp; temp-data=ai; p=temp-next; 4针对带表头结点的单链表，试编写下列函数。5) 整理函数tidyup：在非递减有序的单链表中删除值相同的多余结点。template void LinkSort() Node * p; p=head-next; whil

7、e(p&p-next) if(p-data=p-next-data) p-next=p-next-next; else p=p-next; return； template void LinkSort() Node *p=head-next,*temp; while(p!=null&p-next!=null) if (p-data = p-next-data ) temp = p-next; p-next=temp-next; delete temp; else p = p-link; 课本习题4.5 In the linked list implementation pres

8、ented in Section 4.1.2, the current position is implemented using a pointer to the element ahead of the logical current node. The more“natural”approach might seem to be to have curr point directly to the node containing the current element. However, if this was done, then the pointer of the node pre

9、ceding the current one cannot be updated properly because there is no access to this node from curr. An alternative is to add a new node after the current element, copy the value of the current element to this new node, and then insert the new value into the old current node. (a)What happens if curr

10、 is at the end of the list already? Is there still a way to make this work? Is the resulting code simpler or more complex than the implementation of Section 4.1.2? (b)Will deletion always work in constant time if curr points directly to the current node? In particular, can you make several deletions

11、 in a row?4.10 Section 4.1.3 presents an equation for determining the break-even point for the space requirements of two implementations of lists. The variables are D E Pand n. What are the dimensional units for each variable?Show that both sides of the equation balance in terms of their dimensional units. 在4.1.3中的公式，其中的变量有D E P和n.每一个变量的空间单位是什么？考虑其空间单位如何平衡左右两边的方程？分析：变量D是顺序表的表长。n表示顺序表中实际存储的元素个数，E代表存储一个元素需要的空间，常见单位从bytes到int不等，P代表链表节点中指针域所需的空间大小，常见