計(jì)算機(jī)導(dǎo)論課后習(xí)題參考答案

第1章計(jì)算機(jī)概述

一、單項(xiàng)選擇題

ABDBCCDBAD

二、簡(jiǎn)答題

1.根據(jù)計(jì)算機(jī)所采用的電子邏輯元件可將計(jì)算機(jī)的發(fā)展劃分為4個(gè)發(fā)展階段，每個(gè)階

段所采用的元器件分別為：電子管，晶體管，中、小規(guī)模集成電路，大規(guī)模、超大規(guī)模集

成電路。

2.馮?諾依曼計(jì)算機(jī)主要由4部分組成：運(yùn)算器、存儲(chǔ)器、控制器、輸入/輸出設(shè)備。

3.衡量計(jì)算機(jī)性能的指標(biāo)主要有5個(gè)，分別為：字長(zhǎng)、主頻、存儲(chǔ)容量、運(yùn)算速度和

存取周期。

4.計(jì)算機(jī)的特點(diǎn)：1）能自動(dòng)連續(xù)、高速度地運(yùn)算；2）運(yùn)算速度快；3）運(yùn)算精度高；

4）具有超常的記憶能力；5）具有可靠的邏輯判斷能力。

按運(yùn)算規(guī)模，計(jì)算機(jī)可分為巨型機(jī)、大型機(jī)、中型機(jī)、小型機(jī)、微型機(jī)和工作站。

第2章計(jì)算機(jī)中的數(shù)據(jù)

一、單項(xiàng)選擇題

AABCB

二、計(jì)算題

1.(1)7(2)511(3)4076

2.(1)7660(2)2010(3)2650

3.(1)2510(2)62720(3)643613630

4.(1)0.1B(2)-101.01B(3)110011B

三、簡(jiǎn)答題

1.計(jì)算機(jī)采用二進(jìn)制表示數(shù)據(jù)主要有以下4個(gè)原因：1）二進(jìn)制物理上易于實(shí)現(xiàn)；2）

二進(jìn)制運(yùn)算法則簡(jiǎn)單；3）二進(jìn)制編碼機(jī)器可靠性高：4）二進(jìn)制通用性和邏輯性強(qiáng)。

2.在計(jì)算機(jī)中，所有數(shù)值型數(shù)據(jù)都用二進(jìn)制編碼來表示，這串二進(jìn)制編碼稱為該數(shù)據(jù)

的機(jī)器數(shù)，數(shù)據(jù)原來的表現(xiàn)形式稱為“真值”。一個(gè)進(jìn)制中數(shù)碼的個(gè)數(shù)稱為“基數(shù)”。

3.帶符號(hào)整數(shù)常用的編碼形式有3種，分別為原碼、反碼和補(bǔ)碼。1）原碼表示法為：

最高位是符號(hào)位（0表示正，1表示負(fù)），其余各位表示數(shù)的絕對(duì)值大小。2）反碼表示法為：

最高位是符號(hào)位（0表示正，1表示負(fù)），正數(shù)的反碼與原碼相同，負(fù)數(shù)的反碼是在其原碼

的基礎(chǔ)上，除符號(hào)位外各位求反。3）補(bǔ)碼表示法為：最高位是符號(hào)位（0表示正，I表示

負(fù)），正數(shù)的補(bǔ)碼與原碼相同，負(fù)數(shù)的補(bǔ)碼是在該數(shù)反碼的最低位加1。

4.要表示文本，必須先對(duì)每個(gè)可能出現(xiàn)的字符進(jìn)行表示。計(jì)算機(jī)最早用于處理英文，

使用ASCII碼來表示字符；后來也用于處理中文和其它文字，為了統(tǒng)一，出現(xiàn)了Unicode

碼。1）ASCII碼用7位二進(jìn)制數(shù)表示一個(gè)字符，共可表示128個(gè)字符。2）Unicode碼用

32位二進(jìn)制數(shù)表示一個(gè)字符，最多可表示232個(gè)符號(hào)，代碼的不同部分用于表示世界上不

同語言的符號(hào)，還有部分用于表示圖形和特殊符號(hào)。

第3章計(jì)算機(jī)系統(tǒng)組成

一、單項(xiàng)選擇題

1>B2、A3、B4、A5、B6、D7、D8、B9、D10、C

11、C12、A13、B14、C15、A16、C17、D18、A19、B20、D

二、簡(jiǎn)答題

1.微型計(jì)算機(jī)的結(jié)構(gòu)主要由硬件和軟件兩部分組成，硬件部分主要包括包括中央處理

器（CPU）、外部總線擴(kuò)展電路（包括板卡）、只讀存儲(chǔ)器（ROM）、存儲(chǔ)器（RAM）、外部存儲(chǔ)器：

