《线性表(参考答案)》由会员分享，可在线阅读，更多相关《线性表(参考答案)（10页珍藏版）》请在金锄头文库上搜索。
1、真诚为您提供优质参考资料，若有不当之处，请指正。第二章 线性表一、填空题1、数据逻辑结构包括 线性结构 、 树型结构 、 图型结构 这三种类型，树形结构和图形结构合称为 非线性结构 。2、在线性结构中，第一个结点 没有 前驱结点，其余每个结点有且只有 个前驱结点，最后一个结点 没有 后续结点，其余每个结点有且只有 一 个后续结点。3、在顺序表中插入或删除一个元素，需要平均移动 一半 元素，具体移动的元素个数与 插入或删除的位置 有关。4、在顺序表中，逻辑上相邻的元素，其物理位置 一定 相邻。在单链表中，逻辑上相邻的元素，其物理位置 不一定 相邻。5、在带头结点的非空单链表中，头结点的存储位置由
2、 头指针 指示，首元素结点的存储位置由 头结点的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-lin
3、k_; delete(p); p=_(3)q-link_; /while / purge_linkst二、选择题1、在数据结构中，从逻辑上可以把数据结构分成 C 。 A、动态结构和静态结构 B、紧凑结构和非紧凑结构 C、线性结构和非线性结构 D、内部结构和外部结构 2、线性表的逻辑顺序与存储顺序总是一致的，这种说法 B 。 A、正确 B、不正确 3、线性表若采用链式存储结构时，要求内存中可用存储单元的XXX D 。 A、必须是连续的 B、部分XXX必须是连续的 C、一定是不连续的 D、连续或不连续都可以4、在以下的述叙中，正确的是 B 。 A、线性表的线性存储结构优于链表存储结构B、二维数组是
4、其数据元素为线性表的线性表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-
5、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、删除首元结
6、点的语句序列是（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
7、）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=
8、 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 E
9、lemType *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并返回O
10、K，否则返回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;
