上海市房地產管理進修學院
《資料結構導論》2023年春學期試卷（補考）
姓名班級學號： 得分
一、 單項選擇題(在每小題的四個備選答案中有乙個正確答案。請將其序號寫在題乾後的括號內。每小題l分，共14分)
1．資料的基本單位是 ( )
a．資料結構 b．資料元素 c．資料項 d．檔案
2．在乙個單鏈表中，若要刪除p指標所指向節點的後繼節點，則執行
3．下面關於線性表的敘述中，錯誤的是
a．線性表採用順序儲存，必須占用一片連續的儲存單元
b．線性表採用順序儲存，便於進行插入和刪除操作
c．線性表採用鏈結儲存，不必占用一片連續的儲存單元
d．線性表採用鏈結儲存，便於插入和刪除操作
4．向順序棧中壓入元素時，是
a．先移動棧頂指標，後存人元素 b．先存人元素，後移動棧頂指標
c．無所謂誰先誰後d．同時進行
5．在乙個順序儲存的迴圈佇列中，隊首指標指向隊首元素的
a．前乙個位置 b．後乙個位置
c．隊首元素位置 d．任意位置
6．在完全二叉樹中，若乙個結點是葉子結點，則它沒有
a．父結點b．兄弟結點
c．左子結點和右子結點 d．左子結點、右子結點和兄弟結點
8．由3個結點可以構造出多少種不同的二叉樹
a．2 b．3 c．4 d．5
9．下面關於圖的論述中正確的是
a．鄰接表法只能用於有向圖的儲存，而相鄰矩陣法對於有向圖和無向圖的儲存都適用
b．任何有向圖網路拓撲排序的結果是唯一的
c．有迴路的圖不能進行拓撲排序
d．無向連通網路的最小生成樹是唯一的
10．設圖g有n個頂點和e條邊，進行廣度優先搜尋的時間複雜度至多為
11．查詢表的邏輯結構是
a．線性結構 b．樹形結構c．圖狀結構 d．集合
12．如果要求乙個線性表既能較快地查詢，又能適應動態變化的要求，則可採用____查
找方法a．分塊b．順序c．二分 d．以上皆可
13．順序檔案修改操作困難，採用______的方法可降低所需代價
a．附加檔案b．按關鍵字值排序
c．按記錄輸入先後排序d．快速儲存
14．從未排序序列中挑選元素，並將其依次放入已排序序列初始時為空的一端，這種排序方
法為a．插入排序 b．歸併排序c．選擇排序 d．連續儲存
二、判斷題(每小題2分，共20分。正確的在括號內打「對」。錯誤的打「錯」。)
1．資料的邏輯結構是各資料元素之間的邏輯關係，是使用者按使用需要而建立的
2．線性表中的元素可以是各種各樣的，但同一線性表中的資料元素具有相同的特性，因此
是屬於同一資料物件
3．陣列是一組相繼的記憶體單元
4．棧和佇列都是順序儲存的線性結構
5．二叉樹是樹的特殊情形
6．用一維陣列儲存二叉樹時，總是以前序遍歷儲存結點
7．用鄰接矩陣法儲存乙個圖時，在不考慮壓縮儲存的情況下，所占用的儲存空間大小只與
圖中結點個數有關，而與圖的邊數無關
8．解決衝突的方法有「拉鍊法」和構造後繼雜湊位址序列
9．存放在磁帶、磁碟上的檔案，既可能是順序檔案也可以索引結構或其它結構型別的檔案。
( )
10．對於n個記錄的集合進行快速排序，所需要的附加空間數0(n
三、填空題(每小題2分。共30分)
1．乙個儲存結構主要包括和附加設施。
2．在乙個單鏈表中，在指標p所指向的結點之後插入指標s所指向的結點時，應執行「s一》next=______：」和 「p一》next的操作。
3．當線性表的元素總數基本穩定，且很少進行插入和刪除操作，但要求以最快的速度訪問
線性表中的元素時，應採用_________儲存結構。
4．_______可以作為實現遞迴函式呼叫的一種資料結構。
5．對帶頭結點的鏈佇列lq，判定佇列中只有乙個資料元素的條件是lq→______→
__==lq→_____。
7．樹與二叉樹之間最主要的差別是：二叉樹中各結點的子樹要區分為______和_____。
8．用於描述分類過程的二叉樹稱為______。
9．在具有n個頂點的圖的生成樹中，含有________條邊。
10．對n個頂點，e條邊的無向圖，其鄰接表表示中，需要_______ 個結點。
11．在雜湊儲存中，裝填因子a的值越大，訪問元素時發生衝突的可能性_____，a的值
越小，訪問元素時發生衝突的可能性就_____。
12．乙個索引順序表由兩部分組成：乙個______和乙個_____。
13．檔案的基本運算有兩類：_____和______。
14．對n個記錄的集合進行氣泡排序，其最壞情況下所需的時間複雜度是______。
15．按照排序過程涉及的儲存裝置的不同，排序可分為_____和______。
四、應用題(每小題6分，共24分)
1．已知一棵二叉樹的前根遍歷結果為abcdefghij，中根遍歷的結果為cbedahguf，試畫出該二叉樹。
2．無向圖g如圖所示
試給出 (1)該圖的鄰接矩陣
(2)從a出發的「深度優先」遍歷序列
3．如圖所示的二叉排序樹中
(1)刪除關鍵碼15；(2)插入關鍵碼20，分別畫出得到的=叉排序樹
4．設有乙個棧，元素進棧的次序為a，b，c，d，e，寫出下列出棧序列的操作序列。
(1)c，b，a，d，e
(2)a，c，b，e，d
其中1為進棧操作，0為出棧操作。
五、設計題(每小題6分，共12分)
1．乙個帶頭指標的單鏈表，寫出在其值為x的結點之後插入m個結點的演算法。
2．以二叉鍊錶為儲存結構，寫出求二叉樹中葉子數的演算法。
自考資料結構導論真題
課程 02142 一 單項選擇題 本大題共15小題，每小題2分，共30分 在每小題列出的四個備選項中只有乙個是符合題目要求的，請將其 填寫在題後的括號內。錯選 多選或未選均無分。1.下述檔案中適合於磁帶儲存的是 a.順序檔案 b.索引檔案 c.雜湊檔案 d.多關鍵字檔案 2.某二叉樹的後根遍歷序列為...
自學考試資料結構導論試題
全國2007年1月高等教育自學考試 資料結構導論試題 課程 02142 一 單項選擇題 本大題共15小題，每小題2分，共30分 在每小題列出的四個備選項中只有乙個是符合題目要求的，請將其 填寫在題後的括號內。錯選 多選或未選均無分。1 關於棧和佇列的說法中正確的是 a 棧和佇列都是線性結構 b.棧是...
資料結構導論自考試題
全國2008年10月高等教育自學考試 課程 02142 一 單項選擇題 本大題共15小題，每小題2分，共30分 在每小題列出的四個備選項中只有乙個是符合題目要求的，請將其 填寫在題後的括號內。錯選 多選或未選均無分。1.從邏輯上可以把資料結構分為 a.動態結構 靜態結構 b.順序結構 鏈式結構 c....