軟工期末數(shù)據(jù)結(jié)構(gòu)復(fù)習(xí)習(xí)題

1、1數(shù)據(jù)結(jié)構(gòu)練習(xí)題數(shù)據(jù)結(jié)構(gòu)練習(xí)題數(shù)據(jù)結(jié)構(gòu)練習(xí)題（1－5章）一、選擇題一、選擇題1、從邏輯上可以把數(shù)據(jù)結(jié)構(gòu)分為（C）兩大類。A動(dòng)態(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、以下數(shù)據(jù)結(jié)構(gòu)中，哪一個(gè)是線性結(jié)構(gòu)（D）？A廣義表B.二叉樹C.稀疏矩陣D.串3、在下面的程序段中，對(duì)x的賦值語(yǔ)句的頻度為（C）f(i=1inext=ssnext=pnextBsnext=pnextpnext=sCpnext=spne

2、xt=snextDpnext=snextpnext=s10、對(duì)于一個(gè)頭指針為head的帶頭結(jié)點(diǎn)的單鏈表，判定該表為空表的條件是（B）Ahead==NULLBhead→next==NULLChead→next==headDhead!=NULL11、一個(gè)棧的輸入序列為123…n，若輸出序列的第一個(gè)元素是n，輸出第i（1nextnext==LLnextnext==L__6、一個(gè)棧的輸入序列是：1，2，3則不可能的棧輸出序列是__312___。

3、7、用S表示入棧操作，X表示出棧操作，若元素入棧的順序?yàn)?234，為了得到1342出棧順序，相應(yīng)的S和X的操作串為_SXSSXSXX_SXSSXSXX__。8、__隊(duì)列隊(duì)列__又稱作先進(jìn)先出表。9、組成串的數(shù)據(jù)元素只能是__字符字符___。10、設(shè)有C語(yǔ)言描述的二維數(shù)組A[10][20]其每個(gè)元素占兩個(gè)字節(jié)，第一個(gè)元素的存儲(chǔ)地址為100，若按行優(yōu)先順序存儲(chǔ)，則元素A[6][6]存儲(chǔ)地址為__352352__。(沒說(shuō)明，則下標(biāo)從0開始)四

4、、算法與應(yīng)用題四、算法與應(yīng)用題1.設(shè)線性表存放在向量A[arrsize]的前elenum個(gè)分量中且遞增有序，試寫一算法將x插入到線性表的適當(dāng)位置，以保持線性表的有序性并分析其時(shí)間復(fù)雜度。#define#definearrsizearrsize100100boolboolst(Elemtypest(ElemtypeA[]intA[]intelenumelenumElemtypeElemtypex)x)intintiiif(elenumif

5、(elenum==arrsize)arrsize)printf(“printf(“該數(shù)組向量已滿該數(shù)組向量已滿”)”)；returnreturnfalsefalsei=elenum1i=elenum1while(A[i]xwhile(A[i]xA[i1]=A[i]iiA[i1]=xA[i1]=xreturnreturntruetrue2.已知帶頭結(jié)點(diǎn)的動(dòng)態(tài)單鏈表L中的結(jié)點(diǎn)是按整數(shù)值遞增排列的，試寫一算法將值x為的結(jié)點(diǎn)插入到表L中，使L仍

6、然有序。線性表的單鏈表存儲(chǔ)結(jié)構(gòu)線性表的單鏈表存儲(chǔ)結(jié)構(gòu)typedeftypedefstructstructLnodeLnodeElemTypeElemTypedatadatastructstructLnodeLnodenextnextLNodeLNodeLinkListLinkListLinkListLinkListst(LinkListst(LinkListLintLintx)x)帶頭結(jié)點(diǎn)帶頭結(jié)點(diǎn)LinkListLinkListpqpq