杭電-[數(shù)據(jù)結(jié)構(gòu)(c語(yǔ)言版)]-資料下載頁(yè)
2025-06-17 14:08本頁(yè)面
【正文】 /2249。個(gè)關(guān)鍵字。F10．對(duì)于任何待排序序列來(lái)說(shuō)，快速排序均快于起泡排序。F二．選擇題（每題2分共28分）1．在下列排序方法中，（ c ）方法平均時(shí)間復(fù)雜度為0(nlogn)，最壞情況下時(shí)間復(fù)雜度為0(n2)；（ d ）方法所有情況下時(shí)間復(fù)雜度均為0(nlogn)。a. 插入排序 b. 希爾排序 c. 快速排序 d. 堆排序 2. 在有n個(gè)結(jié)點(diǎn)的二叉樹的二叉鏈表表示中，空指針數(shù)為（ b ）。 +1 3. 下列二叉樹中，（ a ）可用于實(shí)現(xiàn)符號(hào)不等長(zhǎng)高效編碼。 4. 下列查找方法中，（ a ）適用于查找有序單鏈表。 5. 在順序表查找中，為避免查找過(guò)程中每一步都檢測(cè)整個(gè)表是否查找完畢，可采用（ a ）方法。 6. 在下列數(shù)據(jù)結(jié)構(gòu)中，（ c ）具有先進(jìn)先出特性，（ b ）具有先進(jìn)后出特性。a．線性表 b．棧 c．隊(duì)列 d．廣義表7．具有m個(gè)結(jié)點(diǎn)的二叉排序樹，其最大深度為（ f ），最小深度為（ b ）。a. log 2 m b. └ log2 m ┘ +1 c. m/2d .┌ m/2 ┐ 1 e. ┌ m/2 ┐ f. m 8．已知一組待排序的記錄關(guān)鍵字初始排列如下：56,34,58,26,79,52,64,37,28,84,57。下列選擇中（ c ）是快速排序一趟排序的結(jié)果。（ b ）是希爾排序（初始步長(zhǎng)為4）一趟排序的結(jié)果。（ e ）是起泡排序一趟排序的結(jié)果。（ a ）是初始堆（大堆頂）。a. 84，79，64，37，57，52，58，26，28，34，56。b. 28，34，57，26，56，52，58，37，79，84，64。c. 28，34，37，26，52，56，64，79，58，84，57。d. 52，34，64，84，56，26，37，57，58，28，79。e. 34，56，26，58，52，64，37，28，79，57，84。f. 34，56，26，58，52，79，37，64，28，84，57。三．填空題（每題2分共20分）1．有向圖的存儲(chǔ)結(jié)構(gòu)有（鄰接矩陣）、（鄰接表）、（十字鏈表）等方法。2．已知某二叉樹的先序遍歷次序?yàn)閍fbcdeg，中序遍歷次序?yàn)閏edbgfa。其后序遍歷次序?yàn)椋╡dcgbfa）。層次遍歷次序?yàn)椋╝fbcgde）。3．已知如下程序段for( i=n。 i0。 i) {語(yǔ)句1}{x++。 {語(yǔ)句2}for( j=n。 j=i。 i) {語(yǔ)句3}y++。 {語(yǔ)句4}}。語(yǔ)句1執(zhí)行的頻度為（n+1）；語(yǔ)句4執(zhí)行的頻度為（n(n+1)/2）。 4．請(qǐng)?jiān)谙聞澗€上填入適當(dāng)?shù)恼Z(yǔ)句，完成以下法算。Status Preordertraverse(Bitree T,Status(*Visit)(Telemtype e)){//先序非遞歸遍歷二叉樹。Initstack ( S )。 Push ( S,T )。While ( !stackempty( S ) ) { While ( gettop( S, p )amp。amp。 p ) { visit (pdata ) 。 push(S, plchild 。} Pop ( S , p )。 If ( !stackempty(s) ) { pop(S, p) 。 push( S, prchild )。 }}return ok。四．簡(jiǎn)答題（每題5分共25分）1．將圖示森林轉(zhuǎn)換為二叉樹，并對(duì)該二叉樹中序全序線索化。 abdjcehfgmlki abdjcehfgmlki 2．已知Hash函數(shù)為 H（K）=K mod 13 ，散列地址為0 14，用二次探測(cè)再散列處理沖突，給出關(guān)鍵字（23，34，56，24，75，12，49，52，36，92，06，55）在散列表中的分布，并求在等概率情況下查找成功的平均查找長(zhǎng)度。0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 52 925556360634 75 23241249ASL=22/12=11/6 3. 右圖為一棵3階B 樹。 （20，25）a. 畫出在該樹上插入元素15后的B 樹。 ／ │ ＼ b. 接著，再刪除元素35，畫出刪除后的B 樹。 (10,14)（21）（35）14 20101521,2520142510152135 a. b. 。 。0 a 2 4 /\1 b 2 3 4 /\2 c 0 1 4 /\3 d 1 /\ 4 e 0 1 2 /\abecdabecdabecd b. d. c. DFS:acbde。 BFS:acebd5. 設(shè)在某通信系統(tǒng)中使用了八個(gè)字符，，，，，試構(gòu)造一棵赫夫曼樹，并給出赫夫曼編碼。赫夫曼編碼2610121481875: 赫夫曼樹： :000 :0110 :002 :010 :10 :110 :111 :0111五．算法設(shè)計(jì)題（共17分）1. 單鏈表結(jié)點(diǎn)的類型定義如下：typedef struct LNode { int data。 struct LNode *next。} LNode, *Linklist。寫一算法，將帶頭結(jié)點(diǎn)的有序單鏈表A和B合并成一新的有序表C。(注:不破壞A和B的原有結(jié)構(gòu).)Merge(Linklist A, Linklist B, Linklist amp。C )void Merge(Linklist A, Linklist B, Linklist amp。C){ C=(Linklist)malloc(sizeof(LNode))。 pa=Anext。 pb=Bnext。 pc=C。 while(paamp。amp。pb) { pcnext=(Linklist)malloc(sizeof(LNode))。pc=pcnext。if(padata=pbdata){ pcdata=padata。 pa=panext。}else{ pcdata=pbdata。 pb=pbnext。}}if(!pa) pa=pb。while(pa){ pcnext=(Linklist)malloc(sizeof(LNode))。 pc=pcnext。 pcdata=padata。 pa=panext。}pcnext=NULL。}2. 二叉樹用二叉鏈表存儲(chǔ)表示。typedef struct BiTNode { TelemType data。 Struct BiTNode *lchild, *rchild。} BiTNode, *BiTree。編寫一個(gè)復(fù)制一棵二叉樹的遞歸算法。BiTree CopyTree(BiTree T) { if (!T ) return NULL。if (!(newT = (BiTNode*)malloc(sizeof(BiTNode)))) exit(Overflow)。newT data = T data。newT lchild = CopyTree(T lchild)。newT rchild = CopyTree(T rchild)。return newT。} // CopyTreeCopyright 169。 澤豬 2012051
試題試卷相關(guān)推薦
鄂ICP備17016276號(hào)-1