數(shù)據(jù)結構C語言版(崔近平 王霞)VIP

1、第一章緒論一、選擇題1、( B)是數(shù)據(jù)的基本單位。  A) 數(shù)據(jù)結構 B)數(shù)據(jù)元素 C)數(shù)據(jù)項 D)數(shù)據(jù)類型2、以下說法不正確的是( )。  )數(shù)據(jù)結構就是數(shù)據(jù)之間的邏輯結構。  )數(shù)據(jù)類型可看成是程序設計語言中已實現(xiàn)的數(shù)據(jù)結構。)數(shù)據(jù)項是組成數(shù)據(jù)元素的最小標識單位。  )數(shù)據(jù)的抽象運算不依賴具體的存儲結構。3、計算機算法是解決問題的有限運算序列,它具備輸入、輸出和（）等5個特性。A)可執(zhí)行性、可移植性和可擴充性B)可行性、確定性和有窮性C)確定性、有窮性和穩(wěn)定性 D)易讀性、穩(wěn)定性和安全性4、一般而言，最適合描述算法的語言是( )。 A)自然語言 B)

2、計算機程序語言 C)介于自然語言和程序設計語言之間的偽語言 D)數(shù)學公式5、通常所說的時間復雜度指( )。A)語句的頻度 B)算法的時間消耗C)漸近時間復雜度 D)最壞時間復雜度6、A算法的時間復雜度為O(n3)，B算法的時間復雜度為O(2n)，則說明( )。  A)對于任何數(shù)據(jù)量，A算法的時間開銷都比B算法小  B)隨著問題規(guī)模n的增大，A算法比B算法有效  C)隨著問題規(guī)模n的增大，B算法比A算法有效  D)對于任何數(shù)據(jù)量，B算法的時間開銷都比A算法小7、算法分析的目的是（ ）。A)找出數(shù)據(jù)結構的合理性 B)研究算法中的輸入和輸出的關系C)分析算法的

3、效率以求改進 D)分析算法的易懂性和文檔性8、下面程序段的時間復雜度為（ ）。 for( i=0; i<m; i+) for( j=0; j<n; j+) aij=i*j;A)O(m2) B) O(n2) C) O(m*n) D) O(m+n)9、下面算法的時間復雜度為( )。 int f( int n ) if ( n=0 | n=1 ) return 1; else return n*f (n-1); A) O(1) B) O(n) C) O(n2) D) O(n!)二、填空題1、數(shù)據(jù)的( )結構依賴于計算機語言。2、在線性結構中，第一個結點（ ）前驅結點,其余每個結點有且只有

4、（ ）個前驅結點；最后一個結點（ ）后繼結點；其余每個結點有且只有（ ）個后繼結點。3、在樹形結構中,樹根結點沒有（ ）結點，其余每個結點有且只有（ ）個前驅結點；葉子結點沒有（ ）結點，其余每個結點的后繼結點可以（ ）。 4、在線性結構、樹形結構和圖形結構中，前驅和后繼結點之間分別存在著( ) 、（ ）和（ ）的關系。 5、評價一個算法優(yōu)劣的兩個主要指標是（ ）和（ ）。6、數(shù)據(jù)的邏輯結構被分為( )、( )、( )和( )四種。7、數(shù)據(jù)的存儲結構被分為( )、（ ）、（ ）、（ ）四種.8、算法的時間復雜度除了與問題的規(guī)模有關外，還與輸入實例的( )有關。三、問答題與算法題1、 簡述下列概

5、念：數(shù)據(jù)元素：數(shù)據(jù)結構：數(shù)據(jù)類型：數(shù)據(jù)的邏輯結構及其4種類型：數(shù)據(jù)的存儲結構及其4種方式：2、設兩個算法在同一臺機器上執(zhí)行，其執(zhí)行時間分別是 n2和2 n ，要使前者快于后者，n至少需要多大？2、有時為比較兩個同數(shù)量級的算法優(yōu)劣，須突出主項的常數(shù)因子，而將低次項用”O(jiān)”記號表示。如：設T1 ( n ) = 1.39 n log n + 100 n + 256 = 1.39 n log n + O ( n ) ; T2 ( n ) = 2.0 n log n -2 n = 2.0 n log n O( n ) ;這兩個式子表示，當n足夠大時，T1 ( n )優(yōu)于T2 ( n )，因為前者的系數(shù)因

