順序表、鏈表題庫

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

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

3、素,合法的插入位宜是（）»14. 若順序表中的元素是從1位置開始存放的，要刪除具有n個元素的順序表中某個元素，合法的刪除位置是（）<>15. 在具有n個元素的順序存儲結(jié)構(gòu)的線性表中刪除某個元素的時間復(fù)雜度是（）。16. 在具有n個元素的順序存儲結(jié)構(gòu)的線性表中插入某個元素的時間復(fù)雜度是（）。17. 在具有n個元素的順序存儲結(jié)構(gòu)的線性表中要訪問第i個元素的后繼結(jié)點的時間復(fù)雜度是（）。18. 在具有n個元素的順序存儲結(jié)構(gòu)的線性表中，若給定的是某個元素的關(guān)鍵字值，要訪問該元素的其它信息的時間復(fù)雜度是（）-19. 在順序表中査找某個元素時，需要將當(dāng)前元素與要找的元素進(jìn)行若干次的比較

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

5、題1. 下列算法完成在順序表SeqL的第i個位苣插入元素x,正常插入返回1,否則返回0或-1, 請在空的下劃線上填寫合適的內(nèi)容完成該算法。列算法完成刪除順序表SeqL的第i個元素，元素類型為DataType,英值通過參數(shù)px返回, 請在空的下劃線上填寫合適的內(nèi)容完成該算法。int seq_del (SeqList * SeqL, int i, ) int j ;if (SeqL->len=O)/* 表空*/；、printf C'the list is emptyn?z) ;return 0;elseif()/* 位巻不對*/:、printf(z，n the position is

6、 invalid"); return T;else/*正常刪除*/ *px二SeqL->datai;/*刪除元素通過參數(shù)px返回*/for (j=i+l;j<=SeqL->len;j+) ;/*元素前移*/;/*表長減1*/return 1;3. 簡述什么是順序存儲結(jié)構(gòu)，順序存儲結(jié)構(gòu)的優(yōu)缺點都有哪些。4. 設(shè)有一整型順序表L,元素從位置1開始存放，下列算法實現(xiàn)將以第一個元素為基準(zhǔn)， 將其放置在表中合適的位置，使得英前而的元素都比它小，后而的元素均大于等于該元素。 請在空的下劃線上填寫合適的內(nèi)容完成該算法。void part(SeqList *L)int x;/*循環(huán)

7、變量聲明*/*將第一個元素宜入只中*/for(i=2;i<=L->len;i+)辻() L->data0=L->data i;for(j=i-l; j>=l; j)/*當(dāng)前元素小于基準(zhǔn)元素*/*當(dāng)前元素暫存在0位置*/*當(dāng)前元素前而所有元素后移*/L->data j+1 =L->data L j; /*當(dāng)前元素從0位置移到最前而*/5. 設(shè)有一整型順序表L,元素從位宜1開始存放，下列算法實現(xiàn)將以第一個元素為基準(zhǔn),將其放置在表中合適的位置，使得英前而的元素都比它小，后而的元素均大于等于該元素。 請在空的下劃線上填寫合適的內(nèi)容完成該算法。void part

8、(SeqList *L) int i, j；i二1;/*i指向第一個位It*/j=L->len;/*j指向最后一個位置*/L-dataO二L->data 1;/*將基準(zhǔn)元素暫存在0位置*/while ()_ while(L->data j>= L->data 0：)&&(i<j) j; /*j 位置元素大于基準(zhǔn)元素且 i<j 時j前移*/if (i<j) L>data i二 L->data j;i+；while(L->data i<= L->data 0)&&(i<j) i+;/

9、*i 位置元素小于基準(zhǔn)元素且 i<j 時i后移*/if (i<j) /*將基準(zhǔn)元素放在i位置*/四、完整程序設(shè)計1.在順序存儲結(jié)構(gòu)的職工工資表中，職工工資信息包括：職工號（no）、姓需（name）、職 稱（pro）、工資（sal）等四項信息，請編寫一完整的程序，實現(xiàn)以下功能：（1）創(chuàng)建信息表：從鍵盤讀入所有職工的信息。（3分）（2）刪除：給泄職工號，刪除該職工的信息。（6分）（3）修改：對職稱為“教授”的職工工資加100。（4分）（4）在顯示器（屏幕）上顯示所有職工的各項信息。（3分）（5）主程序以菜單的方式調(diào)用以上功能。（4分）元素類型及順序表類型左義如下：typedef str

