大工16春《數據結構》開卷考試復習資料大工16春《數據結構》開卷考試復習資料大工16春《數據結構》開卷考試復習資料V:1.0精細整理，僅供參考大工16春《數據結構》開卷考試復習資料日期：20xx年X月機密★啟用前大連理工大學網絡教育學院2016年9月《數據結構》課程期末復習資料注意事項：本復習題滿分共：400分。一、單項選擇題（本大題共65小題，每小題3分，共195分）1．對于一個算法，當輸入非法數據時，也要能作出相應的處理，這種要求稱為（）。(A).正確性(B).可行性(C).健壯性(D).輸入性2．設S為C語言的語句,計算機執行下面算法時，算法的時間復雜度為（）。for(i=n-1；i>=0；i--)for(j=0；j<i；j++)S；(A).n2(B).O(nlgn)(C).O(n)(D).O(n2)3．折半查找法適用于（）。（A）、有序順序表（B）、有序單鏈表（C）、有序順序表和有序單鏈表都可以（D）、無限制4．順序存儲結構的優勢是（）。（A）、利于插入操作（B）、利于刪除操作（C）、利于順序訪問（D）、利于隨機訪問5．深度為k的完全二叉樹，其葉子結點必在第（）層上。（A）、k-1（B）、k（C）、k-1和k（D）、1至k6．具有60個結點的二叉樹，其葉子結點有12個，則度為1的結點數為（）（A）、11（B）、13（C）、48（D）、377.下列程序段的時間復雜度為（）。for(i=0；i<m；i++)for(j=0；j<t；j++)c[i][j]=0；for(i=0；i<m；i++)for(j=0；j<t；j++)for(k=0；k<n；k++)c[i][j]=c[i][j]+a[i][k]*b[k][j]； (A)O(m*n*t) (B)O(m+n+t) (C)O(m+n*t) (D)O(m*t+n)8．設順序線性表中有n個數據元素，則刪除表中第i個元素需要移動（）個元素。 (A)n-i (B)n+1-i (C)n-1-i (D)i9．設F是由T1、T2和T3三棵樹組成的森林，與F對應的二叉樹為B，T1、T2和T3的結點數分別為N1、N2和N3，則二叉樹B的根結點的左子樹的結點數為（）。 (A)N1-1 (B)N2-1 (C)N2+N3 (D)N1+N310．利用直接插入排序法的思想建立一個有序線性表的時間復雜度為（）。(A)O(n) (B)O(nlog2n) (C)O(n2) (D)O(1og2n)11．設指針變量p指向雙向鏈表中結點A，指針變量s指向被插入的結點X，則在結點A的后面插入結點X的操作序列為（）。 (A)p->right=s；s->left=p；p->right->left=s；s->right=p->right；(B)s->left=p；s->right=p->right；p->right=s；p->right->left=s； (C)p->right=s；p->right->left=s；s->left=p；s->right=p->right； (D)s->left=p；s->right=p->right；p->right->left=s；p->right=s；12．圖的Depth-FirstSearch(DFS)遍歷思想實際上是二叉樹（）遍歷方法的推廣。（A）、先序（B）、中序（C）、后序（D）、層序在上圖列鏈隊列Q中，元素a出隊的操作序列為（）（A）、p=Q.front->next;p->next=Q.front->next;（B）、p=Q.front->next;Q.front->next=p->next;（C）、p=Q.rear->next;p->next=Q.rear->next;（D）、p=Q->next;Q->next=p->next;14．Huffman樹的帶權路徑長度WPL等于（）（A）、除根結點之外的所有結點權值之和（B）、所有結點權值之和（C）、各葉子結點的帶權路徑長度之和（D）、根結點的值15．線索二叉鏈表是利用（）域存儲后繼結點的地址。（A）、lchild（B）、data（C）、rchild（D）、root16．組成數據的基本單位是（）。(A)數據項 (B)數據類型 (C)數據元素 (D)數據變量17．設數據結構A=(D，R)，其中D={1，2，3，4}，R={r}，r={<1，2>，<2，3>，<3，4>，<4，1>}，則數據結構A是（）。(A)線性結構 (B)樹型結構 (C)圖型結構(D)集合18．數組的邏輯結構不同于下列（）的邏輯結構。(A)線性表 (B)棧 (C)隊列 (D)樹19．二叉樹中第i(i≥1)層上的結點數最多有（）個。A．2i B．2i+1C．2i-1 D．2i+220.

