发布时间 : 星期六 文章《数据结构》习题集：第2章 线性表更新完毕开始阅读
数据结构课后练习题 第2章 线性表
所要移动的元素个数又是多少？ 答案：在等概率前提下，平均每插入一个元素需要移动的元素个数为(0+1+2+?+n)/(n+1)=n/2。若元素插在ai 与ai+1 间（0<=i<=n-1）的概率为2(n-i)/(n(n+1))，则平均每插入一个元素所要移动的元素个数为： （2n+1）/3
4. 为什么在单循环链表中设置尾指针比设置头指针更好？
解答：单循环链表中无论设置尾指针还是头指针都可以任一结点从遍历表中其它结点，但设置尾指针时，若在表尾进行插入或删除操作时可在O(1)时间内完成，同样在表头进行插入或删除操作时也可在O(1)时间内完成。但设置的是头指针，表尾进行插入或删除操作，需要遍历整个链表，时间复杂度为O(n)。 5. 双链表和单循环链表中，若仅知道指针p 指向某个结点，不知道头指针，能否将结点*p 从相应的链表中删除？
若可以，其时间复杂度各为多少？
解答：能删除。双链表上删除p 所指向的结点的时间复杂度为O(1)，单循环链表上删除p 所指向的结点的时间复杂度为O(n)。
6. 下列算法的功能是什么？
LinkedList test1(LinkedList L) {
//L 是无头结点的单链表 ListNode *q,*p; if(L&&L->next) {
q=L ;
L=L->next; p=L;
while(p->next)
p=p->next; p->next=q; q->next=NULL; }
return L; }
解答：如果长度大于 1，则将首元结点删除并插入到表尾。
7. 如果有n 个线性表同时共存，并且在处理过程中各表的长度会发生动态变化，线性表的总长度也会自动地改
变。在此情况下，应选择哪一种存储结构。为什么？
解答：应选用链式存储结构。因为顺序表是静态存储结构，只能预先分配存储单元，不能随着线性表长度的改变而变化。而链表则可根据需要动态的申请空间，因此适用于动态变化表长的线性表。
8. 若线性表的总数基本稳定，且很少进行插入删除操作，但要求以最快的方式存取线性表的元素，应该用哪种存
储结构。为什么？
解答：应该用顺序存储结构。因为顺序存储结构存取元素操作的时间复杂度为 O(1)。 9. 设有多项式a(x)=9+8x+9x4+5x10
b(x)=-2x+22x7-5x10
（1） 用单链表给出a(x)、b(x)的存储表示；
（2） 设c (x)=a(x)+b(x)，求得c(x)并用单链表给出其存储表示。
解答：用单链表表示多项式，除指针域外需设置两个数据域，一个用来存储系数，一个用来存储指数。
5/7
北京理工大学珠海学院计算机学院 “数据结构”课程组编制 2011-3-1
数据结构课后练习题 第2章 线性表
五、 设计题
1. 编写一个函数将一个顺序表A（有多个元素且任何元素不为0）分拆成两个顺序表，使A 中大于0的元素存放
在B 中，小于0 的元素存放在C 中。
解答：void split(SqList A,SqList &B,SqList &C){//int I;
B.length=C.length=0; for(I=0;I if(A.elem[i]>0){ B.elem[B.length]=A.elem[i]; B.length++; } else{ C.elem[C.length]=A.elem[i]; C.length++; } } } 2. 设顺序表L 中的数据元素递增有序。试写一算法，将解答：status ListInsert(SqList &L,ElemType e){ ElemType *p,*q,*newbase; int j; if(L.length>=L.listsize){ newbase=(ElemType )realloc(L.elem,(L.listsize+LISTINCRMENT)*sizeof(ElemType)); if(!newbase) exit(OVERFLOW); L.elem=newbase; L.listsize=+LISTINCRMENT; } For(j=L.length-1;j>=0&&e L.elem[j+1]=L.elem[j]; L.elem[j+1]=e; ++L.length; return OK; } 3. A、B 为元素递增有序排列的单链表（同一表中可能有相同元素），编写算法另建一单链表公共元素，要求解答：提示：两个表的公共元素指的是既存在于有一个头结点c，再后将其删除。采用顺序存储结构实现C 的元素值各不相同且递增有序。A 表中， 北京理工大学珠海学院计算机学院 e 插入到顺序表的适当位置，插入后保持该表的有序性。B 表中的元素，为了操作方便， “数据结构”课程组编制 2011-3-1 C，保存两个表的 先让单链表C 带6/7 也存在于数据结构课后练习题 第2章 线性表 LinkList Inter_eq(LinkList a,LinkList b){ LinkList p,q,r,c; c=(LinkList)malloc(sizeof(LNode));//建立单链表C 的头指针 r=c; p=a; q=b; while(p&&q){ if(p.data p=p.next; else if(p.data>q.data) q=q.next; else //找到元素值相同的结点 {s=(LinkList)malloc(sizeof(LNode)); s.data=p.data;r.next=s;r=s; //把s 结点链到c 的末尾，r 始终指向链表C 的最后一个结点 while(p.data==p.next.data) p=p.next; //跳过相同的值的结点 p=p.next; while(q.data==q.next.data) q=q/next; q=q.next; } } r.next=NULL; s=c;c=c.next;free(c); //删除C 链表的头结点 return (c); } 4、设有一个由正整数组成的无序单链表，编写算法实现下列功能： （1） 找出最小值结点，且显示该数值。 （2） 若该数值为奇数，则将其与直接后继结点的数值交换。 （3） 若为偶数，则将其直接后继结点删除。 else{ 解答：参考程序： void outmin(LinkList L){ q=p.next;p.next=q.next; LinkList p=L,q=L; free(q); int temp; } while(q){ } if(p.data>q.data)p=q; } q=q.next; } printf(“%d”,p.data); if(p.next){ if(p.data%2==1){ temp=p.data; p.data=p.next.data; p.next.data=temp; } 7/7 北京理工大学珠海学院计算机学院 “数据结构”课程组编制 2011-3-1