數(shù)據(jù)結(jié)構(gòu)相關(guān)文檔和PPT

數(shù)據(jù)結(jié)構(gòu)任課教師：邱保志Email：iebzqiu@單位：鄭州大學(xué)信息工程學(xué)院持之以恒天道酬勤為什么要學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)？介于數(shù)學(xué)、計(jì)算機(jī)軟件、硬件三者之間的核心課程一般程序設(shè)計(jì)（尤指非數(shù)值計(jì)算的程序設(shè)計(jì)）的基礎(chǔ)設(shè)計(jì)和實(shí)現(xiàn)編譯程序、操作系統(tǒng)、數(shù)據(jù)庫系統(tǒng)及其它系統(tǒng)程序和大型應(yīng)用程序的重要基礎(chǔ)。如何利用計(jì)算機(jī)解決實(shí)際應(yīng)用問題？需經(jīng)過以下三步驟：從具體問題中抽象出一個(gè)適當(dāng)?shù)臄?shù)學(xué)模型。設(shè)計(jì)一個(gè)解此數(shù)學(xué)模型的算法編程調(diào)試，得到最終答案

NiklausWirth：

Algorithm+DataStructures=Programs

算法:處理問題的策略

數(shù)據(jù)結(jié)構(gòu):問題的數(shù)學(xué)模型程序:為計(jì)算機(jī)處理問題編制一組指令集登錄號(hào)書名作者出版單位出版時(shí)間N.3.73.762數(shù)據(jù)結(jié)構(gòu)嚴(yán)蔚敏吳偉民清華大學(xué)出版社2003.12圖書館的書目檢索系統(tǒng)自動(dòng)化問題數(shù)學(xué)模型一對(duì)一的線性結(jié)構(gòu)人機(jī)對(duì)弈問題數(shù)學(xué)模型一對(duì)多的樹結(jié)構(gòu)“井”字棋對(duì)弈“樹”先手：C1C9C4C2C12C10C11C5C3C6C7C8計(jì)算機(jī)專業(yè)課程開設(shè)先后關(guān)系圖數(shù)學(xué)模型多對(duì)多的圖形結(jié)構(gòu)計(jì)算機(jī)專業(yè)課程開設(shè)問題怎樣學(xué)數(shù)據(jù)結(jié)構(gòu)？牢記基本概念和經(jīng)典算法聯(lián)系實(shí)際，富于聯(lián)想總結(jié)算法之間的共性和特性。忌：求偏、求難、重算法輕概念。三階段：模仿->總結(jié)->創(chuàng)新

本書的內(nèi)容簡(jiǎn)介第一章:綜述數(shù)據(jù)結(jié)構(gòu)等基本概念，介紹算法和算法分析(3/2周)第二章-第七章:討論線性表(3周)、棧和隊(duì)列(2周)、串(2周)

、數(shù)組和廣義表(2周)

、樹和二叉樹(2周)

