西華大學(xué)數(shù)據(jù)結(jié)構(gòu)綜合期未試題

CD輯順序相同4、與鏈表相比，采用數(shù)組表示性線表的主要優(yōu)點(diǎn)是(A)。A機(jī)存取B.花費(fèi)的存儲(chǔ)空間比順序表少CD同5、下列關(guān)于棧說法正確的是(A)。8、下列關(guān)于串的說法正確的是(B)。A.串是由n個(gè)字符組成的有限序列(n>0)B.串有任意個(gè)必須連續(xù)的字符組成的子序列稱為原串的子串C操作通常稱為模式匹配D.串只能采用定長(zhǎng)存儲(chǔ)8、下列關(guān)于串的說法正確的是(D)。A.串一般記為s=’a1a2…an’(n>0)B.空串和空格串是同一個(gè)概念C.串的堆分配存儲(chǔ)表示中，存儲(chǔ)單元是在程序執(zhí)行之前分配好的D個(gè)連續(xù)字符序列相等才叫模式匹配成功ABCDAGFEB.CDBFGEACCDBAGFEDCDBGFEA9、若度為m的廣義哈夫曼樹中，總?cè)~子個(gè)數(shù)為n，其非葉子結(jié)點(diǎn)的個(gè)數(shù)有(A)個(gè)。A.(n-1)/(m-1)B.(n-1)/(m)線訂裝：號(hào)班學(xué)教：業(yè)專級(jí)年：名姓：號(hào)學(xué)西華大學(xué)課程考試(考試)試題卷(卷)1、數(shù)據(jù)的基本單位是(B)。A.數(shù)組元素B.數(shù)據(jù)元素1、性質(zhì)相同的數(shù)據(jù)元素的集合是(D)。A.數(shù)組元素B.數(shù)據(jù)元素2、下列選項(xiàng)中哪個(gè)不屬于算法重要特性？(D)A性和確定性B.可行性CD2、算法的效率一般是指(A)。常把這樣的數(shù)據(jù)元素又稱為(A)。A.記錄B.字段C.R={<ai,ai+1>|ai,an∈D,i=1,2…,n}D.R={<ai-1,ai>|ai,an∈D,i=2,3…,n-1}4、與數(shù)組相比，用鏈表表示線性表的主要優(yōu)點(diǎn)是(C)。A機(jī)存取B.花費(fèi)的存儲(chǔ)空間比順序表少A.棧是限定在表尾部進(jìn)行插入和刪除操作的線性表B.一般使用鏈作棧存儲(chǔ)結(jié)構(gòu)，不可使用數(shù)組C.棧是先進(jìn)先出的一種結(jié)構(gòu)D.棧有棧頂和棧底，可從棧頂或棧底開始取元素5、下列關(guān)于棧的說法正確的是(C)D16、如果入棧的序列為(A,B,C,D)，則不可能的出棧序列為()。7、下列哪種情況不使用隊(duì)列作存儲(chǔ)結(jié)構(gòu)(C)。A.操作系統(tǒng)中的作業(yè)管理B.打印時(shí)的多個(gè)任務(wù)輸出C.數(shù)制轉(zhuǎn)換D.模擬銀行業(yè)務(wù)窗口mD.無(wú)法確定A.廣義表表示法B.順序存儲(chǔ)表示法C.雙親表示法D.左子女右兄弟表示法10、向一個(gè)有51個(gè)元素的順序表中插入一個(gè)新元素并保持原來(lái)順序不變，平均要移動(dòng)()個(gè)元素。11、n個(gè)頂點(diǎn)的無(wú)向完全圖有()條邊。11、要連通n個(gè)頂點(diǎn)至少需要()條邊CnDn12、下列有關(guān)圖的概念中，不正確的是()。A、與圖的邊或孤相關(guān)的數(shù)字叫做權(quán)相同的路徑稱為回路B、任何圖中與某頂點(diǎn)相連的邊或孤叫出度D、連通分量是指無(wú)向圖中的極大連通子圖12、下列有關(guān)圖的概念中，不正確的是()。A、在圖中常用(w,v)表示一條邊B、一個(gè)連通圖的生成樹是一個(gè)極小連通子圖C、一區(qū)中的物理位置來(lái)表示元素之間的關(guān)系的D、在無(wú)向圖中，ivi的度。13、下列什么情況下適合采用順序查找法(C)。A、數(shù)據(jù)元素事前基本有序B、數(shù)據(jù)元素呈非遞減順序C、數(shù)據(jù)元素?zé)o序效率最高的排序方法是()A、插入排序B、選擇排序C、快速排序D、歸并排序復(fù)雜性為(C)。while(n>=(y+1)*(y+1)){y++;}性為()。for(j=1;j<=I;j++){m++;}A、二叉排序樹B、哈夫曼樹C、堆D、AVL樹的序列滿足的條件是(B)。A、ki<=k2i且ki<=k2i+1B、ki>=k2i且ki>=k2i+1CkikikikiDkiki且ki+1<=k2i+1m-1個(gè).序法的輔助存儲(chǔ)空間過多和多余的比較的不足m-1個(gè).A、簡(jiǎn)單排序B、快速排序C、堆排序D、歸并排序16、從任意節(jié)點(diǎn)開始不能訪問所有節(jié)點(diǎn)數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)是()A、單鏈表B、雙鏈表C、循環(huán)單鏈表D、循環(huán)雙鏈表17、在線索化二叉樹中，節(jié)點(diǎn)t沒有左子樹的充要條件是(B)A、t->lchild==NULLt沒有右子樹的充要條件是(B)A、t->rchild==NULLB、t->rtag==118、采用折半查找方法進(jìn)行查找，數(shù)據(jù)文件應(yīng)為()，且限于()。A順序存儲(chǔ)結(jié)構(gòu)B.有序表鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)CD儲(chǔ)結(jié)構(gòu)18、就平均查找速度而言，下列幾種查找速度從慢至快的關(guān)系是()。A折半哈希分塊B.順序分塊折半哈希CD順序哈希分塊折半19、將遞歸算法轉(zhuǎn)換為非遞歸算法時(shí)，一般要設(shè)置一個(gè)()輔助結(jié)構(gòu)。A、堆棧或隊(duì)列B、數(shù)組C、堆棧D、隊(duì)列19、在廣度優(yōu)先遍歷樹時(shí)，需要設(shè)置一個(gè)(C)輔助結(jié)構(gòu)。()A.[257934][681143]B.[25][79][34][68][1143]C.[2579][3468][1143]D.[95][72][38][46][1143]大值稱為：樹的度。 7、對(duì)二叉樹以某種次序遍歷使其變?yōu)榫€索二叉樹的過程叫線索化.L右子樹上所有結(jié)點(diǎn)值，則此二10、如果查找表內(nèi)的各子表的最大關(guān)鍵字呈有序狀態(tài)，則最適合的查找算法是分塊。10、能使用折半查找方法的線性表的前提條件是有序。1.每一種數(shù)據(jù)的邏輯結(jié)構(gòu)和物理結(jié)構(gòu)總是一致的.(N).消除遞歸不一定要使用棧.(Y)種存儲(chǔ)表示方法，即順序棧和鏈?zhǔn)綏?Y)4．二叉樹的左右子樹不能隨意顛倒(Y)5．在樹中，其雙親在同一層的結(jié)點(diǎn)相互稱為堂兄弟結(jié)點(diǎn)(Y)子結(jié)點(diǎn)只可能出現(xiàn)在層次最大的最后一層上。(N)27．二叉樹的線索化的目的是盡可能方便地直接訪問結(jié)點(diǎn)的前驅(qū)和后繼。(Y)7．任何一棵和樹對(duì)應(yīng)的二叉樹的右子樹不一定為空(N)9．赫夫曼樹又叫最優(yōu)二叉樹(Y)10．堆排序涉及到的兩個(gè)核心問題，一是如何把一無(wú)序序列建立一個(gè)堆，二是在輸出堆頂后再調(diào)整成一個(gè)新堆。(Y)(Y)。(2)合并過程中，不增加額外的存儲(chǔ)空間(提示：修改La和Lb中結(jié)點(diǎn)指針，使其最終成為一Lc值。(2，3共12分)Intdata;nodenext}Lnode,*LinkList;//3分(2)voidUniList(LinkList&La,LinkList&Lb,LinkList&Lc){//UniList結(jié)構(gòu)正確2分xtpb=Lb->next;While(pa&&pb{If(pa->data<pb->data){Pc->next=pa;pc=pa;pa=pa->next;}//2分else{Pc->next=pb;pc=pb;pb=pb->next;}//2分}pbfree(Lb)}(2)寫出計(jì)算單鏈表的長(zhǎng)度的遞歸算法(6分)(3)寫出計(jì)算單鏈表的長(zhǎng)度的非遞歸算法(6分)(1)TypedefstructLnode{datanodenext}Lnode,*LinkList;//3分(2)遞歸算法(//6分){if(p=NULL)len=0;//1分(3)非遞歸算法(//6分)ULLn}}{initqueue(q)//2分//2分}455