數(shù)據(jù)結(jié)構(gòu)習(xí)題(含答案)

1、1第一章第一章緒論緒論一、填空題一、填空題1數(shù)據(jù)是描述客觀事物的數(shù)、字符以及所有能輸入到計(jì)算機(jī)且能夠被計(jì)算機(jī)程序加工處理的符號(hào)集合。_________是數(shù)據(jù)的基本單位；___________是數(shù)據(jù)的最小單位。通常被計(jì)算機(jī)加工處理的數(shù)據(jù)不是孤立無關(guān)的，而是彼此之間存在著某種聯(lián)系，將這種數(shù)據(jù)間的聯(lián)系稱為________。2數(shù)據(jù)結(jié)構(gòu)進(jìn)行形式化定義時(shí)，可以從邏輯上認(rèn)為數(shù)據(jù)結(jié)構(gòu)DS是_________的集合D和D上_________的集合R所構(gòu)成

2、的二元組：DS=（D，R）。3已知某數(shù)據(jù)結(jié)構(gòu)的二元組形式表示為：A=(D，R)，D=01，02，03，04，05，06，07，08，09，R=r，r=，，，，，，，。則此數(shù)據(jù)結(jié)構(gòu)屬于_____________結(jié)構(gòu)。4一個(gè)算法的時(shí)間復(fù)雜度通常用問題規(guī)模大小的函數(shù)來表示，當(dāng)一個(gè)算法的時(shí)間復(fù)雜度與問題規(guī)模n大小無關(guān)時(shí)，則表示為__________；成正比關(guān)系時(shí)，則表示為___________；成對數(shù)關(guān)系時(shí)，則表示為___________；成平

3、方關(guān)系時(shí)，則表示為__________。5數(shù)據(jù)結(jié)構(gòu)的邏輯結(jié)構(gòu)包括_____________、樹型結(jié)構(gòu)和圖型結(jié)構(gòu)三種類型，其中樹型結(jié)構(gòu)和圖型結(jié)構(gòu)合稱為_____________；數(shù)據(jù)結(jié)構(gòu)的存儲(chǔ)結(jié)構(gòu)主要包括____________和____________兩種類型。6線性結(jié)構(gòu)的特點(diǎn)是：第一個(gè)結(jié)點(diǎn)_______前驅(qū)結(jié)點(diǎn)，其余結(jié)點(diǎn)有且僅有_______個(gè)前驅(qū)結(jié)點(diǎn)；最后一個(gè)結(jié)點(diǎn)_______后繼結(jié)點(diǎn)，其余每個(gè)結(jié)點(diǎn)有且僅有_______個(gè)后繼結(jié)點(diǎn)。

4、7樹型結(jié)構(gòu)的特點(diǎn)是：根結(jié)點(diǎn)沒有________結(jié)點(diǎn)，其余每個(gè)結(jié)點(diǎn)有且僅有________個(gè)前驅(qū)結(jié)點(diǎn)；葉子結(jié)點(diǎn)_________后繼結(jié)點(diǎn)，其余結(jié)點(diǎn)可以有_________個(gè)后繼結(jié)點(diǎn)。8圖型結(jié)構(gòu)的特點(diǎn)是：每個(gè)結(jié)點(diǎn)可以有_________個(gè)前驅(qū)結(jié)點(diǎn)和后繼結(jié)點(diǎn)。9程序段f（i=1，s=0；s，，，，，，。2.B=（K，R），其中：K=a，b，c，d，e，f，g，h，R=r，r=，，，，，，。3.C=（K，R），其中：K=a，b，c，d，e，R=

5、r，r=，，，，，，。4.D=（K，R），其中：K=48，25，64，57，82，36，75，R=r1，r2，r1=，，，，，；r2=，，，，，。5.E=（K，R），其中：K=1，2，3，4，5，6，7，R=r，r=，，，，，，，，，。三、指出下列各函數(shù)的功能并求出其時(shí)間復(fù)雜度。三、指出下列各函數(shù)的功能并求出其時(shí)間復(fù)雜度。1.voidprime(intn)intif(i=2isqrt(n))printf(“yes”)elseprintf

6、(“no”)3第一章參考答案第一章參考答案一、填空題一、填空題1數(shù)據(jù)元素，數(shù)據(jù)項(xiàng)，結(jié)構(gòu)2數(shù)據(jù)，關(guān)系3樹型4O(1)，O(n)，O(log2n)，O(n2)5線性結(jié)構(gòu)，非線性結(jié)構(gòu)，順序結(jié)構(gòu)，鏈?zhǔn)浇Y(jié)構(gòu)6無，一，無，一7前驅(qū)，一，無，任意8任意9O(n12)分析：設(shè)程序段中的循環(huán)體執(zhí)行k次，則有不等式成立，解此不等式得到不等式???????111kikiini，因此。2141223412??????nkn)()(nOknf??10O(1)和這

7、兩個(gè)有序偶對用一個(gè)無序偶對(x，y)或(y，x)來代替。在用圖形表示時(shí)，我們把x結(jié)點(diǎn)和y結(jié)點(diǎn)之間兩條相反的弧用一條無向邊來代替。三、指出下列各函數(shù)的功能并求出其時(shí)間復(fù)雜度。三、指出下列各函數(shù)的功能并求出其時(shí)間復(fù)雜度。1函數(shù)的功能是判斷n是否是一個(gè)素?cái)?shù)，其時(shí)間復(fù)雜度為O(n12)。分析：函數(shù)prime中出現(xiàn)的庫函數(shù)sqrt為平方根函數(shù)，因此。)(1)(nOnnf???2函數(shù)的計(jì)算的值，其時(shí)間復(fù)雜度為O(n2)。??nii1!3函數(shù)的計(jì)算的