數(shù)據(jù)安全及加密

1.對(duì)稱加密和非對(duì)稱加密的區(qū)別？

• 1、對(duì)稱加密又稱公開(kāi)密鑰加密，加密和解密都會(huì)用到同一個(gè)密鑰，如果密鑰被攻擊者獲得，此時(shí)加密就失去了意義。常見(jiàn)的對(duì)稱加密算法有DES、3DES、AES、Blowfish、IDEA、RC5、RC6。

• 2、非對(duì)稱加密又稱共享密鑰加密，使用一對(duì)非對(duì)稱的密鑰，一把叫做私有密鑰，另一把叫做公有密鑰；公鑰加密只能用私鑰來(lái)解密，私鑰加密只能用公鑰來(lái)解密。常見(jiàn)的公鑰加密算法有：RSA、ElGamal、背包算法、Rabin（RSA的特例）、迪菲－赫爾曼密鑰交換協(xié)議中的公鑰加密算法、橢圓曲線加密算法）。

2.簡(jiǎn)述 SSL 加密的過(guò)程用了哪些加密方法，為何這么作？

SSL 加密，在過(guò)程中實(shí)際使用了 對(duì)稱加密 和 非對(duì)稱加密 的結(jié)合。主要的考慮是先使用 非對(duì)稱加密 進(jìn)行連接，這樣做是為了避免中間人攻擊秘鑰被劫持，但是 非對(duì)稱加密 的效率比較低。所以一旦建立了安全的連接之后，就可以使用輕量的 對(duì)稱加密。

3.iOS的簽名機(jī)制是怎么樣的

• 簽名機(jī)制：

  先將應(yīng)用內(nèi)容通過(guò)摘要算法，得到摘要

  再用私鑰對(duì)摘要進(jìn)行加密得到密文

  將源文本、密文、和私鑰對(duì)應(yīng)的公鑰一并發(fā)布

• 驗(yàn)證流程：

  查看公鑰是否是私鑰方的

  然后用公鑰對(duì)密文進(jìn)行解密得到摘要

  將APP用同樣的摘要算法得到摘要，兩個(gè)摘要進(jìn)行比對(duì)，如果相等那么一切正常

數(shù)據(jù)存儲(chǔ)

1.iOS 開(kāi)發(fā)中數(shù)據(jù)持久性有哪幾種?

iOS本地?cái)?shù)據(jù)保存有多種方式,比如NSUserDefaults、歸檔、文件保存、數(shù)據(jù)庫(kù)、CoreData、KeyChain(鑰匙串)等多種方式。其中KeyChain(鑰匙串)是保存到沙盒范圍以外的地方，也就是與沙盒無(wú)關(guān)。

2.FMDB數(shù)據(jù)結(jié)構(gòu)變化升級(jí)

• 1.使用columnExists:inTableWithName方法判斷數(shù)據(jù)表中是否存在字段

• 2.如果不存在，則添加, 如：向bbb表中添加aaa字段 -> ALTER TABLE bbb ADD 'aaa' TEXT

數(shù)據(jù)結(jié)構(gòu)

1.數(shù)據(jù)結(jié)構(gòu)的存儲(chǔ)一般常用的有幾種？各有什么特點(diǎn)？

數(shù)據(jù)結(jié)構(gòu)的存儲(chǔ)一般常用的有兩種 順序存儲(chǔ)結(jié)構(gòu) 和 鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)

• 順序存儲(chǔ)結(jié)構(gòu):

  比如，數(shù)組，1-2-3-4-5-6-7-8-9-10，存儲(chǔ)是按順序的。再比如棧和隊(duì)列等

• 鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu):

  比如，數(shù)組，1-2-3-4-5-6-7-8-9-10，鏈?zhǔn)酱鎯?chǔ)就不一樣了 1(地址)-2(地址)-7(地址)-4(地址)-5(地址)-9(地址)-8(地址)-3(地址)-6(地址)-10(地址)。每個(gè)數(shù)字后面跟著一個(gè)地址 而且存儲(chǔ)形式不再是順序

2.集合結(jié)構(gòu) 線性結(jié)構(gòu) 樹(shù)形結(jié)構(gòu) 圖形結(jié)構(gòu)

• 集合結(jié)構(gòu)

  一個(gè)集合，就是一個(gè)圓圈中有很多個(gè)元素，元素與元素之間沒(méi)有任何關(guān)系 這個(gè)很簡(jiǎn)單

• 線性結(jié)構(gòu)

  一個(gè)條線上站著很多個(gè)人。 這條線不一定是直的。也可以是彎的。也可以是值的 相當(dāng)于一條線被分成了好幾段的樣子 （發(fā)揮你的想象力）。 線性結(jié)構(gòu)是一對(duì)一的關(guān)系

