1、專業(yè)資料專業(yè)資料word word 完美格式單元練習 1一判斷題（下列各題，正確的請在前面的括號內打；錯誤的打 ）（1）數據的邏輯結構與數據元素本身的內容和形式無關。（一個數據結構是由一個邏輯結構和這個邏輯結構上的一個基本運算集構成的整體。（3）數據元素是數據的最小單位。（4）數據的邏輯結構和數據的存儲結構是相同的。（5）程序和算法原則上沒有區(qū)別，所以在討論數據結構時可以通用。（6）從邏輯關系上講，數據結構主要分為線性結構和非線性結構兩類。（7）數據的存儲結構是數據的邏輯結構的存儲映像。（8）數據的物理結構是指數據在計算機內實際的存儲形式。（9）數據的邏輯結構是依賴于計算機的。（1）算法是對解

2、題方法和步驟的描述。二填空題（1）數據有邏輯結構和 存儲結構 兩種結構。（2）數據邏輯結構除了集合以外，還包括：線性結構、樹形結構和圖形結構 。（3）數據結構按邏輯結構可分為兩大類，它們是線性結構和非線性結構。（4）樹形結構和圖形結構合稱為非線性結構。（5）在樹形結構中，除了樹根結點以外，其余每個結點只有1個前趨結點。（6）在圖形結構中，每個結點的前趨結點數和后續(xù)結點數可以任意多個。（7）數據的存儲結構又叫 物理結構 。（8）數據的存儲結構形式包括：順序存儲、鏈式存儲、索引存儲和散列存儲。（9）線性結構中的元素之間存在一對一的關系。（10）樹形結構結構中的元素之間存在一對多的關系，（11）圖形

3、結構的元素之間存在多對多的關系。（12）數據結構主要研究數據的邏輯結構、存儲結構和算法（或運算） 三個方面的內容。數據結構被定義(D，R)，其中D是數據的有限集合是D上的關系的限集合。算法是一個有窮指令的集合。算法效率的度量可以分為事先估算法和事后統計法。一個算法的時間復雜性是算法輸入規(guī)模的函數。算法的空間復雜度是指該算法所耗費的 存儲空間它是該算法求解問題規(guī)模的函數。若一個算法中的語句頻度之和為 T（n）=6n+3nlogn，則算法的時間復雜度為 O2（nlog2n） 。T（n）=3n+nlogn+n2，則算法的時間復雜度為 O2（n2） 。數據結構是一門研究非數值計算的程序設計問題中計算機

4、的操作對象，以它們之間的關系和運算的學科。三選擇題數據結構通常是研究數據的（ A ）及它們之間的相互聯系。存儲結構和邏輯結構B. 存儲和抽象C. 聯系和抽象D.聯系與邏輯在邏輯上可以把數據結構分成（ C 。動態(tài)結構和靜態(tài)結構B.緊湊結構和非緊湊結構C. 線性結構和非線性結構D.內部結構和外部結構數據在計算機存儲器內表示時，物理地址和邏輯地址相同并且是連續(xù)的，稱之為（ C 。存儲結構B. 邏輯結構C. 順序存儲結構D. 鏈式存儲結構非線性結構中的每個結點（ D 。無直接前趨結點無直接后繼結點只有一個直接前趨結點和一個直接后繼結點可能有多個直接前趨結點和多個直接后繼結點鏈式存儲的存儲結構所占存儲空

5、間（ A 。分兩部分，一部分存放結點的值，另一部分存放表示結點間關系的指針只有一部分，存放結點的值只有一部分，存儲表示結點間關系的指針分兩部分，一部分存放結點的值，另一部分存放結點所占單元素算法的計算量大小稱為算法的（ C 。現實性B. 難度C. 時間復雜性D. 效 率數據的基本單位是（ B 。數據結構B. 數據元素C. 數 據項D.文 件存儲結構稱為（ A ）結構。順序存儲B. 鏈式存儲C. 索引存儲D. 散列存儲每一個存儲結點不僅含有一個數據元素，還包含一組指針，該存儲方式是（ B ）儲方式。順序B. 鏈式C. 索引D.散 列以下任何兩個結點之間都沒有邏輯關系的是（ D 。圖形結構B. 線

6、性結構C. 樹形結構D.集 合在數據結構中，與所使用的計算機無關的是（ C 。物理結構B. 存儲結構C. 邏輯結構D. 邏輯和儲結構下列四種基本邏輯結構中，數據元素之間關系最弱的是（ A 。集合B. 線性結構C. 樹形結構D. 圖形結構與數據元素本身的形式、內容、相對位置、個數無關的是數據的（ A 。邏輯結構B. 存儲結構C. 邏輯實現D. 存儲實現（ C ）存儲方式。順序B. 鏈式C. 索引D.散 列算法能正確的實現預定功能的特性稱為算法的（ A 。正確性B. 易 讀性C. 健 壯性D. 高效性算法在發(fā)生非法操作時可以作出處理的特性稱為算法的（ C 。正確性B. 易 讀性C. 健 壯性D.

