緒論習(xí)題一、填空題計(jì)算機(jī)識(shí)別、存儲(chǔ)和加工處理的對(duì)象統(tǒng)稱為數(shù)據(jù)。數(shù)據(jù)結(jié)構(gòu)被定義為（D，R），其中D是數(shù)據(jù)的有限集合，R是D上的關(guān)系有限集合。數(shù)據(jù)結(jié)構(gòu)以不同視角，可以分為邏輯結(jié)構(gòu)和物理結(jié)構(gòu)兩種結(jié)構(gòu)。數(shù)據(jù)結(jié)構(gòu)按邏輯結(jié)構(gòu)可分為兩大類，它們是線性結(jié)構(gòu)和非線性結(jié)構(gòu)。數(shù)據(jù)結(jié)構(gòu)是指數(shù)據(jù)及其相互之間的關(guān)系的集合。當(dāng)結(jié)點(diǎn)之間存在M對(duì)N(M:N)的聯(lián)系時(shí)，稱這種關(guān)系為網(wǎng)狀結(jié)構(gòu)。當(dāng)結(jié)點(diǎn)之間存在1對(duì)N(1:N)的聯(lián)系時(shí)，稱這種結(jié)構(gòu)為層次結(jié)構(gòu)。從數(shù)據(jù)結(jié)構(gòu)的觀點(diǎn)，數(shù)據(jù)通常可分為三個(gè)層次，即數(shù)據(jù)、數(shù)據(jù)元素和數(shù)據(jù)對(duì)象。數(shù)據(jù)物理結(jié)構(gòu)被分為順序存儲(chǔ)、鏈?zhǔn)酱鎯?chǔ)、散列存儲(chǔ)和索引存儲(chǔ)四種。算法是對(duì)求解問題的一種描述，是指令的有限序列。對(duì)算法從時(shí)間和空間兩方面進(jìn)行度量，分別稱為時(shí)間復(fù)雜度和空間復(fù)雜度分析。算法效率的度量可以分為事先估算法和事后統(tǒng)計(jì)法。若一個(gè)算法中的語句頻度之和為T(n)=4n2+3nlog2n，則算法的時(shí)間復(fù)雜度為O(n2)。若一個(gè)算法中的語句頻度之和為T(n)=4n2+3n+2n，則算法的時(shí)間復(fù)雜度為O(2n)。程序for(i=1,t=1,s=0;i<=n;i++){t=t*i;s=s+t;}的時(shí)間復(fù)雜度為O(n)。當(dāng)輸入不合法數(shù)據(jù)時(shí)，應(yīng)能作適當(dāng)處理，不致引起嚴(yán)重后果，是指算法的健壯性特性。二、選擇題數(shù)據(jù)結(jié)構(gòu)通常是研究數(shù)據(jù)的(A)及它們之間的相互關(guān)系。A．存儲(chǔ)結(jié)構(gòu)和邏輯結(jié)構(gòu)B．存儲(chǔ)和抽象C．聯(lián)系和抽象D．聯(lián)系與邏輯數(shù)據(jù)在計(jì)算機(jī)存儲(chǔ)內(nèi)表示時(shí)，物理地址和邏輯地址相同并且是連續(xù)的，稱之為(A)。A．順序存儲(chǔ)結(jié)構(gòu)B．鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)C．邏輯結(jié)構(gòu)D．物理結(jié)構(gòu)鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)所占存儲(chǔ)空間(A)。A．分兩部分，一部分存放結(jié)點(diǎn)的值，另一個(gè)部分存放表示結(jié)點(diǎn)間關(guān)系的指針。B．只有一部分，存放結(jié)點(diǎn)的值。C．只有一部分，存儲(chǔ)表示結(jié)點(diǎn)間關(guān)系的指針。D．分兩部分，一部分存放結(jié)點(diǎn)的值，另一部分存放結(jié)點(diǎn)所占單元素線性表采用鏈?zhǔn)酱鎯?chǔ)時(shí)，其地址(D)。A．必須是連續(xù)的B.部分地址必須是連續(xù)的C.一定是不連續(xù)的D.連續(xù)與否均可以與數(shù)據(jù)元素本身的形式、內(nèi)容、相對(duì)位置、個(gè)數(shù)無關(guān)的是數(shù)據(jù)的(C)。A．存儲(chǔ)結(jié)構(gòu)

B．存儲(chǔ)實(shí)現(xiàn)C．邏輯結(jié)構(gòu)

D．運(yùn)算實(shí)現(xiàn)在數(shù)據(jù)結(jié)構(gòu)中，從邏輯上可以把數(shù)據(jù)結(jié)構(gòu)劃分成(C)。A．動(dòng)態(tài)結(jié)構(gòu)和靜態(tài)結(jié)構(gòu)

B．緊湊結(jié)構(gòu)和非緊湊結(jié)構(gòu)C．線性結(jié)構(gòu)和非線性結(jié)構(gòu)

