算法與數(shù)據(jù)結(jié)構(gòu)題庫及答案

一、單項(xiàng)選擇題1某算法的時(shí)間復(fù)雜度是O(n2)，表明該算法()。A問題規(guī)模是n2 B問題規(guī)模與n2成正比C執(zhí)行時(shí)間等于n2 D執(zhí)行時(shí)間與n2成正比2、關(guān)于數(shù)據(jù)結(jié)構(gòu)的描述，不正確的是()。A數(shù)據(jù)結(jié)構(gòu)相同，對應(yīng)的存儲結(jié)構(gòu)也相同。B數(shù)據(jù)結(jié)構(gòu)涉及數(shù)據(jù)的邏輯結(jié)構(gòu)、存儲結(jié)構(gòu)和施加其上的操作等三個(gè)方面。C數(shù)據(jù)結(jié)構(gòu)操作的實(shí)現(xiàn)與存儲結(jié)構(gòu)有關(guān)。D定義邏輯結(jié)構(gòu)時(shí)可不考慮存儲結(jié)構(gòu)。3、按排序策略分來，起泡排序?qū)儆?)。A插入排序B選擇排序C交換排序D歸并排序4、利用雙向鏈表作線性表的存儲結(jié)構(gòu)的優(yōu)點(diǎn)是()。A便于進(jìn)行插入和刪除的操作B提高按關(guān)系查找數(shù)據(jù)元素的速度C節(jié)省空間D便于銷毀結(jié)構(gòu)釋放空間5、一個(gè)隊(duì)列的進(jìn)隊(duì)順序?yàn)?,2,3,4，則該隊(duì)列可能的輸出序列是()。A1,2,3,4B1,3,2,4C1,4,2,3D4,3,2,16、Dijkstra算法是按()方法求出圖中從某頂點(diǎn)到其余頂點(diǎn)最短路徑的。A按長度遞減的順序求出圖的某頂點(diǎn)到其余頂點(diǎn)的最短路徑B按長度遞增的順序求出圖的某頂點(diǎn)到其余頂點(diǎn)的最短路徑C通過深度優(yōu)先遍歷求出圖中從某頂點(diǎn)到其余頂點(diǎn)的所有路徑D通過廣度優(yōu)先遍歷求出圖的某頂點(diǎn)到其余頂點(diǎn)的最短路徑7、 字符串可定義為n(n20)個(gè)字符的有限()。其中，n是字符串的長度，表明字符串中字符的個(gè)數(shù)。A集合B數(shù)列C序列D聚合8、 在二維數(shù)組A[9][10]中，每個(gè)數(shù)組元素占用3個(gè)存儲單元，從首地址SA開始按行連續(xù)存放。在這種情況下，元素A[8][5]的起始地址為()。ASA+141 BSA+144CSA+222DSA+2559、 已知廣義表為L(A(u,v,(x,y),z),C(m,(),(k,l,n),(())),((())),(e,(f,g),h)),則它的長度是()。TOC\o"1-5"\h\zA2 B3 C4 D510、 對于具有n(n>1)個(gè)頂點(diǎn)的強(qiáng)連通圖，其有向邊條數(shù)至少有 。A.n+1B.n C.n-1D.n-211、 一個(gè)遞歸算法必須包括 。A.遞歸部分B.結(jié)束條件和遞歸部分C.迭代部分D.結(jié)束條件和迭代部分12、 從邏輯上看可以把數(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)13、 若在長度為n的順序表的表尾插入一個(gè)新元素的漸進(jìn)時(shí)間復(fù)雜度為()。AO(n) BO(1) CO(n2) DO(logn)采用順序搜素方式搜索長度為n的線性表時(shí)，在等概率情況下，搜索成功時(shí)的平均搜索長度為 。A.n B.n/2 C.(n+1)/2 D.(n-1)/215、 非空的循環(huán)單鏈表first的鏈尾結(jié)點(diǎn)(由p所指向)滿足()。Ap->link==NULL; BP==NULL;

