數(shù)據(jù)結(jié)構(gòu)復(fù)習(xí)資料

1、 1 第二章 線性表 二、填空題 1.為了便于討論，有時(shí)將含 n(n>=0)個(gè)結(jié)點(diǎn)的線性結(jié)構(gòu)表示成(a1，a2,??an)，其中每個(gè) ai 代表一個(gè)結(jié)點(diǎn)。a1 稱(chēng)為起始結(jié)點(diǎn)，an 稱(chēng)為終端結(jié)點(diǎn)， i 稱(chēng)為 ai在線性表中的位置或序號(hào)。 對(duì)任意一對(duì)相鄰結(jié)點(diǎn) ai、 ai┼1(1=1)個(gè)內(nèi)存單元， 其中， b 是順序表的第一個(gè)存儲(chǔ)結(jié)點(diǎn)的第一個(gè)單元的內(nèi)存地址，那么，第 i 個(gè)結(jié)點(diǎn) ai的存儲(chǔ)地址為 b+(i-1)Xk。 10.以下為

2、順序表的插入運(yùn)算，分析算法，請(qǐng)?jiān)赺_____處填上正確的語(yǔ)句。 Void insert_sqlist(sqlist L，datatype x，int i) /*將 X 插入到順序表 L 的第 i-1 個(gè)位置*/ { if( L.last == maxsize) error(“表滿”)； if((iL.last+1))error(“非法位置”); for(j=L.last;j>=i;j--)L.data[j]=l.data[j-1

3、]; L.data[i-1]=x; L.last=L.last+1; } 11.對(duì)于順序表的插入算法 insert_sqlist 來(lái)說(shuō)， 若以結(jié)點(diǎn)移動(dòng)為標(biāo)準(zhǔn)操作， 則插入算法的最壞時(shí)間復(fù)雜性為_(kāi)__n_____， 量級(jí)是__O(n)_。插入算法的平均時(shí)間復(fù)雜性為 n/2，平均時(shí)間復(fù)雜性量級(jí)是 O(n)。 12.以下為順序表的刪除運(yùn)算，分析算法，請(qǐng)?jiān)赺_______處填上正確的語(yǔ)句。 void delete_sqlist(sqlist

4、 L,int i) /*刪除順序表 L 中的第 i-1 個(gè)位置上的結(jié)點(diǎn)*/ {if((iL.last))error(“非法位置”)； for(j=i+1;j=L.last;j++)_____L.data[j-2]=L.data[j-1]___; L.last=L.last-1; } 13.對(duì)于順序表的刪除算法 delete_sqlist 來(lái)說(shuō)，若以結(jié)點(diǎn)移動(dòng)為標(biāo)準(zhǔn)操作，最壞情況時(shí)間復(fù)雜性及其量級(jí)分別是__n-1______和__O(

5、n)______,其平均時(shí)間復(fù)雜性及其量級(jí)分別為_(kāi)_(n-1)/2______和__O(n)______。 14.以下為順序表的定位運(yùn)算，分析算法，請(qǐng)?jiān)赺_______處填上正確的語(yǔ)句。 int locate_sqlist(sqlist L,datatype X) /*在順序表 L 中查找第一值等于 X 的結(jié)點(diǎn)。若找到回傳該結(jié)點(diǎn)序號(hào)；否則回傳 0*/ {________; while((i≤L.last) if(__i=1 i

6、next=NULL; return(t); } 24.以下為求單鏈表表長(zhǎng)的運(yùn)算，分析算法，請(qǐng)?jiān)?________處填上正確的語(yǔ)句。 int length_lklist(lklist head) /*求表 head 的長(zhǎng)度*/ {p=head; j=0; while(p->next!=NULL) {p=p->next; j++; } return(j);

7、 /*回傳表長(zhǎng)*/ } 25.以下為單鏈表按序號(hào)查找的運(yùn)算，分析算法，請(qǐng)?jiān)赺___處填上正確的語(yǔ)句。 pointer find_lklist(lklist head,int i) { p=head;j=0; while((p->next!=NULL) j++; } 3 . ② 求表長(zhǎng) LENGTH(L)，引用型運(yùn)算，其結(jié)果是線性表 L 的長(zhǎng)度 ③讀表元 GET(L,i), 引用型運(yùn)算。若 1data 是一個(gè)數(shù)據(jù)元素，p

8、->next 的值是一個(gè)指針 11.單鏈表的一個(gè)存儲(chǔ)結(jié)點(diǎn)包含 （ 4 ） ①數(shù)據(jù)域或指針域 ②指針域或鏈域 ③指針域和鏈域 ④數(shù)據(jù)域和鏈域 12.對(duì)于單鏈表表示法，以下說(shuō)法錯(cuò)誤的是 （ 3 ） ①數(shù)據(jù)域用于存儲(chǔ)線性表的一個(gè)數(shù)據(jù)元素 ②指針域或鏈域用于存放一個(gè)指向本結(jié)點(diǎn)所含數(shù)據(jù)元素的直接后繼所在結(jié)點(diǎn)的指針 ③所有數(shù)據(jù)通過(guò)指針的鏈接而組織成單鏈表 ④NULL 稱(chēng)為空指針，它不指向任何

9、結(jié)點(diǎn)，只起標(biāo)志作用 13.對(duì)于單鏈表表示法，以下說(shuō)法錯(cuò)誤的是 （ 5 ） ①指向鏈表的第一個(gè)結(jié)點(diǎn)的指針，稱(chēng)為頭指針 ②單鏈表的每一個(gè)結(jié)點(diǎn)都被一個(gè)指針?biāo)?③任何結(jié)點(diǎn)只能通過(guò)指向它的指針才能引用 ④終端結(jié)點(diǎn)的指針域就為 NULL ⑤尾指針變量具標(biāo)識(shí)單鏈表的作用，故常用尾指針變量來(lái)命名單鏈表 14．有時(shí)為了敘述方便，可以對(duì)一些概念進(jìn)行簡(jiǎn)稱(chēng)，以下說(shuō)法錯(cuò)誤的是 （ 4 ） ①將“指針型變量”簡(jiǎn)稱(chēng)為“指針”

10、 ②將“頭指針變量”稱(chēng)為“頭指針” ③將“修改某指針型變量的值”稱(chēng)為“修改某指針” ④將“p 中指針?biāo)附Y(jié)點(diǎn)”稱(chēng)為“P 值” 15．設(shè)指針 P 指向雙鏈表的某一結(jié)點(diǎn)，則雙鏈表結(jié)構(gòu)的對(duì)稱(chēng)性可用（ 3 ）式來(lái)刻畫(huà) ①p->prior->next->==p->next->next ②p->prior->prior->==p->next->prior ③p->prior-

11、>next->==p->next->prior ④p->next->next==p->prior->prior 16.以下說(shuō)法錯(cuò)誤的是 （ 1 ） ①對(duì)循環(huán)鏈表來(lái)說(shuō)，從表中任一結(jié)點(diǎn)出發(fā)都能通過(guò)前后操作而掃描整個(gè)循環(huán)鏈表 ②對(duì)單鏈表來(lái)說(shuō)，只有從頭結(jié)點(diǎn)開(kāi)始才能掃描表中全部結(jié)點(diǎn) ③雙鏈表的特點(diǎn)是找結(jié)點(diǎn)的前趨和后繼都很容易 ④對(duì)雙鏈表來(lái)說(shuō)，結(jié)點(diǎn)*P 的存儲(chǔ)位置