數(shù)據(jù)結(jié)構(gòu)考試題及答案資料

2012年數(shù)據(jù)結(jié)構(gòu)期末考試題及答案一、選擇題1．在數(shù)據(jù)結(jié)構(gòu)中，從邏輯上可以把數(shù)據(jù)結(jié)構(gòu)分為C。A．動(dòng)態(tài)結(jié)構(gòu)和靜態(tài)結(jié)構(gòu)B．緊湊結(jié)構(gòu)和非緊湊結(jié)構(gòu)C．線(xiàn)性結(jié)構(gòu)和非線(xiàn)性結(jié)構(gòu)D．內(nèi)部結(jié)構(gòu)和外部結(jié)構(gòu)2．?dāng)?shù)據(jù)結(jié)構(gòu)在計(jì)算機(jī)內(nèi)存中的表示是指A。A．?dāng)?shù)據(jù)的存儲(chǔ)結(jié)構(gòu)B．?dāng)?shù)據(jù)結(jié)構(gòu)C．?dāng)?shù)據(jù)的邏輯結(jié)構(gòu)D．?dāng)?shù)據(jù)元素之間的關(guān)系3．在數(shù)據(jù)結(jié)構(gòu)中，與所使用的計(jì)算機(jī)無(wú)關(guān)的是數(shù)據(jù)的A結(jié)構(gòu)。A．邏輯B．存儲(chǔ)C．邏輯和存儲(chǔ)D．物理4．在存儲(chǔ)數(shù)據(jù)時(shí)，通常不僅要存儲(chǔ)各數(shù)據(jù)元素的值，而且還要存儲(chǔ)C。A．?dāng)?shù)據(jù)的處理方法B．?dāng)?shù)據(jù)元素的類(lèi)型C．?dāng)?shù)據(jù)元素之間的關(guān)系D．?dāng)?shù)據(jù)的存儲(chǔ)方法5．在決定選取何種存儲(chǔ)結(jié)構(gòu)時(shí)，一般不考慮A。A．各結(jié)點(diǎn)的值如何B．結(jié)點(diǎn)個(gè)數(shù)的多少C．對(duì)數(shù)據(jù)有哪些運(yùn)算D．所用的編程語(yǔ)言實(shí)現(xiàn)這種結(jié)構(gòu)是否方便。6．以下說(shuō)法正確的是D。A．?dāng)?shù)據(jù)項(xiàng)是數(shù)據(jù)的基本單位B．?dāng)?shù)據(jù)元素是數(shù)據(jù)的最小單位C．?dāng)?shù)據(jù)結(jié)構(gòu)是帶結(jié)構(gòu)的數(shù)據(jù)項(xiàng)的集合D．一些表面上很不相同的數(shù)據(jù)可以有相同的邏輯結(jié)構(gòu)7．算法分析的目的是C，算法分析的兩個(gè)主要方面是A。（1）A．找出數(shù)據(jù)結(jié)構(gòu)的合理性B．研究算法中的輸入和輸出的關(guān)系C．分析算法的效率以求改進(jìn)C．分析算法的易讀性和文檔性（2）A．空間復(fù)雜度和時(shí)間復(fù)雜度B．正確性和簡(jiǎn)明性C．可讀性和文檔性D．?dāng)?shù)據(jù)復(fù)雜性和程序復(fù)雜性8．下面程序段的時(shí)間復(fù)雜度是O（n2）。s＝0；for（I＝0；i＜n；i＋＋）for（j＝0；j＜n；j＋＋）s＋＝B[i][j]；sum＝s；9．下面程序段的時(shí)間復(fù)雜度是O（n*m）。for（i＝0；i＜n；i＋＋）for（j＝0；j＜m；j＋＋）A[i][j]＝0；10．下面程序段的時(shí)間復(fù)雜度是O（log3n）。i＝0；while（i＜＝n）i＝i*3；11．在以下的敘述中，正確的是B。A．線(xiàn)性表的順序存儲(chǔ)結(jié)構(gòu)優(yōu)于鏈表存儲(chǔ)結(jié)構(gòu)B．二維數(shù)組是其數(shù)據(jù)元素為線(xiàn)性表的線(xiàn)性表C．棧的操作方式是先進(jìn)先出D．隊(duì)列的操作方式是先進(jìn)后出12．通常要求同一邏輯結(jié)構(gòu)中的所有數(shù)據(jù)元素具有相同的特性，這意味著B(niǎo)。A．?dāng)?shù)據(jù)元素具有同一特點(diǎn)B．不僅數(shù)據(jù)元素所包含的數(shù)據(jù)項(xiàng)的個(gè)數(shù)要相同，而且對(duì)應(yīng)的數(shù)據(jù)項(xiàng)的類(lèi)型要一致C．每個(gè)數(shù)據(jù)元素都一樣D．?dāng)?shù)據(jù)元素所包含的數(shù)據(jù)項(xiàng)的個(gè)數(shù)要相等13．鏈表不具備的特點(diǎn)是A。A．可隨機(jī)訪問(wèn)任一結(jié)點(diǎn)B．插入刪除不需要移動(dòng)元素C．不必事先估計(jì)存儲(chǔ)空間D．所需空間與其長(zhǎng)度成正比14．不帶頭結(jié)點(diǎn)的單鏈表head為空的判定條件是A。next＝＝NULLC．head－＞next＝＝headDhead?。絅ULL15．帶頭結(jié)點(diǎn)的單鏈表head為空的判定條件是B。next＝＝NULLC．head－＞next＝＝headDhead?。絅ULL16．若某表最常用的操作是在最后一個(gè)結(jié)點(diǎn)之后插入一個(gè)結(jié)點(diǎn)或刪除最后一個(gè)結(jié)點(diǎn)，則采用D存儲(chǔ)方式最節(jié)省運(yùn)算時(shí)間。A．單鏈表B．給出表頭指針的單循環(huán)鏈表C．雙鏈表D．帶頭結(jié)點(diǎn)的雙循環(huán)鏈表17．需要分配較大空間，插入和刪除不需要移動(dòng)元素的線(xiàn)性表，其存儲(chǔ)結(jié)構(gòu)是B。A．單鏈表B．靜態(tài)鏈表C．線(xiàn)性鏈表D．順序存儲(chǔ)結(jié)構(gòu)18．非空的循環(huán)單鏈表head的尾結(jié)點(diǎn)（由p所指向）滿(mǎn)足C。A．p－＞next＝＝NULLB．p＝＝NULLC．p－＞next＝＝headD．p＝＝head19．在循環(huán)雙鏈表的p所指的結(jié)點(diǎn)之前插入s所指結(jié)點(diǎn)的操作是D。A．p－＞prior－＞priorB．p－＞prior－＞priorC．s－＞prior－＞next＝sD．s－＞prior－＞prior＝s20．如果最常用的操作是取第i個(gè)結(jié)點(diǎn)及其前驅(qū)，則采用D存儲(chǔ)方式最節(jié)省時(shí)間。A．單鏈表B．雙鏈表C．單循環(huán)鏈表D．順序表21．在一個(gè)具有n個(gè)結(jié)點(diǎn)的有序單鏈表中插入一個(gè)新結(jié)點(diǎn)并仍然保持有序的時(shí)間復(fù)雜度是B。A．O（1）B．O（n）C．O（n2）D．O（nlog2n）22．在一個(gè)長(zhǎng)度為n（n＞1）的單鏈表上，設(shè)有頭和尾兩個(gè)指針，執(zhí)行B操作與鏈表的長(zhǎng)度有關(guān)。A．刪除單鏈表中的第一個(gè)元素B．刪除單鏈表中的最后一個(gè)元素C．在單鏈表第一個(gè)元素前插入一個(gè)新元素D．在單鏈表最后一個(gè)元素后插入一個(gè)新元素23．與單鏈表相比，雙鏈表的優(yōu)點(diǎn)之一是D。A．插入、刪除操作更簡(jiǎn)單B．可以進(jìn)行隨機(jī)訪問(wèn)C．可以省略表頭指針或表尾指針D．順序訪問(wèn)相鄰結(jié)點(diǎn)更靈活24．如果對(duì)線(xiàn)性表的操作只有兩種，即刪除第一個(gè)元素，在最后一個(gè)元素的后面插入新元素，則最好使用B。A．只有表頭指針沒(méi)有表尾指針的循環(huán)單鏈表B．只有表尾指針沒(méi)有表頭指針的循環(huán)單鏈表C．非循環(huán)雙鏈表D．循環(huán)雙鏈表25．在長(zhǎng)度為n的順序表的第i個(gè)位置上插入一個(gè)元素（1≤i≤n＋1），元素的移動(dòng)次數(shù)為：A。A．n–i＋1B．n–iC．iD．i–126．對(duì)于只在表的首、尾兩端進(jìn)行插入操作的線(xiàn)性表，宜采用的存儲(chǔ)結(jié)構(gòu)為C。A．順序表B．用頭指針表示的循環(huán)單鏈表C．用尾指針表示的循環(huán)單鏈表D．單鏈表27．下述哪一條是順序存儲(chǔ)結(jié)構(gòu)的優(yōu)點(diǎn)?C。A插入運(yùn)算方便B可方便地用于各種邏輯結(jié)構(gòu)的存儲(chǔ)表示C存儲(chǔ)密度大D刪除運(yùn)算方便28．下面關(guān)于線(xiàn)性表的敘述中，錯(cuò)誤的是哪一個(gè)?B。A線(xiàn)性表采用順序存儲(chǔ)，必須占用一片連續(xù)的存儲(chǔ)單元B線(xiàn)性表采用順序存儲(chǔ)，便于進(jìn)行插入和刪除操作。C線(xiàn)性表采用鏈?zhǔn)酱鎯?chǔ)，不必占用一片連續(xù)的存儲(chǔ)單元D線(xiàn)性表采用鏈?zhǔn)酱鎯?chǔ)，便于進(jìn)行插入和刪除操作。29．線(xiàn)性表是具有n個(gè)B的有限序列。A．字符B．?dāng)?shù)據(jù)元素C．?dāng)?shù)據(jù)項(xiàng)D．表元素30．在n個(gè)結(jié)點(diǎn)的線(xiàn)性表的數(shù)組實(shí)現(xiàn)中，算法的時(shí)間復(fù)雜度是O（1）的操作是A。A．訪問(wèn)第i（1＜＝i＜＝n）個(gè)結(jié)點(diǎn)和求第i個(gè)結(jié)點(diǎn)的直接前驅(qū)（1＜i＜＝n）B．在第i（1＜＝i＜＝n）個(gè)結(jié)點(diǎn)后插入一個(gè)新結(jié)點(diǎn)C．刪除第i（1＜＝i＜＝n）個(gè)結(jié)點(diǎn)D．以上都不對(duì)31．若長(zhǎng)度為n的線(xiàn)性表采用順序存儲(chǔ)結(jié)構(gòu)，在其第i個(gè)位置插入一個(gè)新元素的算法的時(shí)間復(fù)雜度為C。A．O（0）B．O（1）C．O（n）D．O（n2）32．對(duì)于順序存儲(chǔ)的線(xiàn)性表，訪問(wèn)結(jié)點(diǎn)和增加、刪除結(jié)點(diǎn)的時(shí)間復(fù)雜度為C。A．O（n）O（n）B．O（n）O（1）C．O（1）O（n）D．O（1）O（1）33．線(xiàn)性表（a1，a2，…，an）以鏈?zhǔn)椒绞酱鎯?chǔ)，訪問(wèn)第i位置元素的時(shí)間復(fù)雜度為C。A．O（0）B．O（1）C．O（n）D．O（n2）34．單鏈表中，增加一個(gè)頭結(jié)點(diǎn)的目的是為了C。A．使單鏈表至少有一個(gè)結(jié)點(diǎn)B．標(biāo)識(shí)表結(jié)點(diǎn)中首結(jié)點(diǎn)的位置C．方面運(yùn)算的實(shí)現(xiàn)D．說(shuō)明單鏈表是線(xiàn)性表的鏈?zhǔn)酱鎯?chǔ)35．在單鏈表指針為p的結(jié)點(diǎn)之后插入指針為s的結(jié)點(diǎn)，正確的操作是B。A．p－＞next＝p－＞next＝p－＞next＝s；C．p－＞next＝s－＞next＝s－＞next；p－＞next＝s36．線(xiàn)性表的順序存儲(chǔ)結(jié)構(gòu)是一種A。A．隨機(jī)存取的存儲(chǔ)結(jié)構(gòu)B．順序存取的存儲(chǔ)結(jié)構(gòu)C．索引存取的存儲(chǔ)結(jié)構(gòu)D．Hash存取的存儲(chǔ)結(jié)構(gòu)37．棧的特點(diǎn)是B，隊(duì)列的特點(diǎn)是A。A．先進(jìn)先出B．先進(jìn)后出38．棧和隊(duì)列的共同點(diǎn)是C。A．都是先進(jìn)后出B．都是先進(jìn)先出C．只允許在端點(diǎn)處插入和刪除元素D．沒(méi)有共同點(diǎn)39．一個(gè)棧的進(jìn)棧序列是a，b，c，d，e，則棧的不可能的輸出序列是C。A．edcbaB．decbaC．dceabD．a(chǎn)bcde40．設(shè)有一個(gè)棧，元素依次進(jìn)棧的順序?yàn)锳、B、C、D、E。下列C是不可能的出棧序列。A．A，B，C，D，EB．B，C，D，E，AC．E，A，B，C，DD．E，D，C，B，A41．以下B不是隊(duì)列的基本運(yùn)算?A．從隊(duì)尾插入一個(gè)新元素B．從隊(duì)列中刪除第i個(gè)元素C．判斷一個(gè)隊(duì)列是否為空D．讀取隊(duì)頭元素的值42．若已知一個(gè)棧的進(jìn)棧序列是1，2，3，，n，其輸出序列為p1，p2，p3，…，pn，若p1＝n，則pi為C。A．iB．n－iC．n－i＋1D．不確定43．判定一個(gè)順序棧st（最多元素為MaxSize）為空的條件是B。A．st－＞top！top＝＝－1C．st－＞top！top＝＝MaxSize44．判定一個(gè)順序棧st（最多元素為MaxSize）為滿(mǎn)的條件是D。A．st－＞top！top＝＝－1C．st－＞top！top＝＝MaxSize45．一個(gè)隊(duì)列的入隊(duì)序列是1，2，3，4，則隊(duì)列的輸出序列是B。A．4，3，2，1B．1，2，3，4C．1，4，3，2D．3，2，4，146．判定一個(gè)循環(huán)隊(duì)列qu（最多元素為MaxSize）為空的條件是C。A．qu－＞rear–qu－＞rear–qu－＞front－1＝＝MaxSizeC．qu－＞front－147．在循環(huán)隊(duì)列中，若front與rear分別表示對(duì)頭元素和隊(duì)尾元素的位置，則判斷循環(huán)隊(duì)列空的條件是C。A．front＝＝rear＋1B．rear＝＝front＋1C．front＝＝rearD．front＝＝048．向一個(gè)棧頂指針為h的帶頭結(jié)點(diǎn)的鏈棧中插入指針s所指的結(jié)點(diǎn)時(shí)，應(yīng)執(zhí)行D操作。A．h－＞next＝h；C．s－＞next＝h－＞next＝s；49．輸入序列為ABC，可以變?yōu)镃BA時(shí)，經(jīng)過(guò)的棧操作為B。A．push，pop，push，pop，push，popB．push，push，push，pop，pop，popC．push，push，pop，pop，push，popD．push，pop，push，push，pop，pop50．若棧采用順序存儲(chǔ)方式存儲(chǔ)，現(xiàn)兩棧共享空間V[1m]，top[1]、top[2]分別代表第1和第2個(gè)棧的棧頂，棧1的底在V[1]，棧2的底在V[m]，則棧滿(mǎn)的條件是B。A．|top[2]－top[1]|＝0B．top[1]＋1＝top[2]C．top[1]＋top[2]＝mD．top[1]＝top[2]51．設(shè)計(jì)一個(gè)判別表達(dá)式中左、右括號(hào)是否配對(duì)出現(xiàn)的算法，采用D數(shù)據(jù)結(jié)構(gòu)最佳。A．線(xiàn)性表的順序存儲(chǔ)結(jié)構(gòu)B．隊(duì)列C．線(xiàn)性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)D．棧52．允許對(duì)隊(duì)列進(jìn)行的操作有D。A．對(duì)隊(duì)列中的元素排序B．取出最近進(jìn)隊(duì)的元素C．在隊(duì)頭元素之前插入元素D．刪除隊(duì)頭元素53．對(duì)于循環(huán)隊(duì)列D。A．無(wú)法判斷隊(duì)列是否為空B．無(wú)法判斷隊(duì)列是否為滿(mǎn)C．隊(duì)列不可能滿(mǎn)D．以上說(shuō)法都不對(duì)54．若用一個(gè)大小為6的數(shù)值來(lái)實(shí)現(xiàn)循環(huán)隊(duì)列，且當(dāng)前rear和front的值分別為0和3，當(dāng)從隊(duì)列中刪除一個(gè)元素，再加入兩個(gè)元素后，rear和front的值分別為B。A．1和5B．2和4C．4和2D．5和155．隊(duì)列的“先進(jìn)先出”特性是指D。A．最早插入隊(duì)列中的元素總是最后被刪除B．當(dāng)同時(shí)進(jìn)行插入、刪除操作時(shí)，總是插入操作優(yōu)先C．每當(dāng)有刪除操作時(shí)，總是要先做一次插入操作D．每次從隊(duì)列中刪除的總是最早插入的元素56．和順序棧相比，鏈棧有一個(gè)比較明顯的優(yōu)勢(shì)是A。A．通常不會(huì)出現(xiàn)棧滿(mǎn)的情況B．通常不會(huì)出現(xiàn)棧空的情況C．插入操作更容易實(shí)現(xiàn)D．刪除操作更容易實(shí)現(xiàn)57．用不帶頭結(jié)點(diǎn)的單鏈表存儲(chǔ)隊(duì)列，其頭指針指向隊(duì)頭結(jié)點(diǎn)，尾指針指向隊(duì)尾結(jié)點(diǎn)，則在進(jìn)行出隊(duì)操作時(shí)C。A．僅修改隊(duì)頭指針B．僅修改隊(duì)尾指針C．隊(duì)頭、隊(duì)尾指針都可能要修改D．隊(duì)頭、隊(duì)尾指針都要修改58．若串S＝‘software’，其子串的數(shù)目是B。A．8B．37C．36D．959．串的長(zhǎng)度是指B。A．串中所含不同字母的個(gè)數(shù)B．串中所含字符的個(gè)數(shù)C．串中所含不同字符的個(gè)數(shù)D．串中所含非空格字符的個(gè)數(shù)60．串是一種特殊的線(xiàn)性表，其特殊性體現(xiàn)在B。A．可以順序存儲(chǔ)B．?dāng)?shù)據(jù)元素是一個(gè)字符C．可以鏈?zhǔn)酱鎯?chǔ)D．?dāng)?shù)據(jù)元素可以是多個(gè)字符61．設(shè)有兩個(gè)串p和q，求q在p中首次出現(xiàn)的位置的運(yùn)算稱(chēng)為B。A．連接B．模式匹配C．求子串D．求串長(zhǎng)62．?dāng)?shù)組A中，每個(gè)元素的長(zhǎng)度為3個(gè)字節(jié)，行下標(biāo)i從1到8，列下標(biāo)j從1到10，從首地址SA開(kāi)始連續(xù)存放的存儲(chǔ)器內(nèi)，該數(shù)組按行存放，元素A[8][5]的起始地址為C。A．SA＋141B．SA＋144C．SA＋222D．SA＋22563．?dāng)?shù)組A中，每個(gè)元素的長(zhǎng)度為3個(gè)字節(jié)，行下標(biāo)i從1到8，列下標(biāo)j從1到10，從首地址SA開(kāi)始連續(xù)存放的存儲(chǔ)器內(nèi)，該數(shù)組按行存放，元素A[5][8]的起始地址為C。A．SA＋141B．SA＋180C．SA＋222D．SA＋22564．若聲明一個(gè)浮點(diǎn)數(shù)數(shù)組如下：froataverage[]＝newfloat[30]；假設(shè)該數(shù)組的內(nèi)存起始位置為200，average[15]的內(nèi)存地址是C。A．214B．215C．260D．25665．設(shè)二維數(shù)組A[1…m，1…n]按行存儲(chǔ)在數(shù)組B中，則二維數(shù)組元素A[i，j]在一維數(shù)組B中的下標(biāo)為A。A．n*（i－1）＋jB．n*（i－1）＋j－1C．i*（j－1）D．j*m＋i－166．有一個(gè)100×90的稀疏矩陣，非0元素有10，設(shè)每個(gè)整型數(shù)占2個(gè)字節(jié)，則用三元組表示該矩陣時(shí)，所需的字節(jié)數(shù)是B。A．20B．66C．18000D．3367．?dāng)?shù)組A[0…4，－1…－3，5…7]中含有的元素個(gè)數(shù)是A。A．55B．45C．36D．1668．對(duì)矩陣進(jìn)行壓縮存儲(chǔ)是為了D。A．方便運(yùn)算B．方便存儲(chǔ)C．提高運(yùn)算速度D．減少存儲(chǔ)空間69．設(shè)有一個(gè)10階的對(duì)稱(chēng)矩陣A，采用壓縮存儲(chǔ)方式，以行序?yàn)橹鞔鎯?chǔ)，a1，1為第一個(gè)元素，其存儲(chǔ)地址為1，每個(gè)元素占1個(gè)地址空間，則a8，5的地址為B。A．13B．33C．18D．4070．稀疏矩陣一般的壓縮存儲(chǔ)方式有兩種，即C。A．二維數(shù)組和三維數(shù)組B．三元組和散列C．三元組和十字鏈表D．散列和十字鏈表71．樹(shù)最適合用來(lái)表示C。A．有序數(shù)據(jù)元素B．無(wú)序數(shù)據(jù)元素C．元素之間具有分支層次關(guān)系的數(shù)據(jù)D．元素之間無(wú)聯(lián)系的數(shù)據(jù)72．深度為5的二叉樹(shù)至多有C個(gè)結(jié)點(diǎn)。A．16B．32C．31C．1073．對(duì)一個(gè)滿(mǎn)二叉樹(shù)，m個(gè)葉子，n個(gè)結(jié)點(diǎn)，深度為h，則D。A．n＝h＋mBh＋m＝2nCm＝h－1Dn＝2h－174．任何一棵二叉樹(shù)的葉子結(jié)點(diǎn)在前序、中序和后序遍歷序列中的相對(duì)次序A。A．不發(fā)生改變B．發(fā)生改變C．不能確定D．以上都不對(duì)75．在線(xiàn)索化樹(shù)中，每個(gè)結(jié)點(diǎn)必須設(shè)置一個(gè)標(biāo)志來(lái)說(shuō)明它的左、右鏈指向的是樹(shù)結(jié)構(gòu)信息，還是線(xiàn)索化信息，若0標(biāo)識(shí)樹(shù)結(jié)構(gòu)信息，1標(biāo)識(shí)線(xiàn)索，對(duì)應(yīng)葉結(jié)點(diǎn)的左右鏈域，應(yīng)標(biāo)識(shí)為_(kāi)_D__。A．00B．01C．10D．1176．在下述論述中，正確的是D。①只有一個(gè)結(jié)點(diǎn)的二叉樹(shù)的度為0；②二叉樹(shù)的度為2；③二叉樹(shù)的左右子樹(shù)可任意交換；④深度為K的順序二叉樹(shù)的結(jié)點(diǎn)個(gè)數(shù)小于或等于深度相同的滿(mǎn)二叉樹(shù)。A．①②③B．②③④C．②④D．①④77．設(shè)森林F對(duì)應(yīng)的二叉樹(shù)為B，它有m個(gè)結(jié)點(diǎn)，B的根為p，p的右子樹(shù)的結(jié)點(diǎn)個(gè)數(shù)為n，森林F中第一棵樹(shù)的結(jié)點(diǎn)的個(gè)數(shù)是A。A．m－nB．m－n－1C．n＋1D．不能確定78．若一棵二叉樹(shù)具有10個(gè)度為2的結(jié)點(diǎn)，5個(gè)度為1的結(jié)點(diǎn)，則度為0的結(jié)點(diǎn)的個(gè)數(shù)是B。A．9B．11C．15D．不能確定79．具有10個(gè)葉子結(jié)點(diǎn)的二叉樹(shù)中有B個(gè)度為2的結(jié)點(diǎn)。A．8B．9C．10D．1180．在一個(gè)無(wú)向圖中，所有頂點(diǎn)的度數(shù)之和等于所有邊數(shù)的C倍。A．1/2B1C2D481．在一個(gè)有向圖中，所有頂點(diǎn)的入度之和等于所有頂點(diǎn)的出度之和的B倍。A．1/2B1C2D482．某二叉樹(shù)結(jié)點(diǎn)的中序序列為ABCDEFG，后序序列為BDCAFGE，則其左子樹(shù)中結(jié)點(diǎn)數(shù)目為：CA．3B．2C．4D．583．已知一算術(shù)表達(dá)式的中綴形式為A＋B*C–D/E，后綴形式為ABC*＋DE/–，其前綴形式為D。A．–A＋B*C/DEB．–A＋B*CD/EC–＋*ABC/DED．–＋A*BC/DE84．已知一個(gè)圖，如圖所示，若從頂點(diǎn)a出發(fā)按深度搜索法進(jìn)行遍歷，則可能得到的一種頂點(diǎn)序列為_(kāi)___D___；按廣度搜索法進(jìn)行遍歷，則可能得到的一種頂點(diǎn)序列為_(kāi)__A___；①A．a(chǎn)，b，e，c，d，fB．a(chǎn)，c，f，e，b，dC．a(chǎn)，e，b，c，f，d，D．a(chǎn)，e，d，f，c，b②A．a(chǎn)，b，c，e，d，fB．a(chǎn)，b，c，e，f，dC．a(chǎn)，e，b，c，f，d，D．a(chǎn)，c，f，d，e，b85．采用鄰接表存儲(chǔ)的圖的深度優(yōu)先遍歷算法類(lèi)似于二叉樹(shù)的___A____。A．先序遍歷B．中序遍歷C．后序遍歷D．按層遍歷86．采用鄰接表存儲(chǔ)的圖的廣度優(yōu)先遍歷算法類(lèi)似于二叉樹(shù)的___D____。A．先序遍歷B．中序遍歷C．后序遍歷D．按層遍歷87．具有n個(gè)結(jié)點(diǎn)的連通圖至少有A條邊。A．n－1B．nC．n（n－1）/2D．2n88．廣義表（（a），a）的表頭是C，表尾是C。A．a(chǎn)B（）C（a）D（（a））89．廣義表（（a））的表頭是C，表尾是B。A．a(chǎn)B（）C（a）D（（a））90．順序查找法適合于存儲(chǔ)結(jié)構(gòu)為B的線(xiàn)性表。A散列存儲(chǔ)B順序存儲(chǔ)或鏈?zhǔn)酱鎯?chǔ)C壓縮存儲(chǔ)D索引存儲(chǔ)91．對(duì)線(xiàn)性表進(jìn)行折半查找時(shí)，要求線(xiàn)性表必須B。A以順序方式存儲(chǔ)B以順序方式存儲(chǔ)，且結(jié)點(diǎn)按關(guān)鍵字有序排列C以鏈?zhǔn)椒绞酱鎯?chǔ)D以鏈?zhǔn)椒绞酱鎯?chǔ)，且結(jié)點(diǎn)按關(guān)鍵字有序排列92．采用折半查找法查找長(zhǎng)度為n的線(xiàn)性表時(shí)，每個(gè)元素的平均查找長(zhǎng)度為D。AO（n2）BO（nlog2n）CO（n）DO（log2n）93．有一個(gè)有序表為{1，3，9，12，32，41，45，62，75，77，82，95，100}，當(dāng)折半查找值為82的結(jié)點(diǎn)時(shí)，C次比較后查找成功。A．11B5C4D894．二叉樹(shù)為二叉排序樹(shù)的充分必要條件是其任一結(jié)點(diǎn)的值均大于其左孩子的值、小于其右孩子的值。這種說(shuō)法B。A正確B錯(cuò)誤95．下面關(guān)于B樹(shù)和B＋樹(shù)的敘述中，不正確的結(jié)論是A。AB樹(shù)和B＋樹(shù)都能有效的支持順序查找BB樹(shù)和B＋樹(shù)都能有效的支持隨機(jī)查找CB樹(shù)和B＋樹(shù)都是平衡的多叉樹(shù)DB樹(shù)和B＋樹(shù)都可用于文件索引結(jié)構(gòu)96．以下說(shuō)法錯(cuò)誤的是B。A．散列法存儲(chǔ)的思想是由關(guān)鍵字值決定數(shù)據(jù)的存儲(chǔ)地址B．散列表的結(jié)點(diǎn)中只包含數(shù)據(jù)元素自身的信息，不包含指針。C．負(fù)載因子是散列表的一個(gè)重要參數(shù)，它反映了散列表的飽滿(mǎn)程度。D．散列表的查找效率主要取決于散列表構(gòu)造時(shí)選取的散列函數(shù)和處理沖突的方法。97．查找效率最高的二叉排序樹(shù)是C。A．所有結(jié)點(diǎn)的左子樹(shù)都為空的二叉排序樹(shù)。B．所有結(jié)點(diǎn)的右子樹(shù)都為空的二叉排序樹(shù)。C．平衡二叉樹(shù)。D．沒(méi)有左子樹(shù)的二叉排序樹(shù)。98．排序方法中，從未排序序列中依次取出元素與已排序序列中的元素進(jìn)行比較，將其放入已排序序列的正確位置上的方法，稱(chēng)為C。A．希爾排序B。冒泡排序C插入排序D。選擇排序99．在所有的排序方法中，關(guān)鍵字比較的次數(shù)與記錄的初始排列次序無(wú)關(guān)的是D。A．希爾排序B．冒泡排序C．直接插入排序D．直接選擇排序100．堆是一種有用的數(shù)據(jù)結(jié)構(gòu)。下列關(guān)鍵碼序列D是一個(gè)堆。A．94，31，53，23，16，72B．94，53，31，72，16，23C．16，53，23，94，31，72D．16，31，23，94，53，72101．堆排序是一種B排序。A．插入B．選擇C．交換D．歸并102．D在鏈表中進(jìn)行操作比在順序表中進(jìn)行操作效率高。A．順序查找B．折半查找C．分塊查找D．插入103．直接選擇排序的時(shí)間復(fù)雜度為D。（n為元素個(gè)數(shù)）A．O（n）B．O（log2n）C．O（nlog2n）D．O（n2）二、填空題。1．?dāng)?shù)據(jù)邏輯結(jié)構(gòu)包括線(xiàn)性結(jié)構(gòu)、樹(shù)形結(jié)構(gòu)和圖狀結(jié)構(gòu)三種類(lèi)型，樹(shù)形結(jié)構(gòu)和圖狀結(jié)構(gòu)合稱(chēng)非線(xiàn)性結(jié)構(gòu)。2．?dāng)?shù)據(jù)的邏輯結(jié)構(gòu)分為集合、線(xiàn)性結(jié)構(gòu)、樹(shù)形結(jié)構(gòu)和圖狀結(jié)構(gòu)4種。3．在線(xiàn)性結(jié)構(gòu)中，第一個(gè)結(jié)點(diǎn)沒(méi)有前驅(qū)結(jié)點(diǎn)，其余每個(gè)結(jié)點(diǎn)有且只有1個(gè)前驅(qū)結(jié)點(diǎn)；最后一個(gè)結(jié)點(diǎn)沒(méi)有后續(xù)結(jié)點(diǎn)，其余每個(gè)結(jié)點(diǎn)有且只有1個(gè)后續(xù)結(jié)點(diǎn)。4．線(xiàn)性結(jié)構(gòu)中元素之間存在一對(duì)一關(guān)系，樹(shù)形結(jié)構(gòu)中元素之間存在一對(duì)多關(guān)系，圖形結(jié)構(gòu)中元素之間存在多對(duì)多關(guān)系。5．在樹(shù)形結(jié)構(gòu)中，樹(shù)根結(jié)點(diǎn)沒(méi)有前驅(qū)結(jié)點(diǎn)，其余每個(gè)結(jié)點(diǎn)有且只有1個(gè)前驅(qū)結(jié)點(diǎn)；葉子結(jié)點(diǎn)沒(méi)有后續(xù)結(jié)點(diǎn)，其余每個(gè)結(jié)點(diǎn)的后續(xù)結(jié)點(diǎn)可以任意多個(gè)。6．?dāng)?shù)據(jù)結(jié)構(gòu)的基本存儲(chǔ)方法是順序、鏈?zhǔn)?、索引和散列存?chǔ)。7．衡量一個(gè)算法的優(yōu)劣主要考慮正確性、可讀性、健壯性和時(shí)間復(fù)雜度與空間復(fù)雜度。8．評(píng)估一個(gè)算法的優(yōu)劣，通常從時(shí)間復(fù)雜度和空間復(fù)雜度兩個(gè)方面考察。9．算法的5個(gè)重要特性是有窮性、確定性、可行性、輸入和輸出。10．在一個(gè)長(zhǎng)度為n的順序表中刪除第i個(gè)元素時(shí)，需向前移動(dòng)n－i－1個(gè)元素。11．在單鏈表中，要?jiǎng)h除某一指定的結(jié)點(diǎn)，必須找到該結(jié)點(diǎn)的前驅(qū)結(jié)點(diǎn)。12．在雙鏈表中，每個(gè)結(jié)點(diǎn)有兩個(gè)指針域，一個(gè)指向前驅(qū)結(jié)點(diǎn)，另一個(gè)指向后繼結(jié)點(diǎn)。13．在順序表中插入或刪除一個(gè)數(shù)據(jù)元素，需要平均移動(dòng)n個(gè)數(shù)據(jù)元素，移動(dòng)數(shù)據(jù)元素的個(gè)數(shù)與位置有關(guān)。14．當(dāng)線(xiàn)性表的元素總數(shù)基本穩(wěn)定，且很少進(jìn)行插入和刪除操作，但要求以最快的速度存取線(xiàn)性表的元素是，應(yīng)采用順序存儲(chǔ)結(jié)構(gòu)。15．根據(jù)線(xiàn)性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)中每一個(gè)結(jié)點(diǎn)包含的指針個(gè)數(shù)，將線(xiàn)性鏈表分成單鏈表和雙鏈表。16．順序存儲(chǔ)結(jié)構(gòu)是通過(guò)下標(biāo)表示元素之間的關(guān)系的；鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)是通過(guò)指針表示元素之間的關(guān)系的。17．帶頭結(jié)點(diǎn)的循環(huán)鏈表L中只有一個(gè)元素結(jié)點(diǎn)的條件是L－＞next－＞next＝L。18．棧是限定僅在表尾進(jìn)行插入或刪除操作的線(xiàn)性表，其運(yùn)算遵循后進(jìn)先出的原則。19．空串是零個(gè)字符的串，其長(zhǎng)度等于零。空白串是由一個(gè)或多個(gè)空格字符組成的串，其長(zhǎng)度等于其包含的空格個(gè)數(shù)。20．組成串的數(shù)據(jù)元素只能是單個(gè)字符。21．一個(gè)字符串中任意個(gè)連續(xù)字符構(gòu)成的部分稱(chēng)為該串的子串。22．子串”str”在主串”datastructure”中的位置是5。23．二維數(shù)組M的每個(gè)元素是6個(gè)字符組成的串，行下標(biāo)i的范圍從0到8，列下標(biāo)j的范圍從1到10，則存放M至少需要540個(gè)字節(jié)；M的第8列和第5行共占108個(gè)字節(jié)。24．稀疏矩陣一般的壓縮存儲(chǔ)方法有兩種，即三元組表和十字鏈表。25．廣義表（（a），（（b），c），（（（d））））的長(zhǎng)度是3，深度是4。26．在一棵二叉樹(shù)中，度為零的結(jié)點(diǎn)的個(gè)數(shù)為n0，度為2的結(jié)點(diǎn)的個(gè)數(shù)為n2，則有n0＝n2＋1。27．在有n個(gè)結(jié)點(diǎn)的二叉鏈表中，空鏈域的個(gè)數(shù)為_(kāi)_n＋1__。28．一棵有n個(gè)葉子結(jié)點(diǎn)的哈夫曼樹(shù)共有__2n－1_個(gè)結(jié)點(diǎn)。29．深度為5的二叉樹(shù)至多有31個(gè)結(jié)點(diǎn)。30．若某二叉樹(shù)有20個(gè)葉子結(jié)點(diǎn)，有30個(gè)結(jié)點(diǎn)僅有一個(gè)孩子，則該二叉樹(shù)的總結(jié)點(diǎn)個(gè)數(shù)為69。31．某二叉樹(shù)的前序遍歷序列是abdgcefh，中序序列是dgbaechf，其后序序列為gdbehfca。32．線(xiàn)索二叉樹(shù)的左線(xiàn)索指向其遍歷序列中的前驅(qū)，右線(xiàn)索指向其遍歷序列中的后繼。33．在各種查找方法中，平均查找長(zhǎng)度與結(jié)點(diǎn)個(gè)數(shù)n無(wú)關(guān)的查找方法是散列查找法。34．在分塊索引查找方法中，首先查找索引表，然后查找相應(yīng)的塊表。35．一個(gè)無(wú)序序列可以通過(guò)構(gòu)造一棵二叉排序樹(shù)而變成一個(gè)有序序列，構(gòu)造樹(shù)的過(guò)程即為對(duì)無(wú)序序列進(jìn)行排序的過(guò)程。36．具有10個(gè)頂點(diǎn)的無(wú)向圖，邊的總數(shù)最多為_(kāi)_45__。37．已知圖G的鄰接表如圖所示，其從頂點(diǎn)v1出發(fā)的深度優(yōu)先搜索序列為_(kāi)v1v2v3v6v5v4_，其從頂點(diǎn)v1出發(fā)的廣度優(yōu)先搜索序列為_(kāi)v1v2v5v4v3v6__。38．索引是為了加快檢索速度而引進(jìn)的一種數(shù)據(jù)結(jié)構(gòu)。一個(gè)索引隸屬于某個(gè)數(shù)據(jù)記錄集，它由若干索引項(xiàng)組成，索引項(xiàng)的結(jié)構(gòu)為關(guān)鍵字和關(guān)鍵字對(duì)應(yīng)記錄的地址。39．Prim算法生成一個(gè)最小生成樹(shù)每一步選擇都要滿(mǎn)足邊的總數(shù)不超過(guò)n－1，當(dāng)前選擇的邊的權(quán)值是候選邊中最小的，選中的邊加入樹(shù)中不產(chǎn)生回路三項(xiàng)原則。40．在一棵m階B樹(shù)中，除根結(jié)點(diǎn)外，每個(gè)結(jié)點(diǎn)最多有m棵子樹(shù)，最少有m/2棵子樹(shù)。三、判斷題。1．在決定選取何種存儲(chǔ)結(jié)構(gòu)時(shí)，一般不考慮各結(jié)點(diǎn)的值如何。（√）2．抽象數(shù)據(jù)類(lèi)型（ADT）包括定義和實(shí)現(xiàn)兩方面，其中定義是獨(dú)立于實(shí)現(xiàn)的，定義僅給出一個(gè)ADT的邏輯特性，不必考慮如何在計(jì)算機(jī)中實(shí)現(xiàn)。（√）3．抽象數(shù)據(jù)類(lèi)型與計(jì)算機(jī)內(nèi)部表示和實(shí)現(xiàn)無(wú)關(guān)。（√）4．順序存儲(chǔ)方式插入和刪除時(shí)效率太低，因此它不如鏈?zhǔn)酱鎯?chǔ)方式好。（×）5．線(xiàn)性表采用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)時(shí)，結(jié)點(diǎn)和結(jié)點(diǎn)內(nèi)部的存儲(chǔ)空間可以是不連續(xù)的。（×）6．