21．线性表的顺序存储结构是一种 的存储结构，线性表的链式存储结构是一种 的存储结构。 A．随机存取 B．顺序存取 C．索引存取 D．散列存取 22．下述哪一条是顺序存储结构的优点？（ ）
A．存储密度大 B．插入运算方便 C．删除运算方便 D．可方便地用于各种逻辑结构的存储表示 23．若某线性表最常用的操作是存取任一指定序号的元素和在最后进行插入和删除运算，则利用（ ）存储方式最节省时间。
A．顺序表 B．双链表 C．带头结点的双循环链表 D．单循环链表
24．设一个链表最常用的操作是在末尾插入结点和删除尾结点，则选用( )最节省时间。 A. 单链表 B.单循环链表 C. 带尾指针的单循环链表 D.带头结点的双循环链表 25．线性表（a1,a2,?,an）以链接方式存储时，访问第i位置元素的时间复杂性为（ ） A．O（i） B．O（1） C．O（n） D．O（i-1） 26．循环链表h的尾结点p的特点是（ ）
A．p→next=h B．p→next=h->next C．p=h D．p=h->next 27．完成在双循环链表结点p之后插入s的操作是（ ）
A． p->next=s ; s->priou=p; p->next->priou:=s ; s->next=p->next; B． p->next->priou=s; p->next=s; s->priou=p; s->next:=p->next; C．s->priou=p; s->next:=p->next; p->next=s; p->next->priou=s ; D．s->priou=p; s->next:=p->next; p->next->priou=s ; p->next=s;
28．双向链表中有两个指针域，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都不对。
二、填空题
1．向一个长度为n的向量的第i个元素(1≤i≤n)之前插入一个元素时，需向后移动 ________个元素。 2．线性表（a1,a2，??，an）以链接方式存储时，在第i个位置删除一个元素的时间复杂度是____ __。 3. 当线性表的元素总数基本稳定，且很少进行插入和删除操作，但要求以最快的速度存取线性表中的元素时，应采用_______存储结构。 4.链表适用于 查找。
6
5.链表对于数据元素的插入和删除不需移动结点，只需改变相关结点的________域的值。 6.在一个链式栈中，若栈顶指针等于NULL则为________。
7.在链表中进行插入和 操作的效率比在顺序存储结构中进行相同操作的效率高。 8.链表对于数据元素的插入和删除不需移动结点，只需改变相关结点的________域的值。
9．在一个带头结点的单循环链表中，p指向尾结点的直接前驱，则指向头结点的指针head可用p表示为head=_____。
10. 对于双向链表,在两个结点之间插入一个新结点需修改的指针共 ______个，单链表为_______个。 11．线性表L=（a1,a2,?,an）用数组表示，假定删除表中任一元素的概率相同，则删除一个元素平均需要移动元素的个数是________。
12．在单链表中设置头结点的作用是________。
13．对于一个具有n个结点的单链表，在已知的结点*p后插入一个新结点的时间复杂度为________, 在给定值为x的结点后插入一个新结点的时间复杂度为________。
14．根据线性表的链式存储结构中每一个结点包含的指针个数，将线性链表分成________和_______；而又根据指针的连接方式，链表又可分成________和________。
15. 在双向链表结构中，若要求在p 指针所指的结点之前插入指针为s 所指的结点，则需执行下列语句： s->next=p； s->prior= ________；p->prior=s；________=s；
16.顺序存储结构是通过________表示元素之间的关系的;链式存储结构是通过________表示元素之间的关系的。
17. 对于双向链表,在两个结点之间插入一个新结点需修改的指针共 ______个，单链表为_______个。 18. 循环单链表的最大优点是：________。
19. 带头结点的双循环链表L中只有一个元素结点的条件是：________ 20. 在单链表L中，指针p所指结点有后继结点的条件是： 21. 带头结点的双循环链表L为空表的条件是：________。
三、判断题
1.顺序存储方式只能用于存储线性结构。
2.顺序表和一维数组一样，都可以按下标随机（或直接）访问。 3.顺序表用一维数组作为存储结构，因此顺序表是一维数组。 4.通常使用两个类来协同表示单链表，即链表的结点类和链表类。
5.在单链表中，任何两个元素的存储位置之间都有固定的联系，因为可以从头结点进行查找任何一个元素。 6.线性表采用顺序存储表示时，必须占用一片连续的存储单元。
7
7.链式存储在插入和删除时需要保持物理存储空间的顺序分配，不需要保持数据元素之间的逻辑顺序。 8．线性表的逻辑顺序与物理顺序总是一致的。 9．线性表的顺序存储表示优于链式存储表示。
10．线性表若采用链式存储表示时所有结点之间的存储单元地址可连续可不连续。
四、应用题
1．线性表的顺序存储表示和链式存储表示的特点比较。
2.这是一个统计单链表中结点的值等于给定值x的结点数的算法，其中while循环有错，请重新编写出正确的while循环。
int count ( ListNode * Ha, ElemType x ) { // Ha为不带头结点的单链表的头指针 int n = 0;
while ( Ha->link != NULL )
{ Ha = Ha->link; if ( Ha->data == x ) n++; return n; }
}
五、算法设计题
1．设带表头结点的双向链表的定义为 typedef int ElemType；
typedef struct dnode { file://双向链表结点定义 ElemType data； file://数据
struct dnode * lLink， * rLink； file://结点前驱与后继指针 DblNode；
typedef DblNode * DblList； file://双向链表
试设计一个算法，改造一个带表头结点的双向链表，所有结点的原有次序保持在各个结点的右链域rLink中，并利用左链域lLink把所有结点按照其值从小到大的顺序连接起来。
2．假设有两个按元素值递增次序排列的线性表，均以单链表形式存储。请编写算法将这两个单链表归并为一个按元素值递减次序排列的单链表，并要求利用原来两个单链表的结点存放归并后的单链表。 3. 已知L1、L2分别为两循环单链表的头结点指针，m,n分别为L1、L2表中数据结点个数。要求设计一算法，用最快速度将两表合并成一个带头结点的循环单链表。
8
4. 顺序结构线性表LA与LB的结点关键字为整数。LA与LB的元素按非递减有序，线性表空间足够大。试用类C语言给出一种高效算法，将LB中元素合到LA中，使新的LA的元素仍保持非递减有序。高效指最大限度的避免移动元素。
5. 设 Listhead为一单链表的头指针，单链表的每个结点由一个整数域DATA和指针域NEXT组成，整数在单链表中是无序的。编一类C过程，将 Listhead链中结点分成一个奇数链和一个偶数链，分别由P,Q指向，每个链中的数据按由小到大排列。程序中不得使用 NEW过程申请空间。 6. 试编写在带头结点的单链表中删除（一个）最小值结点的（高效）算法。
7. 已知非空线性链表由list指出，链结点的构造为（data,link）.请写一算法，将链表中数据域值最小的那个链结点移到链表的最前面。要求：不得额外申请新的链结点。
8. 已知p指向双向循环链表中的一个结点，其结点结构为data、llink、rlink三个域，写出算法change(p),交换p所指向的结点和它的前缀结点的顺序。
9. 线性表(a1,a2,a3,?,an)中元素递增有序且按顺序存储于计算机内。要求设计一算法完成： （1） 用最少时间在表中查找数值为x的元素。 （2） 若找到将其与后继元素位置相交换。
（3） 若找不到将其插入表中并使表中元素仍递增有序。
10 已知两个单链表A和B,其头指针分别为heada和headb，编写一个过程从单链表A中删除自第i个元素起的共len个元素，然后将单链表A插入到单链表B的第j个元素之前。
11．在一个递增有序的线性表中，有数值相同的元素存在。若存储方式为单链表，设计算法去掉数值相同的元素，使表中不再有重复的元素。例如：（7，10，10，21，30，42，42，42，51，70）将变作（7，10，21，30，42，51，70），分析算法的时间复杂度。
12. 函数reverse()实现将已知不带头结点的单链表的链接顺序颠倒的功能，即第一表元变为最后表元，第二表元变为倒数第二表元，??，最后表元变为第一表元。函数中h为链表的头指针，q2为第一个尚未颠倒的链表表元，q1为已颠倒链表的第一个链表表元。
Typedef struct node { int data; struct node *next; }node; //链表的形式说明 void reverse(node h) { node *q1, *q2;
9
; q1=NULL;
while (q2!=NULL) { ; ; h=q2;
;
}
=q1;
}
13. 设有一个表头为first的单链表。试设计一个算法，通过遍历一趟链表，将链表中所有结点按逆序链接。
14．阅读下面的算法
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）,写出算法执行后的返回值所表示的线性表。 15.一个顺序存储的线性表内存储整数，编写算法，将负整数移到线性表的前边，非负整数移到线性表的
10
百度搜索“77cn”或“免费范文网”即可找到本站免费阅读全部范文。收藏本站方便下次阅读，免费范文网，提供经典小说综合文库数据结构习题(2)在线全文阅读。
相关推荐：