本文格式為Word版，下載可任意編輯——數(shù)據(jù)結(jié)構(gòu)復(fù)習(xí)題目

第1章概論

練習(xí)題

一、單項(xiàng)選擇題

1．在數(shù)據(jù)結(jié)構(gòu)中，從規(guī)律上可以把數(shù)據(jù)結(jié)構(gòu)分為

A．緊湊結(jié)構(gòu)和非緊湊結(jié)構(gòu)B．線性結(jié)構(gòu)和非線性結(jié)構(gòu)C．內(nèi)部結(jié)構(gòu)和外部結(jié)構(gòu)D．動(dòng)態(tài)結(jié)構(gòu)和靜態(tài)結(jié)構(gòu)2．若結(jié)點(diǎn)的存儲(chǔ)地址與其關(guān)鍵字之間存在某種映射關(guān)系，則稱這種存儲(chǔ)結(jié)構(gòu)為

A．順序存儲(chǔ)結(jié)構(gòu)B．鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)C．索引存儲(chǔ)結(jié)構(gòu)D．散列存儲(chǔ)結(jié)構(gòu)3．算法分析的兩個(gè)主要方面是

A．正確性和簡明性B．時(shí)間繁雜性和空間繁雜性C．可讀性和可維護(hù)性D．?dāng)?shù)據(jù)繁雜性和程序繁雜性4．線性表采用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)時(shí)，要求內(nèi)存中可用存儲(chǔ)單元地址

A．不一定連續(xù)的B．部分地址必需是連續(xù)的C．必需是連續(xù)的D．一定是不連續(xù)的5．算法指的是

A．計(jì)算機(jī)程序B．解決問題的計(jì)算方法C．解決問題的有限運(yùn)算序列D．排序算法

（B）

（D）

（B）

（A）

（C）

二、填空題

6．?dāng)?shù)據(jù)結(jié)構(gòu)一般包括規(guī)律結(jié)構(gòu)、存儲(chǔ)結(jié)構(gòu)和數(shù)據(jù)運(yùn)算三個(gè)方面的內(nèi)容．7．?dāng)?shù)據(jù)的規(guī)律結(jié)構(gòu)可分為線性結(jié)構(gòu)、非線性結(jié)構(gòu)兩大類．

8．?dāng)?shù)據(jù)的存儲(chǔ)結(jié)構(gòu)（物理結(jié)構(gòu)）一般可以用順序存儲(chǔ)結(jié)構(gòu)、鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)、索引存儲(chǔ)結(jié)構(gòu)及散列存儲(chǔ)結(jié)構(gòu)等四種存儲(chǔ)方法表示．

9．在選用求解一個(gè)問題的算法時(shí)，除了首先考慮算法是“正確的〞之外，還主要考慮執(zhí)行算法所需要的時(shí)間、執(zhí)行算法所需要的存儲(chǔ)空間及算法應(yīng)易于理解、易于編程、易于調(diào)試等三點(diǎn)。

10．設(shè)有一批數(shù)據(jù)元素，為了最快地存取某元素，宜用順序結(jié)構(gòu)存儲(chǔ)，為了便利的插入一個(gè)元素，宜用鏈?zhǔn)浇Y(jié)構(gòu)存儲(chǔ)．

三、應(yīng)用題

設(shè)n為正整數(shù)，利用大“O〞記號(hào)，寫出以下各程序段的時(shí)間繁雜度．11．for(i=1;i=(s+1)*(s+1))

s=s+1;

分析：語句“s=s+1;〞執(zhí)行n次，故該程序段的時(shí)間繁雜度為O(n)．

13．x=1;sum=0;

