數(shù)據(jù)結(jié)構(gòu)實用試題及答案

1、數(shù)據(jù)結(jié)構(gòu)實用試題及答案1 .設(shè)有一個二維數(shù)組Amn,假設(shè)A00存放位置在644(10),A22存放位置在676(1%每個元素占一個空間，問A33(io)存放在什么位置？腳注(10)表示用10進制表示。(C)A.688B.678C.692D.6962 .二叉樹的第k層的結(jié)點數(shù)最多為(D).A.2k-1B.2K+1C.2K-1D.2k-13 .設(shè)哈夫曼樹中的葉子結(jié)點總數(shù)為現(xiàn)若用二叉鏈表作為存儲結(jié)構(gòu)，則該哈夫曼樹中總共有(B)個空指針域。(A)2m-1(B)2m(C)2m+1(D)4m4 .設(shè)某棵二叉樹的中序遍歷序列為ABCD,前序遍歷序列為CABD,則后序遍歷該二叉樹得到序列為(A)。(A)BAD

2、C(B)BCDA(C)CDAB(D)CBDA5 .設(shè)某棵二叉樹中有2000個結(jié)點，則該二叉樹的最小高度為(C)。(A)9(B)10(C)11(D)126 .下面程序的時間復(fù)雜為(B)for(i=1,s=0;i<=n；i+)t=1；for(j=1；j<=i；j+)t=t*j；s=s+t；(A)O(n)(B)O(n2)7 .設(shè)指針變量p指向單鏈表中結(jié)點A,若刪除單鏈表中結(jié)點A,則需要修改指針的操作序列為(A)。(A) q=p->next；p->data=q->data;p->next=q->next；free(q)；(B) q=p->next；q-&

3、gt;data=p->data;p->next=q->next；free(q)；(C) q=p->next；p->next=q->next；free(q)；(D) q=p->next；p->data=q->data;free(q);8 .設(shè)二叉排序樹中有n個結(jié)點，則在二叉排序樹的平均平均查找長度為(B)。(A)O(1)(B)O(log2n)(C)(D)O(n2)9 .數(shù)據(jù)的物理結(jié)構(gòu)主要包括順序存儲結(jié)構(gòu)和鏈?zhǔn)酱鎯Y(jié)構(gòu)兩種情況。10 .設(shè)一棵完全二叉樹中有500個結(jié)點，則該二叉樹的深度為9;若用二叉鏈表作為該完全二叉樹的存儲結(jié)構(gòu)，則共有501個

4、空指針域。11 .設(shè)輸入序列為1、2、3,則經(jīng)過棧的作用后可以得到5種不同的輸出序列。12 .設(shè)有n個結(jié)點的完全二叉樹，如果按照從自上到下、從左到右從1開始順序編號，則第i個結(jié)點的雙親結(jié)點編號為i/2,右孩子結(jié)點的編號為2i+1。13 .設(shè)一維數(shù)組中有n個數(shù)組元素，則讀取第i個數(shù)組元素的平均時間復(fù)雜度為(C)。(A)O(n)(B)O(nlog2n)(C)O(1)(D)O(n2)14 .設(shè)一棵二叉樹的深度為k,則該二叉樹中最多有(D)個結(jié)點，最少有(C)個結(jié)點。(A)2k-1(B)2k(C)2k-1(D)2k-115 .在二叉排序樹中插入一個結(jié)點的時間復(fù)雜度為(B)。(A)O(1)(B)O(n)

5、(C)O(log2n)(D)O(n2)16 .設(shè)用鏈表作為棧的存儲結(jié)構(gòu)則退棧操作(B)0(A)必須判別棧是否為滿(B)必須判別棧是否為空(C)判別棧元素的類型(D)對棧不作任何判別17 .設(shè)某二叉樹中度數(shù)為0的結(jié)點數(shù)為電度數(shù)為1的結(jié)點數(shù)為N,度數(shù)為2的結(jié)點數(shù)為N,則下列等式成立的是(C)。(A)No=N+1(B)No=N+N(C)N0=N+1(D)N0=2N+l18 .設(shè)哈夫曼樹中共有99個結(jié)點，則該樹中有50個葉子結(jié)點；若采用二叉鏈表作為存儲結(jié)構(gòu)，則該樹中有51個空指針域。19 .設(shè)順序線性表中有n個數(shù)據(jù)元素，則第i個位置上插入一個數(shù)據(jù)元素需要移動表中n-i+1個數(shù)據(jù)元素；刪除第i個位置上的