10、uct char no8, name10, pro6;float sal； '：DataType;typedef struct DataType dataMAXLEN+l：int len;；SeqList;2. 圖書管每本圖書包含：書號（no）、書名（name）、現(xiàn)存疑（newnum）、總庫存量（sumnum）、 單價五項信息，編寫完整程序通過順序表實現(xiàn)：（1）初始化：錄入現(xiàn)有的所有圖書的五項信息。（3分）（2）借書：每本書每次只能借一本，如果庫中有該書，則允許借閱并使該書的現(xiàn)存量減1,否則給出相應(yīng)提示信息。（4分）（3）-價值估算：統(tǒng)計庫中所有書的價錢。價錢為所有書的單價乘以庫存量的

11、累加和。（4分）（5）顯示：顯示圖書管所有藏書信息。（3分）（6）主程序以菜單的方式調(diào)用以上功能。（4分）元素類型及順序表類型定義2分。3. 設(shè)有兩個整型順序表Lb L2,其元素值遞增有序存放，請定義該順序表的元素類型及表類型（2分）：設(shè)計以下自泄義函數(shù)：（1）錄入順序表中所有元素的值。（3分）（2）將順序表LI, L2合并為到列外一個順序表L3中，L3中的元素非遞減有序排列。（8分）（3）輸出順序表中元素的值。（3分）主函數(shù)通過調(diào)用以上函數(shù)實現(xiàn)兩個表的合并并顯示合并結(jié)果。（4分）4. 有一個職工基本信息管理，職工信息包含：職工號、姓名、性別；編寫完整程序，實現(xiàn)如 下功能：（1）錄入函數(shù)inp

12、ut:從鍵盤讀入職工信息。（3分）（2）刪除函數(shù)delete：給左職工號,刪除該職工的信息。（5分）（3）插入函數(shù)insert：假泄表中職工信息按職工號升序排列，任意給左一職工信息，使得插入后依然有序。（6分）主函數(shù)以菜單形式調(diào)用以上功能，類型左義2分，主函數(shù)4分。5. 有一個學(xué)生信息包含：學(xué)號no主關(guān)鍵字：姓名name；英語成績score.立義學(xué)生信 息類型DataType及順序表類型SeqList;（1）錄入函數(shù)input：從鍵盤讀入學(xué)生信息。（3分）（2）查找函數(shù)search：任意給左一個學(xué)號，查找其英語成績，將苴成績通過函數(shù)返回，若 找不到，返回-1。（5分）（3）插入函數(shù)insert

13、：假左表中學(xué)生信息按學(xué)號升序排列，任意給左一學(xué)生信息，使得插入后依然有序。（6分）主函數(shù)以菜單形式調(diào)用以上功能，類型圮義2分，主函數(shù)4分。6. 設(shè)有一個超市的庫存情況如下表1所示：表1超市商品信息商品編號商品名稱價格庫存量作業(yè)本20鉛筆10鋼筆30t鉛筆刀105編寫完整程序?qū)崿F(xiàn)：（1）從鍵盤輸入貨物信息并將其放在順序表中。（4分）。（2）假泄商品信息按貨號升序存放，任意插入一商品信息，要求按貨號有序插入到表中。（6分）（3）任意給泄一個商品編號，査找其商品名稱、價格和庫存量，如果存在該商品輸岀并返回1，否則返回0。（4分）主函數(shù)以菜單形式調(diào)用以上功能，類型左義2分，主函數(shù)4分。7. 有一個房產(chǎn)

14、信息管理系統(tǒng)，房產(chǎn)信息包含：門牌號、戶主、電話號碼、而積。編程實現(xiàn)如 下功能（要求用順序表存儲）：（1）編寫一個初始化函數(shù)input:從鍵盤讀入房產(chǎn)基本信息。（3分）（2）編寫一個取曖費用計算函數(shù)cost:任意給左一門牌號，根據(jù)門牌號進(jìn)行查詢，找到 時，返回應(yīng)繳納取曖費，否則返回0,并且給岀提示信息。計算公式為：每戶應(yīng)繳納費用二 而積*元/m'。（4分）（3）編寫一排序函數(shù)sort：按門牌號升序排列。（4分）（4）編寫一個函數(shù)output:輸出所有面積低于90平方米住戶的名稱。（3分）主函數(shù)以菜單形式調(diào)用以上功能，類型左義2分，主函數(shù)4分。8. 有一個學(xué)生信息包含：學(xué)號no主關(guān)鍵字：姓

