山東專升本計(jì)算機(jī)(2024新版大綱新增)-計(jì)算思維(程序設(shè)計(jì))

2024山東專升本計(jì)算機(jī)-大綱新增知識(shí)點(diǎn)

主講人:高老師計(jì)算思維(程序設(shè)計(jì))考綱要求：（一）掌握計(jì)算思維的概念；了解計(jì)算思維在社會(huì)生活中的應(yīng)用。（二）了解計(jì)算機(jī)求解問(wèn)題的基本方法；掌握利用計(jì)算思維解決簡(jiǎn)單計(jì)算問(wèn)題的方法。（三）掌握計(jì)算機(jī)算法的基本知識(shí)；了解典型問(wèn)題求解策略、算法復(fù)雜度分析及對(duì)應(yīng)用程序進(jìn)行時(shí)間優(yōu)化和空間優(yōu)化的實(shí)現(xiàn)方法與思路。（四）掌握計(jì)算機(jī)程序的基本結(jié)構(gòu)（順序結(jié)構(gòu)、分支結(jié)構(gòu)、循環(huán)結(jié)構(gòu)）、程序流程表達(dá)與分析方法（程序流程圖、偽代碼等）；了解面向?qū)ο蟪绦蛟O(shè)計(jì)的思想與方法。2024山東專升本計(jì)算機(jī)-大綱新增計(jì)算思維目錄一、計(jì)算思維概述

二、算法與數(shù)據(jù)結(jié)構(gòu)三、程序設(shè)計(jì)語(yǔ)言四、面向?qū)ο蟪绦蛟O(shè)計(jì)計(jì)算思維一、計(jì)算思維概述1.1

計(jì)算思維概念計(jì)算思維是運(yùn)用計(jì)算機(jī)科學(xué)的基礎(chǔ)概念進(jìn)行問(wèn)題求解、系統(tǒng)設(shè)計(jì)，以及人類(lèi)行為理解等涵蓋計(jì)算機(jī)科學(xué)之廣度的一系列思維活動(dòng)。計(jì)算思維由周以真于2006年3月首次提出。2010年，周以真教授又指出計(jì)算思維是與形式化問(wèn)題及其解決方案相關(guān)的思維過(guò)程，其解決問(wèn)題的表示形式應(yīng)該能有效地被信息處理代理執(zhí)行。計(jì)算思維的本質(zhì)是抽象和自動(dòng)化。就是如何利用計(jì)算機(jī)去求解問(wèn)題，確定合適的抽象；自動(dòng)化是最終目標(biāo)，選擇合適的方法去解釋執(zhí)行該抽象，讓機(jī)器去做計(jì)算的工作。1.2計(jì)算思維在社會(huì)生活中的應(yīng)用決策制定：在個(gè)人生活或商業(yè)環(huán)境中，計(jì)算思維有助于分析信息、評(píng)估選項(xiàng)并做出最佳決策。問(wèn)題解決：計(jì)算思維使人們能夠分解問(wèn)題、識(shí)別模式并提出解決方案。這種思維方式強(qiáng)調(diào)邏輯推理和創(chuàng)造性解決問(wèn)題的能力?？茖W(xué)研究和創(chuàng)新：計(jì)算思維在科學(xué)領(lǐng)域中至關(guān)重要。它幫助科學(xué)家分析數(shù)據(jù)、構(gòu)建模型、測(cè)試假設(shè)，并發(fā)現(xiàn)新的解決方案和創(chuàng)新。技術(shù)和工程領(lǐng)域：計(jì)算思維對(duì)于軟件開(kāi)發(fā)、工程設(shè)計(jì)和技術(shù)創(chuàng)新至關(guān)重要。它涉及編碼、系統(tǒng)設(shè)計(jì)和解決技術(shù)難題的能力。數(shù)據(jù)分析和預(yù)測(cè)：在商業(yè)領(lǐng)域，計(jì)算思維可以幫助分析大量數(shù)據(jù)，發(fā)現(xiàn)趨勢(shì)并做出預(yù)測(cè)。這對(duì)市場(chǎng)營(yíng)銷(xiāo)、銷(xiāo)售預(yù)測(cè)和業(yè)務(wù)決策非常重要。教育和培訓(xùn)：教育界認(rèn)識(shí)到計(jì)算思維對(duì)于學(xué)生的重要性，因此越來(lái)越多的教學(xué)方法側(cè)重于培養(yǎng)學(xué)生的邏輯思維、問(wèn)題解決能力和創(chuàng)造性思維。社會(huì)政策制定：在政府和社會(huì)領(lǐng)域，計(jì)算思維可以幫助分析社會(huì)問(wèn)題、評(píng)估政策效果并制定更有效的政策方案。信息管理和安全：計(jì)算思維對(duì)于管理和保護(hù)信息資產(chǎn)至關(guān)重要。它有助于識(shí)別和解決安全漏洞，確保數(shù)據(jù)和信息的安全性。1.2

