大學計算機軟件技術(shù)基礎考試技術(shù)復習題

線性表采用鏈式存儲時，結(jié)點的存儲地址（）A．必須是不連續(xù)的B．連續(xù)與否均可C．必須是連續(xù)的D．和頭結(jié)點的存儲地址相連續(xù)由兩個棧共享一個向量空間的好處是：（）A．減少存取時間，降低下溢發(fā)生的機率B．節(jié)省存儲空間，降低上溢發(fā)生的機率C．減少存取時間，降低上溢發(fā)生的機率D．節(jié)省存儲空間，降低下溢發(fā)生的機率假設以帶行表的三元組表表示稀疏矩陣，則和下列行表02335對應的稀疏矩陣是（）在一棵度為3的樹中,度為3的結(jié)點個數(shù)為2,度為2的結(jié)點個數(shù)為1,則度為0的結(jié)點個數(shù)為()A．4B．5C．6一棵含18個結(jié)點的二叉樹的高度至少為(C)A.3B.4C.5D.6已知二叉樹的先序序列為ABDECF，中序序列為DBEAFC，則后序序列為(D)A.DEBAFCB.DEFBCAC.DEBCFAD.DEBFCA無向圖中一個頂點的度是指圖中(B)A.通過該頂點的簡單路徑數(shù)B.與該頂點相鄰接的頂點數(shù)C.通過該頂點的回路數(shù)D.與該頂點連通的頂點數(shù)設順序存儲的線性表共有123個元素，按分塊查找的要求等分成3塊。若對索引表采用順序查找來確定塊，并在確定的塊中進行順序查找，則在查找概率相等的情況下，分塊查找成功時的平均查找長度為(B)A.21B.23C.41D.62在含n個頂點和e條邊的無向圖的鄰接矩陣中,零元素的個數(shù)為()A．eB．2eC．n2－eD．n2－2e用某種排序方法對關(guān)鍵字序列（25，84，21，47，15，27，68，35，20）進行排序時，序列的變化情況如下：20，15，21，25，47，27，68，35，8415，20，21，25，35，27，47，68，8415，20，21，25，27，35，47，68，84則所采用的排序方法是（）A．選擇排序B．希爾排序C．歸并排序D．快速排序數(shù)據(jù)的邏輯結(jié)構(gòu)是從邏輯關(guān)系上描述數(shù)據(jù)，它與數(shù)據(jù)的存儲（或存儲結(jié)構(gòu)）無關(guān)，是獨立于計算機的。在一個帶頭結(jié)點的單循環(huán)鏈表中，p指向尾結(jié)點的直接前驅(qū)，則指向頭結(jié)點的指針head可用p表示為head=p－＞next－＞next。棧頂?shù)奈恢檬请S著進棧和退棧操作而變化的。假設一個9階的上三角矩陣A按列優(yōu)先順序壓縮存儲在一維數(shù)組B中，其中B[0]存儲矩陣中第1個元素a1,1,則B[31]中存放的元素是a4,8。已知一棵完全二叉樹中共有768結(jié)點，則該樹中共有384個葉子結(jié)點。已知一個圖的廣度優(yōu)先生成樹如右圖所示，則與此相應的廣度優(yōu)先遍歷序列為abefcdg。從順序表中刪除一個元素時，表中所有在被刪元素之后的元素均需___前移___一個位置。在隊列中，允許進行插入操作的一端稱為____隊尾____，允許進行刪除操作的一端稱為___隊頭___。在有序表（12，24，36，48，60，72，84）中二分查找關(guān)鍵字72時所需進行的關(guān)鍵字比較次數(shù)為２。已知一個無向圖的頂點集為{a,b,c,d,e},其鄰接矩陣如下所示abcde(1)畫出該圖的圖形；（2）根據(jù)鄰接矩陣從頂點a出發(fā)進行深度優(yōu)先遍歷和廣度優(yōu)先遍歷，寫出相應的遍歷序列。該圖的圖形為：深度優(yōu)先遍歷序列為：abdce廣度優(yōu)先遍歷序列為：abedc鏈棧與順序棧相比，比較明顯的優(yōu)點是(

d

)