對一個算法的評價，不包括如下（）方面的內容。A．健壯性和可讀性B．并行性C．正確性D．時空復雜度21.

在帶有頭結點的單鏈表HL中，要向表頭插入一個由指針p指向的結點，則執行()。A.p->next=HL->next;HL->next=p;B.p->next=HL;HL=p;C.p->next=HL;p=HL;D.HL=p;p->next=HL;22.

對線性表，在下列哪種情況下應當采用鏈表表示？()A.經常需要隨機地存取元素B.經常需要進行插入和刪除操作C.表中元素需要占據一片連續的存儲空間D.表中元素的個數不變23.一個棧的輸入序列為123，則下列序列中不可能是棧的輸出序列的是()A.231 B.321C.312 D.12324．下列各種排序算法中平均時間復雜度為O(n2)是（）。(A)快速排序 (B)堆排序 (C)歸并排序 (D)冒泡排序25．設輸入序列1、2、3、…、n經過棧作用后，輸出序列中的第一個元素是n，則輸出序列中的第i個輸出元素是（）。(A)n-i (B)n-1-i (C)n+l-i (D)不能確定26．設散列表中有m個存儲單元，散列函數H(key)=key%p，則p最好選擇（）。(A)小于等于m的最大奇數 (B)小于等于m的最大素數(C)小于等于m的最大偶數 (D)小于等于m的最大合數27．設在一棵度數為3的樹中，度數為3的結點數有2個，度數為2的結點數有1個，度數為1的結點數有2個，那么度數為0的結點數有（）個。(A)4 (B)5 (C)6 (D)728．設完全無向圖中有n個頂點，則該完全無向圖中有（）條邊。(A)n(n-1)/2 (B)n(n-1) (C)n(n+1)/2 (D)(n-1)/229．

