東南大學(xué)數(shù)據(jù)結(jié)構(gòu)試卷

1、東南大學(xué)考試卷（A 卷）課 程名稱數(shù)據(jù)結(jié)構(gòu)考試學(xué)期 08- 09- 3 得分適用專業(yè)吳健雄學(xué)院電類考試形式 半開卷 考試時間長度 120分鐘自 覺 遵 守 考 場 紀(jì) 律如 考 試 作 弊此 答 卷 無 效1 .2.3.4.5.1.2.3.4.5.、選擇題（每題 1分，共5 分）下面有關(guān)鏈棧的描述，對常規(guī)情況正確的是（A .在鏈頭插入，鏈尾刪除。B .在鏈尾插入，C.在鏈尾插入，鏈尾刪除。D .在鏈頭插入，對線性表進(jìn)行對半搜索時，要求線性表必須（ A .以數(shù)組方式存儲C.以鏈表方式存儲）鏈頭刪除。鏈頭刪除。）對包含n個元素的散列表進(jìn)行搜索，平均搜索長度為（A . O（log 2n）B . O（

2、n） C.不直接依賴于 n在同一個有向圖中，所有結(jié)點的入度和與出度和之比為（ A . 1B .以數(shù)組方式存儲并按關(guān)鍵碼排序D .以鏈表方式存儲并按關(guān)鍵碼排序）D .三者均不是）C. 1/2D.都不對在具有n個頂點的無向圖中，要連通全部頂點至少需要（ A . n一、判斷題（每題1分，共5分）條邊。B. n+1C. n-1D. n/2鏈?zhǔn)酱鎯Φ木€性表所有存儲單元的地址可連續(xù)可不連續(xù)。存儲有向圖的鄰接矩陣是對稱的，所以可以僅存矩陣上三角部分。在采用閉散列法解決沖突時，不要立刻做物理刪除，否則搜索時會出錯。二叉樹中序遍歷結(jié)果序列的最后一個結(jié)點必是前序遍歷的最后一個結(jié)點。堆排序的時間復(fù)雜度是O（n lo

3、g 2 n）,但需要額外存儲空間。、填空題（每空1分，第1空、第2空為2分，共11 分）1 .中綴表達(dá)式"（a+b）*d+e/（f+a*d）+c） ”所對應(yīng)的后綴表達(dá)式為()()()()()2 .后綴表達(dá)式ab&&ef>!|所對應(yīng)的中綴表達(dá)式為（2）3 高度為h的二叉樹最多可以有多少結(jié)點(4 若對一棵完全二叉樹從0開始編號，并按此編號把它順序存儲到一維數(shù)組a中，則ai元素的左孩子結(jié)點為(4)，右孩子結(jié)點為(5)，雙親結(jié)點為(6)。5 對用鄰接矩陣表示的圖進(jìn)行任何一種遍歷時，其時間復(fù)雜度為(7)。對用鄰接表表示的圖進(jìn)行任何一種遍歷時，其時間復(fù)雜度為(8)。6 折半

4、插入排序的時間復(fù)雜度為19)。四、簡答簡述題(每題 8分，共24分)1.設(shè)有一組關(guān)鍵碼輸入序列 55 , 31, 12, 37, 46, 73, 63, 02, 07，從空樹開始構(gòu)造 平衡二叉搜索樹，畫出每加入一個新結(jié)點時的二叉樹形態(tài)，需標(biāo)出平衡因子。包括發(fā) 生不平衡時，旋轉(zhuǎn)的各步的二叉樹形態(tài)，并標(biāo)注旋轉(zhuǎn)類型。2 .已知一棵二叉樹的前序遍歷的結(jié)果為ABECDFGHIJ，中序遍歷的結(jié)果是 EBCDAFHIGJ ,試畫出這棵二叉樹。請用圖表示逐步形成二叉樹的過程(也可以用文字)。3 請用Kruskal算法，逐步畫出下面有權(quán)無向圖的最小生成樹。必須每次添加一條邊。五、綜合算法題(每空2.5分，共55

5、分)1 完善改進(jìn)的歸并排序算法。*this是一個待排序的表，而表L2是一個輔助的工作表，幫助完成排序的中間步驟，最終完成*this的排序。所謂改進(jìn)指在把元素序列復(fù)制到輔助表中時，把第2個表的元素順序逆轉(zhuǎn)，這樣兩個待歸并的表從兩端開始處理，向中間歸并?？?以省去檢查子表是否結(jié)束的判斷。template <typename T>void Orderedlist<T>:MergeSort(int left, int right) Orderedlist<T> L2;improvedMergeSort(L2, left, right);對序列進(jìn)行歸并排序templa

6、te <type name T>void Orderedlist<T>:improvedMergeSort(Orderedlist<T> &L2, int left, int right) int mid = (left + right)/2;/從中間劃分為兩個子序列improvedMergeSort(L2, left, mid);/對左側(cè)子序列進(jìn)行歸并排序improvedMergeSort(L2, mid + 1, right);/對右側(cè)子序列進(jìn)行歸并排序(1);二路歸并 template <type name T>void Order

