學(xué)校專業(yè)課試題及答案

單項(xiàng)選擇題(每題2分,共10題)1.以下哪種是常見(jiàn)的算法結(jié)構(gòu)?A.順序結(jié)構(gòu)B.循環(huán)結(jié)構(gòu)C.選擇結(jié)構(gòu)D.以上都是2.數(shù)據(jù)的基本單位是?A.數(shù)據(jù)元素B.數(shù)據(jù)項(xiàng)C.數(shù)據(jù)對(duì)象D.數(shù)據(jù)庫(kù)3.以下哪個(gè)是面向?qū)ο缶幊痰奶匦?A.封裝B.繼承C.多態(tài)D.以上都是4.棧的操作特性是?A.先進(jìn)先出B.先進(jìn)后出C.隨機(jī)進(jìn)出D.按順序進(jìn)出5.線性表的順序存儲(chǔ)結(jié)構(gòu)優(yōu)點(diǎn)不包括?A.隨機(jī)存取B.存儲(chǔ)密度高C.插入刪除效率高D.邏輯物理地址對(duì)應(yīng)簡(jiǎn)單6.一棵二叉樹(shù)高度為3,其節(jié)點(diǎn)數(shù)最多為?A.7B.8C.15D.167.排序算法中平均時(shí)間復(fù)雜度為O(nlogn)的是?A.冒泡排序B.選擇排序C.快速排序D.插入排序8.哈希表查找的平均時(shí)間復(fù)雜度接近?A.O(1)B.O(n)C.O(logn)D.O(n^2)9.以下哪種圖的存儲(chǔ)結(jié)構(gòu)最適合稠密圖?A.鄰接矩陣B.鄰接表C.十字鏈表D.鄰接多重表10.以下數(shù)據(jù)結(jié)構(gòu)中,不屬于線性結(jié)構(gòu)的是?A.隊(duì)列B.樹(shù)C.棧D.線性表多項(xiàng)選擇題(每題2分,共10題)1.算法的特性包括(）A.有窮性B.確定性C.可行性D.輸入輸出2.以下屬于線性數(shù)據(jù)結(jié)構(gòu)的有()A.數(shù)組B.鏈表C.樹(shù)D.圖3.面向?qū)ο缶幊讨蓄惖某蓡T包括()A.數(shù)據(jù)成員B.成員函數(shù)C.構(gòu)造函數(shù)D.析構(gòu)函數(shù)4.?？梢詰?yīng)用于()A.表達(dá)式求值B.遞歸調(diào)用C.廣度優(yōu)先搜索D.深度優(yōu)先搜索5.隊(duì)列的應(yīng)用場(chǎng)景有()A.打印任務(wù)排隊(duì)B.廣度優(yōu)先搜索C.銀行排隊(duì)系統(tǒng)D.深度優(yōu)先搜索6.二叉樹(shù)遍歷方式有()A.前序遍歷B.中序遍歷C.后序遍歷D.層次遍歷7.以下屬于內(nèi)部排序算法的有()A.歸并排序B.基數(shù)排序C.桶排序D.堆排序8.圖的遍歷方法有()A.深度優(yōu)先搜索B.廣度優(yōu)先搜索C.拓?fù)渑判駾.關(guān)鍵路徑算法9.哈希函數(shù)構(gòu)造方法有()A.直接定址法B.除留余數(shù)法C.平方取中法D.折疊法10.數(shù)據(jù)結(jié)構(gòu)從邏輯上可分為()A.線性結(jié)構(gòu)B.非線性結(jié)構(gòu)C.集合結(jié)構(gòu)D.樹(shù)形結(jié)構(gòu)判斷題(每題2分,共10題)1.算法的時(shí)間復(fù)雜度只與問(wèn)題規(guī)模有關(guān)。()2.線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)比順序存儲(chǔ)結(jié)構(gòu)更節(jié)省空間。()3.構(gòu)造函數(shù)可以有多個(gè)。()4.棧和隊(duì)列都是特殊的線性表。()5.完全二叉樹(shù)一定是滿二叉樹(shù)。()6.快速排序在任何情況下都是最優(yōu)的排序算法。()7.圖的鄰接矩陣表示法空間復(fù)雜度為O(n^2)。()8.哈希表一定不會(huì)產(chǎn)生沖突。()9.樹(shù)的度是指樹(shù)中節(jié)點(diǎn)的最大度數(shù)。()10.遞歸算法一定可以轉(zhuǎn)換為非遞歸算法。(）簡(jiǎn)答題(每題5分,共4題)1.簡(jiǎn)述算法時(shí)間復(fù)雜度的定義。答案:算法時(shí)間復(fù)雜度是指執(zhí)行算法所需要的計(jì)算工作量,它是問(wèn)題規(guī)模n的函數(shù),常用O(f(n))表示,反映算法執(zhí)行時(shí)間隨問(wèn)題規(guī)模增長(zhǎng)的變化趨勢(shì)。2.簡(jiǎn)述線性表順序存儲(chǔ)和鏈?zhǔn)酱鎯?chǔ)的優(yōu)缺點(diǎn)。答案:順序存儲(chǔ)優(yōu)點(diǎn)是隨機(jī)存取快、存儲(chǔ)密度高;缺點(diǎn)是插入刪除效率低、需要連續(xù)空間。鏈?zhǔn)酱鎯?chǔ)優(yōu)點(diǎn)是插入刪除靈活、無(wú)需連續(xù)空間;缺點(diǎn)是不能隨機(jī)存取、存儲(chǔ)密度低。3.簡(jiǎn)述二叉樹(shù)的性質(zhì)。答案:性質(zhì)有:第i層最多有2^(i-1)個(gè)節(jié)點(diǎn);深度為k的二叉樹(shù)最多有2^k-1個(gè)節(jié)點(diǎn);對(duì)任何二叉樹(shù),度為0的節(jié)點(diǎn)比度為2的節(jié)點(diǎn)多1個(gè);完全二叉樹(shù)節(jié)點(diǎn)編號(hào)與存儲(chǔ)對(duì)應(yīng)有規(guī)律。4.簡(jiǎn)述選擇排序的基本思想。答案:在未排序序列中找到最小(大)元素,存放到排序序列的起始位置,然后,再?gòu)氖Ｓ辔磁判蛟刂欣^續(xù)尋找最小(大)元素,然后放到已排序序列的末尾。以此類推,直到所有元素均排序完畢。討論題(每題5分,共4題)1.討論在實(shí)際應(yīng)用中如何選擇合適的數(shù)據(jù)結(jié)構(gòu)。答案:需考慮數(shù)據(jù)操作特點(diǎn),如頻繁插入刪除選鏈表,頻繁隨機(jī)訪問(wèn)選順序表;數(shù)據(jù)元素關(guān)系,線性關(guān)系選線性結(jié)構(gòu),樹(shù)形關(guān)系選樹(shù)結(jié)構(gòu);數(shù)據(jù)規(guī)模和存儲(chǔ)要求等,規(guī)模大且需節(jié)省空間選合適存儲(chǔ)方式。2.討論排序算法在不同場(chǎng)景下的應(yīng)用選擇。答案:數(shù)據(jù)量小且接近有序選插入排序;數(shù)據(jù)量較大選快速排序、歸并排序;對(duì)穩(wěn)定性有要求選歸并排序;數(shù)據(jù)范圍小且需穩(wěn)定選基數(shù)排序;堆排序適合求前k大或小元素。3.討論圖的不同存儲(chǔ)結(jié)構(gòu)的適用場(chǎng)景。答案:鄰接矩陣適合稠密圖,方便判斷邊存在性;鄰接表適合稀疏圖,節(jié)省空間;十字鏈表適合有向圖,方便處理入度出度;鄰接多重表適合無(wú)向圖,避