順序表、鏈表題庫(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)行插入和刪除操作，但要求以最快的速度存取線性表中第 i 個(gè)

2、元素時(shí)，應(yīng)采用 ()存儲(chǔ)結(jié)構(gòu)。8順序存儲(chǔ)結(jié)構(gòu)的線性表中， 插入或刪除某個(gè)元素時(shí)，元素移動(dòng)的次數(shù)與其位置 （）關(guān)。（填有或無）。9順序存儲(chǔ)結(jié)構(gòu)的線性表中，訪問第i 個(gè)元素與其位置（）關(guān)。（填有或無）。10在具有 n 個(gè)元素的順序存儲(chǔ)結(jié)構(gòu)的線性表中要訪問第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 位置開始存放的， 要在具有 n 個(gè)元素的順序表中插

3、入一個(gè)元素，合法的插入位置是（）。14若順序表中的元素是從1 位置開始存放的，要?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)的線性表中要訪問第i 個(gè)元素的后繼結(jié)點(diǎn)的時(shí)間復(fù)雜度是（）。18在具有 n 個(gè)元素的順序存儲(chǔ)結(jié)構(gòu)的線性表中，若給定的是某個(gè)元素的關(guān)鍵字值，要訪問該元素的其它信息的時(shí)間復(fù)雜度是（）。19在順序表中查找某個(gè)元素時(shí)， 需要將當(dāng)前元素與要找的元素進(jìn)行若干次的比較，算法經(jīng)常用 w

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

5、列算法完成在順序表SeqL 的第 i 個(gè)位置插入元素x，正常插入返回 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<1|i> SeqL->len+1)/* 位置不對(duì) */printf("the position is invalidn "); return -1;el

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

7、/ printf("n the position is invalid"); return -1;else/* 正常刪除 */*px=SeqL->datai;/* 刪除元素通過參數(shù)px 返回 */for (j=i+1;j<=SeqL->len;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 開始存放，下列算法實(shí)現(xiàn)將以第一個(gè)元素為基準(zhǔn)，將其放置在表中合適的位置，使得其前面的元素都比它小，后面的元素均大于等于該元素。請(qǐng)?jiān)诳盏南聞澗€上填寫合

8、適的內(nèi)容完成該算法。void part(SeqList *L);/* 循環(huán)變量聲明*/.intx;/* 將第一個(gè)元素置入x 中*/for(i=2;i<=L->len;i+)if()/* 當(dāng)前元素小于基準(zhǔn)元素*/L->data0=L->datai;/* 當(dāng)前元素暫存在0 位置 */for(j=i-1;j>=1;j-)/* 當(dāng)前元素前面所有元素后移*/L->dataj+1=L->dataj;/* 當(dāng)前元素從0 位置移到最前面*/5. 設(shè)有一整型順序表 L ，元素從位置 1 開始存放，下列算法實(shí)現(xiàn)將以第一個(gè)元素為基準(zhǔn)，將其放置在表中合適的位置，使得其前面的元

