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

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

2、C(B)BCDA(C)CDAB(D)CBDA5 .設(shè)某棵二叉樹(shù)中有2000個(gè)結(jié)點(diǎn)，則該二叉樹(shù)的最小高度為(C)。(A)9(B)10(C)11(D)126 .下面程序的時(shí)間復(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é)點(diǎn)A,若刪除單鏈表中結(jié)點(diǎn)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è)二叉排序樹(shù)中有n個(gè)結(jié)點(diǎn)，則在二叉排序樹(shù)的平均平均查找長(zhǎng)度為(B)。(A)O(1)(B)O(log2n)(C)(D)O(n2)9 .數(shù)據(jù)的物理結(jié)構(gòu)主要包括順序存儲(chǔ)結(jié)構(gòu)和鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)兩種情況。10 .設(shè)一棵完全二叉樹(shù)中有500個(gè)結(jié)點(diǎn)，則該二叉樹(shù)的深度為9;若用二叉鏈表作為該完全二叉樹(shù)的存儲(chǔ)結(jié)構(gòu)，則共有501個(gè)

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

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

6、數(shù)據(jù)元素需要移動(dòng)表中n-i_個(gè)元素。20 .設(shè)前序遍歷某二叉樹(shù)的序列為ABCD,中序遍歷該二叉樹(shù)的序列為BADC,則后序遍歷該二叉樹(shù)的序列為BDCA。21 .下圖所示的森林：(1)求樹(shù)(a)的先根序列和后根序列；(2)求森林先序序列和中序序列；(3)將此森林轉(zhuǎn)換為相應(yīng)的二叉樹(shù)；答案：(1)ABCDEF;BDEFCA;(2)ABCDEFGHIJK;BDEFCAIJKHG(3)森林轉(zhuǎn)換為相應(yīng)的二叉樹(shù)；22 .數(shù)據(jù)的最小單位是(A)。(A)數(shù)據(jù)項(xiàng)(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è)一個(gè)有序的單鏈表中有n個(gè)結(jié)點(diǎn)，現(xiàn)要求插入一個(gè)新結(jié)點(diǎn)后使得單鏈表仍然保持有序，則該操作的時(shí)間復(fù)雜度為(D)。(A)O(log2n)(B)O(1)(C)O(n2)(D)O(n)25 .設(shè)輸入序列是1、2、3、，、n,經(jīng)過(guò)棧的作用后輸出序列的第一個(gè)元素是n,則輸出序列中第i個(gè)輸出元素是(C)。(A)n-i(B)n-1-i(C)n+1-i(D)不能確定26 .設(shè)一棵完全二叉樹(shù)的順序存儲(chǔ)結(jié)構(gòu)中存儲(chǔ)數(shù)據(jù)元素為ABCDEF則該二叉樹(shù)的前序遍歷'序列為,中序遍歷'序列為,后序遍歷'序列為答案：ABD

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

9、O(n1/2)(D)O(1og2n)31 .設(shè)指針變量front表示鏈?zhǔn)疥?duì)列的隊(duì)頭指針，指針變量rear表示鏈?zhǔn)疥?duì)列的隊(duì)尾指針，指針變量s指向?qū)⒁腙?duì)列的結(jié)點(diǎn)X,則入隊(duì)列的操作序列為(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è)某哈夫曼樹(shù)中有199個(gè)結(jié)點(diǎn)，則該哈夫曼樹(shù)中有(B)個(gè)葉子結(jié)點(diǎn)。(A)99(B)100(C)101(D)10233 .設(shè)二叉排序樹(shù)上有n個(gè)結(jié)點(diǎn)，則在二叉排序樹(shù)上查找結(jié)點(diǎn)的平均時(shí)間復(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；的時(shí)間復(fù)雜度為0(n)。35 .設(shè)F和R分別表示順序循環(huán)隊(duì)列的頭指針和尾指針，則判斷該循欣列K的條件為F=R36 .(B)二叉排序樹(shù)可以得到一個(gè)從小到大的有序序列。(A)先序遍歷(B)中序遍歷(C)后序遍歷(D)層次遍歷37 .設(shè)按照從上到下、從左到右的順序從1開(kāi)始對(duì)完全二叉樹(shù)進(jìn)行順序編號(hào)，則編號(hào)為i結(jié)點(diǎn)的左孩子結(jié)點(diǎn)的編號(hào)為(B)。(A)2i+1(B)2i(C)i/2(D)2i-138 .設(shè)帶有頭結(jié)點(diǎn)的單向循環(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)；的時(shí)間復(fù)雜度為(A)。(A)O(n)(B)O(nlog2n)(C)O(n2)(D)O(n3/2)40 .設(shè)某棵二叉樹(shù)的高度為10,則該二叉樹(shù)上葉子結(jié)點(diǎn)最多有(C)。(A)20(B)256(C)512(D)102441 .設(shè)指針變量top指向當(dāng)前鏈?zhǔn)綏５臈ｍ?，則刪除棧頂元素的操作序列為(D)。(A)top=top+1;(B)top=top-1;(C)top->

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

13、鏈表中結(jié)點(diǎn)A,指針變量s指向被插入的結(jié)點(diǎn)X,則在結(jié)點(diǎn)A的后面插入結(jié)點(diǎn)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è)某棵完全二叉樹(shù)中有100個(gè)結(jié)點(diǎn)，則該二叉樹(shù)中有50個(gè)葉子結(jié)點(diǎn)。49 .入棧操作和入隊(duì)列操作在鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)上實(shí)現(xiàn)時(shí)不需要考慮棧溢出的情況。50 .設(shè)某鏈表中最常用的操作是在鏈表的尾部插入或刪除元素，則選用下列(D)存儲(chǔ)方式最節(jié)省運(yùn)算時(shí)間。(A)單向鏈表(B)單向循環(huán)鏈表(C)雙向鏈表(D)雙向循環(huán)鏈表51 .設(shè)指針q指向單鏈表中結(jié)點(diǎn)A,指針p指向單鏈表中結(jié)點(diǎn)A的后繼結(jié)點(diǎn)B,指針s指向被插入的結(jié)點(diǎn)X,則在結(jié)點(diǎn)A和結(jié)點(diǎn)B插入結(jié)點(diǎn)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 .二叉樹(shù)第i(i