數(shù)字結(jié)構(gòu)考試題及答案

一、單項(xiàng)選擇題（每題2分，共10題）1.線性表采用鏈?zhǔn)酱鎯?chǔ)時(shí)，其地址（）A.必須是連續(xù)的B.部分地址必須是連續(xù)的C.一定是不連續(xù)的D.連續(xù)與否均可以2.棧和隊(duì)列的共同特點(diǎn)是（）A.只允許在端點(diǎn)處插入和刪除元素B.都是先進(jìn)后出C.都是先進(jìn)先出D.沒(méi)有共同點(diǎn)3.樹最適合用來(lái)表示（）A.有序數(shù)據(jù)元素B.無(wú)序數(shù)據(jù)元素C.元素之間具有分支層次關(guān)系的數(shù)據(jù)D.元素之間無(wú)聯(lián)系的數(shù)據(jù)4.深度為5的二叉樹至多有（）個(gè)結(jié)點(diǎn)。A.16B.32C.31D.105.對(duì)線性表進(jìn)行折半查找時(shí)，要求線性表必須（）A.以順序方式存儲(chǔ)B.以順序方式存儲(chǔ)，且數(shù)據(jù)元素有序C.以鏈?zhǔn)椒绞酱鎯?chǔ)D.以鏈?zhǔn)椒绞酱鎯?chǔ)，且數(shù)據(jù)元素有序6.排序方法中，從未排序序列中依次取出元素與已排序序列（初始時(shí)為空）中的元素進(jìn)行比較，將其放入已排序序列的正確位置上的方法，稱為（）A.希爾排序B.冒泡排序C.插入排序D.選擇排序7.一個(gè)具有n個(gè)頂點(diǎn)的無(wú)向圖最多有（）條邊。A.n(n-1)/2B.n(n-1)C.n(n+1)/2D.n28.在一個(gè)單鏈表中，若p所指結(jié)點(diǎn)不是最后結(jié)點(diǎn)，在p之后插入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;9.若一個(gè)棧的輸入序列為1,2,3,…,n，輸出序列的第一個(gè)元素是i，則第j個(gè)輸出元素是（）A.i-j-1B.i-jC.j-i+1D.不確定的10.已知一棵二叉樹的前序遍歷序列為ABCDEFG，中序遍歷序列為CBDAEGF，則后序遍歷序列為（）A.CDBGFEAB.CDBFGEAC.CDBAGFED.BCDAGFE二、多項(xiàng)選擇題（每題2分，共10題）1.以下屬于數(shù)據(jù)結(jié)構(gòu)中邏輯結(jié)構(gòu)的有（）A.線性結(jié)構(gòu)B.樹形結(jié)構(gòu)C.順序存儲(chǔ)結(jié)構(gòu)D.鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)2.以下關(guān)于棧的說(shuō)法正確的有（）A.棧是后進(jìn)先出的線性表B.棧可以用順序存儲(chǔ)結(jié)構(gòu)實(shí)現(xiàn)C.?？梢杂面?zhǔn)酱鎯?chǔ)結(jié)構(gòu)實(shí)現(xiàn)D.棧只能在棧頂進(jìn)行操作3.圖的遍歷方法有（）A.深度優(yōu)先搜索B.廣度優(yōu)先搜索C.中序遍歷D.后序遍歷4.排序算法中，穩(wěn)定的排序有（）A.冒泡排序B.選擇排序C.插入排序D.歸并排序5.下列關(guān)于二叉樹的說(shuō)法正確的是（）A.滿二叉樹一定是完全二叉樹B.完全二叉樹一定是滿二叉樹C.二叉樹的度可以為0D.二叉樹的度最大為26.鏈表相對(duì)于數(shù)組的優(yōu)點(diǎn)有（）A.插入和刪除操作效率高B.不需要連續(xù)的存儲(chǔ)空間C.隨機(jī)訪問(wèn)效率高D.內(nèi)存占用少7.隊(duì)列的基本運(yùn)算有（）A.入隊(duì)B.出隊(duì)C.讀取隊(duì)頭元素D.判斷隊(duì)列是否為空8.以下屬于非線性結(jié)構(gòu)的有（）A.樹B.圖C.棧D.隊(duì)列9.可以用于查找的方法有（）A.順序查找B.折半查找C.哈希查找D.二叉排序樹查找10.數(shù)據(jù)結(jié)構(gòu)的存儲(chǔ)結(jié)構(gòu)包括（）A.順序存儲(chǔ)結(jié)構(gòu)B.鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)C.索引存儲(chǔ)結(jié)構(gòu)D.散列存儲(chǔ)結(jié)構(gòu)三、判斷題（每題2分，共10題）1.數(shù)據(jù)的邏輯結(jié)構(gòu)與存儲(chǔ)結(jié)構(gòu)是一一對(duì)應(yīng)的。（）2.棧和隊(duì)列都是特殊的線性表。（）3.完全二叉樹中，若一個(gè)結(jié)點(diǎn)沒(méi)有左孩子，則它一定沒(méi)有右孩子。（）4.圖的鄰接矩陣表示法是唯一的。（）5.冒泡排序是一種不穩(wěn)定的排序算法。（）6.線性表的順序存儲(chǔ)結(jié)構(gòu)比鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)更有利于隨機(jī)存取。（）7.哈希表的查找效率與哈希函數(shù)、處理沖突的方法及裝填因子有關(guān)。（）8.樹的度是指樹中所有結(jié)點(diǎn)的度數(shù)之和。（）9.隊(duì)列是先進(jìn)后出的線性表。（）10.折半查找只能在有序的順序表中進(jìn)行。（）四、簡(jiǎn)答題（每題5分，共4題）1.簡(jiǎn)述線性表順序存儲(chǔ)結(jié)構(gòu)和鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)的優(yōu)缺點(diǎn)。2.什么是棧的“上溢”和“下溢”現(xiàn)象？3.簡(jiǎn)述圖的鄰接矩陣和鄰接表存儲(chǔ)結(jié)構(gòu)的特點(diǎn)。4.簡(jiǎn)述冒泡排序的基本思想。五、討論題（每題5分，共4題）1.討論在什么情況下選擇順序存儲(chǔ)結(jié)構(gòu)，什么情況下選擇鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)。2.討論棧和隊(duì)列在實(shí)際應(yīng)用中的場(chǎng)景。3.討論不同排序算法的時(shí)間復(fù)雜度和適用場(chǎng)景。4.討論哈希表的優(yōu)缺點(diǎn)及適用場(chǎng)景。答案一、單項(xiàng)選擇題1.D2.A3.C4.C5.B6.C7.A8.B9.D10.A二、多項(xiàng)選擇題1.AB2.ABCD3.AB4.ACD5.ACD6.AB7.ABCD8.AB9.ABCD10.ABCD三、判斷題1.×2.√3.√4.√5.×6.√7.√8.×9.×10.√四、簡(jiǎn)答題1.順序存儲(chǔ)優(yōu)點(diǎn)：隨機(jī)訪問(wèn)快；缺點(diǎn)：插入刪除慢，需連續(xù)空間。鏈?zhǔn)酱鎯?chǔ)優(yōu)點(diǎn)：插入刪除快，無(wú)需連續(xù)空間；缺點(diǎn)：隨機(jī)訪問(wèn)慢，有額外指針開(kāi)銷。2.“上溢”指棧滿時(shí)再入棧；“下溢”指?？諘r(shí)再出棧。3.鄰接矩陣：存儲(chǔ)簡(jiǎn)單，易判斷兩頂點(diǎn)關(guān)系，但空間浪費(fèi)大。鄰接表：節(jié)省空間，適合稀疏圖，但查找邊效率低。4.冒泡排序基本思想是比較相鄰元素，若逆序則交換，每趟將最大（?。┰匾频侥┪?。五、討論題1.順序存儲(chǔ)適合隨機(jī)訪問(wèn)多、數(shù)據(jù)量穩(wěn)定場(chǎng)景；鏈?zhǔn)酱鎯?chǔ)適合插入刪除多、數(shù)據(jù)量變化大場(chǎng)景。2.棧用