云南大學(xué)歷年計(jì)算機(jī)專(zhuān)業(yè)復(fù)試題

1、精選優(yōu)質(zhì)文檔傾情為你奉上精選優(yōu)質(zhì)文檔傾情為你奉上專(zhuān)心專(zhuān)注專(zhuān)業(yè)專(zhuān)心專(zhuān)注專(zhuān)業(yè)精選優(yōu)質(zhì)文檔傾情為你奉上專(zhuān)心專(zhuān)注專(zhuān)業(yè)數(shù)據(jù)結(jié)構(gòu)云南大學(xué) 抽兩道題并答題。從一個(gè)大盒子里面抽倆，每個(gè)紙條上面的題目只有1個(gè)。根據(jù)回答情況追問(wèn)，復(fù)試去的早的話，如果早上，那么老師問(wèn)的比較多。學(xué)碩最長(zhǎng)30分鐘（前幾個(gè)進(jìn)去的同學(xué)）。專(zhuān)碩最短不到10分鐘。老師如果感覺(jué)一天復(fù)試不完那么就會(huì)壓縮時(shí)間，每個(gè)同學(xué)進(jìn)入房間 自我介紹（有的是中文，有的是英文），英語(yǔ)抽提，一個(gè)題有100多個(gè)單詞，特別短，生詞不多，read and translate 翻譯結(jié)束英語(yǔ)就結(jié)束了。接下來(lái)是專(zhuān)業(yè)問(wèn)題抽提了。倆指頭寬度的紙片，20多厘米長(zhǎng)。塞滿一個(gè)塑料盒子，疊

2、著的。這篇文章里面的題能碰到1個(gè)就nice了。我就碰到了一個(gè)，是我瞄到一張沒(méi)有完全折疊好的紙片，我熟悉那個(gè)問(wèn)題所以perfect。專(zhuān)業(yè)題特別雜，看運(yùn)氣英語(yǔ)好的，能看懂句子成分的就不用準(zhǔn)備英語(yǔ)了，下午去的同學(xué)，就隨便準(zhǔn)備一些英語(yǔ)問(wèn)題，your family ,your university ,why, and your outlook?可能會(huì)問(wèn)，時(shí)間緊就不問(wèn)了，逆置一個(gè)順序表，鏈表順序表逆置:由于順序表是連續(xù)存儲(chǔ)的,循環(huán)表廠的一半，交換第一個(gè)和最后一個(gè)元素。i 交換 length-i，每做一次循環(huán)，i+。逆置一個(gè)鏈表： 先保存第一個(gè)數(shù)據(jù)節(jié)點(diǎn)，p=L-next,后把頭結(jié)點(diǎn)摘下 L-next=NUL

3、L; 遍歷p的鏈表，頭插法插入L表。遍歷完出來(lái)L就是逆置的。 排序一個(gè)順序表，鏈表順序表排序：2路歸并排序，堆排序，冒泡排序，插入排序。折半插入排序排序鏈表：我們假設(shè)遞增有序，采用直接插入排序法。先構(gòu)造一個(gè)只有一個(gè)數(shù)據(jù)節(jié)點(diǎn)的有序單鏈表，然后外層循環(huán)依次遍歷源單鏈表剩余節(jié)點(diǎn)，直到遍歷結(jié)束，內(nèi)層循環(huán)在有序單鏈表中比較大小查找合適節(jié)點(diǎn)插入。把一個(gè)有序單鏈表A插入另一個(gè)有序單鏈表B，合成的B鏈表任然有序：掃描A鏈表，取下節(jié)點(diǎn)，掃描B鏈表找到合適節(jié)點(diǎn)插入，若發(fā)現(xiàn)A鏈表空，則結(jié)束，若發(fā)現(xiàn)A鏈表不為空，B鏈表為空，則直接將A中剩余節(jié)點(diǎn)放入B中。改進(jìn)方法：當(dāng)我從A中取下節(jié)點(diǎn)插入B后，記錄該節(jié)點(diǎn)的值。下次掃描B

4、鏈表找合適的位置時(shí)就不用每次從第一個(gè)節(jié)點(diǎn)掃描。把一個(gè)有序順序表插入另一個(gè)有序順序表，合成的順序表任然有序：數(shù)據(jù)結(jié)構(gòu)三要素：邏輯結(jié)構(gòu)，物理結(jié)構(gòu)和數(shù)據(jù)的運(yùn)算邏輯結(jié)構(gòu)：指的是元素之間的邏輯關(guān)系，和數(shù)據(jù)怎么存儲(chǔ)無(wú)關(guān)。邏輯結(jié)構(gòu)一般分為線性結(jié)構(gòu)和非線性結(jié)構(gòu)線性表、樹(shù)、圖等數(shù)據(jù)結(jié)構(gòu)，其核心是如何組織待處理的數(shù)據(jù)以及數(shù)據(jù)之間的關(guān)系物理結(jié)構(gòu)，也叫做存儲(chǔ)結(jié)構(gòu)。如何將線性表、樹(shù)、圖等數(shù)據(jù)結(jié)構(gòu)存儲(chǔ)到計(jì)算機(jī)的存儲(chǔ)器中，其核心是如何有效地存儲(chǔ)數(shù)據(jù)以及數(shù)據(jù)之間的邏輯關(guān)系；算法：，求解特定問(wèn)題步驟的描述，他是指令的有限序列如何基于數(shù)據(jù)的某種存儲(chǔ)結(jié)構(gòu)實(shí)現(xiàn)插入、刪除、查找等基本操作，其核心是如何有效地處理數(shù)據(jù) 有窮，確定，可行性

5、，輸入 輸出52數(shù)組和線性表都是一組類(lèi)型相同的數(shù)據(jù)元素的有序集合，而廣義表的數(shù)據(jù)元素可以有不同的結(jié)構(gòu)，廣義表的元素可以是子表，而子表的元素還可以是廣義表，數(shù)組是順序存儲(chǔ)的，鏈表既可以順序又可以鏈?zhǔn)?，廣義表一般用鏈?zhǔn)酱鎯?chǔ)廣義表是一個(gè)多層次結(jié)構(gòu)，他有長(zhǎng)度（最外層包含元素個(gè)數(shù)）和深度（包含括弧的重?cái)?shù)）的概念，一個(gè)廣義表可以為其他廣義表共享，而數(shù)組沒(méi)有這個(gè)概念，數(shù)組有了名字，那他就有了一塊連續(xù)的存儲(chǔ)空間,不能被其他數(shù)組搶占和共享。線性表也可以共享，只要一個(gè)表中某個(gè)元素的后繼是另一塊表的一個(gè)元素，那就可以共享了。廣義表可以是遞歸的表，鏈表也有循環(huán)單鏈表和循環(huán)雙鏈表。在存儲(chǔ)結(jié)構(gòu)上，單鏈表可以有頭結(jié)點(diǎn)，單鏈

6、表的節(jié)點(diǎn)有指針域和數(shù)據(jù)域組成，數(shù)字沒(méi)有這個(gè)概念，只有值，但是數(shù)組有下標(biāo)，廣義表的表節(jié)點(diǎn)由三個(gè)域組成，標(biāo)志域，指示表頭的指針域(hp)和指向下一個(gè)元素的指針域（tp）。什么是堆？什么是棧？什么是隊(duì)列？有何區(qū)別？棧：只允許一端進(jìn)行插入刪除，的線性表。他的特點(diǎn)是先進(jìn)去的后出來(lái)。隊(duì)列：是一種操作受限的線性表，他只允許在一端口插入，另一端口刪除。特點(diǎn)是先進(jìn)先出。 棧和隊(duì)列都不允許隨便讀取或者刪除中間的元素。堆的特征是什么，如何利用堆進(jìn)行排序堆是一個(gè)完全二叉樹(shù)。而且最大元素存放在根節(jié)點(diǎn)，任意一個(gè)非根節(jié)點(diǎn)，他的值小于或者等于雙親節(jié)點(diǎn)的值 ，這是大根對(duì)，小根堆與之相反堆排序第一步：構(gòu)造一個(gè)初始堆，關(guān)鍵在于篩選

7、。對(duì)于大根堆來(lái)說(shuō)，就是若雙親節(jié)點(diǎn)的關(guān)鍵字小于左右子女的話，那就選取一個(gè)大子女和雙親交換。從下向上依次交換知道根節(jié)點(diǎn)為最大。初始大根堆建好了第二步：輸出堆頂節(jié)點(diǎn)，用堆底元素填充根節(jié)點(diǎn)，輸出的元素放在底部。因?yàn)槎盐覀冇玫氖菙?shù)組存儲(chǔ)，輸出元素一般在數(shù)組末尾。 此時(shí)我們破壞了大根堆，所以要調(diào)整這個(gè)堆，這個(gè)堆已經(jīng)不再包含輸出元素，盡管輸出元素還在堆上，但是堆是數(shù)組存儲(chǔ)的，把根節(jié)點(diǎn)（一般比較?。┫蛳潞妥优粨Q以維持大根堆性質(zhì)。第三部 再次輸出根節(jié)點(diǎn)，重復(fù)上述步驟知道堆僅僅剩下一個(gè)元素為止。數(shù)據(jù)結(jié)構(gòu)中圖的存儲(chǔ)中，鄰接矩陣和鄰接表的優(yōu)缺點(diǎn)？答：圖有鄰接矩陣和鄰接表兩種存儲(chǔ)方式 所謂鄰接矩陣就是，用一維數(shù)組存儲(chǔ)

