本文格式為Word版，下載可任意編輯——數(shù)據(jù)結(jié)構(gòu)模擬題2習題1空格串與空串有區(qū)別?2.串長度如何計算？3.一個字符串中__________________________稱為該串的子串。4.若6行8列的數(shù)組以列序為主序順序存儲,基地址為1000,每個元素占2個存儲單元,則第3行第3列的元素(假定無第0行第0列)的地址是____。5.廣義表(a,((b,()),c),(d,(e)))的深度是_、長度、表頭、表尾。6.廣義表的深度是____、長度。7.tail（head（（a，b），c，（c，d）））的結(jié)果是。8.設(shè)數(shù)組A[1..10,1..8]的基地址為2000,每個元素占2個存儲單元,若以行序為主序順序存儲,則元素A[4,5]的存儲地址為___；若以列序為主序順序存儲,則元素A[4,5]的存儲地址為__。9.數(shù)組A[0:1,0:1,0:1]共有___________元素。10.一個t*t的對稱矩陣，假使以行優(yōu)先的方式壓縮存入內(nèi)存。那么所需存儲

區(qū)的容量應(yīng)當是。11.設(shè)串str1=〞Howdoyoudo〞，str2=〞esshe〞，則strcpy(str1+strlen(str1)/2,str2)

的結(jié)果串是。12.二維數(shù)組M[8][10]，行下標范圍0~7，列下標范圍0~9，M按列優(yōu)先方式存儲，則元素M[7][6]是其中第個元素13.試畫出以下稀疏矩陣以列序為主序的三元組順序表。

14．兩個串相等的充分必要條件是。

15.數(shù)組A中，每個元素A的存儲占3個單元，行下標i從1到8，列下標j

