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