《計算機(jī)軟件技術(shù)基礎(chǔ)》試題答案

《計算機(jī)軟件技術(shù)基礎(chǔ)》試題

1.線性表的鏈?zhǔn)酱鎯Y(jié)構(gòu)與順序存儲結(jié)構(gòu)相比優(yōu)點是CD。

A。所有的操作算法實現(xiàn)簡單B。便于隨機(jī)存取

C.便于插入和刪除D.便于利用零散的存儲器空間

2。線性表是具有n個C的有限序列。

A。表元素B.字符C。數(shù)據(jù)元素

D。數(shù)據(jù)項E。信息項

3.若長度為n的線性表采用順序存儲結(jié)構(gòu),在其第I個位置插入一個新元素的算法的時間復(fù)

雜度為C.（1≤I≤n+1）

A。O（0)B。O(1)

C。O（n）D.O(n2)

4.設(shè)A是一個線性表（a,a,…，a），采用順序存儲結(jié)構(gòu)，則在等概率的前提下，平均每插

12n

入一個元素需要移動的元素個數(shù)為B，平均每刪除一個元素需要移動的元素個數(shù)

為

2(ni)

A；若元素插在a與a之間（0≤I≤n—1)的概率為,則平均每插入一

ii+1n(n1)

個元素所要移動的元素個數(shù)為C;

n1n

A.B。

22

2n13n1

C.D.

34

5。下列函數(shù)中，按它們在n時的無窮大階數(shù)，最大的是D。

A.lognB。nlogn

C。2n/2D。n!

6.將下圖所示的s所指結(jié)點加到p所指的結(jié)點之后，其語句應(yīng)為：D。

nextnext

p

s

next

A。s—〉next=p+1;p-〉next=s；

B。(＊p)。next=s；(＊s）.next=(*p）.next;

C。s->next=p—>next；p—〉next=s—>next;

D.s—>next=p->next;p—>next=s；

7。將兩個各有n個元素的有序表歸并為一個有序表時，其最少的比較次數(shù)是A.

A.nB。2n-1

C。n-1D.2n

8。下面的程序段是合并兩個無頭結(jié)點鏈表(ha和hb）為一個無頭結(jié)點鏈表ha的過程，作

為參數(shù)的兩個鏈表都是按結(jié)點的data域由大到小鏈接的。合并后新鏈表的結(jié)點仍按此方式

鏈接。請?zhí)顚懴率隹湛?使程序能正確運(yùn)行。

#defineNULL0

typedefstructnode｛

intdata;

structnode*next;

｝node，linklisttype;

voidcombine（linklisttype*ha，linklisttype*hb)｛

linklisttype＊h，＊p；

h=（linklisttype＊）malloc(sizeof（linklisttype)）;

h—>next=NULL;

p=h;

while(ha!=NULL＆＆hb！=NULL)

if（ha-〉data〉=hb—〉data）｛/＊較大的元素先插入＊/

p-〉next=（1）;

p=（2）;

（3);

｝

else{

p—>next=（4)；

p=(5);

(6);

}

if（ha==NULL)(7）；

if（hb==NULL）（8）；

ha=h—〉next;

free（h);

｝

參考答案：（1)ha（2）p—>next(3)ha=ha-〉next

(4）hb（5)p->next(6）hb=hb—>next

(7）p->next=hb（8）p->next=ha

9.如果表A中所有元素(a,a,…,a)與表B的一個順序子表（b,b,…b)完全相同(即

12nkk+1k+n—1

a=b,a=b,…a=b），則稱表A包含在表B中。設(shè)ha,hb為帶頭結(jié)點的單鏈表，分別表

1k2k+1nk+n—1

示有序表A和B，下面的函數(shù)用于判別表A是否包含在表B中，若是，則返回true，否則返

回false。（提示：用遞歸實現(xiàn)）

＃definetrue1

#definefalse0

＃defineNULL0

typedefstructnode{

intdata；

structnode*next；

}node，linklisttype；

intinclusion（linklisttype＊ha，linklisttype＊hb){

linklisttype＊pa,*pb；

pa=ha—〉next；

pb=hb—〉next;

（1)；

while（(2))

if（pa—〉data=pb->data）(3)；

else(4)；

(5);

｝

參考答案：

(1)if(pa==NULL)return(true)

(2)pb！=NULL＆＆pa->data>=pb-〉data

（3)return(inclusion（pa，pb））

（4)pb=pb-〉next;

(5）return(false)

10.在本題的程序中，函數(shù)create_link_list(n）建立一個具有n個結(jié)點的循環(huán)鏈表;函數(shù)

josephus（n，I，m）對由create_link_list（n）所建立的具有n個結(jié)點的循環(huán)鏈表按一

定的次序逐個輸出,并刪除鏈表中的所有結(jié)點。參數(shù)n（n>0）指明循環(huán)鏈表的結(jié)點個數(shù),參

數(shù)I（1≤I≤n）指明起始結(jié)點，參數(shù)m（m〉0是步長）,指明從起始結(jié)點或前次被刪除并輸

出的結(jié)點之后的第m個結(jié)點作為本次被輸出并刪除的結(jié)點。例如，對于下圖所示的具有6

個結(jié)點的循環(huán)鏈表,在調(diào)用josephus（6，3，2)后，將輸出5，1,3，6，4，2.請在空框處填

上適當(dāng)內(nèi)容，每框只填一個語句.

＃defineNULL0

typedefstructnode｛

intdata;

structnode＊next；

}node，linklisttype；

