1(12·Ö)
Çë»Ø´ðÏÂÁйØÓÚͼ(Graph)µÄһЩÎÊÌ⣺
¢Ù£¨4·Ö£©ÓÐn¸ö¶¥µãµÄÓÐÏòÁ¬Í¨Í¼×î¶àÓжàÉÙÌõ±ß?×îÉÙÓжàÉÙÌõ±ß£¿
¢Ú£¨4·Ö£©±íʾһ¸öÓÐ1000¸ö¶¥µã¡¢1000Ìõ±ßµÄÓÐÏòͼµÄÁÚ½Ó¾ØÕóÓжàÉÙ¸ö¾ØÕóÔªËØ?ÊÇ·ñÏ¡Êè¾ØÕó£¿
¢Û£¨4·Ö£©¶ÔÓÚÒ»¸öÓÐÏòͼ£¬²»ÓÃÍØÆËÅÅÐò£¬ÈçºÎÅжÏͼÖÐÊÇ·ñ´æÔÚ»·£¿
2(12·Ö)
ì³²¨ÄÇÆõÊýÁÐFn¶¨ÒåÈçÏ£º
F0=0, F1=1, Fn= Fn-1 + Fn-2,n=2,3,¡
Çë¾Í´Ëì³²¨ÄÇÆõÊýÁУ¬»Ø´ðÏÂÁÐÎÊÌ⣺
¢Ù£¨7·Ö£©ÔÚµÝ¹é¼ÆËãFnµÄʱºò£¬ÐèÒª¶Ô½ÏСµÄFn£1£¬Fn£2£¬¡£¬F1£¬F0¾«È·¼ÆËã¶àÉٴΣ¿
¢Ú£¨5·Ö£©Èô¸ÉÓйشóO±íʾ·¨£¬ÊÔ¸ø³öµÝ¹é¼ÆËãFnʱµÝ¹éº¯ÊýµÄʱ¼ä¸´ÔÓ¶ÈÊǶàÉÙ£¿
3 £¨17·Ö£©
ÓÐÒ»ÖÖ¼òµ¥µÄÅÅÐòËã·¨£¬½Ð×ö¼ÆÊýÅÅÐò(count
sorting)¡£ÕâÖÖÅÅ´æËã·¨¶ÔÒ»¸ö´ýÅÅÐòµÄ±í(ÓÃÊý×é±íʾ)½øÐÐÅÅÐò£¬²¢½«ÅÅÐò½á¹û´æ·Åµ½ÁíÒ»¸öеıíÖС£±ØÐë×¢ÒâµÄÊÇ£¬±íÖÐËùÓдýÅÅÐòµÄ¹Ø¼üÂ뻥²»Ïàͬ¡£¼ÆÊýÅÅÐòËã·¨Õë¶Ô±íÖеÄÿ¸ö¼Ç¼£¬É¨Ãè´ýÅÅÐòµÄ±íÒ»ÌË£¬Í³¼Æ±íÖÐÓжàÉÙ¸ö¼Ç¼µÄ¹Ø¼üÂë±È¸Ã¼Ç¼µÄ¹Ø¼üÂëС¡£¼ÙÉèÕë¶Ô³Ò»¸ö¼Ç¼£¬Í³¼Æ³öµÄ¼ÆÊýֵΪc,ÄÇô£¬Õâ¸ö¼Ç¼ÔÚеÄÓÐÐò±íÖеĺÏÊʵĴæ·ÅλÖü´Îªc¡£
¢Ù£¨3·Ö£©¸ø³öÊÊÓÃÓÚ¼ÆÊýÅÅÐòµÄÊý¾Ý±í¶¨Ò壻
¢Ú£¨7·Ö£©Ê¹ÓÃPascal»òCÓïÑÔ±àдʵÏÖ¼ÆÊýÅÅÐòµÄËã·¨£»
¢Û£¨4·Ö£©¶ÔÓÚÓÐn¸ö¼Ç¼µÄ±í£¬¹Ø¼üÂë±È½Ï´ÎÊýÊǶàÉÙ£¿
¢Ü£¨3·Ö£©Óë¼òµ¥Ñ¡ÔñÅÅÐòÏà±È½Ï£¬ÕâÖÖ·½·¨ÊÇ·ñ¸üºÃ£¿ÎªÊ²Ã´£¿
4 £¨10·Ö£©
ÔÚÒ»¿Ã±íʾÓÐÐò¼¯SµÄ¶þ²æËÑË÷Ê÷£¨binary search
tree£©ÖУ¬ÈÎÒâÒ»Ìõ´Ó¸ùµ½Ò¶½ÚµãµÄ·¾¶½«S·ÖΪ3²¿·Ö£ºÔڸ÷¾¶×ó±ß½ÚµãÖеÄÔªËØ×é³ÉµÄ¼¯ºÏS1£»Ôڸ÷¾¶ÉϵĽڵãÖеÄÔªËØ×é³ÉµÄ¼¯ºÏS2£»Ôڸ÷¾¶Óұ߽ڵãÖеÄÔªËØ×é³ÉµÄ¼¯ºÏS3¡£S£½S1¡ÈS2¡ÈS3¡£Èô¶ÔÓÚÈÎÒâµÄa¡ÊS1,
b¡ÊS2, c¡ÊS3,ÊÇ·ñ×ÜÓÐa<=b<=c?Ϊʲô£¿
5 £¨12·Ö£©Çë»Ø´ðÏÂÁйØÓÚ¶Ñ£¨Heap£©µÄһЩÎÊÌ⣺
¢Ù£¨4·Ö£©¶ÑµÄ´æ´¢±íʾÊÇ˳ÐòµÄ£¬»¹ÊÇÁ´½ÓµÄ£¿
¢Ú£¨4·Ö£©ÉèÓÐÒ»¸ö×îС¶Ñ£¬¼´¶ÑÖÐÈÎÒâ½ÚµãµÄ¹Ø¼üÂë¾ù´óÓÚËüµÄ×ó×ÓÅ®ºÍÓÒ×ÓÅ®µÄ¹Ø¼üÂë¡£Æä¾ßÓÐ×î´óÖµµÄÔªËØ¿ÉÄÜÔÚʲôµØ·½£¿
¢Û£¨4·Ö£©¶Ôn¸öÔªËØ½øÐгõʼ½¨¶ÑµÄ¹ý³ÌÖУ¬×î¶à×ö¶àÉÙ´ÎÊý¾Ý±È½Ï£¨²»ÓôóO±íʾ·¨£©£¿
6 £¨12·Ö£©
ÒÑÖªQÊÇÒ»¸ö·Ç¿Õ¶ÓÁУ¬SÊÇÒ»¸ö¿ÕÕ»¡£½öÓöÓÁкÍÕ»µÄADTº¯ÊýºÍÉÙÁ¿¹¤×÷±äÁ¿£¬Ê¹ÓÃPascal»òCÓïÑÔ±àдһ¸öËã·¨£¬½«¶ÓÁÐQÖеÄËùÓÐÔªËØÄæÖá£
Õ»µÄADTº¯ÊýÓУº
makeEmpty(s:stack);ÖÿÕÕ»
push(s:stack; value:datatype); ÐÂÔªËØvalue½øÕ»
pop(s:stack):datatype;³öÕ»£¬·µ»ØÕ»¶¥Öµ
isEmpty(s:stack):boolean;ÅÐÕ»¿Õ·ñ
¶ÓÁеÄADTº¯ÊýÓÐ
enqueue(q:queue;value:datatype); ÔªËØvalue½ø¶Ó
deQueue(q:queue):datatype;³ö¶ÓÁУ¬·µ»Ø¶ÓÍ·Öµ
isEmpty(q:queue):boolean;ÅжÓÁпշñ
7 £¨13·Ö£©
ÉèÉ¢ÁбíΪHT[0..12],¼´±íµÄ´óСΪm=13¡£ÏÖ²ÉÓÃ˫ɢÁз¨½â¾ö³åÍ»¡£É¢Áк¯ÊýºÍÔÚÉ¢Áк¯Êý·Ö±ðΪ£º
H0(key)=key%13;×¢£º£¥ÊÇÇóÓàÊýÔËË㣨£½mod£©
Hi=(Hi-1+REV(key+1)%11+1)%13;i=1,2,3,¡£¬m-1
ÆäÖУ¬º¯ÊýREV£¨x£©±íʾµßµ¹10½øÖÆÊýxµÄ¸÷룬ÈçREV(37)=73,REV(7)=7µÈ¡£Èô²åÈëµÄ¹Ø¼üÂëÐòÁÐΪ{2,8,31,20,19,18,53,27}¡£
¢Ù£¨8·Ö£©ÊÔ»³ö²åÈëÕâ8¸ö¹Ø¼üÂëºóµÄÉ¢ÁÐ±í¡£
¢Ú£¨5·Ö£©¼ÆËãËÑË÷³É¹¦µÄƽ¾ùËÑË÷³¤¶ÈASL¡£
8 £¨12·Ö£©
´Ó×óµ½ÓÒ¼°´ÓÓÒµ½×ó±éÀúÒ»¸öµ¥Á´±íÊÇ¿ÉÄܵ쬯䷽·¨ÊÇÔÚ´Ó×óÏòÓÒ±éÀúµÄ¹ý³ÌÖн«Á¬½Ó·½ÏòÄæ×ª£¬Èçͼ1Ëùʾ¡£ÔÚͼÖеÄÖ¸ÕëpÖ¸Ïòµ±Ç°ÕýÔÚ·ÃÎʵĽڵ㣬ָÕëprÖ¸ÏòÖ¸ÕëpËùÖ¸½ÚµãµÄ×ó²àµÄ½Úµã¡£´Ëʱ£¬Ö¸ÕëpËùÖ¸½Úµã×ó²àµÄËùÓнڵãµÄÁ¬½Ó·½Ïò¶¼ÒÑÄæ×ª¡£
ͼ1Ìâ8ͼ
¢Ù£¨6·Ö£©Ê¹ÓÃPascal»òCÓïÑÔ±àдһ¸öËã·¨£¬´ÓÈÎÒ»¸ø¶¨Î»Öã¨pr,p£©¿ªÊ¼£¬½«Ö¸ÕëpÓÒÒÆ1¸ö½Úµã¡£Èç¹ûpÒÆ³öÁ´±í£¬Ôò½«pÖÃΪNULL£¬²¢ÈÃprÁôÔÚÁ´±í×îÓұߵĽڵãÉÏ¡£
¢Ú£¨6·Ö£©Ê¹ÓÃPascal»òCÓïÑÔ±àдһ¸öËã·¨£¬´ÓÈÎÒ»¸ø¶¨Î»Öã¨pr,p£©¿ªÊ¼£¬½«Ö¸Õëp×óÒÆÒ»¸ö½Úµã¡£Èç¹ûpÒÆ³öÁ´±í£¬Ôò½«pÖÃΪNULL,²¢ÈÃprÍ£ÁôÔÚÁ´±í×î×ó±ßµÄ½ÚµãÉÏ