【正文】 程序復(fù)雜性具有線性結(jié)構(gòu)的數(shù)據(jù)結(jié)構(gòu)是（ D ）。A. 圖 B. 樹 C. 廣義表 D. 棧計算機(jī)中的算法指的是解決某一個問題的有限運(yùn)算序列，它必須具備輸入、輸出、（ B ）等5個特性。A. 可執(zhí)行性、可移植性和可擴(kuò)充性 B. 可執(zhí)行性、有窮性和確定性C. 確定性、有窮性和穩(wěn)定性 D. 易讀性、穩(wěn)定性和確定性下面程序段的時間復(fù)雜度是（ 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. 計算機(jī)程序 B. 解決問題的計算方法 C. 排序算法 D. 解決問題的有限運(yùn)算序列某算法的語句執(zhí)行頻度為（3n+nlog2n+n2+8）,其時間復(fù)雜度表示（ C ）。A. O(n) B. O(nlog2n) C. O(n2) D. O(log2n)下面程序段的時間復(fù)雜度為（ C ）。 i=1。 while(i=n) i=i*3。A. O(n) B. O(3n) C. O(log3n) D. O(n3) 數(shù)據(jù)結(jié)構(gòu)是一門研究非數(shù)值計算的程序設(shè)計問題中計算機(jī)的數(shù)據(jù)元素以及它們之間的（ B ）和運(yùn)算等的學(xué)科。A. 結(jié)構(gòu) B. 關(guān)系 C. 運(yùn)算 D. 算法下面程序段的時間復(fù)雜度是（ C ）。 i=s=0。 while(sn){ i++。s+=i。 }A. O(n) B. O(n2) C. O(√n) D. O(n3)1抽象數(shù)據(jù)類型的三個組成部分分別為（ A ）。 A. 數(shù)據(jù)對象、數(shù)據(jù)關(guān)系和基本操作 B. 數(shù)據(jù)元素、邏輯結(jié)構(gòu)和存儲結(jié)構(gòu) C. 數(shù)據(jù)項(xiàng)、數(shù)據(jù)元素和數(shù)據(jù)類型 D. 數(shù)據(jù)元素、數(shù)據(jù)結(jié)構(gòu)和數(shù)據(jù)類型1通常從正確性、易讀性、健壯性、高效性等4個方面評價算法的質(zhì)量，以下解釋錯誤的是（ A ）。 A. 正確性算法應(yīng)能正確地實(shí)現(xiàn)預(yù)定的功能 B. 易讀性算法應(yīng)易于閱讀和理解，以便調(diào)試、修改和擴(kuò)充 C. 健壯性當(dāng)環(huán)境發(fā)生變化時，算法能適當(dāng)?shù)刈龀龇磻?yīng)或進(jìn)行處理，不會產(chǎn)生不需要的運(yùn)行結(jié)果 D. 高效性即達(dá)到所需要的時間性能1下列程序段的時間復(fù)雜度為（ 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?！钡臅r間復(fù)雜度為 O(log2n) 。數(shù)據(jù)結(jié)構(gòu)的四種基本類型中, 樹形結(jié)構(gòu) 的元素是一對多關(guān)系。三、綜合題將數(shù)量級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的線性表采用順序存儲結(jié)構(gòu)，在其第i個位置插入一個新元素算法的時間復(fù)雜度（ C ）。A. O(log2n) (1) C. O(n) (n2)若一個線性表中最常用的操作是取第i個元素和找第i個元素的前趨元素，則采用（ A ）存儲方式最節(jié)省時間。 A. 順序表 B. 單鏈表 C. 雙鏈表 D. 單循環(huán)鏈表具有線性結(jié)構(gòu)的數(shù)據(jù)結(jié)構(gòu)是（ D ）。A. 圖 B. 樹 C. 廣義表 D. 棧在一個長度為n的順序表中，在第i個元素之前插入一個新元素時，需向后移動（ B ）個元素。A. ni B. ni+1 C. ni1 D. i非空的循環(huán)單鏈表head的尾結(jié)點(diǎn)p滿足（ A ）。A. pnext==head B. pnext==NULL C. p==NULL D. p==head鏈表不具有的特點(diǎn)是（ A ）。A. 可隨機(jī)訪問任一元素　 B. 插入刪除不需要移動元素 C. 不必事先估計存儲空間 D. 所需空間與線性表長度成正比在雙向循環(huán)鏈表中，在p指針?biāo)傅慕Y(jié)點(diǎn)后插入一個指針q所指向的新結(jié)點(diǎn)，修改指針的操作是（ 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。線性表采用鏈?zhǔn)酱鎯r，結(jié)點(diǎn)的存儲地址（ C ）。A. 必須是連續(xù)的 B. 必須是不連續(xù)的 C. 連續(xù)與否均可 D. 和頭結(jié)點(diǎn)的存儲地址相連續(xù)在一個長度為n的順序表中刪除第i個元素，需要向前移動（ A ）個元素。A. ni B. ni+1 C. ni1 D. i+1線性表是n個（ C ）的有限序列。A. 表元素 B. 字符 C. 數(shù)據(jù)元素 D. 數(shù)據(jù)項(xiàng) 1從表中任一結(jié)點(diǎn)出發(fā)，都能掃描整個表的是（ C ）。A. 單鏈表 B. 順序表 C. 循環(huán)鏈表 D. 靜態(tài)鏈表1在具有n個結(jié)點(diǎn)的單鏈表上查找值為x的元素時，其時間復(fù)雜度為（ A ）。A. O(n) B. O(1) C. O(n2) D. O(n1)1線性表L=(a1,a2,……,an)，下列說法正確的是（ D ）。A. 每個元素都有一個直接前驅(qū)和一個直接后繼 B. 線性表中至少要有一個元素C. 表中諸元素的排列順序必須是由小到大或由大到小 D. 除第一個和最后一個元素外，其余每個元素都由一個且僅有一個直接前驅(qū)和直接后繼1一個順序表的第一個元素的存儲地址是90，每個元素的長度為2，則第6個元素的存儲地址是（ B ）。A. 98 B. 100 C. 102 D. 1061在線性表的下列存儲結(jié)構(gòu)中，讀取元素花費(fèi)的時間最少的是（ D ）。 A. 單鏈表 B. 雙鏈表 C. 循環(huán)鏈表 D. 順序表1在一個單鏈表中，若刪除p所指向結(jié)點(diǎn)的后續(xù)結(jié)點(diǎn)，則執(zhí)行（ A ）。A. pnext=pnextnext。B. p=pnext。pnext=pnextnext。C. p =pnext。D. p=pnextnext。1將長度為n的單鏈表連接在長度為m的單鏈表之后的算法的時間復(fù)雜度為（ C ）。A. O(1) B. O(n) C. O(m) D. O(m+n)1線性表的順序存儲結(jié)構(gòu)是一種（ A ）存儲結(jié)構(gòu)。A. 隨機(jī)存取 B. 順序存取 C. 索引存取 D. 散列存取 1順序表中，插入一個元素所需移動的元素平均數(shù)是（ D ）。 A. (n1)/2 B. n C. n+1 D. n/2循環(huán)鏈表的主要優(yōu)點(diǎn)是（ D ）。A. 不再需要頭指針 B. 已知某結(jié)點(diǎn)位置后能容易找到其直接前驅(qū) C. 在進(jìn)行插入、刪除運(yùn)算時能保證鏈表不斷開 D. 在表中任一結(jié)點(diǎn)出發(fā)都能掃描整個鏈表 1不帶頭結(jié)點(diǎn)的單鏈表head為空的判定條件是（ A ）。A. head==NULL B. headnext==NULL （帶頭結(jié)點(diǎn)判定條件） C. headnext==head （循環(huán)鏈表判定條件） D. head!=NULL1在下列對順序表進(jìn)行的操作中，算法時間復(fù)雜度為O(1)的是（ A ）。 A. 訪問第i個元素的前驅(qū)（1） B. 在第i個元素之后插入一個新元素() C. 刪除第i個元素() D. 對順序表中元素進(jìn)行排序1已知指針p和q分別指向某單鏈表中第一個結(jié)點(diǎn)和最后一個結(jié)點(diǎn)。假設(shè)指針s指向另一個單鏈表中某個結(jié)點(diǎn)，則在s所指結(jié)點(diǎn)之后插入上述鏈表應(yīng)執(zhí)行的語句為（ A ）。A. qnext=snext；snext=p； B. snext=p；qnext=snext； C. pnext=snext；snext=q； D. snext=q；pnext=snext；1在以下的敘述中，正確的是（ C ）。 A. 線性表的順序存儲結(jié)構(gòu)優(yōu)于鏈表存儲結(jié)構(gòu)　 B. 線性表的順序存儲結(jié)構(gòu)適用于頻繁插入/刪除數(shù)據(jù)元素的情況 C. 線性表的鏈表存儲結(jié)構(gòu)適用于頻繁插入/刪除數(shù)據(jù)元素的情況 D. 線性表的鏈表存儲結(jié)構(gòu)優(yōu)于順序存儲結(jié)構(gòu)1在表長為n的順序表中，當(dāng)在任何位置刪除一個元素的概率相同時，刪除一個元素所需移動的平均個數(shù)為（ A ）。A. (n1)/2 B. n/2 C. (n+1)/2 D. n1在一個單鏈表中，已知q所指結(jié)點(diǎn)是p所指結(jié)點(diǎn)的前驅(qū)結(jié)點(diǎn)，若在q和p之間插入一個結(jié)點(diǎn)s，則執(zhí)行（ C ）。A. snext=pnext。 pnext=s。 B. pnext=snext。snext=p。 C. qnext=s。snext=p。 D. pnext=s。snext=q。 1在單鏈表中，指針p指向元素為x的結(jié)點(diǎn)，實(shí)現(xiàn)刪除x的后繼的語句是（ B ）。A. p=pnext。 B. pnext=pnextnext。 C. pnext=p。 D. p=pnextnext。1在頭指針為head且表長大于1的單循環(huán)鏈表中，指針p指向表中某個結(jié)點(diǎn)，若pnextnext==head，則（ D ）。A. p指向頭結(jié)點(diǎn)　 B. p指向尾結(jié)點(diǎn) C. p的直接后繼是頭結(jié)點(diǎn) D. p的直接后繼是尾結(jié)點(diǎn)設(shè)單鏈表的結(jié)點(diǎn)結(jié)構(gòu)為（data,next）。已知指針p指向單鏈表中的結(jié)點(diǎn)，q指向新結(jié)點(diǎn)，欲將q插入到p結(jié)點(diǎn)之后，則需要執(zhí)行的語句： qnext=pnext ； pnext = q 。二、填空題答案：qnext=pnext pnext=q線性表的邏輯結(jié)構(gòu)是 線性結(jié)構(gòu) ，其所含元素的個數(shù)稱為線性表的 長度 。答案：線性結(jié)構(gòu) 長度寫出帶頭結(jié)點(diǎn)的雙向循環(huán)鏈表L為空表的條件 。答案：Lprior==Lnext==L帶頭結(jié)點(diǎn)的單鏈表head為空的條件是 。答案：headnext==NULL在一個單鏈表中刪除p所指結(jié)點(diǎn)的后繼結(jié)點(diǎn)時，應(yīng)執(zhí)行以下操作：q = pnext。pnext= _qnext ___。 三、判斷題單鏈表不是一種隨機(jī)存儲結(jié)構(gòu)。 對在具有頭結(jié)點(diǎn)的單鏈表中，頭指針指向鏈表的第一個數(shù)據(jù)結(jié)點(diǎn)。錯用循環(huán)單鏈表表示的鏈隊(duì)列中，可以不設(shè)隊(duì)頭指針，僅在隊(duì)尾設(shè)置隊(duì)尾指針。對順序存儲方式只能用于存儲線性結(jié)構(gòu)。錯在線性表的順序存儲結(jié)構(gòu)中，邏輯上相鄰的兩個元素但是在物理位置上不一定是相鄰的。錯鏈?zhǔn)酱鎯Φ木€性表可以隨機(jī)存取。錯四、程序分析填空題函數(shù)GetElem實(shí)現(xiàn)返回單鏈表的第i個元素，請?jiān)诳崭裉帉⑺惴ㄑa(bǔ)充完整。 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函數(shù)實(shí)現(xiàn)單鏈表的插入算法，請?jiān)诳崭裉帉⑺惴ㄑa(bǔ)充完整。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函數(shù)ListDelete_sq實(shí)現(xiàn)順序表刪除算法，請?jiān)?