一、選擇：(每題2分，共30分 簡單選擇排序冒泡排序歸并排序穩(wěn) ）是穩(wěn)定的。堆排序排序快速排序基數(shù)排序不穩(wěn)A)堆排序，冒泡排 B)快速排序，堆排C)直接選擇排序，排 D)歸并排序，冒泡排 堆排 C)排 312345，則下列序列中不可能是棧的輸出序列的是（2341 B)5413 C)2314 D)15434、非空循環(huán)鏈表head的尾結(jié)點*p滿足下列 A)head->next==p;B)head==p;C)p->next==head;D)p- 6、對于哈希函數(shù)H(key)=key%7,被稱為同義詞的關(guān)鍵字是 A)36和 C)15和 A) B)n- C) D)n- A. B. C. D.9、高度為K的二叉樹最大的結(jié)點數(shù)為 C)2k- D)2k-1- A)(n- B)C) D) 12、已知有向圖的正鄰接鏈表的結(jié)構(gòu)如下，從頂點1出發(fā)的按深度優(yōu)先遍歷序列是()A)123 142 132 D)143 413front,rear，則隊列中元素個數(shù)為()（maxlenA)(rear-front+maxlen)%maxlenB)(rear-front)%C)rear-front+1D)front-14n（深度）是（ D)logn- A)插入 B)冒泡 C)二路歸并 D)快速排序二、填空題：(每空2分，共20分) 個結(jié)點，則前序一定是3、利用篩選法將關(guān)鍵字序列(37，66，48，29，31，75)建成的大根堆為(756648293137 49的結(jié)點的孩子編號為 6AOEe(i)l(i)分別表示活動ai的最早開始時間和最晚開始時間，則當(dāng)且僅當(dāng) ai FORi:=1TOnDOFORj:=iTOnDO 后 9、在有序表A[1..12]中，采用二分查找算法查等于A[12]的元素，所比較的元素下標依次 691110、n個頂點的連通無向圖，其邊的條數(shù)至少為 三、解答題：(每題6分，共30分)1、已知一棵二叉樹的前序掃描序列和中序掃描序列分別為CDFHJ和CDFHJG，試給出該二叉樹的2、已知一棵二叉樹的前序序列和中序序列分別為abdghcefigdhbaecif,請畫出該二叉樹。 I(I為f左e為葉子AB1CDEFAB1CDEF FDC5、指定Hash函數(shù)H(k)=3*kmod11及線性探測開地址法處理，試在0~10的散列空間中對關(guān)鍵字序列0123456789四、算法題：(1020分1stintSimilar(BiTreep,q)//判斷二叉樹pq是否相{if(p==null&&q==null)return(1);elseif(!p&&q||p&&!q)return(0);elsereturn(Similar(p->lchild,q->lchild)&&Similar(p->rchild,q-}//結(jié)束A無HB無IECJID8BKF、EC、LH、J、FBMLGE12345678900一、選擇：(230分 C)最長回 4、非空循環(huán)鏈表head的尾結(jié)點p滿足下列 A.head->next==p B.head==p C.p->next==head D.p->next==nil7、將一個長度為n的向量的第i個元素刪除時，需要前移( A) B)n- C) D)n- )A) B)p→next→next:= D)s→next:=p→next; 12、從下列有關(guān)樹的敘述中,選出正確的敘述（五、填空題：(220分)1、樹中結(jié)點的最大層次稱為樹的高度或深 六、解答題：(630分1n個結(jié)點的K（k>=2)K2abdghcefigdhbaecif,請畫出該二叉樹。 I(I為f左e為葉子3(46,79,56,38,40,84),則利用快速排序的方法,分別寫出以第一個記錄為基準得到的前三4038465679 3840465679 384046567901∞4∞0923508∞∞60AV1->v21->v44^V2->v39->v4V3->v13->v25->v88^V4->v36->v40^5 AVL插入22

插入4后 插入1后 七、算法題：(1020分11，H（key）為關(guān)鍵字（標識符）的第一個字母在字母表中的序號，voidPrint_Hash(HashTableH)//按第一個字母順序輸出Hash表中的所有關(guān)鍵字,1voidPrint_Hash(HashTableH)//按第一個字母順序輸出Hash表中的所有關(guān)鍵字,其中處理采用線性探測開放定{for(j=i;H.elem[j].key;j=(j+1)%hashsize[sizeindex線性探測if(H(H.elem[j].key)==i)printf("%s\n",H.elem[j]);intH(char*s)//Hash{if(s)returns[0]-96;//求關(guān)鍵一個字母的字母序號(小寫)elsereturn0;IntDeepth(PBiTNodeT)ReturnIntleft=Deepth(T->rchild);Intright=Deepth(T->rchild);If(left>right)returnleft+1;Elsereturnright+1;}選擇：(230分 5、A)插入 B)冒泡 C)二路歸并 D)快速排序八、算法題：(每題10分，共20分)1llinkdatarlinkP所指結(jié)點與其rlink2sqqueue1的循環(huán)順序隊列只用一個rearcount用于記錄隊列中的元素個數(shù)。編寫算法實現(xiàn)隊列的初始化、進隊、出隊、取隊頭元素操作。sqqueue1類型的循環(huán)順序隊#define elemtypdata[maxlen]; rear,count;九、算法題：(1020分1typedefstructDLNode{ElemTypedata;structDLNodeStatusSwapANode(DLNode*&P){if(!P||!(P->rlink))returnERROR;q=P->rlink;P->rlink=NULL;else{P->rlink=q->rlink;q->rlink->llink=}{q->llink=NULL;q->rlink=P;P->llink=}elseq->llink=P->llink;q->rlink=P;P->llink->rlink=q;P->llink=q;}return}2 } q, (q.count==maxlen)print(“overflow!”);else{} } } if else }}十、選擇：(230分 A)堆排 C)排 （1）8447251521（2）1547258421（3）1521258447(4）15212547則采用的排序是 )A)選 B)冒 C)快 D)插G=(V,E<V1,V3>,<V1,V4>,<V2,V5>,<V3,V5>,<V3,V6>,<V4,V6>,<V6,V7>},G（ A)下面的B，C，D都不對。 D)9，4，7，8，7，-1，15，20十一、算法題：(每題10分，共20分)VoidPostOrder（PBiTNodeT,(void*)(visit)char{Visit(T-}}13front,rear，則隊列中元素個數(shù)為()（maxlenA)(rear-front+maxlen)%maxl