數(shù)據(jù)結(jié)構(gòu)試題及答案(1)講解

1、數(shù)據(jù)結(jié)構(gòu)試題一、 單選題1、 在數(shù)據(jù)結(jié)構(gòu)的討論中把數(shù)據(jù)結(jié)構(gòu)從邏輯上分為 （C ） A 內(nèi)部結(jié)構(gòu)與外部結(jié)構(gòu) B 靜態(tài)結(jié)構(gòu)與動態(tài)結(jié)構(gòu) C 線性結(jié)構(gòu)與非線性結(jié)構(gòu) D 緊湊結(jié)構(gòu)與非緊湊結(jié)構(gòu)。2、采用線性鏈表表示一個向量時，要求占用的存儲空間地址（D ） A 必須是連續(xù)的 B 部分地址必須是連續(xù)的 C 一定是不連續(xù)的 D 可連續(xù)可不連續(xù)3、采用順序搜索方法查找長度為n的順序表時，搜索成功的平均搜索長度為（ D ）。 A n B n/2 C (n-1)/2 D (n+1)/24、在一個單鏈表中，若q結(jié)點是p結(jié)點的前驅(qū)結(jié)點，若在q與p之間插入結(jié)點s，則執(zhí)行（ D ）。A slink = plink; pli

2、nk = s; B plink = s; slink = q;C plink = slink; slink = p; D qlink = s; slink = p;5、如果想在4092個數(shù)據(jù)中只需要選擇其中最小的5個，采用（ C ）方法最好。 A 起泡排序 B 堆排序 C 錦標(biāo)賽排序 D 快速排序 6、設(shè)有兩個串t和p，求p在t中首次出現(xiàn)的位置的運算叫做（ B ）。 A 求子串 B 模式匹配 C 串替換 D 串連接7、在數(shù)組A中，每一個數(shù)組元素Aij占用3個存儲字，行下標(biāo)i從1到8，列下標(biāo)j從1到10。所有數(shù)組元素相繼存放于一個連續(xù)的存儲空間中，則存放該數(shù)組至少需要的存儲字數(shù)是（ C ）。A

3、80 B 100 C 240 D 2708、將一個遞歸算法改為對應(yīng)的非遞歸算法時，通常需要使用（ A ）。A 棧 B 隊列 C 循環(huán)隊列 D 優(yōu)先隊列9、一個隊列的進隊列順序是1, 2, 3, 4，則出隊列順序為（ C ）。10、在循環(huán)隊列中用數(shù)組A0.m-1 存放隊列元素，其隊頭和隊尾指針分別為front和rear，則當(dāng)前隊列中的元素個數(shù)是（ D ）。 A ( front - rear + 1) % m B ( rear - front + 1) % mC ( front - rear + m) % m D ( rear - front + m) % m11、一個數(shù)組元素ai與（ A ）的表

