1、算法與編程題舉例軟件方法學部分習題1（ ）產生軟件危機的原因主要與兩個方面的問題有關：A、軟件在計算機中很難識別，存在磁盤中也看不到。B、軟件設計對人的智商要求很高，也要求很高的資金投入。C、軟件產品本身的特點與其它工業產品不一樣，而且在軟件的開發和維護過程中用的方法不正確。D、軟件很難理解，硬件也很復雜。 2（ ） 可行性研究主要從以下幾個方面進行研究：A、技術可行性，經濟可行性，操作可行性。B、技術可行性，經濟可行性，系統可行性。C、經濟可行性，系統可行性，操作可行性。D、經濟可行性，系統可行性，時間可行性。 3（ ）軟件開發瀑布模型中的軟件定義時期各個階段依次是：A、可行性研究，問題定義

2、，需求分析。B、問題定義，可行性研究，需求分析。C、可行性研究，需求分析，問題定義。D、以上順序都不對。 4結構程序設計的基本思想是（ ）。5. 軟件生存周期可以分為幾個大的階段，每個階段又可以進一步細分成哪些小的階段？6什么是軟件？數據結構緒論部分習題一、選擇題1. 算法的計算量的大小稱為計算的（ ）。A效率 B. 復雜性 C. 現實性 D. 難度2. 算法的時間復雜度取決于（ ）A問題的規模 B. 待處理數據的初態 C. A和B3.計算機算法指的是（1），它必須具備（2） 這三個特性。(1) A計算方法 B. 排序方法 C. 解決問題的步驟序列 D. 調度方法(2) A可執行性、可移植性、

3、可擴充性 B. 可執行性、確定性、有窮性C. 確定性、有窮性、穩定性 D. 易讀性、穩定性、安全性 4一個算法應該是（ ）。 A程序 B問題求解步驟的描述 C要滿足五個基本特性 DB和C. 5從邏輯上可以把數據結構分為（ ）兩大類。A動態結構、靜態結構 B順序結構、鏈式結構 C線性結構、非線性結構 D初等結構、構造型結構二、判斷題1. 數據元素是數據的最小單位。( )2. 記錄是數據處理的最小單位。 ( ) 3. 數據的邏輯結構是指數據的各數據項之間的邏輯關系；( )4算法的優劣與算法描述語言無關，但與所用計算機有關。( )5健壯的算法不會因非法的輸入數據而出現莫名其妙的狀態。( )6算法可以

4、用不同的語言描述，如果用C 語言或PASCAL語言等高級語言來描述，則算法實際上就是程序了。( )7數據的物理結構是指數據在計算機內的實際存儲形式。( )8. 數據結構的抽象操作的定義與具體實現有關。( )9. 在順序存儲結構中，有時也存儲數據結構中元素之間的關系。( )10. 順序存儲方式的優點是存儲密度大，且插入、刪除運算效率高。( )11. 數據結構的基本操作的設置的最重要的準則是，實現應用程序與存儲結構的獨立。( )12. 數據的邏輯結構說明數據元素之間的順序關系,它依賴于計算機的儲存結構. ( )三 簡答題1. 數據元素之間的關系在計算機中有幾種表示方法？各有什么特點？（1）順序存儲

5、方式。數據元素順序存放，每個存儲結點只含一個元素。存儲位置反映數據元素間的邏輯關系。存儲密度大，但有些操作（如插入、刪除）效率較差。（2）鏈式存儲方式。每個存儲結點除包含數據元素信息外還包含一組（至少一個）指針。指針反映數據元素間的邏輯關系。這種方式不要求存儲空間連續，便于動態操作（如插入、刪除等），但存儲空間開銷大（用于指針），另外不能折半查找等。（3）索引存儲方式。除數據元素存儲在一地址連續的內存空間外，尚需建立一個索引表，索引表中索引指示存儲結點的存儲位置（下標）或存儲區間端點（下標），兼有靜態和動態特性。（4）散列存儲方式。通過散列函數和解決沖突的方法，將關鍵字散列在連續的有限的地址空

6、間內，并將散列函數的值解釋成關鍵字所在元素的存儲地址，這種存儲方式稱為散列存儲。其特點是存取速度快，只能按關鍵字隨機存取，不能順序存取，也不能折半存取。線性表部分習題一 選擇題1下述哪一條是順序存儲結構的優點？（ ）A存儲密度大 B插入運算方便 C刪除運算方便 D可方便地用于各種邏輯結構的存儲表示2下面關于線性表的敘述中，錯誤的是哪一個？（ ）A線性表采用順序存儲，必須占用一片連續的存儲單元。B線性表采用順序存儲，便于進行插入和刪除操作。C線性表采用鏈接存儲，不必占用一片連續的存儲單元。D線性表采用鏈接存儲，便于插入和刪除操作。3線性表是具有n個（ ）的有限序列（n>0）。 A表元素 B