15、軻name：英語成績english,計算機(jī)成 績comp,數(shù)學(xué)成績math。定義學(xué)生信息類型DataType及順序表類型SeqList;Z（1）錄入基本信息函數(shù)input:從鍵盤讀入學(xué)生姓名、學(xué)號。（3分）（2）錄入成績inp_score：給泄課程名稱，錄入所有人本門課的成績。（3分）（3）刪除函數(shù)del：假迫表中學(xué)生信息學(xué)號升序排列，任意給上一學(xué)生學(xué)號，刪除該學(xué)生 信息，正常刪除返回1,否則返回0。（6分）（4）輸岀函數(shù)output:輸出所有人的信息。（2分）主函數(shù)以菜單形式凋用以上功能，類型左義2分，主函數(shù)4分。9. 設(shè)有一個商品信息表（包括商品編號no、商品名稱name、商品庫存M co

16、unt和商品單價 price）編程實現(xiàn)以下功能：（1）貨物信息錄入：按貨號有序輸入學(xué)生信息。（3分）（2）進(jìn)貨管理：任意輸入一個貨物信息，在表中查找該貨物，若存在此貨物，則將該貨 物的數(shù)量加到表中貨物數(shù)量中：若不存在該貨物，則將該貨物信息按照貨物號有序 插入到表中。（10分）（3）貨物信息輸出:輸出所有貨物的信息。（2分）主函數(shù)以菜單形式調(diào)用以上功能，類型左義2分，主函數(shù)3分。10. 設(shè)有一個商品信息表（包括商品編號no、商品名稱name、商品庫存量count和商品單 價 price）編程實現(xiàn)以下功能：（1）貨物信息錄入：按貨號有序輸入貨物信息。（3分）（2）出貨管理：函數(shù)返回值為購買該貨物的

17、金額。任意輸入一個貨物信息X,在表中查找 該貨物，若存在此貨物且?guī)齑媪看笥诘扔趚的數(shù)量，則將表中貨物的庫存量減去x的數(shù)量, 計算出需支付的金額并返回；若庫存量不足，則給岀相應(yīng)的提示并返回0。若不存在該貨物, 返回-1。（10分）（3）貨物信息輸出:輸岀所有貨物的信息。（2分）主函數(shù)以菜單形式調(diào)用以上功能，類型左義2分，主函數(shù)3分。11. 有一自來水公司水費繳費系統(tǒng)中，數(shù)據(jù)信息包括：用戶爼稱、編號、用水量、水費、繳費情況（繳淸，未繳），請立義用戶信息數(shù)據(jù)類型及順序表類型并設(shè)汁如下函數(shù)：函數(shù)1：輸入所有用戶的名稱，編號，用水雖:，用戶冬為”作為結(jié)束符。每個用戶的 水費通過公式：水費二用水雖：*汁算

18、得出。用戶的繳費情況都設(shè)為未繳。（4分）函數(shù)2：輸入用戶編號，査找到該用戶信息并將該用戶的繳費情況都設(shè)為繳淸。（4分）函數(shù)3：設(shè)計一個排序函數(shù)，將元素信息按編號有序排列。（4分）函數(shù)4：輸出所有的未繳費的用戶名稱。（3分）主函數(shù)以菜單形式調(diào)用以上功能，類型立義2分，主函數(shù)3分。12. 設(shè)有一個超市商品信息表（包括商品編號no、商品名稱name、商品庫存M amount和商 品單價price）編程實現(xiàn)以下功能：（1）貨物信息錄入：輸入一批貨物信息，貨號為“000”時結(jié)束。（3分）（2）購物管理：輸入若干貨物貨號、數(shù)量（即客戶所購買的貨物信息），貨號為“000”時 結(jié)朿，輸出所購買的每個貨物貨號、

