D數(shù)據(jù)結(jié)構(gòu)與算法-C資料文檔

D數(shù)據(jù)結(jié)構(gòu)與算法——C資料文檔第1頁，共9頁第1頁，共9頁選擇題（共15題，每題3分）（1）下面關(guān)于算法說法錯(cuò)誤的是__D_____。a.算法最終必須由計(jì)算機(jī)程序?qū)崿F(xiàn)/*不見得，有些算法是NP完全問題，計(jì)算機(jī)程序只能實(shí)現(xiàn)低數(shù)量的值，對于高數(shù)量的是實(shí)現(xiàn)不了的。*/

b.為解決某問題的算法同為該問題編寫的程序含義是相同的

/**/c.算法的可行性是指指令不能有二義性

d.以上幾個(gè)都是錯(cuò)誤的

（2）下面說法錯(cuò)誤的是___A,D___.

a.算法原地工作的含義是指不需要任何額外的輔助空間

b.在相同的規(guī)模n下，復(fù)雜度O(n)的算法在時(shí)間上總是優(yōu)于復(fù)雜度O(2n)的算法

c.所謂時(shí)間復(fù)雜度是指最壞情況下，估算算法執(zhí)行時(shí)間的一個(gè)上界

d.同一個(gè)算法，實(shí)現(xiàn)語言的級(jí)別越高，執(zhí)行效率就越低

（3）在下面的程序段中，對x的賦值語句的頻度為___C__。

for(inti;i<n;i++)

{for(intj=o;j<n;j++)

{x:=x+1;

}}

a.0(2n)

b.0(n)

c.0(n2)

d.O(log2n)

這個(gè)是選擇Co(n2)

這個(gè)是嵌套循環(huán)循環(huán)次數(shù)是n*nD數(shù)據(jù)結(jié)構(gòu)與算法——C資料文檔全文共9頁，當(dāng)前為第1頁。（4）下面說法正確的是__C____。

b.數(shù)據(jù)元素是數(shù)據(jù)的最小單位；

c.數(shù)據(jù)的物理結(jié)構(gòu)是指數(shù)據(jù)在計(jì)算機(jī)內(nèi)的實(shí)際存儲(chǔ)形式

d.數(shù)據(jù)結(jié)構(gòu)的抽象操作的定義與具體實(shí)現(xiàn)有關(guān)

我的回答的前提是你是在進(jìn)行面向?qū)ο缶幊?/p>

D數(shù)據(jù)結(jié)構(gòu)與算法——C資料文檔全文共9頁，當(dāng)前為第1頁。第2頁，共9頁第2頁，共9頁個(gè)人認(rèn)為沒有關(guān)系，而且在面向?qū)ο缶幊讨?，抽象本來就是不考慮具體的實(shí)現(xiàn)細(xì)節(jié)，只是對事物的本質(zhì)和特征的描述。同樣對數(shù)據(jù)結(jié)構(gòu)的抽象操作的定義，在面向?qū)ο蟮木幊讨兄徊贿^把事物具體化成了數(shù)據(jù)結(jié)構(gòu)而已，也次結(jié)構(gòu)的具體實(shí)現(xiàn)應(yīng)該是分開的，比如對數(shù)據(jù)棧的定義在抽象他的操作時(shí)我們只care他能有什么操作，至于實(shí)現(xiàn)我們可以通過數(shù)組來，或鏈表來實(shí)現(xiàn)。（5）下面說法正確的是_______。

a.在順序存儲(chǔ)結(jié)構(gòu)中，有時(shí)也存儲(chǔ)數(shù)據(jù)結(jié)構(gòu)中元素之間的關(guān)系答：錯(cuò)。

說明：“順序存儲(chǔ)結(jié)構(gòu)”必須體現(xiàn)元素之間的關(guān)系，不是“有時(shí)”。

“鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)”并不是“順序存儲(chǔ)結(jié)構(gòu)”，后者稱“順序表”或“鄰接表”。

