數(shù)據(jù)結(jié)構(gòu)(殷人昆)練習(xí)題答案附在后邊

1、11n21)n(nin1i?????第一章第一章緒論緒論11什么是數(shù)據(jù)它與信息是什么關(guān)系12什么是數(shù)據(jù)結(jié)構(gòu)有關(guān)數(shù)據(jù)結(jié)構(gòu)的討論涉及哪三個(gè)方面13數(shù)據(jù)的邏輯結(jié)構(gòu)分為線性結(jié)構(gòu)和非線性結(jié)構(gòu)兩大類。線性結(jié)構(gòu)包括數(shù)組、鏈表、棧、隊(duì)列、優(yōu)先級(jí)隊(duì)列等非線性結(jié)構(gòu)包括樹、圖等、這兩類結(jié)構(gòu)各自的特點(diǎn)是什么？14什么是抽象數(shù)據(jù)類型？試用C的類聲明定義“復(fù)數(shù)”的抽象數(shù)據(jù)類型。要求(1)在復(fù)數(shù)內(nèi)部用浮點(diǎn)數(shù)定義它的實(shí)部和虛部。(2)實(shí)現(xiàn)3個(gè)構(gòu)造函數(shù)：缺省的構(gòu)造函數(shù)沒(méi)

2、有參數(shù)；第二個(gè)構(gòu)造函數(shù)將雙精度浮點(diǎn)數(shù)賦給復(fù)數(shù)的實(shí)部，虛部置為0；第三個(gè)構(gòu)造函數(shù)將兩個(gè)雙精度浮點(diǎn)數(shù)分別賦給復(fù)數(shù)的實(shí)部和虛部。(3)定義獲取和修改復(fù)數(shù)的實(shí)部和虛部，以及、、、等運(yùn)算的成員函數(shù)。(4)定義重載的流函數(shù)來(lái)輸出一個(gè)復(fù)數(shù)。15用歸納法證明：(1)(2)1n61)1)(2nn(nin1i2??????(3)0n1x1x1xx1nn0ii????????16什么是算法算法的5個(gè)特性是什么試根據(jù)這些特性解釋算法與程序的區(qū)別。17設(shè)n為正整

3、數(shù)分析下列各程序段中加下劃線的語(yǔ)句的程序步數(shù)。(1)f(inti=1iarraySize或者對(duì)于某一個(gè)k(0?k?n)，使得k!2kmaxInt時(shí)，應(yīng)按出錯(cuò)處理。可有如下三種不同的出錯(cuò)處理方式：(1)用cerrclassSeqListprivate:Typedata順序表的存放數(shù)組intMaxSize順序表的最大可容納項(xiàng)數(shù)intlast順序表當(dāng)前已存表項(xiàng)的最后位置intcurrent順序表的當(dāng)前指針（最近處理的表項(xiàng)）public:Seq

4、List(intMaxSize)構(gòu)造函數(shù)~SeqList()[]data析構(gòu)函數(shù)intLength()constreturnlast1計(jì)算表長(zhǎng)度intFind(Type定位函數(shù):找x在表中位置，置為當(dāng)前表項(xiàng)intIsIn(Type判斷x是否在表中，不置為當(dāng)前表項(xiàng)TypeGetData()returncurrent==1？NULL:data[current]取當(dāng)前表項(xiàng)的值int(Type插入x在表中當(dāng)前表項(xiàng)之后，置為當(dāng)前表項(xiàng)intAppe

5、nd(Type追加x到表尾，置為當(dāng)前表項(xiàng)TypeRemove(Type刪除x，置下一表項(xiàng)為當(dāng)前表項(xiàng)TypeFirst()取表中第一個(gè)表項(xiàng)的值，置為當(dāng)前表項(xiàng)TypeNext()returncurrent0取當(dāng)前表項(xiàng)的前驅(qū)表項(xiàng)的值，置為當(dāng)前表項(xiàng)intIsEmpty()returnlast==1判斷順序表空否空則返回1否則返回0intIsFull()returnlast==MaxSize1判斷順序表滿否滿則返回1否則返回021設(shè)n個(gè)人圍坐在一

6、個(gè)圓桌周圍，現(xiàn)在從第s個(gè)人開始報(bào)數(shù)，數(shù)到第m個(gè)人，讓他出局；然后從出局的下一個(gè)人重新開始報(bào)數(shù)，數(shù)到第m個(gè)人，再讓他出局，……，如此反復(fù)直到所有的人全部出局為止。下面要解決的Josephus問(wèn)題是：對(duì)于任意給定的ns和m，求出這n個(gè)人的出局序列。請(qǐng)以n=9s=1m=5為例，人工模擬Josephus的求解過(guò)程以求得問(wèn)題的解。22試編寫一個(gè)求解Josephus問(wèn)題的函數(shù)。用整數(shù)序列123……n表示順序圍坐在圓桌周圍的人，并采用數(shù)組表示作為求解

7、過(guò)程中使用的數(shù)據(jù)結(jié)構(gòu)。然后使用n=9s=1m=5，以及n=9s=1m=0，或者n=9s=1m=10作為輸入數(shù)據(jù)，檢查你的程序的正確性和健壯性。最后分析所完成算法的時(shí)間復(fù)雜度。23設(shè)有一個(gè)線性表(e0e1…en2en1)存放在一個(gè)一維數(shù)組A[arraySize]中的前n個(gè)數(shù)組元素位置。請(qǐng)編寫一個(gè)函數(shù)將這個(gè)線性表原地逆置，即將數(shù)組的前n個(gè)原址內(nèi)容置換為(en1en2…e1e0)。24假定數(shù)組A[arraySize]中有多個(gè)零元素試寫出一個(gè)函