7、edlist<T>:improvedMerge(Orderedlist<T> &L2, int left, int mid, int right)int s1 = left, s2 = right, t = left, k ; for (k = left; k <= mid; k+)s1,s2是檢測指針，t是存放指針I(yè)I正向復(fù)制(2)II反向復(fù)制for (k = mid + 1; k <= right; k+)/歸并過程while (t <= right)if(L2.slists1 <= L2.slists2) (4);else (5);

8、2 完成二叉樹前序遍歷的非遞歸算法和層次序遍歷算法操作。/非遞歸前序遍歷。每訪問一個結(jié)點后，在向左子樹遍歷下去之前，利用棧記錄該結(jié)點的 右子女結(jié)點的地址，以便在左子樹退回時可以直接從棧頂取得右子樹的根結(jié)點，繼續(xù)右子 樹的前序遍歷。template <type name T>void Bin aryTree<T>:PreOrder1(void (*visit) (Bin TreeNode<T> *t) ) Li nkedStack<Bi nTreeNode<T>*> S;Bin TreeNode<T> *p = root;S

9、. Push (NULL);while (p != NULL) visit(p);訪問結(jié)點if (p->rightChild != NULL)(6) ; II預(yù)留右指針在棧中if (p->leftChild != NULL)(7) ;II進(jìn)左子樹else 18);II左子樹為空，由堆棧彈出II層次序遍歷。在訪問二叉樹某一層結(jié)點時，把下一層結(jié)點指針預(yù)先記憶在隊列中，利用 隊列安排逐層訪問的次序。因此每當(dāng)訪問一個結(jié)點時，將它的子女依次加到隊尾。然后訪 問已在隊頭的結(jié)點。template <type name T>void Bin aryTree<T>:level

10、Order (void (*visit) (Bin TreeNode<T> *t) if (root = NULL) retur n;Lin kedQueue<B in TreeNode<T> * > Q;Bin TreeNode<T> *p = root;visit (p);(9);while ( (10 ) Q.DeQueue (p);if (p->leftChild != NULL) visit (p->leftChild);(11;if (p->rightChild != NULL) visit (p->right

11、Child);(12)3 完成利用最大堆實現(xiàn)的優(yōu)先級隊列類定義。注意heapO不用，從heap1開始template<type name T>class MaxheapEleme nt<T>* heap;int n;int MaxSize;public:Maxheap(int sz=Defaultsize); /創(chuàng)建空堆，最多可以容納sz個元素void In sert(Eleme nt<T >& item);Eleme nt<T>* Delete(Eleme nt<T >& x);void show();templat

12、e<type name T>Maxheap<T>:Maxheap(i nt sz)MaxSize=sz;n=0;heap= new Element<T>MaxSize+1; / 注意 heap0不用，從 heap1開始template<type name T>void Maxheap<T>:I nsert(Eleme nt<T>& x)int i;if(n=MaxSize)cerr<<"heap is full.n"return;n+;for(i=n;i>1;)i=1表示已達(dá)到

13、根節(jié)點if( (13) ) break; /新元素不大于結(jié)點i的雙親，不處理(14) ;/此時heapi未占用，將雙親結(jié)點元素移入(15) ;i繼續(xù)向上heapi=x;/位置定了數(shù)值再放進(jìn)去template<type name T>Eleme nt<T>* Maxheap<T>:Delete(Eleme nt<T>& x)int i,j;if(!n)cerr<<"heap is empty.n"return NULL;x=heap1;Eleme nt<T> k=heap n;n-;for(i=1

14、,j=2;j<=n;)if(j<n) if( (16if(heapj<=k) break;/j是i的子女)j+; /j指向較大子女候補的結(jié)點大，不再移動(17(18/還需移動，將較大子女直接移入/移動(19)heapi=k;return &x;4 完成的深度優(yōu)先遍歷圖算法。/深度優(yōu)先遍歷圖，輸出所有的連通分量template<type name T, type name E> void Graph<T,E>:DFS()int i, n = NumberOfVertices(); bool *visited = new bool n;for (i

15、 = 0; i < n; i+) visitedi = false;for(i=0;i< n; i+)取圖中頂點個數(shù)創(chuàng)建輔助數(shù)組輔助數(shù)組visited初始化從每個頂點開始，各做一次遍歷。if( (20) )/借助輔助數(shù)組，上一趟遍歷已訪問過的各頂點不會作為新起點。所以輸出了所有連通分量，不會重復(fù)。DFS(i, visited);/從頂點0開始深度優(yōu)先搜索cout<<e ndl;delete visited;釋放 visited/從頂點位置v出發(fā)，以深度優(yōu)先的次序訪問所有可讀入的尚未訪問過的頂點。/算法中用到一個輔助數(shù)組 visited,對已訪問過的頂點作訪問標(biāo)記。template<type name T, type name E>void Graph<