數(shù)據(jù)結(jié)構(gòu)習題

1、第一章 緒論一、問答題 1.         什么是數(shù)據(jù)結(jié)構(gòu)？ 2.         敘述四類基本數(shù)據(jù)結(jié)構(gòu)的名稱與含義。 3.         敘述算法的定義與特性。 4.         

2、敘述算法的時間復雜度。 5.         敘述數(shù)據(jù)類型的概念。 6.          敘述線性結(jié)構(gòu)與非線性結(jié)構(gòu)的差別。 7.         敘述面向?qū)ο蟪绦蛟O(shè)計語言的特點。 8.        

3、0;在面向?qū)ο蟪绦蛟O(shè)計中，類的作用是什么？9.     敘述參數(shù)傳遞的主要方式及特點。 10.      敘述抽象數(shù)據(jù)類型的概念。 二、判斷題（在各題后填寫“”或“×”） 1.         線性結(jié)構(gòu)只能用順序結(jié)構(gòu)來存放，非線性結(jié)構(gòu)只能用非順序結(jié)構(gòu)來存放。（   ） 2.    

4、0;    算法就是程序。（   ） 3.          在高級語言（如C或 PASCAL）中，指針類型是原子類型。（   ）三、計算下列程序段中X=X+1的語句頻度 for(i=1;i<=n;i+)   for(j=1;j<=i;j+) for(k=1;k<=j;k+)  x=x+1; 

5、;四、試編寫算法，求一元多項式Pn(x)=a0+a1x+a2x2+a3x3+anxn的值Pn(x0)，并確定算法中的每一語句的執(zhí)行次數(shù)和整個算法的時間復雜度，要求時間復雜度盡可能小，規(guī)定算法中不能使用求冪函數(shù)。注意：本題中的輸入ai(i=0,1,n),x和n，輸出為Pn(x0)。通常算法的輸入和輸出可采用下列兩種方式之一： （1）通過參數(shù)表中的參數(shù)顯式傳遞。 （2）通過全局變量隱式傳遞。 試討論這兩種方法的優(yōu)缺點，并在本題算法中以你認為較好的一種方式實現(xiàn)輸入和輸出。第二章 線性表2.1 描述以下三個概念的區(qū)別：頭指針，頭結(jié)點，首元素結(jié)點。

6、60;2.2 填空： （1） 在順序表中插入或刪除一個元素，需要平均移動元素，具體移動的元素個數(shù)與插入或刪除的位置有關(guān)。 （2） 在順序表中，邏輯上相鄰的元素，其物理位置相鄰。在單鏈表中，邏輯上相鄰的元素，其物理位置相鄰。 （3） 在帶頭結(jié)點的非空單鏈表中，頭結(jié)點的存儲位置由指示，首元素結(jié)點的存儲位置由指示，除首元素結(jié)點外，其它任一元素結(jié)點的存儲位置由指示。 2.3 已知L是無表頭結(jié)點的單鏈表，且P結(jié)點既不是首元素結(jié)點，也不是尾元素結(jié)點。按要求從下列語句中選擇合適的語句序列。 a.  

7、在P結(jié)點后插入S結(jié)點的語句序列是： 。 b. 在P結(jié)點前插入S結(jié)點的語句序列是： 。 c. 在表首插入S結(jié)點的語句序列是： 。 d. 在表尾插入S結(jié)點的語句序列是： 。 供選擇的語句有： （1）P->next=S; （2）P->next= P->next->next; （3）P->next= S->next; （4）S->next= P->next; （5）S->next= L;&#

8、160;（6）S->next= NULL; （7）Q= P; （8）while(P->next!=Q) P=P->next; （9）while(P->next!=NULL) P=P->next; （10）P= Q; （11）P= L; （12）L= S; （13）L= P; 2.4 已知線性表L遞增有序。試寫一算法，將X插入到L的適當位置上，以保持線性表L的有序性。  Stat

9、us Insert_SqList(SqList &va,int x)/把x插入遞增有序表va中    if(va.length+1>va.listsize) return ERROR;   va.length+;   for(i=va.length-1;va.elemi>x&&i>=0;i-)     va.elemi+1=va.elemi; &

10、#160; va.elemi+1=x;   return OK; /Insert_SqList2.5 寫一算法，從順序表中刪除自第i個元素開始的k個元素。 2.6已知線性表中的元素（整數(shù)）以值遞增有序排列，并以單鏈表作存儲結(jié)構(gòu)。試寫一高效算法，刪除表中所有大于mink且小于maxk的元素（若表中存在這樣的元素），分析你的算法的時間復雜度（注意：mink和maxk是給定的兩個參變量，它們的值為任意的整數(shù)）2.7試分別以不同的存儲結(jié)構(gòu)實現(xiàn)線性表的就地逆置算法，即在原表的存儲空間將線性表（a1, a2.,

