演算法的計算量大小稱為計算機的

『壹』 1. 演算法的計算量的大小稱為計算的什麼

B.復雜性
所謂演算法的計算量大小就是這個演算法的時間復雜度

『貳』 秦九昭演算法的加法與乘法的運算

f(x)=5x^5+4x^4+3x^3+2x^2+x 加法應認為是5次，因為程序默認為常數項為0。
f(x)=x^5+4x^4+3x^3+2x^2+x+1中的最高次項的系數為1，程序默認為1*x^5,所以其乘法為5次。
數值分析書中是這樣說的「秦九昭演算法的計算量是n，當且僅當Pn(x)」，這里Pn(x)是n次多項式。
一般來說，計算一種演算法的乘法計算量都是針對在計算機上實現該演算法，因為乘法佔內存很多，很影響速度。離開了計算機而再來討論乘法計算量意義不大。

『叄』 計算機演算法指的是什麼

計算機演算法是以一步接一步的方式來詳細描述計算機如何將輸入轉化為所要求的輸出的過程，或者說，演算法是對計算機上執行的計算過程的具體描述。

無論演算法有多麼復雜，都必須在有限步之後結束並終止運行；即演算法的步驟必須是有限的。在任何情況下，演算法都不能陷入無限循環中。演算法必須是由一系列具體步驟組成的，並且每一步都能夠被計算機所理解和執行，而不是抽象和模糊的概念。

演算法首先必須是正確的，即對於任意的一組輸入，包括合理的輸入與不合理的輸入，總能得到預期的輸出。如果一個演算法只是對合理的輸入才能得到預期的輸出，而在異常情況下卻無法預料輸出的結果，那麼它就不是正確的。

(3)演算法的計算量大小稱為計算機的擴展閱讀

特點

1、有窮性。一個演算法應包含有限的操作步驟，而不能是無限的。事實上「有窮性」往往指「在合理的范圍之內」。如果讓計算機執行一個歷時1000年才結束的演算法，這雖然是有窮的，但超過了合理的限度，人們不把他視為有效演算法。

2、確定性。演算法中的每一個步驟都應當是確定的，而不應當是含糊的、模稜兩可的。演算法中的每一個步驟應當不致被解釋成不同的含義，而應是十分明確的。也就是說，演算法的含義應當是唯一的，而不應當產生「歧義性」。

3、有零個或多個輸入。所謂輸入是指在執行演算法是需要從外界取得必要的信息。

4、有一個或多個輸出。演算法的目的是為了求解，沒有輸出的演算法是沒有意義的。

5、有效性。 演算法中的每一個 步驟都應當能有效的執行。並得到確定的結果。

『肆』 計算機可以分為哪幾類

計算機分類有以下幾種：
1、計算機如果指的是專業層次，則包含有計算機科學與技術、軟體工程、信息管理與信息系統、網路工程、計算機應用技術、計算機網路技術、物聯網工程等專業。
2、計算機如果是指用途層面，按照用途分為通用計算機和專用計算機。
3、計算機如果是指電腦層面，按照綜合性能指標，將計算機分為如下5大類：高性能計算機、微型計算機、工作站、伺服器、嵌入式計算機。

『伍』 計算機基礎知識

一、計算機的發展

電子計算機是一種能夠自動、高速地進行算術和邏輯運算的電子設備。它是20世紀科學技術發展最偉大的發明創造之一，是人類在第三次工業革命中取得的最輝煌成就。

1.世界上第一台電子計算機的誕生

人類在同大自然斗爭中，創造並逐步發展了計算工具，早在公元前3000年，中國人就發明了算籌和竹籌計數，唐末創造出算盤，南宋1274年已有算盤和歌訣的記載，算盤是同時具有「算」和「存」的計算工具。1633年，奧芙特德（Oughtred）發明了計算尺。1642年，法國數學家帕斯卡製成第一台齒輪加減法器，是世界最早的用於計算的機器。1671年，德國數學家萊布尼茨發明了可以進行四則運算的機械計算機器。1822年英國數學家查爾斯·巴貝奇設計出差分機，這是世界上第一台真正意義上的機械式計算機。1834年，巴貝奇又設計出分析機，這個由存儲數據的「倉庫」、數據運算的「工廠」和調度機器運算的「控制桶」構成的設計，已經奠基了計算機的基本結構框架，因此，巴貝奇被稱為「計算機之父」。第二次世界大戰中，由於新武器研製中的彈道問題涉及許多復雜運算，急需一種能高速、自動計算的機器，因此，在美國陸軍部的資助下，由美國賓夕法尼亞大學任教的物理學家約翰·莫齊利和工程師普雷斯伯·埃克特領導下，從1943年開始，經過三年的努力，終於在1946年研製成功世界上第一台電子計算機，取名為ENIAC。ENIAC約佔170m²，重約30 t，共使用了17456隻電子管，1500個繼電器，7000多個電阻，10000多個電容及其他多種電器元件，運行時耗電約150 kW。這樣一個龐然大物，僅能存儲20個字長10位的十進制數，運算速度也僅為每秒5000次加法運算。盡管如此，ENIAC卻開創了人類計算機科學發展的新時代。

為了克服ENIAC的缺點，人們始終沒有停頓探索的腳步，許多專家、學者就此發表了研究論文。在普林斯頓大學任教的美國數學家馮·諾依曼發表了題為《電子計算機邏輯結構初探》的報告，提出了程序存儲方式，即在計算機中設置存儲器，把符號化的計算過程放入其中，執行時依次將存儲內容取出並解碼，然後按解碼結果進行計算，從而實現計算機工作的自動化。馮·諾依曼在研製EDVAC計算機過程中，改進了內存部件，並將計算機內部的十進制編碼改為二進制編碼。「存儲程序」的設想確立為馮氏結構機的設計體系，從此，採用程序存儲方式的計算機統稱為馮·諾依曼式計算機。

