2023年福師春秋學(xué)期數(shù)據(jù)結(jié)構(gòu)概論在線作業(yè)一

一、單選題（共２5道試題,共５0分。)Ｖ1.已知廣義表L=(（ｘ,y,ｚ）,ａ,(u,t，w)),從L表中取出原子項(xiàng)t的運(yùn)算是（)A.hｅad(ｔail(tａil(Ｌ））)B.tail(head（head(tａｉl(Ｌ）））)Ｃ.head（ｔail(ｈead（ｔａil（L）))）D．head(tail（heａd（tail(ｔail(L)）))）２.設(shè)給定權(quán)值總數(shù)有n個(gè),其哈夫曼樹的結(jié)點(diǎn)總數(shù)為()A.不擬定B.2nC.2n+1D.2n－１３.在下列存儲形式中,哪一個(gè)不是樹的存儲形式？（）A.雙親表達(dá)法B.孩子鏈表表達(dá)法C.孩子兄弟表達(dá)法D．順序存儲表達(dá)法4.線性表（a1,ａ2,…,aｎ)以鏈接方式存儲時(shí)，訪問第i位置元素的時(shí)間復(fù)雜性為(）Ａ.O(i）B.O(1)C.O(ｎ）Ｄ．O(i-１）5.若規(guī)定排序是穩(wěn)定的，且關(guān)鍵字為實(shí)數(shù)，則在下列排序方法中應(yīng)選(）排序?yàn)橐恕.直接插入B.直接選擇C.堆Ｄ.快速6.設(shè)樹Ｔ的度為4，其中度為1，2，3和4的結(jié)點(diǎn)個(gè)數(shù)分別為４,２,1,１則Ｔ中的葉子數(shù)為(）A．5B.６C．7D.87．對于棧操作數(shù)據(jù)的原則是（）Ａ.先進(jìn)先出B．后進(jìn)先出C．后進(jìn)后出D.不分順序8.下面有關(guān)算法說法錯(cuò)誤的是（）A.算法最終必須由計(jì)算機(jī)程序?qū)崿F(xiàn)Ｂ.為解決某問題的算法同為該問題編寫的程序含義是相同的Ｃ.算法的可行性是指指令不能有二義性D.以上幾個(gè)都是錯(cuò)誤的9.就平均性能而言，目前最佳的內(nèi)部排序方法是(）排序法。A．冒泡Ｂ．希爾插入C．互換D.快速1０.廣義表運(yùn)算式Tail（((a,ｂ),（ｃ，d)))的操作結(jié)果是(）。A.（c,ｄ）B．c,dC.((c,d))D.d1１.已知串S=‘a(chǎn)aab’,其Next數(shù)組值為（)。Ａ.01２３Ｂ.112３C．1231D.12111２.連續(xù)存儲設(shè)計(jì)時(shí),存儲單元的地址()。A.一定連續(xù)B.一定不連續(xù)C.不一定連續(xù)D.部分連續(xù),部分不連續(xù)１3.從邏輯上可以把數(shù)據(jù)結(jié)構(gòu)分為(）兩大類。Ａ.動態(tài)結(jié)構(gòu)、靜態(tài)結(jié)構(gòu)Ｂ.順序結(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)14．具有10個(gè)葉結(jié)點(diǎn)的二叉樹中有()個(gè)度為２的結(jié)點(diǎn),A.8B.9C.1０Ｄ．lｌ1５．下面給出的四種排序方法中,排序過程中的比較次數(shù)與排序方法無關(guān)的是(）Ａ.選擇排序法B.插入排序法Ｃ.快速排序法D.堆積排序法16.在下面的排序方法中，輔助空間為O(ｎ)的是(）A．希爾排序B．堆排序Ｃ.選擇排序D.歸并排序１7.圖中有關(guān)途徑的定義是（)A.由頂點(diǎn)和相鄰頂點(diǎn)序偶構(gòu)成的邊所形成的序列B.由不同頂點(diǎn)所形成的序列C.由不同邊所形成的序列D.上述定義都不是1８．算法的計(jì)算量的大小稱為計(jì)算的（)。Ａ.效率B．復(fù)雜性Ｃ.現(xiàn)實(shí)性D．難度1９.設(shè)有兩個(gè)串p和ｑ，其中q是p的子串，求q在p中初次出現(xiàn)的位置的算法稱為(）Ａ.求子串B.聯(lián)接C.匹配Ｄ.求串長２0.用二分(對半)查找表的元素的速度比用順序法（）A.必然快Ｂ.必然慢C.相等D.不能擬定21．串的長度是指(）A．串中所含不同字母的個(gè)數(shù)B.串中所含字符的個(gè)數(shù)C.串中所含不同字符的個(gè)數(shù)Ｄ.串中所含非空格字符的個(gè)數(shù)２2．一個(gè)遞歸算法必須涉及（）A．遞歸部分Ｂ.終止條件和遞歸部分Ｃ.迭代部分D．終止條件和迭代部分23．一個(gè)算法應(yīng)當(dāng)是()A．程序B.問題求解環(huán)節(jié)的描述Ｃ.要滿足五個(gè)基本特性D.A和Ｃ．２4．對于一個(gè)頭指針為ｈead的帶頭結(jié)點(diǎn)的單鏈表，鑒定該表為空表的條件是(）A.hｅaｄ==NUＬＬＢ.ｈｅad→neｘt==ＮUＬＬC.ｈead→neｘt==ｈｅadD．head!=NUＬL２５.由3個(gè)結(jié)點(diǎn)可以構(gòu)造出多少種不同的二叉樹(）A.2B.３Ｃ．４Ｄ.5二、判斷題(共20道試題，共40分。）V１.對無序表用二分法查找比順序查找快()A.錯(cuò)誤B.對的２.線性表只能用順序存儲結(jié)構(gòu)實(shí)現(xiàn)。A.錯(cuò)誤Ｂ.對的3.折半查找法的查找速度一定比順序查找法快（)A.錯(cuò)誤B.對的4.循環(huán)鏈表不是線性表.A．錯(cuò)誤B.對的５.對于有N個(gè)結(jié)點(diǎn)的二叉樹，其高度為log2n。A.錯(cuò)誤B.對的6.順序存儲方式插入和刪除時(shí)效率太低,因此它不如鏈?zhǔn)酱鎯Ψ绞胶茫ǎ粒e(cuò)誤B.對的7．順序存儲結(jié)構(gòu)的重要缺陷是不利于插入或刪除操作。Ａ.錯(cuò)誤B．對的8．當(dāng)待排序的元素很大時(shí),為了互換元素的位置,移動元素要占用較多的時(shí)間,這是影響時(shí)間復(fù)雜度的重要因素A.錯(cuò)誤B.對的9．在查找樹(二叉樹排序樹）中插入一個(gè)新結(jié)點(diǎn),總是插入到葉結(jié)點(diǎn)下面。A.錯(cuò)誤B.對的１0.對一棵二叉樹進(jìn)行層次遍歷時(shí),應(yīng)借助于一個(gè)棧Ａ.錯(cuò)誤Ｂ.對的11.線性表的特點(diǎn)是每個(gè)元素都有一個(gè)前驅(qū)和一個(gè)后繼（）Ａ．錯(cuò)誤B．對的1２.直接選擇排序算法在最佳情況下的時(shí)間復(fù)雜度為O（N）。Ａ.錯(cuò)誤Ｂ.對的13.若一個(gè)廣義表的表頭為空表,則此廣義表亦為空表。A．錯(cuò)誤Ｂ.對的1４.線性表采用鏈表存儲時(shí),結(jié)點(diǎn)和結(jié)點(diǎn)內(nèi)部的存儲空間可以是不連續(xù)的。Ａ．錯(cuò)誤Ｂ.對的1５．當(dāng)待排序的元素很多時(shí),為了互換元素的位置,移動元素要占用較多的時(shí)間，這是影響時(shí)間復(fù)雜度的重要因素(）Ａ．錯(cuò)誤B.對的16．二叉樹的遍歷結(jié)果不是唯一的．A.錯(cuò)誤B.對的1７.兩分法插入排序所需比較次數(shù)與待排序記錄的初始排列狀態(tài)相關(guān)()A.錯(cuò)誤B.對的1８.棧與隊(duì)列是一種特殊操作的線性表。A.錯(cuò)誤B.對的1９．隊(duì)列邏輯上是一個(gè)下端和上端既能增長又能減少的線性表（）。A．錯(cuò)誤B．對的2０.排序的穩(wěn)定性是指排序算法中的比較次數(shù)保持不變，且算法可以終止(）A.錯(cuò)誤B．對的三、多選題（共5道試題,共10分。）Ｖ1.下列關(guān)于m階B－樹的說法對的的是()A.根結(jié)點(diǎn)至多有m棵子樹B．所有葉子都在同一層次上C．非葉結(jié)點(diǎn)至少有m/2（m為偶數(shù))或m/2＋1（m為奇數(shù))棵子樹D.根結(jié)點(diǎn)中的數(shù)據(jù)是有序的ＢC2.下述哪些不是順序存儲結(jié)構(gòu)的優(yōu)點(diǎn)?(）A.存儲密度大B.插入運(yùn)算方便C.刪除運(yùn)算方便D.可方便地用于各種邏輯結(jié)構(gòu)的存儲表達(dá)ＣD3．某堆棧的輸入序列為a,b，c，ｄ，下面的四個(gè)序列中,也許是它的輸出序列的是(）Ａ.a,c,b，dB.b,c