33．向一个顺序栈插入一个元素时，首先使 后移一个位置，然后把待插入元素 到这个位置上。
34．从一个栈中删除元素时，首先取出 ，然后再前移一位 。 35．设单链表的结点结构为(data,next)，next为指针域，已知指针px指向单链表中data为x的结点，指针py指向data为y的新结点 , 若将结点y插入结点x之后，则需要执行以下语句:_______； ______;【华中理工大学 2000 一.4（2分）】
36．在一个长度为n的顺序表中第i个元素（1<=i<=n）之前插入一个元素时，需向后移动________个元素。【北京工商大学 2001 二.4（4分）】
37．在单链表中设置头结点的作用是________。【哈尔滨工业大学 2000 二.1（1分）】
38．对于一个具有n个结点的单链表，在已知的结点*p后插入一个新结点的时间复杂度为________,在给定值为x的结点后插入一个新结点的时间复杂度为________。【哈尔滨工业大学 2001 一.1（2分）】
39．在双向循环链表中,向p所指的结点之后插入指针f所指的结点，其操作是_______、_______、_______、________。【中国矿业大学 2000 一.1（3分）】 40．顺序存储结构是通过________表示元素之间的关系的;链式存储结构是通过________表示元素之间的关系的。【北京理工大学 2001 七.2 （2分）】 41．在单链表L中，指针p所指结点有后继结点的条件是：________ 【合肥工业大学 2001 三.3 （2分）】 三、判断题 1．（ ）线性表的顺序存储结构比链式存储结构更好。 2．( )线性表就是顺序存储的表。 3．（ ）线性表中的所有元素都有一个前驱元素和后继元素。 4．（ ）非空的双向循环链表中任何结点的前驱指针均不为空。 5．（ ）不论线性表采用顺序存储结构还是链式存储结构，删除值为X的结点的时间复杂度均为O(n)。
6．( )对链表进行插入和删除操作时不必移动链表中结点。 7．( )线性表只能用顺序存储结构实现。 8．( )如果某数据结构的每一个元素都最多只有一个直接前驱和一个直接后继，则该数据结构必为线性表。
9．( )采用链式结构存储线性表时，其地址可以是不连续的。 10．( )线性表中的每个元素都有一个前驱元素和后继元素。 11．( )采用顺序结构存储线性表时，其地址可以是不连续的。 12．（ ）如果某数据结构的每一个元素都最多只有一个直接前驱和一个直接后继，则该数据结构必为线性表。 13．（ ）线性表的唯一存储形式就是链表。 14．（ ）线性表不能采用链式存储。 15．（ ）在单链表中插入结点主要通过移动元素实现。 16．( )所谓静态链表就是一直不发生变化的链表。 17．( )集合与线性表的区别在于是否按关键字排序。 18．（ ）用头部插入结点的方法建立单链表时，插入元素的顺序和链表中的元素顺序相同。 19．（ ）线性表中的每个元素都有一个前驱元素和后继元素。
9
四、简答题
1．比较顺序表与单链表的优缺点。
2．说明以下三个概念的关系：头指针，头结点，首元素结点。
3．写出在双向链表中，在指针p所指结点前插入一个结点*S的语句序列。 4. 画出带头结点的单链表、单循环链表和双向循环链表的示意图，并归纳三者的不同之处。
5．写出下列中缀表达式的后缀表达式：
(1)A*B*C (2)(A+B)*C-D (3)A*B+C/(D-E) (4)(A+B)*D+E/(F+A*D)+C
6．线性表的顺序存储结构具有三个弱点：第一，在作插入或删除操作时，需要移动大量元素；第二，由于难以估计，必须预先分配较大的空间，往往使存储空间不能得到充分利用；第三，表的容量难以扩充。试问，线性表的链式存储结构是否一定能够克服上述三个弱点？请简述之。【北京师范大学2003二.4(6分)】 7. 如何通过改链的方法，把一个单向链表变成一个与原来链接方向相反的单向链表？【中国人民大学 2001 二.4 （2分）】
五、应用题
1．在下面的每个程序段中，假定线性表La的类型为List，元素类型ElemType为int，并假定每个程序段是连续执行的，试写出每个程序段执行后所得到的线性表La。
(1) InitList(La);
int a[]={48,26,57,34,62,79};
for(i=0; i<6; i++) InsertFront(La,a[i]); TraverseList(La);
(2) InitList(La);
for(i=0; i<6; i++) Insert(La,a[i]); TraverseList(La);
(3) ClearList(La);
for(i=0; i<6; i++) InsertRear(La,a[i]); Delete(La, a[5]); Sort(La);
Insert(La,a[5]/2); TraverseList(La);
2．写出下面函数被调用执行后，得到的以HL为表头指针的单链表中的数据元素序列。
void AA(LNode * & HL) {
InitList(HL);
InsertRear(HL,30); InsertRear(HL,50);
int a[5] = {15,8,9,26,12}; for (int i=0; i<5; i++ ) InsertFront(HL,a[i]);
10
}
}
六、程序填空题（或算法阅读题） 1．LinkList mynote(LinkList L)
{//L是不带头结点的单链表的头指针 if(L&&L->next){
q=L；L=L－>next；p=L；
S1： while(p－>next) p=p－>next； S2： p－>next=q；q－>next=NULL；
}
return L； }
请回答下列问题：
（1）说明语句S1的功能；
（2）说明语句组S2的功能；
（3）设链表表示的线性表为（a1,a2, …,an）,写出算法执行后的返回值所表示的线性表。
2．int AA(LNode *HL , ElemType x) {
int n=0;
LNode *p=HL;
while (p!=NULL) {
if (p->data= =x) n++; p=p->next;
}
return n; }
对于结点类型为LNode的单链表，以上算法的功能为： 3．void BB(List &L) {
int i=0;
while (i int j=i+1; while (j if(L.list[j] = =L.list[i]) { for (int k=j+1;k 11 else j++; } i++; } } 以上算法的功能为： 4. 已知一个单链表的表头指针为h，每个结点含元素值data和下一个结点的地址next。链表一共有5个结点，其元素值分别为100,200,300,400,500，经过下列语句后，输出什么结果？。（3分） for (p=h;p->data<300;p=p->next) { p->next = p->next->next; } printf(“%d”,p->data); 5. 指出下面程序段的功能是什么？ void demo1(SeqStack S) {int i，arr[64]，n=0; while(!StackEmpty(S)) arr[n++]=Pop(S); for(i=0;i 12
相关推荐：
loading