數(shù)據(jù)結(jié)構(gòu)期中試題及參考答案

1、１淮海工學(xué)院20092010學(xué)年第1學(xué)期數(shù)據(jù)結(jié)構(gòu)期中試卷(閉卷)題號(hào)一二三四五六七八九總分得分一、單項(xiàng)選擇題（本大題共一、單項(xiàng)選擇題（本大題共12小題，每小題小題，每小題2分，共分，共24分）在每小題分）在每小題列出的四個(gè)備選項(xiàng)中只有一個(gè)是符合題目要求的，請(qǐng)將其代碼填寫在題列出的四個(gè)備選項(xiàng)中只有一個(gè)是符合題目要求的，請(qǐng)將其代碼填寫在題后的括號(hào)內(nèi)。選錯(cuò)、多選或未選均無(wú)分。后的括號(hào)內(nèi)。選錯(cuò)、多選或未選均無(wú)分。1.按值可分解，數(shù)據(jù)類型通?？煞?/p>

2、為兩類，他們是【C】A靜態(tài)類型和動(dòng)態(tài)類型B.原子類型和表類型C原子類型和結(jié)構(gòu)類型D.數(shù)據(jù)類型和指針類型2.對(duì)于三個(gè)函數(shù)f(n)=2008896000，g(n)=88n2008和h(n)323=8888nlogn3n2，下列陳述中不成立的是【C】A.f(n)是O(g(n))B.g(n)是O(f(n))C.h(n)是O(n)D.h(n)是O()23.指針p、q和r依次指向某循環(huán)鏈表中三個(gè)相鄰的節(jié)點(diǎn)，交換節(jié)點(diǎn)q和節(jié)點(diǎn)r在表中的次序的程序段是【

3、A】A.pnext=rqnext=rnextrnext=qB.pnext=rrnext=qqnext=rnextC.rnext=qqnext=rnextpnext=rD.rnext=qpnext=rqnext=rnext4.若進(jìn)棧次序?yàn)閍bc且進(jìn)棧和出站可以穿插進(jìn)行，則可能出現(xiàn)的含個(gè)元素的出站序列個(gè)數(shù)是【B】A3B5C6D75.假設(shè)以數(shù)組A[n]存放循環(huán)隊(duì)列的元素，其頭指針front指向隊(duì)頭元素的前一個(gè)位置、為指針rear指向隊(duì)尾元素所

4、在的存儲(chǔ)位置，則在少用一個(gè)元素空間的前提下，隊(duì)列滿的判定條件為【D】Arear==frontB.(front1)%n==rearC.rear1==frontD.(rear1)%n==front6.串的操作函數(shù)str定義為：intstr(s)p=swhile(p!=’0’)preturnps則str(“abcde”)的返回值是【C】A3B4C5D67.二維數(shù)組A[10][6]采用行優(yōu)先的存儲(chǔ)方法，若每個(gè)元素占4個(gè)存儲(chǔ)單元，已知元素A[3]

5、[4]的存儲(chǔ)地址為1000，則元素A[4][3]的存儲(chǔ)地址為【A】A1020B1024C1036D12408.對(duì)廣義表L=(a())執(zhí)行操作tail(L)的結(jié)果是【B】A()B(())CaD(a)9.已知二叉樹的中序序列和后序序列均為ABCDEF，則該二叉樹的先序序列為【A】A.FEDCBAB.ABCDEFC.FDECBAD.FBDCEA10.已知森林F=各棵樹(i=1，2，3，4，5)中所含節(jié)12345點(diǎn)的個(gè)數(shù)分別為7，3，5，1，2

6、，則與F對(duì)應(yīng)的二叉樹的右子樹種的節(jié)點(diǎn)個(gè)數(shù)為【D】A2B3C8D1111.若非連通無(wú)向圖G含有21條邊，則G的頂點(diǎn)個(gè)數(shù)至少為【B】A7B8C21D2212.如圖所示的有向圖的拓?fù)湫蛄惺恰綛】A.cdbaeB.cadbeabed題12圖３四、算法閱讀題（本大題共3小題，每題8分，共24分）1.閱讀下列算法，并回答問題：（1）無(wú)向圖G如圖所示，寫出算法f30(voidDFS(Graphginti)從頂點(diǎn)出發(fā)進(jìn)行深度優(yōu)先搜索，訪問頂點(diǎn)時(shí)置vis

7、ited[j]為1intf30(Graphg)Intikf(i=0Ini)gn為圖g的定點(diǎn)數(shù)目visited[i]=0f(i=k=0Ini)if(visited[i]==0)KDFS(gi)returnk2.假設(shè)學(xué)生成績(jī)按學(xué)號(hào)增序從年初在帶頭結(jié)點(diǎn)的單鏈表中，類型定義如下：typedefstructNodeintid學(xué)號(hào)intsce成績(jī)structNodenextLNodeLinkList閱讀算法f31，并回答問題；（1）設(shè)節(jié)點(diǎn)結(jié)構(gòu)為成績(jī)