6、子小于后者。請用此方法表示下列函數(shù)，并指出當n足夠大時，哪一個較優(yōu)，哪一個較劣。 (1 ) T1 ( n ) = 5n 2 -3 n +60 log n ; (2 ) T2 ( n ) = 3 n 2 +1000 n + 3 log n ; (3 ) T3 ( n ) = 8 n 2 + 3 log n ; (4 ) T4 ( n ) = 1.5 n 2 + O ( n ) 。4、計算執(zhí)行下面程序段時，執(zhí)行S語句的次數(shù)為。 for(i=1; i<=n; i+) for( j=1; j<=i; j+) S;第二章線性表一、 選擇題1、線性表是具有n個（）的有限序列。 A) 數(shù)據(jù)項；B

7、) 數(shù)據(jù)元素；C) 數(shù)據(jù)對象；D) 表元素。2、以下關于線性表的說法不正確的是( )。 A) 線性表中的數(shù)據(jù)元素可以是數(shù)字、字符、記錄等不同類型。B) 線性表中包含的數(shù)據(jù)元素個數(shù)不是任意的。  C) 線性表中的每個結點都有且只有一個直接前趨和直接后繼。  D) 存在這樣的線性表：表中各結點都沒有直接前趨和直接后繼。3、線性表的順序存儲結構是一種( )的存儲結構。  A) 隨機存取  B) 順序存取 C) 索引存取  D) 散列存取4、在順序表中，只要知道( )，就可在相同時間內(nèi)求出任一結點的存儲地址。A) 基地址  B) 結點大小 C

8、) 線性表大小 D) 基地址和結點大小5、下面關于線性表的敘述中，錯誤的是哪一個？（ ）A) 線性表采用順序存儲，必須占用一片連續(xù)的存儲單元。B) 線性表采用順序存儲，便于進行插入和刪除操作。C) 線性表采用鏈接存儲，不必占用一片連續(xù)的存儲單元。D) 線性表采用鏈接存儲，便于插入和刪除操作。6、線性表采用鏈表存儲時其存儲地址要求（）。A) 必須是連續(xù)的；B) 部分地址必須是連續(xù)的；C) 必須是不連續(xù)的；D) 連續(xù)和不連續(xù)都可以。7、一個長度為n的順序存儲線性表中，向第i個元素(1in+1)之前插入一個新元素時，需要從后向前依次后移( )個元素。A) n-i B) n-i+1 C) n-i-1

9、D) i8、( )運算中，使用順序表比鏈表好。 A) 插入 B) 刪除 C) 根據(jù)序號查找 D) 根據(jù)元素值查找9、個具有n個結點的有序單鏈表中插入一個新結點并仍然有序的時間復雜度是( )。  A) O(1)   B) O(n)   C) O(n2)  D) O(log2n)10、在一個長度為n的順序存儲線性表中，刪除第i個元素(1in+1)時，需要從前向后依次前移( )個元素。A) n-i B) n-i+1 C) n-i-1 D) i11、在一個長度為n的線性表中順序查找值為x的元素時，查找時的平均查找長度（即x同元素的平均比較次數(shù)，假定查找

10、每個元素的概率都相等）為( )。A) n B) n/2 C) (n+1)/2 D) (n-1)/212、在一個帶頭結點單鏈表HL中，若要向表頭插入一個由指針p指向的結點，則執(zhí)行( )。 A) HL = p; p->next = HL; B) p->next = HL; HL = p; C) p->next = HL; p = HL; D) p->next = HL->next; HL->next = p;13、在一個單鏈表HL中，若要在指針q所指的結點的后面插入一個由指針p所指的結點，則執(zhí)行( )。 A) q->next = p->next ;