硬盤、光驅(qū)等、外部接口串口、USB口、并行口等，以及顯示器、鍵盤鼠標(biāo)等。軟件部分

主要包括操作系統(tǒng)以及應(yīng)用系統(tǒng)軟件及驅(qū)動(dòng)程序等。

2.計(jì)算機(jī)系統(tǒng)包括硬件系統(tǒng)和軟件系統(tǒng)兩部分，簡(jiǎn)稱為硬件和軟件。硬件（Hardware）

是組成計(jì)算機(jī)的各種物理設(shè)備，由五大功能部件組成，即運(yùn)算器、控制器、存儲(chǔ)器、輸入

設(shè)備和輸出設(shè)備。這五大部分相互配合，協(xié)同工作。軟件（Software）是指在硬件系統(tǒng)上運(yùn)

行的各類程序、數(shù)據(jù)及有關(guān)資料的總稱，由系統(tǒng)軟件和應(yīng)用軟件組成。硬件是軟件建立和

依托的基礎(chǔ)，軟件是計(jì)算機(jī)的靈魂。沒有軟件系統(tǒng)的計(jì)算機(jī)我們稱之為“裸機(jī)”。因此，硬

件和軟件相互結(jié)合構(gòu)成了一個(gè)完整的計(jì)算機(jī)系統(tǒng)，只有硬件和軟件相結(jié)合才能充分發(fā)揮計(jì)

算機(jī)系統(tǒng)的功能。

3.中央處理單元簡(jiǎn)稱CPU（CentralProcessingUnit）,它是計(jì)算機(jī)系統(tǒng)的核心，計(jì)

算機(jī)所發(fā)生的全部動(dòng)作都是由CPU的控制。由三個(gè)組成部分：算術(shù)邏輯單元（ALU）、寄存

器、控制單元

（1）算術(shù)邏輯單元：算術(shù)邏輯單元（ALU）對(duì)數(shù)據(jù)進(jìn)行邏輯、移位和算術(shù)運(yùn)算；

（2）寄存器：寄存器是用來臨時(shí)存放數(shù)據(jù)的高速獨(dú)立的存儲(chǔ)單元。主要有：數(shù)據(jù)寄存器、

指令寄存器、程序計(jì)數(shù)器；

（3）控制單元：控制單元是對(duì)計(jì)算機(jī)發(fā)布命令的“決策機(jī)構(gòu)”，用來協(xié)調(diào)和指揮整個(gè)計(jì)算

機(jī)系統(tǒng)的操作，它是控制整個(gè)計(jì)算機(jī)有條不紊地自動(dòng)執(zhí)行程序的元件。

4.存儲(chǔ)器（Memory）是計(jì)算機(jī)用來存放程序和數(shù)據(jù)的記憶裝置。存儲(chǔ)器按照用途可分

為主存儲(chǔ)器（內(nèi)存）和輔助存儲(chǔ)器（外存）。

（1）主存儲(chǔ)器（內(nèi)存）是指主板上的存儲(chǔ)部件，主要采用半導(dǎo)體器件和磁性材料，用

來存放當(dāng)前正在執(zhí)行的數(shù)據(jù)和程序，它可直接和運(yùn)算器、控制器交換數(shù)據(jù)，具有容量小、

速度快等特點(diǎn)；

（2）輔助存儲(chǔ)器（外存）是指磁性介質(zhì)或光盤等，能長(zhǎng)期保持信息，相對(duì)于內(nèi)存，它

有容量大、速度相對(duì)慢等特點(diǎn)。

5.輸入設(shè)備（inputdevice）是指向計(jì)算機(jī)輸入數(shù)據(jù)和信息的設(shè)備。常見的輸入設(shè)備

有鍵盤、鼠標(biāo)、掃描儀等。

（1）鍵盤（keyboard）：鍵盤廣泛應(yīng)用于微型計(jì)算機(jī)和各種終端上，通過鍵盤想計(jì)算

機(jī)輸入各種指令和數(shù)據(jù)，指揮計(jì)算機(jī)工作。按鍵盤的鍵數(shù)分，鍵盤可分為83鍵盤、101鍵

盤、104鍵盤、107鍵盤等；按鍵盤的形式分，可分為有線鍵盤、無線鍵盤、帶托鍵盤和

USB鍵盤等。按工作原理分，可分為機(jī)械鍵盤、塑料薄膜式鍵盤、導(dǎo)電橡膠式鍵盤、無接

點(diǎn)靜電電容鍵盤。按外形分，可分為標(biāo)準(zhǔn)鍵盤和人體工程學(xué)鍵盤等。

(2)鼠標(biāo)(mouse)：鼠標(biāo)是計(jì)算機(jī)顯示系統(tǒng)縱橫坐標(biāo)定位的指示器，因形似老鼠而得名。