、圖(2周)等基本類型的數(shù)據(jù)結(jié)構(gòu)、物理結(jié)構(gòu)及其相關(guān)操作的實(shí)現(xiàn)。第九章:靜態(tài)查找表和動(dòng)態(tài)查找表。(2周)第十章:介紹五種內(nèi)排序方法(2周)復(fù)習(xí)（1/2周）1.2基本概念和術(shù)語數(shù)據(jù)：信息的載體，是描述客觀事物的數(shù)、字符及所有能輸入到計(jì)算機(jī)中被計(jì)算機(jī)程序識(shí)別和處理的符號(hào)的集合。數(shù)值性數(shù)據(jù)非數(shù)值性數(shù)據(jù)數(shù)據(jù)元素：數(shù)據(jù)的基本單位一個(gè)數(shù)據(jù)元素可由若干個(gè)數(shù)據(jù)項(xiàng)組成。數(shù)據(jù)項(xiàng)是數(shù)據(jù)不可分割的最小單位。數(shù)據(jù)對(duì)象：數(shù)據(jù)的子集。具有相同性質(zhì)的數(shù)據(jù)元素集合。例如：整數(shù)對(duì)象N={0,1,2,…}數(shù)據(jù)結(jié)構(gòu)（邏輯結(jié)構(gòu)）數(shù)據(jù)結(jié)構(gòu)：相互間存在一種或多種特定關(guān)系的數(shù)據(jù)元素集合。結(jié)構(gòu)：數(shù)據(jù)元素相互之間的關(guān)系特定關(guān)系：特定關(guān)系數(shù)據(jù)結(jié)構(gòu)舉例沒有關(guān)系集合正整數(shù)一對(duì)一關(guān)系線性表圖書管理一對(duì)多關(guān)系樹棋局對(duì)弈樹多對(duì)多關(guān)系圖（網(wǎng)）課程開設(shè)先后關(guān)系圖數(shù)據(jù)結(jié)構(gòu)的形式定義DS=(D,S)D：數(shù)據(jù)元素的有限集合。設(shè)Ｄ＝{a1,a2,…,ai,aj,…,an}S：定義在D上的關(guān)系的有限集合。若aiRaj,則＜ai,aj＞∈S若aiRaj,且ajRai,則(ai,aj)∈S例：復(fù)數(shù)可定義為一種數(shù)據(jù)結(jié)構(gòu)：

COMPLEX=(C,R)C：含有兩個(gè)實(shí)數(shù)的集合{C1,C2}；R：{P}是定義在C上的一種關(guān)系{<C1,C2>}課上習(xí)題：T=(K,R)，畫出它所對(duì)應(yīng)的邏輯結(jié)構(gòu)K={1,2,3,4,5,6}；Ｒ={r}r={<1,2>,<1,3>,<2,4>,<2,5,>,<3,6>}aiajaiaj線性結(jié)構(gòu)樹形結(jié)構(gòu)456231ABEDCF圖形結(jié)構(gòu)125643集合結(jié)構(gòu)四類基本邏輯結(jié)構(gòu)關(guān)系圖

數(shù)據(jù)結(jié)構(gòu)在計(jì)算機(jī)中的表示：數(shù)據(jù)元素的表示數(shù)據(jù)元素之間關(guān)系的表示順序映象：借助元素在存儲(chǔ)器的相對(duì)位置表示數(shù)據(jù)元素之間的邏輯關(guān)系。對(duì)應(yīng)于順序存儲(chǔ)結(jié)構(gòu)(sequentialsets).非順序映象：利用指示元素存儲(chǔ)地址的指針表示數(shù)據(jù)元素間的邏輯關(guān)系。對(duì)應(yīng)于鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)(linkedlists)索引樹(indexedtrees)散列表(hashtables)數(shù)據(jù)的物理結(jié)構(gòu)(存儲(chǔ)結(jié)構(gòu))數(shù)據(jù)邏輯結(jié)構(gòu)和物理結(jié)構(gòu)之間的關(guān)系關(guān)系：任意一個(gè)算法的設(shè)計(jì)取決于選定的邏輯結(jié)構(gòu)算法的實(shí)現(xiàn)依賴于采用的物理結(jié)構(gòu)。實(shí)際應(yīng)用算法數(shù)據(jù)結(jié)構(gòu)線性結(jié)構(gòu)非線性結(jié)構(gòu)存儲(chǔ)結(jié)構(gòu)

