－及考試相關關于考試1.考試時間：2015.1.14星期三8:00-9:50答題紙上，否則不得分，并寫明任課教師、班級、學號和姓名。60%4.考試題型：

選擇、填空、判斷、綜合答疑和上機時間：12月24日3、4和5、6節；地點：原上機實驗機房復習大綱基礎知識部分知識點計算工具的發展歷史；計算機的發展歷史；（第一臺？按什么定的四個階段？每個階段的特點？……）圖靈、馮.諾依曼在計算機發展史上的貢獻（圖靈機？程序存儲思想？）；計算機的應用有哪些方面？（天氣預報？人機對戰如國際象棋）計算機的發展趨勢數和進制（重點二進制）字符編碼（ASCII碼）、漢字編碼（P70）數據的存儲單位計算機的基本組成及工作原理（存儲程序和程序控制P75）微機的主要性能指標（字長、運算速度、內/外存容量等）計算機指令的概念（操作碼、地址）（P80）存儲器的原理及其種類及各自特點（地址？內存－寄存器和cache？外存？）計算機系統的組成（計算機的五大部件？）操作系統的概念、功能（P89）和常見操作系統；復習大綱問題求解及算法問題求解的思路（第一步是什么？數學建模）和策略什么是算法？P121，算法的特征和描述方式。從哪些方面可對算法進行評價分析（首先是正確性，時間復雜性—O階表示，空間復雜性）典型算法及其思想窮舉法、遞推法、遞歸法、貪心法搜索問題的要素及計算機搜索中的思想典型的查找方法及思想 順序查找、折半查找（衡量查找算法的好壞是平均查找長度）排序算法的思想選擇排序和冒泡排序復習大綱數據及數據結構4.數據的邏輯結構及其種類（集合、線性、樹狀、圖）5.數據的物理結構及其種類（又叫邏輯結構：順序和鏈式）7.典型線性結構及其特點：隊列和棧復習大綱計算機程序計算機程序的概念P223計算機語言分類（P220，機器、匯編、高級；助記符？面向硬件？）；程序基本結構（順序、分支、循環）數據類型的概念在程序中的作用；P232數據管理技術的發展歷史數據庫的概念數據庫管理系統中常用的數據模型（P260，關系、層次、網狀）數據庫管理系統的功能典型的數據庫管理系統（ACCESS、SQLServer、Oracle、MySQL、FoxPro和Sybase等）了解結構化查詢語言SQL（P262）復習大綱計算機網絡知識點計算機網絡定義和基本功能（P284）計算機網絡的分類（按規模劃分局域網、城域網、廣域網）網絡體系結構：OSI、TCP/IPOSI的七層（注意順序）TCP/IP中應用層的常用協議IP地址編碼方案：IPv4、IPv6（32，128）域名命名機制、常用頂級域名常用網絡設備的名稱及功能（網卡、交換機、路由器）網絡應用模式（C/S、B/S，P309，316或P275）信息安全的概念什么是病毒及其特征？什么是木馬？（P330）信息安全技術：防火墻（P328）……什么是數據加密技術？了解云計算（P349）、物聯網（P355）和大數據（P358）等相關知識互聯網常識（電子郵件地址格式，互聯網通信使用的協議，傳輸介質，黑客？）一、模擬題：單項選擇1.在計算機內部，所有信息都是以（）表示的。2.計算機的硬件主要包括中央處理器（CPU）、存儲器、輸出設備和（）。3.在計算機運行時，把程序和數據一樣存放在內存中，這是1946年由（）領導的小組正式提出并論證的。（P54頁）4.計算機存儲容量的基本單位是（）5.在微型計算機中，下列設備屬于輸入設備的是（） A．打印機 B.顯示器 C.鍵盤 D.硬盤6.在下列設備中，屬于輸出設備的是（） A.硬盤 B.鍵盤 C.鼠標 D.打印機控制器、運算器7.計算機從其誕生至今已經歷了四個時代，劃代的原則是根據（）8.一臺計算機的字長為16位，說明它()。 A．可一次進行運算或傳送的二進制數的最大位數是16位 B．可表示的最大數值是2 C．能處理最多為16位的十進制數 D．能處理的字符串最多由16個英文字母組成9下列關于ASCII碼說法錯誤的是()。 A.8位擴展ASCII碼可表示128個不同字符 B.ASCII碼有7位ASCII碼和8位ASCII碼兩種 C.7位標準ASCII碼規定其最高位為0 D.ASCII碼是AmericanStandardCodeforInformationInterchange的縮寫7位標準ASCII碼規定其最高位為0；278位擴展ASCII碼規定其最高位為1；2810.計算機能夠應用于各個領域，體現了計算機的()。 A.通用性強 B.存儲容量大 C.運算速度快 D.工作自動化11.下列程序段的時間復雜度為（）。 i=1; sum=0; for(i=1;i<=n;i++)

