南郵數(shù)據(jù)結(jié)構(gòu)B期末試卷

1、-.-.-.可修編-班級(jí)學(xué)號(hào) 得分?jǐn)?shù) 據(jù) 結(jié) 構(gòu) B 期 末 試 卷題號(hào)題號(hào)一二三四五六分?jǐn)?shù)一、解答題：（共 82 分）1、下列程序段或函數(shù)的時(shí)間復(fù)雜度。（10%）（1） for(intk=0;km;k+)（2）int fac(unsigned intn)for(intj=0;jn;j+) if (n= =0|n= =1) return 1; akj=k*j;else returnn*fac(n-1);（3） intPrime(intn)（4）k=1;x=0; int k=2 ,x=(int)sqrt(n);do while(k=x)x+;k*=2;if (n %k=0)break;k+;wh

2、ile(kx) return 1; else return 0; 2、有 A、B、C、D 四個(gè)元素依次入棧，即入棧序列唯一，問(wèn)共能得到多少種出棧序列？ BDACCBDADBACPush、Pop（6%）3矩陣 A以行優(yōu)先方式從 1000H 處開(kāi)始存放元素類(lèi)型未知已知存放在 1011Hm*n處，A11存放在 1005H 處，求元素 A20的存放位置。（6%）4、根據(jù)下圖所示的樹(shù)回答問(wèn)題：（共 13%）畫(huà)出該樹(shù)等效的二叉樹(shù)。 （3%）ABABCDEFGHIJKL、寫(xiě)出對(duì)該樹(shù)進(jìn)行先序、后序遍歷的結(jié)點(diǎn)序列。（4%）用帶右鏈的先序表示法來(lái)存儲(chǔ)此樹(shù)，填寫(xiě)下表。（6%）下標(biāo)01234567891011sibl

3、ing element ltagsibling element ltag5、假設(shè)用于通訊的電文僅由 ABCDEFGH 8個(gè)字母組成，字母在電文中出現(xiàn)的頻率分別為0.07, 0.19, 0.02, 0.06, 0.32, 0.03, 0.21, 0.10這8個(gè)字母的哈夫曼編碼，最后求出WPL（9%）6、對(duì)下圖，要求：（共 13%）131363742558834457565561 到頂點(diǎn) 8 的四條路徑長(zhǎng)度為 3 的簡(jiǎn)單路徑。（2%）分別寫(xiě)出從頂點(diǎn) 1所示的鄰接表用深度優(yōu)先搜索和廣度優(yōu)先搜索遍（4%）成樹(shù)是唯一的嗎？（4%）7、一項(xiàng)工程 P 由 P1，P2，P3，P4，P5，P6 六個(gè)子工程組成，

4、這些工程之間有下列關(guān)系： P1P2,P1P3,P1P4,P2P3,P2P5,P3P6,P4P6,P5P6。其中符號(hào)“”表示先于關(guān)系，例如 P1P2 表示只有在工程 P1 完成之后才能進(jìn)行 P2 的工作。請(qǐng)：（7%）AOVP8、按如下關(guān)鍵字序列（60，88，107，15，8，23，100）從空樹(shù)開(kāi)始建立一棵 AVL 搜索樹(shù)， 畫(huà)出建樹(shù)的步驟以及調(diào)整平衡的過(guò)程（6%）9、設(shè)散列表ht13，散列函數(shù)h(key)=key % 13。采用二次探查法解決沖突，試用關(guān)鍵字值序列：56，78，14，27，41，70，51，66，24，50，36建立散列表。（6%）i0123456789101112hti10、

5、元素序列：55，71，12，98，4，70，51 ，請(qǐng)寫(xiě)出用冒泡排序法和 2 路合并排序法進(jìn)行排序的各趟排序結(jié)果。（6%）冒泡排序法 2 路合并排序法二、算法填空：(8%)以下算法實(shí)現(xiàn)二叉搜索樹(shù)的刪除，根據(jù)給定的關(guān)鍵字 k，找到待刪除元素后將元素值通過(guò)參數(shù) e 返回，若成功刪除則返回 true；找不到待刪除元素則返回 false.templateBSTree:Delete(constK &k , E &e)BTNode*p=root,*q=0; while(p &p-element!=kq=p;if (kelement) p=p-lchild; elseif (!p)cerrelement;w

6、hile (p-lchild & p-rchild)BTNode *s=p-rchild, while( s-lchild) s=s-lchild; p=s;q=r;BTNode *c;if(p-lchild)c=p-lchild;else;if()root=c;else if ( p= =q-lchild ) q-lchild=c; else q-rchild=c; returntrue;三、算法設(shè)計(jì)（10%）遞增有序，注意：不允許再增加新的結(jié)點(diǎn)，相同元素只保留一份。該算法為 SingleList 類(lèi)的成員函數(shù)Merge,該函數(shù)的作用是將形參r中，合并后的結(jié)果存于當(dāng)前單循環(huán)鏈表。template class SingleList; template class Node private:T data; Node *link;friend class SingleList;template class SingleList:public LinearListpublic:voidMerge(constSingleList&r);. private:Node *first;.;例：合并前：this-fir