順序存儲(chǔ)結(jié)構(gòu)非順序存儲(chǔ)結(jié)構(gòu)定位(查找)加法、乘法比較、移動(dòng)（邏輯）(物理)數(shù)據(jù)結(jié)構(gòu)主要研究什么？解決問題時(shí)可能遇到的典型的邏輯結(jié)構(gòu)邏輯結(jié)構(gòu)的存儲(chǔ)映象（物理結(jié)構(gòu)）數(shù)據(jù)結(jié)構(gòu)的相關(guān)操作及其實(shí)現(xiàn)（算法）數(shù)據(jù)類型數(shù)據(jù)類型：一組性質(zhì)相同的值的集合以及定義于該值集上的一組操作的總稱。例：C語言中整型變量值：定義在某區(qū)間上的整數(shù)操作：加、減、乘、除、取模按值的不同特性分：原子類型：值不可再分C的五種基本數(shù)據(jù)類型:char,int,float,double,void結(jié)構(gòu)類型：值由若干個(gè)成分按某種結(jié)構(gòu)組成抽象數(shù)據(jù)類型一個(gè)數(shù)據(jù)模型及定義在該模型上的一組操作。按照值域的不同特性:原子類型（值不可分解）、固定聚合類型（值有確定數(shù)目的成分）、可變聚合類型（成分的數(shù)目不確定）。例：抽象數(shù)據(jù)類型：矩陣=矩陣+(求轉(zhuǎn)置、加、乘、逆等）形式定義：DS=(D,S,P)。

D：數(shù)據(jù)對(duì)象

S：D上的關(guān)系集，

P：對(duì)D的基本操作集。構(gòu)造性操作：插入、刪除、修改非構(gòu)造性操作：查找、排序抽象數(shù)據(jù)類型的定義格式(僅適用于本書)ADT抽象數(shù)據(jù)類型名{

數(shù)據(jù)對(duì)象：〈數(shù)據(jù)對(duì)象的定義〉

數(shù)據(jù)關(guān)系：〈數(shù)據(jù)關(guān)系的定義〉

基本操作：〈基本操作的定義〉}ADT抽象數(shù)據(jù)類型名基本操作的定義格式為基本操作名（參數(shù)表）初始條件：〈初始條件描述〉

操作結(jié)果：〈操作結(jié)果描述〉參數(shù)表有兩種參數(shù)：賦值參數(shù)：只為操作提供輸入值；引用參數(shù)：以&打頭，除可提供輸入值外，還將返回操作結(jié)果。初始條件描述了操作執(zhí)行前數(shù)據(jù)結(jié)構(gòu)和參數(shù)應(yīng)滿足的條件，若不滿足，則操作失敗，并返回相應(yīng)出錯(cuò)信息。操作結(jié)果說明了操作正常完成之后，數(shù)據(jù)結(jié)構(gòu)的變化狀況和應(yīng)返回的結(jié)果。若初始條件為空，則省略之。抽象數(shù)據(jù)類型舉例-矩陣ADTMatrix{

數(shù)據(jù)對(duì)象:D={ai,j|i=1,2,…,m;j=1,2,…,n;ai,j∈ElemSet}

數(shù)據(jù)關(guān)系:R={Row,Col}Row={<ai,j,ai,j+1>|1≤i≤m,1≤j≤n-1}Col={<ai,j,ai+1,j>|1≤i≤m-1,1≤j≤n}

基本操作：

CreateMatrix(&M)

DestroyMatrix(&M)

PrintMatrix(&M)

AddMatrix(M,N,&Q)

SubMatrix(M,N,&Q)

MultMatrix(M,N,&Q)

TransposeMatrix(M,&T)}ADTMatrix1.3類Ｃ語言的語法規(guī)則1、預(yù)定義常量和類型：2、數(shù)據(jù)結(jié)構(gòu)的描述，數(shù)據(jù)元素類型的定義3、基本操作的算法可以使用的函數(shù)表示4、算法描述中可以使用的賦值語句形式5、算法描述中可以使用的選擇結(jié)構(gòu)語句形式6、算法描述中可以使用的循環(huán)結(jié)構(gòu)語句形式7、描述算法中可以使用的結(jié)束語句形式8、算法描述中可以使用的輸入輸出語句形式9、算法描述中可以使用的注釋格式10、算法描述中可以使用的擴(kuò)展函數(shù)11、算法描述中可以使用的邏輯運(yùn)算的約定類Ｃ語言的語法規(guī)則示例例1typedef

intStatus;voidexample_1(){Statusa[10];

a[0..9]=0;}例2#defineOK1typedef

intStatus;Statusexample_2(intx,inty){

if(x>y)x<->y;

returnOK;}類Ｃ語言的語法規(guī)則示例（續(xù)）例3typedef

structstudent{

charid[5];

charname[11];

int

age;

intmath;

inteng;

int

ds;

int

os;}student;voidexample_3(){students;

s=('','',0,0,0,0,0);}附加內(nèi)容：算法的描述方法步驟法程序流程圖N-S圖偽碼步驟法順序查找數(shù)據(jù)序列中某個(gè)特定值Step1：輸入數(shù)據(jù)序列data[n]和欲查找值keyStep2：從序列中的最后一個(gè)元素開始查找Step3：若該元素值不等于key，查找前一項(xiàng)．Step4

：若該元素值等于key，表示查找成功，返回key在序列中的位置，去第六步．Step5：如果數(shù)據(jù)全部查找過但未能找到key，表示查找失敗，返回０。Step6：結(jié)束程序流程圖——五種基本控制結(jié)構(gòu)程序流程圖舉例開始輸入待查找序列data[n]查找成功，返回i輸入要查找的值key查找失敗返回０data[i]==key從最后一個(gè)元素開始查找待查序列全查過ＹＹNN順序查找數(shù)據(jù)序列中某特定值結(jié)束i--N-S圖N-S圖也叫盒圖，一種符合結(jié)構(gòu)化程序設(shè)計(jì)原則的圖形描述工具。五種基本控制結(jié)構(gòu)由五種圖形構(gòu)件表示：N-S圖舉例順序查找數(shù)據(jù)序列中某特定值F輸入待查找序列data[n]輸入要查找的值key從最后一個(gè)元素開始查找

data[i]==key

查找成功返回key所在位置

全查過查找失敗返回０TFT下一次循環(huán)Dowhile(data!=key)偽碼以夾雜程序語法和自然語言的形式來描述解決問題的方法，有類C、類PASCAL語言等。本書用的是類C語言。順序查找數(shù)據(jù)序列中某特定值，由類C給出其算法StatusSearch_Seq(SqList

L,KeyTypekey){L.elem[0]=key;for(i=L.length;!EQ(L.elem[i],key);i--);returni;}Search_Seq.h代碼//說明部分#include<stdio.h>//包含預(yù)編譯頭文件#defineTRUE1

//宏定義#defineFALSE0typedef

int

KeyType;//類型別名的定義typedef

struct{

KeyType*elem;

intlength;}SqList;bool

EQ(int

i,intj)

//判斷兩個(gè)整數(shù)是否相等{ if(i==j)

returnTRUE;

else

returnFALSE;}順序查找數(shù)據(jù)序列中某特定值的程序代碼stdio.hmath.hstring.hmalloc.h//函數(shù)實(shí)現(xiàn)void