2.計算機發展的重要階段

從第一台電子計算機誕生至今，它走過了50多年的發展歷程，開創了人類社會信息發展史的三個新紀元，即計算機發展的三個重要階段。

（1）計算機發展的初級階段 這個階段大約以ENIAC誕生為標志到個人計算機開始普及之前。盡管那時計算機及其相關外圍設備的價格十分昂貴，其應用的領域基本局限於軍事、科學計算和大型工業企業的數據處理，但卻開創了人類開始用機器代替部分腦力勞動的新紀元。

這一階段，計算機取得了飛速發展，多次更新換代。計算機劃代一般是以計算機核心部件採用的邏輯元件的種類為依據的。

第一代（1946—1956），以電子管為主要邏輯元件，運算速度在5000～40000（次/秒）。體積大、能耗高、速度慢、容量小、價格貴，僅限於軍事和科學計算的應用。

第二代（1957—1964），以晶體管為主要邏輯元件，並採用了監控程序，運算速度在幾十萬至上百萬（次/秒）。與第一代計算機相比，體積小、成本低、速度快、功能強、可靠性高，應用領域擴展到工程設計、數據處理和事務管理等方面。

第三代（1965—1970），以中、小規模集成電路為主要邏輯元件，運算速度在百萬至幾百萬（次/秒）。這一代計算機以1964年4月IBM公司推出IBM360計算機為標志，具備了通用化、系列化、標准化的特點。

第四代（1971—20世紀80年代初），以大、超大規模集成電路為主要邏輯元件，運算速度在幾百萬至幾億（次/秒）。採用了集成度更高的半導體存儲器作為主存儲器，發展了並行處理技術、分布式系統和計算機網路。在軟體方面，發展了分布式操作系統、資料庫系統、高級語言及軟體工程標准化等，並逐漸形成軟體產業。

（2）計算機廣泛普及應用階段 微型計算機的開發應該是在20世紀70年代中期，1975年，美國MITS公司利用Intel8080處理器開發了Altair8800微電腦，得到電子愛好者的推崇，推動了個人計算機軟硬體的發展。1976年，美國蘋果公司推出Apple個人計算機並得到極大發展。1980年，IBM公司涉足個人計算機領域，為與蘋果公司競爭市場，將PC計算機的結構框架公諸於世，並與比爾·蓋茨的微軟公司合作推出PC-DOS操作系統，使眾多廉價的兼容機問世。微型機以DOS為操作系統，以其低廉的價格使之迅速普及並得到廣泛應用。從此，計算機不再為少數專業人員所擁有和使用，計算機的發展走向了普及化的新紀元，並為向計算機文化階段發展奠定了基礎。

（3）計算機文化階段 計算機文化階段是計算機普及應用到一定程度才出現的。計算機硬體功能不斷提高，價格更加低廉；信息壓縮與全數字化帶來了豐富多彩的多媒體技術；以多媒體技術為基礎的虛擬現實技術、3S（GIS，GPS，RS）技術實現的電子地圖系統、衛星遙感定位跟蹤監控系統等提高了人類認識世界的能力，造福於人類；無處不在的Internet拉近了世界各國的距離，依靠計算機網路技術實現的遠程教育、遠程醫療診斷系統、數字化圖書館、數字化智能小區已經向我們走來；無線接入技術（藍牙技術、WAP）實現了手機上網、無線區域網（WLAN）；電腦卡已由早期的光電卡、條碼卡、磁卡發展到今天的IC卡、射頻卡，帶給人們便捷。這一切不斷拓展了計算機的應用空間，計算機已經成為一種個人的信息機器，改變著人們的生活。當計算機的應用覆蓋到人們社會生活的各個方面時，必然導致人們在思維方式、行為方式、生活方式等方面產生重大變革，這種因具有人腦部分功能的計算機的普遍使用帶來的文化變遷形成了計算機文化。從20世紀90年代初開始，多媒體計算機和網際網路「信息高速公路」的誕生標志著計算機的發展進入了嶄新的階段，開創了最大限度實現資源共享的新紀元。

3.我國計算機的發展概況

新中國誕生為我國科學技術的發展，也為計算機技術的發展開辟了廣闊的發展道路。

1952年，在清華大學成立了以電機系教授閔大可為組長的中國第一個計算機三人研究小組，1954年，小組經擴充和調整，並入以物理學家錢三強為領導的中國科學院近代物理研究所，開始了我國計算機研究的起步。1956年，國家制定科學技術12年遠景規劃時，把計算機技術列為四大技術之首，成立了計算機技術工作小組，開始進行實質性研發。1958年，我國研製成功第一台電子管計算機（103機）；1959年，研製成功每秒1萬次的大型通用電子計算機（104機），從而填補了我國計算機技術領域的空白。華羅庚教授是我國計算機技術的奠基人和我國第一台電子計算機的主要創始人之一。1960年，我國第一台自行設計的通用電子計算機（107機）研製成功並投入運行。1964年，我國開始推出第二代晶體管計算機，如「108」機、「109」機等。1971年，我國研製成功第三代集成電路計算機「150機」，到1973年形成了DJS-100系列國產機。1974～1982年實現了從小規模集成電路計算機到大規模集成電路計算機跨越。1983年，我國研製成功每秒向量運算1000萬次的757大型向量計算機。