11、p->next = q; B) p->next = q->next; q = p; C) q->next = p->next; p->next = q; D) p->next = q->next ; q->next = p;14、在一個單鏈表HL中，若要刪除由指針q所指向結點的后繼結點，則執(zhí)行( )。A) p = q->next ; p->next = q->next; B) p = q->next ; q->next = p;C) p = q->next ; q->next = p->nex

12、t; D) q->next = q->next->next; q->next = q;15、在雙向鏈表指針p所指的結點前插入一個指針q所指的結點操作是（ ）。A) p->Prior=q;q->Next=p;p->Prior->Next=q;q->Prior=q；B) p->Prior=q;p->Prior->Next=q;q->Next=p;q->Prior=p->Prior;C) q->Next=p;q->Prior=p->Prior;p->Prior->Next=q;p-

13、>Prior=q;D) q->Prior=p->Prior;q->Next=q;p->Prior=q;p->Prior=q;16設雙鏈表的結點的存儲結構如下：刪除鏈表中指針p所指結點的兩步主要操作是：Llink Data Rlinkp( )， ( )。二、 填空題1、對于一個具有n個結點的單鏈表，在已知的結點*p后插入一個新結點的時間復雜度為（）,在給定值為x的結點后插入一個新結點的時間復雜度為（）。2、根據(jù)線性表的鏈式存儲結構中每一個結點包含的指針個數(shù)，將線性鏈表分成（）和（）。3、順序存儲結構是通過( )表示元素之間的關系的;鏈式存儲結構是通過( )表示

14、元素之間的關系的。4、對于雙向鏈表,在兩個結點之間插入一個新結點需修改( )個指針，單鏈表為( )個。5、循環(huán)單鏈表的最大優(yōu)點是( ) 。6、在無頭結點的單鏈表中，第1個結點的地址存放在頭指針中，其他結點的存儲地址存放在( )結點的next域中。7、帶頭結點的雙循環(huán)鏈表L為空表的條件是（）。8、當線性表的元素總數(shù)基本穩(wěn)定，且很少進行插入和刪除操作，但要求以最快的速度存取線性表中的元素時，應采用( )存儲結構。9、求順序表和單鏈表的長度算法的時間復雜度分別是 ( )和 ( )。10、順序表存儲結構的優(yōu)點是( )、( )、( )；缺點是 ( )。11、單鏈表存儲結構的優(yōu)點是( )、 ( )；缺點是

15、 ( )、 ( )。12、在單鏈表中，設置頭結點的作用是 ( ) 。13、鏈接存儲的特點是利用( )來表示數(shù)據(jù)元素之間的邏輯關系。14、帶頭結點的雙循環(huán)鏈表L為空表的條件是：( )。15、以下算法的功能是：在一個非遞減的順序表中，刪除所有值相等的多余元素。在畫線處填上適當?shù)恼Z句，將程序補充完整。 # define maxlen 100 typedef struct elemtype a maxlen ; int length ; sqlist ;void delequil ( sqlist & S ) int j=1 , i = 2 ; while ( _ ) if ( S.a i !

16、= S.a j ) _ ; _ ; i + ; 三、 問答題與算法題1、試描述頭指針、頭結點、首結點的區(qū)別、并說明頭指針和頭結點的作用。2、何時選用順序表、何時選用鏈表作為線性表的存儲結構為宜?3、為什么在單循環(huán)鏈表中設置尾指針比設置頭指針更好?4、下述算法的功能是什么?LinkList ABC(LinkList L) / L 是無頭結點單鏈表if( L&&L->next ) Q=L;L=L->next;P=L;while (P->next) P=P->next;P->next=Q; Q->next=NULL;return L; 5、寫出下圖

