1、第一章數(shù)據(jù)結(jié)構(gòu)與算法1 .算法復(fù)雜度相關(guān)試題：算法的空間復(fù)雜度是指（）A）算法在執(zhí)行過程中所需要的計(jì)算機(jī)存儲(chǔ)空間B）算法所處理的數(shù)據(jù)量C）算法程序中的語句或指令條數(shù)D）算法在執(zhí)行過程中所需要的臨時(shí)工作單元數(shù)【解析】算法的空間復(fù)雜度是指算法在執(zhí)行過程中所需要的內(nèi)存空間。所以選擇A2 .數(shù)據(jù)結(jié)構(gòu)相關(guān)試題：下列數(shù)據(jù)結(jié)構(gòu)中，屬于非線性結(jié)構(gòu)的是（）A）循環(huán)隊(duì)列B）帶鏈隊(duì)列C）二叉樹D）帶鏈?！窘馕觥繕涫呛?jiǎn)單的非線性結(jié)構(gòu)，所以二叉樹作為樹的一種也是一種非線性結(jié)構(gòu)。3 .棧和隊(duì)列相關(guān)試題：下列關(guān)于棧的敘述正確的是（）A）棧按“先進(jìn)先出”組織數(shù)據(jù)B）棧按“先進(jìn)后出”組織數(shù)據(jù)C）只能在棧底插入數(shù)據(jù)D）不能刪除數(shù)

2、據(jù)【解析】棧是按“先進(jìn)后出”的原則組織數(shù)據(jù)的，數(shù)據(jù)的插入和刪除都在棧頂進(jìn)行操作。故選B。下列關(guān)于棧的敘述中，正確的A）棧底元素一定是最后入棧的元素B）棧頂元素一定是最先入棧的元素C）棧操作遵循先進(jìn)后出的原則D）以上說法均錯(cuò)誤【解析】棧頂元素總是后被插入的元素，從而也是最先被刪除的元素；棧底元素總是最先被插入的元素，從而也是最后才能被刪除的元素。棧的修改是按后進(jìn)先出的原則進(jìn)行的。因此，棧稱為先進(jìn)后出表，或“后進(jìn)先出”表，所以選擇Co下列關(guān)于棧敘述正確的是（）A）棧頂元素最先能被刪除B）棧頂元素最后才能被刪除C）棧底元素永遠(yuǎn)不能被刪除D）棧底元素最先被刪除【解析】棧是先進(jìn)后出的數(shù)據(jù)結(jié)構(gòu)，所以棧頂元

3、素最后入棧卻最先被刪除。棧底元素最先入棧卻最后被刪除。所以選擇Ao總結(jié)：棧頂元素最先被刪除，棧底元素最后被刪除一原因：棧的數(shù)據(jù)處理原則支持子程序調(diào)用的數(shù)據(jù)結(jié)構(gòu)是（）A）棧B）樹C）隊(duì)列D）二叉樹【解析】棧支持子程序調(diào)用。棧是一種只能在一端進(jìn)行插入或刪除的線性表，在主程序調(diào)用子函數(shù)時(shí)要首先保存主程序當(dāng)前的狀態(tài)，然后轉(zhuǎn)去執(zhí)行子程序，最終把子程序的執(zhí)行結(jié)果返回到主程序中調(diào)用子程序的位置，繼續(xù)向下執(zhí)行，這種調(diào)用符合棧的特點(diǎn)，因此本題的答案為Aob.隊(duì)列：相關(guān)試題：對(duì)于循環(huán)隊(duì)列，下列敘述中正確的是（）A）隊(duì)頭指針是固定不變的B）隊(duì)頭指針一定大于隊(duì)尾指針C）隊(duì)頭指針一定小于隊(duì)尾指針D）隊(duì)頭指針可以大于隊(duì)尾