巨型機是一個國家科學技術水平的標志。從20世紀80年代初開始，我國開始進行巨型機的研製。1983年，向量運算億次的巨型電子計算機「銀河」誕生；1992年，10億次的「銀河」Ⅱ號投入使用；1996年，投入運行的「銀河」Ⅲ號機速度為每秒百億次。1995年曙光1000研製成功，1998年「曙光」2000-I誕生，其峰值運算速度達每秒200億次浮點運算，打破了國外在大規模並行機技術方面的封鎖和壟斷；1999年「曙光」2000Ⅱ問世，其峰值運算速度達每秒1117億次浮點運算，內存高達50GB，成為國家863計劃的重大成果。1999年「神威」並行計算機研製成功，其峰值運算速度高達每秒3840億次浮點運算。「銀河」、「曙光」、「神威」計算機的研製成功標志著我國成為世界上具備獨立研製高性能計算機能力的少數國家之一。

微型機是一個國家科學技術普及應用水平的標志。20世紀90年代以來，我國在微機方面也取得迅速發展。2001年10月13日，我國第一款通用CPU晶元——「龍芯」誕生，使我國成為能夠研究製造計算機晶元的少數國家之一。

在計算機應用領域，我國也取得了輝煌的成就。北京大學王選教授的激光照排技術開創了出版印刷的新時代，這一發明獲得了歐洲專利和8項中國專利。王選率領他的團隊推出了處於國內外領先地位的「華光」、「方正」電子出版系統，取得了重大的經濟和社會效益，使我國的印刷業告別了「鉛與火」的歷史，進入了「電與光」的時代，王選也被譽為「激光照排之父」。多種漢字鍵盤輸入方法以及漢字掃描輸入、手寫輸入和語音識別輸入軟體使漢字可以輕松地進入計算機；眾多國產多媒體軟體的開發，推動了計算機的普及應用；國家「信息高速公路」建設取得突出進展，「金」字工程，如「三金」工程包括國家公用信息網（金橋）、外貿企業間信息系統（金關）、金融業電子貨幣（金卡）的完成，加快了社會信息化進程。據2002年7月23日CNNIC公布，平均每周至少上網1小時的中國公民人數已超過4580萬，排世界第三位。

4.計算機的發展趨勢

計算機已經實現了從「數字計算」到「信息處理」的轉變。目前，電子計算機的發展趨勢，可以概括為「巨型」、「微型」、「網路」、「智能」四個方面。雖然目前我們還不能對未來計算機的發展提出十分確切的時間表，但其發展趨勢已經很明朗，即發展高性能計算和提高計算性能。

發展高性能計算可以有兩條途徑，一是基於現有的半導體集成電路技術和微處理機技術，通過提高並行處理能力來實現；二是突破硅半導體器件的物理限制，發展非傳統的新技術，包括超導計算、量子計算、生物計算與光計算等。

提高計算性能也可以有兩條途徑，一是硬體方面，即研製超高性能器件或部件，如量子器件、超導晶元、光互連和光存儲部件、生物分子部件等；二是計算模型和演算法設計方面，從根本上突破馮·諾依曼計算機和電子技術的局限，如量子計算和DNA計算模型，都為求解復雜問題開辟了嶄新的思路。

5.計算機科學的研究領域

計算機科學注重理論和抽象，計算機工程注重抽象和設計，實際上兩者之間本質上沒有區別。從研究的范疇，統稱為計算機學科。目前，研究所涉及的領域十分廣泛，包括：計算機系統結構、程序設計科學與方法論、軟體工程理論、人工智慧與知識處理、網路和資料庫、計算機輔助技術、理論計算機科學和計算機科學史的研究等。計算機科學與技術對人類社會的影響，超過數學作為基本文化基礎給人類文化帶來的影響和物理學對近代工業革命產生的人類文明帶來的影響。可以預見，計算機的發展必然給人類社會帶來更加美好的未來。

二、計算機的分類

計算機種類繁多，可以按處理數據的形態、使用范圍、規模和功能等不同角度分類。

1.按處理數據的形態分類

（1）數字計算機 數字計算機以二進制數據0和1作為處理對象，是不連續的數字量，處理結果也是以數字形式輸出。優點是精度高、存儲量大、通用性強。我們通常使用的計算機大多是數字計算機。

（2）模擬計算機 模擬計算機以連續的數據作為處理對象，是以電信號幅值來模擬數值或物理量的大小，如電壓、電流、溫度等，處理結果也是以連續的數據輸出。模擬計算機解題速度快，但不如數字計算機精度高、且通用性差。模擬計算機通常以繪圖或量表形式輸出結果。

（3）混合計算機 混合計算機是集數字計算機模擬計算機功能優點為一身的計算機。

2.按使用范圍分類

（1）通用計算機

（2）專用計算機

3.按規模和功能分類

（1）超級計算機（Supercomputer）

（2）大型計算機（Mainframe）

（3）小型計算機（Minicomputer）

（4）微型計算機（Microcomputer）

三、計算機的特點

（1）運算速度快

（2）計算精度高

（3）存儲容量大

（4）自動化程度高

（5）邏輯判斷能力強

（6）具有廣泛的通用性

四、計算機的主要用途

計算機的用途大概可以歸納為以下幾個方面：

（1）數值計算 在科學研究、技術開發、工程設計等進行的科學計算。

（2）數據處理 實現對數值、文字、圖表等信息數據及時地加以記錄、整理、檢索、分類、統計、綜合和傳遞。適用於事務處理、辦公自動化、電子數據交換、信息管理、決策支持中的數據處理。

（3）過程式控制制 包括工業自動監測、自動控制、智能控制等實時控制。

（4）計算機輔助設計（CAD-Computer Aided Design）包括計算機輔助製造（CAM）、計算機輔助測試（CAT）、計算機輔助教學（CAI）等，可提高設計質量和自動化程度，縮短設計周期、降低生產成本。

