數(shù)據(jù)結(jié)構(gòu)試卷及其規(guī)范標(biāo)準(zhǔn)答案

-`《數(shù)據(jù)結(jié)構(gòu)》試卷及答案1．算法分析的目的是(C )。A.找出數(shù)據(jù)結(jié)構(gòu)的合理性 B.研究算法中輸入和輸出的關(guān)系謝謝閱讀C.分析算法的效率以求改進(jìn) D.分析算法的易懂性和文檔性謝謝閱讀2．（ B）是具有相同特性數(shù)據(jù)元素的集合，是數(shù)據(jù)的子集。精品文檔放心下載A.數(shù)據(jù)符號(hào) B.數(shù)據(jù)對(duì)象 C.數(shù)據(jù) D.數(shù)據(jù)結(jié)構(gòu)3．用鏈表表示線性表的優(yōu)點(diǎn)是( C )。A.便于隨機(jī)存取 B.花費(fèi)的存儲(chǔ)空間比順序表少C.便于插入與刪除 D.數(shù)據(jù)元素的物理順序與邏輯順序相感謝閱讀同4．輸入序列為（A,B,C,D）不可能的輸出有（D）。精品文檔放心下載A.(A,B,C,D) B.(D,C,B,A) C.(A,C,D,B) D.(C,A,B,D)感謝閱讀5．在數(shù)組表示的循環(huán)隊(duì)列中，front、rear分別為隊(duì)列的頭、尾指針，maxSize為數(shù)組的最大長(zhǎng)度，隊(duì)滿的條件是(B)。謝謝閱讀A. front=maxSizeC. rear=maxSize

B. (rear+1)%maxSize=frontD. rear=front6．設(shè)有串t='Iamagoodstudent'，那么Substr(t,6,6)=（精品文檔放心下載A.student B.agoods C.good感謝閱讀

D）。

D.agood7．設(shè)有一個(gè)對(duì)稱矩陣A，采用壓縮存儲(chǔ)方式，以行序?yàn)橹餍虼鎯?chǔ)a11為第一個(gè)謝謝閱讀元素，其存儲(chǔ)地址為1，每個(gè)元素占一個(gè)地址空間，則

a85地址為（

B

）。A.23

B.33

C.18

D. 408．已知廣義表LS=(A,(B,C,D),E)運(yùn)用head和tail函數(shù)，取出LS中原子B的運(yùn)精品文檔放心下載算（C

）。A.Gethead(Gethead(LS))C.Gethead(Gethead(Gettail(LS)))感謝閱讀

B.Gettail(Gethead(LS))D.Gethead(Gettail(LS))-`9．若已知一棵二叉樹(shù)先序序列為ABCDEFG，中序序列為CBDAEGF，則其后序序列為(A)。感謝閱讀A. CDBGFEA

B. CDBFGEAC. CDBAGFE

D. BCDAGFE10．下列存儲(chǔ)形式中，(C )不是樹(shù)的存儲(chǔ)形式。A.雙親表示法 B.左子女右兄弟表示法C.廣義表表示法 D.順序表示法11．對(duì)待排序的元素序列進(jìn)行劃分，將其分為左、右兩個(gè)子序列，再對(duì)兩個(gè)子序精品文檔放心下載列施加同樣的排序操作，直到子序列為空或只剩一個(gè)元素為止。這樣的排序方法感謝閱讀(C)。A.直接選擇排序 B.直接插入排序C.快速排序 D.起泡排序12．采用折半查找方法進(jìn)行查找，數(shù)據(jù)文件應(yīng)為（ A），且限于（ ）。精品文檔放心下載A.有序表 順序存儲(chǔ)結(jié)構(gòu)

B.有序表 鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)C.隨機(jī)表 順序存儲(chǔ)結(jié)構(gòu)

D.隨機(jī)表 鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)13．就平均查找速度而言，下列幾種查找速度從慢至快的關(guān)系是（B）精品文檔放心下載A.順序折半哈希分塊C.分塊折半哈希順序

