問答題

【簡答題】
A和B是長度為n的兩個數(shù)組。設計一個算法，該算法輸出長度為n的數(shù)組C，要求：
（1）數(shù)組C中的每一個元素C[i] = || {A[j]| A[j]≤B[i]， 1≤j≤n} ||，其中||S||表示集合S中的元素個數(shù)。例如：下表給出了長度為4的兩個數(shù)組A和B，以及滿足要求的數(shù)組C；
（2）所設計算法盡可能高效。

（1）描述算法的基本設計思想；
（2）用算法描述語言描述算法。
（3）給出算法的時間復雜性分析。

答案：

你可能感興趣的試題

【簡答題】
設高度為h的二叉樹上只有度為0和度為2的結點，則此類二叉樹中所包含的結點數(shù)至少為（2h-1 ）。已知一個帶有表頭結點的單鏈表，結點結構為（data， link）。假設該鏈表只給出了頭指針list。在不改變鏈表的前提下，請設計一個盡可能高效的算法，查找出鏈表中倒數(shù)第k（k為正整數(shù)）個位置上的結點。若查找成功，算法輸出該結點的data域的值，并返回1；否則，只返回0。要求：
（1）描述算法的基本設計思想；
（2）用算法描述語言描述算法；
（3）給出算法的時間復雜性分析。

答案：

算法的基本思想如下：

【簡答題】
試給出二叉樹的自下而上、自右而左的層次遍歷算法。
1）給出算法的基本設計思想；
2）用算法描述語言描述算法，并要求對算法中的關鍵步驟給出注釋。

答案：

1）借助棧，最后彈出棧中元素實現(xiàn)對二叉樹按自下至上，自右至左的層次遍歷。