從1到10，從首地址SA開始連續(xù)存放在存儲器內(nèi)，存放該數(shù)組至少需要的單元個數(shù)是（1），若該數(shù)組按行存放時，元素A[8][5]的起始地址是（2），若該數(shù)組按列存放時，元素A[8][5]的起始地址是（３）。16.設(shè)數(shù)組A[0..8,0..5],已知a[2,3]的地址為2000,每個元素占2個存儲單元,若以行序為主序順序存儲,則數(shù)組的首地址為_____。17.稀疏矩陣一般的壓縮存儲方法有兩種，即和18.當需要隨機查找線性表的元素時,宜采用____作存儲結(jié)構(gòu)。19.由____組成的集合是一個數(shù)據(jù)對象。20.數(shù)據(jù)的不可分割的基本單位是____。21.T(n)=10log2n+2000/n+5n2，則該算法的時間間繁雜度為_______________。22.帶有一個頭結(jié)點的單鏈表head為空的條件是。23不帶有頭結(jié)點的單鏈表head為空的條件是。24.單鏈表中，從任何一個結(jié)點都能通過域找到它的后繼。25.設(shè)長度為n的線性表順序存貯,若在它的第i-1和第i個元素之間插入一個元素,共需移動_________個元素(1Next;tail=tail->Next;free(ptr);

free(tail);C．tail=tail->Next->Next;D．ptr=tail->Next->Next;Free(tail);Free(ptr);tail->Next->Next=free(ptr);

ptr->Next;38.判定一個循環(huán)隊列Q（最多元素為m0）為空的條件是_______39.線性表中____________________________稱為表的長度。40.棧中元素的進出原則為_____________________。41.a+b/c-f+e*e的后綴表達式為____。

42.與中綴表達式a+b*c-d等價的前綴表達式是____。43.算法分析的兩個主要方面是和。

44.元素1，2，3，4,入棧順序1，2，3，4，出棧順序1，3，4，2,試畫出空的順序棧和每插入或彈出一個元素之后的順序棧示意圖。45下述算法的功能是什么

LinkList*Demo{(LinkList*L}LinkList*q,*p;{//L是無頭結(jié)點的單鏈表If(L

L=L->next;p=L;While(p->next)p=p->next;

p->next=q;q->next=NULL;}

return(L);}

46.有n(n>0)個結(jié)點的完全二叉樹的深度是____。

47.一棵深度為6的滿二叉樹有___個非終端結(jié)點。

48.樹中結(jié)點A的____________________稱為結(jié)點A的度。49.二叉樹有哪幾種基本形態(tài)?畫圖說明之。

50.一棵有n個結(jié)點的樹，在把它轉(zhuǎn)換成對應(yīng)的二叉樹之后，該二叉樹根結(jié)點的左子樹上共有個結(jié)點。

51.若某二叉樹中每一結(jié)點都沒有右子樹，則它的中序和遍歷次序一致。52.畫出下圖二叉樹的二叉鏈表存儲結(jié)構(gòu):

53.試將森林F={T1,T2,T3,T4}轉(zhuǎn)換為一棵二叉樹。

54.具有m個葉子結(jié)點的哈夫曼樹共有個結(jié)點。6.給定30個字符組成的電文:

『DDDDDAAABEEAAFCDAACABBCCCBAADD』試為字符A、B、C、D、E、F設(shè)計哈夫曼(Huffman)編碼。(1)畫出相應(yīng)的哈夫曼樹；

(2)分別列出A、B、C、D、E、F的哈夫曼碼；(3)計算該樹的帶權(quán)路徑長度WPL。55.字符集{A、B、C、D、E、F}，概率分別為{0.16、0.25、0.18、0.21、0.14、0.06}

(1)畫出相應(yīng)的哈夫曼樹（給出每一個構(gòu)造的步驟）；(2)分別列出A、B、C、D、E、F的哈夫曼碼；(3)計算該樹的帶權(quán)路徑長度WPL。

56.樹中結(jié)點A的____________________稱為結(jié)點A的度。57.一棵5個結(jié)點的二叉樹，其先序遍歷序列為：A-B-C-D-E，中序遍歷序列為：B-A-D-C-E，那么它的后序遍歷序列為。

58.一棵樹與其轉(zhuǎn)換成相應(yīng)的二叉樹，那么對樹的后序遍歷是對轉(zhuǎn)換成德二叉樹的遍歷。

59.一棵二叉樹度2的結(jié)點數(shù)為7，度1的結(jié)點數(shù)為6。那么它的葉結(jié)點數(shù)是。

71.n(n>0)個結(jié)點二叉樹對應(yīng)的森林最多包含_______________棵非空樹。72.圖的鄰接矩陣:

60.在一棵完全二叉樹的第5層上共有4個葉結(jié)點，該棵完全二叉樹最多有

個結(jié)點。

61.一棵深度為4的二叉樹最多有_____個結(jié)點。

62.試畫出以下二叉樹的中序線索二叉樹存儲結(jié)構(gòu)圖。

63.試將以下樹轉(zhuǎn)成二叉樹的存儲結(jié)構(gòu)圖。

64.已知二叉樹的前序遍歷序列：I,A,B,E,F,G,C,H,D中序遍歷序列：

A,E,F,B,I,G,H,C,D試畫出該二叉樹。

65.___又是一棵滿二叉樹。

A.完全二叉樹B.深度為5有31個結(jié)點的二叉樹C.有15個結(jié)點的完全二叉

樹D.哈夫曼樹

66.在一顆二叉樹中，度為0的結(jié)點個數(shù)為n0，度為2的結(jié)點個數(shù)為n2，則

有n0=_____。

67.深度為k的滿二叉樹有____個分支結(jié)點。

68.n個頂點的帶權(quán)無向連通圖的最小生成樹包含_______條邊。69.假定后序遍歷二叉樹的結(jié)果是A,C,B,

(1)試畫出所有可得到這一結(jié)果的不同形態(tài)的二叉樹；

(2)分別寫出這些二叉樹的中序遍歷序列。

70.高度為h(h>0)的二叉樹最少有________個結(jié)點。

73.有向圖的鄰接表、逆鄰接表:

74.找出下面網(wǎng)絡(luò)的最小生成樹。75.無向完全圖的鄰接矩陣是____矩陣。

76.具有10個頂點的無向圖,邊的總數(shù)最多為_。77具有n個頂點的無向圖最多有條邊78具有n個頂點的無向圖，若采用領(lǐng)接矩陣存儲，則該矩陣含有的元素個數(shù)是79.無向圖的鄰接矩陣是____矩陣。80.具有n個頂點和e條邊的無向圖，若采用領(lǐng)接表存儲，應(yīng)含有n個頭結(jié)點和個表結(jié)點81.具有n個頂點的無向圖至少有條邊才能確保是一個連通圖82．普里姆算法是求圖的83．分別寫出下圖從頂點a出發(fā)按深度優(yōu)先法進行遍歷，

按廣度優(yōu)先法進行遍歷則可能得到的一種頂點序列是

84.對長度為900的表采用分塊(區(qū))查找,最理想的塊長為____。85.各結(jié)點左、右子樹深度之差的絕對值至多為______的二叉樹稱為平衡二叉樹。

86.如下圖的4棵二叉樹中，哪一個是平衡二叉樹A.

B.

C.

D.

101、下面列舉的是常用的排序方法：直接插入排序，二分法插入排序，起泡排序，快速排序，直接選擇排序，堆排序，歸并排序。試問，哪些排序方法是穩(wěn)定的？

102.假定對20個記錄的表作折半查找,

(1)試畫出描述折半查找過程的判定樹；

(2)若每個記錄的查找概率相等,試計算查找成功時的平均查找長度。

87.串中所含字符個數(shù)稱為該串的_______________。

88.對有14個元素的有序表A[1..14]作二分（折半）查找，查找元素A[4]時的被比較元素依次為。89.動態(tài)查找、靜態(tài)查找的定義。

90.設(shè)計冒泡、簡單項選擇擇、二分插入、直接插入、希爾、快速排序算法并對各種算法的穩(wěn)定性、時間繁雜度和空間繁雜度進行分析

91.給出一組關(guān)鍵字給出一組關(guān)鍵字（35,37,56,23,77,52,95,23）建造一個大頂堆(大根)。寫出構(gòu)造的過程。

92.索引查找、塊查找、順序查找、二分查找算法的優(yōu)缺點進行比較，分析每種查找方法的平均查找長度

93.記錄的關(guān)鍵字序列為50，35，75，64，25，2，34，13，22（1）構(gòu)造一顆二叉排序樹，（2）插入記錄18

（3）刪除記錄25后的二叉排序樹，

（4）二叉排序樹中查找關(guān)鍵字為35的記錄需要和那些關(guān)鍵字進行比較，（5）二叉排序樹的查找成功時的平均查找長度ASL。

94.請畫出對數(shù)據(jù)序列：49，38，65，97，76，13，27，20用指定排序算法進行排序的過程。

95.折半查找20個記錄的有序表,若查找失敗,比較關(guān)鍵字的次數(shù)____。96.查找哈希(Hash)表,