AOV網是一種（）。A．有向圖B．無向圖C．無向無環圖D．有向無環圖30．采用開放定址法處理散列表的沖突時，其平均查找長度（）。A．低于鏈接法處理沖突B.高于鏈接法處理沖突C．與鏈接法處理沖突相同D．高于二分查找31．若需要利用形參直接訪問實參時，應將形參變量說明為（）參數。A．值B．函數C．指針D．引用32．在稀疏矩陣的帶行指針向量的鏈接存儲中，每個單鏈表中的結點都具有相同的（）。A．行號B．列號C．元素值D．非零元素個數33．快速排序在最壞情況下的時間復雜度為（）。A．O(log2n)B．O(nlog2n)C．0(n)D．0(n2)34．從二叉搜索樹中查找一個元素時，其時間復雜度大致為()。A.O(n)B.O(1)C.O(log2n)D.O(n2)35．設指針變量p指向單鏈表結點A，則刪除結點A的后繼結點B需要的操作為（）。(A)p->next=p->next->next (B)p=p->next (C)p=p->next->next (D)p->next=p36．設棧S和隊列Q的初始狀態為空，元素E1、E2、E3、E4、E5和E6依次通過棧S，一個元素出棧后即進入隊列Q，若6個元素出列的順序為E2、E4、E3、E6、E5和E1，則棧S的容量至少應該是（）。(A)6 (B)4 (C)3 (D)237．將10階對稱矩陣壓縮存儲到一維數組A中，則數組A的長度最少為（）。(A)100 (B)40 (C)55 (D)8038．設結點A有3個兄弟結點且結點B為結點A的雙親結點，則結點B的度數數為（）。(A)3 (B)4 (C)5 (D)139．根據二叉樹的定義，可知具有3個結點的二叉樹共有（）種不同的形態。(A)4 (B)5 (C)6 (D)740.設有以下四種排序方法，則（）的空間復雜度最大。(A)冒泡排序 (B)快速排序 (C)堆排序 (D)希爾排序41．設某無向圖有n個頂點，則該無向圖的鄰接表中有（）個頂點頭結點。(A)2n (B)n (C)n/2 (D)n(n-1)42．設無向圖G中有n個頂點，則該無向圖的最小生成樹上有（）條邊。(A)n (B)n-1 (C)2n (D)2n-143．設一組初始記錄關鍵字序列為(60，80，55，40，42，85)，則以第一個關鍵字60為基準而得到的一趟快速排序結果是（）。(A)40，42，60，55，80，85 (B)42，45，55，60，85，80(C)42，40，55，60，80，85 (D)42，40，60，85，55，8044．（）二叉排序樹可以得到一個從小到大的有序序列。(A)先序遍歷 (B)中序遍歷 (C)后序遍歷 (D)層次遍歷45．設按照從上到下、從左到右的順序從1開始對完全二叉樹進行順序編號，則編號為i結點的左孩子結點的編號為（）。(A)2i+1 (B)2i (C)i/2 (D)2i-146．程序段s=i=0；do{i=i+1；s=s+i；}while(i<=n)；的時間復雜度為（）。(A)O(n) (B)O(nlog2n) (C)O(n2) (D)O(n3/2)47．設帶有頭結點的單向循環鏈表的頭指針變量為head，則其判空條件是（）。(A)head==0 (B)head->next==0(C)head->next==head (D)head!=048．設某棵二叉樹的高度為10，則該二叉樹上葉子結點最多有（）。(A)20 (B)256 (C)512 (D)102449．設一組初始記錄關鍵字序列為(13，18，24，35，47，50，62，83，90，115，134),則利用二分法查找關鍵字90需要比較的關鍵字個數為（）。(A)1 (B)2 (C)3 (D)450．設指針變量top指向當前鏈式棧的棧頂，則刪除棧頂元素的操作序列為（）。(A)top=top+1; (B)top=top-1;(C)top->next=top; (D)top=top->next;51．棧和隊列的共同特點是()。A.只允許在端點處插入和刪除元素B.都是先進后出C.都是先進先出D.沒有共同點52．用鏈接方式存儲的隊列，在進行插入運算時().A.僅修改頭指針B.頭、尾指針都要修改C.僅修改尾指針D.頭、尾指針可能都要修改53．以下數據結構中哪一個是非線性結構？()A.隊列B.棧C.線性表D.二叉樹54．設有一個二維數組A[m][n]，假設A[0][0]存放位置在644(10)，A[2][2]存放位置在676(10)，每個元素占一個空間，問A[3][3]存放在什么位置？腳注(10)表示用10進制表示。A．688B．678C．692D．69655．樹最適合用來表示()。A.有序數據元素B.無序數據元素C.元素之間具有分支層次關系的數據D.元素之間無聯系的數據56．設順序表的長度為n，則順序查找的平均比較次數為（）。(A)n (B)n/2 (C)(n+1)/2 (D)(n-1)/257．設有序表中的元素為(13，18，24，35，47，50，62)，則在其中利用二分法查找值為24的元素需要經過（）次比較。(A)1 (B)2 (C)3 (D)458．設順序線性表的長度為30，分成5塊，每塊6個元素，如果采用分塊查找，則其平均查找長度為（）。 (A)6 (B)11 (C)5 (D)6.559．設有向無環圖G中的有向邊集合E={<1，2>，<2，3>，<3，4>，<1，4>}，則下列屬于該有向圖G的一種拓撲排序序列的是（）。 (A)1，2，3，4 (B)2，3，4，1 (C)1，4，2，3 (D)1，2，4，360．設有一組初始記錄關鍵字序列為(34，76，45，18，26，54，92)，則由這組記錄關鍵字生成的二叉排序樹的深度為（）。 (A)4 (B)5 (C)6 (D)761

．二叉樹的第k層的結點數最多為().A．2kB.2k-2C.2k+1D.2k-162

．若有18個元素的有序表存放在一維數組A[19]中，第一個元素放A[1]中，現進行二分查找，則查找A［3］的比較序列的下標依次為()A.1，2，3 B.9，5，2，3C.9，5，3 D.9，4，2，363．對n個記錄的文件進行快速排序，所需要的輔助存儲空間大致為A.O（1）B.O（n）C.O（1og2n）D.O（n2）64

．對于線性表（7，34，55，25，64，46，20，10）進行散列存儲時，若選用H（K）=K%9作為散列函數，則散列地址為1的元素有（）個，A．1B．2C．3D．465．設有6個結點的無向圖，該圖至少應有()條邊才能確保是一個連通圖。A.5B.6C.7D.8

二、填空題（本大題共40小題，每小題2分，共80分）1.

