數(shù)據(jù)結(jié)構(gòu)與算法復(fù)習(xí)題

1、全國(guó)計(jì)算機(jī)等級(jí)考試(二級(jí)公共基礎(chǔ)相關(guān)習(xí)題(1數(shù)據(jù)結(jié)構(gòu)與算法一、選擇題1.在計(jì)算機(jī)中,算法是指(CA.查詢(xún)方法B.加工方法C.對(duì)解題方案的準(zhǔn)確而完整的描述D.排序方法2.在下列選項(xiàng)中,哪個(gè)一個(gè)不是算法應(yīng)該具有的基本特征(CA.確定性B.可行性C.無(wú)窮性D.擁有足夠的情報(bào)3.算法一般都可以用哪幾種控制結(jié)構(gòu)組合而成(DA.循環(huán)、分支、遞歸B.順序、循環(huán)、嵌套C.循環(huán)、遞歸、選擇D.順序、選擇、循環(huán)4.算法的時(shí)間復(fù)雜度是指(CA.執(zhí)行算法程序所需要的時(shí)間B.算法程序的長(zhǎng)度C.算法執(zhí)行過(guò)程中所需要的基本運(yùn)算次數(shù)D.算法程序中的指令條數(shù)5.算法的空間復(fù)雜度是指(DA.算法程序的長(zhǎng)度B.算法程序中的指令條數(shù)

2、C.算法程序所占的存儲(chǔ)空間D.算法執(zhí)行過(guò)程中所需要的存儲(chǔ)空間6.算法分析的目的是(D注:書(shū)中沒(méi)有總結(jié),但要牢記A.找出數(shù)據(jù)結(jié)構(gòu)的合理性B.找出算法中輸入和輸出之間的關(guān)系C.分析算法的易懂性和可靠性D.分析算法的效率以求改進(jìn)7.數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)是指(DA.存儲(chǔ)在外存中的數(shù)據(jù)B.數(shù)據(jù)所占的存儲(chǔ)空間C.數(shù)據(jù)在計(jì)算機(jī)中的順序存儲(chǔ)D.數(shù)據(jù)的邏輯結(jié)構(gòu)在計(jì)算機(jī)中的表示8.數(shù)據(jù)結(jié)構(gòu)中,與所使用的計(jì)算機(jī)無(wú)關(guān)的是數(shù)據(jù)的(CA.存儲(chǔ)結(jié)構(gòu)B.物理結(jié)構(gòu)C.邏輯結(jié)構(gòu)D.物理和存儲(chǔ)結(jié)構(gòu)9.下列敘述正確的是(CA.算法的執(zhí)行效率與數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)無(wú)關(guān)B.算法的空間復(fù)雜度是指算法程序中指令(或語(yǔ)句的條數(shù)C.算法的有窮性是指算法必須

3、能在執(zhí)行有限個(gè)步驟之后終止D.以上三種描述都不對(duì)10.以下數(shù)據(jù)結(jié)構(gòu)中不屬于線性結(jié)構(gòu)的是(CA.隊(duì)列B.線性表C.二叉樹(shù)D.棧11.在下面關(guān)于線性表的敘述中,選出正確的一項(xiàng)(DA.線性表的每一個(gè)元素都有一個(gè)直接前驅(qū)和直接后繼B.線性表中至少要有一個(gè)元素C.線性表中的元素必須按遞增或遞減的順序排列D.除第一個(gè)元素和最后一個(gè)元素外,每個(gè)元素都有一個(gè)直接前驅(qū)和直接后繼12.下列對(duì)線性鏈表描述正確的是(AA.存儲(chǔ)空間不一定連續(xù),且各元素的存儲(chǔ)順序是任意的B.存儲(chǔ)空間不一定連續(xù),且前件元素一定存儲(chǔ)在后件元素的前面C.存儲(chǔ)空間必須連續(xù),且前件元素一定存儲(chǔ)在后件元素的前面D.存儲(chǔ)空間必須連續(xù),且各元素的存儲(chǔ)順

4、序是任意的13.下列對(duì)線性表敘述中,正確的一項(xiàng)是(CA.采用鏈?zhǔn)酱鎯?chǔ)的線性表,必須占用一片連續(xù)的存儲(chǔ)單元B.采用順序存儲(chǔ)的線性表,便于進(jìn)行插入和刪除操作C.采用鏈?zhǔn)酱鎯?chǔ)的線性表,不必占用一片連續(xù)的存儲(chǔ)單元D.鏈?zhǔn)胶晚樞虼鎯?chǔ)的線性表,都便于進(jìn)行插入和刪除操作14.線性表的順序存儲(chǔ)結(jié)構(gòu)和線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)分別是(BA.順序存取的存儲(chǔ)結(jié)構(gòu)、順序存取的存儲(chǔ)結(jié)構(gòu)B.隨機(jī)存取的存儲(chǔ)結(jié)構(gòu)、順序存取的存儲(chǔ)結(jié)構(gòu)C.隨機(jī)存取的存儲(chǔ)結(jié)構(gòu)、隨機(jī)存取的存儲(chǔ)結(jié)構(gòu)D.任意存取的存儲(chǔ)結(jié)構(gòu)、任意存取的存儲(chǔ)結(jié)構(gòu)15.鏈表不具有的特點(diǎn)是(BA.不必事先估計(jì)存儲(chǔ)空間B.可隨機(jī)訪問(wèn)任一元素C.插入刪除不需要移動(dòng)元素D.所需空間與線性

5、表長(zhǎng)度成正比16.用鏈表表示線性表的優(yōu)點(diǎn)是(A注:因?yàn)椴恍枰苿?dòng)元素A.便于插入和刪除操作B.數(shù)據(jù)元素的物理順序與邏輯順序相同C.花費(fèi)的存儲(chǔ)空間較順序存儲(chǔ)少D.便于隨機(jī)存取17.線性表若采用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)時(shí),要求內(nèi)存中可用存儲(chǔ)單元的地址(DA.必須是連續(xù)的B.部分地址必須是連續(xù)的C.一定是不連續(xù)的D.連續(xù)不連續(xù)都可以18.下列關(guān)于棧的描述正確的是(CA.在棧中只能插入元素而不能刪除元素B.在棧中只能刪除元素而不能插入元素C.棧是特殊的線性表,只能在一端插入或刪除元素。D.棧是特殊的線性表,只能在一端插入元素,而不能在一端刪除元素19.下列關(guān)于棧的描述中錯(cuò)誤的是(BA.棧是先進(jìn)后出的線性表B.棧只

6、能順序存儲(chǔ)C.棧具有記憶作用D.對(duì)棧的插入與刪除操作中,不需要改變棧底指針20.棧底至棧頂依次存放元素ABCD,在第5個(gè)元素E入棧前,棧中元素可以出棧,則出棧序列可能是(DA.ABCEDB.DBCEAC.CDABED.DCBEA21.棧通常采用的兩種存儲(chǔ)結(jié)構(gòu)是(AA.順序存儲(chǔ)結(jié)構(gòu)和鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)B.散列方式和索引方式C.鏈表存儲(chǔ)結(jié)構(gòu)和數(shù)組D.線性存儲(chǔ)結(jié)構(gòu)和非線性存儲(chǔ)結(jié)構(gòu)22.下列關(guān)于隊(duì)列的敘述中正確的是(CA.在隊(duì)列中只能插入元素B.在隊(duì)列中只能刪除數(shù)據(jù)C.隊(duì)列是先進(jìn)先出的線性表D.隊(duì)列是先進(jìn)后出的線性表23.一個(gè)隊(duì)列的入隊(duì)序列是1,2,3,4,則隊(duì)列的輸出序列是(BA.4,3,2,1B.1,2

7、,3,4C.1,4,3,2D.3,2,4,124.棧和隊(duì)列的共同點(diǎn)是(CA.都是先進(jìn)后出B.都是先進(jìn)先出C.只允許在端點(diǎn)處插入和刪除元素D.沒(méi)有共同點(diǎn)25.樹(shù)最適合用來(lái)表示(CA.有序數(shù)組元素B.無(wú)序數(shù)組元素C.元素之間具有分支層次關(guān)系的數(shù)據(jù)D.元素之間無(wú)聯(lián)系的數(shù)據(jù)26.樹(shù)是結(jié)點(diǎn)的集合,它的根結(jié)點(diǎn)數(shù)目是(CA.有且只有1B.1或多于1C.0或1D.至少227.一棵二叉樹(shù)第5層的結(jié)點(diǎn)數(shù)最多為(BA.8B.16C.32D.1528.設(shè)一棵二叉樹(shù)中有3個(gè)葉子結(jié)點(diǎn),有8個(gè)度為1的結(jié)點(diǎn),則該二叉樹(shù)中總的結(jié)點(diǎn)數(shù)為(B A.12B.13C.14D.1529.某二叉樹(shù)結(jié)點(diǎn)的前序序列為EACBDGF,中序序列為

8、ABCDEFG。該二叉樹(shù)結(jié)點(diǎn)的后序序列為(AA.BDCAFGEB.DBCFAGEC.DCEGFABD.DEGACFB30.已知二叉樹(shù)后序遍歷序列是dabec,中序遍歷序列是debac,它的前序遍歷序列是(AA.cedbaB.acbedC.decabD.deabc31.設(shè)一棵完全二叉樹(shù)共有699個(gè)結(jié)點(diǎn),則在該二叉樹(shù)中的葉子結(jié)點(diǎn)數(shù)為(BA.349B.350C.255D.35132.具有3個(gè)結(jié)點(diǎn)的二叉樹(shù)有(DA.2種形態(tài)B.4種形態(tài)C.7種形態(tài)D.5種形態(tài)33.對(duì)長(zhǎng)度為n的線性表進(jìn)行順序查找,在最壞的情況下所需要的比較次數(shù)為(CA.Log2nB.n/2C.nD.n+134.下列數(shù)據(jù)結(jié)構(gòu)中,能用二分法

9、進(jìn)行查找的是(AA.順序存儲(chǔ)的有序線性表B.線性鏈表C.二叉鏈表D.有序線性鏈表35.二分法查找適合用于存儲(chǔ)結(jié)構(gòu)為(A且按關(guān)鍵字排好序的線性表A.順序存儲(chǔ)B.鏈?zhǔn)酱鎯?chǔ)C.順序和鏈?zhǔn)酱鎯?chǔ)D.索引存儲(chǔ)36.對(duì)于長(zhǎng)度為n的線性表,在最壞的情況下,下列各排序法所對(duì)應(yīng)的比較次數(shù)中正確的是(DA.冒泡排序?yàn)閚/2B.冒泡排序?yàn)閚C.快速排序?yàn)閚D.快速排序?yàn)閚(n-1/237.希爾排序法屬于哪一種類(lèi)型的排序法(BA.交換類(lèi)排序法B.插入類(lèi)排序法C.選擇類(lèi)排序法D.建堆排序法二、填空題1.問(wèn)題處理方案的正確而完整的描述稱(chēng)為_(kāi)。答:算法2.算法復(fù)雜度主要包括時(shí)間復(fù)雜度和_復(fù)雜度。答:空間3.數(shù)據(jù)結(jié)構(gòu)包括數(shù)據(jù)的

10、_結(jié)構(gòu)和數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)。答:邏輯4.數(shù)據(jù)的邏輯結(jié)構(gòu)在計(jì)算機(jī)存儲(chǔ)空間中的存放形式稱(chēng)為數(shù)據(jù)的_。答:存儲(chǔ)結(jié)構(gòu)#物理結(jié)構(gòu)5.數(shù)據(jù)的邏輯結(jié)構(gòu)有線性結(jié)構(gòu)和_兩大類(lèi)。答:非線性結(jié)構(gòu)6.數(shù)據(jù)結(jié)構(gòu)分為邏輯結(jié)構(gòu)與存儲(chǔ)結(jié) 構(gòu)，線性鏈表屬于_。 答：存儲(chǔ)結(jié)構(gòu) 7.數(shù)據(jù)結(jié)構(gòu)分為邏輯結(jié)構(gòu)和存儲(chǔ)結(jié) 構(gòu)，循環(huán)隊(duì)列屬于_結(jié)構(gòu)。 答：存儲(chǔ) 8.順序存儲(chǔ)方法是把邏輯上相鄰的結(jié) 點(diǎn)存儲(chǔ)在物理位置_的存儲(chǔ)單元 中。 答：相鄰 9.長(zhǎng)度為 n 的順序存儲(chǔ)線性表中，當(dāng) 在任何位置上插入一個(gè)元素概率都相 等時(shí)，插入一個(gè)元素所需移動(dòng)元素的 平均個(gè)數(shù)為_(kāi)。 答：n/2 10.棧的基本運(yùn)算有三種：入棧、退棧 和_。 答：讀棧頂元素 11.二叉樹(shù)的遍歷可以分為三種：前序 遍歷、_