目錄

7-66 按層遍歷二叉樹

7-67 折紙

7-68 n以內素數個數

7-69 尋找第k小的數

---

7-66 按層遍歷二叉樹

用先序和中序序列構造一棵二叉樹（樹中結點個數不超過10個），通過用隊記錄結點訪問次序的方法實現對二叉樹進行按層遍歷，即按層數由小到大、同層由左到右輸出按層遍歷序列。

輸入格式:

第一行輸入元素個數

第二行輸入先序序列，以空格隔開

第三行輸入中序序列，以空格隔開

輸出格式:

輸出此二叉樹的按層遍歷序列，以空格隔開，最后也有一個空格。

輸入樣例:

5 10 20 40 30 50 20 40 10 50 30

輸出樣例:

10 20 30 40 50

答案：

#include <bits/stdc++.h> #include <unordered_map>using namespace std;const int N = 40; int n; int preorder[N],inorder[N]; queue<int> level_q,post_q; unordered_map<int,int> l,r,pos;int build (int pl,int pr,int il,int ir) {int root = preorder[pl];int k = pos[root];if (k>il)l[root] = build (pl+1,pl + k - il,il,k-1) ;if (k<ir)r[root] = build (pl+k-il+1,pr,k+1,ir);return root; }void levelorder (int root) {level_q.push(root);while (!level_q.empty()) {cout << level_q.front() << " ";int t = level_q.front();if (l.count(t))level_q.push(l[t]);if (r.count(t))level_q.push(r[t]);level_q.pop();} }void postorder (int root) {int t = root;if (l.count(t))postorder(l[t]);if (r.count(t))postorder(r[t]);post_q.push(root); }int main () {cin >> n;for (int i = 0 ; i < n ; i ++ )cin >> preorder[i];for (int i = 0 ; i < n ; i ++ ){cin >> inorder[i];pos[inorder[i]] = i;}int root = build (0,n-1,0,n-1) ;levelorder(root);return 0; }

7-67 折紙

喜歡折紙和數學的汪汪發現了一個可以同時進行折紙和數學的游戲。只需在大小為N×N的彩色紙的每個單元格中記下數字，并在每次將彩色紙對折時將重疊部分單元格的數兩兩相加。不斷重復這個過程，直到彩紙不能再折疊時，最終剩余的數字是多少。

下面的示例詳細說明了上述使用?2×2?彩色紙進行的游戲過程。

彩紙正好對折一半，從左到右。

將兩個重疊單元格上的數字兩兩相加。上圖中，兩個單元格（1,1）和（1,2）重疊，兩個單元格（2,1）和（2,2）也重疊。

在(1,1)單元格上寫下(1,1)和(1,2)上兩個數相加的值。
在(2,1)單元格上寫下(2,1)和(2,2)上兩個數相加的值

彩紙再對折一半，從底部到頂部。（此時對折后，彩紙無法再對折）。

將兩個重疊單元格中的數字相加。在上圖中，兩個單元格?(1,1)?和?(2,1)?重疊。

在(1,1)單元格上寫下(1,1)和(2,1)上兩個數相加的值。

重復上述過程，直到彩紙不能折疊為止，求最后剩下的數字。

輸入格式:

第一行給出一個整數N?表示彩紙的寬度和長度。

從第二行到最后一行給出了大小為N×N?的彩紙上每個單元格上的數字K，

1≤K≤105

N=2m,1≤m≤10

輸出格式:

當重復在將彩紙對折的同時重疊部分單元格上數字相加的過程時，輸出最后剩余的數字。

輸入樣例:

4 2 6 5 4 1 5 7 6 9 8 8 7 1 4 7 8

輸出樣例:

88

當不斷的折疊時，最終剩余的數字為88

輸入樣例:

2 1 2 3 4

輸出樣例:

10

答案：

#include<stdio.h> int main() {long long int n,sum=0;scanf("%lld",&n);int a[n][n];for(int i=0;i<n;i++) {for(int j=0;j<n;j++) {scanf("%lld",&a[i][j]);sum+=a[i][j];}}printf("%lld",sum);return 0; }

7-68 n以內素數個數

請統計出n以內所有的素數個數。

輸入格式:

請給出最大整數以內的一個數字n。

輸出格式:

輸出n以內素數的個數。

輸入樣例:

在這里給出一組輸入。例如：

1000

輸出樣例:

在這里給出相應的輸出。例如：

168

答案：

#include<stdio.h>int n,ans;char a[100000005]; int main() {scanf("%d",&n);a[1]=1;for(int i=2;i*i<=n;i++){if(a[i]==0){for(int j=i*i;j<=n;j=j+i){a[j]=1;}}}for(int i=1;i<=n;i++){if(a[i]==0)ans++;}printf("%d\n",ans);return 0; }

7-69 尋找第k小的數

給定若干整數，請設計一個高效的算法，確定第k小的數。

輸入格式:

測試數據有多組，處理到文件尾。每組測試數據的第1行輸入2個整數n，k（1≤k≤n≤1000000）。第2行輸入n個整數，每個數據的取值范圍在0到1000000之間。

輸出格式:

對于每組測試，輸出第k小的數。

輸入樣例:

5 3 1 2 2 2 1 9 3 1 2 3 4 5 6 9 8 7

輸出樣例:

2 3

提示:

如果提交后超時，請注意需要設計的是高效的算法！如果你初學《數據結構》，暫時設計不出來，請學完相關知識再回頭來做。
也可以使用STL之sort、nth_element函數求解。
另外，由于輸入數據特別多，為減少輸入數據的耗時，建議使用以下的輸入外掛函數：

void scan_d(int &num) {char in;in=getchar();while(in<'0'||in>'9') in=getchar(); num=in-'0';while(in=getchar(),in>='0'&&in<='9'){num*=10,num+=in-'0';} }

調用方法如下：

int n; scan_d(n);

答案：

#include<iostream> #include<cstdio> using namespace std; void quickSort(int *arr,int begin,int end) {int temp=arr[begin];if(begin<end){int i=begin,j=end;while(i<j){while(i<j&&arr[j]>temp){j--;}arr[i]=arr[j];while(i<j&&arr[i]<=temp){i++;}arr[j]=arr[i];}arr[i]=temp; // for(int k=begin;k<=end;k++){ // cout<<arr[k]<<" "; // } // cout<<endl; quickSort(arr,begin,i-1);quickSort(arr,i+1,end);}else{return;} } int main() {int n,k;int num[1000005];while(cin>>n>>k){for(int i=0;i<n;i++){scanf("%d",&num[i]);}quickSort(num,0,n-1);cout<<num[k-1]<<endl;} }

總結

以上是生活随笔為你收集整理的数据结构66-69的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。