數(shù)構(gòu)半期考數(shù)據(jù)結(jié)構(gòu)2011-20121

1、福建師范大學(xué)學(xué)院卷數(shù)學(xué)與計(jì)算機(jī)科學(xué)20112012學(xué)年第1 學(xué)期 半期專業(yè)：年級(jí)：課程名稱:數(shù)據(jù)結(jié)構(gòu)任課教師：用時(shí)：試卷類別：開(kāi)卷（ ）閉卷（）分鐘時(shí)間:年月日午點(diǎn)分考生信息欄學(xué)院系專業(yè) 年級(jí)學(xué)號(hào)裝訂線題號(hào)一二三四五總得分評(píng)卷人得分題號(hào)六七十得分一、選擇：(每題 2 分，共 20 分)1、已知二叉樹(shù)的前、中根序列分別是 abdefcg和 defbagc，則該二叉樹(shù)的后根遍歷序列是( )。A. defbgcaB. fedbgcaC. abcdefgD. gfedcba2、數(shù)據(jù)在計(jì)算機(jī)器內(nèi)表示時(shí),物理地址與邏輯地址相同并且是連續(xù)的,稱為()A.結(jié)構(gòu)B.邏輯結(jié)構(gòu)C.順序D.鏈?zhǔn)浇Y(jié)構(gòu)結(jié)構(gòu)3、一個(gè)棧的輸

2、入序列為 1 2 3 4 5，則下列序列中不可能是棧的輸出序列的是（ ）。A. 2 3 4 1 5B. 5 4 1 3 2C. 2 3 1 4 5D. 1 5 4 3 24、在具有n 個(gè)結(jié)點(diǎn)的單鏈表中,實(shí)現(xiàn)( )的操作,其算法的時(shí)間復(fù)雜度是 O(n).A.遍歷鏈表和求鏈表的第 i 個(gè)結(jié)點(diǎn).B.在地址為p 的結(jié)點(diǎn)之后C.刪除開(kāi)始結(jié)點(diǎn)一個(gè)結(jié)點(diǎn).D.刪除地址為 p 的結(jié)點(diǎn)的后繼結(jié)點(diǎn).5、數(shù)組用來(lái)表示一個(gè)循環(huán)隊(duì)列，為當(dāng)前隊(duì)列頭元素的前一位置，為隊(duì)尾元素的位置，假定隊(duì)列中元素的個(gè)數(shù)小于，計(jì)算隊(duì)列中元素的公式為A.rf;C.nrf;B.（nfr）% n;D.（nrf）% n6、判定一個(gè)棧 ST（最多元素為

3、 m0）為空的條件是()AST-top0BST-top= =0CST-topm0，將其下三角部分（DST-top= =m0）按行序存放在一維數(shù)7、設(shè)矩陣 A 是一個(gè)對(duì)稱矩陣，為了節(jié)省組 B 1, n(n-1)/2 中，對(duì)下三角部分中任一元素 ai,j(ij), 在一維數(shù)組 B 中下標(biāo)k 的值是：i(i-1)/2+j-1i(i+1)/2+j-1i(i-1)/2+ji(i+1)/2+j8、線性表在情況下適用于使用鏈?zhǔn)浇Y(jié)構(gòu)實(shí)現(xiàn)。A.需經(jīng)常修改中的結(jié)點(diǎn)值B.需不斷對(duì)進(jìn)行刪除D.中結(jié)點(diǎn)結(jié)構(gòu)復(fù)雜C.中9、單鏈表的A.大于 1；的結(jié)點(diǎn)密度（B. 小于 1；）等于 1； D.不能確定C.a,1aaA 2,12

