數(shù)據(jù)結(jié)構(gòu)（自考） 課后習(xí)題及解答

第一章緒論一、單項選擇題1．在數(shù)據(jù)結(jié)構(gòu)中，從邏輯上可以把數(shù)據(jù)結(jié)構(gòu)分為________。A．緊湊結(jié)構(gòu)和非緊湊結(jié)構(gòu) B．線性結(jié)構(gòu)和非線性結(jié)構(gòu)C．內(nèi)部結(jié)構(gòu)和外部結(jié)構(gòu) D．動態(tài)結(jié)構(gòu)和靜態(tài)結(jié)構(gòu)答案：B。從邏輯角度看，基本的數(shù)據(jù)結(jié)構(gòu)包括4類，分別是集合、線性結(jié)構(gòu)、樹結(jié)構(gòu)和圖結(jié)構(gòu)。其中，樹結(jié)構(gòu)和圖結(jié)構(gòu)屬于非線性結(jié)構(gòu)。集合也可以使用線性結(jié)構(gòu)表示。2．?dāng)?shù)據(jù)元素可以細(xì)分為________。A．?dāng)?shù)據(jù)項 B．字符 C．二進(jìn)制位 D．?dāng)?shù)據(jù)記錄答案：A。根據(jù)定義，數(shù)據(jù)元素可以細(xì)分為數(shù)據(jù)項。字符和二進(jìn)制位都是表示數(shù)據(jù)的具體單位（選項B和C都不正確）。數(shù)據(jù)元素有時稱為記錄（選項D不正確）。3．如果說線性結(jié)構(gòu)中元素之間是一對一的關(guān)系，則樹結(jié)構(gòu)中元素之間的關(guān)系是________。A．一對一的 B．一對多的 C．多對多的 D．不確定的答案：B。線性結(jié)構(gòu)中，每個元素有唯一的前驅(qū)和唯一的后繼，所以對于每個元素而言，它對應(yīng)唯一的后繼，形成一對一的關(guān)系。當(dāng)然，首元素和尾元素除外。在樹結(jié)構(gòu)中，每個元素僅有唯一的前驅(qū)，但可以有多個后繼，所以是一對多的關(guān)系。當(dāng)然，樹中的根（最前面的元素）和葉結(jié)點（后面的元素）除外。圖結(jié)構(gòu)中是多對多的關(guān)系，每個元素可以有多個前驅(qū)，也可以有多個后繼。4．下列選項中，不屬于數(shù)據(jù)結(jié)構(gòu)常用存儲方式的是________。A．順序存儲方式 B．鏈?zhǔn)酱鎯Ψ绞?C．分布存儲方式 D．散列存儲方式答案：C。數(shù)據(jù)結(jié)構(gòu)課程中沒有討論分布存儲方式，除了選項中給定的A、B和D以外，還討論了索引存儲方式。這是數(shù)據(jù)結(jié)構(gòu)中常用的4種存儲方式。5．算法分析要評估的兩個主要方面是________。A．正確性和簡明性 B．時間復(fù)雜性和空間復(fù)雜性C．可讀性和可維護(hù)性 D．?dāng)?shù)據(jù)復(fù)雜性和程序復(fù)雜性答案：B。算法的正確性是必須的，簡明性、可讀性、可維護(hù)性等都不是算法要評估的內(nèi)容（選項A和選項C不正確），它們都屬于算法應(yīng)具備的眾多特性中的內(nèi)容。數(shù)據(jù)復(fù)雜性是數(shù)據(jù)本身的狀態(tài)，也不是算法要評估的，程序復(fù)雜性說得不明確（選項D不正確）。算法要評估的是時間和空間復(fù)雜性。6．下列選項中，定義抽象數(shù)據(jù)類型時不需要做的事情是________。A．給出類型的名字 B．定義類型上的操作C．實現(xiàn)類型上的操作 D．用某種語言描述抽象數(shù)據(jù)類型答案：C。定義抽象數(shù)據(jù)類型時，需要給類型命名（選項A），需要指明相關(guān)的操作有哪些（選項B），需要使用程序語言或是自然語言描述抽象數(shù)據(jù)類型（選項D）。在確定了存儲結(jié)構(gòu)之后才能具體實現(xiàn)操作過程，所以在定義抽象數(shù)據(jù)類型階段，不涉及這些操作的實現(xiàn)。7．________。x=2;while(x<n/2) x=2*x;A．O(log2n) B．O(n) C．O(nlog2n) D．O(n2)答案：A。n是輸入規(guī)模。x從2開始，每次倍增，達(dá)到或超過n/2時倍增的次數(shù)與log2n的大小相當(dāng)。8．設(shè)n是描述問題規(guī)模的非負(fù)整數(shù)，下列程序片段的時間復(fù)雜度是________。x=1;while(n>=(x+1)*(x+1)) x=x+1;A．O(n1/2) B．O(log2n) C．O(n) D．O(nlog2n)答案：A。二、填空題1．在數(shù)據(jù)結(jié)構(gòu)課程中，將所有能輸入計算機(jī)并被計算機(jī)程序處理的符號集合稱為__________。答案：數(shù)據(jù)。2．構(gòu)成數(shù)據(jù)的基本單位是__________。答案：數(shù)據(jù)元素。3．?dāng)?shù)據(jù)元素及其關(guān)系在計算機(jī)內(nèi)的存儲方式稱為數(shù)據(jù)的__________。答案：存儲結(jié)構(gòu)。4．?dāng)?shù)據(jù)的邏輯結(jié)構(gòu)表示數(shù)據(jù)元素之間的關(guān)系，與存儲關(guān)系是__________。答案：無關(guān)的。5．構(gòu)成索引表的基本內(nèi)容是__________。答案：索引項。6．一個算法必須在執(zhí)行有窮步之后結(jié)束，這個特性是算法的__________。答案：有窮性。三、解答題1．舉例說明計算機(jī)能處理哪些數(shù)據(jù)？【參考答案】計算機(jī)能處理的數(shù)據(jù)多種多樣，大到可以是一幅地圖、一本書、一部電影，小到可以是一個字符，甚至是計算機(jī)中的一位?？梢允菙?shù)值型的數(shù)據(jù)，也可以是非數(shù)值型的數(shù)據(jù)。只可以是簡單結(jié)構(gòu)的，也可以是復(fù)雜結(jié)構(gòu)的。2．線性結(jié)構(gòu)中，如何理解元素之間是一對一的關(guān)系？【參考答案】線性結(jié)構(gòu)中，除表頭元素和表尾元素外，每個元素有唯一的前驅(qū)和唯一的后繼。所以對于每個元素而言，當(dāng)有后繼時，它與其后繼形成一對一的關(guān)系。3．定義代表交通工具的抽象數(shù)據(jù)類型vehicle，添加必要的數(shù)據(jù)和操作。【參考答案】對于vehicle，可以定義表示其基本屬性的數(shù)據(jù)，包括品牌brand、顏色color、價格price等。相應(yīng)的操作可以是設(shè)置最大速度setSpeed(intspeed)、設(shè)置自重setdeadweight(intweight)等。ADTvehicle{ //交通工具的抽象數(shù)據(jù)類型定義 數(shù)據(jù)部分： brand： //品牌，字符串 color： //顏色，字符串 price： //價格，實型 speed： //最大速度，實型 deadweight： //自重，實型，單位噸 操作部分： setSpeed(speed)： //設(shè)置最大速度 輸入：speed 輸出：是否設(shè)置成功 前提條件：設(shè)置的speed值不能超出限制 setdeadweight(weight)： //設(shè)置自重 輸入：weight 輸出：是否設(shè)置成功 前提條件：設(shè)置的weight值不能超出限制}4．定義表示復(fù)數(shù)的抽象數(shù)據(jù)類型?！緟⒖即鸢浮繌?fù)數(shù)由實部和虛部表示，實部和虛部都是實型值。相應(yīng)的操作有算術(shù)操作。ADTcomplex{ //復(fù)數(shù)的抽象數(shù)據(jù)類型定義 數(shù)據(jù)部分： real： //實部，實型 imaginary： //虛部，實型 操作部分： add(complex1,complex2)： //加法 輸入：兩個復(fù)數(shù) 輸出：它們的和 前提條件：兩個復(fù)數(shù)正確 sub(complex1,complex2)： //減法 輸入：兩個復(fù)數(shù) 輸出：它們的差 前提條件：兩個復(fù)數(shù)正確 multiplication(complex1,complex2)： //乘法 輸入：兩個復(fù)數(shù) 輸出：它們的積 前提條件：兩個復(fù)數(shù)正確 division(complex1,complex2)： //除法 輸入：兩個復(fù)數(shù) 輸出：它們的商 前提條件：兩個復(fù)數(shù)正確}5．為什么不使用算法的絕對運(yùn)行時間來衡量算法的時間效率？【參考答案】同一個算法處理不同數(shù)量的數(shù)據(jù)時，所花的絕對運(yùn)行時間可能不同。同一個算法處理相同數(shù)量的數(shù)據(jù)時，在不同配置的電腦上的絕對運(yùn)行時間也可能不同。所以，使用算法的絕對運(yùn)行時間不能有效衡量算法的時間效率。6．評估算法的空間效率時，需要考慮占用的哪些存儲空間？【參考答案】算法運(yùn)行過程中，臨時占用的空間大小是要考慮的存儲空間。算法代碼占用的空間、算法中初始數(shù)據(jù)占用的存儲空間不考慮在內(nèi)。四、算法設(shè)計題1．試設(shè)計一個算法，使用最少的比較次數(shù)找出三個不同整數(shù)a,b,c的中值。【參考答案】intmiddle(inta,intb,intc){ if(a>b){ if(b>c)returnb; //a>b>c elseif(a>c)returnc; //a>c>b elsereturna; //c>b>a } else{ if(a>c)returna; //b>a>c elseif(b>c)returnc; //b>c>a elsereturnb; //c>b>a }}2．試設(shè)計一個算法，對于給定的正整數(shù)n，列出斐波那契數(shù)列的前n項。【參考答案】斐波那契數(shù)列的前兩項均為1，從第三項開始，每一項都是其前兩項之和。使用整型變量f1、f2和f3表示數(shù)列中相鄰三項的值，初始時，f1和f2的值均為1。然后計算新的項f3=f1+f2，計算后用f2的值更新f1，用f3的值更新f2。voidfibonacci(intn){ intf1=1,f2=1,f3,i; if(n<=0){ printf("n值錯誤\n"); return; } elseif(n==1){ printf("1\n"); return; } else{ printf("11"); for(i=3;i<=n;i++){ f3=f1+f2; printf("%d",f3); f1=f2; f2=f3; } printf("\n"); }}第二章線性表一、單項選擇題1．下列選項中，不是鏈表特點的是________。A．插入、刪除時不需要移動元素 B．可隨機(jī)訪問任一元素C．不必事先估計存儲空間 D．所需空間與元素個數(shù)成正比答案：B。鏈表中的元素可以不必保存在相鄰的地址空間中，所以當(dāng)鏈表中的元素個數(shù)有變化時，其他的元素不必像順序表那樣進(jìn)行移動（選項A）。而且鏈表占用的空間隨需分配，隨用隨分配，不必提前預(yù)估數(shù)量（選項C），表中有多少個元素就分配多少個表結(jié)點（選項D）。但要訪問鏈表中的元素時，只能從表頭開始，沿指針的指示逐個結(jié)點地查找下去，所以不能像在數(shù)組中那樣通過下標(biāo)定位到所需的地址，即不能實現(xiàn)隨機(jī)訪問。2．下列關(guān)于線性表的敘述中，錯誤的是________。A．線性表采用鏈?zhǔn)酱鎯Ψ绞?，便于進(jìn)行插入和刪除操作B．線性表采用順序存儲方式，便于進(jìn)行插入和刪除操作C．線性表采用鏈?zhǔn)酱鎯Ψ绞?，不必占用一片連續(xù)的存儲單元D．線性表采用順序存儲方式，必須占用一片連續(xù)的存儲單元答案：B。線性表既可以采用順序存儲結(jié)構(gòu)，也可以采用鏈?zhǔn)酱鎯Y(jié)構(gòu)。采用順序存儲結(jié)構(gòu)時，各元素要連續(xù)存放（選項D），當(dāng)有插入和刪除操作時，通常會導(dǎo)致其他元素的移動（選項B不正確）。當(dāng)采用鏈?zhǔn)酱鎯Y(jié)構(gòu)時，因為各結(jié)點的地址并不要求是相鄰的（選項C），所以插入和刪除操作不會引起其他元素的移動（選項A）。3．若線性表L最常用的操作是訪問任一位置的元素和在最后進(jìn)行插入和刪除運(yùn)算，為使操作的時間復(fù)雜度好，則下列選項中，為L選擇的存儲結(jié)構(gòu)為________。A．順序表 B．雙向鏈表C．帶頭結(jié)點的雙向循環(huán)鏈表 D．單循環(huán)鏈表答案：A。采用順序存儲結(jié)構(gòu)保存線性表時，能以O(shè)(1)訪問線性表任一位置的元素。要在線性表中間位置進(jìn)行插入和刪除時，會引發(fā)部分元素在數(shù)組中的移動，但如果僅在最后位置進(jìn)行插入和刪除，則避免了元素的移動，操作也能達(dá)到O(1)。選項B、C和D都是鏈?zhǔn)酱鎯Y(jié)構(gòu)，雖然它們進(jìn)行插入和刪除操作時能達(dá)到O(1)，但訪問任一位置元素時，平均情況下，僅能達(dá)到O(n)。綜合來看，選擇順序表更合適。4．線性表L中最常用的操作是在最后一個元素之后插入一個元素和刪除第一個元素，為使操作的時間復(fù)雜度好，則下列選項中，為L選擇的存儲結(jié)構(gòu)為________。A．單鏈表 B．僅有頭指針的單循環(huán)鏈表C．雙向鏈表 D．僅有尾指針的單循環(huán)鏈表答案：D。4個選項給出的都是鏈?zhǔn)酱鎯Y(jié)構(gòu)。根據(jù)題意，操作的位置是表尾和表頭，所以要選擇能快速訪問這兩個位置的結(jié)構(gòu)。單鏈表中僅有表頭指針，能快速訪問表頭，但不能快速訪問表尾。單循環(huán)鏈表中，通過頭指針能快速訪問表頭位置，訪問表尾也是不方便的。雙向鏈表也是類似的。選項D給出的鏈表，通過尾指針可以快速訪問到表尾結(jié)點，實現(xiàn)在其之后的插入，也能通過表尾結(jié)點的next指針快速找到表頭結(jié)點，實現(xiàn)刪除操作。所以，僅有尾指針的單循環(huán)鏈表是最合適的結(jié)構(gòu)。5．為了提供全程對號的高速鐵路售票系統(tǒng)，保證每一位旅客從上車到下車期間都有獨立座位，短途乘客下車后該座位可以銷售給其他乘客，鐵路公司設(shè)計了基于內(nèi)存的系統(tǒng)，系統(tǒng)中需要描述座位信息和每個座位的售票情況。保存座位信息和每個座位售票情況的數(shù)據(jù)結(jié)構(gòu)分別是________。A．?dāng)?shù)組，數(shù)組 B．?dāng)?shù)組，鏈表C．鏈表，數(shù)組 D．鏈表，鏈表答案：B。高鐵上，每節(jié)車廂都有自己固定的座位數(shù)，不變化，所以可以使用數(shù)組來描述座位。但每個座位的售票情況是隨時變化的，應(yīng)當(dāng)使用動態(tài)的結(jié)構(gòu)來描述，故選用鏈表來描述。6．若長度為n的線性表采用順序存儲結(jié)構(gòu)，則在其第i(0≤i≤n)個位置插入一個新元素的算法的時間復(fù)雜度為________。A．O(1) B．O(i) C．O(n) D．O(n2)答案：C。順序表中，插入操作會導(dǎo)致從插入位置至表尾的全部元素依次后移一個位置。平均情況下，要移動一半的元素，所以時間復(fù)雜度是O(n)。7．對于含n個元素采用順序存儲的線性表，訪問位置i（0≤i≤n-1）處的元素和在位置i（0≤i≤n）插入元素的時間復(fù)雜度分別為________。A．O(n)和O(n) B．O(n)和O(1) C．O(1)和O(n) D．O(1)和O(1)答案：C。順序表中，訪問結(jié)點時可以根據(jù)下標(biāo)直接計算地址，所以時間復(fù)雜度是O(1)。而插入結(jié)點的時間復(fù)雜度是O(n)。8．線性表(a0,a1,…,an-1)以鏈接方式存儲時，訪問位置i的元素的時間復(fù)雜度為________。A．O(1) B．O(i-1) C．O(i) D．O(n)答案：D。鏈?zhǔn)酱鎯€性表時，如果要訪問表中的結(jié)點，通常會從表頭開始，逐個結(jié)點依次遍歷過來，平均而言，要訪問表中一半的元素。9．在帶頭結(jié)點的非空單循環(huán)鏈表head中，指向尾結(jié)點的指針p滿足的條件是________。A．p==NULL B．p==headC．p->next==head D．p->next==NULL答案：C。若單循環(huán)鏈表head非空，則必有尾結(jié)點，尾結(jié)點的next指向頭結(jié)點，也就是說，p指向結(jié)點的next值應(yīng)該等于head的值（選項C正確）。若指針p的值是NULL（選項A），則表示指針p沒有指向任何結(jié)點。若p==head（選項B），則表示p與頭指針指向相同，而頭指針指向的是頭結(jié)點（虛擬結(jié)點），在非空鏈表中，尾結(jié)點不是頭結(jié)點。如果不是循環(huán)鏈表，則尾結(jié)點的next值為NULL（選項D）。10．帶頭結(jié)點的單鏈表head為空的判定條件是________。A．head==NULL B．head!=NULLC．head->next==head D．head->next==NULL答案：D。帶頭結(jié)點的空單鏈表是僅含有頭結(jié)點（虛擬結(jié)點）的鏈表，頭結(jié)點的next值為NULL，即它沒有后繼結(jié)點。因為含有頭結(jié)點，故頭指針head在任何時刻都不能為空（選項A不正確）。對于空表與非空表，head!=NULL（選項B）都是成立的，所以用這個條件不能判定表是否為空。head->next==head表明頭結(jié)點的next指針又指向頭結(jié)點，這是空循環(huán)鏈表的狀態(tài)。head->next==NULL表示的是頭指針指向的結(jié)點沒有后繼結(jié)點，這正是空鏈表要滿足的條件。11．在雙向循環(huán)鏈表中，在指針p所指結(jié)點之后插入指針s所指結(jié)點的操作是________。A．p->next=s;s->prev=p;p->next->prev=s;s->next=p->next;B．p->next=s;p->next->prev=s;s->prev=p;s->next=p->next;C．s->prev=p;s->next=p->next;p->next=s;p->next->prev=s;D．s->prev=p;s->next=p->next;p->next->prev=s;p->next=s;答案：D。解答這樣的題目時，畫圖是個不錯的方法。比如，執(zhí)行了選項A中前兩個語句（p->next=s;s->prev=p;）后，得到的鏈表狀態(tài)如圖2.1所示。pp…AB…Xs圖2.1對應(yīng)于選項A的單鏈表其中，第3個語句“p->next->prev=s;”是將結(jié)點X的prev指針又指回自己，這顯然是錯誤的。其他的3個選項，可以畫出類似的鏈表狀態(tài)。12．在一個單鏈表中，已知q所指結(jié)點是p所指結(jié)點的前驅(qū)結(jié)點，若在q和p之間插入s結(jié)點，則執(zhí)行的操作是________。A．s->next=p->next;p->next=s; B．p->next=s->next;s->next=p;C．q->next=s;s->next=p; D．p->next=s;s->next=q;答案：C。以選項A為例，執(zhí)行了其中的兩條語句后，單鏈表的狀態(tài)如圖2.2所示。這表明，結(jié)點s插入在了結(jié)點p的后面，而不是插入在q和p之間。ppqs………BC…X圖2.2對應(yīng)于選項A的單鏈表13．在一個單鏈表中，若p所指結(jié)點不是終端結(jié)點，在p所指結(jié)點之后插入s所指結(jié)點，則執(zhí)行的操作是________。A．s->next=p;p->next=s; B．s->next=p->next;p->next=s;C．s->next=p->next;p=s; D．p->next=s;s->next=p;答案：B。二、填空題1．線性表是一個有限序列，組成線性表的是n（n≥0）個__________。答案：同類型的數(shù)據(jù)元素。線性表的定義要求組成線性表的數(shù)據(jù)元素是同類型的。2．不帶頭結(jié)點的單鏈表L（head為頭指針）為空的判定條件是__________。答案：head==NULL。不帶頭結(jié)點的空單鏈表中一個結(jié)點都沒有，頭指針的值為NULL。3．帶頭結(jié)點的雙向循環(huán)鏈表L（head為頭指針）為空的條件是__________。答案：head->next==head或是head->prev==head帶頭結(jié)點的空雙向循環(huán)鏈表中僅有一個頭結(jié)點，且這個結(jié)點的next指針和prev指針都指向結(jié)點本身，即與head指向相同。4．在帶頭結(jié)點的單鏈表中，當(dāng)刪除某一指定結(jié)點時，必須要找到該結(jié)點的__________。答案：前驅(qū)。被刪除結(jié)點的后繼結(jié)點，變?yōu)楸粍h除結(jié)點原前驅(qū)結(jié)點的后繼，所以要找到前驅(qū)結(jié)點，并修改它的next值。三、解答題1．在單鏈表中設(shè)置頭結(jié)點的作用是什么？【參考答案】在單鏈表中進(jìn)行插入和刪除操作時，都要找到操作位置結(jié)點的前驅(qū)結(jié)點。但根據(jù)線性表當(dāng)前指針的原始定義，前驅(qū)結(jié)點是不能通過當(dāng)前指針直接找到的。所以，修改當(dāng)前指針指向的結(jié)點，讓其前移一個位置，即指向操作位置的前驅(qū)結(jié)點。這樣修改后，通過當(dāng)前指針很容易訪問到插入和刪除操作所涉及的各個結(jié)點。但當(dāng)操作位置是第一個結(jié)點時，或是單鏈表是空表時，當(dāng)前指針的指向又成為特殊情況，需要單獨處理。為了能統(tǒng)一處理各種情況，給單鏈表添加一個虛擬結(jié)點，即頭結(jié)點，從而減少實現(xiàn)插入和刪除操作時對特殊情況的判定及處理情況。2．什么是單鏈表中的頭結(jié)點、第一個數(shù)據(jù)結(jié)點和頭指針？【參考答案】單鏈表中保存線性表中各數(shù)據(jù)的結(jié)點是數(shù)據(jù)結(jié)點，這些結(jié)點中的第一個是第一個數(shù)據(jù)結(jié)點。它的前面是一個虛擬結(jié)點，稱為頭結(jié)點。一個特殊的指向單鏈表中最前面結(jié)點的指針是頭指針。如果單鏈表中一個結(jié)點都沒有，則頭指針為空。3．假設(shè)線性表L=(51,40,19,15,24,36)，使用線性表ADT中定義的方法，列出刪除19時對應(yīng)的語句序列。【參考答案】if(!isEmpty(L)){ intpos,x; pos=find(L,19); if(pos>=0)remove(&L,pos,&x);}4．已知線性表中一個元素占8個字節(jié)，一個指針占2個字節(jié)，數(shù)組的大小為20個元素。在順序及鏈?zhǔn)絻煞N存儲方式中，線性表應(yīng)該采用哪種方式保存？為什么？【參考答案】設(shè)線性表中元素個數(shù)為n。單純考慮空間復(fù)雜度。采用順序存儲時，占用的空間大小=208=160個字節(jié)。采用鏈?zhǔn)酱鎯r，假設(shè)采用單鏈表存儲，占用的空間大小=n(8+2)=10n個字節(jié)。列方程，10n=160，求得n=16。即若線性表中元素個數(shù)少于16個時，采用單鏈表保存更好，元素個數(shù)多于16個時，采用數(shù)組保存更好。等于16個時，兩種方式保存的效果是一樣的。5．在單鏈表和雙向鏈表中，能否從當(dāng)前結(jié)點出發(fā)訪問到表中的任何一個結(jié)點?【參考答案】在單鏈表和雙向鏈表中，如果是從頭結(jié)點或第一個數(shù)據(jù)結(jié)點出發(fā)，能訪問到表中的任一結(jié)點，但從其他結(jié)點出發(fā)，都只能訪問到該結(jié)點及其全部的后繼結(jié)點，它的前驅(qū)結(jié)點是訪問不到的。6．線性表(a0,a1,…,an-1)采用順序存儲方式時，ai和ai+1（0≤i<n-1）的物理位置相鄰嗎？采用鏈?zhǔn)椒绞綍r呢？【參考答案】采用順序存儲方式時，ai和ai+1（0≤i<n-1）的物理位置是相鄰的。采用鏈?zhǔn)酱鎯r，ai和ai+1（0≤i<n-1）的物理位置不一定是相鄰的?？赡芟噜徱部赡懿幌噜?。7．試分析雙向鏈表中插入、刪除、查找等基本操作的時間復(fù)雜度?！緟⒖即鸢浮吭陔p向鏈表中進(jìn)行插入和刪除操作時，如果給定了當(dāng)前指針，則插入操作和刪除操作的時間復(fù)雜度均為O(1)，因為操作過程中不需要進(jìn)行元素的移動，也不需要將當(dāng)前指針從表頭后移到當(dāng)前位置。查找操作的時間復(fù)雜度是根據(jù)查找目標(biāo)在鏈表中的位置而定的。若在雙向鏈表中一定能找到查找目標(biāo)，則最優(yōu)情況下，比較1次就能找到，時間復(fù)雜度為O(1)。最壞的情況下，需要進(jìn)行n次比較，時間復(fù)雜度為O(n)。平均來看，需要查找約一半的鏈表，所以時間復(fù)雜度是O(n)。四、算法閱讀題1．在如主教材圖2.13(b)所示的帶頭結(jié)點的非空循環(huán)鏈表中保存了若干整數(shù)。算法average求出這些整數(shù)的平均值。請在空白處填上適當(dāng)內(nèi)容將算法補(bǔ)充完整。floataverage(LinkListhead){ LinkNode*p; intcounter=0,sum=0; if(head==NULL){ printf("鏈表錯誤\n"); return0; } if(（1）)printf("這是一個空鏈表\n"); else{ p=head->next; while(（2）){ counter++; sum+=p->data; p=p->next; } } return（3）;}【參考答案】（1）head->next==head（2）p!=head（3）sum*1.0/counter對于（1），根據(jù)后面輸出的內(nèi)容可知，這里需要補(bǔ)上判定空表的條件。帶頭結(jié)點的空循環(huán)鏈表只含有一個頭結(jié)點，且該結(jié)點的next域指向結(jié)點本身。對于（2），根據(jù)題意，循環(huán)體中要對表中的全部結(jié)點進(jìn)行處理。進(jìn)入循環(huán)之前，指針p指向了第一個數(shù)據(jù)結(jié)點。while循環(huán)的結(jié)束條件是什么呢？當(dāng)指針p轉(zhuǎn)回到表頭時，表明已經(jīng)處理完全部的數(shù)據(jù)結(jié)點，此時循環(huán)可以結(jié)束。也就是在p沒有指向頭結(jié)點時，循環(huán)不結(jié)束。當(dāng)p==head時表明p指向頭結(jié)點，當(dāng)p!=head時表明p沒有指向頭結(jié)點。對于（3），返回的是表中元素的平均值。while循環(huán)體中已經(jīng)計算了全部元素的和及元素個數(shù)，兩個值做除法就可以了。注意不要進(jìn)行整除，兩個整數(shù)相除，結(jié)果可能除不盡，是個實型值。2．單鏈表的結(jié)點及鏈表定義如下：typedefstructnode{ intdata; //數(shù)據(jù)域 structnode*next; //指針域}LinkNode;typedefLinkNode*LinkList; //單鏈表算法largest找出這些整數(shù)中的最大值。請在空白處填上適當(dāng)內(nèi)容將算法補(bǔ)充完整。intlargest(LinkListhead){ LinkNode*p; intmaxitem; if(head==NULL){ printf("鏈表錯誤\n"); return0; } if(（1）)printf("這是一個空鏈表\n"); else{ p=head->next; maxitem=p->data; p=p->next; while(p!=NULL){ if(（2）)（3）; p=p->next; } } returnmaxitem;}【參考答案】（1）head->next==NULL（2）p->data>maxitem（3）maxitem=p->data對于（1），空單鏈表中僅含有一個頭結(jié)點，頭指針指向結(jié)點的next域為NULL。根據(jù)題意，要記錄表中元素的最大值，這由if語句來完成。顯然，if的條件是篩選最大值，后面的語句是將最大值保存下來。return語句中返回的是maxitem的值，意味著這個變量是用來保存最大值的，所以（3）的內(nèi)容很容易寫下來，就是將當(dāng)前結(jié)點中的值賦給maxitem。那么，當(dāng)前結(jié)點需要滿足什么條件呢？是要大于原來保存的maxitem值，這是（2）要填寫的內(nèi)容。3．閱讀程序，并回答下列問題。intcounterofodd(LinkListhead){ LinkNode*p; intcounter=0; if(head==NULL){printf("鏈表錯誤\n");return0;} if(head->next==NULL)printf("這是一個空鏈表\n"); else{ p=head->next; while(p!=NULL){ if(p->data%2!=0)counter++; p=p->next; } } returncounter;}（1）若單鏈表head中保存的是(1,3,5,7,10)，則執(zhí)行counterofodd(head)后，返回的結(jié)果是什么？（2）counterofodd()的功能是什么？【參考答案】（1）返回的結(jié)果是4。（2）counterofodd()的功能是統(tǒng)計單鏈表head中保存的奇數(shù)的個數(shù)。五、算法設(shè)計題1．設(shè)有一個正整數(shù)序列組成的有序單鏈表（按遞增次序有序，且允許有相等的整數(shù)存在），試編寫能實現(xiàn)下列功能的算法：（1）確定在序列中比正整數(shù)x大的數(shù)有幾個（相同的數(shù)只計算一次，如有序序列{10,20,30,30,40,41,50,50,51}中比30大的數(shù)有4個）；（2）將單鏈表中比正整數(shù)x小的數(shù)按遞減次序重排，仍放置在單鏈表中；如保存有序序列{10,20,30,30,40,41,50,50,51}的單鏈表中，將比40小的數(shù)重排后，得到的單鏈表中保存的序列是{30,30,20,10,40,41,50,50,51}。（3）將比x大的偶數(shù)從單鏈表中刪除?！緟⒖即鸢浮浚?）程序?qū)崿F(xiàn)如下所示。intlargerthanx(LinkListhead,intx){ intcounter=0,lastone; LinkNode*p; if(head==NULL){ printf("鏈表錯誤\n"); return0; } if(head->next==NULL)printf("這是一個空鏈表\n"); else{ p=head->next; lastone=p->data-1; while(p!=NULL){ if(p->data>x){ if(p->data>lastone){ counter++; lastone=p->data; } } p=p->next; } } returncounter;}因為單鏈表有序，所以，如果有相同的整數(shù)，則它們一定是相鄰的。使用變量lastone記錄前一個整數(shù)，如果當(dāng)前整數(shù)與lastone相等，則不計數(shù)。lastone的初值設(shè)為比第一個整數(shù)小的任何數(shù)即可。（2）程序?qū)崿F(xiàn)如下所示。intreversesmallthanx(LinkListhead,intx){ LinkNode*left,*middle,*right,*temp; if(head==NULL){ printf("鏈表錯誤\n"); return0; } if(head->next==NULL){ printf("這是一個空鏈表\n"); return1; } else{ temp=left=head->next; if(left!=NULL)middle=left->next; while(middle!=NULL&&middle->data<x){ right=middle->next; middle->next=left; left=middle; middle=right; } if(middle==NULL){ temp->next=NULL; head->next=left; } else{ temp->next=middle; head->next=left; } } return1;}將單鏈表中比正整數(shù)x小的數(shù)按遞減次序重排，實際上是將單鏈表前面的若干結(jié)點逆置。與教材第二章第五節(jié)中給出的reverse有些類似，但情況更復(fù)雜一些。當(dāng)找不到比x小的元素時，單鏈表維持不變。當(dāng)所有元素均小于x時，整個鏈表逆置。當(dāng)部分元素小于x時，只逆置前面的這些元素，逆置后的子表還要與原來的后半部分子表拼起來。（3）程序?qū)崿F(xiàn)如下所示。intremoveevenlargethanx(LinkListhead,intx){ LinkNode*current; intk; if(head==NULL){ printf("鏈表錯誤\n"); return0; } if(head->next==NULL){ printf("這是一個空鏈表\n"); return1; } else{ current=head; while(current->next!=NULL){ if(current->next->data>x&¤t->next->data%2==0){ removemy(head,current,&k); } elsecurrent=current->next; } } return1;}刪除滿足條件的元素時，可以調(diào)用單鏈表中實現(xiàn)的remove操作。要注意的是，刪除一個結(jié)點后，當(dāng)前指針current不改變，此時，current不后移，繼續(xù)判斷它指向結(jié)點的后繼結(jié)點。但如果沒有刪除結(jié)點，則current需要后移一個位置。2．在單鏈表L中保存了若干整數(shù)。實現(xiàn)算法將L分為兩個單鏈表L1和L2，其中L1中保存奇數(shù)，L2中保存偶數(shù)?！緟⒖即鸢浮砍绦?qū)崿F(xiàn)如下所示。intpartition(LinkList*L,LinkList*L1,LinkList*L2){ LinkNode*L1curr,*L2curr; LinkNode*temp; if((*L)==NULL){ printf("鏈表錯誤\n"); return0; } initList(L1); initList(L2); if((*L)->next==NULL){ printf("這是一個空鏈表\n"); return1; } else{ temp=(*L)->next; L1curr=*L1; L2curr=*L2; while(temp!=NULL){ (*L)->next=temp->next; temp->next=NULL; if(temp->data%2==0){ L2curr->next=temp; L2curr=L2curr->next; (*L2)->data++; } else{ L1curr->next=temp; L1curr=L1curr->next; (*L1)->data++; } temp=(*L)->next; } } return1;}將單鏈表L拆分為兩個單鏈表L1和L2，實際上就是從L中刪除一個結(jié)點，然后根據(jù)結(jié)點中值的奇偶性，或是將結(jié)點添加到L1中，或是將結(jié)點添加到L2中。因為刪除和插入都是依次進(jìn)行的，所以，設(shè)置一個當(dāng)前工作指針記錄三個鏈表的當(dāng)前位置。3．已知帶頭結(jié)點的單鏈表的每個結(jié)點中保存一個整數(shù)，數(shù)據(jù)結(jié)點有n個。請設(shè)計算法以判斷該鏈表中保存的值是否構(gòu)成斐波那契數(shù)列中的前n項。若是算法返回1，否則返回0?！緟⒖即鸢浮砍绦?qū)崿F(xiàn)如下所示。intisFibonacci(LinkListhead){ LinkNode*p1,*p2,*p3; intf1=1,f2=1,f3,i; if(head==NULL){ printf("鏈表錯誤\n"); return0; } if(head->next==NULL){ printf("這是一個空鏈表\n"); return0; } if(head->data==1&&head->next->data==1)return1; if(head->data==2&&head->next->data==1&&head->next->next->data==1) return1; p1=head->next; if(p1->data!=1)return0; p2=p1->next; if(p2->data!=1)return0; p3=p2->next; while(p3!=NULL&&p3->data==p1->data+p2->data){ p1=p2; p2=p3; p3=p3->next; } if(p3==NULL)return1; elsereturn0;}斐波那契數(shù)列中含有多個整數(shù)值，如果整數(shù)的個數(shù)少于3個，則為特殊情況，程序中需要對此進(jìn)行特殊的處理。即單鏈表中數(shù)據(jù)結(jié)點的個數(shù)少于3個時，需要單獨進(jìn)行判定。前兩個結(jié)點中的整數(shù)都是1。當(dāng)結(jié)點個數(shù)大于等于3個時，從第三個結(jié)點開始，一直到尾結(jié)點，判定每個結(jié)點中保存的整數(shù)是否是相鄰的前兩個結(jié)點中值的和。4．實現(xiàn)算法，判斷帶頭結(jié)點的單鏈表中所保存的整數(shù)，是否構(gòu)成遞增有序序列。若是遞增有序序列，則算法返回1；若不是有序序列，則算法返回0?！緟⒖即鸢浮砍绦?qū)崿F(xiàn)如下所示。intisincrease(LinkListhead){ LinkNode*p; intcurrmax; if(head==NULL){ printf("鏈表錯誤\n"); return0; } if(head->next==NULL){ printf("這是一個空鏈表\n"); return1; } p=head->next; //第一個數(shù)據(jù)結(jié)點 currmax=p->data; p=p->next; while(p!=NULL&&p->data>=currmax){ p=p->next; } if(p==NULL)return1; elsereturn0; }5．設(shè)線性表元素為整數(shù)，其中可能有相同的元素。試設(shè)計一個算法刪除表中重復(fù)的元素（即相同元素只保留一個），使刪除后表中各元素均不相同。給出在順序存儲和鏈?zhǔn)酱鎯煞N方式下的實現(xiàn)程序。【參考答案】線性表如果有序，則很容易刪除表中的重復(fù)元素。但當(dāng)線性表無序時，需要進(jìn)行更多的比較才能實現(xiàn)。采用順序存儲方式的程序?qū)崿F(xiàn)如下所示。intunique(LinearList*L){ inti,j,k,len; intNA=-65535; //NA用來做標(biāo)記 len=L->n; for(i=1;i<len;i++) for(j=0;j<i;j++){ if(L->element[i]==L->element[j])L->element[i]=NA; } k=1; for(i=1;i<len;i++){ if(L->element[i]!=NA){ L->element[k++]=L->element[i]; } } L->n=k; return1;}從數(shù)組中刪除一個重復(fù)元素時，后面的元素都要依次向前移動。為避免過多的元素移動，當(dāng)發(fā)現(xiàn)重復(fù)元素時，僅對重復(fù)元素進(jìn)行標(biāo)記，而不是立即進(jìn)行刪除。當(dāng)查找到所有重復(fù)元素后，再將剩余元素依次保存到數(shù)組最前面的若干位置中。使用NA標(biāo)記要刪除的元素。采用鏈?zhǔn)酱鎯Ψ绞降某绦驅(qū)崿F(xiàn)如下所示。voidunique(LinkListhead){ LinkNode*p,*current; intk; if(head==NULL){ printf("鏈表錯誤\n"); return; } if(head->next==NULL){ printf("這是一個空鏈表\n"); return; } if(head->data==1)return; current=head->next; p=current; while(current!=NULL&¤t->next!=NULL){ p=current; while(p->next!=NULL){ if(p->next->data==current->data){ removemy(head,p,&k); } elsep=p->next; } current=current->next; } return; }current是當(dāng)前指針，指示當(dāng)前結(jié)點。使用另一個指針p從當(dāng)前位置開始向后依次掃描結(jié)點。當(dāng)p指向結(jié)點的后繼結(jié)點中的值與current所指結(jié)點中的值相等時，刪除重復(fù)結(jié)點，即刪除p所指結(jié)點的后繼結(jié)點。可以調(diào)用remove函數(shù)完成刪除操作。當(dāng)p指向表尾時，表示一輪掃描完成，current指向下一個結(jié)點，繼續(xù)同樣的查重及刪除操作。6．設(shè)有兩個按元素值遞增有序排列的單鏈表A和B。試實現(xiàn)算法，將它們合并成一個單鏈表C，要求C的元素值仍按遞增有序排列（允許C中有值相同的元素）?！緟⒖即鸢浮砍绦?qū)崿F(xiàn)如下所示。voidmergelist(LinkList*A,LinkList*B,LinkList*C){ LinkNode*pA=*A,*pB=*B,*pC=*C,*temp; while(pA->next!=NULL&&pB->next!=NULL){ if(pA->next->data<pB->next->data){ temp=pA->next; pA->next=temp->next; temp->next=NULL; pC->next=temp; (*A)->data--; } else{ temp=pB->next; pB->next=temp->next; temp->next=NULL; pC->next=temp; (*B)->data--; } pC=pC->next; (*C)->data++; } if(pA->next==NULL){ pC->next=pB->next; pB->next=NULL; (*C)->data+=(*B)->data; } else{ pC->next=pA->next; pA->next=NULL; (*C)->data+=(*A)->data; } return;}因為兩個單鏈表A和B是遞增有序的，合并后的鏈表也要求是遞增有序的，所以可以分別從前向后掃描A和B。使用三個工作指針分別指向A、B和C的當(dāng)前位置。比較A和B當(dāng)前結(jié)點中元素的值，將更小值的結(jié)點移至鏈表C中。這個思想是二路歸并排序中兩個有序歸并段合并的思想?？梢詤⒖嫉?章第五節(jié)的相關(guān)內(nèi)容。

第三章棧和隊列一、單項選擇題1．棧操作數(shù)據(jù)的原則是________。A．先進(jìn)先出 B．后進(jìn)先出 C．后進(jìn)后出 D．隨機(jī)處理答案：B。棧的特性是后進(jìn)先出。選項A是隊列的特性。有些情況下，可以將選項C理解為先進(jìn)先出，這也是隊列的特性。選項D既不是棧的特性，也不是隊列的特性。2．入棧序列是a1,a3,a5,a2,a4,a6，出棧序列是a5,a4,a2,a6,a3,a1，則棧的容量最小是________。A．2 B．3 C．4 D．5答案：C。用圖3.1表示棧狀態(tài)的變化情況。a1入棧a3入棧a5入棧a5出棧a2入棧a4入棧a4a5a2a2a3a3a3a3a3a1a1a1a1a1a1a4出棧a2出棧a6入棧a6出棧a3出棧a1出棧a2a6a3a3a3a3a1a1a1a1a1圖圖3.1棧的狀態(tài)可以看到，在a4入棧后，棧中有4個元素，這是棧含元素最多的時刻。所以棧的容量最小是4。3．6個元素6,5,4,3,2,1依次進(jìn)棧，不能得到的出棧序列是________A．5,4,3,6,1,2 B．4,5,3,1,2,6 C．3,4,6,5,2,1 D．2,3,4,1,5,6答案：C。可以使用操作過程來描述。得到選項A的操作過程是：push(6),push(5),pop(5),push(4),pop(4),push(3),pop(3),pop(6),push(2),push(1),pop(1),pop(2)。得到選項B的操作過程是：push(6),push(5),push(4),pop(4),pop(5),push(3),pop(3),push(2),push(1),pop(1),pop(2),pop(6)。得到選項D的操作過程是：push(6),push(5),push(4),push(3),push(2),pop(2),pop(3),pop(4),push(1),pop(1),pop(5),pop(6)。對于選項C，push(6),push(5),push(4),push(3),pop(3),pop(4)，此時棧頂元素是5，得不到元素6。4．輸入序列為A,B,C，借助于棧將其變?yōu)镃,B,A，經(jīng)過的棧操作為________。A．push,pop,push,pop,push,pop B．push,push,push,pop,pop,popC．push,push,pop,pop,push,pop D．push,pop,push,push,pop,pop答案：B。對應(yīng)于選項A的操作序列，得到的出棧序列是A,B,C。對應(yīng)于選項C的操作序列，得到的出棧序列是B,A,C。對應(yīng)于選項D的操作序列，得到的出棧序列是A,C,B。實際上，出棧序列與入棧序列互逆，所以必然是將所有元素依次入棧，然后依次出棧。5．用不帶頭結(jié)點的單鏈表存儲隊列時，隊頭指針指向隊頭結(jié)點，隊尾指針指向隊尾結(jié)點，則在進(jìn)行刪除操作時________。A．僅需要修改隊頭指針，不需要修改隊尾指針B．僅需要修改隊尾指針，不需要修改隊頭指針C．隊頭指針一定要修改，隊尾指針也一定要修改D．隊頭指針一定要修改，隊尾指針可能要修改答案：D。用不帶頭結(jié)點的單鏈表保存隊列時，通常需要兩個指針分別指向隊頭結(jié)點和隊尾結(jié)點。出隊時，要從隊頭刪除一個結(jié)點，此時必須修改隊頭指針，讓它指向被刪結(jié)點的后繼結(jié)點。如果隊列中還有其他結(jié)點，則隊尾指針不會變化。但如果刪除結(jié)點后隊列變?yōu)榭贞犃?，則還需要修改隊尾指針。6．假設(shè)以數(shù)組A[0..m-1]存放循環(huán)隊列的元素，隊頭指針front指向隊頭元素，隊尾指針rear指向隊尾元素后的空位置，則當(dāng)前隊列中的元素個數(shù)為________。A．(rear-front+m)%m B．rear-front+1C．(front-rear+m+1)%m D．(rear-front)%m答案：A。循環(huán)隊列有兩種基本形態(tài)，如圖3.2(a)和圖3.2(b)所示。a0…am-1↑front↑rear圖3.2(a)循環(huán)隊列示意圖一…v……u…↑rear↑front圖3.2(b)循環(huán)隊列示意圖二對于圖3.2(a)，隊列中的元素個數(shù)=rear-front。對于圖3.2(b)，隊列中的元素個數(shù)=rear+m-front。兩個表達(dá)式可以統(tǒng)一表示為(rear-front+m)%m。7．棧和隊列的共同點是________。A．都是后進(jìn)先出 B．都是先進(jìn)先出C．只允許在端點處插入和刪除元素 D．沒有共同點答案：C。棧具有后進(jìn)先出的特點，而隊列具有先進(jìn)先出的特點。所以選項A和B都不正確。棧的插入和刪除操作都在表的一端進(jìn)行，隊列的插入和刪除分別在表的兩端進(jìn)行。所以，選項C中概括的特點是棧和隊列共同具有的。8．循環(huán)隊列存儲在數(shù)組A[0..m]中，入隊時修改隊尾指針的操作為________。A．rear=rear+1 B．rear=(rear+1)%(m-1)C．rear=(rear+1)%m D．rear=(rear+1)%(m+1)答案：D。根據(jù)題意，數(shù)組A的容量是m+1，用來保存循環(huán)隊列。入隊操作時隊尾指針需要后移一個位置，即rear=rear+1。當(dāng)rear已經(jīng)指向A[m]時，此時入隊操作需要將rear修改為0，即rear=(rear+1)%(m+1)。兩個表達(dá)式可以統(tǒng)一表示為rear=(rear+1)%(m+1)。9．若用一個大小為6的數(shù)組來實現(xiàn)循環(huán)隊列，且當(dāng)前隊尾rear和隊頭front的值分別為0和3，當(dāng)從隊列中刪除一個元素，再加入兩個元素后，rear和front的值分別為________。A．1和5 B．2和4 C．4和2 D．5和答案：B。在循環(huán)隊列中插入一個元素時，rear后移一個位置。刪除一個元素時，front后移一個位置。根據(jù)題意，rear和front的值如圖3.3所示。↑

