數(shù)據(jù)結(jié)構(gòu)期末考試(題集)

1、WORD格式數(shù)據(jù)構(gòu)造的根本概念選擇題 1順序存儲(chǔ)構(gòu)造中數(shù)據(jù)元素之間的邏輯關(guān)系是由表示的， 存儲(chǔ)構(gòu)造中的數(shù)據(jù)元素之間的邏輯關(guān)系是由表示的。A 線性構(gòu)造B 非線性構(gòu)造C存儲(chǔ)位置D指針 2假設(shè)有如下遺產(chǎn)繼承規(guī)那么： 丈夫和妻子可以相互繼承遺產(chǎn)， 子女可以繼承父親或母親的遺產(chǎn)； 子女間不能相互繼承， 那么表示該遺產(chǎn)繼承關(guān)系的最適宜的數(shù)據(jù)構(gòu)造應(yīng)該是。A 樹B 圖C線性表D集合 3計(jì)算機(jī)所處理的數(shù)據(jù)一般具有某種內(nèi)在聯(lián)系，這是指。A 數(shù)據(jù)和數(shù)據(jù)之間存在某種關(guān)系B元素和元素之間存在某種關(guān)系C元素內(nèi)部具有某種構(gòu)造D數(shù)據(jù)項(xiàng)和數(shù)據(jù)項(xiàng)之間存在某種關(guān)系 4在數(shù)據(jù)構(gòu)造中，與所使用的計(jì)算機(jī)無關(guān)的是數(shù)據(jù)的。A 樹B 圖C線性

2、表D集合 5在存儲(chǔ)數(shù)據(jù)時(shí)，通常不僅要存儲(chǔ)各數(shù)據(jù)元素的值，還要存儲(chǔ)。A 數(shù)據(jù)的處理方法B數(shù)據(jù)元素的類型C數(shù)據(jù)元素之間的關(guān)系D數(shù)據(jù)的存儲(chǔ)方法 6在存儲(chǔ)構(gòu)造中，要求。A 每個(gè)結(jié)點(diǎn)占用一片連續(xù)的存儲(chǔ)區(qū)域B所有結(jié)點(diǎn)占用一片連續(xù)的存儲(chǔ)區(qū)域C結(jié)點(diǎn)的最后一個(gè)域是指針類型D每個(gè)結(jié)點(diǎn)有多少個(gè)后繼就設(shè)多少個(gè)指針 7以下說法不正確的選項(xiàng)是。A 數(shù)據(jù)元素是數(shù)據(jù)的根本單位B數(shù)據(jù)項(xiàng)是數(shù)據(jù)中不可分割的最小單位C數(shù)據(jù)可由假設(shè)干個(gè)數(shù)據(jù)項(xiàng)構(gòu)成D數(shù)據(jù)元素可由假設(shè)干個(gè)數(shù)據(jù)項(xiàng)構(gòu)成 8以下與數(shù)據(jù)的存儲(chǔ)構(gòu)造無關(guān)的術(shù)語是。A 循環(huán)隊(duì)列B 鏈表C散列表D棧 9以下術(shù)語屬于邏輯構(gòu)造的是。A 順序表B 哈希表C有序表D單鏈表 10可以用定義一個(gè)完整

3、的數(shù)據(jù)構(gòu)造。A 數(shù)據(jù)元素B 數(shù)據(jù)對(duì)象C數(shù)據(jù)關(guān)系D抽象數(shù)據(jù)類型 11對(duì)于數(shù)據(jù)構(gòu)造的描述，以下說法中不正確的選項(xiàng)是。A 一樣的邏輯構(gòu)造對(duì)應(yīng)的存儲(chǔ)構(gòu)造也必一樣B數(shù)據(jù)構(gòu)造由邏輯構(gòu)造、存儲(chǔ)構(gòu)造和根本操作三方面組成專業(yè)資料整理WORD格式1專業(yè)資料整理WORD格式C數(shù)據(jù)構(gòu)造根本操作的實(shí)現(xiàn)與存儲(chǔ)構(gòu)造有關(guān)D數(shù)據(jù)的存儲(chǔ)構(gòu)造是數(shù)據(jù)的邏輯構(gòu)造的機(jī)內(nèi)實(shí)現(xiàn) 12以下關(guān)于存儲(chǔ)構(gòu)造的表達(dá)中，是不正確的。A 結(jié)點(diǎn)除數(shù)據(jù)信息外還包括指針域，因此存儲(chǔ)密度小于順序存儲(chǔ)構(gòu)造B邏輯上相鄰的結(jié)點(diǎn)物理上不一定相鄰C可以通過計(jì)算得到第i 個(gè)結(jié)點(diǎn)的存儲(chǔ)地址D插入和刪除操作方便，不必移動(dòng)結(jié)點(diǎn) 13可以用、數(shù)據(jù)關(guān)系和根本操作定義一個(gè)完整的抽象數(shù)據(jù)

4、類型。A 數(shù)據(jù)元素B 數(shù)據(jù)對(duì)象C原子類型D存儲(chǔ)構(gòu)造應(yīng)用題 14設(shè)有數(shù)據(jù)構(gòu)造D ， R，其中 D=1 ， 2， 3， 4，5， 6 ，R=(1 ， 2)， (2， 3)，(2， 4)，(3 ， 4)，(3 ，5) ， (3， 6)， (4， 5)， (4， 6) 。試畫出其邏輯構(gòu)造圖并指出屬于何種構(gòu)造。（ 15 試描述數(shù)據(jù)構(gòu)造和抽象數(shù)據(jù)類型的概念與程序設(shè)計(jì)語言中數(shù)據(jù)類型概念的區(qū)別。（ 16 說明數(shù)據(jù)的邏輯構(gòu)造和存儲(chǔ)構(gòu)造之間的關(guān)系。（ 17 抽象數(shù)據(jù)類型的主要特點(diǎn)是什么？數(shù)據(jù)類型和抽象數(shù)據(jù)類型的關(guān)系如何？使用抽象數(shù)據(jù)類型的主要好處是什么？專業(yè)資料整理WORD格式2專業(yè)資料整理WORD格式1 算法和

