數據結構試卷（一 數據結構試卷（二 數據結構試卷（三 數據結構試卷（四 數據結構試卷（五 數據結構試卷（六 數據結構試卷（七 數據結構試卷（八 數據結構試卷（九 數據結構試卷（十

數據結構試卷（一）參考答 數據結構試卷（二）參考答 數據結構試卷（三）參考答 數據結構試卷（四）參考答 數據結構試卷（五）參考答 數據結構試卷（六）參考答 數據結構試卷（七）參考答 數據結構試卷（八）參考答 數據結構試卷（九）參考答 數據結構試卷（十）參考答 數據結構試卷（一一、單選題（每220分 用方式的隊列，在進行插入運算時 A.僅修改頭指 B.頭、尾指針都要修C.僅修改尾指 以下數據結構中哪一個是非線性結構 A.隊 B. C.線性 D.二叉設有一個二維數組A[m][n]，假設A[0][0]存放位置在644(10)，A[2][2] 樹最適合用來表示 ) C.元間具有分支層次關系的數 D.元間無聯系的數 C.2K- D.2k-分查找，則查找A［3］的比較序列的下標依次為( A. B.C. D.對n個記錄的文件進行快速排序，所需要的輔助空間大致A. B. C. D.對于線性表（7，34，55，25，64，46，20，10）進行散列時，若選用=K%9作為散列函數，則散列地址為1的元素有 ）個 設有6個結點的無向圖，該圖至少應有 )條邊才能確保是通圖 二、填空題（每126分通常從四個方面評價算法的質量 A（C，D（E，F，G，H（I，J， 后綴算式923+-102/-的值為 。中綴算式（3+4X）-2Y/3對應的后綴算式 若用鏈表一棵二叉樹時，每個結點除數據域外，還有指向左孩子和右孩子的兩個指針。在這種結構中，n個結點的二叉樹共有 對于一個具有n個頂點和e條邊的有向圖和無向圖，在其對應的鄰接表中，所含邊結點 AOV網是一 的圖在一個具有n個頂點的無向完全圖中，包含有 素成為一個子表，則得到的四個子表分別為 向一棵B_樹插入元素的過程中，若最終引起樹根結點的，則新樹比原樹的高 在快速排序、堆排序、歸并排序中 排序是穩定的三、計算題（每624分在如下數組A中了一個線性表，表頭指針為A[0].next，試寫出該線性表3572041 3572041VE分別為：V={1,2,3,4,5,6,7};4,2,5,8,3四、閱讀算法（每7分14分LinkListmynote(LinkList{//L是不結點的單鏈表的頭指 while(p－>next)p=p－>next； } }S1S2voidABC(BTNode*{ BTABC(BT->right);}}五、算法填空（8分）boolFind(BTreeNode*BST,ElemType&{ifreturnfalse;else{if(item==BST- elseif(item<BST- elsereturnFind( }六、編寫算法（8分HLXintCountX(LNode*HL,ElemType數據結構試卷（二一、選擇題(24 線性表采用順序必須占用一片連續的空線性表采用鏈式不必占用一片連續的空線性表采用鏈式便于插入和刪除操作的實線性表采用順序便于插入和刪除操作的實設哈夫曼樹中的葉子結點總數為m，若用二叉鏈表作為結構，則該哈夫曼樹中總共有（）個空指針域。(A)2m- (B) (C) (D)Q[0：M-1]F和RF素的前一位置，尾指針R總是指向隊尾元素的當前位置，則該循環隊列中的元素個數（(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-設一組初始記錄關鍵字序列(5，2，6，3，8)5快速排序的結果為（(A) (B)(C) (D)二、填空題(24為了能有效地應用HASH查找技術，必須解決的兩個問題 typedefstruct{ints[100];inttop;}sqstack;voidpush(sqstack&stack,intx){if(stack.top==m-1)else }中序遍歷二叉排序樹所得到的序列 快速排序的時間復雜度 2的結點數為 ；若采用二叉鏈表作為該二叉樹的結構，則該二叉樹中共 設某無向圖中頂點數和邊數分別為n和e，所有頂點的度數之和為d，則 已知一有向圖的鄰接表結構如下：從頂點1出發，DFS遍歷的輸出序列，BFS三、應用題(364rlink62TB(CBE)CC設有無向圖四、算法設計題(16（K1K2KnOn)KiK。設有兩個集合A和集合B，要求設計生成集合C=A∩B的算法，其中集合A、B和C用鏈數據結構試卷（三一、選1共20 (A)線性結 (B)樹型結 (C)物理結 (D)圖型結下面程序的時間復雜為（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 n（2(A) (B)O(log (D)2Gne條邊，則其對應的鄰接表中的表頭結點和表結點的個數分別為（(A) (B) (C) (D)n個頂點，則該強連通圖中至少有（）(A)n(n- (B) (C) (D)500010鍵字，則用下列(A(B)堆排 (C)歸并排(D)）(A(B)冒泡排 (C)堆排(D)二、填120數據的物理結構主要包 設一棵完全二叉樹中有500個結點，則該二叉樹的深度為 等于頂點i的 ，第i列上所有元和等于頂點i的 個度數為1的結點Gneded 設查找表中有100個元素，如果用二分法查找方法查找數據元素X 不論是順序結構的棧還是鏈式結構的棧其入棧和出棧操作的時間復雜度均 structrecord{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; }三、計10共30（36，15，40，63，22選用的散列函數是H（K）=Kmod7，若發生采用線性探查法處理，試： 四、算法設1530數據結構試卷（四一、選120設一維數組中有n個數組元素，則第i個數組元素的平均時間復雜度為（2(A) (B)O(nlog (C) (D)2k，則該二叉樹中最多有（）(A)2k- (B) (C)2k- (D)2k-ne（(A) (B) (C) (D) 2(A) (B) (C)O(log (D)2nm（）(A) (B)n- (C) (D)m-(A) (B) (C) (D)設用鏈表作為棧的結構則退棧操作（(A)必須判別棧是否為 (B)必須判別棧是否為(C)判別棧元素的類 (D)對棧不作任何判下列四種排序中（）(A)快速排 (B)冒泡排 (C)希爾排 (D)設某二樹中度數為0的結點為N0度為1的結數為Nl數為2的點數為N2，則下列等式成立的是（ 。(A) (B) (C) (D) (A) (B)log2n- (C) (D)二、填120設有n個無序的記錄關鍵字，則直接插入排序的時間復雜度為 設指針變量p指向雙向循環鏈表中的結點X，則刪除結點X llinkrlink。 設哈夫曼樹中共有99個結點，則該樹中有 設有一個順序循環隊列中有M

設順序線性表中有n個數據元素，則第i 個元素設一組初始記錄關鍵字序列為(20，18，22，16，30，19)，則以20為中軸的一趟快速 設某無向圖G中有n個頂點，用鄰接矩陣A作為該圖的結構，則頂點i和頂點互為鄰接點的條件 設無向圖對應的鄰接矩陣為A，則A中第i上非0元素的個 第i列上非元素的個數（填等于，大于或小于設前序遍歷某二叉樹的序列為ABCD，中序遍歷該二叉樹的序列為BADC，則后序遍歷 hashtalbek的結點，成功時返回指向關鍵0。typedefstructnode{intkey;structnode*next;}lklist;voidcreakhash(lklist*hashtable[]){int lklist {s=(lklist*)malloc(sizeof(lklist));s-k=a[i]%p;s- }}三、計10共301、畫出廣義表LS=((),(e),(a,(b,c,d)))的頭尾鏈表結構ABCABC 30..9H（key）（key2+2）MOD9,并采用鏈表處理，請畫出元素、、、、、、、依次插入散列表的結構。四、算法設1030設計在鏈式結構上交換二叉樹中所有結點左右子樹的算法在鏈式結構上建立一棵二叉排序樹數據結構試卷（五一、選擇題(20分)1．數據的最小單位是（(A)數據 (B)數據類 (C)數據元 (D)數據變趟希爾排序結束后前4條記錄關鍵字為（ (B)(C) (D)個長度為2的有序子表，則用歸并排序的方法對該記錄關鍵字序列進行一趟歸并后的結 substr(“DATASTRUCTURE”，5，9)的返回值為（ (B)(C) (D)n，則該操作的時間復雜度為（2(A)O(log (B) (C) (D)2NmN0=（。 (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)10設一組初始記錄關鍵字序列為(45，80，55，40，42，85)，則以第一個記錄關鍵字為基準而得到一趟快速排序的結果是（(A) (B)(C) (D)二、填20指針top2的初值為n，則判斷共享棧滿的條件是 在圖的鄰接表中用順序結構表頭結點的優點 設有一個n階的下三角矩陣A，如果按照行的順序將下三角矩陣中的元素（包括對角線上元素）存放在n(n+1)個連續的單元中，則A[i][j]與A[0][0]之間有 設一棵完全二叉樹的順序結構中數據元素為ABCDEF，則該二叉樹的前序遍歷 設一棵完全二叉樹有128個結點，則該完全二叉樹的深度為 設有向圖G的結構用鄰接矩陣A來表示則A中第i行中所有非零元素個數之和等于頂點i的 ，第i列中所有非零元素個數之和等于頂點i的 設一組初始記錄關鍵字序列(k1，k2，……，kn)是堆，則對i=1，2，…，n/2而言滿足 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}}三、應用題(32四、算法設計題(28數據結構試卷（六一、選擇題(30之和為（(A) (B) (C) (D)執行一趟快速排序能夠得到的序列是（[41，12，34，45，27]55[45，34，12，41]55[63，12，34，45，27]55[12，27，45，41]55設一條單鏈表的頭指針變量為head且該鏈表沒有頭結點，則其判空條件是 (B)head-(C)head->next==head (D)head!=04．O(nlog2n)的是（(A)堆排 (B)冒泡排 (C)希爾排 (D)快速排設二叉樹的先序遍歷序列和后序遍歷序列正好相反，則該二叉樹滿足的條件是（ (B)高度等于其結點(C)任一結點無左孩 (D)任一結點無右孩一趟排序結束后不一定能夠選出一個元素放在其最終位置上的是（(A)堆排 (B)冒泡排 (C)快速排 (D)希爾排 (A) (B) (C) (D)順序查找不論在順序線性表中還是在鏈式線性表中的時間復雜度為（2(A) (B) (C) (D)O(1og2 (A) (B) (C)O(nlog (D)O(1og 深度為k（）(A)2k-1- (B)2k- (C)2k- (D)2k-sX，則入隊列的操作序列為（ (B)s-(C)rear- (D)s-ne（(A) (B) (C) (D)199（）(A) (B) (C) (D)n（ (A) (B) (C)O(nlog (D)O(1og 設用鄰接矩陣A表示有向圖G的結構，則有向圖G中頂點i的入度為（第i行非0元素的個數之 (B)第i列非0元素的個數之(C)第i行0元素的個數之和 (D)第i列0元素的個數之和二、判斷題(20分)調用一次深度優先遍歷可以到圖中的所有頂點（（（（（（設一棵樹TBTBT（線性表的順序結構比鏈式結構更好（（（三、填空題(30for(i=1，t=1，s=0；i<=n；i++){t=t*i；s=s+t；}的時間復雜度 設指針變量p指向單鏈表中結點A，指針變量s指向入的新結點X，則進行插入操 （設結點的指針域為next設有向圖GG（DRD={12345}R={r}r={<1,2>， 設無向圖G中有n個頂點，則該無向圖中每個頂點的度數最多 5030 設F和R ，的情況下 散列表中解決的兩種方法 四、算法設計題(20３．在鏈式結構上設計直接插入排序算法數據結構試卷（七一、選擇題(30n（）(A) (B) (C) (D)n(n-設無向圖Gn（）(A) (B)n- (C) (D)2n-而得到的一趟快速排序結果是（(A) (B)(C) (D)4（(A)先序遍 (B)中序遍 (C)后序遍 (D)層次遍點的左孩子結點的編號為（(A) (B) (C) (D)2i-程序段s=i=0；do{i=i+1；s=s+i；}while(i<=n)；的時間復雜度為 2(A) (B)O(nlog (C) (D)2 (B)head-(C)head- (D)10，則該二叉樹上葉子結點最多有（(A) (B) (C) (D)用二分法查找關鍵字90需要比較的關鍵字個數為（ (A) (B) (C) (D)top（ (B)top=top-(C)top- (D)top=top-二、判斷題(20不論是入隊列操作還是入棧操作，在順序結構上都需要考慮“溢出”情況（（ （1（對連通圖進行深度優先遍歷可以到該圖中的所有頂點（（（（（）三、填空題(30設指針變量p指向雙向鏈表中的結點A，指針變量s指向入的結點X，則在結點A的后面插入結點X的操作序列為=p；s->right=p->right； >left=s（right設完全有向圖中有n個頂點，則該完全有向圖中共有 中有n個頂點，則該完全無向圖中共有 解決散列表的兩種方法 3的結點數 個 設一棵二叉樹的前序序列為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-} }四、算法設計題(20設計在順序結構上實現求子串算法數據結構試卷（八一、選擇題(30字符串的長度是指 (B)串中不同字母的個(C)串中所含字符的個 (D)串中不同數字的個n（2(A) (B) (C) (D)O(log2兩個字符串相等的充要條件是（ (B)兩個字符串中對應位置上的字符相(C)同時具備(A)和(B)兩個條 (D)以上答案都不100H(k)=kPP（(A) (B) (C) (D)在二叉排序樹中插入一個關鍵字值的平均時間復雜度為（ (A) (B)O(1og (C)O(nlog (D) (B)(C) (D)A[7]，A[5]65（(A) (B) (C) (D)21，22，23則該三叉鏈權中有（）0(A) (B) (C) (D)a（(A) (B) (C) (D)隊列是一種（）(A)先進先 (B)先進后 (C)只能插 (D)只能刪二、判斷題(20（ （）二維數組和數組均不是特殊的線性結構（（ii（（不論線性表采用順序結構還是鏈式結構刪除值為X的結點的時間復雜度均O(n) 稀疏矩陣的壓縮可以用一個三元組表來表示稀疏矩陣中的非0元素（三、填空題(30 typedefstructnode{intdata;structnode*lchild;structnode bstinsert(bitree*&t,intk){if(t==0){ elseif(t->data>k)bstinsert(t->lchild,k);else }設指針變量p指向單鏈表中結點A，指針變量s指向入的結點X，則在結點A的 ;則指針變量p和指針變量head之間的關系是p= 和head= 中的兩個指針域分別為llink和rlink設某棵二叉樹的中序遍歷序列為ABCD，后序遍歷序列為BADC 條邊堆只需把16與 四、算法設計題(20設計一個在鏈式結構上統計二叉樹中結點個數的算法數據結構試卷（九一、選擇題(30下列程序段的時間復雜度為（for(i=0；i<m；i++)for(j=0；j<t；j++)for(i=0；i<m；i++)for(j=0；j<t；j++)for(k=0；k<n；k++)(A) (B) (C) (D)ni（）(A)n- (B)n+l- (C)n-1- (D)設F是由T1、T2和T3三棵樹組成的森林，與F對應的二叉樹為B，T1、T2和T3的結點數分別為N1、N2和N3，則二叉樹B的根結點的左子樹的結點數為（ (A)N1- (B)N2- (C) (D)利用直接插入排序法的思想建立一個有序線性表的時間復雜度為（(A) (B) (C) (D)設指針變量p指向雙向鏈表中結點A，指針變量s指向入的結點X，則在結點A的X（p->right=s；s->left=p；p->right->left=s；s->right=p-s->left=p；s->right=p->right；p->right=s；p->right-p->right=s；p->right->left=s；s->left=p；s->right=p-s->left=p；s->right=p->right；p->right->left=s；p- (A)快速排 (B)堆排 (C)歸并排 (D)冒泡排i（(A)n- (B)n-1- (C)n+l- (D)設散列表中有m個單元，散列函數H(key)=key%p，則p最好選擇 (B)小于等于m的最大素(C)小于等于m的最大偶 (D)小于等于m的最大合120（）(A) (B) (C) (D) ）條邊(A)n(n- (B)n(n- (C) (D)(n-n，則順序查找的平均比較次數為（(A) (B) (C) (D)(n-的元素需要經過（）(A) (B) (C) (D)找長度為（(A) (B) (C) (D)設有向無環圖G中的有向邊集合E={<1，2>，<2，3>，<3，4>，<1，4>}，則下列屬于該有向圖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-

排序，如果從節省空間的角度來考慮則最好選 排序 三、判斷題(20有向圖的鄰接表和逆鄰接表中表結點的個數不一定相等。 對鏈表進行插入和刪除操作時不必移動鏈表中結點。 子串“ABC”在主串“AABCABCD”2。( 中序遍歷一棵二叉排序樹可以得到一個有序的序列。 入棧操作和入隊列操作在鏈式結構上實現時不需要考慮棧溢出的情況。 順序表查找指的是在順序結構上進行查找（（五、算法設計題(20數據結構試卷（十一、選擇題(24下列程序段的時間復雜度為（i=0，s=0；while(s<n)(A)O(n1/2)(B)O(n1/3)(C)O(n)(D)設某鏈表中最常用的操作是在鏈表的尾部插入或刪除元素，則選用下列（）方式 (B)單向循環鏈(C)雙向鏈 (D)雙向循環鏈設指針q指向單鏈表中結點Ap指向單鏈表中結點A的后繼B，指針s指向被XA和結點BX（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)設有一個10階的下三角矩陣A（包括對角線，按照從上到下、從左到右的順序到連續的55個單元中每個數組元素占1個字節的空間則A[5][4]地址與A[0][0]的地址之差為（(A) (B) (C)28(D)m設一棵m叉樹中有N1個度數為1的結點，N2個度數為2結點，……，Nm個度m結點，則該樹中共有（）個葉子結點。mmm(i

mm(B)Ni

mm(C)Ni

1(i1)Ni ）根結點的值(A) (B) (C) (D)夫曼樹，則這棵哈夫曼樹的帶權路徑長度為（(A) (B) (C) (D)表中需要做（）(A) (B) (C) (D)n(n-020n，則這棵二叉中共有（）個結點。(A) (B) (C)2n- (D)8，則最多經過（）(A) (B) (C) (D) 二、填空題(48分，其中最后兩小題各6設需要對5個不同的記錄關鍵字進行排序，則至少需要比較 次設在長度為20的有序表中進行二分查找，則比較一次查找成功的結點數有 設一棵m叉樹脂的結點數為n，用多重鏈表表示其結構，則該樹中有 數據結構從邏輯上劃分為三種基本類型 設無向圖G中有n個頂點e條邊則用鄰接矩陣作為圖的結構進行深度優先或廣度 ；用鄰接表作為圖的結構進行深度優先或廣 設散列表的長度為8，散列函數H(k)=k%7，用線性探測法解決，則根據一組初始 設一組初始關鍵字序列為(38，65，97，76，13，27，10)，則第3趟冒泡排序結束后的 設一組初始關鍵字序列為(38，65，97，76，13，27，10)，則第3趟簡單選擇排序后的 G typedefstructnode{intdata;structnode voidcreatebitree(bitree*&bt){if(ch=='#') {bt=(bitree*)malloc(sizeof(bitree));bt->data=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; }}三、算法設計題(22設計在鏈式結構上合并排序的算法設關鍵字序列(k1，k2，…，kn-1)是堆，設計算法將關鍵字序列(k1，k2，…，kn-1，x)調整為堆。數據結構試卷（一）參考一、選擇題（220分1.A 二、填空題（126分正確 高效 - 34X*+2Y*3/ 12三、計算題（624分（78，50，40，60，34，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數據結構試卷（二）參考一、選擇 二、填空構造一個好的HASH函數，確定解決的方22N0-三、應用q->llink=p;q->rlink=p->rlink;p->rlink->llink=q;p-樹的鏈式結構略，二叉樹略四、算法設 設有一組初始記錄關鍵字序列（K1K2，…，KOn)ii。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-}}ABC=A∩BA、BCtypedefstructnode{intdata;structnode*next;}lklist;voidintersection(lklist*ha,lklist*hb,lklist*&hc){lklist*p,*q,*t; for(q=hb;q!=0;q=q->next)if(q->data==p->data)if(q!=0){t=(lklist*)malloc(sizeof(lklist));t->data=p->data;t->next=hc;}}數據結構試卷（三）參考一、選擇第3小題分析：首先用指針變量q指向結點A的后繼結點B，然后將結點B的值到AB。第9小題分析：9快速排序、歸并排序和插入排序必須等到整個排序結束后才能夠求出最小的10個數，而堆排序只需要在初始堆的基礎上再進行10次篩選即可，每次篩選的時間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;{for(q=p->next,s=q;q!=0;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}數據結構試卷（四）參考一、選擇 二、填空p>llink->rlink=p->rlink;p->rlink->llink=p-32k-三、計算1^-1^-

-- ^^1b0---1^1----b0---1^1----a01^1e01---1----0c1^dd0 BDEFCA；(2) BDEFCAIJKHGAABGCHDIEJ 4^4^3869^^27^^^^5123456789四、算法設typedefchartypedefstructnode{datatypedata;structnode*next;}lklist;voidsplit(lklist*head,lklist*&ha,lklist*&hb,lklist*&hc){lklist*p;ha=0,hb=0,hc=0;{head=p->next;p-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{intfor(i=1;i<=n;i++)}數據結構試卷（五）參考一、選擇二、填空可以隨機到任一個頂點的簡單鏈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)elsereturn(judgebitree(bt1->lchild,bt2->lchild)*judgebitree(bt1->rchild,bt2-}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-}數據結構試卷（六）參考一、選擇 二、判斷1．2．3．4．5．6．7．8．9．10．三、填空s->next=p->next;p-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){ }在鏈式結構上設計直接插入排序算voidstraightinsertsort(lklist{lklist intif(head==0||head->next==0)elsefor(q=head,p=head->next;p!=0;p=q-{for(s=head;s!=q->next;s=s->next)if(s->data>p->data)break; }}數據結構試卷（七）參考一、選擇二、判斷1．2．3．4．5．6．7．8．9．10．三、填空5i<j&&四、算法設voidsimpleselectsorlklist(lklist{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++)t[j]=s[i];t[j]=}inttypedefstructnode{intkey;structnode*lchild,*rchild;}bitree;voidlevel(bitree*bt,intx){if }數據結構試卷（八）參考一、選擇二、判