17、雙鏈表中對換值為23和15的兩個結點相互位置時修改指針的有關語句。結點結構為：(prior,data,next) 6、Void AA(SqList &L, int i, int x) if(i>=1&&i<=Length(L) FOR(j= Length (L);j>=i;j - -) Aj+1=Aj; Ai=x; else exit(ERROR); 假定調(diào)用該算法時線性表L的內(nèi)容為（15，26，37，48，55），i為3,x為51，則調(diào)用返回后該單鏈表的內(nèi)容變?yōu)槭裁?7、重寫建立單連表的算法CreatList_L(Linklist &L,in

18、t n )，要求順序輸入n個元素的值(即先輸入a1,a2.).CreatList_L(LinkList &L ； int n)8、設順序表L是一個遞減有序表，試寫一算法，插入元素x，插入后仍保持L的有序性。 Void sinsert(Sqlist &S, int x) 9、寫一算法，在帶頭結點的單鏈表上實現(xiàn)線性表的求表長ListLength(L)運算。int ListLength(LinkList L)10、寫出從一個帶頭結點的單鏈表中刪除其值等于給定值x的結點的算法函數(shù)。 Int delete(LinkList &L, int x) 11、已知遞增有序的兩個帶頭結點的

19、單鏈表La，Lb分別存儲了一個非空集合A,B。設計算法實現(xiàn)求兩個集合的并集的運算A=AB void mergelist(linklist &La, linklist Lb)12、設計算法將不帶表頭結點的單向鏈表就地逆轉。13、刪除整數(shù)數(shù)組中值相等的多余整數(shù)(只保留第一次出現(xiàn)的那個整數(shù))。 Void delDuplicate(int A，int & n)第三章 棧和隊列一、 選擇題1、對于棧操作數(shù)據(jù)的原則是（ ）。A) 先進先出 B) 后進先出 C) 后進后出 D) 不分順序2、一般情況下，將遞歸算法轉換成非遞歸應通過設置（）實現(xiàn)。A) 數(shù)組；B) 線性表；C) 隊列；D) 棧。

20、3、棧和隊列的共同點是（ ）A) 都是先進后出 B) 都是先進先出C) 只允許在端點處插入和刪除元素D) 沒有共同點4、個棧的入棧序列是abcde，則棧的不可能的輸出序列是( )。  A) edcba B) decba C) dceab D) abcde5、在對棧的操作中，能改變棧的結構的是( )。  A) StackLength(S)  B) StackEmpty(S) C) GetTop(S) D) ClearStack(S)6、在一個棧頂指針為HS的(不帶頭結點)鏈棧中將一個S指針所指的結點入棧,執(zhí)行()。   A) HS->next=s;

21、  B) S->next=HS->next; HS->next=s;  C) S->next=HS; HS=s;   D) S->next=HS; HS=HS->next;7、若已知一個棧的入棧序列是1，2，3，n，其輸出序列是p1,p2,p3，pn，若p1=n，則pi=( )。   A) I B) n-i C) n-i+1 D) 不確定8、若用一個大小為的數(shù)組來實現(xiàn)循環(huán)隊列，且當前尾指針rear和頭指針front的值分別為和，當從隊列中刪除一個元素，再加入兩個元素后，尾指針rear和頭指針front的值分別是（）。A

22、) 和；B) 和；C) 和；D) 和。9、輸入序列為ABC，可以變?yōu)锽AC時，經(jīng)過的棧操作為（ ）A)push,pop,push,pop,push,pop B)push,push,push,pop,pop,pop C)push,push,pop,pop,push,pop D)push,pop,push,push,pop,pop10、設用一個大小m=60的順序表Am表示一個循環(huán)隊列，如果當前的尾指針rear=32，頭指針front15, 則當前循環(huán)隊列的元素個數(shù)是( )。 A) 42 ；B) 16 ；C) 17 ；D) 41 。11、設用順序表an表示循環(huán)隊列，頭、尾指針分別為front和rea

