发布时间 : 星期五 文章计算机软件技术基础所有题目答案-自学更新完毕开始阅读
A．p->prior->next->==p->next->next B．p->prior->prior==p->next->prior *C．p->prior->next->==p->next->prior D．p->next->next==p->prior->prior
18．在循环链表中，将头指针改设为尾指针rear后，其头结点和尾结点的存储位置分别是( )。 A．rear和rear->next->next *B．rear->next和rear C．rear->next->next和rear D．rear和rear->next
19．循环链表的主要优点是( )。
A．不再需要头指针了 B．已知某个结点的位置后，容易找到它的直接前驱 C．在进行插入、删除操作时，能更好地保证链表不断开 *D．从表中任一结点出发都能扫描到整个链表 20．在线性表的下列存储结构中，读取元素花费时间最少的是( )。 A．单链表 B．双链表 C．循环链表 *D．顺序表 二、判断题
√1．顺序存储的线性表可以随机存取。
╳2．顺序存储的线性表的插入和删除操作不需要付出很大的代价，因为平均每次操作只有近一半的元素需要移动。
√3．线性表中的元素可以是各种各样的，但同一线性表中的数据元素具有相同的特性，因此是属于同一数据对象。
╳4．在线性表的顺序存储结构中，逻辑上相邻的两个元素在物理位置上不一定相邻。 √5．在线性表的链式存储结构中，逻辑上相邻的元素在物理位置上不一定相邻。 √6．在单链表中，可以从头结点开始查找任何一个元素。 ╳7．线性表的链式存储结构优于顺序存储结构。
√8．在线性表的顺序存储结构中，插入和删除元素时，移动元素的个数与该元素的位置有关。 ╳9．在单链表中，要取得某个元素，只要知道该元素的指针即可，因此，单链表是随机存取的存储结构。
╳10．顺序存储方式只能用于存储线性结构。 三、填空题
1．为了便于讨论，有时将含n(n>0)个结点的线性结构表示成(a1，a2，?，an)，其中每个ai代表一个__结点_。a1称为_第一个_结点，an称为__最后一个_结点，i称为ai在线性表中的_位置__。对任意一对相邻结点ai、ai+1(1≤i 2．线性结构的基本特征是：若至少含有一个结点，则除起始结点没有直接__前驱_外，其他结点有且仅有一个直接__前驱_；除终端结点没有直接__后继_外，其他结点有且仅有一个直接_后继__。 3．所有结点按一对一的邻接关系构成的整体就是__线性__结构。 4．线性表的逻辑结构是__线性_结构，其所含结点的个数称为线性表的___长度_。 5．在单链表中，删除p所指结点的直接后继的操作是__ q=p->next；p->next=q->next；free(q)；___· 6．非空的单循环链表head的尾结点(由指针p所指)满足__ p->next= head _____。 7．rear是指向非空带头结点的单循环链表的尾指针，则删除起始结点的操作可表示为__ p=rear->next；q=p->next；p->next=q->next；free(q)；____。 8．对于一个具有n个结点的单链表，在p所指结点后插入一个结点的时间复杂度为__O(1)__，在给定值为x的结点后插入新结点的时间复杂度为__ O(n)__。 9．单链表表示法的基本思想是用___指针___表示结点间的逻辑关系。 10．在顺序表中插入或删除一个元素，平均需要移动_一半_元素，具体移动的元素个数与__元素的位置_有关。 11．在一个长度为n的向量的第i(1≤i≤n+1)个元素之前插入一个元素时，需向后移动___ n-i+1__个元素。 12．在一个长度为n的向量中删除第i(1≤i≤n)个元素时，需向前移动__ n-i __个元素。 13．在双链表中，每个结点有两个指针域，一个指向___前驱__，另一个指向___后继___。 5 14．在一个带头结点的单循环链表中，p指向尾结点的直接前驱，则指向头结点的指针head可用p表示为head=__ p->next->next ；___。 15．设head指向单链表的表头，p指向单链表的表尾结点，则执行p->next=head后，该单链表构成__单循环链表___。 16．在单链表中，若p和s是两个指针，且满足p->next与s相同，则语句p->next=s->next的作用是_删除__s指向的结点。 17．设r指向单循环链表的最后一个结点，要在最后一个结点之后插入s所指的结点，需执行的三条语句是___s->next= r->next __；r->next=s；r=s； 18．在单链表中，指针p所指结点为最后一个结点的条件是__ p->next=NULL___。 19．在双循环链表中，若要在指p所指结点前插入s所指的结点，则需执行下列语句：s->next=p； s->prior=p->prior；__ p->prior->next __=s；p->prior=s； 20．在单链表中，若要在p所指结点之前插入s所指的结点，可进行下列操作： s->next=___ p->next __； p->next=s； temp=p->data； p->data=__ s->data ___； s->data=__ temp _； 四、应用题 1．描述以下三个概念的区别：头指针，头结点，首元结点(第一个元素结点)。 答：首元结点是指链表中存储的线性表中的第一个数据元素的结点。为了操作方便，通常在链表的首元结点之前附设一个结点，称为头结点。头指针是指向链表中的第一个结点的指针。 2．何时选用顺序表，何时选用链表作为线性表的存储结构为宜？ 答：从空间上来看，当线性表的长度变化较大、难以估计其规模时，选用动态的链表作为存储结构比较合适，但链表除了需要设置数据域外，还要额外设置指针域，因此当线性表长度变化不大、易于事先确定规模时，为了节约存储空间，宜采用顺序存储结构。从时间上来看，若线性表的操作主要是查找，很少进行插入和删除操作时，应选用顺序表。对于频繁进行插入和删除操作的线性表，宜采用链表作为存储结构。 3．在顺序表中插入和删除一个结点需平均移动多少个结点？具体的移动次数取决于哪两个因素？ 答：平均移动表中大约一半的结点，插入操作平均移动n/2 个结点，删除操作平均移动（n-1）/2 个结点。具体移动的次数取决于表长和插入、删除的结点的位置。 4．为什么在单循环链表中设置尾指针比设置头指针更好？ 答：单循环链表中无论设置尾指针还是头指针都可以遍历表中任一个结点，但设置尾指针时，若在表尾进行插入或删除操作可在O(1)时间内完成，同样在表头进行插入或删除操作也可在O(1)时间内完成。但若设置的是头指针，表尾进行插入或删除操作，需要遍历整个链表，时间复杂度为O(n)。 5．双链表和单循环链表中，若仅知道指针p指向某个结点，不知道头指针，能否将结点*p 从相应的链表中删除？若可以，其时间复杂度各为多少？ 答：能删除。双链表上删除p所指向的结点的时间复杂度为O(1)，单循环链表上删除p所指向的结点的时间复杂度为O(n)。 6．下列算法的功能是什么？ LinkList testl(LinkList 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个线性表同时共存，并且在处理过程中各表的长度会发生动态变化，线性表的总长度也会自动地改变。在此情况下，应选择哪一种存储结构？为什么？ 6 答：应选用链式存储结构。因为顺序表是静态存储结构，只能预先分配，不能随着线性表长度的改变而变化。而链表则可根据需要动态地申请空间，因此适用于动态变化表长的线性表。 8．若线性表的总数基本稳定，且很少进行插入、删除操作，但要求以最快的方式存取线性表的元素，应该用哪种存储结构？为什么？ 答：应选用顺序存储结构。因为顺序存储结构存取元素操作的时间复杂度为O(1)。 五、算法设计题 1．试用顺序表作为存储结构，实现将线性表(a0，a1，a2，?an-1)就地逆置的操作，所谓“就地”是指辅助空间为O(1)。 答：(1)顺序表的就地逆置 分析：分别用两个整型变量指向顺序表的两端，同时向中间移动，移动的同时互换两个下标指示的元素的值。 void Seqreverse(SeqList L){／／顺序表的就地逆置 for(i=0；j=L.1ength-1；i {t=L.data[i]; L.data[i]=L.data[j]; L.data[j]=t; } } (2)链表的就地逆置 分析：本算法的思想是逐个地把L的当前元素r插入到新的链表头部。 void Linkedreverse(LinkedList L){／／链表的就地逆置 p=L->next；L->next=NULL； while(p!=NULL) {r=p，p=p->next； ／／r指向当前待逆置的结点，p记下下—个结点 r->next=L—>next；L->next=r； ／／放到表头 } } 2．设顺序表L是一个递增(允许有相同的值)有序表，试写一算法将x插入L中，并使L仍为一个有序表。 答：分析：先找到x的正确插入位置，然后将大于x的元素从后向前依次向下移动，最后将x插入到其位置上，同时顺序表长度增1。 void SeqListinsert(SeqList L，int x){／／x插入到递增有序的顺序表L中 i=0; while((i<=L.length-1)&&(x>=L.data[i])) i++； ／／找正确的插入位置 for(k=L.length-1;k>=i；k--) ／／元素从后往前依次后移 L.data[k+1]：L.data[k]； L.data(i]’x； ／／x插入到正确位置 L.1ength++； ) 3.设单链表L是一个非递减有序表，试写一个算法将x插入其中后仍保持L的有序性。 答：分析：此问题的关键是在链表中找到x的插入位置，因此需要两个指针一前一后地依次向后移动。 void LinkListinsert(LinkedList L，int x){／／x插入有序链表L中 q=L；p=q—>next； while(p!=NULL&&p—>data s=(LinkedList)malloc(sizeof(LNode))； ／／生成新结点 S—>data=x； S—>next=p； q—>next=s； } 4. 试写出在不带头结点的单链表的第i个元素之前插入一个元素的算法。 答：分析：对不带头结点的链表操作时，要注意对第一个结点和其他结点操作的不同。 void LinkedListlnsert(LinkedList head，int x，int i) {／／不带头结点的单链表的第i个元素之前插入一个元素 p=L：j=1; while(p!=NULL&&j 7 {p=p—>next；j++；} if(i<=0||p==NULL) printf(”插入位置不正确＼n”)； else {q=(LinkedList)malloc(sizeof(LNode))；q—>data=x； if(i==1) {q—>next=L；L=q；} ／／在第一个元素之前插入 else{q—>next=p—>next；p—>next=q；} ／／在其他位置插入 } } 5．设A、B是两个线性表，其表中元素递增有序，长度分别为m和n。试写一算法分别以顺序存储和链式存储将A和B归并成一个仍按元素值递增有序的线性表C。 答：(1)分析：用三个变量i、j、k分别指示A、B、C三个顺序表的当前位置，将A、B表中较小的元素写入C中，直到有一个表先结束。最后将没结束的表的剩余元素写入C表中。 SeqList Seqmerge(SeqList A，SeqList B){／／有序顺序表A和B归并成有序顺序表C i=0；j=0；k=0； ／／i，i，k分别为顺序表A，B，C的下标 while(i {if(A.data[i] else {C.data[k]=B.data[j];j++；} ／／B中当前元素较小 k++； } if (i==m) for(t=j；t VOid Linkmerge(LinkedList A，LinkedList B，LinkedList C) {／／有序链表A和B归并成有序链表C pa=A—>next；pb=B—>next；C=A；pc=C； while(pa&&pb) ／／A和B都不为空时 {if(pa—>data {qa=pa->next； pC->next=pa； pc=pc->next； pa=qa；} else {qb=pb->next；pc->next=pb：pc=pc->next；pb=qb；} ／／B当前结点值较小 } if(pa)pc—>next=pa； ／／A没有结束，将A表剩余元素链接到C表 if(pb)pc—>next=pb； ／／B没有结束，将B表剩余元素链接到C表 free(B)； ／／释放B表的头结点 } 本算法需要遍历两个线性表，因此时间复杂度为O(m+n)。 6．设指针la和lb分别指向两个不带头结点的单链表的首结点，设计从表la中删除第i个元素起共len个元素，并将这些元素插入到lb中第j个结点之前的算法。 答：分析：先在la中找到第i个结点，分别用两个指针pre和p指向第i-1和第i个结点，然后用指针q从第i个结点起向后走len个元素，使q指向此位置。然后在lb中找到第j个结点，将p所指向的la表中的第i个及q所指向的最后一个共len个结点插入到lb中。 void Deletelnsert(LinkedList la，LinkedList lb，int i，int j, int len) {／／删除不带头结点的单链表la中第i个元素起共len个元素,并将这峰元素插入到单链表lb中第j个结点之前 if(i<0||j<0||len<0) exit(0)； p=la；k=1；pre=NULL； while(p&&k q=p；k=l； ／／p指向la表中第i个结点 while(q&&k 8