數(shù)據(jù)結(jié)構(gòu)習(xí)題集new

1、數(shù) 據(jù) 結(jié) 構(gòu) 習(xí) 題 冊(cè)（僅供計(jì)算機(jī)和信息專業(yè)同學(xué)參考）基礎(chǔ)篇習(xí)題1一、選擇題1 計(jì)算機(jī)算法必須具備輸入、輸出、（）等5個(gè)特性。A 可行性、可移植性和可擴(kuò)展性 B 可行性、確定性和有窮性C 確定性、有窮性和穩(wěn)定性 D 易讀性、安全性和穩(wěn)定性2 在數(shù)據(jù)結(jié)構(gòu)中，從邏輯上可以把數(shù)據(jù)結(jié)構(gòu)分為（ ）A 動(dòng)態(tài)結(jié)構(gòu)和靜態(tài)結(jié)構(gòu) B 緊湊結(jié)構(gòu)和非緊湊結(jié)構(gòu)C 內(nèi)容結(jié)構(gòu)和外部結(jié)構(gòu) D 線性結(jié)構(gòu)和非線性結(jié)構(gòu)3 下面程序段的時(shí)間復(fù)雜性的量級(jí)為（ ）For (i=1;i=n;i+) For(j=1;j=I;j+) For(k=1;k=j;k+) x=x+1;A O(1) B O(n) C O(n2) D O(n3)4

2、在數(shù)據(jù)結(jié)構(gòu)中，與所使用的計(jì)算機(jī)無關(guān)的是數(shù)據(jù)的（ ）結(jié)構(gòu)A 邏輯 B 存儲(chǔ) C 邏輯和存儲(chǔ) D 物理5 數(shù)據(jù)結(jié)構(gòu)在計(jì)算機(jī)中的表示是指（ ）A 數(shù)據(jù)的邏輯結(jié)構(gòu) B 數(shù)據(jù)結(jié)構(gòu) C 數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu) D 數(shù)據(jù)元素之間的關(guān)系6 下面（ ）的時(shí)間復(fù)雜性最好，即執(zhí)行時(shí)間最短。A O(n) B O(logn) C O(nlogn) D O(n2)7 下面程序段的時(shí)間復(fù)雜性的量級(jí)為（ ）。Int fun(int n)I=1,s=1;While(sn)s+=+I;return I;A O(n/2) B O(logn) C O(n) D O(n1/2)8 下面程序段的時(shí)間復(fù)雜性的量級(jí)為（ ）。For(int i=0;

3、im;i+)For(int j=0;jn;j+) Aij=i*j;A O(m3) B O(n2) C O(m*n) D O(m+n)9 執(zhí)行下面程序段時(shí)，S 語句的執(zhí)行次數(shù)為（ ）。 For(int i=1;in-1;i+)For(int j=i+1;j=n;j+) S;A n(n-1)/2 B n2/2 C n(n-1)/2 D n二、簡(jiǎn)答題1 數(shù)據(jù)的邏輯結(jié)構(gòu)有哪幾種？常用的存儲(chǔ)有哪幾種？2 舉一個(gè)數(shù)據(jù)結(jié)構(gòu)的例子，敘述其邏輯結(jié)構(gòu)、存儲(chǔ)結(jié)構(gòu)和運(yùn)算三方面的內(nèi)容。3 什么叫算法？它有哪些特性4 有下列幾種用二元組表示的數(shù)據(jù)結(jié)構(gòu)，畫出它們分別對(duì)應(yīng)的邏輯結(jié)構(gòu)圖，并指出它們分別以屬于何種結(jié)構(gòu)。（1）A=

4、(K,R),其中 K=a,b,c,d,e,f,g,h R=r r=,(2) B=(K,R),其中 Ka,b,c,d,e,f,g,h R=r r=,(3) B=(K,R),其中 K=1,2,3,4,5,6 R=r r=(1,2),(2,3),(2,4),(3,4),(3,5),(3,6),(4,5),(4,6)三、計(jì)算題設(shè)n為整數(shù)，求下列各程序段的時(shí)間復(fù)雜度（1）i=1;k=2;While(in) k=k+10*I; i=i+1;(2)i=1;j=0; While(i+jj)j=j+1;Else i=i+1;(3)x=91;y=100 While(y0) If(x100) x=x-10; y=y

5、-1; else x=x+1;習(xí)題2一、選擇題1 線性表是（ ）A 一個(gè)有限序列，可以為空 B 一個(gè)有限序列，不能為空C 一個(gè)無限序列，可以為空 D 一個(gè)無限序列，不能為空2 在一個(gè)長(zhǎng)度為n的順序表中，向第iI個(gè)元素（1in+1）位置插入一個(gè)新元素時(shí)，需要從后向前依次后移（ ）個(gè)元素。A n-i B n-i+1 C n-i-1 D i3 在一個(gè)順序表的表尾插入一個(gè)元素的時(shí)間復(fù)度的量級(jí)為（ ）。A O(n) B O(1) C O(n2) D O(log n)4 表長(zhǎng)為n的順序存儲(chǔ)的線性表，當(dāng)在任意位置上插入或刪除一個(gè)元素的概率相等時(shí)，插入一個(gè)元素所需移動(dòng)元素的平均個(gè)數(shù)為（ ），刪除一個(gè)元素需要移

