2014年本科插班生考試《數(shù)據(jù)結(jié)構(gòu)》課程試卷

韓山師范學(xué)院2014年本科插班生考試試卷計(jì)算機(jī)科學(xué)與技術(shù)專業(yè)數(shù)據(jù)結(jié)構(gòu)試卷（A卷）題號(hào)得分一二三四五六總分評(píng)卷人得分評(píng)卷人一、單項(xiàng)選擇題（每題2分，共30分）題號(hào)答案題號(hào)答案1234567891011121314151.棧和隊(duì)列的共同特點(diǎn)是()。A.只允許在端點(diǎn)處插入和刪除元素B.都是先進(jìn)后出C.都是先進(jìn)先出D.沒有共同點(diǎn)2.用鏈接方式存儲(chǔ)的隊(duì)列，在進(jìn)行插入運(yùn)算時(shí)()。A.僅修改頭指針C.僅修改尾指針B.頭、尾指針都要修改D.頭、尾指針可能都要修改3.以下數(shù)據(jù)結(jié)構(gòu)中哪一個(gè)是非線性結(jié)構(gòu)？(A.隊(duì)列B.棧C.線性表D.二叉樹)4.設(shè)有一個(gè)二維數(shù)組A[m][n]，假設(shè)A[0][0]存放位置在644，A[2][2]存放位置在676，每個(gè)元素占一個(gè)空間，問A[3][3]存放在什么位置？A．688B．678C．692)。D．6965.樹最適合用來(lái)表示(A.有序數(shù)據(jù)元素B.無(wú)序數(shù)據(jù)元素C.元素之間具有分支層次關(guān)系的數(shù)據(jù)D.元素之間無(wú)聯(lián)系的數(shù)據(jù)6.二叉樹的第k層的結(jié)點(diǎn)數(shù)最多為()。A．2k-1B.2K+1C.2K-1D.2k-17.設(shè)有向無(wú)環(huán)圖G中的有向邊集合E={<1，2>，<2，3>，<3，4>，<1，4>}，則下列屬于該有向圖G的一種拓?fù)渑判蛐蛄械氖牵ǎ?。A.1,2,3,4B.2,3,4,1C.1,4,2,3D.1,2,4,38.下列關(guān)于數(shù)據(jù)結(jié)構(gòu)的敘述中，正確的是（）。A.數(shù)組是同類型值的集合B.樹是一種線性結(jié)構(gòu)C.一般情況下遞歸算法的程序結(jié)構(gòu)更為精煉、效率更高D.用一維數(shù)組存儲(chǔ)二叉樹，總是以先序遍歷的順序存儲(chǔ)各結(jié)點(diǎn)9.對(duì)于線性表（7，34，55，25，64，46，20，10）進(jìn)行散列存儲(chǔ)時(shí)，若選用H（K）=K%9作為散列函數(shù)，則散列地址為1的元素有（）個(gè)。A．110.設(shè)有6個(gè)結(jié)點(diǎn)的無(wú)向圖，該圖至少應(yīng)有()條邊才能確保是一個(gè)連通圖。A.5B.6C.7D.8B．2C．3D．411.在帶有頭結(jié)點(diǎn)的單鏈表HL中，要向表頭插入一個(gè)由指針p指向的結(jié)點(diǎn)，則執(zhí)行()。A.p->next=HL->next;HL->next=p;B.p->next=HL;HL=p;C.p->next=HL;p=HL;D.HL=p;p->next=HL;12.線性表采用鏈?zhǔn)酱鎯?chǔ)時(shí)，結(jié)點(diǎn)的存儲(chǔ)地址（）。A．必須是不連續(xù)的C．必須是連續(xù)的B．連續(xù)與否均可D．和頭結(jié)點(diǎn)的存儲(chǔ)地址相連續(xù)13.任何一個(gè)無(wú)向連通圖的最小生成樹（）。A.只有一棵B.一棵或多棵C.一定有多棵D.可能不存在14.設(shè)指針變量p指向單鏈表結(jié)點(diǎn)A，則刪除結(jié)點(diǎn)A的后繼結(jié)點(diǎn)B需要的操作為（）。A.p->next=p->next->nextB.p=p->nextC.p=p->next->nextD.p->next=p15.設(shè)某棵二叉樹的中序遍歷序列為ABCD，前序遍歷序列為CABD，則后序遍歷該二叉樹得到序列為（）。A.BCDAB.BADCC.CDABD.CBDA得分評(píng)卷人二、填空題（每空2分，共20分）1.一個(gè)算法的時(shí)間復(fù)雜度為(n3+n2log2n+14n)/n2，其數(shù)量級(jí)表示為________。2.假定一棵樹的廣義表表示為A（C，D（E，F(xiàn)，G），H（I，J）），則該樹的深度為___________，樹的度為_________。3.后綴算式923+-102/-的值為__________。中綴算式（3+4X）-2Y/3對(duì)應(yīng)的后綴算式為_______________________________。4.若用鏈表存儲(chǔ)一棵二叉樹時(shí)，每個(gè)結(jié)點(diǎn)除數(shù)據(jù)域外，還有指向左孩子和右孩子的兩個(gè)指針。在這種存儲(chǔ)結(jié)構(gòu)中，n個(gè)結(jié)點(diǎn)的二叉樹共有________個(gè)指針域，其中有________________個(gè)指針是空指針。5.有如下遞歸函數(shù)：voidf(intw){inti;staticintj=1;if(w>0){printf(“%d:”,j++);for(i=1;i<=w;i++)printf(“%d，”,w);printf(“\n”);f(w?1);}}調(diào)用語(yǔ)句f(3)的結(jié)果是______________________________。6.已知一有向圖的鄰接表存儲(chǔ)結(jié)構(gòu)如下：從頂點(diǎn)1出發(fā)，DFS遍歷的輸出序列是______________，BFS遍歷的輸出序列是________________。得分評(píng)卷人三、判斷題（對(duì)的劃√，錯(cuò)的劃×。每小題1分，共10分）（）1．調(diào)用一次深度優(yōu)先遍歷可以訪問到圖中的所有頂點(diǎn)。（）2．哈夫曼樹上只有樹葉或者雙支