rear↑

front圖3.3當(dāng)前循環(huán)隊列刪除一個元素后，rear和front的值如圖3.4所示?！?/p>

rear↑

front圖3.4刪除一個元素后再加入兩個元素后，rear和front的值如圖3.5所示?！?/p>

rear↑

front圖3.5再加入二個元素后二、填空題1．設(shè)局域網(wǎng)中含有多臺計算機(jī)與一臺網(wǎng)絡(luò)打印機(jī)，通常打印機(jī)中會設(shè)置一個打印數(shù)據(jù)緩沖區(qū)以滿足多個打印任務(wù)的需求，該緩沖區(qū)的邏輯結(jié)構(gòu)應(yīng)該是__________。答案：隊列。網(wǎng)絡(luò)打印機(jī)通常按先來先服務(wù)的原則提供打印服務(wù)，符合隊列的特性。2．設(shè)棧S和隊列Q的初始狀態(tài)均為空，元素a,b,c,d,e,f依次進(jìn)入S。若每個元素出棧后立即進(jìn)入Q，且6個元素出隊的順序是b,d,c,f,e,a，則S的容量至少是__________。答案：3。對于隊列來說，出隊序列與入隊序列是一樣的。由題意，出隊順序是b,d,c,f,e,a，意味著入隊序列也是b,d,c,f,e,a。而這個序列即是棧的出棧序列。實際上，我們是要計算當(dāng)入棧序列是a,b,c,d,e,f，出棧序列是b,d,c,f,e,a時，占用的?？臻g最大是多少。用圖3.6表示棧狀態(tài)的變化過程。a入棧b入棧b出棧c入棧d入棧d出棧dbcccaaaaaac出棧e入棧f入棧f出棧e出棧a出棧feeeaaaaa圖圖3.6棧的狀態(tài)三、解答題1．對于一個棧，設(shè)元素入棧的次序為：A,B,C,D,E，并給定下列各序列：（1）A,B,C,D,E （2）B,C,D,E,A（3）E,A,B,C,D （4）E,D,C,B,A哪些是可以得到的出棧序列？若要得到相應(yīng)序列，需要執(zhí)行哪些棧操作？根據(jù)棧的ADT寫出操作序列。若其中某些輸出序列不可能得到，試說明理由。【參考答案】（1）、（2）和（4）都是可以得到的出棧序列。對于（1），執(zhí)行的棧操作序列是push(A),pop(A),push(B),pop(B),push(C),pop(C),push(D),pop(D),push(E),pop(E)。對于（2），執(zhí)行的棧操作序列是push(A),push(B),pop(B),push(C),pop(C),push(D),pop(D),push(E),pop(E),pop(A)。對于（4），執(zhí)行的棧操作序列是push(A),push(B),push(C),push(D),push(E),pop(E),pop(D),pop(C),pop(B),pop(A)。（3）中的序列是得不到的。為得到出棧元素E，需要執(zhí)行棧操作push(A),push(B),push(C),push(D),push(E),pop(E)，此時，棧頂是元素D，得不到元素A。2．有5個元素，其入棧次序為：A,B,C,D,E，在各種可能的出棧序列中，以元素C,D最先出棧（即C第一個出棧，且D第二個出棧）的序列有哪些？【參考答案】為了讓C第一個出棧，D第二個出棧，需要執(zhí)行棧操作push(A),push(B),push(C),pop(C),push(D),pop(D)，此時，棧中有兩個元素A和B，且還有元素E尚未入棧。元素A和B的出棧相對次序只能是B,A，在這個過程中元素E可以入棧，然后出棧。這三個元素的出棧序列有：E,B,A、B,E,A和B,A,E。以元素C,D最先出棧的序列有C,D,E,B,A、C,D,B,E,A和C,D,B,A,E。3．將兩個棧存入數(shù)組V[0..m-1]中，應(yīng)如何安排最好？這時?？?、棧滿的條件分別是什么？【參考答案】設(shè)兩個棧為S1和S2，將S1和S2保存在一個一維數(shù)組中，可以選擇對頂棧的方式，將數(shù)組的兩端分別當(dāng)作兩個棧的棧底，數(shù)組的中間位置作為棧可使用的空間，如圖3.7所示。0…k+1h-1…m-1←S1棧底←S1棧頂←S2棧頂←S2棧底圖3.7對頂棧示意圖初始時，棧S1的棧頂指針top1在V[0]，棧S2的棧頂指針top2在V[m-1]，?？盏臈l件是top1==0&&top2==m-1。當(dāng)數(shù)組中沒有空閑單元時，棧滿，如圖3.8所示。棧滿的條件是top1==top2+1。0……m-1top2top1圖3.8對頂棧滿狀態(tài)示意圖4．簡述順序存儲隊列時假溢出的避免方法及隊列滿和空的條件?！緟⒖即鸢浮繉㈥犃斜４嬖谝痪S數(shù)組中時，為使插入和刪除操作的效率更高，規(guī)定插入和刪除操作后不移動隊列中的數(shù)據(jù)元素。因此，數(shù)據(jù)保存在數(shù)組從某一下標(biāo)開始的一段連續(xù)單元中，并使用兩個變量front和rear分別記錄這段連續(xù)單元的首尾位置。當(dāng)占用的這段連續(xù)空間移至數(shù)組的最后面，也就是記錄尾位置的rear到達(dá)數(shù)組最大下標(biāo)處時，會出現(xiàn)通常意義下的數(shù)組“滿”狀態(tài)。但數(shù)組最前面的位置可能是空閑的，所以這個“滿”是假溢出?？梢允褂脭?shù)組最前面空出的位置保存后續(xù)入隊列的元素，即使用循環(huán)隊列來避免順序隊列的假溢出。為了能分辨出循環(huán)隊列的空與滿，規(guī)定循環(huán)隊列中保存的最多元素個數(shù)比數(shù)組最大容量少1。隊列滿的判定條件是：(rear+1)%n==front，其中n是數(shù)組最大容量。隊列空的判定條件是：rear==front。5．當(dāng)rear==front時，為了能區(qū)分循環(huán)隊列的空與滿，教材中使用“讓數(shù)組中始終剩余至少一個空位置”的解決方法。你還有其他的解決方法嗎？【參考答案】有兩種替代的解決方法。方法一，使用一個變量錄循環(huán)隊列的最后一個操作是入隊還是出隊。變量的類型可以是布爾類型、枚舉類型或是整型。只要能區(qū)分兩種情況即可。如果最后一個操作是入隊操作，則當(dāng)rear==front時，循環(huán)隊列為滿。如果最后一個操作是出隊操作，則當(dāng)rear==front時，循環(huán)隊列為空。方法二，使用一個整型變量記錄隊列長度。當(dāng)?shù)竭_(dá)數(shù)組最大容量時，循環(huán)隊列為滿。6．簡要敘述循環(huán)隊列的數(shù)據(jù)結(jié)構(gòu)，并寫出其初始狀態(tài)、隊列空、隊列滿時的隊頭指針與隊尾指針的值?！緟⒖即鸢浮垦h(huán)隊列采用最大容量為maxSize的一維數(shù)組保存隊列中的元素，并使用兩個變量front和rear作為隊頭指針與隊尾指針，分別記錄隊列的兩端。其數(shù)據(jù)結(jié)構(gòu)定義如下：typedefintELEMType;typedefstruct{ ELEMTypeelement[maxSize]; intfront,rear;}SeqQueue;初始狀態(tài)時，隊頭指針front==0，隊尾指針rear==0。隊列空時，rear==front。隊列滿時，(rear+1)%maxSize==front。7．假設(shè)循環(huán)隊列的rear指向隊尾元素本身，則隊列空或滿的條件分別是什么？【參考答案】隊尾指針rear指向隊尾元素，隊頭指針front指向隊頭元素，則初始時，隊頭指針front==0，隊尾指針rear==n-1，其中n是數(shù)組最大容量。隊列空時，(rear+1)%maxSize==front。隊列滿時，(rear+2)%maxSize==front。8．使用兩個棧S1和S2能模擬一個隊列嗎？使用兩個隊列Q1和Q2能模擬一個棧嗎？【參考答案】使用兩個棧S1和S2可以模擬一個隊列。使用兩個隊列Q1和Q2也可以模擬一個棧。使用兩個棧模擬一個隊列的思路：當(dāng)輸入元素（入隊列）時，將該元素入棧S1；當(dāng)輸出元素（出隊列）時，若S2非空，則S2出棧，否則將S1中的全部元素入棧S2，然后S2出棧。這樣得到的序列，與輸入序列是相同的，即用棧S1和S2模擬了隊列。使用兩個隊列模擬一個棧的思路：設(shè)定一個為主隊列，另一個為輔助隊列。不妨設(shè)初始時Q1是主隊列，Q2是輔助隊列。當(dāng)輸入元素（入棧）時，將該元素入主隊列；當(dāng)輸出元素（出棧）時，將主隊列中的元素（除最后一個外）依次出隊列并入隊到輔助隊列中，然后主隊列出隊列，交換主隊列與輔助隊列的設(shè)定。相對于輸入序列，輸出序列是合理的出棧序列。即用隊列模擬了棧。四、算法閱讀題1．給出對頂棧的定義如下。typedefintELEMType; //以int類型為例typedefstruct{ ELEMTypeelement[maxSize]; //maxSize是數(shù)組最大容量，已定義的常量 intlefttop,righttop; //兩個棧頂位置}SeqTopStack;其中，棧中的元素保存在數(shù)組element中，lefttop和righttop分別是左棧和右棧的棧頂指針。以下程序?qū)崿F(xiàn)了對頂棧的若干基本操作，請在空白處填上適當(dāng)內(nèi)容將算法補(bǔ)充完整。（1）initStack函數(shù)初始化左棧和右棧。intinitStack(SeqTopStack*mys) //初始化兩個棧{ mys->lefttop=（1）; mys->righttop=（2）; return1;}【參考答案】（1）0（2）maxSize-1初始化棧，就是設(shè)置棧頂指針，棧頂指針指向棧頂元素的下一個空位置?？諚r，棧頂指針為0。對于對頂棧，數(shù)組的兩端分別作為棧底，左棧的棧頂指針指向位置0，右棧的棧頂指針指向最大位置maxSize-1。（2）isEmpty函數(shù)判定指定的棧若為空則返回1，否則返回0。如果flag為-1時判定左棧，flag為1時判定右棧。intisEmpty(SeqTopStackmys,intflag) { if(flag==-1&&（1）)return1; if(flag==1&&（2）)return1; else（3）;}【參考答案】（1）mys.lefttop==0（2）mys.righttop==maxSize-1（3）return0因為數(shù)組中同時保存兩個棧，所以判定空棧時需要根據(jù)flag的指示分別判定。只要相應(yīng)的棧頂指針位于初始位置（0及maxSize-1），即可表明相應(yīng)的棧為空棧。（3）isFull函數(shù)判定若棧滿返回1，否則返回0。intisFull(SeqTopStackmys){ if(（1）)（2）; elsereturn0;}【參考答案】（1）mys.lefttop==mys.righttop+1（2）return1數(shù)組的空間被兩個棧共同使用，所以棧滿的判定不針對左棧或右棧。只要數(shù)組中沒有空閑空間了，無論是左棧還是右棧，都是滿的。2．給出對頂棧的定義如下。typedefintELEMType; //以int類型為例typedefstruct{ ELEMTypeelement[maxSize]; //maxSize是數(shù)組最大容量，已定義的常量 intlefttop,righttop; //兩個棧頂位置}SeqTopStack;其中，棧中的元素保存在數(shù)組element中，lefttop和righttop分別是左棧和右棧的棧頂指針。說明clear函數(shù)的功能。intclear(SeqTopStack*mys,intflag){ if(flag==-1)mys->lefttop=0; elseif(flag==1)mys->righttop=maxSize-1; else{ mys->lefttop=0; mys->righttop=maxSize-1; } return1;}【參考答案】clear函數(shù)的功能是清空棧，flag為-1時清空左棧，flag為1時清空右棧，flag為0時清空兩個棧。五、程序設(shè)計題1．現(xiàn)使用一個數(shù)組存儲兩個對頂棧，試實現(xiàn)入棧操作?！緟⒖即鸢浮砍绦?qū)崿F(xiàn)如下所示。intpush(SeqTopStack*mys,ELEMTypex,intflag) //將元素x入棧，flag=-1入左棧，flag=1入右棧{ if(!isFull(mys)) if(flag==-1){ //入左棧 mys->element[mys->lefttop++]=x; } else{ //入右棧 mys->element[mys->righttop--]=x; } else{ printf("棧滿\n"); return0; } return1;}入棧時需要指明是入左棧還是入右棧。入左棧的操作與通常的入棧操作是類似的。入右棧的操作有些差別，入棧后棧頂指針向下標(biāo)0的方向變化。2．現(xiàn)使用一個數(shù)組存儲兩個對頂棧，試實現(xiàn)出棧操作?！緟⒖即鸢浮砍绦?qū)崿F(xiàn)如下所示。intpop(SeqTopStack*mys,ELEMType*x,intflag) //返回棧頂元素，flag=-1出左棧，flag=1出右棧{ if(!isEmpty(mys,flag)) if(flag==-1){ *x=mys->element[--mys->lefttop]; return1; } else{ *x=mys->element[++mys->righttop]; return1; } else{ printf("?？誠n"); return0; }}出棧時需要指明是從左棧出棧還是從右棧出棧。從左棧出棧的操作與通常的出棧操作是類似的。從右棧出棧的操作有些差別，出棧后棧頂指針向下標(biāo)maxSize-1的方向變化。3．定義循環(huán)隊列的rear指向隊尾元素本身，實現(xiàn)入隊和出隊操作?！緟⒖即鸢浮砍绦?qū)崿F(xiàn)如下所示。typedefintELEMType;typedefstruct{ ELEMTypeelement[maxSize]; intfront,rear;}SeqQueue;intenqueue(SeqQueue*myq,ELEMTypex) //x入隊{ if(isFull(*myq)==1)return0; myq->element[(++myq->rear)%maxSize]=x; return1;}intdequeue(SeqQueue*myq,ELEMType*x) //出隊，并通過x返回{ if(isEmpty(*myq)==1)return0; *x=myq->element[myq->front++]; return1;}循環(huán)隊列的rear指向隊尾元素本身，不只影響入隊和出隊操作，還會影響隊列其他基本操作的實現(xiàn)細(xì)節(jié)。請考生自行完成其他操作的實現(xiàn)。

第四章數(shù)組、廣義表和串一、單項選擇題1．假定一個二維數(shù)組的定義語句為inta[3][4]={{3,4},{2,8,6}};，則元素a[1][2]的值為________。A．8 B．6 C．4 D．2答案：B。由定義可知，數(shù)組a的狀態(tài)如下所示。a=a[1][2]代表的是第2行第3列的元素6。2．在C語言中，設(shè)有數(shù)組定義：chararray[]="China";，則數(shù)組array所占用的空間為________。A．4個字節(jié) B．5個字節(jié) C．6個字節(jié) D．7個字節(jié)答案：C。使用數(shù)組保存字符串常量時，系統(tǒng)自動添加結(jié)束符'\0'。給array賦值的字符串常量含5個字符，占5個字節(jié)，再加上結(jié)束符占一個字節(jié)，總共需要6個字節(jié)。3．關(guān)于主對角線（從左上角到右下角）對稱的矩陣為對稱矩陣；如果一個矩陣中的各個元素取值為0或1，那么該矩陣可稱為0-1矩陣。大小為nn的0-1對稱矩陣的個數(shù)是________。A．pow(2,n) B．pow(2,nn/2)C．pow(2,(nn+n)/2) D．pow(2,(nn-n)/2)答案：C。nn的0-1矩陣的元素個數(shù)是nn，對稱矩陣中上三角部分與下三角部分對稱相等，上三角部分或下三角部分再加上主對角線的元素個數(shù)是1+2+…+n=n(n+1)/2=(nn+n)/2。每個元素取值為0和1，有2種，故不同的對稱矩陣個數(shù)為2(nn+n)/2。pow函數(shù)是C語言中計算冪次的函數(shù)，pow(x,y)返回x的y次冪的值。4．有一個二維數(shù)組A[10][5]，每個數(shù)據(jù)元素占1個字節(jié)，按行主序保存，且A[0][0]的存儲地址是1000，則A[i][j]的地址是________。A．1000+10i+j B．1000+i+j C．1000+5i+j D．1000+10i+5j答案：C。二維數(shù)組A[10][5]對應(yīng)的矩陣為10行5列。采用按行主序的方式保存時，A[i][j]的前面已經(jīng)保存了0行、1行、…、i-1行（共i行）的元素，每行有5個，共5i個元素。當(dāng)前行中還有j個元素排在前面。每個元素占1個字節(jié)，故A[i][j]相對于數(shù)組首地址的偏移量是5i+j，再加上首地址，就是A[i][j]的地址。5．?dāng)?shù)組通常具有的兩種基本操作是________。A．查找和修改 B．查找和索引 C．索引和修改 D．建立和刪除答案：A。有些教材中，將數(shù)組下標(biāo)稱為索引，這是數(shù)組自身具有的特性，不是索引操作。在分塊索引存儲方式中，或是數(shù)據(jù)庫中，都會建立索引。當(dāng)數(shù)據(jù)有更新時，索引也需要更新。6．已知廣義表LS=(((a)),((b,(c)),(d,(e,f))),())，LS的長度是________。A．2 B．3 C．4 D．5答案：B。LS中，第一個元素是((a))，它也是表頭，第二個元素是((b,(c)),(d,(e,f)))，第三個元素是()，所以長度是3。7．已知廣義表LS=(((a)),((b,(c)),(d,(e,f))),())，LS的深度是________。A．2 B．3 C．4 D．5答案：C。對LS中嵌套的括號進(jìn)行計數(shù)，如圖4.1所示。(((a)),((b,(C)),(d,(e,f))),())123212343234321210圖圖4.1對LS中嵌套的括號進(jìn)行計數(shù)可以看到，最大計數(shù)是4，由此得到LS的深度為4。8．已知廣義表LS=(((a)),((b,(c)),(d,(e,f))),())，Head(LS)的值是________。A．() B．a(chǎn) C．(a) D．((a))答案：D。9．已知廣義表LS=(((a)),((b,(c)),(d,(e,f))),())，Tail(LS)的值是________。A．() B．(((b,(c)),(d,(e,f))),())C．((b,(c)),(d,(e,f))) D．(())答案：B。二、填空題1．采用靜態(tài)方式壓縮保存稀疏矩陣的方法是__________。答案：三元組表法。2．設(shè)有一維整型數(shù)組data，計算數(shù)組data元素數(shù)量的表達(dá)式是__________。答案：sizeof(data)/sizeof(int)。3．若nn矩陣M是一個對稱矩陣，Mij表示i行j列的元素，則對所有的i和j，Mij和Mji滿足__________。答案：Mij=Mji(i,j=0,1,…,n-1)。三、解答題1．設(shè)有數(shù)組score[u1][u2][u3]，采用列主序方式保存，寫出映射函數(shù)。【參考答案】數(shù)組score[u1][u2][u3]是三維數(shù)組，按列主序保存時，映射函數(shù)為：map(i1,i2,i3)=i3u2u1+i2u1+i1以D3Array[3][2][4]為例，按列主序下標(biāo)排列的形式如圖4.2所示。[0][0][0][1][0][0][2][0][0][0][1][0][1][1][0][2][1][0][0][0][1][1][0][1][2][0][1][0][1][1][1][1][1][2][1][1][0][0][2][1][0][2][2][0][2][0][1][2][1][1][2][2][1][2][0][0][3][1][0][3][2][0][3][0][1][3][1][1][3][2][1][3]圖圖4.2三維數(shù)組D3Array的下標(biāo)排列形式比如，保存元素D3Array[2][1][2]的單元，距離數(shù)組首地址的偏移量為：map(2,1,2)=223+13+2=17，與實際相符。保存D3Array[0][0][0]的單元編號為0的話，則D3Array[2][1][2]保存在編號為17的單元中。2．有三對角矩陣A[i][j](0≤i,j≤n-1)如下所示。采用行主序方式僅保存主對角線及兩個副對角線中的元素。設(shè)元素A[i][j](0≤i,j≤n-1)保存在B[k](0≤k≤n(n+1)/2-1)中。給出地址映射函數(shù)。【參考答案】地址映射函數(shù)如下：k=2×i+ji≥03．給出四維數(shù)組按行主序存儲的地址映射函數(shù)。【參考答案】對于四維數(shù)組FourDimenArray[u1][u2][u3][u4]，其行主序的映射函數(shù)應(yīng)為：map(i1,i2,i3,i4)=i1u2u3u4+i2u3u4