計(jì)算思維在社會(huì)生活中的應(yīng)用準(zhǔn)備去旅行時(shí)，提前將所需的衣物、洗漱用品等放入行李箱，這就是一種預(yù)置行為預(yù)置；當(dāng)你使用手機(jī)或電腦瀏覽網(wǎng)頁(yè)時(shí)，瀏覽器會(huì)將已經(jīng)訪問(wèn)過(guò)的網(wǎng)頁(yè)內(nèi)容暫時(shí)存儲(chǔ)在緩存中，以便下次再次訪問(wèn)相同的網(wǎng)頁(yè)時(shí)能夠更快地加載。這就是一個(gè)日常生活中常見(jiàn)的緩存；當(dāng)你在迷宮中迷路時(shí)，你可能會(huì)使用回溯策略來(lái)找到出口；在超市付賬時(shí)，你應(yīng)該選擇哪個(gè)隊(duì)伍排隊(duì)，可以涉及到計(jì)算思維中的“最優(yōu)化”；當(dāng)你對(duì)智能手機(jī)說(shuō)出指令或問(wèn)題時(shí)，比如“設(shè)置提醒我明天早上8點(diǎn)起床”，智能手機(jī)的語(yǔ)音識(shí)別系統(tǒng)會(huì)錄下你的聲音并將其轉(zhuǎn)換成文本。在這個(gè)過(guò)程中，神經(jīng)網(wǎng)絡(luò)可能會(huì)用于語(yǔ)音的識(shí)別和理解；計(jì)算思維的基本特征是概念化，而不是程序化計(jì)算思維不等同于計(jì)算機(jī)編程。像計(jì)算機(jī)科學(xué)家那樣去思維意味著遠(yuǎn)不止能為計(jì)算機(jī)編程，還要求能夠在抽象的多個(gè)層次上思維。是根本的，不是刻板的技能。是一種根本技能，是人為了在現(xiàn)代社會(huì)中發(fā)揮職能所必須掌握的分析和解決問(wèn)題的能力，刻板技能意味著機(jī)械的重復(fù)。是人的，不是計(jì)算機(jī)的思維計(jì)算思維是人類(lèi)求解問(wèn)題的途徑，但決非要使人類(lèi)像計(jì)算機(jī)那樣思考。比如計(jì)算思維使用海量數(shù)據(jù)來(lái)加速計(jì)算，在時(shí)間和空間、處理能力和存儲(chǔ)容量之間進(jìn)行權(quán)衡，人并不需要具備這樣的能力。計(jì)算思維的基本特征是數(shù)學(xué)和工程思維的互補(bǔ)與融合計(jì)算機(jī)科學(xué)本質(zhì)上源自數(shù)學(xué)思維和工程思維，像其它科學(xué)一樣，其基礎(chǔ)源自數(shù)學(xué)學(xué)科，但其實(shí)現(xiàn)過(guò)程又基于工程思維，計(jì)算機(jī)系統(tǒng)的目標(biāo)是創(chuàng)造能與現(xiàn)實(shí)世界互相的系統(tǒng)。是思想，不是人造物計(jì)算思維不只是我們生產(chǎn)的軟硬件以物理形式到處呈現(xiàn)并時(shí)刻觸及我們的生活，更重要的是還體現(xiàn)了人類(lèi)用以接近和求解問(wèn)題，管理日常生活、與他人交流互動(dòng)的計(jì)算思想。1.4

利用計(jì)算思維求解問(wèn)題的一般方法第一步：把實(shí)際的應(yīng)用問(wèn)題轉(zhuǎn)化為數(shù)學(xué)問(wèn)題，建立數(shù)學(xué)模型；第二步：設(shè)計(jì)算法；第三步：將算法編程實(shí)現(xiàn)；

第四步：在計(jì)算機(jī)中運(yùn)行求解前兩步是計(jì)算思維中的抽象，后兩步是計(jì)算思維中的自動(dòng)化。真題解析下列關(guān)于計(jì)算思維的描述，正確的有A.計(jì)算思維是運(yùn)用計(jì)算機(jī)科學(xué)的基礎(chǔ)概念進(jìn)行問(wèn)題求解、系統(tǒng)設(shè)計(jì)以及人類(lèi)行為理解等涵蓋計(jì)算機(jī)科學(xué)之廣度的系列思維活動(dòng)B．計(jì)算思維的本質(zhì)是抽象與自動(dòng)化C．計(jì)算思維是人的思維，不是計(jì)算機(jī)的思維D.計(jì)算思維是分析和解決問(wèn)題的能力，而不是刻板的操作技能例題：1.問(wèn)題解決和系統(tǒng)設(shè)計(jì)涉及哪種思維范式？A.平面思維B.計(jì)算思維C.文學(xué)思維D.視覺(jué)思維答案：B.計(jì)算思維2.計(jì)算思維的核心特征是什么？A.理性與情感的結(jié)合B.創(chuàng)造力和想象力C.抽象化和自動(dòng)化D.實(shí)用主義與理論性的結(jié)合答案：C.抽象化和自動(dòng)化3.計(jì)算思維的特點(diǎn)是什么？A.特定性和固定性B.邏輯性和系統(tǒng)性C.非理性和隨機(jī)性D.實(shí)驗(yàn)性和主觀性答案：B.邏輯性和系統(tǒng)性4.計(jì)算思維是人的思維方式，與計(jì)算機(jī)的思維方式有何區(qū)別？A.無(wú)區(qū)別B.計(jì)算思維和計(jì)算機(jī)思維完全相同C.計(jì)算思維強(qiáng)調(diào)應(yīng)用計(jì)算機(jī)概念和技術(shù)，而不是計(jì)算機(jī)本身的思維D.計(jì)算機(jī)思維更注重人類(lèi)的抽象化能力答案：C.計(jì)算思維強(qiáng)調(diào)應(yīng)用計(jì)算機(jī)概念和技術(shù)，而不是計(jì)算機(jī)本身的思維二、算法與數(shù)據(jù)結(jié)構(gòu)2.1

算法的概念與特征算法通俗講就是解決某種問(wèn)題所采用的一系列的方法和步驟?？梢钥醋魇怯捎邢迋€(gè)步驟組成的用來(lái)解決問(wèn)題的過(guò)程，其實(shí)質(zhì)反映的是解決問(wèn)題的思路和步驟。2.1

算法的概念與特征算法的特征：有窮性、確定性、可行性。有窮性：一個(gè)算法應(yīng)包含有限個(gè)操作步驟，也就是說(shuō)，解決過(guò)程必須是可終止的。確定性：算法的每一個(gè)步驟都必須明確定義，不應(yīng)該產(chǎn)生二義性。