23、r，則判斷隊列為空的條件是（ ），判斷隊列滿的條件是（）。（1）A) a.front +1= =a.rear ； B) a.front = = a.rear +1；C) a.front = = 0 ； D) a.front = = a.rear。（2） A) (a.rear -1) % n = a.front ； B) (a.rear +1) % n = a.front；C) a.rear =( a.front-1) % n； D) a.rear = (a.front +1) % n 。12、循環(huán)隊列存儲在數(shù)組A0.m中，則入隊時的操作為（ ）。A) rear=rear+1 B) rear=(

24、rear+1) mod (m-1) C) rear=(rear+1) mod m D) rear=(rear+1)mod(m+1) 13、在解決計算機主機與打印機之間速度不匹配問題時通常設置一個打印數(shù)據(jù)緩沖區(qū)，主機將要輸出的數(shù)據(jù)依次寫入該緩沖區(qū)，而打印機則從該緩沖區(qū)中取出數(shù)據(jù)打印，該緩沖區(qū)應該是一個（）結構。A) 棧； B) 隊列； C) 數(shù)組； D) 線性表。14、設棧用向量V1.n存儲，初始棧頂指針top為n+1，則下面x進棧的正確操作是( )。Atop:=top+1; V top:=x B. V top:=x; top:=top+1 C. top:=top-1; V top:=x D.

25、V top:=x; top:=top-115、 若棧采用順序存儲方式存儲，現(xiàn)兩棧共享空間V1.m，topi代表第i個棧( i =1,2)棧頂，棧1的底在v1，棧2的底在Vm，則棧滿的條件是（ ）。A. |top2-top1|=0 B. top1+1=top2 C. top1+top2=m D. top1=top216、 若棧采用順序存儲方式存儲，現(xiàn)兩棧共享空間V1.m，topi代表第i個棧( i =1,2)棧頂，棧1的底在v1，棧2的底在Vm，則棧滿的條件是（ ）。A. |top2-top1|=0 B. top1+1=top2 C. top1+top2=m D. top1=top2二、 填空題

26、1、在棧中，可進行插入和刪除操作的一端稱( )。2、在作進棧運算時,應先判別棧是否( ),在作退棧運算時應先判別棧是否( )。當棧中元素為n個,作進棧運算時發(fā)生上溢,則說明該棧的最大容量為( )。3、棧的特點是( )，隊列的特點是（ ）。4、由于鏈棧的操作只在鏈表頭部進行，所以沒有必要設置()結點。5、帶頭結點的單鏈表L是空表的條件是（ ）；順序棧S是空棧的條件是（ ）；順序棧S滿的條件是（ ）；不帶頭結點的鏈棧L是空棧的條件是（ ）；循環(huán)隊列Q是空隊列的條件是（ ）；循環(huán)隊列Q是滿隊列的條件是（ ）6、用數(shù)組Q（其下標在0n-1之間，共有n個元素）表示一個循環(huán)隊列，front 為當前隊頭元素

27、的前一個位置，rear為隊尾元素的位置，假設隊列中的元素個數(shù)總小于n，則求隊列中元素個數(shù)的公式是（）。7、設元素入棧的順序是、3、n ，則所有可能的出棧序列共有（）種。8、在具有n個單元的循環(huán)隊列中，隊滿時共有（）個元素。9、設有一個空棧，棧頂指針為1000H(十六進制)，現(xiàn)有輸入序列為1，2，3，4，5，經(jīng)過PUSH,PUSH,POP,PUSH,POP,PUSH,PUSH之后，輸出序列是( )，而棧頂指針值是( )H。(設棧為順序棧，每個元素占4個字節(jié))10、用PUSH表示入棧操作，POP 表示出棧操作，若元素入棧的順序為1234，為了得到1342出棧順序，相應的PUSH和POP的操作串為(

28、 )。 三、 問答題與算法題 1、 設將整數(shù)1，2，3，4依次進棧，若入、出棧次序為Push(s,1), Pop(s,x1),Push(s,2),Push(s,3), Pop(s,x2), Pop(s,x3),Push(s,4), Pop(s,x4 ),則出棧的數(shù)字序列為何?2、設用不帶頭結點的單鏈表表示棧，請分別寫出入棧和出棧的算法。(1) int push_L(Linkstack &s SelemType e) (2) int pop_L(Linkstack &s SelemType &e) 3、假設用帶頭結點的單循環(huán)鏈表表示隊列，并設置一個指向尾結點的指針（無頭指