9、素都比它小，后面的元素均大于等于該元素。請(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() while(L->data j>= L->data 0)&&(i<j) j-; /*j位置元素大于基準(zhǔn)元素且i<j時(shí) j 前移*/if (i<j) L->data i= L->data j;i+;while

10、(L->data i<= L->data 0)&&(i<j) i+;/*i位置元素小于基準(zhǔn)元素且i<j時(shí) i 后移*/if (i<j)/* 將基準(zhǔn)元素放在i 位置 */四、完整程序設(shè)計(jì)1. 在順序存儲(chǔ)結(jié)構(gòu)的職工工資表中，職工工資信息包括：職工號(hào)（no）、姓名（ name）、職稱（ pro）、工資（ sal）等四項(xiàng)信息，請(qǐng)編寫一完整的程序，實(shí)現(xiàn)以下功能：（ 1）創(chuàng)建信息表：從鍵盤讀入所有職工的信息。（3 分）（ 2）刪除：給定職工號(hào)，刪除該職工的信息。（6 分）.（ 3）修改：對(duì)職稱為“教授”的職工工資加100。（ 4 分）（ 4）在顯示器（屏

11、幕）上顯示所有職工的各項(xiàng)信息。（3 分）（ 5）主程序以菜單的方式調(diào)用以上功能。（4分）元素類型及順序表類型定義如下：typedef structchar no8,name10,pro6;float sal； DataType;typedef structDataType dataMAXLEN+1 ；int len;SeqList;2圖書管每本圖書包含： 書號(hào)（ no）、書名（ name）、現(xiàn)存量（ newnum）、總庫(kù)存量（ sumnum）、單價(jià)五項(xiàng)信息，編寫完整程序通過順序表實(shí)現(xiàn)：（1）初始化：錄入現(xiàn)有的所有圖書的五項(xiàng)信息。（ 3 分）（2）借書：每本書每次只能借一本，如果庫(kù)中有該書，則允

12、許借閱并使該書的現(xiàn)存量減1，否則給出相應(yīng)提示信息。（4 分）（3） 價(jià)值估算：統(tǒng)計(jì)庫(kù)中所有書的價(jià)錢。價(jià)錢為所有書的單價(jià)乘以庫(kù)存量的累加和。（ 4分）（ 4） 顯示：顯示圖書管所有藏書信息。 （ 3 分）（ 5） 主程序以菜單的方式調(diào)用以上功能。 （ 4 分）元素類型及順序表類型定義2 分。3. 設(shè)有兩個(gè)整型順序表 L1， L2，其元素值遞增有序存放，請(qǐng)定義該順序表的元素類型及表類型（ 2 分）；設(shè)計(jì)以下自定義函數(shù)：（ 1）錄入順序表中所有元素的值。 （ 3 分）（ 2）將順序表L1， L2 合并為到另外一個(gè)順序表L3 中， L3 中的元素非遞減有序排列。（ 8 分）（ 3）輸出順序表中元素的值

13、。 （ 3 分）主函數(shù)通過調(diào)用以上函數(shù)實(shí)現(xiàn)兩個(gè)表的合并并顯示合并結(jié)果。（4 分）4.有一個(gè)職工基本信息管理，職工信息包含：職工號(hào)、姓名、性別；編寫完整程序，實(shí)現(xiàn)如下功能：.(1) 錄入函數(shù) input: 從鍵盤讀入職工信息。 (3 分）(2) 刪除函數(shù) delete: 給定職工號(hào) , 刪除該職工的信息。 (5 分 )(3) 插入函數(shù) insert：假定表中職工信息按職工號(hào)升序排列，任意給定一職工信息，使得插入后依然有序。 (6 分 )主函數(shù)以菜單形式調(diào)用以上功能，類型定義2 分，主函數(shù)4 分。5. 有一個(gè)學(xué)生信息包含：學(xué)號(hào) no主關(guān)鍵字；姓名 name；英語成績(jī) score。定義學(xué)生信息類型

14、DataType 及順序表類型 SeqList;(1) 錄入函數(shù) input: 從鍵盤讀入學(xué)生信息。 （ 3 分）（ 2）查找函數(shù) search ：任意給定一個(gè)學(xué)號(hào)，查找其英語成績(jī)，將其成績(jī)通過函數(shù)返回，若找不到，返回 -1。（ 5 分）(3) 插入函數(shù) insert：假定表中學(xué)生信息按學(xué)號(hào)升序排列，任意給定一學(xué)生信息，使得插入后依然有序。 (6 分 )主函數(shù)以菜單形式調(diào)用以上功能，類型定義2 分，主函數(shù)4 分。6.設(shè)有一個(gè)超市的庫(kù)存情況如下表1 所示：表 1超市商品信息商品編號(hào)商品名稱價(jià)格庫(kù)存量10110001作業(yè)本1.22010110002鉛筆1.01010110003鋼筆0.530101

15、10004鉛筆刀105編寫完整程序?qū)崿F(xiàn)：(1)從鍵盤輸入貨物信息并將其放在順序表中。（ 4 分）。(2 ）假定商品信息按貨號(hào)升序存放，任意插入一商品信息，要求按貨號(hào)有序插入到表中。（6 分）(3 ）任意給定一個(gè)商品編號(hào)，查找其商品名稱、價(jià)格和庫(kù)存量，如果存在該商品輸出并返.回 1，否則返回0。（4 分）主函數(shù)以菜單形式調(diào)用以上功能，類型定義2 分，主函數(shù)4 分。7. 有一個(gè)房產(chǎn)信息管理系統(tǒng)，房產(chǎn)信息包含：門牌號(hào)、戶主、電話號(hào)碼、面積。編程實(shí)現(xiàn)如下功能（要求用順序表存儲(chǔ)） ：(1) 編寫一個(gè)初始化函數(shù) input: 從鍵盤讀入房產(chǎn)基本信息。 (3 分 )(2) 編寫一個(gè)取暖費(fèi)用計(jì)算函數(shù)cost:

16、任意給定一門牌號(hào)， 根據(jù)門牌號(hào)進(jìn)行查詢， 找到時(shí)，返回應(yīng)繳納取暖費(fèi)，否則返回0，并且給出提示信息。計(jì)算公式為：每戶應(yīng)繳納費(fèi)用=面積*4.5 元 /m2。（4 分）（ 3）編寫一排序函數(shù) sort：按門牌號(hào)升序排列。 （ 4 分）（ 4）編寫一個(gè)函數(shù) output: 輸出所有面積低于 90 平方米住戶的名稱。 （ 3 分）主函數(shù)以菜單形式調(diào)用以上功能，類型定義2 分，主函數(shù)4 分。8. 有一個(gè)學(xué)生信息包含：學(xué)號(hào) no主關(guān)鍵字；姓名 name；英語成績(jī) english，計(jì)算機(jī)成績(jī) comp,數(shù)學(xué)成績(jī) math 。定義學(xué)生信息類型 DataType 及順序表類型 SeqList;(1) 錄入基本信息

17、函數(shù) input: 從鍵盤讀入學(xué)生姓名、學(xué)號(hào)。 （ 3 分）（2）錄入成績(jī) inp_score ：給定課程名稱，錄入所有人本門課的成績(jī)。（3 分）(3) 刪除函數(shù) del ：假定表中學(xué)生信息學(xué)號(hào)升序排列，任意給定一學(xué)生學(xué)號(hào)，刪除該學(xué)生信息，正常刪除返回 1，否則返回 0。 (6 分 )（ 4）輸出函數(shù) output: 輸出所有人的信息。 （ 2 分）主函數(shù)以菜單形式調(diào)用以上功能，類型定義2 分，主函數(shù)4 分。9設(shè)有一個(gè)商品信息表( 包括商品編號(hào)no、商品名稱name、商品庫(kù)存量count 和商品單價(jià)price)編程實(shí)現(xiàn)以下功能：（1）貨物信息錄入：按貨號(hào)有序輸入學(xué)生信息。（ 3 分）（ 2）

18、進(jìn)貨管理：任意輸入一個(gè)貨物信息，在表中查找該貨物，若存在此貨物，則將該貨物的數(shù)量加到表中貨物數(shù)量中；若不存在該貨物，則將該貨物信息按照貨物號(hào)有序插入到表中。（ 10 分）（ 3）貨物信息輸出 : 輸出所有貨物的信息。 （ 2 分）主函數(shù)以菜單形式調(diào)用以上功能，類型定義2 分，主函數(shù)3 分。10設(shè)有一個(gè)商品信息表( 包括商品編號(hào)no、商品名稱name、商品庫(kù)存量count 和商品單價(jià) price).編程實(shí)現(xiàn)以下功能：（1）貨物信息錄入：按貨號(hào)有序輸入貨物信息。（ 3 分）（2）出貨管理：函數(shù)返回值為購(gòu)買該貨物的金額。任意輸入一個(gè)貨物信息x，在表中查找該貨物，若存在此貨物且?guī)齑媪看笥诘扔趚 的數(shù)量

19、，則將表中貨物的庫(kù)存量減去x 的數(shù)量，計(jì)算出需支付的金額并返回； 若庫(kù)存量不足， 則給出相應(yīng)的提示并返回 0。若不存在該貨物，返回 -1 。（ 10 分）（3）貨物信息輸出: 輸出所有貨物的信息。 （ 2 分）主函數(shù)以菜單形式調(diào)用以上功能，類型定義2 分，主函數(shù)3 分。11. 有一自來水公司水費(fèi)繳費(fèi)系統(tǒng)中，數(shù)據(jù)信息包括：用戶名稱、編號(hào)、用水量、水費(fèi)、繳費(fèi)情況（繳清，未繳） ，請(qǐng)定義用戶信息數(shù)據(jù)類型及順序表類型并設(shè)計(jì)如下函數(shù)：函數(shù) 1：輸入所有用戶的名稱，編號(hào)，用水量，用戶名為”?”作為結(jié)束符。每個(gè)用戶的水費(fèi)通過公式：水費(fèi) =用水量 *0.59 計(jì)算得出。用戶的繳費(fèi)情況都設(shè)為未繳。（4 分）函數(shù)

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

21、通過查找得到，金額=單價(jià)×數(shù)量）；最后輸出總的價(jià)格。 （ 10 分）（3）貨物信息輸出: 輸出所有貨物的信息。 （ 2 分）主函數(shù)以菜單形式調(diào)用以上功能，類型定義2 分，主函數(shù)3 分。13. 有一學(xué)生成績(jī)信息包括：姓名、學(xué)號(hào)、成績(jī)、名次；編程實(shí)現(xiàn)以下功能：（1）輸入所有人姓名、學(xué)號(hào)、成績(jī)，名次初始化為0。（3 分）（2）給定一學(xué)生學(xué)號(hào)，輸出其成績(jī)，若不存在該學(xué)號(hào)，給出相應(yīng)的錯(cuò)誤提示。（4 分）（3）將學(xué)生信息按成績(jī)由高到低排序，并將其名次存入該學(xué)生信息的“名次”中。（ 6分）（4）輸出所有學(xué)生的信息。 （2 分）主函數(shù)以菜單形式調(diào)用以上功能，類型定義2 分，主函數(shù) 3 分。14. 學(xué)

22、生考勤管理。學(xué)生信息包括：姓名、學(xué)號(hào)、考勤情況（遲到、曠課、按時(shí)上課），成績(jī).及本次已經(jīng)是第幾次考勤。每個(gè)人有20 次考勤；編程實(shí)現(xiàn)以下功能：（1）學(xué)生基本信息錄入及初始化：輸入所有學(xué)生的姓名、學(xué)號(hào)，將每個(gè)人的考勤成績(jī)置 0，將考勤次數(shù)也置 0。（ 3 分）（ 2）輸入考勤情況：每次上課，輸入本次考勤，從第一個(gè)人開始，依次輸入每個(gè)人的考勤。（ 4 分）（ 3）計(jì)算考勤成績(jī) : 遲到得 0.5 分，曠課得 0 分，正常上課得 1 分，計(jì)算每個(gè)人的考勤成績(jī)。（ 5 分）（4）輸出所有人的學(xué)號(hào)、姓名、考勤情況、考勤成績(jī)。（3 分）主函數(shù)以菜單形式調(diào)用以上功能，類型定義2 分，主函數(shù)3 分。元素類型定

23、義如下：typedef structchar name10;/*name 表示學(xué)生姓名*/char no12;/*no 表示學(xué)號(hào) */char kaoqin21;/*kaoqin 表示 20 次的考勤， q- 缺課， c- 遲到， z-按時(shí)上課 */int k;/*k 表示已經(jīng)考勤到第幾次，初始化時(shí)將其置為-1*/int score;/*score 表示考勤成績(jī) */ DataType;若有 DataType x，則 x. kaoqin2 表示 x 的第三次考勤。15. 有一個(gè)職工基本信息管理，職工信息包含：職工號(hào)、姓名、工資；編寫完整程序，實(shí)現(xiàn)如下功能：(1) 錄入函數(shù) input: 從鍵盤

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

25、，若找到修改其成績(jī)，若找不到，給出錯(cuò)誤提示。 (4 分)(3) 排序函數(shù)sort ：將學(xué)生信息按成績(jī)由高到低排序。(6分 )（ 4）輸出函數(shù)output:輸出所有人的信息。 （ 2 分）主函數(shù)以菜單形式調(diào)用以上功能，類型定義2 分，主函數(shù)3 分。17. 圖書管每本圖書包含： 書號(hào)（ no）、書名（ name）、現(xiàn)存量（ newnum）、總庫(kù)存量（ sumnum）四項(xiàng)信息，編寫完整程序通過順序表實(shí)現(xiàn)：(1)初始化：錄入現(xiàn)有的所有圖書的四項(xiàng)信息。（3 分）(2)清庫(kù)：給定某書 x 的書號(hào)及數(shù)量，若找到該書，將該書的現(xiàn)存量及庫(kù)存量減去x 的數(shù)量，若減后的庫(kù)存量為0，則刪除該書信息；若找不到該書，則給

26、出錯(cuò)誤提示。（9 分）(3) 顯示：顯示圖書管所有藏書信息。 （ 2 分）(4) 主程序以菜單的方式調(diào)用以上功能。 （ 4 分）元素類型及順序表類型定義（2 分）18. 圖書管每本圖書包含： 書號(hào)（ no）、書名（ name）、現(xiàn)存量（ newnum）、總庫(kù)存量（ sumnum）四項(xiàng)信息，編寫完整程序通過順序表實(shí)現(xiàn)：（ 1）初始化：錄入現(xiàn)有的所有圖書的四項(xiàng)信息。（3 分）（ 2）檢索：給定書名，輸出所有與給定書名相同的書的信息。（3 分）（ 3）價(jià)值估算： 統(tǒng)計(jì)庫(kù)中所有書的價(jià)錢。 價(jià)錢為所有書的單價(jià)乘以庫(kù)存量的累加和。（ 6分）（ 4） 顯示：顯示圖書管所有藏書信息。 （ 2 分）（ 5） 主

27、程序以菜單的方式調(diào)用以上功能。 （ 4 分）（ 6）完成元素類型定義及順序表類型定義（2 分）。19. 圖書管每本圖書包含： 書號(hào)（ no）、書名（ name）、現(xiàn)存量（ newnum）、總庫(kù)存量（ sumnum）四項(xiàng)信息，編寫完整程序通過順序表實(shí)現(xiàn)：（ 1）初始化：錄入現(xiàn)有的所有圖書的四項(xiàng)信息。（3 分）（ 2）查找：給定書號(hào)，在表中查找該書，若存在返回其位置，否則返回0。(4 分)（ 3） 進(jìn)書：給定某個(gè)圖書的書名、書號(hào)、數(shù)量，若此次購(gòu)進(jìn)的是圖書館已有的圖書，則修改其現(xiàn)存量和總庫(kù)存量； 若此次購(gòu)進(jìn)的圖書是新書， 按書號(hào)有序插入到表中。 （假定表中元素按書號(hào)升序排列） （7 分）（ 4） 主

28、程序以菜單的方式調(diào)用以上功能。 （ 4 分）（ 5）完成元素類型定義及順序表類型定義（2 分）。20學(xué)生學(xué)費(fèi)管理。學(xué)生信息包括：姓名、學(xué)號(hào)、學(xué)費(fèi)、已繳學(xué)費(fèi)、欠費(fèi)。編寫完整程序通過順序表實(shí)現(xiàn)：（1） 初始化：錄入所有人的姓名、學(xué)號(hào)、學(xué)費(fèi)。（3分）.（2）繳費(fèi)：輸入學(xué)號(hào)及已繳學(xué)費(fèi)，欠費(fèi)=學(xué)費(fèi) -已繳學(xué)費(fèi)。（ 5 分）（ 3） 催繳學(xué)費(fèi)：對(duì)欠費(fèi)為正數(shù)的人，輸出其姓名、學(xué)號(hào)、欠費(fèi)并統(tǒng)計(jì)所有人的欠費(fèi)總數(shù)，總的欠費(fèi)數(shù)目以函數(shù)值的形式返回（6 分）（ 4） 主程序以菜單的方式調(diào)用以上功能。 （ 4 分）（5）完成元素類型定義及順序表類型定義（2 分）。第四章 鏈表一、填空1鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)的線性表中所有元素的地

29、址（）連續(xù)。2單鏈表中增加頭結(jié)點(diǎn)的目的是為了（）。3用單鏈表存儲(chǔ)線性表，每個(gè)結(jié)點(diǎn)需要兩個(gè)域，一個(gè)是數(shù)據(jù)域，另一個(gè)是（）。4用單鏈表存儲(chǔ)線性表，每個(gè)結(jié)點(diǎn)需要兩個(gè)域，一個(gè)是（），另一個(gè)是指針域。5鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)的線性表其元素之間的邏輯關(guān)系是通過結(jié)點(diǎn)的()域來表示的。6指針為空表示該指針?biāo)赶虻慕Y(jié)點(diǎn)（）。7某帶頭結(jié)點(diǎn)的單鏈表的頭指針為head，判定該鏈表為非空的條件是()。8某帶頭結(jié)點(diǎn)的單鏈表的頭指針為head，判定該鏈表為空的條件是 ()9在單鏈表 L 中，指針 P 所指的結(jié)點(diǎn)為尾結(jié)點(diǎn)的條件是（）。10在單鏈表 L 中，指針 P 所指的結(jié)點(diǎn)有后繼結(jié)點(diǎn)的條件是（）。11頭插法建立單鏈表時(shí)，元素的輸入順