可行性：算法的每一個(gè)步驟都是可以在有限時(shí)間內(nèi)完成的基本操作，并能得到確定的結(jié)果。輸入：有零個(gè)或多個(gè)輸入，執(zhí)行算法有時(shí)需要從外界取得必要的信息。輸出：有一個(gè)或多個(gè)輸出。沒(méi)有輸出的算法是沒(méi)有意義的。2.2

算法的3種基本的控制結(jié)構(gòu)1、順序結(jié)構(gòu)是最簡(jiǎn)單、最基本的控制結(jié)構(gòu)，其操作步驟是按照設(shè)置的先后順序，一步一步的執(zhí)行。2、選擇結(jié)構(gòu)也叫分支結(jié)構(gòu)，它首先需要判斷給定條件的真假，然后選擇執(zhí)行方向和順序3、循環(huán)結(jié)構(gòu)也叫重復(fù)結(jié)構(gòu)，它在給定條件成立時(shí)，需要反復(fù)重復(fù)執(zhí)行同一操作或類(lèi)似操作。算法的表示方法常見(jiàn)的算法表示方法有：自然語(yǔ)言、流程圖、N-S圖、偽代碼等。1、自然語(yǔ)言優(yōu)點(diǎn)通俗易懂缺點(diǎn)：容易產(chǎn)生歧義，導(dǎo)致執(zhí)行的不確定性。當(dāng)算法循環(huán)和分支較多時(shí)，很難清晰的表示出來(lái)。自然語(yǔ)言表示的算法不便翻譯成計(jì)算機(jī)程序設(shè)計(jì)語(yǔ)言。2.3

算法的表示方法2、用流程圖表示算法流程圖是一種常用的算法描述工具，主要采用一些圖框表示

各種操作，用箭頭表示算法流程，其特點(diǎn)是直觀形象，結(jié)構(gòu)清晰，易于理解。美國(guó)標(biāo)準(zhǔn)化協(xié)會(huì)ANSI規(guī)定了一些常用的流程圖符號(hào)，已為世界各國(guó)程序工作者普遍采用。2.3

算法的表示方法2、用流程圖表示算法int

i

=

0;輸出i不成立i=i+1i是偶數(shù)?不成立成立結(jié)束開(kāi)始i

=

0,cnt

=

0;cnt

=

cnt

+

ii

<=

100?成立不成立i=i+1開(kāi)始輸出cnt結(jié)束i<100?int

i

=

0;輸出i不成立i=i+1不成立成立結(jié)束開(kāi)始i

=

0,cnt

=

0;cnt

=

cnt

+

ii

<=

100?成立不成立i=i+1開(kāi)始輸出cnt結(jié)束int

i

=

0;i<100?;i是偶數(shù)嗎？2.3

算法的表示方法3、N-S圖表示法N-S圖也稱N-S流程圖，這種流程圖完全去掉了帶箭頭的流程線，對(duì)算法的每一步描述都用一個(gè)矩形框表示。優(yōu)點(diǎn)：比文字描述更直觀、形象、易于理解比傳統(tǒng)的流程圖緊湊易畫(huà)廢除流程線，整個(gè)算法結(jié)構(gòu)是由各個(gè)基本結(jié)構(gòu)按順序組成，N-S圖的上下順序就是執(zhí)行時(shí)的順序。流程圖和盒圖比較Leap=1?求閏年算法的表示方法4、偽代碼表示法偽代碼是介于自然語(yǔ)言和計(jì)算機(jī)語(yǔ)言之間的文字和符號(hào)來(lái)描述算法的工具。優(yōu)點(diǎn)：書(shū)寫(xiě)方便、格式緊湊，易于理解，便于向計(jì)算機(jī)程序設(shè)計(jì)語(yǔ)言過(guò)渡缺點(diǎn)由于語(yǔ)言的種類(lèi)繁多，偽代碼的語(yǔ)句不容易規(guī)范。2.3

算法的表示方法4、偽代碼表示法真題解析2.4

典型問(wèn)題求解策略算法策略就是在問(wèn)題空間中搜索所有可能的解決問(wèn)題的方法，直到

選擇一種有效的方法解決問(wèn)題，策略是面向問(wèn)題的，算法是面向?qū)崿F(xiàn)的。經(jīng)典的算法策略主要包括：枚舉算法、遞推算法、遞歸算法、分治算法、貪心算法、回溯算法等。1、枚舉算法也叫窮舉法，其思路就是對(duì)問(wèn)題的所有可能的解空間逐一嘗試，直到找到最終解。針對(duì)于要解決的問(wèn)題，列舉出它所有可能的情況，逐個(gè)判定哪些是符合問(wèn)題所要求的約束條件，從而得到問(wèn)題的解。枚舉算法的示例：百錢(qián)買(mǎi)百雞2.4

典型問(wèn)題求解策略2、遞推算法遞推算法是通過(guò)已知條件，利用特定關(guān)系得出中間結(jié)論，直到得到結(jié)果的算法。遞推算法分為順推和逆推兩種。順推就是從已知條件出發(fā)，

逐步推算出要解決的問(wèn)題的方法。逆推從已知問(wèn)題的結(jié)果出發(fā)，

用迭代表達(dá)式逐步推算出問(wèn)題的開(kāi)始的條件，是順推法的逆過(guò)程。示例：斐波拉契數(shù)列，設(shè)它的函數(shù)為f(n),已知f(1)=1，f(2)=1;

f(n)=f(n-2)+f(n-1)(n>=3,n∈N)。則我們通過(guò)順推可以知道：f(3)=f(1)+f(2)=2,f(4)=f(2)+f(3)=3……直至我們要求的解2.4

