《數(shù)據(jù)結(jié)構(gòu)——c語言描述》習題及答案-耿國華

1、第1章緒論習題一、問答題1.什么是數(shù)據(jù)結(jié)構(gòu)？2.四類基本數(shù)據(jù)結(jié)構(gòu)的名稱與含義。3.算法的定義與特性。4.算法的時間復雜度。5.數(shù)據(jù)類型的概念。6.線性結(jié)構(gòu)與非線性結(jié)構(gòu)的差別。7.面向?qū)ο蟪绦蛟O計語言的特點。8.在面向?qū)ο蟪绦蛟O計中，類的作用是什么？9.參數(shù)傳遞的主要方式及特點。10.抽象數(shù)據(jù)類型的概念。二、判斷題1.線性結(jié)構(gòu)只能用順序結(jié)構(gòu)來存放，非線性結(jié)構(gòu)只能用非順序結(jié)構(gòu)來存放。2.算法就是程序。3.在高級語言（如C、或PAL）中，指針

2、類型是原子類型。三、計算下列程序段中X=X1的語句頻度f(i=1i=ni)f(j=1j=ij)f(k=1k=jk)x=x1[提示]：i=1時：1=(11)12=(112)2i=2時：12=(12)22=(222)2i=3時：123=(13)32=(332)2…i=n時：123……n=(1n)n2=(nn2)2f(n)=[(123……n)(122232……n2)]2=[(1n)n2n(n1)(2n1)6]2f(i=1i=ni)f(j=1j

3、=ij)f(k=1k=jk)x=x1【解答】x=x1的語句頻度為：T(n)=1(12)（123）……（12……n）=n(n1)(n2)61.4試編寫算法，求pn(x)=a0a1xa2x2…….anxn的值pn(x0)并確定算法中每一語句的執(zhí)行次數(shù)和整個算法的時間復雜度，要求時間復雜度盡可能小，規(guī)定算法中不能使用求冪函數(shù)。注意：本題中的輸入為ai(i=01…n)、x和n輸出為Pn(x0)。算法的輸入和輸出采用下列方法（1）通過參數(shù)表中的參

4、數(shù)顯式傳遞（2）通過全局變量隱式傳遞。討論兩種方法的優(yōu)缺點，并在算法中以你認為較好的一種實現(xiàn)輸入輸出?！窘獯稹浚?）通過參數(shù)表中的參數(shù)顯式傳遞優(yōu)點：當沒有調(diào)用函數(shù)時，不占用內(nèi)存，調(diào)用結(jié)束后形參被釋放，實參維持，函數(shù)通用性強，移置性強。缺點：形參須與實參對應，且返回值數(shù)量有限。（2）通過全局變量隱式傳遞優(yōu)點：減少實參與形參的個數(shù)，從而減少內(nèi)存空間以及傳遞數(shù)據(jù)時的時間消耗缺點：函數(shù)通用性降低，移植性差算法如下：通過全局變量隱式傳遞參數(shù)Pol