第二章 线性表作业（共 50 分） 一、完成下面选择题（每空 2 分，共 14 分）。 1. 顺序存储结构中数据中数据元素之间逻辑关系是由（ C ）表示的，链接存储结构中 的数据元素之间的逻辑关系是由（ D ）表示的。 A．线性结构 B．非线性结构 C．存储位置 D．指针 2. 线性表是（ A ）。 A．一个有限序列，可以为空 B. 一个有限序列，不能为空 C. 一个无限序列，可以为空 D. 一个无限序列，不能为空 3. 已知一维数组 A 采用顺序存储结构，每个元素占用 4 个存储单元，第 9 个元素的地址为 144，则第一个元素的地址是（ D ）。 A. 108 D. 112 C. 176 B. 180 4. 在单链表中删除指针 p 所指结点的后继结点，则执行（ A ）。 A. p->next= p->next->next B. p->next= p->next C. p= p->next->next D. p= p->next; p->next= p->next->next 5. 若某链表最常用的操作是在最后一个结点之后插入一个结点删除最后一个结点，则采用 （ C ）存储方式最节省时间。 A. 单链表 C. 带头结点的双循环链表 B. 双链表 D. 单循环链表 6．二维数组 A[7][8]以列序为主序的存储， 计算数组元素 A[5][3] 的一维存储空间下标 k= （ C ）。 A. 38 D. 29 B. 43 C. 26 二、完成下列填空题（每空 3 分，共 9 分）。 1．在顺序表 L 中第 i 个位置上插入一个新的元素 e： Status ListInsert_Sq(SqList &L , int i , ET e){ if ( i<1 || i>L.length+1) if(L.length >= L.listsize){ return ERROR; p=(ET*)realloc(L.elem,(L.listsize+10)*sizeof(ET)); if (p==NULL) L.elem=p; exit(OVERFLOW); } for( j=L.length ; j>=i ; --j ) L.elem[j]=L.elem[j-1] ； L.elem[j]=e ; 

++L.length ； return OK; } 2. 删除双向链表中 p 所指向的节点算法： status delete(DuLinkList L, DuLinkList p) { if (p= =L) return ERROR; { else p->prior->next=p->next; p->next->prior=p->prior ； } free(p); return OK; } 三、编程题（共 27 分）。 1. （共 12 分）用顺序表表示集合，设计算法实现集合的求差集运算，要求不另外开辟空间。 顺序表的存储结构定义如下： #define Maxsize 100 typedef struct { ElemType data[MaxSize]; int length; // length 表示线性表的长度 // ElemType 表示不确定的数据类型 }SqList; 将如下函数，伪码补充完整（8 分），代码前先用文字描述自己的算法思想（4 分）。 文字描述算法：略（4 分） void Difference(SqList A, SqList B) {//参考代码如下如下（8 分） for (i=0;i

} 2. （共 15 分）已知带头结点的单循环链表 L，编写算法实现删除其中所有值为 e 的数据元 素结点。 （要求：类型定义、算法描述和算法时间复杂度分析） 类型定义：（3 分） typedef struct LNode{ ElemType data; struct LNode *next; } Lnode, *LinkList; 伪码进行算法描述：（10 分） void ListDelete_e (LinkList L, Element e) LinkList p,q; { (L->next == L) if return; p = L; while (p->next != L) { if (p->next->data != e) P = p->next; else { q = p->next;p->next = q->next; free(q);｝ } } 时间复杂度分析：（2 分） 时间复杂度为 O(n)。