linklisttype*create_link_list(intn){

linklisttype＊head,＊p，＊q;

intI；

head=NULL；

if（n〉0)｛

head=(linklisttype*)malloc(sizeof（linklisttype）)；

p=head；

for（I=1；I<=n—1；I++）｛/＊此循環(huán)用于建立一個鏈表,鏈表的內(nèi)容從1至

n—1＊/

p—〉data=I；

q=（linklisttype＊)malloc（sizeof(linklistttype）);

(1)；

（2）;

}

p->data=n;

(3）；/＊建立從尾鏈到首的環(huán)形結(jié)構(gòu)*/

｝

return（head);

}

voidJosephus(intn,intj,intm)｛

linklisttype＊p，*q；

intj；

p=create_link_list(n）;

for(;I〉1;I--）p=p->next；

(4）;

while（j<n）{

for（I=1；I<=m—1；I++)p=p—〉next;

(5）；

printf(“％8d”，q->data);

（6)；

free（q);

j=j+1；

}

}

參考答案:

(1)p—>next=q；

(2)p=q；

(3）p-〉next=head

(4)j=0

（5）q=p->next;

(6)p—〉next=q—〉next

11。在下列程序中，函數(shù)difference(A,B）用于求兩集合之差C=A—B，即當(dāng)且僅當(dāng)e是A

中的一個元素，且不是B中的元素時，e是C中的一個元素。集合用有序鏈表實現(xiàn)，用一個

空鏈表表示一個空集合,表示非空集合的鏈表根據(jù)元素之值按遞增排列，執(zhí)行C=A—B之后,

表示集合A和B的鏈表不變，若結(jié)果集合C非空，則表示它的鏈表應(yīng)根據(jù)元素之值按遞增序

排列。函數(shù)append（）用于在鏈表中添加結(jié)點.

#include<stdio。h〉

#defineNULL0

typedefstructnode{

intdata;

structnode*next;

}NODE；

NODE*append（NODE＊last,intx）{

last->next=（NODE*)malloc（sizeof(NODE));

last—〉next->data=x；

return（last-〉next）;

｝

NODE*difference（NODE＊A，NODE＊B)｛

NODE＊C,*last;

C=last=（NODE*)malloc（sizeof（NODE));

while（(1)）

if（A—〉data<B—〉data）{

last=append（last,A-〉data)；

A=A-〉next；

｝

else

if((2））｛

A=A-〉next;

B=B—〉next;

}

else

（3）;

while((4）)｛

last=append(last,A->data）；

A=A->next；

｝

（5）；

last=C;

C=C->next;

free(last）；

return(C）;

}

參考答案:

（1)A!=NULL＆B！=NULL

（2）A—〉data==B—>data

(3）B=B-〉next;

（4）A!=NULL

(5）last->next=NULL；

12。閱讀以下算法，填充空格,使其成為完整的算法。其功能是在一個非遞減的順序存儲線

性表中（從下標(biāo)1處開始存儲）,刪除所有值相等的多余元素。

＃defineMAXSIZE30

typedefstruct{

intelem［MAXSIZE]；

intlength;/＊表長＊/

}sqlisttype；

voidexam21(sqlisttype*L)｛

intI，j；

I=2,j=1；

while（(1）)｛

if（L-〉elem[I］〈>L—>elem［j]){

（2）;

(3）；

}

I++；

｝

（4);

｝

參考答案:

（1）i<=L->length

(2)

（3）j++;

（4）

13。用單鏈表表示的鏈?zhǔn)疥犃械年狀^在鏈表的A位置。

A。鏈頭B。鏈尾C。鏈中

14.若用單鏈表表示隊列，則應(yīng)該選用B。

A。帶尾指針的非循環(huán)鏈表B.帶尾指針的循環(huán)鏈表

C。帶頭指針的非循環(huán)鏈表D.帶頭指針的循環(huán)鏈表

15.在解決計算機(jī)主機(jī)與打印機(jī)之間速度不匹配問題時,通常設(shè)置一個打印數(shù)據(jù)緩沖區(qū)，主機(jī)

將要輸出的數(shù)據(jù)依次寫入該緩沖區(qū)，而打印機(jī)則從該緩沖區(qū)中取出數(shù)據(jù)打印，先放入打印緩

沖區(qū)的數(shù)據(jù)先被打印。該緩沖區(qū)應(yīng)該是一個B結(jié)構(gòu).

A.堆棧B。隊列

C。數(shù)組D.線性表

16.若用一個大小為6的數(shù)組來實現(xiàn)循環(huán)隊列,且當(dāng)前rear和front的值分別為0和3。當(dāng)

從隊列中刪除一個元素，再加入兩個元素后，rear和front的值分別為B。

A。1和5B。2和4

C.4和2D.5和1

17.設(shè)棧的輸入序列為1，2，…，10，輸出序列為a，a,…，a，若a=10,則a為C。

121057

A。4B。8C.不確定D.7

18.設(shè)棧的輸入序列是1，2,3，4,則D不可能是其出棧序列。

A．1243B。2134C。1432D。4312

19.以下D是C語言中"abcd321ABCD”的子串。

A。abcdB.321ABC.“abcABC”D.“21AB”

20.若串S=”software”，其子串的數(shù)目是C。

A。8B。37C。36D。9

21.將一個A［1：100,1:100]的三對角矩陣，按行優(yōu)先存入一維數(shù)組B［1：298]中，A中元

