順序表、鏈表題庫

1、第三章 順序表一、填空1若線性表最常用的操作是存取第 i 個元素及其前驅元素的值，則采用（ ）存儲結構最節(jié)省運算時間。2順序存儲結構的線性表中所有元素的地址（ ）連續(xù)。 3順序存儲結構的線性表其物理結構與邏輯結構是（ ）的。4在具有n個元素的順序存儲結構的線性表任意一個位置中插入一個元素，在等概率條件下，平均需要移動（ ）個元素。5在具有n個元素的順序存儲結構的線性表任意一個位置中刪除一個元素，在等概率條件下，平均需要移動（ ）個元素。6在具有n個元素的順序存儲結構的線性表中查找某個元素，平均需要比較（ ）次。7當線性表的元素基本穩(wěn)定，且很少進行插入和刪除操作，但要求以最快的速度存取線性表中第

2、i個元素時，應采用( )存儲結構。8順序存儲結構的線性表中，插入或刪除某個元素時，元素移動的次數(shù)與其位置（ ）關。（填有或無）。9順序存儲結構的線性表中，訪問第i個元素與其位置（ ）關。（填有或無）。10在具有n個元素的順序存儲結構的線性表中要訪問第i個元素的時間復雜度是（ ）。11在順序表L中的i個位置插入某個元素x，正常插入時，i位置以及i位置以后的元素需要后移，首先后移的是（ ）個元素。12要刪除順序表L中的i位置的元素x，正常刪除時，i位置以后的元素需要前移，首先前移的是（ ）元素。13若順序表中的元素是從1位置開始存放的，要在具有n個元素的順序表中插入一個元素，合法的插入位置是（ ）

3、。14若順序表中的元素是從1位置開始存放的，要刪除具有n個元素的順序表中某個元素，合法的刪除位置是（ ）。15在具有n個元素的順序存儲結構的線性表中刪除某個元素的時間復雜度是（ ）。16在具有n個元素的順序存儲結構的線性表中插入某個元素的時間復雜度是（ ）。17在具有n個元素的順序存儲結構的線性表中要訪問第i個元素的后繼結點的時間復雜度是（ ）。18在具有n個元素的順序存儲結構的線性表中，若給定的是某個元素的關鍵字值，要訪問該元素的其它信息的時間復雜度是（ ）。19在順序表中查找某個元素時，需要將當前元素與要找的元素進行若干次的比較，算法經(jīng)常用while循環(huán)來實現(xiàn)，while里面的條件是沒找完

4、且（ ）。20在順序表中查找某個元素時，需要將當前元素與要找的元素進行若干次的比較，算法經(jīng)常用while循環(huán)來實現(xiàn)，while里面的條件是（ ）且沒找到。21如果要將兩個升序排列的整型順序表a中的元素合并到b中（b的空間足夠大），合并后表中元素依然升序排列，可以通過多次調用查找函數(shù)查找插入位置，再調用（ ）函數(shù)來實現(xiàn)插入。22若要將一個整型的順序表拆分為一個存放正數(shù)，另一個存放非正數(shù)的兩個順序表，存放正數(shù)的順序表用原來的表，時間復雜度為（ ）。23順序表中查找某個元素時，從前到后查找與從后到前查找的時間復雜度（ ）同。二、簡答題1.下列算法完成在順序表SeqL的第i個位置插入元素x，正常插入返

5、回1，否則返回0或-1，請在空的下劃線上填寫合適的內容完成該算法。/表中最多可以放置MAXLEN個元素int seq_ins(SeqList *SeqL,int i, DataType x) int j; if ( ) /*表滿*/ printf(the list is fulln); return 0; else if (i SeqL-len+1) /*位置不對*/ printf(the position is invalidn ); return -1; else /*正常插入*/ for (j=SeqL-len;j=i;j-) /*元素后移*/ /*插入元素*/ (SeqL-len)+;

6、 /*表長加1*/ 2.下列算法完成刪除順序表SeqL的第i個元素，元素類型為DataType，其值通過參數(shù)px返回，請在空的下劃線上填寫合適的內容完成該算法。 int seq_del (SeqList * SeqL,int i， ) int j ; if （SeqL-len=0) /*表空*/ printf(the list is emptyn);return 0; elseif( ) /*位置不對*/ printf(n the position is invalid); return -1; else /*正常刪除*/ *px=SeqL-datai; /*刪除元素通過參數(shù)px 返回*/ f

7、or (j=i+1;jlen;j+) ; /*元素前移*/ ; /*表長減1*/ return 1; 3.簡述什么是順序存儲結構，順序存儲結構的優(yōu)缺點都有哪些。4. 設有一整型順序表L，元素從位置1開始存放，下列算法實現(xiàn)將以第一個元素為基準，將其放置在表中合適的位置，使得其前面的元素都比它小，后面的元素均大于等于該元素。請在空的下劃線上填寫合適的內容完成該算法。void part(SeqList *L) ; /*循環(huán)變量聲明*/ int x; ; /*將第一個元素置入x中*/ for(i=2;ilen;i+) if( ) /*當前元素小于基準元素*/ L-data0=L-datai; /*當前

8、元素暫存在0位置*/ for(j=i-1;j=1;j-) /*當前元素前面所有元素后移*/ L-dataj+1=L-dataj; /*當前元素從0位置移到最前面*/ 5. 設有一整型順序表L，元素從位置1開始存放，下列算法實現(xiàn)將以第一個元素為基準，將其放置在表中合適的位置，使得其前面的元素都比它小，后面的元素均大于等于該元素。請在空的下劃線上填寫合適的內容完成該算法。void part(SeqList *L) int i,j; i=1; /*i指向第一個位置*/j=L-len; /*j指向最后一個位置*/ L-data0= L-data 1; /*將基準元素暫存在0位置*/ while( )

