數(shù)據(jù)結(jié)構(gòu)考研分類復(fù)習(xí)真題第一章答案_跨考網(wǎng)
1.B 2.C 3.1C 3.2B 4.B 5.D 6.C 7.C 8.D 9.D 10.A 11.C 12.D 13.D 14.A 15.C 16.A 17.C
二、判斷題
1.× 2.× 3.× 4.× 5.√ 6.× 7.× 8.√ 9.× 10.× 11.× 12.√ 13.×
三.填空題
1.?dāng)?shù)據(jù)元素?? 數(shù)據(jù)元素間關(guān)系
2.集合? 線性結(jié)構(gòu)?? 樹形結(jié)構(gòu)?? 圖狀結(jié)構(gòu)或網(wǎng)狀結(jié)構(gòu)。
3.?dāng)?shù)據(jù)的組織形式,即數(shù)據(jù)元素之間邏輯關(guān)系的總體。而邏輯關(guān)系是指數(shù)據(jù)元素之間的關(guān)聯(lián)方式或稱“鄰接關(guān)系”。
4.表示(又稱映像)。
5.(1)邏輯特性? (2)在計算機內(nèi)部如何表示和實現(xiàn)? (3)數(shù)學(xué)特性。
??????? 6.算法的時間復(fù)雜度和空間復(fù)雜度。
7.(1)邏輯結(jié)構(gòu)(2)物理結(jié)構(gòu)(3)操作(運算)(4)算法。
8.(1)有窮性? (2)確定性 (3)可行性。
9.(1)n+1? (2)n? (3)n(n+3)/2?? (4)n(n+1)/2。
10.1+(1+2++(1+2+3)+…+(1+2+…+n)=n(n+1)(n+2)/6?? O(n3)
11. log2n
12. nlog2n
13. log2n2
14. (n+3)(n-2)/2
??? 15. O(n)
16. ① (1)1? (2)1? (3)f(m,n-1)? (4)n??? ② 9
17. n(n-1)/2
四.應(yīng)用題
1.?dāng)?shù)據(jù)結(jié)構(gòu)是一門研究在非數(shù)值計算的程序設(shè)計問題中,計算機的操作對象及對象間的關(guān)系和施加于對象的操作等的學(xué)科。
2.四種表示方法
(1)順序存儲方式。數(shù)據(jù)元素順序存放,每個存儲結(jié)點只含一個元素。存儲位置反映數(shù)據(jù)元素間的邏輯關(guān)系。存儲密度大,但有些操作(如插入、刪除)效率較差。
?。?)鏈?zhǔn)酱鎯Ψ绞健C總€存儲結(jié)點除包含數(shù)據(jù)元素信息外還包含一組(至少一個)指針。指針反映數(shù)據(jù)元素間的邏輯關(guān)系。這種方式不要求存儲空間連續(xù),便于動態(tài)操作(如插入、刪除等),但存儲空間開銷大(用于指針),另外不能折半查找等。
?。?)索引存儲方式。除數(shù)據(jù)元素存儲在一地址連續(xù)的內(nèi)存空間外,尚需建立一個索引表,索引表中索引指示存儲結(jié)點的存儲位置(下標(biāo))或存儲區(qū)間端點(下標(biāo)),兼有靜態(tài)和動態(tài)特性。
?。?)散列存儲方式。通過散列函數(shù)和解決沖突的方法,將關(guān)鍵字散列在連續(xù)的有限的地址空間內(nèi),并將散列函數(shù)的值解釋成關(guān)鍵字所在元素的存儲地址,這種存儲方式稱為散列存儲。其特點是存取速度快,只能按關(guān)鍵字隨機存取,不能順序存取,也不能折半存取。
???? 3.?dāng)?shù)據(jù)類型是程序設(shè)計語言中的一個概念,它是一個值的集合和操作的集合。如C語言中的整型、實型、字符型等。整型值的范圍(對具體機器都應(yīng)有整數(shù)范圍),其操作有加、減、乘、除、求余等。實際上數(shù)據(jù)類型是廠家提供給用戶的已實現(xiàn)了的數(shù)據(jù)結(jié)構(gòu)。“抽象數(shù)據(jù)類型(ADT)”指一個數(shù)學(xué)模型及定義在該模型上的一組操作。“抽象”的意義在于數(shù)據(jù)類型的數(shù)學(xué)抽象特性。抽象數(shù)據(jù)類型的定義僅取決于它的邏輯特性,而與其在計算機內(nèi)部如何表示和實現(xiàn)無關(guān)。無論其內(nèi)部結(jié)構(gòu)如何變化,只要它的數(shù)學(xué)特性不變就不影響它的外部使用。抽象數(shù)據(jù)類型和數(shù)據(jù)類型實質(zhì)上是一個概念。此外,抽象數(shù)據(jù)類型的范圍更廣,它已不再局限于機器已定義和實現(xiàn)的數(shù)據(jù)類型,還包括用戶在設(shè)計軟件系統(tǒng)時自行定義的數(shù)據(jù)類型。使用抽象數(shù)據(jù)類型定義的軟件模塊含定義、表示和實現(xiàn)三部分,封裝在一起,對用戶透明(提供接口),而不必了解實現(xiàn)細(xì)節(jié)。抽象數(shù)據(jù)類型的出現(xiàn)使程序設(shè)計不再是“藝術(shù)”,而是向“科學(xué)”邁進(jìn)了一步。
4.(1)數(shù)據(jù)的邏輯結(jié)構(gòu)反映數(shù)據(jù)元素之間的邏輯關(guān)系(即數(shù)據(jù)元素之間的關(guān)聯(lián)方式或“鄰接關(guān)系”),數(shù)據(jù)的存儲結(jié)構(gòu)是數(shù)據(jù)結(jié)構(gòu)在計算機中的表示,包括數(shù)據(jù)元素的表示及其關(guān)系的表示。數(shù)據(jù)的運算是對數(shù)據(jù)定義的一組操作,運算是定義在邏輯結(jié)構(gòu)上的,和存儲結(jié)構(gòu)無關(guān),而運算的實現(xiàn)則是依賴于存儲結(jié)構(gòu)。
?。?)邏輯結(jié)構(gòu)相同但存儲不同,可以是不同的數(shù)據(jù)結(jié)構(gòu)。例如,線性表的邏輯結(jié)構(gòu)屬于線性結(jié)構(gòu),采用順序存儲結(jié)構(gòu)為順序表,而采用鏈?zhǔn)酱鎯Y(jié)構(gòu)稱為線性鏈表。
(3)棧和隊列的邏輯結(jié)構(gòu)相同,其存儲表示也可相同(順序存儲和鏈?zhǔn)酱鎯Γ?,但由于其運算集合不同而成為不同的數(shù)據(jù)結(jié)構(gòu)。
(4)數(shù)據(jù)結(jié)構(gòu)的評價非常復(fù)雜,可以考慮兩個方面,一是所選數(shù)據(jù)結(jié)構(gòu)是否準(zhǔn)確、完整的刻劃了問題的基本特征;二是是否容易實現(xiàn)(如對數(shù)據(jù)分解是否恰當(dāng);邏輯結(jié)構(gòu)的選擇是否適合于運算的功能,是否有利于運算的實現(xiàn);基本運算的選擇是否恰當(dāng)。)
??? 5.評價好的算法有四個方面。一是算法的正確性;二是算法的易讀性;三是算法的健壯性;四是算法的時空效率(運行)。
6.(1)見上面題3
(2)見上面題4
?。?)見上面題3
(4)算法的時間復(fù)雜性是算法輸入規(guī)模的函數(shù)。算法的輸入規(guī)模或問題的規(guī)模是作為該算法輸入的數(shù)據(jù)所含數(shù)據(jù)元素的數(shù)目,或與此數(shù)目有關(guān)的其它參數(shù)。有時考慮算法在最壞情況下的時間復(fù)雜度或平均時間復(fù)雜度。
?。?)算法是對特定問題求解步驟的描述,是指令的有限序列,其中每一條指令表示一個或多個操作。算法具有五個重要特性:有窮性、確定性、可行性、輸入和輸出。
(6)頻度。在分析算法時間復(fù)雜度時,有時需要估算基本操作的原操作,它是執(zhí)行次數(shù)最多的一個操作,該操作重復(fù)執(zhí)行的次數(shù)稱為頻度。
7.集合、線性結(jié)構(gòu)、樹形結(jié)構(gòu)、圖形或網(wǎng)狀結(jié)構(gòu)。
8.邏輯結(jié)構(gòu)、存儲結(jié)構(gòu)、操作(運算)。
9.通常考慮算法所需要的存儲空間量和算法所需要的時間量。后者又涉及到四方面:程序運行時所需輸入的數(shù)據(jù)總量,對源程序進(jìn)行編譯所需時間,計算機執(zhí)行每條指令所需時間和程序中指令重復(fù)執(zhí)行的次數(shù)。
2022考研初復(fù)試已經(jīng)接近尾聲,考研學(xué)子全面進(jìn)入2023屆備考,跨考為23考研的考生準(zhǔn)備了10大課包全程準(zhǔn)備、全年復(fù)習(xí)備考計劃、目標(biāo)院校專業(yè)輔導(dǎo)、全真復(fù)試模擬練習(xí)和全程針對性指導(dǎo);2023考研的小伙伴針也已經(jīng)開始擇校和復(fù)習(xí)了,跨考考研暢學(xué)5.0版本全新升級,無論你在校在家都可以更自如的完成你的考研復(fù)習(xí),暑假集訓(xùn)營帶來了院校專業(yè)初步選擇,明確方向;考研備考全年規(guī)劃,核心知識點入門;個性化制定備考方案,助你贏在起跑線,早出發(fā)一點離成功就更近一點!
點擊右側(cè)咨詢或直接前往了解更多
考研院校專業(yè)選擇和考研復(fù)習(xí)計劃 | |||
2023備考學(xué)習(xí) | 2023線上線下隨時學(xué)習(xí) | 34所自劃線院??佳袕?fù)試分?jǐn)?shù)線匯總 | |
2022考研復(fù)試最全信息整理 | 全國各招生院??佳袕?fù)試分?jǐn)?shù)線匯總 | ||
2023全日制封閉訓(xùn)練 | 全國各招生院??佳姓{(diào)劑信息匯總 | ||
2023考研先知 | 考研考試科目有哪些? | 如何正確看待考研分?jǐn)?shù)線? | |
不同院校相同專業(yè)如何選擇更適合自己的 | 從就業(yè)說考研如何擇專業(yè)? | ||
手把手教你如何選專業(yè)? | 高校研究生教育各學(xué)科門類排行榜 |
相關(guān)推薦
跨考考研課程
班型 | 定向班型 | 開班時間 | 高定班 | 標(biāo)準(zhǔn)班 | 課程介紹 | 咨詢 |
秋季集訓(xùn) | 沖刺班 | 9.10-12.20 | 168000 | 24800起 | 小班面授+專業(yè)課1對1+專業(yè)課定向輔導(dǎo)+協(xié)議加強課程(高定班)+專屬規(guī)劃答疑(高定班)+精細(xì)化答疑+復(fù)試資源(高定班)+復(fù)試課包(高定班)+復(fù)試指導(dǎo)(高定班)+復(fù)試班主任1v1服務(wù)(高定班)+復(fù)試面授密訓(xùn)(高定班)+復(fù)試1v1(高定班) | |
2023集訓(xùn)暢學(xué) | 非定向(政英班/數(shù)政英班) | 每月20日 | 22800起(協(xié)議班) | 13800起 | 先行階在線課程+基礎(chǔ)階在線課程+強化階在線課程+真題階在線課程+沖刺階在線課程+專業(yè)課針對性一對一課程+班主任全程督學(xué)服務(wù)+全程規(guī)劃體系+全程測試體系+全程精細(xì)化答疑+擇校擇專業(yè)能力定位體系+全年關(guān)鍵環(huán)節(jié)指導(dǎo)體系+初試加強課+初試專屬服務(wù)+復(fù)試全科標(biāo)準(zhǔn)班服務(wù) |