for(i=0;inext==headC．head?>next==NULLD．head==NULL4．在單循環(huán)鏈表中，p指向表任一結(jié)點(diǎn)，判斷表不是訪問終止的條件是（B）

A．p!=NULLB．p!=headC．p?>next!=headD．p?>next!=NULL5．在一個(gè)單鏈表中，已知q指向p所指向結(jié)點(diǎn)的前趨結(jié)點(diǎn)，若在p、q所指結(jié)點(diǎn)之間插入一個(gè)s所指向的新結(jié)點(diǎn)，則執(zhí)行的操作是（A）

A．q?>next=s;s?>next=pB．p?>next=s;s?>next=qC．s?>next=p?>next;p?>next=sD．p?>next=s?>next;s?>next=p6．在一個(gè)單鏈表中，若刪除p指向結(jié)點(diǎn)的后繼結(jié)點(diǎn)，則執(zhí)行的操作是（A）

A．q=p?>next;p?>next=p?>next?>next;free(q);B．p=p?>next;q=p?>next;p=q?>next;free(q);C．q=p?>next?>next;p=p?>next;free(q);D．p=p?>next?>next;q=p?>next;free(q);

二、填空題

7．在一個(gè)長度為n的順序表中刪除第i個(gè)元素，需要向前移動(dòng)n??i個(gè)元素．

8．在順序表中插入或刪除一個(gè)元素，需要平均移動(dòng)表長的一半個(gè)元素，具體移動(dòng)的元素個(gè)數(shù)與插入或刪除的位置有關(guān)．

9．順序表中規(guī)律上相鄰的元素在物理存儲(chǔ)位置上一定相鄰，鏈表結(jié)構(gòu)中規(guī)律上相鄰的元素在物理位置上不一定相鄰．

10．已知順序表中一個(gè)元素的存儲(chǔ)位置是x，每個(gè)元素占c個(gè)字節(jié)，求其后繼元素位置計(jì)算公式為x??c，而已知單鏈表中某一結(jié)點(diǎn)由p指向，求此后繼結(jié)點(diǎn)存儲(chǔ)地址的操作為p?>next．

11．在用p指針訪問單鏈表時(shí)，判斷不是訪問終止的條件是p!?NULL；在訪問單循環(huán)鏈表時(shí)，判斷不是訪問表終止的條件是p!?head．

12．已知p指向雙向鏈表的中間某個(gè)結(jié)點(diǎn)，從給定的操作語句中選擇適合的填空．（1）在p結(jié)點(diǎn)后插入s結(jié)點(diǎn)的語句序列是I、G、A、D．（2）在p結(jié)點(diǎn)前插入s結(jié)點(diǎn)的語句序列是C、N、H、B．

（3）刪除p結(jié)點(diǎn)的直接后繼結(jié)點(diǎn)的語句序列是J、Q、E、M．（4）刪除p結(jié)點(diǎn)的直接前趨結(jié)點(diǎn)的語句序列是K、P、F、M．（5）刪除p結(jié)點(diǎn)的語句序列是O、R、L．

A．p?>next?sB．p?>prior?sC．s?>next?pD．s?>prior?pE．p?>next?p?>next?>nextF．p?>prior?p?>prior?>prior

G．p?>next?>prior??sH．p?>prior?>next??sI．s?>next?p?>nextJ．q?p??>nextK．q?p??>priorL．free(p)M．free(q)N．s?>prior?p?>priorO．p?>prior?>next??p?>nextP．p?>prior?>prior??>next??pQ．p?>next?>next??>prior?pR．p?>next??>prior?p??>prior13．下面是一個(gè)在帶頭結(jié)點(diǎn)的單鏈表head中刪除所有數(shù)據(jù)域值為x的結(jié)點(diǎn)的算法，但不完善，請?jiān)谙鄳?yīng)的地方填上適當(dāng)?shù)恼Z句，使之成為完整的算法．

voidDeleX(LinkListhead,DataTypex){LinkNode*p,*q,*s;

}

P?head;q??p?>next;while(q!=NULL)

if(q?>data??x){

s?q;

q?q?>next;free(s);

p?>next?q;}else{p?q;q?q?>next;}

三、算法設(shè)計(jì)題

14．設(shè)有兩個(gè)順序表A和B，且都遞增有序。試寫一算法，從A中刪除與B中一致的那些元素（即計(jì)算A??B）．

SeqListSubtraction(SeqListA,SeqListB){

inti,j,k?0;//令匹配位置為0for(i?0;inext;

if(q!?NULL)//判斷所指結(jié)點(diǎn)是否是最終一個(gè)結(jié)點(diǎn){}

elseprintf(“p指向的結(jié)點(diǎn)無后繼節(jié)點(diǎn)!〞)}

if(p??head)//判斷所指結(jié)點(diǎn)是否是頭結(jié)點(diǎn){}else{}

r?head;

while(r?>next!?p)

r?r?>next;//查找p指向結(jié)點(diǎn)直接前趨

r?>next?q;//p指向結(jié)點(diǎn)直接前趨指針域指向p指向結(jié)點(diǎn)直接后繼

p?>next?q?>next;//p指向結(jié)點(diǎn)指針域指向p指向結(jié)點(diǎn)直接后繼的直接后繼q?>next?p;//p指向結(jié)點(diǎn)直接后繼指針域指向p

head?head?>next;//頭結(jié)點(diǎn)指針域所指結(jié)點(diǎn)變成新的頭結(jié)點(diǎn)s?head?>next;//記錄第2個(gè)結(jié)點(diǎn)

head?>next?p;//新的頭結(jié)點(diǎn)指針域指向原頭結(jié)點(diǎn)

p?>next??s;//原頭結(jié)點(diǎn)變成第1個(gè)結(jié)點(diǎn)后指針域指向第2個(gè)結(jié)點(diǎn)

16．已知兩條單鏈表A和B分別表示兩個(gè)集合，其元素值遞增有序。試寫一算法，求A和B的交集C，要求C同樣以元素值遞增的單鏈表形式存儲(chǔ)．

LinkListIntersection(LinkListA,LinkListB){

LinkNode*p,*q,*r,*s;

LinkListC?(LinkNode*)malloc(SizeOf(LinkNode));r?C;p?A;}}

s?B;