4、,2an,1an,2an,n 考生信專業(yè) 年級(jí)息欄學(xué)院系學(xué)號(hào)裝訂線10、設(shè)串 s1=ABCDEFG，s2=PQRST，函數(shù) con(x,y)返回x 和 y 串的連接串， subs(s, i, j)返回串s 的從序號(hào)i 開(kāi)始的j 個(gè)字符組成的子串，len(s)返回串 s 的長(zhǎng)度，則 con(subs(s1, 2, len(s2), subs(s1, len(s2), 2)的結(jié)果串是：BCDEFBCDEFGBCPQRSTBCDEFEF二、填空題：(每空 1.5 分，共 30 分)1 、 數(shù) 據(jù) 的結(jié) 構(gòu) 可 用 四 種 基 本 的方 法 表 示 , 分 別 是,索引與散列。2、在順序表中或刪除一個(gè)

5、元素，需要平均移動(dòng)元素，具體移動(dòng)的元素個(gè)數(shù)與有關(guān)。3、鏈表相對(duì)于順序表的優(yōu)點(diǎn)有和操作方便。4、在 n 個(gè)結(jié)點(diǎn)的單鏈表中要?jiǎng)h除已知結(jié)點(diǎn)*p,需找到,其時(shí)間復(fù)雜度為.5、設(shè)循環(huán)向量有 m 個(gè)元素，循環(huán)向量中有一個(gè)循環(huán)隊(duì)列，在循環(huán)隊(duì)列中設(shè)隊(duì)頭指針 front 指向隊(duì)頭元素，隊(duì)尾無(wú)名指是針指向隊(duì)尾元素后的一個(gè)空閑元素。.在循環(huán)隊(duì)列中，隊(duì)空標(biāo)志為隊(duì)滿標(biāo)志為.當(dāng) rear=front 時(shí)，隊(duì)列長(zhǎng)度為；當(dāng) rearFRONT 時(shí)，隊(duì)列長(zhǎng)度是。6 、向一個(gè)長(zhǎng)度為 n 的向量中刪除第 i 個(gè)元素(1 i n) 時(shí)， 需向前移動(dòng)個(gè)元素。7、三元素組表中的每個(gè)結(jié)點(diǎn)對(duì)應(yīng)于稀疏矩陣的一個(gè)非零元素，它包含有三個(gè)數(shù)據(jù)項(xiàng)，分

6、別表示該元素的、和。8、設(shè)目標(biāo) T=”abccdcdccbaa”，模式 P=“cdcc”，用樸素匹配算法時(shí)，第次匹配成功。9、子串的定位運(yùn)算稱為串的模式匹配；稱為目標(biāo)串，稱為模式。10、設(shè)數(shù)組 a160, 170的址為 2000，每個(gè)元素占 2 個(gè)單元，若以列a32,58。三、解答題：(每題 5 分，共 30 分)1、寫(xiě)出下列算法的語(yǔ)句頻度和時(shí)間復(fù)雜度。x=0;for(i=1;in;i+) for(j=i+1;j=2)叉樹(shù)的 K 叉鏈表表示中，有多少個(gè)空指針。3、已知一棵二叉樹(shù)的前序序列和中序序列分別為 abdghcefi 和 gdhbaecif,請(qǐng)畫(huà)出該二叉樹(shù)。4、畫(huà)出下列廣義表的圖形表示和

7、它們的(1) D(A(c), B(e), C(a, L(b, c, d)(2) J1(J2(J1, a, J3(J1), J3(J1)表示：5、設(shè)長(zhǎng)度為 n 的鏈隊(duì)列用單循環(huán)鏈表表示，若只設(shè)頭指針，則入隊(duì)，出隊(duì)操作的時(shí)間是什么？如果只設(shè)尾指針呢？6、利用廣義表的 head 和tail 操作寫(xiě)出函數(shù)表達(dá)式，把以下各題中的單元素 banana 從廣義表中分離出來(lái)：(1) L1(apple, pear, banana, orange)(2) L2(apple, pear), (banana, orange)(3) L3(apple), (pear), (banana), (orange) (4) L

8、4(apple), (pear), (banana), orange)(5) L5(apple), pear), banana), orange)(6) L6(apple, (pear, (banana), orange)四、算法題：(每題 10 分，共 20 分)1、 描述二叉樹(shù)的二叉鏈表表示的結(jié)構(gòu)，并給出中序遍歷二叉樹(shù)的算法。2、 設(shè)棧 S=(1,2,3,4,5,6,7) ，其中 7 為棧頂元素。簡(jiǎn)述函數(shù) f31 中第一個(gè)循環(huán)語(yǔ)句的功能；寫(xiě)出調(diào)用 f31(&s)后的 s。(stack 表示棧，queue 表示隊(duì)列) void f31(stack *s) queue q;stack t;initqueue(&q);i=0;initstack(&s);while(!stackempty(s)