《大數(shù)據(jù)結(jié)構(gòu)》期中題庫及問題詳解

《《大數(shù)據(jù)結(jié)構(gòu)》期中題庫及問題詳解》由會(huì)員分享，可在線閱讀，更多相關(guān)《《大數(shù)據(jù)結(jié)構(gòu)》期中題庫及問題詳解（68頁珍藏版）》請?jiān)谘b配圖網(wǎng)上搜索。

1、word 一、判斷題： 1、線性表的邏輯順序與物理順序總是一致的。(???) 2、線性表的順序存儲(chǔ)表示優(yōu)于鏈?zhǔn)酱鎯?chǔ)表示。(???) 3、線性表若采用鏈?zhǔn)酱鎯?chǔ)表示時(shí)所有結(jié)點(diǎn)之間的存儲(chǔ)單元地址可連續(xù)可不連續(xù)。(???) 4、二維數(shù)組是其數(shù)組元素為線性表的線性表。(???) 5、每種數(shù)據(jù)結(jié)構(gòu)都應(yīng)具備三種基本運(yùn)算：插入、刪除和搜索。(?????) 6、數(shù)據(jù)結(jié)構(gòu)概念包括數(shù)據(jù)之間的邏輯結(jié)構(gòu)，數(shù)據(jù)在計(jì)算機(jī)中的存儲(chǔ)方式和數(shù)據(jù)的運(yùn)算三個(gè) 方面。(???) 7、線性表中的每個(gè)結(jié)點(diǎn)最多只有一個(gè)前驅(qū)和一個(gè)后繼。（????????）? 8、線性的數(shù)據(jù)結(jié)構(gòu)可以順序存儲(chǔ)，也可以存儲(chǔ)。非線性的數(shù)據(jù)結(jié)構(gòu)只能

2、存儲(chǔ)。（?????） 9、棧和隊(duì)列邏輯上都是線性表。（?????）? 10、單鏈表從任何一個(gè)結(jié)點(diǎn)出發(fā)，都能訪問到所有結(jié)點(diǎn)?（?????） 11、刪除二叉排序樹中一個(gè)結(jié)點(diǎn)，再重新插入上去，一定能得到原來的二叉排序樹。（??） 12、快速排序是排序算法中最快的一種。（??） 13、多維數(shù)組是向量的推廣。（??????） 14、一般樹和二叉樹的結(jié)點(diǎn)數(shù)目都可以為0。?（??????） 15、直接選擇排序是一種不穩(wěn)定的排序方法。（????） 16、98、對(duì)一個(gè)堆按層次遍歷，不一定能得到一個(gè)有序序列。（??） 17、在只有度為0和度為k的結(jié)點(diǎn)的k叉樹中，設(shè)度為0的結(jié)點(diǎn)有n0個(gè)，度為k的結(jié)

3、點(diǎn)有nk個(gè)，則有n0=nk+1。（???） 18、折半搜索只適用與有序表，包括有序的順序表和有序的鏈表。（???） 19、堆棧在數(shù)據(jù)中的存儲(chǔ)原則是先進(jìn)先出。（?????） 20、隊(duì)列在數(shù)據(jù)中的存儲(chǔ)原則是后進(jìn)先出。（?????） 21、用相鄰矩陣表示圖所用的存儲(chǔ)空間大小與圖的邊數(shù)成正比。（?????） 22、哈夫曼樹一定是滿二叉樹。（????） 23、程序是用計(jì)算機(jī)語言表述的算法。（???） 24、線性表的順序存儲(chǔ)結(jié)構(gòu)是通過數(shù)據(jù)元素的存儲(chǔ)地址直接反映數(shù)據(jù)元素的邏輯關(guān)系。（????） 25、用一組地址連續(xù)的存儲(chǔ)單元存放的元素一定構(gòu)成線性表。（????） 26、堆棧、隊(duì)列和數(shù)組的邏

4、輯結(jié)構(gòu)都是線性表結(jié)構(gòu)。（????） 27、給定一組權(quán)值，可以唯一構(gòu)造出一棵哈夫曼樹。（?????） 28、只有在初始數(shù)據(jù)為逆序時(shí)，冒泡排序所執(zhí)行的比較次數(shù)最多。（???） 29、希爾排序在較率上較直接接入排序有較大的改進(jìn)。但是不穩(wěn)定的。（??） 30、在平均情況下，快速排序法最快，堆積排序法最節(jié)省空間。（????） 31、快速排序法是一種穩(wěn)定性排序法。（????） 32、算法一定要有輸入和輸出。（?????） 33、算法分析的目的旨在分析算法的效率以求改進(jìn)算法。（??????） 34、非空線性表中任意一個(gè)數(shù)據(jù)元素都有且僅有一個(gè)直接后繼元素。（??????） 35、數(shù)據(jù)的存儲(chǔ)結(jié)

5、構(gòu)不僅有順序存儲(chǔ)結(jié)構(gòu)和鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)，還有索引結(jié)構(gòu)與散列結(jié)構(gòu)。（??????） 36、若頻繁地對(duì)線性表進(jìn)行插入和刪除操作，該線性表采用順序存儲(chǔ)結(jié)構(gòu)更合適。（??????） 37、若線性表采用順序存儲(chǔ)結(jié)構(gòu)，每個(gè)數(shù)據(jù)元素占用4個(gè)存儲(chǔ)單元，第12個(gè)數(shù)據(jù)元素的存儲(chǔ)地址為144，則第1個(gè)數(shù)據(jù)元素的存儲(chǔ)地址是101。（?????） 38、若長度為n的線性表采用順序存儲(chǔ)結(jié)構(gòu)，刪除表的第i個(gè)元素之前需要移動(dòng)表中n-i+1個(gè)元素。（??????） 39、符號(hào)p->next出現(xiàn)在表達(dá)式中表示p所指的那個(gè)結(jié)點(diǎn)的容。（??????） 40、要將指針p移到它所指的結(jié)點(diǎn)的下一個(gè)結(jié)點(diǎn)是執(zhí)行語句p←p->next。（

6、???????） 41、若某堆棧的輸入序列為1,2,3,4，則4,3,1,2不可能是堆棧的輸出序列之一。（?????） 42、線性鏈表中各個(gè)鏈結(jié)點(diǎn)之間的地址不一定要連續(xù)。（????） 43、程序就是算法，但算法不一定是程序。（?????） 44、線性表只能采用順序存儲(chǔ)結(jié)構(gòu)或者鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)。（????） 45、線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)是通過指針來間接反映數(shù)據(jù)元素之間邏輯關(guān)系的。（????） 46、除插入和刪除操作外，數(shù)組的主要操作還有存取、修改、檢索和排序等。（??????） 47、稀疏矩陣中0元素的分布有規(guī)律，因此可以采用三元組方法進(jìn)行壓縮存儲(chǔ)。（?????） 48、不管堆棧采用何