19、名稱、數(shù)量、單價、金額（單價通過査找得到，金額二 單價X數(shù)量）：最后輸出總的價格。（10分）（3）貨物信息輸出:輸出所有貨物的信息。（2分）主函數(shù)以菜單形式調(diào)用以上功能，類型迫義2分，主函數(shù)3分。13. 有一學(xué)生成績信息包括：姓名、學(xué)號、成績、塔次；編程實現(xiàn)以下功能：（1）輸入所有人姓名、學(xué)號、成績，務(wù)次初始化為0。（3分）（2）給左一學(xué)生學(xué)號，輸出英成績，若不存在該學(xué)號，給出相應(yīng)的錯誤提示。（4分）（3）將學(xué)生信息按成績由髙到低排序，并將其名次存入該學(xué)生信息的'你次”中。（6分）（4）輸岀所有學(xué)生的信息。（2分）主函數(shù)以菜單形式調(diào)用以上功能，類型立義2分，主函數(shù)3分。14. 學(xué)生考勤

20、管理。學(xué)生信息包括：姓名、學(xué)號、考勤情況（遲到、曠課、按時上課，成績及本次已經(jīng)是第幾次考勤。每個人有20次考勒：編程實現(xiàn)以下功能：I（1）學(xué)生基本信息錄入及初始化：輸入所有學(xué)生的姓需、學(xué)號，將每個人的考勤成績置0, 將考勒次數(shù)也豊0。（3分）（2）輸入考勒情況：每次上課，輸入本次考勒，從第一個人開始，依次輸入每個人的考勤。（4分）（3）計算考勒成績:遲到得分，曠課得0分，正常上課得1分，計算每個人的考勤成績。（5 分）（4）輸岀所有人的學(xué)號、姓名、考勤情況、考勤成績。（3分）主函數(shù)以菜單形式凋用以上功能，類型左義2分，主函數(shù)3分。元素類型立義如下：typedef struct char nam

21、e 10;/*name 表示學(xué)生姓名*/char no 12;/*no 表示學(xué)號*/char kaoqin21 ; /*kaoqin表示20次的考勤，q缺課，c遲到，z按時上課*/int k; /*k表示已經(jīng)考勤到第幾次，初始化時將其宜為-1*/int score; /*score表示考勤成績*/:DataTe;若有DataType x,則x. kaoqin2表示x的第三次考勤。15. 有一個職工基本信息管理，職工信息包含：職工號、姓劃、工資；編寫完整程序，實現(xiàn) 如下功能：（1）錄入函數(shù)input:從鍵盤讀入職工信息。（3分）（2）修改函數(shù)modify：給左職工號，查找該職工，若找到修改其信息

22、，若找不到，給出錯 誤提示。（4分）（3）插入函數(shù)insert：假泄表中職工信息按職工號升序排列，任意給左一職工信息，使 得插入后依然有序。（6分）（4）輸岀函數(shù)output:輸出所有人的信息。（2分）主函數(shù)以菜單形式調(diào)用以上功能，類型左義2分，主函數(shù)3分。16. 有一個學(xué)生成績管理，學(xué)生信息包含：學(xué)號、姓名、成績：編寫完整程序，實現(xiàn)如下功 能：（1）錄入函數(shù)input:從鍵盤讀入學(xué)生信息。（3分）（2）修改函數(shù)modify：給左學(xué)號，查找該學(xué)生，若找到修改其成績，若找不到，給出錯誤 提示。（4分）（3）排序函數(shù)sort：將學(xué)生信息按成績由髙到低排序。（6分）（4）輸出函數(shù)output:輸出所

23、有人的信息。（2分）主函數(shù)以菜單形式調(diào)用以上功能，類型左義2分，主函數(shù)3分。17. 圖書管每本圖書包含：書號（no）、書名（name）、現(xiàn)存量（newnum）、總庫存量（sumnum） 四項信息，編寫完整程序通過順序表實現(xiàn)：（1）初始化：錄入現(xiàn)有的所有圖書的四項信息。（3分）（2）淸庫：給定某書x的書號及數(shù)量，若找到該書，將該書的現(xiàn)存量及庫存量減去x的數(shù) 量，若減后的庫存量為0,則刪除該書信息；若找不到該書，則給岀錯誤提示。（9分）（3）-顯示：顯示圖書管所有藏書信息。（2分）（5）主程序以菜單的方式調(diào)用以上功能。（4分）元素類型及順序表類型宦義（2分）18. 圖書管每本圖書包含：書號（no）

