2025年大學(xué)大一（人工智能技術(shù)應(yīng)用）數(shù)據(jù)結(jié)構(gòu)試題及答案

（考試時(shí)間：90分鐘滿分100分）班級(jí)______姓名______第I卷（選擇題共40分）答題要求：每題只有一個(gè)正確答案，請(qǐng)將正確答案的序號(hào)填在括號(hào)內(nèi)。(總共8題，每題5分)1.以下數(shù)據(jù)結(jié)構(gòu)中，屬于非線性結(jié)構(gòu)的是（）A.棧B.隊(duì)列C.二叉樹(shù)D.線性表2.若讓元素1，2，3依次進(jìn)棧，則出棧次序不可能出現(xiàn)（）種情況。A.3，2，1B.2，1，3C.3，1，2D.1，3，23.深度為5的完全二叉樹(shù)的結(jié)點(diǎn)數(shù)不可能是（）A.15B.16C.17D.184.對(duì)線性表進(jìn)行二分查找時(shí)，要求線性表必須（）A.以順序方式存儲(chǔ)B.以鏈?zhǔn)椒绞酱鎯?chǔ)C.以順序方式存儲(chǔ)，且結(jié)點(diǎn)按關(guān)鍵字有序排列D.以鏈?zhǔn)椒绞酱鎯?chǔ)，且結(jié)點(diǎn)按關(guān)鍵字有序排列5.已知一棵二叉樹(shù)的先序遍歷序列為ABDECF，中序遍歷序列為DBEAFC，則后序遍歷序列為（）A.DFEBCAB.DEFBCAC.DFBECAD.DFECBA6.設(shè)有一個(gè)10階的對(duì)稱矩陣A，采用壓縮存儲(chǔ)方式，以行序?yàn)橹鞔鎯?chǔ)，a11為第一元素，其存儲(chǔ)地址為1，每個(gè)元素占一個(gè)地址空間，則a85的地址為（）A.13B.33C.18D.407.下列排序方法中，時(shí)間復(fù)雜度不受數(shù)據(jù)初始狀態(tài)影響，恒為O(n^2)的是（）A.堆排序B.冒泡排序C.快速排序D.直接選擇排序8.哈希表的平均查找長(zhǎng)度取決于（）A.哈希表的長(zhǎng)度B.哈希表的裝填因子C.哈希函數(shù)D.哈希表的設(shè)計(jì)和哈希函數(shù)第II卷（非選擇題共60分）9.（10分）簡(jiǎn)述數(shù)據(jù)結(jié)構(gòu)的定義，并說(shuō)明數(shù)據(jù)結(jié)構(gòu)包含哪三個(gè)方面的內(nèi)容。10.（10分）已知一個(gè)帶頭結(jié)點(diǎn)的單鏈表，其頭指針為head，編寫(xiě)一個(gè)函數(shù)，刪除鏈表中所有值為x的結(jié)點(diǎn)。11.（15分）有如下二叉樹(shù)，畫(huà)出它的中序線索二叉樹(shù)。```A/\BC/\\DEF```12.（15分）閱讀以下材料，回答問(wèn)題。材料：有一個(gè)整數(shù)數(shù)組，要求編寫(xiě)一個(gè)算法，找出數(shù)組中出現(xiàn)次數(shù)超過(guò)一半的元素（即多數(shù)元素）。問(wèn)題：請(qǐng)簡(jiǎn)述一種解決該問(wèn)題的算法思路，并給出代碼實(shí)現(xiàn)。13.（20分）閱讀以下材料，回答問(wèn)題。材料：給定一個(gè)整數(shù)數(shù)組nums，判斷數(shù)組中是否存在重復(fù)元素。如果存在一值在數(shù)組中出現(xiàn)至少兩次，函數(shù)返回true；如果數(shù)組中每個(gè)元素都不相同，則返回false。問(wèn)題：請(qǐng)用多種方法實(shí)現(xiàn)該功能，至少給出兩種不同的算法思路，并分別給出代碼實(shí)現(xiàn)。答案：1.C2.C3.A4.C5.A6.B7.D8.B9.數(shù)據(jù)結(jié)構(gòu)是相互之間存在一種或多種特定關(guān)系的數(shù)據(jù)元素的集合。數(shù)據(jù)結(jié)構(gòu)包含數(shù)據(jù)的邏輯結(jié)構(gòu)、存儲(chǔ)結(jié)構(gòu)和數(shù)據(jù)的運(yùn)算三個(gè)方面的內(nèi)容。邏輯結(jié)構(gòu)是指數(shù)據(jù)元素之間的邏輯關(guān)系；存儲(chǔ)結(jié)構(gòu)是指數(shù)據(jù)結(jié)構(gòu)在計(jì)算機(jī)中的表示；數(shù)據(jù)的運(yùn)算則是對(duì)數(shù)據(jù)元素進(jìn)行的操作。10.voiddeleteX(LinkListhead,intx){LinkListp=head->next,q;while(p!=NULL){if(p->data==x){q=p;p=p->next;head->next=p;free(q);}else{head=p;p=p->next;}}}1  11.首先中序遍歷二叉樹(shù)，然后將遍歷過(guò)程中訪問(wèn)的結(jié)點(diǎn)的左、右指針指向前驅(qū)和后繼結(jié)點(diǎn)。中序遍歷序列：DBEAFC中序線索二叉樹(shù)：```A/\BC/\\DEF\\\BEC\\EF```12.算法思路：可以使用摩爾投票法。遍歷數(shù)組，假設(shè)第一個(gè)元素為多數(shù)元素，設(shè)置一個(gè)計(jì)數(shù)器count為1。然后依次遍歷數(shù)組，若遇到相同元素則計(jì)數(shù)器加1，遇到不同元素則計(jì)數(shù)器減1。當(dāng)計(jì)數(shù)器為0時(shí)，更換假設(shè)的多數(shù)元素，并將計(jì)數(shù)器重新設(shè)為1。遍歷結(jié)束后，假設(shè)的多數(shù)元素即為所求。代碼實(shí)現(xiàn)：```cintmajorityElement(intnums[],intnumsSize){intcount=1;intcandidate=nums[0];for(inti=1;i<numsSize;i++){if(nums[i]==candidate){count++;}else{count--;if(count==0){candidate=nums[i];count=1;}}}returncandidate;}```13.方法一：使用哈希表。遍歷數(shù)組，將每個(gè)元素存入哈希表中，每次存入時(shí)檢查哈希表中是否已存在該元素，如果存在則返回true。遍歷結(jié)束后若未發(fā)現(xiàn)重復(fù)元素則返回false。代碼實(shí)現(xiàn)：```cboolcontainsDuplicate(intnums[],intnumsSize){inthash[100000]={0};for(inti=0;i<numsSize;i++){if(hash[nums[i]]==1){returntrue;}hash[nums[i]]=1;}returnfalse;}```方法二：排序后比較相鄰元素。先對(duì)數(shù)組進(jìn)行排序，然后遍歷數(shù)組比較相鄰元素，若有相等的則返回true。遍歷結(jié)束后若未發(fā)現(xiàn)重復(fù)元素則返回false。代碼實(shí)現(xiàn)：```cboolcontainsDuplicate(intnums[],intnumsSize){for(inti=0;i<numsSize-1;i++){for(int