8、圖的頂點(diǎn)信息，用二維數(shù)組存儲(chǔ)圖的邊的信息（各個(gè)頂點(diǎn)之間的關(guān)系。）所謂鄰接表，就是用順序存儲(chǔ)的方式存儲(chǔ)圖的頂點(diǎn)，用連式存儲(chǔ)存依附于此頂點(diǎn)的邊。優(yōu)缺點(diǎn)：鄰接矩陣清晰明了，容易看出各個(gè)頂點(diǎn)是否有邊相連。而鄰接表則不能給人清晰的表示，他要在響應(yīng)的節(jié)點(diǎn)對(duì)應(yīng)的邊表查找節(jié)點(diǎn)。 但是鄰接矩陣的存儲(chǔ)效率比較差，如果圖比較稀疏，那么矩陣就會(huì)有很大存儲(chǔ)單元被浪費(fèi)了，而我們的鄰接表由于采用鏈?zhǔn)酱鎯?chǔ)存儲(chǔ)邊的關(guān)系，所以避免了這種浪費(fèi)。 在查找邊的個(gè)數(shù)方面，鄰接矩陣要檢測(cè)整個(gè)矩陣，時(shí)間是O(n)而鄰接表很容易找出所有的鄰邊，只用讀取對(duì)應(yīng)頂點(diǎn)的鄰接表就行了。在有向圖求初度和入度方面，采用鄰接矩陣，第一行非零元素個(gè)數(shù)就是頂點(diǎn)V

9、1的出度，第一列非零個(gè)數(shù)就是V1的入度。而鄰接表在求出度方面只需遍歷邊表中節(jié)點(diǎn)個(gè)數(shù)，在求入度方面要遍歷整個(gè)表。十字鏈表是有向圖的一中鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)，包括弧節(jié)點(diǎn)(狐尾虎頭，兩個(gè)弧鏈域，弧頭相同的在一個(gè)鏈表，狐尾相同的在一個(gè)鏈表)和頂點(diǎn)節(jié)點(diǎn)(數(shù)據(jù)域和兩個(gè)鏈域，一個(gè)表示弧的起點(diǎn)(out)，一個(gè)表示弧的終點(diǎn)(in)，所以容易求節(jié)點(diǎn)的入度和出度。一個(gè)圖的十字鏈表不是唯一的，但一個(gè)十字鏈表確定一個(gè)圖。鄰接多重鏈表是無(wú)向圖的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)程序的健壯性？答：對(duì)于不規(guī)范的輸入能夠做出反應(yīng)而不會(huì)產(chǎn)生奇怪的費(fèi)解的輸出結(jié)果。數(shù)據(jù)結(jié)構(gòu)中排序的穩(wěn)定性？答：對(duì)于待排序列中的值相等的元素來(lái)說(shuō)比如a1= a2 ，如果排序結(jié)果沒(méi)有改

10、變這些值相等元素的相對(duì)位置，還是a1在前a2在后面。那么算法就是穩(wěn)定的任意兩個(gè)節(jié)點(diǎn)的最短路徑？答：迪杰斯特拉算法最小生成樹(shù)：在圖所有生成樹(shù)中，代價(jià)最小的生成樹(shù)稱(chēng)為最小生成樹(shù)。他包含圖的所有頂點(diǎn)，并且包含盡可能少的邊最小生成樹(shù)不是唯一的，可以有多個(gè)，當(dāng)圖中邊的權(quán)值互不相等，那么最小生成樹(shù)就是唯一的。最小生成樹(shù)的權(quán)值之和是唯一的，他的邊數(shù)是頂點(diǎn)個(gè)數(shù)減去1構(gòu)造生成樹(shù)的算法：普利姆算法O(V2),適合求解邊多，點(diǎn)少的圖和克魯斯卡爾O(ElogE)算法，適合求解邊少，點(diǎn)多的圖。歐拉圖： 具有歐拉回路的圖就是歐拉圖。歐拉回路是 圖中經(jīng)過(guò)每條邊切僅僅一次經(jīng)過(guò)的回路叫做歐拉回路。那些圖有歐拉回路？ 1 無(wú)向圖

11、中，當(dāng)且僅當(dāng)圖是連通圖，而且圖沒(méi)有奇數(shù)度的頂點(diǎn)。 2 有相圖，當(dāng)且僅當(dāng)圖是聯(lián)通的，且所有的頂點(diǎn)的入度=初度。哈密頓圖 有哈密頓回路的圖。哈密頓回路 經(jīng)過(guò)每個(gè)頂點(diǎn)一次且僅僅一次的初級(jí)回路。 哈密頓通路 經(jīng)過(guò)每個(gè)頂點(diǎn)一次且僅一次的通路。哈密頓圖必然是連通圖。在n個(gè)城市之間建造通信網(wǎng)絡(luò)，至少要架設(shè)n-1條通信線路，而每?jī)蓚€(gè)城市之間架設(shè)通信線路的造價(jià)是不一樣的，那么如何設(shè)計(jì)才能使得總造價(jià)最小最小生成樹(shù)算法，生成樹(shù)邊的權(quán)重之和最小。什么是最小連通子圖？既要保存圖聯(lián)通，又要保持圖的邊數(shù)最少。一個(gè)聯(lián)通圖的生成樹(shù)是圖的最小連通圖。他包含圖的所有頂點(diǎn)，包含盡可能少的邊。如果砍去其中任意一條，都會(huì)讓樹(shù)變成非聯(lián)通圖

12、。如果給他增加一條邊，那就形成圖的一條回路。如何產(chǎn)生最小連通圖？ 那不就是生成樹(shù)么，生成樹(shù)有深度優(yōu)先遍歷和廣度優(yōu)先遍歷算法；最小生成樹(shù)有兩種算法，克魯斯卡爾和普里姆算法。 But無(wú)向圖的極大聯(lián)通子圖是無(wú)向圖的聯(lián)通分量。 有向圖的極大聯(lián)通子圖叫做有向圖的強(qiáng)聯(lián)通分量。 怎樣防止出現(xiàn)環(huán)？第一中方法要拓?fù)渑判蚍椒?。在一個(gè)有向圖中，我們采用拓?fù)渑判?，拓?fù)渑判蛞笕绻硞€(gè)節(jié)點(diǎn)出現(xiàn)在另一個(gè)節(jié)點(diǎn)的前面如 先A后B，那么接下來(lái)的排序中就不用該出現(xiàn)先B后A的路徑。對(duì)有向圖的拓?fù)渑判颍绻l(fā)現(xiàn)不存在拓?fù)渑判?，或者是排序沒(méi)走完，剩下的圖中不存在前驅(qū)的頂點(diǎn)，那就說(shuō)明圖中有環(huán)。第二種方法：求關(guān)鍵路徑。關(guān)鍵路徑本身就要求無(wú)

13、環(huán)，一個(gè)工程的某個(gè)節(jié)點(diǎn)不能既是下一個(gè)節(jié)點(diǎn)開(kāi)始的前提條件，又是下一個(gè)節(jié)點(diǎn)的產(chǎn)出；求關(guān)鍵路徑也要求拓?fù)渑判蛩砸部梢詠?lái)判斷有沒(méi)有環(huán)路。第三種方法：采用圖的深度優(yōu)先遍歷算法。一條深度遍歷路線中如果某個(gè)節(jié)點(diǎn)被第二次訪問(wèn)到，那就有環(huán)，因?yàn)樯疃葍?yōu)先路徑是一條單鏈，訪問(wèn)過(guò)的節(jié)點(diǎn)保存下來(lái)就不應(yīng)該再次被訪問(wèn)。拓?fù)渑判蚝推?，全序的關(guān)系：選課，課程之間有先后關(guān)系，制定選課順序過(guò)程就是拓?fù)渑判虻倪^(guò)程。選課關(guān)系中有課程先后的關(guān)系，也有課程間沒(méi)有特定順序的關(guān)系，但是不允許出現(xiàn)1221這種互相矛盾的關(guān)系也就是環(huán)路。有向無(wú)環(huán)圖兩個(gè)頂點(diǎn)不存在環(huán)路，必然滿足偏序關(guān)系。 如果任意兩個(gè)課程之間只有先后關(guān)系，并且沒(méi)有換，那就是全序關(guān)

14、系。原來(lái)的偏序變成了全序。排序算法1 2 3 4，大小關(guān)系確定，唯一的，則這個(gè)序列滿足全序關(guān)系。表現(xiàn)在拓?fù)渑判蛑芯褪敲總€(gè)頂點(diǎn)間都具有全序關(guān)系，則拓?fù)渑判蚪Y(jié)果唯一。若是偏序的關(guān)系，那就不唯一了。有向無(wú)環(huán)圖在實(shí)際生活中的應(yīng)用例子？日常導(dǎo)航嘛。區(qū)塊鏈領(lǐng)域。什么是哈希表？如何構(gòu)建哈希表？在構(gòu)建哈希表過(guò)程中，會(huì)遇到什么問(wèn)題，如何解決？答：哈希表（Hash table，也叫散列表），是根據(jù)關(guān)鍵碼值(Key value)而直接進(jìn)行訪問(wèn)的數(shù)據(jù)結(jié)構(gòu)，他建立了關(guān)鍵字和存儲(chǔ)地址之間的一種直接映射關(guān)系。怎么構(gòu)建哈希表：在記錄的存儲(chǔ)位置和它的關(guān)鍵字之間建立一個(gè)確定的對(duì)應(yīng)關(guān)系f即哈希函數(shù)。使每個(gè)關(guān)鍵字和表中唯一的存儲(chǔ)位置

15、相對(duì)應(yīng)，根據(jù)這個(gè)思想建立的表為哈希表哈希表的做法其實(shí)很簡(jiǎn)單，首先要構(gòu)造一個(gè)哈希函數(shù)，哈希函數(shù)的構(gòu)造有直接定址法，除留余數(shù)法，平方取中法等等。我們那除留余數(shù)法做例子在，這個(gè)比較簡(jiǎn)單，也比較常用。關(guān)鍵字對(duì)一個(gè)不大于散列表長(zhǎng)度的一個(gè)素?cái)?shù)取余。取余結(jié)果就當(dāng)作關(guān)鍵字的地址，關(guān)鍵字可以存放在數(shù)組里，（也可以存放在二叉樹(shù)）構(gòu)造這個(gè)散列表的過(guò)程中會(huì)遇到幾個(gè)關(guān)鍵字映射到一個(gè)地址上面，也就產(chǎn)生了沖突。原因在于散列函數(shù)選取不當(dāng)。處理沖突有 開(kāi)放定址法：線性探測(cè) 查看下一個(gè)單元，鏈地址法：把所有同義詞存放在一個(gè)鏈表里。不過(guò)對(duì)鏈表查找效率會(huì)變低，我們可以在鏈表上構(gòu)建一平衡二叉樹(shù)。Hashmap是什么：稀疏矩陣？答：如果