7、字符 C數據元素 D數據項 E信息項4若某線性表最常用的操作是存取任一指定序號的元素和在最后進行插入和刪除運算，則利用（ ）存儲方式最節省時間。A順序表 B雙鏈表 C帶頭結點的雙循環鏈表 D單循環鏈表5某線性表中最常用的操作是在最后一個元素之后插入一個元素和刪除第一個元素，則采用（ ）存儲方式最節省運算時間。A單鏈表 B僅有頭指針的單循環鏈表 C雙鏈表 D僅有尾指針的單循環鏈表6. 若長度為n的線性表采用順序存儲結構，在其第i個位置插入一個新元素的算法的時間復雜度為（ ）(1<=i<=n+1)。A. O(0) B. O(1) C. O(n) D. O(n2) 7線性表（ a1,a2

8、,an）以鏈接方式存儲時，訪問第i位置元素的時間復雜性為（ ）AO（i） BO（1） CO（n） DO（i-1）8在單鏈表指針為p的結點之后插入指針為s的結點，正確的操作是：（ ）。Ap->next=s;s->next=p->next; B s->next=p->next;p->next=s;Cp->next=s;p->next=s->next; D p->next=s->next;p->next=s;9對于一個頭指針為head的帶頭結點的單鏈表，判定該表為空表的條件是（ ）Ahead=NULL Bheadnext=NUL

9、L Cheadnext=head Dhead!=NULL二、判斷1. 鏈表中的頭結點僅起到標識的作用。(×)2. 順序存儲結構的主要缺點是不利于插入或刪除操作。()3順序存儲方式插入和刪除時效率太低，因此它不如鏈式存儲方式好。(×)4對任何數據結構鏈式存儲結構一定優于順序存儲結構。(×)5. 順序存儲方式只能用于存儲線性結構。(×)6線性表的特點是每個元素都有一個前驅和一個后繼。(×)7. 取線性表的第i個元素的時間同i的大小有關. (×)8. 順序存儲方式的優點是存儲密度大，且插入、刪除運算效率高。(×)9. 鏈表是采用鏈

10、式存儲結構的線性表,進行插入、刪除操作時，在鏈表中比在順序存儲結構中效率高。 ()三、填空1當線性表的元素總數基本穩定，且很少進行插入和刪除操作，但要求以最快的速度存取線性表中的元素時，應采用_順序_存儲結構。2線性表L=（a1,a2,an）用數組表示，假定刪除表中任一元素的概率相同，則刪除一個元素平均需要移動元素的個數是_（n-1）/2 _。3在一個長度為n的順序表中第i個元素（1<=i<=n）之前插入一個元素時，需向后移動_ n-i+1_個元素。4在單鏈表中設置頭結點的作用是：主要是使插入和刪除等操作統一，在第一個元素之前插入元素和刪除第一個結點不必另作判斷；另外，不論鏈表是否

11、為空，鏈表指針不變。5根據線性表的鏈式存儲結構中每一個結點包含的指針個數，將線性鏈表分成_單鏈表_和多重鏈表；而又根據指針的連接方式，鏈表又可分成（動態）鏈表和靜態鏈表。6鏈接存儲的特點是利用_指針_來表示數據元素之間的邏輯關系。7.順序存儲結構是通過_物理上相鄰表示元素之間的關系的;鏈式存儲結構是通過_指針_表示元素之間的關系的。8. 已知指針p指向單鏈表L中的某結點，則刪除其后繼結點的語句是：u=p->next; p->next=u->next; free(u);9. 在單鏈表L中，指針p所指結點有后繼結點的條件是：p->next!=null10. 以下程序的功能是

