計算機軟件技術(shù)復(fù)習(xí)公開課一等獎市優(yōu)質(zhì)課賽課獲獎?wù)n件

計算機軟件技術(shù)基礎(chǔ)復(fù)習(xí)*第二章常用數(shù)據(jù)結(jié)構(gòu)及其運算算法分析——算法復(fù)雜度算法、數(shù)據(jù)結(jié)構(gòu)（邏輯結(jié)構(gòu)、存儲結(jié)構(gòu)）*例題下面程序段的時間復(fù)雜度為（）。for(inti=0;i<m;i++)for(intj=0;j<n;j++)a[i][j]=i*j;A.O(m2)B.O(n2)C.O(m+n)D.O(m*n)*線性表的順序存儲結(jié)構(gòu)1.順序存儲結(jié)構(gòu)

2.順序存儲結(jié)構(gòu)的插入運算3.順序存儲結(jié)構(gòu)的刪除運算*線性表的鏈?zhǔn)酱鎯Y(jié)構(gòu)鏈?zhǔn)酱鎯Y(jié)構(gòu)基本運算

1、前插

2、后插

3、刪除*特殊線性表——棧和隊棧的定義和基本操作判斷棧空、隊滿的條件有三個元素的進棧序列是1，2，3，舉出此三個元素可能的出棧序列，并寫出相應(yīng)的進棧和出棧操作序列如圖所示(假設(shè)以I和O表示進棧和出棧操作)。*隊隊的定義訪問算法順序隊

1、基本操作：出隊：front＋＋入隊：rear＋＋

2、循環(huán)隊列的結(jié)構(gòu)及判斷隊空、隊滿的條件

3、基本運算*循環(huán)隊列隊列為空front＝＝rearfront=rear+1隊列已滿*數(shù)組數(shù)組的兩種順序存儲方式順序存儲地址公式Loc(aij)=Loc(a11)+(i-1)*n+(j-1)按行優(yōu)先儲存按列優(yōu)先儲存Loc(aij)=Loc(a11)+(j-1)*m+(i-1)*數(shù)組有一個N×N的下三角矩陣A，若采用行優(yōu)先進行順序存儲，每個元素占用4個字節(jié)，則Aij(1≤i≤N,1≤j≤i)元素的相對字節(jié)地址（相對首元素地址而言）為

。

A.（i×（i+1）/2+j-1）×4B.（i×i/2+j）×4C.（i×（i-1）/2+j-1）×4D.（i×（i-1）/2+j）×4A=a110…0a21a22…0

an1an2…ann

C非線性數(shù)據(jù)結(jié)構(gòu)——樹與二叉樹樹及其基本概念二叉樹的定義三種特殊形態(tài)的二叉樹滿二叉樹、完全二叉樹的編號*二叉樹的基本性質(zhì)性質(zhì)1：二叉樹的第i層最多有2i-1

個結(jié)點。(i1)性質(zhì)2：深度為k的二叉樹最多有個結(jié)點。性質(zhì)3：對一棵二叉樹，如果葉子結(jié)點數(shù)為n0，度為2的結(jié)點數(shù)為n2，則n0=n2+1。設(shè)一棵完全二叉樹有1000個結(jié)點，試問

1)有多少個葉子結(jié)點，

2)有多少個度為2的結(jié)點；

3)有多少個結(jié)點只有非空左子樹。二叉樹的基本性質(zhì)二叉樹的遍歷先序、中序、后序二叉排序樹性質(zhì)、生成

哈夫曼樹帶權(quán)路徑長度、哈夫曼樹的生成*有如圖所示的一棵二叉樹，則該二叉樹的先序、中序、后序遍歷序列為

。CBDAEGFABCDEFGCDBGFEA先序中序后序二叉樹的遍歷

給定序列{52，8，5，16，78，19}，畫出產(chǎn)生一棵二叉排序樹的過程。**

字符：S、C、T、A、空格權(quán)值：{6，2，4，5，3}①以字符權(quán)值作為葉子結(jié)點的權(quán)值構(gòu)造一棵哈夫曼樹，并求出其帶權(quán)路徑長度。②試對電文“1000100”進行翻譯2094511562301010101TACS答案：CAT二叉樹的應(yīng)用*

圖頂點的度

在無向圖中，頂點的度就是和該頂點相關(guān)聯(lián)的邊的數(shù)目。在有向圖中：頂點的度=入度+出度兩種最常用的表示方法：鄰接矩陣鄰接表

圖的存儲結(jié)構(gòu)查找評價查找算法好壞的依據(jù)——平均查找長度順序查找對分查找分塊查找二叉排序樹查找*已知長度為6的線性表：(45，24，53，13，30，85)1）按順序依次插入，二叉排序樹；2）試分別求出在等概率情況下二叉排序樹查找成功的平均查找長度。*樹的平均查找長度為

ASL(a)=1/6[1+2+2+3+3+3]=14/6*排序選擇排序插入排序冒泡排序快速排序初始狀態(tài)[46745314263886652734]第一趟[465314263874652734]86第二趟[4614263853652734]7486第三趟[14263846532734]657486第四趟[142638462734]53657486第五趟[1426382734]4653657486第六趟[14262734]384653657486第七趟[14262734]384653657486冒泡第3章操作系統(tǒng)操作系統(tǒng)的類型：特點

多道批處理系統(tǒng)、分時系統(tǒng)、實時系統(tǒng)*存儲管理存儲管理的功能 內(nèi)存分配 地址轉(zhuǎn)換：靜、動態(tài)地址重定位的區(qū)別 存儲保護 內(nèi)存擴充*實存儲管理分區(qū)分配

固定分區(qū)可變分區(qū)：

尋找空閑區(qū)的算法——

最先、最佳、最差適應(yīng)算法*虛擬存儲管理分頁存儲管理地址轉(zhuǎn)換

*例頁號01234頁架號64320狀態(tài)11110每頁長為32字，現(xiàn)有邏輯地址為：68，180，若能翻譯成相應(yīng)的物理地址*處理器管理進程調(diào)度：調(diào)度算法進程的狀態(tài)及轉(zhuǎn)換*進程的同步與互斥進程的同步進程互斥臨界區(qū)P-V操作***雙向制約

設(shè)兩個信號量S1和S2，且賦予它們的初值S1為1，S2為0，L1:進程AL2:進程BP（S1）P（S2）把信息送入緩沖區(qū)從緩沖區(qū)取走信息V（S2）V（S1）GOTOL1GOTOL2*死鎖死鎖的定義必要條件死鎖的預(yù)防*設(shè)備管理設(shè)備分類按使用方法：絕對設(shè)備號、相對設(shè)備號緩沖技術(shù)假脫機系統(tǒng)的目的*1）循環(huán)測試I/O方式:I/O測試指令不斷對該設(shè)備進行測試，直到設(shè)備空閑為止。

2）程序中斷I/O方式:

中斷技術(shù)及中斷處理機構(gòu)的引入，使得CPU與外圍設(shè)備的工作有了相對獨立性。

3）通道I/O方式:

引入通道技術(shù)，使主機不再干預(yù)I/O操作。I/O控制方式的改進**文件管理文件目錄*實體間的聯(lián)系

兩個實體型之間的聯(lián)系可以分為三類：一對一聯(lián)系一對多聯(lián)系多對多聯(lián)系*概念模型表示方法：實體—聯(lián)系方法

E–R圖：提供了表示實體型、屬性和聯(lián)系的方法。*數(shù)據(jù)模型