5、算法分析選擇題 1算法指的是。A 對(duì)特定問題求解步驟的一種描述，是指令的有限序列B計(jì)算機(jī)程序C解決問題的計(jì)算方法D數(shù)據(jù)處理 2下面不是算法所必須具備的特性。A 有窮性B 確切性C高效性D可行性 3算法必須具備輸入、輸出和等特性。A 可行性、可移植性和可擴(kuò)大性B可行性、確定性和有窮性C確定性、穩(wěn)定性和有窮性D易讀性、穩(wěn)定性和強(qiáng)健性 4算法應(yīng)該具有確定性、可行性和有窮性，其中有窮性是指。A 算法在有窮的時(shí)間內(nèi)終止B輸入是有窮的C輸出是有窮的D描述步驟是有窮的 5當(dāng)輸入非法錯(cuò)誤時(shí)， 一個(gè) “好 的算法會(huì)進(jìn)展適當(dāng)處理，而不會(huì)產(chǎn)生難以理解的輸出結(jié)果，這稱為算法的。A 可讀性B 強(qiáng)健性C正確性D有窮性 6

6、算法分析的目的是，算法分析的兩個(gè)主要方面是。A 找出數(shù)據(jù)構(gòu)造的合理性B研究算法中輸入和輸出的關(guān)系C分析算法的效率以求改進(jìn)D分析算法的易讀性和文檔性E空間性能和時(shí)間性能F正確性和簡(jiǎn)明性G可讀性和文檔性H數(shù)據(jù)復(fù)雜性和程序復(fù)雜性 7算法的時(shí)間復(fù)雜度與有關(guān)。A 問題規(guī)模B計(jì)算機(jī)硬件性能C編譯程序的質(zhì)量D程序設(shè)計(jì)語言 8算法的時(shí)間復(fù)雜度與有關(guān)。A 問題規(guī)模B待處理數(shù)據(jù)的初態(tài)C算法的易讀性DA和B 9某算法的時(shí)間復(fù)雜度是(n2)，說明該算法。A 問題規(guī)模是 n2B執(zhí)行時(shí)間等于n2C執(zhí)行時(shí)間與 n2成正比D問題規(guī)模與 n2成正比 10下面說法錯(cuò)誤的選項(xiàng)是。專業(yè)資料整理WORD格式3專業(yè)資料整理WORD格式算

7、法原地工作的含義是指示不需要如何額外的輔助空間在一樣的規(guī)模 n 下，復(fù)雜度 (n)的算法在時(shí)間上總是優(yōu)于復(fù)雜度 (2 n)的算法所謂時(shí)間復(fù)雜度是指最壞情況下，估算算法執(zhí)行時(shí)間的一個(gè)上界同一個(gè)算法，實(shí)現(xiàn)語言的級(jí)別越高，執(zhí)行效率就越低 11算法for (i=n-1; i>=1; i-)for (j=1; j<=i; j+)if (aj>aj+1) aj 與 aj+1 交換；其中 n 為正整數(shù)，那么最后一行語句的頻度執(zhí)行次數(shù)在最壞情況下是。A (n)B (nlog 2 n)32C (n )D (n ) 12算法的時(shí)間復(fù)雜度屬于一種。A 事前統(tǒng)計(jì)的方法B事先分析估算的方法C事后統(tǒng)計(jì)的

8、方法D事后分析估算的方法 13設(shè)某算法完成對(duì) n 個(gè)元素進(jìn)展處理， 所需的時(shí)間是T(n)=100 nlog 2n+200n+500 ，那么該算法的時(shí)間復(fù)雜度是。A (1)B (n)C (nlog 2n)D (nlog 2n+n) 14假設(shè)時(shí)間復(fù)雜度為(n2)的算法在有 200 個(gè)元素的數(shù)組上運(yùn)行需要3.1ms，那么在有 400 個(gè)元素的數(shù)組上運(yùn)行需要 ms。A3.1B6.2C 12.4D x無法確定 15以下程序段加下劃線的語句執(zhí)行次。for (m=0,i=1; i<=1; i+)for (j=1; j<=2*i; j+)A n2m=m+1 ；D n3B 3nC n(n+1)應(yīng)用題

9、 16將以下函數(shù)按它們的n時(shí)的無窮大階數(shù)，從小到大排列。n， n-n3-7n5， nlog 2n， 2n/2， n3， log 2n， n1/2+log 2 n， (3/2) n，n! ，n2+log 2n 17分析以下程序段，并用大記號(hào)表示其執(zhí)行時(shí)間。i=1;k=0;else i+;while (i<n-1)for (i=1;i<=n;i+)for (j=1;j<=i;j+)k=k+10*i;for (k=1;k<=j;k+)i+;x+;i=1;k=0;i=1;j=0;dowhile (i+j<=n)if (i>j) j+;k=k+10*i;專業(yè)資料整理W

10、ORD格式4專業(yè)資料整理WORD格式i+; while (i<=n) for (i=0;i<n;i+) y=0;for (j=0;j<m;j+)while (y+1)*(y+1)<=n)aij=0;y=y+1 18有實(shí)現(xiàn)同一功能的兩個(gè)算法A1 和 A2 ，其中 A1 的時(shí)間復(fù)雜度為T 1= (2n)，2A2 的時(shí)間復(fù)雜度為 T 2= (n )，僅就時(shí)間復(fù)雜度而言，請(qǐng)具體分析這兩個(gè)算法哪一個(gè)好。綜合應(yīng)用題 19設(shè) n 是偶數(shù)，且有程序段：for (i=1;i<=n;i+)if (2*i<=n)for (j=2*I;j<=n;j+)y=y+i*j;那么語句

