第二章线性表(答案)

《第二章线性表(答案)》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、第二章线性表一、选择题1•一个线性表第一个元素的存储地址是100,每个元索的长度为2,则第5个元素的地址是()(A)110(B)108(C)100(D)1202.向一个有127个元素的顺序表中插入一个新元素并保持原來顺序不变，平均要移动()个元素。(A)64(B)63(C)63.5(D)73.线性表釆用链式存储结构时，其地址()。(A)必须是连续的(B)部分地址必须是连续的(0_定是不连续的(D)连续与否均可以4.在一个单链表中，若p所指结点不是最丿舌结点，在p之后插入s所指结点,则执行()(A)s_〉next=p;p_〉next=s;(B)s->next二p->next;p->next二

2、s;(C)s->next=p->next;p=s;(D)p->next=s;s->next=p;5.在一个单链表中，若删除p所指结点的后续结点，则执行()(A)p->next=p->next->next;(B)p=p->next;p->next=p->next->next;(C)p-〉next=p->next;(I))p=p->next~>next;6.下列有关线性表的叙述中，正确的是()(A)线性表中的元素之间隔是线性关系(B)线性表中至少有一个元素(C)线性表中任何一个元素有且仅有一个直接前趋(D)线性表屮任何一个元素有且仅有一个直接后继7.线性表是具有n个()的有限序列(nHO)(A

3、)表元素(B)字符(C)数据元素(D)数据项二、判断题1・线性表的链接存储，表中元素的逻辑顺序与物理顺序一定相同。(F)2.如果没有提供指针类型的语言，就无法构造链式结构。(T)2.线性结构的特点是只有一个结点没有前驱，只有一个结点没有后继，其余的结点只有一个前驱和后继。(T)4•语句p=p->next完成了指针赋值并使p指针得到了p指针所指后继结点的数据域值。(F)5.要想删除p指针的后继结点，我们应该执行q=p->next；p->next二q->next；free(q)o(T)三、填空题1•已知P为单链表中的非首尾结点，在P结点后插入S结点的语句为：__s~>next=p~>next;

4、p->next=s;。2.顺序表中逻辑上相邻的元素物理位置(一定)相邻，单链表中逻辑上相邻的元素物理位置__不一定相邻。3.线性表1=(al,a2,...,an)釆用顺序存储，假定在不同的n+1个位置上插入的概率相同，则插入一个新元素平均需要移动的元素个数是n/2.4.在非空双向循环链表中，在结点q的前面插入结点p的过程如下：p->prior=q->prior;q->prior->next=p;p->next=q;q->prior=p;;5.己知L是无表头结点的单链表，是从下列提供的答案中选择合适的语句序列，分别实现：(1)表头插入s结点的语句序列是6)3)(2)表尾插入s结点的语句序列是

5、2)9)1)7)1.p->next二s;2.p=L;3.L=s;4.p->next=s->next;1.s-〉next=p->next;2.s~>next二L;7・s->next二nul1;2.while(p->next!二Q)?p二p-next;3.while(p->next!=nul1)p二p->next;四、算法设计题1.试编写一个求己知单链表的数据域的平均值的函数（数据域数据类型为整型）。1、intaver(LinkListL){p=L；while(p){p二p-〉next;i++;sum=sum+p->data;}aver=sum/i;returnaver;}2.己知带有头结点的

6、循环链表中头指针为head,试写出删除并释放数据域值为x的所有结点的函数。2、voiddel(LinkListL,intx)/*删除数据域为x的结点*/P二L;q=L->next;while(q!=L){if(q->data==x){p->ncxt=q->noxt;s二q；q二q->next;free(s);}else{p=q；q=q->next;}}}1.线性表中的元素值按递增有序排列，针对循环链表存储方式，编写函数删除线性表中值介于a与b(aWb)之间的元素。voiddel(LinkListL,elemtypea,elemtypeb){p=L;q=p->next;/*假设循环链表带有头

7、结点*/whi1e(q!=L&&q->datanext;}whi1e(q!=L&&q->datanext;free(r);}if(p!=q)p->next二q;1.已知两个链表A和B,其元素值非递减排列。写出将A和B合并成一个非递减有序的链表c的算法。voidMergeList_L(LinkListLa,LinkListLb,LinkList&Lc){//已知单链表La