數(shù)據(jù)結(jié)構(gòu)模擬題答案

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