典型問(wèn)題求解策略3、遞歸算法遞歸算法是把問(wèn)題轉(zhuǎn)化為規(guī)?？s小了的同類(lèi)問(wèn)題的子問(wèn)題，然后通過(guò)遞歸調(diào)用函數(shù)或過(guò)程來(lái)表示問(wèn)題的解。遞歸算法是一個(gè)程序或函數(shù)直接或間接調(diào)用自己本身。示例：漢諾塔問(wèn)題斐波拉契數(shù)列2.4

典型問(wèn)題求解策略4、分治算法分治算法是將一個(gè)規(guī)模較大的問(wèn)題，分解為若干個(gè)規(guī)模較小的子問(wèn)題，這些子問(wèn)題相互獨(dú)立且與原問(wèn)題性質(zhì)相同，再把子問(wèn)題分成更小的子問(wèn)題，直到最后子問(wèn)題可以簡(jiǎn)單的直接求解，原問(wèn)題的解即為子問(wèn)題的解的合并。分治是一種算法思想，思路。示例：二分搜索（折半搜索《幸運(yùn)52》）2.4

典型問(wèn)題求解策略4、分治算法示例：

二分搜索2.4

典型問(wèn)題求解策略5、貪心算法是指在對(duì)問(wèn)題求解時(shí)，總是做出在當(dāng)前看來(lái)是最好的選擇，也就是說(shuō)，不從整體最優(yōu)加以考慮，僅是局部最優(yōu)解。貪心算法常常用于組合優(yōu)化問(wèn)題，它的求解過(guò)程是多步判斷的過(guò)程。示例：合并排序問(wèn)題6、回溯算法也稱試探法，是一種優(yōu)選搜索法，按選優(yōu)條件向前搜索，以達(dá)到目標(biāo)。但

當(dāng)探索到某一步時(shí)，發(fā)現(xiàn)原先選擇并不優(yōu)或達(dá)不到目標(biāo)，就退回一步重新選擇。解決一個(gè)回溯問(wèn)題，實(shí)際上就是一個(gè)決策樹(shù)或回溯樹(shù)的遍歷過(guò)程。示例：全排列問(wèn)題、N皇后問(wèn)題2.4

典型問(wèn)題求解策略6、回溯算法----八皇后2.5

算法評(píng)價(jià)評(píng)價(jià)算法優(yōu)劣的指標(biāo)或條件：正確性、可讀性、健壯性、復(fù)雜性1、正確性算法應(yīng)當(dāng)能正確求解問(wèn)題。正確性是評(píng)價(jià)算法的首要條件，一個(gè)正確的算法是指在合理的輸入數(shù)據(jù)下，能在有限的運(yùn)行時(shí)間內(nèi)得到正確的結(jié)果。2、可讀性好的算法應(yīng)當(dāng)具有良好的可讀性，容易理解3、健壯性（魯棒性）當(dāng)輸入非法數(shù)據(jù)時(shí)，算法也能適當(dāng)?shù)淖龀龇磻?yīng)或進(jìn)行處理，而不會(huì)產(chǎn)生莫名其妙的輸出結(jié)果2.5

算法評(píng)價(jià)4、復(fù)雜性算法復(fù)雜性分為時(shí)間復(fù)雜度和空間復(fù)雜度，用于評(píng)價(jià)算法在運(yùn)行時(shí)間和占用空間上的程度。通常把算法中所消耗的時(shí)間的多少稱為“算法的時(shí)間復(fù)雜度”，算法的時(shí)間效率是問(wèn)題規(guī)模n的函數(shù)?？捎涀鱐(n)=O(f(n))，比如，

算法的執(zhí)行時(shí)間為

3*n2+3n+1，則它的時(shí)間復(fù)雜度為T(mén)(n)=O(n2)算法的時(shí)間復(fù)雜度一般有：O(1)常數(shù)級(jí)、O(logn)對(duì)數(shù)級(jí)、O(n)線性級(jí)、O(nc)多項(xiàng)式級(jí)（c為常數(shù)）、O(cn)指數(shù)級(jí)（c為常數(shù)）、O(n!)階乘級(jí)常數(shù)時(shí)間復(fù)雜度O(1)：算法的執(zhí)行時(shí)間與輸入規(guī)模無(wú)關(guān)，例如直接訪問(wèn)數(shù)組中的一個(gè)元素。對(duì)數(shù)時(shí)間復(fù)雜度O(logn)：二分查找等對(duì)數(shù)據(jù)規(guī)模進(jìn)行對(duì)數(shù)級(jí)別的處理，隨著輸入規(guī)模增加，其執(zhí)行時(shí)間不是線性增長(zhǎng)，而是以對(duì)數(shù)的方式增長(zhǎng)。線性時(shí)間復(fù)雜度O(n)：算法的執(zhí)行時(shí)間與輸入規(guī)模成線性關(guān)系，例如遍歷一個(gè)數(shù)組。線性對(duì)數(shù)時(shí)間復(fù)雜度O(nlogn)：一些高效排序算法（如歸并排序、快速排序）的時(shí)間復(fù)雜度。平方時(shí)間復(fù)雜度O(n^2)：一些簡(jiǎn)單排序算法（如冒泡排序、插入排序）的時(shí)間復(fù)雜度，執(zhí)行時(shí)間與輸入規(guī)模的平方成正比。指數(shù)時(shí)間復(fù)雜度O(2^n)：某些暴力解法、窮舉法等算法的時(shí)間復(fù)雜度，隨著輸入規(guī)模的增加，執(zhí)行時(shí)間指數(shù)級(jí)增長(zhǎng)。階乘時(shí)間復(fù)雜度O(n!)：某些旅行商問(wèn)題、全排列問(wèn)題等的時(shí)間復(fù)雜度，隨著輸入規(guī)模的增加，執(zhí)行時(shí)間按階乘級(jí)別增長(zhǎng)。2.5

