全國(guó)計(jì)算機(jī)等級(jí)考試二級(jí)公共基礎(chǔ)知識(shí)總結(jié)

第一章數(shù)據(jù)結(jié)構(gòu)與算法

1.1 算法

1．算法的基本特征：可行性；確定性，有窮性；擁有足夠的情報(bào)。，

2．確定性：算法中每一步驟都必須有明確定義，不充許有模棱兩可的解釋，不允許有多義性；

3．算法基本設(shè)計(jì)方法：列舉法、歸納法、遞推、遞歸、減斗遞推技術(shù)、回溯法。

4

的設(shè)計(jì)方法。

5．算法時(shí)間復(fù)雜度是指執(zhí)行算法所需要的計(jì)算工作量。可以用算法在執(zhí)行過程中所需基本運(yùn)算的執(zhí)行次數(shù)來(lái)度量算法的工作量。

6．算法時(shí)間復(fù)雜度取決于問題的規(guī)模和待處理的數(shù)據(jù)的初態(tài)。

7．如果算法P調(diào)用另一個(gè)算法Q，而算法Q又調(diào)用算法P，

8．工程上常用的分治法是減半遞推技術(shù)

9

10．如果查找的x一定在數(shù)組中，此時(shí)q=1，則A(n)=(n+1)/2。也就是說(shuō)，在這種情況下，用順序搜索法在長(zhǎng)度為n的一維數(shù)組中查找值為x的元素，在平均的情況下需要檢查數(shù)組中一半的元素。如果已知需要查找的x有一半機(jī)會(huì)在數(shù)組中，此時(shí)q=1/2。則A(n)=[(n+1)/4]+n/2=3n/4。x不在數(shù)組中時(shí)，A(n)=n。.

11．下面程序段的時(shí)間復(fù)雜度是

for(int i=0;i

for(int j=1;j<=m;j++)

A[i][j]=0;

語(yǔ)句的頻度指的是該語(yǔ)句重復(fù)執(zhí)行的次數(shù)，一個(gè)算法中所有語(yǔ)句的頻度之和構(gòu)成了該算法的運(yùn)行時(shí)間。本例中語(yǔ)句:A[i][j]=0;的頻度是n*m，所以該程序段的時(shí)間復(fù)雜度是：O(m*n).

12

13．一個(gè)遞歸的定義可以用遞歸過程求解，也可以用非遞歸過程求解，但單從運(yùn)行時(shí)間來(lái)看，通常遞歸過程比非遞歸過程較慢。

14

1.2 數(shù)據(jù)結(jié)構(gòu)的基本基本概念

1．數(shù)據(jù)結(jié)構(gòu)研究的三個(gè)方面：；數(shù)據(jù)運(yùn)算。

2

．邏輯結(jié)構(gòu)是數(shù)據(jù)元素間關(guān)系的描述，與所用的計(jì)算機(jī)無(wú)關(guān)

3．數(shù)據(jù)的邏輯關(guān)系是指數(shù)據(jù)元素的關(guān)聯(lián)。

4．數(shù)據(jù)的不可分割的基本單位是數(shù)據(jù)項(xiàng)。

5

總結(jié)

以上是生活随笔為你收集整理的计算机二级考试基础知识总结,全国计算机等级考试二级公共基础知识总结的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。