6、動(dòng)元素的平均個(gè)數(shù)為（ ）A (n-1)/2 B n C (n+1)/2 D n/25 設(shè)單鏈表中指針p指向結(jié)點(diǎn)a，若要?jiǎng)h除p之后的結(jié)點(diǎn)（若存在），則需修改指針的操作為（ ）。A p-next=p-next-next B p=p-nextC p=p-next-next D next=p6 單鏈表的存儲(chǔ)密度為（ ）。A 大于1 B 等于5 C 小于1 D 不能確定7 在一個(gè)單鏈表中，若要在p所指向的結(jié)點(diǎn)之后插入一個(gè)新結(jié)點(diǎn)，則需要相繼修改（ ）個(gè)指針域的值。A 1 B 2 C 3 D 48 在一個(gè)單鏈表中，若要在p所指向的結(jié)點(diǎn)之前插入一個(gè)新結(jié)點(diǎn)，則此算法的時(shí)間復(fù)雜度的量級(jí)為（ ）。A O(n) B

7、O(n/2) C O(1) D O(n1/2)9 在一個(gè)帶頭結(jié)點(diǎn)的雙向循環(huán)鏈表中，若要在p所指向的結(jié)點(diǎn)之前插入一個(gè)新結(jié)點(diǎn)，則需要相繼修改（ ）個(gè)指針域的值。A 2 B 3 C 4 D 6二、簡(jiǎn)答題1 什么叫線性表？它有哪些特點(diǎn)？2 在鏈表的設(shè)計(jì)中，為什么通常采用帶頭結(jié)點(diǎn)的鏈表結(jié)構(gòu)？3 對(duì)比順序表與單鏈表，說明順序表與單鏈表的主要優(yōu)點(diǎn)和主要缺點(diǎn)。4 試編寫算法實(shí)現(xiàn)順序表的逆置，即把順序表A中的數(shù)據(jù)元素（a1,a2, ,an）逆置為（an,an-1, ,a1）。5 已知A和B為兩個(gè)非遞減的線性表，現(xiàn)要求實(shí)現(xiàn)如下操作：從A中刪除在B中出現(xiàn)的元素。試編寫在順序表中實(shí)現(xiàn)上述操作的算法。6 試編寫算法實(shí)現(xiàn)

8、鏈表的就地逆置(不增加存儲(chǔ)空間)，即把鏈表A中的數(shù)據(jù)元素（a1,a2, ,an）逆置為（an,an-1, ,a1）。7 假設(shè)有兩個(gè)非遞減的線性表A 和B，均采用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)，試編寫算法將A和B 歸并成一個(gè)按元素非遞減的線性表C。8 試編寫算法求單循環(huán)鏈表的表長(zhǎng)。習(xí)題3一、選擇題 1在棧頂一端可進(jìn)行的全部操作是（ ）。A 插入 B 刪除 C插入和刪除 D進(jìn)棧2 棧的特點(diǎn)是（ ）。A 先進(jìn)先出 B 后進(jìn)先出 C后進(jìn)后出 D不進(jìn)不出3 順序棧是空棧的條件是（ ）。A top=0 B top=1 C top=-1 D top=m4 假定利用數(shù)組AN順序存儲(chǔ)一個(gè)棧，top表示棧頂指針，已知棧未滿，則x入

9、棧時(shí)所執(zhí)行的操作是（ ）。A a-top=x; B atop-=x C a+top=x D atop+=x5 一個(gè)棧的入棧序列是a,b,c,d,e，則不可能的出棧序列是（ ）。A edcda B dceab C decba D abcde6 經(jīng)過下列棧的運(yùn)算后EmptyStack(s)的值是（ ）。InitStack(s);Push(s,a);Push(s,b);Pop(s,x);Pop(s,x) ;A a B b C 1 D 07 若已知一個(gè)棧的入棧序列是1,2,3, ,n，其輸出序列為p1,p2,p3,pn，若p1=n,則pi為（ ）。A i B n-i C n-i+1 D 不確定8 隊(duì)列

10、的特點(diǎn)是（）。A 先進(jìn)先出 B 后進(jìn)先出 C先進(jìn)后出 D 不進(jìn)不出9 循環(huán)隊(duì)列S為滿的條件是（）。A S-rear=S-frontB S-rear+1)%maxsiae=s-frontC S-rear=0D s-front=010 經(jīng)過下列運(yùn)算后GetHead(Q)的值是（）。InitQueue(Q); EnQueue(Q,a); EnQueue(Q,b); DeQueue(Q,x);A a B b C 1 D 2二、簡(jiǎn)答題1 簡(jiǎn)述棧與隊(duì)列的相同點(diǎn)與不同點(diǎn)。2 在順序隊(duì)列中，什么叫真溢出？什么叫假溢出？為什么順序隊(duì)列常都采用循環(huán)隊(duì)列結(jié)構(gòu)？3 設(shè)以帶頭結(jié)點(diǎn)的循環(huán)鏈表表示隊(duì)列，并且只設(shè)一個(gè)指針指向

