上課情況和電子版

數(shù)據(jù)結(jié)構(gòu)試卷（一一、單選題（每題220分棧和隊(duì)列的共同特點(diǎn)是(a)。用方式的隊(duì)列，在進(jìn)行插入運(yùn)算時(shí)(dA.僅修改頭指 B.頭、尾指針都要修C.僅修改尾指 dA.隊(duì) B. C.線性 D.二叉A[m][n]64(10)A2][2]每個(gè)元素占一個(gè)空間，問A[3][3](10)存放在什么位置？腳注(10)表示用10進(jìn)制表示。c 二叉樹的第kd D.2k-若有18個(gè)元素的有序表存放在一維數(shù)組A[19]中，第一個(gè)元素放A[1]中，現(xiàn)進(jìn)行二分查找，則查找A［3］的比較序列的下標(biāo)依次為( cd A. B.C. D.A. B. C. D.1（cd） 二、填空題（126分 時(shí)間正確 復(fù)雜度強(qiáng)壯 準(zhǔn)確度_高效 一個(gè)算法的時(shí)間復(fù)雜度為(n3+n2log2n+14n)/n2，其數(shù)量級(jí)表示 3 （C（EFG（IJ 后綴算式923+-102/-的值為3-1。中綴算式（3+4X）-2Y/3對(duì)應(yīng)的后綴算 34X*+2Y*/- 若用鏈表一棵二叉樹時(shí)，每個(gè)結(jié)點(diǎn)除數(shù)據(jù)域外，還有指向左孩子和右孩子的兩個(gè)指針。在這種結(jié)構(gòu)中，n個(gè)結(jié)點(diǎn)的二叉樹共有n_2n個(gè)指針域，其中有n-1個(gè)指針域是存放了地址，有 3n+1 分別有e+1_e個(gè)和e+12e個(gè)。AOV網(wǎng)是一 n個(gè)頂點(diǎn)的無向完全圖中，包含有n-1_n(n-1)/2 素成為一個(gè)子表，則得到的四個(gè)子表分別

向一棵B_樹插入元素的過程中，若最終引起樹根結(jié)點(diǎn)的，則新樹比原樹的高 增加 O(log2n)整個(gè)堆排序過程的時(shí)間復(fù)雜度為0（1） 堆排序歸并排 三、計(jì)算題（每題624分在如下數(shù)組A中了一個(gè)線性表，表頭指針為A[0].next，試寫出該線性表3572041 3572041A[0]A[3]A[2]A[7]A[1]A[5]A[4]78，5040，6034，90）鄰接矩陣：

1 1

1111已知一個(gè)圖的頂點(diǎn)集VE分別為：V={1,2,3,4,5,6,7}; 4,2,5,8,3四、閱讀算法（714分LinkListmynote(LinkList while(p－>next)p=p－>next； } }S1的功能；判斷pp則指向下一節(jié)點(diǎn)查詢鏈表的尾節(jié)點(diǎn)設(shè)鏈表表示的線性表為（a1,a2,…,an）,寫出算法執(zhí)行后的返回值所表示的線性表。a2,a3,…an,a1voidABC(BTNode*{ BTABC(BT->right);}}該算法的功能是：判斷是否為滿二叉樹遞歸的后序遍歷鏈?zhǔn)降亩鏄湮?、算法填空?分）boolFind(BTreeNode*BST,ElemType&{ifreturnfalse;else{if(item==BST-return item elseif(item<BST-returnFind( elsereturnFind( }六、編寫算法（8分intCountX(LNode*HL,ElemTypex){intcount;node*head,*p;head=HL;if(head-{while(p-{if(p-}}}Structnode{elemtypeStructnodeintCountX(LNode*HL,ElemType inti=0;LNode*p=HL;//i{if(P->data==x)i++;}//while,ixreturn數(shù)據(jù)結(jié)構(gòu)試卷（二一、選擇題(24 設(shè)哈夫曼樹中的葉子結(jié)點(diǎn)總數(shù)為m，若用二叉鏈表作為結(jié)構(gòu)，則該哈夫曼樹中總共有（）個(gè)空指針域。(A)2m- (B) (C) (D)Q[0：M-1FRFR（(A)R- (B)F- (C)(R-F+M)％M(D)(F- (A) (B) (C) (D)n（）(A)n(n- (B)n(n- (C) (D)n2-2000（(A) (B) (C) (D)n（）(A)n- (B) (C) (D)2n-速排序的結(jié)果為（(A) (B)(C) (D)二、填空題(24為了能有效地應(yīng)用HASH查找技術(shù)，必須解決的兩個(gè)問題 typedefstruct{ints[100];inttop;}sqstack;voidpush(sqstack&stack,intx){if(stack.top==m-1)else } 2的結(jié)點(diǎn)數(shù)為 設(shè)某無向圖中頂點(diǎn)數(shù)和邊數(shù)分別為n和e，所有頂點(diǎn)的度數(shù)之和為d，則 ，BFS三、應(yīng)用題(364設(shè)指針變量p指向雙向鏈表中結(jié)點(diǎn)A，指針變量q指向入結(jié)點(diǎn)B，要求給出在結(jié)點(diǎn)AB（設(shè)雙向鏈表中結(jié)點(diǎn)的兩個(gè)指針域分別為llinkrlink62T{(A，B)，(A，C)，(A，D)，(B，E)，(C，F(xiàn))，(C，G)}，要求四、算法設(shè)計(jì)題(16（K1K2Kn個(gè)關(guān)鍵字均大于等于Ki。設(shè)有兩個(gè)AB，要求設(shè)計(jì)生成C=A∩B的算法，其中A、BC用鏈?zhǔn)浇Y(jié)構(gòu)表示。數(shù)據(jù)結(jié)構(gòu)試卷（三一、選擇題(每題1分，共20<03，08>，<03，09>}A（(A)線性結(jié) (B)樹型結(jié) (C)物理結(jié) (D)圖型結(jié)下面程序的時(shí)間復(fù)雜為（for（i=1，s=0；i<=n；i++）{t=1；for(j=1；j<=i；j++)(A) (B) (C) (D)pAA，則需要修改指針的操作序列為（n（）2(A) (B) (C)nlog (D)2錄的一趟快速排序結(jié)束后的結(jié)果為()。n（2(A) (B)O(log (D)2Gne條邊，則其對(duì)應(yīng)的鄰接表中的表頭結(jié)點(diǎn)和表結(jié)點(diǎn)的個(gè)數(shù)分別為（(A) (B) (C) (D)n個(gè)頂點(diǎn)，則該強(qiáng)連通圖中至少有（）(A)n(n- (B) (C) (D)(A)(B)堆排 (C)歸并排(D)(A)(B)冒泡排 (C)堆排(D)二、填空殖(120 設(shè)一棵完全二叉樹中有500個(gè)結(jié)點(diǎn)，則該二叉樹的深度為 等于頂點(diǎn)i的 ，第i列上所有元 和等于頂點(diǎn)i的 100X， 下列算法實(shí)現(xiàn)在順序散列表中查找值為xstructrecord{intkey;intinthashsqsearch(structrecordhashtable[],int{int j=i=k%while(hashtable[j].key!=k&&hashtable[j].flag!=0){j=( )%m;if(i==j)return(-1);}if( )return(j);elsereturn(-1);}typedefstructnode{intkey;structnode*lchild;structnode*rchild;}bitree; *bstsearch(bitree*t,int {if(t==0) whileif(t- ;elseif(t->key>k)t=t->lchild; }三、計(jì)算題(每題10分，共30（3615406322選用的散列函數(shù)是H（K）=Kmod7，若發(fā)生采用線性探查法處理，試： 。四、算法設(shè)計(jì)題(1530數(shù)據(jù)結(jié)構(gòu)試卷（四一、選擇題(120設(shè)一維數(shù)組中有n個(gè)數(shù)組元素，則第i個(gè)數(shù)組元素的平均時(shí)間復(fù)雜度為（2(A) (B)O(nlog (C) (D)2k，則該二叉樹中最多有（）(A)2k- (B) (C)2k- (D)2k-ne（(A) (B) (C) (D)在二叉排序樹中插入一個(gè)結(jié)點(diǎn)的時(shí)間復(fù)雜度為（2(A) (B) (C)O(log (D)2nm（）(A) (B)n- (C) (D)m-(A) (B) (C) (D)設(shè)用鏈表作為棧的結(jié)構(gòu)則退棧操作（(A)必須判別棧是否為 (B)必須判別棧是否為(C)判別棧元素的類 (D)對(duì)棧不作任何判下列四種排序中（）(A)快速排 (B)冒泡排 (C)希爾排 (D)0N01Nl2N2，則下列等式成立的是（。(A) (B) (C) (D)nX超過（。(A) (B)log2n- (C) (D)二、填空題(120設(shè)有n個(gè)無序的記錄關(guān)鍵字，則直接插入排序的時(shí)間復(fù)雜度為 設(shè)指針變量p指向雙向循環(huán)鏈表中的結(jié)點(diǎn)X，則刪除結(jié)點(diǎn)X llinkrlink。 設(shè)哈夫曼樹中共有99個(gè)結(jié)點(diǎn)，則該樹中有

設(shè)順序線性表中有n個(gè)數(shù)據(jù)元素，則第i 個(gè)元素 設(shè)某無向圖G中有n個(gè)頂點(diǎn)，用鄰接矩陣A作為該圖的結(jié)構(gòu)，則頂點(diǎn)i和頂點(diǎn)j互 設(shè)無向圖對(duì)應(yīng)的鄰接矩陣為A，則A中第i上非0元素的個(gè) 第i列上非 hashtalbek的結(jié)點(diǎn)，成功時(shí)返回指向關(guān)鍵0。typedefstructnode{intkey;structnode*next;}lklist;voidcreakhash(lklist*hashtable[]){int lklist {k=a[i]%p;s- }}三、計(jì)算題(每題10分，共301、畫出廣義表LS=((),(e),(a,(b,c,d)))的頭尾鏈表結(jié)構(gòu)ABCABC 3、設(shè)散列表的地址范圍是[0..9H（key）=（key2+2）MOD9,并采用鏈表處理，請(qǐng)畫出元素、、、、、、、依次插入散列表的結(jié)構(gòu)。四、算法設(shè)計(jì)題(每題10分，共30在鏈 數(shù)據(jù)結(jié)構(gòu)試卷（五一、選擇題(20分)1．?dāng)?shù)據(jù)的最小單位是（(A)數(shù)據(jù) (B)數(shù)據(jù)類 (C)數(shù)據(jù)元 (D)數(shù)據(jù)變?cè)O(shè)一組初始記錄關(guān)鍵字序列為(50，40，95，20，15，70，60，45)，則以增量d=4的一趟希爾排序結(jié)束后前4條記錄關(guān)鍵字為（ (B)(C) (D)，其中含有個(gè)長(zhǎng)度為2的有序子表，則用歸并排序的方法對(duì)該記錄關(guān)鍵字序列進(jìn)行一趟歸并后的結(jié) substr(“DATASTRUCTURE”，5，9)的返回值為（ (B)(C) (D)n，則該操作的時(shí)間復(fù)雜度為（2(A)O(log (B) (C) (D)2m0N01NlmNmN0=（。 (B)l+N2+2N3+3N4+……+(m-(C)N2+2N3+3N4+……+(m- (D)1000X（）(A) (B) (C) (D)a（(A) (B) (C) (D)i（(A)n- (B)n-1- (C)n+1- (D)基準(zhǔn)而得到一趟快速排序的結(jié)果是（(A) (B)(C) (D)二、填空題20設(shè)有一個(gè)順序共享?xiàng)[0：n-1]，其中第一個(gè)棧項(xiàng)指針top1的初值為-1，第二個(gè)棧頂指針top2的初值為n，則判斷共享?xiàng)M的條件是 設(shè)有一個(gè)n階的下三角矩陣A，如果按照行的順序?qū)⑾氯蔷仃囍械脑兀ò▽?duì)角線上元素）存放在n(n+1)個(gè)連續(xù)的單元中，則A[i][j]與A[0][0]之間有 設(shè)一棵完全二叉樹的順序結(jié)構(gòu)中數(shù)據(jù)元素為ABCDEF，則該二叉樹的前序遍歷 設(shè)一棵完全二叉樹有128個(gè)結(jié)點(diǎn)，則該完全二叉樹的深度為 設(shè)有向圖G的結(jié)構(gòu)用鄰接矩陣A來表示，則A中第i行中所有非零元素個(gè)數(shù)之和等于頂點(diǎn)i的 ，第i列中所有非零元素個(gè)數(shù)之和等于頂點(diǎn)i的 void {for(i=1;i<=n-1;{for(exchange=0,j=0; if(r[j]>r[j+1]){temp=r[j+1]; if(exchange==0)return；}}structrecord{intkey;intothers;};intbisearch(structrecordr[],intk){intlow=0,mid,high=n-1;{ if(r[mid].key==k)return(mid+1);else )high=mid-1;else}}三、應(yīng)用題(32DBEACABDEC，設(shè)無向圖G（如右圖所示 四、算法設(shè)計(jì)題(28數(shù)據(jù)結(jié)構(gòu)試卷（六一、選擇題(30之和為（(A) (B) (C) (D)執(zhí)行一趟快速排序能夠得到的序列是（[41，12，34，45，27]55[45，34，12，41]55[63，12，34，45，27]55[12，27，45，41]55head且該鏈表沒有頭結(jié)點(diǎn)，則其判空條件是（ (B)head-(C)head->next==head (D)head!=04．O(nlog2n)的是（(A)堆排 (B)冒泡排 (C)希爾排 (D)快速排設(shè)二叉樹的先序遍歷序列和后序遍歷序列正好相反，則該二叉樹滿足的條件是（ (B)高度等于其結(jié)點(diǎn)(C)任一結(jié)點(diǎn)無左孩 (D)任一結(jié)點(diǎn)無右孩一趟排序結(jié)束后不一定能夠選出一個(gè)元素放在其最終位置上的是（(A)堆排 (B)冒泡排 (C)快速排 (D)希爾排40（(A) (B) (C) (D)順序查找不論在順序線性表中還是在鏈?zhǔn)骄€性表中的時(shí)間復(fù)雜度為（2(A) (B) (C) (D)O(1og2二路歸并排序的時(shí)間復(fù)雜度為（(A) (B) (C)O(nlog (D)O(1og 深度為k（）(A)2k-1- (B)2k- (C)2k- (D)2k-sX，則入隊(duì)列的操作序列為（front- (B)s-(C)rear- (D)s-ne（(A) (B) (C) (D)199（）(A) (B) (C) (D)n（22(A) (B) (C)O(nlog (D)O(1og22設(shè)用鄰接矩陣A表示有向圖G的結(jié)構(gòu)，則有向圖G中頂點(diǎn)i的入度為（ (B)第i列非0元素的個(gè)數(shù)之(C)第i行0元素的個(gè)數(shù)之和 (D)第i列0元素的個(gè)數(shù)之和二、判斷題(20分)調(diào)用一次深度優(yōu)先遍歷可以到圖中的所有頂點(diǎn)（（（滿二叉樹一定是完全二叉樹，完全二叉樹不一定是滿二叉樹（（（設(shè)一棵樹TBTBT（線性表的順序結(jié)構(gòu)比鏈?zhǔn)浇Y(jié)構(gòu)更好（（快速排序是排序算法中平均性能最好的一種排序（三、填空題(30 設(shè)指針變量p指向單鏈表中結(jié)點(diǎn)A，指針變量s指向入的新結(jié)點(diǎn)X，則進(jìn)行插入操 （設(shè)結(jié)點(diǎn)的指針域?yàn)閚extGG（DRD={1345R={r}r={<1,2>， 設(shè)無向圖G中有n個(gè)頂點(diǎn)，則該無向圖中每個(gè)頂點(diǎn)的度數(shù)最多 050，130， FR 設(shè)二叉樹中結(jié)點(diǎn)的兩個(gè)指針域分別為lchild和rchild，則判斷指針變量p所指向的結(jié) 四、算法設(shè)計(jì)題(20３．在鏈?zhǔn)浇Y(jié)構(gòu)上設(shè)計(jì)直接插入排序算法數(shù)據(jù)結(jié)構(gòu)試卷（七一、選擇題(30n（）(A) (B) (C) (D)n(n-設(shè)無向圖Gn（）(A) (B)n- (C) (D)2n-而得到的一趟快速排序結(jié)果是（(A) (B)(C) (D)4（(A)先序遍 (B)中序遍 (C)后序遍 (D)層次遍點(diǎn)的左孩子結(jié)點(diǎn)的編號(hào)為（(A) (B) (C) (D)2i-s=i=0；doi=i+1s=s+i；}while(i<=n)；的時(shí)間復(fù)雜度為（2(A) (B)O(nlog (C) (D)2head，則其判空條件是（ (B)head-(C)head- (D)10，則該二叉樹上葉子結(jié)點(diǎn)最多有（(A) (B) (C) (D)90（。(A) (B) (C) (D)top（ (B)top=top-(C)top- (D)top=top-二、判斷題(20不論是入隊(duì)列操作還是入棧操作，在順序結(jié)構(gòu)上都需要考慮“溢出”情況（（ （1（對(duì)連通圖進(jìn)行深度優(yōu)先遍歷可以到該圖中的所有頂點(diǎn)（（（（（）三、填空題(30設(shè)指針變量p指向雙向鏈表中的結(jié)點(diǎn)A，指針變量s指向入的結(jié)點(diǎn)X，則在結(jié)點(diǎn)A的后面插入結(jié)點(diǎn)X=p；s->right=p->right；=s；->left=s（right設(shè)完全有向圖中有n個(gè)頂點(diǎn)，則該完全有向圖中共有 中有n個(gè)頂點(diǎn)，則該完全無向圖中共有 3的結(jié)點(diǎn)數(shù) 個(gè) 設(shè)一棵二叉樹的前序序列為ABC，則有 structrecord{intkey;datatypevoidquickpass(structrecordr[],ints,intt,int{intj=t;structrecordx=r[s];i=s;{while(i<j&&r[j].key>x.key)j=j- if(i<j)while ) if(i<j){r[j]=r[i];j=j-} }四、算法設(shè)計(jì)題(20數(shù)據(jù)結(jié)構(gòu)試卷（八一、選擇題(30 (B)串中不同字母的個(gè)(C)串中所含字符的個(gè) (D)串中不同數(shù)字的個(gè)n（2(A) (B) (C) (D)O(log2兩個(gè)字符串相等的充要條件是（ (B)兩個(gè)字符串中對(duì)應(yīng)位置上的字符相(C)同時(shí)具備(A)和(B)兩個(gè)條 (D)以上答案都不100，H(k)=kP，則P（(A) (B) (C) (D)在二叉排序樹中插入一個(gè)關(guān)鍵字值的平均時(shí)間復(fù)雜度為（22(A) (B)O(1og (C)O(nlog (D)22A[1:1414A[4]的過程中比較元素的順序?yàn)?)。 (B)(C) (D)A[7]，A[5]65（(A) (B) (C) (D)則該三叉鏈權(quán)中有（）0(A) (B) (C) (D)(A)(B)(C)(D)(A)(B)(C)(D)(A)先進(jìn)先出 (B)先進(jìn)后出 (C)只能插入 (D)只能刪除二、判斷題(20分)如果兩個(gè)關(guān)鍵字的值不等但哈希函數(shù)值相等，則稱這兩個(gè)關(guān)鍵字為同義詞（O(nlog2n)（（）二維數(shù)組和數(shù)組均不是特殊的線性結(jié)構(gòu)（（如果某個(gè)有向圖的鄰接表中第ii（（O(n)（（） 可以用一個(gè)三元組表來表示稀疏矩陣中的非0元素（三、填空題(30 typedefstructnode{intdata;structnode*lchild;structnode bstinsert(bitree*&t,intk){if(t==0){ elseif(t->data>k)bstinsert(t->lchild,k);else } 面插入結(jié)點(diǎn)X需要執(zhí)行的語句序列：s->next=p->next; ;設(shè)指針變量head指向雙向鏈表中的頭結(jié)點(diǎn)指針變量p指向雙向鏈表中的第一個(gè)結(jié)點(diǎn)，則指針變量p和指針變量head之間的關(guān)系是p=和head= 中的兩個(gè)指針域分別為llink和rlink設(shè)某棵二叉樹的中序遍歷序列為ABCD，后序遍歷序列為BADC 堆只需把16與 四、算法設(shè)計(jì)題(20數(shù)據(jù)結(jié)構(gòu)試卷（九一、選擇題(30下列程序段的時(shí)間復(fù)雜度為（for(i=0；i<m；i++)for(j=0；j<t；j++)(A) (B) (C) (D)ni（）(A)n- (B)n+l- (C)n-1- (D)數(shù)分別為N1、N2和N3，則二叉樹B的根結(jié)點(diǎn)的左子樹的結(jié)點(diǎn)數(shù)為（ (A)N1- (B)N2- (C) (D)利用直接插入排序法的思想建立一個(gè)有序線性表的時(shí)間復(fù)雜度為（22(A) (B)O(nlog (C) (D)O(1og22設(shè)指針變量p指向雙向鏈表中結(jié)點(diǎn)A，指針變量s指向入的結(jié)點(diǎn)X，則在結(jié)點(diǎn)A的后面插入結(jié)點(diǎn)X（p->right=s；s->left=p；p->right->left=s；s->right=p-p->right=s；p->right->left=s；s->left=p；s->right=p- (A)快速排 (B)堆排 (C)歸并排 (D)冒泡排i（(A)n- (B)n-1- (C)n+l- (D)設(shè)散列表中有m個(gè)單元，散列函數(shù)H(key)=key%p，則p最好選擇（ (B)小于等于m的最大素(C)小于等于m的最大偶 (D)小于等于m的最大合120（）(A) (B) (C) (D)n（）(A)n(n- (B)n(n- (C) (D)(n-n，則順序查找的平均比較次數(shù)為（(A) (B) (C) (D)(n-的元素需要經(jīng)過（）(A) (B) (C) (D)找長(zhǎng)度為（(A) (B) (C) (D)G（(A) (B)2，3，4，1(C)1，4，2，3(D)生成的二叉排序樹的深度為（(A) (B) (C) (D)二、填空題(30X1)s- ；2)p->next=s；3)t=p-4)p- ；5)s- 設(shè)某順序循環(huán)隊(duì)列中有m個(gè)元素，且規(guī)定隊(duì)頭指針F指向隊(duì)頭元素的前一個(gè)位置，隊(duì)尾指針R指向隊(duì)尾元素的當(dāng)前位置，則該循環(huán)隊(duì)列中最多 排序 三、判斷題(20有向圖的鄰接表和逆鄰接表中表結(jié)點(diǎn)的個(gè)數(shù)不一定相等。()對(duì)鏈表進(jìn)行插入和刪除操作時(shí)不必移動(dòng)鏈表中結(jié)點(diǎn)。()子串“ABC”在主串“AABCABCD2。(遍歷序列中的最后一個(gè)結(jié)點(diǎn)。()O(n2)。(數(shù)有關(guān)。()中序遍歷一棵二叉排序樹可以得到一個(gè)有序的序列。()入棧操作和入隊(duì)列操作在鏈?zhǔn)浇Y(jié)構(gòu)上實(shí)現(xiàn)時(shí)不需要考慮棧溢出的情況。(順序表查找指的是在順序結(jié)構(gòu)上進(jìn)行查找（（五、算法設(shè)計(jì)題(20數(shù)據(jù)結(jié)構(gòu)試卷（十一、選擇題(24下列程序段的時(shí)間復(fù)雜度為（i=0，s=0；while(s<n)(A)O(n1/2)(B)O(n1/3)(C)O(n)(D)設(shè)某鏈表中最常用的操作是在鏈表的尾部插入或刪除元素，則選用下列（）方式 (B)單向循環(huán)鏈(C)雙向鏈 (D)雙向循環(huán)鏈設(shè)指針q指向單鏈表中Ap單鏈表中結(jié)點(diǎn)A后繼結(jié)點(diǎn)B，指針s指向被XABX（s->next=p->next；p->next=-s；(B)q->next=s；s-(C)p->next=s->next；s->next=p；(D)p->next=s；s-1、2、3、4、5、6，則通過棧的作用后可以得到的輸出序列為（(A) (B)(C) (D)設(shè)有一個(gè)10階的下三角矩陣A（包括對(duì)角線按照從上到下、從左到右的順序到連續(xù)的55個(gè)單元中每個(gè)數(shù)組元素占1個(gè)字節(jié)的空間則A[5][4]地址與A[0][0]的地址之差為（(A) (B)19(C)28(D)設(shè)一棵m叉樹N1個(gè)度1N2個(gè)度數(shù)為2Nm個(gè)度數(shù)為m結(jié)點(diǎn)，則該樹中共有（）個(gè)葉子結(jié)點(diǎn)。mm(i

mmNi

mm(C)Ni

mm1(i二叉排序樹中左子樹上所有結(jié)點(diǎn)的值均（）(A) (B) (C) (D)夫曼樹，則這棵哈夫曼樹的帶權(quán)路徑長(zhǎng)度為（(A) (B) (C) (D)表中需要做（）(A) (B) (C) (D)n(n-020n，則這棵二叉中共有（）個(gè)結(jié)點(diǎn)。(A) (B) (C)2n- (D)8，則最多經(jīng)過（）(A) (B) (C) (D) 二、填空題(48分，其中最后兩小題各6設(shè)需要對(duì)5個(gè)不同的記錄關(guān)鍵字進(jìn)行排序，則至少需要比較 次設(shè)在長(zhǎng)度為20的有序表中進(jìn)行二分查找，則比較一次查找成功的結(jié)點(diǎn)數(shù)有 設(shè)一棵m叉樹脂的結(jié)點(diǎn)數(shù)為n，用多重鏈表表示其結(jié)構(gòu)，則該樹中有 設(shè)指針變量pA，則刪除結(jié)點(diǎn)A 設(shè)散列表的長(zhǎng)度為8，散列函數(shù)H(k)=k%7，用線性探測(cè)法解決，則根據(jù)一組初始 typedefstructnode{intdata;structnode voidcreatebitree(bitree*&bt){if(ch=='#') }typedefstructnode{intdata;structnode*next;}lklist;voidlklistcreate( *&head){for{p=(lklist*)malloc(sizeof(lklist));scanf(“%d”,&(p->data));p->next=0;if(i==1)head=q=p;else{q->next=p; }}三、算法設(shè)計(jì)題(22設(shè)計(jì)在二叉排序樹上查找結(jié)點(diǎn)X數(shù)據(jù)結(jié)構(gòu)試卷（一）參考答一、選擇題（220分1.A 二、填空題（126分正確 強(qiáng)壯 高效 - 34X*+2Y*3/ n- n(n- n(n- （ 12.三、計(jì)算題（624分78，5040，6034，90） 1 1 鄰接矩陣：

1111 4422424442242452458245 23235 四、讀算法（714分五、法填空（28分 六、編寫算法（8分intCountX(LNode*HL,ElemType inti=0;LNode*p=HL;//i{if(P->data==x)i++;}//while,ixreturn數(shù)據(jù)結(jié)構(gòu)試卷（二）參考答 22N0-略（K1，K2，…，nKi。voidquickpass(intr[],ints,int{inti=s,j=t,x=r[s];while(i<j&&r[j]>x)j=j-1;if(i<j)while(i<j&&r[i]<x)i=i+1;if(i<j){r[j]=r[i];j=j-}}AB，C=A∩BA、BCtypedefstructnode{intdata;structnode*next;}lklist;voidintersection(lklist*ha,lklist*hb,lklist*&hc){lklist*p,*q,*t; }}數(shù)據(jù)結(jié)構(gòu)試卷（三）參考答第3小題分析：首先用指針變量q指向結(jié)點(diǎn)A的后繼結(jié)點(diǎn)B，然后將結(jié)點(diǎn)B的值到AB。第9小題分析：9快速排序、歸并排序和插入排序必須等到整個(gè)排序結(jié)束后才能夠求出最小的10個(gè)數(shù)，而堆排序只需要在初始堆的基礎(chǔ)上再進(jìn)行10次篩選即可，每次篩選的時(shí)間O(log2n)。5071+log2n。AAEBFGCDHFKJ2、H(36)=36mod H１(22)=(1+1)mod7=2;H(15)=15mod7=1;….H2(22)=(2+1)mod7=3;H１(15)=(1+1)mod7=2;H(40)=40modH(63)=63mod7=0;H(22)=22mod7=1;…. （2）ASL=1211353、1,3,typedefinttypedefstructnode{datatypedata;structnode*next;}lklist;voiddelredundant(lklist*&head){lklist*p,*q,*s;{if(q->data==p->data){s->next=q->next;free(q);q=s->next;}else{s=q,q=q->next;}}}typedefstructnode{datatypedata;structnode*lchild,*rchild;}bitree;bitree*q[20];intr=0,f=0,flag=0;voidpreorder(bitree*bt,char{if(bt!=0&&if(bt->data==x){flag=1;else{r=(r+1)%20;q[r]=bt;preorder(bt->lchild,x);preorder(bt->rchild,x);}voidparent(bitree*bt,char{inti;for(i=f+1;i<=r;i++)if(q[i]->lchild->data==x||q[i]->rchild->data)break;if(flag==0)printf("notfoundx\n");elseif(i<=r)printf("%c",bt->data);elseprintf("not}數(shù)據(jù)結(jié)構(gòu)試卷（四）參考答 2231^-1^-

-- ^^1b0---1^1----b0---1^1----a01^1e01---1----0c1^dd0(1) BDEFCA；(2) BDEFCAIJKHGAABGCHDIEJ 4^4^3869^^27^^^^5123456789typedefchartypedefstructnode{datatypedata;structnode*next;}lklist;voidsplit(lklist*head,lklist*&ha,lklist*&hb,lklist*&hc){lklist*p;ha=0,hb=0,hc=0;{if(p->data>='A'&&p->data<='Z'){p->next=ha;elseif(p->data>='0'&&p->data<='9'){p->next=hb;hb=p;}else{p->next=hc;}}typedefstructnode{intdata;structnode*lchild,*rchild;}bitree;voidswapbitree(bitree*bt){bitree*p;if(bt==0)return;swapbitree(bt->lchild);swapbitree(bt->rchild);p=bt->lchild;bt->lchild=bt->rchild;bt->rchild=p;}#definentypedefstructnode{intkey;structnode*lchild,*rchild;}bitree;voidbstinsert(bitree*&bt,intkey){if(bt==0){bt=(bitree*)malloc(sizeof(bitree));bt->key=key;bt->lchild=bt->rchild=0;}elseif(bt->key>key)bstinsert(bt->lchild,key);elsebstinsert(bt->rchild,key);}voidcreatebsttree(bitree{int}數(shù)據(jù)結(jié)構(gòu)試卷（五）參考答ki<=k2i&&n-typedefstructnode{datatypedata;structnode*lchild,*rchild;}bitree;intjudgebitree(bitree*bt1,bitree*bt2){if(bt1==0&&bt2==0)elseif(bt1==0||bt2==0||bt1->data!=bt2->data)}voidmergelklist(lklist*ha,lklist*hb,lklist{lklist*s=hc=0;while(ha!=0&&hb!=0)if(ha->data<hb->data){if(s==0)hc=s=ha;else{s->next=ha;s=ha;};ha=ha->next;}else{if(s==0)hc=s=hb;else{s->next=hb;s=hb;};hb=hb->next;}if(ha==0)s->next=hb;elses-}數(shù)據(jù)結(jié)構(gòu)試卷（六）參考答 1．2．3．4．5．6．7．8．9．10．n-O(nlog2n)，structrecord{intkey;intothers;};intbisearch(structrecordr[],intk){intlow=0,mid,high=n-1;{if(r[mid].key==k)return(mid+1);elseif(r[mid].key>k)high=mid-1;else}}intminnum=-typedefstructnode{intkey;structnode*lchild,*rchild;}bitree;voidinorder(bitree*bt){ }{lklist intif(head==0||head->next==0){for(s=head;s!=q->next;s=s->next)if(s->data>p->data)break; }}數(shù)據(jù)結(jié)構(gòu)試卷（七）參考答1．2．3．4．5．6．7．8．9．10．2h-1，2h-5i<j&&{lklist*p,*q,*s; intmin,t;if(head==0||head->next==0)return;for(q=head;q!=0;q=q->next){min=q->data;for(p=q->next;p!=0;p=p->next)if(min>p->data){min=p->data;s=p;}if(s!=q){t=s->data;s->data=q->data;q->data=t;}}}voidsubstring(chars[],longstart,longcount,chart[{longif(start<1||start>length)printf("Thecopypositioniswrong");elseif(start+count-1>length)printf("Toocharacterstobecopied");else{for(i=start-1,j=0;i<start+count-1;i++,j++