數(shù)據(jù)結(jié)構(gòu)習(xí)題

1、習(xí)題：1、數(shù)據(jù)結(jié)構(gòu)的邏輯結(jié)構(gòu)包括 、樹(shù)型結(jié)構(gòu)和圖型結(jié)構(gòu)三種類(lèi)型， 其中樹(shù)型結(jié)構(gòu)和圖型結(jié)構(gòu)合稱(chēng)為；數(shù)據(jù)結(jié)構(gòu)的存儲(chǔ)結(jié)構(gòu)主要 包括和兩種類(lèi)型。答案 ：線性結(jié)構(gòu)，非線性結(jié)構(gòu)，順序結(jié)構(gòu)，鏈?zhǔn)浇Y(jié)構(gòu)2、下面的程序段中，對(duì)元素 b 賦值的語(yǔ)句頻度是（）。for(k=0;kn;k+)for(m=0;mn;m+) akm=k*m;1)n 2) nlog2n3) n4) n答案 ：（3）3、設(shè)長(zhǎng)度為 n 的順序線性表在任何位置上插入或刪除操作都是等概率的，則插入一個(gè)元素時(shí)平均需要移動(dòng) 個(gè)元素，刪除一個(gè)元素時(shí)平均需要移動(dòng) 個(gè)元素。答案 ：n/2，（n-1）/24、在順序線性表中插入一個(gè)元素時(shí)， 插入位置開(kāi)始后的所有元

2、素均需要 移動(dòng)一個(gè)答案 ：向后5、在順序線性表中刪除一個(gè)元素時(shí)，被刪除元素后的所有元素均需要移動(dòng)一個(gè)位置。答案 ：向前6、在長(zhǎng)度為 n 的順序線性表中刪除第 i 個(gè)元素 （1=inext=q;q-next=p; 2）p-next=q;p=p-next3） q-next=p-next;p-next=q;4）p=p-next;p=next=q;答案 ：（3）8、 設(shè)用一維數(shù)組sm表示棧的存儲(chǔ)空間，用top指向當(dāng)前棧頂元素（其初始值為-1），則進(jìn)行出棧時(shí)的操作序列是（）。1）x=stop ；2）top=top+1 ； x=stop ；3）top=top-1 ；x=stop；4）x=stop ；top

3、=top-1 ；答案 ：（4）9、設(shè)指針 p 指向雙向鏈表中的結(jié)點(diǎn) 結(jié)點(diǎn) X 的操作為（）。A，指針s指向被插入的結(jié)點(diǎn) X，則在結(jié)點(diǎn)A之后插入p-rlink=s ；s-llink=p ； p-rlink-llink=s ；s-rlink=p-rlink ；s-llink=p ；s-rlink=p-rlink；p-rlink=s ；p-rlink-llink=s ；p-rlink=s ；p-rlink-llink=s；s-llink=p ；s-rlink-p-rlink ；s-llink=p ；s-rlink=p-rlink；p-rlink-llink=s ； p-rlink=s ；答案：（ 4

4、 ）10、指針 p 指向雙向鏈表中的結(jié)點(diǎn)A，則刪除結(jié)點(diǎn)A 的操作是（）。 p-llink-rlink=p-rlink ； p-rlink-llink=p-llink ； p-rlink-llink=p-rlink ； p-llink-llink=p-llink ；(3) p-llink-rlink=p_llink;p-rlink-llink=p_rlink;(4) p-rlink-rlink=p-rlink;p-rlink-rlink=p-rlink;答案：(1)11、 假設(shè)用一維數(shù)組sm來(lái)存儲(chǔ)順序棧，指針top指向當(dāng)前棧頂?shù)奈恢谩t當(dāng)棧為空時(shí)滿(mǎn)足 的條件是 ;當(dāng)棧為滿(mǎn)時(shí)滿(mǎn)足的條件是 。答案:

5、top=0， top=m12、 C語(yǔ)言環(huán)境中定義一個(gè)二維數(shù)組A1010,以按行優(yōu)先的順序存儲(chǔ)在內(nèi)存的一段連續(xù)的存儲(chǔ)單元中，存儲(chǔ)首地址是100，每個(gè)元素的長(zhǎng)度是8個(gè)字節(jié)，請(qǐng)問(wèn)元素 A59的起始地址是()。A)572 B )580 C )564 D )588答案：(1)13、 對(duì)于一個(gè)具有m個(gè)存儲(chǔ)單元的順序循環(huán)隊(duì)列，設(shè)front為隊(duì)頭指針，rear為隊(duì)尾指針，則該隊(duì)列中隊(duì)列兀素的個(gè)數(shù)計(jì)算公式為()。 rear-front front-rear(rear-front)%m(rear-front+m)%m答案：(4)14、一棵深度為k的滿(mǎn)二叉樹(shù)的結(jié)點(diǎn)總數(shù)為;一棵深度為k的完全二叉樹(shù)的結(jié)點(diǎn)總數(shù)最少有 個(gè)

