考研真題：廣東財(cái)經(jīng)大學(xué)2021年數(shù)據(jù)結(jié)構(gòu)考試真題

PAGE考研真題：廣東財(cái)經(jīng)大學(xué)2021年[數(shù)據(jù)結(jié)構(gòu)]考試真題一、單項(xiàng)選擇題（每小題2分，共40分）1.關(guān)于線性表的說法正確的是（）。A.線性表的特點(diǎn)是每個(gè)元素都有一個(gè)前驅(qū)和一個(gè)后繼元素B.線性表是特征相同的n（n≥0）個(gè)元素構(gòu)成的有限序列C.線性表采用順序存儲(chǔ)便于進(jìn)行插入和刪除操作D.線性表采用鏈?zhǔn)酱鎯?chǔ)便于進(jìn)行隨機(jī)查找操作2.表長為n的順序存儲(chǔ)的線性表，當(dāng)在任何位置刪除一個(gè)元素的概率相等時(shí)，刪除一個(gè)元素所需移動(dòng)元素的平均個(gè)數(shù)為（）。A.(n-1)/2B.n/2C.(n+1)/2D.n3.假設(shè)單鏈表結(jié)點(diǎn)結(jié)構(gòu)為（data,next），刪除指針p所指結(jié)點(diǎn)的后繼結(jié)點(diǎn)q的語句序列是（）。A.p->next=q->next;free(q);B.p->next=q;free(q);C.free(q);p->next=q->next;D.free(q);p->next=q;4.設(shè)有一個(gè)遞歸算法如下所示，計(jì)算F(8)需要調(diào)用該遞歸函數(shù)的次數(shù)為（）。intF(intn){if(n<=3)return1;elsereturnF(n-2)+F(n-4)+1;}A.7B.8C.9D.105.若循環(huán)隊(duì)列Q存儲(chǔ)在數(shù)組queue[0..n]中，front是隊(duì)首位置，rear是隊(duì)尾位置（初始rear=front=0），則元素e入隊(duì)的操作是（）。A.Q.queue[Q.rear]=e;Q.rear=(Q.rear+1)%n;B.Q.queue[Q.rear]=e;Q.rear=(Q.rear+1)%(n+1);C.Q.rear=(Q.rear+1)%n;Q.queue[Q.rear]=e;D.Q.rear=(Q.rear+1)%(n+1);Q.queue[Q.rear]=e;6.關(guān)于串的敘述中不正確的是（）。A.串是字符的有限序列B.空串是由空格構(gòu)成的串C.串既可以采用順序存儲(chǔ)，也可以采用鏈?zhǔn)酱鎯?chǔ)D.模式匹配是串的一種重要運(yùn)算7.按照從上至下、由左至右的順序依次編號(hào)，深度為7的完全二叉樹編號(hào)最大的葉結(jié)點(diǎn)編號(hào)是（）。A.63B.64C.126D.1278.已知完全二叉樹的第7層有20個(gè)葉結(jié)點(diǎn)，則該二叉樹最多有（）個(gè)結(jié)點(diǎn)。A.83B.147C.214D.2159.設(shè)F是一個(gè)森林，B是由F變換得到的二叉樹。若F中有n個(gè)非終端，則B中右指針域?yàn)榭盏慕Y(jié)點(diǎn)有（）個(gè)。A.n-1B.nC.n+1D.n+210.由權(quán)值為15,3,5,10的四個(gè)葉結(jié)點(diǎn)構(gòu)成的哈夫曼樹的帶權(quán)路徑長度為（）。A.46B.59C.66D.8811.具有n個(gè)頂點(diǎn)的有向完全圖用鄰接表表示時(shí)，共有（）個(gè)弧結(jié)點(diǎn)。n(n-1)/2B.n(n-1)C.2n(n-1)D.n-112.下面的（）算法適合構(gòu)造一個(gè)稠密圖的最小生成樹。A.Prim算法B.Kruskal算法C.Floy算法D.Dijkstra算法13.如果要求一個(gè)線性表既能較快的查找，又能適應(yīng)動(dòng)態(tài)變化的要求，最好采用（）查找法。A.順序查找B.折半查找C.分塊查找D.哈希查找14.對(duì)50個(gè)記錄的有序表作折半查找，當(dāng)查找失敗時(shí)，至少需要比較（）次關(guān)鍵字。A.4B.5C.6D.715.關(guān)于B-樹和B+樹的敘述不正確的是（）。A.B-樹和B+樹都是平衡的多叉樹B.B-樹和B+樹都可用于文件的索引結(jié)構(gòu)C.B-樹和B+樹都能有效支持順序檢索D.B-樹和B+樹都能有效支持隨機(jī)檢索16.假設(shè)散列表長度為11，散列函數(shù)為H(key)=key%7，沖突處理方法為開放地址法的二次探測再散列。已知表中已有記錄的關(guān)鍵字為32,17,9,27，現(xiàn)要將關(guān)鍵字為45的記錄加入表中，則放入的位置是（）。A.1B.3C.5D.717.從未排序序列中依次取出元素與已排序列（初始時(shí)為空）中的元素進(jìn)行比較，將其放入已排序序列的正確位置上的排序方法稱為（）。A.插入排序B.冒泡排序C.選擇排序D.歸并排序18.快速排序法在（）情況下最有利于發(fā)揮其長處。A.待排序數(shù)據(jù)量大B.數(shù)據(jù)中含有多個(gè)相同的關(guān)鍵字C.數(shù)據(jù)按關(guān)鍵字已基本有序D.數(shù)據(jù)按關(guān)鍵字完全無序19.下列排序算法中，占用輔助空間最多的是（