9、while(L-data j= L-data 0)&(ij) j-; /*j位置元素大于基準元素且ij 時j前移*/ if (idata i= L-data j;i+; while(L-data idata 0)&(ij) i+;/*i位置元素小于基準元素且ij 時i后移*/ if (inext=HL-next及( )操作。14設指針變量p指向單鏈表中某結點A，則刪除結點A的后繼結點需要的操作為（ ）（不考慮存儲空間的釋放）。15在單鏈表中，若給定某個結點的指針，要刪除該結點的后繼結點的時間復雜度為（ ）。16統(tǒng)計單鏈表中元素個數(shù)的時間復雜度是（ ）。17要訪問具有n個結點的單鏈表中任意一個結

10、點的時間復雜度是（ ）。18鏈式存儲結構的線性表中，插入或刪除某個元素所需的時間與其位置（ ）關。（填有或無）。19在單鏈表中，若給定某個結點的數(shù)據(jù)信息，要刪除該結點的后繼結點的時間復雜度為（ ）。20若指針p,q的值相同，則*p和*q的值（ ）相同。21若要將一個單鏈表中的元素倒置，可以借助（ ）建立單鏈表的思想將鏈表中的結點重新放置。22線性表用鏈式存儲結構存儲比用順序存儲結構存儲所占的存儲空間（ ）多。（填一定或不一定）二、簡答題1下列算法完成用頭插法為數(shù)組a中的n個元素建立一個帶頭結點的單鏈表，并返回其頭指針，請在空的下劃線上填寫合適的內容完成該算法。NodeType* creatl2

11、 (DataType a,int n) NodeType*head, *s； int i；head=(NodeType*)malloc(sizeof(NodeType)； /*為頭結點申請空間*/if (head=NULL) return NULL; ; /*鏈表初始化為空*/ for (i=1；inext=head-next； /*新結點的指針域指向頭的下一個元素*/ ; /*頭結點指向新結點*/ ; /*返回頭指針*/ 2.下列算法完成用尾接法為數(shù)組a中的n個元素建立一個帶頭結點的單鏈表，并返回其頭指針，請在空的下劃線上填寫合適的內容完成該算法。NodeType* creatl1(Data

12、Type a,int n) NodeType *head,*tail,*s; /* head為頭指針， tail為尾指針*/ int i; head=initl( ); /*鏈表初始化*/ if (head=NULL) return NULL; ; /*尾指針初始化為頭指針*/ for (i=0;inext=NULL; / *給新結點的指針域賦值*/ tail-next=s; /*將新結點接到表尾*/ ; /*新結點為當前的表尾*/ return head; /*返回頭指針*/ 3. 簡述什么是鏈式存儲結構，鏈式存儲結構的優(yōu)缺點有哪些。4. 請解釋：結點，頭結點，頭指針，首元結點。5. 已知整

13、型帶頭結點的單鏈表H，下列算法實現(xiàn)將該鏈表中的元素倒置，若原鏈表中的元素為1，2，3，4，5； 倒置后在則變成5，4，3，2，1. 請在空的下劃線上填寫合適的內容完成該算法。void reverse ( ) NodeType*p; p=H- next; /*p指向首元結點*/ H-next=NULL; /*頭結點的指針域為空*/ while( ) /*當p結點不為空時*/ q=p; p=p-next; /*p指針后移*/ /*將q所指向的結點插入到頭結點之后*/ 三、算法設計1.設單鏈表的結點類型定義如下：typedef struct node int data； struct node *n

14、ext；NodeType；設計一算法在帶頭結點的單鏈表L中查找元素x，若找到，則返回其位置；否則返回一個空位置。2.設單鏈表的結點類型定義如下：typedef struct node int data； struct node *next；NodeType；設計一算法查找?guī)ь^結點的單鏈表L中第i個元素，若找到，則返回其位置；否則返回一個空位置。3.設單鏈表的結點類型定義如下：typedef struct node int data； struct node *next；NodeType；設計一算法求帶頭結點的單鏈表L的長度。4.設單鏈表的結點類型定義如下：typedef struct node

15、 int data； struct node *next；NodeType；設計一算法統(tǒng)計帶頭結點的單鏈表L中元素x的個數(shù)。5.設單鏈表的結點類型定義如下：typedef struct node int data； struct node *next；NodeType；設計一算法在帶頭結點的單鏈表L中查找元素x的前驅結點，若找到，則返回其位置；否則返回一個空位置。6.設單鏈表的結點類型定義如下：typedef struct node int data； struct node *next；NodeType；設計一算法在帶頭結點的單鏈表L中，將新元素x插入到帶頭結點的單鏈表L中的元素elm之后，若不存在元素elm，則插入到最后。7.設單鏈表的結點類型定義如下：typedef struct node int data； struct node *next；NodeType；設計一算法刪除帶頭結點的單鏈表L中的元素x（元素x只有一個）。8.設單鏈表的結點類型定義如下：typedef struct node int data； struct node *next；NodeType；設計一算法刪除帶頭結點的單鏈表L中所有的元素x(元素x可能有多個)。9. 設有一整型的帶頭結點的單鏈表，其元素值升序排列，請定義結點的類型并設計一算法實現(xiàn)：任意給定一個元素x將其插入到該表中，使得該鏈表中的數(shù)