有些書用“鏈表是順序存取”說法，但并不是指“鏈表是順序存儲(chǔ)結(jié)構(gòu)”。

b.順序存儲(chǔ)方式的優(yōu)點(diǎn)是存儲(chǔ)密度大，且插入、刪除運(yùn)算效率高

c.數(shù)據(jù)結(jié)構(gòu)的基本操作的設(shè)置的最重要的準(zhǔn)則是，實(shí)現(xiàn)應(yīng)用程序與存儲(chǔ)結(jié)構(gòu)的獨(dú)立數(shù)據(jù)結(jié)構(gòu)主要從邏輯結(jié)構(gòu)和物理結(jié)構(gòu)兩個(gè)方面來看

而邏輯結(jié)構(gòu)主要是對該結(jié)構(gòu)操作的設(shè)定，物理結(jié)構(gòu)是描述數(shù)據(jù)具體在內(nèi)存中的存儲(chǔ)（如：順序結(jié)構(gòu)、鏈?zhǔn)浇Y(jié)構(gòu)、索引結(jié)構(gòu)、希哈結(jié)構(gòu)）等。

d.數(shù)據(jù)的邏輯結(jié)構(gòu)說明數(shù)據(jù)元素之間的順序關(guān)系,它依賴于計(jì)算機(jī)的儲(chǔ)存結(jié)構(gòu)答：錯(cuò).

說明：邏輯結(jié)構(gòu)可用不同的存儲(chǔ)結(jié)構(gòu)實(shí)現(xiàn)，“它依賴于計(jì)算機(jī)的存儲(chǔ)結(jié)構(gòu)”完全說不通。

D數(shù)據(jù)結(jié)構(gòu)與算法——C資料文檔全文共9頁，當(dāng)前為第2頁。（6）

下述_____是順序存儲(chǔ)結(jié)構(gòu)的特點(diǎn)。

a.存儲(chǔ)密度大

b.插入運(yùn)算不方便

c.刪除運(yùn)算不方便

D數(shù)據(jù)結(jié)構(gòu)與算法——C資料文檔全文共9頁，當(dāng)前為第2頁。第3頁，共9頁第3頁，共9頁d.可方便地用于各種邏輯結(jié)構(gòu)的存儲(chǔ)表示

（7）下面關(guān)于線性表的敘述中，錯(cuò)誤的是_____。

a.線性表采用順序存儲(chǔ)，必須占用一片連續(xù)的存儲(chǔ)單元

b.線性表采用順序存儲(chǔ)，便于進(jìn)行插入和刪除操作

c.線性表采用鏈接存儲(chǔ)，不必占用一片連續(xù)的存儲(chǔ)單元

d.線性表采用鏈接存儲(chǔ)，便于插入和刪除操作

（8）某線性表中最常用的操作是在最后一個(gè)元素之后插入一個(gè)元素和刪除第一個(gè)元素，則采用___A____存儲(chǔ)方式最節(jié)省時(shí)間。

a.順序表

b.雙鏈表

c.帶頭結(jié)點(diǎn)的雙循環(huán)鏈表

d.單循環(huán)鏈表

（9）靜態(tài)鏈表中指針表示的是______。

a.內(nèi)存地址

b.數(shù)組下標(biāo)

c.下一元素地址

d.左、右孩子地址

（10）下面的敘述不正確的是_______。

a.線性表在鏈?zhǔn)酱鎯?chǔ)時(shí)，查找第i個(gè)元素的時(shí)間同i的值成正比

b.線性表在鏈?zhǔn)酱鎯?chǔ)時(shí)，查找第i個(gè)元素的時(shí)間同i的值無關(guān)

c.線性表在順序存儲(chǔ)時(shí)，查找第i個(gè)元素的時(shí)間同i的值成正比

d.線性表在順序存儲(chǔ)時(shí)，查找第i個(gè)元素的時(shí)間同i的值無關(guān)

