《计算机软件技术基础》课后题答案 - 图文(3)

╳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)个元素之前插入一个元素时，需

11

向后移动___ n-i+1__个元素。

12．在一个长度为n的向量中删除第i(1≤i≤n)个元素时，需向前移动__ n-i __个元素。

13．在双链表中，每个结点有两个指针域，一个指向___前驱__，另一个指向___后继___。

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．描述以下三个概念的区别：头指针，头结点，首元结点(第一个元素结点)。 答：首元结点是指链表中存储的线性表中的第一个数据元素的结点。为了操作方便，通常在链表的首元结点之前附设一个结点，称为头结点。头指针是指向

12

链表中的第一个结点的指针。

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)

13

{//L是无头结点的单链表 LinkList *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)。 五、算法设计题

假设算法中用到的顺序表和链表结构如下： #define maxsize 100;

Typedef struct node1 {datatype data[maxsize]; int length } SeqList; Typedef struct node2 {datatype data; struct node2 *next } LinkedList ; 1．试用顺序表作为存储结构，实现将线性表(a0，a1，a2，?an-1)就地逆置的

14

操作，所谓“就地”是指辅助空间为O(1)。 答：(1)顺序表的就地逆置

分析：分别用两个整型变量指向顺序表的两端，同时向中间移动，移动的同时互换两个下标指示的元素的值。

void Seqreverse(SeqList *L){／／顺序表的就地逆置 for(i=0；j=L->length-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仍为一个有序表。

答：分 …… 此处隐藏：1847字，全部文档内容请下载后查看。喜欢就下载吧 ……