7、高效性下列時間復雜度中最壞的是（ D 。B. n）C. n）D. 2下列算法的時間復雜度是（ D 。for (i=0;in;i+) for (j=0;in;j+) cij=i+j;B. n）C. n）D. 2算法分析的兩個主要方面是（ A 。空間復雜性和時間復雜性C. 可讀性和文檔性計算機算法必須具備輸入、輸出和（ CB. 正確性和簡明性數據復雜性和程序復雜性。計算方法B.C. 解決問題的有限運算步驟D.四分析下面各程序段的時間復雜度（1） for (i=0;in;i+)for (j=0;jm;j+) Aij解： O(n*m)（2） s=0;for (i=0;in;i+) for s+=Bij

8、;sum=s; 解： O(n2)T=A；A=B； B=T；解：O(1)s1(int n) int p=1,s=0;for (i=1;i=n;i+) p*=i;s+=p; return(s);排序方法程序設計方法 O(n)s2(int n)x=0; y=0;for (k=1;k=n;k+) x+;for (i=1;i=n;i+) for (j=1;j=n;j+)y+;解：O(n2)五 根據二元組關系，畫出對應邏輯圖形的草圖，指出它們屬于何種數據結構。1）A（，R，其中： R= 解：abcd屬于集合2）B（D,，其中： R=,（尖括號表示結點之間關系是有向的）解：aabcdef屬于線性結構。3）F