4、指針，也可以小于隊(duì)尾指針【解析】循環(huán)隊(duì)列的隊(duì)頭指針與隊(duì)尾指針都不是固定的，隨著入隊(duì)與出隊(duì)操作要進(jìn)行變化。因?yàn)槭茄h(huán)利用的隊(duì)列結(jié)構(gòu)，所以對(duì)頭指針有時(shí)可能大于隊(duì)尾指針有時(shí)也可能小于隊(duì)尾指針。故選Do設(shè)循環(huán)隊(duì)列的存儲(chǔ)空間為0（1:35）,初始狀態(tài)為front=rear=35?，F(xiàn)經(jīng)過一系列入隊(duì)與退隊(duì)運(yùn)算后，front=15,rear=15,則循環(huán)隊(duì)列中的元素個(gè)數(shù)A）15B）16C）20D）0或35【解析】在循環(huán)隊(duì)列中，用隊(duì)尾指針rear指向隊(duì)列中的隊(duì)尾元素，用排頭指針front指向排頭元素的前一個(gè)位置。在循環(huán)隊(duì)列中進(jìn)行出隊(duì)、入隊(duì)操作時(shí)，頭尾指針仍要加1,朝前移動(dòng)。只不過當(dāng)頭尾指針指向向量上界時(shí)，其加1

5、操作的結(jié)果是指向向量的下界0。由于入隊(duì)時(shí)尾指針向前追趕頭指針，出隊(duì)時(shí)頭指針向前追趕尾指針，故隊(duì)空和隊(duì)滿時(shí)，頭尾指針均相等。答案為D選項(xiàng)。相關(guān)綜合習(xí)題：下列敘述中正確的是（）A）棧是一種先進(jìn)先出的線性表B）隊(duì)列是一種后進(jìn)先出的線性表C)棧與隊(duì)列都是非線性結(jié)構(gòu)D)以上三種說法都不對(duì)【解析】棧是一種先進(jìn)后出的線性表，隊(duì)列是一種先進(jìn)先出的線性表，棧與隊(duì)列都是線性結(jié)構(gòu)。故選Do4,樹與二叉樹相關(guān)試題：某二叉樹共有12個(gè)結(jié)點(diǎn)，其中葉子結(jié)點(diǎn)只有1個(gè)。則該二叉樹的深度為(根結(jié)點(diǎn)在第1層)A)3B)6C)8D)12【解析】二叉樹中，度為0的節(jié)點(diǎn)數(shù)等于度為2的節(jié)點(diǎn)數(shù)加1,即n2=n0-1,葉子節(jié)點(diǎn)即度為0,n0=

6、1,則n2=0,總節(jié)點(diǎn)數(shù)為12=n0+n1+n2=1+n1+0則度為1的節(jié)點(diǎn)數(shù)n1=11,故深度為12,選D。某二叉樹有5個(gè)度為2的結(jié)點(diǎn)，則該二叉樹中的葉子結(jié)點(diǎn)數(shù)是()A)10B)8C)6D)4【解析】根據(jù)二叉樹的基本性質(zhì)3:在任意一棵二叉樹中，度為0的葉子節(jié)點(diǎn)總是比度為2的節(jié)點(diǎn)多一個(gè)，所以本題中是5+1=6個(gè)。故選C某二叉樹中有15個(gè)度為1的結(jié)點(diǎn)，16個(gè)度為2的結(jié)點(diǎn)，則該二叉樹中總的結(jié)點(diǎn)數(shù)為()A)32B)46C)48D)49【解析】在樹結(jié)構(gòu)中，一個(gè)結(jié)點(diǎn)所擁有的后件個(gè)數(shù)稱為該結(jié)點(diǎn)的度，所有結(jié)點(diǎn)中最大的度稱為樹的度。對(duì)任何一棵二叉樹，度為0的結(jié)點(diǎn)(即葉子結(jié)點(diǎn))總是比度為2的結(jié)點(diǎn)多一個(gè)。由16個(gè)

