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

1、文檔供參考，可復(fù)制、編制，期待您的好評(píng)與關(guān)注！ 算法與數(shù)據(jù)結(jié)構(gòu)習(xí)題2一、單項(xiàng)選擇題1. 在數(shù)組A8×10中，行列下標(biāo)從0開(kāi)始，每一個(gè)數(shù)組元素占用3個(gè)字節(jié)存儲(chǔ)，所有數(shù)據(jù)元素相繼存放在一個(gè)地址連續(xù)的存儲(chǔ)空間中，則存放該數(shù)組至少需要的字節(jié)數(shù)是（ ）。A240 B100 C80 D270 2. 如果把由樹(shù)轉(zhuǎn)換得到的二叉樹(shù)叫做這棵樹(shù)所對(duì)應(yīng)的二叉樹(shù)，則下面結(jié)論正確的是（ ）。 A等同于該二叉樹(shù)對(duì)應(yīng)的樹(shù)林結(jié)點(diǎn)的先根次序序列 B等同于該二叉樹(shù)對(duì)應(yīng)的樹(shù)林結(jié)點(diǎn)的后根次序序列 C等同于該二叉樹(shù)對(duì)應(yīng)的樹(shù)林結(jié)點(diǎn)的層次次序序列 D不等于上述任何一種序列3. 哈夫曼樹(shù)可應(yīng)用于（ ）。 A組織文件索引 B動(dòng)態(tài)存儲(chǔ)管

2、理 C字符串的模式匹配算法 D外排序中確定二路并歸的最佳歸并次序4. 中綴表達(dá)式A*(B+C)/(D-E+F)的后綴表達(dá)式為（ ）。AA*B+C/D-E+F BAB*C+D/E-F+CABC+*DE-F+/ DABCDEF*+/-+5連續(xù)存儲(chǔ)設(shè)計(jì)時(shí)，存儲(chǔ)單元的地址（ ）。A一定連續(xù) B一定不連續(xù) C不一定連續(xù) D部分連續(xù)，部分不連續(xù)6. 比較次數(shù)與排序碼的初始排列狀態(tài)無(wú)關(guān)的排序算法是（ ）。A直接插入排序 B直接選擇排序 C快速排序 D歸并排序7. 一個(gè)具有n個(gè)頂點(diǎn)的連通無(wú)向圖的生成樹(shù)中有（ ）條邊。An-1 Bn Cn/2 Dn+18. 設(shè)計(jì)最佳二叉排序樹(shù)的構(gòu)造算法的主要技術(shù)是（ ）。A分治

3、法 B貪心法 C動(dòng)態(tài)規(guī)劃法 D分支限界法二、多項(xiàng)選擇題1. 下列屬于算法的重要特征的是（ ）。 A. 有窮性 B. 確定性C. 可行性 D. 輸入和輸出2. 圖的四種存儲(chǔ)結(jié)構(gòu)包括（ ）。A. 鄰接矩陣 B. 鄰接表C. 鄰接多重表 D. 十字鏈表3. 下列說(shuō)法正確的有：（ ）A. 算法和程序原則上沒(méi)有區(qū)別，在討論數(shù)據(jù)結(jié)構(gòu)時(shí)二者通用B. 從邏輯關(guān)系上講，數(shù)據(jù)結(jié)構(gòu)分為兩大類(lèi)：線(xiàn)性結(jié)構(gòu)和非線(xiàn)性結(jié)構(gòu)C. 所謂數(shù)據(jù)的邏輯結(jié)構(gòu)是指數(shù)據(jù)元素之間的邏輯關(guān)系D. 同一數(shù)據(jù)邏輯結(jié)構(gòu)中的所有數(shù)據(jù)元素都具有相同的特性是指數(shù)據(jù)元素所 包含的數(shù)據(jù)項(xiàng)的個(gè)數(shù)相等E. 數(shù)據(jù)的邏輯結(jié)構(gòu)與數(shù)據(jù)元素本身的內(nèi)容和形式無(wú)關(guān)F. 數(shù)據(jù)結(jié)構(gòu)

4、是指相互之間存在一種或多種關(guān)系的數(shù)據(jù)元素的全體4. 線(xiàn)性表的特點(diǎn)正確的（ ） A. 存在唯一的一個(gè)被稱(chēng)作“第一個(gè)”的數(shù)據(jù)元素B. 不存在唯一的一個(gè)被稱(chēng)作“第一個(gè)”的數(shù)據(jù)元素C. 存在唯一的一個(gè)被稱(chēng)作“最后一個(gè)”的數(shù)據(jù)元素D. 不存在唯一的一個(gè)被稱(chēng)作“最后一個(gè)”的數(shù)據(jù)元素三、填空題1. 在n個(gè)結(jié)點(diǎn)的單鏈表中要?jiǎng)h除已知結(jié)點(diǎn)*p，需找到它的_的地址，其時(shí)間復(fù)雜度為_(kāi)。2在對(duì)一組記錄（54，38，96，23，15，72，60，45，83）進(jìn)行直接插入排序時(shí)，當(dāng)把第7個(gè)記錄60插入到有序表時(shí)，為尋找插入位置需比較_次。3. 數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)可用四種基本的存儲(chǔ)方法表示，其中三種分別是_、_、_。（任選三種）

