考研計算機復(fù)試面試題總結(jié)

概念問題C++/數(shù)據(jù)結(jié)構(gòu)1、簡述你對“面向?qū)ο蟆焙汀懊嫦蜻^程”編程思想的認(rèn)識與思考用就可以了。面向過程就是分析出解決問題所需要的步驟，然后用函數(shù)把這些步驟一步一步實現(xiàn)，使用的時候一個一個依次調(diào)面向?qū)ο笫前褬?gòu)成問題事務(wù)分解成各個對象，建立對象的目的不是為了完成一個步驟，而是為了描敘某個事物在整個解決問題的步驟中的行為。例如五子棋，面向過程的設(shè)計思路就是首先分析問題的步驟：1、開始游戲，2、黑子先走，3、繪制畫面，4、判斷輸贏，5、輪到白子，6、繪制畫面，7、判斷輸贏，8、返回步驟2，9、輸出最后結(jié)果。把上面每個步驟用分別的函數(shù)來實現(xiàn)，問題就解決了。而面向?qū)ο蟮脑O(shè)計則是從另外的思路來解決問題。整個五子棋可以分為1、黑白雙方，這兩方的行為是一模一樣的，2、棋盤系統(tǒng)，負(fù)責(zé)繪制畫面，3、規(guī)則系統(tǒng)，負(fù)責(zé)判定諸如犯規(guī)、輸贏等。第一類對象（玩家對象）負(fù)責(zé)接受用戶輸入，并告知第二類對象（棋盤對象）棋子布局的變化，棋盤對象接收到了棋子的i變化就要負(fù)責(zé)在屏幕上面顯示出這種變化，同時利用第三類對象（規(guī)則系統(tǒng)）來對棋局進(jìn)行判定。可以明顯地看出，面向?qū)ο笫且怨δ軄韯澐謫栴}，而不是步驟。同樣是繪制棋局，這樣的行為在面向過程的設(shè)計中分散在了總多步驟中，很可能出現(xiàn)不同的繪制版本，因為通常設(shè)計人員會考慮到實際情況進(jìn)行各種各樣的簡化。而面向?qū)ο蟮脑O(shè)計中，繪圖只可能在棋盤對象中出現(xiàn)，從而保證了繪圖的統(tǒng)一。功能上的統(tǒng)一保證了面向?qū)ο笤O(shè)計的可擴展性。比如我要加入悔棋的功能，如果要改動面向過程的設(shè)計，那么從輸入到判斷到顯示這一連串的步驟都要改動，甚至步驟之間的循序都要進(jìn)行大規(guī)模調(diào)整。如果是面向?qū)ο蟮脑?，只用改動棋盤對象就行了，棋盤系統(tǒng)保存了黑白雙方的棋譜，簡單回溯就可以了，而顯示和規(guī)則判斷則不用顧及，同時整個對對象功能的調(diào)用順序都沒有變化，改動只是局部的。再比如我要把這個五子棋游戲改為圍棋游戲，如果你是面向過程設(shè)計，那么五子棋的規(guī)則就分布在了你的程序的每一個角落，要改動還不如重寫。但是如果你當(dāng)初就是面向?qū)ο蟮脑O(shè)計，那么你只用改動規(guī)則對象就可以了，五子棋和圍棋的區(qū)別不就是規(guī)則嗎？（當(dāng)然棋盤大小好像也不一樣，但是你會覺得這是一個難題嗎？直接在棋盤對象中進(jìn)行一番小改動就可以了。）而下棋的大致步驟從面向?qū)ο蟮慕嵌葋砜礇]有任何變化。當(dāng)然，要達(dá)到改動只是局部的需要設(shè)計的人有足夠的經(jīng)驗，使用對象不能保證你的程序就是面向?qū)ο?，初學(xué)者或者很蹩腳的程序員很可能以面向?qū)ο笾摱忻嫦蜻^程之實，這樣設(shè)計出來的所謂面向?qū)ο蟮某绦蚝茈y有良好的可移植性和可擴展性。2、ADT是什么？簡述你對“數(shù)據(jù)抽象”和“信息隱藏”的認(rèn)識抽象數(shù)據(jù)類型(AbstractDataType簡稱ADT)是指一個數(shù)學(xué)模型以及定義在此數(shù)學(xué)模型上的一組操作。抽象數(shù)據(jù)類型需要通過固有數(shù)據(jù)類型（高級編程語言中已實現(xiàn)的數(shù)據(jù)類型）來實現(xiàn)。抽象數(shù)據(jù)類型是與表示無關(guān)的數(shù)據(jù)類型，是一個數(shù)據(jù)模型及定義在該模型上的一組運算。對一個抽象數(shù)據(jù)類型進(jìn)行定義時，必須給出它的名字及各運算的運算符名，即函數(shù)名，并且規(guī)定這些函數(shù)的參數(shù)性質(zhì)。一旦定義了一個抽象數(shù)據(jù)類型及具體實現(xiàn)，程序設(shè)計中就可以像使用基本數(shù)據(jù)類型那樣，十分方便地使用抽象數(shù)據(jù)類型。抽象數(shù)據(jù)類型通過類(class)實現(xiàn)程序設(shè)計語言對抽象數(shù)據(jù)類型的支持是指允許用戶自定義具有如下特征的數(shù)據(jù)類型：1.模塊封裝：Therepresentationof,andoperationson,objectsofthetypearedefinedinasinglesyntacticunit2.信息隱蔽：Therepresentationofobjectsofthetypeishiddenfromtheprogramunitsthatusetheseobjects,sotheonlyoperationspossiblearethoseprovidedinthetype'sdefinition3、const和static有什么作用？const是一個C和C++語言的關(guān)鍵字，它限定一個變量不允許被改變，即只讀。使用const在一定程度上可以提高程序的安全性和可靠性，也便于實現(xiàn)對此進(jìn)行優(yōu)化（如把只讀對象放入ROM中）。const作為類型限定符，是類型的一部分。4、友元關(guān)系的利與弊如果將一個函數(shù)或一個類聲明為另一個類的友元，那么它就可以直接存取這個類對象中的各種數(shù)據(jù)，而不必在意這些數(shù)據(jù)的封裝級別，即無論是private的，protected的，還是public的，有錢同使，有難同當(dāng)。5、C++多態(tài)的實現(xiàn)1.用virtual關(guān)鍵字申明的函數(shù)叫做虛函數(shù)，虛函數(shù)肯定是類的成員函數(shù)。2.存在虛函數(shù)的類都有一個一維的虛函數(shù)表叫做虛表。類的對象有一個指向虛表開始的虛指針。虛表是和類對應(yīng)的，虛表指針是和對象對應(yīng)的。3.多態(tài)性是一個接口多種實現(xiàn)，是面向?qū)ο蟮暮诵?。分為類的多態(tài)性和函數(shù)的多態(tài)性。4.多態(tài)用虛函數(shù)來實現(xiàn)，結(jié)合動態(tài)綁定。5.純虛函數(shù)是虛函數(shù)再加上=0。6.抽象類是指包括至少一個純虛函數(shù)的類。構(gòu)造函數(shù)順序：基類構(gòu)造函數(shù)派生類構(gòu)造函數(shù)前面輸出的結(jié)果是因為編譯器在編譯的時候，就已經(jīng)確定了對象調(diào)用的函數(shù)的地址，要解決這個問題就要使用遲綁定（latebinding）技術(shù)。當(dāng)編譯器使用遲綁定時，就會在運行時再去確定對象的類型以及正確的調(diào)用函數(shù)。而要讓編譯器采用遲綁定，就要在基類中聲明函數(shù)時使用virtual關(guān)鍵字（注意，這是必須的，很多學(xué)員就是因為沒有使用虛函數(shù)而寫出很多錯誤的例子），這樣的函數(shù)我們稱為虛函數(shù)。一旦某個函數(shù)在基類中聲明為virtual，那么在所有的派生類中該函數(shù)都是virtual，而不需要再顯式地聲明為virtual。前面輸出的結(jié)果是因為編譯器在編譯的時候，就已經(jīng)確定了對象調(diào)用的函數(shù)的地址，要解決這個問題就要使用遲綁定（latebinding）技術(shù)。當(dāng)編譯器使用遲綁定時，就會在運行時再去確定對象的類型以及正確的調(diào)用函數(shù)。而要讓編譯器采用遲綁定，就要在基類中聲明函數(shù)時使用virtual關(guān)鍵字（注意，這是必須的，很多學(xué)員就是因為沒有使用虛函數(shù)而寫出很多錯誤的例子），這樣的函數(shù)我們稱為虛函數(shù)。一旦某個函數(shù)在基類中聲明為virtual，那么在所有的派生類中該函數(shù)都是virtual，而不需要再顯式地聲明為virtual。編譯器在編譯的時候，發(fā)現(xiàn)基類中有虛函數(shù)，此時編譯器會為每個包含虛函數(shù)的類創(chuàng)建一個虛表（即vtable），該表是一個一維數(shù)組，在這個數(shù)組中存放每個虛函數(shù)的地址。那么如何定位虛表呢？編譯器另外還為每個類的對象提供了一個虛表指針（即vptr），這個指針指向了對象所屬類的虛表。在程序運行時，根據(jù)對象的類型去初始化vptr，從而讓vptr正確的指向所屬類的虛表，從而在調(diào)用虛函數(shù)時，就能夠找到正確的函數(shù)。對于例1-2的程序，由于pAn實際指向的對象類型是fish，因此vptr指向的fish類的vtable，當(dāng)調(diào)用pAn->breathe()時，根據(jù)虛表中的函數(shù)地址找到的就是fish類的breathe()函數(shù)。那么虛表指針在什么時候，或者說在什么地方初始化呢？答案是在構(gòu)造函數(shù)中進(jìn)行虛表的創(chuàng)建和虛表指針的初始化。還記得構(gòu)造函數(shù)的調(diào)用順序嗎，在構(gòu)造子類對象時，要先調(diào)用父類的構(gòu)造函數(shù)，此時編譯器只“看到了”父類，并不知道后面是否后還有繼承者，它初始化父類對象的虛表指針，該虛表指針指向父類的虛表。當(dāng)執(zhí)行子類的構(gòu)造函數(shù)時，子類對象的虛表指針被初始化，指向自身的虛表。對于例2-2的程序來說，當(dāng)fish類的fh對象構(gòu)造完畢后，其內(nèi)部的虛表指針也就被初始化為指向fish類的虛表。在類型轉(zhuǎn)換后，調(diào)用pAn->breathe()，由于pAn實際指向的是fish類的對象，該對象內(nèi)部的虛表指針指向的是fish類的虛表，因此最終調(diào)用的是fish類的breathe()函數(shù)。要注意：對于虛函數(shù)調(diào)用來說，每一個對象內(nèi)部都有一個虛表指針，該虛表指針被初始化為本類的虛表。所以在程序中，不管你的對象類型如何轉(zhuǎn)換，但該對象內(nèi)部的虛表指針是固定的，所以呢，才能實現(xiàn)動態(tài)的對象函數(shù)調(diào)用，這就是C++多態(tài)性實現(xiàn)的原理。6、STL是什么？組成部分和核心作用標(biāo)準(zhǔn)模板庫于1994年2月年正式成為ANSI/ISOC++的一部份，它的出現(xiàn)，促使C++程序員的思維方式更朝向泛型編程（genericprogram）發(fā)展。7、闡述C++在什么情況下必須進(jìn)行運算符重載。？8、為什么說“繼承是C++面向?qū)ο蟮囊粋€主要特征之一”，請做一下簡要說明。?9、請說明函數(shù)模板(FunctionTemplate)和函數(shù)模板實例化(function-templatespecification)的區(qū)別和聯(lián)系。函數(shù)模板實例化在函數(shù)模板為每個類型時首先調(diào)用中，編譯器創(chuàng)建一個實例化。每個實例化是為該類型的該模板化功能的版本。在中，此函數(shù)為類型時，使用此實例化將調(diào)用。如果您有幾個相同的實例化，即使在不同的模塊，因此，只有該實例化的一個副本在可執(zhí)行文件將結(jié)果。函數(shù)參數(shù)將所有參數(shù)的函數(shù)模板允許和參數(shù)，對該參數(shù)不依賴于模板參數(shù)的位置。函數(shù)模板可以通過聲明與特定類型的模板顯式實例化作為參數(shù)。C++中提供了函數(shù)模板，實際上是建立一個通用函數(shù)，其函數(shù)類型和形參類型不具體指定，用一個虛擬的類型來代表，這個通用函數(shù)就成為函數(shù)模板。使用模板的好處就是對于那些函數(shù)體相同的函數(shù)都可以用這個模板來代替，而不必去定義每個具體的函數(shù)去實現(xiàn)。下面通過一個簡單的具體例子（比較兩個數(shù)的大小）來說明：#include<iostream>usingnamespacestd;template<classT>//模板聲明，T為類型參數(shù)TMax(Ta,Tb)//定義一個通用函數(shù)，用T作虛擬的類型名{if(a>b){returna;}elsereturnb;}模板實例化（templateinstantiation）是指在編譯或鏈接時生成函數(shù)模板或類模板的具體實例源代碼。ISOC++定義了兩種模板實例化方法：隱式實例化（當(dāng)使用實例化的模板時自動地在當(dāng)前代碼單元之前插入模板的實例化代碼）、顯式實例化（直接聲明模板實例化）。10、編譯和鏈接的過程源文件的編譯過程包含兩個主要階段，而它們之間的轉(zhuǎn)換是自動的。第一個階段是預(yù)處理階段，在正式的編譯階段之前進(jìn)行。預(yù)處理階段將根據(jù)已放置在文件中的預(yù)處理指令來修改源文件的內(nèi)容。#include指令就是一個預(yù)處理指令，它把頭文件的內(nèi)容添加到.cpp文件中還有其他許多預(yù)處理指令這個在編譯之前修改源文件的方式提供了很大的靈活性，以適應(yīng)不同的計算機和操作系統(tǒng)環(huán)境的限制。一個環(huán)境需要的代碼跟另一個環(huán)境所需的代碼可能有所不同，因為可用的硬件或操作系統(tǒng)是不同的。在許多情況下，可以把用于不同環(huán)境的代碼放在同一個文件中，再在預(yù)處理階段修改代碼，使之適應(yīng)當(dāng)前的環(huán)境。預(yù)處理器顯示為一個獨立的操作，但一般不能獨立于編譯器來執(zhí)行這個操作。調(diào)用編譯器會自動執(zhí)行預(yù)處理過程，之后才編譯代碼。編譯器為給定源文件輸出的是機器碼，執(zhí)行這個過程需要較長時間。在對象文件之間并沒有建立任何連接。對應(yīng)于某個源文件的對象文件包含在其他源文件中定義的函數(shù)引用或其他指定項的引用，而這些函數(shù)或項仍沒有被解析。同樣，也沒有建立同庫函數(shù)的鏈接。實際上，這些函數(shù)的代碼并不是文件的一部分。這些工作是由鏈接程序(有時稱為鏈接編輯器)完成的鏈接程序把所有對象文件中的機器碼組合在一起，并解析它們之間的交叉引用。它還集成了對象模塊所使用的庫函數(shù)的代碼。這是鏈接程序的一種簡化表示，因為這里假定在可執(zhí)行模塊中，模塊之間的所有鏈接都是靜態(tài)建立的。實際上有些鏈接是動態(tài)的，即這些鏈接是在程序執(zhí)行時建立的。鏈接程序靜態(tài)地建立函數(shù)之間的鏈接，即在程序執(zhí)行之前建立組成程序的源文件中所包含的函數(shù)鏈接。動態(tài)建立的函數(shù)之間的鏈接(在程序執(zhí)行過程中建立的鏈接)將函數(shù)編譯并鏈接起來，創(chuàng)建另一種可執(zhí)行模塊——動態(tài)鏈接庫或共享庫。動態(tài)鏈接庫中的函數(shù)鏈接是在程序調(diào)用函數(shù)時才建立的，在程序調(diào)用之前，該鏈接是不存在的。動態(tài)鏈接庫有幾個重要的優(yōu)點。一個主要的優(yōu)點是動態(tài)鏈接庫中的函數(shù)可以在幾個并行執(zhí)行的程序之間共享，這將節(jié)省相同函數(shù)占用的內(nèi)存空間。另一個優(yōu)點是動態(tài)鏈接庫在調(diào)用其中的函數(shù)之前是不會加載到內(nèi)存中的。也就是說，如果不使用給定動態(tài)鏈接庫中的函數(shù)，該動態(tài)鏈接庫就不會占用內(nèi)存空間11、解釋“優(yōu)先級隊列”這一抽象數(shù)據(jù)類型及實現(xiàn)方法如果我們給每個元素都分配一個數(shù)字來標(biāo)記其優(yōu)先級，不妨設(shè)較小的數(shù)字具有較高的優(yōu)先級，這樣我們就可以在一個集合中訪問優(yōu)先級最高的元素并對其進(jìn)行查找和刪除操作了。這樣，我們就引入了優(yōu)先級隊列這種數(shù)據(jù)結(jié)構(gòu)。缺省情況下，優(yōu)先級隊列利用一個最大堆完成函數(shù)列表：empty()如果優(yōu)先隊列為空，則返回真pop()刪除第一個元素push()加入一個元素size()返回優(yōu)先隊列中擁有的元素的個數(shù)top()返回優(yōu)先隊列中有最高優(yōu)先級的元素用途就不用多說了吧，例如Huffman編碼、分支限界、A*啟發(fā)式都需要用到優(yōu)先隊列存放信息。12、逆波蘭式用什么數(shù)據(jù)結(jié)構(gòu)算法的效率比較高，為什么13、C和C++，C++和Java的區(qū)別C是一個結(jié)構(gòu)化語言，如譚老爺子所說：它的重點在于算法和數(shù)據(jù)結(jié)構(gòu)。C程序的設(shè)計首要考慮的是如何通過一個過程，對輸入（或環(huán)境條件）進(jìn)行運算處理得到輸出（或?qū)崿F(xiàn)過程（事務(wù)）控制），而對于C++，首要考慮的是如何構(gòu)造一個對象模型，讓這個模型能夠契合與之對應(yīng)的問題域，這樣就可以通過獲取對象的狀態(tài)信息得到輸出或?qū)崿F(xiàn)過程（事務(wù)）控制。所以C與C++的最大區(qū)別在于它們的用于解決問題的思想方法不一樣。之所以說C++比C更先進(jìn)，是因為面向?qū)?4、什么是預(yù)處理程序設(shè)計中的預(yù)處理(Preprocess)，程序設(shè)計領(lǐng)域，預(yù)處理是在程序源代碼被編譯之前，由預(yù)處理器（Preprocessor）對程序源代碼進(jìn)行的處理。這個過程并不對程序的源代碼進(jìn)行解析，但它把源代碼分割或處理成為特定的符號用來支持宏調(diào)用。預(yù)處理器的主要作用就是把通過預(yù)處理的內(nèi)建功能對一個資源進(jìn)行等價替換，最常見的預(yù)處理有：文件包含，條件編譯、布局控制和宏替換4種。15、堆和棧的區(qū)別棧區(qū)（stack）—由編譯器自動分配釋放，存放函數(shù)的參數(shù)值，局部變量的值等。其操作方式類似于數(shù)據(jù)結(jié)構(gòu)中的棧。堆棧（英文：stack），也可直接稱棧。臺灣作堆疊，在計算機科學(xué)中，是一種特殊的串行形式的數(shù)據(jù)結(jié)構(gòu)，它的特殊之處在于只能允許在鏈結(jié)串行或陣列的一端（稱為堆棧頂端指標(biāo)，英文為top）進(jìn)行加入資料（push）和輸出資料（pop）的運算。另外堆棧也可以用一維陣列或連結(jié)串行的形式來完成。堆棧的另外一個相對的操作方式稱為佇列。由于堆棧數(shù)據(jù)結(jié)構(gòu)只允許在一端進(jìn)行操作，因而按照后進(jìn)先出（LIFO,LastInFirstOut）的原理運作。堆棧數(shù)據(jù)結(jié)構(gòu)使用兩種基本操作：推入（push）和彈出（pop）：17、簡述在面向?qū)ο蟪绦蛟O(shè)計中，引入繼承和封裝的主要作用繼承：代碼重用封裝：代碼安全18、簡述C語言中指針及其作用19、Java語言的多線程機制20、簡述四種常見的數(shù)據(jù)邏輯結(jié)構(gòu)①集合集合中任何兩個數(shù)據(jù)元素之間都沒有邏輯關(guān)系，組織形式松散。④圖狀結(jié)構(gòu)圖狀結(jié)構(gòu)中的結(jié)點按邏輯關(guān)系互相纏繞，任何兩個結(jié)點都可以鄰接21、簡述在一棵二叉排序樹中查找一特定元素x的算法過程二叉排序樹（BinarySortTree）又稱二叉查找樹。它或者是一棵空樹；或者是具有下列性質(zhì)的二叉樹：（1）若左子樹不空，則左子樹上所有結(jié)點的值均小于它的根結(jié)點的值；（2）若右子樹不空，則右子樹上所有結(jié)點的值均大于它的根結(jié)點的值；（3）左、右子樹也分別為二叉排序樹；在最壞的情況是，兩子數(shù)列擁有大各為1和n-1，且調(diào)用樹（calltree）變成為一個n個嵌套（nested）調(diào)用的線性連串（chain）。第i次調(diào)用作了O(n-i)的工作量，且遞歸關(guān)系式為：這與插入排序和選擇排序有相同的關(guān)系式，以及它被解為T(n)=O(n2)。它的最壞情況是很恐怖的，需要空間，遠(yuǎn)比數(shù)列本身還多。23、簡述在一帶權(quán)有向圖中尋找關(guān)鍵路徑的基本思想關(guān)鍵路徑：關(guān)鍵路徑是指網(wǎng)絡(luò)終端元素的元素的序列，該序列具有最長的總工期并決定了整個項目的最短完成時間。在AOE網(wǎng)中，從始點到終點具有最大路徑長度（該路徑上的各個活動所持續(xù)的時間之和）的路徑為關(guān)鍵路徑關(guān)鍵活動：關(guān)鍵路徑上的活動稱為關(guān)鍵活動。只有所有關(guān)鍵活動提前完成，整個工程才能提前完成。最早可能開始時間Ve[i]：從原點到頂點Vi最長路徑的長度（之前所有事情做完了才可能開始）；最遲允許開始時間Vl[i]：保證匯點Vn-1在Ve[n-1]時刻完成的前提下（整體工期不拖），事件Vi最遲允許的開始時間。Vl[i]=min{Vl[k]-dur(<Vi,Vk>)}關(guān)鍵活動：松弛時間(slacktime)Al[j]-Ae[k]==0的節(jié)點。24、類作用域和文件作用域的區(qū)別是什么文件作用域也稱“全局作用域”。定義在所有函數(shù)之外的標(biāo)識符，具有文件作用域，作用域為從定義處到整個源文件結(jié)束。文件中定義的全局變量和函數(shù)都具有文件作用域。如果某個文件中說明了具有文件作用域的標(biāo)識符，該文件又被另一個文件包含，則該標(biāo)識符的作用域延伸到新的文件中。如cin和cout是在頭文件iostream.h中說明的具有文件作用域的標(biāo)識符，它們的作用域也延伸到嵌入iostream.h的文件中。操作系統(tǒng)1.進(jìn)程和線程的區(qū)別及聯(lián)系，操作系統(tǒng)的程序?！€程和進(jìn)程的區(qū)別：1、線程是進(jìn)程的一部分，所以線程有的時候被稱為是輕權(quán)進(jìn)程或者輕量級進(jìn)程。2、一個沒有線程的進(jìn)程是可以被看作單線程的，如果一個進(jìn)程內(nèi)擁有多個進(jìn)程，進(jìn)程的執(zhí)行過程不是一條線（線程）的，而是多條線（線程）共同完成的。3、系統(tǒng)在運行的時候會為每個進(jìn)程分配不同的內(nèi)存區(qū)域，但是不會為線程分配內(nèi)存（線程所使用的資源是它所屬的進(jìn)程的資源），線程組只能共享資源。那就是說，出了CPU之外（線程在運行的時候要占用CPU資源），計算機內(nèi)部的軟硬件資源的分配與線程無關(guān)，線程只能共享它所屬進(jìn)程的資源。4、與進(jìn)程的控制表PCB相似，線程也有自己的控制表TCB，但是TCB中所保存的線程狀態(tài)比PCB表中少多了（上下文保存一下就行）。5、進(jìn)程是系統(tǒng)所有資源分配時候的一個基本單位，擁有一個完整的虛擬空間地址，并不依賴線程而獨立存在。進(jìn)程與程序的區(qū)別：程序是一組指令的集合，它是靜態(tài)的實體，沒有執(zhí)行的含義。而進(jìn)程是一個動態(tài)的實體，有自己的生命周期。一般說來，一個進(jìn)程肯定與一個程序相對應(yīng)，并且只有一個，但是一個程序可以有多個進(jìn)程，或者一個進(jìn)程都沒有也可以只有一個進(jìn)程。除此之外，進(jìn)程還有并發(fā)性和交往性。簡單地說，進(jìn)程是程序的一部分，程序運行的時候會產(chǎn)生進(jìn)程?？偨Y(jié)：線程是進(jìn)程的一部分，進(jìn)程是程序的一部分。前一句說的不太準(zhǔn)確，線程也有自己的資源，比如棧，私有數(shù)據(jù)等等。說他使用而不擁有資源指的是使用的是進(jìn)程的打開文件句柄，進(jìn)程的全局?jǐn)?shù)據(jù)，進(jìn)程的地址空間等等,這些都屬于進(jìn)程，而不屬于線程，進(jìn)程內(nèi)個線程共享。進(jìn)程切換比線程切換開銷大是因為進(jìn)程切換時要切頁表，而且往往伴隨著頁調(diào)度，因為進(jìn)程的數(shù)據(jù)段代碼段要換出去，以便把將要執(zhí)行的進(jìn)程的內(nèi)容換進(jìn)來。本來進(jìn)程的內(nèi)容就是線程的超集。而且線程只需要保存線程的上下文（相關(guān)寄存器狀態(tài)和棧的信息）就好了，動作很小。2.OS里面進(jìn)程的“三態(tài)”“五態(tài)”“七態(tài)”是什么3.什么是操作系統(tǒng)4.死鎖的條件，檢測死鎖的可能方法及其基本思想Adeadlockisasituationinwhichtwoormorecompetingactionsareeachwaitingfortheothertofinish,andthusneithereverdoes.1.（互斥）:Atleasttworesourcesmustbenon-shareable.[1]Onlyoneprocesscanusetheresourceatanygiveninstantoftime.2.HoldandWaitorResourceHolding:Aprocessiscurrentlyholdingatleastoneresourceandrequestingadditionalresourceswhicharebeingheldbyotherprocesses.3.No（禁止搶占）:Theoperatingsystemmustnotde-allocateresourcesoncetheyhavebeenallocated;theymustbereleasedbytheholdingprocessvoluntarily.4.Aprocessmustbewaitingforaresourcewhichisbeingheldbyanotherprocess,whichinturniswaitingforthefirstprocesstoreleasetheresource.Ingeneral,thereisaofwaitingprocesses,P={P1,P2,...,PN},suchthatP1iswaitingforaresourceheldbyP2,P2iswaitingforaresourceheldbyP3andsoonuntilPNiswaitingforaresourceheldbyP1.[1][7]ThesefourconditionsareknownastheCoffmanconditionsfromtheirfirstdescriptionina1971articleby[7]Unfulfillmentofanyoftheseconditionsisenoughtoprecludeadeadlockfromoccurring.Ensurethatthesystemwillneverenteradeadlockstate.Prevention:Ensureoneofthefourconditionsfails.Avoidance:TheOSneedsmoreinformationsothatitcandetermineifthecurrentrequestcanbesatisfiedordelayed.死鎖檢測：1.Resource-AllocationGraph2.DetectionAlgorithm5.用戶態(tài)和內(nèi)核態(tài)當(dāng)程序運行在3級特權(quán)級上時，就可以稱之為運行在用戶態(tài)，因為這是最低特權(quán)級，是普通的用戶進(jìn)程運行的特權(quán)級，大部分用戶直接面對的程序都是運行在用戶態(tài)；反之，當(dāng)程序運行在級特權(quán)級上時，就可以稱之為運行在內(nèi)核態(tài)。用戶態(tài)切換到內(nèi)核態(tài)的3種方式a.系統(tǒng)調(diào)用這是用戶態(tài)進(jìn)程主動要求切換到內(nèi)核態(tài)的一種方式，用戶態(tài)進(jìn)程通過系統(tǒng)調(diào)用申請使用操作系統(tǒng)提供的服務(wù)程序完成工作，比如前例中fork()實際上就是執(zhí)行了一個創(chuàng)建新進(jìn)程的系統(tǒng)調(diào)用。而系統(tǒng)調(diào)用的機制其核心還是使用了操作系統(tǒng)為用戶特別開放的一個中斷來實現(xiàn)，例如Linux的int80h中斷。b.異常當(dāng)CPU在執(zhí)行運行在用戶態(tài)下的程序時，發(fā)生了某些事先不可知的異常，這時會觸發(fā)由當(dāng)前運行進(jìn)程切換到處理此異常的內(nèi)核相關(guān)程序中，也就轉(zhuǎn)到了內(nèi)核態(tài)，比如缺頁異常。c.外圍設(shè)備的中斷當(dāng)外圍設(shè)備完成用戶請求的操作后，會向CPU發(fā)出相應(yīng)的中斷信號，這時CPU會暫停執(zhí)行下一條即將要執(zhí)行的指令轉(zhuǎn)而去執(zhí)行與中斷信號對應(yīng)的處理程序，如果先前執(zhí)行的指令是用戶態(tài)下的程序，那么這個轉(zhuǎn)換的過程自然也就發(fā)生了由用戶態(tài)到內(nèi)核態(tài)的切換。比如硬盤讀寫操作完成，系統(tǒng)會切換到硬盤讀寫的中斷處理程序中執(zhí)行后續(xù)操作等。這3種方式是系統(tǒng)在運行時由用戶態(tài)轉(zhuǎn)到內(nèi)核態(tài)的最主要方式，其中系統(tǒng)調(diào)用可以認(rèn)為是用戶進(jìn)程主動發(fā)起的，異常和外圍設(shè)備中斷則是被動的。6.面包店算法該算法的基本思想源于顧客在面包店中購買面包時的排隊原理.顧客在進(jìn)入面包店前,首先抓一個號,然后按照號碼由小到大的次序依次進(jìn)入面包店購買面包.這里,面包店發(fā)放的號碼是由小到大的,但是兩個或兩個以上的顧客卻有可能得到相同的號碼(使所抓號碼不同需要互斥),如果多個顧客抓到相同的號碼,則規(guī)定按照顧客名字的字典次序進(jìn)行排序,這里假定顧客是沒有重名的.在計算機系統(tǒng)中,顧客就相當(dāng)于進(jìn)程,每個進(jìn)程有一個唯一的標(biāo)識,我們用P的下面加一個下標(biāo)來表示.例如:對于Pi和Pj,如果有i<j,則先為Pi服務(wù),即Pi先進(jìn)入臨界區(qū)7.系統(tǒng)調(diào)用和庫函數(shù)的區(qū)別(1)調(diào)用形式不同。過程（函數(shù)）使用一般調(diào)用指令，其轉(zhuǎn)向地址是固定不變的，包含在跳轉(zhuǎn)語句中；但系統(tǒng)調(diào)用中不包含處理程序入口，而僅僅提供功能號，按功能號調(diào)用。(2)被調(diào)用代碼的位置不同。過程（函數(shù)）調(diào)用是一種靜態(tài)調(diào)用，調(diào)用者和被調(diào)用代碼在同一程序內(nèi)，經(jīng)過連接編輯后作為目標(biāo)代碼的一部份。當(dāng)過程（函數(shù)）升級或修改時，必須重新編譯連結(jié)。而系統(tǒng)調(diào)用是一種動態(tài)調(diào)用，系統(tǒng)調(diào)用的處理代碼在調(diào)用程序之外（在操作系統(tǒng)中），這樣一來，系統(tǒng)調(diào)用處理代碼升級或修改時，與調(diào)用程序無關(guān)。而且，調(diào)用程序的長度也大大縮短，減少了調(diào)用程序占用的存儲空間。(3)提供方式不同。過程（函數(shù)）往往由編譯系統(tǒng)提供，不同編譯系統(tǒng)提供的過程（函數(shù)）可以不同；系統(tǒng)調(diào)用由操作系統(tǒng)提供，一旦操作系統(tǒng)設(shè)計好，系統(tǒng)調(diào)用的功能、種類與數(shù)量便固定不變了。(4)調(diào)用的實現(xiàn)不同。程序使用一般機器指令（跳轉(zhuǎn)指令）來調(diào)用過程（函數(shù)），是在用戶態(tài)運行的；程序執(zhí)行系統(tǒng)調(diào)用，是通過中斷機構(gòu)來實現(xiàn)，需要從用戶態(tài)轉(zhuǎn)變到核心態(tài)，在管理狀態(tài)執(zhí)行，因此，安全性好。8.經(jīng)典進(jìn)程同步問題是什么，同步思想？生產(chǎn)者-消費者問題是著名的進(jìn)程同步問題，它描述一組生產(chǎn)者進(jìn)程向一組消費者進(jìn)程提供消息。它們共享一個有界緩沖池，生產(chǎn)者向其中投放消息，消費者從中取得消息。生產(chǎn)者-消費者問題是許多相互合作進(jìn)程的一種抽象。假定緩沖池中有n個緩沖區(qū)，每個緩沖區(qū)存放一個消息。由于緩沖池是臨界資源，它只允許一個生產(chǎn)者投入消息，或者一個消費者從中取出消息。生產(chǎn)者之間、生產(chǎn)者與消費者之間、消費者之間都必須互斥地使用緩沖池。所以必須設(shè)置互斥信號量mutex，它代表緩沖池資源，它的數(shù)值為1。讀者-寫者問題問題描述：一個數(shù)據(jù)集（如文件）被幾個并行進(jìn)程所共享，有些進(jìn)程只要求讀數(shù)據(jù)集內(nèi)容，稱為讀者，而另一些進(jìn)程則要求修改數(shù)據(jù)集內(nèi)容，稱為寫者，幾個讀者可以同時讀數(shù)據(jù)集，而不需要互斥，但一個寫者不能和其他進(jìn)程（不管是寫者或讀者）同時訪問這些數(shù)據(jù)集，它們之間必須互斥。哲學(xué)家進(jìn)餐問題該問題描述如下：有五個哲學(xué)家，他們的生活方式是交替地進(jìn)行思考和進(jìn)餐。哲學(xué)家們公用一張圓桌，周圍放有五把椅子，每人坐一把。在圓桌上有五個碗和五根筷子，當(dāng)一個哲學(xué)家思考時，他不與其他人交談，饑餓時便試圖取用其左、右最靠近他的筷子，但他可能一根都拿不到。只有在他拿到兩根筷子時，方能進(jìn)餐，進(jìn)餐完后，放下筷子又繼續(xù)思考。9.文件管理及組織，F(xiàn)ATFAT=FileAllocationTable10.設(shè)備驅(qū)動程序是否屬于OS，他的作用是什么不是，驅(qū)動程序是另外安裝的軟件，是操作系統(tǒng)控制并且和硬件之間通訊的橋梁（程序）11.程序和任務(wù)的區(qū)別任務(wù)是最抽象的，是一個一般性的術(shù)語，指由軟件完成的一個活動。一個任務(wù)既可以是一個進(jìn)程,也可以是一個線程。簡而言之,它指的是一系列共同達(dá)到某一目的的操作。例如,讀取數(shù)據(jù)并將數(shù)據(jù)放入內(nèi)存中。這個任務(wù)可以作為一個進(jìn)程來實現(xiàn),也可以作為一個線程（或作為一個中斷任務(wù)）來實現(xiàn)。進(jìn)程常常被定義為程序的執(zhí)行。可以把一個進(jìn)程看成是一個獨立的程序,在內(nèi)存中有其完備的數(shù)據(jù)空間和代碼空間。一個進(jìn)程所擁有的數(shù)據(jù)和變量只屬于它自己。線程則是某一進(jìn)程中一路單獨運行的程序。也就是說，線程存在于進(jìn)程之中。一個進(jìn)程由一個或多個線程構(gòu)成，各線程共享相同的代碼和全局?jǐn)?shù)據(jù)，但各有其自己的堆棧。由于堆棧是每個線程一個，所以局部變量對每一線程來說是私有的。由于所有線程共享同樣的代碼和全局?jǐn)?shù)據(jù)，它們比進(jìn)程更緊密，比單獨的進(jìn)程間更趨向于相互作用,線程間的相互作用更容易些,因為它們本身就有某些供通信用的共享內(nèi)存：進(jìn)程的全局?jǐn)?shù)據(jù)進(jìn)程的全局?jǐn)?shù)據(jù)進(jìn)程的全局?jǐn)?shù)據(jù)進(jìn)程的全局?jǐn)?shù)據(jù)進(jìn)程：資源分配、調(diào)度運行的基本單位。線程：進(jìn)程中執(zhí)行運算的最小單位，執(zhí)行處理機調(diào)度的基本單位。12.數(shù)據(jù)庫安全性和操作系統(tǒng)安全性的關(guān)系安全性問題不是數(shù)據(jù)庫系統(tǒng)所獨有的,所有計算機系統(tǒng)都有這個問題.只是在數(shù)據(jù)庫系統(tǒng)中大量數(shù)據(jù)集中存放,而且為許多最終用戶直接共享,從而使安全性問題更為突出.系統(tǒng)安全保護(hù)措施是否有效是數(shù)據(jù)庫系統(tǒng)的主要指標(biāo)之一.數(shù)據(jù)庫的安全性和計算機系統(tǒng)的安全性,包括操作系統(tǒng),網(wǎng)絡(luò)系統(tǒng)的安全性是緊密聯(lián)系,相互支持的.13.中斷處理的過程請求中斷→響應(yīng)中斷→關(guān)閉中斷→保留斷點→中斷源識別→保護(hù)現(xiàn)場→中斷服務(wù)子程序→恢復(fù)現(xiàn)場→中斷返回在實際運行中，一旦設(shè)備通過某引腳N向8259A發(fā)出中斷指令，后者便向8086A的INTR引腳發(fā)送中斷信號。8086A通過INTA引腳通知8259A中斷有效（這個過程實際上還包括對此8259A的選址），后者即通過地址總線將對應(yīng)引腳N的中斷類型碼（已預(yù)先存好，見上節(jié)）發(fā)送給CPU。CPU得到中斷類型碼后，先進(jìn)行現(xiàn)場保護(hù)，主要包括：1.狀態(tài)寄存器FLAGS壓棧（同時堆棧寄存器SP-2）；2.關(guān)閉中斷（將FLAGS寄存器的IF位置零）；3.將當(dāng)前代碼段寄存器CS和程序計數(shù)器IP壓棧（同時堆棧寄存器SP-4）?，F(xiàn)場保護(hù)完成后，CPU開始按照前述的兩步驟翻譯中斷程序入口地址。在得到中斷處理程序地址之后但調(diào)用中斷處理程序之前，CPU會再檢查一下NMI引腳是否有信號，以防在剛才的處理過程中忽略了可能的NMI中斷。NMI的優(yōu)先級始終高于INTR。中斷處理程序雖然是由程序員編寫，但須循一定規(guī)范。作為例程，中斷處理程序應(yīng)該先將各寄存器信息（除了IP和CS，此二寄存器現(xiàn)已指向當(dāng)前中斷程序）壓入堆棧予以保存，這樣才能在中斷處理程序內(nèi)部使用這些寄存器。在程序結(jié)束時，應(yīng)該按與壓棧保護(hù)時相反的順序彈出各寄存器的值。中斷程序的最后一句始終是IRET指令，這條指令將棧頂6個字節(jié)分別彈出并存入IP、CS和FLAGS寄存器，完成了現(xiàn)場的還原。當(dāng)然，如果是操作系統(tǒng)的中斷處理程序，則未必——通常不會——還原中斷前的狀態(tài)。這樣的中斷處理程序通常會在調(diào)用完寄存器保存例程后，調(diào)用進(jìn)程調(diào)度程序（多由高級語言編寫），并決定下一個運行的進(jìn)程。隨后將此進(jìn)程的寄存器信息（上次中斷時保存下來的）存入寄存器并返回。在中斷程序結(jié)束之后，主程序也發(fā)生了改變。14.計算機系統(tǒng)怎樣實現(xiàn)存儲保護(hù)1.防止地址越界（對進(jìn)程所產(chǎn)生的地址必須加以檢查，發(fā)生越界時產(chǎn)生中斷，由操作系統(tǒng)進(jìn)行相應(yīng)處理）2.防止操作越權(quán)（對屬于自己區(qū)域的信息，可讀可寫：對公共區(qū)域中允許共享的信息或獲得授權(quán)可使用的信息，可讀而不可修改；對未授權(quán)使用的信息，不可讀，不可寫）15.調(diào)度的基本準(zhǔn)則(SchedulingCriteria)Therearemanycriteriaforcomparingdifferentschedulingalgorithms.Herearefivecommonones:CPUutilization(CPU利用率)Throughput（吞吐量）Turnaroundtime（周轉(zhuǎn)時間）Waitingtime（等待時間）Responsetime（響應(yīng)時間）16.多線程是否真正能提高效率17.磁盤調(diào)度算法有哪幾種FCFSSSTF(ShortestSeekTimeFirst)Scan/LookC-Sacn/C-Look18.RAID工作原理RAID(RedundantArrayofIndependentDisks)通過條帶化存儲和奇偶校驗兩個措施來實現(xiàn)其冗余和容錯的目標(biāo)。條帶化存儲意味著可以一次寫入一個數(shù)據(jù)塊的方式將文件寫入多個磁盤。條帶化存儲技術(shù)將數(shù)據(jù)分開寫入多個驅(qū)動器，從而提高數(shù)據(jù)傳輸速率并縮短磁盤處理總時間。這種系統(tǒng)非常適用于交易處理、但可靠性卻很差，因為系統(tǒng)的可靠性等于最差的單個驅(qū)動器的可靠性。奇偶校驗通過在傳輸后對所有數(shù)據(jù)進(jìn)行冗余校驗可以確保數(shù)據(jù)的有效性。利用奇偶校驗，當(dāng)RAID系統(tǒng)的一個磁盤發(fā)生故障時，其它磁盤能夠重建該故障磁盤。在這兩種情況中，這些功能對于操作系統(tǒng)都是透明的。由磁盤陣列控制器（DAC）進(jìn)行條帶化存儲和奇偶校驗控制。19.Windows中段最長多少字節(jié)?20.同步、互斥22.簡述請求段頁式虛擬內(nèi)存管理基本思想Bringapageintomemoryonlywhenitisneeded.LessI/OneededLessmemoryneededFasterresponseMoreusersPageisneeded?referencetoitinvalidreference?abortnot-in-memory?bringtomemory網(wǎng)絡(luò)1.路由協(xié)議常見路由協(xié)議有：RIP，OSPF，BGP等2.CSMA/CD,指數(shù)回退載波偵聽多路訪問／沖突檢測（英語：CarrierSenseMultipleAccesswithCollisionDetection，CSMA/CD）此方案要求設(shè)備在發(fā)送幀的同時要對信道進(jìn)行偵聽，以確定是否發(fā)生沖突，若在發(fā)送數(shù)據(jù)過程中檢測到?jīng)_突，則進(jìn)行如下沖突處理操作：1.發(fā)送特殊阻塞信息并立即停止發(fā)送數(shù)據(jù)：特殊阻塞信息是連續(xù)幾個字節(jié)的全1信號，此舉意在強化沖突，以使得其它設(shè)備能盡快檢測到?jīng)_突發(fā)生。2.在固定時間（一開始是1contentionperiodtimes）內(nèi)等待隨機的時間，再次發(fā)送。3.若依舊碰撞，則采用進(jìn)行發(fā)送。即十次之內(nèi)停止前一次“固定時間”的兩倍時間內(nèi)隨機再發(fā)送，十次后則停止前一次“固定時間”內(nèi)隨機再發(fā)送。嘗試16次之后仍然失敗則放棄傳送。載波偵聽多路訪問／沖突避免（英語：CarrierSenseMultipleAccesswithCollisionAvoidance，CSMA/CA）此種方案采用主動避免碰撞而非被動偵測的方式來解決沖突問題?？梢詽M足那些不易準(zhǔn)確偵測是否有沖突發(fā)生的需求，如無線網(wǎng)域。CSMA/CA協(xié)議主要使用兩種方法來避免碰撞：1.設(shè)備欲發(fā)送訊框(Frame)，且訊框聽到通道空閑時，維持一段時間后，再等待一段隨機的時間依然空閑時，才提交數(shù)據(jù)。由于各個設(shè)備的等待時間是分別隨機產(chǎn)生的，因此很大可能有所區(qū)別，由此可以減少沖突的可能性。2.RTS-CTS三向握手（：handshake）：設(shè)備欲發(fā)送訊框前，先發(fā)送一個很小的RTS（RequesttoSend）訊框給目標(biāo)端，等待目標(biāo)端回應(yīng)CTS（CleartoSend）幀后，才開始傳送。此方式可以確保接下來傳送數(shù)據(jù)時，不會發(fā)生沖突。同時由于RTS幀與CTS幀都很小，讓傳送的無效開銷變小。3.解釋FTP、HTTP的全稱及其原理。FTP、HTTP文件傳輸?shù)漠愅現(xiàn)TP：FileTransferProtocolHTTP:HyperTextTransferProtocol都是應(yīng)用層協(xié)議。4.七層協(xié)議的名稱PhysicalDataLinkNetworkTransmissionSessionPresentationApplication5.電子郵件發(fā)送到接收的過程，協(xié)議電子郵件的工作過程遵循客戶-服務(wù)器模式。每份電子郵件的發(fā)送都要涉及到發(fā)送方與接收方，發(fā)送方式構(gòu)成客戶端，而接收方構(gòu)成服務(wù)器，服務(wù)器含有眾多用戶的電子信箱。發(fā)送方通過郵件客戶程序，將編輯好的電子郵件向郵局服務(wù)器（SMTP服務(wù)器）發(fā)送。郵局服務(wù)器識別接收者的地址，并向管理該地址的郵件服務(wù)器（POP3服務(wù)器）發(fā)送消息。郵件服務(wù)器識將消息存放在接收者的電子信箱內(nèi)，并告知接收者有新郵件到來。接收者通過郵件客戶程序連接到服務(wù)器后，就會看到服務(wù)器的通知，進(jìn)而打開自己的電子信箱來查收郵件。發(fā)送：SMTP接收：POP,IMAP6.P2P技術(shù)，具體的實現(xiàn)機制實現(xiàn)P2P需要一個中轉(zhuǎn)服務(wù)器。也就是需要一個第三方。（一會兒我們來說為什么需要一個第三方）7.網(wǎng)絡(luò)中的握手問題8.無線傳感網(wǎng)絡(luò)(WSN)及其應(yīng)用無線傳感網(wǎng)絡(luò)（Wirelesssensornetwork），或譯無線感知網(wǎng)絡(luò)，是由許多在空間中分布的自動裝置組成的一種無線通訊計算機網(wǎng)絡(luò)，這些裝置使用傳感器協(xié)作地監(jiān)控不同位置的物理或環(huán)境狀況（比如溫度、聲音、振動、壓力、運動或污染物）。無線傳感器網(wǎng)絡(luò)的發(fā)展最初起源于戰(zhàn)場監(jiān)測等軍事應(yīng)用。而現(xiàn)今無線傳感器網(wǎng)絡(luò)被應(yīng)用于很多民用領(lǐng)域，如環(huán)境與生態(tài)監(jiān)測、健康監(jiān)護(hù)、家居自動化以及交通控制等。無線傳感網(wǎng)絡(luò)主要包括三個方面：感應(yīng)，通訊，計算（硬件，軟件，算法）。其中的關(guān)鍵技術(shù)主要有無線數(shù)據(jù)庫技術(shù)，比如使用在無線傳感器網(wǎng)絡(luò)的查詢，和用于和其他傳感器通訊的網(wǎng)絡(luò)技術(shù)，特別是多次跳躍路由協(xié)議。9.當(dāng)前網(wǎng)絡(luò)新技術(shù)及其應(yīng)用,Web2.0Web2.0，指的是一個利用Web的平臺，由用戶主導(dǎo)而生成的內(nèi)容互聯(lián)網(wǎng)產(chǎn)品模式，為了區(qū)別傳統(tǒng)由網(wǎng)站雇員主導(dǎo)生成的內(nèi)容而定義為web2.08.無線傳感網(wǎng)絡(luò)(WSN)及其應(yīng)用無線傳感網(wǎng)絡(luò)（Wirelesssensornetwork），或譯無線感知網(wǎng)絡(luò)，是由許多在空間中分布的自動裝置組成的一種無線通訊計算機網(wǎng)絡(luò)，這些裝置使用傳感器協(xié)作地監(jiān)控不同位置的物理或環(huán)境狀況（比如溫度、聲音、振動、壓力、運動或污染物）。無線傳感器網(wǎng)絡(luò)的發(fā)展最初起源于戰(zhàn)場監(jiān)測等軍事應(yīng)用。而現(xiàn)今無線傳感器網(wǎng)絡(luò)被應(yīng)用于很多民用領(lǐng)域，如環(huán)境與生態(tài)監(jiān)測、健康監(jiān)護(hù)、家居自動化以及交通控制等。無線傳感網(wǎng)絡(luò)主要包括三個方面：感應(yīng)，通訊，計算（硬件，軟件，算法）。其中的關(guān)鍵技術(shù)主要有無線數(shù)據(jù)庫技術(shù)，比如使用在無線傳感器網(wǎng)絡(luò)的查詢，和用于和其他傳感器通訊的網(wǎng)絡(luò)技術(shù)，特別是多次跳躍路由協(xié)議。9.當(dāng)前網(wǎng)絡(luò)新技術(shù)及其應(yīng)用,Web2.0Web2.0，指的是一個利用Web的平臺，由用戶主導(dǎo)而生成的內(nèi)容互聯(lián)網(wǎng)產(chǎn)品模式，為了區(qū)別傳統(tǒng)由網(wǎng)站雇員主導(dǎo)生成的內(nèi)容而定義為web2.011.TCP擁塞控制(congestioncontrol)與流量控制(flowcontrol)的功能和區(qū)別流量控制解決的問題：通信雙方速率不匹配。方法：Slidingwindow，控制滑動窗口大小，自適應(yīng)速率。擁塞控制解決的問題：雙方速率都允許的情況下，如何保證途中不出問題。方法：使用RTT(RoundTripTime)以及RTO(RetransmissionTimeOut)以及計算這兩個量的算法，保證傳輸可能失敗的時候重傳。12.PPP協(xié)議點對點協(xié)議（英語：Point-to-PointProtocol，PPP）工作在數(shù)據(jù)鏈路層（以O(shè)SI參考模型的觀點）。它通常用在兩節(jié)點間創(chuàng)建直接的連接，并可以提供連接認(rèn)證、傳輸加密（使用ECP，RFC1968）以及壓縮。13.集線器、路由器和交換機有什么區(qū)別。中繼器、集線器、交換機、網(wǎng)橋、網(wǎng)關(guān)、路由器的功能14.P2P網(wǎng)絡(luò)編程的特點？15.DNS的遞歸查詢和迭代查詢（1）遞歸查詢遞歸查詢是一種DNS服務(wù)器的查詢模式，在該模式下DNS服務(wù)器接收到客戶機請求，必須使用一個準(zhǔn)確的查詢結(jié)果回復(fù)客戶機。如果DNS服務(wù)器本地沒有存儲查詢DNS信息，那么該服務(wù)器會詢問其他服務(wù)器，并將返回的查詢結(jié)果提交給客戶機。（2）迭代查詢DNS服務(wù)器另外一種查詢方式為迭代查詢，DNS服務(wù)器會向客戶機提供其他能夠解析查詢請求的DNS服務(wù)器地址，當(dāng)客戶機發(fā)送查詢請求時，DNS服務(wù)器并不直接回復(fù)查詢結(jié)果，而是告訴客戶機另一臺DNS服務(wù)器地址，客戶機再向這臺DNS服務(wù)器提交請求，依次循環(huán)直到返回查詢的結(jié)果為止。16.ARP協(xié)議、ARP攻擊地址解析協(xié)議（AddressResolutionProtocol），其基本功能為通過目標(biāo)設(shè)備的IP地址，查詢目標(biāo)設(shè)備的MAC地址，以保證通信的順利進(jìn)行。它是中網(wǎng)絡(luò)層必不可少的協(xié)議，不過在中已不再適用，并被鄰居發(fā)現(xiàn)協(xié)議（NDP）所替代。在以太網(wǎng)協(xié)議中規(guī)定，同一局域網(wǎng)中的一臺主機要和另一臺主機進(jìn)行直接通信，必須要知道目標(biāo)主機的MAC地址。而在TCP/IP協(xié)議中，網(wǎng)絡(luò)層和傳輸層只關(guān)心目標(biāo)主機的IP地址。這就導(dǎo)致在以太網(wǎng)中使用IP協(xié)議時，數(shù)據(jù)鏈路層的以太網(wǎng)協(xié)議接到上層IP協(xié)議提供的數(shù)據(jù)中，只包含目的主機的IP地址。于是需要一種方法，根據(jù)目的主機的IP地址，獲得其MAC地址。這就是ARP協(xié)議要做的事情。所謂地址解析（addressresolution）就是主機在發(fā)送幀前將目標(biāo)IP地址轉(zhuǎn)換成目標(biāo)MAC地址的過程。ARP欺騙的運作原理是由攻擊者發(fā)送假的ARP數(shù)據(jù)包到網(wǎng)絡(luò)上，尤其是送到網(wǎng)關(guān)上。其目的是要讓送至特定的IP地址的流量被錯誤送到攻擊者所取代的地方。因此攻擊者可將這些流量另行轉(zhuǎn)送到真正的閘道（被動式數(shù)據(jù)包嗅探，passivesniffing）或是篡改后再轉(zhuǎn)送（中間人攻擊，man-in-the-middleattack）。17.計算機網(wǎng)絡(luò)的接入類型有哪些局域網(wǎng)、城域網(wǎng)、廣域網(wǎng)和互聯(lián)網(wǎng)四種19.電路交換和報文交換的區(qū)別報文交換（英語：Messageswitching），又稱存儲轉(zhuǎn)發(fā)交換，是數(shù)據(jù)交換的三種方式之一，報文整個地發(fā)送，一次一跳。報文交換是分組交換的前身，是由由列奧納德·克萊因饒克于1961年提出的。報文交換的主要特點是：存儲接受到的報文，判斷其目標(biāo)地址以選擇路由，最后，在下一跳路由空閑時，將數(shù)據(jù)轉(zhuǎn)發(fā)給下一跳路由。報文交換系統(tǒng)現(xiàn)今都由分組交換或電路交換網(wǎng)絡(luò)所承載。電路交換（CircuitSwitching）是相對于封包交換(或稱分組交換)的一個概念。電路交換要求必須首先在通信雙方之間建立連接通道。在連接建立成功之后，雙方的通信活動才能開始。通信雙方需要傳遞的信息都是通過已經(jīng)建立好的連接來進(jìn)行傳遞的，而且這個連接也將一直被維持到雙方的通信結(jié)束。在某次通信活動的整個過程中，這個連接將始終占用著連接建立開始時，通信系統(tǒng)分配給它的資源（通道、帶寬、時隙、碼字等等），這也體現(xiàn)了電路交換區(qū)別于分組交換的本質(zhì)特征。20.計組/接口1.Cache的兩種更新策略一般有兩種回寫策略：寫回（Writeback）和寫通（Writethrough）。寫回是指，僅當(dāng)一個緩存塊需要被替換回內(nèi)存時，才將其內(nèi)容寫入內(nèi)存。如果緩存命中，則總是不用更新內(nèi)存。為了減少內(nèi)存寫操作，緩存塊通常還設(shè)有一個臟位（dirtybit），用以標(biāo)識該塊在被載入之后是否發(fā)生過更新。如果一個緩存塊在被置換回內(nèi)存之前從未被寫入過，則可以免去回寫操作。2.計算機中小數(shù)點是如何表示的定點、浮點表示。3.計算機中如何表示數(shù)據(jù)，知識？4.Cache的原理及思想，評價標(biāo)準(zhǔn)，改進(jìn)方案，計算機軟硬件中其他用到這個思想的方法緩存之所以有效，主要是因為程序運行時對內(nèi)存的訪問呈現(xiàn)局部性（Locality）特征。這種局部性既包括空間局部性（SpatialLocality），也包括時間局部性（TemporalLocality）。有效利用這種局部性，緩存可以達(dá)到極高的命中率。評估緩存的性能通常使用平均內(nèi)存訪問時間（AverageMemoryAccessTime,AMAT）這一指標(biāo)。5.分頁、分段、段頁式的特點，為什么要引入分頁（英語：Paging），是一種操作系統(tǒng)里存儲器管理的一種技術(shù)，可以使電腦的主存可以使用存儲在輔助存儲器中的數(shù)據(jù)。操作系統(tǒng)會將輔助存儲器中的數(shù)據(jù)分區(qū)成固定大小的區(qū)塊，稱為“頁”（pages）。當(dāng)不需要時，將分頁由主存移到輔助存儲器；當(dāng)需要時，再將數(shù)據(jù)取回，加載主存中。相對于分段，分頁允許存儲器存儲于不連續(xù)的區(qū)塊以維持文件系統(tǒng)的整齊。在分頁實現(xiàn)前，分段會使文件于系統(tǒng)中連續(xù)，這使它容易造成空間雜亂且產(chǎn)生許多碎片。段頁式存儲器兼顧了程序和數(shù)據(jù)的邏輯結(jié)構(gòu)以及存儲器的物理結(jié)構(gòu)兩方面的特點，兼收頁式和段式虛擬存儲器兩者的長處，并具有如下特點：面向用戶的程序地址空間采用段式分隔。內(nèi)存分成位置固定、長度相等的若干頁面。將每一段的線性地址空間劃分為頁，頁長與內(nèi)存頁面相等。6.中斷的作用中斷的典型應(yīng)用包括系統(tǒng)時鐘、磁盤輸入輸出操作、斷電信號以及軟件自陷等。7.DMA優(yōu)先級為什么比CPU高DMA是有專用數(shù)據(jù)通路的DMA傳送過程中cpu可以繼續(xù)工作不會阻塞可以響應(yīng)外部中斷獨享總線的DMA會在傳輸是占用總線,這時候CPU將總線讓給DMA,這時候DMA優(yōu)先級比CPU高請求型DMA會在占用總線是向CPU發(fā)起請求,CPU優(yōu)先級比DMA高8.虛擬內(nèi)存容量由什么決定尋址長度（地址總線數(shù)量）虛擬存儲區(qū)的容量與物理主存大小無關(guān)，而受限于計算機的地址結(jié)構(gòu)和可用磁盤容量。9.根據(jù)內(nèi)存大小算地址總線數(shù)量10.8086指令地址的計算方式基址寄存器BX,BP變址寄存器SI,DIBX,SI,DI默認(rèn)DS段BP默認(rèn)SS段立即數(shù)尋址直接尋址：MOVAX,[2000H]MOVAX,ES:[2000H]寄存器尋址MOVAX,BX寄存器間接尋址MOVAX,[BX]寄存器相對尋址MOVAX,[SI+06H]基址變址尋址MOVAX,[BS+SI]基址變址相對尋址MOVAX,[BX+DI+6]11.馮.諾伊曼機以什么部件為中心以運算器為中心，I/O設(shè)備與存儲器間的數(shù)據(jù)傳送都要經(jīng)過運算器12.CISC/RISC的特點（1）指令系統(tǒng)：RISC設(shè)計者把主要精力放在那些經(jīng)常使用的指令上，盡量使它們具有簡單高效的特色。對不常用的功能，常通過組合指令來完成。因此，在RISC機器上實現(xiàn)特殊功能時，效率可能較低。但可以利用流水技術(shù)和超標(biāo)量技術(shù)加以改進(jìn)和彌補。而CISC計算機的指令系統(tǒng)比較豐富，有專用指令來完成特定的功能。因此，處理特殊任務(wù)效率較高。（2）存儲器操作：RISC對存儲器操作有限制，使控制簡單化；而CISC機器的存儲器操作指令多，操作直接。（3）程序：RISC匯編語言程序一般需要較大的內(nèi)存空間，實現(xiàn)特殊功能時程序復(fù)雜，不易設(shè)計；而CISC程序編程相對簡單，科學(xué)計算及復(fù)雜操作的程序社設(shè)計相對容易，效率較高。（4）中斷：RISC機器在一條指令執(zhí)行的適當(dāng)?shù)胤娇梢皂憫?yīng)中斷；而CISC機器是在一條指令執(zhí)行結(jié)束后響應(yīng)中斷。（5）CPU：RISCCPU包含有較少的單元電路，因而面積小、功耗低；而CISCCPU包含有豐富的電路單元，因而功能強、面積大、功耗大。（6）設(shè)計周期：RISC微處理器結(jié)構(gòu)簡單，布局緊湊，設(shè)計周期短，且易于采用最新技術(shù)；CISC微處理器結(jié)構(gòu)復(fù)雜，設(shè)計周期長。（7）用戶使用：RISC微處理器結(jié)構(gòu)簡單，指令規(guī)整，性能容易把握，易學(xué)易用；CISC微處理器結(jié)構(gòu)復(fù)雜，功能強大，實現(xiàn)特殊功能容易。（8）應(yīng)用范圍：由于RISC指令系統(tǒng)的確定與特定的應(yīng)用領(lǐng)域有關(guān)，故RISC機器更適合于專用機；而CISC機器則更適合于通用機。13.8254,8255,825914..匯編的，說是怎么讓寄存器低兩位的值取反15.一級緩存存取速度快是為什么靜態(tài)RAM(SRAM)不用刷新，直接與CPU數(shù)據(jù)總線相連16.RS-232接口17.大意是說匯編語言結(jié)果為零時ZF是多少（各個Flag的含義）118.主存-Cache結(jié)構(gòu)有什么作用19.簡述虛擬存儲器的基本概念虛擬存儲器是指具有請求調(diào)入功能和置換功能，能從邏輯上對內(nèi)存容量加以擴充的一種存儲器系統(tǒng)。其邏輯容量由內(nèi)存容量和外存容量之和來決定，其運行速度接近于內(nèi)存速度，而每位的成本卻又接近于外存?？梢?，虛擬存儲技術(shù)是一種性能非常優(yōu)越的存儲器管理技術(shù)，故被廣泛地應(yīng)用于大、中、小型和微型機器中。21.其他（廣）什么是計算機，計算，語法，語義，語用計算機（computer）俗稱電腦，是一種用于高速計算的電子計算機器，可以進(jìn)行數(shù)值計算，又可以進(jìn)行邏輯計算，還具有存儲記憶功能。語義：機器對自然語言的理解語用：如何運用和理解語言（離散）群中Lagrange定理及其證明根本不懂（離散）解釋元素，樹，圖。并各舉一例（軟工）軟件架構(gòu)的理解軟件架構(gòu)是有關(guān)軟件整體結(jié)構(gòu)與組件的抽象描述，用于指導(dǎo)大型軟件系統(tǒng)各個方面的設(shè)計。軟件架構(gòu)師定義和設(shè)計軟件的模塊化，模塊之間的交互，用戶界面風(fēng)格，對外接口方法，創(chuàng)新的設(shè)計特性，以及高層事物的對象操作、邏輯和流程。軟件架構(gòu)師與客戶商談概念上的事情，與經(jīng)理商談廣泛的設(shè)計問題，與軟件工程師商談創(chuàng)新的結(jié)構(gòu)特性，與程序員商談實現(xiàn)技巧，外觀和風(fēng)格。軟件架構(gòu)是一個系統(tǒng)的草圖。軟件架構(gòu)描述的對象是直接構(gòu)成系統(tǒng)的抽象組件。各個組件之間的連接則明確和相對細(xì)致地描述組件之間的通訊。在實現(xiàn)階段，這些抽象組件被細(xì)化為實際的組件，比如具體某個類或者對象。在面向?qū)ο箢I(lǐng)域中，組件之間的連接通常用接口來實現(xiàn)。（廣）什么是平臺無關(guān)性就是說（java）寫的程序不用修改就可以在不同的軟硬件平臺上運行比如你寫了一個程序，在windows下可以執(zhí)行那你直接拷到Linux下也可以執(zhí)行，只要都裝了JRE（數(shù)據(jù)庫）查詢優(yōu)化有哪些基于關(guān)系代數(shù)等價變換規(guī)則的優(yōu)化方法：代數(shù)優(yōu)化物理優(yōu)化：基于規(guī)則的啟發(fā)式優(yōu)化，基于代價估算的優(yōu)化，兩者結(jié)合的優(yōu)化方法（離散）握手定理握手定理：有n個人握手，每人握手x次，握手總次數(shù)為S，必有S=nx/2。頂點度數(shù)之和為邊數(shù)之和的兩倍。推論任何圖(無向的或有向的)中，奇度頂點的個數(shù)是偶數(shù)（數(shù)據(jù)庫）事務(wù)的四個特點（ACID）ACID，是指數(shù)據(jù)庫管理系統(tǒng)（DBMS）在寫入/異動資料的過程中，為保證事務(wù)(transaction)是正確可靠的，所必須具備的四個特性：原子性（Atomicity，或稱不可分割性）、一致性（Consistency）、隔離性（Isolation，又稱獨立性）、持久性（Durability）。原子性：一個事務(wù)(transaction)中的所有操作，要么全部完成，要么全部不完成，不會結(jié)束在中間某個環(huán)節(jié)。事務(wù)在執(zhí)行過程中發(fā)生錯誤，會被回滾（Rollback）到事務(wù)開始前的狀態(tài)，就像這個事務(wù)從來沒有執(zhí)行過一樣。一致性：在事務(wù)開始之前和事務(wù)結(jié)束以后，數(shù)據(jù)庫的完整性沒有被破壞。這表示寫入的資料必須完全符合所有的默認(rèn)規(guī)則，這包含資料的精確度、串聯(lián)性以及后續(xù)數(shù)據(jù)庫可以自發(fā)性地完成預(yù)定的工作。隔離性：當(dāng)兩個或者多個事務(wù)并發(fā)訪問（此處訪問指查詢和修改的操作）數(shù)據(jù)庫的同一數(shù)據(jù)時所表現(xiàn)出的相互關(guān)系。事務(wù)隔離分為不同級別，包括讀未提交(Readuncommitted)、讀提交（readcommitted）、可重復(fù)讀（repeatableread）和串行化（Serializable）。持久性：在事務(wù)完成以后，該事務(wù)對數(shù)據(jù)庫所作的更改便持久地保存在數(shù)據(jù)庫之中，并且是完全的。（數(shù)據(jù)庫）基本的關(guān)系操作有哪些關(guān)系模型中常用的關(guān)系操作包括查詢操作和插入、刪除、修改操作兩大部分。關(guān)系的查詢表達(dá)能力很強，是關(guān)系操作中最主要的部分。查詢操作可以分為：選擇、投影、連接、除、并、差、交、笛卡爾積等。其中，選擇、投影、并、差、笛卡爾積是五種基本操作。（數(shù)據(jù)庫）數(shù)據(jù)庫故障的種類1、事務(wù)內(nèi)部的故障2、系統(tǒng)故障3.介質(zhì)故障4.計算機病毒（數(shù)據(jù)庫）SQL的主鍵約束和唯一約束有什么區(qū)別主鍵不能為空而唯一可以為空相同的就是都不允許重復(fù)（數(shù)據(jù)庫）2PL協(xié)議1)兩段鎖協(xié)議是指所有事務(wù)必須分兩個階段對數(shù)據(jù)項加鎖和解鎖。1)在對任何數(shù)據(jù)進(jìn)行讀、寫操作之前，首先要申請并獲得對該數(shù)據(jù)的封鎖；2)在釋放一個封鎖之后，事務(wù)不再申請和獲得任何其他封鎖。“兩段”的含義是，事務(wù)分為兩個階段：第一階段是獲得封鎖，也稱為擴展階段。在這階段，事務(wù)可以申請獲得任何數(shù)據(jù)項上的任何類型的鎖，但是不能釋放任何鎖。第二階段是釋放封鎖，也稱為收縮階段。在這階段，事務(wù)釋放已經(jīng)獲得的鎖，但是不能再申請任何鎖。（數(shù)據(jù)庫）關(guān)系完整性包括哪三個方面1.實體完整性2.參照完整性3.用戶定義的完整性（數(shù)據(jù)庫）數(shù)據(jù)庫恢復(fù)策略有哪幾種1.數(shù)據(jù)轉(zhuǎn)儲（數(shù)據(jù)冗余）2.日志文件、（？）數(shù)據(jù)字典通常包含5個部分1.數(shù)據(jù)項2.數(shù)據(jù)結(jié)構(gòu)3.數(shù)據(jù)流4.數(shù)據(jù)存儲5.處理過程（數(shù)據(jù)庫）視圖（View）的作用及優(yōu)點（數(shù)據(jù)庫）數(shù)據(jù)庫三要素數(shù)據(jù)模型的三要素：一般而言，數(shù)據(jù)模型是一組嚴(yán)格定義的概念的集合。這些概念精確地描述了系統(tǒng)的靜態(tài)特征（數(shù)據(jù)結(jié)構(gòu)）、動態(tài)特征（數(shù)據(jù)操作）和完整性約束條件，這就是數(shù)據(jù)模型的三要素。（數(shù)據(jù)庫）索引技術(shù)、日志文件目的：提供多種存儲路徑，加快查找速度。建立索引需要考慮的問題：1.沒有查詢、統(tǒng)計的需要則不建2.數(shù)據(jù)增刪改頻繁，系統(tǒng)會花費許多時間來維護(hù)索引，從而降低了查詢效率（數(shù)據(jù)庫）完整性與安全性的區(qū)別完整性和安全性是兩個不同的概念。前者是為了防止數(shù)據(jù)庫中存在不符合語義的數(shù)據(jù)，防止錯誤信息的輸入和輸出造成的無效操作和錯誤結(jié)果，而后者是防止數(shù)據(jù)庫被惡意的破壞和非法的存取。當(dāng)然，完整性和安全性是密切相關(guān)的。特別是從系統(tǒng)實現(xiàn)的方法來看，某一種機制常常既可以用于安全保護(hù)亦可用于完整性保證。（離散）無向圖中某條邊出現(xiàn)在所有生成樹中的充要條件這條邊是割邊（刪去這條邊后，連通分支會增加）（編譯）LR(0)（離散）一棵樹有1個度為4的結(jié)點，1個度為3的結(jié)點，1個度為2的結(jié)點，其余全為葉子結(jié)點，問一共有多少個葉子？5個（編譯/離散）閉包運算數(shù)學(xué)中，對一個集合的成員進(jìn)行某種運算，生成的仍然是這個集合的成員，則該集合被稱為在某個運算下閉合。例如，實數(shù)在減法下閉合，但自然數(shù)不行:自然數(shù)3和7的減法3?7的結(jié)果不是自然數(shù)。（離散）17條邊的簡單圖最少多少個頂點n階完全圖的邊數(shù)n(n-1)/2，完全圖的度是最大的n>=7（軟工）白盒測試、黑盒測試黑盒測試也稱功能測試或數(shù)據(jù)驅(qū)動測試，它是在已知產(chǎn)品所應(yīng)具有的功能，通過測試來檢測每個功能是否都能正常使用，在測試時，把程序看作一個不能打開的黑盆子，在完全不考慮程序內(nèi)部結(jié)構(gòu)和內(nèi)部特性的情況下，測試者在程序接口進(jìn)行測試，它只檢查程序功能是否按照需求規(guī)格說明書的規(guī)定正常使用，程序是否能適當(dāng)?shù)亟邮蛰斎霐?shù)鋸而產(chǎn)生正確的輸出信息，并且保持外部信息（如數(shù)據(jù)庫或文件）的完整性。白盒測試也稱結(jié)構(gòu)測試或邏輯驅(qū)動測試，它是知道產(chǎn)品內(nèi)部工作過程，可通過測試來檢測產(chǎn)品內(nèi)部動作是否按照規(guī)格說明書的規(guī)定正常進(jìn)行，按照程序內(nèi)部的結(jié)構(gòu)測試程序，檢驗程序中的每條通路是否都有能按預(yù)定要求正確工作，而不顧它的功能，白盒測試的主要方法有邏輯驅(qū)動、基路測試等，主要用于軟件驗證。灰盒測試，確實是介于二者之間的，可以這樣理解，灰盒測試關(guān)注輸出對于輸入的正確性，同時也關(guān)注內(nèi)部表現(xiàn)，但這種關(guān)注不象白盒那樣詳細(xì)、完整，只是通過一些表征性的現(xiàn)象、事件、標(biāo)志來判斷內(nèi)部的運行狀態(tài)，有時候輸出是正確的，但內(nèi)部其實已經(jīng)錯誤了，這種情況非常多，如果每次都通過白盒測試來操作，效率會很低，因此需要采取這樣的一種灰盒的方法。（離散）獨異點的*運算表包涵什么通常也會多加上另一個公理：（離散）什么是聯(lián)結(jié)詞完備集設(shè)S是一個聯(lián)結(jié)詞集合，如果任何n(n≥1)元真值函數(shù)都可以由僅含S中的聯(lián)結(jié)詞構(gòu)成的公式表示，則稱S是聯(lián)結(jié)詞完備集S={┐,∧,∨}是聯(lián)結(jié)詞完備集（軟工）什么是UML統(tǒng)一建模語言（UML，英語：UnifiedModelingLanguage）是非專利的第三代建模和規(guī)約語言。UML是一種開放的方法，用于說明、可視化、構(gòu)建和編寫一個正在開發(fā)的、面向?qū)ο蟮?、軟件密集系統(tǒng)的制品的開放方法。UML展現(xiàn)了一系列最佳工程實踐，這些最佳實踐在對大規(guī)模，復(fù)雜系統(tǒng)進(jìn)行建模方面，特別是在軟件架構(gòu)層次已經(jīng)被驗證有效。（算法）闡述對一個數(shù)據(jù)集進(jìn)行等價類劃分的基本思想和過程并查集應(yīng)用:數(shù)據(jù)結(jié)構(gòu)書p267（離散）簡述歐拉回路的基本含義及一個應(yīng)用。另，哈密頓回路對于一個給定的連通圖，怎樣判斷是否存在著一個恰好包含了所有的邊，并且沒有重復(fù)的路徑？這就是一筆畫問題。用圖論的術(shù)語來說，就是判斷這個圖是否是一個能夠遍歷完所有的邊而沒有重復(fù)。這樣的圖現(xiàn)稱為歐拉圖。這時遍歷的路徑稱作歐拉路徑（一個環(huán)或者一條鏈），如果路徑閉合（一個圈），則稱為歐拉回路一筆畫問題哈密頓圖（英語：Hamiltonianpath，或Traceablepath）是一個無向圖，由天文學(xué)家哈密頓提出，由指定的起點前往指定的終點，途中經(jīng)過所有其他節(jié)點且只經(jīng)過一次。在圖論中是指含有哈密頓回路的圖，閉合的哈密頓路徑稱作哈密頓回路（Hamiltoniancycle），含有圖中所有頂?shù)穆窂椒Q作哈密頓路徑。第29/33頁（？）簡述對一個集合可能的表示方法（至少描述兩種）列舉法，描述法..（離散）簡述邏輯命題與邏輯謂詞的關(guān)系？（編譯）簡述用于定義語言句法的文法類型及其主要特征喬姆斯基把方法分成四種類型，即0型、1型、2型和3型。0型，無限制文法。無限制文法是對文法的產(chǎn)生式左右兩側(cè)都沒有限制的。1型，上下文相關(guān)文法。此文法對應(yīng)于線性有界自動機。它是在0型文法的基礎(chǔ)上每一個α→β,都有|β|>=|α|。這里的|β|表示的是β的長度。另外允許Sε2型，上下文無關(guān)文法。它對應(yīng)于下推自動機。2型文法是在1型文法的基礎(chǔ)上,再滿足：每一個α→β都有α是非終結(jié)符。如A->Ba,符合2型文法要求。3型，正規(guī)文法。它對應(yīng)于有限狀態(tài)自動機。它是在2型文法的基礎(chǔ)上滿足:A→α|αB（右線性）或A→α|Bα（左線性）。（編譯）簡述預(yù)測分析法LL(1)的基本思想自頂向下句法分析以文法開始符號為根，試圖構(gòu)造以輸入符號串為樹葉的推導(dǎo)樹，每次都以最左邊的那個非終結(jié)符為子樹根，選擇適當(dāng)?shù)漠a(chǎn)生式