9、（D,，其中： R=,50255025643657825575屬于樹結構4）C（D,，其中： R=(1,2),(2,3),(2,4),(3,4),(3,5),(3,6),(4,5),(4,6園括號表示結點之間關系12123456屬于圖結構5）E（D,，其中： R=,解：ddbgacehf屬于樹結構。單元練習 2一判斷題（下列各題，正確的請在前面的括號內打；錯誤的打 ）（1）線性表的鏈式存儲結構優(yōu)于順序存儲。（2）鏈表的每個結點都恰好包含一個指針域。（3（4）順序存儲方式的優(yōu)點是存儲密度大，插入、刪除效率高。（5的各個單元向前移動。（6（7）線性表鏈式存儲的特點是可以用一組任意的存儲單元存儲表中

10、的數據元素。（8）線性表采用順序存儲，必須占用一片連續(xù)的存儲單元。（9）順序表結構適宜于進行順序存取，而鏈表適宜于進行隨機存取。（10）經常使用。二填空題（1）順序表中邏輯上相鄰的元素在物理位置上必須相連。（2）線性表中結點的集合是有限的，結點間的關系是一對一關系。（3）順序表相對于鏈表的優(yōu)點是：節(jié)省存儲和隨機存取。（4）鏈表相對于順序表的優(yōu)點是：插入、刪除方便。（5）采用順序存儲結構的線性表叫順序表。（6）順序表中訪問任意一個結點的時間復雜度均為O(1)。（7）鏈表相對于順序表的優(yōu)點是插入、刪除方便；缺點是存儲密度小。（8）在雙鏈表中要刪除已知結*P，其時間復雜度為O(1)。（9）*P*P

11、的直接前趨結點的地址，其查找的時間復雜度為O(n)。單鏈表中需知道 頭指針 才能遍歷整個鏈表。性表中第一個結點沒有直接前趨，稱為開始結點。在一個長度為n的順序表中刪除第i個元素，要移動n-i個元素。在一個長度為n的順序表中如果要在第i個元素前插入一個元素要后移n-i個元素。在無頭結點的單鏈表中，第一個結點的地址存放在頭指針中，而其它結點的存儲址存放在前趨結點的指針域中。當線性表的元素總數基本穩(wěn)定，且很少進行插入和刪除操作，但要求以最快速度取線性表中的元素時，應采用順序存儲結構。在線性表的鏈式存儲中，元素之間的邏輯關系是通過指針 決定的。在雙向鏈表中，每個結點都有兩個指針域，它們一個指向其前趨結

12、點，另一個指向其 后繼結點。對一個需要經常進行插入和刪除操作的線性表，采用鏈式存儲結構為宜。雙鏈表中， 設 p 是指向其中待刪除的結點， 則需要執(zhí)行的操作為： p-prior-next=p-next 。）在如圖所示的鏈表中若在指針 P所在的結點之后插入 數據域值為a和b 的兩個結點則可用下列兩個語句： S-next-next=P-next;和P-next=S; 來實現該操作。PPabS三選擇題在具有n（ A）（n。遍歷鏈表或求鏈表的第iC刪除開始結點P點 D刪除地址為P設bc120（ B 。PPa10b20c循環(huán)鏈表單鏈表雙向循環(huán)鏈表雙向鏈表單鏈表的存儲密度（ C 。大于1B 等于1C小于1D

13、 不能確定已知一個順序存儲的線性表，設每個結點占m 個存儲單元，若第一個結點的地址為i（ A 。A B+(i-1)*mBB+i*mC B-i*mD B+(i+1)*m在有n個結點的順序表上做插入、刪除結點運算的時間復雜度為（ B 。AO（1）2LlinkRlinkP循環(huán)鏈表L（ D 。AP= LBP-Llink=LCP=NULLDP-Rlink=L兩個指針PQ， 所指元素是Q是 （ B 。AP-next=Q-nextBP-next= QCQ-next= P Q用鏈表存儲的線性表，其優(yōu)點是（ C 。便于隨機存取 花費的存儲空間比順序表少C 便于插入和刪除 數據元素的物理順序與邏輯順序相同在單鏈表

14、中，增加頭結點的目的是（ C 。使單鏈表至少有一個結點 標志表中首結點的位置C 方便運算的實現 說明該單鏈表是線性表的鏈式存結構下面關于線性表的敘述中，錯誤的是（ D） 關 系 。 A順序表必須占一片地址連續(xù)的存儲單元B順序表可以隨機存取任一元C鏈表不必占用一片地址連續(xù)的存儲單元D鏈表可以隨機存取任一元素（11）L 是線性表，已知 LengthList（L）的值是 5，經 DelList（L，2）運算后，LengthList（L）的值是（ C 。A2ABCABCDPQR指向鏈表Q（ B 。ALDR設p為指向單循環(huán)鏈表上某結點的指針，*p的直接前驅（ C 。A找不到查找時間復雜度為C查找時間復雜

15、度為D查找結點的次數約為nn（ C 。AnB(n-1)/2 n/2D(n+1)/2在下列鏈表中不能從當前結點出發(fā)訪問到其余各結點的是（ C 。雙向鏈表B單循環(huán)鏈表C單鏈表雙向循環(huán)鏈表在順序表中，只要知道（D ，就可以求出任一結點的存儲地址。基地址結點大小向量大小基地址和結點大小在雙鏈表中做插入運算的時間復雜度為（ A 。AO（1）鏈表不具備的特點是（ A 。隨機訪問不必事先估計存儲空間C插入刪除時不需移動元素所需空間與線性表成正比以下關于線性表的論述，不正確的為（ C。 A線性表中的元素可以是數字、字符、記錄等不同類B線性順序表中包含的元素個數不是任意的C線性表中的每個結點都有且僅有一個直接前

16、趨和一個直接后繼D存在這樣的線性表，即表中沒有任何結點在（ B ）的運算中，使用順序表比鏈表好。插入根據序號查找 刪除根據元素查找ListNode *Demo1(LinkList L,ListNode *p)/ListNode *Demo1(LinkList L,ListNode *p)/ L ListNode *q=L-next; While (q & q-next!=p)q=q-next; if (q)return q;elseError(“*p not in L”);void Demo2(ListNode *p,ListNode *q)/ p,*q DataType temp;temp=

17、p-data;p-data=q-data; q-data=temp;（1）（2）解：*p*p*q（pq。五 程序填空表中所有大于min，小于maxVoid delete (lklist head; datatype min, max) q=head-next; while (p!=NULL) if (p-datadata=max )q=p; p= p-next; else q-next= p-next ; delete (p) ;p= q-next ; 在帶頭結點head 的單鏈表的結點a 之后插入新元素x，struct node elemtype data; node *next;void

18、lkinsert (node *head, elemtype x) node *s, *p;s=new node;s-data=xp=head-next;while (p!=NULL) & ( p-data!=a ) p=p-nextif (p=NULL)coutnext=p-next p-next=s;六算法設計題寫一個對單循環(huán)鏈表進行遍歷（打印每個結點的值）地址為P解：void Show(ListNode *P) ListNode *t=P; do printf(%c,t-data); t=t-rear;while (t!=P);LLx算法。解：void delete(ListNode *

19、L)ListNode *p=L,*q;if(L-next-data=X)printf(“值為x 的結點是第一個結點，沒有直接前趨結點可以刪除”); return;For(p-next-data!=X;q=p;p=p-next);/ 刪除指針p 所指向的結點q-next=p-next;delete p;已知一個單向鏈表，編寫一個函數從單鏈表中刪除自第i 個結點起的k 個結點。解：void Del(node *head,int i,int k)node *p,*q; int j; if(i=1)for(j=1;jnext;delete p;elsep=head; for(j=1;jnext;/ p

20、for(j=1;jnext;/ qp-next=q-next;delete q;有一個單向鏈表（不同結點的數據域值可能相同，其頭指針為hea數計算值域為x1，nint counter(head) node *head； node *p; int n=0; p=head；while(p!=NULL) if(p-data=x) n+；p=p-next;return(n);head1 和 head2，編寫一個函數將鏈表 鏈接到鏈表head2，鏈接后的鏈表仍是循環(huán)鏈表。頭結點鏈接起來，使之成為循環(huán)的。函數如下：node *link (node *head1, *head2) node *p,*q; p

21、=head1;while(p-next!=head1) p=p-next;q=head2;while(q-next!=head2) q=q-next;p-next=head2; q-next=head1; return 單元練習 3一判斷題（下列各題，正確的請在前面的括號內打；錯誤的打 ）（1）棧是運算受 限制的線性表。（2）在棧空的情 況下，不能作出棧操作，否則產生下溢出。（3）棧一定是順序存儲的線性結構。（4）棧的特點是 “后進先出”。（5）空棧就是所有元素都為0的棧。（6）在C或C+語言中設順序棧的長度為MAXLE，則top=MAXLEN時表示隊滿。（7）鏈棧與順序 棧相比，其特點之一是

22、通常不會出現棧滿的情況。（8），B，A，D。（9）遞歸定義就 是循環(huán)定義。（10）將十進制 數轉換為二進制數是棧的典型應用之一。二填空題）在棧結構中，允許插入、 刪除的一端稱為棧頂。）在順序棧中，當棧頂指針 top=-1時，表示棧空。）在有n個元素的棧中，進棧 操作的時間復雜度為O（1）。）在棧中，出棧操作的時間 復雜度為：O(1)。）已知表達式，求它的后綴表達式是棧的典型應用。）在一個鏈棧中，若棧頂指針等于NULL，則表示棧空。向一個棧頂指針為 top的鏈棧插入一個新結點 *p時應執(zhí)行p-next=top ；top=p；操作。）順序棧S存儲在數組 S-data0.MAXLEN-1 中，進棧操

23、作時要執(zhí)行的語句有 S-top+。（或= S-top+1 ）鏈棧 LS，指向棧頂元素的指針是LS-next。從一個棧刪除元素時，首先取出棧頂元素 ，然后再移動棧頂指針。由于鏈棧的操作只在鏈表的頭部進行，所以沒有必要設置頭結點。已知順序棧S，在對S已知順序棧S，在對S若內存空間充足， 鏈棧可以不定義棧滿運算。）鏈棧 LS是空的條件是LS-next=NULL。）鏈棧 LS的棧頂元素是鏈表的首元素。）同一棧的各元素的類型相同。若進棧的次序是、B、E，執(zhí)行三次出棧操作以后，棧頂元素為B。A+B/C-D*E的后綴表達式是：ABC/+DE*-。）四個元素按A、B、C、D順序進S棧，執(zhí)行兩次Pop（S，x）

24、運算后，x的值 C。三選擇題）插入和刪除只能在一端進 行的線性表，稱為( C)。A隊列B循環(huán)隊列C棧D循環(huán)棧）設有編號為 1234的四輛列車，順序進入一個棧結構的站臺，下列不可能的出站順序為 ( D )A1234B1243C1324D1423）如果以鏈表作為棧的存儲 結構，則出棧操作時（BA必須判別棧是否滿B必須判別棧是 否空C必須判別棧元素類型D隊棧可不做任何判別）元素A,B,C,D 依次進棧以后 ，棧頂元素是（DAABBCC）順序棧存儲空間的實現使 用（B）存儲棧元）D素。A鏈表B數組C循環(huán)鏈表D變量（6）在C或C+用空間 的大小（A）。A已固定B不固定C可以改變D動態(tài)變化（7）帶頭結點

25、的鏈棧 LS（A）LSHHABCDAABBCCDD）鏈棧與順序棧相比，有一 個比較明顯的優(yōu)點是（B） 。 A插入操作更加方便B通常不會出現棧 滿的情況C不會出現棧空的情況D刪除操作根加方便）從一個棧 頂指針 為topx保存被刪 除的結點， 應執(zhí)行下列 ( D ) 命令。Ax=top;top=top-next;B top=top-next;x=top-data;Cx=top-data;Dx=top-data;top=top-next;在一個棧 頂指針 為HS的鏈棧中，將一個 S指針所指 的結點 入棧，應執(zhí)行下 列- ( B ) 命令。AHS-next=S;BS-next=HS-next;HS-n

26、ext=S; CS-next=HS-next;HS=S;DS-next=HS;HS=HS-next;）四個元素按A、B、C、D順序進S棧，執(zhí)行兩次Pop（S，x）運算 后，棧頂元素的值是 （B）。AABBCCDD）元素A,B,C,D 依次進棧以 后，棧底元素是（A）。AABBCCDD）經過下列棧的運算后，再 執(zhí)行ReadTop(s) 的值是（A）。InitStack(s)（初始化棧）;Push(s,a);Push(s,b); Pop(s)AaBbC1D0）經過下列棧的運算后，x的值是（B）。InitStack(s)（初始化棧） ;Push(s,a);Push(s,b); ReadTop(s);

27、Pop(s,x);AaBbC1D0）經過下列棧的運算后，x的值是（B）。InitStack(s)（初始化棧） ;Push(s,a);Pop(s,x);Push(s,b);Pop(s,x);AaBbC1D0）經過下列棧的運算后，SEmpty(s) 的值是（C）。InitStack(s)（初始化棧） ; Push(s,a); Push(s,b);Pop(s,x); Pop(s,x);AaBbC1D0）向順序棧中壓入元素時， （B）。先存入元素，后移動棧頂指針B先移動棧頂指針， 后存入元C誰先誰后無關緊要D同時進行（18）初始化一個空間大小為5的順序棧S后，S-top的值是（B）。A0B-1C不再改

28、變D動態(tài)變化（19）一個棧的入棧次 序ABCDE ，則棧 的不可 能的輸出 序列是 ( C ) 。AEDCBABDECBACDCEABDABCDE（20）設有一個順序棧 S，元素A,B,C,D,E,F, 依次進棧，如果六 個元素 出棧的順序是BDCFEAA ) 。A3B4C5D 6四應用題）設有一個棧，元素進棧的次序為：A，B，C，D，E，用I表示進棧操作， O表出棧操作，寫出下列出棧的操作序列。C，B，A，D，EA，C，B，E，D解： IIIOOOIOIOIOIIOOIIOO求后綴表達式 ABC/D解： A B C D / -A+B*C+D/E解 ： 0 A B C * + D E / +

29、A*(B+C)*D-E解： A B C + * D * E - (A+B)*C-E/(F+G/H)-D解： A B + C * E F G H / + / - D - 8/(5+2)-6解：8 5 2 + / 6 -六算法設計題設用一維數組 stackn 表示一個堆棧，若堆棧中每個元素需占用M個數組單元（M1）。試寫出其入棧操作的算法。試寫出其出棧操作的算法。解：/用一整型變量top0S 放元素。/入棧算法：void push (char x)if (top+M)MAXLEN-1)printf (“堆棧溢出！”); elseif (top= =0)top+;S top=x;elsetop=to

30、p+M;S /出棧算法：void pop (char x)if (top= =0)printf (“堆棧為空棧！”); elseif (top= =1)x= S top;top;elsex= S top;top=topM;解：/設表達式在字符數組a 中，使用一堆棧Sint correct (char a )stack s ;InitStack (s);/for (i=0; i strlen(a);i+)if (ai= =()Push (s,(); elseif (ai= =)if StackEmpty (s)/調用判棧空函數return 0;/若棧為空返回0；否則出elsePop(s);if

31、(StackEmpty (s) )/調用判棧空函數printf (“配對正確！”);/若棧空，說明配對正確，并返elseprintf (“配對錯誤！”);/配對錯誤返回0解： #include#includetypedef struct stacknode/定義棧的存儲結構int data;struct stacknode *next;stacknode; typedef structstacknode *top;定義棧頂的指針linkstack;void Conversion(int n)換 linkstack s; int x; s.top=NULL;/棧的應用：十十六進制轉/置棧空dox

32、=n%16;/取余數n=n/16;/取新的商stacknode *p=new stacknode;申請新結點p-next=s.top ;/s.top=p;s.top-data=x;余數入棧while(n);printf(ntt 轉換后的十六進制數值為：;while (s.top)出棧處理if(s.top-datadata);elseswitch(s.top-data)case 10:printf(%c,A);break;case 11:printf(%c,B);break;case 12:printf(%c,C);break;case 13:printf(%c,D);break;case 14

33、:printf(%c,E);break;case 15:printf(%c,F);break;stacknode *p=s.top; s.top=s.top-next;free(p) ;出棧一個余數，收回一個結printf(nn);void main()int n;printf(ntt 請輸入一個十進制正整數：); scanf(%d,&n);Conversion(n);單元練習 4一判斷題（下列各題，正確的請在前面的括號內打；錯誤的打 ）（1）隊列是限制 在兩端進行操作的線性表。（2）判斷順序隊 列為空的標準是頭指針和尾指針都指向同一個結點。（3）在鏈隊列上做出隊操作時，會改變front指針的

34、值。（4）在循環(huán)隊列中，若尾指針rear大于頭指針fron，其元素個數為rear- fron。（5）在單向循環(huán)鏈表中，若頭指針為，那么p所指結點為尾結點的條件是p=。（6）鏈隊列在一定范圍內不會出現隊滿的情況。（7）在循環(huán)鏈隊列中無溢出現象。（8）棧和隊列都是順序存儲的線性結構。（9）在隊列中允 許刪除的一端稱為隊尾。（10）順序隊和 循環(huán)隊關于隊滿和隊空的判斷條件是一樣的。二填空題） 在隊列中存取數據應遵循的原則是先進先出。）隊列是被限定為只能在表的一端進行插入運算，在表的另一端進行刪除運算的線性表。（3）在隊列中，允許插入的一端稱為隊尾。（4）在隊列中，允許刪除的一端稱為隊首（或隊頭）。（

35、5）隊列在進行出隊操作時，首先要判斷隊列是否為空。（6）順序隊列在進行入隊操作時，首先要判斷隊列是否為滿。（7）順序隊列初始化后， front=rear=-1。（8）解決順序隊列“假溢出”的方法是采用循環(huán)隊列。（9）循環(huán)隊列的隊首指針為 front，隊尾指針為 rear，則隊空的條件為front=rear。）鏈隊列LQ為空時，LQ-front-next= NULL。）設長度為 n的鏈隊列用單循環(huán)鏈表表示，若只設頭指針，則入隊操作的時復雜度為O（n）。）設長度為 n的鏈隊列用單循環(huán)鏈表表示，若只設尾指針，則出隊操作的時復雜度為0 （1） 。）在一個鏈隊列中，若隊首指針與隊尾指針的值相同，則表示該

36、隊列為空。）設循環(huán)隊列的頭指針 front指向隊首元素，尾指針 rear指向隊尾元素后的一 個 空 閑 元 素 ， 隊 列 的 最 大 空 間 為 MAXLEN ， 則 隊 滿 標 志 為： front=(rear+1)%MAXLEN。） 在一個鏈隊列中，若隊首指針為front，隊尾指針為 rear，則判斷該隊列有一個結點的條件為：front=rear & front !NULL。( 或 front=rear & front NULL )） 向一個循環(huán)隊列中插入元素時，首先要判斷隊尾指針，然后再向針所指的位置寫入新的數據。讀隊首元素的操作不改變（或不影響）隊列元素的個數。設循環(huán)隊列的容量為4（

37、序號從0到3，現經過一系列的入隊和出隊運算后， front=11，rear=19，則循環(huán)隊列中還有8個元素。（L= (Nrearfront)% 40=8）（19）隊列 Q，經過下列運算：InitQueue(Q)( 初始化隊列);InQueue(Q,a); InQueue(Q,b);OutQueue(Q,x); ReadFront(Q,x);QEmpty(Q);后的值是0。（ 20 ） 隊 列 Q 經 過 InitQueue(Q)( 初 始 化 隊 列 );InQueue(Q,a);InQueue(Q,b);ReadFront(Q,x)后，x的值是a。三選擇題）隊列是限 定在（D）進行操作的線性

38、表。A 中間B 隊首C 隊尾D 端點）隊列中的元素個數是( B)。ABC 任意的D0）同一隊列內各元素的類型 ( A)。A必須一致B不能一致C可以不一致）隊列是一個( C)線性表結構。A不加限制的B推廣了的C加了限制的D 不限制D 非）當利用大小為 n的數組順序存儲一個隊列時，該隊列的最后一個元素的下標為（ B）。An-2Bn-1CnDn+1）一個循環(huán)隊列一旦說明， 其占用空間的大小（A）。A已固定B可以變動循環(huán)隊列占用的空 間( A)。C不能固定D動態(tài)變化ABC不能連續(xù)D可以不連續(xù)）存放循 環(huán)隊列元素的數組data有10個元素，則data數組的下標范圍是 (B )。A0.10B0.9C1.9

39、D1.10）若進隊的序列為： A，B，C，D，則出隊的序列是（C）。A B，C，D，C A，B，C，DBA，C，B，D C，B，D，A）四個元素按： A，B，C，D順序連續(xù)進隊 Q，則隊尾元素是（D）。A AC C D ）四個元素按： A，B，C，D順序連續(xù)進隊 Q，執(zhí)行一次 OutQueue(Q) 操作后，隊頭元素是（B）。A AB BC CD D）四個元素按： A，B，C，D順序連續(xù)進隊 Q，執(zhí)行四次 OutQueue(Q) 操作后， 執(zhí)行QEmpty(Q);后的值是（ B）。A 0B 1C 2D 3隊Q，經過下列運算后 的值是（ B）。InitQueue(Q)( 初始化隊列 );InQu

40、eue(Q,a); InQueue(Q,b);OutQueue(Q,x); ReadFront (Q,x);AaBbC0D1循環(huán)隊列 SQ隊滿的條件是 ( B)。ASQ-rear=SQ-frontB (SQ-rear+1)% MAXLEN=SQ-frontCSQ-rear=0DSQ-front=0）設鏈棧中結點的結構： data為數據域， next為指針域，且 top是棧頂指針若想在鏈棧的棧頂插入一個由指針s所指的結點，則應執(zhí)行下列（A）操作。As-next=top-next ；top-next=s ；Btop-next=s ；Cs-next=top ；top=top-next ；Ds-nex

41、t=top ；top=s；）帶頭結點的鏈隊列LQ示意圖如下，鏈隊列的隊頭 元素是（A）LQ-frontHAHABCDAABBCCDDHABCD）帶頭結點的鏈隊列LQ示意圖如下，指向鏈隊列的 HABCDLQ-rearALQ-frontBLQ-rearCLQ-front-nextDLQ-rear-next（18） 帶頭結點的鏈隊列LQ 示意圖如下， 在進行進隊運算時指針LQ-frontHAHABCDLQ-rear始終不改變B有時改變C進隊時改變D出隊時改變隊Q，經過下列運算后，再執(zhí)QEmpty(Q) 的值是（ C）。InitQueue(Q)(初始化隊列);InQueue(Q,a);InQueue(

42、Q,b);OutQueue(Q,x); ReadQueue(Q,x);AaBbC0D1若用一個大小的數組來實現循環(huán)隊列，且當front和rear的值分別為3和0，從隊列中 刪除一個元素，再加入 兩個元素后，front和rear的值分別( B)。A5和1B4和2C2和4D1和5四 寫出程序運行的結果寫出下列程序段的輸出結果（隊列中的元素類型為char void main( )Queue Q; InitQueue (Q);/char x=E; y=C;InQueue (Q, H);InQueue (Q, R); InQueue (Q, y);OutQueue (Q,x); InQueue (Q,x

43、); OutQueue (Q,x); InQueue (Q, A); while (!QEmpty(Q)OutQueue (Q,y); printf(y);printf(x);CHA五程序填空假定用一個循環(huán)單鏈表表示一個循環(huán)隊列，該隊列只設一個隊尾指針 rear，試填空完成向循環(huán)隊列中插入一個元素為x 的結點的函數。typedef struct queuenode/ int data;struct queuenode *next;QueueNode;InQueue(QueueNode *rear,int x)/x QueueNode *rear; QueueNode *head,*s;s=ne

44、w QueueNodes-data=x;if(rear=NULL)/ rear=s; rear-next; else head=rear-next; / 循環(huán)隊列非空，則將srear-next=srear=s;rear-next=head;六. 算法設計題）Queuefront ，不設尾指 針，另設 一個含有元素個數的記 數器cont解：/ 入隊算 法：void inqueqe(int x) int temp;if (count=n)printf( 隊列上 溢出n); elsecount+ temp=(front+count)%n; Queuetemp=x/ 出隊算 法：int outqueu

45、e() int temp; if(count=0)printf( 隊列下溢出 n); else temp=Queuefront; front=(front+1)%n; count-;return temp;）Q0.MAXLEN-1front ，不設尾指 針，而改置一 個記數器 count解：/ 用一個循環(huán)數組Queue0 ， n-1 表示該循環(huán)隊列， 頭指針為front ， 計數器count 用來記錄 隊列中 結點的個 數。/ 隊列為 空： count=0/ 隊列為 滿： count=MAXLEN/ 隊尾第 一個元 素位置 =(front+count)%MAXLEN/=(front+1)%MA

46、XLEN const MAXLEN=100;int queueMAXLEN;int front,count;/count初始化 隊列void init()front=1; count=0;判定隊 空int QEmpty()if (count=0) return(1);elsereturn(0);讀隊頭 元素void ReadFront(int queue,x)if (count=0)printf( 下溢出else入隊操 作front=(front+1)%MAXLEN; x=queuefront;void InQueue(int queue,int x)int place;if (count=M

47、AXLEN) printf( 上溢出n);else出隊操 作count+; place=(front+count)%MAXLEN; queueMAXLEN=x;void OutQueue(int queue)/ 刪除隊列頭 元素if (count=0)printf( 隊列下溢出 n); elsefront=(front+1)%MAXLEN; count-;）一個用 單鏈表 組成的循環(huán) 隊列，只 設一個尾指針 rear ，不設頭指針，請編 寫他如下算 法：向循環(huán) 隊列中 插入一 個元素為 x的結點；從循環(huán) 隊列中 刪除一 個結點。/typedef struct linknodeint data;

48、struct linknode *next;QueueNode; QueueNode Inqueue(int x)/ 向隊列插入結點 xQueueNode *head, *s;s=(qu *) new qu;/ 創(chuàng)建一個新結點s-data=x;if(rear=NUlL)/ 若隊空,則建立一個 循環(huán)隊 列rear=s;rear-next=s;else/s插到后面解：head=rear-next ； rear-next=s;rear=s;/ rear 始終指 向最后一個結 點rear-next=head;void delqueue(rear)if(rear=NULL)printf( 下溢出!n);

49、 elsehead=rear-next;/ head 指向隊首 結點if(head=rear)rear=NULL/ 只有個結 點則直接刪除 該結點elserear-next=head-next/ 否則刪除第一個結delete head ；/ 釋放隊首結點單元練習 5一判斷題（下列各題，正確的請在前面的括號內打；錯誤的打 ）（1）串是n個字母的有限序列。（2）串的數據元素是一個字符。（3）串的長度是指串中不同字符的個數。（4）如果兩個串含有相同的字符，則說明它們相等。（5）如果一個串中所有的字母均在另一個串中出現，則說明前者是后者的子串。（6）串的堆分配存儲是一種動態(tài)存儲結構。（7“DDAT”的

50、子串。（8）串中任意個字符組成的子序列稱為該串的子串。（9）子串的定位運算稱為模式匹配。（1）在鏈串中為了提高存儲密度，應該增大結點的大小。二填空題（1）由零個或多個字符組成的有限序列稱為字符串（或串）。（2）字符串按存儲方式可以分為：順序存儲、鏈接存儲和堆分配存儲。（3）串的順序存儲結構簡稱為順序串。（4）串順序存儲非緊湊格式的缺點是：空間利用率低。（5）串順序存儲緊湊格式的缺點是對串的字符處理效率低。（6）串鏈接存儲的優(yōu)點是插入、刪除方便，缺點的空間利用率低。（7）在C或C+語言中，以字符0表示串值的終結。（8）空格串的長度等于空格的個數。（9）在空串和空格串中，長度不為0的是空格串。）

51、兩個串相等是指兩個串相長度等， 且對應位置的 字符都 相 同 。）S=My Music ，則LenStr(s)= _ 8 。） 兩 個 字 符 串 分 別 為 ： S1=Today is ， S2=30 July,2005,ConcatStr(S1,S2) 的 結 果 是 ： Today is July,2005 。） 求子串函數SubStr(Today is 30 July,2005,13,4) 的結果是 ： July 。（14）在串的運算中，EqualStr(aaa,aab) 的返回值為m，則模式匹配算法最壞情況下的時間復雜度 為 ： (n-m+1)*m 。三選擇題（1）串是一種特殊的線性

52、表，其特殊性體現在（B）。A.可以順序存儲B數據元素是一個字符C.可以鏈接存儲D數據元素可以是多個字符某串的長度小于一個常數，則采用（ B ）存儲方式最節(jié)省空間。A鏈式B 順序C堆結構D無法確定（3）以下論述正確的是（C）。A 空串與空格串是相同的C 空串是零個字符的串（4）以下論述正確的是（B）。空串與空格串是相同的C 空格串是有空格的串（5）以下論斷正確的是 ( A ) A是空串，空格串C somethingSomethigtelTeleptone 的子串D. 空串的長度等于1Bton 是Teleptone 的子串空串的長度等于1B BEIJING 是BEI JING 的子串D BIT=B

53、ITE（6）設有兩個串S1和S2，則EqualStr(S1,S2) 運算稱作(D)。串連接C. 求子串串的模式匹配是指（ D A判斷兩個串是否相等 B對兩個串比較大小符位置B 模式匹配D 串比較C找某字符在主串中第一次出現的位置 ）若字符串 ABCDEFG 采用鏈式存儲，假設每個字符占用1個字節(jié)，每個指針用2個字節(jié)。則該字符串的存儲密度為( D ) 。A20B 40C50D 333）若字符串 ABCDEFG 采用鏈式存儲，假設每個指針占用2個字節(jié)，若希望存密度50，則每個結點應存儲 ( A ) 個字符。A2B 3C4D5（10）設串S1=I AM ，S2=A SDUDENT, 則ConcatS

54、tr(S1,S2)=(B)。AI AMCIAMASDUDENTB I AM ASDUDENTD. A SDUDENT（11）S=LenStr （S）（A）A0B1C2D 3（12）設目標串T=AABBCCDDE ，模式P=ABCDE ，則該模式匹配的有效位移為(A)。A0B1C2D 3（13）設目標串T=AABBCCDDEEFF ，模式P=CCD ，則該模式匹配的有效位移為(D)。A2B3C4D. 5（14）設目標串T=aabaababaabaa ，模式P=abab, 樸素匹配算法的外層循環(huán)行了(D)次。A1B9C4D5）樸素模式匹配算法在最壞情況下的時間復雜度是( D ) 。A O（m）B

55、O（n）C0（m+n）D0（m*n）（16）S=morning ，執(zhí)行求子串函數SubStr(S,2,2) 后的結果為(B)。AmoBorCinDng（17）S1=good ，S2=morning ，執(zhí)行串連接函數ConcatStr(S1,S2) 后的結果為(A)。AgoodmorningB goodmorningCGOODMORNINGD GOODMORNING（18）S1=good ，S2=morning ，執(zhí)行函數SubStr(S2,4,LenStr(S1)后的結為(B)。AgoodBningCgoDmorn（19）S1=ABCDEFGS2=PQRST ,則 ConcatStr(SubS

56、tr(S1,2,LenStr(S2),SubStr(S1,LenStr(S2),2)的結果為(D)。BCDEFBBCDEFGCBCPQRSTD. BCDEFEF（20）若串S=SOFTWARE ，其子串的數目最多是：（C） 。A35B 36C37D（8+7+6+5+4+3+2+1+1=37）四程序題填空下面程序是把兩個串r1r2typedef Struct char vecMAXLEN;/int len;/ len為串的長度St;void ConcatStr(Str *r1,Str *r2)/int i;coutvecvec;if(r1-len+r2-len MAXLEN ) cout兩個串太

57、長，溢出！;elsefor(i=0;ilen ;i+)/r2 連接到r1-vec r1-len+i =r2-veci;r1-vecr1-len+i= 0 ;/ 添上字符串結束標r1-len= r1-len+r2-len ;/修改新串長度設x 和yx 和 y數，試完成程序填空。#define MAXLEN 100 typedef struct char vecMAXLEN; len; str;int same (x,y) str *x,*y; int i=0,tag=1;if (x-len!=y-len) return (0);/ 或else while ( ilen&tag ) if ( x-

58、veci!=y-veci )tag=0 i+;（ 或i=i+1）return (tag);4）下面算法是判斷字符串是否為回文（即正讀和倒讀相同 #include stdio.htypedef struct char vecMAXLEN; int len;str;void Palindrome (str s) int i=0;ing j=s.len-1while ( j-i=1 ) if ( s.veci=s.vecj )i+; j- ;continue/j=j+1 elsebreak;if (j-i=1)coutIt is not a palindromen;elsecoutIt is a p

59、alindromen;五 編程題#define MAXLEN 100typedef struct char vecMAXLEN; int len; str; 將串中r 中所有其值為ch1 的字符換成ch2 將串中rr 從串 r 中刪除其值等于ch 的所有字符。 從串 r1 中第index 個字符起求出首次與字符r2 相同的子串的起始位置。 從串 rr3（允許調用第小題的函數。 編寫一個比較x 和y解：/算法思想：從頭至尾掃描r 串，對于值為ch1 的元素直接替換成ch2 即可。str *trans(r,ch1,ch2)str *r;char ch1,ch2; int i;for(i=0;ile

60、n;i+) if(r-veci=ch1)r-veci=ch2; return(r);/算法思想是：將第一個元素與最后一個元素交換，第二個元素與倒數第二個元素交換，依次類推，便將該串的所有字符反序了。str *invert (r) str *r; int i; char x;for(i=0;ilen%2);i+) x=r-veci;r-veci=r-r-len-i+1; r-vecr-len-i+1=x;return (r );/算法思想：從頭到尾掃描r 串，對于值為ch 的元素用移動的方式進行刪除。str *delall(r,ch)str *r;char ch; int i,j;for(i=0