30、序與在鏈表中的邏輯順序是（）的。12尾接法建立單鏈表時(shí)，元素的輸入順序與在鏈表中的邏輯順序是（）的。13在帶有頭結(jié)點(diǎn)的單鏈表 HL 中，要在首元元素之前插入一個(gè)由指針p 指向的結(jié)點(diǎn)，則應(yīng)執(zhí)行 p->next=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要訪問具有n 個(gè)結(jié)點(diǎn)的單鏈表中任意一個(gè)結(jié)點(diǎn)的時(shí)間復(fù)雜度是（）。18鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)的線性表中，插入或刪除某個(gè)元素

31、所需的時(shí)間與其位置（）關(guān)。（填有或無）。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 (DataType a,int n)NodeType*hea

32、d, *s ；int i ；head=(NodeType*)malloc(sizeof(NodeType) ； /* 為頭結(jié)點(diǎn)申請(qǐng)空間*/if (head=NULL) return NULL;/* 鏈表初始化為空*/for (i=1 ； i<=n ；i+)s=(NodeType*)malloc(sizeof(NodeType) ；;/* 給新結(jié)點(diǎn)的數(shù)據(jù)域賦值*/s->next=head->next ；/* 新結(jié)點(diǎn)的指針域指向頭的下一個(gè)元素*/;/* 頭結(jié)點(diǎn)指向新結(jié)點(diǎn)*/;/* 返回頭指針 */2.下列算法完成用尾接法為數(shù)組 a 中的 n 個(gè)元素建立一個(gè)帶頭結(jié)點(diǎn)的單鏈表， 并返

33、回其頭指針，請(qǐng)?jiān)诳盏南聞澗€上填寫合適的內(nèi)容完成該算法。NodeType* creatl1(DataType a,int n)NodeType *head,*tail,*s;/* head 為頭指針，tail 為尾指針 */int i;head=initl( );/* 鏈表初始化 */if (head=NULL) return NULL;/* 尾指針初始化為頭指針*/for (i=0;i<n;i+);/* 為新結(jié)點(diǎn)申請(qǐng)空間*/if (s=NULL) return NULL;/* 申請(qǐng)不到空間，則返回空*/;/* 給新結(jié)點(diǎn)的數(shù)據(jù)域賦值*/s->next=NULL;/ * 給新結(jié)點(diǎn)的指針

34、域賦值*/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. 已知整型帶頭結(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 nodeintdata；struct node *next ；Node