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

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

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)酱鎯?chǔ)時(shí)，結(jié)點(diǎn)的存儲(chǔ)地址（）A.必須是不連續(xù)的 B.連續(xù)與否均可必須是連續(xù)的 D.和頭結(jié)點(diǎn)的存儲(chǔ)地址相連續(xù)三、 判斷題1、 單鏈表從任何一個(gè)結(jié)點(diǎn)出發(fā)，都能訪問到所有結(jié)點(diǎn)。（）2、 將一棵樹轉(zhuǎn)換成二叉樹后，根結(jié)點(diǎn)沒有左子樹。（）3、 哈夫曼樹是帶權(quán)路徑長度最短的樹，路徑上權(quán)值較大的結(jié)點(diǎn)離根較近。（）4、 在樹結(jié)構(gòu)里，有且僅有一個(gè)結(jié)點(diǎn)沒有前驅(qū)；非根結(jié)點(diǎn)有且僅有一個(gè)雙親，且存在一條從根到該結(jié)點(diǎn)的路徑（）。5、 線性的數(shù)據(jù)結(jié)構(gòu)可以順序存儲(chǔ)，也可以鏈接存儲(chǔ)。非線性的數(shù)據(jù)結(jié)構(gòu)只能鏈接存儲(chǔ)。（）6、 線性表的順序存儲(chǔ)結(jié)構(gòu)的特點(diǎn)是邏輯關(guān)系上相鄰的兩個(gè)元素在物理位置上也相鄰。（）7、 向二叉排序樹插入一個(gè)新結(jié)點(diǎn)時(shí)，新結(jié)點(diǎn)一定成為二叉排序樹的一個(gè)葉子結(jié)點(diǎn)。（）四、 算法填空題：將折半查找的非遞歸算法中的空白處進(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分，共計(jì)40分））1.下圖為某無向圖的鄰接表，分別寫出從A出發(fā)深度優(yōu)先搜索和廣度優(yōu)先搜索的結(jié)果，并畫出該無向圖的邏輯結(jié)構(gòu)圖。123456789102.已知指針ha和hb分別指向兩個(gè)單鏈表的頭結(jié)點(diǎn).并且已知兩個(gè)鏈表的長度分別為m和n。試寫一算法將這兩個(gè)鏈表連接在一起（