D．內(nèi)部結(jié)構(gòu)和外部結(jié)構(gòu)通常要求同一邏輯結(jié)構(gòu)中的所有數(shù)據(jù)元素具有相同的特性，這意味著(B)。A．?dāng)?shù)據(jù)具有同一特點(diǎn)B．不僅數(shù)據(jù)元素所包含的數(shù)據(jù)項(xiàng)的個(gè)數(shù)要相同，而且對(duì)應(yīng)數(shù)據(jù)項(xiàng)的類型要一致C．每個(gè)數(shù)據(jù)元素都一樣D．?dāng)?shù)據(jù)元素所包含的數(shù)據(jù)項(xiàng)的個(gè)數(shù)要相等在數(shù)據(jù)結(jié)構(gòu)中，與所使用的計(jì)算機(jī)無關(guān)的是(C)。A．物理結(jié)構(gòu)B．存儲(chǔ)結(jié)構(gòu)C．邏輯結(jié)構(gòu)D．邏輯和存儲(chǔ)結(jié)構(gòu)算法的時(shí)間復(fù)雜度與(B)有關(guān)。A.計(jì)算機(jī)硬件性能B.問題規(guī)模C.內(nèi)存芯片的有關(guān)參數(shù)D.編譯程序質(zhì)量算法分析的兩個(gè)主要方面是(A)。A.空間復(fù)雜性和時(shí)間復(fù)雜性B.正確性和簡(jiǎn)明性C.可讀性和文檔性D.數(shù)據(jù)復(fù)雜性和程序復(fù)雜性數(shù)據(jù)結(jié)構(gòu)的定義為(D，S)，其中D是(B)的集合。A.?算法????B.數(shù)據(jù)元素???C.?數(shù)據(jù)操作???D.?邏輯結(jié)構(gòu)下面程序段的時(shí)間復(fù)雜度為(C)。for(inti=0;i<m;i++)for(intj=0;j<n;j++)a[i][j]=i*j;A.O(m2)B.O(n2)C.O(m*n)?D.O(m+n)下面程序段的時(shí)間復(fù)雜度為(C)。s=0;for(i=1;i<=n;i++){for(j=n;j>=n-1;j--) s=s+1;}A．O(n)B．O(nlog2n)C．O(n2)D．O(n3/2)下列時(shí)間復(fù)雜度中最壞的是(D)。A．O(1)B．O(n)C．O((log2n)D．O(n2)下面是關(guān)于兩個(gè)矩陣加法的算法實(shí)現(xiàn)，其時(shí)間復(fù)雜度是(D)。for(i=0;i<n;i++)for(j=0;i<n;j++)c[i][j]=a[i][j]+b[i][j];A．O(1)B．O(n)C．O(log2n)D．O(n2)三、簡(jiǎn)答題說明數(shù)據(jù)、數(shù)據(jù)元素、數(shù)據(jù)項(xiàng)之間的關(guān)系。答：數(shù)據(jù)是信息的載體，它是能夠被計(jì)算機(jī)識(shí)別、存儲(chǔ)和加工處理的對(duì)象。數(shù)據(jù)元素是數(shù)據(jù)結(jié)構(gòu)中討論的基本單位，是數(shù)據(jù)集合中的個(gè)體。一個(gè)數(shù)據(jù)元素可由若干個(gè)數(shù)據(jù)項(xiàng)組成，多個(gè)數(shù)據(jù)項(xiàng)構(gòu)成數(shù)據(jù)元素，每一個(gè)數(shù)據(jù)項(xiàng)都是不可再分割的。解釋數(shù)據(jù)結(jié)構(gòu)、邏輯結(jié)構(gòu)、存儲(chǔ)結(jié)構(gòu)之間的聯(lián)系與區(qū)別。答：數(shù)據(jù)結(jié)構(gòu)從不同視角可以劃分為邏輯結(jié)構(gòu)與存儲(chǔ)結(jié)構(gòu)，邏輯結(jié)構(gòu)指的是數(shù)據(jù)間的關(guān)系，它又分為線性結(jié)構(gòu)和非線性結(jié)構(gòu),而存儲(chǔ)結(jié)構(gòu)是邏輯結(jié)構(gòu)的存儲(chǔ)映像。這兩者并不沖突，一個(gè)指的是數(shù)據(jù)之間的關(guān)系，而另一個(gè)指這種關(guān)系在計(jì)算機(jī)中的表示形式。算法的特性有哪些？答：有窮性、確定性、可行性、輸入和輸出。簡(jiǎn)述數(shù)據(jù)結(jié)構(gòu)上的基本操作主要有哪些。答：

查找、插入、刪除、更新和輸出。簡(jiǎn)述時(shí)間復(fù)雜度和空間復(fù)雜度主要與哪些因素有關(guān)。答：時(shí)間復(fù)雜度與算法本身的性質(zhì)即算法中控制結(jié)構(gòu)和原操作有關(guān)，算法本身的性質(zhì)又包括其涉及的問題規(guī)模。同時(shí)算法還有與選擇的何種算法策略有關(guān)。空間復(fù)雜度與所處理數(shù)據(jù)結(jié)點(diǎn)的大小和個(gè)數(shù)有關(guān)，同時(shí)與算法在某次執(zhí)行中處理的特定數(shù)據(jù)的大小和規(guī)模有關(guān)。當(dāng)一個(gè)算法被轉(zhuǎn)換成程序并在計(jì)算機(jī)上執(zhí)行時(shí)，其運(yùn)行所需要的時(shí)間一般取決于哪些因素？答：因素有算法選用何種策略、問題的規(guī)模、程序設(shè)計(jì)的語言、編譯程序所產(chǎn)生的機(jī)器代碼的質(zhì)量和機(jī)器執(zhí)行指令的速度。四、算法分析題分析下面語句段執(zhí)行的時(shí)間復(fù)雜度。for(i=1;i<=n;i++)for(j=1;j<=n;j++)s++;答：時(shí)間復(fù)雜度為：O(n2)。分析下面語句段執(zhí)行的時(shí)間復(fù)雜度。for(i=1;i<=n;i++)for(j=1;j<=i;j++)s++;答：時(shí)間復(fù)雜度為：O(n2)。分析下面語句段執(zhí)行的時(shí)間復(fù)雜度。i=1;k=0;while(i<=n-1){k+=10*i;i++;答：時(shí)間復(fù)雜度為：O(n)。}分析下面語句段執(zhí)行的時(shí)間復(fù)雜度。for(i=1;i<=n;i++)for(j=1;j<=i;j++)for(k=1;k<=j;k++)x=x+1;答：時(shí)間復(fù)雜度為：O(n3)。線性表習(xí)題填空題順序表是指邏輯上相鄰的元素在物理位置上相鄰。線性表中結(jié)點(diǎn)間的關(guān)系是1:1關(guān)系。順序表中提取任意位置的元素，不需要從頭到尾查找，因?yàn)轫樞虮砭哂须S機(jī)定位的特點(diǎn)。線性表的元素總數(shù)基本穩(wěn)定，且很少進(jìn)行插入和刪除操作，但要求以最快速度存取線性表中的元素時(shí)，應(yīng)采用順序存儲(chǔ)結(jié)構(gòu)。順序表中訪問某個(gè)數(shù)值的元素，其時(shí)間復(fù)雜度均為O(1)。在長(zhǎng)度為n的順序表中，插入一個(gè)結(jié)點(diǎn)，其平均移動(dòng)元素的個(gè)數(shù)為n/2。在長(zhǎng)度為n的順序表中，刪除結(jié)點(diǎn)的時(shí)間復(fù)雜度為O(n)。如果線性表需要頻繁進(jìn)行數(shù)據(jù)的插入與刪除操作，則適合鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)。鏈表相對(duì)于順序表的優(yōu)點(diǎn)是插入、刪除方便，不需要移動(dòng)數(shù)據(jù)元素。在雙向鏈表中要?jiǎng)h除已知結(jié)點(diǎn)p，其時(shí)間復(fù)雜度為O(1)。在單向鏈表中要在已知結(jié)點(diǎn)p之后插入一個(gè)新結(jié)點(diǎn)，其時(shí)間復(fù)雜度為O(1)。在單向鏈表中要在已知結(jié)點(diǎn)p之前插入一個(gè)新結(jié)點(diǎn)，其時(shí)間復(fù)雜度為O(n)。在雙鏈表中，每個(gè)結(jié)點(diǎn)有兩個(gè)指針域，一個(gè)指向前驅(qū)結(jié)點(diǎn)，另一個(gè)指向后繼結(jié)點(diǎn)。在單鏈表中設(shè)置頭結(jié)點(diǎn)的作用是便于鏈表上操作的統(tǒng)一性。雙向循環(huán)鏈表中，在p所指的結(jié)點(diǎn)之后插入指針f所指的結(jié)點(diǎn)，其操作為f->rear=p->rear;f->front=p;f->rear->front=f;p->rear=f。選擇題線性表采用鏈?zhǔn)酱鎯?chǔ)時(shí)，其地址(D)。A.必須是連續(xù)的B.部分地址必須是連續(xù)的C.一定是不連續(xù)的D.連續(xù)與否均可以用單鏈表方式存儲(chǔ)的線性表，存儲(chǔ)每個(gè)結(jié)點(diǎn)需要兩個(gè)域，一個(gè)是數(shù)據(jù)域，另一個(gè)是(B)。A.當(dāng)前結(jié)點(diǎn)所在的地址域B.指針域C.空指針域D.空閑域單向鏈表的存儲(chǔ)密度(C)。A.大于1B.等于1C.小于1D.不能確定已知一個(gè)順序存儲(chǔ)的線性表，設(shè)每個(gè)結(jié)點(diǎn)占m個(gè)存儲(chǔ)單元，若第一個(gè)結(jié)點(diǎn)的地址為B，則第i個(gè)結(jié)點(diǎn)的地址為(A)。A.B+(i-1)×mB.B+i×mC.B-i×mD.B+(i+1)×m不帶頭結(jié)點(diǎn)的單鏈表head為空的判斷條件是(A)。A.head==NULLB.head>next==NULLC.head->data==NULLD.head!=NULL設(shè)front，rear分別為循環(huán)雙向鏈表結(jié)點(diǎn)的左指針和右指針，則指針p所指的元素是雙循環(huán)鏈表head的尾元素的條件是(D)。A.p==headB.p->front==headC.p==NULLD.p->rear==head在一個(gè)單鏈表中，已知q所指結(jié)點(diǎn)是p所指結(jié)點(diǎn)的前驅(qū)結(jié)點(diǎn)，若在p和q之間插入s結(jié)點(diǎn)，則執(zhí)行(A)。A.s->next=p;q->next=s；B.p->next=s->next；s->next=p；C.p->next=s->next；s->next=p；D.p->next=s；p->next=s；兩個(gè)指針p和q，分別指向單向鏈表的兩個(gè)元素，p是q的前驅(qū)條件是(B)。A．p->next==q->nextB.p->next==qC.q->next==pD.p==q用鏈表存儲(chǔ)的線性表，其優(yōu)點(diǎn)是(C)。A．便于隨機(jī)存取B．花費(fèi)的存儲(chǔ)空間比順序表少C．便于插入和刪除D．?dāng)?shù)據(jù)元素的物理順序與邏輯順序相同一個(gè)單鏈表中，若刪除p所指結(jié)點(diǎn)的后繼結(jié)點(diǎn)，則執(zhí)行(A)。A.p=p->next->next；B.p=p->next；p->next=p->next->next；C.p->next=p；D.p=p->next->next；在n個(gè)結(jié)點(diǎn)的順序表中，算法的時(shí)間復(fù)雜度是O(1)的操作是(A)。A.訪問第i個(gè)結(jié)點(diǎn)(1≤i≤n)和求第i個(gè)結(jié)點(diǎn)的直接前驅(qū)(2≤i≤n)B.在第i個(gè)結(jié)點(diǎn)后插入一個(gè)新結(jié)點(diǎn)(1≤i≤n)C.刪除第i個(gè)結(jié)點(diǎn)(1≤i≤n)D.將n個(gè)結(jié)點(diǎn)從小到大排序用鏈表表示線性表的優(yōu)點(diǎn)是(B)。A.便于隨機(jī)存取B.便于進(jìn)行插入和刪除操作C.占用的存儲(chǔ)空間較順序表少D.元素的物理順序與邏輯順序相同下面關(guān)于線性表的敘述中，錯(cuò)誤的是(B)。A.線性表采用順序存儲(chǔ)必須占用一片連續(xù)的存儲(chǔ)單元B.線性表采用順序存儲(chǔ)便于進(jìn)行插入和刪除操作C.線性表采用鏈?zhǔn)酱鎯?chǔ)不必占用一片連續(xù)的存儲(chǔ)單元D.線性表采用鏈?zhǔn)酱鎯?chǔ)便于進(jìn)行插入和刪除操作在下列鏈表中不能從當(dāng)前結(jié)點(diǎn)出發(fā)訪問到其余各結(jié)點(diǎn)的是(C)。A.雙向鏈表B.單循環(huán)鏈表C.單向鏈表D.雙向循環(huán)鏈表在順序表中，只要知道(D)，就可以求出任一結(jié)點(diǎn)的存儲(chǔ)地址。A.任意位置結(jié)點(diǎn)地址B.結(jié)點(diǎn)大小C.向量大小D.基地址和結(jié)點(diǎn)大小簡(jiǎn)答題線性表有兩種存儲(chǔ)結(jié)構(gòu)：一是順序表，二是鏈表，簡(jiǎn)述它們各自的優(yōu)缺點(diǎn)。答：順序表的存儲(chǔ)結(jié)構(gòu)是使用連續(xù)的存儲(chǔ)空間存儲(chǔ)數(shù)據(jù)元素，優(yōu)點(diǎn)是隨機(jī)訪問速度快，可以通過下標(biāo)直接訪問元素，缺點(diǎn)是插入和刪除操作需要移動(dòng)大量元素，空間利用率低。鏈表的存儲(chǔ)結(jié)構(gòu)是使用指針將數(shù)據(jù)元素鏈接在一起，優(yōu)點(diǎn)是插入和刪除操作方便高效，不需要移動(dòng)大量元素，缺點(diǎn)是訪問元素需要遍歷鏈表，時(shí)間復(fù)雜度較高。試描述頭指針，頭結(jié)點(diǎn)開始結(jié)點(diǎn)的區(qū)別，并說明頭指針和頭結(jié)點(diǎn)的作用。答：頭指針是指向鏈表頭部的指針變量，用來記錄鏈表的起始位置。頭結(jié)點(diǎn)是在鏈表頭部之前增加的一個(gè)結(jié)點(diǎn)，用來存儲(chǔ)一些附加信息，如鏈表長(zhǎng)度等。頭指針的作用是用來操作鏈表的各種操作，而頭結(jié)點(diǎn)的作用是為鏈表的操作提供方便，可以避免一些特殊情況的處理。何時(shí)選用順序表，何時(shí)選用鏈表作為線性表的存儲(chǔ)結(jié)構(gòu)為宜?答：選擇順序表還是鏈表作為線性表的存儲(chǔ)結(jié)構(gòu)，取決于實(shí)際需求。當(dāng)線性表的長(zhǎng)度固定且需要頻繁隨機(jī)訪問元素時(shí)，使用順序表更合適。當(dāng)線性表的長(zhǎng)度不固定且需要頻繁插入、刪除操作時(shí)，使用鏈表更合適。另外，順序表的存儲(chǔ)需要連續(xù)的存儲(chǔ)空間，而鏈表的存儲(chǔ)可以靈活利用存儲(chǔ)空間。在單鏈表，雙鏈表和單循環(huán)鏈表中，若僅知道指針p指向某結(jié)點(diǎn)，不知道頭指針，能否將結(jié)點(diǎn)p從相應(yīng)的鏈表中刪去？若可以，其時(shí)間復(fù)雜度各為多少?答：如果僅知道指針p指向某個(gè)結(jié)點(diǎn)，不知道頭指針，是無法直接刪除結(jié)點(diǎn)p的，因?yàn)闊o法找到待刪除結(jié)點(diǎn)的前一個(gè)結(jié)點(diǎn)。需要知道頭指針才能進(jìn)行刪除操作。時(shí)間復(fù)雜度為O(n)，其中n為鏈表的長(zhǎng)度，需要遍歷整個(gè)鏈表來找到待刪除結(jié)點(diǎn)的前一個(gè)結(jié)點(diǎn)。在順序表中插入和刪除個(gè)結(jié)點(diǎn)需要平均移動(dòng)多少個(gè)結(jié)點(diǎn)?具體的移動(dòng)次數(shù)取決于哪兩個(gè)因素?答：在順序表中插入和刪除一個(gè)結(jié)點(diǎn)，平均分別需要移動(dòng)n/2和(n-1)/2個(gè)結(jié)點(diǎn)，其中n為順序表的長(zhǎng)度。具體的移動(dòng)次數(shù)取決于插入或刪除操作的位置和順序表中元素的個(gè)數(shù)。插入操作需要移動(dòng)插入位置之后的元素，刪除操作需要移動(dòng)刪除位置之后的元素。算法設(shè)計(jì)題已知順序表L，寫一算法將其倒置，例如倒置前為3,6,2,1,7,9，倒置后為9,7,1,2,6,3。答：參照算法2-20鏈表倒置的算法，只需要在遍歷順序表過程中將順序表中的元素按照前后位置交換即可。設(shè)有帶頭結(jié)點(diǎn)的單向鏈表，head為指向頭結(jié)點(diǎn)的指針。設(shè)計(jì)算法：實(shí)現(xiàn)在值為key的結(jié)點(diǎn)前插入值為y的結(jié)點(diǎn)。若值為key結(jié)點(diǎn)不存在，則將值為y的結(jié)點(diǎn)插在鏈表的最后，作為尾結(jié)點(diǎn)。答：voidinsertNode(ListNode*head,intkey,inty){ListNode*prev=head;ListNode*curr=head->next;//遍歷鏈表，找到值為key的結(jié)點(diǎn)或鏈表的最后一個(gè)結(jié)點(diǎn)while(curr!=null&&curr->data!=key){prev=curr;curr=curr->next;}//創(chuàng)建新的結(jié)點(diǎn)ListNode*newNode=newListNode(y);newNode->next=curr;//在值為key的結(jié)點(diǎn)前插入新的結(jié)點(diǎn)prev->next=newNode;//如果curr為空，說明key不存在，將新結(jié)點(diǎn)插在鏈表的最后if(curr==NULL){prev->next=newNode;}}編寫算法，刪除單鏈表的表頭結(jié)點(diǎn)與表尾結(jié)點(diǎn)。答：參考算法2-14鏈表中刪除指定值的結(jié)點(diǎn)的算法。寫出函數(shù)用于刪除元素遞增排列的帶頭結(jié)點(diǎn)單鏈表L中值大于min且小于max的所有元素，并給出其時(shí)間復(fù)雜度。答：voiddeleteRange(ListNode*head,intmin,intmax){ListNode*prev=head;ListNode*curr=head->next;while(curr!=null){if(curr->val>min&&curr->val<max){prev->next=curr->next;deletecurr;curr=prev->next;}else{prev=curr;curr=curr->next;}}}設(shè)單向鏈表中結(jié)點(diǎn)按有序鏈接，設(shè)計(jì)算法：刪除鏈表中值相同的結(jié)點(diǎn)，使之只保留一個(gè)。答：參考算法2-21鏈表刪除重復(fù)結(jié)點(diǎn)的算法。對(duì)給定的帶頭結(jié)點(diǎn)的單鏈表L，編寫一個(gè)刪除L中值為key的結(jié)點(diǎn)的直接前驅(qū)結(jié)點(diǎn)的算法。答：參考2-14鏈表中刪除指定值的結(jié)點(diǎn)的算法。有兩個(gè)循環(huán)單鏈表，鏈頭指針分別為head1和head2，編寫一個(gè)函數(shù)將鏈表head1鏈接到鏈表head2，鏈接后的鏈表仍是循環(huán)鏈表。答：voidlinkCircularLists(ListNode*head1,ListNode*head2){ListNode*curr1=head1->next;ListNode*curr2=head2->next;while(curr1->next!=head1){curr1=curr1->next;}while(curr2->next!=head2){curr2=curr2->next;}curr1->next=head2;curr2->next=head1;}有一個(gè)由整數(shù)構(gòu)成的單鏈表長(zhǎng)度為n，試編寫算法，將單鏈表分解成兩個(gè)，一個(gè)只由奇數(shù)構(gòu)成，另一個(gè)只由偶數(shù)構(gòu)成。答：voidsplitOddEven(ListNode*head,ListNode**oddHead,ListNode**evenHead){ListNode*oddTail=null;ListNode*evenTail=null;ListNode*curr=head;while(curr!=null){if(curr->data%2==0){//當(dāng)前節(jié)點(diǎn)的值為偶數(shù)if(*evenHead==null){//如果evenHead為空，說明是第一個(gè)偶數(shù)節(jié)點(diǎn)*evenHead=curr;evenTail=curr;}else{//否則，將當(dāng)前偶數(shù)節(jié)點(diǎn)鏈接到偶數(shù)鏈表的末尾evenTail->next=curr;evenTail=curr;}}else{//當(dāng)前節(jié)點(diǎn)的值為奇數(shù)if(*oddHead==null){//如果oddHead為空，說明是第一個(gè)奇數(shù)節(jié)點(diǎn)*oddHead=curr;oddTail=curr;}else{//否則，將當(dāng)前奇數(shù)節(jié)點(diǎn)鏈接到奇數(shù)鏈表的末尾oddTail->next=curr;oddTail=curr;}}curr=curr->next;}//將奇數(shù)鏈表和偶數(shù)鏈表的末尾設(shè)置為null，表示鏈表的結(jié)束if(oddTail!=null){oddTail->next=null;}if(evenTail!=null){evenTail->next=null;}}設(shè)帶頭結(jié)點(diǎn)的單向鏈表，將鏈表中所有的偶數(shù)結(jié)點(diǎn)刪除。答：參照算法2-21鏈表刪除重復(fù)結(jié)點(diǎn)的算法。設(shè)某單鏈表中，存在多個(gè)結(jié)點(diǎn)其數(shù)據(jù)值均為key，試編寫一算法統(tǒng)計(jì)該類結(jié)點(diǎn)的個(gè)數(shù)。答：參照?qǐng)D2-9查找結(jié)點(diǎn)的算法，只需要將鏈表遍歷到尾部即可，遍歷的過程中進(jìn)行統(tǒng)計(jì)結(jié)點(diǎn)的個(gè)數(shù)。若循環(huán)單鏈表長(zhǎng)度大于1，p為指向鏈表中某結(jié)點(diǎn)的指針，試編寫一算法刪除p結(jié)點(diǎn)的前驅(qū)結(jié)點(diǎn)。答：參考2-14鏈表中刪除指定值的結(jié)點(diǎn)的算法。不同的是，不僅需要查找到P結(jié)點(diǎn)的前驅(qū)結(jié)點(diǎn)q，同時(shí)還需要查找q結(jié)點(diǎn)的前驅(qū)結(jié)點(diǎn)s，便于刪除q結(jié)點(diǎn)后，調(diào)整鏈表，也就是設(shè)置s的后繼結(jié)點(diǎn)變?yōu)閜。試寫一算法，將兩個(gè)有序表合并為一個(gè)有序表。答：參考2-17有序表合并的算法。棧習(xí)題填空題在棧結(jié)構(gòu)中，允許插入、刪除的一端稱為棧頂。棧是一種先進(jìn)后出線性表。在有n個(gè)元素的棧中，進(jìn)棧操作時(shí)間復(fù)雜度為O(1)。若進(jìn)棧的次序是A,B,C,D,E，執(zhí)行3次出棧操作以后，棧頂元素為B。三個(gè)元素6,8,4順序進(jìn)棧，執(zhí)行兩次Pop(s，x)運(yùn)算后，x的值是8。設(shè)有編號(hào)為1,2,3,4的四輛列車，順序開入棧式結(jié)構(gòu)的站臺(tái)，則可能的出棧序列有14種。一個(gè)棧的輸入序列是1,2,3,..,n，輸出序列的第一個(gè)元素是n，則第i個(gè)輸出元素為i。在順序棧中，當(dāng)棧頂指針的值為-1時(shí)，表示空棧。已知順序棧s，在對(duì)s進(jìn)棧操作之前首先要判斷棧滿。在順序棧中，當(dāng)有元素入棧時(shí)，首先棧頂指針加1，然后元素再入棧。在順序棧中，刪除元素，需要將棧頂指針減1。已知中綴表達(dá)式，求它的后綴表達(dá)式，是棧的典型應(yīng)用。在一個(gè)鏈?zhǔn)綏Ｖ校魲ｍ斨羔樀扔贜ULL則為空棧；向棧頂指針為top的鏈棧中插入結(jié)點(diǎn)時(shí)，應(yīng)該先判斷top是否為空。向一個(gè)棧頂指針為top的鏈棧中，插入一個(gè)新結(jié)點(diǎn)p時(shí)，應(yīng)執(zhí)行p->next=top和top=p的語句。從一個(gè)棧刪除元素時(shí)，首先取出棧頂元素，然后再移動(dòng)棧頂指針。向一個(gè)棧頂指針為top的鏈棧中，刪除結(jié)點(diǎn)，應(yīng)執(zhí)行s=top和top=top->next的語句。8+7-6/2+3^2-5的后綴表達(dá)式是87+62/-32^+5-。選擇題常用于函數(shù)調(diào)用的數(shù)據(jù)結(jié)構(gòu)是(A)。A．棧 B．隊(duì)列C．鏈表 D．?dāng)?shù)組在棧中進(jìn)行插入和刪除操作的位置是(A)。A．棧頂B．任意位置C．棧底D．與元素有關(guān)設(shè)一數(shù)列的輸入順序?yàn)?,2,3,4,5,6，通過棧操作不可能排成的輸出序列為(B)。A．3,2,5,6,4,1B．1,5,4,6,2,3C．2,4,3,5,1,6D．4,5,3,6,2,1如果以鏈表作為棧的存儲(chǔ)結(jié)構(gòu)，則出棧操作時(shí)(B)。A．必須判別棧是否滿B．必須判別棧是否為空C．必須判別棧元素類型D．棧不做任何判別順序棧存儲(chǔ)空間的實(shí)現(xiàn)使用(B)存儲(chǔ)元素。A．鏈表B．?dāng)?shù)組C．循環(huán)鏈表D．變量一個(gè)順序棧一旦被聲明，其占用空間的大小(A)。A．已固定B．不固定C．可以改變D．動(dòng)態(tài)變化鏈棧與順序棧相比，有一個(gè)比較明顯的優(yōu)點(diǎn)是(B)。A． 插入操作更加方便B．通常不會(huì)出現(xiàn)棧滿的情況C．不會(huì)出現(xiàn)棧空的情況D．刪除操作更加方便從棧頂指針為top的鏈棧中刪除一個(gè)結(jié)點(diǎn)時(shí)，用x保存被刪除的結(jié)點(diǎn)，應(yīng)執(zhí)行下列(D)語句。A．x=top;top->next;B．top=top->next;x=top->dataC．x=top->data;D．x=top->data;top=top->next在一個(gè)棧頂指針為HS的鏈棧中，將一個(gè)s指針?biāo)傅慕Y(jié)點(diǎn)入棧，應(yīng)執(zhí)行下列(C)語句。A．HS->next=sB．s->next=HS->next;HS->next=s;C．s->next=HS;HS=s;D．.s->next=HS=HS->next4個(gè)元素按A,B,C,D順序進(jìn)棧s，執(zhí)行兩次Pop(s，x)運(yùn)算后，棧頂元素的值是(B)。A．AB．BC．CD．D元素A,B,C,D依次進(jìn)棧以后，棧底元素是(A)。A．AB．BC．CD．D經(jīng)過InitStack(s)，Push(s，a)，Push(s，b)Pob(s)的運(yùn)算后，再執(zhí)行ReadTop(s)的值是(A)。A．a(chǎn)B．bC．1D．0經(jīng)過下列棧的運(yùn)算后，x的值是(B)。InitStack(s)（初始化棧）；Push(s，a)；Push(s，b)；ReadTop(s)；Pob(s，x)；A． aB．bC．1D．0經(jīng)過下列棧的運(yùn)算后，EmptySeque(s)的值是(C)。InitStack(s)；Push(s，a)；Push(s，b)；Pop(s，x)；Pop(s，x)；A．a(chǎn)B．bC．1D．0向順序棧中輸入元素時(shí)(B)。A．先存入元素，后移動(dòng)棧頂指針B．先移動(dòng)棧頂指針，后存入元素C．誰先誰后無關(guān)緊要D．同時(shí)進(jìn)行初始化一個(gè)空間大小為5的順序棧s后，s->top的值是(B)。A．0B．-1C．不再改變D．動(dòng)態(tài)變化設(shè)有一個(gè)入棧的次序A,B,C,D,E的序列，則棧不可能的輸出序列是(C)。A．EDCBAB．DECBAC．DCEABD．ABCDE設(shè)有一個(gè)順序棧s，元素A,B,C,D,E,F依次進(jìn)棧，如果6個(gè)元素出棧的順序是B,D,C,F,E,A，則棧的容量至少應(yīng)是(A)。A．3B．4C．5D．6綜合應(yīng)用題在棧的輸入端元素的輸入順序?yàn)?,2,3,4,5,6，進(jìn)棧過程中可以退棧，則退棧時(shí)能否排成序列3,2,5,6,4,1和1,5,4,6,2,3，若能，寫出進(jìn)棧、退棧過程；若不能，簡(jiǎn)述理由。采用用push(x)表示x進(jìn)棧，pop(x)表示x退棧。答：push(1)，push(2)，push(3)，pop(3)，pop(2)，push(4)，push(5)，pop(5)，push(6)，pop(6)，pop(4)，pop(1)。所以可以得到序列3,2,5,6,4,1。push(1)，pop(1)，push(2)，push(3)，push(4)，push(5)，pop(5)，pop(4)，push(6)，pop(6)，，下一個(gè)出棧的是3，而不是2，所以不能得到序列1,5,4,6,2,3。給出表達(dá)式“84*32+-”的求值過程以及結(jié)果。答：創(chuàng)建一個(gè)空棧。從左到右遍歷后綴表達(dá)式：遇到操作數(shù)8，將其壓入棧中：棧=[8]遇到操作數(shù)4，將其壓入棧中：棧=[8,4]遇到操作符*，從棧中彈出兩個(gè)操作數(shù)4和8，計(jì)算8*4=32，并將結(jié)果32壓入棧中：棧=[32]遇到操作數(shù)3，將其壓入棧中：棧=[32,3]遇到操作數(shù)2，將其壓入棧中：棧=[32,3,2]遇到操作符+，從棧中彈出兩個(gè)操作數(shù)2和3，計(jì)算2+3=5，并將結(jié)果5壓入棧中：棧=[32,5]遇到操作符-，從棧中彈出兩個(gè)操作數(shù)5和32，計(jì)算32-5=27，并將結(jié)果27壓入棧中：棧=[27]遍歷完后綴表達(dá)式后，棧中的唯一元素27即為表達(dá)式的求值結(jié)果。因此，給定后綴表達(dá)式“84*32+-”的求值結(jié)果為27。編寫一個(gè)算法，檢查字符串“（x=0）[x=1](x++)[x=x-5](x=0)）“中的方括號(hào)和圓括號(hào)是否配對(duì)，若能夠全部配對(duì)則返回1，否則返回0。答：intcheckParentheses(){stack<char>parenthesesStack;boolisBalanced=true;strings="(x=0)[x=1](x++)[x=x-5](x=0)";for(charc:s){if(c=='('||c=='['){parenthesesStack.push(c);}elseif(c==')'||c==']'){if(parenthesesStack.empty()){isBalanced=false;break;}else{chartop=parenthesesStack.top();parenthesesStack.pop();if((c==')'&&top!='(')||(c==']'&&top!='[')){isBalanced=false;break;}}}}if(!parenthesesStack.empty()){isBalanced=false;}returnisBalanced?1:0;}編寫一算法將中綴表達(dá)式轉(zhuǎn)換為后綴表達(dá)式。答：參考3-13表達(dá)式求值算法中將中綴表達(dá)式轉(zhuǎn)換為后綴表達(dá)式的算法。編寫一算法求解后綴表達(dá)式的值。答：參考3-13表達(dá)式求值算法。隊(duì)列習(xí)題填空題隊(duì)列是一種特殊，只允許在端點(diǎn)操作的線性表。在隊(duì)列中存取數(shù)據(jù)應(yīng)遵循的原則是先進(jìn)先出。棧和隊(duì)列的區(qū)別僅在于插入和刪除位置不相同。隊(duì)列在邏輯結(jié)構(gòu)上屬線性結(jié)構(gòu)。隊(duì)列允許插入的一端稱為隊(duì)尾，允許刪除的一端稱為隊(duì)首。順序隊(duì)列中在出隊(duì)操作時(shí)，首先要判斷隊(duì)列是否為空。順序隊(duì)列中入隊(duì)操作時(shí)，首先需要判斷隊(duì)列是否為滿。順序存儲(chǔ)的隊(duì)列如果不采用循環(huán)方式，則會(huì)出現(xiàn)假溢出問題。循環(huán)隊(duì)列的隊(duì)頭指針為front，隊(duì)尾指針為rear，則隊(duì)列中共有（rear－front＋N）％N個(gè)元素。循環(huán)隊(duì)列的隊(duì)頭指針為front，隊(duì)尾指針為rear，則隊(duì)空的條件為front=rear。鏈隊(duì)列q為空的條件是q->front=q->rear。在具有n個(gè)單元且采用順序存儲(chǔ)的循環(huán)隊(duì)列中，隊(duì)滿時(shí)共有n-1個(gè)元素。若front和rear分別表示循環(huán)隊(duì)列q的頭指針和尾指針，m表示該隊(duì)列的最大容量，則循環(huán)隊(duì)列為空的條件(rear－front＋m)％m==0。對(duì)帶頭結(jié)點(diǎn)的鏈隊(duì)列q，判定隊(duì)列中只有一個(gè)數(shù)據(jù)元素的條件是q->front->next=q->rear。設(shè)循環(huán)隊(duì)列的容量為100（序號(hào)0～99），現(xiàn)經(jīng)過一系列的入隊(duì)和出隊(duì)的運(yùn)算后，front=13，rear=39，則循環(huán)隊(duì)列中還有26個(gè)元素。選擇題隊(duì)列是限定在(D)進(jìn)行操作的線性表。A．中間者B.隊(duì)首C.隊(duì)尾D.端點(diǎn)在鏈隊(duì)列中執(zhí)行入隊(duì)操作，(D)。A．需判別隊(duì)列是否空 B．需判別隊(duì)列是否滿C．限制鏈表頭p進(jìn)行 D．限制在鏈表尾p進(jìn)行在一個(gè)順序存儲(chǔ)的循環(huán)隊(duì)列中，隊(duì)首指針指向隊(duì)首元素的(A)。A．前一個(gè)位置B．后一個(gè)位置C．隊(duì)首元素位置D．任意位置一個(gè)循環(huán)隊(duì)列一旦說明，其占用空間的大小(A)。A．固定B．可以變動(dòng)C．不能固定D．動(dòng)態(tài)變化順序隊(duì)列占用的空間(A)。A.必須連續(xù)B．不必連續(xù)C.不能連續(xù)D.可以不連續(xù)容量為10個(gè)元素的順序循環(huán)隊(duì)列用數(shù)組data來存儲(chǔ)，則data數(shù)組的下標(biāo)范圍是(B)。A．0～10B．0～9C．1～9D．1～104個(gè)元素按A,B,C,D順序連續(xù)入隊(duì)列q，執(zhí)行3次QutQueue(q)操作后，再執(zhí)行EmptyQueue(q)；后的值是(A)。A．0B．1C．2D．3在鏈隊(duì)列中，結(jié)點(diǎn)的結(jié)構(gòu)：data為數(shù)據(jù)域，next為指針域，rear和front分別指向隊(duì)尾和隊(duì)首，則在鏈隊(duì)列中出隊(duì)后的結(jié)點(diǎn)由指針s所指，則應(yīng)執(zhí)行下列(C)操作。A．s=front->next;front->next=sB．front->next=sC．s=front;front=front->nextD．s->next=front;front=s若進(jìn)隊(duì)列的序列為A,B,C,D，則出隊(duì)的序列是(C)。A．B,C,D,AB．A,C,B,DC．A,B,C,DD．C,B,D,A若用一個(gè)大小為10數(shù)組來實(shí)現(xiàn)循環(huán)隊(duì)列，且當(dāng)前front和rear的值分別為3和0，當(dāng)從隊(duì)列中刪除一個(gè)元素，再加入兩個(gè)元素后，front和rear的值分別為(B)。A.5和1B.4和2C.2和4D.1和5簡(jiǎn)答題試舉出幾個(gè)生活中的例子，其操作規(guī)律符合隊(duì)列的操作特征。答：銀行柜臺(tái)辦理業(yè)務(wù)：在銀行柜臺(tái)，顧客按照先來后到的順序等待辦理業(yè)務(wù)。每個(gè)顧客辦理完業(yè)務(wù)后，下一個(gè)顧客才能進(jìn)入柜臺(tái)。這也符合隊(duì)列的先進(jìn)先出的特性。打印隊(duì)列：當(dāng)我們?cè)诖蛴《鄠€(gè)文件時(shí)，打印任務(wù)會(huì)按照提交的順序排隊(duì)等待執(zhí)行。打印機(jī)會(huì)先處理隊(duì)列中的第一個(gè)任務(wù)，然后才會(huì)處理后面的任務(wù)。這也是隊(duì)列的典型應(yīng)用場(chǎng)景。汽車排隊(duì)進(jìn)入收費(fèi)站：在高速公路的收費(fèi)站，汽車會(huì)按照到達(dá)的順序排隊(duì)等待進(jìn)入收費(fèi)站。每個(gè)汽車依次從隊(duì)列中進(jìn)入收費(fèi)站，然后交費(fèi)離開。這也是隊(duì)列的一個(gè)應(yīng)用場(chǎng)景。簡(jiǎn)單描述隊(duì)列、隊(duì)頭、隊(duì)尾、空隊(duì)列、鏈隊(duì)列和循環(huán)隊(duì)列的概念。答：隊(duì)列（Queue）是一種具有先進(jìn)先出（FIFO）特性的線性數(shù)據(jù)結(jié)構(gòu)。它類似于現(xiàn)實(shí)生活中的排隊(duì)，新元素被添加到隊(duì)列的一端，稱為隊(duì)尾（rear），而已存在的元素從隊(duì)列的另一端被移除，稱為隊(duì)頭（front）。隊(duì)頭（Front）是隊(duì)列中的第一個(gè)元素，它是隊(duì)列的入口。當(dāng)元素被添加到隊(duì)列的時(shí)候，它成為新的隊(duì)尾。當(dāng)元素從隊(duì)列中被移除的時(shí)候，隊(duì)頭會(huì)向后移動(dòng)。隊(duì)尾（Rear）是隊(duì)列中的最后一個(gè)元素，它是隊(duì)列的出口。當(dāng)元素被添加到隊(duì)列的時(shí)候，隊(duì)尾會(huì)向后移動(dòng)。當(dāng)元素從隊(duì)列中被移除的時(shí)候，隊(duì)尾保持不變。空隊(duì)列（EmptyQueue）是指沒有任何元素的隊(duì)列。在空隊(duì)列中，隊(duì)頭和隊(duì)尾指向同一個(gè)位置，即沒有任何元素進(jìn)入或離開隊(duì)列。鏈隊(duì)列（LinkedQueue）是使用鏈表實(shí)現(xiàn)的隊(duì)列。每個(gè)節(jié)點(diǎn)都包含一個(gè)數(shù)據(jù)元素和一個(gè)指向下一個(gè)節(jié)點(diǎn)的指針。鏈隊(duì)列可以動(dòng)態(tài)地增加或刪除節(jié)點(diǎn)，因此沒有固定的大小限制。循環(huán)隊(duì)列（CircularQueue）是使用數(shù)組實(shí)現(xiàn)的隊(duì)列。它通過循環(huán)利用數(shù)組空間來避免隊(duì)列滿時(shí)無法繼續(xù)添加元素的問題。在循環(huán)隊(duì)列中，隊(duì)頭和隊(duì)尾可以在數(shù)組的開頭和結(jié)尾之間循環(huán)移動(dòng)。線性表、棧、隊(duì)列有什么區(qū)別與聯(lián)系？答：線性表是一種線性的數(shù)據(jù)結(jié)構(gòu)，數(shù)據(jù)元素按照一定的順序排列。棧和隊(duì)列是特殊的線性表。棧是一種后進(jìn)先出（LIFO）的數(shù)據(jù)結(jié)構(gòu)，只能在棧頂進(jìn)行插入和刪除操作。隊(duì)列是一種先進(jìn)先出（FIFO）的數(shù)據(jù)結(jié)構(gòu)，只能在隊(duì)尾插入元素，在隊(duì)頭刪除元素。操作特性：線性表可以在任意位置插入和刪除元素。棧只能在棧頂進(jìn)行插入和刪除操作，而且只能訪問棧頂?shù)脑亍ｊ?duì)列只能在隊(duì)尾插入元素，在隊(duì)頭刪除元素，不能訪問隊(duì)列中間的元素。使用場(chǎng)景：線性表適用于需要隨機(jī)訪問和靈活操作元素的場(chǎng)景。棧適用于需要按照后進(jìn)先出的順序訪問元素的場(chǎng)景，比如函數(shù)調(diào)用、表達(dá)式求值等。隊(duì)列適用于需要按照先進(jìn)先出的順序訪問元素的場(chǎng)景，比如排隊(duì)、任務(wù)調(diào)度等。什么是順序隊(duì)列的上溢現(xiàn)象？什么是順序隊(duì)列的假溢出現(xiàn)象？答：順序隊(duì)列的上溢現(xiàn)象：當(dāng)隊(duì)列滿時(shí)，再進(jìn)行入隊(duì)操作就會(huì)導(dǎo)致上溢現(xiàn)象。也就是說，隊(duì)列已經(jīng)沒有空閑空間可以存儲(chǔ)新元素了，但是仍然有新元素要入隊(duì)。這種情況下，如果繼續(xù)進(jìn)行入隊(duì)操作，就會(huì)導(dǎo)致數(shù)據(jù)的丟失或覆蓋，因?yàn)樾碌脑責(zé)o法被正確地存儲(chǔ)到隊(duì)列中。順序隊(duì)列的假溢出現(xiàn)象：假溢出現(xiàn)象是指隊(duì)列中存在空閑空間，但由于前面的元素出隊(duì)時(shí)，沒有正確地更新隊(duì)頭指針，導(dǎo)致隊(duì)列判斷為滿的狀態(tài)。也就是說，隊(duì)列實(shí)際上還有空間可以存儲(chǔ)新元素，但由于隊(duì)頭指針沒有及時(shí)更新，導(dǎo)致無法進(jìn)行入隊(duì)操作。循環(huán)隊(duì)列的優(yōu)點(diǎn)是什么，如何判別循環(huán)隊(duì)列的空和滿。答：順序隊(duì)列的上溢現(xiàn)象：當(dāng)隊(duì)列滿時(shí)，再進(jìn)行入隊(duì)操作就會(huì)導(dǎo)致上溢現(xiàn)象。也就是說，隊(duì)列已經(jīng)沒有空閑空間可以存儲(chǔ)新元素了，但是仍然有新元素要入隊(duì)。這種情況下，如果繼續(xù)進(jìn)行入隊(duì)操作，就會(huì)導(dǎo)致數(shù)據(jù)的丟失或覆蓋，因?yàn)樾碌脑責(zé)o法被正確地存儲(chǔ)到隊(duì)列中。順序隊(duì)列的假溢出現(xiàn)象：假溢出現(xiàn)象是指隊(duì)列中存在空閑空間，但由于前面的元素出隊(duì)時(shí)，沒有正確地更新隊(duì)頭指針，導(dǎo)致隊(duì)列判斷為滿的狀態(tài)。也就是說，隊(duì)列實(shí)際上還有空間可以存儲(chǔ)新元素，但由于隊(duì)頭指針沒有及時(shí)更新，導(dǎo)致無法進(jìn)行入隊(duì)操作。算法設(shè)計(jì)題設(shè)用一維數(shù)組data[n]表示一個(gè)隊(duì)列，實(shí)現(xiàn)入隊(duì)與出隊(duì)的操作算法。答：參考算法4-(1~4)隊(duì)列基本算法實(shí)現(xiàn)。編寫算法，利用兩個(gè)棧s1，s2模擬一個(gè)隊(duì)列的入隊(duì)、出隊(duì)和判斷隊(duì)列空的運(yùn)算。答：#defineMAX_SIZE100typedefstruct{intdata[MAX_SIZE];inttop;}Stack;voidinitStack(Stack*s){s->top=-1;}boolisStackEmpty(Stack*s){returns->top==-1;}boolisStackFull(Stack*s){returns->top==MAX_SIZE-1;}voidpush(Stack*s,intitem){if(isStackFull(s)){cout<<"Stackisfull!"<<endl;return;}s->top++;s->data[s->top]=item;}intpop(Stack*s){if(isStackEmpty(s)){cout<<"Stackisempty!”<<endl";return-1;}intitem=s->data[s->top];s->top--;returnitem;}typedefstruct{Stacks1;//用于入隊(duì)操作的棧Stacks2;//用于出隊(duì)操作的棧}Queue;voidinitQueue(Queue*q){initStack(&q->s1);initStack(&q->s2);}voidenqueue(Queue*q,intitem){push(&q->s1,item);//將元素入棧s1}intdequeue(Queue*q){if(isStackEmpty(&q->s1)&&isStackEmpty(&q->s2)){//如果棧s1和棧s2都為空，則隊(duì)列為空cout<<"Queueisempty!"<<endl;return-1;}if(isStackEmpty(&q->s2)){//如果棧s2為空，則將棧s1中的元素依次出棧并入棧s2while(!isStackEmpty(&q->s1)){intitem=pop(&q->s1);push(&q->s2,item);}}intfront=pop(&q->s2);//將s2的棧頂元素出棧并返回returnfront;}boolisQueueEmpty(Queue*q){returnisStackEmpty(&q->s1)&&isStackEmpty(&q->s2);//當(dāng)s1和s2都為空時(shí)，隊(duì)列為空}設(shè)一個(gè)循環(huán)隊(duì)列q，只有頭指針front，不設(shè)尾指針，另設(shè)一個(gè)含有元素個(gè)數(shù)的計(jì)數(shù)器count，編寫相應(yīng)的入隊(duì)算法和出隊(duì)算法。答：#defineMAX_SIZE5typedefstruct{intdata[MAX_SIZE];intfront;intcount;}CircularQueue;voidinitQueue(CircularQueue*q){q->front=0;q->count=0;}boolisQueueEmpty(CircularQueue*q){returnq->count==0;}boolisQueueFull(CircularQueue*q){returnq->count==MAX_SIZE;}voidenqueue(CircularQueue*q,intitem){if(isQueueFull(q)){cout<<"Queueisfull!"<<endl;return;}intrear=(q->front+q->count)%MAX_SIZE;//計(jì)算隊(duì)尾元素的下標(biāo)q->data[rear]=item;//將元素放入隊(duì)尾q->count++;//計(jì)數(shù)器加1}intdequeue(CircularQueue*q){if(isQueueEmpty(q)){cout<<"Queueisempty!"<<endl;return-1;}intitem=q->data[q->front];//取出隊(duì)頭元素q->front=(q->front+1)%MAX_SIZE;//頭指針向后移動(dòng)一位q->count--;//計(jì)數(shù)器減1returnitem;}已知q是一個(gè)非空隊(duì)列，s是一個(gè)空棧。試設(shè)計(jì)一個(gè)算法，利用棧和隊(duì)列的基本運(yùn)算，將隊(duì)列q中的全部元素逆置存放。答：#defineMAX_SIZE100typedefstruct{intdata[MAX_SIZE];intfront;intrear;intcount;}Queue;typedefstruct{intdata[MAX_SIZE];inttop;}Stack;voidinitQueue(Queue*q){q->front=0;q->rear=-1;q->count=0;}boolisQueueEmpty(Queue*q){returnq->count==0;}boolisQueueFull(Queue*q){returnq->count==MAX_SIZE;}voidenqueue(Queue*q,intitem){if(isQueueFull(q)){cout<<"Queueisfull!"<<endl;return;}q->rear=(q->rear+1)%MAX_SIZE;//計(jì)算隊(duì)尾元素的下標(biāo)q->data[q->rear]=item;//將元素放入隊(duì)尾q->count++;//計(jì)數(shù)器加1}intdequeue(Queue*q){if(isQueueEmpty(q)){cout<<"Queueisempty!"<<endl;return-1;}intitem=q->data[q->front];//取出隊(duì)頭元素q->front=(q->front+1)%MAX_SIZE;//頭指針向后移動(dòng)一位q->count--;//計(jì)數(shù)器減1returnitem;}voidinitStack(Stack*s){s->top=-1;}boolisStackEmpty(Stack*s){returns->top==-1;}boolisStackFull(Stack*s){returns->top==MAX_SIZE-1;}voidpush(Stack*s,intitem){if(isStackFull(s)){cout<<"Stackisfull!"<<endl;return;}s->top++;//棧頂指針加1s->data[s->top]=item;//將元素放入棧頂}intpop(Stack*s){if(isStackEmpty(s)){cout<<"Stackisempty!"<<endl;return-1;}intitem=s->data[s->top];//取出棧頂元素s->top--;//棧頂指針減1returnitem;}voidreverseQueue(Queue*q){Stacks;initStack(&s);while(!isQueueEmpty(q)){intitem=dequeue(q);push(&s,item);}while(!isStackEmpty(&s)){intitem=pop(&s);enqueue(q,item);}}設(shè)循環(huán)隊(duì)列q，只設(shè)置頭指針和為指針，設(shè)計(jì)算法求循環(huán)隊(duì)列中當(dāng)前元素的個(gè)數(shù)。答：#defineMAX_SIZE100typedefstruct{intdata[MAX_SIZE];intfront;intrear;}Queue;voidinitQueue(Queue*q){q->front=0;q->rear=-1;}boolisQueueEmpty(Queue*q){returnq->rear<q->front;}intgetCurrentSize(Queue*q){if(isQueueEmpty(q)){return0;}intsize;if(q->rear>=q->front){size=q->rear-q->front+1;}else{size=q->rear+MAX_SIZE-q->front+1;}returnsize;}串與數(shù)組習(xí)題填空題在計(jì)算機(jī)軟件系統(tǒng)中，有兩種處理字符長(zhǎng)度的方法，一是可變長(zhǎng)度處理，二是固定長(zhǎng)度處理。如果s=＂thisisthefirststring＂，sub=＂the＂，stringdex(s，sub)是8。已知字符串s1=＂abcdefghijklmnopqrstuvw＂，由如下運(yùn)算可得到串s2=Concat(Sub(s1，19，3)，Sub(s1，4，2)，sub(s1，14，1)，Sub(s1，20，1))，則s2tuvefov。兩個(gè)串相等的充要條件是長(zhǎng)度相等，對(duì)應(yīng)位置的字符也相等。s=＂xiaotech＂所含子串的個(gè)數(shù)是37。一個(gè)10×10的下三角矩陣A采用行優(yōu)先壓縮存儲(chǔ)后，如果首元素a[0][0]是第一個(gè)元素，那么a[4][2]是第13個(gè)元素。兩個(gè)矩陣Amn，Bnp相乘，其時(shí)間復(fù)雜度為O(m*n*p)。兩個(gè)矩陣Amn，Bmn相加，其時(shí)間復(fù)雜度為O(m*n)。稀疏矩陣采用的壓縮存儲(chǔ)方法是三元組表示法。二維數(shù)組A[11][20]采用按行為主序的存儲(chǔ)方式，每個(gè)元素占4個(gè)存儲(chǔ)單元，若A[0][0]的存儲(chǔ)地址為300，則A[10][10]的地址為1140。選擇題串的邏輯結(jié)構(gòu)與(A)的邏輯結(jié)構(gòu)不同。A．線性表B．隊(duì)列C．棧D．樹設(shè)有二維數(shù)組A[50][60]，其元素長(zhǎng)度為1個(gè)字節(jié)，按列優(yōu)先順序存儲(chǔ)，首元素A[0][0]的地址為200，則元素A[10][20]的存儲(chǔ)地址為()。A．820 B．720 C．1210 D．1410一個(gè)100×100的下三角形矩陣a采用行優(yōu)先壓縮存儲(chǔ)后，如果首元素a[0][0]是第一個(gè)元素，那么a[4][2]是第(A)元素。A．13 B．401 C．402 D．403串的長(zhǎng)度是(D)。A．串中不同字符的個(gè)數(shù)B．串中不同字母的個(gè)數(shù)

C．串中所含字符的個(gè)數(shù)n(n>0)D．串中所含字符的個(gè)數(shù)n(n≥0)設(shè)有一個(gè)10階的對(duì)稱矩陣a，采用壓縮存儲(chǔ)方式，以行序?yàn)橹鞔鎯?chǔ)，a[0][0]的存儲(chǔ)地址為100，每個(gè)元素占1個(gè)地址空間，則a[3][2]的地址為(D)。A．102 B．105 C．106 D．108設(shè)有兩個(gè)串p和q，求q在p中的首次出現(xiàn)的位置的運(yùn)算稱作(B)。A．連接B．模式匹配C．求子串D．求串長(zhǎng)假設(shè)有60行70列的二維數(shù)組a以列序?yàn)橹餍蝽樞虼鎯?chǔ)，其基地址為10000，每個(gè)元素占2個(gè)存儲(chǔ)單元，那么第32行第58列的元素a[31，57]的存儲(chǔ)地址為(A)。A．16902B.16904C.14454D.答案A,B,C均不對(duì)下面關(guān)于串的敘述中，(B)是不正確的？A．串是字符的有限序列