7、度為2的結(jié)點(diǎn)可知葉子結(jié)點(diǎn)個(gè)數(shù)為17,則結(jié)點(diǎn)總數(shù)為16+17+15=48,C選項(xiàng)正確對(duì)下列二叉樹進(jìn)行前序遍歷的結(jié)果為（）A）DYBEAFCZXB）YDEBFZXCAC）ABDYECFXZD）ABCDEFXYZ【解析】前序遍歷是指在訪問根結(jié)點(diǎn)、遍歷左子樹與遍歷右子樹這三者中，首先訪問根結(jié)點(diǎn)，然后遍歷左子樹，最后遍歷右子樹；并且，在遍歷左右子樹時(shí)，仍然先訪問根結(jié)點(diǎn)，然后遍歷左子樹，最后遍歷右子樹。前序遍歷描述為：若二叉樹為空，則執(zhí)行空操作。否則：訪問根結(jié)點(diǎn)；前序遍歷左子樹；前序遍歷右子樹，C正確。某二叉樹的前序序列為ABCD中序序列為DCBA則后序序列為（）A）BADCB）DCBAC）CDABD）A

8、BCD【解析】二叉樹遍歷可以分為3種：前序遍歷（訪問根結(jié)點(diǎn)在訪問左子樹和訪問右子樹之前）、中序遍歷（訪問根結(jié)點(diǎn)在訪問左子樹和訪問右子樹兩者之間）、后序遍歷（訪問根結(jié)點(diǎn)在訪問左子樹和訪問右子樹之后）。本題根據(jù)前序序列為ABCD可知A為根結(jié)點(diǎn)。根據(jù)中序序列為DCBAI知DCBMA的左子樹。根據(jù)前序序列可知B是CD的根結(jié)點(diǎn)。再根據(jù)中序序列可知DC是結(jié)點(diǎn)B的左子樹。根據(jù)前序序列可知，C是D的根結(jié)點(diǎn)，故后序序列為DCBAB選項(xiàng)正確。5,查找技術(shù)最壞情況時(shí)間復(fù)雜度公式：相關(guān)試題：在長(zhǎng)度為n的有序線性表中進(jìn)行二分查找，最壞情況下需要比較的次數(shù)是（）A）。心g2nhO（nlogjn）【解析】當(dāng)有序線性表為順序

9、存儲(chǔ)時(shí)才能用二分法查找?？梢宰C明的是對(duì)于長(zhǎng)度為n的有序線性表，在最壞情況下，二分法查找只需要比較心由n次，而順序查找需要比較n次。故選C。6.排序技術(shù)（非遞減順序）最壞情況時(shí)間復(fù)雜度公式：相關(guān)試題：堆排序最壞情況下的時(shí)間復(fù)雜度為（）.入L蟻0（方此日舊中門匕2-D）51gM【解析】堆排序?qū)儆谶x擇類的排序方法，最壞情況時(shí)間復(fù)雜度為°（nlo&n）。故b選項(xiàng)正確。下列排序方法中，最壞情況下比較次數(shù)最少的是（）A）冒泡排序B）簡(jiǎn)單選擇排序C）直接插入排序D）堆排序【解析】冒泡排序與簡(jiǎn)單插入排序與簡(jiǎn)單選擇排序法在最壞情況下均需要比較n（n-1）/2次，而堆排序在最壞情況下需要比較的次數(shù)是門廊2口。故選d對(duì)長(zhǎng)度為10的線性表進(jìn)行冒泡排序，最壞情況下需要比較的次數(shù)考查公式應(yīng)用A)9B)10C)45D)90【解析】冒泡法是在掃描過程中逐次比較相鄰兩個(gè)元素的大小，最壞的情況是每次比較都要將相鄰的兩個(gè)元素互換，需要互換的次數(shù)為9+8+7+6+5+4+3+2+1=45選C。對(duì)長(zhǎng)度為n的線性表排序，在最壞情況下，比較次數(shù)不是n(n-1)/2的排序方法A)快速排序B)冒泡排序C)簡(jiǎn)單插入排