11、60;an）逆置為（an, an-1,., a1）。 （1） 以順序表作存儲結(jié)構(gòu)。 （2）  以單鏈表作存儲結(jié)構(gòu)。2.8 假設(shè)兩個按元素值遞增有序排列的線性表A和B，均以單鏈表作為存儲結(jié)構(gòu)，請編寫算法，將A表和B表歸并成一個按元素值遞減有序的排列的線性表C，并要求利用原表（即A表和B表的）結(jié)點空間存放表C. 2.9 假設(shè)有一個循環(huán)鏈表的長度大于1，且表中既無頭結(jié)點也無頭指針。已知s為指向鏈表某個結(jié)點的指針，試編寫算法在鏈表中刪除指針s所指結(jié)點的前趨結(jié)點。2.10 已知有單鏈表表示的線性表中含有三類字符的數(shù)

12、據(jù)元素（如字母字符、數(shù)字字符和其它字符），試編寫算法來構(gòu)造三個以循環(huán)鏈表表示的線性表，使每個表中只含同一類的字符，且利用原表中的結(jié)點空間作為這三個表的結(jié)點空間，頭結(jié)點可另辟空間。2.11 設(shè)線性表A=(a1, a2,am)，B=(b1, b2,bn)，試寫一個按下列規(guī)則合并A、B為線性表C的算法，使得：             C= (a1, b1,am, bm, bm+1, ,bn)&

13、#160;    當mn時； 或者    C= (a1, b1,an, bn, an+1, ,am)    當m>n時。 線性表A、B、C均以單鏈表作為存儲結(jié)構(gòu)，且C表利用A表和B表中的結(jié)點空間構(gòu)成。注意：單鏈表的長度值m和n均未顯式存儲。 2.12 將一個用循環(huán)鏈表表示的稀疏多項式分解成兩個多項式，使這兩個多項式中各自僅含奇次項或偶次項，并要求利用原鏈表中的結(jié)點空間來構(gòu)成這兩個鏈

14、表。2.13 建立一個帶頭結(jié)點的線性鏈表，用以存放輸入的二進制數(shù)，鏈表中每個結(jié)點的data域存放一個二進制位。并在此鏈表上實現(xiàn)對二進制數(shù)加1的運算 。2.14 設(shè)多項式P(x)采用課本中所述鏈接方法存儲。寫一算法，對給定的x值，求P(x)的值。 第三章 棧和隊列1. 按圖3.1(b)所示鐵道（兩側(cè)鐵道均為單向行駛道）進行車廂調(diào)度，回答：  如進站的車廂序列為123，則可能得到的出站車廂序列是什么？ 如進站的車廂序列為123456，能否得到435612和135426的出站序列，并說明原因。（即寫出以“S”表

15、示進棧、以“X”表示出棧的棧操作序列）。2. 設(shè)隊列中有A、B、C、D、E這5個元素，其中隊首元素為A。如果對這個隊列重復執(zhí)行下列4步操作： （1） 輸出隊首元素； （2） 把隊首元素值插入到隊尾； （3） 刪除隊首元素； （4） 再次刪除隊首元素。 直到隊列成為空隊列為止，則是否可能得到輸出序列： （A） A、C、E、C、C            

16、0;  （B） A、C、E （C）  A、C、E、C、C、C           （D） A、C、E、C3.  給出棧的兩種存儲結(jié)構(gòu)形式名稱，在這兩種棧的存儲結(jié)構(gòu)中如何判別?？张c棧滿？4. 按照四則運算加、減、乘、除和冪運算（）優(yōu)先關(guān)系的慣例，畫出對下列算術(shù)表達式求值時操作數(shù)棧和運算符棧的變化過程：        &#

17、160;  AB5. 試寫一個算法，判斷依次讀入的一個以為結(jié)束符的字母序列，是否為形如序列1 & 序列2模式的字符序列。其中序列1和序列2 中都不含字符&，且序列2 是序列1的逆序列。例如，a+b&b+a是屬該模式的字符序列，而+&則不是。 6.  假設(shè)表達式由單字母變量和雙目四則運算算符構(gòu)成。試寫一個算法，將一個通常書寫形 式（中綴）且書寫正確的表達式轉(zhuǎn)換為逆波蘭式（后綴）。7. 假設(shè)以帶頭結(jié)點的循環(huán)鏈表表示隊列，并且只設(shè)一個指針指向隊尾元素結(jié)點（注意不設(shè)頭指針

