2020年肇慶學(xué)院本科插班生考試大綱

PAGE3PAGE2020年肇慶學(xué)院本科插班生考試大綱（校考專業(yè)課：數(shù)據(jù)結(jié)構(gòu)）Ⅰ考試性質(zhì)普通高等學(xué)校本科插班生（又稱專插本）招生考試是由?？飘厴I(yè)生參加的選拔性考試。高等學(xué)校根據(jù)考生的成績，按照已確定的招生計(jì)劃，德、智、體全面衡量，擇優(yōu)錄取。因此，本科插班生考試應(yīng)有較高信度、效度、必要的區(qū)分度和適當(dāng)?shù)碾y度。Ⅱ考試內(nèi)容及要求一、考試基本要求主要測試考生對(duì)數(shù)據(jù)結(jié)構(gòu)各項(xiàng)內(nèi)容的掌握程度。要求考生熟悉計(jì)算機(jī)處理數(shù)據(jù)的基本方法，掌握計(jì)算機(jī)加工的數(shù)據(jù)結(jié)構(gòu)的特性，熟悉為實(shí)際應(yīng)用涉及的數(shù)據(jù)選擇適當(dāng)?shù)倪壿嫿Y(jié)構(gòu)、存儲(chǔ)結(jié)構(gòu)及其相應(yīng)的算法，并掌握算法的時(shí)間分析和空間分析技術(shù)?？荚囍邢嚓P(guān)算法要求用類C語言描述。二、考試主要知識(shí)點(diǎn)1．?dāng)?shù)據(jù)結(jié)構(gòu)的基本概念數(shù)據(jù)數(shù)據(jù)元素?cái)?shù)據(jù)項(xiàng)數(shù)據(jù)對(duì)象數(shù)據(jù)結(jié)構(gòu)邏輯結(jié)構(gòu)存儲(chǔ)結(jié)構(gòu)數(shù)據(jù)類型算法算法的描述和算法分析算法描述方法算法效率的判斷標(biāo)準(zhǔn)算法的時(shí)間復(fù)雜度、空間復(fù)雜度計(jì)算2．線性表線性表、單鏈表、循環(huán)鏈表和雙向鏈表的邏輯結(jié)構(gòu)；線性表的存儲(chǔ)結(jié)構(gòu)及定義其上的基本運(yùn)算的實(shí)現(xiàn)；線性表的應(yīng)用。3．堆棧和隊(duì)列堆棧和隊(duì)列的邏輯結(jié)構(gòu)；堆棧和隊(duì)列的存儲(chǔ)結(jié)構(gòu)；堆棧和隊(duì)列的基本運(yùn)算的實(shí)現(xiàn)；堆棧和隊(duì)列的基本應(yīng)用。4．串串的邏輯結(jié)構(gòu)及其存儲(chǔ)結(jié)構(gòu)。5．?dāng)?shù)組數(shù)組、特殊矩陣和稀疏矩陣的概念；三元組表。6．樹和二叉樹樹的基本術(shù)語；樹、森林和二叉樹的邏輯結(jié)構(gòu)；二叉樹的存儲(chǔ)結(jié)構(gòu)；樹或森林與二叉樹的相互轉(zhuǎn)化；樹和二叉樹的遍歷算法；哈夫曼樹的構(gòu)造和應(yīng)用。7．圖圖的基本術(shù)語；圖的邏輯結(jié)構(gòu)和存儲(chǔ)結(jié)構(gòu)；圖的遍歷：深度優(yōu)先搜索與廣度優(yōu)先搜索；最小生成樹的構(gòu)造；最短路徑。8．排序排序的基本概念；插入排序（直接、折半、希爾）、交換排序（冒泡、快速）、選擇排序（簡單選擇、堆）等排序算法的基本思想；各排序算法的實(shí)現(xiàn)、時(shí)間復(fù)雜度和穩(wěn)定性。9．查找查找的基本概念；線性表的查找（順序、折半）、樹表的查找（二叉排序樹）、散列表的查找；各種查找的基本思想及算法實(shí)現(xiàn)。Ⅲ考試形式及試卷結(jié)構(gòu)一、考試形式：閉卷，筆試，考試時(shí)間為120分鐘，試卷滿分為100分?？忌褂么痤}卡答題。二、試題題型及賦分：1、選擇題………………約占30%2、判斷題………………約占15%3、填空題………………約占15%4、概念與術(shù)語解釋題…約占10%5、分析簡答及應(yīng)用題…約占20%6、算法設(shè)計(jì)與分析題…約占10%Ⅳ題型示例一、單項(xiàng)選擇題（共30分）1.從邏輯上可以把數(shù)據(jù)結(jié)構(gòu)分為（）兩大類。A．動(dòng)態(tài)結(jié)構(gòu)、靜態(tài)結(jié)構(gòu)B．順序結(jié)構(gòu)、鏈?zhǔn)浇Y(jié)構(gòu)C．線性結(jié)構(gòu)、非線性結(jié)構(gòu)D．初等結(jié)構(gòu)、構(gòu)造型結(jié)構(gòu)2.線性表是（）。A．一個(gè)有限序列，可以為空B．一個(gè)有限序列，不能為空C．一個(gè)無限序列，可以為空D．一個(gè)無限序列，不能為空二、判斷題（正確的在括號(hào)內(nèi)填√，錯(cuò)誤的填×）（共15分）（）1.算法必須有輸出，但可以沒有輸入。（）2．順序表的插入和刪除操作不需要付出很大的時(shí)間代價(jià)，因?yàn)槊看尾僮髌骄挥薪话氲脑匦枰苿?dòng)。三、填空題（共15分）得分評(píng)卷人1．已知指針p指向單鏈表L中的某結(jié)點(diǎn)，則刪除其后繼結(jié)點(diǎn)的語句序列是：；；。四、概念與術(shù)語解釋（共10分）1.算法的時(shí)間復(fù)雜度2.查找表五、分析簡答及應(yīng)用題（共20分）1.已知權(quán)值W={5,6,2,9,8}，構(gòu)造哈夫曼樹，并求出帶權(quán)路徑長度。六、算法設(shè)計(jì)與分析題（請加適當(dāng)?shù)淖⑨專ü?0分）單鏈表L是一個(gè)遞減有序表，試編寫高效算法，刪除表中值大于min且小于max的結(jié)點(diǎn)，同時(shí)釋放被刪結(jié)點(diǎn)的空間，這里min和max是兩個(gè)給定的參數(shù)。請分析你的算法的時(shí)間復(fù)雜度。Ⅴ參考書目1.《數(shù)據(jù)結(jié)構(gòu):C語