11、隊(duì)尾元素結(jié)點(diǎn)（不設(shè)頭指針），試編寫相應(yīng)的入隊(duì)列、出隊(duì)列算法。4 設(shè)計(jì)一個(gè)輸出如下形式數(shù)值的遞歸算法。4 4 4 43 3 32 215 編寫一個(gè)算法，利用棧的基本運(yùn)算返回指定棧中的棧底元素。習(xí)題4一、選擇題1 串是一種特殊的線性表，其特殊性體現(xiàn)在（ ）A 唯一可以順序存儲(chǔ) B 數(shù)據(jù)元素是一個(gè)字符C 可以鏈接存儲(chǔ) D 數(shù)據(jù)元素可以是多個(gè)字符2 下面（ ）是C語言中“abcd321ABCD”的子串。A abcd B 321AB C “abcAB” D “21AB”3 設(shè)有兩個(gè)串p和q，求p和q首次出現(xiàn)的位置的運(yùn)算稱作( )A 連接 B 模式匹配 C 求子串 D 求串長(zhǎng)4 設(shè)有一個(gè)字符串S=“win

12、dows”，求子串的數(shù)目是（）A 25 B 26 C 27 D 28二、簡(jiǎn)答題1 空串與空格串有什么區(qū)別？字符串中的空格有什么意思？空串在串的處理中有什么作用？2串是由字符組成的，長(zhǎng)度為1的串和字符是否相同？為什么？3簡(jiǎn)述串的靜態(tài)順序存儲(chǔ)結(jié)構(gòu)與動(dòng)態(tài)順序存儲(chǔ)結(jié)構(gòu)有什么區(qū)別，分別寫出它們的結(jié)構(gòu)體定義。4字符串采用靜態(tài)順序存儲(chǔ)結(jié)構(gòu)。編寫一個(gè)算法刪除S中地i個(gè)字符到第j個(gè)字符。5編寫一個(gè)算法判斷s2是否是s1的子串。習(xí)題5一、選擇題1二維數(shù)組A行下標(biāo)i的范圍從1到12，列下標(biāo)j的范圍從3到10，采用行序?yàn)橹餍虼鎯?chǔ)，每個(gè)數(shù)據(jù)元素占用4個(gè)存儲(chǔ)單元，該數(shù)組的首地址（即A13的地址）為1200，則A65的地址

13、為（ ）。A 1400 B 1404 C 1372 D 13682二維數(shù)組M的元素是4個(gè)字符（每個(gè)字符占一個(gè)存儲(chǔ)單元）組成的串，行下標(biāo)i的范圍從0到4，列下標(biāo)j的范圍從0到5，M按行存儲(chǔ)時(shí)元素M35的起始地址與M按列存儲(chǔ)時(shí)元素（ ）的起始地址相同。A M24 B M34 C M35 D M 443數(shù)組A中，每個(gè)元素A的長(zhǎng)度為3個(gè)字節(jié)，行下標(biāo)i從1到5，列下標(biāo)j從1到6，從首地址開始連續(xù)存放在存儲(chǔ)器內(nèi)，存放該數(shù)組至少需要的單元數(shù)是（ ）。A 90 B 70 C 50 D 304設(shè)有10階矩陣A，其對(duì)角線以上的元素aij均取值為-3，其他矩陣元素為正整數(shù)，現(xiàn)在將矩陣A壓縮存放在一維樹組Fm中，則

14、m為（ ）。A 45 B 46 C 55 D 565若廣義表A滿足head(A)=tail(A),則A為（ ）。A （ ） B （） C （），（） D （），（），（）6遞歸函數(shù)f(n)=f(n-1)+n(n1)的遞歸出口是（ ）A f(1)=0 B f(1)=1 C f(0)=1 D f(n)=n二、簡(jiǎn)答題1什么叫二維數(shù)組的行序優(yōu)先存儲(chǔ)？什么叫二維數(shù)組的列序優(yōu)先存儲(chǔ)？2什么樣的矩陣叫特殊矩陣？特殊矩陣壓縮存儲(chǔ)的基本思想是什么？3什么樣的矩陣叫稀疏矩陣？稀疏矩陣壓縮存儲(chǔ)的基本思想是什么？三、計(jì)算題設(shè)有二維數(shù)組A（6*8），每個(gè)元素占4個(gè)字節(jié)，A00的起始地址為1000，計(jì)算（1） 數(shù)組A共占

15、多少個(gè)字節(jié)；（2） 數(shù)組的最后一個(gè)元素A57的起始地址；（3） 按行優(yōu)先存放時(shí)，元素A14的起始地址；（4） 按列優(yōu)先存放時(shí)，元素A47的起始地址；四、設(shè)計(jì)題1對(duì)于二維數(shù)組Amn，其中m=80，nleft=NULL B、t-ltag=1 C、t-ltag=1且t-left=NULL D、以上都不對(duì)5、設(shè)高度為h的二叉數(shù)上只有度為0和度為2的結(jié)點(diǎn)，則此類二叉樹中所包含的結(jié)點(diǎn)數(shù)至少為（ ）A、2h B、2h -1 C、2h +1 D、h+1 6、已知某二叉樹的后序遍歷序列是dabec，中序遍歷序列是debac，它的前序遍歷序列是（ ）A、acbed B、 decab C、 deabc D 、ced

