數據結構試題集含答案(已修改)

　

【正文】 程序復雜性具有線性結構的數據結構是（ D ）。A. 圖 B. 樹 C. 廣義表 D. 棧計算機中的算法指的是解決某一個問題的有限運算序列，它必須具備輸入、輸出、（ B ）等5個特性。A. 可執行性、可移植性和可擴充性 B. 可執行性、有窮性和確定性C. 確定性、有窮性和穩定性 D. 易讀性、穩定性和確定性下面程序段的時間復雜度是（ C ）。 for(i=0。im。i++) for(j=0。jn。j++) a[i][j]=i*j。A. O(m2)　 B. O(n2) C. O(m*n) D. O(m+n)算法是（ D ）。A. 計算機程序 B. 解決問題的計算方法 C. 排序算法 D. 解決問題的有限運算序列某算法的語句執行頻度為（3n+nlog2n+n2+8）,其時間復雜度表示（ C ）。A. O(n) B. O(nlog2n) C. O(n2) D. O(log2n)下面程序段的時間復雜度為（ C ）。 i=1。 while(i=n) i=i*3。A. O(n) B. O(3n) C. O(log3n) D. O(n3) 數據結構是一門研究非數值計算的程序設計問題中計算機的數據元素以及它們之間的（ B ）和運算等的學科。A. 結構 B. 關系 C. 運算 D. 算法下面程序段的時間復雜度是（ C ）。 i=s=0。 while(sn){ i++。s+=i。 }A. O(n) B. O(n2) C. O(√n) D. O(n3)1抽象數據類型的三個組成部分分別為（ A ）。 A. 數據對象、數據關系和基本操作 B. 數據元素、邏輯結構和存儲結構 C. 數據項、數據元素和數據類型 D. 數據元素、數據結構和數據類型1通常從正確性、易讀性、健壯性、高效性等4個方面評價算法的質量，以下解釋錯誤的是（ A ）。 A. 正確性算法應能正確地實現預定的功能 B. 易讀性算法應易于閱讀和理解，以便調試、修改和擴充 C. 健壯性當環境發生變化時，算法能適當地做出反應或進行處理，不會產生不需要的運行結果 D. 高效性即達到所需要的時間性能1下列程序段的時間復雜度為（ B ）。 x=n。y=0。 while(x=(y+1)*(y+1)) y=y+1。 A. O(n) B. C. O(1) D. O(n2)二、填空題程序段“i=1。while(i=n) i=i*2。”的時間復雜度為 O(log2n) 。數據結構的四種基本類型中, 樹形結構 的元素是一對多關系。三、綜合題將數量級O(1),O(N),O(N2),O(N3),O(NLOG2N),O(LOG2N),O(2N)按增長率由小到大排序。答案： O(1) O(log2N) O(N) O(Nlog2N) O(N2) O(N3) O(2N) 第二章 線性表一、選擇題若長度為n的線性表采用順序存儲結構，在其第i個位置插入一個新元素算法的時間復雜度（ C ）。A. O(log2n) (1) C. O(n) (n2)若一個線性表中最常用的操作是取第i個元素和找第i個元素的前趨元素，則采用（ A ）存儲方式最節省時間。 A. 順序表 B. 單鏈表 C. 雙鏈表 D. 單循環鏈表具有線性結構的數據結構是（ D ）。A. 圖 B. 樹 C. 廣義表 D. 棧在一個長度為n的順序表中，在第i個元素之前插入一個新元素時，需向后移動（ B ）個元素。A. ni B. ni+1 C. ni1 D. i非空的循環單鏈表head的尾結點p滿足（ A ）。A. pnext==head B. pnext==NULL C. p==NULL D. p==head鏈表不具有的特點是（ A ）。A. 可隨機訪問任一元素　 B. 插入刪除不需要移動元素 C. 不必事先估計存儲空間 D. 所需空間與線性表長度成正比在雙向循環鏈表中，在p指針所指的結點后插入一個指針q所指向的新結點，修改指針的操作是（ C ）。 A. pnext=q。qprior=p。pnextprior=q。qnext=q。 B. pnext=q。pnextprior=q。qprior=p。qnext=pnext。 C. qprior=p。qnext=pnext。pnextprior=q。pnext=q。 D. qnext=pnext。qprior=p。pnext=q。pnext=q。線性表采用鏈式存儲時，結點的存儲地址（ C ）。A. 必須是連續的 B. 必須是不連續的 C. 連續與否均可 D. 和頭結點的存儲地址相連續在一個長度為n的順序表中刪除第i個元素，需要向前移動（ A ）個元素。A. ni B. ni+1 C. ni1 D. i+1線性表是n個（ C ）的有限序列。A. 表元素 B. 字符 C. 數據元素 D. 數據項 1從表中任一結點出發，都能掃描整個表的是（ C ）。A. 單鏈表 B. 順序表 C. 循環鏈表 D. 靜態鏈表1在具有n個結點的單鏈表上查找值為x的元素時，其時間復雜度為（ A ）。A. O(n) B. O(1) C. O(n2) D. O(n1)1線性表L=(a1,a2,……,an)，下列說法正確的是（ D ）。A. 每個元素都有一個直接前驅和一個直接后繼 B. 線性表中至少要有一個元素C. 表中諸元素的排列順序必須是由小到大或由大到小 D. 除第一個和最后一個元素外，其余每個元素都由一個且僅有一個直接前驅和直接后繼1一個順序表的第一個元素的存儲地址是90，每個元素的長度為2，則第6個元素的存儲地址是（ B ）。A. 98 B. 100 C. 102 D. 1061在線性表的下列存儲結構中，讀取元素花費的時間最少的是（ D ）。 A. 單鏈表 B. 雙鏈表 C. 循環鏈表 D. 順序表1在一個單鏈表中，若刪除p所指向結點的后續結點，則執行（ A ）。A. pnext=pnextnext。B. p=pnext。pnext=pnextnext。C. p =pnext。D. p=pnextnext。1將長度為n的單鏈表連接在長度為m的單鏈表之后的算法的時間復雜度為（ C ）。A. O(1) B. O(n) C. O(m) D. O(m+n)1線性表的順序存儲結構是一種（ A ）存儲結構。A. 隨機存取 B. 順序存取 C. 索引存取 D. 散列存取 1順序表中，插入一個元素所需移動的元素平均數是（ D ）。 A. (n1)/2 B. n C. n+1 D. n/2循環鏈表的主要優點是（ D ）。A. 不再需要頭指針 B. 已知某結點位置后能容易找到其直接前驅 C. 在進行插入、刪除運算時能保證鏈表不斷開 D. 在表中任一結點出發都能掃描整個鏈表 1不帶頭結點的單鏈表head為空的判定條件是（ A ）。A. head==NULL B. headnext==NULL （帶頭結點判定條件） C. headnext==head （循環鏈表判定條件） D. head!=NULL1在下列對順序表進行的操作中，算法時間復雜度為O(1)的是（ A ）。 A. 訪問第i個元素的前驅（1） B. 在第i個元素之后插入一個新元素() C. 刪除第i個元素() D. 對順序表中元素進行排序1已知指針p和q分別指向某單鏈表中第一個結點和最后一個結點。假設指針s指向另一個單鏈表中某個結點，則在s所指結點之后插入上述鏈表應執行的語句為（ A ）。A. qnext=snext；snext=p； B. snext=p；qnext=snext； C. pnext=snext；snext=q； D. snext=q；pnext=snext；1在以下的敘述中，正確的是（ C ）。 A. 線性表的順序存儲結構優于鏈表存儲結構　 B. 線性表的順序存儲結構適用于頻繁插入/刪除數據元素的情況 C. 線性表的鏈表存儲結構適用于頻繁插入/刪除數據元素的情況 D. 線性表的鏈表存儲結構優于順序存儲結構1在表長為n的順序表中，當在任何位置刪除一個元素的概率相同時，刪除一個元素所需移動的平均個數為（ A ）。A. (n1)/2 B. n/2 C. (n+1)/2 D. n1在一個單鏈表中，已知q所指結點是p所指結點的前驅結點，若在q和p之間插入一個結點s，則執行（ C ）。A. snext=pnext。 pnext=s。 B. pnext=snext。snext=p。 C. qnext=s。snext=p。 D. pnext=s。snext=q。 1在單鏈表中，指針p指向元素為x的結點，實現刪除x的后繼的語句是（ B ）。A. p=pnext。 B. pnext=pnextnext。 C. pnext=p。 D. p=pnextnext。1在頭指針為head且表長大于1的單循環鏈表中，指針p指向表中某個結點，若pnextnext==head，則（ D ）。A. p指向頭結點　 B. p指向尾結點 C. p的直接后繼是頭結點 D. p的直接后繼是尾結點設單鏈表的結點結構為（data,next）。已知指針p指向單鏈表中的結點，q指向新結點，欲將q插入到p結點之后，則需要執行的語句： qnext=pnext ； pnext = q 。二、填空題答案：qnext=pnext pnext=q線性表的邏輯結構是 線性結構 ，其所含元素的個數稱為線性表的 長度 。答案：線性結構 長度寫出帶頭結點的雙向循環鏈表L為空表的條件 。答案：Lprior==Lnext==L帶頭結點的單鏈表head為空的條件是 。答案：headnext==NULL在一個單鏈表中刪除p所指結點的后繼結點時，應執行以下操作：q = pnext。pnext= _qnext ___。 三、判斷題單鏈表不是一種隨機存儲結構。 對在具有頭結點的單鏈表中，頭指針指向鏈表的第一個數據結點。錯用循環單鏈表表示的鏈隊列中，可以不設隊頭指針，僅在隊尾設置隊尾指針。對順序存儲方式只能用于存儲線性結構。錯在線性表的順序存儲結構中，邏輯上相鄰的兩個元素但是在物理位置上不一定是相鄰的。錯鏈式存儲的線性表可以隨機存取。錯四、程序分析填空題函數GetElem實現返回單鏈表的第i個元素，請在空格處將算法補充完整。 int GetElem(LinkList L,int i,Elemtype *e){ LinkList p；int j；p=Lnext。j=1。 while(pamp。amp。ji){ (1) 。++j。}if(!p||ji) return ERROR。*e= (2) 。return OK。}答案：(1)p=pnext (2)pdata函數實現單鏈表的插入算法，請在空格處將算法補充完整。int ListInsert(LinkList L,int i,ElemType e){ LNode *p,*s。int j。 p=L。j=0。 while((p!=NULL)amp。amp。(ji1)){ p=pnext。j++。 } if(p==NULL||ji1) return ERROR。 s=(LNode *)malloc(sizeof(LNode))。 sdata=e。 (1) 。 (2) 。 return OK。}/*ListInsert*/答案：(1)snext=pnext (2)pnext=s函數ListDelete_sq實現順序表刪除算法，請在