【正文】 答(3)一、基本知識題答案1. 什么是棧？什么是隊列？它們各自的特點是什么？ 答：棧是限定在表的一端進(jìn)行插入或刪除操作的線性表；隊列是元素的添加在表的一端進(jìn)行，而元素的刪除在表的另一端進(jìn)行的線性表；棧的特點是后進(jìn)先出，隊列的特點是先進(jìn)先出。2. 線性表、棧、隊列有什么異同？ 答：棧和隊列都是線性表，但是是受限的線性表，對插入、刪除運算加以限制。棧是只允許在一端進(jìn)行插入、刪除運算，因而是后進(jìn)先出表；而隊列是只允許在一端進(jìn)行插入、另一端進(jìn)行刪除運算，因而是先進(jìn)先出表。3. 簡述棧的入棧、出棧操作的過程。 答：棧的入棧、出棧操作均在棧頂進(jìn)行，棧頂指針指向棧頂元素的下一個位置。入棧操作先將入棧元素放到棧頂指針?biāo)甘镜奈恢蒙?，然后將棧頂指針? 。出棧操作先將棧頂指針減1，然后從棧頂指針指向位置取值。4. 在循環(huán)隊列中簡述入隊、出隊操作的過程。 答：在循環(huán)隊列中，設(shè)隊首指針指向隊首元素，隊尾指針指向隊尾元素后的一個空閑元素。在隊列不滿時，可執(zhí)行入隊操作，此時先送值到隊尾指針指向的空閑元素，隊尾指針再加1（要取模）。在隊列不空時，可執(zhí)行出隊操作，此時先從隊首指針指向處取值，隊首指針再加1（要取模）。二 、算法設(shè)計題答案1. 設(shè)用一維數(shù)組stack[n]表示一個堆棧，若堆棧中一個元素需占用length個數(shù)組單元（length 1），試寫出其入棧、出棧操作的算法。 解：用一整型變量top表示棧頂指針，top為0時表示棧為空。如果棧不空，則從stack[1]開始存放元素。實現(xiàn)本題功能的函數(shù)如下： 入棧算法： void Push(EleType x) { if((top+length)n) printf(上溢出\n)。 else { if(top==0) /*為空棧*/ { top++。 stack[top]=x。 } else { top=top+length。 stack[top]=x。 } }} 出棧算法： void Pop(EleType x) { if(top==0) printf(為空棧\n)。 else { if(top==1) { x=stack[top]。 top。 } else { x=stack[top]。 top=toplength。 } }} 。 解：設(shè)表達(dá)式在字符數(shù)組a[ ]中，使用一堆棧S來幫助判斷。實現(xiàn)本題功能的函數(shù)如下： int correct(char a[]) { Stack S。 InitStack(S)。 for(i=0。istrlen(a)。i++) if(a[i]==39。(39。) Push(S,39。(39。)。 else if (a[i]==39。)39。) { if(StackEmpty(S)) return 0。 else Pop(S)。 } if(StackEmpty(S)) return 1。 /*配對正確*/ else return 0。 /*配對錯誤*/ } 3. 設(shè)一循環(huán)隊列Queue，只有頭指針front，不設(shè)尾指針，另設(shè)一個內(nèi)含元素個數(shù)的計數(shù)器，試寫出相應(yīng)的入隊、出隊算法。解：實現(xiàn)本題功能的函數(shù)如下： void travel(Queue, int front,rear) { int i。 for(i=front。i=rear。i++) { printf(%4d,Queue[i])。 }}。（提示：對表達(dá)式進(jìn)行掃描，凡遇到“（”就進(jìn)棧，遇到“）”就退出棧頂?shù)摹埃ā?，表達(dá)式掃描完畢時棧若為空則圓括號配對正確。） 解:用一個循環(huán)數(shù)組Queue[0,n1]表示該循環(huán)隊列,頭指針為front,計數(shù)器count用來記錄隊列中結(jié)點的個數(shù)。 入隊算法如下： void enqueue(int x) { int temp。 if(count==n) printf(隊列上溢出\n)。 else{ count++。 temp = (front+count)%n。 Queue[temp]=x。 }}出隊算法如下：int dequeue(){ int temp。 if(count==0) printf(隊列下溢出\n)。 else { temp=Queue[front]。 front=(front+1)%n。 count。 return temp。 }}數(shù)據(jù)結(jié)構(gòu)（本科）期末綜合練習(xí)一（單選題）單選題 1. 一個數(shù)組元素a[i] 與( A )的表示等價。 A. *(a+i) B. a+i C. *a+i D. amp。a+i 2. 若需要利用形參直接訪問實參，則應(yīng)把形參變量說明為( B )參數(shù)。 A. 指針 B. 引用 C. 傳值 D. 常值 3. 下面程序段的時間復(fù)雜度為( C )。 for(int i=0。 im。 i++) for(int j=0。 jn。 j++) a[i][j] = i*j。 A. O(m2) B. O(n2) C. O(m*n) D. O(m+n) 4. 執(zhí)行下面程序段時，執(zhí)行S語句的次數(shù)為(D )。 for(int i=1。 i=n。 i++) for(int j=1。 j=i。 j++) S。 A. n2 B. n2/2 C. n(n+1) D. n(n+1)/2 5. 下面算法的時間復(fù)雜度為( B )。 int f(unsigned int n) { if(n==0 || n==1) return 1。 else return n*f (n1)。 } A. O(1) B. O(n) C. O(n2) D. O(n!) 6. 一種抽象數(shù)據(jù)類型包括數(shù)據(jù)和( B)部分。 A. 數(shù)據(jù)類型 B. 操作 C. 數(shù)據(jù)抽象 D. 類型說明 7. 當(dāng)一個作為實際傳遞的對象占用的存儲空間較大并可能被修改時，應(yīng)最好說明為( B )，以節(jié)省參數(shù)值的傳輸時間和存儲參數(shù)的空間。 A. 基本類型 B. 引用型 C. 指針型 D. 常值引用型 8. 當(dāng)需要進(jìn)行標(biāo)準(zhǔn)I/O操作時，當(dāng)需要進(jìn)行文件I/O操作時，則應(yīng)在程序文件中包含( A )頭文件。 9. 一個記錄r理論上占有的存儲空間的大小等于所有域類型長度之和，實際上占有的存儲空間的大小即記錄長度為( D)。 A. 所有域長度之和 B. 最大域所占字節(jié)長度 C. 任意一個域長度 D. sizeof(r)的值 10. 輸出一個二維數(shù)組b[m][n]中所有元素值的時間復(fù)雜度為( D )。 A. O(n) B. O(m+n) C. O(n2) D. O(m*n) 11. 一個算法的時間復(fù)雜度為(3n2+2nlog2n+4n7)/(5n)，其數(shù)量級形式的復(fù)雜度表示為( A )。 A. O(n) B. O(nlog2n) C. O(n2) D. O(log2n) 12. 某算法的時間代價為T(n)=100n+10nlog2n+n2+10，其時間復(fù)雜度為（ C）。 A. O(n) B. O(nlog2n) C. O(n2) D. O(1) 13. 某算法僅含程序段1和程序段2，程序段1的執(zhí)行次數(shù)3n2，則該算法的時間復(fù)雜度為（ C）。 A. O(n) B. O(n2) C. O(n3) D. O(1) 14. 以下說法錯誤的是（C ）。 A. 抽象數(shù)據(jù)類型具有封裝性。 B. 抽象數(shù)據(jù)類型具有信息隱蔽性。 C. 使用抽象數(shù)據(jù)類型的用戶可以自己定義對抽象數(shù)據(jù)類型中數(shù)據(jù)的各種操作。 D. 抽象數(shù)據(jù)類型的一個特點是使用與實現(xiàn)分離。 15. 在二維數(shù)組中，每個數(shù)組元素同時處于（ C ）個向量中。 A. 0個 B. 1個 C. 2個 D. n個 16. 多維數(shù)組實際上是由嵌套的（A ）實現(xiàn)的。 A. 一維數(shù)組 B. 多項式 C. 三元組表 D. 簡單變量 17. 在一個長度為n的順序表中順序搜索一個值為x的元素時，在等概率的情況下，搜索成功時的數(shù)據(jù)平均比較次數(shù)為（ C）。 A. n B. n/2 C.(n+1)/2 D.(n1)/2 18. 在一個長度為n的順序表中向第i個元素（0≤i≤n1）位置插入一個新元素時，需要從后向前依次后移（ A ）個元素。 A. ni B. ni+1 C. ni1 D. i 19. 在一個長度為n的順序表中刪除第i個元素（0≤i≤n1）時，需要從前向后依次前移（ C ）個元素。 A. ni B. ni+1 C. ni1 D. i 20. 在一個長度為n的順序表中刪除一個值為x的元素時，需要比較元素和移動元素的總次數(shù)為（C ）。 A. (n+1)/2 B. n/2 C. n D. n+1 21. 在一個長度為n的順序表的表尾插入一個新元素的漸進(jìn)時間復(fù)雜度為（B ）。 A. O(n) B. O(1) C. O(n2) D. O(log2n) 22. 在一個長度為n的順序表的任一位置插入一個新元素的漸進(jìn)時間復(fù)雜度為（ A ）。 A. O(n) B. O(n/2) C. O(1) D. O(n2) 23. 在一個長度為n的有序順序表中搜索值為x元素的時間效率最高的算法的漸進(jìn)時間復(fù)雜度為（ C ）。 A. O(1) B. O() C. O(log2n) D. O(n) 24. 在二維數(shù)組A[8][10]中，每一個數(shù)組元素A[i][j] 占用3個存儲空間，所有數(shù)組元素相繼存放于一個連續(xù)的存儲空間中，則存放該數(shù)組至少需要的存儲空間是（ C ）。 A. 80 B. 100 C. 240 D. 270 25. 設(shè)有一個n180。n的對稱矩陣A，將其下三角部分按行存放在一個一維數(shù)組B中，A[0][0]存放于B[0]中，那么第i行的對角元素A[i][i]存放于B中（ A ）處。 A. (i+3)*i/2 B. (i+1)*i/2 C. (2ni+1)*i/2 D. (2ni1)*i/2 26. 設(shè)有一個n180。n的對稱矩陣A，將其上三角部分按行存放在一個一維數(shù)組B中，A[0][0]存放于B[0]中，那么第i行的對角元素A[i][i]存放于B中（ C ）處。 A. (i+3)*i/2 B. (i+1)*i/2 C. (2ni+1)*i/2 D. (2ni1)*i/2 27. 設(shè)有兩個串t和p，求p在t中首次出現(xiàn)的位置的運算叫做（ B ）。 A. 求子串 B. 模式匹配 C. 串替換 D. 串連接 28. 不帶頭結(jié)點的單鏈表first為空的判定條件是（ A ）。