學年二學期數據結構期末考試試卷(a卷)-文庫吧在線文庫

　　

【正文】 存取任一指定序號的元素和在最后進行插入和刪除運算，則利用（ ）存儲方式最節省時間。p nex t q q nex t pr i or q q pr i or p q nex t p nex t? ? ? ? ? ? ? ? ? ? C 、。表左的 s 指向起始表元。 B、 9， 7， 8， 4，1， 7， 15， 20 C、 20， 15， 8， 9， 7， 1， 4， 7 D、 9， 4， 7， 8， 7， 1， 15， 20 21． 一組記錄的關鍵碼為（ 46， 79， 56， 38， 40， 84），則利用快速排序的方法，以第一個記錄為基準得到的一次劃分結果為。（ F ） 19． 哈希表的結點中只包含數據元素自身的信息，不包含任何指針。 （ T ） 11． 順序存儲方式的優點是存儲密度大，且插入、刪除運算效率高。 ( T ) 3． 一個圖的廣 度優先搜索樹是唯一的 。若下一趟首先對較短的子序列進行排序，試證明在此做法下，快速排序所需要的棧的深度為 O(log2n)。 ( F ) 6． 為提高在外排序過程中，對長度為 N 的初始序列進行“置換 — 選擇”排序時，可以得到的最大初始有序段的長度不超過 N/2。（ T ） 14． 對于有 N 個結點的二叉樹，其高度為 log2n。 A、 ni+1 B、 ni C、 i D、 i+1 10． 快速排序 （ ）在 情況下不利于發揮其長處。 A、 ?n/2? B、 ?n/2? 1 C、 1 D、 ?n/2? +2 24． 就平均性能而言 ，目前最好的內排序方法是 ( )排序法。 。 。若 F 中有 N 個非終端結點，則 B 中 右指針域為空的 結點有 ____________個。 A 、 p ==q B 、 Qnext==p C、 pnext==q D、 qnext==pnext 50． 深度為 h 的滿二叉樹的第 i 層有（ ）個結點。 D、 B 樹和 B+樹都能有效地支持隨機檢索。 60． ISAM 文件和 VASM 文件屬于 A、 索引非順序文件 B、 索引順序文件 C、 順序文件 D、 散列文件 評卷人 得分 四、算法設計題（ 2小題，共 4分） 1． 試設計一個算法 , 使得在 O(n)的時間內重排數組 , 將所有取負值的排序碼排在所有取正值(非負值 )的排 序碼之前。k,m:integer)。 IF x=r[j].key THEN finished:=(3)__ ELSE [r[i]:= (4)___。 8． 對于散列文件中的每個散列地址，其對應單鏈表中的第 一 個結點稱為 _______，其余結點稱為 __________。 r＾ .next:= (2)________ ] ELSE IF (3)___ THEN [r＾ .next:=head。 ] ] ENDP。 12． 帶頭結點的雙循環鏈表 L 中只有一個元素結點的條件是： ________ 13． 已知指針 p 指向單鏈表 L 中的某結點，則刪除其后繼結點的語句是： ________ 14． 對于雙向鏈表 ,在兩個結點之間插入一個新結點需修改的指針共 ______個，單鏈表為_______個。 23． 設有 一 個 10 階對稱矩陣 A 采用壓縮存儲方式 (以行為主序存儲： 11 1a? 1)．則 85a 的 地址為 ________。 28． 順序查找長度 n 的順序表，查找成功的平均查找長度為 _________。 35． 先根次序周游樹林正好等同于按 ______周游對應的二叉樹；后根次序周游樹林正好等同于 ______周游對應的二叉樹。 4． 索引順序存取方法（ ISAM）中，主文件已按關鍵字排序， 為何還需要主關鍵字索引？ 評卷人 得分 七、名詞解釋（ 5小題，共 20分） 1． 內部排序 2． 棧。 39． 由一棵二叉樹的前序序列和 可唯一確定這棵二叉樹。 石家莊學院 20222022 學年第 二 學期《 數據結構 》 期末考試 試卷 試卷 第 7 頁 （共 7 頁） 考核人數______ 考核班次_______________ 任課教員_________ 出題教員簽名________ 任課教研室主任簽名_______日期_______ 隊別__________ 教學班次___________ 學號___________ 姓名____________ ??????????密????????????封????????????線??????????????? 31． 如果結點 A 有 3 個兄弟 ，而且 B 是 A 的雙親，則 B 的度是 ______。sumn。因此，這種表便于 ______訪問，是一種 ______結構。 WHILE num0 DO [ insert(head,num)。 IF (6)___ THEN [ q＾ .next:=(7)___。 PROC insert( head, x)。 ENDP。 x:=r[k].key。 下一 個被插入的 關 鍵字 是 42，則其插人的位 置 是 ________。 slink=p C、 plink=slink。 A、 BDGCEFHA B、 GDBECFHA C、 BDGAECHF D、 GDBDHFCA 54． 某二叉樹中序序列為 A,B,C,D,E,F,G，后序序列為 B,D,C,A,F,G,E 則前序序列是： A、E,G,F,A,C,D,B B、 E,A,C,B,D,G,F C、 E,A,G,C,F,B,D D、上面的都不對 55． 下面的說法中正確的是 . （ 1）任何一棵二叉樹的葉子結點在三種遍歷中的相對次序不變； （ 2）按二叉樹定義，具有三個結點的二叉樹共有 6 種。 A、 13 B、33 C、 18 D、 40 46． 串是一中特殊的線性表，其特殊性體現在。 。 。試指出下列各表中使用的是何種存儲方式：表 1 是 (（ 2） )存儲方式；表 2 是 (（ 3） )存儲方式；表 3 是 (（ 4） )存儲方式； 表 4 是 (（ 5） )存儲方式。 A、下面的 B， C， D 都不對。（ T ） 18． 由一棵二叉樹的前序序列和后序序列可以唯一確定它。（ F ） 10． 有 n 個數順序 (依次 )進棧，出棧序列有 種，即：21 (2 )!1 ( !)n nC nn???。 ( F ) 2． 負載因子（裝填因子）是散列表的一個重要參數，它反映敞列表的裝滿程度。 3． 設有上三角矩陣 (aij)n*n，將其上三角中的元素按先行后列的順序存于數組 B（ 1:m）中，使得 B[k]= aij 且 k=f1(i)+f2