1、授課教師：耿國華 教授西北大學可視化技術研究所西北大學可視化技術研究所第一章：緒論n1.2判斷題（在各題后填寫判斷題（在各題后填寫“”或或“”）：）： （1）線性結構只能用順序結構來存放，非線性 結構只能用非順序結構來存放。（） （2）算法就是程序。（） （3）在高級語言（如C或 PASCAL）中，指針類型是原子類型。（）西北大學可視化技術研究所西北大學可視化技術研究所n1.3填空題：填空題： （1）變量的作用域是指 變量的有效范圍 （2）抽象數據類型具有 數據抽象 、 信息隱蔽 的特點。 （3）一種抽象類型包括 數據對象 、 結構關系 和 基本操作 。西北大學可視化技術研究所西北大學可視化技

2、術研究所 （4）當需要用一個形式參數直接改變對應實參的值時，該形式參數應說明為 指針類型 。 （5）數據結構的邏輯結構分為 集合結構 、 線性結構 、 樹形結構 和 圖結構 四種。 （6）數據結構的存儲結構分為 順序存儲結構 和 鏈式存儲結構 兩種。西北大學可視化技術研究所西北大學可視化技術研究所 （7）在線性結構、樹形結構和圖結構中，數據元素之間分別存在著 一對一 、 一對多 和 多對多 的聯系。 （8）算法是規則的有限集合，是為解決特定問題而規定的 操作序列 。 （9）算法具有 有限性 、確定性、 可行性 、 輸入 、輸出五大特性。 西北大學可視化技術研究所西北大學可視化技術研究所n1.4

3、 1.4 選擇題選擇題 （1）若需要利用形式參數直接訪問修改實參值，則應將形參說明為 A 參數。 A.指針 B.值參數西北大學可視化技術研究所西北大學可視化技術研究所 （2）執行下面的程序段的時間復雜度為 C 。 for(int i=0;im;i+) for(int j=0;jn;j+) aij=i*j; A.O(m2) B. O(n2) C. O(m*n) D. O (m+n)西北大學可視化技術研究所西北大學可視化技術研究所n(3)執行下面程序段時，語句S的執行次數為 C 。 for(int i=0;i=n;i+) for(int j=0;j=i;j+) S; A. n2 B. n2/2 C

4、. (n+1) (n+2)/2 D. n(n+1)/2西北大學可視化技術研究所西北大學可視化技術研究所n5.5.計算下列程序段中x=x+1的語句頻度： for(i=1;i=n;i+) for(j=1;j=i;j+) for(k=1;k=j;k+) x=x+1; 思路:語句頻度即為時間頻度，拆分循環語句， 先從后兩個for循環開始思考，最后循環i值。 第一步： 西北大學可視化技術研究所1(1)1 2 3 .2iji iji 西北大學可視化技術研究所n第二步:計算結果 2ni= 111(1 + i)i222nniiii22211(12.)(1 2 .)22nn 1(21)(1)1(1)()()26

5、22nnnn n32623nnn西北大學可視化技術研究所n6.6.編寫算法，求一元多項式： 算法描述： void dxs(int a,int n,int x) int temp=x; /temp保存x的冪次方 int sum=0; /sum保存多項式的計算結果 int i,j,k; int bn; /bi保存多項式的每一項的帶全值 for(j=0;j=n;j+) bj=1; b0=a0; /x的0次方與x的0次方的系數的乘積 b1=a1*x; /x的1次方與x的1次方的系數的乘積n西北大學可視化技術研究所西北大學可視化技術研究所 for(j=2;j=n;j+) /從x的2次方開始，到x的n次方

6、結束 for(k=2;k=j;k+) temp=temp*x; /保存x的m次方 bj=aj*temp; /x的m次方與x的m次方的系數的乘積 temp=x; for(i=0;i=n;i+)sum=sum+bi; cout多項式的值是：sumnext= P-next; A. P-next=S; b.在P結點前插入S結點的語句序列是： H. Q= P; L. P= L; I. while(P-next!=Q) P=P-next; 西北大學可視化技術研究所西北大學可視化技術研究所 E. S-next= P-next; A. P-next=S; c. 在表首插入S結點的語句序列是 F. S-next

