2019-2020(1)數據結構B卷 - 副本

B)B)head=NULLD)head!=NULL江酉理工大學考試試卷試卷墻號， (A、B、C),共3大題2019_-2020學年第1學期課程名稱： 費建構考試性質：［正考/補考］考試方式：［開卷/閉卷］適用專業(yè)班級: 考試時間： 年 月 日時段 (100徹)溫馨提示本試卷的所有解答均應寫在答題紙的指定位置，否則無效。一、 選擇題(共10小題，每小題3分，共計30分)1、 下面程序片段的時間復雜度是 .X=2;while(x<n/2)x=2?x;OClo&n)B)0(n)C)0(nlog?n)D)0(n32、 在雙鏈表中向p所指的結點之前插入一個結點q的操作是 ?p->prior=q;q->next=p;p->prior->next=q;q->prior=p->prior;q->prior=p->prior:p->prior->next=q:q->next=p;p->prior=q->next:q->next=p;p->next=q;q->prior->next=q;q->next=p;p->prior->next=q;q->next=p;q->prior=p->prior;p->prior=q;3、 對于一個頭指針為head的不帶頭結點的單鏈表，判定該表為空的條件是—?A)head->next=NULLC)head->next=head4、 若元素a,b,c,d,e,f依次進棧，允許進棧、出棧操作交替進行，則不可能得到的出棧序列是 ?A)fedcbaB)bcafedC)dcefbaD)cabdef5、 若一棵二叉樹的前序遍歷序列和后序遍歷序列分別為1,2,3,4和4,3,2,1則該二叉樹的中序遍歷序列不會是 ?A)1,2,3,4B)2,3,4,1C)3,2,4,1D)4,3,2,16、 若X是后序線索二叉樹中的葉子結點，且X存在左兄弟結點Y,則X的右線索指向的是 ?A)X的父結點 B)以Y為根的子樹中最左下結點0X的左兄弟結點Y D)以Y為根的子樹中最右下結點7、 將森林F轉換為對應的二叉樹T,F中葉子結點的個數等于 ?A)T中葉子結點的個數 B)T中度為1的結點個數0T中左孩子指針為空的結點個數 D)T中右孩子指針為空的結點個數8、 以下關于圖的敘述中，正確的是 ?強連通有向圖的任何頂點到其他所有頂點都有弧圖的任意頂點的入度等于出度0有向完全圖一定是強連通有向圖D)有向圖邊集的子集和頂點集的子集可構成原有向圖的子圖9、 無向圖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)acfdebB)aebdfcC)aedfcbD)abecdf10、 以下敘述中正確的是 ?只要無向流通圖中沒有權值相同的邊，則其最小生成樹唯一只要無向圖中有權值相同的邊，則其最小生成樹一定不唯一三、綜合題（共5小題，每小題10分，共計50分）1三、綜合題（共5小題，每小題10分，共計50分）1、 設L為帶頭結點的單鏈表，編寫算法實現從尾到頭反向輸出每個結點的值。2、 設計算法求二叉樹的深度。template<classDataType>intBiTree<DataType>::Depth（BiNode<DataType>奉bt）｛D）連通圖G有n個頂點，含有n個頂點n-1條邊的子圖一定是G的生成樹二、填空題（共10小題，每小題2分，共計20分）1、 對于順序表，在第i個位置插入一個元素的時間復雜度為 。2、 在長度為n的順序表中刪除第i（IWiWn）個元素時，需要向前移動 個元素。3、 元素a,b,c,d,e依次進入初始為空的棧中，若元素進棧后可停留、可出棧，3、 對給定的一組權值W=（5,2,9,11,8,3,7）,試構造相應的哈夫曼樹，并計算它的帶權路徑長度。3、 對給定的一組權值W=（5,2,9,11,8,3,7）,試構造相應的哈夫曼樹，并計算它的帶權路徑長度。4、 寫出下面二叉樹的前序、中序和后序序列，并把它轉換為森林。4、 設棧初始為空，將中綴表達式a*b+（cT/e）*f轉為后綴表達式的過程中，當掃描到e時，運算符棧中的元素依次（棧頂至棧底）是 ?5、 在一棵度為4的樹T中，若有20個度為4的結點，10個度為3的結點，1個度為2的結點，10個度為1的結點，則樹T的葉子結點個數是 ―.6、 已知一棵完全二叉樹的第6層（設根為第1層）有8個葉子結點，則該完全二叉樹的結點個數最少是 .7、 若對右圖所示的二叉樹進行中序線索化，則結點X的右線索指向的結點是 ?5、設無向圖G=（V,E）的鄰接矩陣存儲如圖所示，畫出圖G及其鄰接表存儲（邊表序號從小到大排列，頂點以數字1,2,3,4,5表示）。85、設無向圖G=（V,E）的鄰接矩陣存儲如圖所示，畫出圖G及其鄰接表存儲（邊表序號從小到大排列，頂點以數字1,2,3,4,5表示）。9、 一個有28條邊的非連通無向圖至少有 個頂點。010101010110、 一個具有n個頂點的無向連通圖，其邊數至少為 。0101010101答題紙第答題紙第I ■共2頁，閱卷 江酉理工大學考試試卷答題紙試卷編號， (A，閱卷 江酉理工大學考試試卷答題紙試卷編號， (A、B、C),共_ 大題2019 2020學年第1學期考試性員：［正考/補考］課程名稱:數據結構考試方式：［開卷/閉卷］溫V請考生自覺遵守考試乜律，爭做文明誠卡照《江西理工大學學生違紀處分規(guī)定〉處理。E示f的大學生。如有違犯考試乜律，將尸格按題號—二三總分得分一、選擇題（共10小題，每小題3分，共30分）。得分 ，閱者 二、填空題（共10小題，每小題2分，共計20分）。得分 ,閱卷 10(n)6392n-i7A348694/-(+9958210n-1三、綜合題(共5小題，每小題10分，共計50分)。得分 說明：可在反面作答?1〃參見實驗指導P23算法2-4template<classDataType>voidLinkList<DataType>::Reverse()(Node<DataType>”=first->next;Node<DataType>*pre=NULL;Node<DataType>*r=NULL;while(p!=NULL)(r=p->next:p->next=pre;pre=p；P=r;)first->next=pre;PrintListO；)〃頭插法，參見實驗指導P25算法2-6template<classDataType>voidLinkList<DataType>::Reversel0(Node<DataType>*p=first->next;first->next=NULL;Node<DataType>*u=NULL;while(p!=NULL)(答題紙第答題紙第2頁，共2頁u=p->next;p->next=first->next;first->next=p;P=u;}PrintList();2template<classDataType>intBiTree<DataType>::Depth(BiNode<DataType>*bt)(if(!bt)returnO;//bt=