Cp->link==first;Dp==first;16、 用S表示進(jìn)棧操作，用X表示出棧操作，若元素的進(jìn)棧順序是1234，為了得到1342的出棧順序，相應(yīng)的S和X的操作序列為()。ASXSXSSXX BSSSXXSXXCSXSSXXSX DSXSSXSXX17、 含有129個(gè)葉結(jié)點(diǎn)的完全二叉樹，最少有()個(gè)結(jié)點(diǎn)。A254 B255 C257 D25818、一個(gè)有向圖G的鄰接表存儲如圖(1)所示，現(xiàn)按深度優(yōu)先搜索方式從頂點(diǎn)A出發(fā)執(zhí)行一次遍歷，所得的頂點(diǎn)序列是()。A1,2,3,4,5 B1,2,3,5,4 C1,2,4,5,3 D1,2,5,3,419、 樹最合適用來表示()。A有序數(shù)據(jù)元素 B元素之間具有分支層次關(guān)系的數(shù)據(jù)C無序數(shù)據(jù)元素 D元素之間無聯(lián)系的數(shù)據(jù)20、 一棵有124個(gè)葉結(jié)點(diǎn)的完全二叉樹最少有()個(gè)結(jié)點(diǎn)。A247 B248 C249 D25021、 圖(1)給出的一棵二叉搜索樹，對應(yīng)的二叉判定樹如圖(2)所示，它的搜索成功的平均長度是()。A21/7B28/7CA21/7B28/7C15/6D16/6圖(1圖(1)二叉搜索樹圖(2)二叉判定樹23、對5個(gè)不同的數(shù)據(jù)元素進(jìn)行直接插入排序，最大需要進(jìn)行()次比較。A8 B10 C15 D2524、將一個(gè)nXn的對稱矩陣A的下三角部分按行存放在一個(gè)一維數(shù)組B中，A[0][0]存放在B[0]中，那么第i行的對角元素A[i][i]在B中的存放位置是()。A(i+3)*i/2B(i+1)*i/2 C(2n-i+1)*i/2D(2n-i-1)*i/225、已知廣義表為L(A(u,v,(x,y),z),C(m,(),(k,l,n),(())),((())),(e,(f,g),h)),則它的深度是()。A2 B3 C426、 順序搜索法適合于存儲結(jié)構(gòu)為()的線性表。A散列存儲B順序存儲或鏈?zhǔn)酱鎯壓縮存儲D索引存儲27、 采用折半搜索方式搜索一個(gè)長度為n的有序順序表時(shí)，其平均搜索長度為()。AO(n)BO(logn)CO(n2) DO(nlogn)28、n個(gè)結(jié)點(diǎn)的線索二叉樹中，線索的數(shù)目是()。 2An-1 Bn+1 C2n D2n-129、 若數(shù)據(jù)元素序列｛11,12,13,7,8,9,23,4,5｝是采用下列排序方法之一得到的第二趟排序后的結(jié)果，則該排序方法只能是()。A插入排序B選擇排序C交換排序D歸并排序