（5）人工智慧（AI-Artificial Intelligence）用於復雜系統的模擬模擬，實現自然語言理解與生成、定理機器證明、自動程序設計、自動翻譯、圖像識別、聲音識別、疾病診斷，以及各種專家系統和機器人構造等。近年來人工智慧的研究開始走向實用化，成為計算機應用研究的前沿學科。

（6）計算機網路及網路通信 提供地區間、國際間的通信與各種數據的傳遞與處理，實現軟體、硬體信息資源共享。

（7）多媒體技術 實現集聲、文、圖、像一體化，更接近人類習慣的信息交流方式，廣泛應用於文化、教育、娛樂、家庭應用等領域。

『陸』 演算法與程序有何區別

01 演算法是為一個問題或一類問題給出的解決方法與具體步驟，是對問題求解過程的一種准確而完整的邏輯描述。程序則是為了用計算機解題或控制某一過程而編排的一系列指令的集合。程序不等於演算法。但是，通過程序設計可以在計算機上實現演算法。

你可能解答過一個有趣的問題——“人、狼、羊過河”問題。有個人帶著三隻狼、三隻羊，要過河去。有一條小船。船上除了運載一個人外，至多再載狼或羊中的任意兩只。但難點是：當人不在場時，如果狼的數量大於等於羊的數量，那麼羊會被狼吃掉。為了安全過河，你有什麼辦法呢？

解決它的演算法有多個，其中一個解決方案是這樣的：

開始，運一隻狼過河，空船回來；

接著，運一隻狼和一隻羊再過河，到對岸後，再運兩只狼回來；

然後，運兩只羊過河，空船回來；

最後，分兩次將狼全部運過河；

由此，過河問題就得以解決了。

可見，演算法是為一個問題或一類問題給出的解決方法與具體步驟，是對問題求解過程的一種准確而完整的邏輯描述。它由有限步驟的操作序列組成，代表著用系統的方法描述解決問題的策略機制。

演算法是一組嚴謹定義運算順序的規則，每一個規則都是有效的、明確的，此順序必須在有限的次數下終止。在上面的過河問題中，如果第一步中改為：“運一隻狼過河，再運這只狼回來”，那麼，說明人沒找到好辦法，在反復進行無用操作。此類演算法，是失敗的，永遠也實現不了既定目標。

演算法描述，一般可以使用漢、英等自然語言，比較通俗易懂。也可以使用流程圖、偽代碼表格等其他工具。

在古代，演算法通常用於數值計算。中國古代的籌算口訣、珠算口訣及其執行規則就是演算法的雛形。它所解決的是數值計算問題。現代演算法，已超出數值計算范圍。

程序則是為了用計算機解題或控制某一過程而編排的一系列指令的集合。這些指令，可以是計算機的機器指令，也可以是匯編語言和高級程序設計語言。

程序不等於演算法。但是，通過程序設計可以在計算機上實現演算法。在實際應用中，也許只需一條（組）程序設計語句，就可以完成演算法的基本要素處理，包括數據對象的運算和操作，以及順序、選擇、循環結構的控制。通過程序模塊設計，可以實現演算法中的遞推、遞歸、迭代等一系列基本演算法，也包括形式演繹、數據結構、數論圖論、加密解密、科學決策等復雜演算法。

因此，運用計算機解決問題的過程，通常可以分成三個階段：分析問題、設計演算法和編製程序實現演算法。由於計算機運算速度快，存儲數據量大，大大提高了演算法實現效率。

『柒』 求下面數據結構試題的答案...

一．

1,復雜性2.線性結構非線性結構

3．可以按序號隨機存取4.數據元素

5.後進先出6.n7.只能在隊頭進行

9.長度1深度1

10-+A*BC/DE

11

12頂點Vp到頂點Vq之間的路徑是指定的序列Vp，Vi1，Vi2•••Vim，Vq。

13n（n-2）/214n—1152n—1

17一種存儲結構

19可以從表中任意結點開始遍歷整個鏈表；只用一個指向尾結點的指針對鏈表頭、尾進行操作，提高了效率。

20棧是僅限制在表的一端進行插入和刪除的運算的線性表，是一種操作受限的線性表。

二．

1演算法的時間復雜度和空間復雜度

2.隊列

3.

4嵌套集合表示法，廣義表表示法，凹入表示法

5.456.S(1)X(1)S(2)S(3)X(3)S(4)X(4)X(2)

7（1）O（nˆ2）

（2）O（nˆ2）

8.

哈夫曼樹：

WPL=2*5+4*5+5*4+16*3+8*3+7*3+30=173

9.鄰接矩陣：

鄰接表：

10.二叉樹：

前序：ABCEFD

中序：BEFCDA

後序：FEDCBA

『捌』 全國計算機等級考試二級C,VB等等不同語言筆試部分的公共基礎知識考試內容是一樣的嗎

第一章 數據結構與演算法
經過對部分考生的調查以及對近年真題的總結分析，筆試部分經常考查的是演算法復雜度、數據結構的概念、棧、二叉樹的遍歷、二分法查找，讀者應對此部分進行重點學習。
詳細重點學習知識點：
1．演算法的概念、演算法時間復雜度及空間復雜度的概念
2．數據結構的定義、數據邏輯結構及物理結構的定義
3．棧的定義及其運算、線性鏈表的存儲方式
4．樹與二叉樹的概念、二叉樹的基本性質、完全二叉樹的概念、二叉樹的遍歷
5．二分查找法
6．冒泡排序法

