順序表、鏈表題庫(kù)

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

2、i個(gè)元素時(shí)，應(yīng)采用( )存儲(chǔ)結(jié)構(gòu)。8順序存儲(chǔ)結(jié)構(gòu)的線性表中，插入或刪除某個(gè)元素時(shí)，元素移動(dòng)的次數(shù)與其位置（ ）關(guān)。（填有或無(wú)）。9順序存儲(chǔ)結(jié)構(gòu)的線性表中，訪問(wèn)第i個(gè)元素與其位置（ ）關(guān)。（填有或無(wú)）。10在具有n個(gè)元素的順序存儲(chǔ)結(jié)構(gòu)的線性表中要訪問(wèn)第i個(gè)元素的時(shí)間復(fù)雜度是（ ）。11在順序表L中的i個(gè)位置插入某個(gè)元素x，正常插入時(shí)，i位置以及i位置以后的元素需要后移，首先后移的是（ ）個(gè)元素。12要?jiǎng)h除順序表L中的i位置的元素x，正常刪除時(shí)，i位置以后的元素需要前移，首先前移的是（ ）元素。13若順序表中的元素是從1位置開(kāi)始存放的，要在具有n個(gè)元素的順序表中插入一個(gè)元素，合法的插入位置是（ ）

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

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

5、回1，否則返回0或-1，請(qǐng)?jiān)诳盏南聞澗€上填寫合適的內(nèi)容完成該算法。/表中最多可以放置MAXLEN個(gè)元素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) /*位置不對(duì)*/ printf(the position is invalidn ); return -1; else /*正常插入*/ for (j=SeqL-len;j=i;j-) /*元素后移*/ /*插入元素*/ (SeqL-len)+;

6、 /*表長(zhǎng)加1*/ 2.下列算法完成刪除順序表SeqL的第i個(gè)元素，元素類型為DataType，其值通過(guò)參數(shù)px返回，請(qǐng)?jiān)诳盏南聞澗€上填寫合適的內(nèi)容完成該算法。 int seq_del (SeqList * SeqL,int i， ) int j ; if （SeqL-len=0) /*表空*/ printf(the list is emptyn);return 0; elseif( ) /*位置不對(duì)*/ printf(n the position is invalid); return -1; else /*正常刪除*/ *px=SeqL-datai; /*刪除元素通過(guò)參數(shù)px 返回*/ f

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

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

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

10、點(diǎn)的時(shí)間復(fù)雜度是（ ）。18鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)的線性表中，插入或刪除某個(gè)元素所需的時(shí)間與其位置（ ）關(guān)。（填有或無(wú)）。19在單鏈表中，若給定某個(gè)結(jié)點(diǎn)的數(shù)據(jù)信息，要?jiǎng)h除該結(jié)點(diǎn)的后繼結(jié)點(diǎn)的時(shí)間復(fù)雜度為（ ）。20若指針p,q的值相同，則*p和*q的值（ ）相同。21若要將一個(gè)單鏈表中的元素倒置，可以借助（ ）建立單鏈表的思想將鏈表中的結(jié)點(diǎn)重新放置。22線性表用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)存儲(chǔ)比用順序存儲(chǔ)結(jié)構(gòu)存儲(chǔ)所占的存儲(chǔ)空間（ ）多。（填一定或不一定）二、簡(jiǎn)答題1下列算法完成用頭插法為數(shù)組a中的n個(gè)元素建立一個(gè)帶頭結(jié)點(diǎn)的單鏈表，并返回其頭指針，請(qǐng)?jiān)诳盏南聞澗€上填寫合適的內(nèi)容完成該算法。NodeType* creatl2

11、 (DataType a,int n) NodeType*head, *s； int i；head=(NodeType*)malloc(sizeof(NodeType)； /*為頭結(jié)點(diǎn)申請(qǐng)空間*/if (head=NULL) return NULL; ; /*鏈表初始化為空*/ for (i=1；inext=head-next； /*新結(jié)點(diǎn)的指針域指向頭的下一個(gè)元素*/ ; /*頭結(jié)點(diǎn)指向新結(jié)點(diǎn)*/ ; /*返回頭指針*/ 2.下列算法完成用尾接法為數(shù)組a中的n個(gè)元素建立一個(gè)帶頭結(jié)點(diǎn)的單鏈表，并返回其頭指針，請(qǐng)?jiān)诳盏南聞澗€上填寫合適的內(nèi)容完成該算法。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; / *給新結(jié)點(diǎn)的指針域賦值*/ tail-next=s; /*將新結(jié)點(diǎn)接到表尾*/ ; /*新結(jié)點(diǎn)為當(dāng)前的表尾*/ return head; /*返回頭指針*/ 3. 簡(jiǎn)述什么是鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)，鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)的優(yōu)缺點(diǎn)有哪些。4. 請(qǐng)解釋：結(jié)點(diǎn)，頭結(jié)點(diǎn)，頭指針，首元結(jié)點(diǎn)。5. 已知整

13、型帶頭結(jié)點(diǎn)的單鏈表H，下列算法實(shí)現(xiàn)將該鏈表中的元素倒置，若原鏈表中的元素為1，2，3，4，5； 倒置后在則變成5，4，3，2，1. 請(qǐng)?jiān)诳盏南聞澗€上填寫合適的內(nèi)容完成該算法。void reverse ( ) NodeType*p; p=H- next; /*p指向首元結(jié)點(diǎn)*/ H-next=NULL; /*頭結(jié)點(diǎn)的指針域?yàn)榭?/ while( ) /*當(dāng)p結(jié)點(diǎn)不為空時(shí)*/ q=p; p=p-next; /*p指針后移*/ /*將q所指向的結(jié)點(diǎn)插入到頭結(jié)點(diǎn)之后*/ 三、算法設(shè)計(jì)1.設(shè)單鏈表的結(jié)點(diǎn)類型定義如下：typedef struct node int data； struct node *n

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

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