sum=sum+i; A.O(1) B.O(log2n) C.O(n) D.O(n2)12.計算機求解問題過程中，算法策略設計要解決的問題是（）。 A.將問題抽象為一個數學問題 B.選擇較優的算法策略 C.設計算法具體如何執行的控制結構 D.用某種程序設計語言編寫實現算法的程序13.若有如下圖所示的四個城市及其路徑長度，旅行商從城市A出發，到每個城市旅行，途中只能經過每個城市一次，最后回到城市A，則采用貪心算法時，求得的路徑長度是（）。 A.13 B.14 C.13或14 D.19窮舉法所有路徑組合（n-1）!每次在選擇下一個城市的時候，只考慮當前情況，保證迄今為止經過的路徑總距離最短。14.問題求解過程中的第一步就是要（）。 A.數學建模 B.算法設計 C.數據結構設計 D.控制結構設計15.若要對某個序列按升序排序，則使用冒泡排序時，若依次從前往后比較，則第一趟被排出的數是（）。 A.最小數 B.最大數 C.中間數 D.以上都不對冒泡排序：對排序數組元素中相鄰的兩個元素進行比較，將大的放前，小的放后--遞減排序(或者是將小的放前，大的放后--遞增排序)。再重復上述過程，一直進行到數組最后一個元素。時間復雜度為O(n2)12，8，5，98，12，5，98，5，12，98，5，9，12如果有n個數，就要進行n-1次比較；每次比較，小數上升，大數下沉。16.下面關于線性表的敘述中，錯誤的是（）。 A．線性表采用順序存儲，必須占用一片連續的存儲單元 B．線性表采用順序存儲，便于進行插入和刪除操作 C．線性表采用鏈接存儲，不必占用一片連續的存儲單元 D．線性表采用鏈接存儲，便于插入和刪除操作17.棧的插入刪除操作必須在表的（）進行 A．一端 B．兩端 C．中間 D.任意位置18.程序設計中的sum=sum+i中等號代表的是（）19.循環結構最適合解決下面哪一類問題？20.將計算機用于天氣預報，是在（）方面的應用。21.IP地址是由小數點隔開的四個十進制數組成，下列屬于IP地址的是（）棧是一種只在表尾進行插入刪除操作的線性表，隊列只能表的一端進行插入，另一端進行刪除操作。22.防火墻（Firewall）是（） A.用于預防計算機被火災燒毀 C.是Internet（因特網）與Intranet（內部網）之間所采取的一種安全措施23.計算機能直接執行（）24.（）語言是用助記符代替操作碼、地址符號的面向機器的語言。25.計算機的應用領域包括（）計算機輔助系統和計算機網絡與通信。 A.高速運算、網絡管理 B.科學計算、信息管理 C.過程控制、人工智能 D.衛星發射、導彈控制26.程序的開發步驟中不包括()。27.關于計算機語言，下列說法不正確的是()。 A.所謂“高級語言”和“低級語言”是指其和機器硬件的相關程度，不涉及機器硬件的語言為高級語言，而與機器硬件相關的語言則為低級語言。 B.高級語言編程效率高是因為其可用大粒度積木塊來構造程序，比一行行語句、一條條指令來編程效率高出很多。 C.所有源程序最后都需被轉換為匯編語言程序，機器才能夠執行。 D.低級語言程序執行效率高是因為低級語言直接面向硬件。28.以下關于算法的描述中不正確的是（）。 A.算法中每一個步驟的含義都應該是確定的。 B.算法中每一個步驟都應該能有效的執行。 C.正確的算法應在有限的步驟內結束。 D.正確的算法都必須有輸入和輸出。29.網上“黑客”是指（）的人。 A.總在晚上上網 B.匿名上網 二、模擬題：填空題漢諾塔問題中，如果要把5個盤子按要求從a柱移動到c柱，則共需要移動_____次盤子。設n為圓盤數目，移動次數是f(n)，則：f(1)=1f(2)=3f(3)=7……f(n)=2^n-1。abcabc2.電子計算機能夠自動地按照人們的意圖進行工作的最基本思想是_______。P743.通常將計算機程序設計語言分為機器語言、___________、高級語言三種類型。4.已知a=-1，則執行下列語句后b的值為____________。 b=-1; if(a>-2) b=1; elseb=0;5.數據管理經歷了人工管理階段、__________階段和__________階段。P2586.數據庫管理系統通常由數據定義語言、________________、______________和通信功能程序組成。P2607.傳統的計算機網絡，按照計算機分布的地理位置劃分，一般分為：___________、____________和城域網。P2868.IPV4的地址長度是_____位的，采用了點分十進制表示法。IPV6的地址長度是_____位的。9.域名系統的結構是一種分層次結構。每個域名是由幾個域組成的，域與域之間用小圓點“.”分開，最末的域叫___________，其它域的叫子域。P31110.若有序列{2，5，6，10，15，21，26，30，56，78}，若用折半查找算法找30，則需要比較________次。25610152126305678

