數(shù)據(jù)結(jié)構(gòu)期中試卷及答案-全文預(yù)覽
【正文】 需要幾位二進(jìn)制數(shù)，哈夫曼編碼比等長(zhǎng)編碼電文總長(zhǎng)壓縮多少？五、（20分）已知一個(gè)長(zhǎng)度為11的線性表List=(12, 24, 36, 90, 52, 30, 41, 8, 10, 38, 61)，試回答下面問題（1）將線性表元素依次插入一個(gè)空的平衡二叉樹，畫出所得平衡二叉樹，如果假設(shè)每個(gè)元素查找概率相同，則平均查找長(zhǎng)度為多少？（2）如果對(duì)線性表元素排序后進(jìn)行折半查找，畫出折半查找判定樹，假設(shè)每個(gè)元素查找概率相同，計(jì)算平均查找長(zhǎng)度。則該樹中有__12_________個(gè)葉子結(jié)點(diǎn)。minnum=btkey。struct node *lchild,*rchild。createbitree(btrchild)。return。ch)。} bitree。} 。p!=0。p!=0。int lklistsymmetry(lklist *head){sqstack stack。WPL=78 3.(18,5,16,19,21,23)，(5，16，21，19，18，23)h0h1： 鏈地址法：h310L8L1025322768h42532h568h6：125364，廣度：123456，最小生成樹T的邊集為E={(1，4)，(1，3)，(3，5)，(5，6)，(5,6)}四、算法設(shè)計(jì)題。5．設(shè)無向圖G（所右圖所示），要求給出該圖的深度優(yōu)先和廣度優(yōu)先遍歷的序列并給出該圖的最小生成樹。while(i三、應(yīng)用題（30分）1．設(shè)完全二叉樹的順序存儲(chǔ)結(jié)構(gòu)中存儲(chǔ)數(shù)據(jù)ABCDE，要求給出該二叉樹的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)并給出該二叉樹的前序、中序和后序遍歷序列。則該二叉樹的后序遍歷序列為__________。則當(dāng)用二叉鏈表作為其存儲(chǔ)結(jié)構(gòu)時(shí)，該二叉鏈表中共有________個(gè)指針域，__________個(gè)空指針域。(A)3(B)4(C)5(D)1 9．根據(jù)二叉樹的定義可知二叉樹共有（）種不同的形態(tài)。ii1(A)2i(B)2(C)2(D)2i1 5．設(shè)指針變量p指向單鏈表結(jié)點(diǎn)A，則刪除結(jié)點(diǎn)A的后繼結(jié)點(diǎn)B需要的操作為（）。（第3頁，共3頁）第三篇：數(shù)據(jù)結(jié)構(gòu)試卷(一)及答案數(shù)據(jù)結(jié)構(gòu)試卷（一）一、選擇題（20分）1．組成數(shù)據(jù)的基本單位是（）。free(p)。p=headnext。｝，且以帶頭結(jié)點(diǎn)的單鏈表作為存儲(chǔ)結(jié)構(gòu)。while(qnextnext!=p)//qnext不是p的前趨結(jié)點(diǎn)（第2頁，共3頁）q=qnext。該算法的功能是：將開始結(jié)點(diǎn)摘下鏈接到終端結(jié)點(diǎn)之后成為新的終端結(jié)點(diǎn)，而原來的第二個(gè)結(jié)點(diǎn)成為新的開始結(jié)點(diǎn)，返回新鏈表的頭指針。（3）刪除尾元結(jié)點(diǎn)。(3)在表尾插入S結(jié)點(diǎn)。（其中：c1≤d1,c2≤d2,c3≤d3）9.（d1c1+1）（d2c2+1）（d3c3+1）[1?10，2?6，2?8]以行優(yōu)先的順序存儲(chǔ)，設(shè)第一個(gè)元素的首地址是100，每個(gè)元素占3個(gè)存儲(chǔ)長(zhǎng)度的存儲(chǔ)空間，則元素A[5，0，7]的存儲(chǔ)地址為______________。12．O(1)，O(n)；對(duì)于棧只能在_______位置刪除元素；對(duì)于隊(duì)列只能在_______位置插入元素。線性，樹，圖。 ，并且兩串包含的字符相同 ，并且對(duì)應(yīng)位置上的字符相同，每個(gè)元素的長(zhǎng)度為3個(gè)字節(jié)，行下標(biāo)i從1到8，列下標(biāo)j從1到10，從首地址SA開始連續(xù)存放在存儲(chǔ)器內(nèi)，該數(shù)組按行存放時(shí)，元素A[8][5]的起始地址為（C）。snext=p D．pnext=s。i(n)(0A．ni B．ni+l C．ni1 D．i ，已知q結(jié)點(diǎn)是p結(jié)點(diǎn)的前趨結(jié)點(diǎn)，若在q和p之間插入s結(jié)點(diǎn)，則須執(zhí)行（B）。} return count。int sample(link head, int X){ int count=0。}} 答：刪除棧S中所有值為m的數(shù)據(jù)元素，頭指針為head，編寫一個(gè)算法計(jì)算所有數(shù)據(jù)域?yàn)閄的結(jié)點(diǎn)的個(gè)數(shù)（不包括頭結(jié)點(diǎn)）。InitStack(T)。} Stack。}// Demo 答：將單鏈表的第一個(gè)結(jié)點(diǎn)刪除，放到鏈尾。while(Pnext)P=Pnext。amp。}LNode,*LinkList。typedef struct QNode{ QElemType data； struct QNode *next； }QNode, *QueuePtr；typedef struct { QueuePtr front； QueuePtr rear； }LinkQueue；int DeQueue(LinkQueue amp。int stacksize。amp。三、程序填空題（每空3分，共30分），其中L為鏈表頭結(jié)點(diǎn)指針。5． 棧（stack）是限定在表尾進(jìn)行插人或刪除操作的線性表。 二、填空題（每空2分，共20分）1． 線性表、棧和隊(duì)列，串都是__線性_____結(jié)構(gòu)。 12．在一個(gè)鏈隊(duì)列中，假定front和rear分別為頭指針和尾指針，刪除一個(gè)結(jié)點(diǎn)的操作是（A）。A．一個(gè)有限序列，可以為空 B．一個(gè)有限序列，不可以為空 C．一個(gè)無限序列，可以為空 D．一個(gè)無限序列，不可以為空8．若進(jìn)棧序列為1，2，3，4，5，6，且進(jìn)棧和出?？梢源┎暹M(jìn)行，則可能出現(xiàn)的出棧序列為（B）。A．鏈隊(duì)列 3．以下數(shù)據(jù)結(jié)構(gòu)中，（A）是非線性數(shù)據(jù)結(jié)構(gòu)A．樹 B．字符串 C．隊(duì) D．棧4．一個(gè)順序存儲(chǔ)線性表的第一個(gè)元素的存儲(chǔ)地址是90，每個(gè)元素的長(zhǎng)度是2，則第6個(gè)元素的存儲(chǔ)地址是（B）。A．一種數(shù)據(jù)類型 B．?dāng)?shù)據(jù)的存儲(chǔ)結(jié)構(gòu) C．一組性質(zhì)相同的數(shù)據(jù)元素的集合D．相互之間存在一種或多種特定關(guān)系的數(shù)據(jù)元素的集合2．以下與數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)無關(guān)的術(shù)語是（D）。A．必須是連續(xù)的 B．一定是不連續(xù)的 C．部分地址必須連續(xù) D．連續(xù)與否均可以7．線性表是(A)。 （C）。A．順序的存儲(chǔ)結(jié)構(gòu) B．鏈接的存儲(chǔ)結(jié)構(gòu) C．?dāng)?shù)據(jù)元素是一個(gè)字符 D．?dāng)?shù)據(jù)元素可以任意（B）。4． 已知具有n個(gè)元素的一維數(shù)組采用順序
范文總結(jié)相關(guān)推薦
鄂ICP備17016276號(hào)-1