第二章第二章 线性表线性表 一、填空题 1、数据逻辑结构包括 线性结构线性结构 、 树型结构树型结构 、 图型结构图型结构 这三种类 型，树形结构和图形结构合称为 非线性结构非线性结构 。 2、在线性结构中，第一个结点 没有没有 前驱结点，其余每个结点有且只有 个前驱 结点，最后一个结点 没有没有 后续结点，其余每个结点有且只有 一一 个后续结点。 3、在顺序表中插入或删除一个元素，需要平均移动 一半一半 元素，具体移动的 元素个数与 插入或删除的位置插入或删除的位置 有关。 4、在顺序表中，逻辑上相邻的元素，其物理位置 一定一定 相邻。在单链表中， 逻辑上相邻的元素，其物理位置 不一定不一定 相邻。 5、在带头结点的非空单链表中，头结点的存储位置由 头指针头指针 指示，首元素 结点的存储位置由 头结点的头结点的 nextnext 域域 指示，除首元素结点外，其它任一元素 结点的存储位置由 其直接前趋结点的其直接前趋结点的 nextnext 域域 指示。 6、阅读下列算法，并补充所缺内容。 void purge_linkst( ListNode * if(la=NULL) return; q=la; p = la-link; while (p) if (p p = p-link; else q-link= _(2)p-linkp-link_; delete(p); p=_(3)q-linkq-link_; /while / purge_linkst 二、选择题 1、在数据结构中，从逻辑上可以把数据结构分成 C C 。 A、动态结构和静态结构 B、紧凑结构和非紧凑结构 C、线性结构和非线性结构 D、内部结构和外部结构 2、线性表的逻辑顺序与存储顺序总是一致的，这种说法 B B 。 A、正确 B、不正确 3、线性表若采用链式存储结构时，要求内存中可用存储单元的地址 D D 。 A、必须是连续的 B、部分地址必须是连续的 C、一定是不连续的 D、连续或不连续都可以 4、在以下的述叙中，正确的是 B B 。 A、线性表的线性存储结构优于链表存储结构 B、二维数组是其数据元素为线性表的线性表 C、栈的操作是先进先出 D、队列的操作方式是先进后出 三、综合题 1、已知 L 是无表头结点的单链表，且 P 结点既不是首元结点，也不是尾元结点，试从下列 提供的答案中选择合适的语句序列。 A、在 P 结点后插入 S 结点的语句序列是（4） 、 （1） ）； B、在 P 结点前插入 S 结点的语句序列是（7） 、 （11） 、 （8） 、 （4） 、 （1） ）； C、在表首插入 S 结点的语句序列是（5） 、 （12） ）；D、在表尾插入 S 结点的语句序列是（9） 、 （1） 、 （6）或（11） 、 （9） 、 （1） 、 （6） ）（其中 6 的位置可变）； （1）P-next=S; （2）P-next=S-next-next; （3）P-next=S-next; （4）S-next=P-next; （5）S-next=L; （6）S-next=NULL; （7）Q=P; （8）while(P-next!=Q) P=P-next; （9）while(P-next!=NULL) P=P-next; （10）P=Q; （11）P=L; （12）L=S; （13）L=P; 2、已知 L 是带表头结点的非空单链表，且 P 结点既不是首元结点，也不是尾元结点，试从 下列提供的答案中选择合适的语句序列。 A、删除 P 结点的直接后继结点的语句序列是（1111、3 3、1414）； B、删除 P 结点的直接前驱结点的语句序列是（1010、1212、8 8、1111、3 3、1414）； C、删除 P 结点的语句序列是（1010、1212、7 7、3 3、1414）； D、删除首元结点的语句序列是（1212、1111、3 3、1414）； E、删除尾元结点的语句序列是（9 9、1111、3 3、1414）或（1212、9 9、1111、3 3、1414）； （1）P=P-next; （2）P-next=P; （3）P-next= P-next -next; （4）P = P-next -next; （5）while(P-next!=NULL) P=P-next; （6）while(Q-next!=NULL) P=Q;Q=Q-next; （7）while(P-next!=Q) P=P-next; （8）while(P-next-next!=Q) P=P-next; （9）while(P-next-next!=NULL) P=P-next; （10）Q=P; （11）Q=P-next; （12）P=L; （13）L=L-next; （14）free(Q); 3、 线性表定位操作 ListFind(L, x)的功能是：在线性表 L 中查找是否存在数据元素 x， 如果存在，返回线性表中和 x 值相等的第 1 个数据元素的序号（序号编号从 0 开始）；如 果不存在，返回-1。要求编写顺序表的定位操作算法。 intint ListFind(SqlistListFind(Sqlist L,L, ElemTypeElemType x)x) ElemTypeElemType *p;*p;intint i=0;i=0;p p = = L.elem;L.elem;while(iwhile(i next;q=p-next; while(qwhile(q !=!= NULL)NULL) /*/*每次让指针每次让指针 p p 指向数据元素值为指向数据元素值为 x x 的前一结点的前一结点,q,q 指向指向 x*/x*/ if(q-data=if(q-data= x)x) flag=1flag=1 p-nextp-next = = q-next;q-next; /*/*把数据元素把数据元素 aiai 结点从单链表中删除指结点从单链表中删除指*/*/ free(q);free(q); /*/*释放指针释放指针 q q 所指结点的内存空间所指结点的内存空间*/*/ q=p-next;q=p-next;/*/*只改只改 q q 指针指针,p,p 指针暂时不变指针暂时不变*/*/ elseelse p p = = q;q;/*p,q/*p,q 指针同时后移指针同时后移*/*/ q q = = q-nextq-next if(flag=1)if(flag=1) ReturnReturn 1;1; /*/*有有 x*/x*/ elseelse returnreturn 0;/*0;/*无无 x*/x*/ 5、 编写算法实现顺序表的逆置，即要求把顺序表 A 中的数据元素序列（a0,a1,an-1） 逆置为（an-1,a1,a0），并把逆置后的数据元素存储到顺序表 B 中。 # # definedefine LIST_INIT_SIZELIST_INIT_SIZE 100100 typedeftypedef structstruct ElemTypeElemType *elem;*elem; / 存储空间基址存储空间基址 intint length;length; / 当前长度当前长度 intint listsize;listsize; / 当前分配的存储容量当前分配的存储容量 / ( (以以 sizeof(ElemType)sizeof(ElemType)为单位为单位) ) SqList;SqList; voidvoid Reverse(SqlistReverse(Sqlist t; For(i=0,j=LA.length-1;inext;/p 指向第一个结点指向第一个结点while(p!=L) /没到表头没到表头i+;p=p-next;return i; Status GetElem(DuLinkList L,int i,ElemType *e) /当第当第 i 个元素存在时，其值赋给个元素存在时，其值赋给 e 并返回并返回 OK，否则返回，否则返回 ERRORint j=1;DuLinkList p=L-next;/p 指向第一个结点指向第一个结点while(p!=Lj+;if(p=L|ji) /第第 i 个元素不存在个元素不存在return ERROR;*e=p-data; /取第取第 i 个元素个元素return OK; 7、设计单循环链表，要求：单循环链表抽象数据类型包括初始化操作、求数据元素个数操 作、插入操作、删除操作、取数据元素操作和判非空操作。typedeftypedef structstruct LNodeLNode ElemTypeElemType data;data; / 数据域数据域structstruct LNodeLNode *next;*next; / 指针域指针域 LNode,LNode, *LinkList;*LinkList; StatusStatus InitList(LinkListInitList(LinkList *L)*L) LinkListLinkList L;/L;/定义一个链表，定义一个链表， L=(LinkList)malloc(sizeof(listnode);L=(LinkList)malloc(sizeof(listnode); /给这个链表分配内存控件给这个链表分配内存控件 If(!L)If(!L) returnreturn ERROR;ERROR; L-next=L;/L-next=L;/初始化只有链表头，头链表指向自己初始化只有链表头，头链表指向自己 ReturnReturn OK;/OK;/返回这个头链表返回这个头链表 int ListLength(LinkListLinkList L) /初始条件：带头结点初始条件：带头结点 L 存在。操作结果：返回存在。操作结果：返回 L 中数据元素的个数中数据元素的个数int i=0;LinkListLinkList p=L-next;/p 指向第一个结点指向第一个结点while(p!=L) /没到表头没到表头i+;p=p-next;return i; StatusStatus ListInsert_L(LinkListListInsert_L(LinkList L; j j = = 0;0; whilewhile (p!=L(p!=L p-next; +j;+j; / 寻找第寻找第 i-1i-1 个结点个结点 ifif (p=L(p=L | j j i-1)i-1)re