word單元練習(xí)1一判斷題如下各題，正確的請(qǐng)?jiān)谇懊娴睦ㄌ?hào)打；錯(cuò)誤的打1數(shù)據(jù)的邏輯結(jié)構(gòu)與數(shù)據(jù)元素本身的容和形式無(wú)關(guān)。2一個(gè)數(shù)據(jù)結(jié)構(gòu)是由一個(gè)邏輯結(jié)構(gòu)和這個(gè)邏輯結(jié)構(gòu)上的一個(gè)根本運(yùn)算集構(gòu)成的整體。3數(shù)據(jù)元素是數(shù)據(jù)的最小單位。4數(shù)據(jù)的邏輯結(jié)構(gòu)和數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)是一樣的。5程序和算法原如此上沒(méi)有區(qū)別，所以在討論數(shù)據(jù)結(jié)構(gòu)時(shí)可以通用。6從邏輯關(guān)系上講，數(shù)據(jù)結(jié)構(gòu)主要分為線性結(jié)構(gòu)和非線性結(jié)構(gòu)兩類。7數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)是數(shù)據(jù)的邏輯結(jié)構(gòu)的存儲(chǔ)映像。8數(shù)據(jù)的物理結(jié)構(gòu)是指數(shù)據(jù)在計(jì)算機(jī)實(shí)際的存儲(chǔ)形式。9數(shù)據(jù)的邏輯結(jié)構(gòu)是依賴于計(jì)算機(jī)的。10算法是對(duì)解題方法和步驟的描述。二填空題（1） 數(shù)據(jù)有邏輯結(jié)構(gòu)和存儲(chǔ)結(jié)構(gòu)兩種結(jié)構(gòu)。（2） 數(shù)據(jù)邏輯結(jié)構(gòu)除了集合以外，還包括：線性結(jié)構(gòu)、樹(shù)形結(jié)構(gòu)和圖形結(jié)構(gòu)。（3） 數(shù)據(jù)結(jié)構(gòu)按邏輯結(jié)構(gòu)可分為兩大類，它們是線性結(jié)構(gòu)和非線性結(jié)構(gòu)。（4） 樹(shù)形結(jié)構(gòu)和圖形結(jié)構(gòu)合稱為非線性結(jié)構(gòu)。（5） 在樹(shù)形結(jié)構(gòu)中，除了樹(shù)根結(jié)點(diǎn)以外，其余每個(gè)結(jié)點(diǎn)只有1個(gè)前趨結(jié)點(diǎn)。（6） 在圖形結(jié)構(gòu)中，每個(gè)結(jié)點(diǎn)的前趨結(jié)點(diǎn)數(shù)和后續(xù)結(jié)點(diǎn)數(shù)可以任意多個(gè)。（7） 數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)又叫物理結(jié)構(gòu)。（8） 數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)形式包括：順序存儲(chǔ)、鏈?zhǔn)酱鎯?chǔ)、索引存儲(chǔ)和散列存儲(chǔ)。（9） 線性結(jié)構(gòu)中的元素之間存在一對(duì)一的關(guān)系。（10） 樹(shù)形結(jié)構(gòu)結(jié)構(gòu)中的元素之間存在一對(duì)多的關(guān)系，（11） 圖形結(jié)構(gòu)的元素之間存在多對(duì)多的關(guān)系。（12） 數(shù)據(jù)結(jié)構(gòu)主要研究數(shù)據(jù)的邏輯結(jié)構(gòu)、存儲(chǔ)結(jié)構(gòu)和算法或運(yùn)算三個(gè)方面的容。（13） 數(shù)據(jù)結(jié)構(gòu)被定義為(D，R)，其中D是數(shù)據(jù)的有限集合，R是D上的關(guān)系的有限集合。（14） 算法是一個(gè)有窮指令的集合。（15） 算法效率的度量可以分為事先估算法和事后統(tǒng)計(jì)法。（16） 一個(gè)算法的時(shí)間復(fù)雜性是算法輸入規(guī)模的函數(shù)。（17） 算法的空間復(fù)雜度是指該算法所消耗的存儲(chǔ)空間，它是該算法求解問(wèn)題規(guī)模n的函數(shù)。（18） 假如一個(gè)算法中的語(yǔ)句頻度之和為Tn=6n+3nlog2n，如此算法的時(shí)間復(fù)雜度為 Onlog2n。（19） 假如一個(gè)算法中的語(yǔ)句頻度之和為Tn=3n+nlog2n+n2，如此算法的時(shí)間復(fù)雜度為 On2。20數(shù)據(jù)結(jié)構(gòu)是一門研究非數(shù)值計(jì)算的程序設(shè)計(jì)問(wèn)題中計(jì)算機(jī)的操作對(duì)象，以與它們之間的關(guān)系和運(yùn)算的學(xué)科。三選擇題1數(shù)據(jù)結(jié)構(gòu)通常是研究數(shù)據(jù)的 A 與它們之間的相互聯(lián)系。 A. 存儲(chǔ)結(jié)構(gòu)和邏輯結(jié)構(gòu) B. 存儲(chǔ)和抽象 C. 聯(lián)系和抽象 D. 聯(lián)系與邏輯2在邏輯上可以把數(shù)據(jù)結(jié)構(gòu)分成： C 。 A. 動(dòng)態(tài)結(jié)構(gòu)和靜態(tài)結(jié)構(gòu) B. 緊湊結(jié)構(gòu)和非緊湊結(jié)構(gòu) C. 線性結(jié)構(gòu)和非線性結(jié)構(gòu) D. 部結(jié)構(gòu)和外部結(jié)構(gòu)3數(shù)據(jù)在計(jì)算機(jī)存儲(chǔ)器表示時(shí)，物理地址和邏輯地址一樣并且是連續(xù)的，稱之為 C 。 A. 存儲(chǔ)結(jié)構(gòu) B. 邏輯結(jié)構(gòu) C. 順序存儲(chǔ)結(jié)構(gòu) D. 鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)4非線性結(jié)構(gòu)中的每個(gè)結(jié)點(diǎn) D 。A. 無(wú)直接前趨結(jié)點(diǎn)B. 無(wú)直接后繼結(jié)點(diǎn)C. 只有一個(gè)直接前趨結(jié)點(diǎn)和一個(gè)直接后繼結(jié)點(diǎn)D. 可能有多個(gè)直接前趨結(jié)點(diǎn)和多個(gè)直接后繼結(jié)點(diǎn)5鏈?zhǔn)酱鎯?chǔ)的存儲(chǔ)結(jié)構(gòu)所占存儲(chǔ)空間 A 。 A分兩局部，一局部存放結(jié)點(diǎn)的值，另一局部存放表示結(jié)點(diǎn)間關(guān)系的指針 B只有一局部，存放結(jié)點(diǎn)的值 C只有一局部，存儲(chǔ)表示結(jié)點(diǎn)間關(guān)系的指針 D分兩局部，一局部存放結(jié)點(diǎn)的值，另一局部存放結(jié)點(diǎn)所占單元素6算法的計(jì)算量大小稱為算法的 C 。 A. 現(xiàn)實(shí)性 B. 難度 C. 時(shí)間復(fù)雜性 D. 效率7數(shù)據(jù)的根本單位是 B 。 A. 數(shù)據(jù)結(jié)構(gòu) B. 數(shù)據(jù)元素 C. 數(shù)據(jù)項(xiàng) D. 文件8每個(gè)結(jié)點(diǎn)只含有一個(gè)數(shù)據(jù)元素，所有存儲(chǔ)結(jié)點(diǎn)相繼存放在一個(gè)連續(xù)的存儲(chǔ)區(qū)里，這種存儲(chǔ)結(jié)構(gòu)稱為 A 結(jié)構(gòu)。 A. 順序存儲(chǔ) B. 鏈?zhǔn)酱鎯?chǔ) C. 索引存儲(chǔ) D. 散列存儲(chǔ)9每一個(gè)存儲(chǔ)結(jié)點(diǎn)不僅含有一個(gè)數(shù)據(jù)元素，還包含一組指針，該存儲(chǔ)方式是 B 存儲(chǔ)方式。 A. 順序 B. 鏈?zhǔn)紺. 索引 D. 散列10以下任何兩個(gè)結(jié)點(diǎn)之間都沒(méi)有邏輯關(guān)系的是 D 。 A. 圖形結(jié)構(gòu) B. 線性結(jié)構(gòu) C. 樹(shù)形結(jié)構(gòu) D. 集合11在數(shù)據(jù)結(jié)構(gòu)中，與所使用的計(jì)算機(jī)無(wú)關(guān)的是 C 。 A. 物理結(jié)構(gòu) B. 存儲(chǔ)結(jié)構(gòu) C. 邏輯結(jié)構(gòu) D. 邏輯和存儲(chǔ)結(jié)構(gòu)12如下四種根本邏輯結(jié)構(gòu)中，數(shù)據(jù)元素之間關(guān)系最弱的是 A 。 A. 集合 B. 線性結(jié)構(gòu) C. 樹(shù)形結(jié)構(gòu) D. 圖形結(jié)構(gòu)13與數(shù)據(jù)元素本身的形式、容、相對(duì)位置、個(gè)數(shù)無(wú)關(guān)的是數(shù)據(jù)的 A 。 A. 邏輯結(jié)構(gòu) B. 存儲(chǔ)結(jié)構(gòu) C. 邏輯實(shí)現(xiàn) D. 存儲(chǔ)實(shí)現(xiàn)14每一個(gè)存儲(chǔ)結(jié)點(diǎn)只含有一個(gè)數(shù)據(jù)元素，存儲(chǔ)結(jié)點(diǎn)存放在連續(xù)的存儲(chǔ)空間，另外有一組指明結(jié)點(diǎn)存儲(chǔ)位置的表，該存儲(chǔ)方式是 C 存儲(chǔ)方式。 A. 順序 B. 鏈?zhǔn)?C. 索引 D. 散列15算法能正確的實(shí)現(xiàn)預(yù)定功能的特性稱為算法的 A 。 A. 正確性 B. 易讀性 C. 健壯性 D. 高效性16算法在發(fā)生非法操作時(shí)可以作出處理的特性稱為算法的 C 。 A. 正確性 B. 易讀性 C. 健壯性 D. 高效性17如下時(shí)間復(fù)雜度中最壞的是 D 。 A. O1 B. O n C. Olog2n D. On218如下算法的時(shí)間復(fù)雜度是 D 。 for (i=0;i<n;i+) for (j=0;i<n;j+) cij=i+j; A. O1 B. O n C. Olog2n D. On219算法分析的兩個(gè)主要方面是 A 。A. 空間復(fù)雜性和時(shí)間復(fù)雜性 B. 正確性和簡(jiǎn)明性C. 可讀性和文檔性 D. 數(shù)據(jù)復(fù)雜性和程序復(fù)雜性20計(jì)算機(jī)算法必須具備輸入、輸出和 C 。 A. 計(jì)算方法 B. 排序方法C. 解決問(wèn)題的有限運(yùn)算步驟 D. 程序設(shè)計(jì)方法四分析下面各程序段的時(shí)間復(fù)雜度（1） for (i=0;i<n;i+) for (j=0;j<m;j+) Aij解： O(n*m)2 s=0; for (i=0;i<n;i+) for (j=0;j<n;j+) s+=Bij; sum=s;解： O(n2)3 T=A；A=B；B=T；解：O(1)4 s1(int n) int p=1,s=0; for (i=1;i<=n;i+) p*=i;s+=p; return(s);O(n)5 s2(int n)x=0;y=0;for (k=1;k<=n;k+)x+;for (i=1;i<=n;i+)for (j=1;j<=n;j+)y+;解：O(n2)五根據(jù)二元組關(guān)系，畫(huà)出對(duì)應(yīng)邏輯圖形的草圖，指出它們屬于何種數(shù)據(jù)結(jié)構(gòu)。1A=D，R，其中：D=a，b，c，d，e，R= 解： a b c d e屬于集合2B=D,R，其中：D=a,b,c,d,e,f，R=rR=<a,b>,<b,c>,<c,d>,<d,e>,<e,f> 尖括號(hào)表示結(jié)點(diǎn)之間關(guān)系是有向的解：屬于線性結(jié)構(gòu)。3F=D,R，其中：D=50,25,64,57,82,36,75,55，R=rR=<50,25>,<50,64>,<25,36>,<64,57>,<64,82>,<57,55>,<57,75>解：屬于樹(shù)結(jié)構(gòu)4C=D,R，其中： D=1,2,3,4,5,6，R=rR=(1,2),(2,3),(2,4),(3,4),(3,5),(3,6),(4,5),(4,6)園括號(hào)表示結(jié)點(diǎn)之間關(guān)系是有向的解：屬于圖結(jié)構(gòu)5E=D,R，其中：D=a,b,c,d,e,f,g,h，R=rR=<d,b>,<d,g>,<d,a>,<b,c>,<g,e>,<g,h>,<e,f>解：c屬于樹(shù)結(jié)構(gòu)。單元練習(xí)2一判斷題如下各題，正確的請(qǐng)?jiān)谇懊娴睦ㄌ?hào)打；錯(cuò)誤的打×1線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)優(yōu)于順序存儲(chǔ)。×2鏈表的每個(gè)結(jié)點(diǎn)都恰好包含一個(gè)指針域。3在線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)中，邏輯上相鄰的兩個(gè)元素在物理位置上并不一定緊鄰。×4順序存儲(chǔ)方式的優(yōu)點(diǎn)是存儲(chǔ)密度大，插入、刪除效率高。×5線性鏈表的刪除算法簡(jiǎn)單，因?yàn)楫?dāng)刪除鏈中某個(gè)結(jié)點(diǎn)后，計(jì)算機(jī)會(huì)自動(dòng)地將后續(xù)的各個(gè)單元向前移動(dòng)。×6順序表的每個(gè)結(jié)點(diǎn)只能是一個(gè)簡(jiǎn)單類型，而鏈表的每個(gè)結(jié)點(diǎn)可以是一個(gè)復(fù)雜類型。7線性表鏈?zhǔn)酱鎯?chǔ)的特點(diǎn)是可以用一組任意的存儲(chǔ)單元存儲(chǔ)表中的數(shù)據(jù)元素。8線性表采用順序存儲(chǔ)，必須占用一片連續(xù)的存儲(chǔ)單元。×9順序表結(jié)構(gòu)適宜于進(jìn)展順序存取，而鏈表適宜于進(jìn)展隨機(jī)存取。10插入和刪除操作是數(shù)據(jù)結(jié)構(gòu)中最根本的兩種操作，所以這兩種操作在數(shù)組中也經(jīng)常使用。二填空題（1） 順序表中邏輯上相鄰的元素在物理位置上必須相連。（2） 線性表中結(jié)點(diǎn)的集合是有限的，結(jié)點(diǎn)間的關(guān)系是一對(duì)一關(guān)系。（3） 順序表相對(duì)于鏈表的優(yōu)點(diǎn)是：節(jié)省存儲(chǔ)和隨機(jī)存取。（4） 鏈表相對(duì)于順序表的優(yōu)點(diǎn)是：插入、刪除方便。5采用順序存儲(chǔ)結(jié)構(gòu)的線性表叫順序表。6順序表中訪問(wèn)任意一個(gè)結(jié)點(diǎn)的時(shí)間復(fù)雜度均為 O(1) 。7鏈表相對(duì)于順序表的優(yōu)點(diǎn)是插入、刪除方便；缺點(diǎn)是存儲(chǔ)密度小。8在雙鏈表中要?jiǎng)h除結(jié)點(diǎn)*P，其時(shí)間復(fù)雜度為 O(1) 。9在單鏈表中要在結(jié)點(diǎn)*P之前插入一個(gè)新結(jié)點(diǎn)，需找到*P的直接前趨結(jié)點(diǎn)的地址，其查找的時(shí)間復(fù)雜度為 O(n) 。（10） 單鏈表中需知道頭指針才能遍歷整個(gè)鏈表。（11） 性表中第一個(gè)結(jié)點(diǎn)沒(méi)有直接前趨，稱為開(kāi)始結(jié)點(diǎn)。（12） 在一個(gè)長(zhǎng)度為n的順序表中刪除第i個(gè)元素，要移動(dòng) n-i 個(gè)元素。（13） 在一個(gè)長(zhǎng)度為n的順序表中，如果要在第i個(gè)元素前插入一個(gè)元素，要后移 n- i +1 個(gè)元素。（14） 在無(wú)頭結(jié)點(diǎn)的單鏈表中，第一個(gè)結(jié)點(diǎn)的地址存放在頭指針中，而其它結(jié)點(diǎn)的存儲(chǔ)地址存放在前趨結(jié)點(diǎn)的指針域中。（15） 當(dāng)線性表的元素總數(shù)根本穩(wěn)定，且很少進(jìn)展插入和刪除操作，但要求以最快速度存取線性表中的元素時(shí)，應(yīng)采用順序存儲(chǔ)結(jié)構(gòu)。（16） 在線性表的鏈?zhǔn)酱鎯?chǔ)中，元素之間的邏輯關(guān)系是通過(guò)指針決定的。（17） 在雙向鏈表中，每個(gè)結(jié)點(diǎn)都有兩個(gè)指針域，它們一個(gè)指向其前趨結(jié)點(diǎn)，另一個(gè)指向其后繼結(jié)點(diǎn)。（18） 對(duì)一個(gè)需要經(jīng)常進(jìn)展插入和刪除操作的線性表，采用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)為宜。（19） 雙鏈表中，設(shè)p是指向其中待刪除的結(jié)點(diǎn)，如此需要執(zhí)行的操作為： p->prior->next=p->next 。（20） 在如下列圖的鏈表中，假如在指針P所在的結(jié)點(diǎn)之后插入數(shù)據(jù)域值為a和b的兩個(gè)結(jié)點(diǎn)，如此可用如下兩個(gè)語(yǔ)句： S->next->next=P->next;和P->next=S;來(lái)實(shí)現(xiàn)該操作。PabS三選擇題1在具有n個(gè)結(jié)點(diǎn)的單鏈表中，實(shí)現(xiàn) A 的操作，其算法的時(shí)間復(fù)雜度都是On。A遍歷鏈表或求鏈表的第i個(gè)結(jié)點(diǎn) B在地址為P的結(jié)點(diǎn)之后插入一個(gè)結(jié)點(diǎn)C刪除開(kāi)始結(jié)點(diǎn) D刪除地址為P的結(jié)點(diǎn)的后繼結(jié)點(diǎn)2設(shè)a、b、c為三個(gè)結(jié)點(diǎn)，p、10、20分別代表它們的地址，如此如下的存儲(chǔ)結(jié)構(gòu)稱為 B 。A 循環(huán)鏈表 B單鏈表 C雙向循環(huán)鏈表 D雙向鏈表3單鏈表的存儲(chǔ)密度 C 。 A大于1 B等于1 C小于1 D不能確定4一個(gè)順序存儲(chǔ)的線性表，設(shè)每個(gè)結(jié)點(diǎn)占m個(gè)存儲(chǔ)單元，假如第一個(gè)結(jié)點(diǎn)的地址為B，如此第i個(gè)結(jié)點(diǎn)的地址為 A 。A B+(i-1)*m BB+i*m C B-i*m D B+(i+1)*m5在有n個(gè)結(jié)點(diǎn)的順序表上做插入、刪除結(jié)點(diǎn)運(yùn)算的時(shí)間復(fù)雜度為 B 。AO1 BOnCOn2 DOlog2n6設(shè)Llink、Rlink分別為循環(huán)雙鏈表結(jié)點(diǎn)的左指針和右指針，如此指針P所指的元素是雙循環(huán)鏈表L的尾元素的條件是 D 。AP= L BP->Llink= L CP= NULL DP->Rlink=L7兩個(gè)指針P和Q，分別指向單鏈表的兩個(gè)元素，P所指元素是Q所指元素前驅(qū)的條件是 B 。AP->next=Q->next BP->next= Q CQ->next= P DP= Q8用鏈表存儲(chǔ)的線性表，其優(yōu)點(diǎn)是 C 。A便于隨機(jī)存取B花費(fèi)的存儲(chǔ)空間比順序表少C便于插入和刪除 D數(shù)據(jù)元素的物理順序與邏輯順序一樣9在單鏈表中，增加頭結(jié)點(diǎn)的目的是 C 。A使單鏈表至少有一個(gè)結(jié)點(diǎn)B標(biāo)志表中首結(jié)點(diǎn)的位置C方便運(yùn)算的實(shí)現(xiàn) D說(shuō)明該單鏈表是線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)10下面關(guān)于線性表的表示中，錯(cuò)誤的答案是 D 關(guān)系。A順序表必須占一片地址連續(xù)的存儲(chǔ)單元 B順序表可以隨機(jī)存取任一元素C鏈表不必占用一片地址連續(xù)的存儲(chǔ)單元 D鏈表可以隨機(jī)存取任一元素11L是線性表，LengthListL的值是5，經(jīng)DelListL，2運(yùn)算后，LengthListL的值是 C 。A2 B3 C4 D512單鏈表的示意圖如下： LABCDQ RP指向鏈表Q結(jié)點(diǎn)的前趨的指針是 B 。AL BP CQ DR13設(shè)p為指向單循環(huán)鏈表上某結(jié)點(diǎn)的指針，如此*p的直接前驅(qū) C 。A找不到 B查找時(shí)間復(fù)雜度為O1C查找時(shí)間復(fù)雜度為On D查找結(jié)點(diǎn)的次數(shù)約為n14等概率情況下，在有n個(gè)結(jié)點(diǎn)的順序表上做插入結(jié)點(diǎn)運(yùn)算，需平均移動(dòng)結(jié)點(diǎn)的數(shù)目為 C 。An B(n-1)/2 C n/2 D(n+1)/215在如下鏈表中不能從當(dāng)前結(jié)點(diǎn)出發(fā)訪問(wèn)到其余各結(jié)點(diǎn)的是 C 。A雙向鏈表 B單循環(huán)鏈表 C單鏈表 D雙向循環(huán)鏈表16在順序表中，只要知道 D ，就可以求出任一結(jié)點(diǎn)的存儲(chǔ)地址。A基地址 B結(jié)點(diǎn)大小 C向量大小 D基地址和結(jié)點(diǎn)大小17在雙鏈表中做插入運(yùn)算的時(shí)間復(fù)雜度為 A 。AO1 BOn COn2 DOlog2n18鏈表不具備的特點(diǎn)是 A 。A隨機(jī)訪問(wèn) B不必事先估計(jì)存儲(chǔ)空間C插入刪除時(shí)不需移動(dòng)元素 D所需空間與線性表成正比19以下關(guān)于線性表的論述，不正確的為 C 。A線性表中的元素可以是數(shù)字、字符、記錄等不同類型B線性順序表中包含的元素個(gè)數(shù)不是任意的C線性表中的每個(gè)結(jié)點(diǎn)都有且僅有一個(gè)直接前趨和一個(gè)直接后繼D存在這樣的線性表，即表中沒(méi)有任何結(jié)點(diǎn)20在 B 的運(yùn)算中，使用順序表比鏈表好。A插入 B根據(jù)序號(hào)查找 C刪除 D根據(jù)元素查找ListNode *Demo1(LinkList L,ListNode *p) / L是有頭結(jié)點(diǎn)的單鏈表ListNode *q=L->next;While (q && q->next!=p)q=q->next;if (q)return q;elseError(“*p not in L); 四分析下述算法的功能1void Demo2(ListNode *p,ListNode *q) / p,*q是鏈表中的兩個(gè)結(jié)點(diǎn)DataType temp;temp=p->data;p->data=q->data;q->data=temp;2解：1返回結(jié)點(diǎn)*p的直接前趨結(jié)點(diǎn)地址。2交換結(jié)點(diǎn)*p和結(jié)點(diǎn)*qp和q的值不變。五程序填空1線性表中的元素是無(wú)序的，并以帶表頭結(jié)點(diǎn)的單鏈表作存儲(chǔ)。試寫(xiě)一算法，刪除表中所有大于min，小于max的元素，試完成如下程序填空。Void delete (lklist head; datatype min, max) q=head->next; while (p!=NULL) if (p->data<=min ) | | ( p->data>=max ) q=p; p= p->next ; else q->next= p->next ;delete (p) ;p= q->next ; 2在帶頭結(jié)點(diǎn)head的單鏈表的結(jié)點(diǎn)a之后插入新元素x，試完成如下程序填空。struct node elemtype data; node *next;void lkinsert (node *head, elemtype x) node *s, *p;s= new node ;s->data= x ; p=head->next;while (p!=NULL) && ( p->data!=a )_p=p->next ;if (p=NULL)cout<< " 不存在結(jié)點(diǎn)a! " else _s->next=p->next_;_ p->next=s _;六算法設(shè)計(jì)題1寫(xiě)一個(gè)對(duì)單循環(huán)鏈表進(jìn)展遍歷打印每個(gè)結(jié)點(diǎn)的值的算法，鏈表中任意結(jié)點(diǎn)的地址為P 。解：void Show(ListNode *P) ListNode *t=P; do printf("%c",t->data); t=t->rear; while (t!=P);（2） 對(duì)給定的帶頭結(jié)點(diǎn)的單鏈表L，編寫(xiě)一個(gè)刪除L中值為x的結(jié)點(diǎn)的直接前趨結(jié)點(diǎn)的算法。解：void delete(ListNode *L)ListNode *p=L,*q;if(L->next->data=X)printf(“值為x的結(jié)點(diǎn)是第一個(gè)結(jié)點(diǎn)，沒(méi)有直接前趨結(jié)點(diǎn)可以刪除);return;For(p->next->data!=X;q=p;p=p->next);/ 刪除指針p所指向的結(jié)點(diǎn)q->next=p->next;delete p;（3） 一個(gè)單向鏈表，編寫(xiě)一個(gè)函數(shù)從單鏈表中刪除自第i個(gè)結(jié)點(diǎn)起的k個(gè)結(jié)點(diǎn)。解：void Del(node *head,int i,int k) node *p,*q;int j;if(i=1)for(j=1;j<=k;j+) / 刪除前k個(gè)元素 p=head; / p指向要?jiǎng)h除的結(jié)點(diǎn) head=head->next;delete p;else p=head; for(j=1;j<=i-2;j+) p=p->next; / p指向要?jiǎng)h除的結(jié)點(diǎn)的前一個(gè)結(jié)點(diǎn) for(j=1;j<=k;j+) q=p->next; / q 指向要?jiǎng)h除的結(jié)點(diǎn) p->next=q->next; delete q;（4） 有一個(gè)單向鏈表不同結(jié)點(diǎn)的數(shù)據(jù)域值可能一樣，其頭指針為head，編寫(xiě)一個(gè)函數(shù)計(jì)算值域?yàn)閤的結(jié)點(diǎn)個(gè)數(shù)。解：/此題是遍歷單鏈表的每個(gè)結(jié)點(diǎn)，每遇到一個(gè)結(jié)點(diǎn)，結(jié)點(diǎn)個(gè)數(shù)加1，結(jié)點(diǎn)個(gè)數(shù)存儲(chǔ)在變量n中。實(shí)現(xiàn)此題功能的函數(shù)如下：int counter(head)node *head； node *p;int n=0; p=head； while(p!=NULL) if(p->data=x)n+；p=p->next; return(n);5有兩個(gè)循環(huán)單向鏈表，鏈頭指針?lè)謩e為head1和head2，編寫(xiě)一個(gè)函數(shù)將鏈表head1到鏈表head2，后的鏈表仍是循環(huán)鏈表。解：/此題的算法思想是：先找到兩鏈表的尾指針，將第一個(gè)鏈表的尾指針與第二個(gè)鏈表的頭結(jié)點(diǎn)起來(lái)，使之成為循環(huán)的。函數(shù)如下：node *link (node *head1, *head2) node *p,*q;p=head1;while(p->next!=head1) p=p->next;q=head2;while(q->next!=head2) q=q->next;p->next=head2;q->next=head1;return (head1);單元練習(xí)3一判斷題如下各題，正確的請(qǐng)?jiān)谇懊娴睦ㄌ?hào)打；錯(cuò)誤的打1棧是運(yùn)算受限制的線性表。2在?？盏那闆r下，不能作出棧操作，否如此產(chǎn)生下溢出。3棧一定是順序存儲(chǔ)的線性結(jié)構(gòu)。4棧的特點(diǎn)是“后進(jìn)先出。5空棧就是所有元素都為0的棧。6在C或C+語(yǔ)言中設(shè)順序棧的長(zhǎng)度為MAXLEN，如此top=MAXLEN時(shí)表示隊(duì)滿。7鏈棧與順序棧相比，其特點(diǎn)之一是通常不會(huì)出現(xiàn)棧滿的情況。8一個(gè)棧的輸入序列為：A，B，C，D，可以得到輸出序列：C，A，B，D。9遞歸定義就是循環(huán)定義。10將十進(jìn)制數(shù)轉(zhuǎn)換為二進(jìn)制數(shù)是棧的典型應(yīng)用之一。二填空題1在棧結(jié)構(gòu)中，允許插入、刪除的一端稱為棧頂。2在順序棧中，當(dāng)棧頂指針top=-1時(shí)，表示?？?。3在有n個(gè)元素的棧中，進(jìn)棧操作的時(shí)間復(fù)雜度為 O1。4在棧中，出棧操作的時(shí)間復(fù)雜度為： O(1) 。5表達(dá)式，求它的后綴表達(dá)式是棧的典型應(yīng)用。6在一個(gè)鏈棧中，假如棧頂指針等于NULL，如此表示棧空。7向一個(gè)棧頂指針為top的鏈棧插入一個(gè)新結(jié)點(diǎn)*p時(shí)，應(yīng)執(zhí)行 p->next=top；和top=p；操作。8順序棧S存儲(chǔ)在數(shù)組 S->data0.MAXLEN-1中，進(jìn)棧操作時(shí)要執(zhí)行的語(yǔ)句有：S->top + ?；? S->top+19鏈棧LS，指向棧頂元素的指針是 LS->next 。10從一個(gè)棧刪除元素時(shí)，首先取出棧頂元素，然后再移動(dòng)棧頂指針。11由于鏈棧的操作只在鏈表的頭部進(jìn)展，所以沒(méi)有必要設(shè)置頭結(jié)點(diǎn)。12順序棧S，在對(duì)S進(jìn)展進(jìn)棧操作之前首先要判斷棧是否滿。13順序棧S，在對(duì)S進(jìn)展出棧操作之前首先要判斷棧是否空。14假如存空間充足，鏈?？梢圆欢x棧滿運(yùn)算。15鏈棧LS是空的條件是 LS->next=NULL 。16鏈棧LS的棧頂元素是鏈表的首元素。17同一棧的各元素的類型一樣。18假如進(jìn)棧的次序是A、B、C、D、E，執(zhí)行三次出棧操作以后，棧頂元素為 B 。19A+B/C-D*E的后綴表達(dá)式是： ABC/+DE*- 。20四個(gè)元素按A、B、C、D順序進(jìn)S棧，執(zhí)行兩次PopS，x運(yùn)算后，x的值是 C 。三選擇題1插入和刪除只能在一端進(jìn)展的線性表，稱為( C )。 A隊(duì)列 B循環(huán)隊(duì)列 C棧 D循環(huán)棧2設(shè)有編號(hào)為1，2，3，4的四輛列車，順序進(jìn)入一個(gè)棧結(jié)構(gòu)的站臺(tái)，如下不可能的出站順序?yàn)?( D ) A1234 B1243 C1324 D14233如果以鏈表作為棧的存儲(chǔ)結(jié)構(gòu)，如此出棧操作時(shí) B A必須判別棧是否滿 B必須判別棧是否空 C必須判別棧元素類型 D隊(duì)棧可不做任何判別4元素A,B,C,D依次進(jìn)棧以后，棧頂元素是 D AA BB CC DD5順序棧存儲(chǔ)空間的實(shí)現(xiàn)使用 B 存儲(chǔ)棧元素。 A鏈表 B數(shù)組 C循環(huán)鏈表 D變量6在C或C+語(yǔ)言中，一個(gè)順序棧一旦被聲明，其占用空間的大小 A 。 A已固定 B不固定 C可以改變 D動(dòng)態(tài)變化7帶頭結(jié)點(diǎn)的鏈棧LS的示意圖如下，棧頂元素是 A LSHABCD AA BB CC DD8鏈棧與順序棧相比，有一個(gè)比擬明顯的優(yōu)點(diǎn)是 B 。A插入操作更加方便 B通常不會(huì)出現(xiàn)棧滿的情況。C不會(huì)出現(xiàn)?？盏那闆r D刪除操作根加方便9從一個(gè)棧頂指針為top的鏈棧中刪除一個(gè)結(jié)點(diǎn)時(shí)，用x保存被刪除的結(jié)點(diǎn)，應(yīng)執(zhí)行如下 ( D )命令。 Ax=top;top=top->next; Btop=top->next;x=top->data; Cx=top->data; Dx=top->data;top=top->next;10在一個(gè)棧頂指針為HS的鏈棧中，將一個(gè)S指針?biāo)傅慕Y(jié)點(diǎn)入棧，應(yīng)執(zhí)行如下 ( B )命令。 AHS->next=S; BS->next=HS->next;HS->next=S; CS->next=HS->next;HS=S; DS->next=HS;HS=HS->next;11四個(gè)元素按A、B、C、D順序進(jìn)S棧，執(zhí)行兩次PopS，x運(yùn)算后，棧頂元素的值是 B 。 AA BB CC DD12元素A,B,C,D依次進(jìn)棧以后，棧底元素是 A 。 AA BB CC DD13經(jīng)過(guò)如下棧的運(yùn)算后，再執(zhí)行ReadTop(s)的值是 A 。 InitStack(s)初始化棧;Push(s,a);Push(s,b); Pop(s)Aa Bb C1 D014經(jīng)過(guò)如下棧的運(yùn)算后，x的值是 B 。 InitStack(s)初始化棧;Push(s,a);Push(s,b); ReadTop(s);Pop(s,x);Aa Bb C1 D015經(jīng)過(guò)如下棧的運(yùn)算后，x的值是 B 。 InitStack(s)初始化棧;Push(s,a);Pop(s,x);Push(s,b);Pop(s,x);Aa Bb C1 D016經(jīng)過(guò)如下棧的運(yùn)算后，SEmpty(s)的值是 C 。 InitStack(s)初始化棧; Push(s,a); Push(s,b);Pop(s,x); Pop(s,x);Aa Bb C1 D017向順序棧中壓入元素時(shí)， B 。A 先存入元素，后移動(dòng)棧頂指針 B先移動(dòng)棧頂指針，后存入元素C誰(shuí)先誰(shuí)后無(wú)關(guān)緊要 D同時(shí)進(jìn)展18初始化一個(gè)空間大小為5的順序棧S后，S->top的值是 B 。 A0 B-1 C不再改變 D動(dòng)態(tài)變化19一個(gè)棧的入棧次序ABCDE，如此棧的不可能的輸出序列是 ( C )。 AEDCBA BDECBA CDCEAB DABCDE20設(shè)有一個(gè)順序棧S，元素A,B,C,D,E,F,依次進(jìn)棧，如果六個(gè)元素出棧的順序是B，D，C，F(xiàn)，E，A，如此棧的容量至少應(yīng)是 ( A )。 A3 B4 C5 D 6四應(yīng)用題1設(shè)有一個(gè)棧，元素進(jìn)棧的次序?yàn)椋篈，B，C，D，E，用I表示進(jìn)棧操作，O表示出棧操作，寫(xiě)出如下出棧的操作序列。C，B，A，D，E A，C，B，E，D解：IIIOOOIOIOIOIIOOIIOO（2） 求后綴表達(dá)式 ABC/D解：A B C D / -A+B*C+D/E解：0 A B C * + D E / + A*(B+C)*D-E解：A B C + * D * E - (A+B)*C-E/(F+G/H)-D解：A B + C * E F G H / + / - D - 8/(5+2)-6解：8 5 2 + / 6 -六算法設(shè)計(jì)題1設(shè)用一維數(shù)組stackn表示一個(gè)堆棧，假如堆棧中每個(gè)元素需占用M個(gè)數(shù)組單元M>1。試寫(xiě)出其入棧操作的算法。試寫(xiě)出其出棧操作的算法。解：/用一整型變量top表示棧頂指針，top為0時(shí)表示棧為空。棧中元素從S 1開(kāi)始存放元素。/入棧算法：void push (char x) if (top+M)>MAXLEN-1) printf (“堆棧溢出！); else if (top= =0) top+; S top=x; else top=top+M; S top=x; /出棧算法： void pop (char x) if (top= =0) printf (“堆棧為空棧！); else if (top= =1) x= S top; top; else x= S top; top=topM; 2設(shè)計(jì)一個(gè)算法，要求判別一個(gè)算術(shù)表達(dá)式中的圓括號(hào)配對(duì)是否正確。解：/設(shè)表達(dá)式在字符數(shù)組a 中，使用一堆棧S來(lái)幫助判斷。 int correct (char a ) stack s ; InitStack (s); /調(diào)用初始化棧函數(shù) for (i=0; i <strlen(a);i+) if (ai= =() Push (s,(); elseif (ai= =) if StackEmpty (s) /調(diào)用判?？蘸瘮?shù) return 0; /假如棧為空返回0；否如此出棧 else Pop(s); if (StackEmpty (s) ) /調(diào)用判棧空函數(shù) printf (“配對(duì)正確！); /假如?？眨f(shuō)明配對(duì)正確，并返回1 else printf (“配對(duì)錯(cuò)誤！); /配對(duì)錯(cuò)誤返回0 （3） 設(shè)計(jì)一個(gè)將十進(jìn)正整數(shù)轉(zhuǎn)換為十進(jìn)制數(shù)的算法，并要求上機(jī)調(diào)試通過(guò)。解： #include<stdio.h> #include<stdlib.h>typedef struct stacknode /定義棧的存儲(chǔ)結(jié)構(gòu) int data;struct stacknode *next;stacknode;typedef struct stacknode *top; /定義棧頂?shù)闹羔榣inkstack;void Conversion(int n) /棧的應(yīng)用：十十六進(jìn)制轉(zhuǎn)換 linkstack s;int x; s.top=NULL; /置棧空do x=n%16; /取余數(shù)n= n/16 ; /取新的商stacknode *p=new stacknode; /申請(qǐng)新結(jié)點(diǎn)p->next=s.top ; /修改棧頂指針s.top=p;s.top->data=x; /余數(shù)入棧while(n); printf("ntt轉(zhuǎn)換后的十六進(jìn)制數(shù)值為："while (s.top) /出棧處理if(s.top->data<10); printf("%d",s.top->data); else switch(s.top->data) case 10: printf("%c",'A');break;case 11: printf("%c",'B');break;case 12: printf("%c",'C');break;case 13: printf("%c",'D');break;case 14: printf("%c",'E');break;case 15: printf("%c",'F');break; stacknode *p=s.top;s.top=s.top->next;free(p) ; /出棧一個(gè)余數(shù)，收回一個(gè)結(jié)printf("nn");void main() int n; printf("ntt請(qǐng)輸入一個(gè)十進(jìn)制正整數(shù)：");scanf("%d",&n);Conversion(n);單元練習(xí)4一判斷題如下各題，正確的請(qǐng)?jiān)谇懊娴睦ㄌ?hào)打；錯(cuò)誤的打1隊(duì)列是限制在兩端進(jìn)展操作的線性表。2判斷順序隊(duì)列為空的標(biāo)準(zhǔn)是頭指針和尾指針都指向同一個(gè)結(jié)點(diǎn)。×3在鏈隊(duì)列上做出隊(duì)操作時(shí)，會(huì)改變front指針的值。4在循環(huán)隊(duì)列中，假如尾指針rear大于頭指針front，其元素個(gè)數(shù)為rear- front。×5在單向循環(huán)鏈表中，假如頭指針為h，那么p所指結(jié)點(diǎn)為尾結(jié)點(diǎn)的條件是p=h。6鏈隊(duì)列在一定圍不會(huì)出現(xiàn)隊(duì)滿的情況。×7在循環(huán)鏈隊(duì)列中無(wú)溢出現(xiàn)象。×8棧和隊(duì)列都是順序存儲(chǔ)的線性結(jié)構(gòu)。×9在隊(duì)列中允許刪除的一端稱為隊(duì)尾。×10順序隊(duì)和循環(huán)隊(duì)關(guān)于隊(duì)滿和隊(duì)空的判斷條件是一樣的。二填空題（1） 在隊(duì)列中存取數(shù)據(jù)應(yīng)遵循的原如此是先進(jìn)先出。（2） 隊(duì)列是被限定為只能在表的一端進(jìn)展插入運(yùn)算，在表的另一端進(jìn)展刪除運(yùn)算的線性表。（3） 在隊(duì)列中，允許插入的一端稱為隊(duì)尾。（4） 在隊(duì)列中，允許刪除的一端稱為隊(duì)首或隊(duì)頭。（5） 隊(duì)列在進(jìn)展出隊(duì)操作時(shí)，首先要判斷隊(duì)列是否為空。（6） 順序隊(duì)列在進(jìn)展入隊(duì)操作時(shí)，首先要判斷隊(duì)列是否為滿。（7） 順序隊(duì)列初始化后，front=rear= -1 。（8） 解決順序隊(duì)列“假溢出的方法是采用循環(huán)隊(duì)列。（9） 循環(huán)隊(duì)列的隊(duì)首指針為front，隊(duì)尾指針為rear，如此隊(duì)空的條件為 front = rear 。（10） 鏈隊(duì)列LQ為空時(shí)，LQ->front->next= NULL 。（11） 設(shè)長(zhǎng)度為n的鏈隊(duì)列用單循環(huán)鏈表表示，假如只設(shè)頭指針，如此入隊(duì)操作的時(shí)間復(fù)雜度為 On。（12） 設(shè)長(zhǎng)度為n的鏈隊(duì)列用單循環(huán)鏈表表示，假如只設(shè)尾指針，如此出隊(duì)操作的時(shí)間復(fù)雜度為 01。（13） 在一個(gè)鏈隊(duì)列中，假如隊(duì)首指針與隊(duì)尾指針的值一樣，如此表示該隊(duì)列為空。（14） 設(shè)循環(huán)隊(duì)列的頭指針front指向隊(duì)首元素，尾指針rear指向隊(duì)尾元素后的一個(gè)空閑元素，隊(duì)列的最大空間為MAXLEN，如此隊(duì)滿標(biāo)志為： front=(rear+1)%MAXLEN 。（15） 在一個(gè)鏈隊(duì)列中，假如隊(duì)首指針為front，隊(duì)尾指針為rear，如此判斷該隊(duì)列只有一個(gè)結(jié)點(diǎn)的條件為： front=rear && front !NULL 。(或 front=rear && front <>NULL )（16） 向一個(gè)循環(huán)隊(duì)列中插入元素時(shí)，首先要判斷隊(duì)尾指針，然后再向指針?biāo)傅奈恢脤?xiě)入新的數(shù)據(jù)。（17） 讀隊(duì)首元素的操作不改變或不影響隊(duì)列元素的個(gè)數(shù)。18設(shè)循環(huán)隊(duì)列的容量為40序號(hào)從0到39，現(xiàn)經(jīng)過(guò)一系列的入隊(duì)和出隊(duì)運(yùn)算后，有 front=11，rear=19，如此循環(huán)隊(duì)列中還有 8 個(gè)元素。L= (Nrearfront)% N=401911% 40=819隊(duì)列Q，經(jīng)過(guò)如下運(yùn)算：InitQueue(Q)(初始化隊(duì)列);InQueue(Q,a); InQueue(Q,b);OutQueue(Q,x); ReadFront(Q,x);QEmpty(Q);后的值是0 。20隊(duì)列Q經(jīng)過(guò)InitQueue(Q)(初始化隊(duì)列);InQueue(Q,a);InQueue(Q,b); ReadFront(Q,x)后，x的值是 a 。三選擇題1隊(duì)列是限定在 D 進(jìn)展操作的線性表。 A中間 B隊(duì)首 C隊(duì)尾 D端點(diǎn)2隊(duì)列中的元素個(gè)數(shù)是( B )。 A不變的 B可變的 C任意的 D03同一隊(duì)列各元素的類型( A )。 A必須一致 B不能一致 C可以不一致 D不限制4隊(duì)列是一個(gè)( C )線性表結(jié)構(gòu)。 A不加限制的 B推廣了的 C加了限制的 D非5當(dāng)利用大小為n的數(shù)組順序存儲(chǔ)一個(gè)隊(duì)列時(shí)，該隊(duì)列的最后一個(gè)元素的下標(biāo)為 B 。 An-2 Bn-1 Cn Dn+16一個(gè)循環(huán)隊(duì)列一旦說(shuō)明，其占用空間的大小 A 。 A已固定 B可以變動(dòng) C不能固定 D動(dòng)態(tài)變化7循環(huán)隊(duì)列占用的空間( A )。 A必須連續(xù) B不必連續(xù) C不能連續(xù) D可以不連續(xù)8存放循環(huán)隊(duì)列元素的數(shù)組data有10個(gè)元素，如此data數(shù)組的下標(biāo)圍是( B )。 A0.10 B0.9 C1.9 D1.109假如進(jìn)隊(duì)的序列為：A，B，C，D，如此出隊(duì)的序列是 C 。 AB，C，D，A BA，C，B，D CA，B，C，D DC，B，D，A10四個(gè)元素按：A，B，C，D順序連續(xù)進(jìn)隊(duì)Q，如此隊(duì)尾元素是 D 。 A AB B C CD D11四個(gè)元素按：A，B，C，D順序連續(xù)進(jìn)隊(duì)Q，執(zhí)行一次OutQueue(Q)操作后，隊(duì)頭元素是 B 。 A AB B C C D D12四個(gè)元素按：A，B，C，D順序連續(xù)進(jìn)隊(duì)Q，執(zhí)行四次OutQueue(Q)操作后，再執(zhí)行QEmpty(Q);后的值是 B 。 A 0B 1 C 2 D 313隊(duì)列Q，經(jīng)過(guò)如下運(yùn)算后，x 的值是 B 。 InitQueue(Q)(初始化隊(duì)列);InQueue(Q,a); InQueue(Q,b);OutQueue(Q,x); ReadFront (Q,x);Aa Bb C0 D114循環(huán)隊(duì)列SQ隊(duì)滿的條件是( B )。 ASQ->rear=SQ->front B(SQ->rear+1)% MAXLEN =SQ->frontCSQ->rear=0 DSQ->front=015設(shè)鏈棧中結(jié)點(diǎn)的結(jié)構(gòu)：data為數(shù)據(jù)域，next為指針域，且top是棧頂指針。假如想在鏈棧的棧頂插入一個(gè)由指針s所指的結(jié)點(diǎn)，如此應(yīng)執(zhí)行如下 A 操作。 As->next=top->next；top->next=s； Btop->next=s； Cs->next=top；top=top->next； Ds->next=top；top=s；16帶頭結(jié)點(diǎn)的鏈隊(duì)列LQ示意圖如下，鏈隊(duì)列的隊(duì)頭元素是 A LQ->frontHABCDLQ->rearAA BB CC DD17帶頭結(jié)點(diǎn)的鏈隊(duì)列LQ示意圖如下，指向鏈隊(duì)列的隊(duì)頭指針是 C LQ