A.插入操作更加方便

B.刪除操作更加方便

C.不會出現(xiàn)下溢的情況

D.不會出現(xiàn)上溢的情況

二叉樹中第5層上的結(jié)點個數(shù)最多為(

d

)

A.8

B.15

C.16

D.32

假設隊列q中的元素為(2,4,5,7,8),其中“2”為隊頭元素。寫出執(zhí)行函數(shù)調(diào)用algo(&q)后的隊列q；

(2)簡述算法algo的功能。

void

algo(Queue

*Q)

{

Stack

S;

InitStack(&S);

while

(!QueueEmpty(Q))

Push(&S,

DeQueue(Q));

while

(!

StackEmpty(&S))

ＥnQueue(Q,Pop(&S));

}

(1)87542

(2)

隊列倒置

在數(shù)據(jù)結(jié)構(gòu)中，數(shù)據(jù)的邏輯結(jié)構(gòu)可以分成（）

A．內(nèi)部結(jié)構(gòu)和外部結(jié)構(gòu)

B．線性結(jié)構(gòu)和非線性結(jié)構(gòu)

C．緊湊結(jié)構(gòu)和非緊揍結(jié)構(gòu)

D．動態(tài)結(jié)構(gòu)和靜態(tài)結(jié)構(gòu)

在以單鏈表為存儲結(jié)構(gòu)的線性表中，數(shù)據(jù)元素之間的邏輯關(guān)系用（）

A．數(shù)據(jù)元素的相鄰地址表示

B．數(shù)據(jù)元素在表中的序號表示

C．指向后繼元素的指針表示

D．數(shù)據(jù)元素的值表示

設p指向單鏈表中的一個結(jié)點，s指向待插入的結(jié)點，則下述程序段的功能是（）

s

->

next

=

p

->

next;

p

->

next

=

s;

t

=

p

->

data;

p

->

data

=

s

->

data;

s

->data

=

t;

A．結(jié)點*p與結(jié)點*s的數(shù)據(jù)域互換

B．在p所指結(jié)點的元素之前插入元素

C．在p所指結(jié)點的元素之后插入元素

D．在結(jié)點*p之前插入結(jié)點*s棧和隊列都是（）

A．限制存取位置的線性結(jié)構(gòu)

B．順序存儲的線性結(jié)構(gòu)

C．鏈式存儲的線性結(jié)構(gòu)

D．限制存取位置的非線性結(jié)構(gòu)

當在二叉排序樹中插入一個新結(jié)點時，若樹中不存在與待插入結(jié)點的關(guān)鍵字相同的結(jié)點，且新結(jié)點的關(guān)鍵字小于根結(jié)點的關(guān)鍵字，則新結(jié)點將成為（）

A．左子樹的葉子結(jié)點

B．左子樹的分支結(jié)點

C．右子樹的葉子結(jié)點

D．右子樹的分支結(jié)點

希爾排序的增量序列必須是（）

A．遞增的

B．隨機的

C．遞減的

D．非遞減的

如果在排序過程中，每次均將一個待排序的記錄按關(guān)鍵字大小加入到前面已經(jīng)有序的子表中的適當位置，則該排序方法稱為（）

A．插入排序

B．歸并排序

C．冒泡排序

D．堆排序

已知指針p指向單鏈表中某個結(jié)點，則語句p

->

next

=p

->

next

->

next的作用是________________。

刪除*P的直接后繼結(jié)點刪除雙向循環(huán)鏈表中*p的前驅(qū)結(jié)點(存在)應執(zhí)行的語句是____________。

q

=

p->pre;

q->pre->next

=

p;

p->pre

=

q->pre;

free(

q

);棧下溢是指在____?？誣_______時進行出棧操作。已知完全二叉樹T的第5層只有7個結(jié)點，則該樹共有___2^3

+

7

/

2

=

11___個葉子結(jié)點。

在有向圖中，以頂點v為終點的邊的數(shù)目稱為v的_____入度_______。

假設元素只能按a,b,c,d的順序依次進棧，且得到的出棧序列中的第一個元素為c，則可能得到的出棧序列為________________，不可能得到的出棧序列為________________