7、= L; M. L= S; 。d. 在表尾插入S結點的語句序列是： L. P= L; J. while(P-next!=NULL) P=P-next; A. P-next=S; G. S-next= NULL; 。西北大學可視化技術研究所供選擇的語句有： A. P-next=S; B. P-next= P-next-next; C. P-next= S-next; E. S-next= P-next; F. S-next= L; G. S-next= NULL; H. Q= P; I. while(P-next!=Q) P=P-next; J. while(P-next!=NULL) P=P-

8、next; K. P= Q; L. P= L; M. L= S; N. L= P;西北大學可視化技術研究所 （3）某線性表中最常用的操作是存取序號為i的元素和在最后進行插入和刪除運算，則采用 D 存儲方式 時間性能最好。 A雙向鏈表 B雙向循環鏈表 C單向循環鏈表 D順序表 （4）下列選項中， D 項是鏈表不具有的特點。 A插入和刪除運算不需要移動元素 B所需要的存儲空間與線性表的長度成正比 C不必事先估計存儲空間大小 D可以隨機訪問表中的任意元素西北大學可視化技術研究所 (5)在鏈表中最常用的操作是刪除表中最后一個結點和在最后一個結點之后插入元素，則采用 C 最節省時間。 A. 頭指針的單向

9、循環鏈表 B雙向鏈表 C帶尾指針的單向循環鏈表 D帶頭指針雙向循環鏈表 (6)在線性表中最常用的操作是存取第i個元素及其前趨的值，可采用 A 存儲方式。 A順序表 B單向鏈表 C雙向循環鏈表 D單向循環鏈表西北大學可視化技術研究所n5.寫一個算法，從順序表中刪除自第i個元素開始的k個元素。 算法描述：以待移動元素下標m為中心， 計算應移入位置： for ( m= i1+k; mlast; m+) Lelem mk = Lelem m ;西北大學可視化技術研究所n8.假設兩個按元素值遞增有序排列的線性表A和B，均以單鏈表作為存儲結構，請編寫算法，將A表和B表歸并成一個按元素值遞減有序排列的線性表

10、C，并要求利用原表（即A表和B表的）結點空間存放表C。西北大學可視化技術研究所n 算法描述：要求利用現有的表A和B中的結點空間來建立新表C，可通過更改結點的next域來重新建立新的元素之間的線性關系。為保證新表遞減有序可以利用頭插法建立單鏈表的方法，只是新建表中的結點不用malloc，而只需要從A和B中選擇合適的點插入到新表C中即可。西北大學可視化技術研究所合并兩個有序的單鏈表算法演示 LinkList MergeLinkList(LinkList A,LinkList B) /*將遞增有序的單鏈表A和B合并成一個遞減有序的單鏈表C*/ Node *pa,*pb,*smaller; LinkL

11、ist C; /*將C初始置為空表，pa和pb分別指向兩個單鏈表A和B中的第一個結點，r初值為C*/ pa=A-next; pb=B-next; C=A; C-next=NULL; /*初始化操作*/西北大學可視化技術研究所 /*當兩個表中均未處理完時，比較選擇將較大值結點插入到新表C中。*/ while(pa!=NULL&pb!=NULL) if(pa-datadata) smaller=pa; pa=panext; smallernext = cnext; /* 頭插法頭插法 */ cnext = smaller; else smaller=pb; pb=pbnext; small

12、ernext = cnext; cnext = smaller; if(pa) /*若表A未完，將表A中后續元素鏈到新表C表*/ smaller=pa; pa=panext; smallernext = cnext; cnext = smaller; /*否則將表B中后續元素鏈到新表C表尾*/ else smaller=pb; pb=pbnext; smallernext = cnext; cnext = smaller; return(C); 西北大學可視化技術研究所n10.已知有單鏈表表示的線性表中含有三類字符的數據元素（如字母字符，數字字符和其它字符），試編寫算法來構造三個以循環鏈表表示

