數(shù)據(jù)結(jié)構(gòu)與算法單元測試題1及答案

一、單選題1、?在數(shù)據(jù)結(jié)構(gòu)中，從邏輯上可以將之分為（）結(jié)構(gòu)。A.線性和非線性結(jié)構(gòu)B.動態(tài)和靜態(tài)結(jié)構(gòu)C.緊湊和非緊湊結(jié)構(gòu)D.內(nèi)部和非內(nèi)部結(jié)構(gòu)正確答案：A2、?算法的時間復(fù)雜度取決于（）。A.問題的規(guī)模B.待處理數(shù)據(jù)的初態(tài)C.沒有正確答案D.問題的規(guī)模以及待處理數(shù)據(jù)的初態(tài)正確答案：D3、?某算法的時間復(fù)雜度是O(n2)，表明該算法的（A.執(zhí)行時間與n2B.問題規(guī)模與n2C.執(zhí)行時間等于nD.問題規(guī)模是n正確答案：A4、?衡量算法效率優(yōu)劣的不包括（）。A.正確性和可讀性B.現(xiàn)實性C.健壯性/魯棒性D.高效率與低存儲正確答案：B5、?算法效率分析的兩個主要方面是（）。A.空間復(fù)雜度和時間復(fù)雜度B.數(shù)據(jù)復(fù)雜性和程序復(fù)雜性C.正確性和簡明性D.可讀性和文檔性正確答案：A6、?下面程序段的時間復(fù)雜度為（）。?for(i=0;i<n;i++)?for(j=0;j<m;j++)?A[i][j]=0;?A.O(n*m)B.O(1)C.O(n2D.O(m2正確答案：A7、?下面程序段的時間復(fù)雜度為（）。?voidsum(intn)//n為正整數(shù)??{?intp=1,sum=0,i;?for(i=1;i<=n;i++)?{?p*=i;?sum+=p;?}?}?A.O(n2B.O(n)C.O(1)D.O(n)正確答案：B8、下述哪一條是順序存儲結(jié)構(gòu)的優(yōu)點（）。A.插入運算方便B.隨機存取C.可方便地用于各種邏輯結(jié)構(gòu)的存儲表示D.刪除運算方便正確答案：B9、靜態(tài)鏈表中指針表示的是（）。A.下一元素在數(shù)組中的下標B.左、右孩子地址C.數(shù)組下標D.內(nèi)存地址正確答案：A10、?若長度為n的線性表采用順序存儲結(jié)構(gòu)，在其第i個位置插入一個新元素的算法的時間復(fù)雜度為（）。A.O(n2B.O(0)C.O(n)D.O(1)正確答案：C11、對于順序表，訪問結(jié)點和刪除結(jié)點的時間復(fù)雜度分別為（）。A.O(n)O(n)B.O(1)O(n)C.O(1)O(1)D.O(n)O(1)正確答案：B12、?對于一個帶頭結(jié)點的單鏈表，其頭指針為head，判定該表為空表的條件是（）。A.head→next==headB.head==NULLC.head→next==NULLD.head!=NULL正確答案：C13、將兩個各有n個元素的有序表合并成一個有序表，其最少的比較次數(shù)是（）。A.2nB.n-1C.nD.2n-1正確答案：C14、在雙向鏈表中，在p所指向的結(jié)點前插入一個q所指向的結(jié)點，相應(yīng)的操作語句是（）。注：雙向鏈表的結(jié)點結(jié)構(gòu)為(prior，data，next)。A.p->prior=q;p->prior->next=q;q->next=p;q->prior=p->prior;B.q->next=p;q->prior=p->prior;p->prior->next=q;p->prior=q;C.q->prior=p->prior;q->next=q;p->prior=q;p->prior=q;D.p->prior=q;q->next=p;p->prior->next=q;q->prior=q;正確答案：B15、?線性表（a1,a2,…,an）以鏈式方式存儲時，訪問第i個元素的時間復(fù)雜度為（）A.O（n）B.O（i）C.O（i-1）D.O（1）正確答案：A16、?頭指針為H的循環(huán)單鏈表中尾結(jié)點P的特點是（）。A.P->next=HB.P->next=H->nextC.P=H->nextD.P=H正確答案：A17、以下關(guān)于線性表的論述，不正確的是（）。A.線性表中的元素可以是數(shù)字、字符、記錄等不同類型。B.順序表中包含的元素個數(shù)是有限的。C.存在這樣的線性表，即表中沒有任何結(jié)點。D.線性表中的每個結(jié)點都有且僅有一個直接前趨和一個直接后繼。正確答案：D18、函數(shù)遞歸調(diào)用時，處理參數(shù)及返回地址需要用一種（）的數(shù)據(jù)結(jié)構(gòu)。A.線性表B.隊列C.多維數(shù)組D.棧正確答案：D19、若用一個大小為6的數(shù)組來實現(xiàn)循環(huán)隊列，且當(dāng)前rear和front的值分別為3和1，當(dāng)從隊列中刪除一個元素再加入兩個元素后，rear和front的值為()。A.0和5B.2和4C.5和1D.5和2正確答案：D20、用帶頭結(jié)點的表長大于1的單鏈表表示隊列時，其隊頭指針指向隊頭結(jié)點，其隊尾指針指向隊尾結(jié)點，則在進行刪除操作時()。A.僅修改隊頭指針B.僅修改隊尾指針C.隊頭、隊尾指針都要修改D.隊頭,隊尾指針都可能要修改正確答案：A21、以下程序的輸出結(jié)果為（）。intf(intx){return(x>0)?x*f(x-1):2;}voidmain(){inti;i=f(f(1));printf("%d",i);}A.無限遞歸B.4C.2D.8正確答案：B22、輸入序列為ABC，想要得到CBA的輸出結(jié)果，可以經(jīng)過的棧操作為（）。A.push,push,pop,pop,push,popB.push,pop,push,push,pop,popC.push,pop,push,pop,push,popD.push,push,push,pop,pop,pop正確答案：D23、一個棧的輸入序列為12345，則下列序列中不可能是棧的輸出序列的是（）。A.54132B.23415C.15432D.23145正確答案：A24、當(dāng)利用大小為n的數(shù)組順序存儲一個棧時，假定用top=n表示?？眨瑒t每次向這個棧插入一個元素時，首先應(yīng)執(zhí)行（）語句修改top指針。A.top=n;B.top=0;C.top++;D.top--;正確答案：D25、?鏈表不具有的特點是（）。A.所需空間與線性長度成正比B.不必事先估計存儲空間C.可隨機訪問任意元素D.插入、刪除不需要移動元素正確答案：C26、在下面的程序段中，對x的賦值語句的頻度為（）。for(i=1;i<n;i++)for(j=1;j<n;j++)x=x+1;A.O(log2B.O(n)C.O(2n)D.O(n2正確答案：D27、數(shù)據(jù)結(jié)構(gòu)在計算機內(nèi)存中的表示是指（）。A.數(shù)據(jù)結(jié)構(gòu)B.數(shù)據(jù)的邏輯結(jié)構(gòu)C.數(shù)據(jù)的存儲結(jié)構(gòu)D.數(shù)據(jù)元素之間的關(guān)系正確答案：C二、判斷題1、?順序存儲方式的優(yōu)點是存儲密度大，且插入、刪除運算效率高。正確答案:×2、?在相同的數(shù)據(jù)規(guī)模n下，復(fù)雜度為O(n)的算法在時間上總是優(yōu)于復(fù)雜度為O(2n)正確答案：√3、?數(shù)據(jù)的存儲結(jié)構(gòu)表示的是數(shù)據(jù)元素之間的邏輯關(guān)系。正確答案：×4、?線性表的特點是每個元素都有一個前驅(qū)和一個后繼。正確答案：×5、?若長度為n的線性表采用順序存儲結(jié)構(gòu)，找到其中第i個元素的時間復(fù)雜度為O(n)。正確答案：×6、?順序表適宜于順序存取，而鏈表適宜于隨機存取。正確答案：×7、?順序表的每個結(jié)點只能是一個簡單類型，而鏈表的每個結(jié)點可以是一個復(fù)雜類型。正確答案：×8、?線性表的鏈式存儲結(jié)構(gòu)中，邏輯上相鄰的兩個元素在物理位置上不一定相鄰。正確答案：√9、?消除遞歸不一定需要