16、在矩陣中，多數(shù)的元素為0，通常認(rèn)為非零元素比上矩陣所有元素的值小于等于0.05時(shí)，則稱(chēng)此矩陣為稀疏矩陣（sparse matrix）。AOE網(wǎng)的始點(diǎn)和終點(diǎn)是什么？正常的AOE網(wǎng)只有一個(gè)始點(diǎn)和終點(diǎn)嗎？答：關(guān)鍵路徑（臨界路徑）：在AOE網(wǎng)絡(luò)中從源點(diǎn)到匯點(diǎn)（結(jié)束頂點(diǎn)）的最大路長(zhǎng)度的路徑。關(guān)鍵路徑可以有多條起始點(diǎn)：入度為0的點(diǎn) 1個(gè) 終點(diǎn)：僅有一個(gè)也叫做匯點(diǎn) 出度為0關(guān)鍵路徑上的活動(dòng)為關(guān)鍵活動(dòng)，帶權(quán)有向圖中若以頂點(diǎn)表示事件，有向邊表示活動(dòng)，邊上的權(quán)值表示該活動(dòng)持續(xù)的時(shí)間怎么能夠判斷判斷一個(gè)圖是連通還是非連通的？答：對(duì)于無(wú)向圖來(lái)說(shuō)，如果無(wú)向圖聯(lián)通的，那么從任意一個(gè)點(diǎn)出發(fā)，僅需要一次遍歷就能訪問(wèn)所有的點(diǎn)。

17、 如果是非聯(lián)通的，則從任意一個(gè)頂點(diǎn)出發(fā)，一次遍歷只能訪問(wèn)此頂點(diǎn)所在聯(lián)通分量的所有頂點(diǎn)，而剩余的節(jié)點(diǎn)無(wú)法通過(guò)這次遍歷訪問(wèn)。對(duì)于有向圖來(lái)說(shuō)，若從初始點(diǎn)到圖中的每個(gè)頂點(diǎn)都有路徑，那么一次遍歷就可以訪問(wèn)所有的點(diǎn)，否則可以借助深度優(yōu)先遍歷，如果能遍歷所有的點(diǎn)，那他就是聯(lián)通的有向圖和無(wú)向圖的聯(lián)系,試各舉一例說(shuō)明？答：無(wú)向圖可以看作每條邊都有兩個(gè)方向的有向圖，寫(xiě)成鄰接矩陣的形式的話區(qū)別就很清楚；無(wú)向圖的鄰接矩陣一定是對(duì)稱(chēng)陣,而有向圖則未必實(shí)際應(yīng)用的區(qū)別是有向圖可以描述非對(duì)稱(chēng)的關(guān)系,但無(wú)向圖不能.比如你認(rèn)識(shí)奧巴馬,但是他不認(rèn)識(shí)你,用圖來(lái)表示人物關(guān)系時(shí)就將你和奧巴馬之間連一條線,并且指向他.可以用來(lái)解決加快工程

18、進(jìn)度的問(wèn)題。無(wú)向圖和有向圖都可以用來(lái)尋找最優(yōu)路徑。有向圖解決最低路徑成本問(wèn)題。無(wú)向圖能解決的問(wèn)題都能用有向圖表示,但是無(wú)向圖在對(duì)稱(chēng)的問(wèn)題上往往更容易,因?yàn)橛糜邢驁D去表示無(wú)向圖時(shí)需要用兩倍的邊數(shù)。堆排序的思想是什么?答：n個(gè)關(guān)鍵字序列Kl，K2，Kn稱(chēng)為堆，當(dāng)且僅當(dāng)該序列滿足如下性質(zhì)(簡(jiǎn)稱(chēng)堆性質(zhì))：(1)kiK2i且kiK2i+1或(2)KiK2i且kiK2i+1(1iFLOOR(n/2)若將此序列所存儲(chǔ)的向量R1.n看做是一棵完全二叉樹(shù)的存儲(chǔ)結(jié)構(gòu)，則堆實(shí)質(zhì)上是滿足如下性質(zhì)的完全二叉樹(shù)：樹(shù)中任一非葉結(jié)點(diǎn)的關(guān)鍵字均不大于(或不小于)其左右孩子(若存在)結(jié)點(diǎn)的關(guān)鍵字。知道一棵樹(shù)的先序和后序能不能確定

19、它?要證明.答：不能，必須知道中序。這是因?yàn)橥瑯拥那靶虮闅v和后序遍歷序列，可以對(duì)應(yīng)不同的二叉樹(shù)。完全二叉樹(shù)的性質(zhì)：度數(shù)為1的節(jié)點(diǎn)只有1個(gè)或者1個(gè)沒(méi)有。葉子節(jié)點(diǎn)只可能在最大兩層出現(xiàn)，而且對(duì)于最大層次中的葉子節(jié)點(diǎn)，依次排列在該層最左邊的位置。若有N個(gè)元素，則：N為奇數(shù)，每個(gè)分支節(jié)點(diǎn)都有左右子女； N為偶數(shù)，則n/2的節(jié)點(diǎn)只有做子女，沒(méi)有有子女。如何判斷完全二叉樹(shù)：采用層次遍歷，根據(jù)完全二叉樹(shù)的性質(zhì)，如果遍歷遇到了一個(gè)空節(jié)點(diǎn)，那么在這一層中該節(jié)點(diǎn)的后面就不應(yīng)該再有空節(jié)點(diǎn)。如果有，就不是。平衡二叉樹(shù)樹(shù)的任一節(jié)點(diǎn)的左子樹(shù)和右子樹(shù)的深度之差（平衡因子）不超過(guò)1.平衡二叉樹(shù)的節(jié)點(diǎn)平衡因子只能是-1,0,1他

20、的平均查找長(zhǎng)度為O(logN)。（赫夫曼）哈夫曼樹(shù)？答：給定n個(gè)權(quán)值作為n的葉子結(jié)點(diǎn)，構(gòu)造一棵二叉樹(shù)，若帶權(quán)路徑長(zhǎng)度達(dá)到最小，稱(chēng)這樣的二叉樹(shù)為最優(yōu)二叉樹(shù)，也稱(chēng)為哈夫曼樹(shù)(Huffman Tree)。哈夫曼樹(shù)是帶權(quán)路徑長(zhǎng)度最短的樹(shù)，權(quán)值較大的結(jié)點(diǎn)離根較近。帶權(quán)路徑長(zhǎng)度：從樹(shù)的根節(jié)點(diǎn)出發(fā)到任意節(jié)點(diǎn)的路徑長(zhǎng)度（經(jīng)過(guò)的邊數(shù)）與該節(jié)點(diǎn)上權(quán)值的乘積 叫做該節(jié)點(diǎn)的帶權(quán)路徑長(zhǎng)度。樹(shù)的帶權(quán)路徑長(zhǎng)度：樹(shù)中所有葉子節(jié)點(diǎn)的帶權(quán)路徑長(zhǎng)度之和叫做該樹(shù)的帶權(quán)路徑長(zhǎng)度一般用于數(shù)據(jù)壓縮處理，對(duì)于頻度高的數(shù)據(jù)字符賦短編碼 ，頻率較低的賦以長(zhǎng)編碼線索二叉樹(shù)二叉樹(shù)線索化的實(shí)質(zhì)就是對(duì)非線性結(jié)構(gòu)的線性化。為的是加快查找節(jié)點(diǎn)前驅(qū)和后繼的速

21、度。由于二叉鏈表存儲(chǔ)的二叉樹(shù)中存在大量空指針，我們用這些空鏈域存放指向其直接前驅(qū)和直接后繼的指針。在遍歷二叉樹(shù)的時(shí)候，檢查當(dāng)前節(jié)點(diǎn)左右指針域是否為空，若為空，則把他們改為指向前驅(qū)節(jié)點(diǎn)或者后繼節(jié)點(diǎn)的線索。在中序線索二叉樹(shù)中，如何找節(jié)點(diǎn)的直接前驅(qū)？在后序線索二叉樹(shù)中，如何找節(jié)點(diǎn)的直接前驅(qū)？計(jì)算機(jī)如何實(shí)現(xiàn)線索二叉樹(shù)的遍歷先說(shuō)中序線索查找前驅(qū)節(jié)點(diǎn)：在中序線索樹(shù)中找結(jié)點(diǎn)*p的中序直接前驅(qū)，也就是*p節(jié)點(diǎn)的左線索，查找他的左子樹(shù)，如果他的左子樹(shù)空，那么他的左線索就是他的直接前驅(qū)。 倘若左子樹(shù)不為空，有左孩子，那就從他的左孩子開(kāi)始查找，尋找左孩子的右子樹(shù)，當(dāng)右子樹(shù)為空的節(jié)點(diǎn)就是他的直接前驅(qū) 自己畫(huà)個(gè)圖看看就

