河北工程大學(xué)數(shù)據(jù)結(jié)構(gòu)復(fù)習(xí)題

單項選擇題.數(shù)據(jù)的(B)包括集合、線性、樹和圖4種基本類型A, 存儲結(jié)構(gòu)B.邏輯結(jié)構(gòu)C.基本運算 D.算法描述2.對一個長度為n的順序表，在第i個元素(IWiWn+l)之前插入一個新元素時需向右挪移(B)個元素。A.n-i B.n-i+1 C.n-i-1 D.i3下面程序的時間復(fù)雜度為(C)oFor(i=0;ivm;i++)ForO=0;j<n;j++)A[i][j]=i*j；A. 0(m2)B.0(n2)C.O(n*m)D.O(n+m)4長度為n的線性表采用順序存儲結(jié)構(gòu)，在其第i個位置插入一個新元素的算法時間復(fù)雜度為(C)°若沒說明在第幾個位置插入，則其復(fù)雜度為DA.0(0) B.0(1) C.O(n) D.O(n2)5.數(shù)據(jù)結(jié)構(gòu)就是研究(D九A,數(shù)據(jù)的邏輯結(jié)構(gòu) B.數(shù)據(jù)的存儲結(jié)構(gòu)C.數(shù)據(jù)的邏輯結(jié)構(gòu)和存儲結(jié)構(gòu)D.數(shù)據(jù)的邏輯結(jié)構(gòu)、存儲結(jié)構(gòu)及其數(shù)據(jù)在運算上的實現(xiàn)6下面關(guān)于算法的說法，錯誤的是(D)。A.算法最終必須由計算機程序?qū)崿F(xiàn)B.為解決某問題的算法和為該問題編寫的程序含義是相同的C.算法的可行性是指指令不能有二義性D.以上三種說法都錯誤7線性表L=(al,a2,……an,)下列說法正確的是(D7A.每一個元素都有一個直接前驅(qū)和一個直接后繼B.線性表中至少要有一個元素C.表中所有元素的羅列順序必須是由小到大或者由大到小D.除第一個和最后一個元素外，其余每一個元素都有且僅有一個直接前驅(qū)和一個直接后繼8.下面關(guān)于線性表敘述錯誤的是(B)oA.線性表采用順序存儲，必須占用一段地址連續(xù)的單元B.線性表采用順序存儲，便于進行插入和刪除操作C.線性表采用鏈?zhǔn)酱鎯?，不必占用一段地址連續(xù)的單元D.線性表采用鏈?zhǔn)酱鎯?，便于進行插入和刪除操作9用鏈表表示線性表的優(yōu)點是(C)A.便于隨機存取 B.存儲空間比順序存儲方式少C.便于插入和刪除 D.數(shù)據(jù)元素的存儲順序與邏輯順序相同10若某線性表中最常用的操作是取第i個元素和找第i個元素的前趨元素，則采用(D)存儲方式最節(jié)省時間。A.單鏈表 B.雙鏈表 C.單向循環(huán)D.順序表若隊列采用順序存儲結(jié)構(gòu)，元素的羅列順序(B)A.與元素值的大小有關(guān) B.由元素進入隊列的先后順序決定C.與隊頭指針和隊尾指針的取值有關(guān) D.與作為順序存儲結(jié)構(gòu)的數(shù)組大小有關(guān)三個元素按照的順序入棧，下列哪一個是不合法的出棧序列？ (B)A.ABC B.CAB C.ACB D.BAC13假定一個順序循環(huán)隊列存儲于長度為n的一維數(shù)組中，其隊頭和隊尾指針分別用front和rear表示，則判斷隊滿的條件是(A)A.(rear+1)%n==front B.front+l==rearC.rear==(front-1)%n D.rear-(front+1)%n14假定一個順序循環(huán)隊列的隊頭和隊尾指針分別用front和rear表示，則判隊空的條件是(D)。A.(front+1)%n==rear B.front==rear+lC.front==0 D.front==rear深度為5(假設(shè)空樹的深度為0)的二叉樹至多有(c)結(jié)點。TOC\o"1-5"\h\zA. B. C. D.664一個具有n個頂點的比向徹底圖的邊數(shù)為3（1 63A. B.n（n- C. D.『7（后+序1遍）/盾序列為G4）B/E2FCA,中序遍歷序列（n為ID）GBAECF,則前序（遍n歷1序）列為）0A.ABGDCEF B.ABDGCFE C.BDGC D.ABDGCEF EFA18如果以鏈表作為棧的存儲結(jié)構(gòu)，則出棧操作時（C）處致我荊翔雄樓存滿 刑料也免鎮(zhèn)例契劑19線性表采用鏈?zhǔn)酱鎯r，其地址（DA.必須連續(xù)B部份地址必須連C.必須連續(xù) D連續(xù)與否均20數(shù)據(jù)的?）包括集合、線樹和圖4種基本類A.存儲結(jié)構(gòu) B邏輯結(jié)構(gòu)C.基本運算 D.算法描述21-棵徹底二叉樹上?有15個結(jié)點，其深度是不超過（C）的最大整數(shù)。A. B. C. D.A~C項都不2 3 422若某線性表中最常用的操作是在最后一個元素之后插入一個元素和刪除最后素，則采用（D）存儲方式最節(jié)省運算時間。A.單鏈表 B.雙鏈表C.帶頭結(jié)點的雙循環(huán)鏈表 D.容量足夠大的順序23.二叉樹中第5層上的結(jié)點個數(shù)最多為一TOC\o"1-5"\h\zA. B.18 5C.1 D.36 224.深度為5的二叉樹至多有（D）結(jié)點。A. B.64 32C. D.31 63.將一棵有100個結(jié)點的徹底二叉樹從上到下，從左到右挨次對結(jié)點進行編號，根結(jié)占八、、的編號為1,則編號為49的結(jié)點的左孩子的編號為_A.A.98 B.99C.50 D.48.已知廣義表的表頭為A,表尾為（B,C）,則此廣義表為一BC.((A)BC)填空題1.對于給定的n個元素，可以構(gòu)造出的邏輯結(jié)構(gòu)有（集合）、（線性）、（樹）、（圖）4種。2數(shù)據(jù)元素在計算機中的（ ）方式稱為存儲結(jié)構(gòu)。3線性結(jié)構(gòu)中的元素之間存在（一對一）關(guān)系，樹形結(jié)構(gòu)中元素之間存在（一對多）關(guān)系，圖形結(jié)構(gòu)中的元素之間存在（多對多）關(guān)系。4設(shè)單鏈表的結(jié)點結(jié)構(gòu)為（datajnext）,已知指針p指向單鏈表中X結(jié)點，指針q指向y的新結(jié)點，若將結(jié)點y插入到結(jié)點x之后，則需要執(zhí)行以下兩條語句（q->next=p->next）, （p->next=q）。5數(shù)據(jù)的（邏輯）結(jié)構(gòu)與數(shù)據(jù)元素本身的內(nèi)容和形式無關(guān)。6一個算法的好壞取決于該算法的（時間復(fù)雜度）和（空間復(fù)雜度）。7數(shù)據(jù)結(jié)構(gòu)中評價算法的兩個重要指標(biāo)是（時間復(fù)雜度）、空間復(fù)雜度。8一個循環(huán)隊列存儲于下標(biāo)由0開始且長度為m的一維數(shù)組中，假定隊頭和隊尾指針分別為front和rear,貝U判斷隊空的條件為（（rear+1）%n==front）。貝U判斷隊滿的條件為（front==rear）。9隊列的插入操作是在隊列的（隊尾）進行，刪除操作是在隊列的（隊頭）進行。10堆棧的邏輯特點是（先進后出），隊列的邏輯特點是（先進先出）。11堆棧的邏輯特點是（先進后出），隊列的邏輯特點是（先進先出）。二者的共同點是只允許在它們的(端點)處插入和刪除數(shù)據(jù)元素。12堆棧操作設(shè)輸入元素的順序為1234,5,要在棧的輸出端得到43521,則應(yīng)進行棧的基本運算表示應(yīng)為：Push(SJ),Push(S,2),Push(S,3),Push(S,4),Pop(S),(Pop(S)),(Push(S,5)),Pop(S),Pop(S),Pop(S)o13設(shè)有一個鏈隊，結(jié)點結(jié)構(gòu)為datalnext,front為隊頭指針，rear為隊尾指針，當(dāng)執(zhí)行入隊操作時需執(zhí)行下列語句：malloc(p)；p->data=x;p->next=NULL；()■9();13、一棵二叉樹有67個結(jié)點，這些結(jié)點的度要末是0,要末是2O這棵二叉樹中度數(shù)為2的結(jié)點有個。TOC\o"1-5"\h\z14、一個哈夫曼(Huffman)樹有19個結(jié)點，則其葉結(jié)點的個數(shù)是 。15、一棵深度為6的滿二叉樹有31個分支結(jié)點和32個葉子。16、設(shè)二叉樹結(jié)點的先序序列為ABDECFGH,中序序列為DEBAFCHG,則二叉樹的后序序列是 。.克魯斯卡爾算法的時間復(fù)雜度為( )，適合求( )的最小生成樹。.空串是()，其長度等于( )0.空格串是()，其長度等于()0.兩個字符串相等的充分必要條件是()。21寫出模式串p="abaabcac”的next函數(shù)值序列為()22、設(shè)有一稀疏圖G,則G采用 存儲結(jié)構(gòu)較省空間。、 已知廣義表A=((a,b,c),(d?f))廁運算head(head(tail(A))))=..一棵深度為6的滿二叉樹有 個分支結(jié)點和個葉子。.在對一組記錄(54,38,96,23,15,72,60,45,83)進行直接插入排序時，當(dāng)把第7個記錄60插入到有序表時，為尋覓插入位置至少需比較次。應(yīng)用題.什么是線性結(jié)構(gòu)？線性結(jié)構(gòu)的特點是什么？列舉？.什么是樹形結(jié)構(gòu)？樹形結(jié)構(gòu)的特點是什么？.什么是圖結(jié)構(gòu)？.已知二叉樹的前序ABCDEFGHIJ和中序CDBFEAIHGJ,試構(gòu)造出相應(yīng)的二叉樹。.已知一棵二叉樹的后序遍歷序列為EICBGAHDF,中序遍歷序列為ECIFBAGDH,請畫出這棵二叉樹，7,對于一個有10000個結(jié)點的二叉樹，樹葉最多有多少個？至少有多少個？8寫出某個有向圖的頂點V和弧E的鄰接矩陣。9已知某二叉樹，寫出前序遍歷、中序遍歷和后序遍歷10根據(jù)普里姆算法思想，畫出構(gòu)造該無向帶權(quán)圖最小生成樹的過程。（5分）11的有向帶權(quán)圖，根據(jù)狄克斯特拉算法思想，畫出生成從頂點A到其余各項頂點最短路徑的過程。12已知序歹U｛34,17,6,29,33,11,80,37｝請用冒泡排序的方法從大到小進行排序，并給出詳細過程。13已知序列｛34,17,6,29,33,11,80,37｝請用直接選擇排序的方法從大到小進行排序，并給出詳細過程。.已知一棵二叉樹的中序序列和后序序列分別為：DBGEACHF和DGEBHFCA,則該二叉樹的前序序列是什么？試畫出這棵二叉樹。.給定權(quán)值集合｛15,03,14,02,06,09,16,17｝,構(gòu)造相應(yīng)的哈夫曼樹，并計算它的帶權(quán)路徑長度。.設(shè)一數(shù)組A[5]⑹,A⑼[0]的地址為1100,且每一個元素占2個存儲單元，則這個二維數(shù)組的存儲量為多少？A[4][5]的地址為多少？如按行優(yōu)先順序存儲A⑵[3]的地址為多少？.用序列（46,88,45,39,70,58,101,10,66,34）建立一個排序二叉樹，畫出該樹，并求在等概率情況下查找成功的平均查找長度.按下列要求，寫出相