数据结构高手来帮忙（简答题、算法题） 数据结构（c++）字符串 模式匹配算法问题，对高手来说只要写...
\u6570\u636e\u7ed3\u6784\u9898\u4e00\u9053\uff0c\u8bf7\u9ad8\u624b\u5e2e\u5fd9~\u5177\u4f53\u7b97\u6cd5\u662f\u600e\u4e48\u7b97\u7684\uff01\u7528\u67e5\u627e\u6bcf\u4e2a\u5143\u7d20\u7684\u6982\u7387\u4e58\u627e\u5230\u8be5\u5143\u7d20\u9700\u8981\u904d\u5386\u7684\u957f\u5ea6\u540e\u76f8\u52a0\u5373\u5f97\u5230\u7ed3\u679c\u3002
avgLen = (1/24)*1 + (1/6)*2 + (2/3)*3 + (1/8)*4 = 23/8
\u6545\u9009A
#include
using namespace std;
string s = "zabcdefg";
int index1(const string ss, int pos)
{
if (poss.length())
printf("pos²»ºÏ\u00b7\u00a8£¡");
int i = pos, j = 0;
while (i < s.length() && j < ss.length()) {
if (s[i]==ss[j]) {
i++;
j++;
} else {
i=i-j+1;
j=0;
}
}
if (j>=ss.length())
return (i-j+1);
else
return -1;
}
void getnext(const string ss, int *next)
{
int i = 0, j = -1;
next[i] = -1;
while (i < ss.length()) {
if (j == -1 || s[i] == ss[j]) {
i++;
j++;
next[i]=j;
} else
j = next[j];
}
}
int index2(const string ss, int pos)
{
int *next = new int[ss.length()];
getnext(ss, next);
int i = pos, j = 0;
while (i < s.length() && j < ss.length()) {
if (j==0 || s[i]==ss[j] ) {
++i;
++j;
} else {
j = next[j];
}
}
if (j >= ss.length())
return i-ss.length()+1;
else
return -1;
}
int main()
{
string ss = "abc";
printf("index1: %d, index2: %d\n", index1(ss, 0), index2(ss, 0));
return 0;
}
2、数组不适合作为二叉树的存储结构。（ N ）
3、串是一种数据对象和操作都特殊的线性表。（ Y ）
4、线性表采用链表存储时，结点和结点内部的存储空间可以是不连续的。（ Y ）
5、栈和队列都是限飞过海英语角制存取点的线性结构。（ Y ）
6、一个广义表可以为其它广义表所共享。（ N ）
7、树的度是指树内结点的度。（ Y ）
8、一棵一般树的结点的 根次序遍历和后根次序遍历分别与其相应二叉树的结点前序遍历但是和后序就几号回家豫剧遍历是一致的。（ N ）
9、无向图的邻接矩阵一定对称矩阵，有向图的邻接矩阵一定是非对称矩阵。（ N ）
10、排序算法中的比较次数与初始元素序列的排列无关。（ X ）
1、 设目标串t=“abaabcc”，模式串P=“aabc”，试描述根据穷举模式匹配算法进行匹配的过程。
abaabcc
aabc d=0, fail
aabc d=1, fail
aabc d=2, success, return 2
2、 设用于通讯的电文法由8个字母组成，字母在电文中出现的频率分别为7，9，2，6，32，3，21，10，试为这8个字母设计不等长Huffman编码，并给出该电文的总码数（要求画出Huffman编码数）。
假设：
a:7 b:9 c:2 d:6 e:32 f:3 g:21 h:10
排序：
(c:2) (f:3) (d:6) (a:7) (b:9) (h:10) (g:21) (e:32)
按优先级合并：
((c[0],f[1]):5) (d:6) (a:7) (b:9) (h:10) (g:21) (e:32)
(a:7) (b:9) (h:10) (((c[00],f[01]),d[1]):11) (g:21) (e:32)
(h:10) (((c[00],f[01]),d[1]):11) ((a[0],b[1]):16) (g:21) (e:32)
((a[0],b[1]):16) ((h[0],((c[100],f[101]),d[11])):21) (g:21) (e:32)
(g:21) (e:32) (((a[00],b[01]),(h[10],((c[1100],f[1101]),d[111]))):37)
(((a[00],b[01]),(h[10],((c[1100],f[1101]),d[111]))):37) ((g[0],e[1]):43)
((((a[000],b[001]),(h[010],((c[01100],f[01101]),d[0111]))),(g[10],e[11])):80)
a:000 3*7=21
b:001 3*9=37
c:01100 5*2=10
d:0111 4*6=24
e:11 2*32=64
f:01101 5*3=15
g:10 2*21=42
h:010 3*10=30
三、 判断题（10分）
1、顺序存储方式只能用于存储线性结构。（ N ）
2、数组不适合作为二叉树的存储结构。（ N ）
3、串是一种数据对象和操作都特殊的线性表。（ Y ）
4、线性表采用链表存储时，结点和结点内部的存储空间可以是不连续的。（ Y ）
5、栈和队列都是限制存取点的线性结构。（ Y ）
6、一个广义表可以为其它广义表所共享。（ N ）
7、树的度是指树内结点的度。（ Y ）
8、一棵一般树的结点的先根次序遍历和后根次序遍历分别与其相应二叉树的结点前序遍历和后序遍历是一致的。（ N ）
9、无向图的邻接矩阵一定是对称矩阵，有向图的邻接矩阵一定是非对称矩阵。（ N ）
10、排序算法中的比较次数与初始元素序列的排列无关。（ X ）
1、 设目标串t=“abaabcc”，模式串P=“aabc”，试描述根据穷举模式匹配算法进行匹配的过程。
abaabcc
aabc d=0, fail
aabc d=1, fail
aabc d=2, success, return 2
2、 设用于通讯的电文由8个字母组成，字母在电文中出现的频率分别为7，9，2，6，32，3，21，10，试为这8个字母设计不等长Huffman编码，并给出该电文的总码数（要求画出Huffman编码数）。
假设：
a:7 b:9 c:2 d:6 e:32 f:3 g:21 h:10
排序：
(c:2) (f:3) (d:6) (a:7) (b:9) (h:10) (g:21) (e:32)
按优先级合并：
((c[0],f[1]):5) (d:6) (a:7) (b:9) (h:10) (g:21) (e:32)
(a:7) (b:9) (h:10) (((c[00],f[01]),d[1]):11) (g:21) (e:32)
(h:10) (((c[00],f[01]),d[1]):11) ((a[0],b[1]):16) (g:21) (e:32)
((a[0],b[1]):16) ((h[0],((c[100],f[101]),d[11])):21) (g:21) (e:32)
(g:21) (e:32) (((a[00],b[01]),(h[10],((c[1100],f[1101]),d[111]))):37)
(((a[00],b[01]),(h[10],((c[1100],f[1101]),d[111]))):37) ((g[0],e[1]):43)
((((a[000],b[001]),(h[010],((c[01100],f[01101]),d[0111]))),(g[10],e[11])):80)
a:000 3*7=21
b:001 3*9=37
c:01100 5*2=10
d:0111 4*6=24
e:11 2*32=64
f:01101 5*3=15
g:10 2*21=42
h:010 3*10=30
总频数 243
回头慢慢补
绛旓細娓呯┖甯﹀ご缁撶偣鐨勯摼闃熷垪Q銆傗滃凡鐭ョ畻娉曞涓,绠楁硶f31鐨勫姛鑳芥槸浠涔堚濆嚭鑷鏁版嵁缁撴瀯锛岃繖鏄竴閬绠绛旈锛鏍规嵁鎵瀛︽暟鎹粨鏋勭煡璇嗗緱鐭ワ紝绛旀涓猴細娓呯┖甯﹀ご缁撶偣鐨勯摼闃熷垪Q銆
绛旓細1.娌℃湁 2. 鍓嶉┍ 1 鍚庣户 澶 3. 椤哄簭瀛樺偍 閾捐〃瀛樺偍 绱㈠紩瀛樺偍 鏁ｅ垪瀛樺偍 4. 鏁版嵁鐨勮繍绠楁渶甯哥敤鐨勬湁5绉嶏紝鎻掑叆锛 鍒犻櫎锛5. 鏃堕棿澶嶆潅搴 绌洪棿澶嶆潅搴 6. n*(n-1)/2 锛7. ???8.n-i+1 9.n-i 10锛5 11锛32 12.350 (n0+n1+n2=700 n=n2+1 n1鍙兘鍘0 鎴1 ...
绛旓細1锛鏁版嵁缁撴瀯鍦ㄨ绠楁満涓殑琛ㄧず绉颁负鏁版嵁鐨勶紙 B 锛夈侫锛夊瓨鍌ㄧ粨鏋 B锛夋娊璞＄粨鏋 C锛夐『搴忕粨鏋 D锛夐昏緫缁撴瀯 12锛庡湪涓嬪垪搴忓垪涓紝涓嶆槸绾挎ц〃鐨勬槸锛 D 锛夈侫锛('a','b','c') B锛('AB','CD') C锛('a',true,'c') D锛(a,b,c,d)13锛庣嚎鎬ч摼琛ㄤ腑鍚勯摼缁撶偣涔嬮棿鐨勫湴鍧锛 D 锛夈侫锛...
绛旓細鍗曢摼琛ㄤ究浜庢彃鍏ュ拰鍒犻櫎銆傜劧鍚庡崟閾捐〃鏄姩鎬佺敵璇凤紝涓鑸竴娆＄敵璇蜂竴涓┖闂寸粨鐐广
绛旓細涓銆1.3x2鏄粈涔堟剰鎬濓紵3涔樹互x鐨勫钩鏂癸紵3x2+x-1/x+5 => (3x2x+)-(1x/)+5 => (3x2x+1x/-)+5 => 3x2x+1x/-5+ 2.(A+B)*C-D/(E+F)+G => (AB+)*C-D/(EF+)+G => (AB+C*)-(DEF+/)+G => (AB+C*DEF+/-)+G => AB+C*DEF+/-G+ ...
绛旓細2锛庝竴涓爤杈撳叆搴忓垪涓1锛2锛3锛4锛5锛屽垯涓嬪垪搴忓垪涓笉鍙兘鏄爤鐨勮緭鍑哄簭鍒楁槸锛 D 锛夈侫锛1 2 3 4 5 B锛5 4 3 2 1 C锛2 3 4 5 1 D锛4 1 2 3 5 鐗㈣涓鏉″師鍒:123杩涙爤涓嶅彲鑳界殑鍑烘爤褰㈠紡鏄312锛孌涓234杩涙爤423鍑烘爤锛岄敊銆2锛庡凡鐭ヤ竴棰椾簩鍙夋爲鐨勫墠搴忓拰涓簭搴忓垪锛屾眰璇ヤ簩鍙夋爲鐨勫悗搴...
绛旓細绛旓細灏辨彃鍏ュ拰鍒犻櫎鐨勬晥鐜囨潵璇达紝椤哄簭琛ㄧ殑鏁堢巼鏄笉濡傞摼寮忓瓨鍌紝浣嗘槸骞朵笉浠ｈ〃瀹冧笉濡傞摼寮忓瓨鍌ㄥソ锛屽悇鏈夊悇鐨勬湁鐐硅屽凡锛5.瀵逛换浣鏁版嵁缁撴瀯閾惧紡瀛樺偍缁撴瀯涓瀹氫紭浜庨『搴忓瓨鍌ㄧ粨鏋勩傝繖鍙ヨ瘽瀵瑰悧锛熺瓟锛氫笉瀵广傚師鍥犵被浼间笂涓棰樸6.椤哄簭瀛樺偍鏂瑰紡鍙兘鐢ㄩ瀛樺偍绾挎х粨鏋勩傝繖鍙ヨ瘽瀵瑰悧锛熺瓟锛氫笉瀵广傞『搴忓瓨鍌ㄧ┖闂翠篃鏄彲浠ュ姩鎬佸垎閰...
绛旓細2锛氬厛搴忥細ABDCRFG 涓簭锛欴BARCGF 鍚庣画锛欴BRGFCA 3锛氳繃绋嬪啓涓嶅嚭鏉ワ紝瑕佺敾鍥剧殑锛屼篃灏辨槸鍏堥殢渚块夋嫨涓涓《鐐癸紝鐒跺悗鎵惧嚭鐩搁偦鐨勫兼渶灏忕殑杈癸紝鐒跺悗杩炴帴锛岀劧鍚庣户缁壘銆傝矊浼煎墿涓嬬殑閮芥槸鍥撅紝鑷繁瀵圭潃涔︾敾鍚с
绛旓細1. 鎮ㄧ殑绠楁硶涓嶇鍚堥鎰忥紝棰樻剰鏄笉瑕佸垱寤烘柊鐨勭粨鐐瑰氨鏄敤鍘熸潵鐨勭┖闂达紝鎵浠ユ偍 C=(ElemType*)malloc(sizeof(LNode));搴旇鏄浣欑殑銆2. 鎮ㄧ殑绠楁硶鍥犱负AB鏄掑鏈夊簭瑕佹敼涓洪掑噺鏈夊簭锛屾偍灏辨瘡娆″皢鎸囬拡绉诲姩鍒板簭鍒楃殑鏈鏈鏉ヨ繘琛屾瘮杈冨拰鎻掑叆锛岀敱浜庢槸鍗曞悜閾捐〃锛岃繖鏍蜂綘鐨勭畻娉曚細闈炲父浣庢晥銆3. 鎮ㄤ粎浠呴渶瑕佸皢涓や釜...
绛旓細1銆佹煡鎵捐緝澶氾紝澧炲姞鍒犻櫎鎿嶄綔杈冨皯鎴栧鍔犲垹闄ゆ搷浣滃ぇ閮ㄥ垎鍦ㄥ熬閮ㄨ繘琛屾椂浣跨敤椤哄簭缁撴瀯锛鍥犱负鍦ㄩ『搴忕粨鏋勪笂鍙互浣跨敤濡備簩鍒嗘煡鎵剧瓑蹇熸煡鎵炬柟娉曪紝浣嗘槸澧炲姞鍒犻櫎鏁版嵁鍏冪礌鏃堕渶瑕佽皟鏁 2銆佺┖浜屽弶鏍 宸﹀彸瀛愭爲閮戒负绌 宸﹀瓙鏍戜负绌 鍙冲瓙鏍戜负绌 宸﹀彸瀛愭爲閮戒笉涓虹┖ 鑷繁鐪嬩笅銆傘傜湅鐪嬭繕鏈夋病鏈夎鏀圭殑銆傦紵
