第 7 頁數據結構模擬試題答案一.選擇題（每題2分，共20分）（請將答案填寫到表格中）1數據結構主要研究數據的各種邏輯結構、存儲結構，以及對數據的（ ）。A. 關系描述 B. 結構實現 C. 各種操作 D. 各種定義2以下與數據的存儲結構無關的術語是_。A. 散列 B. 循環隊列 C. 三元組表 D. 數組3指出下列各表中使用的是何種存儲方式：表1是(（2）)存儲方式；表2是(（3）)存儲方式。A. 循環鏈接 B. 單向鏈接 C. 雙向鏈接 D. 順序存儲4有六個元素6，5，4，3，2，1 的順序進棧，（ ）是不合法的出棧序列。A. 5 4 3 6 1 2 B. 4 5 3 1 2 6 C. 3 4 6 5 2 1 D. 2 3 4 1 5 65已知廣義表A(a,b,c),(d,e,f)，從A中取出原子e的運算是_。 A. Head(Tail(Head(A)B. Head(Tail(Head(Tail(A) C. Head(Head(Tail(A)D. Head(Head(Tail(Tail(A)6表達式a*(b+c)-d的后綴表達式是( )。A. abcd*+- B. abc+*d- C. abc*+d- D. -+*abcd7判斷有向圖中是否有環的有效方法是_。A. 求最短路徑 B. 廣度優先搜索 C. 拓撲排序D. 關鍵路徑8從下圖中頂點v3出發，對圖進行廣度優先搜索后得到的序列是_；對圖進行深度優先搜索后得到的序列是_。 A. v3,v5,v2,v1,v4,v6B.v3,v6,v1,v4,v5,v2C. v3,v1,v4,v5,v2,v6D.v3,v4,v2,v5,v6,v19具有11個關鍵字的有序表，折半查找成功的平均查找長度（ ）。 A. 3.1 B. 2.5 C. 3 D. 5 10假設一個關鍵字的序列進行了如下的排序過程， 原序列：（12，5，9，32，14，47，98，10） 第一趟排序結果：（10，5，9，12，14，47，98，32） 第二趟排序結果：（9，5，10，12，14，47，98，32） 第三趟排序結果：（5，9，10，12，14，32，47，98） 則這個排序為_。 A. 希爾排序 B. 堆排序 C. 快速排序D.簡單選擇排序選擇題答案12345678910CDDACBBCBACC二. 判斷題：（每題1分，共10分）1算法可以用不同的語言描述，如果用C語言或C+語言等高級語言來描述，則算法實際上就是程序了（ ）2鏈表是一種隨機存取結構，因而便于對鏈表進行插入和刪除操作.（ ）3循環隊列的引入，目的是為了克服假溢出時數據大量的移動.（ ）4從邏輯結構看，n維數組的每個元素均屬于n個向量.（ ）5在圖采用鄰接表存儲時，求最小生成樹的Prim算法的時間復雜度為O(n+e).（ )6由4個結點可以構造出21中不同的二叉樹 （ )7在表示某工程的AOE網中，加速其關鍵路徑上的任意關鍵活動均可縮短整個工程的完成時間.（ )8二叉排序樹的查找效率與構造其樹形的初始序列相關. . ( )9非空的二叉樹一定滿足：某結點若有左孩子，則其中序前驅一定沒有右孩子. ( )10直接選擇排序是一種不穩定的排序方法.（ ）三讀程序：（每題5分，共10分）現有一個單向鏈表類，如下所示：#include templateclass LinkedList;templateclass ListNode T data;/ 結點數據域 ListNode *link;/ 結點指針域 friend class LinkedList; ListNode(ListNode *ptr=NULL)link=ptr; ListNode(const T& item, ListNode *ptr=NULL ):data(item),link(ptr) ; /鏈表結點數據類型templateclass LinkedList public:LinkedList()first = new ListNode;/ 初始化帶頭結點的單向鏈表 LinkedList()makeEmpty(); void makeEmpty(); int Length()const; ListNode* Search(const T &x)const; ListNode* getData(int i); void setData(int i, T x); int Insert(int i,T x); int Remove(int i,int k); int IsEmpty()constreturn first-link=NULL; void input(); void output(); bool A ( LinkedList &L) ;private: ListNode *first;/定義頭指針 bool A ( ListNode *ptr1, ListNode *ptr2);/鏈表模板類1其中，Search函數的功能是若鏈表中存在值為給定值x的結點，則返回該結點的地址；否則，返回NULL。在下面的Search函數實現代碼的空白處填上適當的C+語句，使之能實現指定的功能。templateListNode* LinkedList:Search(T &x)constListNode *p = _ ; while ( ) _ ;if (p) _ _;else_;：first-link：p & p-data != x：p = p-link：return p return NULL2仔細閱讀A函數的程序代碼，并回答程序段后面的問題。templatebool LinkedList:A ( LinkedList &L) return A(first-link, L.first-link); templatebool LinkedList:A (ListNode *pa,ListNode *pb) if (pa = NULL) return true;while (pb )if (pa-data = pb-data)pa = pa-link;pb = pb-link;return (A(pa,pb);elsepb = pb-link; return false;其中，假設成員函數A ( LinkedList &L)涉及的兩個鏈表中的值如下所示：（1）A ( LinkedList &L)函數實現的具體操作是：_判斷子集_。（2）假定鏈表類中定義的其他函數均已實現（鏈表中數據的輸入次序與上圖一致），編寫一個main函數，調用A函數，并寫出運行結果。int main()LinkedList L1,L2;L1.input();L2.input();if(L1.A(L2) coutYes;else coutNo;return 1;運行結果：Yes四. 簡答題：（每題5分，共35分）1畫出與下列已知序列對應的樹T，要求寫出求解過程：（5分）（1）樹的先根次序訪問序列為GFKDAIEBCHJ；（2）樹的后根次序訪問序列為DIAEKFCJHBG。 見P1912根據權值集W=7，19，2，6，32，3，21，10，完成：（5分）（1）創建一棵Huffman樹；（2）計算出該樹帶權路徑長度WPL；（3）在這棵二叉樹上加上中序線索。3用關鍵字序列（50，73，191，325，10，73，40，73）形成一棵二叉排序樹，并計算它在查找成功時和查找不成功時的平均查找長度。（5分）4選取散列函數H（k）= k mod 11，用線性探測法處理沖突。試在012的散列地址空間中，對鍵序列（33，19，53，45，30，13，2，67）構造散列表，并求等概率情況下查找成功與不成功的平均查找長度。（5分）5寫出用Floyd算法求解下圖中各頂點之間最短路徑的過程。（5分）略6在堆排序、快速排序和歸并排序中：（5分）(1) 若只從存儲空間考慮，則應首先選取哪種排序方法，其次選取哪種排序方法？堆排序、快速排序(2) 若只從排序結果的穩定性考慮，則應選取哪種排序方法？歸并排序(3) 若只從平均情況下排序最快考慮，則應選取哪種排序方法？快速排序(4) 若只從最壞情況下排序最快并且要節省內存考慮，則應選取哪種排序方法？堆排序7設有數據邏輯結構為：B = (K, R), K = k1, k2, , k9R=, , , , , , , , ，要求：（5分）（1）畫出這個邏輯結構的圖示。略（2）畫出該邏輯結構正向鄰接表。略（3）在（2）的基礎上，利用棧作為存放入度為0的頂點序號，寫出該圖示的拓撲排序序列。如果正向鄰接表中鄰接點序號從小到大排列，則拓撲排序序列：K2-K5-K4-K6-K1-K8-K3-K9-K7五.編程題：（25分，每題10