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

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

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