河北大學課程考核試卷
（ 2005 —2006 學年第 1 學期）
考核科目資料結構課程類別選修考核方式閉卷卷別_b_
一、選擇題（每題2分，共20分）
（ ）1、向乙個棧頂指標為top的鏈棧中插入乙個s所指結點時，其操作步驟為
a） top->next=sb） s->next=top->next;top->next=s;
c） s->next=top;top=sd） s->next=top;top=top->next;
（ ）2、下列說法正確的是
a）二叉樹中任乙個結點的度為2 b）二叉樹的度為2
c）一棵二叉樹的度可小於2 d）二叉樹中至少有乙個結點度為2
（ ）3、在乙個單鏈表中，若p結點不是最後結點，在p之後插入s結點，則執行
a） snext=p；pnext=s； b） snext=pnext；pnext=s；
c） snext=pnext；p=s； d） pnext=s；snext=p；
（ ）4、具有n個葉子結點的哈夫曼樹的分支結點有個。
a）n b）n＋1 c）2n－1 d）n－1
（ ）5、二叉排序樹中，鍵值最小的結點一定
a）左指標為空b）右指標為空
c）左右指標均為空d）左右指標均非空
（ ）6、將遞迴演算法轉換成對應的非遞迴演算法時，通常需要使用
a）棧b）佇列 c）鍊錶 d）樹
b—1（ ）7、可以進行拓撲排序的圖一定是
a）有環圖b）無向圖 c）強連通圖 d）有向無環圖
（ ）8、乙個棧的入棧序列是a,b,c,d,e，則棧的不可能的輸出序列是
a） edcba b） decba c） dceab d） abcde
（ ）9、設高度為h的二叉樹上只有度為0和2的結點，則此二叉樹中所包含的結點數至少為
a）2*hb）2*h1c）2*h+1 d）h+1
（ ）10、下列排序演算法中， 演算法可能會出現情況：在最後一趟開始之前，所有元素都不在其最終位置上。
a） 堆排序 b） 氣泡排序 c） 快速排序 d） 插入排序
二、判斷題（每題1分，共10分）
（ ）1、前序遍歷二叉樹序列中，任結點的子樹中的所有結點不一定在該結點之後。
（ ）2、圖的最小生成樹的形狀可能不唯一。
（ ）3、在n個結點的無向圖中，若邊數大於n－1，則該圖必是連通圖。
（ ）4、對於給定的關鍵字集合，以不同的次序插入到初始為空的二叉排序樹中，得到的二叉排序樹是相同的。
（ ）5、對有n個記錄的集合進行氣泡排序，所需時間決定於初始記錄的排列情況；在初始記錄無序的情況下最好。
（ ）6、將樹轉換成二叉樹，其根結點的右子樹必是空的。
（ ）7、**性表的鏈式儲存結構中，邏輯上相鄰的元素物理位置上一定相鄰。
（ ）8、任何一棵二叉樹的葉結點在先序、中序和後序遍歷序列中的相對次序不發生改變。
（ ）9、在哈夫曼編碼中，出現頻率相同的字元編碼長度也一定相同。
（ ）10、採用線性探測法處理衝突時，當從雜湊表中刪除乙個記錄時，不應將這個記錄的所在位置置為空，因為這將會影響以後的查詢。
b—2三、簡答題（每題6分，共36分）
1、迴圈佇列的優點是什麼？如何判別它的空和滿？
2、畫出和下列已知序列對應的樹t；並將其轉換為相應的二叉樹。
樹的先根次序訪問序列為：gfkdaiebchj；
樹的後根訪問次序為：diaekfcjhbg。
3、已知查詢表為。
設定雜湊函式為：h(key)=key % 13 ，採用開放位址法的二次探查法解決衝突，試在0～18的雜湊位址空間中對該關鍵字構造雜湊表，並求出查詢成功時的平均查詢長度。
4、輸入乙個正整數序列，建立一棵二叉排序樹，然後刪除結點16。分別畫出該二叉樹及刪除結點16後的二叉樹（要求刪除後樹的深度不能增加）。
5、設aoe網如下圖所示，求：
① 列出各個事件的最早、最遲發生時間；
② 找出該aoe網中的關鍵路徑，並回答完成該工程需要的最短時間。
6、應用直接選擇排序演算法，對關鍵值序列36，88，12，42，18，32，68，28，25從小到大排列。試寫出每趟排序的結果。
b—3四、演算法設計題（共34分）
【要求】①定義主要資料的儲存型別；②對演算法中的主要操作步驟加以注釋。
1、假設有兩個遞增有序的單鏈表a和b，編寫乙個演算法將它們合併成乙個鍊錶c而不改變其排序性。（11分）
2、以二叉鍊錶為儲存結構，寫出求二叉樹高度的演算法。（10分）
3、設順序表是按關鍵碼遞增有序的，將監測哨設在高下標端，編寫順序查詢演算法。並分別求出等概率情況下查詢成功和查詢失敗的平均查詢長度。（13分）b—4
資料結構03 04期末考試B答案
鏈結儲存表示的儲存空間一般在程式的執行過程中動態分配和釋放，且只要儲存器中還有空間，就不會產生儲存溢位的問題。同時在插入和刪除時不需要保持資料元素原來的物理順序，只需要保持原來的邏輯順序，因此不必移動資料，只需修改它們的鏈結指標，修改效率較高。但訪問表中的資料元素時，只能循鏈順序訪問，因此訪問效率不...
資料結構2019級期末考試 A
2010級夜大資料結構期末考試試題 a卷 姓名學號序號 成績 注意事項 本試卷滿分100分，考試時間120分鐘 一.單項選擇題，每題有乙個正確選擇。每題2分，共20分 1.下列資料結構中是線性結構。a二叉樹 b 樹 c佇列 d 圖 2.以下關於演算法的說法不正確的是 a 乙個演算法應包含有限個步驟 ...
西南大學資料結構期末考試試題答案
第2章自測卷答案 一 填空 1.嚴題集2.2 在順序表中插入或刪除乙個元素，需要平均移動表中一半元素，具體移動的元素個數與表長和該元素在表中的位置有關。2.線性表中結點的集合是有限的，結點間的關係是一對一的。3.向乙個長度為n的向量的第i個元素 1 i n 1 之前插入乙個元素時，需向後移動 n i...