第一章緒論
一、填空題
1． 資料是描述客觀事物的數、字元以及所有能輸入到計算機且能夠被電腦程式加工處理的符號集合是資料的基本單位是資料的最小單位。通常被計算機加工處理的資料不是孤立無關的，而是彼此之間存在著某種聯絡，將這種資料間的聯絡稱為________。
2． 資料結構進行形式化定義時，可以從邏輯上認為資料結構ds是_________的集合d和d上_________的集合r所構成的二元組：ds=（d，r）。
3． 已知某資料結構的二元組形式表示為：a=(d，r)，d=，r=，r=。則此資料結構屬於結構。
4． 乙個演算法的時間複雜度通常用問題規模大小的函式來表示，當乙個演算法的時間複雜度與問題規模n大小無關時，則表示為成正比關係時，則表示為成對數關係時，則表示為成平方關係時，則表示為
5． 資料結構的邏輯結構包括樹型結構和圖型結構三種型別，其中樹型結構和圖型結構合稱為資料結構的儲存結構主要包括和兩種型別。
6． 線性結構的特點是：第乙個結點_______前驅結點，其餘結點有且僅有_______個前驅結點；最後乙個結點_______後繼結點，其餘每個結點有且僅有_______個後繼結點。
7． 樹型結構的特點是：根結點沒有________結點，其餘每個結點有且僅有________個前驅結點；葉子結點_________後繼結點，其餘結點可以有_________個後繼結點。
8． 圖型結構的特點是：每個結點可以有_________個前驅結點和後繼結點。
9． 程式段for（i=1，s=0；s10． 常見的時間複雜度有常數階o(1)、對數階o(log2n)、線性階o(n)、平方階o(n2)、線性對數階o(nlog2n)、立方階o(n3)、指數階o(2n)等等，這些數量階之間的大小關係為
二、分析下列用二元組形式表示的資料結構，指出他們分別屬於何種型別的資料結構。
1. a=（k，r），其中：k=，r=，r=。
2. b=（k，r），其中：k=，r=，r=。
3. c=（k，r），其中：k=，r=，r=。
4. d=（k，r），其中：k=，r=，r1=；r2=。
5. e=（k，r），其中：k=，r=，r=。
三、指出下列各函式的功能並求出其時間複雜度。
1. void prime(int n)
2. long sum1(int n)
return(sum);
}3. long sum2(int n)
return(sum);
}4. void sort(int r[ ],int n)
}第一章參***
一、填空題
1． 資料元素，資料項，結構
2． 資料，關係
3． 樹型
4． o(1)，o(n)，o(log2n)，o(n2)
5． 線性結構，非線性結構，順序結構，鏈式結構
6． 無，一，無，一
7． 前驅，一，無，任意
8． 任意
9． o(n1/2)
分析：設程式段中的迴圈體執行k次，則有不等式成立，解此不等式得到不等式，因此。
10． o(1)
二、分析下列用二元組形式表示的資料結構，指出他們分別屬於何種型別的資料結構。
1． 線性結構
2． 樹型結構
3． 圖型結構
4． 圖型結構
分析：資料結構d中的關係集合r有兩個關係r1和r2。如果只考慮關係r1，則為線性結構；如果只考慮關係r2，則為樹型結構；如果把關係r1和r2聯合起來考慮，則為圖型結構。
5． 圖型結構
分析：若用圖形來表示則可以看出r是e上的對稱關係，為了簡化起見，我們通常把和這兩個有序偶對用乙個無序偶對(x，y)或(y，x)來代替。在用圖形表示時，我們把x結點和y結點之間兩條相反的弧用一條無向邊來代替。
三、指出下列各函式的功能並求出其時間複雜度。
1． 函式的功能是判斷n是否是乙個素數，其時間複雜度為o(n1/2)。
分析：函式prime**現的庫函式sqrt為平方根函式，因此。
2． 函式的計算的值，其時間複雜度為o(n2)。
3． 函式的計算的值，其時間複雜度為o(n)。
4． 函式的功能是對陣列r中的n個元素進行氣泡排序，其時間複雜度為o(n2)。
分析：。
第二章線性表
一、填空題
1． 設長度為n的順序線性表在任何位置上插入或刪除操作都是等概率的，則插入乙個元素時平均需要移動_______個元素，刪除乙個元素時平均需要移動______個元素。
2． 在順序線性表中插入乙個元素時，插入位置開始後的所有元素均需要________移動乙個位置。
3． 在順序線性表中刪除乙個元素時，被刪除元素後的所有元素均需要移動乙個位置。
4． 線性表的鏈式儲存結構中，元素之間的線性關係是通過結點中的________來實現的。
5． 線性表的順序儲存結構中邏輯上相鄰的元素，物理位置相鄰；線性表的鏈式儲存結構中邏輯上相鄰的元素，物理位置相鄰。
6． 已知單鏈表的長度為n，則在給定值為x的結點後插入乙個新結點的時間複雜度為
7． 已知單鏈表的長度為n，則刪除給定值為x的結點的時間複雜度為
8． 在單鏈表中設定頭結點的作用是
9． 雙向鍊錶中每個結點含有兩個指標域，其中乙個指標域指向_______結點，另乙個指標域指向______結點。
10． 在長度為n的線性表中順序查詢某個結點值為x的時間複雜度為
二、選擇題
1．在長度為n的順序線性表中刪除第i個元素(1<=i<=n)，則需要向前移動的元素個數為（ ）。
⑴ n-i ⑵ n+1-i ⑶ n-1-i ⑷ i
2．建立乙個長度為n的單鏈表的時間複雜度為（ ）。
⑴ o(n) ⑵ o(1) ⑶ o(n2) ⑷ ((log2n)
3．設指標p指向單鏈表中的結點a，結點a的後繼結點是結點b，則刪除結點b的操作為（ ）。
⑴ p->next=pp=p->next
⑶ p=p->next->nextp->next=p->next->next
4．設指標p指向單鏈表中結點a，指標q指向單鏈表中結點a的前驅結點b，指標s指向被插入的結點x，則在結點a和結點b之間插入結點x的操作為（ ）。
⑴ s->next=p->next； p->next=s； ⑵ q->next=s； s->next=p；
⑶ p->next=s->next； s->next=p； ⑷ p->next=s； s->next=q；
5．在長度為n的順序線性表中的第i個元素(1<=i<=n+1)之前插入乙個新元素時，則需要向後移動的元素個數為（ ）。
⑴ n-i ⑵ n+1-i ⑶ n-1-i ⑷ i
6．在長度為n的有序線性表中插入乙個元素後仍然保持有序的平均時間複雜度為（ ）。
⑴ o(log2n) ⑵ o(1) ⑶ o(n2) ⑷ o(n)
7．設指標p指向雙向鍊錶中的結點a，指標s指向被插入的結點x，則在結點a之後插入結點x的操作為（ ）。
⑴ p->rlink=s； s->llink=p； p->rlink->llink=s； s->rlink=p->rlink；
⑵ s->llink=p； s->rlink=p->rlink； p->rlink=s； p->rlink->llink=s；
⑶ p->rlink=s； p->rlink->llink=s； s->llink=p； s->rlink->p->rlink；
⑷ s->llink=p； s->rlink=p->rlink； p->rlink->llink=s； p->rlink=s；
8．指標p指向雙向鍊錶中的結點a，則刪除結點a的操作是（ ）。
⑴ p->llink->rlink=p->rlink； p->rlink->llink=p->llink；
⑵ p->rlink->llink=p->rlink； p->llink->llink=p->llink；
資料結構複習答案
8.設指標變數p指向單鏈表結點a，則刪除結點a的後繼結點b需要的操作為 a p next p next nextb p p next c p p next nextd p next p 9.又稱為fifo表 又稱為filo表。a 佇列 b 雜湊表c 棧 d 雜湊表 10.對於棧運算元據的原則是 a ...
資料結構複習總結
第二章線性表 1.線性表的邏輯結構 資料元素之間存在一對一的線性關係 線性表的儲存結構 順序和鏈式 順序表和煉表。順序錶用一維陣列實現，鍊錶有單鏈表和雙鏈表及迴圈鍊錶。每種鍊錶含有指標的個數 2.掌握順序表和煉表的查詢，插入 刪除和排序操作的演算法時間複雜度。第三章棧和佇列 1.棧和佇列邏輯結構 資...
資料結構答案
1 有乙個帶頭指標的單鏈表，寫出在值為x的結點之後插入m個結點的演算法 int insertm linklist l,int x,int m p next q連線斷點 3 假設乙個長度大於1的單迴圈鍊錶既無頭結點也無頭指標，s為指向鍊錶中某個結點的指標，試設計刪除結點s的直接前驅結點的演算法 voi...