設指針變量p指向雙向鏈表中的結點A，指針變量s指向被插入的結點X，則在結點A的后面插入結點X的操作序列為_________=p；s->right=p->right；p->right->left=s；__________=s；（設結點中的兩個指針域分別為left和right）。2.

設完全有向圖中有n個頂點，則該完全有向圖中共有________條有向條；設完全無向圖中有n個頂點，則該完全無向圖中共有________條無向邊。3.

當用長度為N的數組順序存儲一個棧時，假定用top==N表示棧空，則表示棧滿的條件是_____________________。4.

對于一個長度為n的單鏈存儲的線性表，在表頭插入元素的時間復雜度為_________，在表尾插入元素的時間復雜度為____________。5.

設W為一個二維數組，其每個數據元素占用4個字節，行下標i從0到7，列下標j從0到3，則二維數組W的數據元素共占用＿_____＿個字節。W中第6行的元素和第4列的元素共占用＿_______＿個字節。若按行順序存放二維數組W，其起始地址為100，則二維數組元素W[6][3]的起始地址為＿________＿。6.

廣義表A=(a,(a,b),((a,b),c)),則它的深度為____________，它的長度為____________。7.

二叉樹是指度為2的____________________樹。一棵結點數為N的二叉樹，其所有結點的度的總和是_____________。8.

設有一組初始關鍵字序列為(24，35，12，27，18，26)，按照從小到大排序，則第3趟直接插入排序結束后的結果的是__________________________________。9.

設一棵二叉樹的前序序列為ABC，則有______________種不同的二叉樹可以得到這種序列。10.

下面程序段的功能是實現一趟快速排序，請在下劃線處填上正確的語句。structrecord{intkey;datatypeothers;};voidquickpass(structrecordr[],ints,intt,int&i){intj=t;structrecordx=r[s];i=s;while(i<j){while(i<j&&r[j].key>x.key)j=j-1;if(i<j){r[i]=r[j];i=i+1;}while(____________________)i=i+1;if(i<j){r[j]=r[i];j=j-1;}}_________________;}11．

設指針p指向單鏈表中結點A，指針s指向被插入的結點X，則在結點A的前面插入結點X時的操作序列為：1)s->next=___________；2)p->next=s；3)t=p->data；4)p->data=___________；5)s->data=t；12．設某棵完全二叉樹中有100個結點，則該二叉樹中有______________個葉子結點。13．設某順序循環隊列中有m個元素，且規定隊頭指針F指向隊頭元素的前一個位置，隊尾指針R指向隊尾元素的當前位置，則該循環隊列中最多存儲_______隊列元素。14.已知一雙向鏈表如下(指針域名為next和prior)：現將p所指的結點插入到x和y結點之間，其中已知q指針指向x節點，其操作步驟為：_________；_________；_________；_________。15．n個結點無向完全圖的的邊數為_________，n個結點的生成樹的邊數為_________。16．已知一有向無環圖如下：任意寫出二種拓撲排序序列：_________、_________。17.已知二叉樹的中序遍歷序列為BCA，后序遍歷序列為CBA，則該二叉樹的先序遍歷序列為_________，層序遍歷序列為_________。18．設用于通信的電文僅由8個字母組成，字母在電文中出現的頻率分別為7、19、2、6、32、3、21、10，根據這些頻率作為權值構造哈夫曼樹，則這棵哈夫曼樹的高度為________________。19．設一組記錄關鍵字序列為(80，70，33，65，24，56，48)，則用篩選法建成的初始堆為（小根堆）_______________________。20．設無向圖G（如右圖所示），則其最小生成樹上所有邊的權值之和為_________________。21.邏輯結構決定了算法的_________，而存儲結構決定了算法的_________。22.棧和隊列都是一種_________的線性表，棧的插入和刪除只能在_________進行。23.線性表（a1,a2,…,an）的順序存儲結構中，設每個單元的長度為L，元素a1的存儲地址為addr，元素ai的存儲地址LOC(ai)為_________.24.隊列的插入操作是在隊列的_________進行，刪除操作是在隊列的__________進行。25．設二叉樹中度數為0的結點數為50，度數為1的結點數為30，則該二叉樹中總共有_______個結點數。26．設F和R分別表示順序循環隊列的頭指針和尾指針，采用犧牲一個單元來區分隊空和隊滿的方式下，則判斷該循環隊列為空的條件為_____________________。27．設二叉樹中結點的兩個指針域分別為lchild和rchild，則判斷指針變量p所指向的結點為葉子結點的條件是_____________________________________________。28．簡單選擇排序和直接插入排序算法的平均時間復雜度為___________。29．快速排序算法的空間復雜度平均情況下為__________，最壞的情況下為__________。30.散列表中解決沖突的兩種方法是_____________和_____________。31.