22、知道了再說(shuō)后序線索查找前驅(qū)節(jié)點(diǎn)：如果節(jié)點(diǎn)p有子女，那么他的右子女就是他的直接前驅(qū)。 如果節(jié)點(diǎn)p沒(méi)有右子女，但是有左子女，那么他的左子女就是他的前驅(qū)。 如果節(jié)點(diǎn)p是個(gè)葉子節(jié)點(diǎn)，那么他的左線索就是他的直接前驅(qū) ！鏈表設(shè)置頭結(jié)點(diǎn)作用：不設(shè)頭結(jié)點(diǎn)時(shí)候，刪除其他節(jié)點(diǎn)沒(méi)什么問(wèn)題，但是刪除第一個(gè)節(jié)點(diǎn)就會(huì)有問(wèn)題，第一個(gè)節(jié)點(diǎn)要特殊化處理。引入頭結(jié)點(diǎn)使第一個(gè)節(jié)點(diǎn)和其他節(jié)點(diǎn)的處理可以統(tǒng)一化，寫(xiě)代碼就不用判斷了樹(shù)的遍歷種類(lèi)，確定一棵樹(shù)的方法？答：前序遍歷、中序遍歷和后序遍歷，層序遍歷。知道前序遍歷和中序遍歷可以確定一棵樹(shù)；知道后序遍歷和中序遍歷可以確定一棵樹(shù)。樹(shù)是否可以用順序存儲(chǔ)，如何存儲(chǔ)？答：可以。順序存儲(chǔ)的話，就

23、是存儲(chǔ)在數(shù)組中，數(shù)組的下標(biāo)就是二叉樹(shù)的結(jié)點(diǎn)位置（層次結(jié)構(gòu)），i的兩個(gè)孩子結(jié)點(diǎn)在數(shù)組中的位置是2i（左孩子）和2i+1（右孩子）。堆排序、快速排序和歸并排序，哪個(gè)輔助存儲(chǔ)空間最少，哪個(gè)平均速度最快，哪個(gè)穩(wěn)定？答：除了快速排序之外（快排的最佳情況和平均運(yùn)行時(shí)間很接近），其他排序的最壞情況和平均情況都是一樣的時(shí)間復(fù)雜度。用一個(gè)遞歸樹(shù)來(lái)表示，每次劃分排序均勻情況下，遞歸樹(shù)的深度LOG(N+1)，每一層的代價(jià)是O（N），這樣總的代價(jià)就是N(logN)選擇排序：簡(jiǎn)單選擇排序和堆排序的空間復(fù)雜度都是O(1)，因?yàn)樗皇褂贸?shù)個(gè)輔助空間。簡(jiǎn)單選擇排序的時(shí)間復(fù)雜度（即元素間的比較次數(shù)，就算有序的，元素頂多不用移

24、動(dòng)，但還是免不了要11比較）和最初序列狀態(tài)無(wú)關(guān)，始終是O(N2)?？焖倥判蛩枷胧腔诜种嗡惴ǖ模捶纸猓ǚ纸鉃閭z個(gè)數(shù)組），處理（通過(guò)遞歸調(diào)用快速排序），合并（這里倆個(gè)數(shù)組是就地排序，不用合并），是對(duì)冒泡的改進(jìn)。當(dāng)元素基本有序（正序或者逆序），他就退化為冒泡排序O（N2）;冒泡是相鄰兩個(gè)比較交換，而快排不是比較相鄰的，故排序算法不穩(wěn)定。他選取一個(gè)元素做為參考，比他大的放在左邊，比他小的放在右邊。然后再分別對(duì)左右兩個(gè)子序列遞歸地排序，需要一個(gè)遞歸工作棧來(lái)保存每一層遞歸調(diào)用的必要信息，最好情況的時(shí)間復(fù)雜度是nlog（n）,最好情況的空間復(fù)雜度是logN,最壞情況下的空間復(fù)雜度O(N)。快排的運(yùn)行時(shí)間

25、取決于劃分的平衡,而劃分是否對(duì)稱(chēng)和選擇哪一個(gè)元素進(jìn)行劃分有關(guān)。如果劃分對(duì)稱(chēng)的化，就與歸并算一樣，如果不對(duì)稱(chēng)，就和插入排序一樣慢了。 但若初始序列基本有序，則插入排序時(shí)間性能最好，而快排最差O(N2)最壞情況，劃分不對(duì)稱(chēng)下，假設(shè)每一次遞歸調(diào)用都出現(xiàn)了不對(duì)稱(chēng)，出現(xiàn)了劃分兩個(gè)區(qū)域，一塊n-1個(gè)，另一塊沒(méi)有元素，那么每一次遞歸調(diào)用都花費(fèi)O(N)，最終每一層疊加起來(lái)就是N2了。樹(shù)和圖之間的區(qū)別？答：樹(shù)是圖，圖不一定是樹(shù)，樹(shù)是圖的子集樹(shù)有一個(gè)根節(jié)點(diǎn)，圖沒(méi)有樹(shù)可以遞歸遍歷，圖要看情況樹(shù)有層次劃分，圖沒(méi)有樹(shù)的非根節(jié)點(diǎn)必定有一個(gè)父節(jié)點(diǎn)，圖不一定樹(shù)是一種“層次”關(guān)系，圖是“網(wǎng)絡(luò)”關(guān)系，圖可以有環(huán)，而樹(shù)不允許。樹(shù)可

26、以是空的，但是圖不允許空。靜態(tài)鏈表的數(shù)據(jù)結(jié)構(gòu)？答：靜態(tài)鏈表是借助數(shù)組來(lái)描述線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)。他也有指針域和數(shù)據(jù)域。所不同的是他是用游標(biāo)代替指針來(lái)指示節(jié)點(diǎn)在數(shù)組中的相對(duì)位置。而且他的插入刪除也不需要移動(dòng)數(shù)組元素。只用修改指針就行了。我們幾個(gè)人圍成一圈，從某個(gè)人開(kāi)始數(shù)數(shù)，數(shù)到3的人OUT，說(shuō)一下這個(gè)算法？答：這個(gè)可以用循環(huán)鏈表實(shí)現(xiàn)。兩個(gè)有序的鏈表A，B。如何把B的節(jié)點(diǎn)插入A鏈表，使之仍是有序的表？答：依次取B鏈表的節(jié)點(diǎn)，分別與A鏈表的節(jié)點(diǎn)的關(guān)鍵字比較，找到合適的位置插入即可。數(shù)據(jù)結(jié)構(gòu)順序表有哪些缺點(diǎn)，如何逆置一個(gè)鏈表？答：順序表的優(yōu)點(diǎn)是便于隨機(jī)存儲(chǔ)，缺點(diǎn)是不便于插入刪除等操作，因?yàn)椴迦雱h除一個(gè)

27、元素需要移動(dòng)其后的所有元素，但是鏈表不存在這個(gè)問(wèn)題，鏈表只要改變指針就行，時(shí)間復(fù)雜度小，所以鏈表于順序表恰恰相反，優(yōu)點(diǎn)是便于插入刪除等操作，缺點(diǎn)是隨機(jī)存儲(chǔ)沒(méi)有順序表方便。void linklist_oppse(LinkList &L)LinkList p,q;p=L;p=p-next;L-next=NULL;while(p)q=p;p=p-next;q-next=L-next;L-next=q;二分查找？答：二分查找又稱(chēng)折半查找，優(yōu)點(diǎn)是比較次數(shù)少，查找速度快，平均性能好；其缺點(diǎn)是要求待查表為有序順序表，不適合連式存儲(chǔ)。且插入刪除困難。因此，折半查找方法適用于不經(jīng)常變動(dòng)而查找頻繁的有序列表。查找

28、思想：首先將待查數(shù)據(jù)和排好順序的順序表中間的那個(gè)元素比較大小，假設(shè)是升序，如果比中間的大，那就縮小范圍查找右半部分的。依次縮小范圍找到返回，找不到就沒(méi)有。我們可以用一個(gè)判定樹(shù)來(lái)描述。分塊查找（索引順序查找）結(jié)合二分查找和順序查找的優(yōu)點(diǎn)。把查找表分成若干個(gè)子塊，塊里面的元素可以無(wú)序，但是塊間要有序。在建立一個(gè)索引表，索引表的組成：索引表含有每個(gè)各塊中第一個(gè)元素的地址和塊中最大元素的值，索引表按照關(guān)鍵字有序排序。分塊查找中，首先在索引表中可以用順序查找或者折半查找來(lái)確定待查元素在哪塊（哪個(gè)分區(qū)）； 然后第二步在快內(nèi)順序查找（只能用）。二路歸并的實(shí)質(zhì)是什么？答：歸并排序 基于分治算法，將兩個(gè)或兩個(gè)以

29、上的有序表組合成一個(gè)新的有序表。把待n個(gè)元素排序表看做n個(gè)子表組合而成，然后每?jī)蓚€(gè)子表歸并，得到長(zhǎng)度為2的新的子表，然后在兩兩歸并如此重復(fù)一直到合并成長(zhǎng)度為n的有序表為止。2路排序是一個(gè)穩(wěn)定的排序算法，時(shí)間效率是O(NlogN)一個(gè)無(wú)序的單鏈表怎樣能讓它變得有序，簡(jiǎn)單說(shuō)明一下算法？答：貪心算法是什么，能給出正確的答案嗎？答：貪心算法（又稱(chēng)貪婪算法）是指，在對(duì)問(wèn)題求解時(shí)，總是做出在當(dāng)前看來(lái)是最好的選擇。也就是說(shuō)，不從整體最優(yōu)上加以考慮，他所做出的每一步驟都是這個(gè)問(wèn)題的局部最優(yōu)解。貪心算法認(rèn)為一個(gè)全局最優(yōu)解可以同局部最優(yōu)選擇（貪心）來(lái)達(dá)到，that means，當(dāng)考慮到如何選擇時(shí)，我們只考慮當(dāng)前問(wèn)