11、 y=y+i*j的執(zhí)行次數(shù)是多少？要求列出計(jì)算公式。 20 斐波那契數(shù)列 Fn定義如下：F0=0， F1=1 ， , ， Fn=Fn-1+Fn-2n=2， 3，,請(qǐng)就此斐波那契數(shù)列，答復(fù)以下問題。在遞歸計(jì)算Fn的時(shí)候，需要對(duì)較小的Fn-1， Fn-2，, ，F(xiàn)1， F0準(zhǔn)確計(jì)算多少次？用大表示法給出遞歸計(jì)算時(shí)遞歸函數(shù)的時(shí)間復(fù)雜度是多少？（ 21 運(yùn)算是數(shù)據(jù)構(gòu)造的一個(gè)重要方面。 舉例說明兩個(gè)數(shù)據(jù)構(gòu)造的邏輯構(gòu)造和存儲(chǔ)方式完全一樣， 只是對(duì)于運(yùn)算的定義不同， 因而具有不同的特性， 那么這兩個(gè)數(shù)據(jù)構(gòu)造是不同的。（ 22 針對(duì)給定的實(shí)際問題建立數(shù)據(jù)構(gòu)造時(shí)，應(yīng)從哪些方面考慮。專業(yè)資料整理WORD格式5專業(yè)

12、資料整理WORD格式2 線性表的邏輯構(gòu)造選擇題 1線性表是具有n 個(gè)的有限序列。A 數(shù)據(jù)B 字符C數(shù)據(jù)元素D數(shù)據(jù)項(xiàng) 2線性表是。A 一個(gè)有限序列，可以為空B一個(gè)有限序列，不能為空C一個(gè)無限序列，可以為空D一個(gè)無限序列，不能為空 3關(guān)于線性表，以下說法中正確的選項(xiàng)是。A 線性表中每個(gè)元素都有一個(gè)直接前驅(qū)和一個(gè)直接后繼B線性表中的數(shù)據(jù)元素可以具有不同的數(shù)據(jù)類型C線性表中數(shù)據(jù)元素的類型是確定的D線性表中任意一對(duì)相鄰的數(shù)據(jù)元素之間存在序偶關(guān)系 4是一個(gè)線性表。A 由 n 個(gè)實(shí)數(shù)組成的集合B由所有實(shí)數(shù)組成的集合C由所有整數(shù)組成的序列D由 n 個(gè)字符組成的序列專業(yè)資料整理WORD格式6專業(yè)資料整理WORD

13、格式3順序線性表選擇題 1一維數(shù)組 A 采用順序存儲(chǔ)構(gòu)造，每個(gè)元素占用4 個(gè)存儲(chǔ)單元，第9 個(gè)元素的地址為144，那么第一個(gè)元素的地址是。A108B180C 176D 112 2在長(zhǎng)度為 n 的線性表中查找值為x 的數(shù)據(jù)元素的時(shí)間復(fù)雜度為。A (0)B (1)C (n)D (n2) 3在一個(gè)長(zhǎng)度為 n 的線性表的第i 1 i n+1 個(gè)元素之前插入一個(gè)元素，需向后移動(dòng)個(gè)元素，刪除第i 1 i n個(gè)元素時(shí)，需向前移動(dòng)個(gè)元素。A n-iB n-i+1C n-iD n-i+1 4線性表的順序存儲(chǔ)構(gòu)造是一種的存儲(chǔ)構(gòu)造。A 隨機(jī)存取B 順序存取C索引存取D散列存取 5順序存儲(chǔ)構(gòu)造的優(yōu)點(diǎn)是。A 存儲(chǔ)密度大

14、B插入運(yùn)算方便C刪除運(yùn)算方便D可方便地用于各種邏輯構(gòu)造的存儲(chǔ)表示 6n 個(gè)結(jié)點(diǎn)的線性表采用數(shù)組實(shí)現(xiàn)，算法的時(shí)間復(fù)雜度是 (1) 的操作是 。A 訪問第 i 個(gè)結(jié)點(diǎn) 1i n和求第 i 個(gè)結(jié)點(diǎn)的直接前驅(qū)2 i nB在第 i 個(gè)結(jié)點(diǎn)后插入一個(gè)新結(jié)點(diǎn) 1 i nC刪除第i 個(gè)結(jié)點(diǎn) 1 i nD以上都不對(duì) 7對(duì)于順序存儲(chǔ)的線性表，訪問某個(gè)元素和增加一個(gè)元素的時(shí)間復(fù)雜度為。A (n)、 (n)B (n) 、 (1)C (1) 、 (n)D (1)、 (1) 8順序表的插入算法中，當(dāng)n 個(gè)空間已滿時(shí)，可再申請(qǐng)?jiān)黾臃峙鋗 個(gè)空間，假設(shè)申請(qǐng)失敗，那么說明系統(tǒng)沒有可分配的存儲(chǔ)空間。A m 個(gè)B m 個(gè)連續(xù)的C

15、n+m 個(gè)D n+m 個(gè)連續(xù)的應(yīng)用題 9設(shè) A 是一個(gè)線性表a1， a2，, ，an，采用順序存儲(chǔ)構(gòu)造，那么在等概論的前提下，平均每插入一個(gè)元素需要移動(dòng)的元素個(gè)數(shù)為多少？假設(shè)元素插在ai與 ai+1之間(1 i n)的概率為 n-i / n n-1 /2，那么平均每插入一個(gè)元素所移動(dòng)的元素個(gè)數(shù)是多少？ 10設(shè) n 表示線性表中的元素個(gè)數(shù)，E 表示存儲(chǔ)數(shù)據(jù)元素所需要的存儲(chǔ)單元大小，專業(yè)資料整理WORD格式7專業(yè)資料整理WORD格式D 表示可以在數(shù)組中存儲(chǔ)線性表的最大元素個(gè)數(shù)D n，那么使用順序存儲(chǔ)方式存儲(chǔ)線性表需要多少存儲(chǔ)空間？ 11在什么情況下線性表使用順序存儲(chǔ)比較好？算法設(shè)計(jì)題（ 12 試以