6、數(shù)據(jù)元素需要移動表中n-i_個元素。20 .設(shè)前序遍歷某二叉樹的序列為ABCD,中序遍歷該二叉樹的序列為BADC,則后序遍歷該二叉樹的序列為BDCA。21 .下圖所示的森林：(1)求樹(a)的先根序列和后根序列；(2)求森林先序序列和中序序列；(3)將此森林轉(zhuǎn)換為相應(yīng)的二叉樹；答案：(1)ABCDEF;BDEFCA;(2)ABCDEFGHIJK;BDEFCAIJKHG(3)森林轉(zhuǎn)換為相應(yīng)的二叉樹；22 .數(shù)據(jù)的最小單位是(A)。(A)數(shù)據(jù)項(B)數(shù)據(jù)類型(C)數(shù)據(jù)元素(D)數(shù)據(jù)變量23 .函數(shù)substr("DATASTRUCTURE5,9)的返回值為(A)。(A)“STRUCTUR

7、E(B)“DATA(C)“ASTRUCTUR(D)“datastructUre24 .設(shè)一個有序的單鏈表中有n個結(jié)點，現(xiàn)要求插入一個新結(jié)點后使得單鏈表仍然保持有序，則該操作的時間復(fù)雜度為(D)。(A)O(log2n)(B)O(1)(C)O(n2)(D)O(n)25 .設(shè)輸入序列是1、2、3、，、n,經(jīng)過棧的作用后輸出序列的第一個元素是n,則輸出序列中第i個輸出元素是(C)。(A)n-i(B)n-1-i(C)n+1-i(D)不能確定26 .設(shè)一棵完全二叉樹的順序存儲結(jié)構(gòu)中存儲數(shù)據(jù)元素為ABCDEF則該二叉樹的前序遍歷'序列為,中序遍歷'序列為,后序遍歷'序列為答案：ABD

8、ECF,DBEAFC,DEBFCA27 .設(shè)一棵完全二叉樹有128個結(jié)點，則該完全二叉樹的深度為8,有64個葉子結(jié)點。28 .設(shè)一條單鏈表的頭指針變量為head且該鏈表沒有頭結(jié)點，則其判空條件是(A)。(A)head=0(B)head->next=0(C)head->next=head(D)head!=029 .設(shè)二叉樹的先序遍歷序列和后序遍歷序列正好相反，則該二叉樹滿足的條件是(D)。(A)空或只有一個結(jié)點(B)高度等于其結(jié)點數(shù)(C)任一結(jié)點無左孩子(D)任一結(jié)點無右孩子30 .順序查找不論在順序線性表中還是在鏈?zhǔn)骄€性表中的時間復(fù)雜度為(A)。(A)O(n)(B)O(n2)(C)

9、O(n1/2)(D)O(1og2n)31 .設(shè)指針變量front表示鏈?zhǔn)疥犃械年狀^指針，指針變量rear表示鏈?zhǔn)疥犃械年犖仓羔槪羔樧兞縮指向?qū)⒁腙犃械慕Y(jié)點X,則入隊列的操作序列為(C)。(A)front->next=s；front=s；(B)s->next=rear;rear=s;(C)rear->next=s；rear=s;(D)s->next=front；front=s；32 .設(shè)某哈夫曼樹中有199個結(jié)點，則該哈夫曼樹中有(B)個葉子結(jié)點。(A)99(B)100(C)101(D)10233 .設(shè)二叉排序樹上有n個結(jié)點，則在二叉排序樹上查找結(jié)點的平均時間復(fù)雜度為

