2010年自学考试《高级语言程序设计》习题第1部分引论二、选择1．链式存储结构中，每个数据的存储结点里D指向邻接存储结点的指针，用以反映数据间的逻辑关系。A．只能有1个B．只能有2个C．只能有3个D．可以有多个2．有下面的算法段：for(i=0;i<n;i++)k++;其时间复杂度为B。A．O(1)B．O(n)C．O(log2n)D．O(n2)四、应用1．给出下面3个算法段的时间复杂度：（1）x++；（2）for(j=1;j<n;j++)x++;（3）for(j=1;j<=n;j++)for(k=1;k<=m;k++)x++;答：（1）的时间复杂度为O(1)；（2）的时间复杂度O(n)；（3）的时间复杂度是O(n2)。第2部分线性表一、填空1．以顺序存储结构实现的线性表，被称为顺序表。2．以链式存储结构实现的线性表，被称为链表。3．不带表头结点的链表，是指该链表的表头指针直接指向该链表的起始结点。4．顺序表Sq=(a1，a2，a3，…，an)（n≥1）中，每个数据元素需要占用w个存储单元。若m为元素a1的起始地址，那么元素an的存储地址是m+(n-1)*w。5．当线性表的数据元素个数基本稳定、很少进行插入和删除操作，但却要求以最快的速度存取表中的元素时，我们应该对该表采用顺序存储结构。二、选择1．下面，对非空线性表特点的论述，C是正确的。A．所有结点有且只有一个直接前驱B．所有结点有且只有一个直接后继C．每个结点至多只有一个直接前驱，至多只有一个直接后继D．结点间是按照1对多的邻接关系来维系其逻辑关系的2．带表头结点的单链表Lk_h为空的判定条件是B。A．Lk_h==NULLB．Lk_h->Next==NULLC．Lk_h->Next==Lk_hD．Lk_h!=NULL3．往一个顺序表的任一结点前插入一个新数据结点时，平均而言，需要移动B个结点。A．nB．n/2C．n+1D．(n+1)/24．在一个单链表中，已知qtr所指结点是ptr所指结点的直接前驱。现要在qtr所指结点和ptr所指结点之间插入一个rtr所指的结点，要执行的操作应该是C。A．rtr->Next=ptr->Next;ptr->Next=rtr;B．ptr->Next=rtr->Next;C．qtr->Next=rtr;rtr->Next=ptr;D．ptr->Next=rtr;rtr->Next=qtr->Next;5．在一个单链表中，若现在要删除ptr指针所指结点的直接后继结点，则需要执行的操作是A。A．ptr->Next=ptr->Next->Next;B．ptr=ptr->Next;ptr->Next=ptr->Next->Next;C．ptr=ptr->Next->Next;D．ptr->Next=ptr;6．在长度为n的顺序表中，往其第i个元素（1≤i≤n）之前插入一个新的元素时，需要往后移动B个元素。A．n-iB．n-i+1C．n-i-1D．i7．在长度为n的顺序表中，删除第i个元素（1≤i≤n）时，需要往前移动A个元素。A．n-iB．n-i+1C．n-i-1D．i8．设tail是指向一个非空带表头结点的循环单链表的尾指针。那么，删除链表起始结点的操作应该是D。A．ptr=tail;B．tail=tail->Next;tail=tail->Next;free(tail);free(ptr);C．tail=tail->Next->Next;D．ptr=tail->Next->Next;Free(tail);tail->Next->Next=ptr->Next;Free(ptr);free(ptr);9．在单链表中，如果指针ptr所指结点不是链表的尾结点，那么在ptr之后插入由指针qtr所指结点的操作应该是B。A．qtr->Next=ptr;B．qtr->Next=ptr->Next;ptr->Next=qtr;ptr->Next=qtr;C．qtr->Next=ptr->Next;D．ptr->Next=qtr;ptr=qtr;qtr->Next=ptr;四、应用1．设计一个计算带表头结点的单链表L的长度（即结点个数）的算法。typedefstructnode*link;typedefstructnode{ListItemelement;linknext;}Node;答：算法设计如下：intLength(linkL){Linkp=L->next;intsum=0;while(p){sum++;p=p->next;}return(sum);}2、已知一个带表头结点的无序单链表L。试编写一个算法，功能是从表中找出最大值和最小值。typedefstructnode{ListItemelement;structnodenext;}Node,*link;viodmaxmin(linkL){intmax,min;linkp=L->next;if(p){max=p->element;min=p->element;p=p->next;while(p){if(max<p->element)max=p->element;if(min>p->element)min=p->element;p=p->next;}printf("max=%d,min=%d\n",max,min);}3．已知一个带表头结点的无序单链表L，不同结点的Data域值有可能相同。编写一个算法，功能是计算出Data域值为x的结点的个数。typedefstructnode*link;typedefstructnode{ListItemdata;linknext;}Node;答：intCount(linkL,intx){n...