25610152126305678哪些數需要查找1次、2次、3次或4次？二分查找又稱折半查找，要求待查表為有序表。首先，假設表中元素是按升序排列，將表中間位置記錄的關鍵字與查找關鍵字比較，如果兩者相等，則查找成功；否則利用中間位置記錄將表分成前、后兩個子表，如果中間位置記錄的關鍵字大于查找關鍵字，則進一步查找前一子表，否則進一步查找后一子表。重復以上過程，直到找到滿足條件的記錄，使查找成功，或直到子表不存在為止，此時查找不成功。11.若使用冒泡排序對n個數降序排序，則最多需要排________趟（輪）。在最好的情況下整個排序只進行一輪，比較n-1次。在最壞情況下，需要比較n-1輪，每輪比較的次數分別是n-1,n-2,…3,2,1，總的比較次數為：n(n-1)/2時間復雜度為O(n2)12．已知斐波那契數列的遞推公式如下，則第20項的值為_______。

13.如果用窮舉法來猜測由8位數字組成的銀行卡密碼，則有_______種解。14.若用窮舉法求解0-1背包問題，則對于有7個物品的問題，所有可能解決方案共有_______種。10827－1三、模擬題：判斷題N-S圖是一種用流程線表示執行順序的算法描述方法。2.數學建模是問題求解的第一個步驟。3.一個優秀的算法應該對于一切合法的輸入數據，算法得到的結果都是正確的。4.計算數列時，由第一項開始一直求到第n項的過程稱為遞歸。5.折半查找算法的效率與順序查找算法相當。折半查找的速度比順序查找要快，若n=127，順序查找的平均查找長度為64，而折半查找的平均查找長度為6。1973年，美國學者I.Nassi和提出了一種在流程圖中完全去掉流程線，全部算法寫在一個矩形陣內，在框內還可以包含其他框的流程圖形式。即由一些基本的框組成一個大的框，這種流程圖又稱為N-S結構流程圖（以兩個人的名字的頭一個字母組成）。N-S圖包括順序、選擇和循環三種基本結構。6.折半查找算法要求被查找的序列必須是有序的。7.選擇排序時，總是相鄰的兩個數不斷的比較，逆序則交換順序。如果是1000個數則需要比較：999+998+997+996+……+1＝499500次時間復雜度為O(n2)

首先在所有數據（保存于數組中）中找出最小值，與第一個數組元素交換；接著在余下的數組元素中（不包含第一個數組元素）再找出最小值的元素，與第二個數組元素交換；如此循環，一直到排完最后一個元素。8.線性表在物理存儲空間中一定是連續的。9.線性表在使用鏈式存儲時邏輯上相鄰的元素未必在存儲的物理位置次序上相鄰。10.棧是一種對所有插入、刪除操作限于在表的一端進行的線性表，是一種先進后出型結構。11.隊列是一種插入與刪除操作分別在表的兩端進行的線性表，是一種先進后出型結構。12.排隊買票屬于棧的實例。錯誤。線性表有兩種存儲方式，順序存儲和鏈式存儲（不需要連續的）。正確。線性表有兩種存儲方式，在順序存儲時，邏輯上相鄰的元素在存儲的物理位置次序上也一定相鄰。但鏈式存儲不一定。正確。棧是一種只在表尾進行插入刪除操作的線性表，隊列在表的一端進行插入，另一端進行刪除操作。錯誤。后半句不對，與棧不同，隊列是一種先進先出的線性表。錯誤。屬于隊列13.資源共享可以分為硬件資源，軟件資源和數據資源三個方面。（P285）14.網絡協議是一種特定的數據格式，兩個通訊的主機或者程序，要支持同樣的網絡協議才能通信。（P290）15.云存儲和云安全都是云計算概念的應用。（P349）16.普適計算是指無所不在，隨時隨地進行，與環境融為一體的計算。（P349）四、模擬題：綜合題1.簡述計算機發展的歷程，及每一代計算機的主要特點。2.什么是操作系統？它在計算機中的主要功能有哪些？3.什么是人工智能？能否舉例說明人工智能在生活中的應用。4.衡量計算機的主要性能指標有哪些？5.公元5世紀末，我國古代數學家張丘建在他的《算經》中提出了著名的“百錢買百雞問題”：雞翁一，值錢五，雞母一，值錢三，雞雛三，值錢一，百錢買百雞，問翁、母、雛各幾何。請寫出該問題所建的數學模型（請寫出解決該問題的算法，表達方式不限）。（P132）窮舉對象：公雞x、母雞y、小雞z窮舉范圍：x、y、z都必須是整數； 0<x<20，0<y<33，3≤z<99并且zmod3=0判定條件： 5x+3y+z/3=100 x+y+z=100四、綜合題6.一般情況下兔子在出生兩個月后就有繁殖能力，一對兔子每個月能生出一對小兔子來。如果所有兔子都不死，請列出一