1.1演算法
考點1 演算法的基本概念
考試鏈接：
考點1在筆試考試中考核的幾率為30%，主要是以填空題的形式出現，分值為2分，此考點為識記內容，讀者還應該了解演算法中對數據的基本運算。
計算機解題的過程實際上是在實施某種演算法，這種演算法稱為計算機演算法。
1．演算法的基本特徵：可行性、確定性、有窮性、擁有足夠的情報。
2．演算法的基本要素：
（1）演算法中對數據的運算和操作
一個演算法由兩種基本要素組成：一是對數據對象的運算和操作；二是演算法的控制結構。
在一般的計算機系統中，基本的運算和操作有以下4類：算術運算、邏輯運算、關系運算和數據傳輸。
（2）演算法的控制結構：演算法中各操作之間的執行順序稱為演算法的控制結構。
描述演算法的工具通常有傳統流程圖、N-S結構化流程圖、演算法描述語言等。一個演算法一般都可以用順序、選擇、循環3種基本控制結構組合而成。
考點2 演算法復雜度
考試鏈接：
考點2在筆試考試中，是一個經常考查的內容，在筆試考試中出現的幾率為70%，主要是以選擇的形式出現，分值為2分，此考點為重點識記內容，讀者還應該識記演算法時間復雜度及空間復雜度的概念。
1.演算法的時間復雜度
演算法的時間復雜度是指執行演算法所需要的計算工作量。
同一個演算法用不同的語言實現，或者用不同的編譯程序進行編譯，或者在不同的計算機上運行，效率均不同。這表明使用絕對的時間單位衡量演算法的效率是不合適的。撇開這些與計算機硬體、軟體有關的因素，可以認為一個特定演算法"運行工作量"的大小，只依賴於問題的規模（通常用整數n表示），它是問題規模的函數。即
演算法的工作量=f（n）
2.演算法的空間復雜度
演算法的空間復雜度是指執行這個演算法所需要的內存空間。
一個演算法所佔用的存儲空間包括演算法程序所佔的空間、輸入的初始數據所佔的存儲空間以及演算法執行過程中所需要的額外空間。其中額外空間包括演算法程序執行過程中的工作單元以及某種數據結構所需要的附加存儲空間。如果額外空間量相對於問題規模來說是常數，則稱該演算法是原地工作的。在許多實際問題中，為了減少演算法所佔的存儲空間，通常採用壓縮存儲技術，以便盡量減少不必要的額外空間。

疑難解答：演算法的工作量用什麼來計算？
演算法的工作量用演算法所執行的基本運算次數來計算，而演算法所執行的基本運算次數是問題規模的函數，即演算法的工作量=f（n），其中n是問題的規模。
1.2數據結構的基本概念
考點3 數據結構的定義
考試鏈接：
考點3在筆試考試中，是一個經常考查的內容，在筆試考試中出現的幾率為70%，主要是以選擇的形式出現，分值為2分，此考點為識記內容，讀者還應該識記數據的邏輯結構和存儲結構的概念。
數據結構作為計算機的一門學科，主要研究和討論以下三個方面：
（1）數據集合中個數據元素之間所固有的邏輯關系，即數據的邏輯結構；
（2）在對數據元素進行處理時，各數據元素在計算機中的存儲關系，即數據的存儲結構；
（3）對各種數據結構進行的運算。
數據：是對客觀事物的符號表示，在計算機科學中是指所有能輸入到計算機中並被計算機程序處理的符號的總稱。
數據元素：是數據的基本單位，在計算機程序中通常作為一個整體進行考慮和處理。
數據對象：是性質相同的數據元素的集合，是數據的一個子集。
數據的邏輯結構是對數據元素之間的邏輯關系的描述，它可以用一個數據元素的集合和定義在此集合中的若干關系來表示。數據的邏輯結構有兩個要素：一是數據元素的集合，通常記為D；二是D上的關系，它反映了數據元素之間的前後件關系，通常記為R。一個數據結構可以表示成
B=（D，R）
其中B表示數據結構。為了反映D中各數據元素之間的前後件關系，一般用二元組來表示。
數據的邏輯結構在計算機存儲空間中的存放形式稱為數據的存儲結構（也稱數據的物理結構）。
由於數據元素在計算機存儲空間中的位置關系可能與邏輯關系不同，因此，為了表示存放在計算機存儲空間中的各數據元素之間的邏輯關系（即前後件關系），在數據的存儲結構中，不僅要存放各數據元素的信息，還需要存放各數據元素之間的前後件關系的信息。
一種數據的邏輯結構根據需要可以表示成多種存儲結構，常用的存儲結構有順序、鏈接、索引等存儲結構。而採用不同的存儲結構，其數據處理的效率是不同的。因此，在進行數據處理時，選擇合適的存儲結構是很重要的。
考點4 線性結構與非線性結構
考試鏈接：
考點4在筆試考試中，雖然說不是考試經常考查的內容，但讀者還是對此考點有所了解，在筆試考試中出現的幾率為30%，主要是以填空題出現的形式出現，分值為2分，此考點為識記內容。
根據數據結構中各數據元素之間前後件關系的復雜程度，一般將數據結構分為兩大類型：線性結構與非線性結構。如果一個非空的數據結構滿足下列兩個條件：
（1）有且只有一個根結點；
（2）每一個結點最多有一個前件，也最多有一個後件。
則稱該數據結構為線性結構。線性結構又稱線性表。在一個線性結構中插入或刪除任何一個結點後還應是線性結構。如果一個數據結構不是線性結構，則稱之為非線性結構。