30、題最佳的選擇，而不考慮子問(wèn)題的結(jié)果。這一點(diǎn)也是和動(dòng)態(tài)規(guī)劃不同的地方，動(dòng)態(tài)規(guī)劃認(rèn)為，每一步都要做出選擇，但這些選擇卻依賴(lài)于子問(wèn)題的解，因此動(dòng)態(tài)規(guī)劃問(wèn)題一般是自底向上，從下到大處理問(wèn)題。但在貪心算法中，我們所做的總是當(dāng)前最佳，不考慮之后有什么不妥的問(wèn)題，至于它產(chǎn)生的問(wèn)題，貪心繼續(xù)貪心的處理。所以他當(dāng)前所做出的選擇會(huì)在一定程度上依賴(lài)于他曾經(jīng)做出的決策，而不是依賴(lài)于那些尚未解決的子問(wèn)題。所以他通常是自頂向下處理子問(wèn)題，不斷的吧問(wèn)題分解為更小的問(wèn)題。齊王：上等馬 中等馬 下等馬田忌： 上等馬 中等馬 下等馬解決單源點(diǎn)最短路徑問(wèn)題。比如說(shuō)有點(diǎn)ABCDE，A是目標(biāo)點(diǎn)?，F(xiàn)在有兩個(gè)集合M(左手比劃，用來(lái)放搜尋到

31、距離M集合所含節(jié)點(diǎn)最短距離的節(jié)點(diǎn)，初始化放置目標(biāo)點(diǎn)A)和N（尚未找到最短路徑的節(jié)點(diǎn)BCDE，右手比劃），倆個(gè)集合都用數(shù)組來(lái)表示?，F(xiàn)在第一次循環(huán)，從集合M出發(fā)，搜索M里面的所有節(jié)點(diǎn)（只有A一個(gè)）能夠到達(dá)的最短路徑節(jié)點(diǎn)，找到后將其放入M中（左手），并從N、（右手）中刪除這個(gè)點(diǎn)。下一輪循環(huán)，從集合M（假設(shè)現(xiàn)在喲了A,B）出發(fā)，以最短路徑到達(dá)集合N中的節(jié)點(diǎn)，假設(shè)C。然后把C放入M中，并將其從N中刪除。動(dòng)態(tài)規(guī)劃算法，典型運(yùn)用？答：一、基本概念 動(dòng)態(tài)規(guī)劃通過(guò)組合子問(wèn)題的解而解決整個(gè)問(wèn)題。分治算法則是把問(wèn)題分解成一些獨(dú)立子問(wèn)題，遞歸的求解各個(gè)子問(wèn)題，然后合并子問(wèn)題的解得到原問(wèn)題的解。然而動(dòng)態(tài)規(guī)劃適用于子問(wèn)題

32、不是獨(dú)立的情況，也就是說(shuō)各個(gè)子問(wèn)題之間是有聯(lián)系的，不是獨(dú)立出來(lái)（分治算法）的。在這種情況下，如果我們利用分治，可能就會(huì)做許多不必要的動(dòng)作，可能會(huì)重復(fù)的求解公共的子問(wèn)題。所以動(dòng)態(tài)規(guī)劃要求每一個(gè)子問(wèn)題只求解一次，記錄這些子問(wèn)題的解。二、基本思想與策略 基本思想與分治法類(lèi)似，也是將待求解的問(wèn)題分解為若干個(gè)子問(wèn)題（階段），按順序求解子階段，前一子問(wèn)題的解，為后一子問(wèn)題的求解提供了有用的信息。在求解任一子問(wèn)題時(shí)，列出各種可能的局部解，通過(guò)決策保留那些有可能達(dá)到最優(yōu)的局部解，丟棄其他局部解。依次解決各子問(wèn)題，最后一個(gè)子問(wèn)題就是初始問(wèn)題的解。 由于動(dòng)態(tài)規(guī)劃解決的問(wèn)題多數(shù)有重疊子問(wèn)題這個(gè)特點(diǎn)，為減少重復(fù)計(jì)算，

33、對(duì)每一個(gè)子問(wèn)題只解一次，將其不同階段的不同狀態(tài)保存在一個(gè)二維數(shù)組中。與分治法最大的差別是：適合于用動(dòng)態(tài)規(guī)劃法求解的問(wèn)題，經(jīng)分解后得到的子問(wèn)題往往不是互相獨(dú)立的（即下一個(gè)子階段的求解是建立在上一個(gè)子階段的解的基礎(chǔ)上，進(jìn)行進(jìn)一步的求解）。用于解決：數(shù)學(xué)三角形問(wèn)題?；蛘咴趯?dǎo)航中選擇最優(yōu)路徑問(wèn)題。裝配線問(wèn)題：兩條裝配線執(zhí)行相同的功能，但是裝配速度不同。求解問(wèn)題是確定在裝配線1選擇那些站點(diǎn)，裝配線2選擇那些站點(diǎn)使得汽車(chē)通過(guò)工廠的時(shí)間最短。什么是多項(xiàng)式非確定性問(wèn)題？答：是一個(gè)數(shù)學(xué)問(wèn)題，我們所學(xué)的算法大多是多項(xiàng)式時(shí)間的算法，對(duì)于規(guī)模N的輸入，他們最壞情況運(yùn)行時(shí)間就是NK時(shí)間，是否所有問(wèn)題都可以在多項(xiàng)式時(shí)間內(nèi)

34、解決？，不是的。停機(jī)問(wèn)題，理發(fā)師悖論這些。NP完全問(wèn)題，他的狀態(tài)為止。NP是多項(xiàng)式復(fù)雜程度非確定性問(wèn)題（P對(duì)NP，P versus NP，polynomial versus nondeterministic polynomial）是指1971年Leonid Levin和Stephen Cook提出的一個(gè)關(guān)于容易解答的問(wèn)題（p型）以及相反的難以解答的問(wèn)題（NP型）的數(shù)學(xué)理論問(wèn)題。P問(wèn)題：一個(gè)問(wèn)題可以在多項(xiàng)式（O(nk)）的時(shí)間復(fù)雜度內(nèi)解決。NP問(wèn)題：一個(gè)問(wèn)題的解可以在多項(xiàng)式的時(shí)間內(nèi)被驗(yàn)證。大整數(shù)因式分解問(wèn)題-比如有人告訴你數(shù)可以分解成兩個(gè)數(shù)的乘積，你不知道到底對(duì)不對(duì)，但是如果告訴你這兩個(gè)數(shù)是11

35、23和8850，那么很容易就可以用最簡(jiǎn)單的計(jì)算器進(jìn)行驗(yàn)證。任何P型問(wèn)題都能夠按照“多項(xiàng)式時(shí)代”解答（一個(gè)多項(xiàng)式包含許多項(xiàng)，每個(gè)項(xiàng)又包括了一個(gè)變量或者是乘以一個(gè)系數(shù)的變量的冪。組成原理 是分組交換，其他電路交換和報(bào)文都是報(bào)文一個(gè)單元原碼:簡(jiǎn)單易懂，最大缺點(diǎn)就是加法運(yùn)算復(fù)雜，異號(hào)相加麻煩（比較絕對(duì)值，大數(shù)-小數(shù)）補(bǔ)碼可以減法轉(zhuǎn)換為加法，使得機(jī)器總可以做加法運(yùn)算。補(bǔ)碼的符號(hào)位同數(shù)值位一起參加運(yùn)算，也簡(jiǎn)化了運(yùn)算器的結(jié)構(gòu)。但是根據(jù)補(bǔ)碼的定義，求負(fù)數(shù)的補(bǔ)碼還要做減法，于是出現(xiàn)了反碼（負(fù)數(shù)的補(bǔ)碼就是在原碼的基礎(chǔ)上，符號(hào)位不變，其余位置取反后末尾加1）。移碼主要用于浮點(diǎn)數(shù)的階碼，使用移碼可以很方便的對(duì)浮點(diǎn)數(shù)的

36、階碼比較運(yùn)算，無(wú)論正負(fù)，從符號(hào)位開(kāi)始，逐個(gè)位置比較大小。而負(fù)數(shù)的補(bǔ)碼，原碼，反碼卻不能這樣比較。浮點(diǎn)數(shù)表示方法浮點(diǎn)數(shù)由階碼E，尾數(shù)M，階碼的底R(shí)三部分組成，尾數(shù)M是一個(gè)定點(diǎn)小數(shù)，決定浮點(diǎn)數(shù)的有效值精度，一般用原碼或者補(bǔ)碼表示，階碼E是一個(gè)定點(diǎn)整數(shù)（有正負(fù)號(hào)之分），階碼位數(shù)越長(zhǎng)，表示的范圍越廣，一般用移碼或者補(bǔ)碼。什么是中斷？（外中斷又稱(chēng)作硬中斷 外設(shè)請(qǐng)求 和 內(nèi)中斷又叫做軟中斷，CPU內(nèi)部數(shù)據(jù)溢出）由于某種原因?qū)е翪PU中止當(dāng)前執(zhí)行當(dāng)前任務(wù)，轉(zhuǎn)去對(duì)所發(fā)生的事件的處理，當(dāng)處理結(jié)束后還能返回到中止發(fā)生的地方接著執(zhí)行中止之前沒(méi)有完成的任務(wù)。中斷意義：中斷時(shí)計(jì)算機(jī)系統(tǒng)結(jié)構(gòu)的一大變革，它是現(xiàn)代多道程序得

37、以實(shí)現(xiàn)的基礎(chǔ)，因?yàn)檫M(jìn)程間的切換時(shí)依靠中斷處理。中斷不僅提高了處理機(jī)的效率，而且也使得外設(shè)和處理機(jī)并發(fā)工作。微程序控制器的基本思想計(jì)算機(jī)系統(tǒng)是按照一系列離散的步驟操作，一條指令可以分成一系列基本操作: 取指令，分析指令，和執(zhí)行指令。這些步驟可以用軟件的方法實(shí)現(xiàn)。每條指令都可以用一段微程序來(lái)實(shí)現(xiàn)。硬布線控制器和微程序比較根本區(qū)別在于微操作信號(hào)的產(chǎn)生方法不同，一個(gè)是微程序代碼執(zhí)行中在需要的時(shí)間從控制存儲(chǔ)器中讀取，另一個(gè)是組合邏輯電路產(chǎn)生的信號(hào)。微程序控制器屬于存儲(chǔ)邏輯電路，硬布線屬于時(shí)序及組合邏輯電路，而且設(shè)計(jì)比較復(fù)雜。微程序容易擴(kuò)充和修改，硬布線非常不利于修改擴(kuò)充。微程序多用于Cisc，硬布線多用

