öλÔÓéÀֵǼÈë¿ÚÏÂÔØ

Ô­ÎÄÄÚÈÝÀ´×ÔÃâ·ÑöλÔÓéÀÖ¹Ù·½appÏÂÔØÂÛ̳£¬Çëµã»÷²é¿´È«ÎÄ
http://bbs.freekaoyan.com/viewthread.php?tid=217965
±±¾©º½¿Õº½Ìì´óѧ³ÌÐòÉè¼ÆÓëÊý¾Ý½á¹¹ÊÔÌâ
(2000Äê)

Ò»¡¢ Ñ¡ÔñÌâ(2¡¯x10)
1. ÔÚ·Ç¿ÕË«ÏòÑ­»·Á´±íÖÐqËùÖ¸µÄ½áµãÇ°²åÈëÒ»¸öÓÉpËùÖ¸µÄÁ´½ÓµãµÄ¹ý³ÌÒÀ´ÎΪ£ºrlink(p)¡ûq£»llink(p)¡ûllink(q)£»llink(q)¡ûp£»_________¡£
(A)rlink(q)¡ûp (B)rlink(llink(q))¡ûp
(C)rlink(llink(p))¡ûp (D)rlink(rlink(p))¡ûp
2. Èô¶Ôn½×¶Ô³Æ¾ØÕóAÒÔÐÐÐòΪÖ÷Ðò·½Ê½½«ÆäÏÂÈý½ÇÐεÄÔªËØ(°üÀ¨Ö÷¶Ô½ÇÏßÉÏËùÓÐÔªËØ)ÒÀ´Î´æ·ÅÓÚһάÊý×éB ÖУ¬ÔòÔÚBÖÐÈ·¶¨aij(i<j)µÄλÖÃkµÄ¹ØϵΪ_________¡£
(A) (B)
(C) (D)
3. ij¶ÑÕ»µÄÊäÈëÐòÁÐΪa£¬b£¬c£¬d£¬ÏÂÃæµÄËĸöÐòÁÐÖУ¬_________²»¿ÉÄÜÊÇËüµÄÊä³öÐòÁС£
(A)a£¬c£¬b£¬d (B)b£¬c£¬d£¬a
(C)c£¬d£¬b£¬a (D)d£¬c£¬a£¬b
4. Éî¶ÈΪhµÄÂúm²æÊýµÄµÚk²ãÓÐ_________¸ö½áµã¡£(1¡Ük¡Üh)
(A)mk-1 (B)mk-1 (C)mh-1 (D)mh-1
5. ¾ßÓÐ10¸öÒ¶½áµãµÄ¶þ²æÊ÷ÖÐÓÐ_________¸ö¶ÈΪ2µÄ½áµã¡£
(A)8 (B)9 (C)10 (D)11
6. ÒªÁ¬Í¨¾ßÓÐn¸ö¶¥µãµÄÓÐÏòͼ£¬ÖÁÉÙÐèÒª_________Ìõ±ß¡£
(A)n-1 (B)n (C)n 1 (D)2n
7. ÒÑÖªÓÐÏòͼG=(V£¬E)£¬ÆäÖÐV={v1£¬v2£¬v3£¬v4£¬v5£¬v6£¬v7}£¬
E={<v1£¬v2>£¬<v1£¬v3>£¬<v1£¬v4>£¬<v2£¬v5>£¬<v3£¬v5>£¬<v3£¬v6>£¬
<v4£¬v6>£¬<v5£¬v7>£¬<v6£¬v7>}£¬GµÄÍØÆËÐòÁÐÊÇ_________¡£
(A)v1£¬v3£¬v4£¬v6£¬v2£¬v5£¬v7 (B)v1£¬v3£¬v2£¬v6£¬v4£¬v5£¬v7
(C)v1£¬v3£¬v4£¬v5£¬v2£¬v6£¬v7 (D)v1£¬v2£¬v5£¬v3£¬v4£¬v6£¬v7
8. Èô²éÕÒÿ¸ö¼Ç¼µÄ¸ÅÂʾùµÈ£¬ÔòÔÚ¾ßÓÐn¸ö¼Ç¼µÄÁ¬Ðø˳ÐòÎļþÖвÉÓÃ˳Ðò²éÕÒ·¨²éÕÒÒ»¸ö¼Ç¼£¬Æäƽ¾ù²éÕÒ³¤¶ÈASLΪ_________
(A) (B) (C) (D)n
9. ÏÂÃæ¹ØÓÚBÊ÷ºÍB Ê÷µÄÐðÊöÖУ¬²»ÕýÈ·µÄÊÇ_________
(A)BÊ÷ºÍB Ê÷¶¼ÊÇƽºâµÄ¶à·ÖÊ÷¡£
(B)BÊ÷ºÍB Ê÷¶¼¿ÉÓÃÓÚÎļþµÄË÷Òý½á¹¹¡£
(C)BÊ÷ºÍB Ê÷¶¼ÄÜÓÐЧµØÖ§³ÖËæ»ú¼ìË÷¡£
(D)BÊ÷ºÍB Ê÷¶¼ÄÜÓÐЧµØÖ§³Ö˳Ðò¼ìË÷¡£
10. ÏÂÃæ¸ø³öµÄËÄÖÖÅÅÐò·½·¨ÖУ¬ÅÅÐò¹ý³ÌÖеıȽϴÎÊýÓëÅÅÐò·½·¨Î޹صÄÊÇ_________¡£
(A)Ñ¡ÔñÅÅÐò·¨ (B)²åÈëÅÅÐò·¨
(C)¿ìËÙÅÅÐò·¨ (D)¶Ñ»ýÅÅÐò·¨