16、ba7、按照二叉樹的定義，具有三個(gè)節(jié)點(diǎn)的二叉樹有（ ）種A、3 B、4 C、5 D、68、任意一棵二叉樹的葉結(jié)點(diǎn)在先序、中序和后序遍歷序列中的相對(duì)次序（ ）A、不發(fā)生改變 B、發(fā)生改變 C、不能確定 D、以上都不對(duì)9、對(duì)一個(gè)滿二叉樹，它有m個(gè)樹葉，n個(gè)結(jié)點(diǎn)，深度為h，則（）A、n=h+m B 、h+m=2n C、m=h-1 D 、n=2h-1二、設(shè)計(jì)題1、已知一棵樹的邊的集合表示為（L,N）,（G,K）,（G,1）,（G,M）,（B,E）,（B,F）,（D,G）,（D,H）,（D,I）,（D,J）,（A,B）,（A,C）,（A,D）。畫出這棵樹并回答下面問題：（1） 樹的根節(jié)點(diǎn)是哪個(gè)，哪些是葉

17、子結(jié)點(diǎn)，哪些是非終端結(jié)點(diǎn)。（2） 樹的深度是多少，各個(gè)結(jié)點(diǎn)的層數(shù)是多少。（3） 對(duì)于G結(jié)點(diǎn)，它的雙親結(jié)點(diǎn)、祖先結(jié)點(diǎn)、孩子結(jié)點(diǎn)、子孫結(jié)點(diǎn)、兄弟和堂兄弟分別是哪些結(jié)點(diǎn)。2、給定二叉樹的先序序列和中序序列，能否重構(gòu)出該二叉樹？給定二叉樹的先序序列和后序序列呢？若不能，給出反例。3、一棵深度為h的滿二叉樹具有如下性質(zhì)：第h層上的結(jié)點(diǎn)都是葉結(jié)點(diǎn)，其余各層上每個(gè)結(jié)點(diǎn)都有m棵非空子樹。若按層次從上到下，每層從左到右的順序從1開始對(duì)全部結(jié)點(diǎn)編號(hào)，試計(jì)算： （1）第k層結(jié)點(diǎn)數(shù)（1kh）。（2）整棵樹結(jié)點(diǎn)數(shù)（3）編號(hào)為i的結(jié)點(diǎn)的雙親結(jié)點(diǎn)的編號(hào)（4）編號(hào)為i的結(jié)點(diǎn)的第j個(gè)孩子結(jié)點(diǎn)（若有）的編號(hào)4、若7個(gè)帶權(quán)結(jié)點(diǎn)，其

18、權(quán)值分別為3，7，8，2，6，10，14，試以它們?yōu)槿~結(jié)點(diǎn)構(gòu)造一棵哈夫曼樹（請(qǐng)按照每個(gè)結(jié)點(diǎn)的左子樹根結(jié)點(diǎn)的權(quán)小于等于右子樹根結(jié)點(diǎn)的權(quán)的次序構(gòu)造），度計(jì)算出帶權(quán)路徑長(zhǎng)度WPL及該樹的結(jié)點(diǎn)總數(shù)。5、假設(shè)二叉數(shù)采用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)，編寫一個(gè)算法釋放該二叉樹所占用的全部結(jié)點(diǎn)。6、編寫一個(gè)計(jì)算一棵二叉樹T的高度算法。7、二叉樹采用二叉樹鏈表的結(jié)構(gòu)存儲(chǔ)，設(shè)計(jì)一個(gè)算法求二叉樹中指定結(jié)點(diǎn)的層數(shù)。習(xí)題7一、選擇題 1、 在一個(gè)具有n個(gè)頂點(diǎn)的無向圖中，要連接全部頂點(diǎn)至少需要（ ）條邊。A、n B、n1 C、n1 D、n/22、對(duì)于一個(gè)具有n個(gè)頂點(diǎn)的無向圖，若采用鄰接矩陣表示，則該矩陣的大小是（ ） A、n B、(n-

19、1)/2 C、n-1 D、n23、具有6個(gè)頂點(diǎn)的無向圖至少應(yīng)用（ ）條邊才能確保是一個(gè)連通圖。 A、5 B、6 C、7 D、84、n個(gè)頂點(diǎn)的強(qiáng)連通圖的鄰接矩陣中至少有（ ）個(gè)非零元素。 A、n-1 B、n C、2n-2 D、2n5、在一個(gè)具有n個(gè)頂點(diǎn)的有向完全圖中，所含的邊數(shù)為（ ） A、n B、n(n-1) C、n(n-1)/2 D、n(n+1)/26、在一個(gè)具有n個(gè)頂點(diǎn)和e條邊的無向圖的鄰接矩陣中，表示邊存在的元素（又稱為有效元素）的個(gè)數(shù)為（ ）。 A、n B、ne C、e D、2e7、在一個(gè)具有n個(gè)頂點(diǎn)和e條邊的有向圖的鄰接表中，保存頂點(diǎn)單鏈接的表頭指針向量大小至少為（ ） A、n B、

