學年二學期數據結構期末考試試卷(a卷)(編輯修改稿)

　

【文章內容簡介】 A、棧 B、 哈希表 C、線索樹 D、 雙向鏈表 34． 一個算法應該是 A、程序 B、問題求解步驟的描述 C、要滿足五個基本特性 D、 A 和 C 35． 線性表（ a1,a2,? ,an）以鏈接方式存儲時，訪問第 i 位置元素的時間復雜性為 A、 O（ i） B、 O（ 1） C、 O（ n） D、 O（ i1） 36． 線性表的表元存儲方式有 (（ 1） )和鏈接兩種。試指出下列各表中使用的是何種存儲方式：表 1 是 (（ 2） )存儲方式；表 2 是 (（ 3） )存儲方式；表 3 是 (（ 4） )存儲方式； 表 4 是 (（ 5） )存儲方式。表左的 s 指向起始表元。 表元編號 貨號 數量 表元間聯系 1 618 40 2 2 205 2 3 3 103 15 4 4 501 20 5 5 781 17 6 6 910 24 0 表元編號 貨號 數量 表元間聯系 1 618 40 5 2 205 2 1 3 103 15 4 4 501 20 2 5 781 17 6 6 910 24 3 石家莊學院 20222022 學年第 二 學期《 數據結構 》 期末考試 試卷 試卷 第 4 頁 （共 7 頁） 考核人數______ 考核班次_______________ 任課教員_________ 出題教員簽名________ 任課教研室主任簽名_______日期_______ 隊別__________ 教學班次___________ 學號___________ 姓名____________ ??????????密????????????封????????????線??????????????? 供選擇的答案： A、連續 B、單向鏈接 C、雙向鏈 接 D、不連接 E、循環鏈接 F、樹狀 G、網狀 H、隨機 I、順序 J、順序循環 37． 在雙向循環鏈表中，在 p 指針所指的結點后插入一個指針 q 所指向的新結點，其修改指針 的 操 作 是 _________ A 、。 。 。p ne x t q q pri or p p ne x t pri or q q ne x t q? ? ? ? ? ? ? ? ? B 、。 。 。 。p nex t q q nex t pr i or q q pr i or p q nex t p nex t? ? ? ? ? ? ? ? ? ? C 、。 。 。 。q ne x t p q ne x t p ne x t p ne x t pri or q p ne x t q? ? ? ? ? ? ? ? ? ? D 、。 。 。 。q ne x t p ne x t q pri or p p ne x t q p ne x t q? ? ? ? ? ? ? ? ? 38． 若某線性表最常用的操作是存取任一指定序號的元素和在最后進行插入和刪除運算，則利用（ ）存儲方式最節省時間。 A、順序表 B、雙鏈表 C、帶頭結點的雙循環鏈表 D、單循環鏈表 39． 在下列 3 種次序的線索二叉樹 中（ ）對查找指定結點在該次序下的后繼效果較差。 A、前序線索樹 B、中 序線索樹 C、 后序線索樹 40． 遍 歷 仍需要棧支持的 A、 前序線索樹 B、 中序線索樹 C、 后序線豢樹 41． 設 F 是森林， B 是由 F 變換得到的 二叉 樹。若 F 中有 N 個非終端結點，則 B 中 右指針域為空的 結點有 ____________個。 A、 N l B、 N C、 N+1 D、 N+2 42． 數 組 SZ[3…50 ， O… 10 ]含有元素數目為 A、 88 B、 99 C、 80 D、 90 43． 已知串 S=‘aaab’， 其 next 數組值為 A、 0123 B、 1123 C、 1231 D、 1211 44． 已知 Head(Tail([Head(S), Head(Tail(Tail(S)))]=[a],廣義表 S 滿足上式，則 S 為 _______.(其中，方括號表示廣義表，圓括號表示函數。如 [a,b])表示由 a,b 構成的廣義表，而 Head()表示取廣義表的頭部。 ) A、 [[a,b],b,a] B、 [[b,a],[a],[b]] C、 [[a],[a,b],[b]] D、 [b,[a],[a,b]] E、 [[a],[b],[b,a]] F 、 [[b],[b,a],[a]] 45． 設有一個 10 階的對稱矩陣 A，采用壓縮破除計方式，以行序為 主存儲， a1,1 為第一個元素，其存儲地址為 1，每個元素占 1 個地址空間，則 a8,5 的地址為。 A、 13 B、33 C、 18 D、 40 46． 串是一中特殊的線性表，其特殊性體現在。 A、 可以順序存儲 B、數據元素是一個字符 C、可以鏈接存儲 D、 數據元素可以是多個字符 47． 下列說法正確的是。 A、 線性表的邏輯順序與存儲順序總是一致的 B、 線性報第鏈式存儲結構中，內存中可用的 存儲單元可以使連續的，也可以不連續 C、 線性表弟順序存儲結構優于鏈式存儲結構 D、 每種數據結構都具有插入、刪除和查找三種基本運算 48． 在一個具有 n 個結點的有序單鏈表中插入一個新結點，并使插入結點后的單鏈表仍然有序，則該操作的時間復雜性量級為。 A、 .0 （ 1 ） B、 0 （ n ） C、 0 （ nlog2n ） D、 0 （ n2 ） 49． P 和 q 兩個指針分別指向雙向循環鏈表 L 兩個元素， p 所指元素是 q 所指元素的后繼的條件是。 A 、 p ==q B 、 Qnext==p C、 pnext==q D、 qnext==pnext 50． 深度為 h 的滿二叉樹的第 i 層有（ ）個結點。（ i≤ h） A、 2i1 B、 2i1 C、 2h1 D、 2h1 表元編號 貨號 數量 表元間聯