算法與數(shù)據(jù)結(jié)構(gòu)習(xí)題及參考答案2

算法與數(shù)據(jù)結(jié)構(gòu)習(xí)題及參考答案2單項(xiàng)選擇題1.文件的基本組織方式有：（）。A、順序組織、索引組織、散列組織和鏈接方式B、磁盤組織、磁帶組織C、數(shù)據(jù)庫組織D、關(guān)鍵字與非關(guān)鍵字答案：A2.為了區(qū)別循環(huán)隊(duì)列中隊(duì)滿與隊(duì)空的條件，采用的方法是：（）。A、不需要特別的方法B、犧牲一個(gè)存貯空間C、把隊(duì)頭永遠(yuǎn)放到隊(duì)尾的前端D、每次出隊(duì)后，移動(dòng)數(shù)據(jù)答案：B3.通過鏈表存貯樹時(shí)，如果給定樹中結(jié)點(diǎn)的個(gè)數(shù)，則鏈域浪費(fèi)的空間隨樹的度增加而：（）。A、增加B、減少C、不變D、無規(guī)律答案：A4.兩字符串相等的條件是（）。A、兩個(gè)串的長度相等 B、兩個(gè)串包含的字符相等C、兩個(gè)串的長度相等，并且兩個(gè)串包含的字符相同 D、兩個(gè)串的長度相等，并且對(duì)應(yīng)位置上的字符相同答案：D5.在下列有關(guān)圖的存儲(chǔ)結(jié)構(gòu)中說法錯(cuò)誤的是（）。A、用鄰接矩陣存儲(chǔ)一個(gè)圖時(shí)所占用的存儲(chǔ)空間大小與圖中的頂點(diǎn)個(gè)數(shù)有關(guān)，而與圖的邊數(shù)無關(guān) B、鄰接表只能用于有向圖的存儲(chǔ)，鄰接矩陣對(duì)于有向圖和無向圖的存儲(chǔ)都適用C、鄰接矩陣只適用于稠密圖（邊數(shù)接近于頂點(diǎn)數(shù)的平方），鄰接表適用于稀疏圖（邊數(shù)遠(yuǎn)小于頂點(diǎn)數(shù)的平方） D、存儲(chǔ)無向圖的鄰接矩陣是對(duì)稱的，因此只要存儲(chǔ)鄰接矩陣的下（上）三角部分就可以了答案：B6.順序搜索法適合于存儲(chǔ)結(jié)構(gòu)為（）的線性表。A、散列存儲(chǔ) B、順序存儲(chǔ)或鏈接存儲(chǔ)C、壓縮存儲(chǔ) D、索引存儲(chǔ)答案：B多項(xiàng)選擇題1.下述陳述中哪一項(xiàng)是正確的():A、文件是由記錄組成的集合B、記錄是文件存取的基本單位C、文件是由數(shù)據(jù)項(xiàng)組成的D、數(shù)據(jù)項(xiàng)有時(shí)也被稱之為字段答案：BD2.下列排序算法中哪些是不穩(wěn)定的():A、昌泡排序B、選擇排序C、快速排序D、堆排序答案：BCD3.稀疏矩陣的存貯結(jié)構(gòu)要滿足哪些條件？()A、每個(gè)非零元素存貯其行號(hào)、列號(hào)以及值B、存貯矩陣的行數(shù)和列數(shù)C、所有的非零元素以行優(yōu)先的排列規(guī)則存貯D、只存貯上三角的元素E、只存貯下三角的元素答案：ABC4.圖的鄰接矩陣存貯結(jié)構(gòu)包括():A、表示圖中頂點(diǎn)間相鄰關(guān)系的矩陣B、對(duì)稱矩陣C、表示圖中頂點(diǎn)元素的數(shù)組D、表示入度的數(shù)組E、表示出度的數(shù)組答案：AC5.假設(shè)有三角矩陣a[n][n]，對(duì)角線及對(duì)角線以上的元素非零，對(duì)角線以下的元素為0。如果采用壓縮存貯，即只存貯矩陣中的上三角元素和既存貯上三角元素又存貯0兩種情況下，所需要的存貯空間的分別容量為()和()。A、n*(n+1)/2,n*(n+1)/2+1B、n*(n+1)/2,n*nC、(n+1)n/2,(n+1)n/2+1D、n(n-1)/2,n*(n-1)/2+1答案：AC判斷題1.拓?fù)渑判蚴菆D的另一種遍歷。答案：正確2.樹是一種特殊的圖。答案：正確3.數(shù)據(jù)結(jié)構(gòu)中只研究了二叉樹，對(duì)一般樹沒有給出解決問題的算法。答案：錯(cuò)誤4.在單向鏈表中，在X指向的結(jié)點(diǎn)后插入結(jié)點(diǎn)，對(duì)應(yīng)的方法與X是否是頭指針無關(guān)。答案：錯(cuò)誤5.有人采用Haffman樹進(jìn)行編碼后，由于每個(gè)符號(hào)的代碼長度不等，當(dāng)接收方收到編碼后的內(nèi)容后，不能轉(zhuǎn)換為原來的正文。該說法是否正確？答案：正確6.一棵度為2的樹是一棵二叉樹。答案：錯(cuò)誤7.數(shù)組是一種復(fù)雜的數(shù)據(jù)結(jié)構(gòu)，數(shù)組元素之間的關(guān)系既不是線性的，也不是樹形的。答案：錯(cuò)誤8.對(duì)于不同的使用者，一個(gè)表結(jié)構(gòu)既可以是棧，也可以是隊(duì)列，也可以是線性表。答案：正確9.兩個(gè)棧共享一片連續(xù)內(nèi)存空間時(shí)，為提高內(nèi)存利用率，減少溢出機(jī)會(huì)，應(yīng)把兩個(gè)棧的棧底分別設(shè)在這片內(nèi)存空間的兩端。答案：正確10.最優(yōu)二叉搜索樹一定是平衡的二叉搜索樹。答案：錯(cuò)誤填空題1．某線性表采用順序存儲(chǔ)結(jié)構(gòu)，每個(gè)元素占據(jù)4個(gè)存儲(chǔ)單元，首地址為100，則下標(biāo)為11（第12個(gè)）的元素的存儲(chǔ)地址為。答案：1442.在函數(shù)中對(duì)引用型形式參數(shù)的修改就是對(duì)相應(yīng)的修改，而對(duì)型形式參數(shù)的修改只局限在該函數(shù)的內(nèi)部，不會(huì)反映到對(duì)應(yīng)的實(shí)際參數(shù)上。答案：實(shí)際參數(shù)的值；傳值3.將一個(gè)n階對(duì)稱矩陣的上三角部分或下三角部分壓縮存放于一個(gè)一維數(shù)組中，則一維數(shù)組需要存儲(chǔ)個(gè)矩陣元素。答案：n(n+1)/2簡答題1.請(qǐng)回答關(guān)于鏈接存儲(chǔ)的優(yōu)缺點(diǎn)。答案：優(yōu)點(diǎn)：1.插入和刪除比較靈活，不需要大量移動(dòng)結(jié)點(diǎn)。2.動(dòng)態(tài)分配空間比較靈活，不需要預(yù)先申請(qǐng)最大的連續(xù)空間。缺點(diǎn)：1.增加指針的空間開銷2.檢索必須沿鏈進(jìn)行，不能隨機(jī)存取。2.請(qǐng)寫一個(gè)遞歸算法來計(jì)算并返回鏈表的長度，并在程序中做出相應(yīng)的文字說明。答案：intlength(LinkListllist){/*計(jì)算單鏈表list的長度*/If(llist==NULL)return();return1+length(llist->link);}3.給出棧的最常用的5種操作，并說明它們的功能。答案：(1)voidpush（ST,x）將元素x插入棧ST的頂端(2)void