24、、書名（name）、現(xiàn)存疑（newnum）、總庫存疑（sumnum） 四項信息，編寫完整程序通過順序表實現(xiàn)：（1）初始化：錄入現(xiàn)有的所有圖書的四項信息。（3分）（2）檢索：給定書名，輸岀所有與給泄書名相同的書的信息。（3分）（3）價值估算：統(tǒng)il庫中所有書的價錢。價錢為所有書的單價乘以庫存量的累加和。（6 分）（4）顯示：顯示圖書管所有藏書信息。（2分）（5）主程序以菜單的方式調(diào)用以上功能。（4分）（6）y完成元素類型左義及順序表類型泄義（2分）。19. 圖書管每本圖書包含：書號（no）、書名（name）、現(xiàn)存量（newnum）、總庫存量（sumnum） 四項信息，編寫完整程序通過順序表實現(xiàn)：

25、（1）初始化：錄入現(xiàn)有的所有圖書的四項信息。（3分）（2）查找：給立書號，在表中查找該書，若存在返回其位宜，否則返回0。（4分）（3）進(jìn)書：給泄某個圖書的書名、書號、數(shù)量，若此次購進(jìn)的是圖書館已有的圖書，則 修改其現(xiàn)存量和總庫存量；若此次購進(jìn)的圖書是新書，按書號有序插入到表中。（假 定表中元素按書號升序排列）（7分）（4）主程序以菜單的方式調(diào)用以上功能。（4分）（5）完成元素類型上義及順序表類型是義（2分）。20. 學(xué)生學(xué)費管理。學(xué)生信息包括：姓名、學(xué)號、學(xué)費.已繳學(xué)費、欠費。編寫完整程序通 過順序表實現(xiàn)：（1）初始化：錄入所有人的姓劃、學(xué)號、學(xué)費。（3分）（2） 繳費：輸入學(xué)號及已繳學(xué)費，欠

26、費二學(xué)費-已繳學(xué)費。（5分）（4）催繳學(xué)費：對欠費為正數(shù)的人，輸岀其姓劍、學(xué)號、欠費并統(tǒng)計所有人的欠費總數(shù),總的欠費數(shù)目以函數(shù)值的形式返回（6分）（5）主程序以菜單的方式調(diào)用以上功能。（4分）（6）完成元素類型泄義及順序表類型左義（2分）。第四章鏈表一、填空1. 鏈?zhǔn)酱鎯Y(jié)構(gòu)的線性表中所有元素的地址（）連續(xù)。2. 單鏈表中增加頭結(jié)點的目的是為了（）。3用單鏈表存儲線性表，每個結(jié)點需要兩個域，一個是數(shù)據(jù)域，另一個是（）。4. 用單鏈表存儲線性表，每個結(jié)點需要兩個域，一個是（）,另一個是指針域。）域來表示的。5. 鏈?zhǔn)酱鎯Y(jié)構(gòu)的線性表其元素之間的邏輯關(guān)系是通過結(jié)點的（6. 指針為空表示該指針?biāo)赶?/p>

