九九影院午夜理论片少妇,少妇真人直播免费视频,国产人妻丰满熟妇嗷嗷叫

第一篇：數(shù)據(jù)結(jié)構(gòu)第九章排序習(xí)題及答案[小編推薦]

習(xí)題九

排序

一、單項選擇題

1．下列內(nèi)部排序算法中：

A．快速排序 B.直接插入排序 C.二路歸并排序 D.簡單選擇排序 E.起泡排序 F.堆排序

（1）其比較次數(shù)與序列初態(tài)無關(guān)的算法是（）（2）不穩(wěn)定的排序算法是（）

（3）在初始序列已基本有序（除去n個元素中的某k個元素后即呈有序，k<

（4）排序的平均時間復(fù)雜度為O(n?logn)的算法是（）為O(n?n)的算法是（）2．比較次數(shù)與排序的初始狀態(tài)無關(guān)的排序方法是()。

A．直接插入排序 B．起泡排序 C．快速排序 D．簡單選擇排序 3．對一組數(shù)據(jù)（84，47，25，15，21）排序，數(shù)據(jù)的排列次序在排序的過程中的變化為（1）84 47 25 15 21（2）15 47 25 84 21（3）15 21 25 84 47（4）15 21 25 47 84 則采用的排序是()。

A.選擇 B.冒泡 C.快速 D.插入

4．下列排序算法中()排序在一趟結(jié)束后不一定能選出一個元素放在其最終位置上。

A.選擇 B.冒泡 C.歸并 D.堆 5．一組記錄的關(guān)鍵碼為（46，79，56，38，40，84），則利用快速排序的方法，以第一個記錄為基準(zhǔn)得到的一次劃分結(jié)果為（）。

A．(38,40,46,56,79,84)B.(40,38,46,79,56,84)C．(40,38,46,56,79,84)D.(40,38,46,84,56,79)6．下列排序算法中，在待排序數(shù)據(jù)已有序時，花費時間反而最多的是()排序。A．冒泡 B.希爾 C.快速 D.堆

7.就平均性能而言，目前最好的內(nèi)排序方法是()排序法。

A.冒泡 B.希爾插入 C.交換 D.快速 8.下列排序算法中，占用輔助空間最多的是：()A.歸并排序 B.快速排序 C.希爾排序 D.堆排序

9.若用冒泡排序方法對序列{10,14,26,29,41,52}從大到小排序，需進(jìn)行（）次比較。

A.3 B.10 C.15 D.25 10.快速排序方法在（）情況下最不利于發(fā)揮其長處。

A.要排序的數(shù)據(jù)量太大 B.要排序的數(shù)據(jù)中含有多個相同值 C.要排序的數(shù)據(jù)個數(shù)為奇數(shù) D.要排序的數(shù)據(jù)已基本有序 11．下列四個序列中，哪一個是堆（）。

A.75,65,30,15,25,45,20,10 B.75,65,45,10,30,25,20,15 C.75,45,65,30,15,25,20,10 D.75,45,65,10,25,30,20,15 12.有一組數(shù)據(jù)（15，9，7，8，20，-1，7，4），用堆排序的篩選方法建立的初始堆為（）

A．-1，4，8，9，20，7，15，7 B．-1，7，15，7，4，8，20，9 C．-1，4，7，8，20，15，7，9 D．A，B，C均不對。

二、填空題

1.若待排序的序列中存在多個記錄具有相同的鍵值，經(jīng)過排序，這些記錄的相對次序仍然保持不變，則稱這種排序方法是________的，否則稱為________的。

2.按照排序過程涉及的存儲設(shè)備的不同，排序可分為________排序和________排序。

3．直接插入排序用監(jiān)視哨的作用是___________________________。

4．對n個記錄的表r[1..n]進(jìn)行簡單選擇排序，所需進(jìn)行的關(guān)鍵字間的比較次數(shù)為_______。

5．下面的c函數(shù)實現(xiàn)對鏈表head進(jìn)行選擇排序的算法,排序完畢,鏈表中的結(jié)點按結(jié)點值從小到大鏈接。請在空框處填上適當(dāng)內(nèi)容,每個空框只填一個語句或一個表達(dá)式： #include typedef struct node {char data;struct node *link;}node;node *select(node *head){node *p,*q,*r,*s;p=(node *)malloc(sizeof(node));p->link=head;head=p;while(p->link!=null){q=p->link;r=p;while((1)____________){ if(q->link->datalink->data)r=q;q=q->link;} if((2)___________){s=r->link;r->link=s->link;

s->link=((3)_________);((4)_________);}((5)________);} p=head;head=head->link;free(p);return(head);}

6．下面的排序算法的思想是：第一趟比較將最小的元素放在r[1]中，最大的元素放在r[n]中，第二趟比較將次小的放在r[2]中，將次大的放在r[n-1]中，…,依次下去，直到待排序列為遞增序。（注：<-->）代表兩個變量的數(shù)據(jù)交換）。

