《算法與數(shù)據(jù)結(jié)構(gòu)》04級(jí)期末考試B卷

PAGEPAGE4一、填空題（每小題2分，共18分）1、數(shù)據(jù)的邏輯結(jié)構(gòu)在計(jì)算機(jī)中的基本存儲(chǔ)結(jié)構(gòu)有和。2、算法的時(shí)間復(fù)雜度取決于。3、隊(duì)列是的線性表，其操作數(shù)據(jù)的基本原則是。4、設(shè)有一個(gè)二維數(shù)組A[0…9][0…9]，若每個(gè)元素占2個(gè)基本存儲(chǔ)單元，A[0][0]的地址是200，若按列優(yōu)先（以列為主）順序存儲(chǔ)，則A[6][6]的存儲(chǔ)地址是。5、在高度為h的二叉樹(shù)的中只有度為0和度為2的結(jié)點(diǎn)，則該類二叉樹(shù)中所包含的結(jié)點(diǎn)數(shù)至少為。6、對(duì)于一個(gè)有n個(gè)頂點(diǎn)和e條弧的有向圖，若采用正鄰接鏈表存儲(chǔ)，則表頭向量的大小為，鄰接表中的結(jié)點(diǎn)總數(shù)為。7、若采用分塊查找，要求線性表塊內(nèi)，塊間。8、對(duì)于文件，按其記錄的類型可將文件分為文件、文件。9、外部排序的最基本方法是，其主要時(shí)間花費(fèi)在方面。二、單項(xiàng)選擇題（請(qǐng)將答案寫(xiě)在題目后的括號(hào)中。每題2分，共18分）1、下面程序段的時(shí)間復(fù)雜度是（）。for(i=1；i<=m；i++)for(j=1；j<=n；j++)A[i][j]=i+j;（A）O(m+n)（B）O(m)（C）O(n)（D）O(m*n)2、判斷一個(gè)循環(huán)隊(duì)列Q（最多元素個(gè)數(shù)為m）為滿隊(duì)列的條件是（）。（A）Q.front==Q.rear；（B）Q.front!=Q.rear；（C）Q.front==(Q.rear+1)%m；（D）Q.front!=(Q.rear+1)%m；3、設(shè)有一個(gè)棧頂指針為top的順序棧S，則將元素p壓入棧S中的操作是（）。（A）S[top++]=p；（B）S[++top]=p；（C）S[top--]=p；（D）S[--top]=p；4、廣義表((a),((b),c),(((d))))的長(zhǎng)度是，深度是。（）（A）3,4（B）3,3（C）4,3（D）4,45、在二叉樹(shù)中，指針P所指的結(jié)點(diǎn)是葉子結(jié)點(diǎn)的條件是（）。（A）P->Lchild!=NULL&&P->Rchild!=NULL；（B）P->Lchild!=NULL&&P->Rchild==NULL；（C）P->Lchild==NULL&&P->Rchild!=NULL；（D）P->Lchild==NULL&&P->Rchild==NULL；6、一棵二叉樹(shù)，其先序遍歷序列是abdghcefi，中序遍歷序列是bgdhaecfi，則其后序遍歷序列是()。（A）ghdbiefca（B）ghdbeicfa（C）ghdbeifca（D）gdheibfca7、若以{4,5,6,7,8}作為葉子的權(quán)值構(gòu)造Huffman樹(shù)(按左子樹(shù)根結(jié)點(diǎn)的權(quán)小于等于右子樹(shù)根結(jié)點(diǎn)的權(quán)的次序構(gòu)造)，則其帶權(quán)路徑長(zhǎng)度WPL為（）。（A）60（B）61（C）73（D）698、在無(wú)權(quán)圖G的鄰接矩陣中，若(Vi,Vj)或<Vi,Vj>屬于G的邊集，則對(duì)應(yīng)元素A[i][j]等于，否則等于。（）（A）1，1（B）1，0（C）0，1（D）0，09、設(shè)有一組記錄的關(guān)鍵字是（37，28，56，80，60，14，25，50），用快速排序法以第一個(gè)記錄為基準(zhǔn)得到的一次劃分結(jié)果是（）。（A）25，28，14，37，60，80，56，50（B）25，28，37，14，60，80，56，50（C）25，28，14，37，60，56，80，50（D）25，28，37，14，56，80，60，50三、分析題（每題6分，共30分）1、設(shè)有一棵樹(shù)如下圖，請(qǐng)先將此樹(shù)轉(zhuǎn)換為二叉樹(shù)，然后給出該二叉樹(shù)的前序線索樹(shù)和中序線索樹(shù)。2、已知某有向圖的逆鄰接鏈表如下圖所示，請(qǐng)先畫(huà)出該有向圖，然后給出其鄰接矩陣和正鄰接鏈表。40401231234538∧510∧18∧3424∧361952∧abdifchjeg3、將關(guān)鍵字序列（17，19，13，7，15，9，25）依此插入到初態(tài)為空的二叉排序樹(shù)中，請(qǐng)畫(huà)出建立二叉排序樹(shù)T的過(guò)程；然后畫(huà)出刪除13之后的二叉排序樹(shù)T1。4、線性表的關(guān)鍵字集合{21，25，28，19，42，57，15，43，17，36，49，27，65}，共有13個(gè)元素，已知散列函數(shù)為：H（k）=kMOD13，采用線性探測(cè)法處理沖突，請(qǐng)給出對(duì)應(yīng)的散列表結(jié)構(gòu)，并計(jì)算該表成功查找的平均查找長(zhǎng)度。5、已知數(shù)據(jù)序列為{35，29，22，16，17，9，38，27，13，45}，請(qǐng)給出采用選擇排序方法按非遞減要求進(jìn)行排序的過(guò)程。四、算法填空（每空2分，共20分）請(qǐng)?jiān)谙旅娓魉惴ǖ目瞻滋幪钌舷鄳?yīng)語(yǔ)句以實(shí)現(xiàn)算法功能。每個(gè)空白只能填一個(gè)語(yǔ)句。1、在以L為頭結(jié)點(diǎn)的雙向鏈表中刪除所有值為key的結(jié)點(diǎn)，結(jié)點(diǎn)結(jié)構(gòu)定義如下。typedefstructLnode{ElemTypedata;/*數(shù)據(jù)域，保存結(jié)點(diǎn)的值*/structLnode*prior;/*指針域，指向直接后繼*/structLnode*next;/*指針域，指向直接前趨*/}DULNode;/*結(jié)點(diǎn)的類型*/VoidDel_Node(DULNode*L，intkey){DULNode*q,*p=L–>next;while(p!=NULL){if(p–>data==key){q=p->next;if(p->next!=NULL){p->next->prior=p->prior;;}elsep->prior->next=NULL;;};}}2、設(shè)T是指向二叉樹(shù)根結(jié)點(diǎn)的指針變量，用非遞歸方法統(tǒng)計(jì)樹(shù)中葉子結(jié)點(diǎn)的數(shù)目。#defineMax_Node_Num50TypedefstructBTNode{ElemTypedata;/*數(shù)據(jù)域，保存結(jié)點(diǎn)的值*/structBTNode*Lchild,*Rchild;/*指針域*/}BTNode;/*結(jié)點(diǎn)的類型*/Voidcount_leaf_node(BTNode*T){BTNode*Stack[Max_Node_Num],*p=T,*q;inttop=0,leaf_num=0;/*leaf_num保存葉子結(jié)點(diǎn)的數(shù)目*/if(T==NULL)printf(“TheBinaryTreeisEmpty!\n”);else{do{if(p->Lchild==NULL&&p->Rchild==NULL);q=p->Rchild;if(q!=NULL);p=p->Lchild;}while();printf(“葉子結(jié)點(diǎn)的數(shù)目是:%d\n”,leaf_num);}}鏈表結(jié)點(diǎn)adjvexinfonextarc頂點(diǎn)結(jié)點(diǎn)鏈表結(jié)點(diǎn)adjvexinfonextarc頂點(diǎn)結(jié)點(diǎn)indegreedatafirstarcVoidcount_indegree(ALGraph*G){intk;LinkNode*p;for(k=0;k<G->vexnum;k++)G->adjlist[k].indegree=0;for(k=0;k<G->vexnum;k++){;while(p!=NULL){G->adjlist[p->adjvex].indegree++;;}}}4、H->R[s…m]中記錄關(guān)鍵字除H->R[s].key均滿足堆定義，調(diào)整H->R[s]的位置使之成為小根堆。VoidHeap_adjust(Sqlist*H,ints,intm){intj=s,k=2*j;/*計(jì)算H->R[j]的左孩子的位置*/H->R[0]=H->R[j];/*臨時(shí)保存H->R[j]*/for(k=2*j;k<=m;k=2*k){if((k<m)&&(H->R[k].key>H->R[k+1].key)k++;/*選擇左、右孩子中關(guān)鍵字的最小者*/