【正文】 關(guān)系，樹(shù)形結(jié)構(gòu)中元素之間存在 一對(duì)多 關(guān)系，圖形結(jié)構(gòu)中元素之間存在 多對(duì)多 關(guān)系。（n 為元素個(gè)數(shù)）A．O（n) B．O(log2n) C．O(nlog2n) D． O(n2) 二、填空題。下列關(guān)鍵碼序列 D 是一個(gè)堆。A．希爾排序 B。B．所有結(jié)點(diǎn)的右子樹(shù)都為空的二叉排序樹(shù)。C．負(fù)載因子是散列表的一個(gè)重要參數(shù)，它反映了散列表的飽滿(mǎn)程度。這種說(shuō)法 B 。A 散列存儲(chǔ) B 順序存儲(chǔ)或鏈?zhǔn)酱鎯?chǔ) C 壓縮存儲(chǔ) D 索引存儲(chǔ)91．對(duì)線(xiàn)性表進(jìn)行折半查找時(shí)，要求線(xiàn)性表必須 B 。A．先序遍歷 B．中序遍歷 C．后序遍歷 D．按層遍歷87．具有n 個(gè)結(jié)點(diǎn)的連通圖至少有 A 條邊。A．1/2 B 1 C 2 D 482．某二叉樹(shù)結(jié)點(diǎn)的中序序列為ABCDEFG，后序序列為BDCAFGE，則其左子樹(shù)中結(jié)點(diǎn)數(shù)目為： C A．3 　 B．2 C．4 D．583．已知一算術(shù)表達(dá)式的中綴形式為A＋B *C–D/E，后綴形式為ABC *+DE/–，其前綴形式為A．mn B．mn1 C．n+1 D．不能確定78．若一棵二叉樹(shù)具有10個(gè)度為2的結(jié)點(diǎn)，5個(gè)度為1的結(jié)點(diǎn)，則度為0的結(jié)點(diǎn)的個(gè)數(shù)是 B 。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．二維數(shù)組和三維數(shù)組 B． 三元組和散列C．三元組和十字鏈表 D． 散列和十字鏈表71．樹(shù)最適合用來(lái)表示 C 。A．20 B． 66 C．18 000 D．3367．?dāng)?shù)組A[0 … 4，1 … 3，5 …7]中含有的元素個(gè)數(shù)是 A 。A．SA＋141 B． SA＋180 C．SA＋222 D．SA＋22564．若聲明一個(gè)浮點(diǎn)數(shù)數(shù)組如下： froat average[]=new float[30]。A．串中所含不同字母的個(gè)數(shù) B．串中所含字符的個(gè)數(shù) C．串中所含不同字符的個(gè)數(shù) D．串中所含非空格字符的個(gè)數(shù)60．串是一種特殊的線(xiàn)性表，其特殊性體現(xiàn)在 B 。A．最早插入隊(duì)列中的元素總是最后被刪除 B．當(dāng)同時(shí)進(jìn)行插入、刪除操作時(shí)，總是插入操作優(yōu)先C．每當(dāng)有刪除操作時(shí)，總是要先做一次插入操作D．每次從隊(duì)列中刪除的總是最早插入的元素56．和順序棧相比，鏈棧有一個(gè)比較明顯的優(yōu)勢(shì)是 A 。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 。hnext=s B．snext=hA．4，3，2，1 B．1，2，3，4C．1，4，3，2 D．3，2，4，146．判定一個(gè)循環(huán)隊(duì)列qu（最多元素為MaxSize）為空的條件是 C 。 A．A,B,C,D,E B．B,C,D,E,A C．E,A,B,C,D D．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．先進(jìn)先出 B．先進(jìn)后出38．棧和隊(duì)列的共同點(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．訪問(wèn)第i（1=i=n）個(gè)結(jié)點(diǎn)和求第i個(gè)結(jié)點(diǎn)的直接前驅(qū)（1i=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線(xiàn)性表采用順序存儲(chǔ)，必須占用一片連續(xù)的存儲(chǔ)單元B線(xiàn)性表采用順序存儲(chǔ)，便于進(jìn)行插入和刪除操作。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．單鏈表 B．雙鏈表 C．單循環(huán)鏈表 D． 順序表21．在一個(gè)具有n個(gè)結(jié)點(diǎn)的有序單鏈表中插入一個(gè)新結(jié)點(diǎn)并仍然保持有序的時(shí)間復(fù)雜度是 B 。A．單鏈表 B．給出表頭指針的單循環(huán)鏈表 C．雙鏈表 D．帶頭結(jié)點(diǎn)的雙循環(huán)鏈表17．需要分配較大空間，插入和刪除不需要移動(dòng)元素的線(xiàn)性表，其存儲(chǔ)結(jié)構(gòu)是 B 。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 。j++) A[i][j] ＝ 0。for( i =0。jn。 s =0。A．各結(jié)點(diǎn)的值如何 B．結(jié)點(diǎn)個(gè)數(shù)的多少C．對(duì)數(shù)據(jù)有哪些運(yùn)算 D．所用的編程語(yǔ)言實(shí)現(xiàn)這種結(jié)構(gòu)是否方便。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 。1．在數(shù)據(jù)結(jié)構(gòu)中，從邏輯上可以把數(shù)據(jù)結(jié)構(gòu)分為 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 。（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) 。 i++) for(j=0。9．下面程序段的時(shí)間復(fù)雜度是 O(n*m) 。jm。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 。A．head == NULL B headnext ==NULL C．headnext ==head D head!=NULL16．若某表最常用的操作是在最后一個(gè)結(jié)點(diǎn)之后插入一個(gè)結(jié)點(diǎn)或刪除最后一個(gè)結(jié)點(diǎn)，則采用 D 存儲(chǔ)方式最節(jié)省運(yùn)算時(shí)間。A．pprior = s；snext = p；ppriornext = s；sprior = ppriorB．pprior = s；ppriornext = s；snext = p；sprior = ppriorC．snext = p；sprior = pprior；pprior = s；ppriornext = sD．snext = p；sprior = pprior；ppriornext = s；pprior = s20．如果最常用的操作是取第i個(gè)結(jié)點(diǎn)及其前驅(qū)，則采用 D 存儲(chǔ)方式最節(jié)省時(shí)間。A．插入、刪除操作更簡(jiǎn)單 B．可以進(jìn)行隨機(jī)訪問(wèn)C．可以省略表頭指針或表尾指針D．順序訪問(wèn)相鄰結(jié)點(diǎn)更靈活24．如果對(duì)線(xiàn)性表的操作只有兩種，即刪除第一個(gè)元素，在最后一個(gè)元素的后面插入新元素，則最好使用 B 。A插入運(yùn)算方便 B可方便地用于各種邏輯結(jié)構(gòu)的存儲(chǔ)表示C存儲(chǔ)密度大 D刪除運(yùn)算方便28．下面關(guān)于線(xiàn)性表的敘述中，錯(cuò)誤的是哪一個(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．O(0) B．O(1) C．O