38、于RiSC系統(tǒng)。CPU如何區(qū)分主存上的程序代碼與數(shù)據(jù)的？答：在不同的周期區(qū)分，取指周期取指令流向控制器，執(zhí)行周期取數(shù)據(jù)流向運(yùn)算器。計(jì)算機(jī)的乘法運(yùn)算是怎么做的？除法運(yùn)算呢？答：乘法通過(guò)加減法和移位運(yùn)算指令來(lái)實(shí)現(xiàn)的，還可以通過(guò)編制程序?qū)崿F(xiàn)；而除法可以轉(zhuǎn)換為乘法，乘法轉(zhuǎn)成加法，減法也轉(zhuǎn)成加法。cpu的功能？答：CPU是中央處理單元(Cntral Pocessing Uit)的縮寫(xiě)，它可以被簡(jiǎn)稱(chēng)做微處理器（mcroprocessor)，不過(guò)經(jīng)常被人們直接稱(chēng)為處理器(processor)。 cpu是計(jì)算機(jī)的核心，作用和大腦更相似，因?yàn)樗?fù)責(zé)處理、運(yùn)算計(jì)算機(jī)內(nèi)部的所有數(shù)據(jù)，而主板芯片組則更像是心臟，它控制

39、著數(shù)據(jù)的交換。 cpu的種類(lèi)決定了你使用的操作系統(tǒng)和相應(yīng)的軟件。CPU主要由運(yùn)算器、控制器、寄存器組和內(nèi)部總線等構(gòu)成，是PC的核心，再配上儲(chǔ)存器、輸入/輸出接口和系統(tǒng)總線組成為完整的PC。CPU三大部分：運(yùn)算器，cache，控制器CPU有四個(gè)方面的基本功能：指令控制，操作控制，時(shí)間控制和數(shù)據(jù)加工。CPU中至少有6類(lèi)寄存器： 數(shù)據(jù)緩沖寄存器DR，指令寄存器IR，程序計(jì)數(shù)器PC，數(shù)據(jù)地址寄存器AR，通用寄存器R0R3，狀態(tài)字寄存器PSW?？偩€的結(jié)構(gòu)，分類(lèi)3種，單總線，雙總線，多總線。 CPU內(nèi)部總線和外部總線和通信總線。 并行總線和串行總線。 總線的信息傳輸3種方式，并行串行和分時(shí)傳輸。 運(yùn)算器有

40、什么組成，有什么功能有ALU算數(shù)邏輯單元，通用寄存器，數(shù)據(jù)緩沖寄存器DR和狀態(tài)條件寄存器PSW組成，他是數(shù)據(jù)加工處理部件，兩大功能：1.執(zhí)行所有的算術(shù)運(yùn)算，2.執(zhí)行所有的邏輯運(yùn)算控制器由什么組成，有什么功能？程序計(jì)數(shù)器PC，指令寄存器IR，指令譯碼器ID，操作控制信號(hào)形成部件，時(shí)序信號(hào)產(chǎn)生器，地址寄存器AR，數(shù)據(jù)寄存器DR控制器的功能：他能夠完成協(xié)調(diào)和指揮整個(gè)計(jì)算機(jī)系統(tǒng)的操作，1.從指令cache中取出一條指令，并指出下一條指令的位置。2.對(duì)指令進(jìn)行譯碼或測(cè)試，并產(chǎn)生相應(yīng)的操作控制信號(hào)，以便啟動(dòng)規(guī)定的動(dòng)作，建立正確的數(shù)據(jù)通路；指揮并控制CPU，數(shù)據(jù)cache和輸入輸出設(shè)備間的數(shù)據(jù)流動(dòng)的方向。A

41、LU的全稱(chēng)？答：ALU：Arithmetic Logic Unit，算術(shù)邏輯單元。定點(diǎn)運(yùn)算器組成ALU算數(shù)邏輯單元，數(shù)據(jù)緩沖寄存器，通用寄存器，多路轉(zhuǎn)換器，標(biāo)志寄存器，內(nèi)部總線等 評(píng)價(jià)計(jì)算機(jī)的三個(gè)指標(biāo)？答：1、機(jī)器字長(zhǎng)：CPU一次能并行處理的數(shù)據(jù)位數(shù)。2、主頻：CPU的時(shí)鐘周期。3、運(yùn)算速度。4、存儲(chǔ)的容量。5、存儲(chǔ)周期。什么是尋址？基址尋址，變址尋址是什么，作用是什么？答：尋址是數(shù)據(jù)恢復(fù)技術(shù)的基礎(chǔ)，是定位數(shù)據(jù)和扇區(qū)的關(guān)鍵。尋址這個(gè)概念比較抽象，簡(jiǎn)單的說(shuō)是磁頭在盤(pán)片上定位數(shù)據(jù)的一個(gè)過(guò)程。如果你想找到你的計(jì)算機(jī)中的一個(gè)文件，你可能會(huì)在Windows中先打開(kāi)我的電腦、分區(qū)、文件夾，再打開(kāi)你要找的文

42、件。這是表面的尋找文件的過(guò)程，而磁頭在盤(pán)片的尋找過(guò)程就是尋址?；穼ぶ肥菍PU中基址寄存器的內(nèi)容，加上指令格式中的形式地址而形成操作數(shù)的有效地址變址尋址是在通用寄存器中，有些寄存器可作為變址寄存器。把變址寄存器的內(nèi)容（通常是首地址）與指令地址碼部分給出的地址（通常是位移量）之和作為操作數(shù)的地址來(lái)獲得所需要的操作數(shù)就稱(chēng)為變址尋址。根據(jù)Flynn分類(lèi)法，可以將計(jì)算機(jī)系統(tǒng)分為哪幾類(lèi)？答：四類(lèi)。 單指令流單數(shù)據(jù)流機(jī)器(SISD)單指令流多數(shù)據(jù)流機(jī)器(SIMD)多指令流單數(shù)據(jù)流機(jī)器(MISD)多指令流多數(shù)據(jù)流機(jī)器(MIMD)計(jì)算機(jī)組成原理關(guān)于溢出？指的是運(yùn)算結(jié)果超出了機(jī)器數(shù)的表示范圍，就發(fā)生了溢出 對(duì)

43、于加減法運(yùn)算來(lái)說(shuō)，只有當(dāng)同號(hào)兩數(shù)相加或者異號(hào)兩數(shù)相減才可能會(huì)發(fā)生溢出 。兩個(gè)正數(shù)相加，結(jié)果大于機(jī)器字長(zhǎng)所能表示的最大正數(shù)，稱(chēng)正溢出兩個(gè)負(fù)數(shù)相加，結(jié)果小于機(jī)器所能表示的最小負(fù)數(shù)，成福溢出本來(lái)結(jié)果是正的，溢出之后變成負(fù)的，叫做正溢出。判別溢出：根據(jù)運(yùn)算結(jié)果的最高位進(jìn)位和符號(hào)位的進(jìn)位進(jìn)行異或運(yùn)算。倘若異或結(jié)果為0，即最高位進(jìn)位和符號(hào)位進(jìn)位相同時(shí)，沒(méi)有發(fā)生溢出，否則就發(fā)生了溢出。 稱(chēng)之為單符號(hào)位判別第二種采用雙符號(hào)位 稱(chēng)之為變形補(bǔ)碼。任何正數(shù)符號(hào)位都是00，任何負(fù)數(shù)符號(hào)位都是11.計(jì)算結(jié)果如果是01，那么發(fā)生正溢出；如果是10則發(fā)生負(fù)溢出。借助異或運(yùn)算，兩個(gè)符號(hào)位相同就沒(méi)溢出。地址線，數(shù)據(jù)線是干什么的

44、？答：地址線是用來(lái)傳輸?shù)刂沸畔⒂玫?。地址線傳遞地址機(jī)器指令和微指令？答：機(jī)器指令和微指令的關(guān)系歸納如下：1. 一條機(jī)器指令對(duì)應(yīng)一個(gè)微程序，這個(gè)微程序是由若干條微指令構(gòu)成的。因此，一條機(jī)器指令的功能是若干條微指令組成的序列來(lái)實(shí)現(xiàn)的。簡(jiǎn)而言之，一條機(jī)器指令所完成的操作劃分成若干條微指令來(lái)完成，由微指令進(jìn)行解釋和執(zhí)行。2.從指令與微指令，程序與微程序，地址與微地址的一一對(duì)應(yīng)關(guān)系上看，前者與內(nèi)存儲(chǔ)器有關(guān)，而后者與控制存儲(chǔ)器（它是微程序控制器的一部分。微程序控制器主要由控制存儲(chǔ)器、微指令寄存器和地址轉(zhuǎn)移邏輯三部分組成。其中，微指令寄存器又分為微地址寄存器和微命令寄存器兩部分）有關(guān)，與此相關(guān)也有相對(duì)應(yīng)的硬

45、設(shè)備。3.從一般指令的微程序執(zhí)行流程圖可以看出。每個(gè)CPU周期就對(duì)于一條微指令。這就告訴我們?cè)趺丛O(shè)計(jì)微程序，也將使得我們進(jìn)一步體驗(yàn)到機(jī)器指令很微指令的關(guān)系。什么是存儲(chǔ)元，什么是存儲(chǔ)單元，什么是存儲(chǔ)單元地址？答：存儲(chǔ)器是由大量寄存器組成的，其中每一個(gè)寄存器就稱(chēng)為一個(gè)存儲(chǔ)單元。它可存放一個(gè)有獨(dú)立意義的二進(jìn)制代碼。一個(gè)代碼由若干位（bit）組成，代碼的位數(shù)稱(chēng)為位長(zhǎng)，習(xí)慣上也稱(chēng)為字長(zhǎng)。存放一個(gè)機(jī)器字的存儲(chǔ)單元叫做字存儲(chǔ)單元；相應(yīng)的單元地址叫做字地址。 存儲(chǔ)元（Storage Unit）是存儲(chǔ)器的最小存儲(chǔ)單元，它的作用是用來(lái)存放一位二進(jìn)制代碼0或1。存儲(chǔ)單元一般應(yīng)具有存儲(chǔ)數(shù)據(jù)和讀寫(xiě)數(shù)據(jù)的功能，以8位二進(jìn)

