用二進(jìn)制來編碼字符串“abcdabaa”因块，需要能夠根據(jù)編碼，解碼回原來的字符串籍铁，最少需要()長的二進(jìn)制字符串涡上？
答案：14
Huffman編碼結(jié)果不是唯一的。a：1位 b：2位 c: 3位 d：3位 所以拒名，abcdabaa一共占用 4 * 1 + 2 * 2 + 3 + 3 = 14
字符串www.qq.com所有非空子串（兩個(gè)子串如果內(nèi)容相同則只算一個(gè)）個(gè)數(shù)是（）
答案：50
要求的是子串吩愧，從左到右一次截取， 10個(gè)字符的子串增显，1個(gè); 9個(gè)字符的子串雁佳，2個(gè); 8----------------------37----------------------4 ......... 1----------------------10共有:1+2+3+...+10=10*(10+1)/2=55 減去重復(fù)的: 1個(gè)字符時(shí)有3個(gè)w,2個(gè)q,2個(gè). 2個(gè)字符時(shí)有2個(gè)ww故應(yīng)減去:(2+1+1+1)=5 答案:55-5=50
KMP算法下，長為n的字符串中匹配長度為m的子串的復(fù)雜度為（）
答案：O(M+N)
BF算法（普通匹配算法）：時(shí)間復(fù)雜度O(m*n)同云；空間復(fù)雜度O(1)
KMP算法：時(shí)間復(fù)雜度O(m+n)糖权；空間復(fù)雜度O(n)//模式串大小
串′ababaaababaa′的next數(shù)組為()？
答案：011234223456
next數(shù)組下標(biāo)從1開始計(jì)算
next[1] 肯定是 0
next[2] 肯定是 1
next[n] 的情況炸站，將前面n-1個(gè)字符星澳，計(jì)算從首尾開始組成最大的相同子串的長度，如果找到旱易，那么next值是該長度加1禁偎，否則next值是1腿堤。
舉例
next[6]的計(jì)算，字符串第六位是 a 届垫，( ababa a ababaa)
將前面的5個(gè)字符释液，從頭尾開始取4個(gè)組成子串比較，如果不相等装处，則從首尾取3個(gè)字符組成子串繼續(xù)比較误债，并以此類推， 如果一直比較到最后一個(gè)字符都不相等妄迁，那么該next值為1寝蹈。
4個(gè)字符的情況：abab : baba
3個(gè)字符的情況：aba : aba 此時(shí)相等，那么next[6] = 3+1 = 4
**
下列數(shù)據(jù)結(jié)構(gòu)不是多型數(shù)據(jù)類型的是（）**
答案：字符串 都是char類型 （堆登淘，棧箫老，有向圖都是多型數(shù)據(jù)類型）
假設(shè)某段通信電文僅由 6 個(gè)字母 ABCDEF 組成，字母在電文中出現(xiàn)的頻率分別為2黔州，3耍鬓，7，15流妻，4牲蜀，6。根據(jù)這些頻率作為權(quán)值構(gòu)造哈夫曼編碼绅这，最終構(gòu)造出的哈夫曼樹帶權(quán)路徑長度與字母 B 的哈夫曼編碼分別為______涣达。(這里假定左節(jié)點(diǎn)的值小于右節(jié)點(diǎn)的值)
答案：86 1011
長度：（2+3）4+（4+6+7）3+15=86
一棵哈夫曼樹的帶權(quán)路徑長度等于樹中所有的葉結(jié)點(diǎn)的權(quán)值乘上其到根結(jié)點(diǎn)的路徑長度。
**
若初始序列為gbfcdae证薇，那么至少需要 次兩兩交換度苔，才能使該序列變?yōu)閍bcdefg。任給一個(gè)自由a--g這7個(gè)字母組成的排列浑度，最壞的情況下需要至少_ 次兩兩交換寇窑，才能使序列變?yōu)閍bcdefg。**
答案 ： 5 6
次數(shù)最少的交換方法是：每次兩兩交換至少要使一個(gè)字符到達(dá)最終位置箩张。
第一次交換a,g結(jié)果為：abfcdge
第二次交換c,f結(jié)果為：abcfdge
第三次交換f,d結(jié)果為：abcdfge
第四次交換e,f結(jié)果為：abcdegf
第五次交換g,f結(jié)果為：abcdefg
完成疗认，一共交換了5次上面的交換中，由于b正好在最終位置伏钠，因此省去了一次交換任給一個(gè)自由a--g這7個(gè)字母組成的排列横漏，最壞情況需要交換7-1=6次這種最壞情況是每個(gè)字符都需要交換一次來達(dá)到最終位置，最后一次交換使的兩個(gè)字符同時(shí)到達(dá)最終位置熟掂。N個(gè)字符最壞情況需要至少N-1次交換
若串 =’software’ 缎浇，其子串?dāng)?shù)目為
答案：37
8+7+...+1+1=37;注意加上空串
串既可以用順序存儲(chǔ)，也可以用鏈?zhǔn)酱鎯?chǔ)赴肚。
字符串通常采用順序存儲(chǔ)素跺，但是字符串較長而沒有那么大的連續(xù)空間時(shí)二蓝，可以把一個(gè)字符串分成多個(gè)小串，串與串之間采用鏈?zhǔn)酱鎯?chǔ)
**
由4個(gè)“1”和4個(gè)“0”組成的8位二進(jìn)制補(bǔ)碼指厌，能表示的最小整數(shù)是刊愚？**
答案：-121
這里我們需要知道的是:
正數(shù)： 原碼 = 反碼 = 補(bǔ)碼
負(fù)數(shù)：原碼 反碼 = 原碼除符號(hào)位之外的各位求反 補(bǔ)碼 = 反碼 +1 （如果 +1 之后有進(jìn)位的，要一直往前進(jìn)位踩验，包括符號(hào)位）
最小的一定是負(fù)數(shù)鸥诽，因?yàn)槭狗创a絕對(duì)值盡量小，這樣原碼絕對(duì)值就更大箕憾。補(bǔ)碼為10000111牡借，-121（10）； 最大的一定是正數(shù)袭异，為01111000
字符串′ababaabab′的nextval為()
答案：(0,1,0,1,0,4,1,0,1)
第一步先計(jì)算Next[i] 不再贅述
接下來計(jì)算nextval[i]的值：
nextval[i]的求解需要比較s中next[i]所在位置的字符是否與s[i]的字符一致钠龙，如果一致則用s[next[i]]的nextval的值作為nextval[i]，
如果不一致御铃，則用next[i]做為nextval[i]碴里。
nextval[0] = -1;
s[1]=b != s[next[1]]=s[0]=a; nextval[1]=next[1]=0;
s[2]=a = s[next[2]]=s[0]=a, nextval[2]=nextval[0]=-1;
s[3]=b = s[next[3]]=s[1]=b, nextval[3]=nextval[1]=0;
s[4]=a = s[next[4]]=s[2]=a, nextval[4]=nextval[2]=-1;
s[5]=a != s[next[5]]=s[3]=b, nextval[5]=next[5]=3;
s[6]=b = s[next[6]]=s[1]=b, nextval[6]=nextval[1]=0;
s[7]=a = s[next[7]]=s[2]=a, nextval[7]=nextval[2]=-1;
s[8]=b = s[next[8]]=s[3]=b, nextval[8]=nextval[3]=0;
nextval -1 0 -1 0 -1 3 0 -1 0
有的時(shí)候下標(biāo)從1開始即 0 1 0 1 0 4 1 0 1
字符串”qiniu”根據(jù)順序不同有多少種排列組合的方式？
方法一：由于有兩個(gè)i上真，可以看成是有5個(gè)位置咬腋，只要確定了q，n谷羞，u的位置，字符串就確定了溜徙，因此湃缎，是5×4×3=60
方法二：c52*a33=60
StringBuffer是線程安全的,StringBuilder是非線程安全的
卡特蘭數(shù)公式 h(n)=C(2n，n)/(n+1)蠢壹，適用于出棧情況求和
例如n=3 h(3)=c(6,3)/4=5種