Construction(SqList&L)

//構(gòu)造無序序列{inti;

printf(“inputthelengthofdata:\n");

scanf("%d",&L.length);

L.elem=(KeyType*)malloc((L.length+1)*sizeof(KeyType));

printf(“inputthekey:\n”);

//輸入待查找的關(guān)鍵字

for(i=1;i<=L.length;i++)

scanf("%d",&L.elem[i]);}int

Search(SqList

L,KeyTypekey)

//查找函數(shù){

inti; L.elem[0]=key; for(i=L.length;!EQ(L.elem[i],key);--i);

returni;}順序查找數(shù)據(jù)序列中某特定值的程序代碼Search_Seq.cpp代碼#include“search_seq.h"voidmain(){ KeyTypekey;

SqListL;

printf(“inputkey:\n”);

scanf(“%d”,&key);

//讀入要查找的值

Construction(L);

//創(chuàng)建待查找數(shù)據(jù)序列

int

position=Search(L,key);

//查找

printf("thekeyislocatedin%d",position);}順序查找數(shù)據(jù)序列中某特定值的程序代碼1.4算法和算法分析算法的定義：對(duì)特定問題求解步驟的一種描述，是指令的有限序列，一條指令表示一個(gè)或多個(gè)操作。操作分為：數(shù)值計(jì)算：加、減、乘、除等算術(shù)運(yùn)算非數(shù)值計(jì)算：檢索、排序、插入、刪除。算法的特性：有窮性：算法應(yīng)在執(zhí)行有窮步后結(jié)束確定性：每步定義都是確切、無歧義的可行性：算法中描述的操作都可通過已經(jīng)實(shí)現(xiàn)的基本運(yùn)算執(zhí)行有限次實(shí)現(xiàn)輸入：有0個(gè)或多個(gè)輸入輸出：有一個(gè)或多個(gè)輸出(處理結(jié)果)算法與程序的區(qū)別算法設(shè)計(jì)的要求正確性：程序不含語法錯(cuò)誤；程序?qū)τ趲捉M輸入數(shù)據(jù)能夠得出滿足要求的結(jié)果；對(duì)精心選擇帶有刁難性的幾組數(shù)據(jù)能得出滿足要求的結(jié)果；程序?qū)τ谝磺泻戏ǖ妮斎霐?shù)據(jù)都能產(chǎn)生滿足要求的結(jié)果?？勺x性：易于閱讀和交流，其次是機(jī)器運(yùn)行。

