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

×¢£º1¡¢³ýµÚ¾ÅÌâÍ⣬ÆäËû¸÷ÌâÿÌâ10·Ö£¬µÚ¾ÅÌâ20·Ö¡£
2¡¢ËùÓÐÊÔÌâµÄ´ð°¸Ð´ÔÚ´ðÌâÖ½ÉÏ¡£

Ò»¡¢ÅжÏÏÂÁÐÐðÊöµÄ¶Ô´í¡£
(1) ÏßÐÔ±íµÄÂß¼­Ë³ÐòÓëÎïÀí˳Ðò×ÜÊÇһֵġ£
(2) ÏßÐÔ±íµÄ˳Ðò´æ´¢±íʾÓÅÓÚÁ´Ê½´æ´¢±íʾ¡£
(3) ÏßÐÔ±íÈô²ÉÓÃÁ´Ê½´æ´¢±íʾʱËùÓнáµãÖ®¼äµÄ´æ´¢µ¥ÔªµØÖ·¿ÉÁ¬Ðø¿É²»Á¬Ðø¡£
(4) ¶þάÊý×éÊÇÆäÊý×éÔªËØΪÏßÐÔ±íµÄÏßÐÔ±í¡£
(5) ÿÖÖÊý¾Ý½á¹¹¶¼Ó¦¾ß±¸ÈýÖÖ»ù±¾ÔËË㣺²åÈ롢ɾ³ýºÍËÑË÷¡£

¶þ¡¢Éèµ¥Á´±íÖнáµãµÄ½á¹¹Îª
TYPEDEF STRUCT NODE { //Á´±í½áµã¶¨Òå
ELEMTYPE DATA; //Êý¾Ý
STRUCT NODE * LINK; //½áµãºó¼ÌÖ¸Õë
} LISTNODE;
(1) ÒÑÖªÖ¸ÕëPËùÖ¸½áµã²»ÊÇβ½áµã£¬ÈôÔÚ*PÖ®ºó²åÈë½áµã*S£¬ÔòÓ¦Ö´ÐÐÏÂÁÐÄÄÒ»¸ö²Ù×÷£¿
A. S->LINK = P; P->LINK = S;
B. S->LINK = P->LINK; P->LINK = S;
C. S->LINK = P->LINK; P = S;
D. P->LINK = S; S->LINK = P;

(2) ·Ç¿ÕµÄÑ­»·µ¥Á´±íFIRSTµÄβ½áµã£¨ÓÉPËùÖ¸Ïò£©Âú×㣺
A. P->LINK == NULL;
B. P == NULL;
C. P->LINK == FIRST;
D. P == FIRST;

Èý¡¢ÉèÓÐÒ»¸ö˳ÐòÕ»S£¬ÔªËØS1, S2, S3, S4, S5, S6ÒÀ´Î½øÕ»£¬Èç¹û6¸öÔªËصijöջ˳ÐòΪS2, S3, S4, S6, S5, S1£¬Ôò˳ÐòÕ»µÄÈÝÁ¿ÖÁÉÙӦΪ¶àÉÙ£¿

ËÄ¡¢Ò»¿Ã¾ßÓÐN¸ö½áµãµÄÀíÏëƽºâ¶þ²æÊ÷£¨¼´³ýÀë¸ù×îÔ¶µÄ×îµ×²ãÍâÆäËû¸÷²ã¶¼ÊÇÂúµÄ£¬×îµ×²ãÓÐÈô¸É½áµã£©ÓжàÉٲ㣿ÈôÉè¸ù½áµãÔÚµÚ0²ã£¬ÔòÊ÷µÄ¸ß¶ÈHÈçºÎÓÃNÀ´±íʾ£¨×¢ÒâN¿ÉÄÜΪ0£©£¿

Îå¡¢´Ó¹©Ñ¡ÔñµÄ´ð°¸ÖÐÑ¡ÔñÓëÏÂÃæÓйØͼµÄÐðÊöÖи÷À¨ºÅÏàÆ¥ÅäµÄ´Ê¾ä£¬½«Æä±àºÅÌîÈëÏàÓ¦µÄÀ¨ºÅÄÚ¡£
(1) ¶ÔÓÚÒ»¸ö¾ßÓÐN¸ö½áµãºÍEÌõ±ßµÄÎÞÏòͼ£¬Èô²ÉÓÃÁÚ½Ó±í±íʾ£¬Ôò¶¥µã±íµÄ´óСΪ£¨ A £©£¬ËùÓбßÁ´±íÖб߽áµãµÄ×ÜÊýΪ£¨ B £©¡£
(2) ²ÉÓÃÁÚ½Ó±í´æ´¢µÄͼµÄÉî¶ÈÓÅÏȱéÀúËã·¨ÀàËÆÓÚÊ÷µÄ£¨ C £©¡£
(3) ²ÉÓÃÁÚ½Ó±í´æ´¢µÄͼµÄ¹ã¶ÈÓÅÏȱéÀúËã·¨ÀàËÆÓÚÊ÷µÄ£¨ D £©¡£
(4) ÅжÏÓÐÏòͼÊÇ·ñ´æÔڻط£¬³ýÁË¿ÉÒÔÀûÓÃÍØÆËÅÅÐò·½·¨Í⣬»¹¿ÉÒÔÀûÓ㨠E £©¡£
¹©Ñ¡ÔñµÄ´ð°¸
A£º¢Ù N ¢Ú N+1 ¢Û N-1 ¢Ü N+E
B£º¢Ù E/2 ¢Ú E ¢Û 2E ¢Ü N+E
C~D£º¢Ù Öиù±éÀú ¢Ú Ïȸù±éÀú ¢Û ºó¸ù±éÀú ¢Ü °´²ã´Î±éÀú
E£º¢Ù Çó¹Ø¼ü·¾¶µÄ·½·¨ ¢Ú Çó×î¶Ì·¾¶µÄDIJKSTRA·½·¨
¢Û Éî¶ÈÓÅÏȱéÀúËã·¨ ¢Ü ¹ã¶ÈÓÅÏȱéÀúËã·¨

