for(i=l; i sum++; printf(\； } return (sum); } 4． 设计求解下列问题的类C语言算法，并分析其最坏情况时间复杂度。 （1） 在数组A[1..n]中查找值为K的元素,若找到则输出其位置i(1<=i<=n),否则输 出0作为标志。 （2） 找出数组A[1..n]中元素的最大值和次最大值（本小题以数组元素的比较为标 准操作）。 4 习题二 线性表 一、单项选择题 1．顺序表是线性表的（ ） A．链式存储结构 B．顺序存储结构 C．索引存储结构 D．散列存储结构 2.对于顺序表，以下说法错误的是（ ） A．顺序表是用一维数组实现的线性表，数组的下标可以看成是元素的绝对地址 B．顺序表的所有存储结点按相应数据元素间的逻辑关系决定的次序依次排列 C．顺序表的特点是:逻辑结构中相邻的结点在存储结构中仍相邻 D．顺序表的特点是:逻辑上相邻的元素，存储在物理位置也相邻的单元中 3．线性表是具有n个（ ）的有限序列（n>0）。 A．表元素 B．字符 C．数据元素 D．数据项 E．信息项 4.以下说法错误的是 ( ) A．对于线性表来说，定位运算LocateElem在顺序表和单链表上的时间复杂度均为O（n） B．读表元运算在顺序表上只需常数时间O（1）便可实现，因此顺序表是一种随机存取结构 C．在链表上实现读表元运算的平均时间复杂度为O（1） D．插入、删除操作在链表上的实现可在O（1）时间内完成 E．插入、删除操作在顺序表上的实现，平均时间复杂度为O（n） 5.若某线性表中最常用的操作是取第i个元素和找第i个元素的前趋元素，则采用（ ）存储方式最节省时间。 A．顺序表 B．单链表 C．双链表 D．单循环链表 6．设一个链表最常用的操作是在末尾插入结点和删除尾结点，则选用( )最节省时间。 A. 单链表 B.单循环链表 C. 带尾指针的单循环链表 D.带头结点的双循环链表 7. 静态链表中指针表示的是（ ）. A． 内存地址 B．数组下标 C．下一元素地址 D．左、右孩子地址 8. 链表不具有的特点是（ ） A．插入、删除不需要移动元素 B．可随机访问任一元素 C．不必事先估计存储空间 D．所需空间与线性长度成正比 9．在循环链表中，将头指针改设为尾指针（rear）后，其头结点和尾结点的存储位置分别是（ ） A．rear和rear->next->next B．rear->next 和rear C．rear->next->next和rear D．rear和rear->next 10. 对于顺序存储的线性表，访问结点和增加、删除结点的时间复杂度为（ ）。 A．O(n) O(n) B. O(n) O(1) C. O(1) O(n) D. O(1) O(1) 11．线性表（ a1,a2,…,an）以链接方式存储时，访问第i位置元素的时间复杂性为（ ） A．O（i） B．O（1） C．O（n） D．O（i-1） 12．在单链表指针为p的结点之后插入指针为s的结点，正确的操作是：（ ）。 5 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; 13．对于一个头指针为head的带头结点的单链表，判定该表为空表的条件是（ ） A． head==NULL B．head→next==NULL C．head→next==head D．head!=NULL 二、判断题（在各题后填写“√”或“×”） 1. 链表中的头结点仅起到标识的作用。( ) 2．线性表采用链表存储时，结点和结点内部的存储空间可以是不连续的。( ) 3．顺序存储方式插入和删除时效率太低，因此它不如链式存储方式好。( ) 4. 对任何数据结构链式存储结构一定优于顺序存储结构。( ) 5. 所谓静态链表就是一直不发生变化的链表。( ) 6. 线性表的特点是每个元素都有一个前驱和一个后继。( ) 7. 循环链表不是线性表. ( ) 8. 线性表只能用顺序存储结构实现。( ) 9. 线性表就是顺序存储的表。( ) 10.链表是采用链式存储结构的线性表,进行插入、删除操作时，在链表中比在顺序存储结构中效率高。 ( ) 三、填空题 1．在顺序表中，逻辑上相邻的元素，其物理位置 相邻。在单链表中，逻辑上相邻的元素，其物理位置 相邻。 2．在带头结点的非空单链表中，头结点的存储位置由 指示，首元素结点的存储位置由 指示，除首元素结点外，其它任一元素结点的存储位置由 指示。 3．在单链表中若在每个结点中增加一个指针域,所含指针指向前驱结点，这样构成的链表中有两个方向不同的链，称为______。 4.对于顺序表的插入算法insert_sqlist来说，若以结点移动为标准操作，则插入算法的在最坏情况下的移动次数为________，时间复杂度是________。在平均情况下的移动次数为________，时间复杂度是________。 5.线性表的常见链式存储结构有________、________和________。 6.单链表表示法的基本思想是用________表示结点间的逻辑关系。 7．线性表L=（a1,a2,…,an）用数组表示，假定删除表中任一元素的概率相同，则删除一个元素平均需要移动元素的个数是________。 8．设单链表的结点结构为(data,next)，next为指针域，已知指针px指向单链表中data为x的结点，指针py指向data为y的新结点 , 若将结点y插入结点x之后，则需要执行以下语句:_______； ______; 6 9. 对于双向链表,在两个结点之间插入一个新结点需修改的指针共 ______个，单链表为_______个。 10.以下为顺序表的定位运算，分析算法，请在________处填上正确的语句。 int locate_sqlist(sqlist L,datatype X) /*在顺序表L中查找第一值等于X的结点。若找到回传该结点序号；否则回传0*/ {________; while((i≤L.last)&&(L.data[i-1]!=X))i++; if(________)return(i); else return(0); } 11．对单链表中元素按插入方法排序的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->data<=p->data) {r=q; q=q->next;} u=p->next; (4)__ ____; (5)__ ____; p=u; } } 12．下面是一个求两个集合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运算执行完毕，再删除并释放表示结果集合的链表的表头结点。 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) 7 {NODE *C,*last; C=last=(NODE*) malloc (sizeof(NODE)); while (1)_ __ if (A->element 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);*/ 四、应用题 1. 试述头结点,首元结点,头指针这三个概念的区别. 参考答案： 在线性表的链式存储结构中，头指针指链表的指针，若链表有头结点则是链表的头结点的指针，头指针具有标识作用，故常用头指针冠以链表的名字。头结点是为了操作的统一、方便而设立的，放在第一元素结点之前，其数据域一般无意义（当然有些情况下也可存放链表的长度、用做监视哨等等），有头结点后，对在第一元素结点前插入结点和删除第一结点，其操作与对其它结点的操作统一了。而且无论链表是否为空，头指针均不为空。首元结点也就是第一元素结点，它是头结点后边的第一个结点。 2. 在单链表和双向链表中，能否从当前结点出发访问到任何一个结点? 参考答案：在单链表中不能从当前结点（若当前结点不是第一结点）出发访问到任何一个结点，链表只能从头指针开始，访问到链表中每个结点。在双链表中求前驱和后继都容易，从当前结点向前到第一结点，向后到最后结点，可以访问到任何一个结点。 3. 一线性表存储在带头结点的双向循环链表中，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) __ ____； } } 参考答案：1）本算法功能是将双向循环链表结点的数据域按值自小到大排序，成为非递减（可能包括数据域值相等的结点）有序双向循环链表。 2）(1)r->prior=q->prior;∥将q结点摘下，以便插入到适当位置。 (2)p->next->prior=q;∥（2）（3）将q结点插入 (3)p->next=q; (4)r=r->next;或r=q->next;∥后移指针，再将新结点插入到适当位置。 8