29、針），請分別寫出隊列的入隊和出隊算法。(1)int EnQueue_L(Queueptr &QL QelemType e) (2)int DeQueue_L(Queueptr &QL QelemType &e)4、指出下述程序段的功能是什么? (1) void abc1(Stack &S) int i， arr64 , n=0 ; while (! StackEmpty(S) Pop(S，e);arrn+=e;for (i=0, i< n; i+) Push(S, arri); (2) Void abc2 (Stack S1, Stack &am

30、p; S2); initstack(tmp);while ( ! StackEmpty (S1) pop(S1,x);Push(tmp,x); while ( ! StackEmpty (tmp) ) Pop( tmp,x); Push( S1,x); Push( S2, x);(3) void abc3( Stack &S, int m)  InitStack (T); while (! StackEmpty( S) Pop(S,e); if( e!=m) Push( T,e); while (! StackEmpty( T)Pop(T,e); Push(S,e);(4)

31、void abc4( Queue &Q)InitStack( S);while (! QueueEmpty( Q )DeQueue( Q,x); Push( S,x);while (! StackEmpty( S) Pop(S,x); EnQueue( Q,x );(5) void invert1( LinkList &L)。 p=L;initstack(S); while(p) /鏈表中的元素全部進棧push(S,p->data); p=p->next;p=L; /利用原來的鏈表只修改數(shù)據(jù)域的值（反序）while(!stackempt(S) pop(S,e); p

32、->data=e; p=p->next;return OK; 5、回文是指正讀反讀均相同的字符序列，如"abba"和"abdba"均是回文，但"good"不是回文。試寫一個算法判定給定的用帶頭結點的單鏈表表示的字符串是否為回文。 Int hw1(linklist L) 6、寫一個將不帶頭結點的鏈棧S中所有結點均刪去的算法void ClearStack( LinkStack &S)。7、寫一個返回不帶頭結點的鏈棧S中結點個數(shù)的算法 int StackSize( LinkStack S).int Stacks

33、ize( LinkStack S)。8、利用棧操作，寫一個算法把一個不帶頭結點的鏈表的元素反序存放（同第二章12題，這里要求利用棧操作）。void invert2( LinkList &L)。9、試將下列遞歸過程改寫為非遞歸過程。 void test(int &sum) int x； scanf(x)； if(x=0) sum=0 else test(sum); sum+=x; printf(sum)； 10、從鍵盤上輸入一個逆波蘭表達式，用偽碼寫出其求值程序。規(guī)定：逆波蘭表達式的長度不超過一行，以$符作為輸入結束，操作數(shù)之間用空格分隔,操作符只可能有+、-、*、/四種運算。例

34、如：234 34+2*$第四章 串一、 選擇題1、 串是一種特殊的線性表，其特殊性體現(xiàn)在( )。  A) 可以順序存儲 B) 數(shù)據(jù)元素是一個字符 C) 可以鏈接存儲 D) 數(shù)據(jù)元素可以是多個字符2、有兩個串P和Q，求P在Q中首次出現(xiàn)的位置的運算稱( )。  A )連接 B) 模式匹配 C) 求子串 D) 求串長3、設S為一個長度為n的字符串，其中的字符各不相同，則S中的互異的非平凡子串（非空且不同于S本身）的個數(shù)為（ ）。A）2n-1 B）n2 C）(n2/2)+(n/2) D）(n2/2)+(n/2)-1 E） (n2/2)-(n/2)-1 4、設串s1='ABC

35、DEFG',s2='PQRST',函數(shù)concat(x,y)返回x和y串的連接串，subString(s,i,j)返回串s的從序號i的字符開始的j個字符組成的子串，Strlength(s)返回串s的長度，則concat(subString(s1,2,Strlength(s2),subString(s1,Strlength(s2),2)的結果串是( )。 A) BCDEF B) BCDEFG C) BCPQRST D) BCDEFEF5、順序串中，根據(jù)空間分配方式的不同，可分為( )。  A) 直接分配和間接分配   B) 靜態(tài)分配和動態(tài)分配 