素A66,65(即該元素的下標(biāo)）在B數(shù)組中位置k為B。

A.198B.195C.197D。196

22.設(shè)高為h的二叉樹只有度為0和2的結(jié)點，則此類二叉樹的結(jié)點數(shù)至少為B,

至多為F。高為h的完全二叉樹的結(jié)點數(shù)至少為E，至多為F。

A．2hB.2h-1C.2h+1D。h+1

E.2h—1F.2h-1G.2h+1-1H.2h+1

23.一棵有124個葉結(jié)點的完全二叉樹，最多有B個結(jié)點。

A。247B。248C。249D.251

24。若從二叉樹的任一結(jié)點出發(fā)到根的路徑上所經(jīng)過的結(jié)點序列按其關(guān)鍵字有序，則該二叉

樹是C。

A。滿二叉樹B。哈夫曼樹

C。堆D。二叉查找樹

25。前序遍歷和中序遍歷結(jié)果相同的二叉樹為F；前序遍歷和后序遍歷結(jié)果相同

的二叉樹為B。

A.一般二叉樹B。只有根結(jié)點的二叉樹

C.根結(jié)點無左孩子的二叉樹D。根結(jié)點無右孩子的二叉樹

E.所有結(jié)點只有左孩子的二叉樹F。所有結(jié)點只有右孩子的二叉樹

26.具有n個結(jié)點的完全二叉樹,已經(jīng)順序存儲在一維數(shù)組A［1..n]中，下面的算法是將A

中順序存儲變?yōu)槎骀湵泶鎯Φ耐耆鏄?。請?zhí)顚戇m當(dāng)語句在下面的空格內(nèi),完成上述算

法.

＃defineMAXSIZE30

typedefstructbtnode｛

intdata；

structbtnode*lchild，＊rchild；

｝BTN；

voidcreatetree（BTN＊p,intA[］,intI，intn)｛

（1）;

p—>data=A［I]；

if（（2))

（3)；

else

p-〉lchild=NULL；

if(（4))