20、2n C、e D、2e8、在一個(gè)具有n個(gè)頂點(diǎn)和e條邊的無向圖的鄰接表中，邊結(jié)點(diǎn)的個(gè)數(shù)為（ ）。 A、n B、ne C、e D、e9、對(duì)于一個(gè)有向圖，若一個(gè)頂點(diǎn)的度為k1，出度為k2，則對(duì)應(yīng)逆鄰接表中該頂點(diǎn)單鏈表中的邊結(jié)點(diǎn)數(shù)為（ ） A、k1 B、k2 C、k1-k2 D、k1+k210、采用鄰接表存儲(chǔ)的圖的深度優(yōu)先遍歷算法類似于二叉樹的（ ） A、接層遍歷 B、中序遍歷 C、先序遍歷 D、后序遍歷 11、無向圖G（V，A），其中Va,b,c,d,e,A=,對(duì)該圖進(jìn)行撲拓排序，下面序列中（ ）不是拓?fù)湫蛄小?A、adcbe B、dabce C、abdce D、abcde12、G是一個(gè)非連通無向圖

21、，共有28條邊，則該圖至少有（ ）個(gè)頂點(diǎn)。 A、7 B、8 C、9 D、10二、簡(jiǎn)答題1、 對(duì)于一個(gè)有向圖，不用拓?fù)渑判?，如何判定圖中是否存在環(huán)？2、 用鄰接矩陣表示圖時(shí)，矩陣元素的個(gè)數(shù)與頂點(diǎn)個(gè)數(shù)是否相關(guān)？與邊數(shù)是否相關(guān)？習(xí)題8一、選擇題 1、 若查找每個(gè)記錄的概率均等，則在具有n個(gè)記錄的連續(xù)順序文件中采用順序查找法查找一個(gè)記錄，其平均查找長(zhǎng)度ASL為（ ） A、（n-1）/2 B、n/2 C、(n+1)/2 D、n2、下面關(guān)于二分查找敘述正確的是（ ） A、表必須有序，表可以順序方式存儲(chǔ)，也可以鏈表方式存儲(chǔ)B、表必須有序且表中數(shù)據(jù)必須是整型，實(shí)型或字符型C、表必須有序，而且只能從小到大排序D

22、、表必須有序，且表只能以順序方式存儲(chǔ)3、當(dāng)在一個(gè)有序的順序存儲(chǔ)表上查找一個(gè)數(shù)據(jù)時(shí)，既可用折半查找，也可用順序查找，但前者比后者的查找速度（ ） A、必定快 B、不一定 C、在大部分情況下要快 D、取決于表遞增還是遞減4、具有12個(gè)關(guān)鍵字的有序表，折半查找的平均查找長(zhǎng)度為（ ） A、3.1 B、4 C、2.5 D、55、當(dāng)采用分塊查找時(shí)，數(shù)據(jù)的組織方式為（ ）A、數(shù)據(jù)分成若干塊，每塊內(nèi)數(shù)據(jù)有序B、數(shù)據(jù)分成若干塊，每塊內(nèi)數(shù)據(jù)不必有序，但塊間必須有序C、數(shù)據(jù)分成若干塊，每塊內(nèi)數(shù)據(jù)有序，每塊內(nèi)最大（或最?。┑臄?shù)據(jù)組成索引塊D、數(shù)據(jù)分成若干塊，每塊（除最后一塊外）中數(shù)據(jù)個(gè)數(shù)需相同6、既希望查找速度快又便

23、于線性表動(dòng)態(tài)變化的查找方法有（）A、順序查找 B、折半查找 C、索引順序查找 D、哈希法查找7、分別以下序列構(gòu)造二叉排序樹，與用其他三個(gè)序列所構(gòu)造的結(jié)果不同的是（ ）A、（100，80，90，60，120，110，130） B、（100，120，110，130，80，60，90）C、（100，60，80，90，120，110，130） D、（100，80，60，90，120，130，110）二、簡(jiǎn)答題1、 什么叫動(dòng)態(tài)查找？什么叫靜態(tài)查找？什么樣的存儲(chǔ)結(jié)構(gòu)適宜于進(jìn)行靜態(tài)查找？什么樣的存儲(chǔ)結(jié)構(gòu)適宜于進(jìn)行動(dòng)態(tài)查找？2、 什么叫平均查找長(zhǎng)度？寫出平均查找長(zhǎng)度的定義三、設(shè)計(jì)題 1、 已知一個(gè)個(gè)數(shù)為12的

24、數(shù)據(jù)元素序列為Dec,Feb,Nov,Oct,June,Sept,Aug,Apr,May,July,Jan,Mar，要求（注意字母的大小是指字母的ASCII碼數(shù)值大?。海?） 按各數(shù)據(jù)元素的順序構(gòu)造一棵二叉排序樹（2） 設(shè)各數(shù)據(jù)元素的查找概率相等，給出該二叉排序樹的平均查找長(zhǎng)度。2、 設(shè)有數(shù)據(jù)元素序列11，23，35，47，51，60，75，88，90，102，113，126，用除留余數(shù)法構(gòu)造哈希表，要求：（1） 設(shè)計(jì)哈希表的長(zhǎng)度取值為m;（2） 畫出用開放定址法的線性探查法解決哈希沖突的哈希表結(jié)構(gòu)；（3） 畫出用鏈表法解決哈希沖突的哈希表結(jié)構(gòu)。習(xí)題9一、選擇題 1、設(shè)有1000個(gè)無序的元素