健壯性：當(dāng)輸入數(shù)據(jù)非法時(shí)，算法能適當(dāng)?shù)刈鞒龇磻?yīng)或進(jìn)行處理，保證不會(huì)產(chǎn)生莫名其妙的輸出結(jié)果。處理出錯(cuò)的方法是返回一個(gè)表示錯(cuò)誤或錯(cuò)誤性質(zhì)的值，以便在更高的抽象層次上進(jìn)行處理，不應(yīng)中斷程序的執(zhí)行。高效率和低存儲(chǔ)量需求：兩者都與問題的規(guī)模有關(guān)。1.4.3算法效率的度量事后統(tǒng)計(jì)：運(yùn)用計(jì)算機(jī)的計(jì)時(shí)功能統(tǒng)計(jì)算法的運(yùn)行時(shí)間。缺陷：要運(yùn)行算法對(duì)應(yīng)的程序；時(shí)間統(tǒng)計(jì)結(jié)果依賴于計(jì)算機(jī)軟、硬件環(huán)境；事前分析估計(jì)：算法消耗的時(shí)間與下列因素有關(guān)：算法采用的策略問題的規(guī)模書寫程序的語言編譯器產(chǎn)生的機(jī)器代碼的質(zhì)量計(jì)算機(jī)執(zhí)行指令的速度。doublestart,stop;time(&start); intk=search_seq(ST,key);time(&stop); doublerunTime=stop-start;printf(“%f”,runTime);算法的時(shí)間量度算法的時(shí)間量度與問題的規(guī)模n有關(guān)從算法中選取一種對(duì)于所研究問題來說是基本操作的原操作，以該基本操作重復(fù)執(zhí)行次數(shù)作為算法的時(shí)間量度。算法中基本操作重復(fù)執(zhí)行次數(shù)是問題規(guī)模n的某個(gè)函數(shù)f(n)(漸近)時(shí)間復(fù)雜度：算法的時(shí)間量度記作(n)=O(f(n))，表示隨問題規(guī)模n的增大，算法執(zhí)行時(shí)間的增長(zhǎng)率和f(n)的增長(zhǎng)率相同，稱為算法的漸近時(shí)間復(fù)雜度。簡(jiǎn)稱時(shí)間復(fù)雜度。語句頻度：語句重復(fù)執(zhí)行的次數(shù)。兩個(gè)n*n矩陣相乘的算法

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