B.順序分塊折半哈希D.順序哈希分塊折半14．執(zhí)行下面程序段時(shí)，執(zhí)行S語(yǔ)句的次數(shù)為（D ）感謝閱讀for(intI=1;I<=n;I++)for(intj=1;j<=I;j++)S;A. n2 B. n2/2 C. n(n+1) D. n(n+1)/2謝謝閱讀15．串是一種特殊的線性表，其特殊性體現(xiàn)在（B）A.可以順序存儲(chǔ) B.數(shù)據(jù)元素是一個(gè)字符-`C.可以鏈接存儲(chǔ) D.數(shù)據(jù)元素可以是多個(gè)字符16．樹(shù)的基本遍歷策略分為先根遍歷和后根遍歷；二叉樹(shù)的基本遍歷策略可分為精品文檔放心下載先序遍歷、中序遍歷和后序遍歷。結(jié)論(A)是正確的。精品文檔放心下載A.樹(shù)的先根遍歷序列與其對(duì)應(yīng)的二叉樹(shù)的先序遍歷序列相同感謝閱讀B.樹(shù)的后根遍歷序列與其對(duì)應(yīng)的二叉樹(shù)的先序遍歷序列相同精品文檔放心下載C.樹(shù)的先根遍歷序列與其對(duì)應(yīng)的二叉樹(shù)的中序遍歷序列相同謝謝閱讀D.以上都不對(duì)17．由五個(gè)分別帶權(quán)值為9，2，3，5，14的葉子結(jié)點(diǎn)構(gòu)成的一棵哈夫曼樹(shù)，該樹(shù)的帶權(quán)路徑長(zhǎng)度為(C)。感謝閱讀A.60 B.66 C.67 D.5018．一棵二叉樹(shù)有67個(gè)結(jié)點(diǎn)，這些結(jié)點(diǎn)的度要么是0，要么是2。這棵二叉樹(shù)中度為2的結(jié)點(diǎn)有(A)個(gè)精品文檔放心下載A.33 B.34 C.32 D.3019．有一個(gè)有序表為{1,3,9,12,32,41,45,62,75,77,82,95,100},當(dāng)二分查找值82為的結(jié)點(diǎn)時(shí)，（C）次比較后查找成功。感謝閱讀A. 1 B. 2 C. 4 D. 820．若有文件的關(guān)鍵字序列為：[265][301][751][129][937][863][742][694][076]感謝閱讀[438]，以下為二路歸并排序過(guò)程。第二趟為:DA.[265301][129751][863937][694742][076438]精品文檔放心下載B.[076129265301438694742751863937]謝謝閱讀C.[129265301694742751863937][076438]精品文檔放心下載D.[129265301751][694742863937][076438]謝謝閱讀二、填空題（本大題共6小題，每空2分，共12分；答案填在下表內(nèi)）感謝閱讀算法是指令的有限序列，其中每一條指令表示一個(gè)或多個(gè)操作，此外，一個(gè)算法還具有五個(gè)重要特性，它們分別是__有窮性確定性可行性-,感謝閱讀-`有零或多個(gè)輸入和有一或多個(gè)輸出。2算法優(yōu)劣的五個(gè)標(biāo)準(zhǔn)是正確性、可使用性、-可讀性

健壯性