46、制作為一個(gè)存儲(chǔ)單元，也就是一個(gè)字節(jié)。每個(gè)單元有一個(gè)地址，是一個(gè)整數(shù)編碼，可以表示為二進(jìn)制整數(shù)。儲(chǔ)單元地址在計(jì)算機(jī)中的存儲(chǔ)器往往有成千上萬(wàn)個(gè)存儲(chǔ)單元，為了使存入和取出不發(fā)生混淆，必須給每個(gè)存儲(chǔ)單元一個(gè)唯一的固定編號(hào)。內(nèi)中斷 和外中斷區(qū)別？答：中斷信號(hào)的來(lái)源不同，內(nèi)中斷信號(hào)源是內(nèi)部的，外中斷的信號(hào)源來(lái)自外部。答：指當(dāng)出現(xiàn)需要時(shí)，CPU暫時(shí)停止當(dāng)前程序的執(zhí)行轉(zhuǎn)而執(zhí)行處理新情況的程序和執(zhí)行過(guò)程。即在程序運(yùn)行過(guò)程中，系統(tǒng)出現(xiàn)了一個(gè)必須由CPU立即處理的情況，此時(shí)，CPU暫時(shí)中止程序的執(zhí)行轉(zhuǎn)而處理這個(gè)新的情況的過(guò)程就叫做中斷。cache和虛擬存儲(chǔ)器結(jié)構(gòu)（OS）的區(qū)別？答：工作環(huán)境不同：Cache是介于CP

47、U和主存之間的存儲(chǔ)器，虛擬存儲(chǔ)器是介于主存和輔存之間的存儲(chǔ)器。目的不同：虛擬存儲(chǔ)器是為了從邏輯上實(shí)現(xiàn)內(nèi)存擴(kuò)充而引進(jìn)的。而cache是為了緩解CPU和主存速度差異而引進(jìn)的。實(shí)現(xiàn)方式不同：cache用全硬件實(shí)現(xiàn)，虛擬存儲(chǔ)器在主存和輔存之間用軟件實(shí)現(xiàn)。Cache的命中率必須很高，一般要達(dá)到90%以上，才能使訪存的速度跟得上CPU的速度。在CPU和Cache之間通常一次傳送一個(gè)字塊，字塊的長(zhǎng)度是只有幾十字節(jié)，而虛擬存儲(chǔ)器訪問(wèn)速度要比cache慢得多，而且信息塊劃分方案很多，有頁(yè)、段等等，長(zhǎng)度均在幾百幾百K 字節(jié)左右。，虛擬存儲(chǔ)器的實(shí)現(xiàn)方兩種 請(qǐng)求分頁(yè)和請(qǐng)求分段；請(qǐng)求分頁(yè)是在分頁(yè)系統(tǒng)上增加請(qǐng)求調(diào)頁(yè)和頁(yè)面

48、置換功能形成的頁(yè)式虛擬存儲(chǔ)系統(tǒng)。 cache和虛擬存儲(chǔ)都是基于時(shí)間局部性和空間局部性原理。Cache的命中率和什么有關(guān)：程序自身結(jié)構(gòu)2.cache的容量大小.cache的組織方式和塊的大小內(nèi)存和cache分別是什么區(qū)別？答：內(nèi)存，是存儲(chǔ)器，用于輔助CPU輸入輸出數(shù)據(jù)進(jìn)行運(yùn)算。cache，是一種特殊的內(nèi)存。因?yàn)镃OU速度和主存的速度不匹配，用少量的特別快的但特別昂貴的內(nèi)存來(lái)做緩存加速。CPU cache 主存 cpu-主存輔存 的異同？答：根據(jù)概率統(tǒng)計(jì)，在90%的時(shí)間內(nèi)CPU只對(duì)10%的內(nèi)存進(jìn)行訪問(wèn)。為了提高速度，增加容量，降低成本，目前各類(lèi)計(jì)算機(jī)中已經(jīng)廣泛采用多層次存儲(chǔ)器結(jié)構(gòu)，即采用DRAM組

49、成高速緩存（cache memory）存放做常用的數(shù)九；用DRAM組成內(nèi)存，存放次常用的大量數(shù)據(jù)；將不常用的數(shù)據(jù)存放在虛擬內(nèi)存（virtual memory）的硬盤(pán)中，除CPU內(nèi)部寄存器外，由上向下分三個(gè)層次，即高速緩存、主存和輔存。容量逐級(jí)增大，速度逐級(jí)降低，成本逐級(jí)減少。從整個(gè)結(jié)構(gòu)看分兩個(gè)層次，即“主存輔存“和”Cache主存“。內(nèi)存有哪些引腳？答：各種內(nèi)存條金手指引腳定義小全（72、144、168、152、184、200、240線） 內(nèi)存的擴(kuò)展方式？答：字拓展 增加存儲(chǔ)器的容量 片選線不一樣，地址線，數(shù)據(jù)線都用一根線位拓展 增加同一個(gè)地址下的存儲(chǔ)單元的位數(shù) 地址線和片選線一樣，不一樣的數(shù)

50、據(jù)線，低8位數(shù)據(jù)線和高8位數(shù)據(jù)線 2根數(shù)據(jù)線字位同時(shí)拓展 內(nèi)存條的作用？答；內(nèi)存用是用于暫時(shí)存放CPU中的運(yùn)算數(shù)據(jù)，以及與硬盤(pán)等外部存儲(chǔ)器交換的數(shù)據(jù)。只要計(jì)算機(jī)在運(yùn)行中，CPU就會(huì)把需要運(yùn)算的數(shù)據(jù)調(diào)到內(nèi)存中進(jìn)行運(yùn)算，當(dāng)運(yùn)算完成后CPU再將結(jié)果傳送出來(lái)，內(nèi)存的運(yùn)行也決定了計(jì)算機(jī)的穩(wěn)定運(yùn)行。比如在使用WPS處理文稿時(shí)，在鍵盤(pán)上敲入字符時(shí)，它就被存入內(nèi)存中，選擇存盤(pán)時(shí)，內(nèi)存中的數(shù)據(jù)才會(huì)被存入硬（磁）盤(pán)。寄存器？答：寄存器是中央處理器內(nèi)的組成部分。寄存器是有限存貯容量的高速存貯部件，它們可用來(lái)暫存指令、數(shù)據(jù)和地址。在中央處理器的控制部件中，包含的寄存器有指令寄存器(IR)和程序計(jì)數(shù)器(PC)。在中央處

51、理器的算術(shù)及邏輯部件中，存器有累加器(ACC)。關(guān)于高速緩沖存儲(chǔ)器的問(wèn)題？答：高速緩存的出現(xiàn)就是因?yàn)樘幚砥鞯母咚僮x取數(shù)據(jù)的速度比內(nèi)存儲(chǔ)器的工作速度快太多.高速緩存是一種比處理器慢比內(nèi)存快介于二者之間的一種儲(chǔ)存裝置。說(shuō)一說(shuō)Cache，談一談Wlan？答：Cache(即高速緩沖存儲(chǔ)器(Cache Memory)。CPU在訪問(wèn)內(nèi)存時(shí)，首先判斷所要訪問(wèn)的內(nèi)容是否在Cache中，如果在，就稱(chēng)為“命中”，此時(shí)CPU直接從Cache中調(diào)用該內(nèi)容；否則，就稱(chēng)為“不命中”，CPU只好去內(nèi)存中調(diào)用所需的子程序或指令了。CPU不但可以直接從Cache中讀出內(nèi)容，也可以直接往其中寫(xiě)入內(nèi)容。由于Cache的存取速率相當(dāng)

52、快，使得CPU的利用率大大提高，進(jìn)而使整個(gè)系統(tǒng)的性能得以提升。WLAN，（wireless local area network） 無(wú)線局域網(wǎng)的意思，指應(yīng)用無(wú)線通信技術(shù)將計(jì)算機(jī)設(shè)備互聯(lián)起來(lái)，構(gòu)成可以互相通信和實(shí)現(xiàn)資源共享的網(wǎng)絡(luò)體系。虛擬存儲(chǔ)器的思想是什么?答：虛擬存儲(chǔ)器的基本思想是把作業(yè)地址空間和主存空間視為兩個(gè)不同的地址空間。虛擬存儲(chǔ)器：在具有層次結(jié)構(gòu)存儲(chǔ)器的計(jì)算機(jī)系統(tǒng)中，自動(dòng)實(shí)現(xiàn)部分裝入和部分替換功能，能從邏輯上為用戶提供一個(gè)比物理貯存容量大得多，可尋址的“主存儲(chǔ)器”。虛擬存儲(chǔ)區(qū)的容量與物理主存大小無(wú)關(guān)，而受限于計(jì)算機(jī)的地址結(jié)構(gòu)和可用磁盤(pán)容量。特點(diǎn)：虛擬內(nèi)存的作用 內(nèi)存在計(jì)算機(jī)中的作用很大

53、，電腦中所有運(yùn)行的程序都需要經(jīng)過(guò)內(nèi)存來(lái)執(zhí)行，如果執(zhí)行的程序很大或很多，就會(huì)導(dǎo)致內(nèi)存消耗殆盡。為了解決這個(gè)問(wèn)題，Windows中運(yùn)用了虛擬內(nèi)存技術(shù)，即拿出一部分硬盤(pán)空間來(lái)充當(dāng)內(nèi)存使用，當(dāng)內(nèi)存占用完時(shí)，電腦就會(huì)自動(dòng)調(diào)用硬盤(pán)來(lái)充當(dāng)內(nèi)存，以緩解內(nèi)存的緊張。計(jì)算機(jī)由什么組成？答：計(jì)算機(jī)由軟件和硬件組成。由硬件系統(tǒng)和軟件系統(tǒng)組成：硬件系統(tǒng)分主機(jī)系統(tǒng)和外部設(shè)備。主機(jī)系統(tǒng)分中央處理器（CPU）、內(nèi)存和主板。外部設(shè)備分外部存儲(chǔ)設(shè)備、輸入設(shè)備、輸出設(shè)備。軟降系統(tǒng)分基本輸入輸/輸出系統(tǒng)（BIOS)、系統(tǒng)軟件、應(yīng)用軟件DMA原理？他和中斷的區(qū)別，通道的區(qū)別:答：DMA direct Memory Access 直接存