25、，希望用最快的速度挑出其中前10個(gè)最大的元素，最好（ ）排序法。A、起泡排序 B、選擇排序 C、堆排序 D、希爾排序2、在待排序的元素序列基本有序的前提下，效率最高的排序方法是（ ）A、插入排序 B、選擇排序 C、快速排序 D、希爾排序3、一組記錄排序碼為（46，79，56，38，40，84），則利用堆排序的方法建立的初始堆為（ ）A、79，46，56，38，40，80 B、84，79，56，38，40，46C、84，79，56，46，40，38 D、84，56，79，40，46，384、排序方法中，從未排序序列中依次取出元素與已排序序列（初始時(shí)為空）中的元素進(jìn)行比較，將其放入已排序序列的正確

26、位置上的方法，稱為（ ）A、希爾排序 B、起泡排序 C、插入排序 D、選擇排序5、下述幾種排序方法中，要求內(nèi)存量最大的是（ ）A、插入排序 B、選擇排序 C、快速排序 D、歸并排序6、下列四種排序方法中，不穩(wěn)定的方法是（ ）A、直接插入排序 B、冒泡排序 C、歸并排序 D、直接選擇排序二、設(shè)計(jì)題 1、對(duì)給定的j（1=j=n），要求在無序的記錄區(qū)R1n中找到按關(guān)鍵字自小到大排在第j個(gè)位置上的記錄（即在無序集合中找到第j個(gè)最小元），試?yán)每焖倥判虻膭澐炙枷刖帉懰惴▽?shí)現(xiàn)上述的查找操作。2、以單鏈表為存儲(chǔ)結(jié)構(gòu)，寫一個(gè)直接選擇排序算法。3、改寫快速排序算法，要求采用三者取中的方式選擇劃分的基準(zhǔn)記錄；若當(dāng)

27、前被排序的區(qū)間長(zhǎng)度小于等于3時(shí)，無須劃分而是直接采用直接插入方式對(duì)其排序?；A(chǔ)篇參考答案習(xí)題1參考答案一、選擇題1. B 2. D 3. D 4. A 5. C 6. B 7. D 8. C 9. A二、簡(jiǎn)答題1. 答：數(shù)據(jù)的邏輯結(jié)構(gòu)通常有四種，即集合、線性結(jié)構(gòu)、樹形結(jié)構(gòu)和圖狀結(jié)構(gòu)。存儲(chǔ)結(jié)構(gòu)主要有順序存儲(chǔ)結(jié)構(gòu)和鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)。2. 答：比如一分通訊錄，記錄了相關(guān)人員的電話號(hào)碼，將其按姓名一人占一行構(gòu)成表，這個(gè)表就是一個(gè)數(shù)據(jù)結(jié)構(gòu)。每一行是一個(gè)記錄，對(duì)于整個(gè)表來說，只有一個(gè)開始結(jié)點(diǎn)和一個(gè)終端結(jié)點(diǎn)，其它結(jié)點(diǎn)也只有一個(gè)前驅(qū)和一個(gè)后繼。這幾個(gè)關(guān)系就確定了表的邏輯結(jié)構(gòu)。3. 答：算法是對(duì)特定問題求解步驟的一

28、種描述，是指令的有限序列，其中每一條指令表示一個(gè)或多個(gè)操作。算法具有有窮性、確定性、可行性、輸入和輸出5個(gè)特性。4.答： (1) A對(duì)應(yīng)的邏輯圖形如下圖左，它是一種線性結(jié)構(gòu)。abcdefghabcdefgh(2) B對(duì)應(yīng)的邏輯圖形如上圖右所示，它是一種樹型結(jié)構(gòu)。(3) C對(duì)應(yīng)的邏輯圖形如下圖所示，它是一種圖型結(jié)構(gòu)。123465三、計(jì)算題解： (1) O(n)； (2) O(n) ； (3) O(n1/2)。 習(xí)題2參考答案一、選擇題1. A 2. B 3. B 4. D A5. A 6. C 7. B 8. A 9. C二、簡(jiǎn)答題1. 答：線性表是具有n個(gè)數(shù)據(jù)元素的一個(gè)有限序列。線性表的特點(diǎn)是

29、：數(shù)據(jù)元素之間是一對(duì)一的關(guān)系。除第一個(gè)元素外，每個(gè)元素有且只有一個(gè)直接前驅(qū)；除最后一個(gè)元素外，每個(gè)元素有且只有一個(gè)直接后繼。2. 答：頭指針是鏈表的一個(gè)標(biāo)識(shí)，它用來指向帶頭結(jié)點(diǎn)的鏈表中的頭結(jié)點(diǎn)。頭結(jié)點(diǎn)是在鏈表的第一個(gè)數(shù)據(jù)元素之前附加的一個(gè)結(jié)點(diǎn)，它的作用是使對(duì)第一個(gè)結(jié)點(diǎn)的操作和其它結(jié)點(diǎn)一致，表空與非空時(shí)處理一致，不需要特殊處理，簡(jiǎn)化了操作。3. 答：順序表的特點(diǎn)是邏輯位置相鄰的數(shù)據(jù)元素其物理位置也相鄰，因此可以進(jìn)行隨機(jī)存儲(chǔ)， 是一種隨機(jī)存儲(chǔ)結(jié)構(gòu)。其插入和刪除操作的時(shí)間復(fù)雜度均為O(n)。鏈表中的數(shù)據(jù)元素使用一組任意的存儲(chǔ)單元存儲(chǔ)，不要求邏輯位置相鄰的數(shù)據(jù)元素物理位置也相鄰，而是采用附加的指針表示