鼠標(biāo)按其工作原理的不同分為機(jī)械鼠標(biāo)和光電鼠標(biāo)，機(jī)械鼠標(biāo)主要由滾球、輻柱和光柵信

號(hào)傳感器組成。當(dāng)你拖動(dòng)鼠標(biāo)時(shí)，帶動(dòng)滾球轉(zhuǎn)動(dòng)，滾球又帶動(dòng)輯柱轉(zhuǎn)動(dòng)，裝在輯柱端部的

光柵信號(hào)傳感器采集光柵信號(hào)。傳感器產(chǎn)生的光電脈沖信號(hào)反映出鼠標(biāo)器在垂直和水平方

向的位移變化，再通過電腦程序的處理和轉(zhuǎn)換來控制屏幕上光標(biāo)箭頭的移動(dòng)。按照形式可

分為有線鼠標(biāo)和無線鼠標(biāo)等。

(3)掃描儀(scanner)：掃描儀是利用光電技術(shù)和數(shù)字處理技術(shù)，以掃描方式將圖形

或圖像信息轉(zhuǎn)換為數(shù)字信號(hào)的裝置?掃描儀對(duì)照片、文本頁面、圖紙、美術(shù)圖畫、照相底

片、菲林軟片，甚至紡織品、標(biāo)牌面板、印制板樣品等三維對(duì)象都可作為掃描對(duì)象，提取

和將原始的線條、圖形、文字、照片、平面實(shí)物轉(zhuǎn)換成可以編輯及加入文件中的裝置。常

用的掃描儀有臺(tái)式、手持式和滾筒式三種。分辨率是掃描儀最主要的技術(shù)指標(biāo)，它表示掃

描儀對(duì)圖像細(xì)節(jié)上的表現(xiàn)能力，即決定了掃描儀所記錄圖像的細(xì)致度，其單位為PPI

(PixelsPerInch)。

輸出設(shè)備(outputdevice)是指將計(jì)算機(jī)中的數(shù)據(jù)或信息輸出給用戶，是人與計(jì)算機(jī)

交互的一種部件。常見的輸出設(shè)備有顯示器、打印機(jī)、繪圖儀、影像輸出系統(tǒng)、語音輸出

系統(tǒng)和磁記錄設(shè)備等。

(1)顯示器(display)：也稱為監(jiān)視器，屬于計(jì)算機(jī)輸出設(shè)備。顯示器的主要性能指

標(biāo)有像素、分辨率、屏幕尺寸、點(diǎn)間距、灰度級(jí)、對(duì)比度、幀頻、行頻和掃描方式等；

(2)打印機(jī)(printer):用于將計(jì)算機(jī)處理的結(jié)果打印在相關(guān)介質(zhì)上。衡量打印機(jī)性

能的指標(biāo)有3項(xiàng)：打印分辨率、打印速度和噪聲。

6.計(jì)算機(jī)軟件系統(tǒng)由系統(tǒng)軟件和應(yīng)用軟件組成。操作系統(tǒng)是最基本的軟件系統(tǒng)，是人

機(jī)交互的接口。應(yīng)用軟件是為某類應(yīng)用需要或解決某些特定問題而設(shè)計(jì)開發(fā)的程序，主要

由通用軟件和專門軟件組成。

第4章操作系統(tǒng)

一、單項(xiàng)選擇題

DAABAACBCC

二、簡(jiǎn)答題

1.操作系統(tǒng)是一個(gè)管理和控制計(jì)算機(jī)硬件與軟件資源，合理組織計(jì)算機(jī)工作流程，控

制程序運(yùn)行，并向用戶提供良好工作環(huán)境和接口的系統(tǒng)軟件。操作系統(tǒng)至少應(yīng)當(dāng)具有4種

管理功能：內(nèi)存管理、進(jìn)程管理、設(shè)備管理和文件管理。

2.操作系統(tǒng)是隨著計(jì)算機(jī)硬件技術(shù)的不斷發(fā)展和用戶的使用要求的提高而從無到有

不斷完善起來的，其主要類型及其特點(diǎn)如下：

(1)批處理操作系統(tǒng)：具有很高的資源利用率和系統(tǒng)吞吐量，但作業(yè)的平均周轉(zhuǎn)時(shí)

間較長(zhǎng)，也沒有交互性。

(2)分時(shí)操作系統(tǒng)：具有多路性、獨(dú)立性、及時(shí)性和交互性特征，而交互性是其最

重要的特征之一。

