2023年數(shù)據(jù)結構專升本模擬題及參考答案

東北農(nóng)業(yè)大學網(wǎng)絡教育學院數(shù)據(jù)結構專升本作業(yè)題作業(yè)題（一）一、單項選擇題1.從邏輯上可以把數(shù)據(jù)結構分為（）兩大類。A．動態(tài)結構、靜態(tài)結構B．順序結構、鏈式結構C．線性結構、非線性結構D．初等結構、構造型結構2.鏈表不具有的特點是（）A．插入、刪除不需要移動元素B．可隨機訪問任一元素C．不必事先估計存儲空間D．所需空間與線性長度成正比3.下面程序段的時間復雜度的量級為（）。For(i=1;i<=n;i++)For(j=1;j<=I;j++)For(k=1;k<=j;k++)X=x+1;A．O(1)B．O(n)C．O(n2)D．O(n3)4.在一個帶頭結點的雙向循環(huán)鏈表中，若要在p所指向的結點之前插入一個新結點，則需要相繼修改（）個指針域的值。A．2B．3C．4D．65、一個順序存儲線性表的第一個元素的存儲地址是90，每個元素的長度是2，則第6個元素的存儲地址是（）。A．98B．100C．102D．1066、鑒定一個棧s（最多元素為m0）為空的條件是（）。A．s-〉top!=0B．s-〉top==0C．s-〉top!=m0D．s-〉top==m07、循環(huán)隊列用數(shù)組A[m]（下標從0到m-1）存放其元素值，已知其頭尾指針分別是front和rear，則當前隊列中的元素個數(shù)是（）。A．（rear-front+m）%mB．rear-front+1C．rear-front-1D．rear-front8、設有兩個串S1與S2，求串S2在S1中初次出現(xiàn)位置的運算稱作（）。A．連接B．求子串C．模式匹配D．判子串9、設串S1='ABCDEFG'，S2='PQRST'，函數(shù)con（x，y）返回x和y串的連接串，subs(s,i,j)返回串S的的從序號i的字符開始的j個字符組成的子串，len(s)返回串S的長度，則con(subs(S1,2,len(S2)),subs(S1,len(S2),2))的結果是（）。A．BCDEF B．BCDEFGC．BCPQRSTD．BCDEFEF10、數(shù)組常用的兩種基本操作是（）。A．建立與查找B．刪除與查找C．插入與索引D．查找與修改二、填空題1.所謂稀疏矩陣指的是________且分布沒有規(guī)律。2.隊列是________的線性表，其運算遵循________的原則。3.空格串是________________________________。4.簡樸選擇排序和起泡排序中比較次數(shù)與序列初態(tài)無關的算法有________。5、設圖G有n個頂點和e條邊，則對用鄰接矩陣表達的圖進行深度或廣度優(yōu)先搜索遍歷時的時間復雜度為，而對用鄰接表表達的圖進行深度或廣度優(yōu)先搜索遍歷時的時間復雜度為，圖的深度或廣度優(yōu)先搜索遍歷時的空間復雜度均為。6、一個圖的表達法是唯一的，而表達法是不唯一的。三、算法設二叉樹采用二叉鏈表結構，試設計一個算法記錄給定二叉樹中的一度結點數(shù)目。四、應用題1、對關鍵字無序序列(36，25，48，12，65，43，20，58)進行直接選擇排序，請寫出每一趟排序的結果。（10分）2、對無向帶權圖，用克魯斯卡爾算法構造最小生成樹。（10分）20A3920A39D4FCB8D4FCB81E651E65G2G23、已知記錄關鍵字集合為（53,17,19,61,98,75,79,63,46,49）規(guī)定散列到地址區(qū)間（100,101,102,103,104,105,106,107,108,109）內，若產(chǎn)生沖突用開型尋址法的線性探測法解決。規(guī)定寫出選用的散列函數(shù)；形成的散列表；計算出查找成功時平均查找長度與查找不成功的平均查找長度。（設等概率情況）4、設被查找文獻有4095個記錄，對每個記錄查找記錄概率相等，若采用順序查找，成功查找平均比較次數(shù)為多少？作業(yè)題（二）、單項選擇題1.有六個元素6，5，4，3，2，1的順序進棧，問下列哪一個不是合法的出棧序列？（）A.543612B.453126C.346521D.2341562.棧和隊都是（）A．順序存儲的線性結構B.鏈式存儲的非線性結構C.限制存取點的線性結構D.限制存取點的非線性結構3、順序查找法適合于存儲結構為（）的線形表。A．散列存儲 B．順序存儲或鏈接存儲C．壓縮存儲 D．索引存儲4、分別以下列序列構造二叉排序樹，與用其它三個序列所構造的結果不同的是()。A．（100，80，90，60，120，110，130） B．（100，120，110，130，80，60，90）C．（100，60，80，90，120，110，130） D．(100，80，60，90，120，130，110)5、折半查找的平均比較次數(shù)為（）。A．n B．n/2C．log2n D．log2(n+1)6、當在一個有序的順序存儲表上查找一個數(shù)據(jù)時，即可用折半查找，也可用順序查找，但前者比后者的查找速度（）A．必然快 B．不一定C．在大部分情況下要快 D．取決于表遞增還是遞減7、已知一有向圖的鄰接表存儲結構如下圖如示。根據(jù)有向圖的深度優(yōu)先遍歷算法，從頂點v1出發(fā)，所得到的頂點序列是（）。A．v1，v2，v3，v5，v4 B．v1，v2，v3，v4，v5C．v1，v3，v4，v5，v2 D．v1，v4，v3，v5，v28、為了方便地對圖狀結構的數(shù)據(jù)進行存取操作，則其中數(shù)據(jù)存儲結構宜采用（）。A．順序存儲 B．鏈式存儲C．索引存儲 D．散列存儲9、在一個具有n個頂點的有向圖中，若所有頂點的出度之和為s，則所有頂點的入度之和為（）。A．s B．s-1C．s+1 D．n10、如圖所示，給出由7個頂點組成的無向圖。從頂點A出發(fā)，對它進行深度優(yōu)先搜索得到的頂點序列是（）。A．AECDBFG B．AGBFDECC．ACEDBGF D．ABDGFEC二、填空題1.設n0為哈夫曼樹的葉子結點數(shù)目，則該哈夫曼樹共有________個結點。2.有數(shù)據(jù)WG={7，19，2，6，32，3，21，10}，則所建Huffman樹的樹高是________，帶權途徑長度WPL為________。3.設一棵完全二叉樹葉子結點數(shù)為k,最后一層結點數(shù)>2，則該二叉樹的高度為________________。4.采用分塊查找時，若線性表中共有625個元素，查找每個元素的概率相同，假設采用順序查找來擬定結點所在的塊時，每塊應分個結點最佳。5、設G為具有N個頂點的無向連通圖，則G中至少有條邊。6、哈夫曼樹（HuffmanTree）又稱。它是n個帶權葉子結點構成的所有二叉樹中，帶權途徑長度WPL。7、樹的先序遍歷過程如下：若樹為空，則進行空操作；若樹非空，則訪問樹的；依次先序遍歷樹的。三、應用題1、給定權值集合{1,4,2,6,9,},構造相應的哈夫曼樹,并計算它的帶權途徑長度。2、對關鍵字序列{10，6，3，2，5，4}，構造一棵平衡二叉（排序）樹并畫圖（規(guī)定畫出建樹過程）。3、設有一個有序文獻，其中各記錄的關鍵字為（1，2，3，4，5，6，7，8，9，10，11，12，13，14，15），當用折半查找算法查找關鍵字為3，8，19時，其比較次數(shù)分別為多少？4、對有五個結點{A,B,C,D,E}的圖的鄰接矩陣，（1）．畫出邏輯圖；（2）．畫出圖的十字鏈表存儲；（3）．基于鄰接矩陣寫出圖的深度、廣度優(yōu)先遍歷序列；（4）．計算圖的關鍵途徑。作業(yè)題（三）一、單項選擇題1．串的長度是指（）A．串中所含不同字母的個數(shù)B．串中所含非空格字符的個數(shù)C．串中所含不同字符的個數(shù)D．串中所含字符的個數(shù)2．設有數(shù)組A[i,j]，數(shù)組的每個元素長度為3字節(jié)，i的值為1到8，j的值為1到10，數(shù)組從內存首地址BA開始順序存放，當用以列為主存放時，元素A[5，8]的存儲首地址為()。A.BA+141B.BA+180C.BA+222D.BA+2253．算法分析的兩個重要方面是（）。A．空間復雜性和時間復雜性B．對的性和簡明性C．可讀性和文檔性D．數(shù)據(jù)復雜性和程序復雜性4．算法分析的目的是（）。A．找出數(shù)據(jù)結構的合理性B．研究算法中的輸入和輸出的關系C．分析算法的效率以求改善D．分析算法的易懂性和文檔性5.下面程序段的時間復雜性的量極為（）。Intfun(intn){inti=1,s=1;While(s<n)S+=++I;ReturnI;}A．O(n/2)B．O(lbn)C．O(n)D．O()6.線性表是（）。A．一個有限序列，可認為空B．一個有限序列，不能為空C．一個無限序列，可認為空D．一個無限序列，不能為空7.帶頭結點的單鏈表L為空的鑒定條件是（）。A．L==NULLB．L-〉next==NULLC．L-〉next==LD．L!=NULL8.在一個長度為n的線性表中，刪除值為x的元素時需要比較元素和移動元素的總次數(shù)為（）。A．（n+1）/2B．n/2C．nD．n+19.一個順序存儲線性表的第一個元素的存儲地址是90，每個元素的長度是2，則第6個元素的存儲地址是（）。A．98B．100C．102D．10610.假如某鏈表中最常用的操作是取第i個結點及其前驅，則采用（）存儲方式最節(jié)省時間。A．單鏈表B．雙向鏈表C．單循環(huán)鏈表D．順序表二、填空題1.高度為2的二叉樹的結點數(shù)至少有________個，高度為3的二叉樹的結點數(shù)至少有________個。2.在順序表（8,11,15,19,25,26,30,33,42,48,50）中，用折半查找關鍵字值20，需做的關鍵字比較次數(shù)為________。3.在有n個頂點的無向圖中，每個頂點的度最大可達________。4．已知廣義表A=（（a，b，c），（d，e，f）），則廣義表運算head（tail（tail（A）））=。5、數(shù)組（Array）是n（n≥1）個的有序組合，數(shù)組中的數(shù)據(jù)是按順序存儲在一塊的存儲單元中。6.采用順序存儲結構表達三元組表（TripleTable），來實現(xiàn)對稀疏矩陣的一種壓縮存儲形式，就稱為，簡稱表。7.運算是矩陣運算中最基本的一項，它是將一個mxn的矩陣變成此外一個nxm的矩陣，同時使本來矩陣中元素的行和列的位置互換而值保持不變。三、應用題1、對于下圖所示的二叉樹，畫出二叉鏈表存儲結構圖。2、請畫出下圖所示的樹所相應的二叉樹。AABCDE3.已知一個無向圖如下圖所示，規(guī)定分別用Prim和Kruskal算法生成最小樹（假設以①為起點，試畫出構造過程）。4.已知完全二叉樹的第8層有8個結點，則其葉子結點是多少？5.畫出如圖所示中樹的二叉樹的表達形式。作業(yè)題（四）一、單項選擇題1.將兩個各有n個元素的有序表歸并成一個有序表，其最少得比較次數(shù)是（）。A．nB．2n-1C．2nD．n-12.一個有n個頂點的無向連通圖，它所包含的連通分量個數(shù)為（）。A．0 B．1C．n D．n+13.數(shù)據(jù)文獻的基本操作中最重要的操作是（）。A．插入 B．刪除C．修改 D．檢索4.對關鍵碼序列28，16，32，12，60，2，5，72快速排序，從小到大一次劃分結果為（）。A．(2,5,12,16)26(60,32,72) B．(5,16,2,12)28(60,32,72)C．(2,16,12,5)28(60,32,72) D．(5,16,2,12)28(32,60,72)5.假如只想得到1000個元素組成的序列中第5個最小元素之前的部分排序的序列，用（）方法最快。A．堆排序 B．快速排序C．插入排序 D．歸并排序6．算法分析的目的是（）。A．找出數(shù)據(jù)結構的合理性B．研究算法中的輸入和輸出的關系C．分析算法的效率以求改善D．分析算法的易懂性和文檔性7.二叉樹的第I層上最多具有結點數(shù)為（）A．2IB．2I-1-1C．2I-1D．2I-18．循環(huán)隊列存儲在數(shù)組A中，長度為m，則入隊時的操作為（）。A.rear=rear+1B.rear=(rear+1)mod(m-1)C.rear=(rear+1)modmD.rear=(rear+1)mod(m+1)9.廣義表滿足Head(A)=Tail(A)，則A為（）。A．（）B．（（））C．（（），（））D．（（），（），（））10.在一棵度為3的樹中，度為3的結點數(shù)為2個，度為2的結點數(shù)為1個，度為1的結點數(shù)為2個，則度為0的結點數(shù)為（）個。A．3B．4C．5D．6二、填空題1.在一個循環(huán)隊列中，隊首指針指向隊首元素的_________。2.數(shù)組中每一個數(shù)據(jù)通常稱為，用下標區(qū)分，其中下標的個數(shù)由數(shù)組的決定。3.一個圖的表達法是唯一的，而表達法是不唯一的。4.在一個10階的B-樹上，每個數(shù)根結點中所含的關鍵字數(shù)目最多允許個，最少允許個5.對關鍵字序列（52，80，63，44，48，91）進行一趟快速排序之后的得到結果為。10.高度為1的平衡二叉樹的結點數(shù)至少有________個，高度為2的平衡二叉樹的結點數(shù)至少有________個。三判斷1.順序存儲結構屬于靜態(tài)結構，鏈式結構屬于動態(tài)結構。（）2.即使對不含相同元素的同一輸入序列進行兩組不同的、合法的入棧和出棧組合操作，所得的輸出序列也一定相同。（）3.帶權無向圖的最小生成樹必是唯一的。（）4.B-樹和B+樹都可用于文獻的索引結構。（）5.在用堆排序算法排序時，假如要進行增序排序，則需要采用"大根堆"。（）四、應用題1.模式串p="abaabcac"的next函數(shù)值序列為多少？2.設二維數(shù)組A[5][6]的每個元素占4個字節(jié)，已知LOC（a0,0）=1000，A共占多少個字節(jié)？A的終端結點a4,5的起始地址為多少？按行和按列優(yōu)先存儲時，a2,5的起始地址分別為多少？3.設a,b,c,d,e五個字符的編碼分別為1,2,3,4,5，并設標記符依以下順序出現(xiàn)：ac,bd,aa,be,ab,ad,cd,bc,ae,ce。規(guī)定用哈希（Hash）方法將它們存入具有10個位置的表中。（1）將上述關鍵字（標記符）構造一個哈希函數(shù)，使得發(fā)生沖突盡也許地少；（2）線性探測再散列法解決沖突。寫出上述各關鍵字在表中位置。4.給定一個關鍵字序列{24，19，32，43，38，6，13，22}，請寫出快速排序第一趟的結果；堆排序時所建的初始堆；歸并排序的全過程。然后回答上述三中排序方法中那一種方法使用的輔助空間最少？在最壞情況下那種方法的時間復雜度最差？作業(yè)題（五）一、單項選擇題1.一組記錄的關鍵碼為（46，79，56，38，40，84），則運用快速排序的方法，以第一個記錄為基準得到的一次劃分結果為（）。A．(38,40,46,56,79,84) B．(40,38,46,79,56,84)C．（40,38,46,56,79,84) D．(40,38,46,84,56,79)2．廣義表A=(a,b,(c,d),(e,(f,g))),則下面式子的值為（）。GetHead(GetTail(GetHead(GetTail(GetTail(A)))))A.(g)B.(d)C.cD.d3．對于有n個結點的二叉樹,其高度為（）A．nlog2nB．log2nC．?log2n?+1D．不擬定4.如圖所示，給出由7個頂點組成的無向圖。從頂點1出發(fā)，對它進行深度優(yōu)先搜索得到的頂點序列是（）。A．1354267 B．1347625C．1534276 D．12476535.采用鄰接表存儲的圖，其深度優(yōu)先遍歷類似于二叉樹的（）。A．中序遍歷 B．先序遍歷C．后序遍歷 D．按層次遍歷6.已知有向圖G=(V,E)，其中V={V1,V2,V3,V4,V5,V6,V7}，E={<V1,V2>,<V1,V3>,<V1,V4>,<V2,V5>,<V3,V5>,<V3,V6>,<V4,V6>,<V5,V7>,<V6,V7>},G的拓撲序列是（）。A．V1,V3,V4,V6,V2,V5,V7 B．V1,V3,V2,V6,V4,V5,V7C．V1,V3,V4,V5,V2,V6,V7 D．V1,V2,V5,V3,V4,V6,V77.順序查找法合用于查找順序存儲或鏈式存儲的線性表，平均比較次數(shù)為（）。在此假定N為線性表中結點數(shù)，且每次查找都是成功的。A．N+1 B．2log2NC．log2N D．N8.下面關于m階B樹說法對的的是（）。①每個結點至少有兩棵非空子樹；②樹中每個結點至多有m一1個關鍵字；③所有葉子在同一層上；④當插入一個數(shù)據(jù)項引起B(yǎng)樹結點分裂后，樹長高一層。A．①②③ B．②③C．②③④ D．③9.已知一個線性表（38，25，74，63，52，48），假定采用h(k)=k%7計算Hash地址進行散列存儲，若運用鏈地址法解決沖突，則在該Hash表上進行查找的平均查找長度為（）。A．1.0 B．7/6C．4/3 D．3/210.在排序算法的實行過程中，使用輔助存儲空間為O（1）的有（）。A．簡樸排序法 B.快速排序法C．歸并排序法 D.基數(shù)排序法二、填空題1.n（n大于1）個結點的各棵樹中，其中深度最大的那棵樹的深度是n，它共有________個葉子結點和________個非葉子結點。2.設一棵后序線索樹的高是50，結點x是樹中的一個結點，其雙親是結點y,y的右子樹高度是60，x是y的左孩子。則擬定x的后繼最多需通過________中間結點（不含后繼及x自身）3.高度為2（第2層為葉子）的3階B-樹中，最多有________個關鍵字。4.分別采用堆排序，快速排序，冒泡排序和歸并排序，對初態(tài)為無序的表，則平均情況下最省時間的是________算法。5.簡樸選擇排序和起泡排序中比較次數(shù)與序列初態(tài)無關的算法有________。6.串的鏈式存儲結構是將存儲區(qū)域提成一系列大小相同的結點,每個結點有兩個域域和域。其中域用于用于存放數(shù)據(jù)，域用于存放下一個結點的指針三．判斷1.順序存儲的線性表可以隨機存取。（）2.即使對不含相同元素的同一輸入序列進行兩組不同的、合法的入棧和出棧組合操作，所得的輸出序列也一定相同。（）3.十字鏈表是無向圖的一種存儲結構。（）4.折半查找方法合用于排列連續(xù)順序文獻的查找。（）5.在執(zhí)行某個排序算法過程中，出現(xiàn)了排序碼朝著最終排序序列位置相反方向移動，則該算法是不穩(wěn)定的。（）四、應用題1.用十字鏈表表達一個有k個非零元素的mxn的稀疏矩陣，則其總的結點數(shù)為多少？2.G=(V,E)是一個帶有權的連通圖,則：（1）．請回答什么是G的最小生成樹；（2）．G為下圖所示,請找出G的所有最小生成樹。3.請分別敘述在一個連續(xù)順序文獻中采用順序查找法，折半查找法和分塊查找法查找一個記錄，該文獻中記錄應當滿足什么條件？4.設待排序文獻之排序碼為（88，33，22，55，99，11，66），采用順序存儲。請用直接選擇排序算法對上述文獻進行排序，用圖示說明排序過程。東北農(nóng)業(yè)大學網(wǎng)絡教育學院數(shù)據(jù)結構專升本作業(yè)題參考答案作業(yè)題一參考答案：一、單項選擇題1、C2、B3、D4、C5、B6、B7、A8、C9、D10、D二、填空題1、非零元很少2、操作受限（或限定僅在表尾進行插入和限定僅在表頭進行刪除操作或限制存取點或特殊），先進先出(或后進后出)3、簡樸選擇排序4、O(n2)，O(e)，O(n)5、鄰陣矩陣，鄰接表三、算法答：intcount=0;voidonechild(Btreet){if(t!=NULL){onechild(t->lchild);onechild(t->rchild);if(t->lchild!=NULL&&(t->rchild!=NULL||t->lchild!=NULL&&t->rchild==NULL)count++;}}四、應用題1、答：2、答：（1） （2）CC11C11C2FGGG3AD3AD3AD11C2FG1C1C4422FG（5） （6）33ADEBEB561C61C441CB543A1CB543AD2FG2FG 3、答：由于地址空間為10，且從100開始，故散列函數(shù)選為H（key）=key%7+100。用線性探測再散列解決沖突，ASLsucc=27/104、答：成功查找平均比較查找長度為：（n+1）/n[log2（n+1）]-1。作業(yè)題二參考答案：一、單項選擇題1、C2、C3、B4、C5、D6、C7、C8、B9、A10、C二、填空題1、2n0-12、6，2613、élog2kù+14、255、N-16、最優(yōu)二叉樹，最小的二叉樹7、根結點，各子樹三、應用題 1、41241263713922此樹的帶權途徑長度WPL=9*1+6*2+4*3+(1+2)*4=452、答：6（1）插入10 (2)插入6 (3)插入3 (4)61010 1010103調整610103調整61066 （5）插入2 （6）插入5 （7）插入4 （8）65365324101063210632調整106325調整106325553、答：當關鍵字為3時，比較次數(shù)為4；當關鍵字為8時，比較次數(shù)為1；當關鍵字為19時，查找不成功；4、答：（2）略（3）深度優(yōu)先遍歷序列：ABCDE廣度優(yōu)先遍歷序列：ABCED（4）關鍵途徑A--B（長100）作業(yè)題三參考答案：一、單項選擇題1、D2、B3、A4、C5、D6、A7、B8、C9、B10、D二、填空題1、2，32、43、n-14、e5、相同類型數(shù)據(jù)，地址連續(xù)6.三元組順序表，三元組7.矩陣轉置三、應用題1、答： 二叉鏈表∧∧∧∧∧∧∧∧∧∧⑧⑨⑦⑥⑤④③②① ∧∧∧∧∧∧∧∧∧∧⑧⑨⑦⑥⑤④③②① (2 2、答：A ACDBCDB EE 3.答：Prim算法構造最小生成樹的環(huán)節(jié)如24題所示，為節(jié)省篇幅，這里僅用Kruskal算法，構造最小生成樹過程如下：（下圖也可選(2,4)代替(3,4),(5,6)代替(1,5)）即：4.答：由完全二叉樹的定義可知，除最后一層外，其他各層的結點是滿的。設該完全二叉樹有d層，則除最后一層外各層的結點個數(shù)分別為：1，2，4，8，16，32，…，即第i層的結點個數(shù)為2i-1。這里第8層有8個結點，顯然第8/層是最后的一層，那么第7層的結點個數(shù)為27-1=64個，其中的4個結點有8個葉子結點，余下的為葉子結點，個數(shù)為64-4=60，所以該完全二叉樹的葉子結點個數(shù)為60+8=68個。5.答：相應的二叉樹形式如圖所示：作業(yè)題四參考答案：一、單項選擇題1.A