for(j=1;j<=n;++j)

{ c[i][j]=0; for(k=1;k<=n;++k)

c[i][j]+=a[i][k]*b[k][j];

}例１問題規(guī)模:n*n原操作:c[i][j]+=a[i][k]*b[k][j];基本操作重復(fù)執(zhí)行的次數(shù):f(n)=n3算法時(shí)間度:T(n)=O(f(n))=O(n3)例２程序段語句頻度時(shí)間復(fù)雜度{++x;s=0}@

for(i=1;i<=n;++i){++x;s+=x;}@for(i=1;i<=n;++i)for(j=1;j<=n;++j){++x;s+=x;}@i=1;while(i<=n)i=i*2;@1O(1)nO(n)n2log2nO(log2n)O(n2)大O表示法的加法規(guī)則和乘法規(guī)則加法規(guī)則針對(duì)并列程序段

T(n,m)=T1(n)+T2(m) =O(max(f(n),g(m)))

乘法規(guī)則針對(duì)嵌套程序段

T(n,m)=T1(n)*T2(m)

=O(f(n)*g(m))

特例：若T1(n)=O(c)，T2(n)=O(f(n))則T(n)=T1(n)*T2(n)=O(c*f(n))=O(f(n))問題規(guī)模:m*n原操作:

sum[i]+=x[i][j];

基本操作重復(fù)執(zhí)行的次數(shù):f(n)=m*n算法時(shí)間度:T(n)=O(f(n))=O(m*n)

voidadd(floatx[][],intm,intn){for(inti=0;i<m;i++){sum[i]=0.0;

for(intj=0;j<n;j++) sum[i]+=x[i][j];}for(i=0;i<m;i++)

printf(“%f”,sum[i]);}例３O(max(m*n,m))問題規(guī)模:n原操作:

a[j]<->a[j+1];基本操作重復(fù)執(zhí)行的次數(shù):

不定算法時(shí)間度:T(n)=O(n2)例４voidbubble_sort(int

a[],int

n){for(i=n-1,change=TRUE;i>=1,change;--i){change=FALSE;//判斷是否有相鄰元素交換

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

if(a[j]>a[j+1]){a[j]<->a[j+1];change=TRUE;}}}例５for(i=2;i<=n;++i)for(j=2;j<=i-1;++j){++x;a[i][j]=x;}問題規(guī)模:n原操作:

a[i][j]=x;基本操作重復(fù)執(zhí)行的次數(shù):

難以精確計(jì)算(1+1+2+…+n-2)算法時(shí)間度:T(n)=O(n2)算法的設(shè)計(jì)、選取和時(shí)間復(fù)雜度分析的原則應(yīng)該盡可能選用多項(xiàng)式階的算法，不希望用指數(shù)階算法的時(shí)間復(fù)雜度只考慮問題規(guī)模n的增長(zhǎng)率，在難以精確計(jì)算基本操作執(zhí)行次數(shù)（或語句頻度）時(shí)，只需求得它關(guān)于n的增長(zhǎng)率或階即可。算法中基本操作重復(fù)執(zhí)行次數(shù)隨問題的輸入數(shù)據(jù)集不同而不同，要考慮最壞情況下的時(shí)間復(fù)雜度。例６：百錢買百雞問題100元錢買100只雞，母雞每只5元，公雞每只3元，小雞3只1元，問共可以買多少只母雞、多少只公雞、多少只小雞？解：設(shè)母雞、公雞、小雞各為x,y,z只。則有：

x+y+z=100 5x+3y+z/3=100方法1：for(i=0;i<=100;i++)

for(j=0;j<=100;j++)

for(k=0;k<=100;k++){

if(k%3==0&&i+j+k==100&&5*I+3*j+k/3==100)

printf(“%d,%d,%d\n”,i,j,k);

}方法2：用兩重循環(huán)：

