吉林大學(xué)《數(shù)據(jù)結(jié)構(gòu)》2020-2021學(xué)年期末試卷

吉林大學(xué)2020-2021學(xué)年第一學(xué)期期末試卷《數(shù)據(jù)結(jié)構(gòu)》課程試題注意：所有答題一律寫在答題紙上，否則無(wú)效。一、填空題(每空3分，共30分)1.數(shù)據(jù)結(jié)構(gòu)的研究的內(nèi)容包括：數(shù)據(jù)的,數(shù)據(jù)的及數(shù)據(jù)的。2.當(dāng)線性表很少做插入刪除操作時(shí)，應(yīng)采用存儲(chǔ)結(jié)構(gòu)為好。3.若哈夫曼樹(shù)的葉結(jié)點(diǎn)個(gè)數(shù)為m,則該哈夫曼樹(shù)共有個(gè)結(jié)點(diǎn)。5.對(duì)n個(gè)元素的表做順序查找時(shí)，若查找每個(gè)元素的概率相同，則查找成功的平均查找長(zhǎng)度為。_6.已知一個(gè)圖的鄰接矩陣表示，計(jì)算第i個(gè)結(jié)點(diǎn)的入度的方法是。7.一個(gè)圖的生成樹(shù)包含圖的全部頂點(diǎn)和圖的條邊。1.算法分析的兩個(gè)主要方面是。A.可讀性和文檔性B.空間復(fù)雜性和時(shí)間復(fù)雜性C.正確性和簡(jiǎn)明性D.數(shù)據(jù)復(fù)雜性和程序復(fù)雜性2.數(shù)據(jù)的邏輯結(jié)構(gòu)主要類型中不包括。A.集合B.線性結(jié)構(gòu)C.存儲(chǔ)結(jié)構(gòu)D.圖形結(jié)構(gòu)3.數(shù)組Q[n]用來(lái)表示一個(gè)循環(huán)隊(duì)列，f為當(dāng)前隊(duì)列頭元素的前一位置，r為隊(duì)尾元素的位置，假定隊(duì)列中元素的個(gè)數(shù)小于n,計(jì)算隊(duì)列中元素的公式為。4.在長(zhǎng)度為n的線性順序表中刪除一個(gè)元素(元素刪除概率相等)所需移動(dòng)元素的平均次數(shù)為。5.隊(duì)列結(jié)構(gòu)的元素個(gè)數(shù)是。A.不變的B.可變的C.任意的D.06.設(shè)有100個(gè)元素，用折半查找法進(jìn)行查找時(shí)，最大比較次數(shù)是。7.一個(gè)隊(duì)列的入列序列是1,2,3,4,則隊(duì)列的輸出序列是A、4,3,2,1B、1,2,3,4C、 8.已知某二叉樹(shù)的后序遍歷序列是dabec,中序遍歷序列是debac,它的前序遍歷序列是 9.穩(wěn)定排序是指在排序中，關(guān)鍵字相等的不同記錄間的前后相對(duì)位置。A.保持不變B.一定相反C.不定10.假設(shè)一個(gè)有n個(gè)頂點(diǎn)和e條弧的有向圖用鄰接表表示，則刪除與某個(gè)頂點(diǎn)vi相關(guān)的所有弧的時(shí)間復(fù)雜度是。A.O(n)B.O(e)C.O(n+e)D.O(n*e) 三、問(wèn)答題(每小題10分，共20分)1.什么是算法?算法分析的目的是什么?算法分析主要涉及哪兩個(gè)主要方面的內(nèi)容?2.一棵有n個(gè)結(jié)點(diǎn)的滿二叉樹(shù)，請(qǐng)計(jì)算它的度為0的結(jié)點(diǎn)數(shù)、它的分枝結(jié)點(diǎn)和葉子結(jié)點(diǎn)各為多少?。四、圖表計(jì)算題(每小題15分，共30分)1.以{13,24,37,90,53,12}構(gòu)造二叉平衡樹(shù)，并進(jìn)行中序遍歷。2.假定一個(gè)待散列存儲(chǔ)的線性表為(32,75,63,48,94,25,36,18,70),散列地址空間為[0,1....,10]1、設(shè)數(shù)組a是一個(gè)有n個(gè)結(jié)點(diǎn)的完全二叉樹(shù)的靜態(tài)存儲(chǔ)結(jié)構(gòu)，算法bintree將a轉(zhuǎn)換為相應(yīng)的二叉鏈表存儲(chǔ)結(jié)構(gòu)。試在下劃線處填入適當(dāng)語(yǔ)句，以完善該算法功能。(20分)New(bt);bt.data=a[1];Q[rear]=bt;/*}2、(共20分，每小題4分)某工程的AOE網(wǎng)如下圖所示，圖中孤上的權(quán)值表示所需天數(shù)，請(qǐng)求解：(1)事件V?的最早發(fā)生時(shí)間Ve(5);(2)事件V?的最遲發(fā)生時(shí)間V1(4