【正文】 65 個(gè)結(jié)點(diǎn)的完全二叉樹(shù)其深度為（ ）。（ ） A． 23 B． 24 C． 25 D．無(wú)法 確定 標(biāo)準(zhǔn)答案： A 1串的長(zhǎng)度是（ ）。（ ） A． (n+1)/2 B． n(n1)/2 C． n(n1) D． n(n+1) 標(biāo)準(zhǔn)答案： B 如果待排序序列中兩個(gè)數(shù)據(jù)元素具有相同的值，在排序后它們的位置發(fā)生顛倒，則稱該排序是不穩(wěn)定的。（ ） A． a B． b C． (a) D． ((a)) 標(biāo)準(zhǔn)答案： C 數(shù)組 A中，每個(gè)元素 A的長(zhǎng)度為 3個(gè)字節(jié)，行下標(biāo) i從 1 到 8，列下標(biāo) j 從 1 到 10，從首地址 SA開(kāi)始連續(xù)存放在存儲(chǔ)器內(nèi)，存放該數(shù)組至少需要的單元數(shù)是（ C ）。（ ） A．有序數(shù)據(jù)元素 B．無(wú)序數(shù)據(jù)元素 C．元素之間具有分支層次關(guān)系的數(shù)據(jù) D．元素之間無(wú)聯(lián)系的數(shù)據(jù) 標(biāo)準(zhǔn)答案： C 設(shè)有兩個(gè)串 p 和 q，求 p 在 q 中首次出現(xiàn)的位置的運(yùn)算稱作（ ）。（ ） A． 24 B． 48 C． 53 D． 72 標(biāo)準(zhǔn)答案： C 1某二叉樹(shù)的先序序列和后序序列正好相反，則該二叉樹(shù)一定是（ ）的二叉樹(shù)。（ ） A．必須是連續(xù)的 B．部分地址必須是連續(xù)的 C．一定不是連續(xù)的 第 5 頁(yè) 共 24 頁(yè) D．連續(xù)不連續(xù)都可以 標(biāo)準(zhǔn)答案： D 2設(shè)有向圖有 n 個(gè)頂點(diǎn)和 e條邊，采用領(lǐng)接表作為其存儲(chǔ)表示，在進(jìn)行拓?fù)渑判驎r(shí)，總的計(jì)算時(shí)間為（ ）。（ ） A．單鏈表 B．雙鏈表 C．單循環(huán)鏈表 D．順序表 標(biāo)準(zhǔn)答案： D 3若待排序?qū)ο笮蛄性谂判蚯耙寻雌渑判虼a遞增順序排序，則采用（ ）方法比較次數(shù)最少。（ ） A． s→ link=p→ link； p→ link=s； B． p→ link=s； s→ link=q； C． p→ link=s→ link； s→ link=p； D． q→ link=s； s→ link =p； 第 7 頁(yè) 共 24 頁(yè) 標(biāo)準(zhǔn)答案： D 3算法分析的兩個(gè)主要方面是（ ）。（ ） 第 8 頁(yè) 共 24 頁(yè) A．順序存儲(chǔ) B．鏈?zhǔn)酱鎯?chǔ) C．索引存儲(chǔ) D．散列存儲(chǔ) 標(biāo)準(zhǔn)答案： D 4具有 2020 個(gè)節(jié) 點(diǎn)的二叉樹(shù)，其高度至少為（ ）。 S2=39。 D． 39。（ ） A． 3， 2， 5， 6， 4， 1 B． 1， 5， 4， 6， 2， 3 C． 2， 4， 3， 5， 1， 6 D． 4， 5， 3， 6， 2， 1 標(biāo)準(zhǔn)答案： B 5棧的插入和刪除操作在（ ）進(jìn)行。（ ） A．必須判別棧是否滿 B．對(duì)棧不作任何判別 C．必須判別棧是否空 D．判別棧元素的類型 標(biāo)準(zhǔn)答案： C 6組成數(shù)據(jù)結(jié)構(gòu)的基本單位是（ ）。DATA STRUCTURE39。（ ） A．鍵值有序的鏈接表 B．鏈接表但鍵值不一定有序 C．鍵值有序的順序表 D．順序表但鍵值不一定有序 第 13 頁(yè) 共 24 頁(yè) 標(biāo)準(zhǔn)答案： C 二、填空題（本大題共 48 小題，每小題 2 分，共 96 分） 7數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)被分為順序結(jié)構(gòu)、鏈接結(jié)構(gòu)、 ___、散列結(jié)構(gòu)四種。 標(biāo)準(zhǔn)答案：有窮性 7一個(gè)算法應(yīng)具備的 5 個(gè)特性為有窮性、 ___、可行性、輸入、輸出。 標(biāo)準(zhǔn)答案： O(n)。O(n2) 9前序序列和中序序列相同的二叉樹(shù)為 ___。18 第 15 頁(yè) 共 24 頁(yè) 9從一個(gè)棧刪除元素時(shí)，首先取出 ___。向下 10假定一棵樹(shù)的廣義表表示為 A(B(C(D,E),F,G(H,I,J)),K)，則度為 2 的結(jié)點(diǎn)數(shù)為 ___個(gè)。 標(biāo)準(zhǔn)答案： pnext=HL； HL=p； 10假定一組記錄的排序碼為（ 46， 79， 56， 38， 40， 80， 25， 34），在對(duì)其進(jìn)行快速排序的過(guò)程中，進(jìn)行第一次劃分后得到的排序碼序列為 ___。 標(biāo)準(zhǔn)答案： (3h1)/2 11對(duì)于一個(gè)順序?qū)崿F(xiàn)的共享?xiàng)?S[1? n]，棧頂指針?lè)謩e為 top1 和 top2， top1 由小到大， top2由大到小，其判斷下溢的條件是 ___；判斷上溢的條件是 ___。 標(biāo)準(zhǔn)答案： 0 11在一棵樹(shù)中， ___沒(méi)有前驅(qū)結(jié)點(diǎn)。 while (p!=NULL) { LNode *q=p。 ListNode * temp。請(qǐng)?jiān)跈M線處將程序補(bǔ)充完整。 else______________________________。 i3。L) { int i=0。 } } 標(biāo)準(zhǔn)答 案：刪除線性表中所有重復(fù)的元素。 QInsert(Q,QDelete(Q))。 newptrdata=item。請(qǐng)?jiān)诳瞻滋幪顚?xiě)語(yǔ)句，將程序補(bǔ)充完整。 標(biāo)準(zhǔn)答案： 13假定調(diào)用以下算法時(shí)棧 S 中已有 2 個(gè)元素（ 23， 16），其中 23 是棧底。 while (p!=NULL) { if (pdata= =x) n++。i++) { flag=0。 } } 標(biāo)準(zhǔn)答案：該算法的功能是：對(duì)數(shù)組 A中的 n 個(gè)元素進(jìn)行排序，稱為起泡算法。 TwoMerge(A, B,0,4,9)。 L,int i,ElemType x) { for(int j=。 BTreeNode *p=BT。 } } } 。 s[top]=p。j) [j+1]=[j]。 i10。 int BB(ElemType A[], int n, KeyType K) { for (int i=0。j=i。 } return n。S) { Pop(S)。 else { int dep1,dep2。 while ( pnext!=HL ) p=pnext。 QInsert(Q,QDelete(Q)+10)。 void AF(Queue amp。 while (j) { if([j] = =) { for (int k=j+1。 for(i=3。試畫(huà)出對(duì)其進(jìn)行折半搜索時(shí)做性能分析用的擴(kuò)充二叉搜索樹(shù)（判定樹(shù)），并計(jì)算搜索成功時(shí)的平均搜索長(zhǎng)度（ ASLsucc）和搜索不成功進(jìn)的平均搜索長(zhǎng)度（ ASLunsucc）。BST,const ElemTypeamp。data==x) { temp= flink。 qnext=HL。 標(biāo)準(zhǔn)答案：順序 。top1+1=top2 11在循環(huán)雙向鏈表中表頭結(jié)點(diǎn)的左指針域指向 ___結(jié)點(diǎn)，最后一個(gè)結(jié)點(diǎn)的右指針域指向 ___結(jié)點(diǎn)。 標(biāo)準(zhǔn)答案： 1。 標(biāo)準(zhǔn)答案： 1。 標(biāo)準(zhǔn)答案：鏈接 9一棵深度為 5 的滿二叉樹(shù)中的結(jié)點(diǎn)數(shù)為 ___個(gè)。 標(biāo)準(zhǔn)答案：插入 9一個(gè) n*n 的對(duì)稱矩陣，如果以行或列為主序存入內(nèi)存，則其容量為 ___。 標(biāo)準(zhǔn)答案： 3 x 5 ／ 6 － *＋ 8假定一棵樹(shù)的廣義表表示為 A(B(C(D,E),F,G(H,I,J)),K)，則度為 0 的結(jié)點(diǎn)數(shù)為 ___個(gè)。 標(biāo)準(zhǔn)答案： 37/12 8對(duì)于線性表 (18,25,63,50,42,32,90)進(jìn)行散列存儲(chǔ)時(shí)，若選用 H(K)=K % 9 作為散列函數(shù)，則散列地址為 0 的元素有 ___個(gè)，散列地址為 5 的元素有