算法評(píng)價(jià)4、復(fù)雜性算法在運(yùn)行過(guò)程中所消耗的內(nèi)存空間的大小被稱為“算法的空間復(fù)雜度”。用S(n)表示。與算法的時(shí)間復(fù)雜度相同。算法的空間復(fù)雜度也可表示為：S(n)=O(g(n))，表示隨著問(wèn)題規(guī)模n的增大，算法運(yùn)行所需存儲(chǔ)量的增長(zhǎng)率與g(n)的增長(zhǎng)率相同。2.6

數(shù)據(jù)結(jié)構(gòu)定義一：數(shù)據(jù)結(jié)構(gòu)是計(jì)算機(jī)存儲(chǔ)、組織數(shù)據(jù)的方式。定義二：數(shù)據(jù)結(jié)構(gòu)(data

structure)是帶有結(jié)構(gòu)特性的數(shù)據(jù)元素的集合，它研究的是數(shù)據(jù)的邏輯結(jié)構(gòu)和數(shù)據(jù)的物理結(jié)構(gòu)，以及它們之間的相互關(guān)系，并對(duì)這種結(jié)構(gòu)定義相適應(yīng)的運(yùn)算，設(shè)計(jì)出相應(yīng)的算法，并確保經(jīng)過(guò)這些運(yùn)算以后所得到的新結(jié)構(gòu)仍保持原來(lái)的結(jié)構(gòu)類(lèi)型。數(shù)據(jù)結(jié)構(gòu)與算法之間的關(guān)系：數(shù)據(jù)結(jié)構(gòu)+算法=程序2.6

數(shù)據(jù)結(jié)構(gòu)典型的數(shù)據(jù)結(jié)構(gòu)包括線性表、樹(shù)和圖。線性表是最基本、最簡(jiǎn)單也是最常用的一種數(shù)據(jù)結(jié)構(gòu)。線性表的定義：一個(gè)線性表是n個(gè)具有相同特性的數(shù)據(jù)元素的有限序列。通常來(lái)說(shuō)，從邏輯上看，線性表中數(shù)據(jù)元素之間的關(guān)系是一對(duì)一的關(guān)系，即除了第一個(gè)和最后一個(gè)數(shù)據(jù)元素之外，其它數(shù)據(jù)元素都是首尾相接的。堆棧和隊(duì)列是兩種特殊的線性表數(shù)據(jù)結(jié)構(gòu)，前者是一種后進(jìn)先出（FILO），后者是一種先進(jìn)先出（FIFO）的集合。2.6

數(shù)據(jù)結(jié)構(gòu)1、隊(duì)列（先進(jìn)先出：FIFO）2.6

數(shù)據(jù)結(jié)構(gòu)2、堆棧（后進(jìn)先出：LIFO）2.6

數(shù)據(jù)結(jié)構(gòu)3、樹(shù)是由n(n≥0)個(gè)有限節(jié)點(diǎn)組成一個(gè)具有層次關(guān)系的集合2.6

數(shù)據(jù)結(jié)構(gòu)4、圖是由頂點(diǎn)集合以及頂點(diǎn)間的關(guān)系集合組成的一種數(shù)據(jù)結(jié)構(gòu)。真題解析2.7

算法的時(shí)間和空間優(yōu)化算法復(fù)雜度的優(yōu)化，就是要將可行解提高到更優(yōu)解，其最終目標(biāo)是：要采用盡可能低的時(shí)間復(fù)雜度和空間復(fù)雜度，去完成一個(gè)算法的設(shè)計(jì)。1、無(wú)效操作剔除處理為了降低算法復(fù)雜度，一個(gè)首要的思路是：

清理算法中的無(wú)效計(jì)算或無(wú)效存儲(chǔ)。即首先嘗試將代碼中的無(wú)效計(jì)算、無(wú)效存儲(chǔ)剔除。比如，在一個(gè)窮舉算法中，可以嘗試縮小可用的窮舉空間，以減少無(wú)用的窮舉操作?；蛘弑M量提高變量或數(shù)據(jù)結(jié)構(gòu)的復(fù)用性，減少內(nèi)存的使用。2.7

算法的時(shí)間和空間優(yōu)化2、使用合理的算法和數(shù)據(jù)結(jié)構(gòu)對(duì)于同一問(wèn)題，可用的算法或數(shù)據(jù)結(jié)構(gòu)可以有很多種，都能實(shí)現(xiàn)相同的目的，為了減少算法的時(shí)間和空間復(fù)雜性，可以選用最優(yōu)的方案。降低空間復(fù)雜度的核心思路就是。盡可能用低復(fù)雜度的數(shù)據(jù)結(jié)構(gòu)，而不用高復(fù)雜度的數(shù)據(jù)結(jié)構(gòu)；盡可能復(fù)用現(xiàn)有內(nèi)存，而不是重新分配

新的內(nèi)存降低時(shí)間復(fù)雜度常用的方法有遞歸、二分法、排序算法、動(dòng)態(tài)規(guī)劃等。2.7

算法的時(shí)間和空間優(yōu)化3、時(shí)間換空間或空間換時(shí)間由于系統(tǒng)資源是有限的，為了在有限的資源內(nèi)，達(dá)成某些特定的性能目標(biāo)，還可以使用時(shí)間換空間或者空間換時(shí)間的方法。性能優(yōu)化的關(guān)鍵在于掌握各部分組件的性能平衡點(diǎn)，如果系統(tǒng)CPU資源有空閑，但是內(nèi)存使用緊張，便可以使用用時(shí)間換空間的策略，即多花一點(diǎn)CPU工作時(shí)間，來(lái)?yè)Q取空間的節(jié)省。。時(shí)間換空間通常用于嵌入式設(shè)備，或者內(nèi)存、硬盤(pán)空間不足的情況，通過(guò)使用犧牲CPU的方式，獲得原本需要更多內(nèi)存或者硬盤(pán)空間才能完成的工作。2.7