12、實現帶附加頭結點的單鏈表數據結點逆序連接，請填空完善之。void reverse(SqList h) /* h為附加頭結點指針；類型pointer */ SqList p,q; p=h->next; h->next=NULL;while(1)_ p!=null _) q=p; p=p->next; q->next=h->next; h->next=(2)_q_; 棧和隊列部分習題一 選擇題1. 對于棧操作數據的原則是（ ）。A. 先進先出 B. 后進先出 C. 后進后出 D. 不分順序2. 在作進棧運算時,應先判別棧是否( ),在作退棧運算時應先判別棧是否(

13、 )。當棧中元素為n個,作進棧運算時發生上溢,則說明該棧的最大容量為( )。為了增加內存空間的利用率和減少溢出的可能性,由兩個棧共享一片連續的內存空間時,應將兩棧的 ( )分別設在這片內存空間的兩端,這樣,當( )時，才產生上溢。 , : A. 空 B. 滿 C. 上溢 D. 下溢 : A. n-1 B. n C. n+1 D. n/2 : A. 長度 B. 深度 C. 棧頂 D. 棧底 : A. 兩個棧的棧頂同時到達棧空間的中心點.B. 其中一個棧的棧頂到達棧空間的中心點. C. 兩個棧的棧頂在棧空間的某一位置相遇. D. 兩個棧均不空,且一個棧的棧頂到達另一個棧的棧底.3. 一個棧的輸入序

14、列為123n，若輸出序列的第一個元素是n，輸出第i（1<=i<=n）個元素是（ ）。A. 不確定 B. n-i+1 C. i D. n-i4. 某堆棧的輸入序列為a, b，c ，d,下面的四個序列中，不可能是它的輸出序列的是（ ）。 A. a，c，b，d B. b, c，d，a C. c, d，b, a D. d, c，a，b5. 依次讀入數據元素序列a，b，c，d，e，f，g進棧,每進一個元素，機器可要求下一個元素進棧或彈棧，如此進行，則棧空時彈出的元素構成的序列是以下哪些序列？ Ad ，e，c，f，b，g，a B. f，e，g，d，a，c，bC. e，f，d，g，b，c，a D

15、. c，d，b，e，f，a，g6. 循環隊列A0.m-1存放其元素值，用front和rear分別表示隊頭和隊尾，則當前隊列中的元素數是( )。A. (rear-front+m)%m B. rear-front+1 C. rear-front-1 D. rear-front7. 循環隊列存儲在數組A0.m中，則入隊時的操作為（ ）。A. rear=rear+1 B. rear=(rear+1) mod (m-1) C. rear=(rear+1) mod m D. rear=(rear+1)mod(m+1) 8. 若用一個大小為6的數組來實現循環隊列，且當前rear和front的值分別為0和3，

16、當從隊列中刪除一個元素，再加入兩個元素后，rear和front的值分別為多少？( ) A. 1和 5 B. 2和4 C. 4和2 D. 5和1 9. 最大容量為n的循環隊列，隊尾指針是rear，隊頭是front，則隊空的條件是 （ ）。 A. (rear+1) MOD n=front B. rear=front Crear+1=front D. (rear-l) MOD n=front10. 棧和隊列的共同點是（ ）。A. 都是先進先出 B. 都是先進后出 C. 只允許在端點處插入和刪除元素 D. 沒有共同點11. 設棧S和隊列Q的初始狀態為空，元素e1，e2，e3，e4,e5和e6依次通過棧

17、S，一個元素出棧后即進隊列Q，若6個元素出隊的序列是e2，e4，e3,e6,e5,e1則棧S的容量至少應該是( )。A 6 B. 4 C. 3 D. 2二 判斷題1. 消除遞歸不一定需要使用棧，此說法（）2. 棧是實現過程和函數等子程序所必需的結構。（）3. 兩個棧共用靜態存儲空間，對頭使用也存在空間溢出問題。（）4兩個棧共享一片連續內存空間時，為提高內存利用率，減少溢出機會，應把兩個棧的棧底分別設在這片內存空間的兩端。（）5. 即使對不含相同元素的同一輸入序列進行兩組不同的合法的入棧和出棧組合操作，所得的輸出序列也一定相同。（×）6. 棧與隊列是一種特殊操作的線性表。（）7. 若輸

