20132014學年第2學期課程考試〔A〕卷題號得分閱卷一題號得分閱卷一二三四五六七八九十總分〔2×15=30〕大題得分胡春玲共5頁，第1大題得分胡春玲共5頁，第1頁A、只允許在端點處插入和刪除元素B、都是先進后出C、都是先進先出D、沒有共同點以下數(shù)據(jù)構造中哪一個是非線性構造？( )A、隊列 B、棧 C、線性表 D、二叉樹下面程序的時間簡單為〔 。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) C、O(n3) D、O(n4)在一個單鏈表中，q結點是p結點的前趨結點，假設在q和p之間插入s結點，則須裝執(zhí)行〔。訂 A．s->next=p->next; p->next=s B．q->next=s; C．p->next=s->next; s->next=p D．p->next=s; 線5.設一組初始記錄關鍵字序列為(45，80，55，40，42，85)，則以第一個記錄關鍵字45為基準而得到一趟快速排序的結果是〔 。A、40，42，45，55，80，83 B、42，40，45，80，85，88C、42，40，45，55，80，85 D、42，40，45，85，55，80設一個有序的單鏈表中有n個結點現(xiàn)要求插入一個結點后使得單鏈表仍舊保持有序，則該操作的時間簡單度為〔 。A、O(log2n) B、O(1) C、O(n2) D、O(n)設有6個結點的無向圖，該圖至少應有( 一個連通圖。A、5 B、6 C、7 D、8圖G中的邊集E={(a，b)，(a，e)，(a，c)，(b，e)，(e，d)，(d，f)，(f，c)}，則從頂點a動身可以得到一種深度優(yōu)先遍歷的頂點序列為〔 。A、abedfc B、acfebd C、aebdfc D、aedfcb是()。A、8 B、3 C、5 D、9設用鄰接矩陣A表示有向圖G的存儲構造，則有向圖G中頂點i的入度為〔 。和 C、第i行0元素的個數(shù)之和 設指針變量top指向當前鏈式棧的棧頂，則刪除棧頂元素的操作序列為〔 。命題教師A、top=top+1 B、top=top-1 C、top->next=top;D、top=top->next二叉樹的第K層的結點數(shù)最多為( A、2k-1 B、2K+1 C、2K-1+1 D、2k-113.設有向無環(huán)圖G中的有向邊集合E={<1，2>，<2，3>，<3，4>，<1，4>}，則以下屬于該有向圖G的一種拓撲排序序列的是〔 。A、1，2，3，4 B、2，3，4，1 C、1，4，2，3 D、1，2，4，3則由這組記錄關鍵字生成的二叉排序樹的深度為〔 。A、4 B、5 C、6 D、7圖的深度優(yōu)先遍歷類似于二叉樹的( 大題得分A.先序遍歷 B.中序遍歷 C.后序遍歷 二、填空題〔2分×10=20分〕大題得分設挨次線性表中有n個數(shù)據(jù)元素，則在第i個位置上插入一個數(shù)據(jù)元素需要移動表中數(shù)據(jù)元素個數(shù)是 。設指針變量p指向單鏈表中結點A，指針變量s指向被插入的結點X，則在p后進展插入操作的語句序列為〔 ; 〔設結點的指針域為nex的結果的是 。GnAij互為鄰接點的條件是 。最多需要比較 次。組初始記錄關鍵字序列(k1，k2，……，kn)是小根堆，則對i=1，2，…，n/2而言滿足的條件為 。下面程序段的功能是實現(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);}大題得分樹承受 遍歷法。大題得分〔5×5=25〕小題得分1T中邊的集合為{(A，B)，(A，C)，(A，D)，(B，E)，(C，F(xiàn))，(C，G)}，要求用孩子兄弟表示法〔二叉鏈表〕表示出該樹的存儲構造并將該樹轉(zhuǎn)化成對應的二叉樹。小題得分共共5頁，第2頁小題得分2．請畫出以下圖的鄰接矩陣和鄰接表。小題得分裝 小題得分訂 出構造過程。小題得分線 小題得分小題得分55頁，第3 頁小題得分5ABCDEFGHIJ和中序序列是CDBFEAIHGJ,請畫出該樹。小題得分大題得分〔12分〕大題得分小題得分1、LinkListmynote(LinkListL) 〔7分〕小題得分if(L&&L->next){q=L；L=L－>next；p=L；S1： while(p－>next)p=p－>next；S2： }return L；}請答復以下問題：〔1〕S1的功能?！?〕S2的功能?！?〕設鏈表表示的線性表為〔a1,a2,…,an〕,寫出算法執(zhí)行后的返回值所表示的線性表。小題得分2．voidABC(BTNode*BT) 〔5分〕小題得分{if BT{ABC