數(shù)據(jù)結(jié)構(gòu)選擇[復(fù)制]1．從邏輯上可以把數(shù)據(jù)結(jié)構(gòu)分為（）兩大類[單選題]*A、動(dòng)態(tài)結(jié)構(gòu)、靜態(tài)結(jié)構(gòu)B、順序結(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)2．算法分析的兩個(gè)主要方面是（）[單選題]*A、空間復(fù)雜度和時(shí)間復(fù)雜度(正確答案)B、正確性和簡(jiǎn)明性C、可讀性和文檔性D、數(shù)據(jù)復(fù)雜性和程序復(fù)雜性3．算法的時(shí)間復(fù)雜度是指（）[單選題]*A、執(zhí)行算法程序所需要的時(shí)間B、算法執(zhí)行過(guò)程中所需要的基本運(yùn)算次數(shù)(正確答案)C、算法程序的長(zhǎng)度D、算法程序中的指令條數(shù)4．?dāng)?shù)據(jù)在計(jì)算機(jī)存儲(chǔ)器內(nèi)表示時(shí)，物理地址與邏輯地址不相同的，稱為（）[單選題]*A、存儲(chǔ)結(jié)構(gòu)B、邏輯結(jié)構(gòu)C、鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)(正確答案)D、順序存儲(chǔ)結(jié)構(gòu)5．下列屬于線性數(shù)據(jù)結(jié)構(gòu)的是（）[單選題]*A、隊(duì)列(正確答案)B、樹C、圖D、不確定6．算法的空間復(fù)雜度是指（）[單選題]*A、執(zhí)行算法程序所占的存儲(chǔ)空間B、算法程序中的指令條數(shù)C、算法程序的長(zhǎng)度D、算法執(zhí)行過(guò)程中所需要的存儲(chǔ)空間(正確答案)7．以下屬于邏輯結(jié)構(gòu)的是（）[單選題]*A、順序表//ABD物理結(jié)構(gòu)//B、哈希表C、有序表(正確答案)D、單鏈表8．算法分析的目的是（）[單選題]*A、找出數(shù)據(jù)結(jié)構(gòu)的合理性B、研究算法中的輸入和輸出關(guān)系C、分析算法的效率以求改進(jìn)(正確答案)D、分析算法的易懂性和文檔性1．帶頭結(jié)點(diǎn)的單鏈表Head為空的判定條件是（）。[單選題]*A、Head==NULLB、Head->next==NULL(正確答案)C、Head->next==Head2．以下說(shuō)法錯(cuò)誤的是（）。[單選題]*A、對(duì)于線性表來(lái)說(shuō)，查找定位運(yùn)算在順序表和單鏈表上的量級(jí)均為O(n)B、讀表元運(yùn)算在順序表上只需常數(shù)時(shí)間O(1)便可實(shí)現(xiàn)，因此順序表是一種隨機(jī)存取結(jié)構(gòu)C、在鏈表上實(shí)現(xiàn)讀表元運(yùn)算的平均時(shí)間復(fù)雜性為O(1)哦（n）(正確答案)D、插入、刪除操作在鏈表上的實(shí)現(xiàn)可在O(n)時(shí)間內(nèi)完成3．以下說(shuō)法正確的是（）。[單選題]*A、在單鏈表中，任何兩個(gè)元素的存儲(chǔ)位置之間都有固定的聯(lián)系，因此可以從頭結(jié)點(diǎn)開始，查找任何一個(gè)元素(正確答案)B、在單鏈表中，要取得某個(gè)元素，只要知道該元素的指針即可，因此，單鏈表是隨機(jī)存取的存儲(chǔ)結(jié)構(gòu)（單鏈表是一種鏈?zhǔn)酱嫒〉臄?shù)據(jù)結(jié)構(gòu)）C、順序存儲(chǔ)方式只能用于存儲(chǔ)線性結(jié)構(gòu)D、D、順序存儲(chǔ)方式的優(yōu)點(diǎn)是存儲(chǔ)密度大，且插入、刪除運(yùn)算效率高（效率低）4．鏈表不具有的特點(diǎn)是（）。[單選題]*A、可隨機(jī)訪問(wèn)任一個(gè)元素(正確答案)B、插入刪除不需要移動(dòng)元素C、不必事先估計(jì)存儲(chǔ)空間D、所需空間及線性表長(zhǎng)度成正比5．線性表若采用鏈表存儲(chǔ)結(jié)構(gòu)時(shí)，要求內(nèi)存中可用存儲(chǔ)單元的地址（）。[單選題]*A、必須是聯(lián)系的B、部分地址必須是連續(xù)的C、一定是不連續(xù)的D、連續(xù)不連續(xù)都可以(正確答案)6．單鏈表中，增加頭結(jié)點(diǎn)的目的是為了（）。[單選題]*A、使單鏈表至少有一個(gè)結(jié)點(diǎn)B、標(biāo)示表結(jié)點(diǎn)中首結(jié)點(diǎn)的位置C、方便運(yùn)算的實(shí)現(xiàn)(正確答案)D、說(shuō)明單鏈表是線性表的鏈?zhǔn)酱鎯?chǔ)實(shí)現(xiàn)1．對(duì)于順序存儲(chǔ)的有序表(5,12,20,26,37,42,46,50,64)，若采用折半查找，則查找元素26的比較次數(shù)為（）。[單選題]*A、2B、3C、4(正確答案)D、52．若查找每個(gè)元素的概率相等，則在長(zhǎng)度為n的順序表上查找任一元素的平均查找長(zhǎng)度為（）。[單選題]*A、nB、n+1C、(n-1)/2D、(n+1)/2(正確答案)3．具有12個(gè)關(guān)鍵字的有序表，折半查找的平均查找長(zhǎng)度為（）。[單選題]*A、3.1(正確答案)B、4C、2.5D、54．從具有n個(gè)結(jié)點(diǎn)的二叉排序樹中查找一個(gè)元素時(shí)，在平均情況下的時(shí)間復(fù)雜度大致為（）。[單選題]*A、O(n)B、O(1)C、O(log2n)(正確答案)D、O(n2)5．對(duì)具有n個(gè)元素的有序表采用折半查找，則算法的時(shí)間復(fù)雜度為（）。[單選題]*A、O(n)B、O(n2)C、O(1)D、O(log2n)(正確答案)6．下面關(guān)于二分查找的敘述正確的是（）。[單選題]*A、表必須有序，表可以順序方式存儲(chǔ)，也可以鏈?zhǔn)椒绞酱鎯?chǔ)B、表必須有序且表中數(shù)據(jù)必須是整型、實(shí)型或字符型C、表必須有序，而且只能從小到大排序D、表必須有序，且表只能以順序方式存儲(chǔ)(正確答案)7．分別以下列序列構(gòu)造二叉排序樹，與用其它三個(gè)序列所構(gòu)造的結(jié)果不同的是（）。[單選題]*A、(100,80,90,60,120,110,130)B、(100,120,110,130,80,60,90)C、(100,60,80,90,120,110,130)(正確答案)D、(100,80,60,90,120,130,110)8．對(duì)于長(zhǎng)度為18的順序存儲(chǔ)的有序表，若采用折半查找，則查找第15個(gè)元素的比較次數(shù)為（）。[單選題]*A、3B、4(正確答案)C、5D、61．下面敘述正確的是（）。[單選題]*A、二叉樹是特殊的樹B、二叉樹等價(jià)于度為2的樹C、完全二叉樹必為滿二叉樹D、二叉樹的左右子樹有次序之分(正確答案)2．由分別帶權(quán)為9、2、5、7的四個(gè)葉子結(jié)點(diǎn)構(gòu)造一棵霍夫曼樹，該樹的帶權(quán)路徑長(zhǎng)度為（）。[單選題]*A、23B、37C、44(正確答案)D、463．在一棵二叉樹上第4層的結(jié)點(diǎn)數(shù)最多為（）。[單選題]*A、2B、4C、6D、8(正確答案)4．已知一棵完全二叉樹的結(jié)點(diǎn)總數(shù)為9個(gè)，則最后一層的結(jié)點(diǎn)數(shù)為（）。[單選題]*A、1B、2(正確答案)C、3D、45．線索二叉樹是一種（）結(jié)構(gòu)。[單選題]*A、邏輯B、邏輯和存儲(chǔ)C、物理(正確答案)D、線性1．在對(duì)n個(gè)元素進(jìn)行快速排序的過(guò)程中，最好情況下需要進(jìn)行（）趟。[單選題]*A、n(正確答案)B、n/2C、log2nD、2n2．若一個(gè)元素序列基本有序，則選用（）方法較快。[單選題]*A、直接插入排序(正確答案)B、簡(jiǎn)單選擇排序C、堆排序D、快速排序3．假定對(duì)元素序列(7,3,5,9,1,12)進(jìn)行堆排序，并且采用小根堆，則由初始數(shù)據(jù)構(gòu)成的初始堆為（）。[單選題]*A、1,3,5,7,9,12(正確答案)B、1,3,5,9,7,12C、1,5,3,7,9,12D、1,5,3,9,12,74．一組記錄的關(guān)鍵碼為(46,79,56,38,40,84)，則利用快速排序的方法，以第一個(gè)記錄為基準(zhǔn)得到的一次劃分結(jié)果為（）。[單選題]*A、(38,40,46,56,79,84)(正確答案)B、(40,38,46,79,56,84)C、(40,38,46,56,79,84)D、(40,38,46,84,56,79)5．假定一個(gè)初始堆為(1,5,3,9,12,7,15,10)，則進(jìn)行第一趟堆排序后得到的結(jié)果為（）。[單選題]*A、3,5,7,9,12,10,15,1(正確答案)B、3,5,9,7,12,10,12,1C、3,7,5,9,12,10,15,1D、3,5,7,12,9,10,15,11．在一個(gè)具有n個(gè)結(jié)點(diǎn)的有序單鏈表中插入一個(gè)新結(jié)點(diǎn)，并保持該表有序，其時(shí)間復(fù)雜度為（）。[單選題]*A、O(1)B、O(n)(正確答案)C、O(n2)D、O(log2n)2．在一個(gè)長(zhǎng)度為n的順序表中向第i個(gè)元素（0<i<n+1）之前插入一個(gè)新元素時(shí)，需向后移動(dòng)（）個(gè)元素。[單選題]*A、n-iB、n-i+1(正確答案)C、n-i-1D、i3．若線性表最常用的操作是存取第i個(gè)元素及其前驅(qū)的值，則采用（）存儲(chǔ)方式節(jié)省時(shí)間。[單選題]*A、單鏈表B、雙向鏈表C、單循環(huán)鏈表D、順序表(正確答案)4．線性表的順序存儲(chǔ)結(jié)構(gòu)是一種（）的存儲(chǔ)結(jié)構(gòu)。[單選題]*A、隨機(jī)存取(正確答案)B、順序存取C、索引存取D、散列存取5．在一個(gè)長(zhǎng)度為n的順序表中刪除第i個(gè)元素（0<=i<=n）時(shí)，需向前移動(dòng)（）個(gè)元素。[單選題]*A、n-i(正確答案)B、n-i+1C、n-i-1D、i1．若一個(gè)圖的邊集為{(A,B),(A,C),(B,D),(C,F),(D,E),(D,F)}，則從頂點(diǎn)A開始對(duì)該圖進(jìn)行深度優(yōu)先搜索，得到的頂點(diǎn)序列可能為（）。[單選題]*A、A,B,C,F,D,E(正確答案)B、A,C,F,D,E,BC、A,B,D,C,F,ED、A,B,D,F,E,C2．若一個(gè)圖的邊集為{(A,B),(A,C),(B,D),(C,F),(D,E),(D,F)}，則從頂點(diǎn)A開始對(duì)該圖進(jìn)行廣度優(yōu)先遍歷，得到的頂點(diǎn)序列可能為（）。[單選題]*A、A,B,C,D,E,FB、A,B,C,F,D,EC、A,B,D,C,E,F(正確答案)D、A,C,B,F,D,E3．由一個(gè)具有n個(gè)頂點(diǎn)的連通圖生成的最小生成樹中，具有（）條邊。[單選題]*A、nB、n-1(正確答案)C、n+1D、2×n4．已知一個(gè)有向圖的邊集為{<a,b>,<a,c>,<a,d>,<b,d>,<b,e>,<d,e>}，則由該圖產(chǎn)生的一種可能的拓?fù)湫蛄袨椋ǎ?。[單選題]*A、a,b,c,d,e(正確答案)B、a,c,d,e,bC、a,c,b,e,dD、a,c,d,b,e1．設(shè)指針p指向雙向鏈表的某一結(jié)點(diǎn)，則雙向鏈表結(jié)構(gòu)的對(duì)稱性可用（）式來(lái)刻畫。[單選題]*A、p->prior->next==p->next->nextB、p->prior->prior==p->next->priorC、p->prior->next==p->next->prior(正確答案)D、p->next->next==p->prior->prior2．空的單循環(huán)鏈表L的尾結(jié)點(diǎn)*p，滿足（）。[單選題]*A、P->next==NULLB、P==NULLC、P->next=L(正確答案)D、p>next=head->next3．循環(huán)鏈表的主要優(yōu)點(diǎn)是（）。[單選題]*A、不需要頭指針B、已知某個(gè)結(jié)點(diǎn)的位置后，能夠容易找到它的直接前驅(qū)C、從表中任一結(jié)點(diǎn)出發(fā)都能掃描到整個(gè)鏈表(正確答案)D、在進(jìn)行插入、刪除運(yùn)算時(shí)，能更好地保證鏈表不斷開1．一個(gè)隊(duì)列的入隊(duì)列順序是1，2，3，4，則隊(duì)列的輸出序列是（）[單選題]*A、4，3，2，1(正確答案)B、1，2，3，4C、1，4，3，2D、3，2，4，12．循環(huán)隊(duì)列的隊(duì)滿條件為（）。[單選題]*A、(sq.rear+1)%maxsize==(sq.front+1)%maxsizeB、(sq.rear+1)%maxsize==sq.front+1C、sq.(rear+1)%maxsize==sq.front(正確答案)D、sq.rear==sq.front3．隊(duì)列的操作原則是（）。[單選題]*A、先進(jìn)先出(正確答案)B、后進(jìn)先出C、先進(jìn)后出D、不分順序4．設(shè)計(jì)一個(gè)判別表達(dá)式中左、右括號(hào)是否配對(duì)出現(xiàn)的算法，采用（）數(shù)據(jù)結(jié)構(gòu)最佳。[單選題]*A、線性標(biāo)的順序存儲(chǔ)結(jié)構(gòu)B、棧(正確答案)C、隊(duì)列D、線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)5．循環(huán)隊(duì)列A[0…m-1]存放其元素值，用front和rear分別表示隊(duì)頭和隊(duì)尾，則當(dāng)前隊(duì)列中的元素?cái)?shù)是（）。[單選題]*A、(rear-front+m)%m(正確答案)B、rear-front+1C、rear-front-1D、rear-front6．循環(huán)隊(duì)列的出隊(duì)操作為（c）。[單選題]*A、sq.front=(sq.front+1)%maxsize(正確答案)B、sq.front=sq.front+1C、sq.rear=(sq.rear+1)%maxsizeD、sq.rear=sq.rear+17．棧的操作原則是（c）。[單選題]*A、先進(jìn)先出(正確答案)B、后進(jìn)先出C、先進(jìn)后出D、不分順序8．有六個(gè)元素6,