軟工期末數(shù)據(jù)結構復習習題

1、1數(shù)據(jù)結構練習題數(shù)據(jù)結構練習題數(shù)據(jù)結構練習題（1－5章）一、選擇題一、選擇題1、從邏輯上可以把數(shù)據(jù)結構分為（C）兩大類。A動態(tài)結構、靜態(tài)結構B順序結構、鏈式結構C線性結構、非線性結構D初等結構、構造型結構2、以下數(shù)據(jù)結構中，哪一個是線性結構（D）？A廣義表B.二叉樹C.稀疏矩陣D.串3、在下面的程序段中，對x的賦值語句的頻度為（C）f(i=1inext=ssnext=pnextBsnext=pnextpnext=sCpnext=spne

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

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

4、、算法與應用題四、算法與應用題1.設線性表存放在向量A[arrsize]的前elenum個分量中且遞增有序，試寫一算法將x插入到線性表的適當位置，以保持線性表的有序性并分析其時間復雜度。#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.已知帶頭結點的動態(tài)單鏈表L中的結點是按整數(shù)值遞增排列的，試寫一算法將值x為的結點插入到表L中，使L仍

6、然有序。線性表的單鏈表存儲結構線性表的單鏈表存儲結構typedeftypedefstructstructLnodeLnodeElemTypeElemTypedatadatastructstructLnodeLnodenextnextLNodeLNodeLinkListLinkListLinkListLinkListst(LinkListst(LinkListLintLintx)x)帶頭結點帶頭結點LinkListLinkListpqpq