效率__。有n個(gè)球隊(duì)參加的足球聯(lián)賽按主客場(chǎng)制進(jìn)行比賽，共需進(jìn)行n(n-1)場(chǎng)比賽。精品文檔放心下載設(shè)有串t='Iamastudent'，s='good'，那么Concat(t,s)='Iamastudentgood'，Substr(t,8,7)='student'精品文檔放心下載在解決計(jì)算機(jī)主機(jī)與打印機(jī)之間速度不匹配時(shí)通常設(shè)置一個(gè)打印數(shù)據(jù)緩沖區(qū)，主機(jī)將要輸出的數(shù)據(jù)依次寫入該緩沖區(qū)，而打印機(jī)從該緩沖區(qū)中取出數(shù)據(jù)打印。該緩沖區(qū)應(yīng)該是一個(gè)隊(duì)列結(jié)構(gòu)，其主要特點(diǎn)是先進(jìn)先出。精品文檔放心下載廣義表((a),a)的表頭是(a)，表尾是(a)。三、判斷題（對(duì)的打“√”，錯(cuò)的打“×”。每小題1分，共10分;答案填在下表精品文檔放心下載內(nèi)）T1數(shù)據(jù)的邏輯結(jié)構(gòu)與數(shù)據(jù)元素本身的內(nèi)容和形式無(wú)關(guān)。精品文檔放心下載F2三個(gè)結(jié)點(diǎn)的二叉樹(shù)和三個(gè)結(jié)點(diǎn)的樹(shù)一樣，都具有三種不同的形態(tài)。精品文檔放心下載T3中序序列和后序序列相同的二叉樹(shù)為：空樹(shù)和缺右子樹(shù)的單支樹(shù)。精品文檔放心下載T4對(duì)于兩棵具有相同關(guān)鍵字集合而形狀不同的二叉排序樹(shù)，中序遍歷后得謝謝閱讀到的關(guān)鍵字排列順序相同。F5序列{30，40，50，15，25，35，38，10}是堆。感謝閱讀F6對(duì)于無(wú)向圖的生成樹(shù)，從同一頂點(diǎn)出發(fā)所得的生成樹(shù)相同。精品文檔放心下載T7若設(shè)哈希表長(zhǎng)m=14，哈希函數(shù)H(key)=key%11，表中已有4個(gè)結(jié)點(diǎn)。精品文檔放心下載addr(15)=4addr(38)=5addr(61)=6addr(84)=7其余地址為空，如用二次探測(cè)再謝謝閱讀散列處理沖突，關(guān)鍵字為49的結(jié)點(diǎn)的地址是9。T8一個(gè)深度為k的，具有最少結(jié)點(diǎn)數(shù)的完全二叉樹(shù)按層次，(同層次從左向右)用自然數(shù)依此對(duì)結(jié)點(diǎn)編號(hào)則，則編號(hào)最小的葉子的序號(hào)是2k-2+1；編號(hào)是i的結(jié)點(diǎn)所在的層次號(hào)是「logi|+1。（「logi|表示向上取整」（根所在的層次謝謝閱讀2 2號(hào)規(guī)定為1層）。F9在一棵7階B樹(shù)中，一個(gè)結(jié)點(diǎn)中最多有6棵子樹(shù)，最少有3棵子樹(shù)。精品文檔放心下載T10算法可以沒(méi)有輸入，但是必須有輸出。-`四、畫出樹(shù)的孩子兄弟表示法示意的樹(shù)或森林。（4分）謝謝閱讀∧B C ∧∧ D E ∧F∧∧ G ∧∧ H ∧I ∧五、要求題（本大題共2小題，共12分）設(shè)關(guān)鍵字的輸入序列為{4，5，7，2，1，3，6}1．（8分）從空樹(shù)開(kāi)始構(gòu)造平衡二叉樹(shù)，畫出每加入一個(gè)新結(jié)點(diǎn)時(shí)二叉樹(shù)的感謝閱讀形態(tài)，若發(fā)生不平衡，指明需做的平衡旋轉(zhuǎn)類型及平衡旋轉(zhuǎn)的結(jié)果。精品文檔放心下載2．（4分）上面的數(shù)據(jù)作為待排序的數(shù)據(jù)，寫出用快速排序進(jìn)行一趟劃分后感謝閱讀的數(shù)據(jù)序列-`六、按要求做題（本大題共2小題，共12分）1畫出無(wú)向圖G的鄰接表存儲(chǔ)結(jié)構(gòu)，根據(jù)鄰接表存儲(chǔ)結(jié)構(gòu)寫出深度優(yōu)先和廣精品文檔放心下載度優(yōu)先遍歷序列。（7分）V1V2 V3V4 V5 V6 V7V8用prim算法求下圖的最小生成樹(shù)，寫出最小生成樹(shù)的生成過(guò)程。（5分）感謝閱讀V160V3V1V3V1V3505245506542V4V7V2V4V7V2V4V7V250304070V6V6V5V5V5V6-`七、算法分析設(shè)計(jì)題（本大題共5小題，共30分）精品文檔放心下載1．寫出程序段的功能,并給出一個(gè)測(cè)試用例（一個(gè)輸入數(shù)據(jù)和一個(gè)輸出結(jié)果）(5分)。感謝閱讀voidconversion(){Stacks;intn;SElemTypee;initstack(s);printf("Pleaseinputnumber:");感謝閱讀scanf(“%d”,&n);while(n){push(s,n%8);n=n/8;}while(!stackempty(s))-`{pop(s,e);printf(“%d”,e);}}.將十進(jìn)制轉(zhuǎn)化成八進(jìn)制數(shù)（5分）測(cè)試用例：輸入10輸出122.下面是一個(gè)使用棧stack實(shí)現(xiàn)對(duì)二叉樹(shù)進(jìn)行非遞歸先根遍歷的函數(shù),請(qǐng)?jiān)跇?biāo)號(hào)處填寫合適的語(yǔ)句。(每空1分，共5分)程序:精品文檔放心下載Voidpreorder(bitree*T){bitree*stack[m];inttop;if(T!=NULL){top=1;stack[top]=(1);while( (2) ){p=stack[top];top--;printf(“%d”,p->data);if(p->rchild!=NULL){(3) ; stack[top]=p->rchild;}精品文檔放心下載if( (4)){ top++; (5);}}}}⑴⑷