• 樹(shù)形結(jié)構(gòu)

  做開(kāi)發(fā)的肯定或多或少的知道xml 解析 樹(shù)形結(jié)構(gòu)跟他非常類似。也可以想象成一個(gè)金字塔。樹(shù)形結(jié)構(gòu)是一對(duì)多的關(guān)系

• 圖形結(jié)構(gòu)

  這個(gè)就比較復(fù)雜了。他呢 無(wú)窮。無(wú)邊 無(wú)向（沒(méi)有方向）圖形機(jī)構(gòu) 你可以理解為多對(duì)多 類似于我們?nèi)说慕患P(guān)系

3.單向鏈表 雙向鏈表 循環(huán)鏈表

• 單向鏈表 A->B->C->D->E->F->G->H. 這就是單向鏈表 H 是頭 A 是尾 像一個(gè)只有一個(gè)頭的火車一樣 只能一個(gè)頭拉著跑

  
  
  單向鏈表

• 雙向鏈表

  
  
  雙向鏈表

• 循環(huán)鏈表

  循環(huán)鏈表是與單向鏈表一樣，是一種鏈?zhǔn)降拇鎯?chǔ)結(jié)構(gòu)，所不同的是，循環(huán)鏈表的最后一個(gè)結(jié)點(diǎn)的指針是指向該循環(huán)鏈表的第一個(gè)結(jié)點(diǎn)或者表頭結(jié)點(diǎn)，從而構(gòu)成一個(gè)環(huán)形的鏈。發(fā)揮想象力 A->B->C->D->E->F->G->H->A. 繞成一個(gè)圈。就像蛇吃自己的這就是循環(huán) 不需要去死記硬背哪些理論知識(shí)。

4.數(shù)組和鏈表區(qū)別

• 數(shù)組

  數(shù)組元素在內(nèi)存上連續(xù)存放，可以通過(guò)下標(biāo)查找元素；插入、刪除需要移動(dòng)大量元素，比較適用于元素很少變化的情況

• 鏈表

  鏈表中的元素在內(nèi)存中不是順序存儲(chǔ)的，查找慢，插入、刪除只需要對(duì)元素指針重新賦值，效率高

5.堆、棧和隊(duì)列

堆

• 堆是一種經(jīng)過(guò)排序的樹(shù)形數(shù)據(jù)結(jié)構(gòu)，每個(gè)節(jié)點(diǎn)都有一個(gè)值，通常我們所說(shuō)的堆的數(shù)據(jù)結(jié)構(gòu)是指二叉樹(shù)。所以堆在數(shù)據(jù)結(jié)構(gòu)中通?？梢员豢醋鍪且豢脴?shù)的數(shù)組對(duì)象。而且堆需要滿足一下兩個(gè)性質(zhì)：

  1）堆中某個(gè)節(jié)點(diǎn)的值總是不大于或不小于其父節(jié)點(diǎn)的值；

  2）堆總是一棵完全二叉樹(shù)。

• 堆分為兩種情況，有最大堆和最小堆。將根節(jié)點(diǎn)最大的堆叫做最大堆或大根堆，根節(jié)點(diǎn)最小的堆叫做最小堆或小根堆，在一個(gè)擺放好元素的最小堆中，父結(jié)點(diǎn)中的元素一定比子結(jié)點(diǎn)的元素要小，但對(duì)于左右結(jié)點(diǎn)的大小則沒(méi)有規(guī)定誰(shuí)大誰(shuí)小。

• 堆常用來(lái)實(shí)現(xiàn)優(yōu)先隊(duì)列，堆的存取是隨意的，這就如同我們?cè)趫D書(shū)館的書(shū)架上取書(shū)，雖然書(shū)的擺放是有順序的，但是我們想取任意一本時(shí)不必像棧一樣，先取出前面所有的書(shū)，書(shū)架這種機(jī)制不同于箱子，我們可以直接取出我們想要的書(shū)。

棧

• 棧是限定僅在表尾進(jìn)行插入和刪除操作的線性表。我們把允許插入和刪除的一端稱為棧頂，另一端稱為棧底，不含任何數(shù)據(jù)元素的棧稱為空棧。棧的特殊之處在于它限制了這個(gè)線性表的插入和刪除位置，它始終只在棧頂進(jìn)行。

• 棧是一種具有后進(jìn)先出的數(shù)據(jù)結(jié)構(gòu)，又稱為后進(jìn)先出的線性表，簡(jiǎn)稱 LIFO（Last In First Out）結(jié)構(gòu)。也就是說(shuō)后存放的先取，先存放的后取，這就類似于我們要在取放在箱子底部的東西（放進(jìn)去比較早的物體），我們首先要移開(kāi)壓在它上面的物體（放進(jìn)去比較晚的物體）。