7、種存儲(chǔ)結(jié)構(gòu)，只要堆棧不空，可以任意刪除一個(gè)元素。（????） 49、確定串Ｔ在串Ｓ中首次出現(xiàn)的位置的操作稱為串的模式匹配。（?????） 50、深度為h的非空二叉樹的第i層最多有2i-1?個(gè)結(jié)點(diǎn)。（????） 51、滿二叉樹也是完全二叉樹。（????） 52、已知一棵二叉樹的前序序列和后序序列可以唯一地構(gòu)造出該二叉樹。（?????） 53、非空二叉排序樹的任意一棵子樹也是二叉排序樹。（????） 54、對(duì)一棵二叉排序樹進(jìn)行前序遍歷一定可以得到一個(gè)按值有序的序列。（????） 55、一個(gè)廣義表的深度是指該廣義表展開后所含括號(hào)的層數(shù)。（???） 56、散列表的查找效率主要取決于所選

8、擇的散列函數(shù)與處理沖突的方法。（?????） 57、序列初始為逆序時(shí)，冒泡排序法所進(jìn)行的元素之間的比較次數(shù)最多。（?????） 58、已知指針P指向鍵表L中的某結(jié)點(diǎn)，執(zhí)行語句P=P-〉next不會(huì)刪除該鏈表中的結(jié)點(diǎn)。 （?????） 59、在鏈隊(duì)列中，即使不設(shè)置尾指針也能進(jìn)行入隊(duì)操作。（????） 60、如果一個(gè)串中的所有字符均在另一串中出現(xiàn)，則說前者是后者的子串。（???????） 61、設(shè)與一棵樹T所對(duì)應(yīng)的二叉樹為BT，則與T中的葉子結(jié)點(diǎn)所對(duì)應(yīng)的BT中的結(jié)點(diǎn)也一定是葉子結(jié)點(diǎn)。（?????） 62、若圖G的最小生成樹不唯一，則G的邊數(shù)一定多于n-1，并且權(quán)值最小的邊有多條（其中

9、n為G的頂點(diǎn)數(shù)）。（????） 63、給出不同的輸入序列建造二叉排序樹，一定得到不同的二叉排序樹。（?????） 64、由于希爾排序的最后一趟與直接插入排序過程相同，因此前者一定比后者花費(fèi)的時(shí)間多。（?????） 65、程序越短，程序運(yùn)行的時(shí)間就越少。（??????） 66、采用循環(huán)鏈表作為存儲(chǔ)結(jié)構(gòu)的隊(duì)列就是循環(huán)隊(duì)列。（??????） 67、堆棧是一種插入和刪除操作在表的一端進(jìn)行的線性表。（?????） 68、一個(gè)任意串是其自身的子串。（?????） 69、哈夫曼樹一定是完全二叉樹。（?????） 70、帶權(quán)連通圖中某一頂點(diǎn)到圖中另一定點(diǎn)的最短路徑不一定唯一。（????） 7

10、1、折半查找方法可以用于按值有序的線性鏈表的查找。（?????） 72、稀疏矩陣壓縮存儲(chǔ)后,必會(huì)失效掉隨機(jī)存取功能。（??????） 73、由一棵二叉樹的前序序列和后序序列可以唯一確定它。（?????） 74、在n個(gè)結(jié)點(diǎn)的元向圖中,若邊數(shù)在于n-1,則該圖必是連通圖。（??????） 75、在完全二叉樹中,若某結(jié)點(diǎn)元左孩子,則它必是葉結(jié)點(diǎn)。（????） 76、若一個(gè)有向圖的鄰接矩陣中,對(duì)角線以下元素均為0,則該圖的拓?fù)溆行蛐蛄斜囟ù嬖?。???） 77、樹的帶權(quán)路徑長度最小的二叉樹中必定沒有度為1的結(jié)點(diǎn)。（????） 78、二叉樹可以用0≤度≤2的有序樹來表示。（?????）

11、79、一組權(quán)值，可以唯一構(gòu)造出一棵哈夫曼樹。(?????)? 80、101，88，46，70，34，39，45，58，66，10）是堆；（???） 81、將一棵樹轉(zhuǎn)換成二叉樹后，根結(jié)點(diǎn)沒有左子樹；（????） 82、用樹的前序遍歷和中序遍歷可以導(dǎo)出樹的后序遍歷；（????） 83、在非空線性鏈表中由p所指的結(jié)點(diǎn)后面插入一個(gè)由q所指的結(jié)點(diǎn)的過程是依次執(zhí)行語句：q->next=p->next;p->next=q。（????） 84、非空雙向循環(huán)鏈表中由q所指的結(jié)點(diǎn)后面插入一個(gè)由p指的結(jié)點(diǎn)的動(dòng)作依次為：p->prior=q,?p->next=q->next,q->next=p,q->pri

12、or->next←p。（????） 85、刪除非空鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)的堆棧(設(shè)棧頂指針為top)的一個(gè)元素的過程是依次執(zhí)行:p=top,top=?p->next,free?(p)。(???) 86、哈希的查找無需進(jìn)行關(guān)鍵字的比較。（???） 87、一個(gè)好的哈希函數(shù)應(yīng)使函數(shù)值均勻的分布在存儲(chǔ)空間的有效地址圍，以盡可能減少?zèng)_突。（?????） 88、排序是計(jì)算機(jī)程序設(shè)計(jì)中的一種重要操作，它的功能是將一個(gè)數(shù)據(jù)元素（或記錄）的任意序列，重新排列成一個(gè)按關(guān)鍵字有序的序列。（????） 89、隊(duì)列是一種可以在表頭和表尾都能進(jìn)行插入和刪除操作的線性表。（?????） 90、在索引順序表上實(shí)現(xiàn)分塊查找，

13、在等概率查找情況下，其平均查找長度不與表的個(gè)數(shù)有關(guān)，而與每一塊中的元素個(gè)數(shù)有關(guān)。（???） 91、對(duì)于有向圖，頂點(diǎn)的度分為入度和出度，入度是以該頂點(diǎn)為終點(diǎn)的入邊數(shù)目；出度是以該頂點(diǎn)為起點(diǎn)的出邊數(shù)目，該頂點(diǎn)的度等于其入度和出度之和。（????） 92、無向圖的鄰接矩陣是對(duì)稱的有向圖的鄰接矩陣是不對(duì)稱的。（????） 93、具有n個(gè)頂點(diǎn)的連通圖的生成樹具有n-1條邊（???） 二、填空題： 1、《數(shù)據(jù)結(jié)構(gòu)》課程討論的主要容是數(shù)據(jù)的邏輯結(jié)構(gòu)、存儲(chǔ)結(jié)構(gòu)和______________。 2、數(shù)據(jù)結(jié)構(gòu)算法中，通常用時(shí)間復(fù)雜度和__________________兩種方法衡量其效率。 3、一個(gè)

