《數(shù)據(jù)結構》3套模擬試題綜合測試題帶答案3

PAGEPAGE5《數(shù)據(jù)結構》模擬試題07一、單項選擇題（每題3分，共30分）1．設一維數(shù)組中有n個數(shù)組元素，則讀取第i個數(shù)組元素的平均時間復雜度為（）。 (A)O(n) (B)O(nlog2n) (C)O(1) (D)O(n2)2．設一棵二叉樹的深度為k，則該二叉樹中最多有（）個結點。 (A)2k-1 (B)2k (C)2k-1 (D)2k-13．設某無向圖中有n個頂點e條邊，則該無向圖中所有頂點的入度之和為（）。 (A)n (B)e (C)2n (D)2e4．在二叉排序樹中插入一個結點的時間復雜度為（）。 (A)O(1) (B)O(n) (C)O(log2n) (D)O(n2)5．設某有向圖的鄰接表中有n個表頭結點和m個表結點，則該圖中有（）條有向邊。 (A)n (B)n-1 (C)m (D)m-16．設一組初始記錄關鍵字序列為(345，253，674，924，627)，則用基數(shù)排序需要進行（）趟的分配和回收才能使得初始關鍵字序列變成有序序列。 (A)3 (B)4 (C)5 (D)87．設用鏈表作為棧的存儲結構則退棧操作（）。 (A)必須判別棧是否為滿 (B)必須判別棧是否為空 (C)判別棧元素的類型 (D)對棧不作任何判別8．下列四種排序中（）的空間復雜度最大。 (A)快速排序 (B)冒泡排序 (C)希爾排序 (D)堆9．設某二叉樹中度數(shù)為0的結點數(shù)為N0，度數(shù)為1的結點數(shù)為Nl，度數(shù)為2的結點數(shù)為N2，則下列等式成立的是（）。 (A)N0=N1+1 (B)N0=Nl+N2 (C)N0=N2+1 (D)N0=2N1+l10.設有序順序表中有n個數(shù)據(jù)元素，則利用二分查找法查找數(shù)據(jù)元素X的最多比較次數(shù)不超過（）。 (A)log2n+1 (B)log2n-1 (C)log2n (D)log2(n+1)二、填空題（每題2分，共26分）設有n個無序的記錄關鍵字，則直接插入排序的時間復雜度為________，快速排序的平均時間復雜度為_________。設指針變量p指向雙向循環(huán)鏈表中的結點X，則刪除結點X需要執(zhí)行的語句序列為_________________________________________________________（設結點中的兩個指針域分別為llink和rlink）。根據(jù)初始關鍵字序列(19，22，01，38，10)建立的二叉排序樹的高度為____________。深度為k的完全二叉樹中最少有____________個結點。設初始記錄關鍵字序列為(K1，K2，…，Kn)，則用篩選法思想建堆必須從第______個元素開始進行篩選。設哈夫曼樹中共有99個結點，則該樹中有_________個葉子結點；若采用二叉鏈表作為存儲結構，則該樹中有_____個空指針域。設有一個順序循環(huán)隊列中有M個存儲單元，則該循環(huán)隊列中最多能夠存儲________個隊列元素；當前實際存儲________________個隊列元素（設頭指針F指向當前隊頭元素的前一個位置，尾指針指向當前隊尾元素的位置）。設順序線性表中有n個數(shù)據(jù)元素，則第i個位置上插入一個數(shù)據(jù)元素需要移動表中_______個數(shù)據(jù)元素；刪除第i個位置上的數(shù)據(jù)元素需要移動表中_______個元素。設一組初始記錄關鍵字序列為(20，18，22，16，30，19)，則以20為中軸的一趟快速排序結果為______________________________。設一組初始記錄關鍵字序列為(20，18，22，16，30，19)，則根據(jù)這些初始關鍵字序列建成的初始堆為________________________。設某無向圖G中有n個頂點，用鄰接矩陣A作為該圖的存儲結構，則頂點i和頂點j互為鄰接點的條件是______________________。設無向圖對應的鄰接矩陣為A，則A中第i上非0元素的個數(shù)_________第i列上非0元素的個數(shù)（填等于，大于或小于）。設前序遍歷某二叉樹的序列為ABCD，中序遍歷該二叉樹的序列為BADC，則后序遍歷該二叉樹的序列為_____________。三、算法填空題（每題8分，共8分）設散列函數(shù)H(k)=kmodp，解決沖突的方法為鏈地址法。要求在下列算法劃線處填上正確的語句完成在散列表hashtalbe中查找關鍵字值等于k的結點，成功時返回指向關鍵字的指針，不成功時返回標志0。typedefstructnode{intkey;structnode*next;}lklist;voidcreatelkhash(lklist*hashtable[]){inti,k;lklist*s;for(i=0;i<m;i++)_____________________;for(i=0;i<n;i++){s=(lklist*)malloc(sizeof(lklist));s->key=a[i];k=a[i]%p;s->next=hashtable[k];_______________________;}}四、算法設計題（每題12分，共36分）設單鏈表中有僅三類字符的數(shù)據(jù)元素(大寫字母、數(shù)字和其它字符)，要求利用原單鏈表中結點空間設計出三個單鏈表的算法，使每個單鏈表只包含同類字符。設計在鏈式存儲結構上交換二叉樹中所有結點左右子樹的算法。在鏈式存儲結構上建立一棵二叉排序樹。PAGEPAGE1《數(shù)據(jù)結構》模擬試題07參考答案一、單項選擇題（每題3分，共30分）1．C 2．D 3．D 4．B 5．C6．A 7．B 8．A 9．C 10．A二、填空題（每小題2分，共26分）O(n2)，O(nlog2n)p>llink->rlink=p->rlink;p->rlink->llink=p->rlink32k-1n/250，51m-1，(R-F+M)%Mn+1-i，n-i(19，18，16，20，30，22)(16，18，19，20，32，22)A[i][j]=1等于BDCA三、算法填空題（每題8分，共8分）hashtable[i]=0，hashtable[k]=s四、算法設計題（每題12分，共36分）設單鏈表中有僅三類字符的數(shù)據(jù)元素(大寫字母、數(shù)字和其它字符)，要求利用原單鏈表中結點空間設計出三個單鏈表的算法，使每個單鏈表只包含同類字符。typedefchardatatype;typedefstructnode{datatypedata;structnode*next;}lklist;voidsplit(lklist*head,lklist*&ha,lklist*&hb,lklist*&hc){lklist*p;ha=0,hb=0,hc=0;for(p=head;p!=0;p=head){head=p->next;p->next=0;if(p->data>='A'&&p->data<='Z'){p->next=ha;ha=p;}elseif(p->data>='0'&&p->data<='9'){p->next=hb;hb=p;}else{p->next=hc;hc=p;}}}設計在鏈式存儲結構上交換二叉樹中所有結點左右子樹的算法。typedefstructnode{intdata;structnode*lchild,*rchild;}bitree;voidswapbitree(bitree*bt){bitree*p;if(bt==0)return;swapbitree(bt->lchild);swapbitree(bt->rchild);p=bt->lchild;bt->lchild=bt->rchild;bt->rchild=p;}在鏈式存儲結構上建立一棵二叉排序樹。#definen10typedefstructnode{intkey;structnode*lchild,*rchild;}bitree;voidbstinsert(bitree*&bt,intkey){if(bt==0){bt=(bitree*)malloc(sizeof(bitree));bt->key=key;bt->lchild=bt->rchild=0;}elseif(bt->key>key)bstinsert(bt->lchild,key);elsebstinsert(bt->rchild,key);}voidcreatebsttree(bitree*&bt){inti;for(i=1;i<=n;i++)bstinsert(bt,random(100));}《數(shù)據(jù)結構》模擬試題08一、單項選擇題（每題2分，共20分）1．數(shù)據(jù)的最小單位是（）。 (A)數(shù)據(jù)項 (B)數(shù)據(jù)類型 (C)數(shù)據(jù)元素 (D)數(shù)據(jù)變量2．設一組初始記錄關鍵字序列為(50，40，95，20，15，70，60，45)，則以增量d=4的一趟希爾排序結束后前4條記錄關鍵字為（）。 (A)40，50，20，95 (B)15，40，60，20 (C)15，20，40，45 (D)45，40，15，203．設一組初始記錄關鍵字序列為(25，50，15，35，80，85，20，40，36，70)，其中含有5個長度為2的有序子表，則用歸并排序的方法對該記錄關鍵字序列進行一趟歸并后的結果為（）。(A)15，25，35，50，20，40，80，85，36，70(B)15，25，35，50，80，20，85，40，70，36(C)15，25，35，50，80，85，20，36，40，70(D)15，25，35，50，80，20，36，40，70，854．函數(shù)substr(“DATASTRUCTURE”，5，9)的返回值為（）。 (A)“STRUCTURE” (B)“DATA” (C)“ASTRUCTUR” (D)“DATASTRUCTURE”5．設一個有序的單鏈表中有n個結點，現(xiàn)要求插入一個新結點后使得單鏈表仍然保持有序，則該操作的時間復雜度為（）。 (A)O(log2n) (B)O(1) (C)O(n2) (D)O(n)6．設一棵m叉樹中度數(shù)為0的結點數(shù)為N0，度數(shù)為1的結點數(shù)為Nl，……，度數(shù)為m的結點數(shù)為Nm，則N0=（）。 (A)Nl+N2+……+Nm (B)l+N2+2N3+3N4+……+(m-1)Nm (C)N2+2N3+3N4+……+(m-1)Nm (D)2Nl+3N2+……+(m+1)Nm7．設有序表中有1000個元素，則用二分查找查找元素X最多需要比較（）次。 (A)25 (B)10 (C)7 (D)18．設連通圖G中的邊集E={(a，b)，(a，e)，(a，c)，(b，e)，(e，d)，(d，f)，(f，c)}，則從頂點a出發(fā)可以得到一種深度優(yōu)先遍歷的頂點序列為（）。 (A)abedfc (B)acfebd (C)aebdfc (D)aedfcb9．設輸入序列是1、2、3、……、n，經(jīng)過棧的作用后輸出序列的第一個元素是n，則輸出序列中第i個輸出元素是（）。 (A)n-i (B)n-1-i (C)n+1-i (D)不能確定10設一組初始記錄關鍵字序列為(45，80，55，40，42，85)，則以第一個記錄關鍵字45為基準而得到一趟快速排序的結果是（）。 (A)40，42，45，55，80，83 (B)42，40，45，80，85，88 (C)42，40，45，55，80，85 (D)42，40，45，85，55，80二、填空題（每題2分，共16分）設有一個順序共享棧S[0：n-1]，其中第一個棧項指針top1的初值為-1，第二個棧頂指針top2的初值為n，則判斷共享棧滿的條件是____________________。在圖的鄰接表中用順序存儲結構存儲表頭結點的優(yōu)點是____________________。設有一個n階的下三角矩陣A，如果按照行的順序將下三角矩陣中的元素（包括對角線上元素）存放在n(n+1)個連續(xù)的存儲單元中，則A[i][j]與A[0][0]之間有_______個數(shù)據(jù)元素。棧的插入和刪除只能在棧的棧頂進行，后進棧的元素必定先出棧，所以又把棧稱為__________表；隊列的插入和刪除運算分別在隊列的兩端進行，先進隊列的元素必定先出隊列，所以又把隊列稱為_________表。設一棵完全二叉樹的順序存儲結構中存儲數(shù)據(jù)元素為ABCDEF，則該二叉樹的前序遍歷序列為___________，中序遍歷序列為___________，后序遍歷序列為___________。設一棵完全二叉樹有128個結點，則該完全二叉樹的深度為________，有__________個葉子結點。設有向圖G的存儲結構用鄰接矩陣A來表示，則A中第i行中所有非零元素個數(shù)之和等于頂點i的________，第i列中所有非零元素個數(shù)之和等于頂點i的__________。設一組初始記錄關鍵字序列(k1，k2，……，kn)是堆，則對i=1，2，…，n/2而言滿足的條件為_______________________________。三、算法填空題（每題8分，共16分）下面程序段的功能是實現(xiàn)冒泡排序算法，請在下劃線處填上正確的語句。voidbubble(intr[n]){for(i=1;i<=n-1;i++){for(exchange=0,j=0;j<_____________;j++)if(r[j]>r[j+1]){temp=r[j+1];______________;r[j]=temp;exchange=1;}if(exchange==0)return；}}下面程序段的功能是實現(xiàn)二分查找算法，請在下劃線處填上正確的語句。structrecord{intkey;intothers;};intbisearch(structrecordr[],intk){intlow=0,mid,high=n-1;while(low<=high){________________________________;if(r[mid].key==k)return(mid+1); elseif(____________)high=mid-1; elselow=mid+1;}return(0);}四、算法簡答題（每題6分，共24分）設某棵二叉樹的中序遍歷序列為DBEAC，前序遍歷序列為ABDEC，要求給出該二叉樹的的后序遍歷序列。設無向圖G（如下圖所示），給出該圖的最小生成樹上邊的集合并計算最小生成樹各邊上的權值之和。設一組初始記錄關鍵字序列為(15，17，18，22，35，51，60)，要求計算出成功查找時的平均查找長度。設散列表的長度為8，散列函數(shù)H(k)=kmod7，初始記錄關鍵字序列為(25，31，8，27，13，68)，要求分別計算出用線性探測法和鏈地址法作為解決沖突方法的平均查找長度。五、算法設計題（每題12分，共24分）設計判斷兩個二叉樹是否相同的算法。設計兩個有序單鏈表的合并排序算法。PAGEPAGE5《數(shù)據(jù)結構》模擬試題08參考答案一、單項選擇題（每題2分，共20分）1．A 2．B 3．A 4．A 5．D6．B 7．B 8．B 9．C 10．C二、填空題（每小題2分，共16分）top1+1=top2可以隨機訪問到任一個頂點的簡單鏈表i(i+1)/2+j-1FILO，F(xiàn)IFOABDECF，DBEAFC，DEBFCA8，64出度，入度ki<=k2i&&ki<=k2i+1三、算法填空題（每題8分，共16分）n-i，r[j+1]=r[j]mid=(low+high)/2，r[mid].key>k四、算法簡答題（每題6分，共24分）DEBCAE={(1,5),(5,2),(5,3),(3,4)},W=10ASL=(1*1+2*2+3*4)/7=17/7ASL1=7/6，ASL2=4/3五、算法設計題（每題12分，共24分）設計判斷兩個二叉樹是否相同的算法。typedefstructnode{datatypedata;structnode*lchild,*rchild;}bitree;intjudgebitree(bitree*bt1,bitree*bt2){if(bt1==0&&bt2==0)return(1);elseif(bt1==0||bt2==0||bt1->data!=bt2->data)return(0);elsereturn(judgebitree(bt1->lchild,bt2->lchild)*judgebitree(bt1->rchild,bt2->rchild));}設計兩個有序單鏈表的合并排序算法。voidmergelklist(lklist*ha,lklist*hb,lklist*&hc){lklist*s=hc=0;while(ha!=0&&hb!=0)if(ha->data<hb->data){if(s==0)hc=s=ha;else{s->next=ha;s=ha;};ha=ha->next;}else{if(s==0)hc=s=hb;else{s->next=hb;s=hb;};hb=hb->next;}if(ha==0)s->next=hb;elses->next=ha;}《數(shù)據(jù)結構》模擬試題09一、單項選擇題（每題2分，共30分）1．設一組權值集合W={2，3，4，5，6}，則由該權值集合構造的哈夫曼樹中帶權路徑長度之和為（）。 (A)20 (B)30 (C)40 (D)452．執(zhí)行一趟快速排序能夠得到的序列是（）。 (A)[41，12，34，45，27]55[72，63] (B)[45，34，12，41]55[72，63，27] (C)[63，12，34，45，27]55[41，72] (D)[12，27，45，41]55[34，63，72]3．設一條單鏈表的頭指針變量為head且該鏈表沒有頭結點，則其判空條件是（）。(A)head==0 (B)head->next==0(C)head->next==head (D)head!=04．時間復雜度不受數(shù)據(jù)初始狀態(tài)影響而恒為O(nlog2n)的是（）。 (A)堆排序 (B)冒泡排序 (C)希爾排序 (D)快速排序5．設二叉樹的先序遍歷序列和后序遍歷序列正好相反，則該二叉樹滿足的條件是（）。 (A)空或只有一個結點 (B)高度等于其結點數(shù) (C)任一結點無左孩子 (D)任一結點無右孩子6．一趟排序結束后不一定能夠選出一個元素放在其最終位置上的是（）。 (A)堆排序 (B)冒泡排序 (C)快速排序 (D)希爾排序7．設某棵三叉樹中有40個結點，則該三叉樹的最小高度為（）。 (A)3 (B)4 (C)5 (D)68．順序查找不論在順序線性表中還是在鏈式線性表中的時間復雜度為（）。 (A)O(n) (B)O(n2) (C)O(n1/2) (D)O(1og2n)9．二路歸并排序的時間復雜度為（）。 (A)O(n) (B)O(n2) (C)O(nlog2n) (D)O(1og2n)10.深度為k的完全二叉樹中最少有（）個結點。 (A)2k-1-1 (B)2k-1 (C)2k-1+1 (D)2k-111.設指針變量front表示鏈式隊列的隊頭指針，指針變量rear表示鏈式隊列的隊尾指針，指針變量s指向將要入隊列的結點X，則入隊列的操作序列為（）。 (A)front->next=s；front=s； (B)s->next=rear；rear=s； (C)rear->next=s；rear=s； (D)s->next=front；front=s；12.設某無向圖中有n個頂點e條邊，則建立該圖鄰接表的時間復雜度為（）。 (A)O(n+e) (B)O(n2) (C)O(ne) (D)O(n3)13.設某哈夫曼樹中有199個結點，則該哈夫曼樹中有（）個葉子結點。 (A)99 (B)100 (C)101 (D)10214.設二叉排序樹上有n個結點，則在二叉排序樹上查找結點的平均時間復雜度為（）。 (A)O(n) (B)O(n2) (C)O(nlog2n) (D)O(1og2n)15.設用鄰接矩陣A表示有向圖G的存儲結構，則有向圖G中頂點i的入度為（）。 (A)第i行非0元素的個數(shù)之和 (B)第i列非0元素的個數(shù)之和 (C)第i行0元素的個數(shù)之和 (D)第i列0元素的個數(shù)之和二、填空題（每題2分，共20分）1．for(i=1，t=1，s=0；i<=n；i++){t=t*i；s=s+t；}的時間復雜度為_________。2．設指針變量p指向單鏈表中結點A，指針變量s指向被插入的新結點X，則進行插入操作的語句序列為__________________________（設結點的指針域為next）。3．設有向圖G的二元組形式表示為G=（D，R），D={1，2，3，4，5}，R={r}，r={<1,2>，<2,4>，<4,5>，<1,3>，<3,2>，<3,5>}，則給出該圖的一種拓撲排序序列__________。4．設無向圖G中有n個頂點，則該無向圖中每個頂點的度數(shù)最多是_________。5．設二叉樹中度數(shù)為0的結點數(shù)為50，度數(shù)為1的結點數(shù)為30，則該二叉樹中總共有_______個結點數(shù)。6．設F和R分別表示順序循環(huán)隊列的頭指針和尾指針，則判斷該循環(huán)隊列為空的條件為_____________________。7．設二叉樹中結點的兩個指針域分別為lchild和rchild，則判斷指針變量p所指向的結點為葉子結點的條件是_____________________________________________。8．簡單選擇排序和直接插入排序算法的平均時間復雜度為___________。9．快速排序算法的空間復雜度平均情況下為__________，最壞的情況下為__________。10.散列表中解決沖突的兩種方法是_____________和_____________。三、判斷題（每題2分，共20分）1．調用一次深度優(yōu)先遍歷可以訪問到圖中的所有頂點。（）2．分塊查找的平均查找長度不僅與索引表的長度有關，而且與塊的長度有關。（）3．冒泡排序在初始關鍵字序列為逆序的情況下執(zhí)行的交換次數(shù)最多。（）4．滿二叉樹一定是完全二叉樹，完全二叉樹不一定是滿二叉樹。（）5．設一棵二叉樹的先序序列和后序序列，則能夠唯一確定出該二叉樹的形狀。（）6．層次遍歷初始堆可以得到一個有序的序列。（）7．設一棵樹T可以轉化成二叉樹BT，則二叉樹BT中一定沒有右子樹。（）8．線性表的順序存儲結構比鏈式存儲結構更好。（）9．中序遍歷二叉排序樹可以得到一個有序的序列。（）10.快速排序是排序算法中平均性能最好的一種排序。（）四、算法設計題（每題10分，共30分）設計在順序有序表中實現(xiàn)二分查找的算法。設計判斷二叉樹是否為二叉排序樹的算法。在鏈式存儲結構上設計直接插入排序算法。《數(shù)據(jù)結構》模擬試題09參考答案一、單項選擇題（每題2分，共30分）1．D 2．A 3．A 4．A