算法與數(shù)據(jù)結(jié)構(gòu)習(xí)題

1、算法與數(shù)據(jù)結(jié)構(gòu)習(xí)題1一、單項選擇題1. 數(shù)據(jù)結(jié)構(gòu)從邏輯上分為（ ）。A動態(tài)結(jié)構(gòu)和靜態(tài)結(jié)構(gòu) B內(nèi)部結(jié)構(gòu)和外部結(jié)構(gòu)C緊湊結(jié)構(gòu)和非緊湊結(jié)構(gòu) D線性結(jié)構(gòu)和非線性結(jié)構(gòu)2. 棧和隊列的共同點是（ ）。A都是先進后出 B都是后進先出C只允許在端點處插入和刪除元素 D沒有共同點3若按從左到右的順序讀入已知序列a、b、c、d、e、f、g中的元素，然后結(jié)合棧的操作，能得到下列序列中的哪些序列？（ ）Adecfbga Bfegdacb Cefdgbca Ddcbefag4. 在一個單鏈表中，若q結(jié)點是p結(jié)點的前驅(qū)結(jié)點，若在q與p之間插入結(jié)點s，則執(zhí)行（ ）。Aslink=plink；plink =s； Bplink

2、 =s；slink=q；Cplink=slink；slink =p； Dqlink =s；slink=p；5算法的計算量的大小稱為計算的（ ）。A效率 B. 復(fù)雜性 C. 現(xiàn)實性 D. 難度6. 一個算法應(yīng)該是（ ）。A程序 B問題求解步驟的描述 C要滿足五個基本特性 DA和C7. 從邏輯上可以把數(shù)據(jù)結(jié)構(gòu)分為（ ）兩大類。A動態(tài)結(jié)構(gòu)、靜態(tài)結(jié)構(gòu) B順序結(jié)構(gòu)、鏈?zhǔn)浇Y(jié)構(gòu) C線性結(jié)構(gòu)、非線性結(jié)構(gòu) D初等結(jié)構(gòu)、構(gòu)造型結(jié)構(gòu)8. 以下數(shù)據(jù)結(jié)構(gòu)中，哪一個是線性結(jié)構(gòu)？（ ）A廣義表 B. 二叉樹 C. 稀疏矩陣 D. 串二、多項選擇題1. 以下說法正確的是（ ）。A. 二叉樹的特點是每個結(jié)點至多只有兩棵子樹B.

3、 二叉樹的子樹無左右之分C. 二叉樹只能進行鏈?zhǔn)酱鎯. 樹的結(jié)點包含一個數(shù)據(jù)元素及若干指向其子樹的分支2在數(shù)組上能做的操作有（ ）。 A. 插入B. 刪除C. 取值操作D. 賦值操作3. 圖的應(yīng)用算法有（ ）。 A. 克魯斯卡爾算法 B. 哈弗曼算法C. 迪杰斯特拉算法 D. 拓?fù)渑判蛩惴?. 計算機算法必須具備（ ）等特性。A. 可行性、確定性 B. 可行性、可移植性C. 輸入、輸出 D. 有窮性E. 易讀性 F. 穩(wěn)定性三、填空題1. 一個算法的效率可分為 效率和 效率。2. 向一個長度為n的向量的第i個元素(1in+1)之前插入一個元素時，需向后

4、移動 個元素。3. 棧只能在 插入和刪除元素；對于隊列只能在 插入和 刪除元素。4. 一棵具有257個結(jié)點的完全二叉樹，它的深度為 。四、判斷題1. 鏈表的每個結(jié)點中都恰好包含一個指針。（ ）2. 線性表的每個結(jié)點只能是一個簡單類型，而鏈表的每個結(jié)點可以是一個復(fù)雜類型。（ ）3. 數(shù)和二叉樹都是分支結(jié)構(gòu)。（ ）4. 優(yōu)先隊列是一種給每個元素增加了優(yōu)先級的隊列，它具有隊列的基本特性。（ ）5. 數(shù)據(jù)元素是數(shù)據(jù)的最小單位。（ ）6. 記錄是數(shù)據(jù)處理的最小單位。（ ） 7. 數(shù)據(jù)的邏輯結(jié)構(gòu)是指數(shù)據(jù)的各數(shù)據(jù)項之間的邏輯關(guān)系。（ ）五、簡答題1. 能否講二叉樹是一種特殊的樹？為什么？ 2. 在C語言中字

5、符串可以用字符指針來表示。字符串的長度隱含在字符指針?biāo)傅淖址麛?shù)組中，通過特殊的字符0判定。寫一個遞歸算法，以字符指針為參數(shù)，在屏幕上打印出它反轉(zhuǎn)后得到的字符串。3. 算法與程序有什么區(qū)別？ 4. 試寫出如圖所示的二叉樹分別按先序、中序、后序遍歷時得到的結(jié)點序列。5. 什么是網(wǎng)絡(luò)的最小生成樹？6. 已知兩個串為S1=“bc cad cabcadf”, S2=”abc”,試求兩個串的長度，并判斷S2串是否是S1串的子串；如果是，請指出S2在S1中的位置。算法與數(shù)據(jù)結(jié)構(gòu)習(xí)題1答案 一、單項選擇題題號12345678答案DCABBBCD二、多項選擇題題號1234答案ADCDACDACD三、填空題題號

6、答案1時間；空間2n-i+13棧頂；隊尾；隊首49四、判斷題題號1234567答案××××××五、簡答題1. 答：不能。二叉樹并不是樹的特例。樹和二叉樹的定義及操作都是不同的，周游算法也有很大的區(qū)別。二叉樹可以與一般樹林建立對應(yīng)，它的提出可以為研究樹提供一種簡單而統(tǒng)一的范型。2. 答：void printRevString(char *s) If(s0= =0)return; /*空串*/ If(s1= =0)putchar(s0); /*只有一個字符，直接打印*/ Else PrintRevString（s+1）；Putchar（s0）;3.答：算法與程序的關(guān)系十分密切，但并不等同。一般來說，一個程序并不需要滿足算法的有窮性等條件，例如操作系統(tǒng)的程序，只要整個系統(tǒng)不遭到破壞，操作系統(tǒng)程序就永不結(jié)束。另外，程序是用機器可執(zhí)行的語言書寫的，而算法通常并沒有這種限制。4. 答：DLR： A B D F J G K C E H I L M LDR： B F J D G K A C H E L I M LRD： J F K G D B H L M I E C A5. 答：因