數據結構復習資料

1、 1 第二章 線性表 二、填空題 1.為了便于討論，有時將含 n(n>=0)個結點的線性結構表示成(a1，a2,??an)，其中每個 ai 代表一個結點。a1 稱為起始結點，an 稱為終端結點， i 稱為 ai在線性表中的位置或序號。 對任意一對相鄰結點 ai、 ai┼1(1=1)個內存單元， 其中， b 是順序表的第一個存儲結點的第一個單元的內存地址，那么，第 i 個結點 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 來說， 若以結點移動為標準操作， 則插入算法的最壞時間復雜性為___n_____， 量級是__O(n)_。插入算法的平均時間復雜性為 n/2，平均時間復雜性量級是 O(n)。 12.以下為順序表的刪除運算，分析算法，請在________處填上正確的語句。 void delete_sqlist(sqlist

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

5、n)______,其平均時間復雜性及其量級分別為__(n-1)/2______和__O(n)______。 14.以下為順序表的定位運算，分析算法，請在________處填上正確的語句。 int locate_sqlist(sqlist L,datatype X) /*在順序表 L 中查找第一值等于 X 的結點。若找到回傳該結點序號；否則回傳 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)，引用型運算，其結果是線性表 L 的長度 ③讀表元 GET(L,i), 引用型運算。若 1data 是一個數據元素，p

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

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

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