createtree((5)）;

else

p—〉rchild=NULL;

｝

voidbtree(BTN＊p,intA[],intn）{

createtree(p，A,1,n）;

}

參考答案：

(1）p=（BTN＊）malloc(sizeof(BTN）)

（2）2*I〈=n

(3)createtree(p—>lchild，A,2＊I,n)

(4）2＊I+1〈=n

(5)p->rchild,A，2*I+1,n

27.若在線性表中采用折半查找法查找元素，該線性表應(yīng)該C。

A.元素按值有序B。采用順序存儲結(jié)構(gòu)

C。元素按值有序,且采用順序存儲結(jié)構(gòu)D。元素按值有序，且采用鏈?zhǔn)酱鎯Y(jié)構(gòu)

28。在分塊檢索中，對256個元素的線性表分成16塊最好,每塊的最佳長度是

16；若每塊的長度為8,其平均檢索長度為21。

29.假定有K個關(guān)鍵字互為同義詞,若用線性探測法把這K個關(guān)鍵字存入散列表中，至少要進(jìn)

行D次探測。

A.K—1次B。K次

C.K+1次D。K（K+1）/2次

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

2

31。Hash技術(shù)廣泛應(yīng)用于查找過程，選擇Hash函數(shù)的標(biāo)準(zhǔn)是和。

處理沖突的技術(shù)有優(yōu)有劣,其共同標(biāo)準(zhǔn)是。

32。在下述排序算法中,所需輔助存儲空間最多的是B，所需輔助存儲空間最小

的是C，平均速度最快的是A。

A。快速排序B.歸并排序C。堆排序

33.在文件局部有序或文件長度較小的情況下，最佳內(nèi)部排序的方法是A.

A。直接插入排序B。冒泡排序C。簡單選擇排序

34?？焖倥判蛟谧顗那闆r下時間復(fù)雜度是O（n2）,比A的性能差.

A.堆排序B.冒泡排序C。簡單選擇排序

35。若需在O（nlogn)的時間內(nèi)完成對數(shù)組的排序,且要求排序是穩(wěn)定的，則可選擇的排序

方法是C。

A.快速排序B.堆排序

C。歸并排序D。希爾排序

36.如果只想得到1000個元素組成的序列中第5個最小元素之前的部分排序的序列，用

B方法最快。

A。冒泡排序B?？焖倥判?/p>

C.希爾排序D。堆排序E.簡單選擇排序

37.以下結(jié)點序列是堆的為A。

A.100，90，80，60，85，75,20，25,10，70，65，50

B.100,70,50，20，90,75,60，25，10，85，65,80

38.若要盡可能快地完成對實數(shù)數(shù)組的排序，且要求排序是穩(wěn)定的，則應(yīng)選C。

A.快速排序B。堆排序

C。歸并排序D.希爾排序

39.從未排序序列中依次取出一個元素與已排序序列中的元素依次進(jìn)行比較，然后將其放在

已排序序列的合適位置，該排序方法稱為A排序法。

A。插入排序B。交換排序

C.選擇排序D。歸并排序

40.直接插入排序在最好情況下的時間復(fù)雜度為B。

A.O(logn）B.O(n)

C。O(nlogn）D.O（n2)

41.下面函數(shù)是將任意序列調(diào)整為最大堆的算法，請將空白部分填上:

將任意序列調(diào)整為最大堆通過不斷調(diào)用adjust函數(shù)，即

for（i=n/2;i>0；i--）adjust(list，i,n）；

其中l(wèi)ist為待調(diào)整序列所在數(shù)組(從下標(biāo)1開始），n為序列元素的個數(shù)。

voidadjust(intlist［］，introot,intn){

/*將以root為下標(biāo)的對應(yīng)元素作為待調(diào)整堆的根，待調(diào)整元素放在list數(shù)組中，最大元素

下標(biāo)為n*/

intchild，rootkey;

rootkey=(1);

child=2＊root;

while（child〈n)｛

if（（child<n）＆＆(list［child］〈list［child+1］）)

（2）；

if（rootkey〉list［child]）

break；

else｛

list[（3)］=list［child］;

（4)；

｝

}

list[(5)]=rootkey；

｝

參考答案：

(1）list[root］

(2）child++；

（3)child/2

(4）child*=2;

(5)child/2

41.表是一種數(shù)據(jù)結(jié)構(gòu),鏈表是一種（1）。隊列和棧都是線性表，棧的操作特性

是(2),隊列的操作特性是(3)。今有一空棧S，對下列待進(jìn)棧的數(shù)

據(jù)元素序列a，b,c,d,e，f依次進(jìn)棧、進(jìn)棧、出棧、進(jìn)棧、進(jìn)棧、出棧的操作,則此操作完

成后，棧S的棧頂元素為(4)，棧底元素為(5）。

供選答案：

(1）:A.非順序存儲線性表B.非順序存儲非線性表

C。順序存儲線性表D.順序存儲非線性表

(2):A.隨機(jī)進(jìn)出B。先進(jìn)后出

C.先進(jìn)先出D。出優(yōu)于進(jìn)

(3）：A.隨機(jī)進(jìn)出B.先進(jìn)后出

C.后進(jìn)后出D。進(jìn)優(yōu)于出

（4)：A。fB。c

C.aD。b

（5）:A.bB.c

C。aD.d

答案：ABCBC

42。操作系統(tǒng)主要是對計算機(jī)系統(tǒng)全部（1)進(jìn)行管理，以方便用戶、提高計算

機(jī)使用效率的一種系統(tǒng)軟件。它的主要功能有：處理機(jī)管理、存儲管理、文件管理、(2）

管理和設(shè)備管理等。Windows和Unix是最常用的兩類操作系統(tǒng)。前者是一個具有圖形界面

的窗口式的（3)系統(tǒng)軟件,后者是一個基本上采用(4)語言編制而成

的的系統(tǒng)軟件。在（5）操作系統(tǒng)控制下，計算機(jī)能及時處理由過程控制反饋的

信息并作出響應(yīng)。

供選答案：

(1）：A.應(yīng)用軟件B.系統(tǒng)軟硬件

C。資源D。設(shè)備

(2):A。數(shù)據(jù)B。作業(yè)

C.中斷D.I/O

(3):A.分時B.多任務(wù)

C.多用戶D。實時

(4）:A。PASCALB.宏

C。匯編D.C

（5）:A.網(wǎng)絡(luò)B.分時

C.批處理D.實時

答案:CBBDD

43.本程序從鍵盤讀入整數(shù),并按從大到小的順序輸出輸入整數(shù)中互不相等的那些整數(shù)。

程序一邊讀入整數(shù)，一邊構(gòu)造一個從大到小順序鏈接的鏈表，直至不能從鍵盤讀入整數(shù)，

然后順序輸出鏈表上各表元的整數(shù)值。主函數(shù)每讀入一個整數(shù),就調(diào)用函數(shù)insert（),函數(shù)

insert（）將還未出現(xiàn)在鏈表上的整數(shù)按從大到小的順序插入到鏈表中。

為了插入方便，鏈表在表首有一個輔助表元。

閱讀下列C代碼,在（n）處填入相應(yīng)的字句以完成上述功能.

＃include<stdio.h〉

＃include〈malloc。h〉

＃defineNULL0

typedefstructnode｛

intval;

structnode＊next；

}NODE；

voidinsert（NODE＊list,intx)｛

NODE＊u,＊v，＊p;

u=list;v=u—〉next;

while((1)＆&x〈v—〉val){/*尋找插入位置＊/

u=v;v=u->next;

}

if((v==NULL|｜（2)）｛/＊判斷是否要插入表元*/

p=(NODE＊）malloc（sizeof(NODE）);

p->val=x；/*生成新表元＊/

（3）=v;（4）=p；/＊插入新表元*/

｝

}

main（）｛

intx;

NODE*head,*p;

/*首先建立只有輔助表元的空鏈表*/

head=(NODE＊)malloc（sizeof(NODE)）;

(5）=NULL;

printf(“EnterIntegers：\n”）；

while（scanf（“％d”,＆x）==1)/*反復(fù)讀入整數(shù)插入鏈表*/

insert（head,x）;

for(p=head->next;p！=NULL;p=p->next)/＊輸出鏈表＊/

printf(“%d\t”,p-〉val);

printf(“\n”）；

}

答案:

（1)v!=NULL或v

(2)x>v->val或x！=v—〉val

(3）p->next

(4）u—>next

（5）head->next

44.計算機(jī)數(shù)據(jù)處理的對象是具有不同結(jié)構(gòu)的各種數(shù)據(jù)，可以訪問的最小數(shù)據(jù)信息單位是

(1)，可以引用的最小命名數(shù)據(jù)單位是(2）。

線性表是最簡單的一種數(shù)據(jù)結(jié)構(gòu)，有順序和鏈接兩種存儲方式。線性表按鏈接方式存儲

時，每個結(jié)點的包括(3）兩部分。

線性表的查找有（4）和(5）兩種，但(5)只能用

于順序存儲的情況。

供選答案：

(1）:A.數(shù)字B.字符

C.數(shù)據(jù)元素D。數(shù)據(jù)項

（2):A.結(jié)點B。記錄

C.數(shù)據(jù)元素D。數(shù)據(jù)項

（3）:A。數(shù)據(jù)值與符號B.數(shù)據(jù)與指針

C.數(shù)據(jù)與表名D.頭地址與尾地址

(4):A。隨機(jī)查找B.順序查找

C.二分法查找D.瀏覽

(5)：A。隨機(jī)查找B.順序查找

C.二分法查找D。瀏覽

答案：CDBBC

45.本程序用于從鏈盤讀入整數(shù)，插入到鏈表，或從鏈表刪除一個整數(shù)。

閱讀下面的C代碼，將應(yīng)填入（n)處的字名寫在答卷的對應(yīng)欄內(nèi)。

#include〈stdio。h>

＃include〈malloc。h>

typedefstructnode{

intval;

structnode*next;

｝NODE；

NODE*ins(NODE＊list，intx）｛/＊將x按從小到大的次序插入鏈表＊/

NODE＊u,*v=list,*p；

for（;v!=NULL&&x〈v-〉val;v=v—〉next);/＊尋找插入位置＊/

if（v!=NULL&&x==v->val)return(list）；/＊已有，被忽略＊/

p=(NODE*）malloc(sizeof(NODE));p—>val=x；/*生成新表元*/

if（v==list)list=p；

else（1)；

（2）；

returnlist；

}

NODE＊del（NODE＊list，intx）{/＊從鏈表中刪除值為x的表元*/

NODE＊u，＊v;

for(v=list;v！=NULL＆＆x〈v-〉valu；u=v;v=v—>next);

if（v!=NULL＆&x==v->val）｛/*找到值為x的表元＊/

if（v==list）list=list—〉next；

else（3);

(4)；/*釋放空間＊/

}

elseprintf(“沒有找到!\n”）;

return（list);

｝

main(）｛

intx，ans;

NODE＊list=NULL,*p;

while（1）｛

printf(“\n輸入1：將整數(shù)插入到鏈表。\n輸入2：從鏈表刪除一個整數(shù)。\n”)；

printf（“其它整數(shù)，結(jié)束程序。\n\t請輸入選擇!”)；

scanf(%d,＆ans）;

if（(5))return;

printf（“輸入整數(shù):”)；scanf（“％d",＆x)；

if(ans==1)list=ins（list,x)；

elselist=del(list,x);

for(p=list;p！=NULL；p=p—>next)

printf(“%4d”，p->val)；

}

｝

答案:

(1)u—〉next=p；

(2)p-〉next=v

(3)u-〉next=v->next

(4)free(v）

（5)ans!=1&＆ans!=2

46.從未排序的序列中，依次取出元素，與已排序序列的元素比較后，放入已排序序列中的

恰當(dāng)位置上，這是（1)排序。從未排序的序列中，挑選出元素，放在已排序序

列的某一端位置，這是(2)排序.逐次將待排序的序列中的相鄰元素兩兩比較,

凡是逆序則進(jìn)行交換，這是(3)排序。如果整個排序過程都在內(nèi)存中進(jìn)行，稱為

（4)排序。排序算法的復(fù)雜性與排序算法的(5）有關(guān)。

供選答案：

(1)：A.選擇B.插入

C。比較D。歸并

(2):A。選擇B.插入

C。比較D。歸并

(3):A。冒泡B。交換

C。比較D.散列

（4)：A。外部B.內(nèi)部

C.外存D.內(nèi)存

(5）：A.運(yùn)算量大小與占用存儲多少

B.運(yùn)算量大小與處理的數(shù)據(jù)量大小

C.并行處理能力和占用存儲多少

D。占用存儲多少和處理的數(shù)據(jù)量大小

答案：BAABA

47.操作系統(tǒng)是對計算機(jī)資源進(jìn)行的(1）系統(tǒng)軟件，是（2)的接口。

在處理機(jī)管理中，進(jìn)程是一個重要的概念,它由程序塊、（3)和數(shù)據(jù)塊三部

分組成，它有3種基本狀態(tài),不可能發(fā)生的狀態(tài)轉(zhuǎn)換是（4)。

虛擬存儲器的作用是允許程序直接訪問比內(nèi)存更大的地址空間,它通常使用(5）

作為它的一個主要組成部分.

供選答案：

(1)：A。輸入和輸出B。鍵盤操作

C.管理和控制D。匯編和執(zhí)行

(2）:A.軟件和硬件B。主機(jī)和外設(shè)

C.高級語言和機(jī)器語言D.用戶和計算機(jī)

（3）:A。進(jìn)程控制塊B。作業(yè)控制塊

C.文件控制塊D。設(shè)備控制塊

(4）:A.運(yùn)行態(tài)轉(zhuǎn)換為就緒態(tài)B.就緒態(tài)轉(zhuǎn)換為運(yùn)行態(tài)

C。運(yùn)行態(tài)轉(zhuǎn)換為等待態(tài)D.等待態(tài)轉(zhuǎn)換為運(yùn)行態(tài)

(5):A.軟盤B。硬盤

C。CDROMD.寄存器

答案：CDADB

48。A是信息的載體,它能夠被計算機(jī)識別、存儲和加工處理.

A.數(shù)據(jù)B。數(shù)據(jù)元素C.結(jié)點D.數(shù)據(jù)項

49。下列程序段的時間復(fù)雜度為C。

for（i=1；i<n；i++)｛

y=y+1；

for（j=0；j<=（2＊n）;j++）x++；

｝

供選答案：

A。O(n-1）B.O(2n)C。O（n2）D.O(2n+1)

50。下面程序段的時間復(fù)雜度為D.

i=1；

while(i<=n）i=i*2；

供選答案：

A。O(1）B.O（n)C.O（n2)D。O(logn）

2

51。下面程序段的時間復(fù)雜度為B。

a=0;b=1;

for(i=2；i<=n;i++）｛

s=a+b；

b=a；

a=s;

｝

供選答案:

A。O(1）B.O（n)C。O（logn）D。

2

O(n2）

52。數(shù)據(jù)結(jié)構(gòu)是一門研究非數(shù)值計算的程序設(shè)計問題中，計算機(jī)的A以及它們之

間的關(guān)系和運(yùn)算等的學(xué)科。

A.操作對象B。計算方法C.邏輯存儲D。數(shù)據(jù)映象

53。在數(shù)據(jù)結(jié)構(gòu)中，從邏輯上可以把數(shù)據(jù)結(jié)構(gòu)分成C。

A。動態(tài)結(jié)構(gòu)和靜態(tài)結(jié)構(gòu)B。緊湊結(jié)構(gòu)和非緊湊結(jié)構(gòu)

C。線性結(jié)構(gòu)和非線性結(jié)構(gòu)D。內(nèi)部結(jié)構(gòu)和外部結(jié)構(gòu)

54.算法分析的目的是C。

A.找出數(shù)據(jù)結(jié)構(gòu)的合理性

B.研究算法中輸入和輸出的關(guān)系

C.分析算法的效率以求改進(jìn)

D。分析算法的易懂性和文檔性

55.算法分析的兩個主要方面是(4）。

A。間復(fù)雜性和時間復(fù)雜性B。正確性和簡明性

C。可讀性和文檔性D。數(shù)據(jù)復(fù)雜性和程序復(fù)雜性

56.一個線性順序表第一個元素的存儲地址是100,每個元素的長度為2，則第5個元素的地

址為B。

A.110B.108C.100D.120

57。若已知一個棧的入棧序列是1,2,3，…,n,其輸出序列為P,P，P,…，P，若P=n,則

123n1

P為C。

i

A。iB.n—iC。n-i+1D。不確定

58。對于一個棧，給出輸入項A，B,C。如果輸入項序列由A,B,C所組成，則不可能產(chǎn)生的

輸出序列是A。

A。CABB。CBAC.ABCD.ACB

59.設(shè)有如下的單鏈表的按序號查找的算法，其時間復(fù)雜度為B。

LinkNode*GetNode(Linklisthead，inti){

intj；

ListNode*p；

P=head；j=0;

while（p—>next&&j<i）{

p=p->next；

j++；

}

if（i==j)

return(p)；

else

return（NULL)；

｝

供選答案:

A.O（n2)B。O（2n)C。O(n3）D。O（logn）

60.二維數(shù)組A按行序為主順序存放在內(nèi)存中,每個數(shù)組元素占1個存儲單元，則元素a

mnij

的地址計算公式是C。

A。LOC(a）=LOC(a）+[（i—1)*m+(j-1)］

ij11

B.LOC（a)=LOC（a)+[（j—1)＊m+(i-1)]

ij11

C.LOC（a）=LOC（a)+[(i-1）*n+(j-1)］

ij11

D。LOC(a）=LOC（a）+[(j-1）＊n+（i—1)］

ij11

61.以下哪一個不是隊列的基本運(yùn)算C。

A。從隊尾插入一個新元素B。從隊列中刪除第i個元素

C.判斷一個隊列是否為空D。讀取隊頭元素的值

62.在一個長度為n的順序表中,向第i個元素之前插入一個新元素,需向后移動B個

元素.

A.n—iB。n-i+1C.n-i-1D.i

63.從一個長度為n的順序表中刪除第i個元素時，需向前移動A個元素。

A。n-iB。n—i+1C.n-i—1D。i

64。在具有n個單元的順序存儲的循環(huán)隊列中，假定front和rear分別為隊首指針和隊尾

指針，則判斷隊空的條件是B。

A.front=rear+1B.front=rearC.front+1=rearD.front=0

65.從一個具有n個結(jié)點的單鏈表中查找其值等于x的結(jié)點時，在查找成功的情況下，需平

均比較D個結(jié)點。

A。nB。n/2C。（n—1)/2D.(n+1)/2

66.一個棧的入棧序列是a,b，c,d,e，則棧不可能的輸出序列是C。

A.edcbaB。decbaC。dceabD。abcde

67。棧結(jié)構(gòu)通常采用的兩種存儲結(jié)構(gòu)是A。

A.順序存儲結(jié)構(gòu)和鏈表存儲結(jié)構(gòu)B。散列方式和索引方式

C.鏈表存儲結(jié)構(gòu)和數(shù)組D.線性存儲結(jié)構(gòu)和非線性存儲結(jié)構(gòu)

68。判斷一個順序棧ST(最多元素為mo）為空的條件是B。

A。ST—>top〈>0B.ST—>top=0C。st—〉top〈〉moD.st

—>top==mo

69.不帶頭結(jié)點的單鏈表head為空表的判定條件是A。

A.head==NILLB.head—〉next==NULLC.head—〉next==headD.head！=

NULL

70.在一個單鏈表中，已知q所指結(jié)點是p所指結(jié)點的前驅(qū)結(jié)點，若在p和q之間插入s結(jié)

點，則應(yīng)執(zhí)行C。

A.s—〉next=p—〉next；p->next=s；

B。p-〉next=s—〉next；s—〉next=p;

C.q—>next=s;s—〉next=p;

D。p->next=s;s—〉next=q;

71。假設(shè)雙向鏈表結(jié)點的類型如下：

typedefstructLinknode｛

intdata;

structLinknode＊lLink;/＊前驅(qū)結(jié)點指針＊/

structLinknode＊rLink；/＊后繼結(jié)點指針＊/

}

下面給出的算法是要把一個q所指新結(jié)點，作為非空雙向鏈表中的p所指的結(jié)點前驅(qū)結(jié)點插

入到該雙向鏈表中,能正確完成要求的算法段是C。

A．q—〉rLink=p；q—>lLink=p-〉lLink;p->lLink=q;p—>lLink->rLink=q;

B.p->lLink=q,q—>rLink=p；p—〉lLink—〉rLink=q；q->lLink=p—>lLink;

C.q-〉lLink=p—>lLink；q-〉rLink=p;p—〉lLink—〉rLink=q;p-〉lLink=q;

D.以上均不對

72。串是一種特殊的線性表，其特殊性體現(xiàn)在B。

A?？梢皂樞虼鎯.數(shù)據(jù)元素是一個字符

C?？梢枣溄哟鎯.數(shù)據(jù)元素可以是多個字符

73。設(shè)有兩個串p和q，求q在p中首次出現(xiàn)的位置的運(yùn)算稱作B。

A。連接B.模式匹配C.求子串D。求串長

74.設(shè)串s1=”ABCDEFG”，s2=”PQRST”，函數(shù)con（x，y)返回x和y串的連接串,subs(s,I,j）

返回串s的從序號i的字符開始的j個字符組成的子串,len(s）返回串s的長度，則con(sub

（s1,2，len（s2)）,sub（s1，len(s2)，2）)的結(jié)果是D.

A.BCDEFB.BCDEFGC.BCPQRSTD.BCDEFEF

75。常對數(shù)組進(jìn)行的兩種基本操作是C。

A。建立和刪除B.索引和修改C。查找和修改D.索引和查找

76.稀疏矩陣一般的壓縮存儲方法有兩種，即Ｃ.

A.二維數(shù)組和三維數(shù)組B。三元組和散列

C。三元組和十字鏈表D。散列和十字鏈表

77。對下圖所示的二叉表，按先根次序遍歷得到的結(jié)點序列為B。

A.ABCDHEIFGB.ABDHIECFG

C.HDIBRAFCGD.HIDBEFGAC

78。在一棵二叉樹上，度為0的結(jié)點個數(shù)為n,度為2的結(jié)點數(shù)為n，則n0=A。

02

A.n+1B。n—1

22

C。nD。n/2

22

79.某二叉樹前序遍歷結(jié)點的訪問順序是ABCDEFG,中序遍歷結(jié)點的訪問順序是CBDAFGE，則

其后序遍歷結(jié)點的訪問順序是A。

A．CDBGFEAB.CDGFEAB

C.CDBAGFED。CDBFAGE

80。在下列存儲形式中,D不是樹的存儲形式。

A。雙親表示法B。孩子鏈表表示法

C。孩子兄弟表示法D.順序存儲表示法

81.已知一棵二叉樹的中序序列為cbedahgijf,后序序列為cedbhjigfa，則該二叉樹為

B。

82.已知一棵權(quán)集W=｛2，3,4，7,8,9}的哈夫曼樹，其加權(quán)路徑長度WPL為Ｃ。

A。20B.40C。80D.160

83。已知一棵度為m的樹中有n個度為1的結(jié)點，n個度為2的結(jié)點，…,n個度為m的結(jié)

12m

點，問這棵樹中葉子結(jié)點為Ｃ。

A.1+n（I-1）B。1+n（I+1)C。n+n+…+nD.m·n

ii12mm

84。如下圖所示的4棵二叉樹中，Ｃ不是完全二叉樹。

85。設(shè)高度為h的二叉樹上只有度為0或度為2的結(jié)點，則此類二叉樹中所包含的結(jié)點數(shù)至

少為B。

A.2hB。2h-1C.2h+1D。h+1

86。如下圖所示的二叉樹的中序遍歷序列是Ｃ。

A。abcdgefB.dfebagcC.dbaefcgD.defbagc

87.已知某二叉樹的后序遍歷序列是dabec，中序遍歷序列是debac，則其前序遍歷序列為

D.

A。acbedB.decabC。deabcD.cedba

88。如果T2是由有序樹T轉(zhuǎn)換而來的二叉樹,則T中結(jié)點的前序就是T2中結(jié)點的A.

A。前序B。中序C。后序D.層次序

89.樹的基本遍歷策略可分為先根遍歷和后根遍歷；二叉樹的基本遍歷策略可分為先序遍歷、

中序遍歷和后序遍歷。這里，我們把由樹轉(zhuǎn)化得到的二叉樹叫做這棵樹對應(yīng)的二叉樹。下面

結(jié)論正確的是A。

A。樹的先根遍歷序列與其對應(yīng)的二叉樹的先序遍歷序列相同

B。樹的先根遍歷序列與其對應(yīng)的二叉樹的后序遍歷序列相同

C。樹的先根遍歷序列與其對應(yīng)的二叉樹的中序遍歷序列相同

D.以上均不對

90。深度為5的二叉樹至多有Ｃ個結(jié)點。

A。16B。32C.31D。10

91。在一非空二叉樹的中序遍序序列中，根結(jié)點的右邊A.

A.只有右子樹的所有結(jié)點B.只有右子樹的部分

C.只有左子樹的部分結(jié)點D。只有左子樹的所有結(jié)點

92.樹最適合用來表示Ｃ。

A.有序數(shù)據(jù)元素B.無序數(shù)據(jù)元素

C.元素之間具有分支層次關(guān)系的數(shù)據(jù)D.元素之間無聯(lián)系的數(shù)據(jù)

93.設(shè)n，m為一棵二叉樹上的兩個結(jié)點，在中序遍歷時，n在m前的條件是C。

A。n在m的右方B。n是m的祖先

C。n在m的左方D。n是m的子孫

94.對一個滿二叉樹，m個樹葉,n個結(jié)點，深度為h,則D。

A。n=h+mB.h+m=2n

C。m=h-1D。n=2h—1

95。如果某二叉樹的前序為stuwv,中序為uwtvs，則該二叉樹后序為Ｃ。

A。uwvtsB。vwuts

C.wuvtsD。wutsv

96。設(shè)待排序的記錄為(20,16，13，14，19），經(jīng)過下列過程將這些記錄排序。

20，16,13,14，19

16,20，13，14,19

13，16，20,14,19

13,14，16,20，19

13，14，16,19,20

所用的排序方法是A.

A.直接插入排序B.冒泡排序

C.希爾排序D。堆排序

97.對下列4個序列用快速排序的方法進(jìn)行排序，以序列的第一個元素為基礎(chǔ)進(jìn)行劃分，在

第一趟劃分過程中，元素移動次數(shù)最多的是A序列。

A.70,75，82，90,23,16,10，68

B。70，75,68,23，10，16,90,82

C。82,75,70,16,10，90,68,23

D。23,10,16,70，82，75,68,90

98。用快速排序的方法對包含幾個關(guān)