16、順序表作存儲(chǔ)構(gòu)造，實(shí)現(xiàn)線性表就地逆置。（ 13 設(shè)計(jì)算法判斷給定字符串是否是回文。所謂回文是正讀和反讀均一樣的字符串，例如 abcba 或 abba 是回文，而 abcda 不是回文。 14設(shè)計(jì)一個(gè)時(shí)間復(fù)雜度為(n)的算法，實(shí)現(xiàn)將數(shù)組An 中所有元素循環(huán)左移k個(gè)位置。 15數(shù)組An 中的元素為整型，設(shè)計(jì)算法將其調(diào)整為左右兩局部，左邊所有元素為奇數(shù)，右邊所有元素為偶數(shù)，并要求算法的時(shí)間復(fù)雜度為(n)。 16假定數(shù)組中有多個(gè)零元素，設(shè)計(jì)算法將數(shù)組中所有非零元素移到數(shù)組的前端。 17順序存儲(chǔ)的線性表A ，其數(shù)據(jù)元素為整型，設(shè)計(jì)算法將A 拆成 B 和 C 兩個(gè)表，使 A 中值大于0 的元素存入表B，值

17、小于0 的元素存入表C，要求 B 和 C 不另外設(shè)置存儲(chǔ)空間而利用A 的空間。 18順序表L 中的元素遞增有序排列，設(shè)計(jì)算法將元素x 插入到表L 中并保持表 L 仍遞增有序。 19設(shè)計(jì)一個(gè)高效算法，在順序表中刪除所有元素值為x 的元素， 要求空間復(fù)雜度為 (1) 。 20設(shè)計(jì)算法實(shí)現(xiàn)從順序表L 中刪除所有值在x 和 y 之間的所有元素，要求時(shí)間性能復(fù)雜度為(n)，空間性能為(1) 。（ 21 設(shè)計(jì)算法刪除順序表中重復(fù)的元素， 要求算法移動(dòng)元素的次數(shù)較少并使剩余元素間的相對(duì)次序保持不變。 22給定 n 個(gè)記錄的有序序列An 和 m 個(gè)記錄的有序序列Bm ，將它們歸并為一個(gè)有序序列， 存放在 Cn

18、+m 中，試寫出這一算法 假設(shè) A 、B 和 C 均為升序序列。專業(yè)資料整理WORD格式8專業(yè)資料整理WORD格式4線性鏈表選擇題 1線性表的存儲(chǔ)構(gòu)造是一種的存儲(chǔ)構(gòu)造。A 隨機(jī)存取B 順序存取C索引存取D散列存取 2線性表采用存儲(chǔ)時(shí)，其。A 地址必須是連續(xù)的B局部地址必須是連續(xù)的C地址一定是不連續(xù)的D地址連續(xù)與否均可以 3鏈表不具有的特點(diǎn)是。A 可隨機(jī)訪問任一元素B插入、刪除不需要移動(dòng)元素C不必事先估計(jì)存儲(chǔ)空間D所需空間與線性表長(zhǎng)度成正比（ 4在具有 n 個(gè)結(jié)點(diǎn)的有序單鏈表中插入一個(gè)新結(jié)點(diǎn)并仍然有序的時(shí)間復(fù)雜度是（ 。A (1)B (n)C (n2)D (nlog 2n1) 5對(duì)于 n 個(gè)元素

19、組成的線性表，建立一個(gè)單鏈表的時(shí)間復(fù)雜度是。A (1)B (n)C (n2)D (nlog 2n1) 6對(duì)于 n 個(gè)元素組成的線性表，建立一個(gè)有序單鏈表的時(shí)間復(fù)雜度是。A (1)B (n)C (n2)D (nlog 2n1) 7在單鏈表中刪除指針p 所指結(jié)點(diǎn)的后續(xù)結(jié)點(diǎn)，那么執(zhí)行。A p->next=p->next->nextB p->next=p->nextCp=p->next->nextD p=p->next; p->next=p->next->next 8在一個(gè)單鏈表中， q 所指結(jié)點(diǎn)是 p 所指結(jié)點(diǎn)的直接前驅(qū)，假設(shè)在 q

20、和 p 之間插入 s 所指結(jié)點(diǎn)，那么執(zhí)行操作。A s->next=p->next; p->next=s;B q->next=s; s->next=p;Cp->next=s->next; s->next=p;D p->next=s; s->next=q 9在一個(gè)長(zhǎng)度為 n n>1的帶頭結(jié)點(diǎn)的單鏈表h 上，另設(shè)有尾指針r 指向尾結(jié)點(diǎn)，執(zhí)行操作與鏈表的長(zhǎng)度有關(guān)。A 刪除單鏈表中的第一個(gè)元素B刪除單鏈表中的最后一個(gè)元素C在單鏈表第一個(gè)元素前插入一個(gè)新元素D在單鏈表的最后一個(gè)元素后插入一個(gè)新元素 10在單鏈表中附加頭結(jié)點(diǎn)的目的是為了。A

21、保證單鏈表中至少有一個(gè)結(jié)點(diǎn)B標(biāo)識(shí)單鏈表中首結(jié)點(diǎn)的位置C方便運(yùn)算的實(shí)現(xiàn)D說明單鏈表是線性表的鏈?zhǔn)酱鎯?chǔ)專業(yè)資料整理WORD格式9專業(yè)資料整理WORD格式 11將長(zhǎng)度為n 個(gè)單鏈表在長(zhǎng)度為m 的單鏈表之后的算法，其時(shí)間復(fù)雜度是。A (1)B (n)C (m)D (n+m) 12循環(huán)單鏈表的主要優(yōu)點(diǎn)是。A 不再需要頭指針了B從表中任一結(jié)點(diǎn)出發(fā)都能掃描到整個(gè)鏈表C某個(gè)結(jié)點(diǎn)的位置后，能夠容易找到它的直接前驅(qū)D在進(jìn)展插入、刪除操作時(shí)，能更好地保證鏈表不斷開 13 將線性表 a1， a2，, ， an組織為一個(gè)帶頭結(jié)點(diǎn)的循環(huán)單鏈表，設(shè)H 為鏈表的頭指針，那么鏈表中最后一個(gè)結(jié)點(diǎn)的指針域中存放的是。A 變量 H