¶þ¡¢ (10¡¯)
ÓÐʵÏÖͬһ¹¦ÄܵÄÁ½¸öËã·¨A1ºÍA2£¬ÆäÖÐA1µÄʱ¼ä¸´ÔÓ¶ÈΪT1=O(2n)£¬A2µÄʱ¼ä¸´ÔÓ¶ÈΪT2=O(n2)£¬½ö¾Íʱ¼ä¸´ÔӶȶøÑÔ£¬Çë¾ßÌå·ÖÎöÕâÁ½¸öËã·¨ÄÄÒ»¸öºÃ¡£

Èý¡¢(5¡¯ 10¡¯ 10¡¯ 5¡¯)
Ϊ½¨Á¢Ò»¸ö¾ßÓÐn·Ýµµ°¸µÄµµ°¸¿âÐèÒªÉè¼ÆÈçÏÂÊý¾Ý½á¹¹£ºËùÓеµ°¸´æ´¢ÔÚÒ»¸ö¶¯Ì¬´æ´¢µÄË«ÏòÑ­»·Á´±íÖУ¬Ã¿·Ýµµ°¸Õ¼ÓÃÒ»¸öµØÖ·Á¬ÐøµÄ´æ´¢¿é³ÉΪ¸ÃÁ´±íÖеÄÒ»¸ö½áµã£¬Õû¸öÁ´±íΪһ¸öÁ´½Ó˳ÐòÎļþ£¬È¡ÃûΪdossier(µµ°¸)£¬Í¬Ê±·Ö±ð½¨Á¢Á½¸öË÷Òý£¬ÆäÖÐÒ»¸öΪ³íÃÜË÷Òý£¬È¡ÃûΪdense£¬ÁíÒ»¸öÊÇ±í³¤ÎªmµÄÔÓ´Õ±íË÷Òý£¬È¡ÃûΪbucket£¬¸ÃÔÓ´Õ±í²ÉÓÃÁ´µØÖ··¨´¦Àí³åÍ»¡£ÉÏÊöÁ½ÖÖË÷ÒýÖж¼·Ö±ð´æ´¢ÔÚÿһ·Ýµµ°¸µÄ´æ´¢µØÖ·¡£
1. Çë·Ö±ð»­³ödossier¡¢dense¡¢bucketµÄ½á¹¹Ê¾Òâͼ¡£
2. ·Ö±ðÉè¼Æ³ödossier¡¢dense¡¢bucketµÄÊý¾Ý½áµãµÄ½á¹¹£¬¼´ÎªÁËÂú×ãµµ°¸µÄ²åÈ롢ɾ³ý¡¢²éÕҵIJÙ×÷£¬Ã¿¸ö½áµã±ØÒªµÄÊý¾ÝÏîµÄÃû³Æ¼°Æä×÷Óá£
3. Õë¶ÔÉÏÊö½á¹¹£¬ÓüòÃ÷µÄÎÄ×Ö·Ö±ð˵Ã÷ËùÓпÉÄܵIJéÕÒ·½·¨(²éÕÒ·¾¶)¡£
4. ·Ö±ð¸ø³öÿһÖÖ²éÕÒ·½·¨ÔÚ²éÕҳɹ¦Ê±µÄƽ¾ù²éÕÒ³¤¶È¡£

ËÄ¡¢(10¡¯)
ÒÑÖªnumΪÎÞ·ûºÅÊ®½øÖÆÕûÊý£¬Çëдһ·ÇµÝ¹éËã·¨£¬¸ÃËã·¨ÒÀ´ÎÊä³önum¶ÔÓ¦µÄr½øÖƵĸ÷λÊý×Ö¡£ÒªÇóËã·¨ÖÐÓõ½µÄ¶ÑÕ»²ÉÓÃÏßÐÔÁ´±í´æ´¢½á¹¹¡£(1<r<10)

Îå¡¢(10¡¯)
ÒÑÖª³¤¶ÈΪnµÄÏßÐÔ±íA²ÉÓÃ˳Ðò´æ´¢½á¹¹£¬Çëдһʱ¼ä¸´ÔÓ¶ÈΪO(n)¡¢¿Õ¼ä¸´ÔÓ¶ÈΪO(1)µÄËã·¨£¬¸ÃË㷨ɾ³ýÏßÐÔ±íÖÐËùÓÐֵΪitemµÄÊý¾ÝÔªËØ¡£(O(1)±íʾËã·¨µÄ¸¨Öú¿Õ¼äΪ³£Á¿)

Áù¡¢(10¡¯x2)
ÉèÓÐÒ»¼¯ºÏ£¬Æä³ÉԱΪÈÎÒâÀàÐ͵ÄÊý¾ÝÔªËØ£¬»ù±¾²Ù×÷Ϊ²åÈ롢ɾ³ýºÍ³ÉÔ±²âÊÔ¡£ÈôΪ¸Ã¼¯ºÏÉè¼ÆÒ»¸ö¼¯ºÏÀàÐÍ£¬Ôò
1. ¸Ã¼¯ºÏ¿ÉÒÔ²ÉÓÃÄļ¸ÖÖ´æ´¢½á¹¹£¿¾Í´æ´¢¿Õ¼ä¿ªÏúÒÔ¼°²Ù×÷¶øÑÔ£¬·Ö±ð˵Ã÷ÿÖÖ´æ´¢½á¹¹µÄÌصã¡£
2. ·Ö±ðд³öÉÏÊöÈýÖÖ²Ù×÷ÔÚÄãËùÈ·¶¨µÄÒ»ÖÖ´æ´¢½á¹¹ÉϵľßÌåÌåÏÖ(Ëã·¨)¡£
---------------------------------
ºÃ¶«Î÷£¡£¡£¡
---------------------------------
ºÜºÃ°¡£¬ºÃ¶«Î÷
---------------------------------
ºÃ°¡¡«¡«ÎÒÏ뿼±±º½¡«¡«£¡£¡£¡
---------------------------------
¶¥¶¥¶¥¶¥¶¥¶¥¶¥¶¥
---------------------------------
ÔõôûÓд𰸰¡
---------------------------------
ÔõôûÓд𰸰¡
---------------------------------
°¢.ûÓд𰸰¡...
---------------------------------
ûÓд𰸰¡
---------------------------------
ллÀ² ºÙºÙ