线性表(参考答案).doc

第二章 线性表一、填空题1、数据逻辑结构包括 线性结构 、 树型结构 、 图型结构 这三种类型，树形结构和图形结构合称为 非线性结构 。2、在线性结构中，第一个结点 没有 前驱结点，其余每个结点有且只有 个前驱结点，最后一个结点 没有 后续结点，其余每个结点有且只有 一 个后续结点。3、在顺序表中插入或删除一个元素，需要平均移动 一半 元素，具体移动的元素个数与 插入或删除的位置 有关。4、在顺序表中，逻辑上相邻的元素，其物理位置 一定 相邻。在单链表中，逻辑上相邻的元素，其物理位置 不一定 相邻。5、在带头结点的非空单链表中，头结点的存储位置由 头指针 指示，首元素结点的存储位置由 头结点的next域 指示，除首元素结点外，其它任一元素结点的存储位置由 其直接前趋结点的next域 指示。6、阅读下列算法，并补充所缺内容。 void purge_linkst( ListNode *& la ) / 从头指针为 la 的有序链表中删除所有值相同的多余元素，并释放被删结点空间 ListNode *p,*q; if(la=NULL) return; q=la; p = la-link; while (p) if (p & _(1)p-data!=q-data_) q=p; p = p-link; else q-link= _(2)p-link_; delete(p); p=_(3)q-link_; /while / purge_linkst二、选择题1、在数据结构中，从逻辑上可以把数据结构分成 C 。 A、动态结构和静态结构 B、紧凑结构和非紧凑结构 C、线性结构和非线性结构 D、内部结构和外部结构 2、线性表的逻辑顺序与存储顺序总是一致的，这种说法 B 。 A、正确 B、不正确 3、线性表若采用链式存储结构时，要求内存中可用存储单元的地址 D 。 A、必须是连续的 B、部分地址必须是连续的 C、一定是不连续的 D、连续或不连续都可以4、在以下的述叙中，正确的是 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结点的直接后继结点的语句序列是（11、3、14）；B、删除P结点的直接前驱结点的语句序列是（10、12、8、11、3、14）；C、删除P结点的语句序列是（10、12、7、3、14）；D、删除首元结点的语句序列是（12、11、3、14）；E、删除尾元结点的语句序列是（9、11、3、14）或（12、9、11、3、14）；（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。要求编写顺序表的定位操作算法。int ListFind(Sqlist L, ElemType x) ElemType *p; int i=0; p = L.elem; while(i next;while(q != NULL) /*每次让指针p指向数据元素值为x的前一结点,q指向x*/if(q-data= x)flag=1p-next = q-next; /*把数据元素ai结点从单链表中删除指*/free(q); /*释放指针q所指结点的内存空间*/q=p-next;/*只改q指针,p指针暂时不变*/elsep = q;/*p,q指针同时后移*/q = q-nextif(flag=1)Return 1; /*有x*/elsereturn 0;/*无x*/5、 编写算法实现顺序表的逆置，即要求把顺序表A中的数据元素序列（a0,a1,an-1）逆置为（an-1,a1,a0），并把逆置后的数据元素存储到顺序表B中。# define LIST_INIT_SIZE 100typedef struct ElemType *elem; / 存储空间基址int length; / 当前长度int listsize; / 当前分配的存储容量 / (以sizeof(ElemType)为单位) SqList; void Reverse(Sqlist &LA，Sqlist &LB)/顺序表的就地逆置ElemType 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，否则返回ERROR int j=1; DuLinkList p=L-next;/p指向第一个结点 while(p!=L&jnext; j+; if(p=L|ji) /第i个元素不存在 return ERROR; *e=p-data; /取第i个元素 return OK;7、设计单循环链表，要求：单循环链表抽象数据类型包括初始化操作、求数据元素个数操作、插入操作、删除操作、取数据元素操作和判非空操作。typedef struct LNode ElemType data; / 数据域 struct LNode *next; / 指针域 LNode, *LinkList; Status InitList(LinkList *L) LinkList L;/定义一个链表，L=(LinkList)malloc(sizeof(listnode); /给这个链表分配内存控件If(!L) return ERROR;L-next=L;/初始化只有链表头，头链表指向自己Return OK;/返回这个头链表 int ListLength(LinkList L)/初始条件：带头结点L存在。操作结果：返回L中数据元素的个数 int i=0; LinkList p=L-next;/p指向第一个结点 while(p!=L) /没到表头 i+; p=p-next; return i;Status ListInsert_L(LinkList &L, int i, ElemType e) / L 为带头结点的单链表的头指针，本算法 / 在链表中第i 个结点之前插入新的元素 e p = L; j = 0;while (p!=L & j next; +j; / 寻找第 i-1 个结点if (p=L | j i-1) return ERROR; / i 大于表长或者小于1s=(LNode *)malloc(sizeof(LNode);s-data = e;s-next = p-next;p-next = s; / LinstInsert_LStatus ListDelete_L(LinkList &L, int i, ElemType &e) / 删除以 L 为头指针(带头结点)的单链表中第 i 个结点p = L; j = 0;while (p-next!=L & j next; +j; / 寻找第 i 个结点，并令 p 指向其前趋if (p-next=L | j i-1) return ERROR; / 删除位置不合理q = p-next; p-next = q-next; / 删除并释放结点e = q-data; free(q);return OK; / ListDelete_LStatus GetElem_L(LinkList L, int i, ElemType &e) / L是带头结点的链表的头指针，以 e 返回第 i 个元素p = L-next; j = 1; / p指向第一个结点，j为计数器while (p!=L & jnext; +j; / 顺指针向后查找，直到 p 指向第 i 个元素 / 或 p 为空if ( p=L | ji ) return ERROR; / 第 i 个元素不存在e = p-data; / 取得第 i 个元素return OK; / GetElem_LBoolean ListEmpty(LinkList L )/初始条件：线性表L已存在。/操作结果：若 L 为空表，则返回 TRUE，否则返回 FALSE。If(L-next=L) return FALSE;Else return TRUE;8、 设计一个有序顺序表，要求：有序顺序表的操作集合有如下操作：初始化、求数据元素个数、插入、删除和取数据元素。#define MaxSize 100typedef structElemType elemMaxSize;int length;SqList;void InitList(SqList *&L) L=(SqList *)malloc(sizeof(SqList); L-length=0;int ListLength(SqList *L) return(L-length);int ListInsert(SqList *&L, ElemType e)/设顺序表升序排列int j;if(L-length=Maxsize) return ERROR;for(j=L-length-1;j=0;j-)/从后往前比较e和每个元素的值if(eelemj+1=L-elemj;/要插入元素更小时，当前元素后移L-elemj+1=e;L-length+;return OK;int ListDelete(SqList *&L, ElemType &e)int j;for(j=0;jlength-1;j+)if(e=L-elemj) break;/找efor(i=j;ilength-1,i+) L-elemi=L-elemi+1;/找到时，找到位置以后的每个元素前移一个位置。If(jlength) L-length-;return 1;/找到了eElsereturn 0;int GetElem(SqList *L,int i,ElemType &e)if(iL-length)return 0;e=L-elemi-1;return 1;*思考以下题目，不要求做在本子上*1、描述以下基本概念：线性表、顺序存储结构、链式存储结构、 给出线性表的抽象数据类型定义。2、说明在顺序表中实现插入操作和删除操作时为什么必须移动数据元素，以及插入操作和删除操作各自移动数据元素的方向。3、对比顺序表和单链表，说明顺序表和单链表的主要优点和主要缺点。4、 编写一个逐个输出顺序表中所有数据元素的算法。5、 编写一个逐个输出单链表中所有数据元素的算法。6、 编写算法实现顺序表的就地逆置，即要求利用原顺序表的存储单元，把数据元素序列（a0,a1,an-1）逆置为（an-1,a1,a0）。2约瑟夫环问题。约瑟夫问题的一种描述是：编号为1，2，n的n个人按顺时针方向围坐一圈，每人持有一个密码（正整数）。一开始任选一个整数作为报数上限值m,从第一个人开始顺时针自1开始顺序报数，报到m时停止报数。报m的人出列，将他的密码作为新的m值，从他在顺时针方向上的下一个人开始重新从1报数，如此下去，直至所有的人全部出列为止。试设计一个程序，求出出列顺序。利用单向循环链表作为存储结构模拟此过程，按照出列顺序打印出各人的编号。约瑟夫环问题：约瑟夫问题的一种描述为：编号1,2,n的n个人按顺时针方向围坐一圈，每个人持有一个密码（正整数）。一开始任选一个报数上限值m,从第一个人开始顺时针自1开始顺序报数，报到m时停止报数。报m的人出列，将他的密码作为新的m值，从他在顺时针方向上的下一个人开始重新从1报数，如此下去，直至所有的人全部出列为止。试设计一个程序，求出出列顺序。利用单向循环链表作为存储结构模拟此过程，按照出列顺序打印出各人的编号。例如m的初值为20；n=7，7个人的密码依次是：3,1,7,2,4,8,4,出列顺序为6,1,4,7,2,3,5。【解答】算法如下： typedef struct Nodeint password;int num;struct Node *next; Node,*Linklist; void Josephus() Linklist L; Node *p,*r,*q; int m,n,C,j; L=(Node*)malloc(sizeof(Node); /*初始化单向循环链表*/ if(L=NULL) printf(n链表申请不到空间!);return; L-next=NULL; r=L; printf(请输入数据n的值(n0):); scanf(%d,&n); for(j=1;jpassword=C; p-num=j; r-next=p; r=p; r-next=L-next;printf(请输入第一个报数上限值m(m0):); scanf(%d,&m); printf(*n); printf(出列的顺序为:n); q=L; p=L-next; while(n!=1) /*计算出列的顺序*/ j=1; while(jnext; j+; printf(%d-,p-num); m=p-password; /*获得新密码*/ n-; q-next=p-next; /*p出列*/ r=p; p=p-next; free(r); printf(%dn,p-num); 2.7试分别以不同的存储结构实现单线表的就地逆置算法，即在原表的存储空间将线性表（a1,a2,an）逆置为(an,an-1,a1)。【解答】（1）用一维数组作为存储结构 void invert(SeqList *L, int *num) int j;