最新数据结构线性表答案Word文件下载.docx

1、next=S;（2） P-next=P-next-（3） P-next=S-（4） S-（5） S-next=L;（6） S-（7） Q=P;（8） while（P-next!=Q） P=P-（9） while（P-=NULL） P=P-（10） P=Q;（11） P=L;（12） L=S;（13） L=P;a. （4） （1） b. （7） （11） （8） （4） （1） c. （5） （12） d. （9） （1） （6）2.7 已知L是带表头结点的非空单链表，且P结点既不是首元结点，也不是尾元结点，试从下列提供的答案中选择合适的语句序列。 a. 删除P结点的直接后继结点的语句序列是_。

2、 b. 删除P结点的直接前驱结点的语句序列是_。 c. 删除P结点的语句序列是_。 d. 删除首元结点的语句序列是_。 e. 删除尾元结点的语句序列是_。（1） P=P-next=P;（4） P=P-（5） while（P!（6） while（Q-=NULL） P=Q; Q=Q-（7） while（P-（10） Q=P;（11） Q=P-（12） P=L;（13） L=L-（14） free（Q）;a. （11） （3） （14） b. （10） （12） （8） （3） （14） c. （10） （12） （7） （3） （14） d. （12） （11） （3） （14） e. （9） （

3、11） （3） （14）2.8 已知P结点是某双向链表的中间结点，试从下列提供的答案中选择合适的语句序列。a. 在P结点后插入S结点的语句序列是_。b. 在P结点前插入S结点的语句序列是_。c. 删除P结点的直接后继结点的语句序列是_。d. 删除P结点的直接前驱结点的语句序列是_。e. 删除P结点的语句序列是_。priou=P-priou-priou;（4） P-priou=S;priou=P;（7） S-（8） S-（9） P-（10） P-（11） P-（12） P-（13） P-（14） P-（15） Q=P-（16） Q=P-（17） free（P）;（18） free（Q）;a. （

4、7） （3） （6） （12） b. （8） （4） （5） （13） c. （15） （1） （11） （18） d. （16） （2） （10） （18） e. （14） （9） （17）2.9 简述以下算法的功能。（1） Status A（LinkedList L） /L是无表头结点的单链表 if（L & L-next） Q=L; L=L- while（P-next） P=P-next=Q; Q- return OK;（2） void BB（LNode *s, LNode *q） p=s; while（p-=q） p=p- p-next =s; void AA（LNode *pa, LN

5、ode *pb） /pa和pb分别指向单循环链表中的两个结点 BB（pa,pb）; BB（pb,pa）;（1） 如果L的长度不小于2，将L的首元结点变成尾元结点。 （2） 将单循环链表拆成两个单循环链表。2.10 指出以下算法中的错误和低效之处，并将它改写为一个既正确又高效的算法。Status DeleteK（SqList &a,int i,int k） /本过程从顺序存储结构的线性表a中删除第i个元素起的k个元素 if（i1|ka.length） return INFEASIBLE;/参数不合法 else for（count=1;count=i+1;j-） a.elemj-i=a.elemj

6、; a.length-; /从顺序存储结构的线性表a中删除第i个元素起的k个元素 /注意i的编号从0开始 int j;0|ia.length-1|ka.length-i） return INFEASIBLE; for（j=0;j=k;j+） a.elemj+i=a.elemj+i+k; a.length=a.length-k;2.11 设顺序表va中的数据元素递增有序。试写一算法，将x插入到顺序表的适当位置上，以保持该表的有序性。Status InsertOrderList（SqList &va,ElemType x） /在非递减的顺序表va中插入元素x并使其仍成为顺序表的算法 int i;

7、if（va.length=va.listsize）return（OVERFLOW）; for（i=va.length;0,xB.length?A.length:B.length; for（i=0; if（A.elemiB.elemi） j=1; if（A.elemik） j=1; if（B.lengthk） j=-1; if（A.length=B.length） j=0; return j;2.13 试写一算法在带头结点的单链表结构上实现线性表操作Locate（L,x）;int LocateElem_L（LinkList &L,ElemType x） int i=0; LinkList p=L

8、; while（p&p-data!=x） p=p- i+; if（!p） return 0; else return i;2.14 试写一算法在带头结点的单链表结构上实现线性表操作Length（L）。/返回单链表的长度int ListLength_L（LinkList &L） if（p） p=p-next; while（p） return i;2.15 已知指针ha和hb分别指向两个单链表的头结点，并且已知两个链表的长度分别为m和n。试写一算法将这两个链表连接在一起，假设指针hc指向连接后的链表的头结点，并要求算法以尽可能短的时间完成连接运算。请分析你的算法的时间复杂度。void MergeL

9、ist_L（LinkList &ha,LinkList &hb,LinkList &hc） LinkList pa,pb; pa=ha; pb=hb; while（pa-next&pb-next） pa=pa- pb=pb-pa- hc=hb; while（pb-next） pb=pb- pb-next=ha- else hc=ha;next） pa=pa- pa-next=hb-2.16 已知指针la和lb分别指向两个无头结点单链表中的首元结点。下列算法是从表la中删除自第i个元素起共len个元素后，将它们插入到表lb中第i个元素之前。试问此算法是否正确？若有错，请改正之。Status De