22、的地址B變量 H 的值C元素 a1的地址D空指針 14 非空的循環(huán)單鏈表 L 的尾結(jié)點(diǎn)p 滿足。A p=NULLB p->next=NULLC p->next=LD p=L 15假設(shè)要在 (1) 的時(shí)間內(nèi)實(shí)現(xiàn)兩個(gè)循環(huán)單鏈表的首尾相接，那么兩個(gè)循環(huán)單鏈表應(yīng)各設(shè)一個(gè)指針，分別指向。A 各自的頭結(jié)點(diǎn)B各自的尾結(jié)點(diǎn)C各自的第一個(gè)元素結(jié)點(diǎn)D一個(gè)表的頭結(jié)點(diǎn)，一個(gè)表的尾結(jié)點(diǎn) 16設(shè)線性表非空， 可以在 (1)的時(shí)間內(nèi)在表尾插入一個(gè)新結(jié)點(diǎn)。A 帶頭結(jié)點(diǎn)的單鏈表，有一個(gè)鏈表指針指向頭結(jié)點(diǎn)B帶頭結(jié)點(diǎn)的循環(huán)單鏈表，有一個(gè)鏈表指針指向頭結(jié)點(diǎn)C不帶頭結(jié)點(diǎn)的單鏈表，有一個(gè)鏈表指針指向表的第一個(gè)結(jié)點(diǎn)D不帶頭結(jié)點(diǎn)

23、的循環(huán)單鏈表，有一個(gè)鏈表指針指向表中某個(gè)結(jié)點(diǎn)除第一個(gè)結(jié)點(diǎn)外 17設(shè)指針rear 指向帶頭結(jié)點(diǎn)的循環(huán)單鏈表的尾指針，假設(shè)要?jiǎng)h除鏈表的第一個(gè)元素結(jié)點(diǎn)，正確的操作是。A s=rear; rear=rear->next;Brear=rear->next;Crear=rear->next->next;D s=rear->next->next; rear->next->next=s->next; 18設(shè)有兩個(gè)長(zhǎng)度為n 個(gè)單鏈表， 以 h1 為頭指針的鏈表是非循環(huán)的，以 h2 為尾指針的鏈表是循環(huán)的，那么。A 在兩個(gè)鏈表上刪除第一個(gè)結(jié)點(diǎn)的操作，其時(shí)間復(fù)雜

24、度均為(1)B在兩個(gè)鏈表的表尾插入一個(gè)結(jié)點(diǎn)的操作，其時(shí)間復(fù)雜度均為(n)C循環(huán)鏈表要比非循環(huán)鏈表占用更多的存儲(chǔ)空間D循環(huán)鏈表要比非循環(huán)鏈表占用更少的存儲(chǔ)空間 19使用雙鏈表存儲(chǔ)線性表，其優(yōu)點(diǎn)是可以。專業(yè)資料整理WORD格式10專業(yè)資料整理WORD格式A 提高查找速度B更方便數(shù)據(jù)的插入和刪除C節(jié)約存儲(chǔ)空間D很快回收存儲(chǔ)空間 20 與單鏈表相比，雙鏈表的優(yōu)點(diǎn)之一是。A 插入和刪除操作更簡(jiǎn)單B可以進(jìn)展隨機(jī)訪問C可以省略表頭指針或表尾指針D訪問其后相鄰結(jié)點(diǎn)更靈活 21 帶頭結(jié)點(diǎn)的循環(huán)雙鏈表L 為空表的條件是。A L->next->prior=NULLB L->prior=LCL-&g

25、t;next=LDB和 C都對(duì) 22 在循環(huán)雙鏈表的p 所指結(jié)點(diǎn)后插入 s所指結(jié)點(diǎn)的操作是。A p->next=s; s->prior=p; p->next->prior=s; s->next=p->next;Bp->next=s; p->next->prior=s; s->prior=p; s->next=p->next;Cs->prior=p; s->next=p->next; p->next=s; p->next->prior=s;D s->prior=p; s->ne

26、xt=p->next; p->next->prior=s; p->next=s; 23 在雙鏈表中指針pa 所指結(jié)點(diǎn)后面插入 pb 所指結(jié)點(diǎn)，執(zhí)行的語句序列是 。 pb->next=pa->next;pb->prior=pa; pa->next=pb;pa->next->prior=pb;A B CD 24在一個(gè)雙鏈表中，刪除結(jié)點(diǎn)p 的操作是。A p->prior->next=p->next; p->next->prior=p->prior;Bp->prior=p->prior->

27、prior; p->prior->prior=p;Cp->next->prior=p; p->next=p->next->next;D p->next=p->prior->prior; p->prior=p->prior->prior;應(yīng)用題（ 25 單鏈表設(shè)置頭結(jié)點(diǎn)的作用是什么？（ 26 線性表的順序存儲(chǔ)構(gòu)造具有三個(gè)弱點(diǎn)：其一，插入或刪除操作需要移動(dòng)大量元素；其二， 由于難以估計(jì)， 必須預(yù)先分配較大的空間，往往使存儲(chǔ)空間不能得到充分利用；其三， 表的容量難以擴(kuò)大。 試問，線性表的存儲(chǔ)構(gòu)造是否能夠抑制上述三個(gè)弱點(diǎn)？（

