《計算機軟件基礎》考試題庫及答案

《計算機軟件基礎》復習題庫(帶答案)

1.線性表的虛式存儲結構與順序存儲結構相比優(yōu)點是CD.

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

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

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

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

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

3.若長度為n的線性表采用順序存儲結構，在其第1個位置插入一個新元素的算法的時間復雜度為(：°(IWlWn+I)

A.0(0)B.0(1)

C.0(n)D.0(n2)

4.設A是?個線性表⑥,山,…,a),采用順序存儲結構，則在等概率的前提下，平均每插入一個元素需要移動的元素個數(shù)為

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

2(〃-i)

A:若元素插在a.與a.”之間(OWIWnT)的概率為---------，則平均每插入一個元素所要移動的元素個數(shù)為

n(n+1)

c；

n-ln

2n+13〃+1

c.----D.---------

34

5.下列函數(shù)中，按它們在〃-8時的無窮大階數(shù)，最大的是一D.

A.lognB.nlogn

C.2n/2D.n!

6.將下圖所示的s所指結點加到p所指的結點之后，其語句應為：I)

nextnext

next

A.s->next=p+l;p->next=s;

B.(*p).next=s;(*s).next=(*p).next;

C.s->next=p->next;p->next=s->next;

I).s->next=p->next;p->next=s;

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

A.nB.2n~l

C.n-lD.2n

8.下面的程序段是合并兩個無頭結點鏈表(ha和hb)為一個無頭結點鏈表ha的過程，作為參數(shù)的兩個鏈表都是按結點的data

域由大到小鏈接的。合并后新鏈表的結點仍按此方式鏈接。請?zhí)顚懴率隹湛颍钩绦蚰苷_運行。

#defineNULL0

typedefstructnode(

intdata;

structnode*next;

}node,linklisttype;

voidcombine(1ink1isttype*ha,linklisttype*hb){

linklisttype*h,*p;

h=(linklisttype*)malloc(sizeof(1ink!isttype));

h->next=NULL;

p=h;

while(ha!=NULL&&hb!=NULL)

if(ha->data>=hb->data)(/*較大的元素先插入*/

p->next=(1)

P=⑵；

⑶：

else{

p->next=(4);

P=(5);

⑹；

)

if(ha=NULL)⑺;

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中所有元素（a1,a2,an）與表B的一個順序子表（bk,b”，…b-J完全相同（即a）=bk,a2=bk.b,?,an=bk.ni）,則稱表A包

含在表B中。設ha,hb為帶頭結點的單鏈衣，分別表示有序表A和B,下面的函數(shù)用手判別表A是否包含在表B中，若是，則

返回true,否則返回false。（提示：用遞歸實現(xiàn)）

ttdefinetrue1

#definefalse0

^defineNULL0

typedefstructnode{

intdata;

structnode*next;

}node,linklisttype;

intinclusion(1inklisttype*ha,Iinklisttype*hb){

linklisttype*pa,*pb;

pa=ha->next;

pb=hb->next;

⑴；

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個結點的循環(huán)鏈表；函數(shù)josephus(n,I,m)對由

create」ink」ist(n)所建立的具有n個結點的循環(huán)鏈表按一定的次序逐個輸出，并刪除鏈表中的所有結點。參數(shù)n(n>0)指明循

環(huán)鏈表的結點個數(shù)，參數(shù)I(lWlWn)指明起始結點，參數(shù)m(m>0是步長)，指明從起始結點或前次被刪除并輸出的結點之后的

第m個結點作為本次被輸出并刪除的結點。例如，對于下圖所示的具有6個結點的循環(huán)鏈表，在調用josephus(6,3,2)后，將輸

出5,1,3,6,4,2。請在空框處填上適當內容,每框只填一個語句。

^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(1inklisttype));

p=head;

for(I=1;I<=n-1;1++){/*此循環(huán)用于建立一個鏈表，鏈表的內容從1至nT*/

p->data=I;

q=(linklisttype*)malloc(sizeof(1inklistttype));

⑴；

⑵；

)

p->data=n;

⑶；/*建立從尾鏈到首的環(huán)形結構*/

)

return(head);

)

