試卷編號 數(shù)據(jù)結 課 課程類別 開卷(范圍題—二三題—二三四五六七八九十總題得

A4紙一張專業(yè)班級學學生簽考生注意事項：1、本試卷共頁，總 分鐘一、選擇題(每題2分，共30分假設某算法語句總的執(zhí)行次數(shù)為T(n)=5n5+n3+n2,那么該算法的時間復雜性量級為B 若長度為n的線性表采用順序結構，刪除它的第i數(shù)據(jù)元素，需要先 個數(shù)據(jù)元素。()n- n-在一個采用順序方式的線性表中，若表的第一個元素的地址10025個元素的地址是 B) C) D) B．順序結構、鏈式結構 C）表中元素需要占據(jù)一片連續(xù)的空間 結點的單鏈表為空的判斷條件 B)head- head- D)以下哪一個術語與數(shù)據(jù)的具體結構無關 D)雙向鏈棧的插入和刪除操作在（ ）進行 棧 棧 任意位 指定位某堆棧的輸入序列為a,b,c,d,下面的四個序列中 不可能是 一棵有16結點的完全二叉樹，對它按層編號根為1，則對編號為7的結點X，它的雙親結點及右孩子結點的編號分別為 C) 設有6個結點的無向圖，該圖至少應有 一棵滿二叉樹,同時又是一 二叉排序 C)非完全二叉 設一棵完全二叉樹有700個結點，則共 個葉子結點 B) 隊 D)在一個圖中，所有頂點的度數(shù)之和等于圖的邊數(shù) 倍 B) 二、填空題（每空1分,20分數(shù)據(jù)結構包括那面的內(nèi)容：邏輯結構 物理結構數(shù)據(jù)的運算隊列中允許進行刪除的一端 隊 數(shù)據(jù)元間有四類基本結構,它們是：①集合② ③樹形結構④圖形或網(wǎng)狀結構。線性表的單鏈表結構用C語言可定義為 struct 棧操作的原則 后進先 ；隊列的操作原則是先進先 voidpostorder {if }在n個頂點的無向完全圖中，邊的數(shù)目為_n(n-1)/2_ 遍歷;廣度優(yōu)先搜索遍歷類似于樹的層次遍歷。后綴算式79 +- /*的值為 _中綴算-2*Y/3對應的后綴算式為 n個頂點e條邊的圖，若采用鄰接矩陣1這棵樹的根結點是K1這棵樹的葉子結點是結點K3的度 這棵樹的度 這棵樹的深度 結點K3的 結點K3的父結點 三、判斷題：正確在（）內(nèi)打√，否則打×(1分，共10分1（×2（×3、線性表只能采用順序結構或者鏈式結構（ 4、在棧滿的情況下不能做進棧運算，否則產(chǎn)生“上溢 5、程序越短，程序運行的時間就越少 即可圖的每個頂點（× 7、一個有向圖的鄰接表和逆鄰接表中表結點的個數(shù)一定不相等 8、一個圖的鄰接矩陣表示法是不是唯一的，而鄰接表表示法是唯一的 9、數(shù)據(jù)的邏輯結構與數(shù)據(jù)元素本身的內(nèi)容和形式有關 （ 10、二叉樹是深度為2的有序樹 四、作圖題（按題目要求寫出結果（共25分和后序遍歷序列（9分）先序：ABCDFGHE中序 后序23所對應的鄰接表,A點開始廣度優(yōu)先遍歷該圖的結果（8文中出現(xiàn)的概率分別為{0.07,0.19,0.02,0.06,0.32,0.03,0.21,0.10}.ABCABCDEFGHBACDEF圖 圖五、寫算法（15分1、is，試寫出語句（a條語句）a

bc已知該雙向鏈表結構形式描述如下 bctypedefstructd{d structdnodedlinklist*head; /*在結點的雙鏈表中，將值為x的新結點插入*p之 dlinklist*s;p-}2、已知節(jié)點的動態(tài)單鏈表L中s結點是按整