（11）下面說法錯(cuò)誤的是_____。

a.靜態(tài)鏈表既有順序存儲(chǔ)的優(yōu)點(diǎn)，又有動(dòng)態(tài)鏈表的優(yōu)點(diǎn)。所以，它存取表中第i個(gè)元素的時(shí)間與i無關(guān)。

b.靜態(tài)鏈表中能容納的元素個(gè)數(shù)的最大數(shù)在表定義時(shí)就確定了，以后不能增加。

c.靜態(tài)鏈表與動(dòng)態(tài)鏈表在元素的插入、刪除上類似，不需做元素的移動(dòng)。

d.靜態(tài)鏈表就是一直不發(fā)生變化的鏈表。

D數(shù)據(jù)結(jié)構(gòu)與算法——C資料文檔全文共9頁，當(dāng)前為第3頁。（12）在雙向鏈表指針p的結(jié)點(diǎn)前插入一個(gè)指針q的結(jié)點(diǎn)操作是______。

a.p->Llink=q;q->Rlink=p;p->Llink->Rlink=q;q->Llink=q；

b.p->Llink=q;p->Llink->Rlink=q;q->Rlink=p;q->Llink=p->Llink;

c.q->Rlink=p;q->Llink=p->Llink;p->Llink->Rlink=q;p->Llink=q;

D數(shù)據(jù)結(jié)構(gòu)與算法——C資料文檔全文共9頁，當(dāng)前為第3頁。第4頁，共9頁第4頁，共9頁d.q->Llink=p->Llink;q->Rlink=q;p->Llink=q;p->Llink=q;

（13）下面說法正確的是______。

a.順序存儲(chǔ)結(jié)構(gòu)的主要缺點(diǎn)是不利于插入或刪除操作；

b.線性表采用鏈表存儲(chǔ)時(shí)，結(jié)點(diǎn)和結(jié)點(diǎn)內(nèi)部的存儲(chǔ)空間可以是不連續(xù)的；

c.順序存儲(chǔ)方式插入和刪除時(shí)效率太低，因此它不如鏈?zhǔn)酱鎯?chǔ)方式好；

d.順序存儲(chǔ)方式只能用于存儲(chǔ)線性結(jié)構(gòu)。

（14）下面說法正確的是______。

a.線性表只能用順序存儲(chǔ)結(jié)構(gòu)實(shí)現(xiàn)。

b.為了很方便的插入和刪除數(shù)據(jù)，可以使用雙向鏈表存放數(shù)據(jù)。

c.順序存儲(chǔ)方式的優(yōu)點(diǎn)是存儲(chǔ)密度大，且插入、刪除運(yùn)算效率高。

d.鏈表是采用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)的線性表,進(jìn)行插入、刪除操作時(shí)，在鏈表中比在順序存儲(chǔ)結(jié)構(gòu)中效率高。

（15）下面說法正確的是_________。

a.數(shù)據(jù)元素是數(shù)據(jù)的最小單位。

b.隊(duì)列邏輯上是一個(gè)下端口和上端能增加又能減少的線性表。

c.任何一個(gè)遞歸過程都可以轉(zhuǎn)換成非遞歸過程。

d.只有那種使用了局部變量的遞歸過程在轉(zhuǎn)換成非遞歸過程時(shí)才必須使用棧。D數(shù)據(jù)結(jié)構(gòu)與算法——C資料文檔全文共9頁，當(dāng)前為第4頁。二.

填空題(共5題，每題5分)

（1）

下列程序的功能是創(chuàng)建單向鏈表，請補(bǔ)充完整。

#include<stdio.h>

#include<alloc.h>

structlink

{char

name[10];

int

mark;

structlink

*next;

};

voidinsert(char*name,

intmark);

structlink*head=NULL;

D數(shù)據(jù)結(jié)構(gòu)與算法——C資料文檔全文共9頁，當(dāng)前為第4頁。第5頁，共9頁第5頁，共9頁main()