(3實(shí)時(shí)操作系統(tǒng)：實(shí)時(shí)操作系統(tǒng)通常是專用的，具有高及時(shí)性和高可靠性，但交互

性較弱。

(4)微機(jī)操作系統(tǒng)：是配置在微型計(jì)算機(jī)上的操作系統(tǒng)，可以是單任務(wù)或多任務(wù)，

也可以是單用戶或多用戶系統(tǒng)。

(5)網(wǎng)絡(luò)操作系統(tǒng)：是配置在網(wǎng)絡(luò)中的操作系統(tǒng)，用于管理網(wǎng)絡(luò)通信和共享資源，

協(xié)調(diào)各計(jì)算機(jī)上任務(wù)的運(yùn)行，并向用戶提供統(tǒng)一的、有效方便的網(wǎng)絡(luò)接口。

(6)分布式操作系統(tǒng)：是配置在分布式處理系統(tǒng)上的操作系統(tǒng)，其最基本的特征是

能實(shí)現(xiàn)處理上的分布，而處理分布的實(shí)質(zhì)是資源、功能、任務(wù)和控制都是分布的。

3.死鎖是指多個(gè)進(jìn)程在執(zhí)行過程中，因爭(zhēng)奪資源而造成的一種互相等待的現(xiàn)象。若無

外力推動(dòng)，它們都將無法執(zhí)行下去。發(fā)生死鎖需要4個(gè)必要條件：互斥、資源占有、搶先

和循環(huán)等待。

4.64M-16M=48M

第5章程序設(shè)計(jì)基礎(chǔ)

一、單項(xiàng)選擇題

1、D2、C3、A4、C5、D6、D7、B8、A9、C10、C11、D

二、簡(jiǎn)答題

1.計(jì)算機(jī)程序設(shè)計(jì)語言的分類：

(1)機(jī)器語言：由機(jī)器指令構(gòu)成的語言稱機(jī)器語言，即用二進(jìn)制編碼組成。

(如:01110101)

特點(diǎn)：①費(fèi)時(shí)費(fèi)事；

②難懂容易錯(cuò)；

③只能在一種型號(hào)計(jì)算機(jī)上運(yùn)行；

④可以直接在計(jì)算機(jī)上運(yùn)行。

(2)匯編語言：用容易記憶的符號(hào)來代替機(jī)器指令中操作碼和地址碼的一種語言。

(如：ADD代表“+”SUB代表MOV代表“傳遞”)

優(yōu)點(diǎn)：①程序直觀容易閱讀；

②編程工作量相對(duì)小。

缺點(diǎn)：①只能在一種型號(hào)機(jī)器上運(yùn)行；

②不能直接在計(jì)算機(jī)上運(yùn)行。

(3)高級(jí)程序設(shè)計(jì)語言：高級(jí)程序設(shè)計(jì)語言是一種面向過程或者面向?qū)ο蟮恼Z言，不面

向機(jī)器，用一些符號(hào)或者數(shù)字對(duì)求解的問題或者現(xiàn)實(shí)世界進(jìn)行描述。

特點(diǎn)：①直觀、易寫、易讀、工作量??；

②不依賴于具體的機(jī)器；

③便于程序交流；

④不可直接在計(jì)算機(jī)上運(yùn)行，經(jīng)編譯程序編譯成機(jī)器語言后方可運(yùn)行。

2.算法(Algorithm)是對(duì)特定問題求解步驟準(zhǔn)確而完整的描述，它的表現(xiàn)形式是計(jì)算

機(jī)指令的有序系列，執(zhí)行這些指令就可解決特定問題。一個(gè)好的算法應(yīng)當(dāng)具有以下5個(gè)重

要特性。

(1)有限性：算法在執(zhí)行有限步之后必須終止，且每一步都應(yīng)在有限的時(shí)間內(nèi)完成：

(2)確定性：算法的每一步必須要有確切的含義，不能存在二義性；

(3)可行性：算法的每一步都是可執(zhí)行的，可以通過有限次操作來完成其功能；

(4)輸入：一個(gè)算法具有0個(gè)或多個(gè)輸入；

(5)輸出：一個(gè)算法具有1個(gè)或多個(gè)輸出。

3.常用算法的描述方法有：自然語言法、流程圖法、N-S流程圖法、偽代碼法等。

(1)自然語言：就是采用人們?nèi)粘Ｊ褂玫恼Z言，來描述解決問題的方法和步驟；這種描

述方法通俗易懂，即使是不熟悉計(jì)算機(jī)語言的用戶也很容易理解程序。

(2)流程圖：流程圖是以特定的圖形符號(hào)加上說明來表示算法，通常是用一些圖框來表

示各種操作。

(3)N-S圖是在流程圖的基礎(chǔ)上完全去掉流程線，并將全部算法寫在一個(gè)矩形框內(nèi)，且

框內(nèi)還可以包含其他框的表示形式。N-S圖包括順序、選擇和循環(huán)3種基本結(jié)構(gòu)，如下圖

所示：

順序結(jié)構(gòu)選擇結(jié)構(gòu)

當(dāng)條件為JI時(shí)

循環(huán)結(jié)構(gòu)