10、leteAndInsertSub（LinkedList la,LinkedList lb,int i,int j,int len）0|j0|len0） return INFEASIBLE; p=la; k=1; while（k k+; q=p;=len） q=q- s=lb;j） s=s- s-next=p; q-next=s-Status DeleteAndInsertSub（LinkList &la,LinkList &lb,int i,int j,int len） LinkList p,q,s,prev=NULL; int k=1; / 在la表中查找第i个结点kq）return INF

11、EASIBLE; / 完成删除，注意，i=1的情况需要特殊处理prev） la=q- else prev-next=q- / 将从la中删除的结点插入到lb中 if（j=1）next=lb; lb=p; while（s&j-1） s=s-s）return INFEASIBLE; /完成插入2.17 试写一算法，在无头结点的动态单链表上实现线性表操作Insert（L,i,b），并和在带头结点的动态单链表上实现相同操作的算法进行比较。Status Insert（LinkList & L,int i,int b） /在无头结点链表L的第i个元素之前插入元素bp=L;q=（LinkList*）mall

12、oc（sizeof（LNode）;q.data=b;if（i=1）q.next=p;L=q; /插入在链表头部elsewhile（-i1） p=p-q-next=p-next=q; /插入在第i个元素的位置/ Insert 2.18试写一算法，实现线性表操作Delete（L,i），并和在带头结点的动态单链表上实现相同操作的算法进行比较。Status Delete（LinkList &L,int i） / 在无头结点链表L中删除第i个元素if（i=1） L=L- / 删除第一个元素 / 删除第i个元素/ Delete 2.19 已知线性表中的元素以值递增有序排列，并以单链表作存储结构。试写一高效

13、的算法，删除表中所有值大于mink且小于maxk的元素（若表中存在这样的元素），同时释放被删结点空间，并分析你的算法的时间复杂度（注意，mink和maxk是给定的两个参变量，它们的值可以和表中的元素相同，也可以不同）。Status ListDelete_L（LinkList &L,ElemType mink,ElemType maxk） LinkList p,q,prev=NULL; if（minkmaxk）return ERROR; p=L;data=mink） prev- free（q）;2.20 同2.19题条件，试写一高效的算法，删除表中所有值相同的多余元素（使得操作后的线性表中所有元

14、素的值均不相同），同时释放被删结点空间，并分析你的算法的时间复杂度。void ListDelete_LSameNode（LinkList & LinkList p,q,prev; if（p&data=prev-data）2.21 试写一算法，实现顺序表的就地逆置，即利用原表的存储空间将线性表逆置为/ 顺序表的逆置Status ListOppose_Sq（SqList & ElemType x;L.length/2; x=L.elemi; L.elemi=L.elemL.length-1-i; L.elemL.length-1-i=x;2.22 试写一算法，对单链表实现就地逆置。/ 带头结点的单

15、链表的逆置Status ListOppose_L（LinkList & LinkList p,q;next=L-2.23 设线性表，试写一个按下列规则合并A，B为线性表C的算法，即使得 当时；时。线性表A，B和C均以单链表作存储结构，且C表利用A表和B表中的结点空间构成。注意：单链表的长度值m和n均未显式存储。/ 将合并后的结果放在C表中，并删除B表Status ListMerge_L（LinkList &A,LinkList &B,LinkList &C） LinkList pa,pb,qa,qb; pa=A- pb=B- C=A; while（pa&pb） qa=pa; qb=pb; qb

16、-next=qa- qa-next=qb;pa）qb-next=pb; pb=B; free（pb）;2.24 假设有两个按元素值递增有序排列的线性表A和B，均以单链表作存储结构，请编写算法将A表和B表归并成一个按元素值递减有序（即非递增有序，允许表中含有值相同的元素）排列的线性表C，并要求利用原表（即A表和B表）的结点空间构造C表。/ 将合并逆置后的结果放在C表中，并删除B表Status ListMergeOppose_L（LinkList & pa=A; / 保存pa的前驱指针 / 保存pb的前驱指针 A- if（pa-next=A- /将当前最小结点插入A表表头next=qa; whil

17、e（pa） while（pb）2.25 假设以两个元素依值递增有序排列的线性表A和B分别表示两个集合（即同一表中的元素值各不相同），现要求另辟空间构成一个线性表C，其元素为A和B中元素的交集，且表C中的元素有依值递增有序排列。试对顺序表编写求C的算法。/ 将A、B求交后的结果放在C表中Status ListCross_Sq（SqList &B,SqList & int i=0,j=0,k=0; while（iA.length & jB.length）B.elemj） i+; elseB.elemj） j+; ListInsert_Sq（C,k,A.elemi）;2.26 要求同2.25题。试对单链表编写求C的算法。/ 将A、B求交后的结果放在C表中，并删除B表Status ListCross_L（LinkList & LinkList pa,pb,qa,qb,pt; /