[高等教育]考題解答0506年福建專升本數(shù)據(jù)結(jié)構(gòu)-在線瀏覽
2025-02-26 15:53本頁面
【正文】 1一個有 n 個結(jié)點 k 叉樹，樹中所有結(jié)點的度數(shù)之和是 __B__。 思路 2：正確的做法： 樹中所有結(jié)點的度數(shù)之和 =樹中所有邊條數(shù)， 每一條邊指向一個結(jié)點，每個結(jié)點有一條天線，指向父親結(jié)點，除了根結(jié)點之外。 解答：后序列表為 CEDBA，因此根是 A， 中序列 表為 CBEDA，因此根只有左子樹CBED，沒有右子樹 A / CEDB 后序，根是 B CBED 中序，左子樹 C，右子樹 ED A / B / \ C ED 后序 ED 中序 A / B / \ C D / E 1 N 個結(jié)點的有向圖，最多有 ___N*(N1)_____條邊。 1設(shè)有一個閉散列表的容量為 m，用線性探測法解決沖突，要插入一個鍵值，若插入成功，至多要進行______比較。 解答：哈夫曼樹沒有度為 1 的結(jié)點， 葉子數(shù) =內(nèi)結(jié)點數(shù) +1 結(jié)點總數(shù) =葉子數(shù) +內(nèi)結(jié)點數(shù) =2*葉子數(shù) 1 =2*內(nèi)結(jié)點數(shù) +1 1已知單鏈表的結(jié)點定義為 struct node{ int data。 }。 1已知雙鏈表結(jié)點定義為 struct node{ int data。 }。 對于隊列，只能在 __隊尾 ___插入元素，在 ___隊頭 ____刪除元素。 （ 2） 樹的度是 ______3_____。以第一個元素 90 作為基準元素，根據(jù)快速排序算法，寫出完成第一趟劃分后序列重新排列的情況。整數(shù)序列是 180、 160、 250、 300、 170、 1 12290、 380。要求依次畫出從頂點 1 出發(fā)的最小生成樹的生成過程。 typedef struct btnode *btlink。 btlink left。 }Btnode 解答：與 05 年考題不一樣 int f(指向樹根的指針 ){//f()計算樹中葉子節(jié)點的個數(shù) if(指向樹根的指針 ==NULL)return 0。 //左子樹中葉節(jié)點數(shù)； y= f(指向樹根的右孩子指針 )。amp。 else return x+y。amp。 else return x+y。 x=f(rootleft)。//右子樹中葉節(jié)點數(shù)； if(x==0amp。y==0)return 1。 } T(n)=1+T(n1)+T(n2) n1+n2=n =1+1+T(n11)+T(n12)+1+T(n21)+T(n22) n1=n11+n12 n2=n21+n22 2二叉樹以二叉表為存儲結(jié)構(gòu)，結(jié)點結(jié)構(gòu)的定義如下，請寫出一個求二叉樹的高度算法。 x=h(指向樹根的左孩子指針 )。//右子樹高度； if(xy)return x+1。 //return (xy?x:y) +1。試問它是什么方法實現(xiàn)的？并請完善程序。 define N 10 void bs(int a[],int x){ int l,r,m。r=N1。 while((_____l=r_______) amp。 (x!=a[m]) ){ if(xa[m]) l=_____m+1______。 m=(l+r)/2。 else printf(found)。 int x。 scanf(%d,amp。 bs(____a, x_______)。 A、 1 B、 2 C、 0 D、 3 在 n 個結(jié)點的順序表中，算法的時間復(fù)雜度都是O(1)的操作是 ( A )。 A、先進先出 B、后進后出 ? C、先進后出 D、不進不出 在棧中，出棧操作的時間復(fù)雜度為 ( A )。 A、 O(1) B、 0(logn) C、 0(n) D、 O(n*n) 如果二叉樹的葉結(jié)點數(shù)為 n0，則具有雙分支的結(jié)點數(shù) n2 等于 ( D )。現(xiàn)采用 ( B )遍歷方式就可以得到這棵二叉樹所有結(jié)點的遞增序列。 A、棧 B、隊列 C、樹 D、圖 廣度優(yōu)先遍歷類似于二叉樹的 ( D )。 A、 1／ 2 倍 B、 1 倍 C、 2 倍 D、 4 倍 1任何一個帶權(quán)無向連通圖的最小生成樹 ( B )。 A、 snext=p； pnext=s B、 pnext=s； snext=pn
試題試卷相關(guān)推薦
鄂ICP備17016276號-1