數(shù)據(jù)結(jié)構(gòu)模擬試卷及參考答案

數(shù)據(jù)結(jié)構(gòu)模擬試卷(一)及參考答案單項(xiàng)選擇題（本大題共15小題，每小題2分，共30分）1．如果只想得到1024個(gè)元素組成的序列中的前5個(gè)最小元素，那么用(A)方法最快。A、起泡排序B、快速排序C、堆排序D、直接選擇排序2．算法分析的目的是（B）A．辨別數(shù)據(jù)結(jié)構(gòu)的合理性B．評(píng)價(jià)算法的效率C．研究算法中輸入與輸出的關(guān)系D．鑒別算法的可讀性3．在線性表的下列運(yùn)算中，不改變數(shù)據(jù)元素之間結(jié)構(gòu)關(guān)系的運(yùn)算是（C）A．插入 B．刪除C．定位 D．排序4．若進(jìn)棧序列為1，2，3，4，5，6，且進(jìn)棧和出?？梢源┎暹M(jìn)行，則可能出現(xiàn)的出棧序列為（D）A．3，2，6，1，4，5 B．5，6，4，2，3，1C．1，2，5，3，4，6 D．3，4，2，1，6，55．設(shè)串sl=″DataStructureswithJava″,s2=″it″，則子串定位函數(shù)index(s1,s2)的值為（A）A．15 B．16 C．17 D．186．一個(gè)順序存儲(chǔ)的線性表的第一個(gè)元素的存儲(chǔ)地址是100，每個(gè)元素的長(zhǎng)度為4，則第4個(gè)元素的存儲(chǔ)地址是（B）。A.108B.112C.116D.1207．從一個(gè)具有n個(gè)結(jié)點(diǎn)的單鏈表中查找其值等于x的結(jié)點(diǎn)，在查找成功的情況下，平均需要比較（C）個(gè)結(jié)點(diǎn)。A.nB.n/2C.(n+1)/2D.(n-1)/28．在任意一棵二叉樹(shù)的前序序列和后序序列中，各葉子之間的相對(duì)次序關(guān)系（D）A．不一定相同 B．互為逆序C．都不相同 D．都相同9．高度為5的二叉樹(shù)至多有結(jié)點(diǎn)數(shù)為（A）A.63B.32C.24D.6410．若用鄰接矩陣表示一個(gè)有向圖，則其中每一列包含的″1″的個(gè)數(shù)為（B）A．圖中每個(gè)頂點(diǎn)的出度 B．圖中每個(gè)頂點(diǎn)的入度C．圖中弧的條數(shù) D．圖中連通分量的數(shù)目11．圖的鄰接矩陣表示法適用于表示（C）A．無(wú)向圖 B．有向圖 C．稠密圖 D．稀疏圖12．在一個(gè)單鏈表中，若p所指的結(jié)點(diǎn)不是最后一個(gè)結(jié)點(diǎn)，在p之后插入s所指的結(jié)點(diǎn)，則執(zhí)行（D）。A.s->next=p;p->next=sB.p-next=s;s->next=pC.p=s;s->next=p->nextD.s->next=p->next;p->next=s13．下列排序算法中，其時(shí)間復(fù)雜度和記錄的初始排列無(wú)關(guān)的是（A）A．直接選擇排序 B．插入排序C．快速排序 D．冒泡排序14．若有序表的關(guān)鍵字序列為（b,c,d,e,f,g,q,r,s,t），則在二分查找關(guān)鍵字b的過(guò)程中，先后進(jìn)行比較的關(guān)鍵字依次為（B）A．f,d,b B．f,c,b C．g,c,b D．g,d,b15．如下圖所示的4棵二叉樹(shù)中，（C）不是完全二叉樹(shù)。ABCDABCD填空題（本大題共15小題，每小題2分，共30分）在數(shù)據(jù)結(jié)構(gòu)中，數(shù)據(jù)的邏輯結(jié)構(gòu)分線性結(jié)構(gòu)和非線性結(jié)構(gòu)。稱算法的時(shí)間復(fù)雜度為O(f(n))，其含義是指算法的執(zhí)行時(shí)間和___f(n)____的數(shù)量級(jí)相同。在一個(gè)長(zhǎng)度為n的單鏈表L中，刪除鏈表中*p的前驅(qū)結(jié)點(diǎn)的時(shí)間復(fù)雜度為_(kāi)____O(n)____。假設(shè)為循環(huán)隊(duì)列分配的向量空間為Q[20]，若隊(duì)列的長(zhǎng)度和隊(duì)頭指針值分別為13和17，則當(dāng)前尾指針的值為_(kāi)_10____。對(duì)于棧只能在___棧頂_____插入和刪除元素。通常從正確性、____可使用性___、可讀性、效率和健壯性等5個(gè)方面評(píng)價(jià)算法（包括程序）的質(zhì)量。在具有n個(gè)單元的循環(huán)隊(duì)列中，隊(duì)滿時(shí)共有n-1個(gè)元素。若對(duì)關(guān)鍵字序列（43，02，80，48，26，57，15，73，21，24，66）進(jìn)行一趟增量為3的希爾排序，則得到的結(jié)果為(15,02,21,24,26,57,43,66,80,48,73)。在索引存儲(chǔ)中，若一個(gè)索引項(xiàng)對(duì)應(yīng)數(shù)據(jù)對(duì)象表中的一個(gè)表項(xiàng)（記錄），則稱此索引為稠密索引，若對(duì)應(yīng)數(shù)據(jù)對(duì)象表中的若干個(gè)表項(xiàng)，則稱此索引為稀疏索引。二叉樹(shù)中度為0的結(jié)點(diǎn)數(shù)為30，度為1的結(jié)點(diǎn)數(shù)為30，總結(jié)點(diǎn)數(shù)為89。廣義表A((a，b，c)，(d，e，f))的表尾為（(d，e，f)）。設(shè)有一個(gè)順序棧S，元素sl，s2，s3，s4，s5，s6依次進(jìn)棧，如果6個(gè)元素的出棧順序?yàn)閟2，s3，s4，s6，s5，sl，則順序棧的容量至少應(yīng)為3。根據(jù)一組記錄(56，42，50，64，48)依次插入結(jié)點(diǎn)生成一棵AVL樹(shù)(高度平衡的二叉搜索樹(shù))時(shí)，當(dāng)插人到值為50的結(jié)點(diǎn)時(shí)需要進(jìn)行旋轉(zhuǎn)調(diào)整。n（n＞0）個(gè)頂點(diǎn)的無(wú)向圖最多有n(n-1)／2條邊。設(shè)無(wú)向圖的鄰接表如下圖所示，則該圖的邊的數(shù)目是5。判斷題(本大題共10小題，每小題1分，共10分)（×）鏈?zhǔn)酱鎯?chǔ)在插人和刪除時(shí)需要保持物理存儲(chǔ)空間的順序分配，不需要保持?jǐn)?shù)據(jù)元素之間的邏輯順序。（√）在用循環(huán)單鏈表表示的鏈?zhǔn)疥?duì)列中，可以不設(shè)隊(duì)頭指針，僅在鏈尾設(shè)置隊(duì)尾指針。（×）通常遞歸的算法簡(jiǎn)單、易懂、容易編寫，而且執(zhí)行的效率也高。（√）一個(gè)廣義表的表尾總是一個(gè)廣義表。（×）對(duì)于一棵具有n個(gè)結(jié)點(diǎn)，其高度為h的二叉樹(shù)，進(jìn)行任一種次序遍歷的時(shí)間復(fù)雜度為O（h）。（√）當(dāng)從一個(gè)最小堆中刪除一個(gè)元素時(shí)，需要把堆尾元素填補(bǔ)到堆頂位置，然后再按條件把它逐層向下調(diào)整，直到調(diào)整到合適位置為止。（×）存儲(chǔ)圖的鄰接矩陣中，鄰接矩陣的大小不但與圖的頂點(diǎn)個(gè)數(shù)有關(guān)，而且與圖的邊數(shù)也有關(guān)。（√）進(jìn)行折半搜索的表必須是順序存儲(chǔ)的有序表。（×）直接選擇排序是一種穩(wěn)定的排序方法。（×）在用單鏈表表示的鏈?zhǔn)疥?duì)列中，隊(duì)頭在鏈表的鏈尾位置。問(wèn)答題(本大題共5小題，每小題6分，共30分)1．由如圖所示的二叉樹(shù)，回答以下問(wèn)題。a.其中序遍歷序列為dgbaechif。b.其先序遍歷序列為abdgcefhi。c.其后序遍歷序列為gdbeihfca。aadcbefghi2．已知圖G=(V,E)，其中V＝{a,b,c,d,e,f,g}，E＝｛<a,b>,<a,g>,<b,g>,<c,b>,<d,c>,<d,f>,<e,d>,<f,a>,<f,e>,<g,c>,<g,d>,<g,f>｝，請(qǐng)畫出圖G，并寫出其鄰接矩陣和鄰接表表示。aabcgfedabcdefg鄰接矩陣：abcdefg100001000001100000010010100001000001100000010010001000000100011010abcdefg010123456abcdefg16Λ6Λ1Λ25Λ3Λ04Λ235Λ3．寫出利用直接選擇排序?qū)﹃P(guān)鍵字序列(40,24,80,39,43,18,20)進(jìn)行從小到大排序的每一趟結(jié)果。參考答案：18,24,80,39,43,40,2018,20,80,39,43,40,2418,20,24,39,43,40,8018,20,24,39,43,40,8018,20,24,39,40,43,8018,20,24,39,40,43,804．設(shè)A、B、C是不同的關(guān)鍵字且A>B>C，可組成6種不同的輸入順序。問(wèn)其中哪幾種輸入順序所構(gòu)造的二叉排序樹(shù)的高度為2?參考答案：4種。ABCACBCABCBA評(píng)分標(biāo)準(zhǔn)：次序不限，寫對(duì)一種得1分，4種全寫對(duì)得6分。若在4種正確答案之外，又多寫一種則只能得4分，若6種排列順序全寫上則0分。5．在如圖所示的AOE網(wǎng)中，試回答如下問(wèn)題：（1）計(jì)算出每個(gè)頂點(diǎn)所表示的事件的最早發(fā)生時(shí)間和最遲發(fā)生時(shí)間；（2）計(jì)算出每條邊所表示的活動(dòng)的最早開(kāi)始時(shí)間和最遲開(kāi)始時(shí)間；（3）找出此網(wǎng)絡(luò)中的關(guān)鍵活動(dòng)和關(guān)鍵路徑。664521187244abcehgkdf 事件的最早發(fā)生時(shí)間和最遲發(fā)生時(shí)間： 活動(dòng)的最早開(kāi)始時(shí)間和最遲開(kāi)始時(shí)間：網(wǎng)絡(luò)中的關(guān)鍵活動(dòng)：ab,be,eh,hk關(guān)鍵路徑:aàbàeàhàk數(shù)據(jù)結(jié)構(gòu)模擬試卷(二)單項(xiàng)選擇題（每小題2分，共30分）1.線性結(jié)構(gòu)的邏輯特征是除第一個(gè)節(jié)點(diǎn)和最后一個(gè)節(jié)點(diǎn)，其它節(jié)點(diǎn)都有。A．一個(gè)直接前趨和一個(gè)直接后繼B．多個(gè)直接前趨和一個(gè)直接后繼C．一個(gè)直接前趨和多個(gè)直接后繼D．多個(gè)直接前趨和多個(gè)直接后繼算法必須具備輸入、輸出和。A．計(jì)算方法B．排序方法C．解決問(wèn)題的有限運(yùn)算步驟D．程式序設(shè)計(jì)方法3.將遞歸過(guò)程轉(zhuǎn)化為非遞歸過(guò)程需用到。A．棧B．隊(duì)C．線性表D．鏈表4.在順序表上做增、刪節(jié)點(diǎn)運(yùn)算的平均時(shí)間復(fù)雜度是。A．O(1)B．O(n)C．O(log2n)D．O(n2)5.設(shè)二維數(shù)組A[0…m-1][0…n-1]按行優(yōu)先順序存儲(chǔ)，則元素A[i][j]的地址為。A．LOC(A[0][0])+(i*m+j)B．LOC(A[0][0])+(i*n+j)C．LOC(A[0][0])+[(i-1)*n+j-1]D．LOC(A[0][0])+[(i-1)*m+j-1]設(shè)目標(biāo)串T=“aababbadbbaa”，模式P=“bba”，則該模式匹配的有效位移為。A.4B.5C.7 D.107.把長(zhǎng)度為m的單鏈表接在長(zhǎng)度為n的單鏈表之后的算法的時(shí)間復(fù)雜度為。A．O(m)B．O(n)C．O(m+n)D．O(1)在一個(gè)單鏈表中，若P所指節(jié)點(diǎn)不是最后節(jié)點(diǎn)，在P之后插入S所指節(jié)點(diǎn)，則執(zhí)行。A．S->next=P->next;P->next=S;B．P->next=S->next;S->next=P;C．S->next=P;P->next=S;D．P->next=S;S->next=P;9.設(shè)將整數(shù)1,2,3,4,5依次進(jìn)棧，最后都出棧，出棧可以在任何時(shí)刻（只要棧不空）進(jìn)行，則出棧序列不可能是。A．23415B．54132C．23145D．1543210.循環(huán)隊(duì)列是空隊(duì)列的條件是。A．Q->rear==Q->frontB．(Q->rear+1)%maxsize==Q->frontC．Q->rear==0D．Q->front==011.設(shè)有一廣義表E=（a,b,(c,d)），其長(zhǎng)度為。A．2B．3C．4D．512.某二叉樹(shù)的前序遍歷序列為ABDEFC，中序遍歷序列為DBEFAC，則后序遍歷序列為。A．DFEBCAB．DBECFAC．BDAECFD．DBEFCA下列哪項(xiàng)不是利用查找表中數(shù)據(jù)元素的關(guān)系進(jìn)行查找的方法。A．有序表的查找B．二叉排序樹(shù)的查找C．平衡二叉樹(shù)D．散列查找下述幾種排序方法中，要求內(nèi)存量最大的是。A．插入排序B．快速排序C．歸并排序D．選擇排序在一個(gè)有向圖中，所有頂點(diǎn)的入度之和等于所有頂點(diǎn)的出度之和的倍。A．1/2B．1C．2D．4填空題(每空2分，共20分)16．?dāng)?shù)據(jù)結(jié)構(gòu)一般包括三個(gè)方面內(nèi)容：數(shù)據(jù)的，數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)及數(shù)據(jù)的運(yùn)算。17．在包含n個(gè)結(jié)點(diǎn)的順序表上做等概率插入運(yùn)算，平均要移動(dòng)_____個(gè)結(jié)點(diǎn)。18．隊(duì)列的特性是______。19．已知二叉樹(shù)中葉子數(shù)為30，僅有一個(gè)孩子的結(jié)點(diǎn)數(shù)為20，則總結(jié)點(diǎn)數(shù)為_(kāi)___。20．_______遍歷二叉排序樹(shù)中的結(jié)點(diǎn)可以得到一個(gè)遞增的關(guān)鍵字序列（選填“先序”、“中序”或“后序”）。21．n個(gè)節(jié)點(diǎn)的連通圖至少有_________條邊。22．在堆排序和快速排序中，如果從平均情況下排序的速度最快的角度來(lái)考慮，應(yīng)最好選擇排序。23．帶有一個(gè)頭結(jié)點(diǎn)的單鏈表head為空的條件是（假設(shè)指針域的名稱為next）_____。24．設(shè)一組初始關(guān)鍵字序列為(38，65，97，76，13，27，10)，則第3趟簡(jiǎn)單選擇排序后的結(jié)果為_(kāi)__________________。25．在拓?fù)渑判蛑?，拓?fù)湫蛄械牡谝粋€(gè)頂點(diǎn)必定是的頂點(diǎn)。簡(jiǎn)答題（每題6分，共36分）26．已知一棵樹(shù)邊的集合為｛<e,i>,<b,e>,<b,d>,<a,b>,<g,j>,<g,k>,<c,g>,<c,f>,<h,l>,<c,h>,<a,c>｝，畫出這棵樹(shù)，并回答下列問(wèn)題：哪個(gè)是根結(jié)點(diǎn)？哪些是葉子結(jié)點(diǎn)？哪些是結(jié)點(diǎn)g的祖先？樹(shù)的深度是多少？樹(shù)的度數(shù)是多少？27．以下面數(shù)據(jù)作為葉子結(jié)點(diǎn)的權(quán)值構(gòu)造一Huffman樹(shù)，畫出該樹(shù)并計(jì)算出其帶權(quán)路徑長(zhǎng)度。2，4，5，828．給定關(guān)鍵字集合(45,28,52,20,10,35,40,70,30,75,63,32)，從一棵空的二叉搜索樹(shù)開(kāi)始，按表中元素的次序構(gòu)造一棵二叉搜索樹(shù)。畫出從該二叉搜索樹(shù)中刪除關(guān)鍵碼28和52后的結(jié)果。29．試畫出下面帶權(quán)無(wú)向圖的一棵最小生成樹(shù)。95576843297abdcef30．寫出利用希爾排序?qū)﹃P(guān)鍵字序列(40,24,80,39,43,18,20,10,90,70)進(jìn)行從小到大排序的每一趟結(jié)果。（假設(shè)gap取值分別為5、3、1）31．設(shè)一散列表長(zhǎng)為13，采用線性探查法解決沖突。散列函數(shù)h(key)=key%13。（1）畫出在空表中依次插入關(guān)鍵字25,20,36,15,41,52,29,72,67后的散列表。（2）該散列表在等概率查找成功和不成功的平均查找長(zhǎng)度。綜合題（共14分）32．試對(duì)下圖所示的AOE網(wǎng)絡(luò)回答下列問(wèn)題：這個(gè)工程最早可能在什么時(shí)間結(jié)束。（2分）求每個(gè)活動(dòng)的最早開(kāi)始時(shí)間e()和最遲開(kāi)始時(shí)間l().（8分）確定哪些活動(dòng)是關(guān)鍵活動(dòng)。（4分）652101941512345611652101941512345611數(shù)據(jù)結(jié)構(gòu)模擬試卷(二)參考答案單項(xiàng)選擇題（每小題2分，共30分）1~5ACABB6~10ABABA11~15BADCB填空題(每空2分，共20分)16．?dāng)?shù)據(jù)結(jié)構(gòu)一般包括三個(gè)方面內(nèi)容：數(shù)據(jù)的邏輯結(jié)構(gòu)，數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)及數(shù)據(jù)的運(yùn)算。17．在包含n個(gè)結(jié)點(diǎn)的順序表上做等概率插入運(yùn)算，平均要移動(dòng)__n/2____個(gè)結(jié)點(diǎn)。18．隊(duì)列的特性是____先進(jìn)先出__。19．已知二叉樹(shù)中葉子數(shù)為30，僅有一個(gè)孩子的結(jié)點(diǎn)數(shù)為20，則總結(jié)點(diǎn)數(shù)為_(kāi)_79__。20．______中序_遍歷二叉排序樹(shù)中的結(jié)點(diǎn)可以得到一個(gè)遞增的關(guān)鍵字序列（選填“先序”、“中序”或“后序”）。21．n個(gè)節(jié)點(diǎn)的連通圖至少有_____n-1____條邊。22．在堆排序和快速排序中，如果從平均情況下排序的速度最快的角度來(lái)考慮，應(yīng)最好選擇快速排序排序。23．帶有一個(gè)頭結(jié)點(diǎn)的單鏈表head為空的條件是（假設(shè)指針域的名稱為next）__head->next==NULL___。24．設(shè)一組初始關(guān)鍵字序列為(38，65，97，76，13，27，10)，則第3趟簡(jiǎn)單選擇排序后的結(jié)果為_(kāi)______10,13,27,76,65,97,38____________。25．在拓?fù)渑判蛑?，拓?fù)湫蛄械牡谝粋€(gè)頂點(diǎn)必定是入度為零的頂點(diǎn)。簡(jiǎn)答題（每題6分，共36分）26．已知一棵樹(shù)邊的集合為｛<e,i>,<b,e>,<b,d>,<a,b>,<g,j>,<g,k>,<c,g>,<c,f>,<h,l>,<c,h>,<a,c>｝，畫出這棵樹(shù)，并回答下列問(wèn)題：哪個(gè)是根結(jié)點(diǎn)？哪些是葉子結(jié)點(diǎn)？哪些是結(jié)點(diǎn)g的祖先？樹(shù)的深度是多少？樹(shù)的度數(shù)是多少？參考答案：根結(jié)點(diǎn)是：a葉子結(jié)點(diǎn)是：difjklg的祖先：ac樹(shù)的深度：4樹(shù)的度數(shù)：327．以下面數(shù)據(jù)作為葉子結(jié)點(diǎn)的權(quán)值構(gòu)造一Huffman樹(shù)，畫出該樹(shù)并計(jì)算出其帶權(quán)路徑長(zhǎng)度。2，4，5，8參考答案：198116425198116425帶權(quán)路徑長(zhǎng)度：WPL=(2+4)*3+5*2+8=3628．給定關(guān)鍵字集合(45,28,52,20,10,35,40,70,30,75,63,32)，從一棵空的二叉搜索樹(shù)開(kāi)始，按表中元素的次序構(gòu)造一棵二叉搜索樹(shù)。畫出從該二叉搜索樹(shù)中刪除關(guān)鍵碼28和52后的結(jié)果。參考答案：(1)(2)（評(píng)分標(biāo)準(zhǔn)：每個(gè)圖3分）29．試畫出下面帶權(quán)無(wú)向圖的一棵最小生成樹(shù)。55768432997abdcef參考答案：554326abdcef(對(duì)1根線得1分，全對(duì)得6分)30．寫出利用希爾排序?qū)﹃P(guān)鍵字序列(40,24,80,39,43,18,20,10,90,70)進(jìn)行從小到大排序的每一趟結(jié)果。（假設(shè)gap取值分別為5、3、1）參考答案：Gap=5時(shí)18,20,10,39,43,40,24,80,90,70Gap=3時(shí)18,20,10,24,43,40,39,80,90,70Gap=1時(shí)10,18,20,24,39,40,43,70,80,90(每對(duì)1行得2分)31．設(shè)一散列表長(zhǎng)為13，采用線性探查法解決沖突。散列函數(shù)h(key)=key%13。（1）畫出在空表中依次插入關(guān)鍵字25,20,36,15,41,52,29,72,67后的散列表。（2）該散列表在等概率查找成功和不成功的平均查找長(zhǎng)度。參考答案：(1)散列表：（2分）00123456789101112521541296720723625 (2)ASLSUCC=(5*1+3*2+1*4)/9=5/3（2分） ASLNSUCC=(2+1+5+4+3+2+1+3+2+1+2+1+3)/13=30/13（2分）綜合題（共14分）32．試對(duì)下圖所示的AOE網(wǎng)絡(luò)回答下列問(wèn)題：這個(gè)工程最早可能在什么時(shí)間結(jié)束。（2分）求每個(gè)活動(dòng)的最早開(kāi)始時(shí)間e()和最遲開(kāi)始時(shí)間l().（8分）確定哪些活動(dòng)是關(guān)鍵活動(dòng)。（4分）652101941512345611652101941512345611數(shù)據(jù)結(jié)構(gòu)模擬試卷(三)單項(xiàng)選擇題（每小題2分，共30分）1．一個(gè)非空廣義表的表頭A．一定是子表B.一定是原子C．不能是子表D.可以是原子，也可以是子表2．下列排序算法中時(shí)間復(fù)雜度不受數(shù)據(jù)初始狀態(tài)影響，恒為O(n2)的是A．堆排序B.冒泡排序C．直接選擇排序D.快速排序3．設(shè)將整數(shù)1,2,3,4,5依次進(jìn)棧，最后都出棧，出?？梢栽谌魏螘r(shí)刻（只要棧不空）進(jìn)行，則出棧序列不可能是A．23415B.15432C．23145D.541324.算法必須具備輸入、輸出和A.計(jì)算方法B.排序方法C．解決問(wèn)題的有限運(yùn)算步驟D.程序設(shè)計(jì)方法5．拓?fù)渑判蜻\(yùn)算只能用于A．帶權(quán)有向圖B.連通無(wú)向圖C．有向無(wú)環(huán)圖D.無(wú)向圖6.在一個(gè)具有n個(gè)結(jié)點(diǎn)的有序單鏈表中插入一個(gè)新結(jié)點(diǎn)并仍然保持有序的時(shí)間復(fù)雜度是A.O(1)B.O(n)C.O(n2)D.O(nlogn)7．在一個(gè)無(wú)向圖中，所有頂點(diǎn)的度數(shù)之和等于圖的邊數(shù)的倍A．1/2B.1C.2D.48.設(shè)二維數(shù)組A[0..m-1][0..n-1]按行優(yōu)先順序存儲(chǔ)，則元素A[i][j]的地址為A．LOC(A[0][0])+(i*m+j)B．LOC(A[0][0])+(i*n+j)LOC(A[0][0])+[(i-1)*n+j-1]D.LOC(A[0][0])+[(i-1)*m+j-1]9．單鏈表的存儲(chǔ)密度A．大于1B.等于1C．小于1D.不能確定10.有n個(gè)節(jié)點(diǎn)的順序表中，算法的時(shí)間復(fù)雜度是O(1)的操作是訪問(wèn)第i個(gè)節(jié)點(diǎn)（1≤i≤n）在第i個(gè)節(jié)點(diǎn)后插入一個(gè)新節(jié)點(diǎn)（1≤i≤n）刪除第i個(gè)節(jié)點(diǎn)（1≤i≤n）將n個(gè)節(jié)點(diǎn)從小到大排序11.循環(huán)隊(duì)列SQ的存儲(chǔ)空間是數(shù)組d[m]，隊(duì)頭、隊(duì)尾指針?lè)謩e是front和rear，則執(zhí)行出隊(duì)后其頭指針front值是A．front=front+1B.front=(front+1)%(m-1)C.front=(front-1)%mD.front=(front+1)%m12．下列排序算法中時(shí)間復(fù)雜度不受數(shù)據(jù)初始狀態(tài)影響，恒為O(n2)的是A．堆排序B.冒泡排序C．直接選擇排序D.快速排序13.若要惟一地確定一棵二叉樹(shù)，只需知道該二叉樹(shù)的A．前序序列B.中序序列C．前序和后序序列D.中序和后序序列14．在所有排序方法中，關(guān)鍵字比較的次數(shù)與記錄的初始排列次序無(wú)關(guān)的是A．希爾排序B.冒泡排序C．插入排序D.選擇排序15．具有n個(gè)節(jié)點(diǎn)的完全二叉樹(shù)的深度為A．élog2(n+1)ù-1B.log2n+1C.log2nD.?log2n?填空題（每小題2分，共20分）1．?dāng)?shù)據(jù)的邏輯結(jié)構(gòu)分為兩大類，它們是線性結(jié)構(gòu)和。2．在單鏈表中（假設(shè)結(jié)點(diǎn)指針域名稱為next），刪除指針P所指結(jié)點(diǎn)的后繼結(jié)點(diǎn)的語(yǔ)句是。3．已知循環(huán)隊(duì)列用數(shù)組data[n]存儲(chǔ)元素值，用front,rear分別作為頭尾指針，則當(dāng)前元素個(gè)數(shù)為。4．若n為主串長(zhǎng)，m為子串長(zhǎng)，則串的樸素匹配算法最壞的情況下需要比較字符的總次數(shù)為_(kāi)___。5．廣義表((a),((b),j,(((d)))))的表尾是。6．已知二叉樹(shù)有61個(gè)葉子節(jié)點(diǎn)，且僅有一個(gè)孩子的節(jié)點(diǎn)數(shù)為45，則總節(jié)點(diǎn)數(shù)為。7．解決計(jì)算機(jī)與打印機(jī)之間速度不匹配問(wèn)題，須要設(shè)置一個(gè)數(shù)據(jù)緩沖區(qū)，應(yīng)是一個(gè)結(jié)構(gòu)。8．n個(gè)頂點(diǎn)e條邊的圖采用鄰接表存儲(chǔ)，深度優(yōu)先遍歷算法的時(shí)間復(fù)雜度為_(kāi)___________。9．對(duì)于n個(gè)關(guān)鍵字的集合進(jìn)行冒泡排序，在最壞情況下所需要的時(shí)間為_(kāi)_______。10．在一個(gè)長(zhǎng)度為n的順序表中的第i個(gè)元素（1≤i≤n）之前插入一個(gè)元素時(shí)，需向后移個(gè)元素。算法閱讀題（每空2分，共10分）1．設(shè)線性表的n個(gè)結(jié)點(diǎn)定義為（a0,a1,…,an-1），在順序表上實(shí)現(xiàn)的插入和刪除算法如下，請(qǐng)?jiān)诳瞻滋幪钊脒m當(dāng)內(nèi)容。(順序表的最大可容納項(xiàng)數(shù)為MaxSize)Template<classType>intSeqList<Type>::Insert(Type&x,inti){If(i<0||i>last+1||last==(1))return0;Else{Last++;For(intj=last;j<i;j--)data[j]=(2);(3);Return1;}}Template<classType>intseqList<Type>::Remove(Type&x){inti=Find(x);if(i>=0){last--;for(intj=(4);j<=last;j++)data[j]=(5);return1;}return0;}答題:(1)(2)(3)(4)(5)四、問(wèn)答題（共40分）1.已知一棵二叉樹(shù)的中序序列和序序列分別如下，請(qǐng)寫出它的后序序列。（10分）前序序列： ABDECRGMHK 中序序列：DBEARGCHKM答題:后序序列：2．