for(i=0;i<100;i++) for(j=0;j<100;j++) {k=100–i–j;//小雞的數(shù)目可以由母雞數(shù)和公雞數(shù)得到。

if(k%3==0&&5*i+3*j+k/3==100)

printf(“%d,%d,%d\n”,i,j,k); }方法3：用兩重循環(huán)：

for(i=0;i<=20;i++)//母雞數(shù)不可能超過20只

for(j=0;j<33;j++)//公雞數(shù)也不超過33只

{k=100–i–j; if(k%3==0&&5*i+3*j+k/3==100)

printf(“%d,%d,%d\n”,i,j,k); }例６：百錢買百雞問題(續(xù))例６：百錢買百雞問題(續(xù))方法4：用一重循環(huán)由x+y+z=100和5*x+3*y+z/3=100合并為一個(gè)方程：

14*x+8*y=200,進(jìn)一步簡(jiǎn)化為:7*x+4*y=100x不超過14，并可以進(jìn)一步判斷x必為4的倍數(shù)，有：for(i=0;i<=14;i+=4){ j=(100–7*i)/4; k=100–i–j;

printf(“%d,%d,%d\n”,i,j,k);}方法一的循環(huán)次數(shù)為：100*100*100方法二的循環(huán)次數(shù)為：100*100，1萬次；方法三的循環(huán)次數(shù)為：20*34，680次，方法四的循環(huán)次數(shù)為：4次，時(shí)間復(fù)雜度O（n3）O(n2)O(n2)O(n)事前估計(jì)與事后統(tǒng)計(jì)方法：

例:設(shè)兩個(gè)矩陣相乘算法的時(shí)間復(fù)雜度為T(n)=O(n3),兩個(gè)10*10的矩陣相乘,執(zhí)行時(shí)間為12ms，請(qǐng)問估計(jì)兩個(gè)31＊31矩陣相乘的時(shí)間。

10312

－－＝－－

313time算法的空間復(fù)雜度度量漸進(jìn)的空間復(fù)雜度：算法所需存儲(chǔ)空間的量度。記作：S(n)=O(g(n))，其中n為問題的規(guī)模,表示隨著問題規(guī)模n的增大，算法運(yùn)行所需存儲(chǔ)量的增長(zhǎng)率與g(n)的增長(zhǎng)率相同。算法的存儲(chǔ)量包括:

1．輸入數(shù)據(jù)所占空間; 2．程序本身所占空間；

3．額外輔助空間。應(yīng)掌握的類型題一、數(shù)據(jù)結(jié)構(gòu)的基本概念

1、在數(shù)據(jù)結(jié)構(gòu)中，從邏輯上可以把數(shù)據(jù)結(jié)構(gòu)分成

和

。

2、線性結(jié)構(gòu)中元素之間存在

關(guān)系，樹形結(jié)構(gòu)中元素之間存在

關(guān)系，圖形結(jié)構(gòu)中元素之間存在

關(guān)系。

3、數(shù)據(jù)元素是數(shù)據(jù)的最小單位(對(duì)/錯(cuò))(北京郵電大學(xué)1998年)二、算法和時(shí)間復(fù)雜度分析

1、將下列函數(shù)，按它們?cè)趎->∞時(shí)的無窮大階數(shù)，從小到大排序（中科院計(jì)算所1995年）

