數(shù)據(jù)結(jié)構(gòu)模擬試題（含答案）

數(shù)據(jù)結(jié)構(gòu)模擬試題（含答案）一、單選題（共100題，每題1分，共100分）1、在一棵度為3的樹中，度為3的結(jié)點數(shù)為2個，度為2的結(jié)點數(shù)為1個，度為1的結(jié)點數(shù)為2個，則度為0的結(jié)點數(shù)為（）個。A、5B、6C、7D、4正確答案：B2、假設(shè)在一棵二叉樹中，雙分支結(jié)點數(shù)為15，單分支結(jié)點數(shù)為30個，則葉子結(jié)點數(shù)為（）個。A、15B、47C、16D、17正確答案：C3、設(shè)某哈夫曼樹中有199個結(jié)點，則該哈夫曼樹中有（）個葉子結(jié)點。A、100B、99C、102D、101正確答案：A4、一棵含18個結(jié)點的二叉樹的高度至少為()A、5B、4C、6D、3正確答案：A5、有關(guān)棧的描述，正確的是（）A、棧是一種先進先出的特殊的線性表B、只能從棧頂執(zhí)行插入、刪除操作C、只能從棧頂執(zhí)行插入、棧底執(zhí)行刪除D、棧頂和棧底均可執(zhí)行插入、刪除操作正確答案：B6、若采用孩子兄弟鏈表作為樹的存儲結(jié)構(gòu)，則樹的后序遍歷應(yīng)采用二叉樹的（）A、中序遍歷算法B、前序遍歷算法C、后序遍歷算法D、層次遍歷算法正確答案：A7、若要在單鏈表中的結(jié)點*p之后插入一個結(jié)點*s，則應(yīng)執(zhí)行的語句是()typedefstructnode{chardata[8];structnode*next;}LinkStrNode;A、s->next=p;p->next=s->next;B、s->next=p->next;p->next=s;C、p->next=s->next;s->next=p;D、p->next=s;s->next=p->next;正確答案：B8、在一個長度為n的順序表的任一位置插入一個新元素的漸進時間復(fù)雜度為()。A、O(n)B、O(1)C、O(n2)D、O(n／2)正確答案：A9、執(zhí)行一趟快速排序能夠得到的序列是（）。A、[45，34，12，41]55[72，63，27]B、[63，12，34，45，27]55[41，72]C、[12，27，45，41]55[34，63，72]D、[41，12，34，45，27]55[72，63]正確答案：D10、帶權(quán)有向圖G用鄰接矩陣A存儲，則頂點i的入度等于A中（）。A、第i行非0的元素之和B、第i列非0的元素之和C、第i行非0的元素個數(shù)D、第i列非0的元素個數(shù)正確答案：D11、順序查找法適用于存儲結(jié)構(gòu)為()的線性表。A、順序存儲或鏈?zhǔn)酱鎯、散列存儲C、索引存儲D、壓縮存儲正確答案：A12、已知一個單鏈表中，指針q指向指針p的前趨結(jié)點，若在指針q所指結(jié)點和指針p所指結(jié)點之間插入指針s所指結(jié)點，則需執(zhí)行（）A、q→next=s；s→next=q；B、q→next=s；s→next=p；C、q→next=s；q→next=p；D、q→next=s；p→next=s；正確答案：B13、導(dǎo)致棧上溢的操作是()A、棧滿時執(zhí)行的出棧B、?？諘r執(zhí)行的出棧C、棧空時執(zhí)行的入棧D、棧滿時執(zhí)行的入棧正確答案：D14、在具有n個結(jié)點的有序單鏈表中插入一個新結(jié)點并使鏈表仍然有序的時間復(fù)雜度是()A、O(n2)B、O(nlogn)C、O(n)D、O(1)正確答案：C15、若要把n個頂點連接為一個連通圖，則至少需要()條邊。A、n+1B、2nC、n-1D、n正確答案：C16、對于任何一棵二叉樹T，如果其終端結(jié)點數(shù)為n0，度為2的結(jié)點為n2.,則()A、n2=n0+1B、n0=n2+1C、n2=2n0+1D、n0=2n2+1正確答案：B17、具有4個頂點的無向完全圖有()條邊。A、12B、16C、20D、6正確答案：D18、設(shè)單鏈表中指針p指向結(jié)點A，要刪除A之后的結(jié)點（若存在），則修改指針的操作為（）A、p->next=p->next->nextB、p=p->nextC、p=p->next->nextD、p->next=p正確答案：A19、深度為6（根的層次為1）的二叉樹至多有（）結(jié)點。A、64B、63C、31D、32正確答案：B20、樹中所有結(jié)點的度之和等于所有結(jié)點數(shù)加（）。A、0B、-1C、2D、1正確答案：B21、一個棧的輸入序列為1，2，3，…，n，設(shè)若輸出序列的第1個元素為n，輸出第i（1≤i≤n)個元素是()。A、不確定B、n-i+1C、n-iD、i正確答案：B22、數(shù)據(jù)結(jié)構(gòu)中所定義的數(shù)據(jù)元素，是用于表示數(shù)據(jù)的（）A、最小單位B、基本單位C、最大單位D、不可分割的單位正確答案：B23、對于具有n個頂點的連通無向圖，其邊的個數(shù)至少為()。A、n-1B、n+1C、nD、nlog2n正確答案：A24、設(shè)順序循環(huán)隊列Q[0：M-1]的頭指針和尾指針分別為F和R，頭指針F總是指向隊頭元素的前一位置，尾指針R總是指向隊尾元素的當(dāng)前位置，則該循環(huán)隊列中的元素個數(shù)為（）A、(R-F+M)％MB、F-RC、R-FD、(F-R+M)％M正確答案：A25、已知一棵完全二叉樹有64個葉子結(jié)點，則該樹可能達(dá)到的最大深度為（）A、10B、9C、7D、8正確答案：D26、若一個圖的邊集為{<1,2>,<1,4>,<2,5>,<3,1>,<3,5>,<4,3>}，則從頂點1開始對該圖進行廣度優(yōu)先搜索，得到的頂點序列可能為()。A、1,2,4,3,5B、1,4,2,5,3C、1,2,3,4,5D、1,2,4,5,3正確答案：D27、（）二叉排序樹可以得到一個從小到大的有序序列。A、后序遍歷B、層次遍歷C、中序遍歷D、先序遍歷正確答案：C28、設(shè)順序表有19個元素，第一個元素的地址為200，且每個元素占3個字節(jié)，則第14個元素的存儲地址為()A、239B、236C、245D、242正確答案：A29、對于二叉樹來說，第I層上至多有（）個節(jié)點。A、2^(i-1)-1B、2^iC、2^(i-1)D、2^i-1正確答案：C30、棧和隊列()A、沒有共同之處B、共同之處在于二者都是先進后出的特殊的線性表C、共同之處在于二者都只允許在頂端執(zhí)行刪除操作D、共同之處在于二者都是先進先出的特殊的線性表正確答案：C31、二叉樹中第5層上的結(jié)點個數(shù)最多為()A、15B、16C、8D、32正確答案：B32、設(shè)按照從上到下、從左到右的順序從1開始對完全二叉樹進行順序編號，則編號為i結(jié)點的左孩子結(jié)點的編號為（）。A、i/2B、2i+1C、2iD、2i-1正確答案：C33、在數(shù)據(jù)結(jié)構(gòu)中，與所使用的計算機無關(guān)的是（）。A、邏輯結(jié)構(gòu)B、物理結(jié)構(gòu)C、存儲結(jié)構(gòu)D、邏輯結(jié)構(gòu)和物理結(jié)構(gòu)正確答案：A34、設(shè)數(shù)組data[m]作為循環(huán)隊列SQ的存儲空間，front為隊頭指針，rear為隊尾指針，則執(zhí)行出對操作后其頭指針front值為（）。A、front=(front+1)%(m-1)B、front=(front-1)%mC、front=(front+1)%mD、front=front+1正確答案：C35、對一個滿二叉樹，m個樹葉，k個分枝結(jié)點，n個結(jié)點，則（）。A、n=m+1B、m+1=2nC、n=2k+1D、m=k-1正確答案：C36、若一個圖的邊集為{<1,2>,<1,4>,<2,5>,<3,1>,<3,5>,<4,3>}，則從頂點1開始對該圖進行深度優(yōu)先搜索，得到的頂點序列可能為()。A、1,2,5,3,4B、1,4,3,2,5C、1,2,5,4,3D、1,2,3,4,5正確答案：C37、對于一組記錄的關(guān)鍵字值(25,38,63,74)，采用折半查找25時，()次查找成功。A、4B、2C、1D、3正確答案：B38、對于哈希函數(shù)H(key)=key%13,被稱為同義詞的關(guān)鍵字是()A、35和41B、15和44C、23和39D、25和51正確答案：D39、判定一個棧ST（最多元素為m0）為空的條件是A、ST->top<>0B、ST->top=m0C、ST->top<>m0D、ST->top=0正確答案：D40、假定一個順序存儲的循環(huán)隊列的隊頭和隊尾指針分別為f和r,則判斷隊空的條件為().A、r+1==fB、f+1==rC、f==rD、f==0正確答案：C41、順序棧S中top為棧頂指針，指向棧頂元素所在的位置，elem為存放棧的數(shù)組，則元素e進棧操作的主要語句為（）。A、s.elem［top++］=e；s.top=s.top+1；B、s.elem［top］=e；s.top=s.top+1；C、s.top=s.top+1；s.elem［top+1］=e；D、s.top=s.top+1；s.elem［top］=e；正確答案：D42、算法分析的兩個主要方面是：A、空間復(fù)雜性和時間復(fù)雜性B、數(shù)據(jù)復(fù)雜性和程序復(fù)雜性C、正確性和簡明性D、可讀性和文檔性正確答案：A43、設(shè)哈夫曼樹中的葉子結(jié)點總數(shù)為m，若用二叉鏈表作為存儲結(jié)構(gòu)，則該哈夫曼樹中總共有（）個空指針域。A、2mB、2m-1C、4mD、2m+1正確答案：A44、對ｎ個不同的排序碼進行冒泡排序，在元素?zé)o序的情況下比較的次數(shù)為（）。A、n-1B、n+1C、n(n-1)/2D、n正確答案：C45、在下面的程序段中，對x的賦值語句的頻度為（）。for(i=1;n>=i;i++)for(j=1;n>=j;j++)x=x+1;A、O(log2n)B、O(n^2)C、O(2^n)D、O(n)正確答案：B46、已知某二叉樹的后序遍歷序列是DABEC，中序遍歷序列是DEBAC，則其先序遍歷的結(jié)點訪問序列是()。A、ACBEDB、DECABC、DEABCD、CEDBA正確答案：D47、設(shè)循環(huán)隊列的元素存放在一維數(shù)組Q［0‥30］中，隊列非空時，front指示隊頭元素的前一個位置，rear指示隊尾元素。如果隊列中元素的個數(shù)為11，front的值為25，則rear應(yīng)指向的元素是（）A、Q［4］B、Q［14］C、Q［5］D、Q［15］正確答案：C48、對于棧操作數(shù)據(jù)的原則是（）。A、不分順序B、先進先出C、后進先出D、后進后出正確答案：C49、利用二叉鏈表存儲樹，則根結(jié)點的右指針是()。A、非空B、指向最左孩子C、指向最右孩子D、空正確答案：D50、無向圖G=(V,E),其中：V={a,b,c,d,e,f},E={(a,b),(a,e),(a,c),(b,e),(c,f),(f,d),(e,d)}，對該圖進行深度優(yōu)先遍歷，得到的頂點序列正確的是（）。A、a,c,f,e,b,dB、a,b,e,c,d,fC、a,e,d,f,c,bD、a,e,b,c,f,d正確答案：C51、對于一個有向圖，若一個頂點的度為k1，出度為k2，則對應(yīng)鄰接表中該頂點單鏈表中的邊結(jié)點數(shù)為()。A、k2B、k1+k2C、k1D、k1-k2正確答案：A52、對于順序表來說，訪問任一節(jié)點的時間復(fù)雜度是（）A、O(n)B、O(1)C、O(log2n)D、O(n2)正確答案：B53、設(shè)一維數(shù)組中有n個數(shù)組元素，則讀取第i個數(shù)組元素的平均時間復(fù)雜度為（）。A、O(n2)B、O(1)C、O(n)D、O(nlog2n)正確答案：B54、已知二叉樹的中序序列和后序序列均為ABCDEF，則該二叉樹的先序序列為（）A、FEDCBAB、ABCDEFC、FDECBAD、FBDCEA正確答案：A55、具有n個結(jié)點的二叉樹，擁有指向孩子結(jié)點的分支數(shù)目是（）A、n-1B、nC、2nD、n+1正確答案：A56、下列排序算法中，不穩(wěn)定的是（）A、冒泡排序B、簡單選擇排序C、歸并排序D、直接插入排序正確答案：B57、設(shè)單鏈表中結(jié)點結(jié)構(gòu)為(data,link).已知指針q所指結(jié)點是指針p所指結(jié)點的直接前驅(qū)，若在*q與*p之間插入結(jié)點*s，則應(yīng)執(zhí)行下列哪一個操作（）A、q->link=s;s->link=pB、p->link=s;s->link=q;C、p->link=s->link;s->link=p;D、s->link=p->link;p->link=s;正確答案：A58、若最常用的操作是讀取線性表中元素的值，則采用()存儲方式最節(jié)省時間。A、單鏈表B、帶尾指針的單循環(huán)鏈表C、順序表D、帶尾指針的單鏈表正確答案：C59、從一個長度為n的順序表中刪除第i個元素（1≤i≤n）時，需向前移動的元素的個數(shù)是（）。A、iB、n-i+1C、n-i-1D、n-i正確答案：D60、棧的兩種常用存儲結(jié)構(gòu)分別為()A、鏈?zhǔn)酱鎯Y(jié)構(gòu)和索引存儲結(jié)構(gòu)B、鏈?zhǔn)酱鎯Y(jié)構(gòu)和散列存儲結(jié)構(gòu)C、順序存儲結(jié)構(gòu)和散列存儲結(jié)構(gòu)D、順序存儲結(jié)構(gòu)和鏈?zhǔn)酱鎯Y(jié)構(gòu)正確答案：D61、從未排序序列中挑選元素，并將其依次插入已排序序列（初始時為空）的一端的方法，稱為（）。A、插入排序B、選擇排序C、希爾排序D、歸并排序正確答案：B62、設(shè)一棵完全二叉樹中有65個結(jié)點，則該完全二叉樹的深度為（）。A、8B、5C、7D、6正確答案：C63、當(dāng)利用大小為n的數(shù)組順序存儲一個隊列時，該隊列的最大長度為（）A、n-2B、n-1C、n+1D、n正確答案：B64、求單鏈表中當(dāng)前結(jié)點的后繼和前驅(qū)的時間復(fù)雜度分別是（）A、O(n)和O（n）B、O（1）和O（n）C、O（1）和O（1）D、O（n）和O（1）正確答案：B65、假定對元素序列（7,3,5,9,1,12,8,15）進行快速排序，則進行第一次劃分后，得到的左區(qū)間中元素的個數(shù)為（）。A、3B、5C、4D、2正確答案：A66、用二叉鏈表表示具有n個結(jié)點的二叉樹時，值為空的指針域的個數(shù)為()A、2nB、n-1C、nD、n+l正確答案：D67、數(shù)據(jù)的基本單位是（）A、數(shù)據(jù)變量B、數(shù)據(jù)元素C、數(shù)據(jù)類型D、數(shù)據(jù)項正確答案：B68、對具有n個元素的有序表采用折半查找，則算法的時間復(fù)雜度為()。A、O(log2n)B、O(n2)C、O(n)D、O(1)正確答案：A69、一個遞歸的定義可以用遞歸過程求解，也可以用非遞歸過程求解，但單從運行時間來看，通常遞歸過程比非遞歸過程（）。A、不定B、相同C、較快D、較慢正確答案：D70、具有n個頂點的無向圖，若要連通全部頂點，至少需要（）A、（n-1）條邊B、n(n-1)條邊C、n條邊D、n(n-1)/2條邊正確答案：A71、設(shè)單鏈表中結(jié)點結(jié)構(gòu)為(data,link).若想摘除結(jié)點*p的直接后繼，則應(yīng)執(zhí)行下列哪一個操作（）A、p=p->link->link;B、p=p->link;p->link=p->link->link;C、p->link=p->link->link;D、p->link=p->link;正確答案：C72、從邏輯上可以把數(shù)據(jù)結(jié)構(gòu)分為（）.A、線性結(jié)構(gòu)、非線性結(jié)構(gòu)B、初等結(jié)構(gòu)、構(gòu)造型結(jié)構(gòu)C、動態(tài)結(jié)構(gòu)、靜態(tài)結(jié)構(gòu)D、順序結(jié)構(gòu)、鏈?zhǔn)浇Y(jié)構(gòu)正確答案：A73、在順序表中，只要知道（），就可在相同時間內(nèi)求出任一結(jié)點的存儲地址。A、結(jié)點大小B、基地址和結(jié)點大小C、基地址D、向量大小正確答案：B74、用鄰接表表示圖進行深度優(yōu)先遍歷時，通常是采用（）來實現(xiàn)算法的。A、樹B、隊列C、棧D、圖正確答案：C75、在對n個元素進行冒泡排序的過程中，至少需要（）趟完成。A、n-1B、1C、n/2D、n正確答案：B76、若已知一個棧的入棧序列是1,2,3,4……n，其輸出序列為p1,p2,p3,……pn，若p1==n,則pi為（）。A、iB、n==iC、n-i+1D、不確定正確答案：C77、在待排關(guān)鍵字序列基本有序的前提下，效率最高的排序方法是()A、直接插入排序B、快速排序C、歸并排序D、直接選擇排序正確答案：A78、設(shè)用鏈表作為棧的存儲結(jié)構(gòu)則退棧操作（）。A、必須判別棧是否為空B、判別棧元素的類型C、對棧不作任何判別D、必須判別棧是否為滿正確答案：A79、設(shè)數(shù)組A[m]為循環(huán)隊列Q的存儲空間，front為隊頭指針，rear為隊尾指針，則判定Q為空隊列的條件是()A、(rear-front)%m==1B、front==rearC、(rear-front)%m==m-1D、front==(rear+1)%m正確答案：B80、設(shè)n,m為一棵二叉樹上的兩個結(jié)點，在中序遍歷序列中n在m前的條件是（）。A、n是m的祖先B、n在m右方C、n是m的子孫D、n在m左方正確答案：D81、假設(shè)一個有n個頂點和e條弧的有向圖用鄰接表表示，則刪除預(yù)某個頂點vi相關(guān)的所有弧的時間復(fù)雜度是（）。A、O(e)B、O(n)C、O(n+e)D、O(n*e)正確答案：C82、隊列操作的原則是（）。A、只能進行刪除B、先進先出C、只能進行插入D、后進先出正確答案：B83、用順序存儲的方法將完全二叉樹中的所有結(jié)點逐層存放在數(shù)組中R[1..n]，結(jié)點R[i]若有左孩子，其左孩子的編號為結(jié)點（）。A、R[i/2]B、R[2i+1]C、R[2i]D、R[2i-1]正確答案：C84、從一個具有n個結(jié)點的單鏈表中查找其值等于x的結(jié)點時，在查找成功的情況下，需平均比較（）個元素結(jié)點。A、n/2B、（n+1）/2C、（n-1）/2D、n正確答案：B85、下列排序算法中，第一趟排序結(jié)束后其最大或最小元素一定在其最終位置上的算法是()。A、直接插入排序B、冒泡排序C、歸并排序D、快速排序正確答案：B86、設(shè)p指向單鏈表中的一個結(jié)點，s指向待插入的結(jié)點，則下述程序段的功能是（）s->next=p->next;p->next=s;t=p->data;p->data=s->data;s->data=t;A、在p所指結(jié)點的元素之前插入元素B、結(jié)點*p與結(jié)點*s的數(shù)據(jù)域互換C、在p所指結(jié)點的元素之后插入元素D、在結(jié)點*p之前插入結(jié)點*s正確答案：D87、數(shù)據(jù)的四種基本存儲結(jié)構(gòu)是指（）A、順序存儲結(jié)構(gòu)、非順序存儲結(jié)構(gòu)、指針存儲結(jié)構(gòu)、樹型存儲結(jié)構(gòu)B、順序存儲結(jié)構(gòu)、鏈?zhǔn)酱鎯Y(jié)構(gòu)、樹型存儲結(jié)構(gòu)、圖型存儲結(jié)構(gòu)C、順序存儲結(jié)構(gòu)、索引存儲結(jié)構(gòu)、直接存儲結(jié)構(gòu)、倒排存儲結(jié)構(gòu)D、順序存儲結(jié)構(gòu)、索引存儲結(jié)構(gòu)、鏈?zhǔn)酱鎯Y(jié)構(gòu)、散列存儲結(jié)構(gòu)正確答案：D88、對于線性表（7，34，55，25，64，46，20，10）進行散列存儲時，若選用H（K）=K%9作為散列函數(shù)，則散列地址為1的元素有（）個.A、4B、3C、1D、2正確答案：A89、將長度為n的單鏈表鏈接在長度為m的單鏈表之后的算法的時間復(fù)雜度為（）。A、O(n)B、O(m)C、O(1)D、O(m+n)正確答案：B90、在一個有向圖的鄰接表中，每個頂點單鏈表中結(jié)點的個數(shù)等于該頂