数据结构题一道,请高手帮忙~具体算法是怎么算的! 一道数据结构的题,请帮忙改错。。在线等
\u6570\u636e\u7ed3\u6784\u9ad8\u624b\u6765\u5e2e\u5fd9\uff08\u7b80\u7b54\u9898\u3001\u7b97\u6cd5\u9898\uff091\u3001\u987a\u5e8f\u5b58\u50a8\u65b9\u5f0f\u53ea\u80fd\u7528\u4e8e\u5b58\u50a8\u7ebf\u6027\u7ed3\u6784\u3002\uff08 N \uff09
2\u3001\u6570\u7ec4\u4e0d\u9002\u5408\u4f5c\u4e3a\u4e8c\u53c9\u6811\u7684\u5b58\u50a8\u7ed3\u6784\u3002\uff08 N \uff09
3\u3001\u4e32\u662f\u4e00\u79cd\u6570\u636e\u5bf9\u8c61\u548c\u64cd\u4f5c\u90fd\u7279\u6b8a\u7684\u7ebf\u6027\u8868\u3002\uff08 Y \uff09
4\u3001\u7ebf\u6027\u8868\u91c7\u7528\u94fe\u8868\u5b58\u50a8\u65f6\uff0c\u7ed3\u70b9\u548c\u7ed3\u70b9\u5185\u90e8\u7684\u5b58\u50a8\u7a7a\u95f4\u53ef\u4ee5\u662f\u4e0d\u8fde\u7eed\u7684\u3002\uff08 Y \uff09
5\u3001\u6808\u548c\u961f\u5217\u90fd\u662f\u9650\u98de\u8fc7\u6d77\u82f1\u8bed\u89d2\u5236\u5b58\u53d6\u70b9\u7684\u7ebf\u6027\u7ed3\u6784\u3002\uff08 Y \uff09
6\u3001\u4e00\u4e2a\u5e7f\u4e49\u8868\u53ef\u4ee5\u4e3a\u5176\u5b83\u5e7f\u4e49\u8868\u6240\u5171\u4eab\u3002\uff08 N \uff09
7\u3001\u6811\u7684\u5ea6\u662f\u6307\u6811\u5185\u7ed3\u70b9\u7684\u5ea6\u3002\uff08 Y \uff09
8\u3001\u4e00\u68f5\u4e00\u822c\u6811\u7684\u7ed3\u70b9\u7684 \u6839\u6b21\u5e8f\u904d\u5386\u548c\u540e\u6839\u6b21\u5e8f\u904d\u5386\u5206\u522b\u4e0e\u5176\u76f8\u5e94\u4e8c\u53c9\u6811\u7684\u7ed3\u70b9\u524d\u5e8f\u904d\u5386\u4f46\u662f\u548c\u540e\u5e8f\u5c31\u51e0\u53f7\u56de\u5bb6\u8c6b\u5267\u904d\u5386\u662f\u4e00\u81f4\u7684\u3002\uff08 N \uff09
9\u3001\u65e0\u5411\u56fe\u7684\u90bb\u63a5\u77e9\u9635\u4e00\u5b9a\u5bf9\u79f0\u77e9\u9635\uff0c\u6709\u5411\u56fe\u7684\u90bb\u63a5\u77e9\u9635\u4e00\u5b9a\u662f\u975e\u5bf9\u79f0\u77e9\u9635\u3002\uff08 N \uff09
10\u3001\u6392\u5e8f\u7b97\u6cd5\u4e2d\u7684\u6bd4\u8f83\u6b21\u6570\u4e0e\u521d\u59cb\u5143\u7d20\u5e8f\u5217\u7684\u6392\u5217\u65e0\u5173\u3002\uff08 X \uff09
1\u3001 \u8bbe\u76ee\u6807\u4e32t=\u201cabaabcc\u201d\uff0c\u6a21\u5f0f\u4e32P=\u201caabc\u201d\uff0c\u8bd5\u63cf\u8ff0\u6839\u636e\u7a77\u4e3e\u6a21\u5f0f\u5339\u914d\u7b97\u6cd5\u8fdb\u884c\u5339\u914d\u7684\u8fc7\u7a0b\u3002
abaabcc
aabc d=0, fail
aabc d=1, fail
aabc d=2, success, return 2
2\u3001 \u8bbe\u7528\u4e8e\u901a\u8baf\u7684\u7535\u6587\u6cd5\u75318\u4e2a\u5b57\u6bcd\u7ec4\u6210\uff0c\u5b57\u6bcd\u5728\u7535\u6587\u4e2d\u51fa\u73b0\u7684\u9891\u7387\u5206\u522b\u4e3a7\uff0c9\uff0c2\uff0c6\uff0c32\uff0c3\uff0c21\uff0c10\uff0c\u8bd5\u4e3a\u8fd98\u4e2a\u5b57\u6bcd\u8bbe\u8ba1\u4e0d\u7b49\u957fHuffman\u7f16\u7801\uff0c\u5e76\u7ed9\u51fa\u8be5\u7535\u6587\u7684\u603b\u7801\u6570\uff08\u8981\u6c42\u753b\u51faHuffman\u7f16\u7801\u6570\uff09\u3002
\u5047\u8bbe\uff1a
a:7 b:9 c:2 d:6 e:32 f:3 g:21 h:10
\u6392\u5e8f\uff1a
(c:2) (f:3) (d:6) (a:7) (b:9) (h:10) (g:21) (e:32)
\u6309\u4f18\u5148\u7ea7\u5408\u5e76\uff1a
((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
\u8fd9\u662f\u6309\u4f60\u7684\u601d\u8def\u6539\u7684\uff0c\u6ca1\u95ee\u9898\u4e86\u3002\u4f46\u6211\u89c9\u5f97\u4e0d\u592a\u5408\u9002\uff0c\u56e0\u4e3a\u4f60\u6ca1\u6709\u5efa\u7acb\u4e24\u4e2a\u94fe\u8868\uff0c
#include
#include
typedef struct node{
int data;
struct node *link;
}LNode,*LinkList;
LinkList INSERT(LinkList list,int item)
{
LinkList p,q,r;
q=(LinkList)malloc(sizeof(LNode));
q->data=item;
q->link=NULL;
p=list;
r=NULL;
while(p!=NULL)
{
if((p->data)==(q->data))
break;
else if((p->data)data))
{
r=p;
p=p->link;
}
else
{
if(r==NULL)
{
q->link=list;
list=q;
}
else
{
r->link=q;
q->link=p;
}
break;
}
}
if(p==NULL)
{
r->link=q;
q->link=NULL;
}
return list;
}
int main()
{
LinkList p,r,lista;
int a,i;
char c;
lista=NULL;
do
{
scanf("%d",&a);
c=getchar();
p=(LinkList)malloc(sizeof(LNode));
p->data=a;
p->link=NULL;
if(lista==NULL)
lista=p;
else
r->link=p;
r=p;
}
while(c==' ');
do
{
scanf("%d",&a);
c=getchar();
lista=INSERT(lista,a);
}
while(c==' ');
p=lista;
while(p!=NULL)
{
printf("%d ",p->data);
p=p->link;
}
return 0;
}
avgLen = (1/24)*1 + (1/6)*2 + (2/3)*3 + (1/8)*4 = 23/8
故选A
1*(1/24)+2*(1/6)+3*(2/3)+4*(1/8)=23/8
即答案A
绛旓細avgLen = (1/24)*1 + (1/6)*2 + (2/3)*3 + (1/8)*4 = 23/8 鏁呴堿
绛旓細1.2 璁緉涓烘鏁存暟銆傝瘯纭畾涓嬪垪鍚勭▼搴忔涓墠缃互璁板彿@鐨勮鍙ラ搴︼細(1) i=1; k=0;while (i<=n-1) { k+=10*i; // 1,2 ,3,...,n-1 棰戝害锛 n-1娆 i++;} (2) k=0;for (i=1;i<=n; i++) { for (j=i; j<=n; j++) i = 1 2 3 ...
绛旓細锛1锛夌畻娉曞姛鑳斤細鍦ㄦ暟缁刟涓笅鏍囧皬浜巒鐨勬垚鍛樹腑鏌ユ壘锛岃繑鍥炲伓鏁颁笅鏍囨垚鍛樹腑鍊间负k鐨勬垚鍛樹笅鏍囷紝鑻ユ棤锛岃繑鍥炲鏁颁笅鏍囨垚鍛樹腑鍊间负k鐨勬垚鍛樹笅鏍囷紝閮芥棤锛岃繑鍥-1锛涳紙2锛夎繑鍥炵粨鏋4锛岃繘琛屼簡3娆℃瘮杈冿紙涓嶅寘鎷琭or寰幆涓帶鍒跺彉閲廼鐨勬瘮杈冿級锛屽嵆锛歛[0]銆乤[2]銆乤[4]閮戒笌k杩涜浜嗘瘮杈冿紝a[4]=k锛屽惊鐜粨鏉燂紝杩斿洖 4 锛...
绛旓細6. 璁捐涓涓▼搴忓疄绾夸簩鍙夋爲鐨勫眰娆¢亶鍘嗭紝瑕佹眰姣忓眰涔嬮棿鐨鏁版嵁鐢ㄤ竴涓┖鏍煎垎寮銆備簩鍙夋爲閲囩敤浜屽弶閾捐〃鏂瑰紡杩涜瀛樺偍銆傚懙鍛碉紝灏忔牱鐨勪笉瑕佷互涓轰綘绌夸釜椹敳鎴戝氨璁や笉鍑烘潵浜嗐傘傘備簩鍙夋爲灞傛閬嶅巻锛屽吀鍨嬬殑鐢ㄩ摼琛ㄥ疄鐜帮紝杩欓涓嶈繃鏄閾捐〃鐨勮妭鐐逛繚瀛樺唴瀹归櫎浜嗘爲鑺傜偣鎸囬拡澶栵紝杩樻湁灞傛姝よ妭鐐瑰眰娆′俊鎭7. 鍒╃敤澶ч《鍫嗗疄鐜颁竴涓...
绛旓細璧峰锛64锛夛紝锛56,23,89,10,75锛夌涓瓒 锛56,64锛夛紝锛23,89,10,75锛夌浜岃稛 锛23,56,64锛夛紝锛89,10,75锛夌涓夎稛 锛23,56,64,89锛夛紝锛10,75锛夌鍥涜稛 锛10,23,56,64,89锛夛紝锛75锛夌浜旇稛 锛10,23,56,64,75,89锛2. 鍐掓场鎺掑簭 璧峰锛50锛38锛77锛26锛45锛69锛夌涓瓒燂紙38锛...
绛旓細涓銆1銆丅 2銆丅 3銆 ?4銆丆 銆 A鐨勬繁搴︿负1锛孊鐨勬繁搴︿负3锛孌鐨勬繁搴︿负3銆5銆丆 6銆丅?7銆丆 8銆丅 鐩存帴鎻掑叆鎺掑簭 锛歯涓笉鍚岀殑鏁版嵁鍏冪礌锛屾渶澶氶渶瑕佹瘮杈僴*(n-1)/2 9銆丆 10銆丄 浜屻1.绾挎缁撴瀯 锛闈炵嚎鎬х粨鏋 銆2. 352 < 100+ (6*20+6)*2 > 锛 232 ...
绛旓細1銆侀『搴忓瓨鍌ㄦ柟寮忓彧鑳界敤浜庡瓨鍌ㄧ嚎鎬缁撴瀯銆傦紙 N 锛2銆佹暟缁勪笉閫傚悎浣滀负浜屽弶鏍戠殑瀛樺偍缁撴瀯銆傦紙 N 锛3銆佷覆鏄竴绉鏁版嵁瀵硅薄鍜屾搷浣滈兘鐗规畩鐨勭嚎鎬ц〃銆傦紙 Y 锛4銆佺嚎鎬ц〃閲囩敤閾捐〃瀛樺偍鏃讹紝缁撶偣鍜岀粨鐐瑰唴閮ㄧ殑瀛樺偍绌洪棿鍙互鏄笉杩炵画鐨勩傦紙 Y 锛5銆佹爤鍜岄槦鍒楅兘鏄檺椋炶繃娴疯嫳璇鍒跺瓨鍙栫偣鐨勭嚎鎬х粨鏋勩傦紙 Y 锛6...
绛旓細2棰 锛坆,c,e,d,a锛夈俛,b杩涙爤(SS)锛宐鍑烘爤(X)锛岃緭鍑恒恇銆, c杩涙爤(S)锛宑鍑烘爤(X)锛岃緭鍑恒恈銆, d,e杩涙爤(SS)锛宔,d,a鍑烘爤(XXX)锛岃緭鍑恒恊,d,a銆,鎵浠ョ粨鏋滀负b,c,e,d,a 3棰 锛55锛4棰 http://xz7.2000y.net/mb/1/ReadNews.asp?NewsID=463885 绗19棰 浣犵湅鐪 5棰 锛3锛...
绛旓細1銆佹煡鎵捐緝澶氾紝澧炲姞鍒犻櫎鎿嶄綔杈冨皯鎴栧鍔犲垹闄ゆ搷浣滃ぇ閮ㄥ垎鍦ㄥ熬閮ㄨ繘琛屾椂浣跨敤椤哄簭缁撴瀯锛鍥犱负鍦ㄩ『搴忕粨鏋勪笂鍙互浣跨敤濡備簩鍒嗘煡鎵剧瓑蹇熸煡鎵炬柟娉曪紝浣嗘槸澧炲姞鍒犻櫎鏁版嵁鍏冪礌鏃堕渶瑕佽皟鏁 2銆佺┖浜屽弶鏍 宸﹀彸瀛愭爲閮戒负绌 宸﹀瓙鏍戜负绌 鍙冲瓙鏍戜负绌 宸﹀彸瀛愭爲閮戒笉涓虹┖ 鑷繁鐪嬩笅銆傘傜湅鐪嬭繕鏈夋病鏈夎鏀圭殑銆傦紵
绛旓細鐓ф剰鎬濈湅搴旇鏄帓杩囧簭鐨勪簡 缁欎釜鎬濊矾锛氬亣璁綼[n]涓哄崌搴 1銆佸畾涔夊彉閲弇1銆乵2銆丮锛屼护m1=0锛宮2=n-1锛2銆丮 = 锛坢1+m2+1锛/2锛屾瘮杈僡[M]涓巏鐨勫ぇ灏忥細濡俛[M]=k锛岃繑鍥濵锛涘a[M]>k,璇存槑鍙兘瀛樺湪鐨刱搴旇鍦╝[M]椤逛箣鍓嶏紝鎵浠ヨ涓嬩竴娆℃悳绱㈣寖鍥翠负鍓嶉潰鐨勯」鐩紝鍗砿2 = M-1锛屼竴鏃2<m1璇存槑鏃...