數(shù)據(jù)結(jié)構(gòu)課后習(xí)題部分參考答案(編輯修改稿)
2025-07-19 21:25 本頁面
【文章內(nèi)容簡介】 odenum1(rootrchild)。 }}第二種方法（不用全局變量）：求結(jié)點數(shù)的遞歸定義為： 若為空樹，結(jié)點數(shù)為0 若只有根結(jié)點，則結(jié)點數(shù)為1； 否則，結(jié)點數(shù)為根結(jié)點的左子樹結(jié)點數(shù)+右子樹結(jié)點數(shù)+1int nodenum2(BiTree root) { if(root==NULL) return 0。 else return (1+nodenum2(rootlchild)+nodenum2(rootrchild))。 }第六章一、選擇題1．B 3. B 4. C 5.(1) B (2) D 7. B 10. B二、判斷題1．╳ 2． ∨ 3．∨ 4．╳ 7．∨ 9. ╳ 11．╳ 12．∨三、簡答題1.(1) 每個頂點入度和出度： ID(v1)=2 OD(v1)=1 ID(v2)=2 OD(v2)=2 ID(v3)=1 OD(v3)=3 ID(v4)=3 OD(v4)=0ID(v5)=2 OD(v5)=3 ID(v6)=1 OD(v6)=2(2) 鄰接矩陣：0 0 0 1 0 0 1 0 1 0 0 0 0 0 0 1 1 1 0 0 0 0 0 0 1 1 0 1 0 0 0 1 0 0 1 0(3) 鄰接表：13∧ ∧4∧ ∧1236∧ ∧544∧54∧ ∧2165∧ ∧22.(1)0 1 1 0 0 0 0 1 0 0 1 0 0 0 1 0 0 1 0 0 0 0 1 1 0 1 1 0 0 0 0 1 0 0 1 0 0 0 1 0 0 1 0 0 0 0 1 1 03∧ ∧2 ∧(2)V14∧ ∧1 ∧V2V34∧ ∧1 ∧V46∧ ∧5 ∧3 ∧2 ∧V57∧ ∧4 ∧V67∧ ∧4 ∧V76∧ ∧5 ∧(4)v1,v2,v4,v3,v5,v7,v6(5)v1,v2,v3,v4,v5,v6,v7，矩陣元素的個數(shù)與頂點個數(shù)有關(guān)（矩陣元素的個數(shù)是頂點個數(shù)的平方），與邊的條數(shù)無關(guān)（矩陣中非零元素的個數(shù)與邊的條數(shù)有關(guān)）。四、算法設(shè)計題8．（1） int PATHDFS(ALGraph *G，int i,int j){ //以鄰接表為存儲結(jié)構(gòu)，判斷vi和vj之間是否有路徑，若有返回1，否則返回0 EdgeNode *p； visited[i]=TRUE； //標(biāo)記vi已訪問 p=Gadjlist[i].firstedge； //取vi邊表的頭指針 while(p){//依次搜索vi的鄰接點vk，這里k=padjvex if （!visited[padjvex])//若vk尚未被訪問 if (padjvex==j) return 1。 else ruturn PATHDFS(g，padjvex,j)。//則以Vk為出發(fā)點向縱深搜索 p=pnext； //找vi的下一鄰接點 } return 0?！ //PATHDFS（2） int BFS(ALGraph *G，int i,int j) {//以鄰接表為存儲結(jié)構(gòu)，判斷vi和vj之間是否有路徑，若有返回1，否則返回0 int i； CirQueue Q； //須將隊列定義中DataType改為int EdgeNode *p； InitQueue(amp。Q)；//隊列初始化 visited[i]=TRUE； EnQueue(amp。Q，i)；//vi已訪問，將其人隊。（實際上是將其序號人隊） while(!QueueEmpty(amp。Q)){//隊非空則執(zhí)行 i=DeQueue(amp。Q)； //相當(dāng)于vi出隊 p=Gadjlist[i].firstedge； //取vi的邊表頭指針 while(p){//依次搜索vi的鄰接點vk(令padjvex=k) if(!visited[padjvex]) //若vk未訪問過 if (padjvex==j) return 1?！ lse{ visited[Padjvex]=TRUE； EnQueue(amp。Q，padjvex)； }//訪問過的vk人隊 p=pnext；//找vi的下一鄰接點 }//endwhile }//endwhile return 0。 }//end of pathBFS10．void ShortestPath(ALGraph *G,int P[ ],int D[ ]) { int final[MaxVerNum],i,j,k,min。 EdgeNode *s。 final[0]=1。 /* 初始時集合S中只有0號頂點 */ D[0]=0。 P[0]=1。 /* 0號頂點 無前驅(qū)頂點 ，用1表示 */ for(i=1。iGn。i++) { final[i]=0。 D[i]= INFINIT
法律信息相關(guān)推薦
鄂ICP備17016276號-1