）。A.希爾排序

B.快速排序

C.堆排序

D.歸并排序20.下列排序方法中，其中（）是穩(wěn)定的。A.堆排序，冒泡排序B.快速排序，堆排序C.選擇排序，歸并排序D.歸并排序，冒泡排序二、填空題（每空2分，共40分）1.從邏輯結(jié)構(gòu)上看，堆棧是操作受限的（）結(jié)構(gòu)，遵循（）存取原則。2.圖的主要存儲(chǔ)結(jié)構(gòu)有四種：（）、（）、十字鏈表和鄰接多重表表示法。3.如果已知二叉樹的（）和（）遍歷序列，可以唯一確定該二叉樹。4.平均查找長度ASL和數(shù)據(jù)元素個(gè)數(shù)無關(guān)的查找方法所使用的數(shù)據(jù)結(jié)構(gòu)是（），在快速排序、歸并排序和堆排序中，穩(wěn)定的排序方法是（）排序。5.假設(shè)記錄R1和R2的關(guān)鍵字相同且R1在R2的前面，如果排序后R1仍在R2的前面則稱排序方法是（）的，一般情況下基于（）關(guān)鍵字比較的排序算法是穩(wěn)定的。6.一棵高度為5的理想平衡樹中，最少含有（）個(gè)結(jié)點(diǎn)，最多含有（）個(gè)結(jié)點(diǎn)。7.通過將樹的（）存儲(chǔ)方式轉(zhuǎn)換為（）存儲(chǔ)方式，可以利用已有的算法解決樹的問題。8.已知一顆完全二叉樹中共有768結(jié)點(diǎn)，則該樹中共有（）個(gè)葉子結(jié)點(diǎn)。已知一棵度為3的樹有2個(gè)度為1的結(jié)點(diǎn)，3個(gè)度為2的結(jié)點(diǎn)，4個(gè)度為3的結(jié)點(diǎn)，則該樹中有（）個(gè)葉子結(jié)點(diǎn)。9.G是一個(gè)非連通無向圖，共有28條邊，則該圖至少有（）個(gè)頂點(diǎn)。在有n個(gè)頂點(diǎn)的有向圖中，若要使任意兩點(diǎn)間可以互相到達(dá)，則至少需要（）條弧。10.對(duì)于一個(gè)具有n個(gè)頂點(diǎn)e條邊的無向圖的鄰接表的表示，則表頭向量大小為（），鄰接表的邊結(jié)點(diǎn)個(gè)數(shù)為（）。三、分析計(jì)算題（每小題10分，共40分）1.設(shè)一棵二叉樹的中序序列是：BDEAFGCKH，后序序列是：EDBGFKHCA。（1）寫出該二叉樹的先序序列。（2）畫出該二叉樹的中序線索二叉樹。（3）將這棵二叉樹轉(zhuǎn)換成樹或森林。2.圖-1所示是帶權(quán)的無向網(wǎng)，圖中頂點(diǎn)的存儲(chǔ)順序?yàn)閳D-2所示，要求：畫出該無向網(wǎng)的鄰接表。按步驟畫出根據(jù)克魯斯卡爾算法構(gòu)造最小生成樹的過程(圖中標(biāo)明對(duì)應(yīng)邊的權(quán)值)。計(jì)算最小生成樹的權(quán)值。3.假設(shè)Bt是元素值為字符的二叉鏈表，其數(shù)據(jù)結(jié)構(gòu)的表示以及test函數(shù)的調(diào)用如圖-3所示，用圖-4所示的二叉鏈表Bt調(diào)用test函數(shù)。（1）簡述test函數(shù)的功能。（2）盡量按屏幕顯示格式寫出運(yùn)行結(jié)果。（3）調(diào)用test的次數(shù)是多少？4.設(shè)待排序數(shù)據(jù)的關(guān)鍵字序列為{49,54,60,75,36,93,27}，回答以下問題：（1）寫出創(chuàng)建大頂堆的一趟初始建堆的過程，要求寫出中間步驟。（2）堆排序采用何種存儲(chǔ)結(jié)構(gòu)？是否穩(wěn)定的排序方法？（3）如果要降序排列全部數(shù)據(jù)，需要?jiǎng)?chuàng)建大頂堆還是小頂堆？四、算法設(shè)計(jì)題（每小題15分，共30分）1.在一個(gè)非遞減有序的線性表中，有數(shù)值相同的元素存在。若存儲(chǔ)方式為單鏈表，設(shè)計(jì)算法去掉數(shù)值相同的元素，使鏈表中不再有重復(fù)元素，要求算法時(shí)間復(fù)雜度為O(N)。例如：算法輸入鏈表為（19，26，26，32，50，62，62，62，89），則輸出為（1