數(shù)據(jù)結(jié)構(gòu)第3版習(xí)題答案

1、十二五普通高等教育國家級本科規(guī)劃教材第1章緒論高等學(xué)校精品資源共享課程1.1什么是數(shù)據(jù)結(jié)構(gòu)？【答】：數(shù)據(jù)結(jié)構(gòu)是指按一定的邏輯結(jié)構(gòu)組成的一批數(shù)據(jù)，使用某種存儲結(jié)構(gòu)將這批數(shù)據(jù)存儲于計算機中，并在這些數(shù)據(jù)上定義了一個運算集合。1.2數(shù)據(jù)結(jié)構(gòu)涉及哪幾個方面？【答】：數(shù)據(jù)結(jié)構(gòu)涉及三個方面的內(nèi)容，即數(shù)據(jù)的邏輯結(jié)構(gòu)、數(shù)據(jù)的存儲結(jié)構(gòu)和數(shù)據(jù)的運算集合。1.3兩個數(shù)據(jù)結(jié)構(gòu)的邏輯結(jié)構(gòu)和存儲結(jié)構(gòu)都相同，但是它們的運算集合中有一個運算的定義不一樣，它們是否可以認

2、作是同一個數(shù)據(jù)結(jié)構(gòu)？為什么？【答】：不能，運算集合是數(shù)據(jù)結(jié)構(gòu)的重要組成部分，不同的運算集合所確定的數(shù)據(jù)結(jié)構(gòu)是不一樣的，例如，棧與隊列它們的邏輯結(jié)構(gòu)與存儲結(jié)構(gòu)可以相同，但由于它們的運算集合不一樣，所以它們是兩種不同的數(shù)據(jù)結(jié)構(gòu)。1.4線性結(jié)構(gòu)的特點是什么？非線性結(jié)構(gòu)的特點是什么？【答】：線性結(jié)構(gòu)元素之間的關(guān)系是一對一的，在線性結(jié)構(gòu)中只有一個開始結(jié)點和一個終端結(jié)點，其他的每一個結(jié)點有且僅有一個前驅(qū)和一個后繼結(jié)點。而非線性結(jié)構(gòu)則沒有這個特點，元

3、素之間的關(guān)系可以是一對多的或多對多的。1.5數(shù)據(jù)結(jié)構(gòu)的存儲方式有哪幾種？【答】：數(shù)據(jù)結(jié)構(gòu)的存儲方式有順序存儲、鏈?zhǔn)酱鎯Α⑸⒘写鎯退饕鎯Φ人姆N方式。1.6算法有哪些特點？它和程序的主要區(qū)別是什么？【答】：算法具有（1）有窮性（2）確定性（3）0個或多個輸入（4）1個或多個輸出（5）可行性等特征。程序是算法的一種描述方式，通過程序可以在計算機上實現(xiàn)算法。1.7抽象數(shù)據(jù)類型的是什么？它有什么特點？【答】：抽象數(shù)據(jù)類型是數(shù)據(jù)類型的進一步抽象

4、，是大家熟知的基本數(shù)據(jù)類型的延伸和發(fā)展。抽象數(shù)據(jù)類型是與表示無關(guān)的數(shù)據(jù)類型，是一個數(shù)據(jù)模型及定義在該模型上的一組運算。對一個抽象數(shù)據(jù)類型進行定義時，必須給出它的名字及各運算的運算符名，即函數(shù)名，并且規(guī)定這些函數(shù)的參數(shù)性質(zhì)。一旦定義了一個抽象數(shù)據(jù)類型及具體實現(xiàn)，程序設(shè)計中就可以像使用基本數(shù)據(jù)類型那樣，十分方便地使用抽象數(shù)據(jù)類型。抽象數(shù)據(jù)類型的設(shè)計者根據(jù)這些描述給出操作的具體實現(xiàn)，抽象數(shù)據(jù)類型的使用者依據(jù)這些描述使用抽象數(shù)據(jù)類型。1.8算法

5、的時間復(fù)雜度指的是什么？如何表示？【答】：算法執(zhí)行時間的度量不是采用算法執(zhí)行的絕對時間來計算的，因為一個算法在不同的機器上執(zhí)行所花的時間不一樣，在不同時刻也會由于計算機資源占用情況的不同，使得算法在同一臺計算機上執(zhí)行的時間也不一樣，另外，算法執(zhí)行的時間還與輸入數(shù)據(jù)的狀態(tài)有關(guān)，所以對于算法的時間復(fù)雜性，采用算法執(zhí)行過程中其基本操作的執(zhí)行次數(shù)，稱為計算量來度量。算法中基本操作的執(zhí)行次數(shù)一般是與問題規(guī)模有關(guān)的，對于結(jié)點個數(shù)為n的數(shù)據(jù)處理問題，

6、用T(n)表示算法基本操作的執(zhí)行次數(shù)。為了評價算法的執(zhí)行效率，通常采用大寫O符號表示算法的時間復(fù)雜度，大寫O符號給出了函數(shù)f的一個上限。其它義如下：3十二五普通高等教育國家級本科規(guī)劃教材高等學(xué)校精品資源共享課程第2章線性表及其順序存儲2.1選擇題（1）表長為n的順序存儲的線性表，當(dāng)在任何位置上插入或刪除一個元素的概率相等時，插入一個元素所需移動元素的平均個數(shù)為（為（A）。E），刪除一個元素所需移動元素的平均個數(shù)A（n?1）2En2BnF

7、(n1)2Cn1G(n?2)2Dn?1（2）設(shè)棧S和隊列Q的初始狀態(tài)為空，元素e1、e2、e3、e4、e5和e6依次通過棧S，一個元素出棧后即進入隊列Q，若6個元素出隊的序列為e2、e4、e3、e6、e5和e1，則棧S的容量至少應(yīng)該為（C）。A6B4C3D2（3）設(shè)棧的輸入序列為1、2、3…n，若輸出序列的第一個元素為n，則第i個輸出的元素為（B）。A不確定Bn?i1CiDn?i（4）在一個長度為n的順序表中刪除第i個元素（1=i=n）

8、時，需向前移動（A）個元素。An?iBn?i1Cn?i?1Di（5）若長度為n的線性表采用順序存儲結(jié)構(gòu)存儲，在第i個位置上插入一個新元素的時間復(fù)雜度為（A）。AO(n)BO(1)CO(n2)DO(n3)（6）表達式a(bc)?d的后綴表達式是（B）。Aabcd?Babcd?Cabcd?D?abcd（7）隊列是一種特殊的線性表，其特殊性在于（C）。A插入和刪除在表的不同位置執(zhí)行B插入和刪除在表的兩端位置執(zhí)行C插入和刪除分別在表的兩端執(zhí)行D

9、插入和刪除都在表的某一端執(zhí)行（8）棧是一種特殊的線性表，具有（B）性質(zhì)。A先進先出B先進后出C后進后出D順序進出（9）順序循環(huán)隊列中（數(shù)組的大小為n），隊頭指示front指向隊列的第1個元素，隊尾指示rear指向隊列最后元素的后1個位置，則循環(huán)隊列中存放了n?1個元素，即循環(huán)隊列滿的條件為（B）。A(rear1)%n=front?1C(rear)%n=frontB(rear1)%n=frontDrear1=front（10）順序循環(huán)隊列