2002級數(shù)據(jù)結(jié)構(gòu)期末試卷A

PAGEPAGE4n，n2C．n1，n2

n2D．n2

，n-1，n-12002級《數(shù)據(jù)結(jié)構(gòu)》期末試卷A一、二題答案寫在試卷對應(yīng)答題表中，三、四題答案寫在答題紙上一．判斷題（每小題1分，共10分）1方面。數(shù)組可以看作是二元組<下標(biāo)，值>的一個集合。帶表頭結(jié)點的雙向循環(huán)鏈表判空的條件是：first->rlink==first（first出棧序列為abcd，則入棧序列可能是bcda。5．0kk0n個，0度為k的結(jié)點有n個，則有n=n+1。k 0 k對二叉搜索樹進行前序遍歷，可以得到該二叉搜索樹所有結(jié)點構(gòu)成的有序序列。8．n個結(jié)點的無向圖最多有n*(n-1)條邊。9．一組關(guān)鍵碼已完全有序時，最快的排序方法是快速排序。10．一個索引項對應(yīng)數(shù)據(jù)表中一組數(shù)據(jù)對象的方式叫稀疏索引，稠密索引則是每個索引項對應(yīng)唯一的數(shù)據(jù)對象。112345678910二．單項選擇題（每小題2分，共30分）算法分析的兩個方面是 。A.空間復(fù)雜性和時間復(fù)雜性 B.正確性和簡明性C.可讀性和文檔性 D.數(shù)據(jù)復(fù)雜性和程序復(fù)雜性2．對長度為n的無序線性表進行順序查找，則查找成功、不成功時的均數(shù)據(jù)比較次數(shù)分別為 。

對于只在首、尾兩端進行插入操作的線性表，宜采用的存儲結(jié)構(gòu)為 。順序表B．C．單鏈表D．p。A．q->link=p;p->link=q;B．p->link=q;q->link=p->link;C．q->link=p->link;p->link=q;D．p->link=q->link;q->link=p;分別用frontrear空的條件是。front+1==rearB．(rear+1)%maxSize==C．front==0 D．front==rear6A=(a,b,(c,d),(e,(f,g)))，則Head(Tail(Head(Tail(Tail(A)))))的值為。A.(g) B.(d) C.c D.d7．一個二叉樹的前序遍歷序列為 ABCDEFG，它的中序遍歷序列可。A.CABDEFG B.BCDEAFG C.DBACEFG D.EBACDFG8．高度為h的滿二叉樹(僅含根結(jié)點的二叉樹高度為零)的結(jié)點數(shù)是。A.h＋1 B.2h＋1 C.2h+1－1 D.2h9．依次插入序列(50，72，43，85，75，20，35，45，65，30)后建立的二叉搜索樹中，查找元素35要進行 元素間的比較。A.4次 B.5次 C.7次 D.10次10.AVL：49,94,91,47,92,45,89,42,87，當(dāng)刪除關(guān)鍵碼時，如果該關(guān)鍵碼同時具有左右子女，則以其中后繼替代，則刪除關(guān)鍵碼91時的旋轉(zhuǎn)類型是 。A.左單旋 B.左右雙旋 C.右單旋 D.其它情況關(guān)鍵路徑是結(jié)點網(wǎng)絡(luò)中 。從源點到匯點的最長路徑從源點到匯點的最短路徑最長的回路最短的回路

三．應(yīng)用題（每小題5分，共30分）1． list=(5,(3,2,(14,9,3),(),4),2,(6,3,10))的鏈表表示。2．設(shè)初始數(shù)據(jù)為(40,12,64,74,65,63,82,36)，試將其調(diào)整為最小堆；如果初始堆為空，在按照上述序列依次輸入數(shù)據(jù)的同時調(diào)整堆，最如圖所示的無向圖，從頂點v1訪問序列是 。

開始進行深度優(yōu)先遍歷，可得到的頂點

后得到的最小堆是什么？3.對如圖所示的樹：A.1234567 B.1243567C.1245637 D.1243576題題2-12圖在基于關(guān)鍵碼比較的排序算法中算法在最壞情況下，關(guān)鍵比較次數(shù)不高于O(nlog。2A.起泡排序 B.直接插入排序C.二路歸并排序 D.快速排序14．對數(shù)據(jù)元素序列(49,72,68,13,38,50,97,27)排序，前三趟排序結(jié)束時的結(jié)果依次為：第一趟：13,72,68,49,38,50,97,27；第二趟：13,27,68,49,38,50,97,72；第三趟：13,27,38,49,68,50,97,72；該排序采用的方法是 。A.直接插入排序 B.直接選擇排序C.冒泡排序 D.堆排序在一棵m階B-樹中若在某葉子結(jié)點中插入一個新關(guān)鍵字而引起該點分裂，則此結(jié)點中原有的關(guān)鍵字的個數(shù)是 。123456789101112131415A.m B.m-1 C.m123456789101112131415

寫出先根遍歷得到的結(jié)點序列；寫出層次遍歷得到的結(jié)點序列；ababcdefghijklm題3-3圖PrimV12325 1 4① 2325 1 42353 ⑤ 23552 ⑧題題3-4圖序列？對不是拓撲序列的說明理由。① ③ ⑤ ⑧④ ⑥ ⑨

a/=b;}while(a!=0);while(!stack.IsEmpty())cout<<stack.Pop();}對于函數(shù)調(diào)用f(1234,10)，請寫出其運行結(jié)果。② ⑦題題3-5圖(1)．①②③④⑤⑥⑦⑧⑨(2)．①③②④⑥⑤⑧⑦⑨(3)．②①④③⑥⑤⑦⑧⑨(4)．①④②③⑥⑦⑤⑧⑨6．給定關(guān)鍵碼序列(11,81,23,59,17,19,68H(key)=(5*key)%11均搜索長度。四．算法題（每小題6分，共30分）1．a(chǎn)mbnabc。2．p是雙向循環(huán)鏈表中的一個結(jié)點，請寫出實現(xiàn)下列操作的語句：在pqlLink、rLink（左鏈）后繼（右鏈）指針。voidf(longa,intb){Stack<int>stack;do{stack.Push(a%b);

定義二叉樹結(jié)構(gòu)如下：template<classType> classBinaryTree;template<classType> classBinTreeNode{//friendclassBinaryTree<Type>;//二叉樹類BinTreeNode<Type> *leftChild, *rightChild;Typedata; //數(shù)據(jù)域Public:??}已知該算法為交換二叉樹中所有結(jié)點的左右子女，試填寫出空白處的語句。template<classType>voidfun(BinTreeNode<Type>*&p)BinTreeNode<Type>*temp;if(p==NULL) return;if(p->leftChild!=NULL||p->rightChild!=NULL){temp=p->leftChild;p->leftChild=p->rightChild;p->rightChild=temp; ;fun(p->rightChild);}}根據(jù)注釋完成算法template<classType>intorderedList<Type>::BinarySearch(constType&x)const{ // 折半搜索的迭代算法in