1)cbad,

cbda,

cdba

2)cabd,

cadb,

cdab若以鄰接矩陣表示有向圖，則鄰接矩陣上

第i行中非零元素的個數(shù)即為頂點vi的________________。

出度下列函數(shù)的功能是，對以帶頭結(jié)點的單鏈表作為存儲結(jié)構(gòu)的兩個遞增有序表（表中不存在值相同的數(shù)據(jù)元素）進行如下操作：將所有在Lb表中存在而La表中不存在的結(jié)點插入到La中，其中La和Lb分別為兩個鏈表的頭指針。請在空缺處填入合適內(nèi)容，使其成為一個完整的算法。

void

union

(LinkList

La,

LinkList

Lb)

{

//本算法的功能是將所有Lb表中存在而La表中不存在的結(jié)點插入到La表中

LinkList

pre

=

La,

q;

LinkList

pa

=

La

->

next;

LinkList

pb

=

Lb

->

next;

free

(Lb);

while

(pa

&&

pd)

{

if

(pa

->

data

<pb

->

data)

{

pre

=

pa;

pa

=

pa

->

next;}

else

if

(pa

->

data

>

pb

->data)

{

(1)

;

pre

=

pb;

pb

=

pb

->

next;

(2)

;

}

else

{

q

=

pb;

pb

=

pb

->

next;

free

(q);

}

}

if

(pb)

(3)

;

}

(1)

pre->next

=

pb

(2)

pre->next

=

pa

(3)

pre->next

=

pb

已知整形數(shù)組L［1..8］中的元素依次為（9，8，5，7，6，3，2，1），閱讀下列函數(shù)，并寫出執(zhí)行函數(shù)調(diào)用sort(L,

8)時，對L進行的頭兩趟（pass分別為0和1）處理結(jié)果。

Void

sort

(int

R[],int

n)

{

int

pass

=

0,

k,

exchange,

x;

do

{

k=pass%2+1;

exchange

=

0;

while

(k<n)

{

if

(R[k]>R[k+1])

{

x

=

R[k];

R[k]

=

R[k+1];

R[k+1]

=

x;

exchange

=1;

}

K+=2

}

pass

++;

}while

(exchange

=

=

1||

pass

<=1);

}

第一趟（pass

=

0）:

8

9

5

7

3

6

1

2

第二趟（pass

=

1）:

8

5

9

3

7

1

6

2

在長度為n的順序表中刪除第i個元素(1≤i≤n)時，元素移動的次數(shù)為(

)

A.

n-i+1

B.

i

C.

i+1

D.

n-i

若不帶頭結(jié)點的單鏈表的頭指針為head，則該鏈表為空的判定條件是(

)

A.

head==NULL

B.

head->next==NULL

C.

head!=NULL

D.

head->next==head

引起循環(huán)隊列隊頭位置發(fā)生變化的操作是(

)

A.

出隊

B.

入隊

C.

取隊頭元素

D.

取隊尾元素

若進棧序列為1，2，3，4，5，6，且進棧和出?？梢源┎暹M行，則不可能出現(xiàn)的出棧序列是(

)

A.

2，4，3，1，5，6

B.

3，2，4，1，6，5

C.

4，3，2，1，5，6

D.

2，3，5，1，6，4

對關(guān)鍵字序列(56，23，78，92，88，67，19，34)進行增量為3的一趟希爾排序的結(jié)果為(

)

A.

(19，23，56，34，78，67，88，92)

B.

(23，56，78，66，88，92，19，34)

C.

(19，23，34，56，67，78，88，92)

D.

(19，23，67，56，34，78，92，88)

由同一關(guān)鍵字集合構(gòu)造的各棵二叉排序樹(

)

A.

其形態(tài)不一定相同，但平均查找長度相同

B.

其形態(tài)不一定相同，平均查找長度也不一定相同

C.

其形態(tài)均相同，但平均查找長度不一定相同

D.

其形態(tài)均相同，平均查找長度也都相同

數(shù)據(jù)的邏輯結(jié)構(gòu)在計算機存儲器內(nèi)的表示，稱為數(shù)據(jù)的_____存儲結(jié)構(gòu)_______。

