《數(shù)據(jù)結(jié)構(gòu)》模擬試卷八

試一、選擇題（每題分，共10分一個的輸入序列為12345則列序列不可能是棧的輸出序列的是。（）12345（54321（）23451（41235．一棵左子樹為空的二叉樹在序線索化后，其中的空鏈域的個為。（）（）（）（）確定．在用鄰接表表示圖的情況下拓撲排序算法的時間復雜度為。（）（n＋）（2）On）（）（n×）（4）On）．下列排序算法中，在每一趟能選出一個元素放到其最終位置，并且其時間性能受數(shù)據(jù)初始特影響的是。（）直接插入排序（2）快速排序（）直接選擇排序（4）堆排序．下列排序算法中，依次將待序序列中的元素和前面有序序列并為一個新的有序序列的排序法是。（）直接插入排序（2）冒泡排序（）快速排序（4）直接擇排序二、判斷題（每題分，共10分l）設指針P向單鏈表中一個點句序列U:=U^.next將刪除一個結(jié)點2）和隊列都是運算限的線性表。3）義表的長度是指義表中的原子個數(shù)。4）某二叉樹的葉子點數(shù)為1，則其先序列和后序序列一定相反。5.（）二叉樹在按任一種序線索化后，都可以很容易地求出相應次序下的前趨和后繼。6.（）在采用線性探測法理沖突的散列表中，所有同義詞在表中相鄰。7.（）對B樹中任一非葉結(jié)點中的某關(guān)鍵字K比小最大關(guān)鍵字和比K大的最小關(guān)鍵字定都在葉子結(jié)點中。8）若一個無向圖的以點為起點的深度遍歷序列唯，則可唯一確定該圖。9）對一有向無環(huán)圖行拓撲排序算法之后，入度數(shù)組中的所有元素的值為0。10.）數(shù)據(jù)表基本有序時，冒泡排序算的時間復雜度一定接近On1/3

三、填空題（每題分，共20分．在單鏈表中，在指針P所指點的后面插入一個結(jié)點到的語序列是。．已知一個棧的輸入序列為123...n，則其輸出序列第二個元素為的輸出序列的個數(shù)是。．取出廣義表A=((ax，，z）)中的原子c的合函數(shù)是。4．若以4，，，7，｝作為葉子結(jié)點的權(quán)值構(gòu)造哈夫曼樹，則其帶權(quán)路徑長是。5.在序存儲的二叉樹中，編為和j的個結(jié)點處在同一的條件是。．已知二叉樹有5O個子結(jié)點，則該二叉樹的總結(jié)點數(shù)至少是。7.在關(guān)鍵字遞增的數(shù)組A[1..20]中按二分查找方法進行查找時，找長度為5的元素個數(shù)是。8.知數(shù)組，0..9]中個元素4單元，在按行優(yōu)先方式將其存到起始地址為1000的續(xù)的存儲區(qū)域時A［，］的址是。．有n球隊參加的足球聯(lián)賽主客場制進行比賽，共需進行場賽。10.下列排序算中，占用輔助空間最多的是（排序，希爾排序，快速排序，歸并排序四、解答下列各20分）．一棵二叉樹的先序、中序和序序列如下，其中一部分本標出請構(gòu)造出該二叉樹。先序序列：CDEGHIK中序序列：CBFAJKIG后序序列：EFDBJIH．將下面數(shù)據(jù)表建成一個堆。（70，，20，311，544，66，，2O0，30，，15O，28．求出下圖中頂點1到其各點的最短路徑。4．已知下面二叉排序樹的各結(jié)點的值依次為1～，請標出各結(jié)點的值五、算法設計（分，每題分）2/3

．已知遞增有序的單鏈表AB分存儲了一個合。設計算法以求出兩個集合A，B的集AB即僅由在A出現(xiàn)而不在B中出的元素所構(gòu)成的集合以同樣的形式存儲同時返回該集合的元素個數(shù)。．設計算法以返回二叉樹的后序序列的第一個結(jié)點的指針。求采用非遞歸形式，且不用棧。．已知二叉樹T以二鏈表形作為其存儲結(jié)構(gòu)。設計算法按先序次序輸出各結(jié)點的值及相應的層數(shù)，并以二元組的形式給出。下面的二叉樹及對應的輸出如下頁圖所示。（，1，，，4，，，，，4）4．已知數(shù)組的素類型為integer。計算法將其調(diào)整