14、算法一該具有______,______,____,______和____這五種特性。 4、若頻繁地對(duì)線性表進(jìn)行插入與刪除操作，該線性表應(yīng)采用____________存儲(chǔ)結(jié)構(gòu)。 5、在非空線性表中除第一個(gè)元素外，集合中每個(gè)數(shù)據(jù)元素只有一個(gè)_______；除最后一個(gè)元素之外，集合中每個(gè)數(shù)據(jù)元素均只有一個(gè)_________。 6、線性表中的每個(gè)結(jié)點(diǎn)最多有________前驅(qū)和____________后繼。 7、______鏈表從任何一個(gè)結(jié)點(diǎn)出發(fā)，都能訪問到所有結(jié)點(diǎn)。 8、鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)中的結(jié)點(diǎn)包含____________域，_______________域。 9、在雙向鏈表中，每個(gè)結(jié)點(diǎn)含有

15、兩個(gè)指針域，一個(gè)指向______結(jié)點(diǎn)，另一個(gè)指向________結(jié)點(diǎn)。 10、某帶頭結(jié)點(diǎn)的單鏈表的頭指針head，判定該單鏈表非空的條件______________。 11、在雙向鏈表中，每個(gè)結(jié)點(diǎn)含有兩個(gè)指針域，一個(gè)指向_______結(jié)點(diǎn)，另一個(gè)指向_____結(jié)點(diǎn)。 12、已知指針p指向單鏈表中某個(gè)結(jié)點(diǎn)，則語句p->next=p->next->next的作用__刪除p?的后繼結(jié)點(diǎn)_。 13、已知在結(jié)點(diǎn)個(gè)數(shù)大于1的單鏈表中，指針p指向某個(gè)結(jié)點(diǎn)，則下列程序段結(jié)束時(shí)，指針q指向*p的_____________結(jié)點(diǎn)。 q=p; while(q->next!=p)? q=q->next;

16、 14、若要在單鏈表結(jié)點(diǎn)*P后插入一結(jié)點(diǎn)*S，執(zhí)行的語句_______________。 15、線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)地址空間可以_________，而向量存儲(chǔ)必須是地址空間___________。 16、棧結(jié)構(gòu)允許進(jìn)行刪除操作的一端為_____________。 17、在棧的順序?qū)崿F(xiàn)中，棧頂指針top，棧為空條件______________。 18、對(duì)于單鏈表形式的隊(duì)列，其空隊(duì)列的F指針和R指針都等于__________________。 19、若數(shù)組s[0..n-1]為兩個(gè)棧s1和s2的共用存儲(chǔ)空間，僅當(dāng)s[0..n-1]全滿時(shí)，各棧才不能進(jìn)行棧操作，則為這兩個(gè)棧分配空間的最佳方案

17、是：s1和s2的棧頂指針的初值分別為_________。 20、允許在線性表的一端插入,另一端進(jìn)行刪除操作的線性表稱為_______。插入的一端為______,刪除的一端為______。 21、設(shè)數(shù)組A[m]為循環(huán)隊(duì)列Q的存儲(chǔ)空間，font為頭指針，rear為尾指針，判定Q為空隊(duì)列的條件____________________。 22、對(duì)于順序存儲(chǔ)的隊(duì)列，存儲(chǔ)空間大小為n，頭指針為F，尾指針為R。若在邏輯上看一個(gè)環(huán)，則隊(duì)列中元素的個(gè)數(shù)為___________。 23、已知循環(huán)隊(duì)列的存儲(chǔ)空間為數(shù)組data[21]，且頭指針和尾指針分別為8和3，則該隊(duì)列的當(dāng)前長度__________。

18、24、一個(gè)串的任意個(gè)連續(xù)的字符組成的子序列稱為該串的________，包含該子串的串稱為 ________。 25、求串T在主串S中首次出現(xiàn)的位置的操作是________________。 26、在初始為空的隊(duì)列中插入元素A,B,C,D以后，緊接著作了兩次刪除操作，此時(shí)的隊(duì)尾元素是__________。 27、在長度為n的循環(huán)隊(duì)列中，刪除其節(jié)點(diǎn)為x的時(shí)間復(fù)雜度為_______________。 28、已知廣義表L為空，其深度為___________。 29、已知一順序存儲(chǔ)的線性表，每個(gè)結(jié)點(diǎn)占用k個(gè)單元，若第一個(gè)結(jié)點(diǎn)的地址為DA1，則第i個(gè)結(jié)點(diǎn)的地址為______________。

19、 30、設(shè)一行優(yōu)先順序存儲(chǔ)的數(shù)組A[5][6]，A[0][0]的地址為1100，且每個(gè)元素占2個(gè)存儲(chǔ)單元，則A[2][3]的地址為_____________。 31、設(shè)有二維數(shù)組A[9][19]，其每個(gè)元素占兩個(gè)字節(jié)，第一個(gè)元素的存儲(chǔ)地址為100，若按行優(yōu)先順序存儲(chǔ)，則元素A[6,6]的存儲(chǔ)地址為______________，按列優(yōu)順序存儲(chǔ)，元素A[6,6]的存儲(chǔ)地址為______________。 32、在進(jìn)行直接插入排序時(shí),?其數(shù)據(jù)比較次數(shù)與數(shù)據(jù)的初始排列________關(guān)；而在進(jìn)行直接選擇排序時(shí)，其數(shù)據(jù)比較次數(shù)與數(shù)據(jù)的初始排列__________關(guān)。 33、假設(shè)以行為優(yōu)先存儲(chǔ)的三維

20、數(shù)組A[5][6][7]，A[0][0][0]的地址為1100，每個(gè)元素占兩個(gè)存儲(chǔ)單元，則A[4][3][2]的地址為_______。 34、設(shè)二維數(shù)組A[m][n]按列優(yōu)先存儲(chǔ)，每個(gè)元素占1個(gè)存儲(chǔ)單元，元素A00的存儲(chǔ)地址loc(A00)，則Aij的存儲(chǔ)地址loc(Aij)=____________________。 35、稀疏矩陣一般采用__________方法進(jìn)行壓縮存儲(chǔ)。 36、稀疏矩陣可用_________進(jìn)行壓縮存儲(chǔ)，存儲(chǔ)時(shí)需存儲(chǔ)非零元的________、________、________。 37、若矩陣中所有非零元素都集中在以主對(duì)角線為中心的帶狀區(qū)域中，區(qū)域外的值全為0，

21、則稱為__________。 38、若一個(gè)n?階矩陣A中的元素滿足：Aij=Aji?(0<=I?,j<=n-1)則稱A為____________矩陣；若主對(duì)角線上方(或下方)的所有元素均為零時(shí)，稱該矩陣為______________。 39、對(duì)于上三角形和下三角形矩陣，分別以按行存儲(chǔ)和按列存儲(chǔ)原則進(jìn)行壓縮存儲(chǔ)到數(shù)組M[k]中，若矩陣中非0元素為Aij，則k對(duì)應(yīng)為________和__________。 40、設(shè)有一上三角形矩陣A[5][5]按行壓縮存儲(chǔ)到數(shù)組B中，B[0]的地址為100，每個(gè)元素占2個(gè)單元，則A[3][2]地址為____________。 41、廣義表（A,(a,b),

