山東省常識題庫九
▲香菸
最早的香菸或紙菸，是在1799年由土耳其的士兵發明的。當時守衛亞克城的土耳其軍隊受到拿破崙炮兵的攻擊，士兵隊公用的水煙筒被炮彈擊毀。嗜煙如命的土耳其人就用點槍炮的火藥紙來捲菸葉。這樣就發明了香菸。
▲火柴
最初的火柴是由英國化學家約翰·華爾克發明的。在一次偶然的機會中，華爾克發現用砂皮紙摩擦氯化鉀和硫化銻的混合物能產生火焰。在1827年，華爾克出售第一盒氯化鉀和硫化銻做的火柴。當時每購買一盒火柴，免費奉送一塊砂皮紙。
▲紙幣
最早使用紙幣的國家是中國，時間約在公元九世紀。首次在歐洲使用的紙幣是1661年由瑞典銀行發行的，不過那時發行紙幣只是權宜之計，並不是作為真正的貨幣。在1694年，英格蘭銀行創立，開始發行銀單。銀單最初是手寫的，後來才改為印刷品。印刷的'銀單一經為公眾接受就成為真正的鈔票了。
▲聖誕樹
十六世紀，德國宗教改革的領袖馬丁·路德就在家中佈置了燃著蠟燭的聖誕樹。據說，馬丁·路德用蠟燭的光芒來象徵滿天的星斗。但是，早在古代，日耳曼人就把樹當作繁殖力的象徵而作為崇拜物。所以佈置聖誕樹的起源可能和日耳曼人這種風俗有關。至於用樅樹作聖誕樹則是因為這種樹的樹葉在冬天常綠，而且樹形象教堂的天頂。
▲三明治
三明治或稱夾肉麵包，是一種深受歡迎的簡便食物。三明治的發明者是一位伯爵。在十八世紀，英國的第四代三明治伯爵是一個嗜賭如命的賭鬼。他在時，甚至顧不得去吃飯。他往往叫家人準備幾片熟肉夾在兩片面包中，一面吃，一面賭。以後，以他名字命名的夾肉麵包——三明治就成為大眾食品了。
▲餐刀
17世紀以前，歐洲人用餐時還用銳利的匕首來切割食物。據說在17世紀時，法國的紅衣主教黎希留看見宴會上的群臣用匕首刀尖當牙籤，覺得很不雅觀。於是他下令把刀尖改成圓形。這樣就產生了現在西餐檯上的餐刀了。
山東計算機常識-二叉樹的儲存結構
二叉樹的遍歷
二叉樹的遍歷是指不重複地訪問二叉樹的所有結點。
在遍歷二叉樹的過程中，一般先遍歷左子樹，然後再遍歷右子樹。
1、前序遍歷（DLR）
所謂前序遍歷是指在訪問根結點、遍歷左子樹與遍歷右子樹這三者中，首先訪問根結點，然後遍歷左子樹，最後遍歷右子樹；並且，在遍歷左、右子樹時，仍然先訪問根結點，然後遍歷左子樹，最後遍歷右子樹。F，C，A，D，B，E，G，H，P
2、中序遍歷（LDR）
所謂中序遍歷是指在訪問根結點、遍歷左子樹與遍歷右子樹這三者中，首先遍歷左子樹，然後訪問根結點，最後遍歷右子樹；並且，在遍歷左、右子樹時，仍然先遍歷左子樹，然後訪問根結點，最後遍歷右子樹。A，C，B，D，F，E，H，G，P
3、後序遍歷（LRD）
所謂中序遍歷是指在訪問根結點、遍歷左子樹與遍歷右子樹這三者中，首先遍歷左子樹，然後遍歷右子樹，最後訪問根結點；並且，在遍歷左、右子樹時，仍然先遍歷左子樹，然後遍歷右子樹，最後訪問根結點。A，B，D，C，H，P，G，E，F
山東計算機常識-二分法查詢
二分法查詢只適用於儲存的有序表。在此所說的有序表是指線性表的中元素按值非遞減排列（即從小到大，但允許相鄰元素值相等）。
設有序線性表的長度為n，被查元素為x，則對分查詢的方法如下：
將x與線性表的中間項進行比較：
若中間項的值等於x，則說明查到，查詢結束；
若x小於中間項的值，則線上性表的前半部分（即中間項以前的部分）以相同的方法進行查詢；
若x大於中間項的值，則線上性表的後半部分（即中間項以後的部分）以相同的方法進行查詢。
這個過程一直進行到查詢成功或子表長度為0（說明線性表中沒有這個元素）為止。
顯然，當有序線性表為順序儲存時才能採用二分查詢，並且，二分查詢的效率要比順序查詢高得多。可以證明，對於長度為n的有序線性表，在最壞情況下，二分查詢只需要比較log2n次，而順序查詢需要比較n次。
