蘇州大學(xué)-數(shù)據(jù)結(jié)構(gòu)-課程期中考試答案

《蘇州大學(xué)-數(shù)據(jù)結(jié)構(gòu)-課程期中考試答案》由會員分享，可在線閱讀，更多相關(guān)《蘇州大學(xué)-數(shù)據(jù)結(jié)構(gòu)-課程期中考試答案（10頁珍藏版）》請在裝配圖網(wǎng)上搜索。

蘇州大學(xué) 數(shù)據(jù)結(jié)構(gòu) 課程期中考試（共6頁） 學(xué)院 計算機 專業(yè) 計算機科學(xué)與技術(shù) 成績____________________ 班級 11計科 學(xué)號_____________姓名_____________日期 2012.11_ 一、 填空（14*2 分） 1、下列算法的時間復(fù)雜度是 O() 。 x=n; y=0; while (x>=y*y) y=y+1; 2、 對于順序存儲的棧，因為棧的空間是有限的，在進行 入棧 運算時，可能發(fā)生棧的上溢（overflow），在進行 出棧 _運算時，可能發(fā)生棧的下溢(underflow)。 3、以順序結(jié)構(gòu)實現(xiàn)的雙棧類中，其私有數(shù)據(jù)成員數(shù)組S[0..n-1]存放兩個棧中的所有元素，top1和top2分別指向兩個棧的棧頂位置，入棧1時top1由小到大，入棧2時top2由大到小，則判斷雙棧棧滿的條件是 top1+1>=top2 ，雙棧?？盏臈l件是 top1==-1 && top2==n 。 4、完成鏈?zhǔn)酱鎯Y(jié)構(gòu)下Queue類的append方法，其中front和rear指針分別指示隊首和隊尾結(jié)點： Error_code Queue :: append(const Queue_entry &item) { Node *new_rear = new Node(item); if (new_rear == NULL) return overflow; if (rear == NULL) front=rear=new_rear; ; else { rear->next=new_rear; ； rear = new_rear; } return success; } 5、如果一個函數(shù)直接或間接地 調(diào)用 自己，則稱這個函數(shù)是一個遞歸函數(shù)。 6、在一個長度為n的順序表中的第position（0≤position void List :: rec_count(Node *head,List_entry item,int &count) { if (head==NULL) return ; else if (head->entry==item) count++; rec_count(head->next,item,count); } (2)為List添加一個成員函數(shù)，刪除線性表中所有值為item的結(jié)點。 例如：原線性表為：（7，2，1，7，2，3，6，5） 刪除7之后的表為：（2，1，2，3，6，5） 請按以下函數(shù)原型進行設(shè)計，其中count返回被刪除的元素的個數(shù)。（10分） template Error_code List :: removealloccurance(List_entry item,int &count) { Node *p,*q; count=0; p=head; while (p!=NULL) if ( p->entry!=item ) break; else{ head=p->next; delete p; count++; p=head;} //刪除表首與item相同的結(jié)點，可能有多個連續(xù)相同的結(jié)點 if (head==NULL) return success; //若此時已為空表，則返回 q=head;p=head->next;//表長大于等于1 //q,p分別為鏈表的0號和1號結(jié)點（如果1號結(jié)點不存在，則p為空）， //0號結(jié)點的值肯定不是item //以下要求保證p,q保持前后相鄰 while (p!=NULL) if (p->entry==item){ q->next=p->next; delete p; count++;//刪除p結(jié)點 p=q->next;//維護p的值 } else { q=p;p=p->next;//q,p分別向后移動 } return success; } 10