Áù¡¢Ìî¿ÕÌâ
(1) ÔÚÓÃÓÚ±íʾÓÐÏòͼµÄÁÚ½Ó¾ØÕóÖÐ, ¶ÔµÚIÐеÄÔªËؽøÐÐÀÛ¼Ó, ¿ÉµÃµ½µÚI ¸ö¶¥µãµÄ£¨ ¢Ù £©¶È, ¶ø¶ÔµÚJÁеÄÔªËؽøÐÐÀÛ¼Ó, ¿ÉµÃµ½µÚJ¸ö¶¥µãµÄ£¨ ¢Ú £©¶È¡£
(2) Ò»¸öÁ¬Í¨Í¼µÄÉú³ÉÊ÷ÊǸÃͼµÄ£¨ ¢Û £©Á¬Í¨×Óͼ¡£ÈôÕâ¸öÁ¬Í¨Í¼ÓÐN¸ö¶¥µã, ÔòËüµÄÉú³ÉÊ÷ÓУ¨ ¢Ü £©Ìõ±ß¡£
(3) ¸ø¶¨ÐòÁÐ{100, 86, 48, 73, 35, 39, 42, 57, 66, 21}, °´¶Ñ½á¹¹µÄ¶¨Òå, ÔòËüÒ»¶¨( ¢Ý )¶Ñ¡£
(4) ÔÚ½øÐÐÖ±½Ó²åÈëÅÅÐòʱ, ÆäÊý¾Ý±È½Ï´ÎÊýÓëÊý¾ÝµÄ³õʼÅÅÁУ¨ ¢Þ £©¹Ø£»¶øÔÚ½øÐÐÖ±½ÓÑ¡ÔñÅÅÐòʱ£¬ÆäÊý¾Ý±È½Ï´ÎÊýÓëÊý¾ÝµÄ³õʼÅÅÁУ¨ ¢ß £©¹Ø¡£
(5) ÀûÓùؼüÂë·Ö±ðΪ10, 20, 30, 40µÄËĸö½áµã£¬Äܹ¹Ôì³ö£¨ ¢à £©ÖÖ²»Í¬µÄ¶þ²æËÑË÷Ê÷¡£

Æß¡¢Éè´ø±íÍ·½áµãµÄË«ÏòÁ´±íµÄ¶¨ÒåΪ
TYPEDEF INT ELEMTYPE;

TYPEDEF STRUCT DNODE { //Ë«ÏòÁ´±í½áµã¶¨Òå
ELEMTYPE DATA; //Êý¾Ý
STRUCT DNODE * LLINK, * RLINK; //½áµãÇ°ÇýÓëºó¼ÌÖ¸Õë
} DBLNODE;

TYPEDEF DBLNODE * DBLLIST; //Ë«ÏòÁ´±í
ÊÔÉè¼ÆÒ»¸öËã·¨£¬¸ÄÔìÒ»¸ö´ø±íÍ·½áµãµÄË«ÏòÁ´±í£¬ËùÓнáµãµÄÔ­ÓдÎÐò±£³ÖÔÚ¸÷¸ö½áµãµÄÓÒÁ´ÓòRLINKÖУ¬²¢ÀûÓÃ×óÁ´ÓòLLINK°ÑËùÓнáµã°´ÕÕÆäÖµ´ÓСµ½´óµÄ˳ÐòÁ¬½ÓÆðÀ´¡£

°Ë¡¢ÉèÓÐÒ»¸ö¹Ø¼üÂëµÄÊäÈëÐòÁÐ { 55, 31, 11, 37, 46, 73, 63, 02, 07 },
(1) ´Ó¿ÕÊ÷¿ªÊ¼¹¹Ôìƽºâ¶þ²æËÑË÷Ê÷, »­³öÿ¼ÓÈëÒ»¸öнáµãʱ¶þ²æÊ÷µÄÐÎ̬¡£Èô·¢Éú²»Æ½ºâ, Ö¸Ã÷Ðè×öµÄƽºâÐýתµÄÀàÐͼ°Æ½ºâÐýתµÄ½á¹û¡£
(2) ¼ÆËã¸Ãƽºâ¶þ²æËÑË÷Ê÷ÔڵȸÅÂÊϵIJéÕҳɹ¦µÄƽ¾ù²éÕÒ³¤¶ÈºÍ²éÕÒ²»³É¹¦µÄƽ¾ù²éÕÒ³¤¶È¡£