27、的結(jié)點（7. 某帶頭結(jié)點的單鏈表的頭指針為head,判立該鏈表為非空的條件是（）。8.某帶頭結(jié)點的單鏈表的頭指針為head,判龍該鏈表為空的條件是（9. 在單鏈表1中指針P所指的結(jié)點為尾結(jié)點的條件是（）。10. 在單鏈表L中，指針P所指的結(jié)點有后繼結(jié)點的條件是（）。11頭插法建立單鏈表時，元素的輸入順序與在鏈表中的邏輯順序是（）的。12. 尾接法建立單鏈表時，元素的輸入順序與在鏈表中的邏輯順序是（）的。13. 在帶有頭結(jié)點的單鏈表HL中，要在首元元素之前插入一個由指針p指向的結(jié)點，則應(yīng)執(zhí)行 p->next=HL->next 及(）操作。14設(shè)指針變量p指向單鏈表中某結(jié)點A,則刪除結(jié)

28、點A的后繼結(jié)點需要的操作為（）（不考慮存儲空間的釋放九15 在單鏈表中，若給左某個結(jié)點的指針要刪除該結(jié)點的后繼結(jié)點的時間復(fù)雜度為（）o16. 統(tǒng)計單鏈表中元素個數(shù)的時間復(fù)雜度是()。17. 要訪問具有n個結(jié)點的單鏈表中任意一個結(jié)點的時間復(fù)雜度是()。18. 鏈?zhǔn)酱鎯Y(jié)構(gòu)的線性表中，插入或刪除某個元素所需的時間與其位置()關(guān)。(填有 或無)。19. 在單鏈表中，若給泄某個結(jié)點的數(shù)據(jù)信息，要刪除該結(jié)點的后繼結(jié)點的時間復(fù)雜度為 ( )。20. 若指針p,q的值相同，則*戸和*q的值()相同。21. 若要將一個單鏈表中的元素倒宜，可以借助()建立單鏈表的思想將鏈表中的結(jié)點重新放置"22. 線

29、性表用鏈?zhǔn)酱鎯Y(jié)構(gòu)存儲比用順序存儲結(jié)構(gòu)存儲所占的存儲空間()多。(填一定或不一定)二、簡答題1. 下列算法完成用頭插法為數(shù)組a中的n個元素建立一個帶頭結(jié)點的單鏈表，并返回其頭 指針，請在空的下劃線上填寫合適的內(nèi)容完成該算法。NodeType* creatl2 (DataType a, int n) NodeType*head, *s；int i：head= (NodeType*)malloc(sizeof (NodeType):/*為頭結(jié)點申請空間*/if (head二二NULL) return NULL;/*鏈表初始化為空*/for (i=l： i<=n： i+)s二(NodeType

30、*)malloc(sizeof(NodeType):;/*給新結(jié)點的數(shù)據(jù)域賦值*/s->next=head->next:/*新結(jié)點的指針域指向頭的下一個元素*/;/*頭結(jié)點指向新結(jié)點*/;返回頭指針*/2. 下列算法完成用尾接法為數(shù)組a中的n個元素建立一個帶頭結(jié)點的單鏈表，并返回其頭指 針，請在空的下劃線上填寫合適的內(nèi)容完成該算法。INodeType* creatll(DataType a, int n) NodeType *head,*s;/* head 為頭指針，tail 為尾指針*/int i;head二initl ( ) ;/*鏈表初始化*/if (head=NULL) r

31、eturn NULL;/*尾指針初始化為頭指針*/for (i=0;i<n;i+)辻（s二二NULL） return NULL;/*為新結(jié)點申請空間*/ 申諳不到空間，則返回空*/*給新結(jié)點的數(shù)據(jù)域賦值*/s->next=NULL; tail->next=s;/ *給新結(jié)點的指針域賦值*/ /*將新結(jié)點接到表尾*/*新結(jié)點為當(dāng)前的表尾*/返回頭指針*/return head;3. 簡述什么是鏈?zhǔn)酱鎯Y(jié)構(gòu)，鏈?zhǔn)酱鎯Y(jié)構(gòu)的優(yōu)缺點有哪些。4請解釋：結(jié)點，頭結(jié)點，頭指針，首元結(jié)點。5.已知整型帶頭結(jié)點的單鏈表H,下列算法實現(xiàn)將該鏈表中的元素倒宜，若原鏈表中的元 素為1, 2, 3,

32、4, 5；倒置后在則變成5, 4, 3, 2, 1.請在空的下劃線上填寫合適的內(nèi)容 完成該算法。void reverse ( NodeType*p;/*P指向首元結(jié)點*/*頭結(jié)點的指針域為空*/)/*當(dāng)P結(jié)點不為空時*/p二H-> next; "next 二 NULL;while (p=p->next;/*p 指針后移*/*將q所指向的結(jié)點插入到頭結(jié)點之后*/三、算法設(shè)計1. 設(shè)單鏈表的結(jié)點類型左義如下：typedef struct nodeint data：struct node *next：NodeType：設(shè)汁一算法在帶頭結(jié)點的單鏈表L中查找元素x,若找到，則返回其位置；否則返回一個空 位置。2