B．空串是由空格構(gòu)成的串

C．模式匹配是串的一種重要運(yùn)算

D．串既可以采用順序存儲(chǔ)，也可以采用鏈?zhǔn)酱鎯?chǔ)C++語言對(duì)數(shù)組元素的存放方式通常采用(A)。A．按行為主的存儲(chǔ)結(jié)構(gòu) B．按列為主的存儲(chǔ)結(jié)構(gòu)C．按行或列為主的存儲(chǔ)結(jié)構(gòu) D．具體存儲(chǔ)結(jié)構(gòu)無法確定二維數(shù)組A[n][m］以列優(yōu)先順序存儲(chǔ)，數(shù)組A中每個(gè)元素占用1個(gè)字節(jié)，A［1］［1］為首元素，其地址為0，則元素A[i][j]的地址為(B)。A．(j-1)×m+(j-1) B．(j-1)×n+(i-1)C．(j-1)×n+i D．j×n+i簡(jiǎn)答題簡(jiǎn)述下列每對(duì)術(shù)語的區(qū)別。空串和空格串。答：空串是指一個(gè)沒有任何字符的字符串，長(zhǎng)度為0。空格串是指只包含空格字符的字符串，長(zhǎng)度大于等于1串變量和串常量。答：串變量是在程序中定義的一個(gè)變量，用來存儲(chǔ)字符串的值。可以通過賦值操作來改變串變量的值。串常量是在程序中直接指定的一個(gè)字符串值，不可修改。通常用引號(hào)括起來表示，例如“hello”。主串和子串。答：主串是指一個(gè)完整的字符串，可以包含子串。子串是主串中的一個(gè)連續(xù)的字符序列。變量的名字和串變量的值。答：串變量的名字是程序中定義的標(biāo)識(shí)符，用來表示一個(gè)存儲(chǔ)字符串值的變量。串變量的值是存儲(chǔ)在該變量中的字符串值。可以通過賦值操作來改變串變量的值。設(shè)有二維數(shù)組A（6×8），每個(gè)元素占6個(gè)字節(jié)存儲(chǔ)，順序存放，A的起地址為1000，計(jì)算：（1）數(shù)組A的體積（即存儲(chǔ)量）；（2）數(shù)組的最后一個(gè)元素A的起地址；（3）按行優(yōu)先存放時(shí)，元素a14的地址是多少；（4）按列優(yōu)先存放時(shí)，元素a47的地址。答：存儲(chǔ)容量為：（1）6*8*6=1288。（2）1000+(6*8-1)*6=2282（3）1000+（8+4）*6=1072（4）1000+（6*7+4）*6=1276算法設(shè)計(jì)題寫一個(gè)算法來實(shí)現(xiàn)字符串逆序存儲(chǔ)，要求不另設(shè)串存儲(chǔ)空間。答：參考第二章順表表的逆置算法。設(shè)s、t為兩個(gè)字符串，分別放在兩個(gè)一維數(shù)組中，m、n分別為其長(zhǎng)度，判斷t是否為s的子串。如果是，輸出子串所在位置（第一個(gè)字符），否則輸出-1。答：參考法5-4Brute-Force模式匹配算法編寫程序，統(tǒng)計(jì)在輸入字符串中各個(gè)不同字符出現(xiàn)的頻度并將結(jié)果存入文件（字符串中的合法字符為A-Z這26個(gè)字母和0-9這10個(gè)數(shù)字）。答：voidcountFrequency(conststd::string&input){unordered_map<char,int>frequency;//統(tǒng)計(jì)字符頻度for(charc:input){c=toupper(c);//將字符轉(zhuǎn)換為大寫字母if(isalnum(c)){//只處理字母和數(shù)字字符frequency[c]++;}}//將結(jié)果存入文件ofstreamfile("result.txt");if(!file){cout<<"無法打開文件。\n";return;}file<<"字符\t頻度\n";for(charc='A';c<='Z';c++){file<<c<<"\t"<<frequency[c]<<"\n";}for(charc='0';c<='9';c++){file<<c<<"\t"<<frequency[c]<<"\n";}cout<<"結(jié)果已保存到result.txt文件中。\n";}}試編寫算法實(shí)現(xiàn)將字符串s中所有值為c的字符換成值為d的字符。答：參考算法5-7文本匹配算法。試編寫算法實(shí)現(xiàn)將字符串s中所有值為s1的子串替換成值為s2的子串。答：參考算法5-7文本匹配算法。從串s中刪除其值等于c的所有字符。答：參考第二章刪除重復(fù)元素的算法。試編寫算法實(shí)現(xiàn)將字符串s中所有值為s1的子串刪除。答：voiddeleteSubstring(char*s,constchar*s1){ints1Len=strlen(s1);char*p=s;while((p=strstr(p,s1))!=NULL){memmove(p,p+s1Len,strlen(p+s1Len)+1);}}樹與二叉樹習(xí)題一、填空題一個(gè)結(jié)點(diǎn)所擁有的子樹數(shù)稱為該結(jié)點(diǎn)的度。度為零的結(jié)點(diǎn)稱為葉子結(jié)點(diǎn)。對(duì)于二叉樹來說，第i層上至多有2i-1個(gè)結(jié)點(diǎn)。56個(gè)結(jié)點(diǎn)的完全二叉樹有28個(gè)葉子結(jié)點(diǎn)。深度為8的二叉樹最多有255個(gè)結(jié)點(diǎn)。有8個(gè)結(jié)點(diǎn)的二叉樹最大深度為8。前序?yàn)锳，B，C且后序C，B，A的二叉樹共有4種。已知完全二叉樹的第8層有8個(gè)結(jié)點(diǎn)，則其葉結(jié)點(diǎn)數(shù)是68。中序?yàn)锳，B，C且后序C，B，A的二叉樹共有1種。樹與二叉樹之間最主要的差別是：二叉樹中各結(jié)點(diǎn)的子樹要區(qū)分為左子樹和右子樹。由一個(gè)二叉樹的前序序列和后序列不能確定這個(gè)二叉樹。有30個(gè)結(jié)點(diǎn)的完全二叉樹，編號(hào)為11的結(jié)點(diǎn)的父結(jié)點(diǎn)的編號(hào)是5。哈夫曼樹是帶權(quán)路徑長(zhǎng)度最短的二叉樹。由樹轉(zhuǎn)換二叉樹時(shí)，其二叉樹沒有右子樹。采用二叉鏈表存儲(chǔ)的20個(gè)結(jié)點(diǎn)的二叉樹，一共有21個(gè)空指針域。若用鏈表存儲(chǔ)一個(gè)二叉樹時(shí)，每個(gè)結(jié)點(diǎn)除數(shù)據(jù)域外，還有指向左孩子和右孩子的兩個(gè)指針。在這種存儲(chǔ)結(jié)構(gòu)中，n個(gè)結(jié)點(diǎn)的二叉樹共有___2n____個(gè)指針域，其中有n-1個(gè)指針域是存放了地址，有n+1個(gè)指針是空指針。中序遍歷二叉排序樹所得到的序列是有序序列（填有序或無序）。設(shè)哈夫曼樹中共有99個(gè)結(jié)點(diǎn)，則該樹中有50個(gè)葉子結(jié)點(diǎn)；若采用二叉鏈表作為存儲(chǔ)結(jié)構(gòu)，則該樹中有100個(gè)空指針域。設(shè)一個(gè)二叉樹中有50個(gè)度數(shù)為0的結(jié)點(diǎn)，21個(gè)度數(shù)為1的結(jié)點(diǎn)，則該二叉樹總的結(jié)點(diǎn)個(gè)數(shù)為120個(gè)。設(shè)某二叉樹有100個(gè)結(jié)點(diǎn)，則該二叉樹的深度最小為7，最大為100。選擇題樹最適合用來表示(D)。A.無序數(shù)據(jù)元素B.無關(guān)系數(shù)據(jù)元素C.元素間多種聯(lián)系的數(shù)據(jù)D.元素間有分支的層次關(guān)系在一個(gè)具有五層的滿二叉樹中，結(jié)點(diǎn)的個(gè)數(shù)為(B)。A.16B.31C.32D.33具有64個(gè)結(jié)點(diǎn)的完全二叉樹的深度為(C)。A.5B.6C.7D.8任何一個(gè)二叉樹的葉結(jié)點(diǎn)在前序、中序、后序遍歷序列中的相對(duì)次序(A)。A.不發(fā)生改變B.發(fā)生改變C.不能確定D.以上都不對(duì)A，B為一個(gè)二叉樹上的兩個(gè)結(jié)點(diǎn)，在中序遍歷時(shí)，A在B前的條件是(C)。A.A在B右方B.A是B祖先C.A在B左方D.A是B子孫二叉樹的葉結(jié)點(diǎn)個(gè)數(shù)比度為2的結(jié)點(diǎn)的個(gè)數(shù)(C)。A.無關(guān)B.相等C.多一個(gè)D.少一個(gè)一個(gè)二叉樹的后序遍歷序列為ADBEC，中序遍歷序列為AEBDC，則前序遍歷序列為(D)。A.DCBEAB.AECDBC.AEDBCD.CEABD將一個(gè)有100個(gè)結(jié)點(diǎn)的完全二叉樹從上到下，從左到右依次對(duì)結(jié)點(diǎn)編號(hào)，根結(jié)點(diǎn)的編號(hào)為1，則編號(hào)為45的結(jié)點(diǎn)的左孩子編號(hào)為(C)。A.46B.47C.90D.91二叉樹按某種順序線索化后，任一結(jié)點(diǎn)不一定有指向其前驅(qū)和后繼的線索，這種說法(A)。A.正確B.錯(cuò)誤C.不確定D.都有可能下列陳述正確的是(A)。A.二叉樹是度為2的有序樹B.二叉樹中結(jié)點(diǎn)只有一個(gè)孩子時(shí)無左右之分C.二叉樹必有度為2的結(jié)點(diǎn)D.二叉樹中最多只有兩個(gè)子樹，且有左右子樹之分用5個(gè)權(quán)值{3,2,4,5,1}構(gòu)造的哈夫曼樹的帶權(quán)路徑長(zhǎng)度是(B)。A.32B.33C.34D.15在樹結(jié)構(gòu)中，若結(jié)點(diǎn)B有4個(gè)兄弟，A是B的父親結(jié)點(diǎn)，則A的度為(C)。A.3B.4C.5D.6依據(jù)給定的權(quán)值，構(gòu)造的哈夫曼是唯一的。這種說法(B)。A.正確B.錯(cuò)誤C.不確定D.都有可能哈夫曼樹中無度為1的結(jié)點(diǎn)，這種說法(A)。A．正確B．錯(cuò)誤C．不確定D．都有可能線索二叉樹中無空指針存在，這種說法(B)。A.正確B.錯(cuò)誤C.不確定D.都有可能一個(gè)二叉樹的前序序列和后序序列正好相反，則該二叉樹一定是(C)的二叉樹A．空或只有一個(gè)結(jié)點(diǎn)B．任一結(jié)點(diǎn)無左子樹C．高度等于其結(jié)點(diǎn)數(shù)D．任一結(jié)點(diǎn)無右子樹引入二叉線索樹的目的是(A)A．加快查找結(jié)點(diǎn)的前驅(qū)或后繼的速度B．為了能在二叉樹中方便地進(jìn)行插入與刪除C．為了提高空間利用率D．為了向上查找雙親結(jié)點(diǎn)線索二叉樹是一種(C)結(jié)構(gòu)。A．邏輯B．存儲(chǔ)結(jié)構(gòu)C．為了能方便地找到雙親D．使二叉樹的遍歷結(jié)果唯一二叉樹在線索后，仍不能有效求解的問題是(A)。A．先序線索二叉樹中求先序后繼B．中序線索二叉樹中求中序后繼C．中序線索二叉樹中求中序前驅(qū)D．后序線索二叉樹中求后序后繼哈夫曼樹是帶權(quán)路徑最短的樹，路徑上權(quán)值較大的結(jié)點(diǎn)離根較近(A)。A．正確B．錯(cuò)誤C．不確定D．都有可能三、簡(jiǎn)答題描述樹與二叉樹的區(qū)別與聯(lián)系。答：區(qū)別：結(jié)構(gòu)：樹是由節(jié)點(diǎn)和邊組成的非線性結(jié)構(gòu)，每個(gè)節(jié)點(diǎn)可以有多個(gè)子節(jié)點(diǎn)。而二叉樹是一種特殊的樹結(jié)構(gòu)，每個(gè)節(jié)點(diǎn)最多只有兩個(gè)子節(jié)點(diǎn)，分別稱為左子節(jié)點(diǎn)和右子節(jié)點(diǎn)。子節(jié)點(diǎn)個(gè)數(shù)：樹的節(jié)點(diǎn)可以有任意多個(gè)子節(jié)點(diǎn)，而二叉樹的節(jié)點(diǎn)最多只有兩個(gè)子節(jié)點(diǎn)。排列方式：樹的子節(jié)點(diǎn)之間沒有順序關(guān)系，可以以任意方式排列。而二叉樹的左子節(jié)點(diǎn)和右子節(jié)點(diǎn)有固定的順序關(guān)系，左子節(jié)點(diǎn)在前，右子節(jié)點(diǎn)在后。聯(lián)系：結(jié)構(gòu)關(guān)系：二叉樹是樹的一種特殊情況，可以看作是每個(gè)節(jié)點(diǎn)最多只有兩個(gè)子節(jié)點(diǎn)的樹。因此，二叉樹也是樹的一種特殊結(jié)構(gòu)。數(shù)據(jù)表示：樹和二叉樹都可以用多種方式進(jìn)行表示，常見的表示方法有順序存儲(chǔ)和鏈