百度実習ペン試験問題解析(3-5問題)(2012.05.06)

3.cとc++はそれぞれどのようにメモリを動的に割り当てて解放しますか?どんな違いがありますか?
cはmallocとfree、c++はnewとdeleteで、違いは以下の通りです:(1)new、deleteはオペレータで、リロードでき、C++でしか使用できません.(2)malloc,freeは関数であり,上書き可能であり,C,C++ともに使用可能である.(3)newはオブジェクトのコンストラクション関数を呼び出し,対応するdeleteは対応するコンストラクション関数を呼び出す.(4)mallocはメモリのみを割り当て,freeはメモリのみを回収し,構造解析関数を実行しない(5)new,deleteは何らかのデータ型ポインタ,malloc,freeはvoidポインタを返す.
4.ページ爬虫類、すなわち、1つのページから、ページのすべてのurlサイトを検索し、これらのurlに入り、ある時点で接続されたり、空白のページに戻ったりするまでループします.これらの接続urlを一つ一つ接続します.簡単にするために、各ページにurlが1つしかないと仮定し、2つのページエントリから上記の操作を行うと、2つの一方向チェーンテーブルが形成される.この2つの爬虫類に同じurlがあるかどうかを判断してください.
【プログラミングの美233-235ページ】
実はこれは変相の質問で、2つの一方向チェーンテーブルが交差しているかどうかです.私は2つの考え方があります.1つは、2つの独身チェーンテーブルが交差している場合、交差ノードから、後ろのノードがチェーンテーブルの末尾まで完全に重なります(これは自分で描くことができます.一方向チェーンテーブルですから).したがって,2つのポインタでそれぞれ2つのチェーンヘッダノードを指し,先頭ノードからチェーンテーブルの末尾を指すまで順次後ろに進み,2つのポインタが同じノードを指しているかどうかを判断し,もしそうであれば同じurlがある. 
構想2:一方のチェーンテーブル(L 1)の末尾を他方のチェーンテーブル(L 2)のヘッダノードに向け、その後、L 1のヘッダノードから各ノードを後方に遍歴し、アクセスしたタグを残す.交差があると必ずリングが形成されるので、リングが検出されると同じurlがあることを示します. 
5.配列al[0...num-1]は、2つの部分、al[0...mid-1]およびal[mid...num-1]に分けることができ、これらの2つの部分はそれぞれ秩序化されている.配列の2つの部分merge(マージ)を全体的に秩序化された配列にし、空間の複雑さをO(1)にしてください.
ダイレクトコード

void merge(int a[], int left, int right, int x, int y)
{
	int i = 0, j = x, k;
	while (1) {
		if (a[i] > a[j]) {
			swap(a[i], a[j]);
			int t = a[j];
			for (k = j + 1; k <= y; ++k) {
				if (a[k] < t) {
					a[k - 1] = a[k];
				} else {
					a[k - 1] = t;
					break;
				}
			}
		}
		++i;
		if (i == x + 1) break;
	}
}