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

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

2、為兩類，他們是【C】A靜態(tài)類型和動態(tài)類型B.原子類型和表類型C原子類型和結(jié)構(gòu)類型D.數(shù)據(jù)類型和指針類型2.對于三個函數(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)鏈表中三個相鄰的節(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)棧次序為abc且進(jìn)棧和出站可以穿插進(jìn)行，則可能出現(xiàn)的含個元素的出站序列個數(shù)是【B】A3B5C6D75.假設(shè)以數(shù)組A[n]存放循環(huán)隊列的元素，其頭指針front指向隊頭元素的前一個位置、為指針rear指向隊尾元素所

4、在的存儲位置，則在少用一個元素空間的前提下，隊列滿的判定條件為【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)先的存儲方法，若每個元素占4個存儲單元，已知元素A[3]

5、[4]的存儲地址為1000，則元素A[4][3]的存儲地址為【A】A1020B1024C1036D12408.對廣義表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)的個數(shù)分別為7，3，5，1，2

6、，則與F對應(yīng)的二叉樹的右子樹種的節(jié)點(diǎn)個數(shù)為【D】A2B3C8D1111.若非連通無向圖G含有21條邊，則G的頂點(diǎn)個數(shù)至少為【B】A7B8C21D2212.如圖所示的有向圖的拓?fù)湫蛄惺恰綛】A.cdbaeB.cadbeabed題12圖３四、算法閱讀題（本大題共3小題，每題8分，共24分）1.閱讀下列算法，并回答問題：（1）無向圖G如圖所示，寫出算法f30(voidDFS(Graphginti)從頂點(diǎn)出發(fā)進(jìn)行深度優(yōu)先搜索，訪問頂點(diǎn)時置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é)生成績按學(xué)號增序從年初在帶頭結(jié)點(diǎn)的單鏈表中，類型定義如下：typedefstructNodeintid學(xué)號intsce成績structNodenextLNodeLinkList閱讀算法f31，并回答問題；（1）設(shè)節(jié)點(diǎn)結(jié)構(gòu)為成績