1.设n为正整数，利用大"O"记号，将下列程序段的执行时间表示为n的函数。
(1) i=1; k=0;
while(i<n)
{ k=k+10*i;i++;
}
(2) i=1; j=0;
while(i+j<=n)
{
if (i>j) j++;
else i++;
}
(3)x=n; // n>1
while (x>=(y+1)*(y+1))
y++;
第二章线性表
2.1下述算法的功能是什么?
LinkList Demo(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;
}// Demo
答：
该算法的功能是：将开始结点摘下链接到终端结点之后成为新的终端结点，而原来的第二个结点成为新的开始结点，返回新链表的头指针。
2.9设顺序表L是一个递增有序表，试写一算法，将x插入L中，并使L仍是一个有序表。
答：
因已知顺序表L是递增有序表，所以只要从顺序表终端结点（设为i位置元素）开始向前寻到第一个小于或等于x的元素位置i后插入该位置即可。
在寻过程中，由于大于x的元素都应放在x之后，所以可边寻，边后移元素，当到第一个小于或等于x的元素位置i时，该位置也空出来了。
算法如下：
//顺序表存储结构如题2.7
void InsertIncreaseList( Seqlist *L , Datatype x )
{
int i;
if ( L->length>=ListSize)
Error(“overflow");
for ( i=L -> length ; i>0 && L->data[ i-1 ] > x ; i--)
L->data[ i ]=L->data[ i ] ; //比较并移动元素
L->data[ i ] =x;
L -> length++;
}
2.14已知单链表L是一个递增有序表，试写一高效算法，删除表中值大于min且小于max的结点(若表中有这样的结点)，同时释放被删结点的空间，这里min和max是两个给定的参数。请分析你的算法的时间复杂度。
解：
要解这样的问题，我们首先想到的是拿链表中的元素一个个地与max和min比较，然后删除这个结点。由于为已知其是有序链表，则介于min和max之间的结点必为连续的一段元素序列。所以我们只要先到所有大于min结点中的最小结点的直接前趋结点*p后，依次删除小于max的结点，直到第一个大于等于max结点*q位置，然后将*p结点的直接后继指针指向*q结点。
算法如下：
void DeleteList ( LinkList L, DataType min , DataType max )
{
ListNode *p , *q , *s;
p=L;
while( p->next && p->next->data <=min )
//比min大的前一个元素位置
p=p->next;
q=p->next;//p指向第一个不大于min结点的直接前趋，q指向第一个大于min的结点
while(q &&q->data<max)
{s=q;q=q->next;
free(s);//删除结点，释放空间
}
p->next=q;//将*p结点的直接后继指针指向*q结点
}
第三章栈和队列
3.1设将整数1，2，3，4依次进栈，但只要出栈时栈非空，则可将出栈操作按任何次序夹入其中，请回答下述问题：
(1)若入、出栈次序为Push(1), Pop(),Push(2),Push(3), Pop(), Pop( ),Push(4), Pop( ),则出栈的数字序列为何(这里Push(i)表示i进栈，Pop( )表示出栈)?
(2)能否得到出栈序列1423和1432?并说明为什么不能得到或者如何得到。
(3)请分析1，2，3，4的24种排列中，哪些序列是可以通过相应的入出栈操作得到的。
答：
(1)出栈序列为：1324
(2)不能得到1423序列。因为要得到14的出栈序列，则应做Push(1),Pop(),Push(2),Push (3),
Push(4),Pop()。这样，3在栈顶，2在栈底，所以不能得到23的出栈序列。能得到1432的出栈序列。具体操作为：Push(1), Pop(),Push(2),Push(3),Push(4),Pop(),Pop(),Pop()。
(3)在1，2，3，4的24种排列中，可通过相应入出栈操作得到的序列是：
1234,1243,1324,1342,1432,2134,2143,2314,2341,2431,3214,3241,3421,4321
不能得到的序列是：
1423,2413,3124,3142,3412,4123,4132,4213,4231,4312

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。