⑵⑸

⑶（1）T-`top>0top++p->lchild!=NULLstack[top]=p->lchild3.請(qǐng)?jiān)跇?biāo)號(hào)處填寫合適的語(yǔ)句。完成下列程序。(每空1分，共5分)感謝閱讀int Binary_Search(S_TBL tbl，KEY kx)謝謝閱讀{/*在表tbl中查找關(guān)鍵碼為kx的數(shù)據(jù)元素，若找到返回該元素在表中的位置，否則，返回0*/感謝閱讀int mid，flag=0；low=1；high=length；while( ⑴ &!flag){/*非空，進(jìn)行比較測(cè)試*/mid= ⑵ ；if(kx<tbl.elem[mid].key) ⑶ ；謝謝閱讀elseif(kx>tbl.elem[mid].key) ⑷ ；謝謝閱讀else {flag= ⑸ ；break；}}return flag;}⑴ ⑵ ⑶⑷ ⑸（1）low<=high(low+high)/2high=mid-1low=mid+114.下面是一個(gè)采用直接選擇排序方法進(jìn)行升序排序的函數(shù)，請(qǐng)?jiān)跇?biāo)號(hào)處填寫合適感謝閱讀-`的語(yǔ)句。(每空1分，共5分)程序：Voidseletesort(intA[n],intn)謝謝閱讀{inti,j,t,minval,minidx;for(i=1;i<=n-1;i++){minval=A[i+1];(1)for(j=i+2;j<=n;j++)if( (2) ){ (3) ; minidx=j;}精品文檔放心下載if( (4) ) {t=A[i+1];(5)A[minidx]=t;}}}⑴ ⑵ ⑶⑷ ⑸（1）minidx=i+1minval>A[j]minval=A[j]i!=jA[i+1]=A[minidx]5試寫出求有向無(wú)環(huán)圖的關(guān)鍵路徑算法的設(shè)計(jì)思路（10分）感謝閱讀輸入頂點(diǎn)和弧信息，建立其鄰接表-`計(jì)算每個(gè)頂點(diǎn)的入度對(duì)其進(jìn)行拓?fù)渑判蚺判蜻^(guò)程中求頂點(diǎn)的Ve[i]將得到的拓?fù)湫蛄羞M(jìn)棧按逆拓?fù)湫蛄星箜旤c(diǎn)的Vl[i]計(jì)算每條弧的e[i]和l[i],找出e[i]=l[i]的關(guān)鍵活動(dòng)精品文檔放心下載數(shù)據(jù)結(jié)構(gòu)試卷A答案選擇題（本大題共20小題，每題1分，共20分；答案填在下表內(nèi)）感謝閱讀12345678910CB:C:D:B:D:B:C:A:C11121314151617181920:CA:B:D:B:A:C:ACD二、填空題（本大題共5小題，每空1分，共12分；答案填在下表內(nèi)）謝謝閱讀1有窮性確定性可行性2可讀性健壯性效率n(n-1)'student'5隊(duì)列先進(jìn)先出6(a)(a)三、判斷題（對(duì)的打“√”，錯(cuò)的打“×”。每小題1分，共10分）精品文檔放心下載1）true; 2）flase; 3）true; 4）true; 5）flase;感謝閱讀6）flase; 7）true; 8）true; 9）flase; 10）true精品文檔放心下載四、畫出樹(shù)的孩子兄弟表示法示意的樹(shù)或森林。（4分）謝謝閱讀AB CD E F G-`其他形式的樹(shù)形結(jié)構(gòu)酌情給分。五、要求題（本大題共2小題，共12分）1.4554 77552 74 71 4241 52 52 61 3 71 443 42 62 51 3 5 71 3 76-`2.一趟劃分后的數(shù)據(jù)序列3124756六、按要求做題（12分）1DFS遍歷序列v1v2v4v8v5v3v6v7(或12485367)感謝閱讀BFS遍歷序列v1v2v3v4v5 v6v7v8(或12345 678)謝謝閱讀鄰接點(diǎn)的順序可以不同，可以有不同的深度優(yōu)先和廣度優(yōu)先遍歷序列。（5分，謝謝閱讀如有錯(cuò)誤酌情扣分。）2V1V350V1V350V1V350V2V4V7V2V4V7V250V4V740504040V630V5V5V6V5V6V1V3V1V3V2V4V7V2V4V7V5V5V6-`七、算法設(shè)計(jì)題（30分）1.將十進(jìn)制轉(zhuǎn)化成八進(jìn)制數(shù)（5分）測(cè)試用例：輸入10輸出122（5分，每空1分）（1）Ttop>0top++p->lchild!=NULLstack[top]=p->lchild（5分，每空1分）（1）low<=high(low+high)/2high=mid-1low=mid+11（5分，每空1分）（1）minidx=i+1(2)minval>A[j](3)minval=A[j](4)i!=j(5)A[i+1]=A[minidx]5（10分，不同答案，酌情得分）輸入頂點(diǎn)和弧信息，建立其鄰接表計(jì)算每個(gè)頂點(diǎn)的入度對(duì)其進(jìn)行拓?fù)渑判蚺判蜻^(guò)程中求頂點(diǎn)的Ve[i]將得到的拓?fù)湫蛄羞M(jìn)棧-`按逆拓?fù)湫蛄星箜旤c(diǎn)的Vl[i]計(jì)算每條弧的e[i]和l[i],找出e[i]=l[i]的關(guān)鍵活動(dòng)謝謝閱讀第2學(xué)期數(shù)據(jù)結(jié)構(gòu)試卷A一、選擇題（本大題共15小題，每題2分，共30分；答案填在下表內(nèi)）精品文檔放心下載1.從一個(gè)長(zhǎng)度為100的順序表中刪除第30個(gè)元素時(shí)需向前移動(dòng) A 個(gè)元素謝謝閱讀A、70 B、71 C、69 D、302.在一個(gè)具有N個(gè)單元的順序表中,假定以地址低端(即下標(biāo)為1的單元)作為底,精品文檔放心下載以top作為頂指針,則當(dāng)做進(jìn)棧處理時(shí)top變化為_(kāi)_D____。精品文檔放心下載A、top不變 B、top=0 C、top=top-1 D、top=top+1謝謝閱讀3.從一個(gè)具有n個(gè)結(jié)點(diǎn)的單鏈表中查找其值等于x結(jié)點(diǎn)時(shí),在查找成功情況下,則平均比較___D_個(gè)結(jié)點(diǎn)。感謝閱讀A、n B、n/2 C、(n-1)/2 D、(n+1)/2精品文檔放心下載4.在一個(gè)單鏈表中,若要?jiǎng)h除p指針?biāo)附Y(jié)點(diǎn)的后繼結(jié)點(diǎn),則執(zhí)行B謝謝閱讀A、p->next;p->next=p->next->next;精品文檔放心下載B、p->next=p->next->next;感謝閱讀C、p=p->next;5.在一個(gè)鏈隊(duì)列中,假定front和rear分別為隊(duì)首和隊(duì)后指針,則進(jìn)行插入S結(jié)感謝閱讀點(diǎn)的操作時(shí)應(yīng)執(zhí)行__C_。A、front->next=s；front=s；B、s->next=rear;rear=s；C、rear->next=s;rear=s；D、s->next=front;front=s；6.在一棵度為3的樹(shù)中度為3的結(jié)點(diǎn)數(shù)為3個(gè),度為2的結(jié)點(diǎn)數(shù)為1個(gè),度為1感謝閱讀的結(jié)點(diǎn)數(shù)為1個(gè),那么度為0的結(jié)點(diǎn)數(shù)為_(kāi)C___個(gè)謝謝閱讀A、6 B、7 C、8 D、97.假定一棵二叉樹(shù)的結(jié)點(diǎn)數(shù)為33個(gè),則它的最小高度為_(kāi)_,最大高度為_(kāi)_C_謝謝閱讀A、4,33 B、5,33 C、6,33 D、6,32謝謝閱讀-`在一棵完全二叉樹(shù)中,若編號(hào)為i的結(jié)點(diǎn)有右孩子,則該結(jié)點(diǎn)的右孩子編號(hào)為_(kāi)_B_。精品文檔放心下載A、2iB、2i+1C、2i-1D、i/2謝謝閱讀9.在一個(gè)有向圖中,所有頂點(diǎn)的入度之和等于所有弧數(shù)和_A__倍。謝謝閱讀A、1B、2C、3D、410.對(duì)于一個(gè)具有N個(gè)頂點(diǎn)的圖,若用鄰接矩陣表示,則該矩陣的大小為_(kāi)D__。謝謝閱讀A、 N B、(N-1)2 C、(N+1)2 D、 N2精品文檔放心下載11.已知一個(gè)圖如圖所示，在該圖的最小生成樹(shù)中各邊上數(shù)值之和為_(kāi)B___。精品文檔放心下載A、21 B、26 C、28 D、3312.已知一個(gè)圖如圖所示，由該圖行到的一種拓樸序列為 A謝謝閱讀A、v1v4v6v2v5v3B、v1v2v3v4v5v6C、v1v4v2v3v6v5D、v1v2v4v6v3v5-`13.二維數(shù)組M的元素是4個(gè)字符（每個(gè)字符占一個(gè)存儲(chǔ)單元）組成的串，行下謝謝閱讀i的范圍從0到4，列下標(biāo)j的范圍從0到5，M按行存儲(chǔ)時(shí)元素M[2][4]的起始地址與M按列存儲(chǔ)時(shí)元素D的起始地址相同。精品文檔放心下載A、m[2][4]B、M[4][2]C、M[3][1]D、M[3][1]謝謝閱讀14.具有6個(gè)結(jié)點(diǎn)的無(wú)向圖至少應(yīng)有 A 條邊才能保證是連通圖。謝謝閱讀A、5 B、6 C、 7 D、 815.采用鄰接表存儲(chǔ)的圖的深度優(yōu)先遍歷類似于二叉樹(shù)的 A 。精品文檔放心下載先序遍歷B中序遍歷C.后序遍歷D.按層遍歷精品文檔放心下載二、填空題（本大題共5小題，每空1分，共8分；答案填在下表內(nèi)）感謝閱讀1 2 3 4 5 6 7 81.數(shù)據(jù)結(jié)構(gòu)是研究數(shù)據(jù)元素之間抽象化的相互關(guān)系和這種關(guān)系在計(jì)算機(jī)中的存儲(chǔ)結(jié)構(gòu)表示，根據(jù)數(shù)據(jù)元素之間關(guān)系的不同特性，通常有下列四類基本結(jié)構(gòu)：集合、線性結(jié)構(gòu)、（1）和（2）。精品文檔放心下載2.評(píng)價(jià)算法的標(biāo)準(zhǔn)很多，通常是以執(zhí)行算法所需要的 （3）和所占用的（4）來(lái)精品文檔放心下載判別一個(gè)算法的優(yōu)劣。3.線性表的順序存儲(chǔ)結(jié)構(gòu)特點(diǎn)是表中邏輯關(guān)系相鄰的元素在機(jī)器內(nèi)的位置也感謝閱讀是相鄰的。4.空格串的長(zhǎng)度為串中所包含 空格字符的個(gè)數(shù)，空串的長(zhǎng)度為零感謝閱讀5.加上表示指向前驅(qū)和后繼 的線索的二叉數(shù)稱為線索二叉樹(shù)。謝謝閱讀三、判斷題（對(duì)的打“√”，錯(cuò)的打“×”。每小題1分，共10分）精品文檔放心下載（X）1.線性表的唯一存儲(chǔ)形式是鏈表。（）2.已知指針P指向鍵表L中的某結(jié)點(diǎn)，執(zhí)行語(yǔ)句P=P-〉next不會(huì)刪除該謝謝閱讀鏈表中的結(jié)點(diǎn)。（）3.在鏈隊(duì)列中，即使不設(shè)置尾指針也能進(jìn)行入隊(duì)操作。精品文檔放心下載（X）4.如果一個(gè)串中的所有字符均在另一串中出現(xiàn)，則說(shuō)前者是后者的子串。謝謝閱讀-`（X）5.設(shè)與一棵樹(shù)T所對(duì)應(yīng)的二叉樹(shù)為BT，則與T中的葉子結(jié)點(diǎn)所對(duì)應(yīng)的感謝閱讀BT中的結(jié)點(diǎn)也一定是葉子結(jié)點(diǎn)。（）6.快速排序是不穩(wěn)定排序。（X）7.任一AOE網(wǎng)中至少有一條關(guān)鍵路徑，且是從源點(diǎn)到匯點(diǎn)的路徑中最短精品文檔放心下載的一條。（X）8.若圖G的最小生成樹(shù)不唯一，則G的邊數(shù)一定多于n-1，并且權(quán)值最感謝閱讀小的邊有多條（其中n為G的頂點(diǎn)數(shù)）。（X）9.給出不同的輸入序列建造二叉排序樹(shù)，一定得到不同的二叉排序樹(shù)。感謝閱讀（X）10.基數(shù)排序是多關(guān)鍵字排序。從最低位關(guān)鍵字起進(jìn)行排序。謝謝閱讀四、應(yīng)用題。（共44分）1.畫出該圖的鄰接矩陣和鄰接表。根據(jù)鄰接表從A開(kāi)始求DFS和BFS序列。（12分）精品文檔放心下載2.假設(shè)用于通信的電子由字符集{a,b,c,d,e,f,g,h}中的字母構(gòu)成，這8個(gè)字母在電文中出現(xiàn)的概率分別為{0.07，0.19，0.02，0.06，0.32，0.03，0.21，0.10}畫出哈夫曼樹(shù)，并為這8個(gè)字母設(shè)計(jì)哈夫曼編碼。（8分）謝謝閱讀已知序列{70，73，69，23，93，18,11，68}請(qǐng)給出直接插入排序作升序排序每一趟的結(jié)果和快速排序作升序排序時(shí)一趟的結(jié)果。（10分）感謝閱讀4.設(shè)有一組關(guān)鍵字關(guān)鍵碼集為{47，7，29，11，16，92，22，8，3}，哈希表表謝謝閱讀-`長(zhǎng)為11，Hash(key)=keymod11，用線性探測(cè)法處理沖突，構(gòu)造哈希表，并求它成功查找的ASL。（8分）精品文檔放心下載二叉樹(shù)的先序遍歷序列為ABCDEFGH，I中序遍歷序列為BCAEDGHFI，畫出這棵二叉樹(shù)。(6分)感謝閱讀五、算法設(shè)計(jì)題（8分）定義有序表抽象數(shù)據(jù)類型，并據(jù)此類型設(shè)計(jì)折半查找算法。謝謝閱讀typedefstruct{ intkey;floatinfo;}JD;intbinsrch(JDr[],intn,intk)精品文檔放心下載{intlow,high,mid,found;low=1;high=n;found=0;while((low<=high)&&(found==0)){mid=(low+high)/2;感謝閱讀if(k>r[mid].key)low=mid+1;謝謝閱讀elseif(k==r[mid].key) found=1;謝謝閱讀else high=mid-1;}if(found==1)return(mid);elsereturn(0);}