30、為了增加內(nèi)存空間的利用率和減少溢出的可能，在兩個(gè)棧共享一片連續(xù)的存儲空間時(shí)，應(yīng)將兩個(gè)棧的棧頂分別設(shè)在這片存儲空間的兩端，當(dāng)()時(shí)才產(chǎn)生上溢。A兩個(gè)棧的棧頂同時(shí)到達(dá)?？臻g的中心點(diǎn)B其中一個(gè)棧的棧頂?shù)竭_(dá)棧空間的中心點(diǎn)C兩個(gè)棧的棧頂在?？臻g的某一位置相遇D兩個(gè)棧的棧頂相加超過了?？臻g的最大容量31、設(shè)一棵二叉樹的中序序列為badce,后序遍歷為bdeca,則該二叉樹前序遍歷的順序是()。Aadbec Bdecab Cdebac Dabcde32、 圖的簡單路徑是指()不重復(fù)的路徑。A權(quán)值B頂點(diǎn)C邊D邊與頂點(diǎn)均不重復(fù)33、 用n個(gè)權(quán)值構(gòu)造出來的Huffman樹共有()個(gè)結(jié)點(diǎn)。A2n-1 B2n C2n+1 Dn+134、在如圖(2)所示的AVL樹中插入關(guān)鍵碼48,得到了一棵新的AVL樹，在這棵新的AVL樹中,關(guān)鍵碼3734、在如圖(2)所示的AVL樹中插入關(guān)鍵碼48,得到了一棵新的AVL樹，在這棵新的AVL樹中,關(guān)鍵碼37所在結(jié)點(diǎn)的左右子女結(jié)點(diǎn)中保存的關(guān)鍵碼分別是(A13,48 B24,48）。D24,90C24,53圖(1)14小題的鄰接表15小題的AVL樹圖2)ABCDE251\3141\二、填空題1、算法效率的度量分為事后測量和事前估兩種。2、 算法是一個(gè)有窮的指令集,它為解決某一特定任務(wù)規(guī)定了一個(gè)運(yùn)算序列。它應(yīng)當(dāng)具有輸入、輸出、確定性、 有窮性 可行性等特性。3、一個(gè)抽象數(shù)據(jù)類型ADT包括. 數(shù)據(jù)操作 和對象 兩個(gè)部分。4、隊(duì)列的插入操作是在隊(duì)尾進(jìn)行，刪除操作是在 隊(duì)頭進(jìn)行。5、棧又稱為 先進(jìn)后岀 的線性表，隊(duì)列又稱為 先進(jìn)先岀線性表。6、對稱矩陣的行數(shù)和列數(shù) 相等 且以主對角線為對稱軸，因此只要存儲它的上三角部分或者下三角部分即可。7、 利用三元組表存放稀疏矩陣中的非零元素,則在三元組表中每個(gè)三元組中應(yīng)記錄相應(yīng)非TOC\o"1-5"\h\z零元的行號、列號和非零元素的—值 。8、廣義表A((a,b,c),(d,e,f))的表頭是 (a,b,c) 。9、廣義表A((a,b,c),(d,e,f))的表尾是 ((d,e,f))10、 在一棵有n個(gè)結(jié)點(diǎn)的二叉樹中，若度為2的結(jié)點(diǎn)數(shù)為n2,度為1的結(jié)點(diǎn)數(shù)為n1,度為0的結(jié)點(diǎn)數(shù)為n0,則樹的最小高度為—^先“」+1 ，其葉節(jié)點(diǎn)數(shù)為—n2+1 。11、 在一棵有n個(gè)結(jié)點(diǎn)的二叉樹中，若度為2的結(jié)點(diǎn)數(shù)為n2,度為1的結(jié)點(diǎn)數(shù)為n1,度為0的結(jié)點(diǎn)數(shù)為n0,則樹的最大高度為 n ，其葉節(jié)點(diǎn)數(shù)為 1 。12、 已知有序順序表(13,18,24,35,47,50,62,83,90,115,134)，當(dāng)用折半搜索法搜索值18TOC\o"1-5"\h\z的元素時(shí)，搜索成功的數(shù)據(jù)比較次數(shù)為4 。13、采用順序搜索方式搜索長度為n的線性表時(shí)，平均搜索長度為 （n+l）/2 。14、 對于一個(gè)具有n個(gè)頂點(diǎn)和e條邊的無向圖進(jìn)行遍歷，若采用鄰接矩陣表示，則時(shí)間復(fù)雜度為 0（e），若采用鄰接表表示，則時(shí)間復(fù)雜度為O（n+e）。15、 對于一個(gè)具有n個(gè)頂點(diǎn)和e條邊的無向圖，若采用鄰接矩陣表示，則該矩陣大小是—n2 ,矩陣中的非零元個(gè)數(shù)為 2e。16、 每次從無序表中挑選一個(gè)最小或者最大兀素，把它交換到有序表的一端，此種排序方法叫彳 排序。17、 對n個(gè)元素的序列進(jìn)行排序時(shí)，如果待排序元素序列的初始排列完全逆序，則起泡排序過程中需要進(jìn)行n（n-1）/2 次元素值的比較， n（n-1）/2次元素值的交換。18、 每次從無序表中取出一個(gè)元素，把它插入到有序表中的適當(dāng)位置，此種排序方法叫做插入插入排序。19、 對n個(gè)元素的序列進(jìn)行排序時(shí)，如果待排序元素序列的初始排列已經(jīng)全部有序，則起泡排序過程中需要進(jìn)行n-1 次元素值的比較， 0次元素值的交換。三、判斷題1、 數(shù)據(jù)的邏輯結(jié)構(gòu)是指各數(shù)據(jù)元素之間的邏輯關(guān)系，是用戶按照使用需要建立的。錯(cuò)2、 數(shù)據(jù)結(jié)構(gòu)是指相互之間存在一種或多種關(guān)系的數(shù)據(jù)元素的全體。對3、 根據(jù)隊(duì)列的先進(jìn)先出的特性，最后進(jìn)隊(duì)列的元素最后出隊(duì)列。對4、 在順序棧中元素是按照其值的大小有序存放的。錯(cuò)5、 棧底元素是不能刪除的。錯(cuò)6、 在隊(duì)列中，n個(gè)元素的進(jìn)隊(duì)列順序和出隊(duì)列順序總是一致的。對7、 數(shù)組是一種復(fù)雜的數(shù)據(jù)結(jié)構(gòu)，數(shù)組元素之間的關(guān)系既不是線性的，也不是樹形的。錯(cuò)8、 廣義表是線性表的推廣，但它不是一種線性結(jié)構(gòu)。對9、 二維數(shù)組可以視為數(shù)組元素為一維數(shù)組的一維數(shù)組。因此，二維數(shù)組是線性結(jié)構(gòu)。錯(cuò)10、 有n個(gè)整數(shù)存放在一維數(shù)組A[n]中，在進(jìn)行順序搜索時(shí)，無論這n個(gè)整數(shù)的排列是否有序，其平均搜索長度都相同。錯(cuò)11、 鄰接矩陣適用于稠密圖（邊數(shù)接近于頂點(diǎn)數(shù)的平方），鄰接表適用于稀疏圖（邊數(shù)遠(yuǎn)小于頂點(diǎn)數(shù)的平方）。對12、 對n個(gè)頂點(diǎn)的連通圖G來說，如果其中的某個(gè)子圖有n個(gè)頂點(diǎn)，n-1條邊，則該子圖一定是G的生成樹。錯(cuò)13、 希爾排序、簡單選擇排序都是不穩(wěn)定的排序方法。錯(cuò)14、 如果一個(gè)二叉樹的結(jié)點(diǎn)，或者兩棵子樹都空，或者兩棵子樹都非空，則此二叉樹稱為完全二叉樹。錯(cuò)15、 在二叉搜索樹中，任一結(jié)點(diǎn)所具有的關(guān)鍵碼值都大于它的左子女（如果存在）的關(guān)鍵碼值，同時(shí)小于其右子女（如果存在）的關(guān)鍵碼值。對16、 具有n個(gè)頂點(diǎn)的無向圖最多有n（n-1）條邊，最少有n-1條邊。錯(cuò)17、 最小生成樹是指邊數(shù)最少的生成樹。錯(cuò)四、簡答與計(jì)算題1、 什么是數(shù)據(jù)結(jié)構(gòu)？有關(guān)數(shù)據(jù)結(jié)構(gòu)的討論涉及哪三個(gè)方面？2、 什么是算法，算法的5個(gè)特性是什么？3、 已知如圖（3）所示的有向圖，請利用Kruskal算法求出最小生成樹。