voidJosephus(intn,intj,intm){

linklisttype*p,*q;

intj：

p=create」ink」ist(n);

for(;I>1;I-)p=p->next;

⑷；

while(j<n){

for(1=1;I<=m-1;I++)p=p->next;

_______(5)______;

printf(a%8dM,q->data);

⑹；

free(q)：

j=j+l：

)

I

參考答案：

(1)p->next=q;

(2)p=q;

(3)p->next=head

(4)j=0

(5)q=p->next;

(6)p->next=q->next

1.在下列程序中,函數(shù)difference(A,B)用于求兩集合之差C=A-B,即當且僅當e是A中的?個元素，且不是B中的元素時,e

是C中的一個元素。集合用有序鏈表實現(xiàn)，用一個空鏈表表示一個空集合，表示非空集合的鏈表根據(jù)元素之值按遞增排列，執(zhí)

行C=A-B之后，表示集合A和B的鏈表不變，若結果集合C非空，則表示它的鏈表應根據(jù)元素之值按遞增序排列。函數(shù)append。

用于在鏈表中添加結點。

^include<stdio.h>

^defineNULL0

typedefstructnode{

intdata;

structnode*next;

}NODE;

NODE*append(NODE*last,intx){

1ast->next=(NODE*)malloc(sizeof(NODE));

last->next->data=x;

return(last->next);

)

NODE"difference(NODE*A,NODE*B){

NODE*C,*last;

C=last=(NODE*)ma1loc(sizeof(NODE));

while(G))

if(A->data<B_>data){

last=append(last,A->data);

A=A->next:

else

if((2)){

A=A->next;

B=B->next;

}

else

⑶；

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.閱讀以下算法，填充空格，使其成為完整的算法。其功能是在?個非遞減的順序存儲線性表中(從下標1處開始存儲)，刪除

所有值相等的多余元素。

#defineMAXSIZE30

typedefstruct(

intelem[MAXSIZE];

intlength;/*表長*/

}sqlistlype;

voidexam21(sqlisttype*L){

inti,j;

i=l,j=2;

while((I)){

if(L->elem[i]!=L->elem[j])

|

if(j!=(i+D)

⑵；

L->length=L->length-(j-i-l);

⑶；

else

{

⑷；

if(j>L->length)(5);

)

I

I

參考答案：

(1)j<=L->length

(2)for(intk=j;k<=L->length;k++)L->elem[k-(j-i-l)]=L->elem[k];

(3)i++,j=i+l;

(4)j++;

(5)(L->length=L->length-(j-i-l);break:}

13.用單鏈表表示的鏈式隊列的隊頭在鏈表的A位置。

A.鏈頭B,鏈尾C.鏈中

14.若用單鏈表表示隊列，則應該選用B°

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

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

15.在解決計算機主機與打印機之間速度不匹配問題時，通常設置?個打印數(shù)據(jù)緩沖區(qū)，主機將要輸出的數(shù)據(jù)依次寫入該緩沖區(qū)，

而打印機則從該緩沖區(qū)中取出數(shù)據(jù)打印，先放入打印緩沖區(qū)的數(shù)據(jù)先被打印。該緩沖區(qū)應該是一個B結構。

A.堆棧B.隊列

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

16.若用一個大小為6的數(shù)組來實現(xiàn)循環(huán)隊列，且當前rear和front的值分別為。和3。當從隊列中刪除一個元素，再加入兩個

元素后，rear和front的值分別為B。

A.1和5B.2和4

C.4和2D.5和1

17.設棧的輸入序列為1,2,…，10,輸出序列為ag,…,a。,若8s=10,則a?為C0

A.4B.8C.不確定1).7

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

A.1243B.2134C.1432D.4312

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

A.abedB.321ABC.“abcABC”I).“21AB”

20.若串S="software”，其子串的數(shù)目是一C0

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

21.將一個A[l:100,1:100]的三對角矩陣，按行優(yōu)先存入一維數(shù)組B[l:298]中，A中元素A66,65(即該元素的下標)在B數(shù)組中

位置k為B。

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

22.設高為h的二叉樹只有度為0和2的結點，則此類二叉樹的結點數(shù)至少為2,至多為F。高為h的完全

二叉樹的結點數(shù)至少為一E,至多為__F____D

A.2hB.2h-lC.2h+lD.h+1

E.2gF.2-1G.2hM-lH.2h+l

23.一棵有124個葉結點的完全二叉樹，最多有_B個結點。

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

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

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

C.堆D.二叉查找樹

25.前用遍歷和中序遍歷結果相同的二叉樹為F:前序遍歷和后序遍歷結果相同的二叉樹為B。

A.一般二叉樹B.只有根結點的二叉樹

C.根結點無左孩子的二叉樹D.根結點無右孩子的二叉樹

E.所有結點只有左孩子的二叉樹F.所有結點只有右孩子的二叉樹

26.具有n個結點的完全二叉樹，已經(jīng)順序存儲在?維數(shù)組A[L.n]中，下面的算法是將A中順序存儲變?yōu)槎骀湵泶鎯Φ耐耆?/p>

二叉樹。請?zhí)顚戇m當語句在下面的空格內，完成上述算法。

