【正文】 amp。int ListLength(LinkList L)寫(xiě)出從一個(gè)帶頭結(jié)點(diǎn)的單鏈表中刪除其值等于給定值x的結(jié)點(diǎn)的算法函數(shù)。L, int x) { 1已知遞增有序的兩個(gè)帶頭結(jié)點(diǎn)的單鏈表La，Lb分別存儲(chǔ)了一個(gè)非空集合A,B。La, linklist Lb)1設(shè)計(jì)算法將不帶表頭結(jié)點(diǎn)的單向鏈表就地逆轉(zhuǎn)。 Void delDuplicate(int A[]，int amp。A) 先進(jìn)先出 B) 后進(jìn)先出 C) 后進(jìn)后出 D) 不分順序一般情況下，將遞歸算法轉(zhuǎn)換成非遞歸應(yīng)通過(guò)設(shè)置（　?。?shí)現(xiàn)。棧和隊(duì)列的共同點(diǎn)是（ ）A) 都是先進(jìn)后出 　　　B) 都是先進(jìn)先出C) 只允許在端點(diǎn)處插入和刪除元素　　D) 沒(méi)有共同點(diǎn)若棧的入棧序列是abcde，則棧的不可能的輸出序列是(　　　 )。A) edcba B) decba C) dceab D) abcde在對(duì)棧的操作中，能改變棧的結(jié)構(gòu)的是(　　 )。A) StackLength(S) HSnext=s。C) Snext=HS。 HS=HSnext。 A) １和５；　　　B) ２和４；　　C) ４和２；　　　D) ５和１。 A) 42 ；　　　B) 16 ；　　　C) 17 ；　　　　　D) 41 。（1）A) +1= = ；　　 　　　 B) = = +1；C) = = 0 ； 　　　 D) = = 。1循環(huán)隊(duì)列存儲(chǔ)在數(shù)組A[0..m]中，則入隊(duì)時(shí)的操作為（ ）。A) 棧； 　　　 B) 隊(duì)列； 　　 C) 數(shù)組； 　　D) 線性表。A．V[++top]=x 。 C. V[top] =x 。1 若棧采用順序存儲(chǔ)方式存儲(chǔ)，現(xiàn)兩棧共享空間V[1..m]，top[i]代表第i個(gè)棧( i =1,2)棧頂，棧1的底在v[1]，棧2的底在V[m]，則棧滿的條件是（ ）?！灸暇├砉ご髮W(xué) 2001 一、2（）】A．a(chǎn)bcd*+ B. abc+*d C. abc*+d D. +*abcd二、 填空題在棧中，可進(jìn)行插入和刪除操作的一端稱( )。當(dāng)棧中元素為n個(gè),作進(jìn)棧運(yùn)算時(shí)發(fā)生上溢,則說(shuō)明該棧的最大容量為( 　　　)。由于鏈棧的操作只在鏈表頭部進(jìn)行，所以沒(méi)有必要設(shè)置(　　　)結(jié)點(diǎn)。設(shè)元素入棧的順序是１、２、…、n ，則所有可能的出棧序列共有（　　　?。┓N。設(shè)有一個(gè)空棧，棧頂指針為1000H(十六進(jìn)制)，現(xiàn)有輸入序列為1，2，3，4，5，經(jīng)過(guò)PUSH,PUSH,POP,PUSH,POP,PUSH,PUSH之后，輸出序列是( )，而棧頂指針值是( )H。 三、 問(wèn)答題與算法題 設(shè)將整數(shù)1，2，3，4依次進(jìn)棧，若入、出棧次序?yàn)镻ush(s,1), Pop(s,x1),Push(s,2),Push(s,3), Pop(s,x2), Pop(s,x3),Push(s,4), Pop(s,x4 ),則出棧的數(shù)字序列為何?設(shè)用不帶頭結(jié)點(diǎn)的單鏈表表示棧，請(qǐng)分別寫(xiě)出入棧和出棧的算法。s SelemType e) (2) int pop_L(Linkstack amp。e) 假設(shè)用帶頭結(jié)點(diǎn)的單循環(huán)鏈表表示隊(duì)列，并設(shè)置一個(gè)指向尾結(jié)點(diǎn)的指針（無(wú)頭指針），請(qǐng)分別寫(xiě)出隊(duì)列的入隊(duì)和出隊(duì)算法。QL QelemType e) (2)int DeQueue_L(Queueptr amp。e)指出下述程序段的功能是什么?S){　　 int i， arr[64] , n=0 。arr[n++]=e}。 i++) Push(S, arr[i])。 S2)?！hile ( ! StackEmpty (S1))　　 　{pop(S1,x)?！　　　　 while ( ! StackEmpty (tmp) )　　 　{Pop( tmp,x)。 Push( S2, x)。S, int m)　　　 while (! StackEmpty( S))　　　　　{ Pop(S,e)。 }　　　　while (! StackEmpty( T))　　　　　{Pop(T,e)。}　　　}(4) void abc4( Queue amp?！hile (! QueueEmpty( Q ))　{DeQueue( Q,x)。}　　while (! StackEmpty( S))　　{ Pop(S,x)。}　　}(5) void invert1( LinkList amp。{ p=L。 while(p) //鏈表中的元素全部進(jìn)棧{push(S,pdata)。}p=L。 pdata=e。}return OK。試寫(xiě)一個(gè)算法判定給定的用帶頭結(jié)點(diǎn)的單鏈表表示的字符串是否為回文。Int hw1(linklist L)寫(xiě)一個(gè)將不帶頭結(jié)點(diǎn)的鏈棧S中所有結(jié)點(diǎn)均刪去的算法void ClearStack( LinkStack amp。寫(xiě)一個(gè)返回不帶頭結(jié)點(diǎn)的鏈棧S中結(jié)點(diǎn)個(gè)數(shù)的算法.int Stacksize( LinkStack S)。void invert2( LinkList amp。試將下列遞歸過(guò)程改寫(xiě)為非遞歸過(guò)程。sum) { int x； scanf(x)； if(x=0) sum=0 else {test(sum)。} printf(sum)； } 從鍵盤(pán)上輸入一個(gè)逆波蘭表達(dá)式，用偽碼寫(xiě)出其求值程序。例如：234 34+2*$第四章 串一、 選擇題 串是一種特殊的線性表，其特殊性體現(xiàn)在( 　)。A) 可以順序存儲(chǔ) 　 　B) 數(shù)據(jù)元素是一個(gè)字符 C) 可以鏈接存儲(chǔ) 　　 D) 數(shù)據(jù)元素可以是多個(gè)字符有兩個(gè)串P和Q，求P在Q中首次出現(xiàn)的位置的運(yùn)算稱(　　 )。A ) 模式匹配　　 B) 連接　 C) 求子串 　 　D) 求串長(zhǎng)設(shè)S為一個(gè)長(zhǎng)度為n的字符串，其中的字符各不相同，則S中的互異的非平凡子串（非空且不同于S本身）的個(gè)數(shù)為（ ）。ABCDEFG39。PQRST39。 A) BCDEF　 　 B) BCDEFG 　　 C) BCPQRST　　 　 D) BCDEFEF順序串中，根據(jù)空間分配方式的不同，可分為( )。A) 直接分配和間接分配 C) 順序分配和鏈?zhǔn)椒峙?A) 8 ； B) 37； C) 36； D) 35。A) O(m) ； B) O(n)； C) O(m+n)； D) O(n* m)。A．0123 B．1123 C．1231 D．1211二、 填空題 在空串和空格串中，長(zhǎng)度不為0的是( )。按存儲(chǔ)結(jié)構(gòu)不同，串可分為( )、（ ）、（ ）。在塊鏈串中，為了提高存儲(chǔ)密度，應(yīng)該增大( ).假設(shè)每個(gè)字符占1個(gè)字節(jié)，若結(jié)點(diǎn)大小為4的鏈串的存儲(chǔ)密度為50%，則其每個(gè)指針占( 　)個(gè)字節(jié)。設(shè)串S=’Ilikeputer .’，T=’’，則Length (S ) = （ ）。字符串’ababaaab’的nextval函數(shù)值為（ ）。12．實(shí)現(xiàn)字符串拷貝的函數(shù) strcpy為： void strcpy(char *s , char *t) /*copy t to s*/{ while ( ________ ) ； } 三、 問(wèn)答題與算法題 簡(jiǎn)述下列每對(duì)術(shù)語(yǔ)的區(qū)別：空串和空格串：串常量和串變量：主串和子串：目標(biāo)串和模式串。 strcat(s3,)。 　(２)調(diào)用函數(shù)strcmp(s1,s2)的返回值是什么? 　(３)調(diào)用函數(shù)strcmp(s1[5],Ton)的返回值是什么? 　(４)調(diào)用函數(shù)strlen(strcat(s1,s2))的返回值是什么? ３、 利用C的庫(kù)函數(shù)strlen,strcpy和strcat寫(xiě)一算法void StrInsert(char *S, char *T, int i),將串T插入到串S的第i個(gè)位置上。void StrInsert(char *S, char *T, int i)利用C的庫(kù)函數(shù)strlen 和strcpy(或strcpy)寫(xiě)一算法void StrDelete(char *S,int i, int m)刪去串S中從位置i開(kāi)始的連續(xù)m個(gè)字符。void StrDelete(char *S, int i ,int m) //串刪除若S和T是用結(jié)點(diǎn)大小為1的帶頭結(jié)點(diǎn)的單鏈表存儲(chǔ)的兩個(gè)串，試設(shè)計(jì)一個(gè)算法找出S中第一個(gè)不在T中出現(xiàn)的字符。（1） ‘a(chǎn)baabcac’ （2）’aaabaaba’設(shè)目標(biāo)為t=‘a(chǎn)bcaabbabcabaacbacba’,模式為p=‘a(chǎn)bcabaa’（1）計(jì)算模式p的naxtval函數(shù)值；（2）不寫(xiě)出算法,只畫(huà)出利用KMP算法進(jìn)行模式匹配時(shí)每一趟的匹配過(guò)程。第五章 數(shù)組與廣義表一、 選擇題稀疏矩陣的一般壓縮方法是( )。A) 二維數(shù)組 B) 廣義表 C) 三元組表 D) 一維數(shù)組設(shè)矩陣A是一個(gè)對(duì)稱矩陣，為了節(jié)省空間，將其下三角部分按行優(yōu)先存放在一維數(shù)組B中。 C) 矩陣中非零元素的行號(hào)和列號(hào) D) 矩陣中非零元素的行號(hào)、列號(hào)和值對(duì)稀疏矩陣進(jìn)行壓縮存儲(chǔ)是為了( 　)。A) 便于進(jìn)行矩陣運(yùn)算 B) 便于輸入和輸出 C) 節(jié)約存儲(chǔ)空間 D) 降低運(yùn)算的時(shí)間復(fù)雜度 假設(shè)以行序?yàn)橹餍虼鎯?chǔ)二維數(shù)組A=array[1..100，1..100]，設(shè)每個(gè)數(shù)據(jù)元素占2個(gè)存儲(chǔ)單元，基地址為10，則LOC[5，5]=（ ）。A） BA+141 B） BA+180 C） BA+222 D） BA+225廣義表是線性表的推廣，它們之間的區(qū)別在于(　　 )。A) 能否使用子表 　B) 能否使用原子項(xiàng) 　 D) 是否能為空已知廣義表L=（（x,y,z），a，（u，t，w）），從L表中取出原子項(xiàng)t的運(yùn)算是（ ）。A）（a） B） A C） a D） (b) E） b F） (A) 廣義表運(yùn)算式Tail(((a,b),(c,d)))的操作結(jié)果是（ ）。A） a B）（） C）（a,b,c,d） D）（b,c,d）1設(shè)廣義表L=（（a,b,c）），則L的長(zhǎng)度和深度分別為（ ）。 A） 廣義表的表頭總是一個(gè)廣義表 B） 廣義表的表尾總是一個(gè)廣義表C） 廣義表難以用順序存儲(chǔ)結(jié)構(gòu) D） 廣義表可以是一個(gè)多層次的結(jié)構(gòu)1已知廣義表LS＝((a,b,c),(d,e,f)),運(yùn)用head和tail函數(shù)取出LS中原子e的運(yùn)算是( )。 A) O(1) B) O(n) C) O(n2) D) O(log2n)二、 填空題n維數(shù)組中的每個(gè)元素都最多有( )個(gè)直接前趨。已知二維數(shù)組A[m][n]采用行優(yōu)先順序存儲(chǔ)，每個(gè)元素占k個(gè)存儲(chǔ)單元，并且第一個(gè)元素的存儲(chǔ)地址LOC（A[0][0]），則A[i][j]的地址是( )。因此，數(shù)組是一種( )存取結(jié)構(gòu)。遞歸是算法設(shè)計(jì)的重要方法，遞歸由（ ）項(xiàng)和（ ）項(xiàng)構(gòu)成。 基本項(xiàng)：遞歸項(xiàng)： 廣義表( a , ( a , b ) , d , e , ((i , j ) , k ) ) 的長(zhǎng)度是（ ），深度是（ ）。設(shè)廣義表S=((a , b) , ( c , d))，GetHeat(S)和GetTail(S)是取廣義表的表頭和表尾函數(shù)。設(shè)廣義表S=(a , b , ( c , d) , (e , (f , g )))，GetHeat(S)和GetTail(S)是取廣義表的表頭和表尾函數(shù)。(設(shè)a[0][0][0]的地址是1000,數(shù)據(jù)以行為主方式存儲(chǔ))1設(shè)有二維數(shù)組A[0..9,0..19],其每個(gè)元素占兩個(gè)字節(jié)，第一個(gè)