{char

name[10];

int

mark;

struct

link*t;

while(1)

{

scanf(“%s%d”,

name,

&mark);

if(strcmp(name,“#”)==0)

{break;}

______(1)_______;

}

for(t=head;______(2)_______)

{

printf(“<%s>:%d\n”,

t->name,

t->mark);

}

}

voidinsert(char*name,

intmark)

{

structlink*p;

p=______(3)_______;

strcpy(p->name,

name);

p->mark=mark;

______(4)_______;

if(head!=NULL)

{

______(5)_______;

}

head=p;

}

D數(shù)據(jù)結(jié)構(gòu)與算法——C資料文檔全文共9頁，當(dāng)前為第5頁。（2）

用循環(huán)鏈表表示的隊(duì)列長度為n，若只設(shè)頭指針,則出隊(duì)和入隊(duì)的時(shí)間復(fù)雜度分別是______和_____；若只設(shè)尾指針,則出隊(duì)和入隊(duì)的時(shí)間復(fù)雜度分別是_____和_____。

D數(shù)據(jù)結(jié)構(gòu)與算法——C資料文檔全文共9頁，當(dāng)前為第5頁。第6頁，共9頁第6頁，共9頁（3）

在n個(gè)記錄的有序順序表中進(jìn)行折半查找,最大的比較次數(shù)是______。

（4）

仔細(xì)閱讀下列程序，在空白處填入適當(dāng)?shù)恼Z句。

函數(shù)match(s,t)完成在字符串s中尋找與t匹配的字符，若存在一個(gè)匹配，則返回t在字符串s中的下標(biāo)；否則，返回-1。其中，字符指針*b始終指向s的第一元素。

Match(s,t)

Chars,t;

｛char*b=s;

char*p,*r;

for_________________________________

｛

for(p=s,r=t;*r!=`\0`&&*p==*r;p++,r++);

if__________________________________

return(s-b);

｝

return(-1);

｝

（5）

補(bǔ)充下列程序：設(shè)一棵二叉序列樹b，下列算法函數(shù)是實(shí)現(xiàn)在b中插入一個(gè)結(jié)點(diǎn)s。

函數(shù)：

voidinsert（btree*b，btree*s）

{if（b==NULL）b=s；

else

if（s->data==b->data）return();

else

if(s->data<b->data)

；

else

；

}

D數(shù)據(jù)結(jié)構(gòu)與算法——C資料文檔全文共9頁，當(dāng)前為第6頁。三.簡答題（共3題，每題10分）

D數(shù)據(jù)結(jié)構(gòu)與算法——C資料文檔全文共9頁，當(dāng)前為第6頁。第7頁，共9頁第7頁，共9頁（1）

在一個(gè)包含n個(gè)元素的數(shù)組M中查找一個(gè)元素x。算法假設(shè)M已經(jīng)按升序排列了，請寫出二分搜索算法的步驟。（2）

試將一個(gè)無序的線性表A=(11,16,8,5,14,10,38,23)轉(zhuǎn)換成一個(gè)按升序排列的有序線性表（用鏈表實(shí)現(xiàn)）。（3）

何為棧和隊(duì)列？簡述兩者的區(qū)別和。另一篇下列關(guān)于算法的敘述不正確的是C

A.算法是解決問題的有序步驟

B.算法具有確定性、可行性、有限性等特征

C．一個(gè)問題的算法都只有一種

D．常見的算法描述方法有自然語言、圖示法、偽代碼法等

29、雞、兔共籠問題，有腿共60條，問雞、兔各有多少只？下面雞和兔只數(shù)最合理的范圍是

B．雞：2到28，兔：1到14

33、就算法實(shí)現(xiàn)的平臺(tái)而言，可以抽象的對算法定義為：算法=控制結(jié)構(gòu)+原操作。

34、自然語言表示算法的特征不包括C

A．容易具有歧義性

B．語句太長

C．層次感強(qiáng)、嵌套明確

D．自然且通俗易懂

35、下列問題求解使用的算法與其他三個(gè)不同的是B

A．冒泡排序

B。折半查找

C。選擇排序

D。順序查找D數(shù)據(jù)結(jié)構(gòu)與算法——C資料文檔全文共9頁，當(dāng)前為第7頁。37、下列關(guān)于算法的錯(cuò)誤說法是

B

A．算法必須有輸出

B。算法必須在計(jì)算機(jī)上用某種語言實(shí)現(xiàn)

C.算法不一定有輸入

D.算法必須在有限步執(zhí)行后能結(jié)束

D數(shù)據(jù)結(jié)構(gòu)與算法——C資料文檔全文共9頁，當(dāng)前為第7頁。第8頁，共9頁第8頁，共9頁38、算法的描述方法不包括

D

A.盒圖

B.自然語言

C.流程圖

D.E-R圖

39、算法設(shè)計(jì)時(shí)，應(yīng)該嚴(yán)格考慮其質(zhì)量指標(biāo)，下列不屬于該指標(biāo)的是

A

A.分布性

B.可讀性

C.正確性

D.穩(wěn)健性

40、下列算法的運(yùn)行時(shí)間復(fù)雜度中（n:問題規(guī)模），數(shù)量級(jí)最高的是

D

O(logn)

B.O(n)

C.O(1)

D.O(n!)下列哪個(gè)不屬于迭代法的設(shè)計(jì)步驟

D

A.確定迭代模型

B.建立迭代模型

C.對迭代關(guān)系式進(jìn)行控制

D.計(jì)算迭代次數(shù)

41、通俗地講，算法是指解決問題的一種方法或一個(gè)過程，描述算法的方式有很多種，AA.自然語言

B.表格方式

C.畫圖方式

D.C語言

42、下列那些問題不可以用貪心算法求的最優(yōu)解

C

A.哈夫曼編碼

B.活動(dòng)安排問題

C.0-1背包問題

D.單源最短路徑

43、下面4個(gè)說法：

1.算法原地工作的含義是指不需要任何額外的輔助空間

2.在相同的規(guī)模n下,復(fù)雜度O（n）的算法空間上總是優(yōu)于復(fù)雜度O（n*n）的算法

3.所謂時(shí)間復(fù)雜度是指最壞情況下，估算算法時(shí)間的一個(gè)上界

4.同一個(gè)算法，實(shí)現(xiàn)語言的級(jí)別越高，執(zhí)行效率就越低

其中，錯(cuò)誤的是

C

A.(1)

B.(1)(2)

C.(1)(4)

D.(3)

44、下面關(guān)于算法說法錯(cuò)誤的是

D

A.算法最終必須由計(jì)算機(jī)程序?qū)崿F(xiàn)

B.為解決某問題的算法同為該問題編寫的程序含義是相同的

C.算法的可行性是指指令不能不能有二義性

D.以上幾個(gè)都是錯(cuò)誤D數(shù)據(jù)結(jié)構(gòu)與算法——C資料文檔全文共9頁，當(dāng)前為第8頁。D數(shù)據(jù)結(jié)構(gòu)與算法——C資料文檔全文共9頁，當(dāng)前為第8頁。第9頁，共9頁第9頁，共9頁（×）1.鏈表的每個(gè)結(jié)點(diǎn)中都恰好包含一個(gè)指針。

答：錯(cuò)誤。鏈表中的結(jié)點(diǎn)可含多個(gè)指針域，分別存放多個(gè)指針。例如，雙向鏈表中的結(jié)點(diǎn)可以含有兩個(gè)指針域，分別存放指向其直接前趨和直接后繼結(jié)點(diǎn)的指針。

（×）2.鏈表的物理存儲(chǔ)結(jié)構(gòu)具有同鏈表一樣的順序。

錯(cuò)，鏈表的存儲(chǔ)