18、），試編寫相應(yīng)的隊列初始化、入隊列和出隊列的算法。8. 要求循環(huán)隊列不損失一個空間全部都能得到利用, 設(shè)置一個標志域tag , 以tag為0或1來區(qū)分頭尾指針相同時的隊列狀態(tài)的空與滿，請編寫與此結(jié)構(gòu)相應(yīng)的入隊與出隊算法。9.  簡述以下算法的功能（其中棧和隊列的元素類型均為int）： （1）void proc_1(Stack S)  int i, n, A255;   n=0;   while(!Empty

19、Stack(S)   n+;  Pop(&S,  &An);    for(i=1;  i<=n;  i+)         Push(&S,  Ai);  （2） void proc_2(Stack S,  int e) 

20、60;Stack T;  int d; InitStack(&T);   while(!EmptyStack(S)    Pop(&S,  &d); if (d!=e) Push( &T,  d);      while(!EmptyStack(T)    Pop(&

21、amp;T,  &d);     Push( &S,  d);     （3） void proc_3(Queue  *Q)  Stack S;  int d; InitStack(&S);   while(!EmptyQueue(*Q)    DeleteQueu

22、e(Q,  &d); Push( &S,  d);            while(!EmptyStack(S)    Pop(&S,  &d); EnterQueue(Q，d)       第四章 串1. 設(shè)s=I 

23、;AM A STUDENT,  t=GOOD,  q=WORKER。給出下列操作的結(jié)果： StrLength(s);  SubString(sub1,s,1,7);  SubString(sub2,s,7,1); StrIndex(s,A,4);  StrReplace(s,STUDENT,q);   StrCat(StrCat(sub1,t), StrCat(sub2,q);2.  編寫算法，實現(xiàn)串的基本

24、操作StrReplace(S,T,V)。3. 假設(shè)以塊鏈結(jié)構(gòu)表示串，塊的大小為1，且附設(shè)頭結(jié)點。 試編寫算法，實現(xiàn)串的下列基本操作： StrAsign(S,chars)； StrCopy(S,T)； StrCompare(S,T)； StrLength(S)； StrCat(S,T)； SubString(Sub,S,pos,len)。4 敘述以下每對術(shù)語的區(qū)別：空串和空格串；串變量和串常量；主串和子串；串變量的名字和串變量的值。5 已知：S=”(xyz)*”,T=”(x+z)*y”。試利用聯(lián)接

25、、求子串和置換等操作，將S轉(zhuǎn)換為T. 6 S和T是用結(jié)點大小為1的單鏈表存儲的兩個串，設(shè)計一個算法將串S中首次與T匹配的子串逆置。7 S是用結(jié)點大小為4的單鏈表存儲的串,分別編寫算法在第k個字符后插入串T，及從第k個字符刪除len個字符。 以下算法用定長順序串： 8  寫下列算法： （1）  將順序串r中所有值為ch1的字符換成ch2的字符。（2） 將順序串r中所有字符按照相反的次序仍存放在r中。 （3） 從順序串r中刪除其值等于ch的所有字符。 （4） 從順序串r

26、1中第index 個字符起求出首次與串r2相同的子串的起始位置。 （5） 從順序串r中刪除所有與串r1相同的子串。 9  寫一個函數(shù)將順序串s1中的第i個字符到第j個字符之間的字符用s2串替換。10  寫算法，實現(xiàn)順序串的基本操作StrCompare(s,t)。 11 寫算法，實現(xiàn)順序串的基本操作StrReplace(&s,t,v)。 第五章 數(shù)組和廣義表 1 假設(shè)有6行8列的二維數(shù)組A，每個元素占用6個字節(jié)，存儲器按字節(jié)編址。已知A的基地址為1000，計算：

27、0;（1） 數(shù)組A共占用多少字節(jié)；（2） 數(shù)組A的最后一個元素的地址； （3） 按行存儲時，元素A36的地址； （4）  按列存儲時，元素A36的地址。第六章 數(shù)和二叉樹1試分別畫出具有3個結(jié)點的樹和3個結(jié)點的二叉樹的所有不同形態(tài)。 2對題1所得各種形態(tài)的二叉樹，分別寫出前序、中序和后序遍歷的序列。 3已知一棵度為k的樹中有n1個度為1的結(jié)點，n2個度為2的結(jié)點，nk個度為k的結(jié)點，則該樹中有多少個葉子結(jié)點并證明之。4. 假設(shè)一棵二叉樹的先序序列為EBADCFHGIKJ，中序序列為ABCDEFGHIJK，

28、請畫出該二叉樹。5.  已知二叉樹有50個葉子結(jié)點，則該二叉樹的總結(jié)點數(shù)至少應(yīng)有多少個？6. 給出滿足下列條件的所有二叉樹： a) 前序和中序相同 b) 中序和后序相同 c) 前序和后序相同 7  n個結(jié)點的K叉樹，若用具有k個child域的等長鏈結(jié)點存儲樹的一個結(jié)點，則空的Child域有多少個？8畫出與下列已知序列對應(yīng)的樹： 樹的先根次序訪問序列為GFKDAIEBCHJ； 樹的后根次序訪問序列為DIAEKFCJHBG。 9 假設(shè)用于通訊的電文僅由8個字母組成，字母

29、在電文中出現(xiàn)的頻率分別為： 0.07，0.19，0.02，0.06，0.32，0.03，0.21，0.10 請為這8個字母設(shè)計哈夫曼編碼。10已知二叉樹采用二叉鏈表存放,要求返回二叉樹T的后序序列中的第一個結(jié)點的指針,是否可不用遞歸且不用棧來完成?請簡述原因. 11. 畫出和下列樹對應(yīng)的二叉樹：  12 已知二叉樹按照二叉鏈表方式存儲，編寫算法，計算二叉樹中葉子結(jié)點的數(shù)目。 13 編寫遞歸算法：對于二叉樹中每一個元素值為x的結(jié)點，刪去以它為根的子樹，并釋放相應(yīng)的空間。14 分別寫函數(shù)完成：在先序線索二叉樹T中，查找給定結(jié)點*

30、p在先序序列中的后繼。在后序線索二叉樹T中，查找給定結(jié)點*p在后序序列中的前驅(qū)。15 分別寫出算法，實現(xiàn)在中序線索二叉樹中查找給定結(jié)點*p在中序序列中的前驅(qū)與后繼。16 編寫算法，對一棵以孩子-兄弟鏈表表示的樹統(tǒng)計其葉子的個數(shù)。17 對以孩子-兄弟鏈表表示的樹編寫計算樹的深度的算法。 18已知二叉樹按照二叉鏈表方式存儲，利用棧的基本操作寫出后序遍歷非遞歸的算法。19 設(shè)二叉樹按二叉鏈表存放，寫算法判別一棵二叉樹是否是一棵正則二叉樹。正則二叉樹是指：在二叉樹中不存在子樹個數(shù)為1的結(jié)點。20 計算二叉樹最大寬度的算法。二叉樹的最大寬度是指：二叉樹所有層中結(jié)點個數(shù)的最大值。21 已知二叉樹

31、按照二叉鏈表方式存儲，利用棧的基本操作寫出先序遍歷非遞歸形式的算法。  22.  證明：a)給定一棵二叉樹的前序序列與中序序列，可唯一確定這棵二叉樹；  B)  給定一棵二叉樹的后序序列與中序序列，可唯一確定這棵二叉樹；23.  二叉樹按照二叉鏈表方式存儲，編寫算法，計算二叉樹中葉子結(jié)點的數(shù)目。 24. 二叉樹按照二叉鏈表方式存儲，編寫算法，將二叉樹左右子樹進行交換。第七章 圖7.1 已知如圖所示的有向圖，請給出該圖的： （1） 每個頂點的入度、出度； （

32、2）  鄰接矩陣； （3） 鄰接表；（4） 逆鄰接表； （5） 十字鏈表； （6） 強連通分量。 7.2 已知如圖所示的無向圖，請給出該圖的： （1） 鄰接多重表；（要求每個邊結(jié)點中第一個頂點號小于第二個頂點號，且每個頂點的各鄰接邊的鏈接順序，為它所鄰接到的頂點序號由小到大的順序。） （2） 從頂點1開始，深度優(yōu)先遍歷該圖所得頂點序列和邊的序列；（給出深度優(yōu)先搜索樹） （3） 從頂點1開始，廣度優(yōu)先遍歷該圖所得頂點序列和邊的序列。（給出廣度優(yōu)先搜索樹）  7.3 已知如圖7.31所示的AOE-網(wǎng)，試求： （1）  每個事件的最早發(fā)生時間和最晚發(fā)生時間； （2） 每個活動的最早開始時間和最晚開始時間； （3） 給出關(guān)鍵路徑。  7.4 已知如圖7.30所示的有向網(wǎng)，試利用Dijkstra算法求頂點1到其余頂點的最短路徑，并給出算法執(zhí)行過程中各步的狀態(tài)。  7.5 編寫算法，由依次輸入