36、0;C) 順序分配和鏈式分配   D) 隨機分配和固定分配6、設串S=”abcdefgh”，則S的所有非平凡子串（除空串和S自身的串）的個數(shù)是（ ）。A) 8 ； B) 37； C) 36； D) 9。7、設主串的長度為n，模式串的長度為m，則串匹配的KMP算法時間復雜度是（ ）。A) O(m) ； B) O(n)； C) O(n* m)； D) O(m+n)。8、已知串S=aaab,其Next數(shù)組值為（ ）。A0123 B1123 C1231 D1211二、 填空題1、 在空串和空格串中，長度不為0的是( )。2、 空格串是指_(1)_，其長度等于_(2)_3、按存儲結構不同，串可

37、分為( )、（ ）、（ ）。4、C語言中，以字符( )表示串值的終結。5、在塊鏈串中，為了提高存儲密度，應該增大( ).6、假設每個字符占1個字節(jié)，若結點大小為4的鏈串的存儲密度為50%，則其每個指針占( )個字節(jié)。7、串操 作雖然較多，但多可通過五種操作（ ）、（ ）、（ ）、 （ ）、（ ）構成的最小子集中的操作來實現(xiàn)。8、設串S=Ilikecomputer .，T=com，則Length (S ) = （ ）。Index(S,T,1) = ( )9、在KMP算法中，nextj只與（ ）串有關，而與（ ）串無關。10、模式串P=abaabcac的next函數(shù)值序列為（ ）。11、兩個字符串

38、相等的充分必要條件是（ ）。12、串是一種特殊的線性表，其特殊性表現(xiàn)在（ ）；串的兩種最基本的存儲方式是（ ）。三、 問答題與算法題1、 簡述下列每對術語的區(qū)別：空串和空格串：串常量和串變量：主串和子串：目標串和模式串。2、在C語言中假設有如下的串說明：char s130="Stocktom", s230="March51999", s330, ()在執(zhí)行下列語句后，s3的值是什么?strcpy(s3,s1); strcat(s3,","); strcat(s3,s2); ()調(diào)用函數(shù)strcmp(s1,s2)的返回值是什么? ()調(diào)

39、用函數(shù)strcmp(s15,"Ton")的返回值是什么? ()調(diào)用函數(shù)strlen(strcat(s1,s2)的返回值是什么? 、 利用C的庫函數(shù)strlen,strcpy和strcat寫一算法void StrInsert(char *S, char *T, int i),將串T插入到串S的第i個位置上。若i大于S的長度，則插入不執(zhí)行。void StrInsert(char *S, char *T, int i)、利用C的庫函數(shù)strlen 和strcpy(或strcpy)寫一算法void StrDelete(char *S,int i, int m)刪去串S中從位置i開始

40、的連續(xù)m個字符。若istrlen(S),則沒有字符被刪除；若i+mstrlen(S),則將S中從位置i開始直至末尾的字符均刪去。void StrDelete(char *S, int i ,int m) /串刪除5、若S和T是用結點大小為1的帶頭結點的單鏈表存儲的兩個串，試設計一個算法找出S中第一個不在T中出現(xiàn)的字符。 Int indexst(LinkList S, linkLint T)6、在KMP算法中，求下列模式串的nextj。（1） abaabcac （2）aaabaaba7、S=abcabcaabcabcabbacb, T=abcabcabbac，畫出以T為模式串，以S為目標串的KM

41、P算法匹配過程8、如果字符串的一個子串（其長度大于1）的各個字符均相同，則稱之為等值子串。試設計一算法，輸入字符串S，以“！”作為結束標志。如果串S中不存在等值子串，則輸出信息“無等值子串”，否則求出（輸出）一個長度最大的等值子串。例如：若S=“abc123abc123!”，則輸出“無等值子串”；若S=“abceebccadddddaaadd!”，則輸出“ddddd”。第五章 數(shù)組與廣義表一、 選擇題1、稀疏矩陣的一般的壓縮方法有( )。  A) 二維數(shù)組 B) 廣義表 C) 三元組表 D) 一維數(shù)組2、設矩陣A是一個對稱矩陣，為了節(jié)省空間，將其下三角部分按行優(yōu)先存放在一維數(shù)組B中。