(4)偽代碼：偽代碼是介于自然語言和計(jì)算機(jī)語言之間的文字和符號(hào).偽代碼通常采用

自然語言、數(shù)學(xué)公式和符號(hào)來描述算法的操作步驟，同時(shí)采用計(jì)算機(jī)高級(jí)語言的控制結(jié)構(gòu)

來描述算法步驟的執(zhí)行順序。在程序開發(fā)期間，偽代碼經(jīng)常用于“規(guī)劃”一個(gè)程序，然后

再轉(zhuǎn)換成某種高級(jí)語言程序。

4.計(jì)算機(jī)技術(shù)所涉及的算法比較多，常用的算法有枚舉法、遞推法、遞歸法、貪心算

法、分治法、回溯法等.

(1)枚舉法，或稱為窮舉法，其基本思路是：對(duì)于要解決的問題，列舉出它所有可能的

情況，逐個(gè)判斷哪些是符合問題所要求的條件，從而得到問題的解；

(2)遞推法：是按照一定的規(guī)律來計(jì)算序列中的某個(gè)項(xiàng)，通常是通過計(jì)算前面的一些項(xiàng)

來得出序列中指定項(xiàng)的值；

(3)遞歸法：程序直接或間接自己調(diào)用自己的方法簡(jiǎn)稱為遞歸，它通常是把一個(gè)大型的、

復(fù)雜的問題層層轉(zhuǎn)化為一個(gè)個(gè)與原問題相似的、規(guī)模較小的問題來進(jìn)行求解；

(4)貪心算法：貪心算法采用自頂向下，以迭代的方式做出相繼的貪心選擇，每做一次

貪心選擇就將所求解問題簡(jiǎn)化為一個(gè)規(guī)模更小的子問題，通過每一步貪心選擇，就可得到

問題的一個(gè)最優(yōu)解。貪心算法的每一步都能獲得局部最優(yōu)解，但由此產(chǎn)生的全局解有時(shí)不

一定是最優(yōu)解，所以貪婪法不能回溯。

(5)分治法：分治法是把一個(gè)復(fù)雜的問題分解成兩個(gè)或更多個(gè)相同或相似的子問題，再

把子問題分解成更小的子問題，直到最后的子問題可以進(jìn)行簡(jiǎn)單的直接求解，合并所有子

問題的解就可得到原問題的解。

(6)回溯法：回溯法的基本思想是，在包含問題所有解的解空間樹中，按照深度優(yōu)先搜

索的策略，從根結(jié)點(diǎn)出發(fā)深度搜索解空間樹；當(dāng)搜索到某一結(jié)點(diǎn)時(shí)，要先判斷該結(jié)點(diǎn)是否

包含問題的解，如果包含就從該結(jié)點(diǎn)出發(fā)繼續(xù)搜索下去，否則就逐層向其祖先結(jié)點(diǎn)回溯。

若用回溯法求問題的所有解，需要回溯到根，且根結(jié)點(diǎn)的所有可行的子樹都要進(jìn)行搜索后

才能結(jié)束；若使用回溯法求任一個(gè)解時(shí)，則只需搜索到問題的一個(gè)解就可以結(jié)束。

三、程序編程

1.#include"stdio.h"

voidmain()