假設以數(shù)組seqn［m］存放循環(huán)隊列的元素，設變量rear和quelen分別指示循環(huán)隊列中隊尾元素的位置和元素的個數(shù)。

(1)寫出隊滿的條件表達式；

(2)寫出隊空的條件表達式；

(3)設m=40,rear=13,quelen=19,求隊頭元素的位置；

(4)寫出一般情況下隊頭元素位置的表達式。

(1)

quelen

==

m

(2)

quelen

==

0

(3)

(

13

-

19

+

40

)

%

40

=

34

(4)

(

rear

-

quelen

+

m

)

%

m

閱讀下列算法，并回答問題：

(1)設順序表L=(3,7,11,14,20,51)，寫出執(zhí)行f30(&L,15)之后的L；

(2)設順序表L=(4,7,10,14,20,51)，寫出執(zhí)行f30(&L,10)之后的L；

(3)簡述算法的功能。

void

f30(SeqList*L,

DataType

x)

{

int

i

=0,

j;

while

(i<L->length

&&

x>L->data［i］)i++;

if(i<L->length

&&

x==L->data［i］)

{//找到x，則刪除x，大于x的數(shù)前移

for(j=i+1;j<L->length;j++)

L->data［j-1］=L->data［j］;

L->length--;

}

else

{//沒找到，插入x,

大于x的數(shù)后移

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

L->data［j］=L->data［j-1］;

L->data［i］=x;

L->length++;

}

}

(1)

L=(3,7,11,14,15,20,51)

(2)

L=(4,7,14,20,51)

(3)

在順序表L中查找數(shù)x,

找到，則刪除x，

沒找到，則在適當?shù)奈恢貌迦離，插入后，L依然有序.

假設數(shù)組L［8］={3,0,5,1,6,4,2,7}，寫出執(zhí)行函數(shù)調(diào)用f32(L，8)后的L；

(2)寫出上述函數(shù)調(diào)用過程中進行元素交換操作的總次數(shù)。

void

f32(int

R［］,int

n){

int

i,t;

for

(i=0;i<n-1;i++)

while

(R［i］!=i){

t=R［R［i］］;

R［R［i］］=R［i］;

R［i］=t;

}

}

while(){}里是把R[

i

]

和

R[

R[

i

]

]

交換;

(1)

L

=

{

0,

1,

2,

3,

4,

5,

6,

7

};

(2)5次

能進行二分查找的線性表,必須以（A）

A．順序方式存儲,且元素按關(guān)鍵字有序

B．鏈式方式存儲,且元素按關(guān)鍵字有序

C．順序方式存儲,且元素按關(guān)鍵字分塊有序

D．鏈式方式存儲,且元素按關(guān)鍵字分塊有序

數(shù)組采用順序存儲方式表示是因為通常不對數(shù)組進行___插入和刪除______操作。

結(jié)點數(shù)為20的二叉樹可能達期的最大高度為____19_____。

在現(xiàn)代操作系統(tǒng)中引入了（），從而使并發(fā)和共享成為可能。A.單道程序B.磁盤C.對象D.多道程序()操作系統(tǒng)允許在一臺主機上同時連接多臺終端，多個用戶可以通過各自的終端同時交互地使用計算機。A.網(wǎng)絡B.分布式C.分時D.實時當一個進程處于（）狀態(tài)時，稱其為等待（或阻塞）狀態(tài)。A.它正等待中央處理機 B.它正等待合作進程的一個消息C.它正等待分給它一個時間片D.它正等待進入內(nèi)存一個進程釋放一種資源將有可能導致一個或幾個進程（）。A.由就緒變運行B.由運行變就緒C.由阻塞變運行D.由阻塞變就緒有m個進程共享同一臨界資源，若使用信號量機制實現(xiàn)對一臨界資源的互斥訪問，則信號量的變化范圍是（）。A.1至–(m-1)B.1至m-1C.1至–mD.1至m在下面關(guān)于虛擬存儲器的敘述中，正確的是（）。A.要求程序運行前必須全部裝入內(nèi)存且在運行過程中一直駐留在內(nèi)存B.要求程序