22、d,e,((i,j),k)）,則廣義表的長度為___________，深度為___________。 42、已知廣義表A=((a,b,c),(d,e,f)),則運(yùn)算head(head?(tail（A）)))=___?________。 43、已知廣義表ls?=(a,(b,c,d),e),運(yùn)用head和tail函數(shù)取出ls中的原子b的運(yùn)算是_____。 44、在樹結(jié)構(gòu)里，有且僅有一個(gè)結(jié)點(diǎn)沒有前驅(qū)，稱為根。非根結(jié)點(diǎn)有且僅有一個(gè)___________,且存在一條從根到該結(jié)點(diǎn)的_______________。 45、度數(shù)為0的結(jié)點(diǎn)，即沒有子樹的結(jié)點(diǎn)叫作__________結(jié)點(diǎn)或________

23、_結(jié)點(diǎn)。同一個(gè)結(jié)點(diǎn)的兒子結(jié)點(diǎn)之間互稱為___________結(jié)點(diǎn)。? 46、假定一棵樹的廣義表為A(B(e),C(F(h,i,j),g),D),則該樹的度為___________，樹的深度為_________，終端結(jié)點(diǎn)為______，單分支結(jié)點(diǎn)為，雙分支結(jié)點(diǎn)個(gè)數(shù)為?_______，三分支結(jié)點(diǎn)為_______，C結(jié)點(diǎn)的雙親結(jié)點(diǎn)是______，孩子結(jié)點(diǎn)是______。 48、完全二叉樹、滿二叉樹、線索二叉樹和二叉排序樹這四個(gè)名詞術(shù)語中，與數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)有關(guān)系的是_____________。 47、有三個(gè)結(jié)點(diǎn)的二叉樹，最多有________種形狀。 48、每一趟排序時(shí)從排好序的元素中挑出一個(gè)

24、值最小的元素與這些未排小序的元素的第一個(gè)元素交換位置，這種排序方法成為_____________排序法。 49、高度為k的二叉樹具有的結(jié)點(diǎn)數(shù)目，最少為_____,最多為_____。 50、對(duì)任何一棵二叉樹，若n0，n1，n2分別是度為0，1，2的結(jié)點(diǎn)的個(gè)數(shù)，則n0=_______。 51、在含100個(gè)結(jié)點(diǎn)的完全二叉樹，葉子結(jié)點(diǎn)的個(gè)數(shù)為_______。 52、將一個(gè)數(shù)據(jù)元素（或記錄）的任意序列，重新排列成一個(gè)按關(guān)鍵字有序的序列叫_____。 53、若一棵滿二叉樹含有121個(gè)結(jié)點(diǎn)，則該樹的深度為_________。 54、一個(gè)具有767個(gè)結(jié)點(diǎn)的完全二叉樹，其葉子結(jié)點(diǎn)個(gè)數(shù)為_______

25、_。 55、深度為90的滿二叉樹，第11層有________個(gè)結(jié)點(diǎn)。 56、有100個(gè)結(jié)點(diǎn)的完全二叉樹，深度為________。 57、設(shè)一棵二叉樹中度為2的結(jié)點(diǎn)10個(gè)，則該樹的葉子個(gè)數(shù)為________。 58、若待散列的序列為(18,25,63,50,42,32,9)，散列函數(shù)為H(key)=key?MOD?9，與18發(fā)生沖突的元素有_____________個(gè)。 59、含有3個(gè)2度結(jié)點(diǎn)和4個(gè)葉結(jié)點(diǎn)的二叉樹可含__________個(gè)1度結(jié)點(diǎn)。 60、一棵具有５層滿二叉樹中節(jié)點(diǎn)總數(shù)為___________。 61、一棵含有16個(gè)結(jié)點(diǎn)的完全二叉樹，對(duì)他按層編號(hào)，對(duì)于編號(hào)為7的結(jié)點(diǎn)

26、，他的雙親結(jié)點(diǎn)及左右結(jié)點(diǎn)編號(hào)為______、______、_______。 62、深度為k(設(shè)根的層數(shù)為1)的完全二叉樹至少有_______個(gè)結(jié)點(diǎn),?至多有_______個(gè)結(jié)點(diǎn)。 63、若要對(duì)某二叉排序樹進(jìn)行遍歷，保證輸出所有結(jié)點(diǎn)的值序列按增序排列，應(yīng)對(duì)該二叉排序樹采用________遍歷法。 64、在序列(2,5,8,11,15,16,22,24,27,35,50)中采用折半查找(二分查找)方法查找元素24，需要進(jìn)行______________次元素之間的比較。 65、設(shè)有10個(gè)值，構(gòu)成哈夫曼樹，則該哈夫曼樹共有______個(gè)結(jié)點(diǎn)。 66、從樹中一個(gè)結(jié)點(diǎn)到另一個(gè)結(jié)點(diǎn)之間的分支構(gòu)成這

27、兩個(gè)結(jié)點(diǎn)之間的____________。 67、關(guān)鍵字自身作為哈希函數(shù)，即H（k）=k，也可自身加上一個(gè)常數(shù)作為哈希函數(shù)，即H(k)=k+C這種構(gòu)造哈希函數(shù)的方式叫____________。 68、對(duì)于一個(gè)圖G，若邊集合E（G）為無向邊的集合，則稱該圖為____________。 69、對(duì)于一個(gè)圖G，若邊集合E（G）為有向邊的集合，則稱該圖為____________。 70、對(duì)于有向圖，頂點(diǎn)的度分為入度和出度，以該頂點(diǎn)為終點(diǎn)的邊數(shù)目叫________；以該頂點(diǎn)為起點(diǎn)的邊數(shù)目叫_________。 71、一個(gè)無向圖采用鄰接矩陣存儲(chǔ)方法，其鄰接矩陣一定是一個(gè)______________。

28、 72、有一個(gè)n個(gè)頂點(diǎn)的有向完全圖的弧數(shù)_____________。 73、在無向圖中，若從頂點(diǎn)A到頂點(diǎn)B存在_________，則稱A與B之間是連通的。 74、在一個(gè)無向圖中，所有頂點(diǎn)的度數(shù)之和等于所有邊數(shù)的___________倍。 75、一個(gè)連通圖的生成樹是該圖的____________連通子圖。若這個(gè)連通圖有n個(gè)頂點(diǎn),?則它的生成樹有__________條邊。 76、無向圖的鄰接矩陣是一個(gè)_____________矩陣。 77、如果從一無向圖的任意頂點(diǎn)出發(fā)進(jìn)行一次深度優(yōu)先搜索即可訪問所有頂點(diǎn)，則該圖一定是_____?_______。 78、若采用鄰接表的存儲(chǔ)結(jié)構(gòu)，則圖的廣

