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

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

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

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

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

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

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

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