void sort(SqList &r,int n){ i=1;while((1)______){ min=max=1;for(j=i+1;(2)________;++j){if((3)________)min=j;else if(r[j].key>r[max].key)max=j;} if((4)_________)r[min] <---->r[j];if(max!=n-i+1){if((5)_______)r[min] <----> r[n-i+1];else((6)______);} i++;} }//sort

7．下列算法為奇偶交換排序，思路如下：第一趟對所有奇數(shù)的i,將a[i]和a[i+1]進(jìn)行比較,第二趟對所有偶數(shù)的i,將a[i]和a[i+1]進(jìn)行比較,每次比較時若a[i]>a[i+1],將二者交換;以后重復(fù)上述二趟過程,直至整個數(shù)組有序。

void oesort(int a[n]){int flag,i,t;do {flag=0;for(i=1;ia[i+1]){flag=(1)______;t=a[i+1];a[i+1]=a[i];(2)________;} for(3)________ if(a[i]>a[i+1]){flag=(4)________;t=a[i+1];a[i+1]=a[i];a[i]=t;} }while(5)_________;}

第九章排序

一、單項選擇題 1．（1）DC（2）ADF（3）B（4）ACF BDE 2．D 3．A 4．C 5．C 6．C 7.D 8.A 9.C 10.D 11．C 12.C

二、填空題 1.穩(wěn)定、不穩(wěn)定 2.內(nèi)部、外部

3．免去查找過程中每一步都要檢測整個表是否查找完畢，提高了查找效率。4．n(n-1)/2 5．題中為操作方便，先增加頭結(jié)點（最后刪除），p指向無序區(qū)的前一記錄，r指向最小值結(jié)點的前驅(qū)，一趟排序結(jié)束，無序區(qū)第一個記錄與r所指結(jié)點的后繼交換指針。

(1)q->link!=NULL(2)r!=p(3)p->link(4)p->link=s(5)p=p->link 6．.(1)ir[n-i+1] 7．(1)1(2)a[i]=t(3)(i=2;i<=n;i+=2)(4)1(5)flag

第二篇：數(shù)據(jù)結(jié)構(gòu)習(xí)題與答案

第 1 章緒論

課后習(xí)題講解

1.填空

⑴（）是數(shù)據(jù)的基本單位，在計算機程序中通常作為一個整體進(jìn)行考慮和處理。【解答】數(shù)據(jù)元素

⑵（）是數(shù)據(jù)的最小單位，（）是討論數(shù)據(jù)結(jié)構(gòu)時涉及的最小數(shù)據(jù)單位。【解答】數(shù)據(jù)項，數(shù)據(jù)元素

【分析】數(shù)據(jù)結(jié)構(gòu)指的是數(shù)據(jù)元素以及數(shù)據(jù)元素之間的關(guān)系。

⑶ 從邏輯關(guān)系上講，數(shù)據(jù)結(jié)構(gòu)主要分為（）、（）、（）和（）。【解答】集合，線性結(jié)構(gòu)，樹結(jié)構(gòu)，圖結(jié)構(gòu)

⑷ 數(shù)據(jù)的存儲結(jié)構(gòu)主要有（）和（）兩種基本方法，不論哪種存儲結(jié)構(gòu)，都要存儲兩方面的內(nèi)容：（）和（）。

【解答】順序存儲結(jié)構(gòu)，鏈接存儲結(jié)構(gòu)，數(shù)據(jù)元素，數(shù)據(jù)元素之間的關(guān)系

⑸ 算法具有五個特性，分別是（）、（）、（）、（）、（）。【解答】有零個或多個輸入，有一個或多個輸出，有窮性，確定性，可行性

⑹ 算法的描述方法通常有（）、（）、（）和（）四種，其中，（）被稱為算法語言。【解答】自然語言，程序設(shè)計語言，流程圖，偽代碼，偽代碼

⑺ 在一般情況下，一個算法的時間復(fù)雜度是（）的函數(shù)。【解答】問題規(guī)模

⑻ 設(shè)待處理問題的規(guī)模為n，若一個算法的時間復(fù)雜度為一個常數(shù)，則表示成數(shù)量級的形式為（），若為n*log25n，則表示成數(shù)量級的形式為（）。【解答】Ο(1)，Ο(nlog2n)

【分析】用大O記號表示算法的時間復(fù)雜度，需要將低次冪去掉，將最高次冪的系數(shù)去掉。2.選擇題

⑴ 順序存儲結(jié)構(gòu)中數(shù)據(jù)元素之間的邏輯關(guān)系是由（）表示的，鏈接存儲結(jié)構(gòu)中的數(shù)據(jù)元素之間的邏輯關(guān)系是由（）表示的。

A 線性結(jié)構(gòu) B 非線性結(jié)構(gòu) C 存儲位置 D 指針【解答】C，D