54、儲(chǔ)器訪問(wèn)，簡(jiǎn)單來(lái)說(shuō)，總線控制權(quán)在CPU“手上”，外設(shè)無(wú)權(quán)直接訪問(wèn)內(nèi)存，需要CPU參與，但DMA控制器從CPU那“偷出”幾個(gè)時(shí)鐘來(lái)控制總線，讓外設(shè)可以直接訪問(wèn)內(nèi)存，這樣外設(shè)的讀寫(xiě)就不需要CPU參與，降低了CPU的占用率。DMA是直接存儲(chǔ)器存取。DMA傳輸將數(shù)據(jù)從一個(gè)地址空間復(fù)制到另外一個(gè)地址空間。當(dāng)CPU初始化這個(gè)傳輸動(dòng)作，即，CPU向磁盤(pán)控制器發(fā)送一個(gè)命令，啟動(dòng)DM傳送命令。整個(gè)傳輸動(dòng)作本身是由DMA控制器來(lái)實(shí)行和完成。傳輸結(jié)束后，由DMA發(fā)送一個(gè)中斷信號(hào)給CPU。在實(shí)現(xiàn)DMA傳輸時(shí)，是由DMA控制器直接掌管總線，因此，存在著一個(gè)總線控制權(quán)轉(zhuǎn)移問(wèn)題。即DMA傳輸前，CPU要把總線控制權(quán)交給DM

55、A控制器，而在結(jié)束DMA傳輸后，DMA控制器應(yīng)立即把總線控制權(quán)再交回給CPU。 它與中斷方式的主要區(qū)別在于，DMA方式只需要CPU在開(kāi)始和完成傳輸時(shí)進(jìn)行干預(yù)，其它時(shí)候不需要CPU干預(yù)。中斷驅(qū)動(dòng)方式在每個(gè)數(shù)據(jù)需要傳輸時(shí)中斷CPU，而DMA方式則是在所要求傳送的一批數(shù)據(jù)全部傳送結(jié)束時(shí)才中斷CPU。中斷驅(qū)動(dòng)方式數(shù)據(jù)傳送是在中斷處理時(shí)由CPU控制完成的，而DMA方式則是在DMA控制器的控制下完成的。DMA控制方式與通道控制方式有什么不同？答：在DMA控制方式中，DMA控制器控制設(shè)備和主存之間成批地進(jìn)程數(shù)據(jù)交流，而不用CPU干預(yù)。這樣不但減輕了CPU的負(fù)擔(dān)，而且提高了I/O數(shù)據(jù)傳送速度。這種控制方式應(yīng)用

56、于塊設(shè)備的數(shù)據(jù)傳輸。 通道控制方式與DMA控制方式類(lèi)似，也是一種以?xún)?nèi)存為中心，實(shí)現(xiàn)設(shè)備與內(nèi)存直接交換數(shù)據(jù)的控制方式。在通道控制方式中，CPU只需發(fā)出啟動(dòng)指令，指出通道相應(yīng)的操作和I/O設(shè)備，該指令就可以啟動(dòng)通道并使通道從內(nèi)存中調(diào)出相應(yīng)的通道程序執(zhí)行。與DMA相比，通道方式所需的CPU干預(yù)更少，并且可以做到一個(gè)通道控制多臺(tái)設(shè)備，從而進(jìn)一步減輕了CPU負(fù)擔(dān)。什么是CISC和RISC ？簡(jiǎn)述它們的特點(diǎn)和區(qū)別？答：CISC的英文全稱(chēng)為“Complex Instruction Set Computer”，即“復(fù)雜指令系統(tǒng)計(jì)算機(jī)”，從計(jì)算機(jī)誕生以來(lái)，人們一直沿用CISC指令集方式。RISC的英文全稱(chēng)為“R

57、educed Instruction Set Computer”，即“精簡(jiǎn)指令集計(jì)算機(jī)”，是一種執(zhí)行較少類(lèi)型計(jì)算機(jī)指令的微處理器1、指令系統(tǒng)CISC計(jì)算機(jī)的指令系統(tǒng)比較豐富，有專(zhuān)用指令來(lái)完成特定的功能。因此，處理特殊任務(wù)效率較高。RISC設(shè)計(jì)者把主要精力放在那些經(jīng)常使用的指令上，盡量使它們具有簡(jiǎn)單高效的特色。對(duì)不常用的功能，常通過(guò)組合指令來(lái)完成。因此，在RISC 機(jī)器上實(shí)現(xiàn)特殊功能時(shí)，效率可能較低。但可以利用流水技術(shù)和超標(biāo)量技術(shù)加以改進(jìn)和彌補(bǔ)。2、存儲(chǔ)器操作CISC機(jī)器的存儲(chǔ)器操作指令多，操作直接。RISC對(duì)存儲(chǔ)器操作有限制，使控制簡(jiǎn)單化。3、程序CISC匯編語(yǔ)言程序編程相對(duì)簡(jiǎn)單，科學(xué)計(jì)算及復(fù)

58、雜操作的程序社設(shè)計(jì)相對(duì)容易，效率較高。RISC匯編語(yǔ)言程序一般需要較大的內(nèi)存空間，實(shí)現(xiàn)特殊功能時(shí)程序復(fù)雜，不易設(shè)計(jì)。4、中斷CISC機(jī)器是在一條指令執(zhí)行結(jié)束后響應(yīng)中斷。RISC機(jī)器在一條指令執(zhí)行的適當(dāng)?shù)胤娇梢皂憫?yīng)中斷。5、CPUCISCCPU包含有豐富的電路單元，因而功能強(qiáng)、面積大、功耗大。RISCCPU包含有較少的單元電路，因而面積小、功耗低。6、設(shè)計(jì)周期CISC微處理器結(jié)構(gòu)復(fù)雜，設(shè)計(jì)周期長(zhǎng)。RISC微處理器結(jié)構(gòu)簡(jiǎn)單，布局緊湊，設(shè)計(jì)周期短，且易于采用最新技術(shù)。7、用戶使用CISC微處理器結(jié)構(gòu)復(fù)雜，功能強(qiáng)大，實(shí)現(xiàn)特殊功能容易。RISC微處理器結(jié)構(gòu)簡(jiǎn)單，指令規(guī)整，性能容易把握，易學(xué)易用。8、應(yīng)用

59、范圍CISC機(jī)器則更適合于通用機(jī)。RISC由于RISC指令系統(tǒng)的確定與特定的應(yīng)用領(lǐng)域有關(guān)，故RISC 機(jī)器更適合于專(zhuān)用機(jī)。流水線技術(shù)和超標(biāo)量技術(shù)流水線允許同時(shí)運(yùn)行多條指令，使這些指令運(yùn)行在不同的階段，使各個(gè)部件都工作起來(lái)。超標(biāo)量技術(shù)是在標(biāo)量流水線基礎(chǔ)上，采用資源重復(fù)利用，重復(fù)設(shè)置硬件資源，使一個(gè)時(shí)鐘周期內(nèi)能啟動(dòng)n條指令。數(shù)據(jù)庫(kù)SQL特點(diǎn)：綜合統(tǒng)一，集數(shù)據(jù)查詢(xún)，數(shù)據(jù)操作，數(shù)據(jù)定義 數(shù)據(jù)控制功能于一體。 高度非過(guò)程化，只提做什么，不提怎么做。 面向集合的操作方式，操作對(duì)象可以是集合，查找結(jié)果也可以是集合 既是獨(dú)立的語(yǔ)言，還是一門(mén)嵌入式語(yǔ)言，嵌入到C,C+ JAVA什么是函數(shù)依賴(lài)？舉個(gè)例子。所謂函數(shù)

60、依賴(lài)是指關(guān)系中一個(gè)或一組屬性的值可以決定其它屬性的值。函數(shù)依賴(lài)正如一個(gè)函數(shù) y = f(x) 一樣，x的值給定后，y的值也就唯一地確定了。如果屬性集合X中每個(gè)屬性的值構(gòu)成的集合唯一地決定了屬性集合X中每個(gè)屬性的值構(gòu)成的集合，則屬性集合Y函數(shù)依賴(lài)于屬性集合X，計(jì)為：XY。X也稱(chēng)之為決定因素。例：身份證號(hào)姓名或者一個(gè)學(xué)生實(shí)體中有學(xué)號(hào)，性別，姓名。給了學(xué)號(hào)就唯一確定了其他屬性。非平凡函數(shù)依賴(lài)： 如果XY，但是Y不屬于X集合，則XY是非平凡函數(shù)依賴(lài)。完全函數(shù)依賴(lài)：在一個(gè)屬性集合U中，如果XY，并且對(duì)于X的真子集X都不能確定Y，只有X才能確定Y，那么成Y對(duì)X完全函數(shù)依賴(lài)。否則稱(chēng)之為部分函數(shù)依賴(lài)。例如（學(xué)