^defineMAXSIZE30

typedefstructbtnode(

intdata;

structbtnode*lchild,*rchild;

}BTN;

voidcreatetree(BTN*p,intA[],intI,intn){

⑴；

p->data=A[I];

if((2))

⑶；

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*)ma11oc(sizeof(BTN))

(2)2*1<=n

(3)createtree(p->lchiId,A,2*1,n)

(4)2*I+K=n

(5)p->rchiId,A,2*1+1,n

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

A.元素按值有序B.采用順序存儲結構

C.元素按值有序，R采用順序存儲結構D.元素按值有序，旦采用鏈式存儲結構

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

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

29.假定有K個關鍵字互為同義詞，若用線性探測法把這K個關鍵字存入散列表中，至少要進行D次探測。

A.K-1次B.K次

C.K+1次D.K(K+l)/2次

30.在n個記錄的有序順序表中進行折半傷找，最大的比較次數(shù)是|10g2〃」+1

31.Hash技術廣泛應用于查找過程，選擇Hash函數(shù)的標準是和。處理沖突的技術有優(yōu)有劣，其共同標

準是o

32.在下述排序算法中，所輻輔助存儲空間最多的是B,所需輔助存儲空間最小的是C,平均速度最快的

是—A°

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

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

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

34.快速排序在最壞情況下時間復雜度是0(n2),比A的性能差。

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

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

A.快速排序B.堆排序

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

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

B方法最快o

A.冒泡排序B.快速排序

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

37.以下結點序列是堆的為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)定的，則應選-C°

A.快速排序B.堆排序

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

39.從未排序序列中依次取出一個元素與已排序序列中的元素依次進行比較，然后將其放在已排序序列的合適位置，該排序方法

稱為A排序法。

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

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

40.百一接插入排序在最好情況下的時間復雜度為B。

A.0(logn)B.0(n)

C.0(nlogn)1).0(n2)

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

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

for(i=n/2;i>0;i-)adjust(list,i,n);

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

voidadjust(intlist[],introot,intn){

/*將以root為下標的對應元素作為待調整堆的根，待調整元素放在list數(shù)組中，最大元素下標為n*/

intchild,rootkey;

rootkey=(1);

chiId=2*root;

while(child<n){

if((child<n)&&(1ist[child]<list[child+1]))

(2);

if(rootkey>listtchild])

break;

else{

list[⑶]=list[child];

⑷：

)

1ist[(5)]=rootkey;

)

參考答案：

(1)list[root]

(2)child++;

(3)child/2

(4)child*=2;

(5)child/2

41.表是一種數(shù)據(jù)結構，鏈表是種⑴°隊列和棧都是線性表，棧的操作特性是(2),隊列的操作特性

是一⑶.今有一空棧S，對下列待進棧的數(shù)據(jù)元素序列為人。,人孰￡依次進棧、進棧、出棧、進棧、進棧、出棧的操

作，則此操作完成后，棧S的棧頂元素為(4),棧底元素為(5)°

供選答案

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

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

(2):A.隨機進出B.先進后出

C.先進先出D.出優(yōu)于進