算法的時(shí)間和空間優(yōu)化2、時(shí)間換空間或空間換時(shí)間與時(shí)間換空間的方法相反，空間換時(shí)間則是嘗試使用更多的內(nèi)存或者磁盤(pán)空間換取CPU資源或者網(wǎng)絡(luò)資源等，通過(guò)增加系統(tǒng)的內(nèi)存消耗，來(lái)加快程序的運(yùn)行速度。典型應(yīng)用就是緩存的使用，緩存是一塊額外的系統(tǒng)內(nèi)存區(qū)域，如果沒(méi)有緩存，程序依然可以正常工作，但是在一般情況下，緩存中總是保存那些頻繁或即將使用的數(shù)據(jù)，反復(fù)從內(nèi)存獲取這些數(shù)據(jù)會(huì)花費(fèi)大量的資源和時(shí)間，而通過(guò)緩存這塊額外的內(nèi)存，避免了頻繁的CPU資源消耗，加快了程序的運(yùn)行速度。CPU內(nèi)部的高速緩存（cache），程序設(shè)計(jì)中的緩存策略，都是空間換時(shí)間的典型應(yīng)用。三、程序設(shè)計(jì)語(yǔ)言程序設(shè)計(jì)語(yǔ)言可以分為三類(lèi)：機(jī)器語(yǔ)言、匯編語(yǔ)言、高級(jí)語(yǔ)言。其中，機(jī)器語(yǔ)言和匯編語(yǔ)言都屬于低級(jí)語(yǔ)言。1、機(jī)器語(yǔ)言機(jī)器語(yǔ)言是計(jì)算機(jī)系統(tǒng)唯一能直接識(shí)別、不需要翻譯直接供機(jī)器使用的程序設(shè)計(jì)語(yǔ)言。機(jī)器語(yǔ)言實(shí)際上是一串二進(jìn)制指令代碼，其中的每條語(yǔ)句稱為指令。機(jī)器語(yǔ)言的缺點(diǎn)：編寫(xiě)難掌握、編程繁瑣、可讀性差、容易出錯(cuò)、修改和調(diào)試均不方便。依賴于具體的機(jī)器，所以通用性和移植性很差。機(jī)器語(yǔ)言的優(yōu)點(diǎn)：能充分發(fā)揮硬件功能的特點(diǎn)，程序運(yùn)行速度非常快，程序也可以編寫(xiě)的非常簡(jiǎn)潔。2、匯編語(yǔ)言是機(jī)器語(yǔ)言的“符號(hào)化”。匯編語(yǔ)言和機(jī)器語(yǔ)言基本上一一對(duì)應(yīng)的，但在表示方法上作了改進(jìn)，用一

種助記符來(lái)代替操作碼，用符號(hào)來(lái)表示操作數(shù)地址（地址碼）。例如用“ADD”表示加操作，用“MOV”來(lái)表示數(shù)據(jù)傳送等。用助記符和符號(hào)地址來(lái)表示指令，

容易辨認(rèn)，給程序的編寫(xiě)帶來(lái)了很大的方便。匯編語(yǔ)言的優(yōu)點(diǎn)：比機(jī)器語(yǔ)言直觀、容易記憶和理解，比機(jī)器語(yǔ)言程序易讀、易檢查、易修改。缺點(diǎn)：本質(zhì)上仍然是面向機(jī)器的語(yǔ)言，依賴于具體的計(jì)算機(jī)、很難在系統(tǒng)間移植，這樣的程序編寫(xiě)起來(lái)仍然比較困難，程序的可讀性也比較差。匯編語(yǔ)言不能直接被計(jì)算機(jī)直接識(shí)別和執(zhí)行，把匯編語(yǔ)言源程序翻譯成機(jī)器語(yǔ)言的過(guò)程稱為匯編。3、高級(jí)語(yǔ)言高級(jí)語(yǔ)言是20世紀(jì)50年代后期開(kāi)始出現(xiàn)的，是一種接近于人類(lèi)自然語(yǔ)言的習(xí)慣、便于閱讀理解、檢查和修改。高級(jí)語(yǔ)言易學(xué)易用、可讀性好、表達(dá)能力強(qiáng)（接近自然語(yǔ)言）、通用性好（編寫(xiě)的程序能在不同的計(jì)算機(jī)系統(tǒng)上運(yùn)行）。高級(jí)語(yǔ)言不能被計(jì)算機(jī)直接識(shí)別和執(zhí)行。高級(jí)語(yǔ)言可以分成兩類(lèi)：解釋型和編譯型解釋型語(yǔ)言：有一個(gè)專門(mén)的解釋程序，對(duì)源程序一邊翻譯、一邊執(zhí)行，不產(chǎn)生目標(biāo)程序，如python。編譯型語(yǔ)言：需要由編譯程序先翻譯成目標(biāo)程序以后才可以執(zhí)行，會(huì)產(chǎn)生目標(biāo)程序。如C語(yǔ)言、C++、Basic、Visual