疑難解答：空的數據結構是線性結構還是非線性結構？
一個空的數據結構究竟是屬於線性結構還是屬於非線性結構，這要根據具體情況來確定。如果對該數據結構的演算法是按線性結構的規則來處理的，則屬於線性結構；否則屬於非線性結構。
1.3棧及線性鏈表
考點5 棧及其基本運算
考試鏈接：
考點5在筆試考試中，是一個必考的內容，在筆試考試中出現的幾率為100%，主要是以選擇的形式出現，分值為2分，此考點為重點掌握內容，讀者應該掌握棧的運算 。
1．棧的基本概念
棧是限定只在一端進行插入與刪除的線性表，通常稱插入、刪除的這一端為棧頂，另一端為棧底。當表中沒有元素時稱為空棧。棧頂元素總是後被插入的元素，從而也是最先被刪除的元素；棧底元素總是最先被插入的元素，從而也是最後才能被刪除的元素。棧是按照"先進後出"或"後進先出"的原則組織數據的。
2．棧的順序存儲及其運算
用一維數組S（1∶m）作為棧的順序存儲空間，其中m為最大容量。
在棧的順序存儲空間S（1∶m）中，S（bottom）為棧底元素，S（top）為棧頂元素。top=0表示棧空；top=m表示棧滿。
棧的基本運算有三種：入棧、退棧與讀棧頂元素。
（1）入棧運算：入棧運算是指在棧頂位置插入一個新元素。首先將棧頂指針加一（即top加1），然後將新元素插入到棧頂指針指向的位置。當棧頂指針已經指向存儲空間的最後一個位置時，說明棧空間已滿，不可能再進行入棧操作。這種情況稱為棧"上溢"錯誤。
（2）退棧運算：退棧是指取出棧頂元素並賦給一個指定的變數。首先將棧頂元素（棧頂指針指向的元素）賦給一個指定的變數，然後將棧頂指針減一（即top減1）。當棧頂指針為0時，說明棧空，不可進行退棧操作。這種情況稱為棧的"下溢"錯誤。
（3）讀棧頂元素：讀棧頂元素是指將棧頂元素賦給一個指定的變數。這個運算不刪除棧頂元素，只是將它賦給一個變數，因此棧頂指針不會改變。當棧頂指針為0時，說明棧空，讀不到棧頂元素。

小技巧：棧是按照"先進後出"或"後進先出"的原則組織數據，但是出棧方式有多種選擇，在考題中經常考查各種不同的出棧方式。
考點6 線性鏈表的基本概念
考試鏈接：
考點6在筆試考試中出現的幾率為30%，主要是以選擇的形式出現，分值為2分，此考點為識記內容。重點識記結點的組成。
在鏈式存儲方式中，要求每個結點由兩部分組成：一部分用於存放數據元素值，稱為數據域，另一部分用於存放指針，稱為指針域。其中指針用於指向該結點的前一個或後一個結點（即前件或後件）。
鏈式存儲方式既可用於表示線性結構，也可用於表示非線性結構。
（1）線性鏈表
線性表的鏈式存儲結構稱為線性鏈表。
在某些應用中，對線性鏈表中的每個結點設置兩個指針，一個稱為左指針，用以指向其前件結點；另一個稱為右指針，用以指向其後件結點。這樣的表稱為雙向鏈表。
（2）帶鏈的棧
棧也是線性表，也可以採用鏈式存儲結構。帶鏈的棧可以用來收集計算機存儲空間中所有空閑的存儲結點，這種帶鏈的棧稱為可利用棧。