4、示等價。A *（a+i） B a+i C *a+i D &a+i 12、若需要利用形參直接訪問實參，則應(yīng)把形參變量說明為（ B ）參數(shù)。A 指針 B 引用 C 值 D 變量13、下面程序段的時間復(fù)雜度為（ C ） for (int i=0;im;i+) for (int j=0;jlink=p;p-link=s;B s-link=p-link;p-link=s;C s-link=p-link;p=s;D p-link=s;s-link=p;19、設(shè)單鏈表中結(jié)點結(jié)構(gòu)為(data,link).已知指針q所指結(jié)點是指針p所指結(jié)點的直接前驅(qū)，若在*q與*p之間插入結(jié)點*s，則應(yīng)執(zhí)行下列哪一個操作（ B

5、 ）A s-link=p-link; p-link=s; B q-link=s; s-link=pC p-link=s-link;s-link=p; D p-link=s; s-link=q;20、設(shè)單鏈表中結(jié)點結(jié)構(gòu)為(data,link).若想摘除結(jié)點*p的直接后繼，則應(yīng)執(zhí)行下列哪一個操作（ A ）A p-link=p-link-link; B p=p-link; p-link=p-link-link;C p-link=p-link; D p=p-link-link;21、設(shè)單循環(huán)鏈表中結(jié)點的結(jié)構(gòu)為（data,link）,且rear是指向非空的帶表頭結(jié)點的單循環(huán)鏈表的尾結(jié)點的指針。若想刪除鏈

6、表第一個結(jié)點，則應(yīng)執(zhí)行下列哪一個操作（ D ）A s=rear; rear=rear-link; delete s; B rear=rear-link; delete rear; C rear=rear-link-link; delete rear; D s=rear-link-link; rear-link-link=s-link; delete s;s為第一個結(jié)點硫22、設(shè)單循環(huán)鏈表中結(jié)點的結(jié)構(gòu)為（data,link）,且first為指向鏈表表頭的指針，current為鏈表當(dāng)前指針，在循環(huán)鏈表中檢測current是否達到鏈表表尾的語句是( D )。A current-link =null

7、B first-link=currentC first=current D current-link=first？23、一個棧的入棧序列為a，b，c，則出棧序列不可能的是( C )。A c,b,a B b,a,c C c,a,b D a,c,b24、棧的數(shù)組表示中，top為棧頂指針，?？盏臈l件是( A )。A top=0 B top=maxSize C top=maxSize D top=-125、棧和隊列的共同特點是( C )。A 都是先進后出 B 都是先進先出C 只允許在端點處插入和刪除 D 沒有共同點26、假定一個順序存儲的循環(huán)隊列的隊頭和隊尾指針分別為f和r ,則判斷隊空的條件為( D

8、 ).A f+1= =r B r+1= =f C f= =0 D f= =r27、當(dāng)利用大小為n 的數(shù)組順序存儲一個隊列時，該隊列的最大長度為（ B ）A n-2 B n-1 C n D n+128、當(dāng)利用大小為n 的數(shù)組順序存儲一個棧時，假定用top= =n 表示?？?，則向這個棧插入一個元素時，首先應(yīng)執(zhí)行（ ）語句修改top指針。A top+; B top-; C top=0; D top;29、設(shè)鏈?zhǔn)綏Ｖ薪Y(jié)點的結(jié)構(gòu)為（data, link）,且top是指向棧頂?shù)闹羔?。若想摘除鏈?zhǔn)綏５臈ｍ斀Y(jié)點，并將被摘除結(jié)點的值保存到x中，則應(yīng)執(zhí)行下列（ A ）操作。A x=top-data; top=to

9、p-link; B top=top-link; x=top-data; C x=top; top=top-link; D x=top-data;30、設(shè)循環(huán)隊列的結(jié)構(gòu)是： const int Maxsize=100; typedef int Data Type; typedef struct Data Type dataMaxsize; Int front, rear; Queue;若有一個Queue類型的隊列Q，試問判斷隊列滿的條件應(yīng)是下列哪一個語句（ D ）A Q.front= = Q.rear; B Q.front - Q.rear= = Maxsize; C Q.front + Q.r