29、度優(yōu)先搜索類似于二叉樹的____________遍歷。 79、若圖的鄰接矩陣是對(duì)稱矩陣，則該圖一定是________________。 80、從如圖所示的臨接矩陣可以看出，該圖共有______個(gè)頂點(diǎn)。如果是有向圖，該圖共有______條弧；如果是無向圖，則共有________條邊。 81、如果從一個(gè)頂點(diǎn)出發(fā)又回到該頂點(diǎn)，則此路徑叫做___________。 82、一個(gè)具有個(gè)n頂點(diǎn)的無向圖中，要連通全部頂點(diǎn)至少需要________條邊。 83、給定序列{100,?86,?48,?73,?35,?39,?42,?57,?66,?21},?按堆結(jié)構(gòu)的定義,?則它一定_________堆。

30、 84、從未排序序列中選擇一個(gè)元素，該元素將當(dāng)前參加排序的那些元素分成前后兩個(gè)部分，前一部分中所有元素都小于等于所選元素，后一部分中所有元素都大于或等于所選元素，而此時(shí)所選元素處在排序的最終位置。這種排序法稱為_____________排序法。 85、折半搜索只適合用于___________________。 86、結(jié)點(diǎn)關(guān)鍵字轉(zhuǎn)換為該結(jié)點(diǎn)存儲(chǔ)單元地址的函數(shù)H稱為_____________或叫__________。 87、在索引查找中，首先查找________，然后查找相應(yīng)的_________，整個(gè)索引查找的平均查找長度等于查找索引表的平均長度與查找相應(yīng)子表的平均查找長度的_______。

31、 三、選擇題： （??????及它們之間的聯(lián)系。 A存儲(chǔ)和邏輯結(jié)構(gòu)?? B存儲(chǔ)和抽象?? C理想和抽象???? D理想與邏輯 （??????。 A先進(jìn)先出???????? B后進(jìn)先出????? C先進(jìn)后出?????? D隨意進(jìn)出 （???）3.將一棵有100個(gè)結(jié)點(diǎn)的完全二叉樹從上到下，從左到右依次對(duì)結(jié)點(diǎn)進(jìn)行編號(hào)，根結(jié)點(diǎn)的編號(hào)為1，則編號(hào)為49的結(jié)點(diǎn)的左孩子的編號(hào)為______。 ????????????????????? ??????????? (???)4.對(duì)于如圖所示二叉樹采用中根遍歷，正確的遍歷序列應(yīng)為(????) ???????????????????? ??

32、?????????????????? （???）5.設(shè)有100個(gè)元素，用折半查找法進(jìn)行查找時(shí)，最大比較次數(shù)是_____?。 ????????? ???????? （???）6.快速排序在_____情況下最易發(fā)揮其長處。 ? ???????????? （????）7.由兩個(gè)棧共享一個(gè)向量空間的好處是______。????? A減少存取時(shí)間,降低下溢發(fā)生的機(jī)率? B節(jié)省存儲(chǔ)空間,降低上溢發(fā)生的機(jī)率 C減少存取時(shí)間,降低上溢發(fā)生的機(jī)率? D節(jié)省存儲(chǔ)空間,降低下溢發(fā)生的機(jī)率 （????）8.某二叉樹的前序和后序序列正好相反，則該二叉樹一定是_____的二叉樹 A空或者只有一個(gè)結(jié)點(diǎn)

33、??? B高度等于其結(jié)點(diǎn)數(shù) C任一結(jié)點(diǎn)無左孩子????? D任一結(jié)點(diǎn)無右孩子 （????）9.設(shè)散列表長m=14,散列函數(shù)H（K）=K％11，已知表中已有4個(gè)結(jié)點(diǎn)：r(15)=4;?r(38)=5;?r(61)=6;r(84)=7，其他地址為空，如用二次探測再散列處理沖突，關(guān)鍵字為49的結(jié)點(diǎn)地址是________。 A8?????????B3?????? C5???????????D9 （???）10.在含有n個(gè)項(xiàng)點(diǎn)有e條邊的無向圖的鄰接矩陣中，零元素的個(gè)數(shù)為________。 ?????????????????? ????????? （?????）11.圖的深度優(yōu)先遍歷類似于

34、二叉樹的_______。 ?????????? ?????????? （????）12.設(shè)長度為n的鏈隊(duì)列用單循環(huán)鏈表表示，若只設(shè)頭指針，則入隊(duì)操作的時(shí)間復(fù)雜度為_______。 A.?O(1)??????? B.?O(log2n)?????? C.?O(n)??????????? D.?O(n2) （????）13.堆的形狀是一棵_______。 ????????????????? ???????????? （????）14.一個(gè)無向連連通圖的生成樹是含有該連通圖的全部項(xiàng)點(diǎn)的_______。 ???????????????? ??????????? （????）15.

35、一個(gè)序列中有10000個(gè)元素，若只想得到其中前10個(gè)最小元素，最好采用_______方法 ?????????????????? ????????????????????? （??? 　　typedef?struct?node?{? 　　ElemType?data；? 　　struct?node?*?Link；? 　　}?ListNode； 　　 已知指針p所指結(jié)點(diǎn)不是尾結(jié)點(diǎn)，若在*p之后插入結(jié)點(diǎn)*s，則應(yīng)執(zhí)行下列哪一個(gè)操作______。 A.?s->link?=?p；?p->link?=?s；　　B.?s->link?=?p->link；?p->link?=?s； C.?s

36、->link?=?p->link；?p?=?s；????D.?p->link?=?s；?s->link?=?p； （??? typedef?struct?node? {? ElemType?data；? struct?node?*?Link；? }?ListNode； 非空的循環(huán)單鏈表first的尾結(jié)點(diǎn)（由p所指向）滿足：______ A.?p->link?==?NULL；　　?B.?p?==?NULL； C.?p->link?==?first；　　D.?p?==?first； （????）18.計(jì)算機(jī)識(shí)別、存儲(chǔ)和加工處理的對(duì)象被統(tǒng)稱為_________ A．?dāng)?shù)據(jù) ???

37、???????? ???????????? （??? A．O（1）??????B.O（n）? C.O(nlogn) D.O(n2) （???）20．隊(duì)和棧的主要區(qū)別是________ ????????????? ????? （????）21．鏈棧與順序棧相比，比較明顯的優(yōu)點(diǎn)是________ ?????? ???? （????）22．在目標(biāo)串T[0…n-1]=”xwxxyxy”中，對(duì)模式串p[0…m-1]=”xy”進(jìn)行子串定位操作的結(jié)果_______ A.0 ???????????? C.3 ???????? （???）23．已知廣義表的表頭為A，表尾為(B,C)，

38、則此廣義表為________ A.（A,(B,C)） ??B.（A,B,C） C.(A,B,C) ??????D.((?A,B,C)) （???）24．二維數(shù)組A按行順序存儲(chǔ)，其中每個(gè)元素占1個(gè)存儲(chǔ)單元。若A[1][1]的存儲(chǔ)地址為420，A[3][3]的存儲(chǔ)地址為446，則A[5][5]的存儲(chǔ)地址為_______ A.470 ????????? C.472 ????????? （????）25．二叉樹中第5層上的結(jié)點(diǎn)個(gè)數(shù)最多為________ A.8 ?????????? C.16 ?????????????? （???）26．如果某圖的鄰接矩陣是對(duì)角線元素均為零的上三角矩