疑難解答：在鏈式結構中，存儲空間位置關系與邏輯關系是什麼？
在鏈式存儲結構中，存儲數據結構的存儲空間可以不連續，各數據結點的存儲順序與數據元素之間的邏輯關系可以不一致，而數據元素之間的邏輯關系是由指針域來確定的。
1.4樹與二叉樹
考點7 樹與二叉樹及其基本性質
考試鏈接：
考點7在筆試考試中，是一個必考的內容，在筆試考試中出現的幾率為100%，主要是以選擇的形式出現，有時也有出現在填空題中，分值為2分，此考點為重點掌握內容。重點識記樹及二叉樹的性質。
誤區警示：
滿二叉樹也是完全二叉樹，而完全二叉樹一般不是滿二叉樹。應該注意二者的區別。
1、樹的基本概念
樹(tree）是一種簡單的非線性結構。在樹結構中，每一個結點只有一個前件，稱為父結點，沒有前件的結點只有一個，稱為樹的根結點。每一個結點可以有多個後件，它們稱為該結點的子結點。沒有後件的結點稱為葉子結點。
在樹結構中，一個結點所擁有的後件個數稱為該結點的度。葉子結點的度為0。在樹中，所有結點中的最大的度稱為樹的度。
2、二叉樹及其基本性質
（1）二叉樹的定義
二叉樹是一種很有用的非線性結構，具有以下兩個特點：
①非空二叉樹只有一個根結點；
②每一個結點最多有兩棵子樹，且分別稱為該結點的左子樹和右子樹。
由以上特點可以看出，在二叉樹中，每一個結點的度最大為2，即所有子樹（左子樹或右子樹）也均為二叉樹，而樹結構中的每一個結點的度可以是任意的。另外，二叉樹中的每個結點的子樹被明顯地分為左子樹和右子樹。在二叉樹中，一個結點可以只有左子樹而沒有右子樹，也可以只有右子樹而沒有左子樹。當一個結點既沒有左子樹也沒有右子樹時，該結點即為葉子結點。
（2）二叉樹的基本性質
二叉樹具有以下幾個性質：
性質1：在二叉樹的第k層上，最多有2k-1（k≥1）個結點；
性質2：深度為m的二叉樹最多有2m-1個結點；
性質3：在任意一棵二叉樹中，度為0的結點（即葉子結點）總是比度為2的結點多一個。
性質4：具有n個結點的二叉樹，其深度至少為〔log2n〕+1，其中〔log2n〕表示取log2n的整數部分。

小技巧：在二叉樹的遍歷中，無論是前序遍歷，中序遍歷還是後序遍歷，二叉樹的葉子結點的先後順序都是不變的。
3、滿二叉樹與完全二叉樹
滿二叉樹是指這樣的一種二叉樹：除最後一層外，每一層上的所有結點都有兩個子結點。在滿二叉樹中，每一層上的結點數都達到最大值，即在滿二叉樹的第k層上有2k-1個結點，且深度為m的滿二叉樹有2m－1個結點。
完全二叉樹是指這樣的二叉樹：除最後一層外，每一層上的結點數均達到最大值；在最後一層上只缺少右邊的若干結點。
對於完全二叉樹來說，葉子結點只可能在層次最大的兩層上出現：對於任何一個結點，若其右分支下的子孫結點的最大層次為p，則其左分支下的子孫結點的最大層次或為p，或為p+1。
完全二叉樹具有以下兩個性質：
性質5:具有n個結點的完全二叉樹的深度為〔log2n〕+1。
性質6:設完全二叉樹共有n個結點。如果從根結點開始，按層次（每一層從左到右）用自然數1，2，……，n給結點進行編號，則對於編號為k（k=1，2，……，n）的結點有以下結論：
①若k=1，則該結點為根結點，它沒有父結點；若k>1，則該結點的父結點編號為INT（k/2）。
②若2k≤n，則編號為k的結點的左子結點編號為2k；否則該結點無左子結點（顯然也沒有右子結點）。
③若2k+1≤n，則編號為k的結點的右子結點編號為2k+1；否則該結點無右子結點。
考點8 二叉樹的遍歷
考試鏈接：
考點8在筆試考試中考核幾率為30%，分值為2分，讀者應該熟練掌握各種遍歷的具體演算法，能由兩種遍歷的結果推導另一種遍歷的結果。
在遍歷二叉樹的過程中，一般先遍歷左子樹，再遍歷右子樹。在先左後右的原則下，根據訪問根結點的次序，二叉樹的遍歷分為三類：前序遍歷、中序遍歷和後序遍歷。
（1）前序遍歷：先訪問根結點、然後遍歷左子樹，最後遍歷右子樹；並且，在遍歷左、右子樹時，仍然先訪問根結點，然後遍歷左子樹，最後遍歷右子樹。
（2）中序遍歷：先遍歷左子樹、然後訪問根結點，最後遍歷右子樹；並且，在遍歷左、右子樹時，仍然先遍歷左子樹，然後訪問根結點，最後遍歷右子樹。
（3）後序遍歷：先遍歷左子樹、然後遍歷右子樹，最後訪問根結點；並且，在遍歷左、右子樹時，仍然先遍歷左子樹，然後遍歷右子樹，最後訪問根結點。

疑難解答：樹與二叉樹的不同之處是什麼？
在二叉樹中，每一個結點的度最大為2，即所有子樹（左子樹或右子樹）也均為二叉樹，而樹結構中的每一個結點的度可以是任意的。
1.5查找技術
考點9 順序查找
考試鏈接：
考點9在筆試考試中考核幾率在30%，一般出現選擇題中，分值為2分，讀者應該具體掌握順序查找的演算法。
查找是指在一個給定的數據結構中查找某個指定的元素。從線性表的第一個元素開始，依次將線性表中的元素與被查找的元素相比較，若相等則表示查找成功；若線性表中所有的元素都與被查找元素進行了比較但都不相等，則表示查找失敗。
在下列兩種情況下也只能採用順序查找：
（1）如果線性表為無序表，則不管是順序存儲結構還是鏈式存儲結構，只能用順序查找。
（2）即使是有序線性表，如果採用鏈式存儲結構，也只能用順序查找。
考點10 二分法查找
考試鏈接：
考點10在筆試考試中考核幾率為30%，一般出現填空題中，分值為2分，考核比較多查找的比較次數，讀者應該具體掌握二分查找法的演算法。
二分法只適用於順序存儲的，按非遞減排列的有序表，其方法如下：
設有序線性表的長度為n，被查找的元素為i，
（1）將i與線性表的中間項進行比較；
（2）若i與中間項的值相等，則查找成功；
（3）若i小於中間項，則在線性表的前半部分以相同的方法查找；
（4）若i大於中間項，則在線性表的後半部分以相同的方法查找。

疑難解答：二分查找法適用於哪種情況？
二分查找法只適用於順序存儲的有序表。在此所說的有序表是指線性表中的元素按值非遞減排列（即從小到大，但允許相鄰元素值相等）。
這個過程一直進行到查找成功或子表長度為0為止。
對於長度為n的有序線性表，在最壞情況下，二分查找只需要比較log2n次。
1.6排序技術
考點11 交換類排序法
考試鏈接:
考點11屬於比較難的內容，一般以選擇題的形式考查，考核幾率為30%，分值約為2分，讀者應該熟練掌握幾種排序演算法的基本過程。
冒泡排序法和快速排序法都屬於交換類排序法。
（1）冒泡排序法
首先，從表頭開始往後掃描線性表，逐次比較相鄰兩個元素的大小，若前面的元素大於後面的元素，則將它們互換，不斷地將兩個相鄰元素中的大者往後移動，最後最大者到了線性表的最後。
然後，從後到前掃描剩下的線性表，逐次比較相鄰兩個元素的大小，若後面的元素小於前面的元素，則將它們互換，不斷地將兩個相鄰元素中的小者往前移動，最後最小者到了線性表的最前面。
對剩下的線性表重復上述過程，直到剩下的線性表變空為止，此時已經排好序。
在最壞的情況下，冒泡排序需要比較次數為n（n－1）/2。
（2）快速排序法
它的基本思想是：任取待排序序列中的某個元素作為基準（一般取第一個元素），通過一趟排序，將待排元素分為左右兩個子序列，左子序列元素的排序碼均小於或等於基準元素的排序碼，右子序列的排序碼則大於基準元素的排序碼，然後分別對兩個子序列繼續進行排序，直至整個序列有序。

疑難解答：冒泡排序和快速排序的平均執行時間分別是多少？
冒泡排序法的平均執行時間是O（n2），而快速排序法的平均執行時間是O（nlog2n）。

1.7 例題詳解
一、選擇題
【例1】演算法的時間復雜度取決於_______。（考點2）
A）問題的規模 B）待處理的數據的初態
C）問題的難度 D）A）和B）
解析：演算法的時間復雜度不僅與問題的規模有關，在同一個問題規模下，而且與輸入數據有關。即與輸入數據所有的可能取值范圍、輸入各種數據或數據集的概率有關。
答案：D）
【例2】在數據結構中，從邏輯上可以把數據結構分成_______。（考點3）
A）內部結構和外部結構 B）線性結構和非線性結構
C）緊湊結構和非緊湊結構 D）動態結構和靜態結構
解析：邏輯結構反映數據元素之間的邏輯關系，線性結構表示數據元素之間為一對一的關系，非線性結構表示數據元素之間為一對多或者多對一的關系，所以答案為B）。
答案：B）
【例3】以下_______不是棧的基本運算。（考點5）
A）判斷棧是否為素空 B）將棧置為空棧
C）刪除棧頂元素 D）刪除棧底元素
解析：棧的基本運算有：入棧，出棧（刪除棧頂元素），初始化、置空、判斷棧是否為空或滿、提取棧頂元素等，對棧的操作都是在棧頂進行的。
答案：D）
【例4】鏈表不具備的特點是_______。（考點6）
A）可隨機訪問任意一個結點 B）插入和刪除不需要移動任何元素
C）不必事先估計存儲空間 D）所需空間與其長度成正比
解析：順序表可以隨機訪問任意一個結點，而鏈表必須從第一個數據結點出發，逐一查找每個結點。所以答案為A）。
答案：A）
【例5】已知某二叉樹的後序遍歷序列是DACBE，中序遍歷序列是DEBAC，則它的前序遍歷序列是_______。（考點8）
A）ACBED B）DEABC
C）DECAB D）EDBAC
解析：後序遍歷的順序是"左子樹－右子樹－根結點"；中序遍歷順序是"左子樹－根結點－右子樹"；前序遍歷順序是"根結點－左子樹－右子樹"。根據各種遍歷演算法，不難得出前序遍歷序列是EDBAC。所以答案為D）。
答案：D）
【例6】設有一個已按各元素的值排好序的線性表（長度大於2），對給定的值k，分別用順序查找法和二分查找法查找一個與k相等的元素，比較的次數分別是s和b，在查找不成功的情況下，s和b的關系是_______。（考點9）
A）s=b B）s>b C）s<b D）s≥b
解析：對於順序查找，查找不成功時和給定關鍵字比較的次數為n+1。二分查找查找不成功的關鍵字比較次數為〔log2n〕+1。當n≥2時，顯然n+1>〔log2n〕+1。
答案：B）
【例7】在快速排序過程中，每次劃分，將被劃分的表（或子表）分成左、右兩個子表，考慮這兩個子表，下列結論一定正確的是_______。（考點11）
A）左、右兩個子表都已各自排好序
B）左邊子表中的元素都不大於右邊子表中的元素
C） 左邊子表的長度小於右邊子表的長度
D）左、右兩個子表中元素的平均值相等
解析：快速排序基本思想是：任取待排序表中的某個元素作為基準（一般取第一個元素），通過一趟排序，將待排元素分為左右兩個子表，左子表元素的排序碼均小於或等於基準元素的排序碼，右子表的排序碼則大於基準元素的排序碼，然後分別對兩個子表繼續進行排序，直至整個表有序。
答案：B）
二、填空題
【例1】問題處理方案的正確而完整的描述稱為_______。（考點1）
解析：計算機解題的過程實際上是在實施某種演算法，這種演算法稱為計算機演算法。
答案：演算法
【例2】一個空的數據結構是按線性結構處理的，則屬於_______。（考點4）
解析：一個空的數據結構是線性結構或是非線性結構，要根據具體情況而定。如果對數據結構的運算是按線性結構來處理的，則屬於線性結構，否則屬於非線性結構。
答案：線性結構
【例3】設樹T的度為4，其中度為1、2、3和4的結點的個數分別為4、2、1、1，則T中葉子結點的個數為_______。（考點7）
解析：根據樹的性質：樹的結點數等於所有結點的度與對應的結點個數乘積之和加1。
因此樹的結點數為1×4＋2×2＋3×1＋4×1＋1＝16。葉子結點數目等於樹結點總數減去度不為0的結點數之和，即16－（4＋2＋1＋1）＝8。
答案：8
【例4】二分法查找的存儲結構僅限於_______且是有序的。（考點10）
解析：二分查找，也稱折半查找，它是一種高效率的查找方法。但二分查找有條件限制：要求表必須用順序存儲結構，且表中元素必須按關鍵字有序(升序或降序均可）。
答案：順序存儲結構

『玖』 什麼是演算法

是指解題方案的准確而完整的描述，是一系列解決問題的清晰指令，演算法代表著用系統的方法描述解決問題的策略機制。