10、ear= = Maxsize; D Q.front= = (Q.rear+1)% Maxsize;31、設(shè)有一個遞歸算法如下：int fact (int n ) if (n=0) return 1;else return n*fact(n-1);下面正確的敘述是（ B ）A 計算fact(n) 需要執(zhí)行n次遞歸 B fact(7)=5040 C 此遞歸算法最多只能計算到fact(8) D 以上結(jié)論都不對32、設(shè)有一個遞歸算法如下int x (int n) if (n遞歸表純表線性表 B 遞歸表線性表再入表純表 C 遞歸表再入表純表線性表 D遞歸表再入表線性表純表37、某二叉樹的前序和后序序列正

11、好相反，則該二叉樹一定是（B）的二叉樹。A 空或只有一個結(jié)點 B 高度等于其結(jié)點數(shù) C 任一結(jié)點無左孩子 D 任一結(jié)點無右孩子38、對于任何一棵二叉樹T，如果其終端結(jié)點數(shù)為n0，度為2的結(jié)點為n2.,則( A )A n0= n2+1 B n2= n0+1 C n0= 2n2+1 D n2=2n0+1 39、 由權(quán)值分別為11，8，6，2，5的葉子結(jié)點生成一棵哈夫曼樹，它的帶權(quán)路徑長度為（B ）A 24 B 73 C 48 D 5340、已知一個順序存儲的線性表，設(shè)每個結(jié)點需占m個存儲單元，若第一個結(jié)點的地址為da1,則第I 個結(jié)點的地址為（A）。A da1+(I-1)*m B da1+I*m

12、C da1-I*m D da1+(I+1)*m41、34 具有35個結(jié)點的完全二叉樹的深度為( A )A 5 B 6 C 7 D 842、對線性表進行折半搜索時，要求線性表必須（ C ）A 以鏈接方式存儲且結(jié)點按關(guān)鍵碼有序排列 B 以數(shù)組方式存儲 C 以數(shù)組方式存儲且結(jié)點按關(guān)鍵碼有序排列 D以鏈接方式存儲43、順序搜索算法適合于存儲結(jié)構(gòu)為（ B ）的線性表。A 散列存儲 B 順序存儲或鏈接存儲 C 壓縮存儲 D 索引存儲44、采用折半搜索算法搜索長度為n的有序表時，元素的平均搜索長度為（ C ）A O（n2） B O（n log2n） C O（log2n） D O（n）45、對于一個具有n個頂

13、點和e條邊的無向圖，進行拓撲排序時，總的時間為( A )A n B n+1 C n-1 D n+e46、判斷一個有向圖是否存在回路，除了可以利用拓撲排序方法外，還可以利用（C ）。A 求關(guān)鍵路徑的方法 B 求最短路徑的Dijkstra方法 C 深度優(yōu)先遍歷算法 D 廣度優(yōu)先遍歷算法47、在10階B-樹中根結(jié)點所包含的關(guān)鍵碼個數(shù)最多為（C ），最少為( A )A 1 B 2 C 9 D 1048、對包含n 個元素的散列表進行搜索，平均搜索長度為（ C ）A O（log2n） B O（n）C 不直接依賴于n D 上述都不對二、 填空題（）1、數(shù)據(jù)的邏輯結(jié)構(gòu)被分為集合結(jié)構(gòu)、線性結(jié)構(gòu)、樹形結(jié)構(gòu)、圖形結(jié)

14、構(gòu) 四種2、數(shù)據(jù)的存儲結(jié)構(gòu)被分為順序結(jié)構(gòu)、鏈接結(jié)構(gòu)、索引結(jié)構(gòu)、散列結(jié)構(gòu) 四種3、一種抽象數(shù)據(jù)類型包括（數(shù)據(jù) ）和（操作 ）兩個部分。4、 設(shè)有兩個串p和q，求p在q中首次出現(xiàn)的位置的運算稱為（模式匹配） 5、 棧、隊列邏輯上都是（線性存儲）結(jié)構(gòu)。6、 線性結(jié)構(gòu)反映結(jié)點間的邏輯關(guān)系是（一對一）的，圖中的數(shù)據(jù)元素之間的關(guān)系是（多對多）的，樹形結(jié)構(gòu)中數(shù)據(jù)元素間的關(guān)系是（一對多）的。7、棧中存取數(shù)據(jù)的原則（后進先出），隊列中存取數(shù)據(jù)的原則（先進先出）8、串是由（零個或多個）字符組成的序列。（長度為零的串）稱為空串，（由一個或多個空格組成的串）稱為空格串。9、設(shè)目標(biāo)串T=”abccdcdccbaa”,模

15、式P=”cdcc”則第（6）次匹配成功。10、一維數(shù)組的邏輯結(jié)構(gòu)是（線性結(jié)構(gòu)），存儲結(jié)構(gòu)是（順序存儲表示）。對于二維數(shù)組，有（行優(yōu)先順序）和（列優(yōu)先順序）兩種不同的存儲方式，對于一個二維數(shù) 組Amn,若采用按行優(yōu)先存放的方式，則任一數(shù)組元素Aij相對于A00的地址為（ n*i+j）。11、向一個順序棧插入一個元素時，首先使（ 棧頂指針 ）后移一個位置，然后把待插入元素（ 寫 ）到這個位置上。從一個順序棧刪除元素時，需要前移一位（棧頂指針）。12、在一個循環(huán)隊列Q中，判斷隊空的條件為（Q.front= =Q.rear）, 判斷隊滿的條件為（ (Q.rear+1)%MaxSize= =q.fron

16、t ）13、對于一棵具有n個結(jié)點的樹，該樹中所有結(jié)點的度數(shù)之和為（ n-1 ）。14、一棵高度為5的滿二叉樹中的結(jié)點數(shù)為（ 63 ）個，一棵高度為3滿四叉樹中的結(jié)點數(shù)為（ 85 ）個。15、若對一棵二叉樹從0開始進行結(jié)點編號，并按此編號把它順序存儲到一維數(shù)組中，即編號為0的結(jié)點存儲到a0中，其余類推，則ai元素的左子女結(jié)點為（ 2*i+1），右子女結(jié)點為（2*i+2 ），雙親結(jié)點（i=1）為（(i-1)/2 ）.16、在一個最大堆中，堆頂結(jié)點的值是所有結(jié)點中的（最大值），在一個最小堆中，堆頂結(jié)點的值是所有結(jié)點中的（最小值）。17、已知具有n個元素的一維數(shù)組采用順序存儲結(jié)構(gòu)，每個元素占k個存儲單

17、元，第一個元素的地址為LOC(a1)，那么，LOC(ai)= LOC(a1)+(i-1)*k 。18、在霍夫曼編碼中，若編碼長度只允許小于等于4,則除掉已對兩個字符編碼為0和10外，還可以最多對（ 4 ）個字符編碼。19、設(shè)高度為h的空二叉樹的高度為-1，只有一個結(jié)點的二叉樹的高度為0，若設(shè)二叉樹只有度為2上度為0的結(jié)點，則該二叉樹中所含結(jié)點至少有（2h+1）個。20、由一棵二叉樹的前序序列和（中序序列）可唯一確定這棵二叉樹。 21、以折半搜索方法搜索一個線性表時，此線性表必須是（順序）存儲的（有序）表。22、已知完全二叉樹的第8層有8個結(jié)點，則其葉子結(jié)點數(shù)是（68）。若完全二叉樹的第7有10

18、個葉子結(jié)點，則整個二叉樹的結(jié)點數(shù)最多是（235）23、對于折半搜索所對應(yīng)的判定樹，它既是一棵（二叉搜索樹），又是一棵（理想平衡樹）。24、假定對長度n=50的有序表進行折半搜索，則對應(yīng)的判定樹高度為（），判定樹中前層的結(jié)點數(shù)為（），最后一層的結(jié)點數(shù)為（）。25、在一個無向圖中，所有頂點的度數(shù)之和等于所有邊數(shù)的（）倍。在一個具有n個頂點的無向完全圖中，包含有（ n(n-1)/2 ）條邊，在一個具有n個頂點的有向完全圖中，包含有（ n(n-1) ）條邊。26、對于一個具有n個頂點和e條邊的連通圖，其生成樹中的頂點數(shù)和邊數(shù)分別為（n）和（n-1）。27、設(shè)線性表中元素的類型是實型，其首地址為1024

19、，則線性表中第6個元素的存儲位置是(1044)。28、在插入和選擇排序中，若初始數(shù)據(jù)基本正序，則選擇（插入排序），若初始數(shù)據(jù)基本反序，則最好選擇（選擇排序）。29、算法是對特定問題的求解步驟的一種描述，它是（指令）的有限序列，每一條（指令）表示一個或多個操作。30、對于一個具有n個頂點肯e 條邊的無向圖，進行拓樸排序時，總的進間為（n）31、構(gòu)造哈希函數(shù)有三種方法，分別為(平方取中)法、(除留余數(shù))法、(折迭移位)法。32、處理沖突的三種方法，分別為(線性探測)、（ 隨機探測 ）、（ 鏈地址法）。33、對于含有n個頂點和e條邊的無向連通圖，利用普里姆算法產(chǎn)生的最小生成樹，其時間復(fù)雜度為（ （n

20、2） ）、利用克魯斯卡爾算法產(chǎn)生的最小生成樹，其時間復(fù)雜度為（elog2e） ）34、快速排序在平均情況下的時間復(fù)雜度為（nlog2n），在最壞情況下的時間復(fù)雜度為（n2）；快速排序在平均情況下的空間復(fù)雜度為（log2n），在最壞情況下的空間復(fù)雜度為（n）。35、假定一組記錄的排序碼為（，），對其進行歸并排序的過程中，第二趟排序后的結(jié)果是（）36、假定一組記錄的排序碼為（，），對其進行快速排序的第一次劃分的結(jié)果是（）。37、一個結(jié)點的子樹的（個數(shù)）稱為該結(jié)點的度。度為（零）的結(jié)點稱為葉結(jié)點或終端結(jié)點。度不為（零）的結(jié)點稱為分支結(jié)點或非終端結(jié)點。樹中各結(jié)點度的（最大值）稱為樹的度。38、設(shè)Ki=

21、Kj (1=i=n, 1=j=n,ji)且在排序前的序列中Ri領(lǐng)先于Rj (i1)的各棵樹中，高度最小的樹的高度是多少？它有多少個葉結(jié)點？多少個分支結(jié)點？高度最大的樹的高度是多少？它有多少個葉結(jié)點？多少個分支結(jié)點？答案：結(jié)點個數(shù)為n時，高度最小的樹的高度為1，有2層；它有n-1個葉結(jié)點，1個分支結(jié)點；高度最大的樹的高度為n-1,有n層；它有1個葉結(jié)點，n-1個分支結(jié)點。6、 一棵高度為h的滿k叉樹有如下性質(zhì): 第h層上的結(jié)點都是葉結(jié)點, 其余各層上每個結(jié)點都有k棵非空子樹, 如果按層次自頂向下, 同一層自左向右, 順序從1開始對全部結(jié)點進行編號, 試問:(1) 各層的結(jié)點個數(shù)是多少?(2) 編

22、號為i的結(jié)點的父結(jié)點(若存在)的編號是多少?(3) 編號為i的結(jié)點的第m個孩子結(jié)點(若存在)的編號是多少?(4) 編號為i的結(jié)點有右兄弟的條件是什么? 其右兄弟結(jié)點的編號是多少?(5) 若結(jié)點個數(shù)為 n, 則高度h是n 的什么函數(shù)關(guān)系?答案：（1）各層的結(jié)點個數(shù)是ki (i=0,1,2,.,h)（2）編號為i的結(jié)點的父結(jié)點(若存在)的編號是 (i+k-2)/k（3）編號為i的結(jié)點的第m個孩子結(jié)點(若存在)的編號是(i-1)*k+m+1（4）當(dāng)(i-1)%k0時有右兄弟， 右兄弟的編號為 i+1（5）若結(jié)點個數(shù)為 n ，則高度h和n 的關(guān)系為：h=logk(n*(k-1)+1)-1 (n=0時h

23、=-1)9、題目：11、將下面的森林變換成二叉樹（7分）。ACDBFEKJGHIACDBFEKJGHI答案：10、將算術(shù)表達式 (a+b)+c*(d+e)+f)*(g+h) 轉(zhuǎn)化為二叉樹。（7分）*+f+*+cbahgde答案：12、 將給定的圖簡化為最小的生成樹，要求從頂點1出發(fā)。（7分）13254768515310122796 答案: 1325476515362713、某子系統(tǒng)在通信聯(lián)絡(luò)中只可能出現(xiàn)8種字符，其出現(xiàn)的概率分別為0.05，0.29，0.07，0.08，0.14，0.23，0.03，0.11試設(shè)計赫夫曼編碼。答案： 為方便起見，設(shè)各種字符的權(quán)值w=5,29,7,8,14,23,