39、陣，則此圖是_______ A.有向完全圖 ???? （????）27．對(duì)n個(gè)關(guān)鍵字的序列進(jìn)行快速排序，平均情況下的空間復(fù)雜度為_______ A.O（1） ??????????B.O（logn） C.O（n） ??????????D.O（nlogn） （???）28．對(duì)于哈希函數(shù)H(key)=key%13，被稱為同義詞的關(guān)鍵字是_______ A．35和41 ????????? C.15和44 ????????????? （???）29.?由權(quán)值分別為3,8,6,2,5的葉子結(jié)點(diǎn)生成一棵哈夫曼樹，它的帶權(quán)路徑長度為________。 A、?24?????????????

40、????????????????B、?48?????? C、?72?????????????????????????????D、?53 （???）30．對(duì)包含N個(gè)元素的散列表進(jìn)行檢索，平均檢索長度?________ A、為?o(log2N)?????????????B、為o(N)? C、不直接依賴于N??????????D、上述三者都不是 （???）31.?向堆中插入一個(gè)元素的時(shí)間復(fù)雜度為________。 A、?O(log2n)??????????????????????B、?O(n)?????? C、?O(1)??????????????????????????D、?O(nl

41、og2n) （????）32．下面關(guān)于圖的存儲(chǔ)的敘述中，哪一個(gè)是正確的。?________ A．用相鄰矩陣法存儲(chǔ)圖,占用的存儲(chǔ)空間數(shù)只與圖中結(jié)點(diǎn)個(gè)數(shù)有關(guān),而與邊數(shù)無關(guān)? B．用相鄰矩陣法存儲(chǔ)圖,占用的存儲(chǔ)空間數(shù)只與圖中邊數(shù)有關(guān),而與結(jié)點(diǎn)個(gè)數(shù)無關(guān) C．用鄰接表法存儲(chǔ)圖，占用的存儲(chǔ)空間數(shù)只與圖中結(jié)點(diǎn)個(gè)數(shù)有關(guān)，而與邊數(shù)無關(guān) D．用鄰接表法存儲(chǔ)圖，占用的存儲(chǔ)空間數(shù)只與圖中邊數(shù)有關(guān)，而與結(jié)點(diǎn)個(gè)數(shù)無關(guān) （????）33.輸入序列為（A,B,C,D），不可能得到的輸出序列是______. A.?(A,B,C,D)????????????????B.(D,C,B,A) C.(A,?C,D,B)

42、????????????????D.(C,A,B,D) （???）34.在長度為n的順序存儲(chǔ)的線性表中，刪除第i個(gè)元素（1≤i≤n）時(shí)，需要從前向后依次前移____個(gè)元素。 A、n-i?????????????????????????B、n-i+1??????????? C、n-i-1???????????????????????D、i （???）35.設(shè)一個(gè)廣義表中結(jié)點(diǎn)的個(gè)數(shù)為n，則求廣義表深度算法的時(shí)間復(fù)雜度為____。 A、O(1)?????????????????????B、O(n)??????????? C、O(n2)????????????????????D、O(log

43、?2?n) （???）36.假定一個(gè)順序隊(duì)列的隊(duì)首和隊(duì)尾指針分別為f和r，則判斷隊(duì)空的條件為?____。 A、f+1==r??????????????????????B、r+1==f????????? C、f==0????????????????????????D、f==r （???）37.從堆中刪除一個(gè)元素的時(shí)間復(fù)雜以為____。 A、O(1)??????????????????????B、O(log?2?n)?????? C、O(n)??????????????????????D、O(nlog?2?n) （???）38．若需要利用形參直接訪問實(shí)參，則應(yīng)把形參變量說明為____

44、參數(shù)。 ????????????????????????????? C.值 ?????????????? （????）39．在一個(gè)單鏈表HL中，若要在指針q所指結(jié)點(diǎn)的后面插入一個(gè)由指針p所指向的結(jié)點(diǎn)，則執(zhí)行____。 A.?q一>next=p一>next；p一>next=q；C.?q一>next=p一>next；p一>next=q； B.?p一>next=q一>next；q=p；????????D.?p一>next=q一>next；q一>next=p； （????）40．在一個(gè)順序隊(duì)列中，隊(duì)首指針指向隊(duì)首元素的____位置。 ???????????????????????????

45、? ???????????????????? （???）41．向二叉搜索樹中插入一個(gè)元素時(shí)，其時(shí)間復(fù)雜度大致力____。 A??O（1）?????????????????????????B??O（1og2n） C??O（n）?????????????????????????D??O（nlog2n） （??? A.計(jì)算機(jī)程序 ???? （???）43.線性表采用鏈?zhǔn)酱鎯?chǔ)時(shí)，結(jié)點(diǎn)的存儲(chǔ)地址________ A.必須是不連續(xù)的 ???? （??? A.O（1） ???????B.O（n） C.O（m） ???????????D.O（m+n） （???）45.由兩個(gè)棧共

46、享一個(gè)向量空間的好處是：________ A.減少存取時(shí)間，降低下溢發(fā)生的機(jī)率?B.節(jié)省存儲(chǔ)空間，降低上溢發(fā)生的機(jī)率 C.減少存取時(shí)間，降低上溢發(fā)生的機(jī)率?D.節(jié)省存儲(chǔ)空間，降低下溢發(fā)生的機(jī)率 （???）46.設(shè)數(shù)組DAtA[m]作為循環(huán)隊(duì)列SQ的存儲(chǔ)空間，front為隊(duì)頭指針，reAr為隊(duì)尾指針，則執(zhí)行出隊(duì)操作后其頭指針front值為________ A.?front=front+1????????????B.?front=(front+1)%(m-1) C.?front=(front-1)%m????????D.?front=(front+1)%m （?? A.?串是一種特殊

47、的線性表?????????B.?串的長度必須大于零 C.?串中元素只能是字母?????????D.?空串就是空白串 （???）48.若目標(biāo)串的長充為n，模式串的長度為[n/3]，則執(zhí)行模式匹配算法時(shí)，在最壞情況下的時(shí)間復(fù)雜度是________ A.O（1） ???????????B.O（n） C.O（n2） ???????????D.O（n3） （??? C.只能是原子 ???? （???）50.?從堆中刪除一個(gè)元素的時(shí)間復(fù)雜度為________。 A、?O(1)?????????????????????????B、?O(n)?????? C、?O(log2n)?????

48、????????????????D、?O(nlog2n) （????）51.一棵度為3的樹中，度為3的結(jié)點(diǎn)個(gè)數(shù)為2，度為2的結(jié)點(diǎn)個(gè)數(shù)為1，則度為0的結(jié)點(diǎn)個(gè)數(shù)為________ A.4 ?????????? C.6 ?????????? （???）52.?從二叉搜索樹中查找一個(gè)元素時(shí)，其時(shí)間復(fù)雜度大致為________。 A、?O(n)????????????????????????B、?O(1)?????? C、?O(log2n)????????????????????D、?O(n2) （???）53.?根據(jù)n個(gè)元素建立一棵二叉搜索樹時(shí)，其時(shí)間復(fù)雜度大致為________。 A

