大學(xué)計(jì)算機(jī)軟件技術(shù)基礎(chǔ)考試技術(shù)復(fù)習(xí)題

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

d

)

A.插入操作更加方便

B.刪除操作更加方便

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

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

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

d

)

A.8

B.15

C.16

D.32

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

(2)簡(jiǎn)述算法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)

隊(duì)列倒置

在數(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．動(dòng)態(tài)結(jié)構(gòu)和靜態(tài)結(jié)構(gòu)

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

A．?dāng)?shù)據(jù)元素的相鄰地址表示

B．?dāng)?shù)據(jù)元素在表中的序號(hào)表示

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

D．?dāng)?shù)據(jù)元素的值表示

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

s

->

next

=

p

->

next;

p

->

next

=

s;

t

=

p

->

data;

p

->

data

=

s

->

data;

s

->data

=

t;

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

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

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

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

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

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

C．鏈?zhǔn)酱鎯?chǔ)的線性結(jié)構(gòu)

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

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

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

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

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

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

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

A．遞增的

B．隨機(jī)的

C．遞減的

D．非遞減的

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

A．插入排序

B．歸并排序

C．冒泡排序

D．堆排序

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

->

next

=p

->

next

->

next的作用是________________。

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

q

=

p->pre;

q->pre->next

=

p;

p->pre

=

q->pre;

free(

q

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

+

7

/

2

=

11___個(gè)葉子結(jié)點(diǎn)。

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

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

1)cbad,

cbda,

cdba

2)cabd,

cadb,

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

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

出度下列函數(shù)的功能是，對(duì)以帶頭結(jié)點(diǎn)的單鏈表作為存儲(chǔ)結(jié)構(gòu)的兩個(gè)遞增有序表（表中不存在值相同的數(shù)據(jù)元素）進(jìn)行如下操作：將所有在Lb表中存在而La表中不存在的結(jié)點(diǎn)插入到La中，其中La和Lb分別為兩個(gè)鏈表的頭指針。請(qǐng)?jiān)诳杖碧幪钊牒线m內(nèi)容，使其成為一個(gè)完整的算法。

void

union

(LinkList

La,

LinkList

Lb)

{

//本算法的功能是將所有Lb表中存在而La表中不存在的結(jié)點(diǎn)插入到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)時(shí)，對(duì)L進(jìn)行的頭兩趟（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

在長(zhǎng)度為n的順序表中刪除第i個(gè)元素(1≤i≤n)時(shí)，元素移動(dòng)的次數(shù)為(

)

A.

n-i+1

B.

i

C.

i+1

D.

n-i

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

)

A.

head==NULL

B.

head->next==NULL

C.

head!=NULL

D.

head->next==head

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

)

A.

出隊(duì)

B.

入隊(duì)

C.

取隊(duì)頭元素

D.

取隊(duì)尾元素

若進(jìn)棧序列為1，2，3，4，5，6，且進(jìn)棧和出?？梢源┎暹M(jìn)行，則不可能出現(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

對(duì)關(guān)鍵字序列(56，23，78，92，88，67，19，34)進(jìn)行增量為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)不一定相同，但平均查找長(zhǎng)度相同

B.

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

C.

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

D.

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

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

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

(1)寫出隊(duì)滿的條件表達(dá)式；

(2)寫出隊(duì)空的條件表達(dá)式；

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

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

(1)

quelen

==

m

(2)

quelen

==

0

(3)

(

13

-

19

+

40

)

%

40

=

34

(4)

(

rear

-

quelen

+

m

)

%

m

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

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

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

(3)簡(jiǎn)述算法的功能。

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，

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

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

(2)寫出上述函數(shù)調(diào)用過程中進(jìn)行元素交換操作的總次數(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次

能進(jìn)行二分查找的線性表,必須以（A）

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

B．鏈?zhǔn)椒绞酱鎯?chǔ),且元素按關(guān)鍵字有序

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

D．鏈?zhǔn)椒绞酱鎯?chǔ),且元素按關(guān)鍵字分塊有序

數(shù)組采用順序存儲(chǔ)方式表示是因?yàn)橥ǔ２粚?duì)數(shù)組進(jìn)行___插入和刪除______操作。

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

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