42、對下三角矩陣中任一元素aij (i>=j)，在一維數(shù)組B中下標的值是( )。   A) i(i-1)/2+j-1 B) i(i-1)/2+j C) i(i+1)/2+j-1 D) i(i+1)/2+j3、在稀疏矩陣的三元組表表示法中，每個三元組表示( )。  A) 矩陣中數(shù)據(jù)元素的行號、列號和值 B) 矩陣中非零元素的值  C) 矩陣中非零元素的行號和列號 D) 矩陣中非零元素的行號、列號和值4、對稀疏矩陣進行壓縮存儲是為了( )。  A) 便于進行矩陣運算 B) 便于輸入和輸出 C) 節(jié)約存儲空間 D) 降低運算的時間復雜度5、 假設以行序為主序

43、存儲二維數(shù)組A=array1.100，1.100，設每個數(shù)據(jù)元素占2個存儲單元，基地址為10，則LOC5，5=（ ）。 A） 808 B） 818 C）1010 D） 10206、 設有數(shù)組Ai,j，數(shù)組的每個元素長度為3字節(jié)，i的值為1 到8 ，j的值為1 到10，數(shù)組從內(nèi)存首地址BA開始順序存放，當用以列為主存放時，元素A5，8的存儲首地址為( )。A） BA+141 B） BA+180 C） BA+222 D） BA+2257、廣義表是線性表的推廣，它們之間的區(qū)別在于( )。  A) 能否使用子表 B) 能否使用原子項  C) 表的長度   D) 是否能為空

44、8、已知廣義表L=（x,y,z），a，（u，t，w），從L表中取出原子項t的運算是（ ）。A. head（tail（tail（L） B. tail（head（head（tail（L） C. head（tail（head（tail（L） D. head（tail(head（tail（tail（L）)）9、已知廣義表: A=(a,b), B=(A,A), C=(a,(b,A),B),下列運算的結果是: tail(head(tail(C) =( )。A）（a） B） A C） a D） (b) E） b F） (A)10、 廣義表運算式Tail(a,b),(c,d)的操作結果是（ ）。A） (c,d

45、) B） c,d C） (c,d) D） d11、廣義表（a,b,c,d）的表頭是（ ），表尾是（ ）。A） a B）（） C）（a,b,c,d） D）（b,c,d）12、設廣義表L=（a,b,c），則L的長度和深度分別為（ ）。 A） 1和1 B） 1和3 C） 1和2 D）2和313、下面說法不正確的是( )。 A） 廣義表的表頭總是一個廣義表 B） 廣義表的表尾總是一個廣義表C） 廣義表難以用順序存儲結構 D） 廣義表可以是一個多層次的結構14、已知廣義表LS(a,b,c),(d,e,f),運用head和tail函數(shù)取出LS中原子e的運算是( )。 A）head(tail(LS) B）

46、tail(head(LS)C）head(tail(head(tail(LS) D) head(tail(tail(head(LS)15、設一個廣義表中結點的個數(shù)為n，則求廣義表深度算法的時間復雜度為( )。 A) O(1) B) O(n) C) O(n2) D) O(log2n)二、 填空題1、n維數(shù)組中的每個元素都最多有( )個直接前趨。2、對于一個一維數(shù)組A12，若一個數(shù)據(jù)元素占用字節(jié)數(shù)為S，首地址為1，則Ai(i>=0)的存儲地址為( )，若首地址為d，則Ai的存儲地址為( )。3、已知二維數(shù)組Amn采用行優(yōu)先順序存儲，每個元素占k個存儲單元，并且第一個元素的存儲地址LOC（A00），則Aij的地址是( )。4、 多維數(shù)組中，數(shù)據(jù)元素的存放地址直接可通過地址計算公式計算出。因此，數(shù)組是一種( )存取結構。5、 陣的壓縮存儲就是為多個相同的非零元素分配( )個存儲空間，零元素不分配空間。6、遞歸是算法設計的重要方法，遞歸由（ ）項和（ ）項構成。用遞歸的方法求廣義表LS的深度DEPTH(LS)，寫出基本項和遞歸項。 基本項：遞歸項： 7、廣義表( a , ( a , b ) , d