49、、?O(n)?????????????????????B、?O(log2n?)?????? C、?O(n2)????????????????????D、?O(nlog2n) （???）54.用某種排序方法對(duì)關(guān)鍵字序列（25，84，21，47，15，27，68，35，20）進(jìn)行排序時(shí)，序列的變化情況是如下________： ?????????20，15，21，25，47，27，68，35，84 ?????????15，20，21，25，35，27，47，68，84 ?????????15，20，21，25，27，35，47，68，84 則所采用的排序方法是________ A.選擇

50、排序 ??????????????? C.歸并排序 ??????????????? （??? A.有序表 ????????????? C.二叉排序樹 ????????? （????）56.?若需要利用形參直接訪問實(shí)參，則應(yīng)把形參變量說明為________參數(shù)。? A?指針???????????????????????B?引用????????? C?值?????????????????????????D?常量? （?????）57.鏈?zhǔn)綏Ｅc順序棧相比，一個(gè)比較明顯的優(yōu)點(diǎn)是________。? A.?插入操作更加方便 ????????????B.?通常不會(huì)出現(xiàn)棧滿的情況? C.

51、?不會(huì)出現(xiàn)?？盏那闆r ????????????D.?刪除操作更加方便? （????）58.設(shè)單鏈表中結(jié)點(diǎn)的結(jié)構(gòu)為（data,?link）。已知指針q所指結(jié)點(diǎn)是指針p所指結(jié)點(diǎn)的直接前驅(qū)，若在*q與*p之間插入結(jié)點(diǎn)*s，則應(yīng)執(zhí)行下列哪一個(gè)操作________? A.?s->link?=?p->link;?p->link?=?s;?????B.?p->link?=?s;?s->link?=?q; C.?p->link?=?s->link;?s->link?=?p;?????D.?q->link?=?s;?s->link?=?p; （?????）59．若讓元素1,2,3依次進(jìn)棧，則出棧次序不可

52、能出現(xiàn)________種情況。? A.?3,?2,?1??????????????????????????B.?2,?1,?3? C.?3,?1,?2??????????????????????????D.?1,?3,?2? （???）60.線性鏈表不具有的特點(diǎn)是________。? A.?隨機(jī)訪問???????????????????????B.?不必事先估計(jì)所需存儲(chǔ)空間大小? C.?插入與刪除時(shí)不必移動(dòng)元素???????D.?所需空間與線性表長度成正比? （???）61．在稀疏矩陣的十字存儲(chǔ)中，每個(gè)列單鏈表中的結(jié)點(diǎn)都具有相同的_____。? Ａ．行號(hào)?????????????

53、??????Ｂ．列號(hào)?????????? Ｃ．元素值?????????????????Ｄ．地址? （????）62.假定一個(gè)順序隊(duì)列的隊(duì)首和隊(duì)尾指針分別為front和rear，存放該隊(duì)列的數(shù)組長度為N，則判斷隊(duì)空的條件為________。? A．（front+1）%?N?==?rear???????????C．?front?==?0 B．（rear+1）%?N?==?front???????????D．?front?==?rear （???）63．棧的插入和刪除操作在＿＿＿進(jìn)行．? (Ａ)．棧頂　????????????????(Ｂ)．棧底 (Ｃ)．任意位置???????????

54、???(Ｄ).指定位置? （????）64.?在一個(gè)順序循環(huán)隊(duì)列中，隊(duì)首指針指向隊(duì)首元素的________位置。? A.?后兩個(gè)????????????????B.?后一個(gè) C.?當(dāng)前??????????????????? （????）65．下面算法的時(shí)間復(fù)雜度為＿＿。? int?f（int?n）{? if?（n＝＝0）return?1；? else??return??n＊f（n-1）；}? A．O(1)?????????????B．O(n)　?? C．O(n2)??????????D．O(n!) （????）66.數(shù)據(jù)結(jié)構(gòu)是一門研究非數(shù)值計(jì)算的程序設(shè)計(jì)問題中計(jì)算機(jī)的（?、?/p>

55、?。┮约八鼈冎g的（?、凇。┖瓦\(yùn)算的學(xué)科①Ａ、操作對(duì)象?。?、計(jì)算方法?。?、邏輯存儲(chǔ)?。?、數(shù)據(jù)映象 ②Ａ、結(jié)構(gòu)　　?。?、關(guān)系　　　Ｃ、運(yùn)算　　?。摹⑺惴? （????）67.數(shù)據(jù)結(jié)構(gòu)被形式地定義為(K，R)，其中K是（?、佟。┑挠邢藜希琑是K上（?、凇。┑挠邢藜? ①Ａ、算法　Ｂ、數(shù)據(jù)元素　Ｃ、數(shù)據(jù)操作　Ｄ、邏輯結(jié)韻 ②Ａ、操作?。?、映象　　?。?、存儲(chǔ)　　?。?、關(guān)系 （????）68.在數(shù)據(jù)結(jié)構(gòu)中，從邏輯上可以把數(shù)據(jù)結(jié)構(gòu)分為________ Ａ、動(dòng)態(tài)結(jié)構(gòu)和靜態(tài)結(jié)構(gòu)　　 Ｂ、緊湊結(jié)構(gòu)和非緊湊結(jié)構(gòu) Ｃ、線性結(jié)構(gòu)和非線性結(jié)構(gòu)　 Ｄ、部結(jié)構(gòu)和外部結(jié)構(gòu) （????）69.線性表的順序存儲(chǔ)結(jié)

56、構(gòu)是一種_________的存儲(chǔ)結(jié)構(gòu)，線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)是一種________的存儲(chǔ)結(jié)構(gòu) Ａ、隨機(jī)存取　　??????????????Ｂ、順序存取　　 Ｃ、索引存取　　 ????????????Ｄ、HASH存取 （????）70.算法分析的目的是（?、佟。?，算法分析的兩個(gè)主要方面是（?、凇。? ①Ａ、找出數(shù)據(jù)結(jié)構(gòu)的合理性???????Ｃ、分析算法的效率以求改進(jìn) 　　　 Ｂ、研究算法中的輸入和輸出的關(guān)系Ｄ、分析算法的易懂性和文檔性 ②Ａ、空間復(fù)雜性和時(shí)間復(fù)雜性???Ｃ、可讀性和文檔性 Ｂ、正確性和簡明性???????????Ｄ、數(shù)據(jù)復(fù)雜性和程序復(fù)雜性 （????）71.計(jì)算機(jī)算法