5、4某線(xiàn)性表采用順序存儲(chǔ)結(jié)構(gòu)，每個(gè)元素占據(jù)4個(gè)存儲(chǔ)單元，首地址為100，則下標(biāo)為11（第12個(gè)）的元素的存儲(chǔ)地址為_(kāi)。四、判斷題1. 對(duì)于不同的使用者，一個(gè)表結(jié)構(gòu)既可以是棧，也可以是隊(duì)列，也可以是線(xiàn)性表。（ ）2. 一個(gè)棧的輸入序列是12345，則棧的輸出序列不可能是12345。（ ）3. 任意圖都是其自身的子圖。（ ）4. 如果圖中有一部分邊的權(quán)為負(fù)值，那么用Dijkstra算法求圖的最短路徑是可行的。（ ）5算法的優(yōu)劣與算法描述語(yǔ)言無(wú)關(guān)，但與所用計(jì)算機(jī)有關(guān)。（ ）6健壯的算法不會(huì)因非法的輸入數(shù)據(jù)而出現(xiàn)莫名其妙的狀態(tài)。（ ）7. 算法可以用不同的語(yǔ)言描述，如果用C語(yǔ)言或PASCAL語(yǔ)言等高級(jí)語(yǔ)

6、言來(lái)描述，則算法實(shí)際上就是程序了。（ ）五、簡(jiǎn)答題1什么是索引文件？它有什么特點(diǎn)？2. 寫(xiě)一個(gè)遞歸算法，用來(lái)把整數(shù)字符串轉(zhuǎn)換為整數(shù)。例如：“43567”->43567。3計(jì)算下列程序片段的時(shí)間代價(jià)（寫(xiě)明計(jì)算步驟）。Int i=1;While (i<=n) Int j =1; While(j<=n) Int k=1;While(k<=n) Printf(“i=%d,j=%d,k=%dn”,i,j,k);K=k+1; J=j+1; i=i+1;4. 鏈接存儲(chǔ)的優(yōu)缺點(diǎn)分別是什么？ 5. 在堆排序、快速排序和歸并排序這三種中，若只從存儲(chǔ)空間考慮，則應(yīng)該首選_,其次選取_算法，最

7、后選取_算法；若只從排序結(jié)果的穩(wěn)定性來(lái)考慮，則應(yīng)該選取_算法，其次選取_算法，最后選取_算法。若只從最壞情況下排序要快，并且要節(jié)省內(nèi)存考慮，則選擇_算法。6. 什么是二叉樹(shù)的高度？7. 什么是內(nèi)排序？算法與數(shù)據(jù)結(jié)構(gòu)習(xí)題2答案 一、單項(xiàng)選擇題題號(hào)12345678答案AADDADAC二、多項(xiàng)選擇題題號(hào)1234答案ABCDABCDBCEAC三、填空題題號(hào)答案1前驅(qū)結(jié)點(diǎn)；O（n）233順序；鏈?zhǔn)?；索?144四、判斷題題號(hào)1234567答案××××五、簡(jiǎn)答題1. 答：索引表是由索引組成的表，每個(gè)索引項(xiàng)是一條記錄的關(guān)鍵碼和指向該記錄的指針組成的二元組。實(shí)際中的索引

8、表是很大的，需要存放在外存儲(chǔ)器上，因此索引表也是一種文件。索引表本身可以用不同的方式來(lái)組織。主文件的記錄可以在外存儲(chǔ)器上按關(guān)鍵碼的順序排列，也可以不按關(guān)鍵碼的順序排列。2. 答：先遞歸調(diào)用本算法，以轉(zhuǎn)換除去末位外剩余的字符串，結(jié)果乘以10；再轉(zhuǎn)換末位。將兩結(jié)果相加即為所求。 Int stringTolnt1(char *s, int start, int end) /*把整數(shù)字符串s中從start到end的部分轉(zhuǎn)換為整數(shù)*/If（start>end）return -1; /*轉(zhuǎn)換失敗*/If（start= =end）return send-0; /*只有一個(gè)字符，直接轉(zhuǎn)換*/Return

9、 stringTolnt1(s,start,end-1)*10+send-0;/*先轉(zhuǎn)換其他位，再轉(zhuǎn)換末位*/ Int stringTolnt(char *s) Int i=0; While (si!=0)i+; /*計(jì)算字符串的長(zhǎng)度*/Return stringTolnt1(s,0,i-1)3. 答：循環(huán)控制變量i從1增加到n，最外層循環(huán)體執(zhí)行n次，循環(huán)控制變量j從1增加到n，中間層循環(huán)體執(zhí)行n*i，循環(huán)控制變量k從1增加到n，最內(nèi)層循環(huán)體執(zhí)行n次，所以該程序段總的時(shí)間代價(jià)為T(mén)(n)=1+n+n1+n+n1+n+2n+1+1+1+1=3n3+3n2+4n+2=O（n3）4. 答：優(yōu)點(diǎn)：1.插入和刪除比較靈活，不需要大量移動(dòng)結(jié)點(diǎn)。 2.動(dòng)態(tài)分配空間比較靈活，不需要預(yù)先申請(qǐng)最大的連續(xù)空間。 缺點(diǎn)：1.增加指針的空間開(kāi)銷(xiāo) 2.檢索必須沿鏈進(jìn)行，不能隨機(jī)存取。5.