basic、C#、java、Jbuilder、delphi。問(wèn)題1：在編程中，“變量”是什么？a)一種控制結(jié)構(gòu)b)用于存儲(chǔ)數(shù)據(jù)的標(biāo)識(shí)符c)只能存儲(chǔ)數(shù)字的存儲(chǔ)單元d)用于執(zhí)行循環(huán)的關(guān)鍵字答案：b)用于存儲(chǔ)數(shù)據(jù)的標(biāo)識(shí)符問(wèn)題2：在編程中，“if”語(yǔ)句用于什么目的？a)執(zhí)行循環(huán)b)定義函數(shù)c)實(shí)現(xiàn)條件判斷d)進(jìn)行數(shù)據(jù)類(lèi)型轉(zhuǎn)換答案：c)實(shí)現(xiàn)條件判斷問(wèn)題3：以下哪個(gè)關(guān)鍵字用于退出循環(huán)？a)exitb)loopc)breakd)continue答案：c)break問(wèn)題4：在編程中，“數(shù)組”是什么？a)一種數(shù)據(jù)類(lèi)型b)一種函數(shù)c)一組相同類(lèi)型的元素集合d)用于控制程序流程的結(jié)構(gòu)答案：c)一組相同類(lèi)型的元素集合問(wèn)題5：在編程中，“函數(shù)”是用來(lái)做什么的？a)存儲(chǔ)數(shù)據(jù)b)控制程序流程c)執(zhí)行特定任務(wù)的獨(dú)立模塊d)定義變量類(lèi)型答案：c)執(zhí)行特定任務(wù)的獨(dú)立模塊問(wèn)題6：在編程中，“循環(huán)”用于什么目的？a)限制變量的范圍b)重復(fù)執(zhí)行特定代碼塊c)控制函數(shù)的返回值d)使變量變得全局可用答案：b)重復(fù)執(zhí)行特定代碼塊問(wèn)題7：在編程中，“對(duì)象”是什么？a)變量的別名b)一種數(shù)據(jù)類(lèi)型c)一種抽象數(shù)據(jù)類(lèi)型的實(shí)例d)用于存儲(chǔ)常量的容器答案：c)一種抽象數(shù)據(jù)類(lèi)型的實(shí)例問(wèn)題8：在編程中，“字符串”是什么？a)一種數(shù)據(jù)類(lèi)型b)用于保存數(shù)字的變量c)用于存儲(chǔ)文字的變量d)一種控制流結(jié)構(gòu)答案：c)用于存儲(chǔ)文字的變量問(wèn)題9：在編程中，“迭代”是指什么？a)數(shù)據(jù)類(lèi)型轉(zhuǎn)換b)循環(huán)的執(zhí)行次數(shù)c)重復(fù)執(zhí)行過(guò)程的過(guò)程d)函數(shù)的返回值答案：c)重復(fù)執(zhí)行過(guò)程的過(guò)程問(wèn)題10：在編程中，“注釋”是用來(lái)做什么的？a)改變變量的值b)調(diào)試程序錯(cuò)誤c)解釋代碼的功能d)控制程序的執(zhí)行順序答案：c)解釋代碼的功能四、面向?qū)ο螅?/p>

Object

Oriented

）程序設(shè)計(jì)1、概述目前程序設(shè)計(jì)方法主要有兩種：結(jié)構(gòu)化程序設(shè)計(jì)和面向?qū)ο蟪绦蛟O(shè)計(jì)。在結(jié)構(gòu)化程序設(shè)計(jì)中，任何程序段的編寫(xiě)都基于3種結(jié)構(gòu)：順序結(jié)構(gòu)、分支結(jié)構(gòu)、循環(huán)結(jié)構(gòu)。程序具有明顯的模塊化特征，每個(gè)程序模塊具有唯一的出口和入口語(yǔ)句。面向?qū)ο蟪绦蛟O(shè)計(jì)方法是盡可能模擬人類(lèi)的思維方式，使得軟件的開(kāi)發(fā)方法與過(guò)程盡可能接近人類(lèi)認(rèn)識(shí)世界、解決現(xiàn)實(shí)問(wèn)題的方法和過(guò)程，也即使得描述問(wèn)題的問(wèn)題空間與問(wèn)題的解決方案空間在結(jié)構(gòu)上盡可能一致，把客觀世界中的實(shí)體抽象為問(wèn)題域中的對(duì)象。1、概述面向?qū)ο蟪绦蛟O(shè)計(jì)可以看作一種在程序中包含各種獨(dú)立而又互相調(diào)用的對(duì)

象的思想，這與傳統(tǒng)的思想剛好相反：傳統(tǒng)的程序設(shè)計(jì)主張將程序看作一系列

函數(shù)的集合，以功能模塊為中心，采用模塊化自頂向下，逐步求精的設(shè)計(jì)過(guò)程。面向?qū)ο蟪绦蛟O(shè)計(jì)把構(gòu)成問(wèn)題的事務(wù)抽象分解成各個(gè)對(duì)象，每一個(gè)對(duì)象都

能夠接受數(shù)據(jù)、處理數(shù)據(jù)并將數(shù)據(jù)傳達(dá)給其它對(duì)象，或者調(diào)用其它對(duì)象的方法。面向?qū)ο蠓椒ǖ膬?yōu)點(diǎn)：與人類(lèi)習(xí)慣的思維方法一致；穩(wěn)定性好；可重用性好；易于開(kāi)發(fā)大型軟件產(chǎn)品；2、面向?qū)ο蟪绦蛟O(shè)計(jì)的基本思想客觀事物是由對(duì)象組成的，對(duì)象是在原事物基礎(chǔ)上抽象的結(jié)果。對(duì)象是由屬性和操作組成的，其屬性反映了對(duì)象的數(shù)據(jù)信息特征，而操作則用來(lái)定義改變對(duì)象屬性狀態(tài)的各種操作方式。對(duì)象之間的聯(lián)系通過(guò)消息傳遞機(jī)制來(lái)實(shí)現(xiàn)。對(duì)象可以按其屬性來(lái)歸類(lèi)。對(duì)象具有封裝、繼承、多態(tài)的特性，可達(dá)到軟件復(fù)用的目的。面向?qū)ο蟮娜ㄋ模┐筇匦裕?/p>