【分析】順序存儲結(jié)構(gòu)就是用一維數(shù)組存儲數(shù)據(jù)結(jié)構(gòu)中的數(shù)據(jù)元素，其邏輯關(guān)系由存儲位置（即元素在數(shù)組中的下標(biāo)）表示；鏈接存儲結(jié)構(gòu)中一個數(shù)據(jù)元素對應(yīng)鏈表中的一個結(jié)點，元素之間的邏輯關(guān)系由結(jié)點中的指針表示。⑵ 假設(shè)有如下遺產(chǎn)繼承規(guī)則：丈夫和妻子可以相互繼承遺產(chǎn)；子女可以繼承父親或母親的遺產(chǎn)；子女間不能相互繼承。則表示該遺產(chǎn)繼承關(guān)系的最合適的數(shù)據(jù)結(jié)構(gòu)應(yīng)該是（）。A 樹 B 圖 C 線性表 D 集合【解答】B 【分析】將丈夫、妻子和子女分別作為數(shù)據(jù)元素，根據(jù)題意畫出邏輯結(jié)構(gòu)圖。

⑶ 算法指的是（）。

A 對特定問題求解步驟的一種描述，是指令的有限序列。B 計算機程序 C 解決問題的計算方法 D 數(shù)據(jù)處理【解答】A 【分析】計算機程序是對算法的具體實現(xiàn)；簡單地說，算法是解決問題的方法；數(shù)據(jù)處理是通過算法完成的。所以，只有A是算法的準(zhǔn)確定義。⑷ 下面（）不是算法所必須具備的特性。A 有窮性 B 確切性 C 高效性 D 可行性【解答】C

【分析】高效性是好算法應(yīng)具備的特性。

⑸ 算法分析的目的是（），算法分析的兩個主要方面是（）。A 找出數(shù)據(jù)結(jié)構(gòu)的合理性 B 研究算法中輸入和輸出的關(guān)系 C 分析算法的效率以求改進(jìn) D 分析算法的易讀性和文檔性

E 空間性能和時間性能 F 正確性和簡明性

G 可讀性和文檔性 H 數(shù)據(jù)復(fù)雜性和程序復(fù)雜性【解答】C，E 3.判斷題

⑴ 算法的時間復(fù)雜度都要通過算法中的基本語句的執(zhí)行次數(shù)來確定。【解答】錯。時間復(fù)雜度要通過算法中基本語句執(zhí)行次數(shù)的數(shù)量級來確定。⑵ 每種數(shù)據(jù)結(jié)構(gòu)都具備三個基本操作：插入、刪除和查找。

【解答】錯。如數(shù)組就沒有插入和刪除操作。此題注意是每種數(shù)據(jù)結(jié)構(gòu)。

⑶ 所謂數(shù)據(jù)的邏輯結(jié)構(gòu)指的是數(shù)據(jù)之間的邏輯關(guān)系。【解答】錯。是數(shù)據(jù)之間的邏輯關(guān)系的整體。

⑷ 邏輯結(jié)構(gòu)與數(shù)據(jù)元素本身的內(nèi)容和形式無關(guān)。【解答】對。因此邏輯結(jié)構(gòu)是數(shù)據(jù)組織的主要方面。⑸ 基于某種邏輯結(jié)構(gòu)之上的基本操作，其實現(xiàn)是唯一的。

【解答】錯。基本操作的實現(xiàn)是基于某種存儲結(jié)構(gòu)設(shè)計的，因而不是唯一的。4.分析以下各程序段，并用大O記號表示其執(zhí)行時間。

【解答】⑴ 基本語句是k=k+10*i，共執(zhí)行了n-2次，所以T(n)=O(n)。

⑵ 基本語句是k=k+10*i，共執(zhí)行了n次，所以T(n)=O(n)。

⑶ 分析條件語句，每循環(huán)一次，i+j 整體加1，共循環(huán)n次，所以T(n)=O(n)。

⑷ 設(shè)循環(huán)體共執(zhí)行T(n)次，每循環(huán)一次，循環(huán)變量y加1，最終T(n)=y，即：

(T(n)+1)2≤n，所以T(n)=O(n1/2)。

⑸ x++是基本語句，所以

5．設(shè)有數(shù)據(jù)結(jié)構(gòu)（D，R），其中D={1, 2, 3, 4, 5, 6}，R={(1,2),(2,3),(2,4),(3,4),(3,5),(3,6),(4,5),(4,6)}。試畫出其邏輯結(jié)構(gòu)圖并指出屬于何種結(jié)構(gòu)。

【解答】其邏輯結(jié)構(gòu)圖如圖1-3所示，它是一種圖結(jié)構(gòu)。

6.為整數(shù)定義一個抽象數(shù)據(jù)類型，包含整數(shù)的常見運算，每個運算對應(yīng)一個基本操作，每個基本操作的接口需定義前置條件、輸入、功能、輸出和后置條件。【解答】整數(shù)的抽象數(shù)據(jù)類型定義如下：

ADT integer Data 整數(shù)a：可以是正整數(shù)(1, 2, 3, …)、負(fù)整數(shù)(-1,-2,-3, …)和零 Operation Constructor

前置條件：整數(shù)a不存在輸入：一個整數(shù)b

功能：構(gòu)造一個與輸入值相同的整數(shù) 輸出：無

后置條件：整數(shù)a具有輸入的值

Set 前置條件：存在一個整數(shù)a 輸入：一個整數(shù)b

功能：修改整數(shù)a的值，使之與輸入的整數(shù)值相同

輸出：無

后置條件：整數(shù)a的值發(fā)生改變

Add