算法與數(shù)據(jù)結(jié)構(gòu)選擇題

三、選擇題：（A）1.數(shù)據(jù)結(jié)構(gòu)通常是研究數(shù)據(jù)的及它們之間的聯(lián)系。A存儲和邏輯結(jié)構(gòu)B存儲和抽象C理想和抽象D理想與邏輯（C）2?在堆棧中存取數(shù)據(jù)的原則是。A先進(jìn)先出B后進(jìn)先出C先進(jìn)后出D隨意進(jìn)出TOC\o"1-5"\h\z（A）3.將一棵有100個結(jié)點(diǎn)的完全二叉樹從上到下，從左到右依次對結(jié)點(diǎn)進(jìn)行編號，根結(jié)點(diǎn)的編號為1，則編號為49的結(jié)點(diǎn)的左孩子的編號為。98B.99C.50D.48（D）4.對于如圖所示二叉樹采用中根遍歷，正確的遍歷序列應(yīng)為（）ABCDEFB.ABECDFB.CDFBEAD.CBDAEFD.TOC\o"1-5"\h\z（D）5.設(shè)有100個元素，用折半查找法進(jìn)行查找時，最大比較次數(shù)是。25B.50C.10D.7（C）6.快速排序在情況下最易發(fā)揮其長處。被排序數(shù)據(jù)中含有多個相同排序碼B?被排序數(shù)據(jù)已基本有序B.被排序數(shù)據(jù)完全無序D?被排序數(shù)據(jù)中最大值和最小值相差懸殊D.（B）7.由兩個棧共享一個向量空間的好處是。A減少存取時間，降低下溢發(fā)生的機(jī)率B節(jié)省存儲空間，降低上溢發(fā)生的機(jī)率C減少存取時間，降低上溢發(fā)生的機(jī)率D節(jié)省存儲空間，降低下溢發(fā)生的機(jī)率A.P->linkA.P->link==NULL；B.p==NULL；A.P->linkA.P->link==NULL；B.p==NULL；A.A.極小連通子圖B.極小子圖B)8.某二叉樹的前序和后序序列正好相反，則該二叉樹一定是的二叉樹A空或者只有一個結(jié)點(diǎn)B高度等于其結(jié)點(diǎn)數(shù)C任一結(jié)點(diǎn)無左孩子D任一結(jié)點(diǎn)無右孩子(D)9?設(shè)散列表長m=14，散列函數(shù)H(K)二K%11，已知表中已有4個結(jié)點(diǎn)：r(15)二4;TOC\o"1-5"\h\zr(38)=5;r(61)=6;r(84)=7,其他地址為空，如用二次探測再散列處理沖突，關(guān)鍵字為49的結(jié)點(diǎn)地址是。A8B3C5D9(D)10.在含有n個項點(diǎn)有e條邊的無向圖的鄰接矩陣中，零元素的個數(shù)為。eB.2eC.n2-eD.n2-2e(A)11.圖的深度優(yōu)先遍歷類似于二叉樹的。A?先序遍歷B?中序遍歷C?后序遍歷D?層次遍歷(C)12.設(shè)長度為n的鏈隊列用單循環(huán)鏈表表示，若只設(shè)頭指針，則入隊操作的時間復(fù)雜度為。O(1)B.O(log2n)0(n)D.0(n2)(C)13.堆的形狀是一棵。A.二叉排序樹B.滿二叉樹完全二叉樹D.平衡二叉樹(A)14.一個無向連連通圖的生成樹是含有該連通圖的全部項點(diǎn)的。B.極大連通子圖D?極大子圖D.（B）15.一個序列中有10000個元素，若只想得到其中前10個最小元素，最好采用方法快速排序B.堆排序插入排序D.二路歸并排序D.（B）16.設(shè)單鏈表中結(jié)點(diǎn)的結(jié)構(gòu)為Typedefstructnode{file://鏈表結(jié)點(diǎn)定義ElemTypedata；file://數(shù)據(jù)Structnode*Link；file://結(jié)點(diǎn)后繼指針}ListNode；已知指針p所指結(jié)點(diǎn)不是尾結(jié)點(diǎn)，若在*p之后插入結(jié)點(diǎn)*s，則應(yīng)執(zhí)行下列哪一個操作。S->link=p；p->link=s；B.s->link=p->link；p->link=s；S->link=p->link；p=s；D.p->link=s；s->link=p；（C）17.設(shè)單鏈表中結(jié)點(diǎn)的結(jié)構(gòu)為Typedefstructnode{file://鏈表結(jié)點(diǎn)定義ElemTypedata；file://數(shù)據(jù)Structnode*Link；file://結(jié)點(diǎn)后繼指針}ListNode；非空的循環(huán)單鏈表first的尾結(jié)點(diǎn)（由p所指向）滿足：A.470A.470B.471A.470A.470B.471B.P->linkB.P->link==first；D.p==first；(A)18.計算機(jī)識別、存儲和加工處理的對象被統(tǒng)稱為A?數(shù)據(jù)B?數(shù)據(jù)元素C?數(shù)據(jù)結(jié)構(gòu)D.數(shù)據(jù)類型(B)19.在具有n個結(jié)點(diǎn)的有序單鏈表中插入一個新結(jié)點(diǎn)并使鏈表仍然有序的時間復(fù)雜度是A?O⑴B.O(n)O(nlogn)D.O(n2)D.(D)20?隊和棧的主要區(qū)別是邏輯結(jié)構(gòu)不同B.存儲結(jié)構(gòu)不同B.所包含的運(yùn)算個數(shù)不同D.限定插入和刪除的位置不同D.(D)21.鏈棧與順序棧相比，比較明顯的優(yōu)點(diǎn)是插入操作更加方便B.刪除操作更加方便C.不會出現(xiàn)下溢的情況D.不會出現(xiàn)上溢的情況(C)22.在目標(biāo)串T[0…n-1]="xwxxyxy"中，對模式串p[0…m-1]="xy"進(jìn)行子串定位操作的結(jié)果0B.2C.3D.5(B)23?已知廣義表的表頭為A,表尾為(B,C),則此廣義表為(A,(B,C))B.(A,B,C)C.(A,B,C)D.((A,B,C))(C)24.二維數(shù)組A按行順序存儲，其中每個元素占1個存儲單元。若A[1][1]的存儲地址為420,A[3][3]的存儲地址為446,則A[5][5]的存儲地址為

C.472D.473（C）25．二叉樹中第5層上的結(jié)點(diǎn)個數(shù)最多為8B.15C.16D.32（D）26．如果某圖的鄰接矩陣是對角線元素均為零的上三角矩陣，則此圖是A?有向完全圖B.連通圖強(qiáng)連通圖D.有向無環(huán)圖D.（D）27?對n個關(guān)鍵字的序列進(jìn)行快速排序，平均情況下的空間復(fù)雜度為O（1）B.O（logn）C.O（n）D.O（nlogn）（D）28?對于哈希函數(shù)H（key）二key%13，被稱為同義詞的關(guān)鍵字是A?35和41B.23和39C.15和44D.25和51B、48D、53（DB、48D、53A、24B、C、72（C）30?對包含N個元素的散列表進(jìn)行檢索，平均檢索長度A、B、C、DA、B、C、D、（A不直接依賴于ND、上述三者都不是31.向堆中插入一個元素的時間復(fù)雜度為A、O(log2n)A、O(log2n)B、O(n)BB、O(1)D、O(nlog2n)BB、O(1)D、O(nlog2n)(A)32．下面關(guān)于圖的存儲的敘述中，哪一個是正確的。A?用相鄰矩陣法存儲圖，占用的存儲空間數(shù)只與圖中結(jié)點(diǎn)個數(shù)有關(guān),而與邊數(shù)無關(guān)B．C?用相鄰矩陣法存儲圖，占用的存儲空間數(shù)只與圖中邊數(shù)有關(guān)，而與結(jié)點(diǎn)個數(shù)無關(guān)D．C.用鄰接表法存儲圖，占用的存儲空間數(shù)只與圖中結(jié)點(diǎn)個數(shù)有關(guān)，而與邊數(shù)無關(guān)用鄰接表法存儲圖，占用的存儲空間數(shù)只與圖中邊數(shù)有關(guān)，而與結(jié)點(diǎn)個數(shù)無關(guān)F．(D)33?輸入序列為(A,B,C,D),不可能得到的輸出序列是.(A,B,C,D)B.(D,C,B,A)C.(A,C,D,B)D.(C,A,B,D)(A)34.在長度為n的順序存儲的線性表中，刪除第i個元素(iWiWn)時，需要從前向后依次前移個元素。A、n-iB、n-i+1C、n-i-1D、i(D)35.設(shè)一個廣義表中結(jié)點(diǎn)的個數(shù)為n,則求廣義表深度算法的時間復(fù)雜度為—。A、O(1)B、O(n)B、C、O(n2)D、O(log2n)D、(D)36.假定一個順序隊列的隊首和隊尾指針分別為f和r,則判斷隊空的條件為A、f+1==rB、r+1==fB、C、f==0D、f==rD、(B)37.從堆中刪除一個元素的時間復(fù)雜以為____。A、O(1)B、O(log2n)B、C、O(n)D、O(nlog2n)D、(B)38．若需要利用形參直接訪問實(shí)參，則應(yīng)把形參變量說明為參數(shù)。指針B.引用B.C值D?變量(D)39.在一個單鏈表HL中，若要在指針q所指結(jié)點(diǎn)的后面插入一個由指針p所指向的結(jié)點(diǎn)，則執(zhí)行。Q—>next二p—>next；p—>next二q；C.q—>next二p—>next；p—>next二q；P—>next=q—>next；q=p；D.p—>next=q—>next；q—>next=p；(A)40.在—個順序隊列中，隊首指針指向隊首元素的位置。前一"個B?后一"個B.當(dāng)前D?最后—個D.41?向二叉搜索樹中插入一個元素時，其時間復(fù)雜度大致力—。AO(1)BO(1og2n)CO(n)DO(nlog2n)(D)42.算法指的是計算機(jī)程序B.解決問題的計算方法排序算法D.解決問題的有限運(yùn)算序列D.(B)43.線性表采用鏈?zhǔn)酱鎯r，結(jié)點(diǎn)的存儲地址必須是不連續(xù)的B.連續(xù)與否均可必須是連續(xù)的D.和頭結(jié)點(diǎn)的存儲地址相連續(xù)D.(C)44.將長充為n的單鏈表鏈接在長度為m的單鏈表之后的算法的時間復(fù)雜度為O(1)O(n)O(1)O(n)C.OC.O（m）D.O（m+n）C.OC.O（m）D.O（m+n）（B）45.由兩個棧共享一個向量空間的好處是：減少存取時間，降低下溢發(fā)生的機(jī)率B.節(jié)省存儲空間，降低上溢發(fā)生的機(jī)率B.減少存取時間，降低上溢發(fā)生的機(jī)率D.節(jié)省存儲空間，降低下溢發(fā)生的機(jī)率D.（D）46.設(shè)數(shù)組DatA[m]作為循環(huán)隊列SQ的存儲空間，front為隊頭指針，reAr為隊尾指針，則執(zhí)行出隊操作后其頭指針front值為Front二front+1B.front=（front+1）%（m-1）Front=（front-1）%mD.front=（front+1）%m（A）47.如下陳述中正確的是串是一種特殊的線性表B.串的長度必須大于零串中元素只能是字母D.空串就是空白串（B）48.若目標(biāo)串的長充為n,模式串的長度為[n/3],則執(zhí)行模式匹配算法時，在最壞情況下的時間復(fù)雜度是O（1）B.O（n）O（n2）D.O（n3）（D）49.一個非空廣義表的表頭不可能是子表B?只能是子表B.只能是原子D.可以是子表或原子（C）50.從堆中刪除一個元素的時間復(fù)雜度為。A、O（1）B、O（n）B、O（log2n）D、O（nlog2n）C）51.一棵度為3的樹中，度為3的結(jié)點(diǎn)個數(shù)為2，度為2的結(jié)點(diǎn)個數(shù)為1，則度為AA指針B引用AA指針B引用0的結(jié)點(diǎn)個數(shù)為4B.56D.7(C)52.從二叉搜索樹中查找一個元素時，其時間復(fù)雜度大致為A、O(n)B、O(1)B、C、O(log2n)D、O(n2)(D)53.根據(jù)n個元素建立一棵二叉搜索樹時，其時間復(fù)雜度大致為。A、O(n)B、O(log2n)B、O(n2)D、O(nlog2n)(D)54.用某種排序方法對關(guān)鍵字序列(25，84，21，47，15，27，68，35，20)進(jìn)行排序時，序列的變化情況是如下：20，15，21，25，47，27，68，35，8415，20，21，25，35，27，47，68，8415，20，21，25，27，35，47，68，84則所采用的排序方法是選擇排序B.希爾排序B.歸并排序D?快速排序D.(C)55.適于對動態(tài)查找表進(jìn)行高效率查找的組織結(jié)構(gòu)是A.有序表B?分塊有序表C?二叉排序樹D?線性鏈表(A)56.若需要利用形參直接訪問實(shí)參，則應(yīng)把形參變量說明為參數(shù)CC值D常量CC值D常量B.(rear+1B.(rear+1。%N==frontD.front==rearB.(rear+1B.(rear+1。%N==frontD.front==rear(B)57.鏈?zhǔn)綏Ｅc順序棧相比，一個比較明顯的優(yōu)點(diǎn)是。插入操作更加方便B.通常不會出現(xiàn)棧滿的情況不會出現(xiàn)?？盏那闆rD.刪除操作更加方便(D)58.設(shè)單鏈表中結(jié)點(diǎn)的結(jié)構(gòu)為(data,link)。已知指針q所指結(jié)點(diǎn)是指針p所指結(jié)點(diǎn)的直接前驅(qū)，若在*q與*P之間插入結(jié)點(diǎn)*s，則應(yīng)執(zhí)行下列哪一個操作S->link=p->link;p->link=s;B.p->link=s;s->link=q;P->link=s->link;s->link=p;D.q->link=s;s->link=p;(C。59．若讓元素1,2,3依次進(jìn)棧，則出棧次序不可能出現(xiàn)種情況。3,2,1B.2,1,33,1,2D.1,3,2TOC\o"1-5"\h\z(A。60.線性鏈表不具有的特點(diǎn)是。隨機(jī)訪問B.不必事先估計所需存儲空間大小插入與刪除時不必移動元素D.所需空間與線性表長度成正比(A。61．在稀疏矩陣的十字鏈接存儲中，每個列單鏈表中的結(jié)點(diǎn)都具有相同的。A.行號B.列號元素值D.地址(D)62?假定一個順序隊列的隊首和隊尾指針分別為front和rear,存放該隊列的數(shù)組長度為N,則判斷隊空的條件為。A.(front+1。%N==rearC.front==0（A）63?棧的插入和刪除操作在進(jìn)行.（A）.棧頂（B）.棧底（C）.任意位置（D）.指定位置（D）64.在一個順序循環(huán)隊列中，隊首指針指向隊首元素的位置后兩個B.后一個當(dāng)前D.前一個（B）65?下面算法的時間復(fù)雜度為。Intf（intn）｛If((n==0)return1；Elsereturnn＊f(n-1)；｝A?O(1)B?O(n)C?0仲）D?O(n!)（DA）66.數(shù)據(jù)結(jié)構(gòu)是一門研究非數(shù)值計算的程序設(shè)計問題中計算機(jī)的（①）以及它們之間的（②）和運(yùn)算的學(xué)科①A、操作對象B、計算方法C、邏輯存儲D、數(shù)據(jù)映象②A、結(jié)構(gòu)B、關(guān)系C、運(yùn)算D、算法（DA）67.數(shù)據(jù)結(jié)構(gòu)被形式地定義為（K,R）,其中《是（①）的有限集合，R是K上（②）的有限集合A、算法B、數(shù)據(jù)元素C、數(shù)據(jù)操作D、邏輯結(jié)韻A、操作B、映象C、存儲D、關(guān)系（C）68.在數(shù)據(jù)結(jié)構(gòu)中,從邏輯上可以把數(shù)據(jù)結(jié)構(gòu)分為A、動態(tài)結(jié)構(gòu)和靜態(tài)結(jié)構(gòu)B、緊湊結(jié)構(gòu)和非緊湊結(jié)構(gòu)C、線性結(jié)構(gòu)和非線性結(jié)構(gòu)D、內(nèi)部結(jié)構(gòu)和外部結(jié)構(gòu)

（BA）69.線性表的順序存儲結(jié)構(gòu)是一種的存儲結(jié)構(gòu)，線性表的鏈?zhǔn)酱鎯Y(jié)構(gòu)是一種的存儲結(jié)構(gòu)A、隨機(jī)存取B、順序存取C、索引存取D、HASH存?。–A）70.算法分析的目的是（①），算法分析的兩個主要方面是（②）A、找出數(shù)據(jù)結(jié)構(gòu)的合理性C、分析算法的效率以求改進(jìn)B、研究算法中的輸入和輸出的關(guān)系D、分析算法的易懂性和文檔性A、空間復(fù)雜性和時間復(fù)雜性C、可讀性和文檔性B、正確性和簡明性D、數(shù)據(jù)復(fù)雜性和程序復(fù)雜性（CB）71.計算機(jī)算法指的是（①），它必具備輸入、輸出和（②）等五個特性A、計算方法B、排序方法C、解決萊一問題的有限運(yùn)算序列D、調(diào)度方法A、可執(zhí)行性、可移植性和可擴(kuò)充性C、確定性、有窮性和穩(wěn)定性B、可執(zhí)行性、確定性和有窮性D、易謾性、穩(wěn)定性和安全性（D）72.線性表若采用鏈表存儲結(jié)構(gòu)時，要求內(nèi)存中可用存儲單元的地A、必須是連續(xù)的B、部分地址必須是連續(xù)的C、一定是不連續(xù)的D、連續(xù)不連續(xù)都可以（B）73.在以下的敘述中，正確的是A、線性表的線性存儲結(jié)構(gòu)優(yōu)于鏈表存儲結(jié)構(gòu)C、棧的操作方式是先進(jìn)先出B、二維數(shù)組是它的每個數(shù)據(jù)元素為一個線性表的線性表D、隊列的操作方式是先進(jìn)后出（A）74.—個數(shù)組元素A[i]與的表示等價。A、*（A+i）B、A+IC、C、*A+ID、&A+I}}}}(C)75.對于兩個函數(shù)，若函數(shù)名相同，但只是不同則不是重載函數(shù)。A、參數(shù)類型B、參數(shù)個數(shù)C、函數(shù)類型D、函數(shù)變量(A)76.若需要利用形參直接訪問實(shí)參，則應(yīng)把形參變量說明為參數(shù)A、指針B、引用D、值D、函數(shù)E、(C)77.下面程序段的時間復(fù)雜度為。For(inti=0;i<m;i++)For(intj=0;j<n;j++)A[i][j]=i*j;A、O(m2)B、O(n2)C、O(m*n)D、O(m+n)(D)78.執(zhí)行下面程序段時，執(zhí)行S語句的次數(shù)為。For(inti=1;i<=n;i++)For(intj=1;j<=I;j++)S;A、N2B、n2/2B、N(n+1)D、n(n+1)/2(B)79.下面算法的時間復(fù)雜度為。Intf(unsignedintn){If(n==0||n==1)return1;elsereturnn*f(n-1);AA、O(1)B、O(n)AA、O(1)B、O(n)B、O(n2)D、O(n!)(B)80.在一^長度為n的順序存儲線性表中，向第i個元素(1WiWn+1)之前插入一^個新元素時，需要從后向前依次后移個元素。A、n-iB、n-i+1C、n-i-1D、i(A)81.在一個長度為n的順序存儲線性表中，刪除第i個元素(1WiWn+1)時，需要從前向后依次前移個元素。A、n-iB、n-i+1C、n-i-1D、i(D)82.在—長度為n的線性表中順序查找值為x的元素時，查找時的平均查找長度(即x同元素的平均比較次數(shù)，假定查找每個元素的概率都相等)為—。A、nB、n/2C、(n+1)/2D、(n-1)/2(D)83在一^單鏈表HL中，若要向表頭插入一^由指針p指向的結(jié)點(diǎn),則執(zhí)行。A、HL=p;p->next=HL;C、p->next=HL;p=HL;B、p->next=HL;HL=p;D、p->next=HL->next;HL->next=p;(D)84.在一個單鏈表HL中，若要在指針q所指的結(jié)點(diǎn)的后面插入一個由指針p所指的結(jié)點(diǎn),則執(zhí)行。A、q->next=p->next;p->next=q;C、q->next=p->next;p->next=q;B、p->next=q->next;q=p;D、p->next=q->next;q->next=p;(B)85?在一個單鏈表HL中，若要刪除由指針q所指向結(jié)點(diǎn)的后繼結(jié)點(diǎn)，則執(zhí)行—。A、p=q->next;p->next=q