プログラマーの筆記試験問題--2012百度実習生の筆記試験問題


今日の筆記試験は6つの問題しかなく、最初の3つの簡単な答えは、最も基本的な問題です.2つのプログラムの設計問題、この2つの問題はまだ少し難しいです.一つのシステムの設計問題は、前のヒントを入力して、フロントで開発した子供紙を作ったことがあれば、きっとこれに接触したことがありますが、実は原理は簡単です.本題に戻ります.
一.ある辞書は、単語aを入力、辞書aのすべての兄弟単語を入力、兄弟単語の意味は、含まれるアルファベットとそのアルファベットの個数が同じである、例えばarmy出力maryなどである.
この問題はtrieツリーを使って解決しました.
まず、単語の中のすべてのアルファベットに基づいてtrieツリーを構築し、各ツリーと辞書の間を比較します.△今考えてみると、Trieの木ではこの問題を解決できない.ほほほ!前は自分の修練が足りないのを責めて、みんなを笑わせた.
昨夜、貼るのを見て、今も他の人の答えを以下のように抜粋しました.
1)各単語はchar[127]の配列に対応し,char[n]はアルファベットASCIIアルファベットnの出現回数を表し,検索時にmemcmpを効率的に比較することができる.
【このchar配列の大きさについては、主にASII表の上位127文字に対応するASII値が原因ですが、この値をどう計算するか分かりません.】
2),3)個案:1,勝手に5個のkeyを種々の変化+Hashで算出した個値でハッシュすればよい.2、同じく多段ハッシュ、先にA+keyハッシュを押して、もし衝突するならば2級ハッシュに入って、a+keyハッシュを使って、更に衝突してi+keyハッシュに入って、全部で4級で、5級は限界で、必ずハッシュを開けなければならなくて、前の4級はハッシュを閉じることができます.このような利点は,計算ハッシュが比較的速く,上位4レベルのメモリが静的であり,効率も高いことが明らかである.3、将来レベル別にログを閲覧したい場合は、難しくはありません.
二.cとc++がメモリを割り当てて解放する方法は何ですか?違いはどこですか.
これは主にcの中にmalloc/calloc/realoc/freeとC++のnew/deleteと彼らの違いを書いています.
malloc/calloc/reallocはいずれも割り当てメモリ空間であるが、違いはmallocが割り当て空間を割り当てた後、中のデータはランダムなデータであり、calloc空間内は0に初期化される.realloc:元の空間に空間を再申請します.今回の空間の大きさは元の空間より大きくなければなりません.freeは、これらの申請のメモリ領域を解放します.malloc/calloc/realloc/freeはライブラリ関数、new/deleteは演算子です.New/deleteは、オブジェクトを作成したり、オブジェクトを除去したりすることができます.メモリを動的に申請したり、メモリを解放したりすることができます.オブジェクトは作成時にコンストラクション関数を呼び出し、消滅時にコンストラクション関数を呼び出します.これらのmallocとfreeは操作できません.
三.プロセスとスレッドの違いと連絡?スレッドセキュリティの理解方法
次の答えはネット上を抜粋して、参考にします.
プログラムは命令のセットの秩序ある集合にすぎません
二プロセスは一定の独立機能を有するプログラムがあるデータ集合上の運行活動について、システムが資源の分配とスケジューリングを行う独立した単位である.
三スレッドはプロセスの実体であり、CPUのスケジューリングと割り当ての基本単位であり、プロセスよりも小さく独立して実行できる基本単位である.スレッド自体は基本的にシステムリソースを持たず、実行中に欠かせないリソース(プログラムカウンタ、レジスタのセット、スタックなど)を少ししか持っていません.1つのスレッドは別のスレッドを作成して取り消すことができます.
プロセスとスレッドの区別と連絡
(1)分割尺度:スレッドがより小さいため、マルチスレッドプログラムの同時性がより高い;
(2)資源配分:プロセスは資源配分の基本単位であり、同じプロセス内の複数のスレッドがその資源を共有する.
(3)アドレス空間:プロセスは独立したアドレス空間を持ち、同じプロセス内の複数のスレッドがその資源を共有する.
(4)プロセッサスケジューリング:スレッドはプロセッサスケジューリングの基本単位である.
(5)実行:各スレッドにはプログラム実行のエントリがあり、シーケンスとプログラムの出口を順番に実行するが、スレッドは単独で実行することはできず、プロセスを構成しなければならず、1つのプロセスには少なくとも1つのメインスレッドがある.簡単に言えば、1つのプログラムには少なくとも1つのプロセスがあり、1つのプロセスには少なくとも1つのスレッドがある.
四.題意分析の下で:2つのとても長い単鎖表、単鎖表を求めて最後に一緒に歩いたのではないでしょうか.
このテーマは相対的に簡単で、主にどのようにテーマの中の意味を掘り起こして、テーマはとても長い1段を言って、やった頭はすべて気絶して、何を言って百億、何を言ってhashを使うことができません.すべてあなたの考えを麻痺させて、最後に私が書いた題意です.簡単でしょう.最後にチェーンの2つのチェーンテーブルが交差しているかどうかを求めます!
考え方:
1)先に求めた2つのチェーンテーブルの長さをaとbと記す.
2)a>bを仮定すると、長さaのチェーンテーブルのポインタは先にa-bの長さで、それから2つのチェーンテーブルのポインタは同時に歩いて、中間に要素が同じであれば、交差を説明して、さもなくば交差しません!(a【後記】この問題かもしれないが、私の上の答えには考えが足りない.結局データが多くて、百億以上です.
五.1つの配列aは、前部分と後部分が秩序化する、空間的複雑度がO(1)の場合、配列a全体が秩序化される.
//    a,            ,       O(1)    ,      a  .

int main()
{
	int a[11]={1,2,3,4,8,5,7,9,12,32,34};
	for(int i=5;i<11;i++)
	{
		int temp=a[i];
		for(int j=i-5;j<i;j++)
		{
			if(a[j]>a[i])
			{
				while(j<i)
				{
					a[i]=a[i-1];
					i--;
				}
				a[j]=temp;
			}
		}
	}
	for(int k=0;k<11;k++)
		cout<<a[k]<<" ";
	return 0;
}

六.入力前にヒントを与える原理は何ですか?内部はどのように実現されていますか.時間の複雑さと空間の複雑さにもっと良い方法がありますか.
先端開発の子供紙を作ったことがあるので、このようなテーマに触れるに違いない.これがGoogleで有名な入力前のヒントです.この方面のソースコードはたくさんあります!ダウンロードしてみてください.もし疑問があれば、私は細かく説明して、へへ!
午前中ずっと走っていたので,疲れた.
今度の筆記試験は、あまりよくできていないような気がします.
自分にはまだまだ学ぶべきことがたくさんあります...
Fighting...
上の问题に対して、みんなはどんな良い解答の方式があって、伝言を忘れないで私に解答します!ほえ!