測(cè)試數(shù)據(jù)結(jié)構(gòu)

A.s->next=p->next;p->next=s;C.q->next=s;s->nextA.s->next=p->next;p->next=s;C.q->next=s;s->next=p;5.如圖所示的4棵二叉樹中， 6.如圖所示二叉樹的中序遍歷序列是 a測(cè)試一、選擇題TOC\o"1-5"\h\z1?一個(gè)棧的入棧序列是a、b、c、d、e,則棧的不可能輸出序列是 。edcba B.decba C.dceabD.abcde一個(gè)隊(duì)列的入隊(duì)序列是1、2、3、4,則隊(duì)列輸出序列是 。A.4、3、2、1 B.1、2、3、4 C.1、4、3、2 D.3、2、4、1判斷一個(gè)循環(huán)隊(duì)列QU（最多元素為m）為滿隊(duì)列的條件是 。A.QU->front==QU->rear B.QU->front!=QU->rearC.QU->front==（QU->rear+1）%mD.QU->front!=（QU->rear+1）%m4?在一個(gè)單鏈表中，已知q所指結(jié)點(diǎn)是p所指結(jié)點(diǎn)的前驅(qū)結(jié)點(diǎn)，若在q和p之間插入s結(jié)點(diǎn),則執(zhí)行 。p->next=s->next;s->next=p;D.p->next=s;s->next=q;不是完全二叉樹。A.abcdgef B.dfebagc C.dbaefcg D.defbagcTOC\o"1-5"\h\z已知某二叉樹的后序遍歷序列是dabec，中序遍歷序列是debac，前序遍歷序列 。A.acbed B.decab C.deabc D.cedba具有4個(gè)頂點(diǎn)的無(wú)向完全圖有 條邊。A.6 B.12 C.16 D.20已知一個(gè)圖如圖所示，若從頂點(diǎn)a出發(fā)按深度搜索法進(jìn)行遍 A歷，則可得到頂點(diǎn)序列為 ；按寬度搜索法進(jìn)行遍歷，則可得到頂點(diǎn)序列為 。A.abecdfB.acfebd C.aebcfd D.aedfcbc已知一有向圖的鄰接表存儲(chǔ)結(jié)構(gòu)如圖所示（1） 根據(jù)有向圖的深度優(yōu)先遍歷算法，從v1頂點(diǎn)出發(fā)，所得到的頂點(diǎn)序列是 1 。（2） 根據(jù)有向圖的寬度優(yōu)先遍歷算法，從v1頂點(diǎn)出發(fā)，所得到的頂點(diǎn)序列是 2 。A. v1,v2,v3,v5,v4 B. v1,v2,v3,v4,v5v1,v3,v4,v5,v2 D. v1,v4,v3,v5,v2A. v1,v2,v3,v4,v5 B. v1,v3,v2,v4,v5C.v1,v2,v3,v5,v4D.v1,v4,v3,v5,v2有一個(gè)有序表為{1,3,9,12,32,41,45,62,75,77,82,95,100},當(dāng)二分査找值為82的結(jié)點(diǎn)時(shí)， 次比較后査找成功。A.1B.2C.4D.8設(shè)哈希表長(zhǎng)m=14，哈希函數(shù)H(key)=key%11。表中有4個(gè)結(jié)點(diǎn)：addr(15)=4,addr(38)=5,addr(61)=6,addr(84)=7，其余地址為空TOC\o"1-5"\h\z如用二次探測(cè)再散列處理沖突，關(guān)鍵字為49的結(jié)點(diǎn)的地址是 。A.8B.3C.5D.9一組記錄的排序碼為(46,79,56,38,40,84),則利用堆排序方法建立的初始堆為 。A.79, 46, 56, 38, 40, 80 B.84, 79, 56, 38, 40, 46C.84, 79, 56, 46, 40, 38 D.84, 56, 79, 40, 46, 38一組記錄的排序碼為(46,79,56,38,40,84),則利用快速排序方法,以第一個(gè)記錄為基準(zhǔn)得到的一次劃分結(jié)果為 。A.38, 40, 46, 56, 79, 84 B.40, 38, 46, 79, 56, 84C.40, 38, 46, 56, 79, 84 D.40, 38, 46, 84, 56, 79二、填空題下面程序段的時(shí)間復(fù)雜度是 。for(i=0;i<n;i++)for(j=0;j<m;j++)