18、入序列為1,2,3,4,5,6,則通過一個棧可以輸出序列3,2,5,6,4,1. （）8. 棧和隊列都是限制存取點的線性結構。（）9若輸入序列為1，2，3，4，5，6，則通過一個棧可以輸出序列1，5，4，6，2，3。（×）10.任何一個遞歸過程都可以轉換成非遞歸過程。（）填空題15. 隊列的特點是_先進先出。16隊列是限制插入只能在表的一端，而刪除在表的另一端進行的線性表，其特點是_先進先出。17. 已知鏈隊列的頭尾指針分別是f和r，則將值x入隊的操作序列是_ s=(LinkedList)malloc(sizeof(LNode)； s->data=x;s->next=r-

19、>next；r->next=s；r=s；。18區分循環隊列的滿與空，只有兩種方法，它們是犧牲一個存儲單元和設標記。19. 循環隊列的引入，目的是為了克服_假溢出時大量移動數據元素。數組部分習題1.設有一個10階的對稱矩陣A，采用壓縮存儲方式，以行序為主存儲，a11為第一元素，其存儲地址為1，每個元素占一個地址空間，則a85的地址為（ ）。A. 13 B. 33 C. 18 D. 402. 設有數組Ai,j，數組的每個元素長度為3字節，i的值為1 到8 ，j的值為1 到10，數組從內存首地址BA開始順序存放，當用以列為主存放時，元素A5，8的存儲首地址為( )。A. BA+141 B

20、. BA+180 C. BA+222 D. BA+2253. 對稀疏矩陣進行壓縮存儲目的是（ ）。A便于進行矩陣運算 B便于輸入和輸出 C節省存儲空間 D降低運算的時間復雜度4. 判斷：數組可看成線性結構的一種推廣，因此與線性表一樣，可以對它進行插入，刪除等操作。（×）5. 設有二維數組A0.9,0.19,其每個元素占兩個字節，第一個元素的存儲地址為100，若按列優先順序存儲，則元素A6,6存儲地址為_232_。6、 二維數組A的每個元素是由6個字符組成的串，其行下標i=0,1,8,列下標j=1,2,10。若A按行先存儲，元素A8,5的起始地址與當A按列先存儲時的元素（ ）的起始地址

21、相同。設每個字符占一個字節。A. A8,5 B. A3,10 C. A5,8 D. A0,9樹部分1、樹的定義及相關術語，二叉樹和完全二叉樹的性質（填空和選擇）2、試分別畫出具有3個結點的樹和具有3個結點的二叉樹的所有不同形態。3、若一棵樹具有n1個度為1的結點，n2個度為2的結點，,nm個度為m的結點，則這棵樹中的葉子結點有多少個。4、掌握樹、森林和二叉樹的轉換方法。5、從概念上講，樹，和二叉樹是兩種不同的數據結構，將樹轉化為二叉樹的基本目的是什么，并指出樹和二叉樹的主要區別。答：樹的孩子兄弟鏈表表示法和二叉樹二叉鏈表表示法，本質是一樣的，只是解釋不同，也就是說樹（樹是森林的特例，即森林中只

22、有一棵樹的特殊情況）可用二叉樹唯一表示，并可使用二叉樹的一些算法去解決樹中的問題。樹和二叉樹的區別有二：一是二叉樹的度至多為2，樹無此限制；二是二叉樹有左右子樹之分，即使在只有一個分枝的情況下， 也必須指出是左子樹還是右子樹，樹無此限制。6、二叉樹的先序、中序和后序遍歷序列。7、哈夫曼樹的生成及哈夫曼編碼。圖部分1、圖的定義及相關術語（填空和選擇）2、對一個圖進行遍歷可以得到不同的遍歷序列，導致得到的遍歷序列不唯一的因素有哪些？開始遍歷的頂點不同；存儲結構不同；在鄰接表情況下鄰接點的順序不同。2、給出一個有向圖或者無向圖的鄰接矩陣或者鄰接鏈表，能畫出該圖，并指出某個結點的度，以及寫出其廣度和深

23、度優先搜索的遍歷序列。查找部分1、 查找的基本概念2、線性表的查找（順序查找、二分（折半）查找、分塊查找）的適用范圍及查找算法，尤其是順序和折半查找的算法必須理解。另外了解這些算法的時間復雜度。3、順序查找算法（監視哨的使用）和折半查找算法。可能會以程序填空的形式考察大家。4、哈希查找關于哈希表生成的例子：對關鍵字序列（62，30，18，45，21，78，66，32，54，48），現用除留余數法作為哈希函數，請分別利用線性探測再散列和鏈地址法處理沖突，將其散列到地址空間為0-10的哈希表中，并計算在等概率條件下查找成功的平均查找長度。答案：（1）哈希函數為：H（k）=k%p取不大于哈希表空間單元數11的最大質數作為p的值所以： H（k）=k%11 （2）按照哈希函數計算出的各關鍵字與地址的關系如下：關鍵字62301845217866325448地址7871101010104一、線性探測再散列方法（3）線性探測再散列公式： （i=1，2，3，）其中= 1，2，3， ，m-1按照線性探測再散列的方法處理沖突生成的哈希表如下：地址012345678910關鍵字66457832544862301821（4）其平均