57、指的是（?、佟。?，它必具備輸入、輸出和（?、凇。┑任鍌€(gè)特性 ①Ａ、計(jì)算方法　 Ｂ、排序方法　 Ｃ、解決萊一問題的有限運(yùn)算序列　 Ｄ、調(diào)度方法 ②Ａ、可執(zhí)行性、可移植性和可擴(kuò)充性??????Ｃ、確定性、有窮性和穩(wěn)定性 Ｂ、可執(zhí)行性、確定性和有窮性??????????Ｄ、易謾性、穩(wěn)定性和安全性 （????）72.線性表若采用鏈表存儲(chǔ)結(jié)構(gòu)時(shí)，要求存中可用存儲(chǔ)單元的地址________ Ａ、必須是連續(xù)的　　?。?、部分地址必須是連續(xù)的 Ｃ、一定是不連續(xù)的　?。?、連續(xù)不連續(xù)都可以 （????）73.在以下的敘述中，正確的是__________ Ａ、線性表的線性存儲(chǔ)結(jié)構(gòu)優(yōu)于鏈表存儲(chǔ)結(jié)構(gòu)??

58、??????Ｃ、棧的操作方式是先進(jìn)先出 Ｂ、二維數(shù)組是它的每個(gè)數(shù)據(jù)元素為一個(gè)線性表的線性表Ｄ、隊(duì)列的操作方式是先進(jìn)后出 （???）74.?一個(gè)數(shù)組元素A[i]與________的表示等價(jià)。 A、?*(A+i)??????B、?A+i????????? C、?*A+i????????D、?&A+i? （???）75.?對(duì)于兩個(gè)函數(shù)，若函數(shù)名相同，但只是____________不同則不是重載函數(shù)。 A、?參數(shù)類型?????????????B、?參數(shù)個(gè)數(shù)???? C、?函數(shù)類型 ???????D、函數(shù)變量 （????）76.?若需要利用形參直接訪問實(shí)參，則應(yīng)把形參變量說明為_____

59、___參數(shù) A、?指針??????????????B、?引用???????? C、?值 D、函數(shù) （???）77.下面程序段的時(shí)間復(fù)雜度為____________。 ????????for(int?i=0;?i

60、??????for(int?i=1;?i<=n;?i++) ????????????for(int?j=1;?j<=i;?j++) ????????????????S; A、?n2????????????B、?n2/2????????? C、?n(n+1)????????D、?n(n+1)/2 （????）79.?下面算法的時(shí)間復(fù)雜度為____________。 ????????int??f(?unsigned??int??n?)?{ ????????????if?(?n==0?||?n==1?)?return??1;???else??return??n*f(n-1); ???

61、?????} A、?O(1)??????????????B、?O(n)????????? C、?O(n2)?????????????D、?O(n!) （???）80．在一個(gè)長度為n的順序存儲(chǔ)線性表中，向第i個(gè)元素(1≤i≤n+1)之前插入一個(gè)新元素時(shí)，需要從后向前依次后移????????個(gè)元素。 A、n-i?????????????????B、n-i+1???????? C、n-i-1???????????????D、i （???）81．在一個(gè)長度為n的順序存儲(chǔ)線性表中，刪除第i個(gè)元素(1≤i≤n+1)時(shí)，需要從前向后依次前移_____個(gè)元素。 A、n-i????????????

62、B、n-i+1???????? C、n-i-1??????????D、i （???）82.在一個(gè)長度為n的線性表中順序查找值為x的元素時(shí)，查找時(shí)的平均查找長度（即x同元素的平均比較次數(shù)，假定查找每個(gè)元素的概率都相等）為_____。 A、n?????????????????????B、n/2?????????? C、(n+1)/2???????????????D、(n-1)/2 （???）83．在一個(gè)單鏈表HL中，若要向表頭插入一個(gè)由指針p指向的結(jié)點(diǎn)，則執(zhí)行_____?。 A、HL?=?p;??p->next?=?HL;?C、p->next?=?HL;???p?=?HL; B、p-

63、>next?=?HL;??HL?=?p;?D、p->next?=?HL->next;??HL->next?=?p; （???）84．在一個(gè)單鏈表HL中，若要在指針q所指的結(jié)點(diǎn)的后面插入一個(gè)由指針p所指的結(jié)點(diǎn)，則執(zhí)行_____。 A、q->next?=?p->next?;??p->next?=?q;?C、q->next?=?p->next;??p->next?=?q; B、p->next?=?q->next;??q?=?p;????????D、p->next?=?q->next?;??q->next?=?p; （???）85．在一個(gè)單鏈表HL中，若要?jiǎng)h除由指針q所指向結(jié)點(diǎn)的后繼結(jié)點(diǎn)，則執(zhí)

64、行_____。 A、p?=?q->next?;??p->next?=?q->next;?C、p?=?q->next?;??q->next?=?p->next; B、p?=?q->next?;??q->next?=?p;?D、q->next?=?q->next->next;??q->next?=?q; （???）86.?在稀疏矩陣的帶行指針向量的存儲(chǔ)中，每個(gè)行單鏈表中的結(jié)點(diǎn)都具有相同的________。 A、?行號(hào)????????B、?列號(hào)?????? C、?元素值??????D、?地址 （???）87.?設(shè)一個(gè)廣義表中結(jié)點(diǎn)的個(gè)數(shù)為n，則求廣義表深度算法的時(shí)間復(fù)雜度為_______。

65、 A、?O(1)???????B、?O(n)?????? C、?O(n2)??????D、?O(log2n) （???）88．棧的插入與刪除操作在_____進(jìn)行。 A、棧頂??????????B、棧底?????????? C、任意位置??????D、指定位置 （???）89．當(dāng)利用大小為N的一維數(shù)組順序存儲(chǔ)一個(gè)棧時(shí)，假定用top==N表示棧空，則向這個(gè)棧插入一個(gè)元素時(shí)，首先應(yīng)執(zhí)行_____語句修改top指針。 A、top++??????????B、top--????????? C、top=0??????????D、top （???）90．若讓元素1，2，3依次進(jìn)棧，則出棧次序

66、不可能出現(xiàn)_____種情況。 A、3，2，1??????????B、2，1，3??????? C、3，1，2??????????D、1，3，2 （???）91．在一個(gè)循環(huán)順序隊(duì)列中，隊(duì)首指針指向隊(duì)首元素的_____位置。 A、前一個(gè)????????????????B、后一個(gè)???????? C、當(dāng)前??????????????????D、后面 （???）92．當(dāng)利用大小為N的一維數(shù)組順序存儲(chǔ)一個(gè)循環(huán)隊(duì)列時(shí)，該隊(duì)列的最大長度為_____。 A、N-2???????????????????B、N-1??????????? C、N?????????????????????D、N+1 （???）93．從一個(gè)循環(huán)順序隊(duì)列刪除元素時(shí)，首先需要_____。 A、前移一位隊(duì)首指針?????????????????B、后移一位隊(duì)首指針 C、取出隊(duì)首指針?biāo)肝恢蒙系脑?????D、取出隊(duì)尾指針?biāo)肝恢蒙系脑? （???）94．假定一個(gè)循環(huán)順序隊(duì)列的隊(duì)首和隊(duì)尾指針分別為f和r，則判斷隊(duì)空的條件是_____。 A、f+1==r?????????????????????????B、r