24、3,11。因為n=8，所以要構(gòu)造的赫夫曼樹共有m=2n-1=2*8-1=15個結(jié)點。生成的赫夫曼樹為下圖所示：23115329147800000001111111赫夫曼編碼為：概率為0.23的字符編碼為：00概率為0.11的字符編碼為：010概率為0.05的字符編碼為：0110概率為0.03的字符編碼為：0111概率為0.29的字符編碼為：10 概率為0.14的字符編碼為：110 概率為0.07的字符編碼為：1110 概率為0.08的字符編碼為：111114、已知一棵二叉樹的前序遍歷的結(jié)果是ABECDFGHIJ, 中序遍歷的結(jié)果是EBCDAFHIGJ, 試畫出這棵二叉樹，并給出這棵二叉樹的后序遍歷序列。答案：根據(jù)前序序列和中序序列能得到唯一的二叉樹，所得二叉樹如圖：ABFGECDHJI、 這棵二叉樹的后序遍歷序列為：EDCBIHJGFA15、在結(jié)點個數(shù)為n(n1)的各棵樹中，高度最小的樹的高度是多少？它有多少個葉結(jié)點？多少個分支結(jié)點？高度最大的樹的高度是多少？它有多少個葉結(jié)點？多少個分支結(jié)點？答案：結(jié)點個數(shù)為n時，高度最小的樹的高度為1，有2層；它有n-1個葉結(jié)點，1個分支結(jié)點；高度最大的樹的高度為n-1,有n層；它有1個葉結(jié)點，n-1個分支結(jié)點。16、 對于一個高度為h的AVL樹，其最少結(jié)點數(shù)是多少？反之，對于一個