江南大學(xué)現(xiàn)代遠(yuǎn)程教育2015數(shù)據(jù)結(jié)構(gòu)第1階段測試題1b

1、江南大學(xué)現(xiàn)代遠(yuǎn)程教育 第一階段測試卷考試科目:數(shù)據(jù)結(jié)構(gòu)第一章至第四章（總分100分） 時間：90分鐘_學(xué)習(xí)中心（教學(xué)點） 批次： 層次： 專業(yè)： 學(xué)號： 身份證號： 姓名： 得分： 一、選擇題（每題3分，共30分）1、在樹形結(jié)構(gòu)中，數(shù)據(jù)元素間存在（B）的關(guān)系。、一對一、一對多、多對多、除同屬一個集合外別無關(guān)系2、下列說法中錯誤的是（B）。、數(shù)據(jù)對象是數(shù)據(jù)的子集、數(shù)據(jù)元素間關(guān)系在計算機(jī)中的映象即為數(shù)據(jù)的存儲結(jié)構(gòu)、非順序映象的特點是借助指示元素存儲地址的指針來表示數(shù)據(jù)元素間邏輯關(guān)系、抽象數(shù)據(jù)類型指一個數(shù)學(xué)模型及定義在該模型上的一組操作3、下列不屬算法特性的是（D）。、有窮性、確定性、零或多個輸入、

2、健壯性4、在長為n的順序表中刪除一個數(shù)據(jù)元素，平均需移動（D）個數(shù)據(jù)元素。、n、n-1、n/2、(n-1)/25、若某線性表最常用的操作是存取任一指定序號的元素和在最后進(jìn)行插入和刪除運(yùn)算，則利用（A）存儲方式最節(jié)省時間。、順序表、雙鏈表、帶頭結(jié)點的雙向循環(huán)鏈表、單循環(huán)鏈表6、在一個可存放n個數(shù)據(jù)元素的順序棧中，假設(shè)以高地址端為棧底，以top為棧頂指針，當(dāng)向棧中壓入一個數(shù)據(jù)元素時，top的變化是（D）。、不變、top=n、top+、top-7、設(shè)在一不帶頭結(jié)點的鏈隊列中，front和rear分別為其隊頭和隊尾指針，則刪除一個結(jié)點的操作是（C）。、rear=front->next、rear=

3、rear->next、front=front->next、front=rear->next8、判定一個棧頂指針為S且不帶頭結(jié)點的鏈棧為空棧的條件是（D）。、S、S->next、S->next=NULL、!S9、設(shè)在一不帶頭結(jié)點的鏈隊列中，front和rear分別為其隊頭和隊尾指針，則判定該隊中只有一個結(jié)點的條件是（C）。、front->next、rear->next、front=rear、front!=rear10、串的長度是指（B）。A、串中所含不同字母的個數(shù)B、串中所含字符的個數(shù)C、串中所含不同字符的個數(shù)D、串中所含非空格字符的個數(shù)二、（10分）設(shè)

4、為正整數(shù)，試確定如下程序段中語句“x+;”的頻度。for (i=1;i<=n;i+)for (j=1;j<=i;j+)for (k=1;k<=n;k+)x+;答：n2(n+1)/2三、（15分）設(shè)單鏈表如圖所示：畫出執(zhí)行如下程序段后，各指針變量及單鏈表的示意圖。p=L;for(i=1;i<=3;i+)q=(LinkList)malloc(sizeof(LNode);q->data=i*3;q->next=p->next;p->next=q;答：369四、（10分）設(shè)元素的入棧次序為a、b、c、d，且在入棧的過程中允許出棧，試寫出所有不可能得到的出

5、棧序列。答：dabc dbac dbca cadb cdab bdac adbc五、（15分）設(shè)a='data structure'，b='computer'，c='demo'，試求： StrLength(a)的返回值； 執(zhí)行StrInsert(b,4,c)后串b的值； Index(a,'u',10)的返回值； 執(zhí)行Replace(a,'structure',b)后串a(chǎn)的值； 執(zhí)行SubString(s,b,3,3)后串s的值。答：14 comdemoputer 12 data computer mpu六、（20分）已知單鏈表L中含有三類字符的數(shù)據(jù)元素，即字母字符、數(shù)字字符和其他字符，試編寫算法將L分割為三個循環(huán)鏈表，其中每個循環(huán)鏈表只含一類字符。答：Void parition(LinkList &L,LinkList &LC