(

intx,y,z,t;

scanf("%d%d%d”,&x,&y,&z);

if(x>y)

(

t=x;x=y;y=t;

}/*交換x,y的值*/

if(x>z)

(

t=Z；Z=X;x=t;

}/*交換X,z的值*/

if(y>z)

(

t=y;y=z;z=t;

}/*交換z,y的值*/

printf(""smalltobig:%d%d%d\n〃，x,y,z);

2.^include“stdio.h”

voidmain()

(

intn,i,j,k;

printf(〃請(qǐng)輸入要打印的行數(shù)：〃)；

scanf(〃％d〃，&n);

for(i=0;i<n;i++)

(

for(j=0;j<n-i-l;j++)

(

printf(/z");

)

for(k=0;k<2*(i+1)T;k++)

(

printf(〃*〃);

printf(〃\n〃)；

)

3.#includez，stdio.h〃

voidmain()

{intx,y,z;

printf(〃%8s%8s%8s\n〃，〃Cock〃，"Hen","chicken");

for(x=0;x<=20;x++)

for(y=0;y<=33;y++)

{z=3*(100-5*x-3*y);

if(z>=0&&x+y+z==100)

printf("%8d%8d%8d\n”,x,y,z);

)

第6章數(shù)據(jù)結(jié)構(gòu)*

一、單項(xiàng)選擇題

DDCCABDCCB

二、填空題

1.線性結(jié)構(gòu)非線性結(jié)構(gòu)。2.一對(duì)一一對(duì)多多對(duì)多

3.前驅(qū)1后續(xù)14.前驅(qū)1后續(xù)可以任意多個(gè)

5.有限集合D上的關(guān)系有限集合6.有序序列。

7.開放定址法拉鏈法8.散結(jié)構(gòu)表結(jié)構(gòu)樹結(jié)構(gòu)圖結(jié)構(gòu)

9.m=2ee=m10.插入排序選擇排序

三、上機(jī)編程題

1.(1)實(shí)現(xiàn)順序表類的參考代碼：

#include<iostream>

usingnamespacestd;

classSeqList1{

public:

SeqList1(intsz,intleng);//構(gòu)造函數(shù)

voidResize(intnewSize);

intlength(){returnlen;}//表長(zhǎng)度

voidGet();//輸入線性表中的元素

voidGetOut();//輸出線性表中的元素

intSearch(intx);//在表中順序搜索x

intbinarySearch(intx);〃二分查找

intInsert(intx,inti);〃在索引i處插入x

intinsertx(intx);//有序插入

intRemove(inti);//刪除第i個(gè)位置處的表項(xiàng)

private:

int*data;//表的存放數(shù)組

intmaxSize;//表的最大可容納項(xiàng)數(shù)

intlen;〃表實(shí)際長(zhǎng)度

)；

SeqListl::SeqListl(intsz,intleng){//構(gòu)造函數(shù)

if(sz>0){

maxSize=sz;

len=leng;

data二newint[maxSize];

if(data==NULL){

cout<<〃存儲(chǔ)分配錯(cuò)誤！〃<<〃\n〃；

return;

}

)

)

voidSeqListl::Resize(intnewSize){

if(newSize<=0){

cerr<〈〃無效的數(shù)組大小〃<<endl;

return;}

if(newSize!=maxSize){

int*NewArray=newint[newSize];

if(NewArray==NULL){

cerr<<"存儲(chǔ)分配錯(cuò)誤〃<<endl;

return;}

intn=len+l;

int*srcptr=data;

int*destptr=NewArray;

while(n--)*destptr++=*srcptr++;

data=NewArray;

maxSize=newSize;

)

)

voidSeqListl::Get(){//輸入線性表中的元素

for(inti=0;i<len;i++){

cout<〈〃線性表第〃+〃個(gè)元素是：〃；

cin>>data[i];

)

cout<<endl;

}

voidSeqListl::GetOut(){//輸出線性表中的元素

cout<〈〃線性表元素：{〃；

for(inti=0;i<len;i++){

cout<<data[i]<<z，

)

cout<<"}"<<endl;

}

intSeqListl::Insert(intx,inti){

//在順序表中索引為i的位置處插入項(xiàng)x

〃函數(shù)返回插入是否成功的信息

intj;

if(i<0I|i>len)return1;

//插入位置不合理，不能插入

if(len==maxSize)return2;

//無空閑可用存儲(chǔ)單元，不能插入

for(j=len;j>i;j一)

data[j]=data[j-1];〃依次后移

data[i]=x;//插入

len++;//順序表長(zhǎng)度增1

return0;

)

intSeqListl::insertx(intx){//有序插入

if(len==maxSize)Resize(maxSize*2);

//無空閑可用存儲(chǔ)單元，擴(kuò)容2倍

inti;

for(i=len-l;x<data[i]&&i>=0;i--)

data[i+l]=data[i];//邊查邊移

data[i+l]=x;〃插入x

len++;//表長(zhǎng)增1

return0;

)

intSeqListl::Remove(inti){

//刪除第i個(gè)位置處的表項(xiàng)

intj;

if(i<0||i>len)return1;

//刪除位置不合理，不能刪除

for(j=i+l;j<len;j++)

data[j-l]=data[j];//依次前移

len--;//表長(zhǎng)度減1

return0;

}

intSeqListl::Search(intx){

//搜索函數(shù)：在表中順序搜索與給定值x匹配的表項(xiàng)

//找到則函數(shù)返回該元素在線性表中的索引

//否則函數(shù)返回7,表示搜索失敗

for(inti=0;i<len;i++)

if(data[i]==x)returni;

return-1;

)

intSeqListl::binarySearch(intx){

intleft,right,mid;

left=0;right=len-l;//定左右邊界指針

while(left<=right){〃當(dāng)待查段不空時(shí)

mid=(left+right)/2;//計(jì)算中值地址mid

if(x==data[mid])return(mid);//返回x的地址mid

if(x<data[mid])right=mid-l;//準(zhǔn)備查前半段

elseleft=mid+l;//準(zhǔn)備查后半段

}

return-1;//未找到x,返回?zé)o效地址

}

intmain(){

SeqListls1(100,5);

s1.Get();

s1.GetOut();

cout<<“線性表長(zhǎng)度：z,<<sl.length()<<endl;

cout<<〃請(qǐng)輸入需要查找的元素：〃；

intx;

cin>>x;

inti=s1.Search(x);

if(i!=-l)cout<<〃元素〃<<x<<”為線性表中第〃<<i+l<<〃個(gè)元素”<<endl;

elsecout<<“查找元素不存在！"<<endl;

ints;

i=s1.binarySearch(x);

if(i!=-l)cout<<"元素〃<<x<<〃為線性表中第〃<<i+l<<〃個(gè)元素〃<<endl;

elsecout<〈〃查找元素不存在！"<<endl;

i=sl.insertx(x);

if(i!=-l)cout<<x<<〃已插入線性表〃<<endl;

cout<<”插入后線性表長(zhǎng)度:,z<<sl.length()<<endl;

s1.GetOut();

intj=s1.Remove(i);

if(j!=-l)cout<<〃表頭元素已從線性表中刪除〃<<endl;

cout<<"刪除后線性表長(zhǎng)度:，z<<sl.length()<<endl;

s1.GetOut();

return0;

}

運(yùn)行結(jié)果如下圖所示：

D:\JMSOFT\CYuYan\bin\wwtemp.exea*?*[o|回

a

型

房

元B

二F12

m

二

泰

呆

r2元5

旨

二B

幺

型

呆

元

二F316

?

二m

幺

型

球

p4元S18

L二

幺

為

球

元2

二is-52

L.F

!51618

唾線:l建l慧ll鬻r元素:

8

質(zhì)△后續(xù)性表長(zhǎng)度：6

緩性美元藁：〈258161822>

表頭元素已從線性表中刪除

秘除后續(xù)些表長(zhǎng)度：5

線性表兀素：＜58161822>

Pressanykeytocontinue,

(2)實(shí)現(xiàn)鏈表類的參考代碼:

#include<iostream.h>

typedefintElemType;

structNodeType{

ElemTypedata;

NodeType*next;

)；

classLinkList{

private:

NodeType*Head;

intlen;

public:

LinkList();//構(gòu)造

"LinkList();//析構(gòu)

voidcreate();//頭插法建表

voidcreate2();//尾插法建表

intgetLen();〃獲取長(zhǎng)度

voidinsert();//插入

ElemTypedelet。；//刪除

voidsearch();//查找

voiddisplay();

voidinverse();//逆轉(zhuǎn)函數(shù)

)；

//創(chuàng)建空鏈表

LinkList::LinkList(){

Head二newNodeType;

Head->next二NULL;

Head->data=O;

len=0;

)

LinkList::"LinkList(){

NodeType*p=Head->next;

〃使指針P指向鏈表的第一個(gè)節(jié)點(diǎn)

while(p!=NULL){

Head->next=p->next;

//使頭指針指向P的下一個(gè)節(jié)點(diǎn)

deletep;

p=Head->next;

//使P節(jié)點(diǎn)指向頭指針向的那個(gè)節(jié)點(diǎn)

)

deleteHead;

〃最后將頭節(jié)點(diǎn)也刪除

len=0;

cout<〈〃已經(jīng)刪除鏈表!z，<<endl;

}

voidLinkList::display()(

NodeType*p;

p=Head->next;

cout<<〃鏈表的值為：〃；

while(p!=NULL){

cout<<p->data<<zz〃；

p=p->next;

)

cout<<endl;

)

voidLinkList::create(){//頭插法創(chuàng)建鏈表

NodeType*s;

ElemTypex;

cout<〈〃請(qǐng)輸入一組數(shù)據(jù)并且以0結(jié)束?！?lt;<endl;

cin>>x;//輸入數(shù)據(jù)元素。

while(x!=0){

s二newNodeType;//動(dòng)態(tài)的申請(qǐng)一個(gè)節(jié)點(diǎn)

s->data=x;//給節(jié)點(diǎn)的數(shù)據(jù)域賦值

s->next=Head->next;//使s指向第一個(gè)節(jié)點(diǎn)

Head->next=s;〃使頭節(jié)點(diǎn)指向新申請(qǐng)的s節(jié)點(diǎn)

1en++;

cin>>x;

)

cout<<“鏈表建成!，，<<endl;

)

voidLinkList::create2(){//尾插法創(chuàng)建鏈表

NodeType*last,*p;

ElemTypex;

last=Head;

cout<〈〃請(qǐng)輸入一組數(shù)據(jù)并且以0結(jié)束。z，<<endl;

cin>>x;//輸入數(shù)據(jù)元素。

while(x!=0){

p=newNodeType;

p->data=x;

last->next=p;//插在表尾

last=p;//修改尾指針

len++;

cin>>x;//讀入下一個(gè)元素

)

last->next=NULL;

cout<<〃鏈表建成！〃<<endl;

)

voidLinkList::insert(){

cout<〈〃要插入元素的位置：，，<<endl;

inti;

cin>>i;

cout<<“要插入的元素：，z<<endl;

ElemTypex;

cin>>x;

NodeType*p,*q,*s;〃定義結(jié)構(gòu)體類型指針

intk=l;

p=Head;//讓p指向Head節(jié)點(diǎn)

q=p->next;//讓q指向第一個(gè)節(jié)點(diǎn)

while(k<i&&q!=NULL){

P二q；

q=q->next;

k++;

)

if(k==i){〃實(shí)現(xiàn)插入

s=newNodeType;

s->data=x;

p->next=s;

s->next=q;

len++;

cout<〈〃記錄成功插入！"<<endl;

)

else

cout<〈〃插入記錄失??！〃；

)

ElemTypeLinkList::delet(){

cout<<〃輸入要?jiǎng)h除的元素：，z<<endl;

intx;

cin>>x;

NodeType*p,*q;

ElemTypey;

intk=1;

p=Head;

q=p->next;

while(q!=NULL&&q->data!=x){

P=q；

q=q->next;

)

if(q!=NULL&&q->data==x){

y=q->data;

p->next=q->next;

deleteq;

len一;

cout<<”記錄成功刪除!”<<endl;

)

else{

cout<<，zx不存在，刪除失敗"<<endl;

y=0;

}

returny;

)

voidLinkList::search(){

cout<〈”輸入要查找的元素："<<endl;

intx;

cin>>x;

NodeType*p=Head;

while(p!=NULL){

if(p->data==x){

cout<<”記錄查找成功！〃<<endl;//找到x

return;

)

p=p->next;//暫時(shí)沒找到，則繼續(xù)向后找

)

cout<<〃記錄不存在！〃<<endl;//查找不成功

)

voidLinkList::inverse(){//鏈表的逆置

NodeType*p,*q;

p=Head->next;//讓p指向第一個(gè)元素

Head->next=NULL;//讓Head的指針域?yàn)榭?/p>

while(p!=NULL){

q=p->next;//讓q指向第二個(gè)元素

p->next=Head->next;〃讓p的指針域?yàn)榭?/p>

Head->next=p;

p=q;

)

)

intLinkList::getLen(){

returnlen;

voidmain(){

LinkListh;

h.create2();

h.display();

h.search();

h.delet();

h.display();

h.insert();

h.display();

cout<<〃進(jìn)行鏈表元素逆置〃〈〈endl;

h.inverse();

h.display();

}

運(yùn)行結(jié)果如下圖所示：

2.實(shí)現(xiàn)二叉樹類。

4include〃stdio.h〃

^includeiostream.h〃

#defineN6

typedefstructBTreeNode{

intdata;

BTreeNode*lChiId,*rChiId;

}Bnode,*ptr;

classBTree{

public:

voidsetRoot(ptrr){root=r;}

ptrgetRoot(){returnroot;}

ptrcreateBTree();//二叉樹的創(chuàng)建

ptrbuiIdtree(inta[],intb[],inti,intj,ints,intt);

voidpreOrder。；//前序遍歷(遞歸)

voidinOrder。；//中序遍歷(遞歸)

voidpostOrder();〃后序遍歷(遞歸)

intBTreeSize();//求結(jié)點(diǎn)個(gè)數(shù)

intBTreeLeaves();//求葉子結(jié)點(diǎn)個(gè)數(shù)

intBTreeHeight();//求樹高

protected:

voidinOrder(ptr)"/中序遍歷

voidpreOrder(ptr);//前序遍歷

voidpostOrder(ptr);//后序遍歷

intBTreeSize(ptr);〃結(jié)點(diǎn)個(gè)數(shù)

intBTreeLeaves(ptr);//葉子結(jié)點(diǎn)

intBTreeHeight(ptr);//樹高

private:

ptrroot;

}；

ptrBTree::createBTree(){

ptrp;

intx;

scanf("%d〃，&x);

if(x==0)returnNULL;

p=newBnode;

p->data=x;

p->lChild=createBTree();

p->rChild=createBTree();

returnp;

}

ptrBTree::buildtree(inta[],intb[],inti,intj,ints,intt){

intk;

ptrp;

if(i>j)returnNULL;//序列空，返回空指針

p=newBnode;//申請(qǐng)結(jié)點(diǎn)

p->data=a[i];//造根結(jié)點(diǎn)

k=s;

while((k<=t)&&(b[k]!=a[i]))k++;//找根

if(b[k]!=a[i]){

cout<<z，Errorz，<<endl;

returnNULL;//沒找到，出錯(cuò)

)

p->lChild=buiIdtree(a,b,i+1,i+k-s,s,k-l);

p->rChild=buiIdtree(a,b,i+k-s+1,j,k+1,t);

returnp;//返回根結(jié)點(diǎn)