數(shù)據(jù)結(jié)構(gòu)c語言描述習(xí)題及答案耿國(guó)華

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

2、類型是原子類型。三、計(jì)算下列程序段中X=X1的語句頻度f(i=1i=ni)f(j=1j=ij)f(k=1k=jk)x=x1[提示]：i=1時(shí)：1=(11)12=(112)2i=2時(shí)：12=(12)22=(222)2i=3時(shí)：123=(13)32=(332)2…i=n時(shí)：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ù)和整個(gè)算法的時(shí)間復(fù)雜度，要求時(shí)間復(fù)雜度盡可能小，規(guī)定算法中不能使用求冪函數(shù)。注意：本題中的輸入為ai(i=01…n)、x和n輸出為Pn(x0)。算法的輸入和輸出采用下列方法（1）通過參數(shù)表中的參

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