數(shù)據(jù)結(jié)構(gòu)考試試題(帶答案)

1、系別班次學(xué)號姓名第1頁共15頁科技大學(xué)成都學(xué)院二零零八至二零零九學(xué)年第一學(xué)期科技大學(xué)成都學(xué)院二零零八至二零零九學(xué)年第一學(xué)期數(shù)據(jù)結(jié)構(gòu)課堂測試（60分鐘）閉卷考試時間：題號一二三總分評卷教師分?jǐn)?shù)一填空題（每空2分，共40分）；1.數(shù)據(jù)結(jié)構(gòu)算法中，通常用時間復(fù)雜度和__空間復(fù)雜度___兩種方法衡量其效率。2.下面程序段的時間復(fù)雜度為___O(n2)______。(n1)f(i=1inext==NULL__________。9.在棧頂指針為hs

2、的鏈棧中，判斷?？盏臈l件是_________hs==NULL__________。10.在hq的鏈隊列中，判定只有一個結(jié)點的條件是__hq.frontnext==hq.rear________。11.非空的循環(huán)單鏈表head的尾結(jié)點（由p指向），滿足條件____pnext==head。12.兩個串相等的充分必要條件是______串長相等且對應(yīng)字符相等_______。13.空串是_______長度為0的串______，其長度等于___0_

3、_______。14.空格串是______由空格字符組成的串______，其長度等于_____空格的個數(shù)_________。二單項選擇題（每題2分，共30分）；（說明：請將答案填入下表中）題號1234567891010答案AABBDBCBBC題號11111212131314141515答案AACDD1.若某線性表最常用的操作是存取任一指定序號的元素和在最后進行插入和刪除運算，則利用（A）存儲方式最節(jié)省時間。A順序表B雙鏈表C帶頭結(jié)點的雙

4、循環(huán)鏈表D單循環(huán)鏈表2.設(shè)a1、a2、a3為3個結(jié)點，則如下的鏈?zhǔn)酱鎯Y(jié)構(gòu)稱為：A系別班次學(xué)號姓名第3頁共15頁13.15.在雙向鏈表指針p的結(jié)點前插入一個指針q的結(jié)點操作是（C）。A.pLlink=qqRlink=ppLlinkRlink=qqLlink=q；B.pLlink=qpLlinkRlink=qqRlink=pqLlink=pLlinkC.qRlink=pqLlink=pLlinkpLlinkRlink=qpLlink=qD

5、.qLlink=pLlinkqRlink=qpLlink=qpLlink=q14.從一個具有n個結(jié)點的單鏈表中查找其值等于x結(jié)點時，在查找成功的情況下，需平均比較___D___個結(jié)點。AnBn2C(n—1)2D(n1)215.設(shè)串s1=‘ABCDEFG’s2=PQRST函數(shù)con(xy)返回x和y串的連接串，subs（sij）返回串s的從序號i的字符開始的j個字符組成的字串，len(s)返回串s的長度，則con(subs(s12len(

6、s2))subs(s1len(s2)2))的結(jié)果串是DA）BCDEFB）BCDEFGC）BCPQRSTD）BCDEFEF三綜合題（每題6分，共30分）1.線性表具有兩種存儲方式，即順序方式和鏈接方式?，F(xiàn)有一個具有五個元素的線性表L=23，17，47，05，31，若它以單鏈表方式存儲在下列100～119號地址空間中，每個結(jié)點由數(shù)據(jù)（占2個字節(jié)）和指針（占2個字節(jié)由大寫字母表示）組成，如下所示：p47q23r05s31t17100120其中

7、指針p，q，r，s，t的值分別為多少？該線性表的首結(jié)點起始地址為多少？末結(jié)點的起始地址為多少？(共6分)2.答：p=108q=116r=112s=0或NULLt=100首址=104末址=112。3.如果想將輸入的一個字符序列逆序輸出，如輸入“abcdef”，輸出“fedcba”，請分析用線性表、堆棧和隊列等方式正確輸出的可能性？(共6分)線性表是隨機存儲，可以實現(xiàn)，靠循環(huán)變量（j）從表尾開始打印輸出；堆棧是后進先出，也可以實現(xiàn)，靠正序入