【正文】 的 (B)連續(xù)不連續(xù)都可以(c)部分地址必須是連續(xù)的 (D)必須是不連續(xù)的8．具有2000個(gè)結(jié)點(diǎn)的二叉樹，其高度至少為( )。6．下面程序段的時(shí)間復(fù)雜度為( )。（ ）5．二叉排序樹中，任一結(jié)點(diǎn)的值都大于或等于其孩子的值。 4．快速排序?yàn)槭裁词遣环€(wěn)定的排序?試舉例說(shuō)明。 R[j1]=R[j]。8．設(shè)鍵值序列為{k1，k2，…，kn}，建堆和排序全過(guò)程共需進(jìn)行____________次堆調(diào)整。 (A)1 (B)2 (C)3 (D)48．在內(nèi)部排序中，排序時(shí)不穩(wěn)定的有( )。( )7．哈希表的查找效率主要取決于哈希建表時(shí)所選取的哈希函數(shù)和處理沖突的方法。2．設(shè)計(jì)一個(gè)算法，求出指定結(jié)點(diǎn)在給定的二叉排序樹中所在的層次。 bitreptr * bstsearch(bitreptr *t，keytype k) { if (t==NULL) return NULL。 (A)25 (B)7 (C)10 (D) 110．在內(nèi)部排序中，排序時(shí)不穩(wěn)定的有( ) (A)插入排序 (B)冒泡排序 (C)快速排序 (D)歸并排序二、填空題(22分)1．具有64個(gè)結(jié)點(diǎn)的完全二叉樹的深度為_________________。 (A)理想結(jié)構(gòu)，物理結(jié)構(gòu) (B)理想結(jié)構(gòu)，抽象結(jié)構(gòu) (c)物理結(jié)構(gòu)，邏輯結(jié)構(gòu) (D)抽象結(jié)構(gòu)，邏輯結(jié)構(gòu)2．線性表采用鏈?zhǔn)酱鎯?chǔ)時(shí)，其地址( )。( )4．一棵滿二叉樹同時(shí)又是一棵平衡樹。 2．一棵完全二叉樹共有21個(gè)結(jié)點(diǎn)，現(xiàn)順序存放在一個(gè)矢量中，矢量的下標(biāo)正好為結(jié)點(diǎn)的序號(hào)，試問(wèn)序號(hào)為12的雙親結(jié)點(diǎn)存在嗎?為什么?(4分) 3．線性表有順序表和鏈表兩種存儲(chǔ)結(jié)構(gòu)，簡(jiǎn)述各自的優(yōu)缺點(diǎn)。 else return(1)。2．循環(huán)鏈表的主要優(yōu)點(diǎn)是__________________。 (A)數(shù)據(jù)項(xiàng) (B)數(shù)據(jù)類型 (C)數(shù)據(jù)元素 (D)數(shù)據(jù)變量2．線性表的鏈接實(shí)現(xiàn)有利于( )運(yùn)算。(A)13 (B)33 (C)18 (D)409．如果結(jié)點(diǎn)A有3個(gè)兄弟，且B為A的雙親，則B的度為( )。 } else { i=_________________。三、應(yīng)用題(16分) 1．設(shè)二叉樹的順序存儲(chǔ)結(jié)構(gòu)如下：(4分)1234567891011121314151617181920EAF^D^H^^C^^^GI^^^^B (1)根據(jù)其存儲(chǔ)結(jié)構(gòu)，畫出二叉樹。(10分)五、判斷題(10分)1．具有線性序關(guān)系的集合中，若a，b是集合中的任意兩個(gè)元素，則必有ab的關(guān)系。 ( )9．表中的每一個(gè)元素都有前驅(qū)和后繼元素。 (A)二叉平衡樹 (B)二叉排序樹 (c)堆的形狀 (D)以上都不是7．對(duì)于含有n個(gè)頂點(diǎn)e條邊的無(wú)向連通圖，利用Prim算法生成最小代價(jià)生成樹其時(shí)間復(fù)雜度為( )，利用Kruskal時(shí)間復(fù)雜度為( )。6．設(shè)圖G的頂點(diǎn)數(shù)為n，邊數(shù)為e，第i個(gè)頂點(diǎn)的度數(shù)為D(vi)則e＝________________(即邊數(shù)與各頂點(diǎn)的度數(shù)之間的關(guān)系)。2．設(shè)有5000個(gè)無(wú)序的元素，希望用最快的速度挑選出其中前10個(gè)最大的元素，在快速排序、堆排序和基數(shù)排序方法中，采用哪種方法最好?為什么?3．對(duì)于下圖，試給出(1)每個(gè)頂點(diǎn)的入度和出度(2)鄰接矩陣，(3)逆鄰接表；(4)強(qiáng)連通分量。( )4．若有一個(gè)葉子結(jié)點(diǎn)是某子樹的中序遍歷的最后一個(gè)結(jié)點(diǎn)，則它必須是該子樹的先序遍歷的最后一個(gè)結(jié)點(diǎn)。 (A)插人 (B)讀表元 (C)查找 (D)定位3．中序遍歷一棵二叉排序樹所得到的結(jié)點(diǎn)訪 (A)遞增或遞減 (B)遞減 (C)遞增 (D)無(wú)序4．SubStr(‘DATA STRUCTURE’，6，9)=（ ）。5．后序序列和中序序列相同的二叉樹為_________________。 for(j=n。 }三、應(yīng)用題(24分) 1．已知一棵二叉樹的中序遍歷結(jié)果為DBHEAFICG，先序遍歷結(jié)果為ABDEFHCFIG，試畫出該二叉樹。正確的打√，錯(cuò)誤的打X)1．如果某數(shù)據(jù)結(jié)構(gòu)的每一個(gè)元素都最多只有一個(gè)直接前驅(qū)和一個(gè)直接后繼，則元素必為線性表。 (A)2n 〔B)n (C)n/2 (D)n(n1)2．設(shè)連通圖G的頂點(diǎn)數(shù)為n，則G的生成樹的邊數(shù)為( ) (A)n (B)n一1 (C)2n (D) 2n13．下列哪種排序需要的附加存儲(chǔ)開銷最小( )。j=n1。( )2．二叉排序樹的左、右子樹都是二叉排序樹。( )10．作為解決一類特定問(wèn)題的算法，不能沒(méi)有輸入運(yùn)算項(xiàng)。6．哈希表的兩種形式是：__________和__________。(8分)2．我們用鏈表來(lái)存儲(chǔ)多項(xiàng)式, 其中, ,試編寫求微商的算法。im。(A) n/2 (B) n (C) (n+1)/2 (D) (n1)/24．對(duì)一個(gè)具有n個(gè)元素的線性表，建立其有序單鏈表的時(shí)間復(fù)雜度為( )。 pnext=s。 pnextprior=s。 (A)Shell排序 (c)直接插入排序15．已知8個(gè)元素(34，76，45，18，26，54，92，65)，按照依次插入結(jié)點(diǎn)的方法生成一棵二叉排序樹，該樹的深度為( )。( )2．在單鏈表中任何兩個(gè)元素的存儲(chǔ)位置之間都有固定的聯(lián)系，因此可以從首結(jié)點(diǎn)進(jìn)行查找任何一個(gè)元素。( )四、應(yīng)用題(20分)1．已知—個(gè)長(zhǎng)度為12的表{Jan，F(xiàn)eb，Mar，Apr，May，June，July，Aug，Sep，Oct，Nov，Dec}。試編寫一個(gè)刪除表中所有值大于min且小于max的元素的算法。(A)4 （B)5 (C)6 (D)205．在具有N個(gè)單元的順序存儲(chǔ)的循環(huán)隊(duì)列中，假定front和rear分別為隊(duì)首指針和隊(duì)尾指針，則判斷隊(duì)空的條件為( )。6．一個(gè)具有5個(gè)結(jié)點(diǎn)的有向圖最少有____________條弧。( )5．在冒泡排序中，關(guān)鍵碼的比較次數(shù)與記錄的初始排列無(wú)關(guān)。(1)畫出該有向圖的鄰接矩陣。int push(STACK *s, int e){if(__________________) return 0。 *rchild。}3．寫出以下程序的輸出結(jié)果。}main(){ Printf(“%d\n”, strc(“student”, “study”))。 (A)3 (B)4 (C)5 (D)12．設(shè)有一個(gè)棧，元素的進(jìn)棧次序?yàn)锳，B，C，D，E，下列( )是不可能的出棧序列。( )2．先序遍歷一棵一又搜索樹所得的結(jié)點(diǎn)訪問(wèn)序列不可能是鎂值遞增序列、( )3．若有一個(gè)葉子結(jié)點(diǎn)是某子樹的中序遍歷的最后一個(gè)結(jié)點(diǎn)，則它必須是該子樹的先序遍歷的最后一個(gè)結(jié)點(diǎn)。3．一個(gè)無(wú)向連通圖有6個(gè)頂點(diǎn)7條邊，則其生成樹有_____________條邊。(4分)2．給出右圖所示二叉樹中序遍歷結(jié)果。(4分)Typedef struct { int data[100]。}2．以下函數(shù)ins的功能是在順序表a中找到第一個(gè)值為x的元素，然后在該元素之前插入一個(gè)值為y的元素。 if( ________________ ) return 0。 ________________ =y。六、編程題(共15分)1．已知二叉樹結(jié)點(diǎn)數(shù)據(jù)結(jié)構(gòu)如下，編寫算法求二叉樹的非葉子結(jié)點(diǎn)數(shù)目。 Struct LinkNode *next。 (A)10 (B)11 (C)19 (D)2l 8．一個(gè)100100的三角矩陣a采用行優(yōu)先壓縮存儲(chǔ)后，如果首元素a[0][0]是第—個(gè)元素，那么a[4][2]是第( )個(gè)元素。( )7．對(duì)長(zhǎng)度為100的有序線性表用折半查找時(shí)，最小比較次數(shù)為0。 7．無(wú)向圖用鄰接矩陣存儲(chǔ)，其所有元素之和表示無(wú)向圖的__________。(4分)4．用Prim算法(一條頂點(diǎn)一條頂點(diǎn)加入生成樹)求下圖的最小生成樹。(4分)bsort(int a[], int n){int n, i, j, tmp。} }}}2．在單鏈表(表首指針為head)的元素中找出最后一個(gè)值為e的元素，返回其指針；如果找不到，返回NULL。 ________________ 。if(i==1){printf(%d\n,treedata)。 int length。(A)n一1 (B)n (C)n十1 (D) n log2 n7．總共3層的完全二叉樹，其結(jié)點(diǎn)數(shù)至少有( )個(gè)。( )6．任何一棵二叉樹，不可能沒(méi)有葉子結(jié)點(diǎn)。5．一棵深度為5的二叉樹，至少有_______________個(gè)葉子結(jié)點(diǎn)。(5分) 4．已知左下圖是一個(gè)無(wú)向圖。(4分)typedef struct LinkNode{int data。 pf=pfnext)。i1=0。完成以下算法。 else if(c0) xe[i ________________]=xe[i]。struct LinkNode *next。 (A)先進(jìn)先出 (B)后進(jìn)先出 (c)只能進(jìn)行插入 (D)只能進(jìn)行刪除6．在有n個(gè)結(jié)點(diǎn)的二叉鏈表中，值為非空鏈域的個(gè)數(shù)為( )。( ) 3．在鏈隊(duì)列中，即使不設(shè)置尾指針也能進(jìn)行人隊(duì)操作。（ ）三、填空題(每空2分，共計(jì)20分) 1．設(shè)單鏈表中指針p指著結(jié)點(diǎn)A，若要?jiǎng)h除A之后的結(jié)點(diǎn)(假設(shè)存在), 則需要修改指針的操作為_______________。 8．在有序表A[1…18]中，采用折半查找法查找元素值等于A[7]的元素，所比較過(guò)的元素的下標(biāo)依次為_____________。(每空2分)int BinSearch(SqList R, KeyType K){／* 參數(shù)R為線性表，元素從0到n，R具有字段key為關(guān)鍵碼，參數(shù)K為待查關(guān)鍵碼 *／int i=0, j=n。在空格處填上合適的語(yǔ)句或表達(dá)式完成該算法。 /* 添加到C中 */ i++。 /* 再次遞歸調(diào)用 */ } }____________________________________________________六、編程題(共15分) 1．編寫函數(shù)用于實(shí)現(xiàn)將一棵二叉樹中所有子樹左、右交換。struct node *next } *LinkList。(6分)typedef struct node{Datatype Data。 }}/* while */=k。C{ int i=1,j=1,k=0。while(ij){ m=(i+j)/2。四、簡(jiǎn)答題(每小題5分，共30分)1．己知一棵樹的雙親表示存儲(chǔ)映像圖如下所示，試畫出該樹的邏輯示意圖2．己知一帶權(quán)有向圖的鄰接矩陣表示如下，試畫出其邏輯圖。 3．字符串S1＝39。( )5．對(duì)稱矩陣的存儲(chǔ)只需要存儲(chǔ)一半的數(shù)據(jù)元素。 (A)空或只有一個(gè)結(jié)點(diǎn) (B)高度等于其結(jié)點(diǎn)數(shù) (c)任一結(jié)點(diǎn)無(wú)左孩子 (D)任一結(jié)點(diǎn)無(wú)右孩子8．在具有n個(gè)結(jié)點(diǎn)且為完全二叉樹的二叉排序樹中查找一個(gè)關(guān)鍵碼，其平均比較次數(shù)的數(shù)量級(jí)為( )。模擬試題10一、選擇題(每小題1分，共10分)1．若線性表最常用的操作是存取第i個(gè)元素及其前驅(qū)元素的值，則采用( )存儲(chǔ)方式最節(jié)省時(shí)間。return c。 int length。while(i1=i2){ k=(i1+i2)/2。 free(p)。}Node。(5分) (2)基于你給出的鄰接矩陣，求從頂點(diǎn)A出發(fā)的深度優(yōu)先遍歷。7．衡量一個(gè)算法的優(yōu)劣主要看它的______________效率和_______________效率。（ ）。〔A)O(n) (B)O(n2) (C)O(log2n) (D)0(n3log2n)二、判斷題(每題1分，共8分。模擬試題9一、選擇題(每小題1分，共8分)1．設(shè)有一個(gè)10階的對(duì)稱矩陣a，采用壓縮存儲(chǔ)方式，以行序?yàn)橹鞔鎯?chǔ)，a[0][0]的存儲(chǔ)地址為100，每個(gè)元素占1個(gè)地址空間，則a[3][2]的地址為( )。}outi( ______________ )。return q。(6分)Typedef struct LinkNode{ int data。 i1。(4分)(2)畫出最終的最小生成樹。四、簡(jiǎn)答題(共38分)1．寫出線性表(26，4，12，25，30，6，15，20．16，2，18)采用二路歸并排序算法排序后，第一趟和第二趟結(jié)束時(shí)的結(jié)果。( )三、填空題(每題2分，共15分)1．?dāng)?shù)據(jù)結(jié)構(gòu)有______