2025年大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)（數(shù)據(jù)結(jié)構(gòu)與算法）試題及答案

（考試時(shí)間：90分鐘滿分100分）班級(jí)______姓名______第I卷（選擇題共40分）每題只有一個(gè)正確答案，請將正確答案填涂在答題卡相應(yīng)位置。（總共8題，每題5分）1.以下關(guān)于線性表的說法，錯(cuò)誤的是（）A.線性表是一種線性結(jié)構(gòu)B.線性表可以采用順序存儲(chǔ)或鏈?zhǔn)酱鎯?chǔ)C.線性表的插入和刪除操作效率在順序存儲(chǔ)和鏈?zhǔn)酱鎯?chǔ)下相同D.線性表的元素具有一對一的邏輯關(guān)系2.若某線性表最常用的操作是存取第i個(gè)元素及其前驅(qū)的值，則采用（）存儲(chǔ)方式最節(jié)省時(shí)間。A.單鏈表B.雙鏈表C.順序表D.單循環(huán)鏈表3.一個(gè)棧的入棧序列是1，2，3，4，5，則棧的不可能的輸出序列是（）A.5，4，3，2，1B.4，5，3，2，1C.4，3，5，1，2D.1，2，3，4，54.深度為5的完全二叉樹的結(jié)點(diǎn)數(shù)不可能是（）A.15B.16C.17D.185.對關(guān)鍵字集合K={60，40，49，23，25，13，95，196，85}，創(chuàng)建平衡二叉排序樹，其根結(jié)點(diǎn)的值為（）A.49B.60C.40D.236.對一組數(shù)據(jù)進(jìn)行排序，若關(guān)鍵字序列基本有序，則采用（）排序算法效率最高。A.快速排序B.冒泡排序C.歸并排序D.選擇排序7.哈希表的平均查找長度與（）有關(guān)。A.哈希函數(shù)B.哈希表的裝填因子C.哈希表的大小D.以上都有關(guān)8.以下關(guān)于圖的說法，正確的是（）A.無向圖的鄰接矩陣一定是對稱矩陣B.有向圖的鄰接矩陣一定是非對稱矩陣C.圖的遍歷只能采用深度優(yōu)先遍歷D.圖的最小生成樹一定是唯一的第II卷（非選擇題共60分）9.（10分）簡述順序表和鏈表的優(yōu)缺點(diǎn)。10.（10分）已知一棵二叉樹的先序遍歷序列為ABDECF，中序遍歷序列為DBEAFC，畫出該二叉樹。11.（15分）用堆排序法對關(guān)鍵字序列{38，27，43，3，9，82，10}進(jìn)行排序，寫出每一趟排序后的結(jié)果。12.（15分）閱讀以下材料：在一個(gè)學(xué)校的學(xué)生信息管理系統(tǒng)中，需要對學(xué)生的成績進(jìn)行管理。學(xué)生成績包括學(xué)號(hào)、姓名、課程成績等信息。要求能夠快速地根據(jù)學(xué)號(hào)查詢學(xué)生成績，并且能夠方便地對學(xué)生成績進(jìn)行修改和添加。請?jiān)O(shè)計(jì)一種合適的數(shù)據(jù)結(jié)構(gòu)來存儲(chǔ)學(xué)生成績信息，并說明理由。同時(shí)，設(shè)計(jì)相應(yīng)的算法來實(shí)現(xiàn)根據(jù)學(xué)號(hào)查詢學(xué)生成績、修改學(xué)生成績和添加學(xué)生成績的功能。13.（10分）簡述圖的深度優(yōu)先遍歷和廣度優(yōu)先遍歷的基本思想，并分析它們的時(shí)間復(fù)雜度。答案：1.C2.C3.C4.A5.B6.B7.D8.A9.順序表優(yōu)點(diǎn)：隨機(jī)存取效率高，存儲(chǔ)密度大；缺點(diǎn)：插入和刪除操作效率低，需要預(yù)先分配存儲(chǔ)空間。鏈表優(yōu)點(diǎn)：插入和刪除操作效率高，不需要預(yù)先分配存儲(chǔ)空間；缺點(diǎn)：隨機(jī)存取效率低，存儲(chǔ)密度小。10.先序遍歷確定根結(jié)點(diǎn)，中序遍歷確定左右子樹。二叉樹為：A/\BC/\\DEF11.初始序列：38，27，43，3，9，82，10第一趟：10，27，43，3，9，82，38第二趟：10，27，3，9，82，43，38第三趟：10，9，3，27，82，43，38第四趟：3，9，10，27，82，43，38第五趟：3，9，10，27，43，82，38第六趟：3，9，10，27，43，82，3812.可以采用哈希表來存儲(chǔ)學(xué)生成績信息。理由是哈希表能通過哈希函數(shù)快速定位元素，滿足快速查詢的要求。算法設(shè)計(jì)：查詢時(shí)，通過學(xué)號(hào)計(jì)算哈希值找到對應(yīng)位置；修改時(shí)，找到位置修改相應(yīng)成績；添加時(shí)，計(jì)算哈希值找到合適位置插入新成績。13.深度優(yōu)先遍歷：從起始頂點(diǎn)開始，沿著一條路徑盡可能深地訪問頂點(diǎn)，直到無法繼續(xù)或已訪問完所有頂點(diǎn)，然后回溯到前一步，繼續(xù)訪問其