页面打开中,请稍候...
www.Gzu521.com
| GZU521.COM学习网 |
|
●试题四 阅读下列函数说明，将应填入(n)处的字句写在答卷纸的对应栏内。 【函数1说明】 函数compare(sqlist a，sqlist b)的功能是：设a=(al，…，am)和b=(bl，…，bn)均为顺序表，"比较"，两个顺序表a和b的大小。设a’和b’分别为a和b中除去最大共同前缀后的子表(例如，a=(y，x，x，z，x，z)，b=(y，x，x，z，y，x，x，z)，则两者中最大的共同前缀为(y，x，x，z)，在两表中除去最大共同前缀后的子表分别为a′=(x，z)和b′=(y，x，x，z))。若a′=b′=空表，则a=b;若a′=空表，而b′≠空表，或者两者均不为空表，且a′的首元小于b’的首元，则a 提示：算法的基本思想为：若相等，则j+l，之后继续比较后继元素;否则即可得出比较结果。显然，j的初值应为0，循环的条件是j不超出其中任何一个表的范围。若在循环内不能得出比较结果，则循环结束时有3种可能出现的情况需要区分。 【函数1】 int compare(sqlista，sqlist b) { //若a j=0; while(i< (1) &&j<E M /^ %D[N#�1$[转 贴 于 我 的 学 习 网 IT认证计算机软件水平考试 HTtp://wwW.gzU521.coM)E M /^ %D[N#�1$ b.length) if(a.elem[j]< b.elem[j])return(-1); else if(a.elem[j]> b.elem[j])return (1) ; else (2) ; if(a.length== b.length)return(0); else if(a.length< b.length)return(-1); else return (1) ; }//compare //函数1的时间复杂度是 (3) 。 【函数2说明】 函数exchange_l(slink&l，int m)的功能是：用尽可能少的辅助空间将单链表中前m个结点和后n个结点的互换。即将单链表(a1，a2…，am，b1，b2，…，bn)改变成(b1，b2，…，bn，a1，a2，…，am)。 【函数2】 void exchange_l(slink &l，int m) { if( (4) &&l->next)//链表不空且m!=0 { p=l->next;k=1; while(k { p= (5) ;++k; } if( (6) &&p->next)//n!=0时才需要修改指针 { ha=l->next;//以指针ha记a1结点的位置 l->next=p->next;//将b1结点链接在头结点之后 p->next=null;//设am的后继为空 q= (7) ;//令q指向b1结点 while(q->next)q= (8) ;//查找bn结点 q->next= (9) ;//将a1结点链接到bn结点之后 } } } //函数2的时间复杂度是 (10) 。 |
责任编辑：gzu521
您现在的位置:
