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

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

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

rear↑

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

rear↑

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

rear↑

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

第四章數(shù)組、廣義表和串一、單項(xiàng)選擇題1．假定一個(gè)二維數(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個(gè)字節(jié) B．5個(gè)字節(jié) C．6個(gè)字節(jié) D．7個(gè)字節(jié)答案：C。使用數(shù)組保存字符串常量時(shí)，系統(tǒng)自動(dòng)添加結(jié)束符'\0'。給array賦值的字符串常量含5個(gè)字符，占5個(gè)字節(jié)，再加上結(jié)束符占一個(gè)字節(jié)，總共需要6個(gè)字節(jié)。3．關(guān)于主對(duì)角線（從左上角到右下角）對(duì)稱的矩陣為對(duì)稱矩陣；如果一個(gè)矩陣中的各個(gè)元素取值為0或1，那么該矩陣可稱為0-1矩陣。大小為nn的0-1對(duì)稱矩陣的個(gè)數(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矩陣的元素個(gè)數(shù)是nn，對(duì)稱矩陣中上三角部分與下三角部分對(duì)稱相等，上三角部分或下三角部分再加上主對(duì)角線的元素個(gè)數(shù)是1+2+…+n=n(n+1)/2=(nn+n)/2。每個(gè)元素取值為0和1，有2種，故不同的對(duì)稱矩陣個(gè)數(shù)為2(nn+n)/2。pow函數(shù)是C語言中計(jì)算冪次的函數(shù)，pow(x,y)返回x的y次冪的值。4．有一個(gè)二維數(shù)組A[10][5]，每個(gè)數(shù)據(jù)元素占1個(gè)字節(jié)，按行主序保存，且A[0][0]的存儲(chǔ)地址是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]對(duì)應(yīng)的矩陣為10行5列。采用按行主序的方式保存時(shí)，A[i][j]的前面已經(jīng)保存了0行、1行、…、i-1行（共i行）的元素，每行有5個(gè)，共5i個(gè)元素。當(dāng)前行中還有j個(gè)元素排在前面。每個(gè)元素占1個(gè)字節(jié)，故A[i][j]相對(duì)于數(shù)組首地址的偏移量是5i+j，再加上首地址，就是A[i][j]的地址。5．?dāng)?shù)組通常具有的兩種基本操作是________。A．查找和修改 B．查找和索引 C．索引和修改 D．建立和刪除答案：A。有些教材中，將數(shù)組下標(biāo)稱為索引，這是數(shù)組自身具有的特性，不是索引操作。在分塊索引存儲(chǔ)方式中，或是數(shù)據(jù)庫中，都會(huì)建立索引。當(dāng)數(shù)據(jù)有更新時(shí)，索引也需要更新。6．已知廣義表LS=(((a)),((b,(c)),(d,(e,f))),())，LS的長度是________。A．2 B．3 C．4 D．5答案：B。LS中，第一個(gè)元素是((a))，它也是表頭，第二個(gè)元素是((b,(c)),(d,(e,f)))，第三個(gè)元素是()，所以長度是3。7．已知廣義表LS=(((a)),((b,(c)),(d,(e,f))),())，LS的深度是________。A．2 B．3 C．4 D．5答案：C。對(duì)LS中嵌套的括號(hào)進(jìn)行計(jì)數(shù)，如圖4.1所示。(((a)),((b,(C)),(d,(e,f))),())123212343234321210圖圖4.1對(duì)LS中嵌套的括號(hào)進(jìn)行計(jì)數(shù)可以看到，最大計(jì)數(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，計(jì)算數(shù)組data元素?cái)?shù)量的表達(dá)式是__________。答案：sizeof(data)/sizeof(int)。3．若nn矩陣M是一個(gè)對(duì)稱矩陣，Mij表示i行j列的元素，則對(duì)所有的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í)，映射函數(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，與實(shí)際相符。保存D3Array[0][0][0]的單元編號(hào)為0的話，則D3Array[2][1][2]保存在編號(hào)為17的單元中。2．有三對(duì)角矩陣A[i][j](0≤i,j≤n-1)如下所示。采用行主序方式僅保存主對(duì)角線及兩個(gè)副對(duì)角線中的元素。設(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ù)組按行主序存儲(chǔ)的地址映射函數(shù)?！緟⒖即鸢浮繉?duì)于四維數(shù)組FourDimenArray[u1][u2][u3][u4]，其行主序的映射函數(shù)應(yīng)為：map(i1,i2,i3,i4)=i1u2u3u4+i2u3u4