6、，最多有 個(gè)。答案:2k-1，2k-1，2k-115、一棵完全二叉樹(shù)有100個(gè)結(jié)點(diǎn)，其中度為 2的結(jié)點(diǎn)的個(gè)數(shù)是( )。1) 502) 473) 484) 49答案：(4)求解：n0=n2+1, n=nO+n 1+ n2 - n=2n2+n1+1, 根據(jù)性質(zhì) 5，n仁1。n2=(100-2)/2=4916、連通具有n個(gè)頂點(diǎn)的無(wú)向圖至少需要()條邊。nn+1n/2n-1答案：(4)0 10 00 0 5 0 心17、稀疏矩陣A= $貝V A的三元組表為0 0 0 06 0 2 0J答案：(1,2,1 ) ,(2,3,5),(4,1,6),(4,3,2)18、一棵高度為h的二叉樹(shù)最多含有個(gè)結(jié)點(diǎn)。答案

7、:2h-119、設(shè)有向圖G中的頂點(diǎn)數(shù)為n,最多有 條邊。答案：n(n-1)20、設(shè)有一個(gè)空棧，現(xiàn)有輸入序列5、4、3、2、1，經(jīng)過(guò) push、pop、push、push、pop、pop、push、push、pop、pop 后，輸出序歹U為 。答案：5341221、已知關(guān)鍵字序列(49, 36, 61, 26, 59, 19, 52, 85),構(gòu)造一棵二叉排序樹(shù)，計(jì)算該樹(shù)在等概率下查找成功的平均查找長(zhǎng)度(ASL)等于。答案：22/822、 單鏈表中從任何結(jié)點(diǎn)出發(fā)均可訪問(wèn)鏈表中的所有結(jié)點(diǎn)。()答案：錯(cuò)，循環(huán)鏈表從任何結(jié)點(diǎn)出發(fā)均可訪問(wèn)鏈表中的所有結(jié)點(diǎn)。23、 帶頭結(jié)點(diǎn)的單鏈表 head為空的判定條件

8、是 head=NULL（）答案：錯(cuò)，head-next=NULL24、 二叉樹(shù)用二叉鏈表存儲(chǔ)時(shí)，非空鏈域數(shù)多于空鏈域數(shù)。（）答案：錯(cuò)，二叉樹(shù)用二叉鏈表存儲(chǔ)時(shí)，非空鏈域數(shù)比空鏈域數(shù)少2個(gè)。問(wèn)答題：1把下列樹(shù)轉(zhuǎn)換成一棵二叉樹(shù)，畫(huà)出這棵二叉樹(shù)，并出該二叉樹(shù)的后序遍歷序列。答案：abcehg，后序遍歷序列：egfhdcba2、某電文中共使用6個(gè)字符：u、v、w、x、y、乙它們的出現(xiàn)頻率依次為0.05,0.2,0.3,0.1, 0.18,0.17,請(qǐng)畫(huà)出相應(yīng)的霍夫曼樹(shù)（要求左子樹(shù)根結(jié)點(diǎn)的權(quán)不大于右子樹(shù)根結(jié)點(diǎn)的權(quán)）,并寫(xiě)出每個(gè)字符的霍夫曼編碼（左子樹(shù)編碼為0,右子樹(shù)編碼為1）。386218 2030321

9、51710答案：u:1100v:01w:10x:1101y:00z:1113.對(duì)關(guān)鍵字序列(35,82,10,33,78,52,60), ( 1)請(qǐng)給出初始建立的大頂堆。(2)使用希爾排序方法進(jìn)行遞增排序，請(qǐng)給出第一次使用d=3進(jìn)行排序結(jié)果。(3)使用快速排序方法進(jìn)行 遞增排序，請(qǐng)給出使用第一個(gè)記錄關(guān)鍵字35作為樞軸的排序結(jié)果。答案：(1) 82,78,60,33,35,52,10(2) 33,78,10,35,82,52,60(3) 33,10,35,82,78,52,604編寫(xiě)算法完成以下任務(wù)：統(tǒng)計(jì)二叉樹(shù)中度為2的結(jié)點(diǎn)個(gè)數(shù)。算法編寫(xiě)要求使用以下二叉樹(shù)的存儲(chǔ)結(jié)構(gòu)：typedef struct

10、 BiTNodeDataType data;struct BiTNode *lchild,*rchild;BiTNode, *BiTree;答案：int Count2(BiTree T)if(T=NULL) retur n 0;if(T-lchild!=NULL & T-rchild!=NULL)x=1;else x=0;returnx+Coun t2(T-lchild)+Cou nt2(T-rchild);5請(qǐng)用Dijkstra算法求下圖中頂點(diǎn)1到其他各頂點(diǎn)的最短路徑長(zhǎng)度和最短路徑(4分)，寫(xiě)答案：21(1,2)3OO(1,2,3)9(1,2,3)7(1,2,5,6,3)4OOOOOOOO11(1,2,5,6,3,4)54(1