數(shù)據(jù)結(jié)構(gòu)選擇附有答案

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