30、元素之間的邏輯關(guān)系。鏈表的插入和刪除結(jié)點(diǎn)均不需要移動(dòng)其他結(jié)點(diǎn)，但是，其查找運(yùn)算必須從頭指針開始順序查找，其時(shí)間復(fù)雜度為O(n)。4. 答：算法如下void Convert(SqList &L)int i,j,temp;j=L.length-1;i=0;while(ij)temp=L.elemi;L.elemi=L.elemj;L.elemj=temp;i+;j-;5. 答：算法如下 void Delete(SqList &La,SqList Lb)int i,j,k;i=0;j=0;while(iLa.length&jLb.length)if(La.elemiLb.elemj) j+;else

31、 ListDelete_Sq(La, i+1, k);6. 答：算法如下void InvertList(LinkList &L)LinkList p,q,r;p = L-next;q = p-next;p-next=NULL;while(q!=NULL)r=q-next;q-next=p;p=q;q=r;L-next=p;7.答：算法如下void MergeOrder(LinkList La,LinkList Lb)LinkList pa,pb,Lc,pc;pa=La-next;pb=Lb-next;Lc=pc=La;while (pa&pb)if(pa-data data )pc-next=

32、pa;pc=pa;pa=pa-next;elsepc-next=pb;pc=pb;pb=pb-next;if (!pa) pc-next=pb;else pc-next=pa;8.答：算法如下int Length(LinkList L)int i=0;LinkList p;p=L-next;while(p)p=p-next;i+;return i;習(xí)題3參考答案一、選擇題1. C 2. B 3. A 4. D 5. B 6. C7. C 8. A 9. B 10. B二、簡(jiǎn)答題1. 答：棧是限定在表的一端進(jìn)行插入和刪除操作的線性表。隊(duì)列是只允許在表的一端進(jìn)行插入，而在另一端進(jìn)行刪除元素的線性表

