徐州工程學(xué)院數(shù)據(jù)結(jié)構(gòu)

一、填空題評價算法的五個標(biāo)準(zhǔn)是 、、、、和。鏈表最后一個結(jié)點的指針指向鏈表的頭節(jié)點，這樣的鏈表稱為鏈表；鏈表的每個結(jié)點都有兩個指針域，一個指針指向前一結(jié)點，另一個指針指向后一結(jié)點，這樣的鏈表稱為 鏈表。在稀疏矩陣所對應(yīng)的三元組線形表中，每個三元組元素為主序、為輔序的次序排列。對于一個具有n個頂點和e條邊的連通圖，其生成樹中的頂點數(shù)和邊數(shù)分別為 和。Hanoi塔、求一個數(shù)的階乘、二叉樹遍歷等類似問題的解決一般通過使用 來解決。。在進(jìn)行直接插入排序時，其數(shù)據(jù)比較次數(shù)與數(shù)據(jù)的初始排歹—關(guān)；而在進(jìn)行直接選擇排序時，其數(shù)據(jù)比較次數(shù)與數(shù)據(jù)的初始排列____關(guān)。設(shè)r指向單鏈表的最后一個結(jié)點，要在最后一個結(jié)點之后插入s所指的結(jié)點，需執(zhí)行的三條語句是 ；r=s;r->next=null;。棧中存取數(shù)據(jù)的原則，隊列中存取數(shù)據(jù)的原則。二、選擇題在數(shù)據(jù)結(jié)構(gòu)的討論中把數(shù)據(jù)結(jié)構(gòu)從邏輯上分為（）內(nèi)部結(jié)構(gòu)與外部結(jié)構(gòu)C內(nèi)部結(jié)構(gòu)與外部結(jié)構(gòu)C.線性結(jié)構(gòu)與非線性結(jié)構(gòu)算法分析的兩個主要方面是（A.空間復(fù)雜性和時間復(fù)雜性C.可讀性和文檔性一個非空廣義表的表頭（）靜態(tài)結(jié)構(gòu)與動態(tài)結(jié)構(gòu)D.緊湊結(jié)構(gòu)與非緊湊結(jié)構(gòu)）B.正確性和簡明性D.數(shù)據(jù)復(fù)雜性和程序復(fù)雜性A.不可能是子表B.只能是子表 C.只能是原子D.可以是子表或原子在一個單鏈表中，若p所指結(jié)點不是最后結(jié)點，在p之后插入s所指結(jié)點，則執(zhí)行（）A.s->next=p；p->next=sB.s->next=p->next；p->next=sA.s->next=p；p->next=s深度為5的二叉樹其結(jié)點數(shù)最多為（ ）A.16B.30C.31D.32設(shè)單循環(huán)鏈表中結(jié)點的結(jié)構(gòu)為（data,next）,且rear是指向非空的帶表頭結(jié)點的單循環(huán)鏈表的尾結(jié)點的指針。若想刪除鏈表第一個結(jié)點，則應(yīng)執(zhí)行下列哪一個操作（）

A.s=rearA.s=rear；rear=rear->next； deletes；B. rear=rear->next；deleterear；C.rear=rear->next->next；deleterear；D.s=rear->next->next；rear->next->next=s->next；deletes；線性表采用鏈?zhǔn)酱鎯r，結(jié)點的存儲地址（）A.必須是不連續(xù)的 B.連續(xù)與否均可必須是連續(xù)的 D.和頭結(jié)點的存儲地址相連續(xù)三、 判斷題1、 單鏈表從任何一個結(jié)點出發(fā)，都能訪問到所有結(jié)點。（）2、 將一棵樹轉(zhuǎn)換成二叉樹后，根結(jié)點沒有左子樹。（）3、 哈夫曼樹是帶權(quán)路徑長度最短的樹，路徑上權(quán)值較大的結(jié)點離根較近。（）4、 在樹結(jié)構(gòu)里，有且僅有一個結(jié)點沒有前驅(qū)；非根結(jié)點有且僅有一個雙親，且存在一條從根到該結(jié)點的路徑（）。5、 線性的數(shù)據(jù)結(jié)構(gòu)可以順序存儲，也可以鏈接存儲。非線性的數(shù)據(jù)結(jié)構(gòu)只能鏈接存儲。（）6、 線性表的順序存儲結(jié)構(gòu)的特點是邏輯關(guān)系上相鄰的兩個元素在物理位置上也相鄰。（）7、 向二叉排序樹插入一個新結(jié)點時，新結(jié)點一定成為二叉排序樹的一個葉子結(jié)點。（）四、 算法填空題：將折半查找的非遞歸算法中的空白處進(jìn)行正確填寫。intSearch_Bin（SSTableST,KeyTypekey）TOC\o"1-5"\h\z(intlow=； high=ST.length； (1)While(low<=high){ (2)mid=； (3)if(EQ(key,ST.elem[mid].key)return；elseif(LT(key,ST.elem[mid].key))； (4)else； (5)}return 0；}//Search_Bin

五、綜合應(yīng)用題 （（共4小題，每題10分，共計40分））1.下圖為某無向圖的鄰接表，分別寫出從A出發(fā)深度優(yōu)先搜索和廣度優(yōu)先搜索的結(jié)果，并畫出該無向圖的邏輯結(jié)構(gòu)圖。123456789102.已知指針ha和hb分別指向兩個單鏈表的頭結(jié)點.并且已知兩個鏈表的長度分別為m和n。試寫一算法將這兩個鏈表連接在一起（