10、(D)。(A)O(n)(B)O(n2)(C)O(nlog2n)(D)O(1og2n)34 .for(i=1,t=1,s=0；i<=n；i+)t=t*i；s=s+t；的時間復(fù)雜度為0(n)。35 .設(shè)F和R分別表示順序循環(huán)隊列的頭指針和尾指針，則判斷該循欣列K的條件為F=R36 .(B)二叉排序樹可以得到一個從小到大的有序序列。(A)先序遍歷(B)中序遍歷(C)后序遍歷(D)層次遍歷37 .設(shè)按照從上到下、從左到右的順序從1開始對完全二叉樹進行順序編號，則編號為i結(jié)點的左孩子結(jié)點的編號為(B)。(A)2i+1(B)2i(C)i/2(D)2i-138 .設(shè)帶有頭結(jié)點的單向循環(huán)鏈表的頭指針變量

11、為head,則其判空條件是(C)。(A)head=0(B)head->next=0(C)head->next=head(D)head!=039 .程序段s=i=0;doi=i+1;s=s+i;while(i<=n)；的時間復(fù)雜度為(A)。(A)O(n)(B)O(nlog2n)(C)O(n2)(D)O(n3/2)40 .設(shè)某棵二叉樹的高度為10,則該二叉樹上葉子結(jié)點最多有(C)。(A)20(B)256(C)512(D)102441 .設(shè)指針變量top指向當(dāng)前鏈?zhǔn)綏５臈ｍ敚瑒t刪除棧頂元素的操作序列為(D)。(A)top=top+1;(B)top=top-1;(C)top->

12、next=top;(D)top=top->next;42 .哈夫曼樹中沒有度數(shù)為1的結(jié)點。43 .字符串的長度是指(C)。(A)用中不同字符的個數(shù)(B)用中不同字母的個數(shù)(C)用中所含字符的個數(shù)(D)用中不同數(shù)字的個數(shù)44 .建立一個長度為n的有序單鏈表的時間復(fù)雜度為(C)(A)O(n)(B)O(1)(C)O(n2)(D)O(log2n)45 .兩個字符串相等的充要條件是(C)。(A)兩個字符串的長度相等(B)兩個字符串中對應(yīng)位置上的字符相等(C)同時具備(A)和(B)兩個條件(D)以上答案都不對46 .完全二叉樹中第5層上最少有1一個結(jié)點，最多有16個結(jié)點。47 .設(shè)指針變量p指向雙向

13、鏈表中結(jié)點A,指針變量s指向被插入的結(jié)點X,則在結(jié)點A的后面插入結(jié)點X的操作序列為(D)。(A) p->right=s；s->left=p；p->right->left=s;s->right=p->right;(B) s->left=p；s->right=p->right;p->right=s；p->right->left=s;(C) p->right=s；p->right->left=s;s->left=p；s->right=p->right;(D) s->left=p；s-&g

14、t;right=p->right;p->right->left=s;p->right=s；48 .設(shè)某棵完全二叉樹中有100個結(jié)點，則該二叉樹中有50個葉子結(jié)點。49 .入棧操作和入隊列操作在鏈?zhǔn)酱鎯Y(jié)構(gòu)上實現(xiàn)時不需要考慮棧溢出的情況。50 .設(shè)某鏈表中最常用的操作是在鏈表的尾部插入或刪除元素，則選用下列(D)存儲方式最節(jié)省運算時間。(A)單向鏈表(B)單向循環(huán)鏈表(C)雙向鏈表(D)雙向循環(huán)鏈表51 .設(shè)指針q指向單鏈表中結(jié)點A,指針p指向單鏈表中結(jié)點A的后繼結(jié)點B,指針s指向被插入的結(jié)點X,則在結(jié)點A和結(jié)點B插入結(jié)點X的操作序列為(B)。(A)s->next=p->next;p->next=-s;(B)q->next=s;s->next=p;(C)p->next=s->next;s->next=p;(D)p->next=s;s->next=q;52 .二叉樹第i(i