（抽象）、封裝、繼承、多態(tài)塞大象()把大象裝進(jìn)冰箱-結(jié)構(gòu)化程序設(shè)計(jì)方法開(kāi)始結(jié)束打開(kāi)冰箱門(mén)()關(guān)閉冰箱門(mén)()雙手開(kāi)門(mén)單手開(kāi)門(mén)結(jié)束雙手關(guān)門(mén)單手關(guān)門(mén)把大象裝進(jìn)冰箱-結(jié)構(gòu)化程序設(shè)計(jì)方法開(kāi)始 開(kāi)始結(jié)束雙開(kāi)門(mén)冰箱？是開(kāi)冰箱門(mén)(

)關(guān)冰箱門(mén)(

)否否雙開(kāi)門(mén)冰箱？是把大象裝進(jìn)冰箱-結(jié)構(gòu)化程序設(shè)計(jì)方法裝大象揍大象()開(kāi)始結(jié)束塞大象(

)否大象愿意進(jìn)？是皮鞭抽棍棒打開(kāi)始結(jié)束揍大象(

)棍棒工具？皮鞭把大象裝進(jìn)冰箱-面向?qū)ο蟪绦蛟O(shè)計(jì)方法屬性：冰箱類(lèi)型方法1：開(kāi)門(mén)()方法2：關(guān)門(mén)()方法3：裝載(物品)屬性：意愿方法：挨揍(工具)冰箱對(duì)象大象對(duì)象冰箱.開(kāi)門(mén)()開(kāi)始結(jié)束冰箱.關(guān)門(mén)()大象.挨揍(皮鞭)冰箱.裝東西(大象)大象.意愿=愿意？是否3、對(duì)象(object)對(duì)象是面向?qū)ο蠓椒ㄖ凶罨镜母拍睿梢杂脕?lái)表示客觀世界中的任何實(shí)體，對(duì)象可以是具體的物（人、動(dòng)物），也可以指某些概念（會(huì)議、課程）。對(duì)象是構(gòu)成系統(tǒng)的一個(gè)基本單位，任何對(duì)象都具有自己的特征和行為。所以對(duì)象由一組表示其靜態(tài)特征的屬性和它可執(zhí)行的一組操作組成。屬性即對(duì)象的特征，操作描述了對(duì)象執(zhí)行的功能（對(duì)象具有的行為），操作也稱為方法或服務(wù)。4、類(lèi)（class）類(lèi)是編程實(shí)現(xiàn)中的概念，是指編程中具有相同屬性和方法的對(duì)象的集合。在編程中，類(lèi)是對(duì)象的抽象，對(duì)象是類(lèi)的一個(gè)實(shí)例。類(lèi)相當(dāng)于在程序語(yǔ)言中為某個(gè)對(duì)象設(shè)計(jì)的圖紙，而對(duì)象則是依據(jù)圖紙制造出來(lái)的某個(gè)實(shí)際產(chǎn)品。類(lèi)中所包含的所有東西，稱為類(lèi)的成員，包括類(lèi)的屬性和方法。右方的代碼定義了一個(gè)“狗”的類(lèi)，這只狗具有毛發(fā)顏色和是否孕育兩個(gè)屬

性，還有一個(gè)吠叫的方法。5、消息（Message）消息是對(duì)象之間傳遞的信息。對(duì)象之間只能通過(guò)消息進(jìn)行通信，而不允許在對(duì)象之外直接地訪問(wèn)它內(nèi)部的屬性，這是由封裝原則引起的。消息必須直接發(fā)給特定的對(duì)象，消息中包含所請(qǐng)求服務(wù)的必要信息，且遵守所規(guī)定的通信規(guī)格說(shuō)明。一條消息至少包括：消息名、入口參數(shù)、可能返回的參數(shù)，一個(gè)對(duì)象可以是消息的接受者、發(fā)送者和參數(shù)。6、封裝（Encapsulation）在完成抽象后，通過(guò)某種語(yǔ)法形式，將對(duì)象的屬性和方法捆綁在一起，在形式上寫(xiě)成一個(gè)整體，即“類(lèi)”，并盡可能隱藏對(duì)象的內(nèi)部細(xì)節(jié)，對(duì)象好像是一個(gè)不透明的黑盒子，這個(gè)過(guò)程就叫作“封裝”。封裝是面向?qū)ο蟪绦蛟O(shè)計(jì)方法的一個(gè)重要特性，封裝具有兩方面的含義:1）將數(shù)據(jù)和操作代碼封裝在一個(gè)對(duì)象中，各個(gè)對(duì)象相對(duì)獨(dú)立、互不干擾；2）將對(duì)象中某些操作代碼對(duì)外隱藏，即隱藏其內(nèi)部實(shí)現(xiàn)細(xì)節(jié),只留下少量接口，以便與外界聯(lián)系，接收外界消息，這種做法稱為信息隱藏。信息隱藏有利于數(shù)據(jù)安全，防止無(wú)關(guān)人員訪問(wèn)和修改數(shù)據(jù)。6、封裝（Encapsulation）對(duì)象封裝以后，使用一個(gè)對(duì)象的時(shí)候，只需知道它向外界提供的接口而無(wú)需知道它的數(shù)據(jù)結(jié)構(gòu)細(xì)節(jié)和實(shí)現(xiàn)操作的算法。封裝的結(jié)果實(shí)際上隱藏了復(fù)雜性，并提供了代碼重用性，從而減輕了開(kāi)發(fā)軟件系統(tǒng)的難度。7、繼承（In