(3):A.隨機進出B.先進后出

C.后進后出D.進優(yōu)于出

(4):A.fB.C

C.aD.b

(5):A.bB.C

C.aD.d

答案:ABCBC

42.操作系統(tǒng)主要是對計算機系統(tǒng)全部(1)進行管理,以方便用戶、提高計算機使用效率的一種系統(tǒng)軟件。它的主要

功能有：處理機管理、存儲管理、文件管理、(2)管理和設備管理等。Windows和Unix是最常用的兩類操作系統(tǒng)。前者

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

在(5)操作系統(tǒng)控制下,計算機能及時處理由過程控制反饋的信息并作出響應。

供選答案：

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

C.資源I).設備

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

C.中斷1).I/O

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

C.多用戶D.實時

(4):A.PASCALB.宏

C.匯編I).C

(5):A.網(wǎng)絡B.分時

C.批處理D.實時

答案：CBBDD

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

程序一邊讀入整數(shù)，?邊構造?個從大到小順序鏈接的鏈表，直至不能從鍵盤讀入整數(shù)，然后順序輸出鏈表上各表元的整

數(shù)值。主函數(shù)每讀入一個整數(shù)，就調用函數(shù)insert。，函數(shù)insert0將還未出現(xiàn)在鏈表上的整數(shù)按從大到小的順序插入到鏈表

中。

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

閱讀下列C代碼，在（n）處填入相應的字句以完成上述功能。

#include<stdio.h>

^include<malloc.h>

^defineNULL0

typedefstructnode(

intval;

structnode*next;

}NODE;

