孤心无意
4、在单链表中，要取得某个元素，只要知道该元素的指针即可，因此，单链表是随机存取的存储结构。 5、链表的每个结点中，都恰好包含一个指针。
6、线性表中每个元素都有一个直接前驱和直接后继。
7、线性表中所有元素的排列顺序必须由小到大或由大到小。 8、静态链表的存储空间在运算中可以改变大小。
9、静态链表既有顺序存储结构的优点，又有动态链表的优点。所以，它存取表中的第i个元素的时间与i无关。
10、静态链表中能容纳元素个数的最大数在定义时就确定了，以后不能增加。 11、静态链表与动态链表的插入、删除操作类似，不需做元素的移动。 12、线性表的顺序存储结构优于链式存储结构。
15、在双链表中，可以从任一结点开始沿同一方向查找任何其他结点。F
数据结构复习题：线性表 算法分析题
1、己知一个顺序表L,其中的元素按值非递减有序排列,设计一个算法插入一个元素x后保持该顺序表仍按递减有序排列。要求算法的空间复杂度为O(1)。
2、设计一个算法从顺序表L中删除所有值为X的元素。要求算法的空间复杂度为O(1)。
3、从顺序表L中删除重复的元素,并使剩余元素间的相应次序保持不变.要求本算法的空间复杂记度为O(1)。 4、有一个单链表(不同结点的数据域值可能相同),其头指针为head,设计一个算法计算数据域为x的结点个数。 5、己知线性表元素递增有序,并以带头结点的单链表作存储结构,设计一个高效算法,删除表中所有值大于mink且小于maxk的元素(若表中存在这样的元素)。并分析所写算法的时间复杂度。 6、设计一个在带头结点的单链表中删除一个最小值结点的高效算法。
7、有一个不带头结点的单链表L(至少有1人结点),其头指针为head,设计一个算法将L逆置,即最后一个结点变成第一个结点,原来倒数第二个结点变成第二个结点,如此等等。
8、用单链表表示集合,设计一个算法求两个集合的差。要求不破坏原有的结点。 9、用单链表表示集合,设计一个算法求两个集合的并。要求不破坏原有的结点。
10、设计一个算法,将一个头结点指针为a的单链表A分解成两个单链表A和B,其头结点指针分别为a和b,使得A链表中含有原链表A中序号为奇数的元素,而B链表中含有原链表A中序号为倒数的元素,且保持原来的相对顺序。 11、有一个单链表,其结点的元素值以递增有序排列,设计一个算法删除该单链表中多余的元素值相同的结点。 12、己知两个存放整数的有序单链表(己按整数从小至大的顺序排序),指针L1和L2分别指向这两个单链表的头结点。设计一个算法,将L1和L2合并成一个单链表,且新的链表仍按整数由小到大的顺序排列,新的单链表的结点由L1和L2的结点构成。要求合并后的单链表利用原来单链表的存储空间。
13、设计一个算法,将线性表lb连接到la之后,要求其时间复杂度为O(1),占用的辅助空间尽量小。描述所用的结构。
14、设指针p指向双链表中的结点X,指针f指向将要插入的新结点Y,Y要插入在结点X之后,写出指针需要修改的有关步骤。
15、有一个循环双链表,每个结点由两个指针(prior和next)以及关键字(data)构成,p指向其中某一结点,设计一个算法从该循环双链表中删除p所指的结点。
16、设有一个循环双链表,其中有一结点的指针为p,设计一个算法将p与其后续结点进行交换。
19、设A和B是两个单链表(带头结点)，其表中元素递增有序。设计一个算法将A和B归并成一个按元素值递增有序的单链表C，要求辅助空晨为O(1)，并分析算法的时间复杂度。
- 13 -
数据结构复习题：线性表 填空题
1、在线性结构中第一结点_____前驱结点，其余每个结点有且只有______个前驱结点；最后一个结点______后继结点。
2、对于顺序存储的线性表，当随机插入或删除一个元素时，约需平均移动表长______的元素。
3、对于长度为n的顺序表，插入或删除元素的时间复杂性为________；对于顺序栈或队列，插入或删除元素的时间复杂性为_________。
4、在线性表的顺序存储中，元素之间的逻辑关系是通过_____相邻位置_____决定的；在线性表的链接存储中，元素之间的逻辑关系是通过______连接指针______决定的。 5、一个单链表中删除*p结点时，应执行如下操作: (1)q=p->next;
(2)p->data=p->next->data; (3)p->next=__________; (4)free(q);
6、对于线性表的顺序存储，需要预先分配好存储空间，若分配太多则容易造成存储空间的__________，若分配太少又容易在算法中造成_____溢出_____，因此适应于数据量变化不大的情况；对于线性表的链接存储(假定采用动态结点)，不需要__________存储空间，存储器中的整个____动态存储区______都可供使用，分配和回收结点都非常方便，能够有效地利用存储空间，在算法中不必考虑_____溢出_____的发生，因此适应数据量变化较大的情况。
7、从顺序表中删除第i个元素时，首先把第i个元素赋给_____变参或函数名_____带回，接着从______连接指针_______开始向后的所有元素均___________一个位置，最后使线性表的长度_____________。
8、向一个长度为n的顺序表中的第i个元素(0<=i<=n-1)之前插入一个元素时，需向后移动______个元素。 9、在一个长度为n的顺序表删除第i个元素(0<=i<=n-1)时，需向前移动______个元素。 10、在单链表中设置头结点的作用是_____简化插入、删除算法______。 11、在单链表中，要删除某一指定的结点，必须找到该结点的_______结点。 12、访问单链表中的结点，必须沿着_____指针链___依次进行。
13、在双链表中，每个结点有两个指针域，一个指向________，另一个指向_________。 14、在___循环双___链表上，删除最后一个结点，其算法的时间复杂度为O(1)。 15、在一个单链表中的p所指结点之前插入一个s所指结点时，可执行如下操作。 (1)s->next=_________。 (2)p->next=s; (3)t=p->data;
(4)p->data=_________。 (5)s-.data=_________。
16、在一个单链表中删除p所指结点时，应执行以下操作： q=p->next;
p_data=p->next->data; p->next=______; free(q);
17、在一个单链表中p所指结点之后插入一个s所指结点时，应执行s->next=_______和p->next=________的操作。
18、对于一个具有n个结点的单链表，在*p结点后插入一个新结点的时间复杂度是____O(1)____；在给定值
- 14 -
为x的结点后插入一后新结点的时间复杂度是________。
19、在线性表的顺序存储中，元素之间的逻辑关系是通过___物理存储位置___决定的；在线性表的链式存储中，元素之间的逻辑关系是通过___链域的指针值___决定的。
20、在一个长度为n的顺序表中删除第i个元素(1<=i<=n)时，需向前移动_______个元素。 21、为了设置一个空的顺序表L，采用的操作是___L->length=0___。 22、删除顺序表的______元素，不需要移动任何元素。
23、删除顺序表的___最后一个___元素，不需要移动的元素最多。 24、在顺序表_____元素后面插入一个元素，不需要移动任何元素。 25、插入顺序表的______元素，需要移动的元素最多。
26、在长度为n的顺序表L中查找指定元素值的元素，其时间复杂度为______。 27、求单链表长度的时间复杂度为_______。
28、删除单链表L中某结点*p之后的一个结点，其时间复杂度为______。 29、删除单链表L中某结点*p之前的一个结点，其时间复杂度为___O(n)___。
30、在一个单链表(己知每个结点含有数据域data和指针域next)中删除p所指结点时，应执行以下操作： (1)q=p->next;
(2)p->data=q->data; (3)p->next = _____; (4)free(q);
31、在一个单链表中的p所指结点之后插入*s结点时，应执行s->next=_____和p->next=______的操作。 32、对于一个具有n个结点的单链表，在*p结点后插入一个新结点的时间复杂度是_______;在给定值为x的结点后插入一个新结点的时间复杂度是_______。
33、删除双链表L中某结点*p之后的一个结点，其时间复杂度为_______。 34、删除双链表L中某结点*p之前的一个结点，其时间复杂度为_______。 35、在非循环的______链表中，可以用表尾指针代替表头指针。
36、对于双链表，在两个结点之间插入一个新结点需要修改的指针共______。 37、在一个双链表中，若要在*p结点之前插入结点*q，则执行的操作是______。 38、循环单链表L为空的条件是_____。 39、在单链表中,结点与结点之间的逻辑关系不是通过存储单元的顺序来表示的,而是通过___指向下一个结点的指针___来实现的.
40、对于一个长度为n的顺序存储的线性表，在表头插入元素的时间复杂度为____________，在表尾插入元素的时间复杂度为____________。
41、对于一个单链接存储的线性表，在表头插入结点的时间复杂度为____________，在表尾插入元素的时间复杂度为____________。
42、在线性表的顺序存储中，若一个元素的下标为i，则它的前驱元素的下标为____________，后继元素的下标为____________。
43、在线性表的单链接存储中，若一个元素所在结点的地址为p，则其后继结点的地址为
_____p->next_______，若p为一个数组a中的下标，则其后继结点的下标的______a[p]->next______。 44、在循环单链表中，最后一个结点的指针域指向____________结点。
45、在双向链表中每个结点包含有两个指针域，一个指向其____________结点，另一个指向其____________结点。
46、在循环双向链表中表头结点的左指针域指向____________结点，最后一个结点的右指针域指向____________结点。
47、在以ＨＬ为表头指针的带表头附加结点的单链表和循环单链表中，链表为空的条件分别为____________和____________。
- 15 -
50、在由数组a中元素结点构成的单链表中，在下标为i的结点的后面插入一个下标为j的结点时，需要进行的操作为____________和____________语句。 数据结构复习题：线性表 问答题
1、线性表有两种存储结构：一是顺序表，二是链表。试问： (1)两种存储表示各有哪些主要优缺点?
(2)如果有n个线性表同时并存，并且在处理过程中各表的长度会动态发生变化，线性表的总数也会自动地改变。在此情况下，应选用哪种存储结构?为什么?
(3)若线性表的总数基本稳定，且很少进行插入和删除，但要求以最快的速度存取线性表中的元素，那么，应采用哪种存储结构?为什么?
解答：(1)顺序存储是按索引（隐含的）直接存取数据元素，方便灵活，效率高，但插入、删除操作时将引起元素移动，因而降低效率；链接存储内存采用动态分配，利用率高，但需增设指示结点之间有序关系的指针域，存取数据元素不如顺序存储方便，但结点的插入、删除操作十分简单。 (2)应选用链接表存储结构。其理由是，链式存储结构用一组任意的存储单元依次存储线性表里各元素，这里存储单元可以是连续的，也可以是不连续的。这种存储结构，在对元素作插入或删除运算时，不需要移动元素，仅修改指针即可。所以很容易实现表的容量扩充。
(3)应选用顺序存储结构。其理由是，每个数据元素的存储位置和线性表的起始位置相差一个和数据元素在线性表中的序号成正比的常数。由此，只要确定了起始位置，线性表中任一数据元素都可随机存取，所以线性表的顺序存储结构是一种随机存取的存储结构。而链表则是一种顺序存取的存储结构。 2、用线性表的顺序结构来描述一个城市的设计和规划合适吗?为什么?
不合适。因为一个城市的设计和规划涉及非常多的项目，很复杂，经常需要修改、 扩充和删除各种信息，才能适应不断发展的需要。有鉴于此，顺序线性表不能很好适应其需要，故是不合适的。 3、在单链表和双向表中，能否从当前结点出发访问到任一结点?
在单链表中只能由当前结点访问其后的任一结点，因为没有指向其前驱结点的指针。而在双向链表中，既有指向后继结点的指针又有指向前驱结点的指针，故可由当前结点出发访问链表中任一结点。 4、编写下列算法
(1)向类型有list的线性表L的第i个元素（0≤i≤L.len）之后插入一个新元素x。 (2)从类型为list的线性表L中删除其值等于x的所有元素。
(3)将两个有序表A和B合并成一个有序表C，其中A，B，C均为list类型的变参。 (1) 解答: status insert(SqList L,int i,ElemType x){
// 向线性表L中第i个元素之后插入值为x的新元素 (1) if (L.len = =m0) error('overflow');
(2) if (i<0) || (i>L.len) error ('out of range'); (3) for (j=L.len ;j>= i＋1;--j ) L.vec[j＋1]＝L.vec[j]; }
(4) L.vec[i＋1]＝x; (5) L.len＝len＋1; }
(2) 解答: status delete(L,x) {
// 从线性表L中删除其值等于x的所有元素 i＝1;
while (i<＝L.len ) if (L.vec[i]= =x ){
- 16 -