• 堆棧中定義了一些操作。兩個(gè)最重要的是PUSH和POP。PUSH操作在堆棧的頂部加入一個(gè)元素。POP操作相反，在堆棧頂部移去一個(gè)元素，并將堆棧的大小減一。

• 棧的應(yīng)用—遞歸

隊(duì)列

• 隊(duì)列是只允許在一端進(jìn)行插入操作、而在另一端進(jìn)行刪除操作的線性表。允許插入的一端稱為隊(duì)尾，允許刪除的一端稱為隊(duì)頭。它是一種特殊的線性表，特殊之處在于它只允許在表的前端進(jìn)行刪除操作，而在表的后端進(jìn)行插入操作，和棧一樣，隊(duì)列是一種操作受限制的線性表。

• 隊(duì)列是一種先進(jìn)先出的數(shù)據(jù)結(jié)構(gòu)，又稱為先進(jìn)先出的線性表，簡(jiǎn)稱 FIFO（First In First Out）結(jié)構(gòu)。也就是說(shuō)先放的先取，后放的后取，就如同行李過(guò)安檢的時(shí)候，先放進(jìn)去的行李在另一端總是先出來(lái)，后放入的行李會(huì)在最后面出來(lái)。

6.輸入一棵二叉樹(shù)的根結(jié)點(diǎn)，求該樹(shù)的深度？

二叉樹(shù)的結(jié)點(diǎn)定義如下：

struct BinaryTreeNode
{
    int m_nValue ；
    BinaryTreeNode* m_pLeft;
    BinarvTreeNode* m_pRight ；
}

• 如果一棵樹(shù)只有一個(gè)結(jié)點(diǎn)，它的深度為1。
• 如果根結(jié)點(diǎn)只有左子樹(shù)而沒(méi)有右子樹(shù)，那么樹(shù)的深度應(yīng)該是其左子樹(shù)的深度加1；同樣如果根結(jié)點(diǎn)只有右子樹(shù)而沒(méi)有左子樹(shù)，那么樹(shù)的深度應(yīng)該是其右子樹(shù)的深度加1。
• 如果既有右子樹(shù)又有左子樹(shù)，那該樹(shù)的深度就是其左、右子樹(shù)深度的較大值再加1。

int TreeDepth(TreeNode* pRoot)
{
    if(pRoot == nullptr)
        return 0;
    int left = TreeDepth(pRoot->left);
    int right = TreeDepth(pRoot->right);

    return (left>right) ? (left+1) : (right+1);
}

7.輸入一課二叉樹(shù)的根結(jié)點(diǎn)，判斷該樹(shù)是不是平衡二叉樹(shù)？

• 重復(fù)遍歷結(jié)點(diǎn)

  先求出根結(jié)點(diǎn)的左右子樹(shù)的深度，然后判斷它們的深度相差不超過(guò)1，如果否，則不是一棵二叉樹(shù)；如果是，再用同樣的方法分別判斷左子樹(shù)和右子樹(shù)是否為平衡二叉樹(shù)，如果都是，則這就是一棵平衡二叉樹(shù)。

• 遍歷一遍結(jié)點(diǎn)

  遍歷結(jié)點(diǎn)的同時(shí)記錄下該結(jié)點(diǎn)的深度，避免重復(fù)訪問(wèn)。

方法1:

struct TreeNode{
    int val;
    TreeNode* left;
    TreeNode* right;
};
 
int TreeDepth(TreeNode* pRoot){
    if(pRoot==NULL)
        return 0;
    int left=TreeDepth(pRoot->left);
    int right=TreeDepth(pRoot->right);
    return left>right?(left+1):(right+1);
}
 
bool IsBalanced(TreeNode* pRoot){
    if(pRoot==NULL)
        return true;
    int left=TreeDepth(pRoot->left);
    int right=TreeDepth(pRoot->right);
    int diff=left-right;
    if(diff>1 || diff<-1)
        return false;
    return IsBalanced(pRoot->left) && IsBalanced(pRoot->right);
}

方法2：

bool IsBalanced_1(TreeNode* pRoot,int& depth){
    if(pRoot==NULL){
        depth=0;
        return true;
    }
    int left,right;
    int diff;
    if(IsBalanced_1(pRoot->left,left) && IsBalanced_1(pRoot->right,right)){
        diff=left-right;
        if(diff<=1 || diff>=-1){
            depth=left>right?left+1:right+1;
            return true;
        }
    }
    return false;
}
 
bool IsBalancedTree(TreeNode* pRoot){
    int depth=0;
    return IsBalanced_1(pRoot,depth);
}