28、 27假設(shè)頻繁地對(duì)一個(gè)線性表進(jìn)展插入和刪除操作，該線性表采用什么存儲(chǔ)構(gòu)造比較好？ 28設(shè) n 表示線性表中的元素個(gè)數(shù)，P 表示指針?biāo)璧拇鎯?chǔ)單元大小，E 表示存儲(chǔ)數(shù)據(jù)元素所需的存儲(chǔ)單元大小，那么使用單鏈表存儲(chǔ)方式存儲(chǔ)該線性表需要多少存儲(chǔ)空間不考慮頭結(jié)點(diǎn)？算法設(shè)計(jì)題專業(yè)資料整理WORD格式11專業(yè)資料整理WORD格式（ 29 設(shè)計(jì)算法依次打印單鏈表中每個(gè)結(jié)點(diǎn)的數(shù)據(jù)信息。（ 30 求單鏈表的長(zhǎng)度。 31設(shè)計(jì)算法將值為x 的結(jié)點(diǎn)插入到不帶頭結(jié)點(diǎn)的單鏈表L 中值為 k 的結(jié)點(diǎn)之前，假設(shè)找不到值為k 的結(jié)點(diǎn)，那么將x 插入到鏈表的末尾。 32判斷非空單鏈表是否遞增有序。 33非空線性鏈表由list 指出

29、，結(jié)點(diǎn)構(gòu)造為data， link 。請(qǐng)編寫算法，將鏈表中數(shù)據(jù)域最小的結(jié)點(diǎn)移到鏈表的最前面。要求：不得額外申請(qǐng)新的結(jié)點(diǎn)。 34給定一個(gè)帶頭結(jié)點(diǎn)的單鏈表，設(shè)head 為頭指針，設(shè)計(jì)算法按遞增次序輸出單鏈表中各結(jié)點(diǎn)的數(shù)據(jù)元素， 并釋放結(jié)點(diǎn)所占的存儲(chǔ)空間 要求： 不允許使用數(shù)組作輔助空間。 35非空線性鏈表由list 指出， 設(shè)計(jì)算法交換p 所指結(jié)點(diǎn)與其后續(xù)結(jié)點(diǎn)在鏈表中的位置設(shè)p 所指結(jié)點(diǎn)不是鏈表的最后一個(gè)結(jié)點(diǎn)。（ 36 設(shè)計(jì)算法實(shí)現(xiàn)將單鏈表就地逆置。（ 37 頭插法建立單鏈表。（ 38 尾插法建立單鏈表（ 39 復(fù)制一個(gè)單鏈表。（ 40 設(shè)計(jì)算法實(shí)現(xiàn)將單鏈表就地逆置。 41在一個(gè)有序單鏈表假設(shè)從小到

30、大排列中插入一個(gè)元素值為x 的結(jié)點(diǎn)， 使得插入后單鏈表仍然有序。（ 42 設(shè)單鏈表以非遞減有序排列，設(shè)計(jì)算法實(shí)現(xiàn)在單鏈表中刪去值一樣的多余結(jié)點(diǎn)。（ 43單鏈表中各結(jié)點(diǎn)的元素值為整型且遞增有序，設(shè)計(jì)算法刪除表中大于 mink 且小于 maxk 的所有元素，并釋放被刪結(jié)點(diǎn)的存儲(chǔ)空間。 44有兩個(gè)整數(shù)序列 A=(a1，a2，, ， am)和 B=(b1， b2，, ， bn) 已經(jīng)存入兩個(gè)單鏈表中，設(shè)計(jì)算法判斷序列 B 是否是序列 A 的子序列。（ 45 設(shè)線性表 C=(a1，b1，a2，b2，, ， an，bn)采用帶頭結(jié)點(diǎn)的單鏈表存儲(chǔ)，設(shè)計(jì)算法將表 C 拆分為兩個(gè)線性表 A 和 B ，使得 A=

31、(a 1， a2，, ， an)， B=(b 1，b2，, ，bn)。專業(yè)資料整理WORD格式12專業(yè)資料整理WORD格式（ 46 有兩個(gè)遞增有序的單鏈表la 和 lb，設(shè)計(jì)算法將這兩個(gè)單鏈表合并為一個(gè)有序鏈表。（ 47 有兩個(gè)有序的單鏈表， 一個(gè)表為升序， 另一個(gè)表為降序， 設(shè)計(jì)算法將這兩個(gè)鏈表合并為一個(gè)有序鏈表。（ 48單鏈表 A 和 B 的數(shù)據(jù)設(shè)為整型遞增有序，設(shè)計(jì)算法利用原有結(jié)點(diǎn)，將表 A 中與表 B 具有一樣值的結(jié)點(diǎn)刪除， 將表 B 中與原表 A 不同值的結(jié)點(diǎn)存入表 A 中，并保持表 A 的遞增有序。（ 49 設(shè)計(jì)算法將循環(huán)單鏈表就地逆置。（ 50 L 為單鏈表的頭結(jié)點(diǎn)地址， 表中共

32、有 m m 3個(gè)結(jié)點(diǎn)， 從表中第 i 個(gè) 1 i m結(jié)點(diǎn)起到第 m 個(gè)結(jié)點(diǎn)構(gòu)成一個(gè)局部循環(huán)鏈表。設(shè)計(jì)算法將這局部循環(huán)鏈表中所有結(jié)點(diǎn)順序完全倒置。 51假設(shè)在長(zhǎng)度大于1 的循環(huán)單鏈表中，即無頭結(jié)點(diǎn)也無頭指針，s 為指向鏈表中某個(gè)結(jié)點(diǎn)的指針，試編寫算法刪除結(jié)點(diǎn)s的前驅(qū)結(jié)點(diǎn)。（ 52 設(shè)循環(huán)單鏈表 L1 ，對(duì)其遍歷的結(jié)果是： x1， x2， x3，, ， xn-1， xn。請(qǐng)將該循環(huán)鏈表拆成兩個(gè)循環(huán)單鏈表 L1 和 L2 ，使得 L1 中含有原 L1 表中序號(hào)為奇數(shù)的結(jié)點(diǎn)且遍歷結(jié)果為： x1，x3，, ；L2 中含有原L1 表中序號(hào)為偶數(shù)的結(jié)且遍歷結(jié)果為：, ，x4， x2。（ 53一單鏈表中的數(shù)據(jù)