數據結構是指數據及其相互之間的______________。當結點之間存在M對N（M：N）的聯系時，稱這種結構為_____________________。32.

對一棵二叉搜索樹進行中序遍歷時，得到的結點序列是一個______________。對一棵由算術表達式組成的二叉語法樹進行后序遍歷得到的結點序列是該算術表達式的__________________。33.

對于一棵具有n個結點的二叉樹，用二叉鏈表存儲時，其指針總數為_____________個，其中_______________個用于指向孩子，_________________個指針是空閑的。34.

若對一棵完全二叉樹從0開始進行結點的編號，并按此編號把它順序存儲到一維數組A中，即編號為0的結點存儲到A[0]中。其余類推，則A[i]元素的左孩子元素為________,右孩子元素為_______________，雙親元素為____________。35.

在線性表的散列存儲中，處理沖突的常用方法有________________________和_____________________________兩種。36.

當待排序的記錄數較大，排序碼較隨機且對穩定性不作要求時，宜采用_______________排序；當待排序的記錄數較大，存儲空間允許且要求排序是穩定時，宜采用________________________排序。37.

__________遍歷二叉排序樹中的結點可以得到一個遞增的關鍵字序列（填先序、中序或后序）。38.

設查找表中有100個元素，如果用二分法查找方法查找數據元素X，則最多需要比較________次就可以斷定數據元素X是否在查找表中。39.

不論是順序存儲結構的棧還是鏈式存儲結構的棧，其入棧和出棧操作的時間復雜度均為____________。40.

設有n個結點的完全二叉樹，如果按照從自上到下、從左到右從1開始順序編號，則第i個結點的雙親結點編號為____________，右孩子結點的編號為___________。算法題（本大題共13小題，除第8題5分，其他每小題10分，共125分）1.設計在順序有序表中實現二分查找的算法。2.設計判斷二叉樹是否為二叉排序樹的算法。3.在鏈式存儲結構上設計直接插入排序算法4.設計在鏈式結構上實現簡單選擇排序算法。5.設計在順序存儲結構上實現求子串算法。6.編寫算法，將一個結點類型為Lnode的單鏈表按逆序鏈接，即若原單鏈表中存儲元素的次序為a1，……an-1，an，則逆序鏈接后變為,an，an-1，……a1。voidcontrary(Lnode*&HL){}7.

設有一組初始記錄關鍵字序列（K1，K2，…，Kn），要求設計一個算法能夠在O(n)的時間復雜度內將線性表劃分成兩部分，其中左半部分的每個關鍵字均小于Ki，右半部分的每個關鍵字均大于等于Ki。8.設有兩個集合A和集合B，要求設計生成集合C=A∩B的算法，其中集合A、B和C用鏈式存儲結構表示。9．設計計算二叉樹中所有結點值之和的算法。10.設單鏈表中有僅三類字符的數據元素(大寫字母、數字和其它字符)，要求利用原單鏈表中結點空間設計出三個單鏈表的算法，使每個單鏈表只包含同類字符。11.設計在鏈式存儲結構上交換二叉樹中所有結點左右子樹的算法。12.在鏈式存儲結構上建立一棵二叉排序樹。13.設計一個在鏈式存儲結構上統計二叉樹中結點個數的算法。答案：一、單項選擇題（本大題共65小題，每小題3分，共195分）C 2、D 3、A 4、D 5、C 6、D 7、A 8、A 9、A 10、CD 12、A 13、B 14、C 15、C 16、C 17、C 18、D 19、C 20、BA 22、B 23、C 24、D 25、C 26、B 27、C 28、A 29、D30、B31、D32、A33、D34、C 35、A 36、C 37、C 38、B 39、B 40、B41、B 42、B 43、C 44、B 45、B 46、A 47、C 48、C 49、B 50、D51、A 52、D 53、D 54、C 55、C 56、C 57、C 58、D 59、A 60、A61、D 62、D63、C 64、D65、A二、填空題（本大題共40小題，每小題2分，共80分）1.

