《2021年澳門特別行政區(qū)數(shù)據(jù)要領(lǐng)加強(qiáng)》由會(huì)員分享，可在線閱讀，更多相關(guān)《2021年澳門特別行政區(qū)數(shù)據(jù)要領(lǐng)加強(qiáng)（6頁珍藏版）》請(qǐng)?jiān)谘b配圖網(wǎng)上搜索。
1、2021年澳門特別行政區(qū)數(shù)據(jù)要領(lǐng)加強(qiáng)
1、冒泡排序算法是把大的元素向上移（氣泡的上?。?，也可以把小的元素向下移（氣泡的下沉）請(qǐng)給出上浮和下沉過程交替的冒泡排序算法。
48.有n個(gè)記錄存儲(chǔ)在帶頭結(jié)點(diǎn)的雙向鏈表中，現(xiàn)用雙向起泡排序法對(duì)其按上升序進(jìn)行排序，請(qǐng)寫出這種排序的算法。（注：雙向起泡排序即相鄰兩趟排序向相反方向起泡）
2、假設(shè)以I和O分別表示入棧和出棧操作。棧的初態(tài)和終態(tài)均為空，入棧和出棧的操作序列可表示為僅由I和O組成的序列，稱可以操作的序列為合法序列，否則稱為非法序列。（15分）
（1）A和D是合法序列，B和C 是非法序列。
（2）設(shè)被判定的操作序列已存入一維數(shù)組A中。
in
2、t Judge(char A[])
//判斷字符數(shù)組A中的輸入輸出序列是否是合法序列。如是，返回true，否則返回false。
{i=0; //i為下標(biāo)。
j=k=0; //j和k分別為I和字母O的的個(gè)數(shù)。
while(A[i]!=‘\0’) //當(dāng)未到字符數(shù)組尾就作。
{switch(A[i])
{case‘I’: j++; break; //入棧次數(shù)增1。
case‘O’: k++; if(k>j){printf(“序列非法\n”)；exit(0);}
}
i++; //不論A[i]是‘I’或‘O’，指針i均后移。}
if(j!=k) {printf(“序列非法\n”)
3、；return(false);}
else {printf(“序列合法\n”)；return(true);}
}//算法結(jié)束。
3、有一種簡單的排序算法，叫做計(jì)數(shù)排序（count sorting）。這種排序算法對(duì)一個(gè)待排序的表(用數(shù)組表示)進(jìn)行排序，并將排序結(jié)果存放到另一個(gè)新的表中。必須注意的是，表中所有待排序的關(guān)鍵碼互不相同，計(jì)數(shù)排序算法針對(duì)表中的每個(gè)記錄，掃描待排序的表一趟，統(tǒng)計(jì)表中有多少個(gè)記錄的關(guān)鍵碼比該記錄的關(guān)鍵碼小，假設(shè)針對(duì)某一個(gè)記錄，統(tǒng)計(jì)出的計(jì)數(shù)值為c，那么，這個(gè)記錄在新的有序表中的合適的存放位置即為c。
(1) (3分)給出適用于計(jì)數(shù)排序的數(shù)據(jù)表定義;
(2) (7分)
4、使用Pascal或C語言編寫實(shí)現(xiàn)計(jì)數(shù)排序的算法；
(3) (4分)對(duì)于有n個(gè)記錄的表，關(guān)鍵碼比較次數(shù)是多少?
(4) (3分)與簡單選擇排序相比較，這種方法是否更好?為什么?
4、有一種簡單的排序算法，叫做計(jì)數(shù)排序（count sorting）。這種排序算法對(duì)一個(gè)待排序的表(用數(shù)組表示)進(jìn)行排序，并將排序結(jié)果存放到另一個(gè)新的表中。必須注意的是，表中所有待排序的關(guān)鍵碼互不相同，計(jì)數(shù)排序算法針對(duì)表中的每個(gè)記錄，掃描待排序的表一趟，統(tǒng)計(jì)表中有多少個(gè)記錄的關(guān)鍵碼比該記錄的關(guān)鍵碼小，假設(shè)針對(duì)某一個(gè)記錄，統(tǒng)計(jì)出的計(jì)數(shù)值為c，那么，這個(gè)記錄在新的有序表中的合適的存放位置即為c。
(1) (3分)給出
5、適用于計(jì)數(shù)排序的數(shù)據(jù)表定義;
(2) (7分)使用Pascal或C語言編寫實(shí)現(xiàn)計(jì)數(shù)排序的算法；
(3) (4分)對(duì)于有n個(gè)記錄的表，關(guān)鍵碼比較次數(shù)是多少?
(4) (3分)與簡單選擇排序相比較，這種方法是否更好?為什么?
5、設(shè)有一個(gè)數(shù)組中存放了一個(gè)無序的關(guān)鍵序列K1、K2、…、Kn。現(xiàn)要求將Kn放在將元素排序后的正確位置上，試編寫實(shí)現(xiàn)該功能的算法，要求比較關(guān)鍵字的次數(shù)不超過n。
51. 借助于快速排序的算法思想，在一組無序的記錄中查找給定關(guān)鍵字值等于key的記錄。設(shè)此組記錄存放于數(shù)組r[l..h]中。若查找成功，則輸出該記錄在r數(shù)組中的位置及其值，否則顯示“not find”信息。
6、請(qǐng)編寫出算法并簡要說明算法思想。
6、有一個(gè)帶頭結(jié)點(diǎn)的單鏈表，每個(gè)結(jié)點(diǎn)包括兩個(gè)域，一個(gè)是整型域info，另一個(gè)是指向下一個(gè)結(jié)點(diǎn)的指針域next。假設(shè)單鏈表已建立，設(shè)計(jì)算法刪除單鏈表中所有重復(fù)出現(xiàn)的結(jié)點(diǎn)，使得info域相等的結(jié)點(diǎn)只保留一個(gè)。
#include typedef char datatype;
typedef struct node{
datatype data;
struct node * next;
} listnode;
typedef listnode* linklist;
/*------------------------------------------
7、--*/
/* 刪除單鏈表中重復(fù)的結(jié)點(diǎn) */
/*--------------------------------------------*/
linklist deletelist(linklist head)
{ listnode *p,*s,*q;
p=head->next;
while(p)
{s=p;
q=p->next;
while(q)
if(q->data==p->data)
{s->next=q->next;free(q);
q=s->next;}
else
{ s=q; /*找與P結(jié)點(diǎn)值相同的結(jié)點(diǎn)*/
q=q->next;
}
p=p->n
8、ext;
}
return head;
}
7、連通圖的生成樹包括圖中的全部n個(gè)頂點(diǎn)和足以使圖連通的n-1條邊，最小生成樹是邊上權(quán)值之和最小的生成樹。故可按權(quán)值從大到小對(duì)邊進(jìn)行排序，然后從大到小將邊刪除。每刪除一條當(dāng)前權(quán)值最大的邊后，就去測試圖是否仍連通，若不再連通，則將該邊恢復(fù)。若仍連通，繼續(xù)向下刪；直到剩n-1條邊為止。
void SpnTree (AdjList g)
//用“破圈法”求解帶權(quán)連通無向圖的一棵最小代價(jià)生成樹。
{typedef struct {int i,j,w}node; //設(shè)頂點(diǎn)信息就是頂點(diǎn)編號(hào)，權(quán)是整型數(shù)
node edge[];
scanf(
9、"%d%d",&e,&n) ; //輸入邊數(shù)和頂點(diǎn)數(shù)。
for (i=1;iscanf("%d%d%d" ,&edge[i].i ,&edge[i].j ,&edge[i].w);
for (i=2;i{edge[0]=edge[i]; j=i-1;
while (edge[j].wedge[j+1]=edge[0]; }//for
k=1; eg=e;
while (eg>=n) //破圈，直到邊數(shù)e=n-1.
{if (connect(k)) //刪除第k條邊若仍連通。
{edge[k].w=0; eg--; }//測試下一條邊edge[k]，權(quán)值置0表示該邊被刪除k++; //下條邊
}//while
}//算法結(jié)束。
connect()是測試圖是否連通的函數(shù)，可用圖的遍歷實(shí)現(xiàn)，
8、給出折半查找的遞歸算法，并給出算法時(shí)間復(fù)雜度性分析。
2021年澳門特別行政區(qū)數(shù)據(jù)要領(lǐng)加強(qiáng)