33、元素含有三類字符：字母、數(shù)字和其他字符。 試編寫算法，構(gòu)造三個(gè)循環(huán)單鏈表，使每個(gè)循環(huán)鏈表中只含同一類字符。 54有兩個(gè)循環(huán)鏈表tail1 和 tail2 tail1 和 tail2 分別指向循環(huán)鏈表的尾指針，編寫算法將循環(huán)鏈表tail2 到循環(huán)鏈表tail1 之后，并使后的鏈表仍是循環(huán)鏈表。（ 55 p 指向循環(huán)單鏈表最后一個(gè)結(jié)點(diǎn)的指針，試編寫只包含一個(gè)循環(huán)的算法，將線性表 a1，a2，, ， an-1，an，改造成 a1，a2，, ， an-1，an，an-1，, ， a2，a1。（ 56 判斷帶頭結(jié)點(diǎn)的循環(huán)雙鏈表是否對(duì)稱。 57設(shè)計(jì)算法實(shí)現(xiàn)雙鏈表中第i 個(gè)結(jié)點(diǎn)的前面插入一個(gè)值為x 的結(jié)點(diǎn)。

34、 58非空循環(huán)雙鏈表 head 的存儲(chǔ)構(gòu)造為：Struct DNode TElem info;Struct DNode *left;Struct DNode *right;專業(yè)資料整理WORD格式13專業(yè)資料整理WORD格式;設(shè)計(jì)算法實(shí)現(xiàn)從鏈表中刪除指針p 所指結(jié)點(diǎn)的前驅(qū)結(jié)點(diǎn)假設(shè)該結(jié)點(diǎn)存在。 59非空雙鏈表由d 指出，結(jié)點(diǎn)構(gòu)造為priordatanext ，請(qǐng)?jiān)O(shè)計(jì)算法將鏈表中數(shù)據(jù)值最大 假定唯一 的那個(gè)結(jié)點(diǎn)移至鏈表的最前面。要求不得額外申請(qǐng)新的雙鏈表結(jié)點(diǎn)。 60設(shè)計(jì)算法實(shí)現(xiàn)將雙鏈表中結(jié)點(diǎn)p 與其后繼結(jié)點(diǎn)互換位置。 61設(shè)有一個(gè)雙鏈表，每個(gè)結(jié)點(diǎn)中除了有prior 、 data 和 next 三個(gè)

35、域外，還有一個(gè)訪問頻度域freq ，在鏈表被起用之前，其值均初始化為零，每當(dāng)在雙鏈表上進(jìn)展一次 LOCATE 運(yùn)算時(shí)，令元素值為 x 的結(jié)點(diǎn)中 freq 域的值增 1，并使此鏈表中結(jié)點(diǎn)保持頻度遞減的順序排列， 以便使頻繁訪問的結(jié)點(diǎn)總是靠近表頭。 編寫算法實(shí)現(xiàn)符合上述要求的 LOCATE 算法。專業(yè)資料整理WORD格式14專業(yè)資料整理WORD格式5 靜態(tài)鏈表選擇題 1靜態(tài)鏈表中指針表示的是。A 下一結(jié)點(diǎn)在內(nèi)存中的地址B下一元素在數(shù)組中的下標(biāo)C左、右孩子的存儲(chǔ)位置D左、右孩子的地址 2以下說法錯(cuò)誤的選項(xiàng)是。靜態(tài)鏈表既有順序存儲(chǔ)的優(yōu)點(diǎn)又有動(dòng)態(tài)鏈表的優(yōu)點(diǎn)。所以，它存取表中第i 個(gè)元素的時(shí)間與 i 無關(guān)

36、靜態(tài)鏈表中能容納的元素個(gè)數(shù)在定義表時(shí)必須是確定的靜態(tài)鏈表與動(dòng)態(tài)鏈表在元素的插入、刪除上類似，不需做元素的移動(dòng)A ，B C，D 3用數(shù)組 r 存儲(chǔ)靜態(tài)鏈表， 結(jié)點(diǎn)的 next 域指向后繼， 工作指針 j 指向鏈中某結(jié)點(diǎn)，使 j 沿鏈移動(dòng)的操作為。A j=rj.nextB j=j+1Cj=j->nextD j=rj->next 4線性表的靜態(tài)鏈表存儲(chǔ)與順序存儲(chǔ)相比，優(yōu)點(diǎn)是。A 所有根本操作的算法實(shí)現(xiàn)簡(jiǎn)單B便于隨機(jī)存取C便于插入和刪除D便于利用零散的存儲(chǔ)空間 5以下列圖所示數(shù)組中以靜態(tài)鏈表形式存儲(chǔ)了一個(gè)線性表，設(shè)頭指針為a0.link ，那么該線性表的元素依次為。下標(biāo)012345678d

37、ata606340457425link4376201A 60， 63，40， 45，74， 25B 45， 63， 25， 60， 40， 74C74， 25，45， 60， 40， 63D 25，45， 60，40， 63， 74專業(yè)資料整理WORD格式15專業(yè)資料整理WORD格式6 線性表綜合選擇題 1下面關(guān)于線性表的表達(dá)中，錯(cuò)誤的選項(xiàng)是。A 線性表采用順序存儲(chǔ)，必須占用一片連續(xù)的存儲(chǔ)單元B線性表采用順序存儲(chǔ)，便于進(jìn)展插入和刪除操作C線性表采用存儲(chǔ)，不必占用一片連續(xù)的存儲(chǔ)單元D線性表采用存儲(chǔ)，便于插入和刪除操作 2假設(shè)某線性表中最常用的操作是取第i 個(gè)元素和找第i 個(gè)元素的前驅(qū)，那么采用存