A[i][j]=0;在具有n個(gè)單元的循環(huán)隊(duì)列中，隊(duì)滿時(shí)共有 個(gè)元素的。在一個(gè)單鏈表中，p所指結(jié)點(diǎn)之前插入s所指向結(jié)點(diǎn)，可執(zhí)行如下操作：TOC\o"1-5"\h\z(1)s->next= ；(2)p->next=s；(3)t=p->data；p->data= ；s->data= ；已知二維數(shù)組A[m][n]采用行序?yàn)橹鞣绞酱鎯?chǔ)，每個(gè)元素占k個(gè)存儲(chǔ)單元，并且第一個(gè)元素的存儲(chǔ)地址是LOC(A[0][0]),則A[i]j]的地址是 一個(gè)稀疏矩陣如圖所示，則對(duì)應(yīng)的三元數(shù)組表示為 。_0020_30 0 000-15_0000_有一棵樹如圖所示，回答下面問題：⑴這棵樹的根結(jié)點(diǎn)是 ； 集這棵樹的葉子結(jié)點(diǎn)是 ;bVTVd結(jié)點(diǎn)c的度是 ; 嚴(yán)、、]這棵樹的度是 ; WY這棵樹的深度是 ; lg結(jié)點(diǎn)c的子女是 ； °結(jié)點(diǎn)c的父母結(jié)點(diǎn)是 7.一棵二叉樹的結(jié)點(diǎn)數(shù)據(jù)采用順序存儲(chǔ)結(jié)構(gòu)，存儲(chǔ)于數(shù)組T中，如圖所示，則該二叉樹的鏈接表示形式為 。1 2 3 4 5 67 8 9101112131415161718192021eafdgc?J?i7.一棵二叉樹的結(jié)點(diǎn)數(shù)據(jù)采用順序存儲(chǔ)結(jié)構(gòu)，存儲(chǔ)于數(shù)組T中，如圖所示，則該二叉樹的鏈接表示形式為 。1 2 3 4 5 67 8 9101112131415161718192021eafdgc?J?ihb在無(wú)權(quán)圖G的鄰接矩陣中，若A[i]|j]等于1,則等于A[j][i]= 。已知一圖的鄰接矩陣表示，計(jì)算第i個(gè)結(jié)點(diǎn)的入度的方法是 10.在分塊査找方法中，首先査找三、算法題由如圖所示的二叉樹（1）該二叉樹的中序線為 ；（2）該二叉樹對(duì)應(yīng)的森；已知一棵樹如圖所示，為 。然后再査找相應(yīng)的93.以數(shù)據(jù)集｛4,5,6,7,10,12,18｝為結(jié)點(diǎn)權(quán)值所構(gòu)造的哈夫曼樹為 ，其帶權(quán)路徑長(zhǎng)度為 已知如圖所示的有向圖，請(qǐng)給出該圖的:（1） 每個(gè)頂點(diǎn)的入/出度；（2） 鄰接矩陣；（3） 鄰接表；（4） 逆鄰接表。求下面這個(gè)圖的廣度優(yōu)先生成樹和深度優(yōu)先生成6.用普里母算法和克魯斯卡爾算法求下圖的最小生成樹。7?根據(jù)下圖以及圖的鏈?zhǔn)酱鎯?chǔ)寫出該圖的拓?fù)湫蛄?inlinkvexnext仆仆8.求下圖的關(guān)鍵路徑。設(shè)關(guān)鍵字序列為｛10、18、3、8、12、2、7｝，構(gòu)造一棵二叉排序樹。給定一個(gè)數(shù)組10，13，9，7，4，8，15，20，18,按給定順序建立一棵平衡二叉樹。對(duì)下圖的三階B-樹依次執(zhí)行下列操作。（1）插入70（2）插入3012.已知哈希表長(zhǎng)為12，關(guān)鍵碼集合為｛47,7,29,11,15,92,22,8,3｝，采用除留余數(shù)法構(gòu)造哈希函數(shù)。解決沖突的方法分別有（1）設(shè)為線性探測(cè)再散列（2）二次探測(cè)法處理沖突。并求出每種查方法的平均查找復(fù)雜度。已知表長(zhǎng)為14的哈希表，采用除留余數(shù)法構(gòu)造哈希函數(shù):H（key）=key%13,鏈地址法處理沖突，將關(guān)鍵字集合｛19,14,23,1,68,20,3,84,27,55,11,10,79,24｝填入哈希表；并求其平均查找復(fù)雜度。給出一組關(guān)鍵字T=（12，2，16，30，8，28，4，10，20，6，18）。寫出用下列算法