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

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

2、順序表的插入運算，分析算法，請在______處填上正確的語句。 Void insert_sqlist(sqlist L，datatype x，int i) /*將 X 插入到順序表 L 的第 i-1 個位置*/ { 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.對于順序表的插入算法 insert_sqlist 來說， 若以結(jié)點移動為標準操作， 則插入算法的最壞時間復(fù)雜性為___n_____， 量級是__O(n)_。插入算法的平均時間復(fù)雜性為 n/2，平均時間復(fù)雜性量級是 O(n)。 12.以下為順序表的刪除運算，分析算法，請在________處填上正確的語句。 void delete_sqlist(sqlist

4、 L,int i) /*刪除順序表 L 中的第 i-1 個位置上的結(jié)點*/ {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.對于順序表的刪除算法 delete_sqlist 來說，若以結(jié)點移動為標準操作，最壞情況時間復(fù)雜性及其量級分別是__n-1______和__O(

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

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

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

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

9、結(jié)點，只起標志作用 13.對于單鏈表表示法，以下說法錯誤的是 （ 5 ） ①指向鏈表的第一個結(jié)點的指針，稱為頭指針 ②單鏈表的每一個結(jié)點都被一個指針所指 ③任何結(jié)點只能通過指向它的指針才能引用 ④終端結(jié)點的指針域就為 NULL ⑤尾指針變量具標識單鏈表的作用，故常用尾指針變量來命名單鏈表 14．有時為了敘述方便，可以對一些概念進行簡稱，以下說法錯誤的是 （ 4 ） ①將“指針型變量”簡稱為“指針”

10、 ②將“頭指針變量”稱為“頭指針” ③將“修改某指針型變量的值”稱為“修改某指針” ④將“p 中指針所指結(jié)點”稱為“P 值” 15．設(shè)指針 P 指向雙鏈表的某一結(jié)點，則雙鏈表結(jié)構(gòu)的對稱性可用（ 3 ）式來刻畫 ①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.以下說法錯誤的是 （ 1 ） ①對循環(huán)鏈表來說，從表中任一結(jié)點出發(fā)都能通過前后操作而掃描整個循環(huán)鏈表 ②對單鏈表來說，只有從頭結(jié)點開始才能掃描表中全部結(jié)點 ③雙鏈表的特點是找結(jié)點的前趨和后繼都很容易 ④對雙鏈表來說，結(jié)點*P 的存儲位置