38、儲(chǔ)方法最節(jié)約時(shí)間。A 順序表B 單鏈表C雙鏈表D循環(huán)單鏈表 3假設(shè)鏈表中最常用的操作是在最后一個(gè)結(jié)點(diǎn)之后插入一個(gè)結(jié)點(diǎn)和刪除第一個(gè)結(jié)點(diǎn)，那么采用存儲(chǔ)方法最節(jié)約時(shí)間。A 單鏈表B循環(huán)雙鏈表C循環(huán)單鏈表D帶尾指針的循環(huán)單鏈表 4設(shè)線性表有n 個(gè)元素，以下操作中， 在順序表上實(shí)現(xiàn)比在鏈表上實(shí)現(xiàn)的效率更高。A 輸出第i 1 i n個(gè)元素值B交換第1 個(gè)和第 2 個(gè)元素的值C順序輸出所有n 個(gè)元素D查找與給定值x 相等的元素在線性表中的序號(hào) 5如果對(duì)于具有n n 1個(gè)元素的線性表的根本操作有4 種：刪除第一個(gè)元素；刪除最后一個(gè)元素；在第一個(gè)元素前插入新元素；在最后一個(gè)元素的后面插入新元素。那么最好使用。A

39、 只設(shè)尾指針的循環(huán)單鏈表B只設(shè)尾指針的非循環(huán)單鏈表C只設(shè)頭指針的循環(huán)雙鏈表D同時(shí)設(shè)置頭指針和尾指針的循環(huán)單鏈表應(yīng)用題 6請(qǐng)比較線性表的兩種根本的存儲(chǔ)構(gòu)造順序表和單鏈表。 7舉例說明對(duì)一樣的邏輯構(gòu)造， 同一種運(yùn)算在不同的存儲(chǔ)方式下實(shí)現(xiàn)，算法的效率不同。 8如果某線性表中數(shù)據(jù)元素的類型不一致，但是希望能根據(jù)下標(biāo)隨機(jī)存取每個(gè)元素，請(qǐng)為這個(gè)線性表設(shè)計(jì)一個(gè)適宜的存儲(chǔ)構(gòu)造。 9線性鏈表有哪幾種常見的變形？各有何特點(diǎn)？專業(yè)資料整理WORD格式16專業(yè)資料整理WORD格式kk n個(gè)單詞。算法設(shè)計(jì)題（ 10 用順序表表示集合，設(shè)計(jì)算法實(shí)現(xiàn)集合的求交集運(yùn)算。（ 11 用順序表表示集合，設(shè)計(jì)算法實(shí)現(xiàn)集合的求并集運(yùn)算

40、。（ 12 用順序表表示集合，設(shè)計(jì)算法實(shí)現(xiàn)集合的求差集運(yùn)算，要求不另外開辟空間。（ 13 假定以有序表表示集合，設(shè)計(jì)算法判斷兩個(gè)給定集合是否相等。 14設(shè)兩個(gè)單鏈表L1 和 L2 分別表示兩個(gè)集合，設(shè)計(jì)算法判斷L1 是否是 L2 的子集。（ 15兩個(gè)不帶頭結(jié)點(diǎn)的單鏈表A 和 B 分別表示兩個(gè)集合，并且其元素值遞增有序，求 A 、 B 的交集 C，并以同樣的遞增形式存儲(chǔ)，要求盡可能節(jié)省時(shí)間。（ 16 在某商店的倉庫中， 對(duì)電視機(jī)按其價(jià)格從低到高建立一個(gè)單鏈表，鏈表的每個(gè)結(jié)點(diǎn)指出同樣價(jià)格的電視機(jī)的臺(tái)數(shù)?，F(xiàn)有m 臺(tái)價(jià)格為n 元的電視機(jī)入庫，請(qǐng)編寫算法完成倉庫的進(jìn)貨管理。 17從鍵盤輸入n 個(gè)英語單詞

41、，輸入格式為n， w1，w 2，, ， w n，其中 n 表示隨后輸入英語單詞個(gè)數(shù)，試編寫算法建立一個(gè)單鏈表，要求：如果單詞重復(fù)出現(xiàn)，那么只在鏈表上只保存一個(gè)；統(tǒng)計(jì)單詞重復(fù)出現(xiàn)的次數(shù)，然后輸出次數(shù)最多的前 18一元稀疏多項(xiàng)式可以采用單鏈表形式存儲(chǔ)，設(shè)計(jì)算法完成A(x)+B(x) ，其中 A(x)和 B(x) 均為稀疏的一元多項(xiàng)式，要求利用原表的存儲(chǔ)空間。 19假設(shè)用不帶頭結(jié)點(diǎn)的單鏈表表示八進(jìn)制數(shù)，例如，八進(jìn)制數(shù)536 可以表示成三個(gè)結(jié)點(diǎn)的鏈表。 要求寫一個(gè)函數(shù)Add ，該函數(shù)有兩個(gè)參數(shù)P 和 Q，分別指向表示八進(jìn)制數(shù)的鏈表，執(zhí)行函數(shù)調(diào)用Add(P,Q) 后，將返回表示八進(jìn)制數(shù)P 加八進(jìn)制數(shù)Q所

42、得結(jié)果數(shù)的鏈表。 20約瑟夫環(huán)問題：設(shè)有編號(hào)為1， 2，, ， n 的 n n 0個(gè)人圍成一個(gè)圈，每個(gè)人持有一個(gè)密碼m m 1，從第1 個(gè)人開場(chǎng)報(bào)數(shù)，報(bào)到m 時(shí)停頓報(bào)數(shù)，報(bào)m 的人出圈，再從他的下一個(gè)人起重新報(bào)數(shù)，報(bào)到m 時(shí)停頓報(bào)數(shù)，報(bào)m 的出圈， , ，如此下去，直到所有人全部出圈為止。當(dāng)任意給定n 和 m 后，設(shè)計(jì)算法求n 個(gè)人出圈的次序。 21編寫算法，完成下述要求：建立一個(gè)鏈表用于存放輸入的二進(jìn)制數(shù)，鏈表中的每個(gè)結(jié)點(diǎn)的data 域存放一個(gè)二進(jìn)制位。在此鏈表上實(shí)現(xiàn)對(duì)二進(jìn)制數(shù)加1 的運(yùn)算，并輸出運(yùn)算結(jié)果。 22有一個(gè)不帶頭結(jié)點(diǎn)的單鏈表h，通過遍歷鏈表將鏈表中所有的方向逆轉(zhuǎn)，專業(yè)資料整理WORD格式17