7．若某表最常用的操作是在最后一个结点之后插入一个结点或删除最后一个结点。则采用（ ）存储方式最节省运算时间。【北京理工大学 2000 一、1（2分）】
A．单链表 B．双链表 C．单循环链表 D．带头结点的双循环链表 8. 静态链表中指针表示的是（ ）. 【北京理工大学 2001 六、2（2分）】 A． 内存地址 B．数组下标 C．下一元素地址 D．左、右孩子地址
9. 链表不具有的特点是（ ） 【福州大学 1998 一、8 (2分)】 A．插入、删除不需要移动元素 B．可随机访问任一元素 C．不必事先估计存储空间 D．所需空间与线性长度成正比
10. 下面的叙述不正确的是（ ）【南京理工大学 1996 一、10（2分）】 A．线性表在链式存储时，查找第i个元素的时间同i的值成正比 B. 线性表在链式存储时，查找第i个元素的时间同i的值无关 C. 线性表在顺序存储时，查找第i个元素的时间同i 的值成正比 D. 线性表在顺序存储时，查找第i个元素的时间同i的值无关
11. 线性表的表元存储方式有(（1）)和链接两种。试指出下列各表中使用的是何种存储方式：表1是(（2）)存储方式；表2是(（3）)存储方式；表3是(（4）)存储方式；表4是(（5）)存储方式。表左的s指向起始表元。 供选择的答案：
A.连续 B.单向链接 C.双向链接 D.不连接 E.循环链接 F.树状 G.网状 H.随机 I.顺序 J.顺序循环 【上海海运学院 1995 二、1（5分）】
12.(1) 静态链表既有顺序存储的优点，又有动态链表的优点。所以，它存取表中第i个元素的时间与i无关。
(2) 静态链表中能容纳的元素个数的最大数在表定义时就确定了，以后不能增加。
(3) 静态链表与动态链表在元素的插入、删除上类似，不需做元素的移动。 以上错误的是（ ）【南京理工大学 2000 一、3（1.5分）】
A．（1），（2） B．（1） C．（1），（2）,(3) D.（2） 13. 若长度为n的线性表采用顺序存储结构，在其第i个位置插入一个新元素的算法的时间复杂度为（ ）(1Rlink=p;p->Llink->Rlink=q;q->Llink=q； B. p->Llink=q;p->Llink->Rlink=q;q->Rlink=p;q->Llink=p->Llink; C. q->Rlink=p;q->Llink=p->Llink;p->Llink->Rlink=q;p->Llink=q; D. q->Llink=p->Llink;q->Rlink=q;p->Llink=q;p->Llink=q;
24．在单链表指针为p的结点之后插入指针为s的结点，正确的操作是：（ ）。 A．p->next=s;s->next=p->next; B． s->next=p->next;p->next=s; C．p->next=s;p->next=s->next; D． p->next=s->next;p->next=s; 【青岛大学 2001 五、3（2分）】
25．对于一个头指针为head的带头结点的单链表，判定该表为空表的条件是（ ）
A．head==NULL B．head→next==NULL C．head→next==head D．head!=NULL 【北京工商大学 2001 一、5（3分）】
26. 在双向链表存储结构中，删除p所指的结点时须修改指针（ ）。 A． (p^.llink)^.rlink:=p^.rlink (p^.rlink)^.llink:=p^.llink; B． p^.llink:=(p^.llink)^.llink (p^.llink)^.rlink:=p; C． (p^.rlink)^.llink:=p p^.rlink:=(p^.rlink)^.rlink D． p^.rlink:=(p^.llink)^.llink p^.llink:=(p^.rlink)^.rlink; 【西安电子科技大学 1998 一、1（2分）】
27. 双向链表中有两个指针域，llink和rlink分别指向前趋及后继，设p指向链表中的一个结点，现要求删去p所指结点，则正确的删除是（ ）（链中结点数大于2，p不是第一个结点）
A．p^.llink^.rlink:=p^.llink; p^.llink^.rlink:=p^.rlink; dispose(p); B．dispose(p); p^.llink^.rlink:=p^.llink; p^.llink^,rlink:=p^.rlink; C．p^.llink^.rlink:=p^.llink; dispose(p); p^.llink^.rlink:=p^.rlink; D．以上A，B，C都不对。 【南京理工大学 1997 一、1（2分）】 二、判断
1. 链表中的头结点仅起到标识的作用。( )【南京航空航天大学 1997 一、1（1分）】
2. 顺序存储结构的主要缺点是不利于插入或删除操作。( )【南京航空航天大学1997 一、2（1分）】
3．线性表采用链表存储时，结点和结点内部的存储空间可以是不连续的。( ) 【北京邮电大学 1998 一、2（2分）】
4．顺序存储方式插入和删除时效率太低，因此它不如链式存储方式好。( ) 【北京邮电大学 2002 一、2（1分）】
5. 对任何数据结构链式存储结构一定优于顺序存储结构。( )【南京航空航天大学 1997 一、3（1分）】
6．顺序存储方式只能用于存储线性结构。( )
【中科院软件所 1999 六、1-2（2分）】【上海海运学院 1997 一、1（1分）】 7．集合与线性表的区别在于是否按关键字排序。( )【大连海事大学 2001 一、5 ( 1分)】
8. 所谓静态链表就是一直不发生变化的链表。( )【合肥工业大学 2000 二、1（1分）】
9. 线性表的特点是每个元素都有一个前驱和一个后继。( )【合肥工业大学2001 二、1（1分）】
10. 取线性表的第i个元素的时间同i的大小有关. ( )【南京理工大学 1997 二、9（2分）】
11. 循环链表不是线性表. ( )【南京理工大学 1998 二、1（2分）】 12. 线性表只能用顺序存储结构实现。( )【青岛大学 2001 四、2（1分）】
13. 线性表就是顺序存储的表。( )【青岛大学 2002 一、1（1分）】 14．为了很方便的插入和删除数据，可以使用双向链表存放数据。( ) 【上海海运学院 1995 一、1（1分）】 【上海海运学院 1997 一、2（1分）】 15. 顺序存储方式的优点是存储密度大，且插入、删除运算效率高。( ) 【上海海运学院 1996 一、1（1分）】 【上海海运学院 1999 一、1（1分）】
16. 链表是采用链式存储结构的线性表,进行插入、删除操作时，在链表中比在顺序存储结构中效率高。 ( ) 【上海海运学院 1998 一、2（1分）】 三、填空
1．当线性表的元素总数基本稳定，且很少进行插入和删除操作，但要求以最快的速度存取线性表中的元素时，应采用_______存储结构。【北方交通大学 2001 二、4】
2．线性表L=（a1,a2,…,an）用数组表示，假定删除表中任一元素的概率相同，则删除一个元素平均需要移动元素的个数是________。【北方交通大学 2001 二、9】
3．设单链表的结点结构为(data,next)，next为指针域，已知指针px指向单链表中data为x的结点，指针py指向data为y的新结点 , 若将结点y插入结点x之后，则需要执行以下语句:_______； ______;【华中理工大学 2000 一、4（2分）】
4．在一个长度为n的顺序表中第i个元素（11 DO BEGIN p:=p^.link; i:=i-1 END; (D)___ ;
WHILE jp^.pre^.freq DO p:=p^.pre; IF pq THEN [ （3）______ ]
]； IF （4）_ THEN [q^.next:=p, q^.pre;=p^.pre; p^.pre^.next:=q; p^.pre:=q] return(q);
END;【北京工业大学 1999 五 (12分)】
29．循环链表a和b的结点值为字母，其中a表非递减有序，下面的程序欲构造一个递增有序的循环链表c，其中结点的值为同时在a，b两链表中出现的字母，且c中字母不重复，请补上程序中空缺的部分，并估计算法的时间复杂度。（设a，b的结点数分别为m，n） TYPE
link=^node; node=RECORD
key:char; next:link END;
PROC jj(a,b:link; VAR c:link); VAR p,q,r,s:link; BEGIN
new(c);c^.next:=c; q:=a; p:=a^.next; WHILE pa DO [（1）___；
WHILE p^.key=p^.next^.key DO [q:=p; p=p^.next];｛跳过相同字母｝ r:=b^.next ; （2）_____;
WHILE r^.key p^.key DO r:=r^.next; IF rb THEN
[ s:=p; q^.next:=p^.next; （3） ; s^.next:=c^.next; c^.next:=s; c:=s ] ELSE [ q:=p; p:=p^.next ] ]; c:=c^.next；
END;
算法时间复杂度为O（4）___ 【北京工业大学 2000 四 (15分)】
30. 以下程序的功能是实现带附加头结点的单链表数据结点逆序连接，请填空完善之。
void reverse(pointer h)
/* h为附加头结点指针；类型pointer同算法设计第3题*/ { pointer p,q;
p=h->next; h->next=NULL; while((1)________)
{q=p; p=p->next; q->next=h->next; h->next=(2)________; } }【西南交通大学 2000 一、9】
31. 下面是用c语言编写的对不带头结点的单链表进行就地逆置的算法，该算法用L返回逆置后的链表的头指针，试在空缺处填入适当的语句。 void reverse（linklist &L）{ p=null；q=L； while（q！=null）
{ (1) ; q->next=p；p=q；(2)___ ; } (3)_____;
}【北京理工大学 2001 九、1 （6分）】
32．下面程序段是逆转单向循环链表的方法，p0 是原链表头指针，逆转后链表头指针仍为p0。
（可以根据需要增加标识符） p:= p0; q0:=NIL; WHILE （1）________ DO
BEGIN （2）________; （3）________;（4）______;（5）________ END; p^.next:= q0; p0 ^.next:=p; p0:=p;【中国人民大学 2000 二、1（4分）】
33．一个无头结点的线性链表(不循环)有两个域。数据域data，指针域 next，链首head，下面算法用read(num)读入数据，当num小于0时，输入结束。建立一个数据以递增序组成的链表。 PROC insert( head, x); {在链首为head的表中按递增序插入x} new(r);r＾.data:=x; IF head=NIL
THEN[ head:=(1) _____; r＾.next:= (2)________ ] ELSE IF (3)___ THEN [r＾ .next:=head; head:=r] ELSE [p:=head;
WHILE (4)___ AND (p＾.next≠NIL ) DO[q:=p; (5)___ ]; IF (6)___ THEN [ q＾ .next:=(7)___; r＾.next:= (8)____; ] ELSE [p＾.next:=(9)____; r＾.next:= (10)___; ] ] ENDP;
PROC creat(head);
head:= (11)______; read(num); WHILE num>0 DO
[ insert(head,num); read(num) ] ENDP;【南京理工大学 1999 三、4（11分）】
34. 一元稀疏多项式以循环单链表按降幂排列，结点有三个域，系数域coef ，指数域exp和指针域 next；现对链表求一阶导数 ，链表的头指针为ha，头结点的exp域为 –1。 derivative(ha)
{ q=ha ; pa=ha->next;
while( (1)_______)
{ if ( (2)____) { ( (3)__); free(pa); pa= ( (4) _); } else{ pa->coef ( (5) ___); pa->exp( (6)___); q=( (7) __);} pa=( (8)________); }
} 【南京理工大学 2000 三、3（10分）】
35.下面是删除单链表L中最大元素所在结点的类PASCAL语言算法，请在横线填上内容，完成其功能。 TYPE pointer =↑node； node=RECORD
data:integer; next: pointer END;
PROCEDURE delmax (L:pointer); VAR p,q,r:pointer; m:integer; BEGIN
r:=L； p:=L↑.next; IF pNIL THEN
[ m:=p↑.data; (1)________; p:=p↑.next; WHILE pNIL DO
[ IF (2)________THEN [ (3)________ ; m:=p↑.data; ] (4)________; p:=p↑.next; ]
q:=r↑.next; (5)______; dispose(q); ]
END;【北京科技大学 1998 二】
36．对单链表中元素按插入方法排序的C语言描述算法如下，其中L为链表头结点指针。请填充算法中标出的空白处，完成其功能。 typedef struct node
{int data; struct node *next; }linknode,*link; void Insertsort(link L) { link p,q,r,u;
p=L->next; (1)______; while((2)________) { r=L; q=L->next;
while((3)________&& q->datadata) {r=q; q=q->next;} u=p->next; (4)______; (5)______; p=u; }
}【北京科技大学 2001 二 （10分）】
37．下面是一个求两个集合A和B之差C=A-B的程序，即当且仅当e是A的一个元素，但不是B中的一个元素时，e才是C中的一个元素。集合用有序链表实现，初始时，A，B集合中的元素按递增排列，C为空；操作完成后A，B保持不变，C中元素按递增排列。下面的函数append(last,e)是把值为e的新结点链接在由指针last指向的结点的后面，并返回新结点的地址；函数difference(A,B)实现集合运算A-B，并返回表示结果集合C的链表的首结点的地址。在执行A-B运算之前，用于表示结果集合的链表首先增加一个附加的表头结点，以便新结点的添加，当A-B运算执行完毕，再删除并释放表示结果集合的链表的表头结点。 程序(a)（编者略去这个PASCAL程序） 程序（b）
typedef struct node{ int element; struct node *link; }NODE;
NODE *A，*B，*C;
NODE *append (NODE *last,int e)
{ last->link=(NODE*) malloc (sizeof(NODE)); last->link->element=e; return(last->link); }
NODE *difference(NODE *A,NODE *B) {NODE *C,*last;
C=last=(NODE*) malloc (sizeof(NODE)); while (1)___
if (A->elementelement)
{ last=append(last,A->element); A=A->link; }
else if (2) ___ { A=A->link; B=B->link; } ELSE (3) ___ ; while (4) __
{ last=append(last,A->element); A=A->link; }
(5) ___; last=C; C=C->link; free (last); return (C); }
/*call form:C=difference(A,B);*/【上海大学 2000 一、4 （10分）】 四 应用题
1．线性表有两种存储结构：一是顺序表，二是链表。试问：
（1）如果有 n个线性表同时并存，并且在处理过程中各表的长度会动态变化，线性表的总数也会自动地改变。在此情况下，应选用
9. 在单链表和双向链表中，能否从当前结点出发访问到任何一个结点? 【西安电子科技大学1999计应用一、1 （5分）】
10. 如何通过改链的方法，把一个单向链表变成一个与原来链接方向相反的单向链表？
【中国人民大学 2001 二、4 （2分）】
11. 下面是一算法的核心部分，试说明该算法的功能。 pre:=L↑.next;
{L是一单链表，结点有数据域 data和指针域 next} IF preNIL THEN WHILE pre↑.nextNIL DO
BEGIN p:=pre↑.next; IF p↑.data>=pre↑.data THEN pre:=p ELSE return(false) END;
return(true); 【燕山大学 2000 七、1 （7分）】
12. 设单链表结点指针域为next，试写出删除链表中指针p所指结点的直接后继的C语言语句。
【北京科技大学 2000 一、3】
13. 设单链表中某指针p所指结点（即p结点）的数据域为data，链指针域为next，请写出在p结点之前插入s结点的操作（PASCAL语句）。【北京科技大学 1999 一、2 （2分）】
14. 有线性表(a1,a2,…,an),采用单链表存储，头指针为H，每个结点中存放线性表中一个元素，现查找某个元素值等于X的结点。分别写出下面三种情况的查找语句。要求时间尽量少。
（1）线性表中元素无序。（2）线性表中元素按递增有序。 （3）线性表中元素按递减有序。
【北京邮电大学 1994 七 （7分）】
15．设pa，pb分别指向两个带头结点的有序（从小到大）单链表。仔细阅读如下的程序，并回答问题：
（1） 程序的功能。（2） s1，s2中值的含义。（3） pa，pb中值的含义。 PROCEDURE exam(pa,pb) BEGIN
p1:=pa↑.next; p2:=pb↑.next; pa↑.next:=∧; s1:=0; s2:=0; WHILE p1≠∧ AND p2≠∧ DO [ CASE p1↑.data
p1↑.data>p2↑.data: p2:=p2↑.next;
p1↑.data=p2↑.data: [p:=p1; p1:=p1↑.next; p↑.next:= pa↑.next; pa↑.next:= p; p2:= p2↑.next;s1:=s1+1; ]; END ];
WHILE p1≠∧ DO [ p:=p1; p1:=p1↑.next; dispose(p); s2:=s2+1 ] END;【南京航空航天大学 1995 十 （9分）】
16．写出下图双链表中对换值为23和15的两个结点相互位置时修改指针的有关语句。
结点结构为：(llink,data,rlink) 【北京邮电大学 1992 三、4 （25/4分）】 18．已知L是一个数据类型linkedlist的单循环链表，pa和pb是指向L中结点的指针。简述下列程序段的功能。【山东科技大学 2001 一、2 （5分）】 TYPE linkedlist=↑node; node=RECORD
data:datatype; next:linkedlist END; PROC Mp(pa,pb:linkedlist); PROC subp(s,q: linkedlist); p:=s;
WHILE p↑.nextq DO p:=p↑.next; p↑.next:=s
ENDP; subp(pa,pb); subp(pb,pa); ENDP;
19．设双向循环链表中结点的数据域、前驱和后继指针域分别为data,pre和next,试写出在指针p 所指结点之前插入一s结点的C语言描述语句。【北京科技大学 2001 一、3 （2分）】
20．本题给出一个子程序的框图，如图2，试填空完善此算法框图。该子程序用来寻找第一个均出现在三个整数单向链表f1，f2，f3中的相同整数。假定在调用该子程序前，这三个整数链表已按从小到大的次序排序，单向链表的形式如下图1的例子所示。
注：在图2的框图中：found和exit均为布尔型的变量，可取值为true和false。val是整型变量，用来存放第一个均出现在f1，f2，f3中的相同整数。若f1，f2和f3中无相同的整数，found 的值为false，否则found的值为true。f1↑.link表示访问f1所指结点的link域。 【哈尔滨工业大学 1999 三 （15分）】
21. 一线性表存储在带头结点的双向循环链表中，L为头指针。如下算法： （1）说明该算法的功能。（2）在空缺处填写相应的语句。 void unknown (BNODETP *L) { …
p=L->next; q=p->next; r=q->next； while (q!=L)
{ while (p!=L) && (p->data>q->data) p=p->prior； q->prior->next=r；(1) ______； q->next=p->next；q->prior=p；
(2) ______；(3) ______； q=r；p=q->prior； (4) ______；
}
} 【北京理工大学 1999 第二部分 数据结构 [7] （8分）】 五、算法设计题
1． 假设有两个按元素值递增次序排列的线性表，均以单链表形式存储。请编写算法将这两个单链表归并为一个按元素值递减次序排列的单链表，并要求利用原来两个单链表的结点存放归并后的单链表。 【北京大学 1998 三、1 （5分）】 类似本题的另外叙述有：
（1）设有两个无头结点的单链表,头指针分别为ha,hb,链中有数据域data,链域next,两链表的数据都按递增序存放,现要求将hb表归到ha表中,且归并后ha仍递增序,归并中ha表中已有的数据若hb中也有,则hb中的数据不归并到ha中,hb的链表在算法中不允许破坏。【南京理工大学1997 四、3（15分）】 PROCEDURE merge(ha,hb);
（2）已知头指针分别为la和lb 的带头结点的单链表中，结点按元素值非递减有序排列。写出将la 和 lb两链表归并成一个结点按元素值非递减有序排列的单链表（其头指针为 lc），并计算算法的时间复杂度。【燕山大学 1998 五 （20分）】
2. 图（编者略）中带头结点且头指针为ha和hb的两线性表A和B 分别表示两个集合。两表中的元素皆为递增有序。请写一算法求A和B的并集AUB。要求该并集中的元素仍保持递增有序。且要利用A和B的原有结点空间。【北京邮电大学 1992 二 （15分）】 类似本题的另外叙述有：
(1) 已知递增有序的两个单链表A，B分别存储了一个集合。设计算法实现求两个集合的并集的运算A:=A∪B【合肥工业大学 1999 五、1（8分）】
（2）已知两个链表A和B分别表示两个集合，其元素递增排列。编一函数，求A与B的交集，并存放于A链表中。【南京航空航天大学 2001 六（10分）】 （3）设有两个从小到大排序的带头结点的有序链表。试编写求这两个链表交运算的算法（即L1∩L2）。要求结果链表仍是从小到大排序，但无重复元素。【南京航空航天大学 1996 十一（10分）】
（4）己知两个线性表A ，B均以带头结点的单链表作存储结构，且表中元素按值递增有序排列。设计算法求出A与B的交集C，要求C另开辟存储空间，要求C同样以元素值的递增序的单链表形式存贮。
【西北大学 2000 五 ( 8分)】
（5）已知递增有序的单链表A,B和C分别存储了一个集合，设计算法实现A：=A∪（B∩C），并使求解结构A仍保持递增。要求算法的时间复杂度为O(|A|+|B|+|C|)。其中,|A|为集合A的元素个数。 【合肥工业大学 2000 五、1（8分）】
3. 知L1、L2分别为两循环单链表的头结点指针，m,n分别为L1、L2表中数据结点个数。要求设计一算法，用最快速度将两表合并成一个带头结点的循环单链表。【东北大学1996 二 (12分)】 类似本题的另外叙述有：
（1）试用类Pascal语言编写过程PROC join（VAR la：link； lb：link） 实现连接线性表la和lb(lb在后)的算法，要求其时间复杂度为0（1）， 占用辅助空间尽量小。描述所用结构。 【北京工业大学 1997 一、1 (8分)】
（2）设有两个链表，ha为单向链表，hb为单向循环链表。编写算法，将两个链表合并成一个单向链表，要求算法所需时间与链表长度无关。【南京航空航天大学 1997 四（8分）】
4. 顺序结构线性表LA与LB的结点关键字为整数。LA与LB的元素按非递减有序，线性表空间足够大。试用类PASCAL语言给出一种高效算法，将LB中元素合到LA中，使新的LA的元素仍保持非递减有序。高效指最大限度的避免移动元素。【北京工业大学 1997 一、2 (12分)】
5. 已知不带头结点的线性链表list，链表中结点构造为（data、link），其中data为数据域，link为指针域。请写一算法，将该链表按结点数据域的值的大小从小到大重新链接。要求链接过程中不得使用除该链表以外的任何链结点空间。【北京航空航天大学 1998 五（15分）】
6. 设L为单链表的头结点地址，其数据结点的数据都是正整数且无相同的，试设计利用直接插入的原则把该链表整理成数据递增的有序单链表的算法。【东北大学 1996 六 (14分)】 类似本题的另外叙述有：
（1）设一单向链表的头指针为head,链表的记录中包含着整数类型的key域,试设计算法,将此链表的记录按照key递增的次序进行就地排序.【中科院计算所 1999 五、1（10分）】
7. 设 Listhead为一单链表的头指针，单链表的每个结点由一个整数域DATA和指针域NEXT组成，整数在单链表中是无序的。编一PASCAL过程，将 Listhead
链中结点分成一个奇数链和一个偶数链，分别由P,Q指向，每个链中的数据按由小到大排列。程序中不得使用 NEW过程申请空间。【山东大学1993六( 15分)】 类似本题的另外叙述有：
（1）设计算法将一个带头结点的单链表A分解为两个具有相同结构的链表B、C，其中B表的结点为A表中值小于零的结点，而C表的结点为A表中值大于零的结点（链表A的元素类型为整型，要求B、C表利用A表的结点）。【北京理工大学 2000 四、2（4分）】
(2) 设L为一单链表的头指针，单链表的每个结点由一个整数域 data和指针域NEXT组成，整数在单链表中是无序的。设计算法，将链表中结点分成一个奇数链和一个偶数链，分别由P，Q指向，每个链中的数据按由小到大排列，算法中不得申请新的结点空间。【青岛海洋大学 1999 三（12分）】
(3) 将一个带头结点的单链表A分解为两个带头结点的单链表A和B，使得A表中含有原表中序号为奇数的元素，而B表中含有原表中序号为偶数的元素，且保持其相对顺序不变。 1) 写出其类型定义：
2) 写出算法。【山东大学 1998 九 (9分)】 【山东工业大学 2000 九（9分）】 8. 已知线性表（a1 a2 a3 …an）按顺序存于内存，每个元素都是整数，试设计用最少时间把所有值为负数的元素移到全部正数值元素前边的算法：例：（x,-x,-x,x,x,-x …x）变为（-x,-x,-x…x,x,x）。 【东北大学 1998 二 (15分)】 类似本题的另外叙述有：
（1）设有一元素为整数的线性表L=(a1,a2,a3,…,an),存放在一维数组A[N]中,设计一个算法,以表中an作为参考元素,将该表分为左、右两部分,其中左半部分每个元素小于等于an,右半部分每个元素都大于an, an位于分界位置上(要求结果仍存放在A[N]中)。【北京理工大学 1999 八（6分）】
（2）顺序存储的线性表A,其数据元素为整型,试编写一算法,将A拆成B和C两个表,使A中元素值大于等于0的元素放入B,小于0的放入C中.. 要求: 1）表B和C另外设置存储空间;
2）表B和C不另外设置,而利用A的空间.【山东大学 2001 九、1 (12分)】 （3）知线性表（a1, a2,a3,…,an）按顺序存储，且每个元素都是整数均不相同，设计把所有奇数移到所有偶数前边的算法。（要求时间最少，辅助空间最少）【东北大学 1997 三 (15分)】
(4) 编写函数将一整数序列中所有负数移到所有正数之前，要求时间复杂度为O（n）
【南京航空航天大学 2001 八（10分）】
(5) 已知一个由n（ 设n=1000）个整数组成的线性表，试设计该线性表的一种存储结构，并用标准pascal语言描述算法，实现将n个元素中所有大于等于19的整数放在所有小于19的整数之后。要求算法的时间复杂度为O(n),空间复杂度O(1)。【西安交通大学 1996 六（11分）】
9. 试编写在带头结点的单链表中删除（一个）最小值结点的（高效）算法。void delete（Linklist &L） 【北京理工大学 2001 九、3 （8分）】
10. 已知非空线性链表由list指出，链结点的构造为（data,link）.请写一算法，将链表中数据域值最小的那个链结点移到链表的最前面。要求：不得额外申请新的链结点。【北京航空航天大学 2001 四（10分）】
11. 已知p指向双向循环链表中的一个结点，其结点结构为data、llink、rlink三个域，写出算法change(p),交换p所指向的结点和它的前缀结点的顺序。【首都经贸大学 1997 二、2（15分）】
12. 线性表(a1,a2,a3,…,an)中元素递增有序且按顺序存储于计算机内。要求设计一算法完成：
（1） 用最少时间在表中查找数值为x的元素。 （2） 若找到将其与后继元素位置相交换。
（3） 若找不到将其插入表中并使表中元素仍递增有序。【东北大学 1996 三 ( 12分)】
13. 设单链表的表头指针为h，结点结构由data和next两个域构成，其中data域为字符型。写出算法dc(h,n),判断该链表的前n个字符是否中心对称。例如 xyx, xyyx都是中心对称。【首都经贸大学1998三、9（15分）】
14. 已知两个单链表A和B,其头指针分别为heada和headb，编写一个过程从单链表A中删除自第i个元素起的共len个元素，然后将单链表A插入到单链表B的第j个元素之前。
【中国矿业大学 2000 三（10分）】 类似本题的另外叙述有：
（1）h1、h2为两个链表的表头指针，结点结构为data和link两个域组成。写出算法inde(h1,h2,i,j,l),将链表h1从第i个结点起的l个结点删除，并插入到h2表的第j个结点之前。
【首都经贸大学 1998 三、10（20分）】
15. 设线性表存于A[1..size]的前num各分量中，且递增有序。请设计一个算法，将x插入到线性表的适当位置上，以保持线性表的有序性，并在设计前说明设计思想，最后说明所设计算法的时间复杂度。
【西安电子科技大学 1999计应用 1997 二 （10分）】 类似本题的另外叙述有：
(1) 试编制在线性表L={12,13,21,24,28,30,42,}中插入数据元素26的程序。（要求该程序用turbo Pascal语言编制并能在计算机上运行，结点类型为链式结构）【大连海事大学 1996 二、1 (16分)】
16. 假设一个单循环链表，其结点含有三个域pre、data、link。其中data为数据域；pre为指针域，它的值为空指针（NIL）；link为指针域，它指向后继结点。请设计算法，将此表改成双向循环链表。 【西安电子科技大学 1999软件 五（10分）】
17. 已知递增有序的单链表A,B分别存储了一个集合，请设计算法以求出两个集合A和B 的差集A-B（即仅由在A中出现而不在B中出现的元素所构成的集合），并以同样的形式存储，同时返回该集合的元素个数。 【西安电子科技大学2000计应用1997 二 （10分）】
18. 已知一个单链表中每个结点存放一个整数，并且结点数不少于2，请设计算法以判断该链表中第二项起的每个元素值是否等于其序号的平方减去其前驱的值，若满足则返回ture，否则返回false. 【西安电子科技大学2000软件1997 二（10分）】
19．两个整数序列A=a1,a2,a3,…,am和B=b1,b2,b3,…,bn已经存入两个单链表中，设计一个算法，判断序列B是否是序列A的子序列。【东北大学 1999 二 (10分)】
20．L1与L2分别为两单链表头结点地址指针，且两表中数据结点的数据域均为一个字母。设计把L1中与L2中数据相同的连续结点顺序完全倒置的算法。【东北大学 1997 四 (１５分)】 例：
类似本题的另外叙述有：
(1) 知L为链表的头结点地址，表中共有m(m>3)个结点，从表中第i个结点(1