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

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

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

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

4、0;    算法就是程序。（   ） 3.          在高級(jí)語言（如C或 PASCAL）中，指針類型是原子類型。（   ）三、計(jì)算下列程序段中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、;四、試編寫算法，求一元多項(xiàng)式Pn(x)=a0+a1x+a2x2+a3x3+anxn的值Pn(x0)，并確定算法中的每一語句的執(zhí)行次數(shù)和整個(gè)算法的時(shí)間復(fù)雜度，要求時(shí)間復(fù)雜度盡可能小，規(guī)定算法中不能使用求冪函數(shù)。注意：本題中的輸入ai(i=0,1,n),x和n，輸出為Pn(x0)。通常算法的輸入和輸出可采用下列兩種方式之一： （1）通過參數(shù)表中的參數(shù)顯式傳遞。 （2）通過全局變量隱式傳遞。 試討論這兩種方法的優(yōu)缺點(diǎn)，并在本題算法中以你認(rèn)為較好的一種方式實(shí)現(xiàn)輸入和輸出。第二章 線性表2.1 描述以下三個(gè)概念的區(qū)別：頭指針，頭結(jié)點(diǎn)，首元素結(jié)點(diǎn)。

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

7、在P結(jié)點(diǎn)后插入S結(jié)點(diǎn)的語句序列是： 。 b. 在P結(jié)點(diǎn)前插入S結(jié)點(diǎn)的語句序列是： 。 c. 在表首插入S結(jié)點(diǎn)的語句序列是： 。 d. 在表尾插入S結(jié)點(diǎn)的語句序列是： 。 供選擇的語句有： （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的適當(dāng)位置上，以保持線性表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個(gè)元素開始的k個(gè)元素。 2.6已知線性表中的元素（整數(shù)）以值遞增有序排列，并以單鏈表作存儲(chǔ)結(jié)構(gòu)。試寫一高效算法，刪除表中所有大于mink且小于maxk的元素（若表中存在這樣的元素），分析你的算法的時(shí)間復(fù)雜度（注意：mink和maxk是給定的兩個(gè)參變量，它們的值為任意的整數(shù)）2.7試分別以不同的存儲(chǔ)結(jié)構(gòu)實(shí)現(xiàn)線性表的就地逆置算法，即在原表的存儲(chǔ)空間將線性表（a1, a2.,

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

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

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

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

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

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

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

18、），試編寫相應(yīng)的隊(duì)列初始化、入隊(duì)列和出隊(duì)列的算法。8. 要求循環(huán)隊(duì)列不損失一個(gè)空間全部都能得到利用, 設(shè)置一個(gè)標(biāo)志域tag , 以tag為0或1來區(qū)分頭尾指針相同時(shí)的隊(duì)列狀態(tài)的空與滿，請(qǐng)編寫與此結(jié)構(gòu)相應(yīng)的入隊(duì)與出隊(duì)算法。9.  簡(jiǎn)述以下算法的功能（其中棧和隊(duì)列的元素類型均為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.  編寫算法，實(shí)現(xiàn)串的基本

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

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

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

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

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

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

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

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

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