s->left=p，p->right2.

n(n-1)，n(n-1)/23.

top==04.

O（1）O（n）5.

128441086.

337.

有序n-18.

(12，24，35，27，18，26)9.

510.

i<j&&r[i].key<x.key，r[i]=x11.

p->next，s->data12.

5013.

m14. p->next=q->next;q->next->prior=p;q->next=p;p->prior=q;15. n(n-1)/2、n-116. ADCBFEG、ABCDEFFG17. ABC、ABC18.

619.

(24，65，33，80，70，56，48)20.

821.設計、實現22.特殊、棧頂23.addr+(i-1)xL24.

尾首25.

12926.

F==R27.

p->lchild==NULL&&p->rchild==NULL28.

O(n2)29.

O(nlog2n)，O(n)30.

開放定址法，鏈地址法31.

聯系圖（或圖結構）32.

有序序列后綴表達式（或逆波蘭式）33.

2nn-1n+134.

A[2i+1]A[2i+2]A[]35.

開放定址法鏈接法36.

快速歸并37.

中序38.

739.

O(1)40.

，2i+1三、算法題（本大題共13小題，除第8題5分，其他每小題10分，共125分）1.

設計在順序有序表中實現二分查找的算法。structrecord{intkey;intothers;};intbisearch(structrecordr[],intk){intlow=0,mid,high=n-1;while(low<=high){mid=(low+high)/2;if(r[mid].key==k)return(mid+1);elseif(r[mid].key>k)high=mid-1;elselow=mid+1;}return(0);}2.

設計判斷二叉樹是否為二叉排序樹的算法。intminnum=-32768,flag=1;typedefstructnode{intkey;structnode*lchild,*rchild;}bitree;voidinorder(bitree*bt){if(bt!=0){inorder(bt->lchild);if(minnum>bt->key)flag=0;minnum=bt->key;inorder(bt->rchild);}}3.

在鏈式存儲結構上設計直接插入排序算法voidstraightinsertsort(lklist*&head){lklist*s,*p,*q;intt;if(head==0||head->next==0)return;elsefor(q=head,p=head->next;p!=0;p=q->next){for(s=head;s!=q->next;s=s->next)if(s->data>p->data)break;if(s==q->next)q=p;else{q->next=p->next;p->next=s->next;s->next=p;t=p->data;p->data=s->data;s->data=t;}}}4.

設計在鏈式結構上實現簡單選擇排序算法。voidsimpleselectsorlklist(lklist*&head){lklist*p,*q,*s;intmin,t;if(head==0||head->next==0)return;for(q=head;q!=0;q=q->next){min=q->data;s=q;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;}}}5.

設計在順序存儲結構上實現求子串算法。voidsubstring(chars[],longstart,longcount,chart[]){longi,j,length=strlen(s);if(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]='\0';}}6.編寫算法，將一個結點類型為Lnode的單鏈表按逆序鏈接，即若原單鏈表中存儲元素的次序為a1，……an-1，an，則逆序鏈接后變為,an，an-1，……a1。voidcontrary(Lnode*&HL){}答案：voidcontrary(Lnode*&HL){ Lnode*p=HL;HL=NULL;While(p!=null){Lnode*q=p;p=p→next;q→next=HL;HL=q;}}7.

設有一組初始記錄關鍵字序列（K1，K2，…，Kn），要求設計一個算法能夠在O(n)的時間復雜度內將線性表劃分成兩部分，其中左半部分的每個關鍵字均小于Ki，右半部分的每個關鍵字均大于等于Ki。答案：voidquickpass(intr[],ints,intt){inti=s,j=t,x=r[s];while(i<j){while(i<j&&r[j]>x)j=j-1;if(i<j){r[i]=r[j];i=i+1;}while(i<j&&r[i]<x)i=i+1;if(i<j){r[j]=r[i];j=j-1;}}r[i]=x;}8.設有兩個集合A和集合B，要求設計生成集合C=A∩B的算法，其中集合A、B和C用鏈式存儲結構表示。答案：typedefstructnode{intdata;structnode*next;}lklis