蘇州大學-數(shù)據(jù)結構-課程期中考試答案
《蘇州大學-數(shù)據(jù)結構-課程期中考試答案》由會員分享,可在線閱讀,更多相關《蘇州大學-數(shù)據(jù)結構-課程期中考試答案(10頁珍藏版)》請在裝配圖網(wǎng)上搜索。
蘇州大學 數(shù)據(jù)結構 課程期中考試(共6頁)學院 計算機 專業(yè) 計算機科學與技術 成績_班級 11計科 學號_姓名_日期 2012.11_一、 填空(14*2 分)1、下列算法的時間復雜度是 O() 。x=n;y=0;while (x=y*y)y=y+1;2、 對于順序存儲的棧,因為棧的空間是有限的,在進行 入棧 運算時,可能發(fā)生棧的上溢(overflow),在進行 出棧 _運算時,可能發(fā)生棧的下溢(underflow)。3、以順序結構實現(xiàn)的雙棧類中,其私有數(shù)據(jù)成員數(shù)組S0.n-1存放兩個棧中的所有元素,top1和top2分別指向兩個棧的棧頂位置,入棧1時top1由小到大,入棧2時top2由大到小,則判斷雙棧棧滿的條件是 top1+1=top2 ,雙棧??盏臈l件是 top1=-1 & top2=n 。4、完成鏈式存儲結構下Queue類的append方法,其中front和rear指針分別指示隊首和隊尾結點: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(0positionn)個位置刪除某個元素時,需移動 n-position-1 個元素。7、在線性表改進的單鏈表實現(xiàn)方法中,我們定義了一個current指針指向最近訪問過的結點,請解釋這樣做的好處: 在對表中元素進行訪問時,不需要每次都從頭開始,在順序訪問或從前往后的訪問中能提供操作效率。8、用抽象數(shù)據(jù)類型對數(shù)據(jù)結構進行的ADT定義通常包含兩個內(nèi)容,分別是這種數(shù)據(jù)結構的邏輯結構定義以及 基本操作集 。9、Evaluate the postfix expression: 2 4 3 1 + * + , where each number represents an operand and each symbol of + and * represents an operator, please give the result of the expression on the following line 18 。10、在高級語言中為了實現(xiàn)函數(shù)之間的相互調(diào)用,需要用到 棧 作為輔助數(shù)據(jù)結構來存放調(diào)用記錄(invocation record),調(diào)用記錄中主要包含該調(diào)用函數(shù)的局部變量、參數(shù)和 函數(shù)返回地址 。二、 應用題(46分)1、說明線性表、棧與隊列的異同點。(9分)相同點:都是線性結構,都是邏輯結構的概念。都可以用順序存儲或鏈表存儲;棧和隊列是兩種特殊的線性表,即受限的線性表,只是對插入、刪除運算加以限制。不同點: 運算規(guī)則不同線性表可以在任何合法位置進行插入和刪除;棧是只允許在一端進行插入、刪除運算,因而是后進先出表LIFO;隊列是只允許在一端進行插入、另一端進行刪除運算,因而是先進先出表FIFO。 用途不同線性表用于處理更一般的數(shù)據(jù)處理場合;堆棧用于子程調(diào)用和保護現(xiàn)場;隊列用于多道作業(yè)處理、資源分配等。2、A circular queue has the problem in which it is not easy to distinguish between full and empty queues.Draw two situations to illustrate this point.The front and rear pointers should be in the same position in each situation. Give an solution to distinguish between full and empty queues.(9分)答:用損失一個空間的方法,即人為地將隊滿條件修改為:front=(rear+2)%maxqueue;隊空條件不變,仍為:front=(rear+1)%maxqueue;3、What is wrong with the following attempt to use the copy constructor to implement the overloaded assignment operator for a linked Stack?(9分)void Stack : operator = (const Stack &original)Stack new_copy(original);top_node = new_copy.top_node;Answer (1) The assignment top_node = new_copy.top_node; leaves the former nodes of the left hand side of the assignment operator as garbage.應該回收的空間沒回收,結果丟了變成垃圾!(2) Moreover, when the function ends, the statically allocatedStack new_copy will be destructed, this will destroy the newly assigned left hand side of the assignment operator. 把需要賦值不該回收的空間回收了。4、簡述順序線性表和鏈式線性表兩種存儲結構的優(yōu)缺點和適用場合。(10分)順序表的缺點:Overflow,可能溢出Must determine the maximum amount of the list,必須確定表的最大長度Insert will cause moving .插入刪除帶來元素的移動順序表的優(yōu)點:Random access 隨機存取, 讀寫效率為O(1)適用場合:when the entries are individually very small;元素個體較小when the size of the list is known when the program is written;表長能事先確定when few insertions or deletions need to be made except at the end of the list; 很少在非尾部位置插入和刪除when random access is important 經(jīng)常需要根據(jù)位序進行讀寫鏈表的優(yōu)點:Dont worry about overflow 不需要擔心溢出Dynamic structure 動態(tài)的結構,不需事先申請空間Insert only need change the links. 插入刪除只引起指針的變化鏈表的缺點:The links also take space. 鏈域也占空間,使存儲密度降低Not to suited to random access. 不能做到隨機存取,讀寫效率為O(n)適用場合:when the entries are large; 元素個體較大when the size of the list is not known in advance; 不能事先確定when flexibility is needed in inserting, deleting and rearranging the entries經(jīng)常需要做插入、刪除和元素的重排5、為了求解兩個一元多項式的和,需要將多項式存儲到計算機中。請設計多項式的邏輯結構和存儲結構,說明你這樣設計的原因。(9分)多項式的邏輯結構:1、 由Term元素構成的線性表。2、 Term是一個結構體,包含有一個非零項的系數(shù)和指數(shù)3、 此線性表為遞減有序表,按各非零項的指數(shù)遞減有序。4、 在做多項式加法時,從兩個多項式的頭上刪除相應的非零項結點,進行指數(shù)的比較,生成相應的項結點,插入到結果表的尾部,所以,這個操作的特點是頭上刪除,尾部插入,所以可將多項式設計為一個隊列。多項式的存儲結構:用鏈式結構比較合適。事先不知道多項式的長度,多項式系數(shù)不連續(xù),建議采用鏈式結構。三、算法設計題(26分)1、設stack類接口定義如下, class Stack public:Stack() ;bool empty() const ;Error_code pop() ;Error_code top(Stack_entry &item) const;Error_code push(const Stack_entry &item) ;int size(); void clear() ;private:使用以上棧的方法,設計外部函數(shù)bottom()。要求:如果棧非空,則返回棧底的數(shù)據(jù)元素;如果???,返回錯誤代碼fail。注意在實現(xiàn)bottom()后不能破壞棧原來的內(nèi)容,你所書寫的代碼不能依賴于棧的具體存儲方式,即必須使用上述的棧方法。提示:可以使用臨時棧來實現(xiàn)算法。請用以下函數(shù)原型進行設計。(8分)Error_code bottom( Stack &s, Stack_entry &item)Stack temp;Stack_entry t;if (s.empty() return fail;while (!s.empty( ) s.top(t);s.pop( );temp.push(t);item=t;while (!temp.empty( ) temp.top(t);temp.pop( );s.push(t);return success;2、假設用不帶current指針的簡單單鏈表作為線性表List的存儲結構。(1)為List類添加一個遞歸成員函數(shù),統(tǒng)計表中值為item的結點的個數(shù)。例如:線性表為:(7,2,1,7,2,3,6,5)統(tǒng)計鏈表中值為7的結點數(shù),返回結果應為2。(8分)template void List : rec_count(Node *head,List_entry item,int &count)if (head=NULL)return ;elseif (head-entry=item)count+; rec_count(head-next,item,count);(2)為List添加一個成員函數(shù),刪除線性表中所有值為item的結點。例如:原線性表為:(7,2,1,7,2,3,6,5)刪除7之后的表為:(2,1,2,3,6,5)請按以下函數(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;elsehead=p-next;delete p;count+;p=head;/刪除表首與item相同的結點,可能有多個連續(xù)相同的結點if (head=NULL)return success;/若此時已為空表,則返回q=head;p=head-next;/表長大于等于1/q,p分別為鏈表的0號和1號結點(如果1號結點不存在,則p為空),/0號結點的值肯定不是item/以下要求保證p,q保持前后相鄰while (p!=NULL)if (p-entry=item)q-next=p-next;delete p;count+;/刪除p結點p=q-next;/維護p的值elseq=p;p=p-next;/q,p分別向后移動return success;10- 配套講稿:
如PPT文件的首頁顯示word圖標,表示該PPT已包含配套word講稿。雙擊word圖標可打開word文檔。
- 特殊限制:
部分文檔作品中含有的國旗、國徽等圖片,僅作為作品整體效果示例展示,禁止商用。設計者僅對作品中獨創(chuàng)性部分享有著作權。
- 關 鍵 詞:
- 蘇州大學 數(shù)據(jù)結構 課程 期中考試 答案
裝配圖網(wǎng)所有資源均是用戶自行上傳分享,僅供網(wǎng)友學習交流,未經(jīng)上傳用戶書面授權,請勿作他用。
鏈接地址:http://www.szxfmmzy.com/p-10065711.html