n,n-n3+7n5,nlog2n,2n/2,n3,log2n,n1/2+log2n,(3/2)n,n!,n2+log2n答：log2n,n1/2+log2n,n,nlog2n,n2+log2n,n3,n-n3+7n5,2n/2,(3/2)n,n!c<log2n<n<nlog2n<n2<n3<2n<3n<n!應(yīng)掌握的類型題2、voidprime(intn){inti=2;

while((n%i)!=0&&i*1.0<sqrt(n))i++;if(i*1.0>sqrt(n))printf(“%disaprimenumber!”);else

printf(“%disnotaprimenumber!”);}答：prime嵌套最深層語句是：i++，頻度由((n%2)!=0&&i*1.0<sqrt(n))決定，時(shí)間復(fù)雜度是O(√n)鄭州大學(xué)歷年試題選（第一章）(2005).已知有實(shí)現(xiàn)同一功能的兩個(gè)算法A和B，其時(shí)間復(fù)雜度分別為O(n)和O(n2)，當(dāng)問題規(guī)模n=100時(shí)，執(zhí)行A算法需要10秒鐘，請(qǐng)問在同樣的運(yùn)行環(huán)境下，對(duì)同一問題規(guī)模能否估計(jì)B算法運(yùn)行的時(shí)間？若能，試估計(jì)B算法的運(yùn)行時(shí)間；若不能，說明原因。(不能。算法復(fù)雜度是指用算法的基本操作重復(fù)執(zhí)行的次數(shù)作為時(shí)間的量度，不能用一個(gè)算法的具體執(zhí)行時(shí)間估計(jì)另一個(gè)算法具體的執(zhí)行時(shí)間，因?yàn)閺?fù)雜度表示中常量被忽略了。)（2006）

任何一個(gè)算法設(shè)計(jì)取決于選定的數(shù)據(jù)（邏輯）結(jié)構(gòu)，而算法的實(shí)現(xiàn)依賴于采用的存儲(chǔ)結(jié)構(gòu)。（2006）

算法的有窮性的含義是：對(duì)任何合法的輸入值，一個(gè)算法必須再執(zhí)行有窮步后結(jié)束，且每一步都可在有窮時(shí)間內(nèi)完成，也就是說，在算法中不能使用無限循環(huán)語句。

（2001）計(jì)算下列程序段中x-=10的執(zhí)行次數(shù)。

X=91;y=100; While(y>0) If(x>100){x-=10;y--;} Elsex++;鄭州大學(xué)歷年試題選（第一章續(xù)）有一計(jì)算矩陣相乘的程序，它的時(shí)間復(fù)雜度為O(n3)，當(dāng)上機(jī)運(yùn)行兩個(gè)10×10矩陣相乘時(shí)，執(zhí)行時(shí)間為5ms，試計(jì)算兩個(gè)30×30的矩陣相乘所需的時(shí)間。1.數(shù)據(jù)類型是一個(gè)值集合和定義在這個(gè)值集合上的一組___總稱。

2.若上機(jī)運(yùn)行兩個(gè)10×10矩陣相乘，執(zhí)行時(shí)間為5ms，該矩陣相乘算法的時(shí)間復(fù)雜度T(n)=O(n3)，其中n為矩陣的規(guī)模，則利用該算法計(jì)算兩個(gè)20×20的矩陣相乘時(shí)，執(zhí)行時(shí)間為_____________。

3.單鏈表中，邏輯上相鄰的元素的物理位置__________緊鄰。

4.數(shù)據(jù)元素在計(jì)算機(jī)中有兩種不同的存儲(chǔ)結(jié)構(gòu)即__________。

5.程序段for(i=1;i<=n;i++)for(j=i;j<=n;j++)k++中k++執(zhí)行的頻度是______________。設(shè)問題規(guī)模為n，算法1和算法2的基本語句執(zhí)行的頻度分別為f(n)、g(n)，用戶從n=1測(cè)試到n=103

，發(fā)現(xiàn)f(n)<g(n)總成立，請(qǐng)問：算法1的時(shí)間復(fù)雜度小于算法2的時(shí)間復(fù)雜度嗎？說明理由。鄭州大學(xué)歷年試題選（第一章續(xù)）（2004）一個(gè)算法的基本語句執(zhí)行的頻度如下：，其中n是問題的規(guī)模，試計(jì)算該算法的時(shí)間復(fù)雜度。

（2007）設(shè)n為3的倍數(shù)，試分析程序段中帶“＊”語句的執(zhí)行頻度

for(i=