¾Å¡¢ÏÂÃæÊÇÇóÁ¬Í¨ÍøÂçµÄ×îСÉú³ÉÊ÷µÄPRIMËã·¨µÄʵÏÖ£¬ÖмäÓÐ5¸öµØ·½È±Ê§£¬ÇëÔĶÁ³ÌÐòºó½«ËüÃDz¹ÉÏ¡£
CONST INT MAXINT = INT_MAX; //INT_MAXµÄÖµÔÚÖÐ
CONST INT N = 6; //ͼµÄ¶¥µãÊý, Ó¦ÓÉÓû§¶¨Òå
TYPEDEF INT ADJMATRIX[N>[N>; //ÓöþάÊý×é×÷ΪÁÚ½Ó¾ØÕó±íʾ
TYPEDEF STRUCT { //Éú³ÉÊ÷µÄ±ß½áµã
INT FROMVEX, TOVEX; //±ßµÄÆðµãÓëÖÕµã
INT WEIGHT; //±ßÉϵÄȨֵ
} TREEEDGENODE;
TYPEDEF TREEEDGENODE MST[N-1>; //×îСÉú³ÉÊ÷¶¨Òå

VOID PRIMMST ( ADJMATRIX G, MST T, INT RT ) {
//´Ó¶¥µãRT³ö·¢¹¹ÔìͼGµÄ×îСÉú³ÉÊ÷T£¬RT³ÉΪÊ÷µÄ¸ù½áµã
TREEEDGENODE E; INT I, K = 0, MIN, MINPOS, V;
FOR ( I = 0; I < N; I++ ) //³õʼ»¯×îСÉú³ÉÊ÷T
IF ( I != RT ) {
T[K>.FROMVEX = RT;
T[K>.TOVEX = I ;
T[K++>.WEIGHT = G[RT>;
}
FOR ( K = 0; K < N-1; K++ ) { //ÒÀ´ÎÇóMSTµÄºòÑ¡±ß
MIN = MAXINT ;
FOR ( I = K; I < N-1; I++ ) //±éÀúµ±Ç°ºòÑ¡±ß¼¯ºÏ
IF ( T.WEIGHT < MIN ) //Ñ¡¾ßÓÐ×îСȨֵµÄºòÑ¡±ß
{ MIN = T.WEIGHT; MINPOS = I ; }
IF ( MIN == MAXINT ) //ͼ²»Á¬Í¨, ³ö´í´¦Àí
{ CERR << ¡°GRAPH IS DISCONNECTED!¡± << ENDL; EXIT(1) ; }
E = T[MINPOS>; T[MINPOS> = T[K> ; T[K> = E;
V = T[K>.TOVEX;
FOR ( I = K+1; I < N-1; I++ ) //Ð޸ĺòÑ¡±ß¼¯ºÏ
IF ( G[V>[T.TOVEX> < T.WEIGHT ) {
T.WEIGHT = G[V>[T.TOVEX>;
T.FROMVEX = V ;
}
}
}

²Î¿¼´ð°¸

Ò»¡¢(1) ´í (2) ´í (3) ¶Ô (4) ´í (5) ¶Ô

¶þ¡¢(1) B (2) C

Èý¡¢3

ËÄ¡¢H = ¨¦LOG2(N+1)¨´ -1

Îå¡¢A. ¢Ù B. ¢Û C. ¢Ú D. ¢Ü E. ¢Û

Áù¡¢¢Ù ³ö ¢Ú Èë ¢Û ¼«Ð¡ ¢Ü N-1
¢Ý ÊÇ£¨×îС£© ¢Þ ÓÐ ¢ß ÎÞ ¢à 14

Æß¡¢Ëã·¨ÈçÏÂ
VOID SORT ( DBLNODE * L ) {
DBLNODE * S = L->RLINK;
//Ö¸ÕëSÖ¸Ïò´ý²åÈë½áµã, ³õʼʱָÏòµÚÒ»¸ö½áµã
WHILE ( S != NULL ) { //´¦ÀíËùÓнáµã
PRE = L; P = L->LLINK;
//Ö¸ÕëPÖ¸Ïò´ý±È½ÏµÄ½áµã, PREÊÇPµÄÇ°ÇýÖ¸Õë
WHILE ( P != NULL && S->DATA < P->DATA )
//Ñ­LLINKÁ´Ñ°ÕÒ½áµã *SµÄ²åÈëλÖÃ
{ PRE = P; P = P->LLINK; }
PRE->LLINK = S; S->LLINK = P; S = S->RLINK;
//½áµã *SÔÚLLINK·½Ïò²åÈëµ½ *PREÓë *PÖ®¼ä
}
}

°Ë¡¢¹Ø¼üÂëµÄÊäÈëÐòÁÐ { 55, 31, 11, 37, 46, 73, 63, 02, 07 }