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

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

2、f (n % k= =0) break; k+; while (k<n); if (k>x) return 1; else return 0; 2、有A、B、C、D四個(gè)元素依次入棧，即入棧序列唯一，問(wèn)共能得到多少種出棧序列？能否得到以下四種出棧序列：ABCD、BDAC、CBDA、DBAC。對(duì)能得到的序列，請(qǐng)寫(xiě)出Push、Pop序列；對(duì)不能得到的序列，請(qǐng)說(shuō)明理由。（6%）3、矩陣Am*n以行優(yōu)先方式從1000H處開(kāi)始存放，元素類型未知，已知：A23存放在1011H處，A11存放在1005H處，求元素A20的存放位置。（6%）4、根據(jù)下圖所示的樹(shù)回答問(wèn)題：（共13%）（1）畫(huà)出該樹(shù)等效

3、的二叉樹(shù)。 （3%）AB CDE F G H I J K L 等效的二叉樹(shù)（2）、寫(xiě)出對(duì)該樹(shù)進(jìn)行先序、后序遍歷的結(jié)點(diǎn)序列。（4%）（3）用帶右鏈的先序表示法來(lái)存儲(chǔ)此樹(shù)，填寫(xiě)下表。（6%）下標(biāo)01234567891011siblingelementltag5、假設(shè)用于通訊的電文僅由 ABCDEFGH 8個(gè)字母組成，字母在電文中出現(xiàn)的頻率分別為0.07, 0.19, 0.02, 0.06, 0.32, 0.03, 0.21, 0.10。請(qǐng)畫(huà)出哈夫曼樹(shù)并在樹(shù)中標(biāo)明編碼情況，給出這8個(gè)字母的哈夫曼編碼，最后求出WPL。（9%）6、對(duì)下圖，要求：（共13%）123456783355554664785（1

4、）畫(huà)出它的鄰接表。（3%）（2）寫(xiě)出從頂點(diǎn)1到頂點(diǎn)8的四條路徑長(zhǎng)度為3的簡(jiǎn)單路徑。（2%）（3）分別寫(xiě)出從頂點(diǎn)1出發(fā)根據(jù)（1）所示的鄰接表用深度優(yōu)先搜索和廣度優(yōu)先搜索遍歷圖得到的頂點(diǎn)序列。（4%）（4）求出它的一棵最小代價(jià)生成樹(shù)(方法任選)，其代價(jià)是多少？你所求出的最小代價(jià)生成樹(shù)是唯一的嗎？（4%）7、 一項(xiàng)工程P由P1，P2，P3，P4，P5，P6六個(gè)子工程組成，這些工程之間有下列關(guān)系：P1>P2, P1>P3, P1>P4, P2>P3, P2>P5, P3>P6, P4>P6, P5>P6。其中符號(hào)“>”表示先于關(guān)系，例如P1>

5、P2表示只有在工程P1完成之后才能進(jìn)行P2的工作。請(qǐng)：（7%）（1） 畫(huà)出該工程的AOV網(wǎng) （2） 給出工程P的其中四種可能的施工順序。8、按如下關(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、元素序列：55，71，12，98，4，70，51 ，請(qǐng)寫(xiě)出用冒泡排序法和2路合并排序法進(jìn)行排

6、序的各趟排序結(jié)果。（6%）冒泡排序法 2路合并排序法二、算法填空：(8%)以下算法實(shí)現(xiàn)二叉搜索樹(shù)的刪除，根據(jù)給定的關(guān)鍵字k，找到待刪除元素后將元素值通過(guò)參數(shù)e返回，若成功刪除則返回true；找不到待刪除元素則返回false.template <class E,class K>_ BSTree<E,K>:Delete (const K &k , E & e) BTNode<E> *p=root,*q=0; while ( p && p->element!=k ) q=p;if (k<p->element) p=

7、p->lchild;else _; if (!p) cerr<<”No element with key kn”; _; e=p->element;while (p->lchild && p->rchild) BTNode<E> *s=p->rchild, *r=p; while ( s->lchild ) _; s=s->lchild; _ ;p=s;q=r;BTNode<E> *c;if (p->lchild) c=p->lchild;else _ ;if ( _ ) root=c;e

8、lse if ( p= =q->lchild ) q->lchild=c;else q->rchild=c;_;return true;三、算法設(shè)計(jì)（10%）編程實(shí)現(xiàn)將兩個(gè)按元素遞增排序的單向循環(huán)鏈表合并成一個(gè)單向循環(huán)鏈表，合并后元素仍遞增有序，注意：不允許再增加新的結(jié)點(diǎn)，相同元素只保留一份。該算法為SingleList類的成員函數(shù)Merge,該函數(shù)的作用是將形參r代表的單向循環(huán)鏈表合并到當(dāng)前單向循環(huán)鏈表中，合并后的結(jié)果存于當(dāng)前單循環(huán)鏈表。template <class T> class SingleList;template <class T>class Node private: T data; Node<T> *link;friend class SingleList<T> ;template <class T>class SingleList:public LinearList<T>public:void Merge(const SingleList<T> &r);.private:Node<T> *first;.;例：合并前：234108223782233478108this->first->