基礎(chǔ)數(shù)據(jù)類型

• short int 長(zhǎng)度為2字節(jié)

基礎(chǔ)存儲(chǔ)數(shù)據(jù)集：

1. 數(shù)組可以實(shí)現(xiàn)順序遍歷但是插入刪除操作復(fù)雜，平均移動(dòng)n/2個(gè)元素
2. 鏈表因?yàn)榇鎯?chǔ)的地址不連續(xù)（邏輯上連續(xù)實(shí)際上不連續(xù)），可以實(shí)現(xiàn)順序遍歷
3. 哈希表是隨機(jī)存儲(chǔ)，所以是離散分布，順序遍歷實(shí)現(xiàn)不了
4. 隊(duì)列只可以在隊(duì)尾插入隊(duì)頭刪除，不可以實(shí)現(xiàn)中間插入和刪除，不滿足條件

三維數(shù)組是層行列堆積

廣義表：

廣義表是n (n>=0)個(gè)元素a1,a2,a3,…,an的有限序列，其中ai或者是原子項(xiàng)，或者是一個(gè)廣義表。通常記作LS=（a1,a2,a3,…,an)。LS是廣義表的名字，n為它的長(zhǎng)度。若ai是廣義表，則稱它為L(zhǎng)S的子表。

折半查找：

• 算法條件：
  1.必須采用順序存儲(chǔ)結(jié)構(gòu)
  2.必須按關(guān)鍵字大小有序排列。
• 算法過(guò)程：
  首先，假設(shè)表中元素是按升序排列，將表中間位置記錄的[關(guān)鍵字]與查找關(guān)鍵字比較，如果兩者相等，則查找成功；否則利用中間位置[記錄](méi)將表分成前、后兩個(gè)子表，如果中間位置記錄的關(guān)鍵字大于查找關(guān)鍵字，則進(jìn)一步查找前一子表，否則進(jìn)一步查找后一子表。重復(fù)以上過(guò)程，直到找到滿足條件的[記錄](méi)，使查找成功，或直到子表不存在為止，此時(shí)查找不成功。
• 時(shí)間復(fù)雜度：O(h)=O(log2n)

特殊矩陣和稀疏矩陣哪一種壓縮存儲(chǔ)后失去隨機(jī)存取的功能？為什么？

• 答：
  1. 特殊矩陣指值相同的元素或零元素在矩陣中的分布有一定規(guī)律，因此可以對(duì)非零元素分配單元（對(duì)值相同元素只分配一個(gè)單元），將非零元素存儲(chǔ)在向量中，元素的下標(biāo)i和j和該元素在向量中的下標(biāo)有一定規(guī)律，可以用簡(jiǎn)單公式表示，仍具有隨機(jī)存取功能。
  2. 稀疏矩陣是指非零元素和矩陣容量相比很小（t＜＜m*n），且分布沒(méi)有規(guī)律。用十字鏈表作存儲(chǔ)結(jié)構(gòu)自然失去了隨機(jī)存取的功能。即使用三元組表的順序存儲(chǔ)結(jié)構(gòu)，存取下標(biāo)為i和j的元素時(shí)，要掃描三元組表，下標(biāo)不同的元素，存取時(shí)間也不同，最好情況下存取時(shí)間為O(1)，最差情況下是O(n)，因此也失去了隨機(jī)存取的功能。
• 隨機(jī)存取與非隨機(jī)存?。?
  1. 隨機(jī)存取就是直接存取，可以通過(guò)下標(biāo)直接訪問(wèn)的那種數(shù)據(jù)結(jié)構(gòu)，與存儲(chǔ)位置無(wú)關(guān)，例如數(shù)組。
  2. 非隨機(jī)存取就是順序存取了，不能通過(guò)下標(biāo)訪問(wèn)了，只能按照存儲(chǔ)順序存取，與存儲(chǔ)位置有關(guān)，例如鏈表。

數(shù)組

• 定義的結(jié)構(gòu)形式：
  • 棧內(nèi)存
    在方法中定義的一些基本類型的變量和對(duì)象的引用變量都在方法的棧內(nèi)存中分配，當(dāng)在一段代碼中定義一個(gè)變量時(shí)，java就在棧內(nèi)存中為這個(gè)變量分配內(nèi)存空間，當(dāng)超出變量的作用域后，java會(huì)自動(dòng)釋放掉為該變量所分配的內(nèi)存空間。
  • 堆內(nèi)存
    堆內(nèi)存用來(lái)存放由new運(yùn)算符創(chuàng)建的對(duì)象和數(shù)組，在堆中分配的內(nèi)存，由java虛擬機(jī)的自動(dòng)垃圾回收器來(lái)管理。在堆中創(chuàng)建了一個(gè)數(shù)組或?qū)ο蠛?，同時(shí)還在棧內(nèi)存中定義一個(gè)特殊的變量。讓棧內(nèi)存中的這個(gè)變量的取值等于數(shù)組或者對(duì)象在堆內(nèi)存中的首地址，棧中的這個(gè)變量就成了數(shù)組或?qū)ο蟮囊米兞?，引用變量?shí)際上保存的是數(shù)組或?qū)ο笤诙褍?nèi)存中的地址（也稱為對(duì)象的句柄），以后就可以在程序中使用棧的引用變量來(lái)訪問(wèn)堆中的數(shù)組或?qū)ο蟆?/li>
  • 與結(jié)構(gòu)或類中的字段的區(qū)別
    數(shù)組中的所有元素都具有相同類型(這一點(diǎn)和結(jié)構(gòu)或類中的字段不同，它們可以是不同類型)。數(shù)組中的元素存儲(chǔ)在一個(gè)連續(xù)性的內(nèi)存塊中，并通過(guò)索引來(lái)訪問(wèn)(這一點(diǎn)也和結(jié)構(gòu)和類中的字段不同，它們通過(guò)名稱來(lái)訪問(wèn))。