voidinsert(NODE*1ist,intx){

NODE*u,*v,*p;

u=list;v=u->next;

while(⑴&&x<v->val){/*尋找插入位置*/

u=v;v=u->next;

)

if((v-NULL||(2)){/*判斷是否要插入表元*/

p=(NODE*)malloc(sizeof(NODE));

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

⑶=v;(4)=p;/*插入新表元*/

)

)

mainO{

intx;

NODE*head,*p;

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

head=(NODE*)malloc(sizeof(NODE));

⑸=NULL;

printf(<4EnterIntegers:\nw);

while(scanf(u%dn,&x)=1)/*反復讀入整數(shù)插入鏈表*/

inserl(head,x);

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

printf(a%d\tn,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.計算機數(shù)據(jù)處理的對象是具有不同結構的各種數(shù)據(jù)，可以訪問的最小數(shù)據(jù)信息單位是

⑴，可以引用的最小命名數(shù)據(jù)單位是一(2),

線性表是最簡單的一種數(shù)據(jù)結構，有順序和鏈接兩種存儲方式。線性表按鏈接方式存儲時，每個結點的包括⑶

兩部分。

線性表的查找彳i⑷和(5)兩種,但(5)只能用于順序存儲的情況。

供選答案

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

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

(2):A.結點B.記錄

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

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

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

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

C.二分法查找D.瀏覽

(5):A.隨機查找B.順序查找

C.二分法查找D.瀏覽

答案：CDBBC

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

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

#include<stdio.h>

#include<malloc.h>

typedefstructnode(

intval;

structnode*next;

}N0DE;

NODE*ins(NODEintx){/*將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:

e1se(1);

⑵；

return1ist;

}

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;

whi31){

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

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

scanf(%d,&ans);

if(⑸)return;

printf("輸入整數(shù)：");scanf(u%dn,&x);

if(ans=l)list=ins(list,x);

elselist=del(list,x);

for(p=list;p!=NULL;p=p->next)

printf(“融d”，p->val);

)

}

答案：

(1)u->next=p;

(2)p->next=v

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

(4)free(v)

(5)ans!=1&&ans!=2

46.從未排序的序列中，依次取出元素，與已排序序列的元素比較后，放入已排序序列中的恰當位置上，這是⑴排

序。從未排序的序列中，挑選出元素，放在已排序序列的某一端位置，這是⑵排序。逐次將待排序的序列中的相

鄰元素兩兩比較，凡是逆序則進行交換，這是一⑶排序。如果整個排序過程都在內存中進行，稱為

⑷排序。排序算法的熨雜性與排序算法的（生有關。

供選答案：

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

C.比較D.歸并

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

C.比較D.歸并

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

C.比較D.散列

(4):A.外部B.內部

C.外存D.內存

(5):A.運兜量大小與占用存儲多少

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

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

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

答案：BAABA

47.操作系統(tǒng)是對計算機資源進行的(1)系統(tǒng)軟件,是(2)的接口。

在處理機管理中，進程是一個重要的概念，它由程序塊、(3)和數(shù)據(jù)塊三部分組成,它有3種基本狀態(tài)，不可

能發(fā)生的狀態(tài)轉換是(4).

虛擬存儲器的作用是允許程序直接訪問比內存更大的地址空間，它通常使用(5)作為它的一個主要組成部分。

供選答案：

(1):A.輸入和輸出B.鍵盤操作

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

(2):A.軟件和硬件B.主機和外設

C.高級語言和機器語言D.用戶和計算機

(3):A.進程控制塊B.作業(yè)控制塊

C.文件控制塊D.設備控制塊

(4):A.運行態(tài)轉換為就緒態(tài)B.就緒態(tài)轉換為運行態(tài)

C.運行態(tài)轉換為等待態(tài)D.等待態(tài)轉換為運行態(tài)

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

C.CDROMD.寄存器

答案：CDADB

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

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

49.下列程序段的時間由雜度為C°

for(i=l：i<n;i++){

y=y+l;

for(j=0;j<=(2*n):j++)x++;

)

供選答案：

A.O(n-l)B.0(2n)C.0(n2)D.0(2n+l)

50.下面程序段的時間復雜度為I)。

i=l;

while(i<=n)i=i*2;

供選答案：

A.0(1)B.0(n)C.0(n2)I).O(logzn)

51.下面程序段的時間由雜度為B°

a=O;b=l;

for(i=2;i<=n;i++){

s=a+b;

b=a;

供選答案:

A.0(1)B.0(n)C.0(log?n)D.0(n2)

52.數(shù)據(jù)結構是一門研究非數(shù)值計算的程序設計問題中，計算機的A以及它們之間的關系和運和等的學科。

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

53.在數(shù)據(jù)結構中，從邏輯上可以把數(shù)據(jù)結構分成C°

A.動態(tài)結構和靜態(tài)結構B.緊湊結構和非緊湊結構

C.線性結構和非線性結構D.內部結構和外部結構

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

A.找出數(shù)據(jù)結構的合理性

B.研究算法中輸入和輸出的關系

C.分析算法的效率以求改進

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

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

A.間復雜性和時間復雜性B.正確性和簡明性

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

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

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

57.若已知?個棧的入棧序列是1,2,3,…,n,其輸出序列為R,%P.,…,P"，若P尸n，則為C。

A.iB.n_iC.n-i+lD.不確定

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

A.CABB.CBAC.ABCD.ACB

59.設有如下的單鏈表的按序號查找的算法，其時間復雜度為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.0(/)B.0(2n)C.0(n3)I).0(logn)

60.二維數(shù)組燈按行序為主順序存放在內存中，每個數(shù)組元素占1個存儲單元，則元素配的地址計算公式是C，

A.L0C(alt)=L0C(au)+[(i-l)*m+(j-l)]

B.L0C(aQ=L0C(a”)+[(jT)*m+(iT)]

C.L0C(alt)=LOC(au)+[(i-l)*n+(j-l)]

D.LOC(aij)=L0C(au)+[(」-l)*n+(iT)]

61.以下哪一個不是隊列的基本運算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分別為隊首指針和隊尾指針，則判斷隊空的條件是

Bo

A.front=rear+lB.front=rearC.front+l=rearD.front=0

65.從一個具有n個結點的單鏈表中查找其值等于x的結點時，在查找成功的情況下，需平均比較D個結點。

A.nB.n/2C.(n-l)/2D.(n+l)/2

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

A.edcbaB.decbaC.dceabD.abcde

67.棧結構通常采用的兩種存儲結構是一A。

A.順序存儲結構和鏈表存儲結構B.散列方式和索引方式

C.鏈表存儲結構和數(shù)組D.線性存儲結構和非線性存儲