33、。棧的操作是按照后進(jìn)先出原則進(jìn)行的，因此又稱作后進(jìn)先出的線性表。隊(duì)列的操作是按照先進(jìn)先出原則進(jìn)行的，因此又稱作先進(jìn)先出的線性表。2. 答：當(dāng)front0，rear=M時(shí)，再有元素入隊(duì)發(fā)生溢出，稱之為“假溢出”，存儲(chǔ)空間還有剩余。為了改進(jìn)這種狀況，可以將順序隊(duì)列想象為一個(gè)首尾相接的環(huán)狀空間，稱之為循環(huán)隊(duì)列。3. 答：(1) 相應(yīng)入隊(duì)列操作Status EnQueue_L (LinkQueue &Q, ElemType e) p = (QLink) malloc (sizeof (QNode);p-data = e; p-next=Q-next;Q-next = p;Q = p;return OK

34、;(2) 相應(yīng)出隊(duì)列的操作Status DeQueue_L (LinkQueue &Q, ElemType &e) if (Q-next = Q) return ERROR;p = Q.next-next;e = p-data;Q-next-next = p-next;free(p);return OK;4.答：算法如下void Print(int n)int i;if (n=0)return;for (i=1;i=n;i+)printf(%3d,n);printf(n);Print(n-1);5.答：算法如下ElemType Bottom(Stack S)ElemType x,y;Stack

35、 T;InitStack(T);while (!StackEmpty(S)pop(S,x);push(T,x);while (!StackEmpty(T)pop(T,y);push(S,y);return x;習(xí)題4參考答案一、選擇題1. B 2. D 3. B 4. D 二、簡(jiǎn)答題1. 答：長(zhǎng)度為零的串稱為空串，記作?？崭褚彩谴淖址现械囊粋€(gè)元素，由一個(gè)或多個(gè)空格組成的串稱為空格串。例如 ，其長(zhǎng)度為串中空格的個(gè)數(shù)。2. 答：雖然串是由字符組成的，但串和字符是兩個(gè)不同的概念。串是長(zhǎng)度不確定的字符序列，而字符只是一個(gè)字符。即使是長(zhǎng)度為1的串也與字符不同。例如，串a(chǎn)和字符a就是兩個(gè)不同的概念，

36、因?yàn)樵诖鎯?chǔ)時(shí)串的結(jié)尾通常加上串結(jié)束標(biāo)志0。3. 答：在串的順序存儲(chǔ)結(jié)構(gòu)是用一維數(shù)組存放串中的字符。一種方法是用靜態(tài)內(nèi)存分配的方法定義的數(shù)組，數(shù)組元素的個(gè)數(shù)是在編譯時(shí)確定的，在運(yùn)行時(shí)是不可改變的，稱之為靜態(tài)順序存儲(chǔ)。另一種方法是用動(dòng)態(tài)內(nèi)存分配的方法定義的數(shù)組，數(shù)組元素的個(gè)數(shù)是在程序運(yùn)行時(shí)用戶申請(qǐng)確定的，稱之為動(dòng)態(tài)順序存儲(chǔ)。4. 答：Status StrDelete (String &S,int i,int j)int len;len=j-i+1;if (iS0| jS0)/ 非法情況的處理return ERROR;Spos.S0-len=Spos+len.S0;/ 將S中從下標(biāo)從pos+len開

37、始的元素前移len位S0=S0-len;/ 串長(zhǎng)的處理return OK;5. 答：Status SubString(String S1,String S2)int i,j,k,flag=0;i=1;while(iS10&!flag)j=1;if(S1i=S2j)k=i+1;j+;while(S1k=S2j)k+;j+;if (j=s20) flag=1;else i+;else i+;return flag;習(xí)題5參考答案一、選擇題1. D 2. B 3. A 4. D 5. B 6. B二、簡(jiǎn)答題1. 答：所謂行序優(yōu)先存儲(chǔ)，其基本思想為：從第1行的元素開始按順序存儲(chǔ)，第1行元素存儲(chǔ)完成后，

38、再按順序存儲(chǔ)第2行的元素，然后依次存儲(chǔ)第3行，直到最后一行的所有元素存儲(chǔ)完畢為止。而列序優(yōu)先存儲(chǔ)即為：依次按順序存儲(chǔ)第1列，第2列，直到最后一列的所有元素存儲(chǔ)完畢為止。2. 答：我們把相同的元素或零元素在矩陣中的分布有一定的規(guī)律的稱為特殊矩陣。壓縮存儲(chǔ)的原則是：對(duì)多個(gè)值相同的元素只存儲(chǔ)一次，對(duì)零元素甚至不分配存儲(chǔ)空間。3. 答：矩陣中非零元素的個(gè)數(shù)遠(yuǎn)遠(yuǎn)小于矩陣元素的總數(shù)，這樣的矩陣稱為稀疏矩陣。稀疏存儲(chǔ)的原則是只存儲(chǔ)非零元。三、計(jì)算題(1) 228 (2) 1282 (3) 1072 (4) 1276四、設(shè)計(jì)題1void proc1(matrix A) /*第(1)題解*/ int s=0,i

39、,j; for(i=0;im;i+) /*第一列*/ s=s+Ai1; for(i=0;im;i+) /*最后一列*/ s=s+Ain; for(j=0;jn;j+) /*第一行*/ s=s+A1j; for(j=0;jm;j+) /*最后一行*/ s=s+Amj; s=s-A00-A0n-1-Am-10-Am-1n-1; /*減去4個(gè)角的重復(fù)元素值*/ printf(s=%dn,s);void proc2(matrix A) /*第(2)題解*/ int s=0,i,j; i=0; while(im) j=0; while(jn) s=s+Aij; j=j+2; /*跳過一列*/ i=i+2

40、; /*跳過一行*/ printf(s=%dn,s);void proc3(matrix A) /*第(2)題解*/ int i,s; if(m!=n) printf(m!=n); else s=0; for(i=0;im;i+) s=s+Aii; /*求第一列對(duì)角線之和*/ for(i=0;in;i+) s=s+An-i-1i; /*累加第二條對(duì)角線之和*/ printf(s=%dn,s); 2void mmult() matrix A; int i,s; for(i=0;i4;i+) for(j=0;j4;j+) scanf(%d,Aij; s=1; for(i=0;i4;i+) s=s*

41、Aii; for(i=0;ilchild);Release(T-rchild);free(T);6. 解：int Depth(BiTree T)if (!T) return 0;/ 如果T為空，則其深度為0else / 若T不空返回其子樹中深度較大值加1if ( Depth(T-lchild) = Depth(T-rchild)return Depth(T-lchild)+1;else return Depth(T-rchild)+1;7.解：void Level(BiTree b,BiTree p, int *h,int lh)if (b=NULL) *h=0;else if(p=b) *h

42、=lh;else Level(p,b-lchild,h,lh+1);if(*h=-1)Level(p,b-rchild,h,lh+1);習(xí)題7參考答案一、選擇題1. C 2. D 3. A 4. B 5. B 6. D 7. A 8. D 9. C 10. C 11. D 12. C二、簡(jiǎn)答題1. 對(duì)于無向圖，如果在深度優(yōu)先遍歷中遇到回邊，則必定存在環(huán)。對(duì)于有向圖，如果從有向圖的某個(gè)頂點(diǎn)v出發(fā)的遍歷，在DFS(v)結(jié)束之前出現(xiàn)了一條從頂點(diǎn)u指向v的回邊，則此有向圖必定存在環(huán)。因?yàn)閡在深度優(yōu)先生成樹上是v的子樹，即存在u到v的路徑，現(xiàn)在又出現(xiàn)一條從u指向v的弧，則它們必然構(gòu)成一條回路。2. 用鄰接矩陣表示圖時(shí)，矩陣元素的個(gè)