13、的線性表，使每個表中只含同一類的字符，且利用原表中的結點空間作為這三個表的結點空間，頭結點可另辟空間。 西北大學可視化技術研究所n 算法描述:只要新建三個頭結點，然后在原來的單鏈表中依次查詢，找到一類字符結點時，就摘下此結點鏈接到相應頭結點指明的新鏈表中就可以實現題目的要求。n 算法提示： 設已建立三個帶頭結點的空循環鏈表 A,B,C.西北大學可視化技術研究所nvoid DivideList( LinkList L, LinkList A, LinkList B, LinkList C) ListNode *p=L-next, *q; ListNode *a=A, ListNode *b=B;

14、 ListNode *c=C; while ( p ) if ( p-data=a &p-datadata=A &p-datanext;/指向下一結點 else if( p-data=0 & p-datanext; b-next=q; q-next=B; b=b-next; else /分出其他字符結點 q=p; p=p-next; c-next=q; q-next=C; c=c-next; /結束西北大學可視化技術研究所第三章 限定性線性表-棧和隊列n1、按書上圖3.1（b）所示鐵道（兩側鐵道均為單向行駛道）進行車廂調度，回答 ：（1）如進站的車廂序列為123，則可能

15、得到的出站車廂序列是什么？答案：123 132 213 231 321 （2）如進站的車廂序列為123456，能否得到435612和135426的出站序列，并說明原因。（即寫出以“S”表示進站，以“X”表示出站的棧操作序列）。西北大學可視化技術研究所n答案：435612不可以 原因 （1）S：1234 X：43 （2）S：5 X: 5 （3）S：6 X: 6 （4）X：21 135426 可以 原因（1）S：1 X：1 （2）S：23 X: 3 （3）S：45 X: 54 （4）X：2 （5）S：6 X: 6 西北大學可視化技術研究所n3、給出棧的兩種存儲結構形式名稱，在這兩種棧的存儲結構中如

16、何判斷?？蘸蜅M？答案：鏈棧和順序棧 鏈棧：?？眨侯^指針為空：即if（head-next=NULL） 棧滿：結點存儲空間申請失敗 順序棧：棧空：棧下標小于零：即 if（stack-toptopMAX） 西北大學可視化技術研究所n4、按照四則運算加、減、乘、除和冪（）運算優先關系的慣例，畫出對下列算術表達式求值時運算數棧和運算符棧的變化過程： A-B*C/D+E F 答案 ： 西北大學可視化技術研究所n ABC-*/=optr(*)T(1)=B*C+=optr(/)T(2)=T(1)/DA-DT(1)/AT(2)-T(3)FE+=optr(-)T(3)=A-T(2)+右邊界右邊界#=optr()

17、T(4)=EFT(3)T(4)+右邊界右邊界#rear%MAXSIZE=q-front &tag=1) /*隊列已滿 return(FALSE); q-elementq-rear = x; /*裝元素*/ q-rear=(q-rear+1)%MAXSIZE; if(q-rear%MAXSIZE=q-front)/*判斷并設置 標志位tag*/ tag=1;return(true);西北大學可視化技術研究所出隊操作：Int deletequeue(seqqueue *q,element *x) if(q-front=q-rear & tag=0)return(FALSE); *x

18、=q-elementq-front; q-front=(q-front+1)%MAXSIZE; if(q-front=q-rear) tag=0; /*設標志tag*/ return（true）；西北大學可視化技術研究所9、設4個元素1、2、3、4依次進棧，而出棧操作可隨時進行（進出?？扇我饨诲e進行，但要保證進棧不破環1、2、3、4的相對次序，）請寫出所有不可能的和可能的出棧次序。 所有可能的：1234 1243 1324 1432 2134 2143 2314 2341 2431 3214 3241 3421 4321 所有不可能的： 1342 1423 2413 3124 3142 3412 4312 4213 4231 4123 41