圖（3）4、如圖（3）所示的有向圖，請給出該圖的鄰接矩陣和鄰接表。圖（3）5、已知一棵二叉樹的前序遍歷結(jié)果是ABECDFGHIJ,中序遍歷結(jié)果是EBCDAFHIGJ,試畫出這6、給定權(quán)值集合｛15,03,14,02,06,09,16,17｝，構(gòu)造相應(yīng)的huffman樹，并計(jì)算它的帶權(quán)外部路徑長度。7、設(shè)串s為“abcabaa”，試計(jì)算其next數(shù)組的值。j0123456rabcabaanext[j]-10001218、利用廣義表的head和tail操作寫出函數(shù)表達(dá)式，把以下各題中單元素banana從廣義表中分離出來。L1(apple,pear,banana,orange)L2((apple,pear),(banana,orange))L3(((apple),(pear),(banana),(orange)))L4((((apple),pear),banana),orange)L5(apple,(pear,(banana),orange))Head(Tail(Tail(Ll)))(l分)Head(Head(Tail(L2)))(1分)Head(Head(Tail(Tail(Head(L3)))))(1分)Head(Tail(Head(L4)))(1分)Head(Head(Tail(Head(Tail(L6)))))(1分)9、 設(shè)有序順序表中的元素依次為17,154,170,275,503,509,512,553,612,677,765,897,908。試畫出對其進(jìn)行折半搜索時(shí)的判定樹，并計(jì)算搜索成功的平均搜索長度和搜索不成功的平均搜索長度。搜索成功的平均搜索長度為45/14（1分）搜索不成功的平均搜索長度為59/14（1分）10、已知一個(gè)待排序的關(guān)鍵字序列為｛56，36，22，86，72，10，28，48｝，請寫出快速排序每一趟排序的結(jié)果（寫出過程）。（5分）第1趟排序結(jié)果：48,36,22,28,10,56,72,86第2趟排序結(jié)果：10,36,22,28,48,56,72,86第3趟排序結(jié)果：10,36,22,28,48,56,72,86第4趟排序結(jié)果：10,22,28,36,48,56,72,86第5趟排序結(jié)果：10,22,28,36,48,56,72,8611、已知一個(gè)有序表(15,26,34,39,45,56,58,63,74,76,83,94)順序存儲于一維數(shù)組a[12]中，根據(jù)折半搜索過程填寫成功搜索下表中所給元素34,56,58,63,94,50時(shí)的比較次數(shù)。元素值345658639450比較次數(shù)21344412、已知一