大連東軟數(shù)據(jù)結(jié)構(gòu)題庫(kù)

1、WORD格式1.6 習(xí)題1.6.1 知識(shí)點(diǎn)：數(shù)據(jù)構(gòu)造的定義一、選擇題1數(shù)據(jù)構(gòu)造通常是研究數(shù)據(jù)的A 及它們之間的相互聯(lián)系。A存儲(chǔ)和邏輯構(gòu)造 B存儲(chǔ)構(gòu)造 C順序構(gòu)造D鏈?zhǔn)酱鎯?chǔ)構(gòu)造2數(shù)據(jù)在計(jì)算機(jī)存儲(chǔ)器內(nèi)表示時(shí)，物理地址與邏輯地址一樣并且是連續(xù)的，稱之為C A存儲(chǔ)構(gòu)造B邏輯構(gòu)造C順序存儲(chǔ)構(gòu)造 D 鏈?zhǔn)酱鎯?chǔ)構(gòu)造3線性構(gòu)造是數(shù)據(jù)元素之間存在一種D 。A一對(duì)多關(guān)系B. 多對(duì)多關(guān)系 C 多對(duì)一關(guān)系 D 一對(duì)一關(guān)系4計(jì)算機(jī)內(nèi)部數(shù)據(jù)處理的根本單位是B 。A. 數(shù)據(jù) B數(shù)據(jù)元素C.數(shù)據(jù)項(xiàng)D 數(shù)據(jù)庫(kù)5從邏輯上可以把數(shù)據(jù)構(gòu)造分為C 兩大類?！?交通科技1996】A動(dòng)態(tài)構(gòu)造、靜態(tài)構(gòu)造B順序構(gòu)造、鏈?zhǔn)綐?gòu)造C線性構(gòu)造、非線性

2、構(gòu)造D初等構(gòu)造、構(gòu)造型構(gòu)造二、填空題1數(shù)據(jù)構(gòu)造按邏輯構(gòu)造可分為四大類，它們分別是集合、 線性、 樹(shù)、 圖 。2數(shù)據(jù)的存儲(chǔ)構(gòu)造可用四種根本的存儲(chǔ)方法表示，它們分別是順序、 鏈?zhǔn)健?散列、索引。三、判斷題（ F 1數(shù)據(jù)元素是數(shù)據(jù)的最小單位。（ T 2記錄是數(shù)據(jù)處理的最小單位。（ F 3數(shù)據(jù)的邏輯構(gòu)造是指數(shù)據(jù)的各數(shù)據(jù)項(xiàng)之間的邏輯關(guān)系。（ T 4數(shù)據(jù)的物理構(gòu)造是指數(shù)據(jù)在計(jì)算機(jī)內(nèi)的實(shí)際存儲(chǔ)形式。四、簡(jiǎn)答題1簡(jiǎn)述什么是數(shù)據(jù)構(gòu)造"2數(shù)據(jù)構(gòu)造與數(shù)據(jù)類型有什么區(qū)別" 【*工業(yè)2001】1.6.2 知識(shí)點(diǎn)：算法的概念一、選擇題1計(jì)算機(jī)算法指的是CA計(jì)算方法B 排序方法C解決問(wèn)題的有限運(yùn)算序列D

3、調(diào)度方法2算法分析的目的是 1 C ，算法分析的兩個(gè)主要方面 2A 1A 找出數(shù)據(jù)構(gòu)造的合理性B研究算法中的輸入與輸出的關(guān)系C分析算法的效率以求改進(jìn)D分析算法的易查性和文檔性 2A 空間復(fù)雜度和時(shí)間復(fù)雜度B正確性和簡(jiǎn)明性C可讀性和文檔性D數(shù)據(jù)復(fù)雜性和程序復(fù)雜性3設(shè)語(yǔ)句 X+ 的時(shí)間是單位時(shí)間，那么語(yǔ)句：for i=1;i<=n;i+x+;專業(yè)資料整理WORD格式時(shí)間復(fù)雜度為 C 。A O 1 B O n C O n2 D O n34算法的計(jì)算量的大小稱為計(jì)算的B ?！距]電 2000】A效率 B復(fù)雜性 C現(xiàn)實(shí)性 D難度5算法的時(shí)間復(fù)雜度取決于C 【中科院計(jì)算所1998】A問(wèn)題的規(guī)模 B待處

4、理數(shù)據(jù)的初態(tài) CA 和 B6下面關(guān)于算法說(shuō)法錯(cuò)誤的選項(xiàng)是A 【*理工2000】A算法最終必須由計(jì)算機(jī)程序?qū)崿F(xiàn)B為解決某問(wèn)題的算法同為該問(wèn)題編寫的程序含義是一樣的C算法的可行性是指指令不能有二義性D以上幾個(gè)都是錯(cuò)誤的7下面說(shuō)法錯(cuò)誤的選項(xiàng)是 D 【*理工2000】 1算法原地工作的含義是指不需要任何額外的輔助空間 2在一樣的規(guī)模 n 下，復(fù)雜度 O n的算法在時(shí)間上總是優(yōu)于復(fù)雜度O 2n的算法（ 3 所謂時(shí)間復(fù)雜度是指最壞情況下，估算算法執(zhí)行時(shí)間的一個(gè)上界（ 4 同一個(gè)算法，實(shí)現(xiàn)語(yǔ)言的級(jí)別越高，執(zhí)行效率就越低A 1B 1, 2C 1, 4D 38程序段 for i=n-1;i>=1;i+ f

5、or j=1;j<= i;j+if Aj>Aj+1Aj 與 Aj+1對(duì)換；其中 n 為正整數(shù)，那么最后一行的語(yǔ)句頻度在最壞情況下是D 【*理工1998】AOn BOnlog nO3 D O2nn2 C二、填空題1以?shī)A雜自然語(yǔ)言和程序語(yǔ)句的形式來(lái)描述解決問(wèn)題的方法稱為_(kāi)偽碼 _。2一個(gè)算法的效率可分為_(kāi)時(shí)間 _ 效率和 _空間 _效率3有一個(gè)程序片斷如下：for i=0;i<n;i+ x=x+1;那么其時(shí)間復(fù)雜度為：_O n _4有一個(gè)程序片斷如下：for i=0;i<n;i+ for（ j=i;j<n;j+ for k=j;k<n;k+ m=1;那么其時(shí)間復(fù)

6、雜度為：O n35有一個(gè)程序片斷如下：for i=0;i<n;i+ j=i;while j>=2 j=j/2;那么其時(shí)間復(fù)雜度為：O nlog2n三、判斷題專業(yè)資料整理WORD格式（ T 1算法的優(yōu)劣與算法描述語(yǔ)言無(wú)關(guān)，但與所用計(jì)算機(jī)有關(guān)。（ T 2強(qiáng)健的算法不會(huì)因非法的輸入數(shù)據(jù)而出現(xiàn)莫名其妙的狀態(tài)。（ F 3程序一定是算法。四、簡(jiǎn)答題專業(yè)資料整理WORD格式1如何判斷一個(gè)算法的好壞"專業(yè)資料整理WORD格式2調(diào)用以下C 函數(shù)f n答復(fù)以下問(wèn)題： 1 試指出fn值的大小，并寫出f n值的推導(dǎo)過(guò)程； 2 假定n= 5，試指出f 5值的大小和執(zhí)行f 5時(shí)的輸出結(jié)果。C 函數(shù)：

7、專業(yè)資料整理WORD格式int f int n 專業(yè)資料整理WORD格式 int i,j， k,sum= 0;專業(yè)資料整理WORD格式for i=l; i<n+1;i+專業(yè)資料整理WORD格式 for j=n;j>i-1; j-專業(yè)資料整理WORD格式for k=1;k<j+1;k+sum+; printf專業(yè)資料整理WORD格式（ "sum=%dn",sum ; return sum ; 【華中理工2000】2.7 習(xí)題2.7.1 知識(shí)點(diǎn)：線性表的邏輯構(gòu)造一、選擇題1線性表12 ,an ,以下說(shuō)法正確的選項(xiàng)是D。L= a , aA 每個(gè)元素都有一個(gè)直接前

8、驅(qū)和一個(gè)直接后繼。B線性表中至少要有一個(gè)元素。C表中諸元素的排列順序必須是由小到大或由大到小。D除第一個(gè)和最后一個(gè)元素外,其余每個(gè)元素都有一個(gè)且僅有一個(gè)直接前驅(qū)和直接后繼。2在線性表的以下運(yùn)算中，不改變數(shù)據(jù)元素之間構(gòu)造關(guān)系的運(yùn)算是D 。A 插入B 刪除C排序D 定位3線性表是具有n 個(gè) C 的有限序列n>0?！厩迦A1998】A 表元素B字符C數(shù)據(jù)元素D 數(shù)據(jù)項(xiàng)E信息項(xiàng)二、判斷題（ T 1線性表中的每個(gè)結(jié)點(diǎn)最多只有一個(gè)前驅(qū)和一個(gè)后繼。（ F 2線性表中的每個(gè)結(jié)點(diǎn)都至少有一個(gè)前驅(qū)結(jié)點(diǎn)和后繼結(jié)點(diǎn)。（ F 3線性表是 N 個(gè)數(shù)的有限序列。（ F 4同一線性表的數(shù)據(jù)元素可以具有不同的特性。 T 5

9、線性表的長(zhǎng)度n 就是表中數(shù)據(jù)元素的個(gè)數(shù)，當(dāng)n=0 時(shí)，稱為空表。（ T 6線性表是一個(gè)相當(dāng)靈活的數(shù)據(jù)構(gòu)造，它的長(zhǎng)度可根據(jù)需要增長(zhǎng)或縮短。（ F 7對(duì)線性表中的數(shù)據(jù)元素只能進(jìn)展訪問(wèn)，不能進(jìn)展插入和刪除操作。專業(yè)資料整理WORD格式2.7.2 知識(shí)點(diǎn)：線性表的順序存儲(chǔ)構(gòu)造一、選擇題1在一個(gè)長(zhǎng)度為n 的順序表中，在第i 個(gè)元素 1 <= i <=n+1 之前插入一個(gè)新元素時(shí)需向后移動(dòng)B 個(gè)元素A n-1B n-i+1C n-i-1D i2假設(shè)某線性表中最常用的操作是取第i 個(gè)元素和找第i 個(gè)元素的前趨元素，那么采用D 存儲(chǔ)方式最節(jié)省時(shí)間。A 單鏈表B雙鏈表C單向循環(huán)D 順序表3一個(gè)數(shù)組第

10、一個(gè)元素的存儲(chǔ)地址是100，每個(gè)元素的長(zhǎng)度為2，那么第 5 個(gè)元素的地址是 B A110B108C 100D 1204下述哪一條是順序存儲(chǔ)構(gòu)造的優(yōu)點(diǎn)A 。【北方交通 2001】A 存儲(chǔ)密度大B 插入運(yùn)算方便C刪除運(yùn)算方便D可方便地用于各種邏輯構(gòu)造的存儲(chǔ)表示5假設(shè)長(zhǎng)度為 n 的線性表采用順序存儲(chǔ)構(gòu)造，在其第i 個(gè)位置插入一個(gè)新元素的算法的時(shí)間復(fù)雜度為C （ 1<=i<=n+1 ?！竞娇蘸教?1999】AO0BO1CO nD O n 26對(duì)于順序存儲(chǔ)的線性表，訪問(wèn)結(jié)點(diǎn)和增加、刪除結(jié)點(diǎn)的時(shí)間復(fù)雜度為C ?！? 2000】A O n O nB O n O 1C O 1 O nDO1 O1二

11、、填空題1線性表的順序存儲(chǔ)的缺點(diǎn)是在任意位置上_插入 _數(shù)據(jù)與 _刪除 _數(shù)據(jù)費(fèi)時(shí)間。2設(shè)一線性表的順序存儲(chǔ)，總存儲(chǔ)容量為M ，其元素存儲(chǔ)位置的X圍為_(kāi)0M-1_ 。3向一個(gè)長(zhǎng)度為n 的向量中刪除第i 個(gè)元素 1 i n時(shí)，需向前移動(dòng)_n-i_ 個(gè)元素。三、簡(jiǎn)答題1線性表的存儲(chǔ)構(gòu)造為順序表，閱讀以下算法，并答復(fù)以下問(wèn)題：voidf30 SeqList *L inti， j;for i=j=0;i<L->length; i+ if L->datai>=0 if i!=j L->dataj=L->datai; j+；L->length=j; 1設(shè)線性表L=

12、 21， -7， -8， 19，0， -11，34， 30，-10，寫出執(zhí)行f30 &L 后 L 狀態(tài)； (21,19,0,34,30) 2簡(jiǎn)述算法f30 的功能。刪除順序表中小于0 的元素四、編程題專業(yè)資料整理WORD格式1順序表La中數(shù)據(jù)元素按非遞減有序排列。試寫一個(gè)算法，將x 插入到La的適宜位置上，保持該表的專業(yè)資料整理WORD格式有序性。專業(yè)資料整理WORD格式2.7.3 知識(shí)點(diǎn)：線性表的鏈?zhǔn)酱鎯?chǔ)構(gòu)造一、選擇題1鏈表是一種采用B 存儲(chǔ)構(gòu)造存儲(chǔ)的線性表。專業(yè)資料整理WORD格式A 順序B鏈?zhǔn)紺星式D網(wǎng)狀2存儲(chǔ)的存儲(chǔ)構(gòu)造所占存儲(chǔ)空間A 。A 分兩局部，一局部存放結(jié)點(diǎn)值，另一局部存

13、放表示結(jié)點(diǎn)間關(guān)系的指針。B只有一局部，存放結(jié)點(diǎn)值。C只有一局部，存儲(chǔ)表示結(jié)點(diǎn)間關(guān)系的指針。D分兩局部，一局部存放結(jié)點(diǎn)值，另一局部存放結(jié)點(diǎn)所占單元數(shù)。3線性表假設(shè)采用鏈?zhǔn)酱鎯?chǔ)構(gòu)造時(shí)，要求內(nèi)存中可用存儲(chǔ)單元的地址D 。A 必須是連續(xù)的B 局部地址必須是連續(xù)的C一定是不連續(xù)的D連續(xù)或不連續(xù)都可以4線性表在B 情況下適用于使用鏈?zhǔn)綐?gòu)造實(shí)現(xiàn)。A 需經(jīng)常修改中的結(jié)點(diǎn)值B 需不斷對(duì)進(jìn)展刪除插入C中含有大量的結(jié)點(diǎn)D 中結(jié)點(diǎn)構(gòu)造復(fù)雜5對(duì)單鏈表表示法,以下說(shuō)法錯(cuò)誤的選項(xiàng)是C。A 數(shù)據(jù)域用于存儲(chǔ)線性表的一個(gè)數(shù)據(jù)元素。B指針域或鏈域用于存放一個(gè)指向本結(jié)點(diǎn)所含數(shù)據(jù)元素的直接后繼所在結(jié)點(diǎn)的指針。C所有數(shù)據(jù)通過(guò)指針的而組織

14、成單鏈表。D NULL 稱為空指針，它不指向任何結(jié)點(diǎn)只起標(biāo)志作用。6以下說(shuō)法正確的選項(xiàng)是D。A 順序存儲(chǔ)方式的優(yōu)點(diǎn)是存儲(chǔ)密度大且插入、刪除運(yùn)算效率高B鏈表的每個(gè)結(jié)點(diǎn)中都恰好包含一個(gè)指針C線性表的順序存儲(chǔ)構(gòu)造優(yōu)于鏈?zhǔn)酱鎯?chǔ)構(gòu)造D順序存儲(chǔ)構(gòu)造屬于靜態(tài)構(gòu)造而鏈?zhǔn)綐?gòu)造屬于動(dòng)態(tài)構(gòu)造7以下說(shuō)法錯(cuò)誤的選項(xiàng)是D。A 求表長(zhǎng)、定位這兩種運(yùn)算在采用順序存儲(chǔ)構(gòu)造時(shí)實(shí)現(xiàn)的效率不比采用鏈?zhǔn)酱鎯?chǔ)構(gòu)造時(shí)實(shí)現(xiàn)的效率低B順序存儲(chǔ)的線性表可以隨機(jī)存取C由于順序存儲(chǔ)要求連續(xù)的存儲(chǔ)區(qū)域,所以在存儲(chǔ)管理上不夠靈活D線性表的鏈?zhǔn)酱鎯?chǔ)構(gòu)造優(yōu)于順序存儲(chǔ)構(gòu)造8不帶頭結(jié)點(diǎn)的單鏈表head 為空的判定條件是A 。A head= =NULLB hea

15、d->next= =NULLC head->next= =headD head!=NULL9帶頭結(jié)點(diǎn)的單鏈表head 為空的判定條件是B 。A head= =NULLB head->next= =NULL專業(yè)資料整理WORD格式C head->next= =headD head!=NULL專業(yè)資料整理WORD格式10在頭指針為head 的非空單循環(huán)鏈表中，指針p 指向尾結(jié)點(diǎn)，以下關(guān)系成立的是A 。專業(yè)資料整理WORD格式A p->next= =headB p->next->next= =head專業(yè)資料整理WORD格式C p->next= =NU

16、LLDp= =head專業(yè)資料整理WORD格式11在一個(gè)單鏈表中，q 所指結(jié)點(diǎn)是 p 所指結(jié)點(diǎn)的前驅(qū)結(jié)點(diǎn)，假設(shè)在q 和 p 之間插入s 結(jié)點(diǎn)，那么執(zhí)行語(yǔ)句C。A s->next=p->next;p->next=s;B p->next=s->next;s->next=p;C q->next=s;s->next=p;D p->next=s;s->next=q;12在一個(gè)單鏈表中，假設(shè)p 所指結(jié)點(diǎn)不是最后結(jié)點(diǎn)，在p 之后插入s 結(jié)點(diǎn)，那么應(yīng)執(zhí)行語(yǔ)句B 。A s->next=p:p->next=s;B s->next=p-&

17、gt;next;p->next=s;C s->next=p->next;p=s;D p->next=s;s->next=p;13在一個(gè)單鏈表中，假設(shè)刪除p 所指結(jié)點(diǎn)的后續(xù)結(jié)點(diǎn)，那么應(yīng)執(zhí)行語(yǔ)句A 。A p->next=p->next->next;B p=p->next;p->next=p->next->next;C p->next=p->next;D p=p->next->next;14指針 p 、 q 和 r 依次指向某循環(huán)鏈表中三個(gè)相鄰的結(jié)點(diǎn)，交換結(jié)點(diǎn)*q 和結(jié)點(diǎn) *r 在表中次序的程序段是 A。

18、A p->next=r ； q->next=r->next ； r->next=q ；B p->next=r ； r->next=q ； q->next=r->next ；C r->next=q ； q->next=r->next ； p->next=r ；D r->next=q ； p->next=r ； q->next=r->next ；15鏈表不具有的特點(diǎn)是B 【* 1998】A 插入、刪除不需要移動(dòng)元素B 可隨機(jī)訪問(wèn)任一元素C不必事先估計(jì)存儲(chǔ)空間D所需空間與線性長(zhǎng)度成正比16下面的表達(dá)不正確

19、的選項(xiàng)是BC【*理工1996】A 線性表在鏈?zhǔn)酱鎯?chǔ)時(shí)，查找第i 個(gè)元素的時(shí)間同i 的值成正比B線性表在鏈?zhǔn)酱鎯?chǔ)時(shí)，查找第i 個(gè)元素的時(shí)間同i 的值無(wú)關(guān)C線性表在順序存儲(chǔ)時(shí)，查找第i 個(gè)元素的時(shí)間同i 的值成正比D線性表在順序存儲(chǔ)時(shí)，查找第i 個(gè)元素的時(shí)間同i 的值無(wú)關(guān)17下面關(guān)于線性表的表達(dá)中，錯(cuò)誤的選項(xiàng)是哪一個(gè)？B【北方交通2001】A 線性表采用順序存儲(chǔ)，必須占用一片連續(xù)的存儲(chǔ)單元。B線性表采用順序存儲(chǔ)，便于進(jìn)展插入和刪除操作。C線性表采用存儲(chǔ)，不必占用一片連續(xù)的存儲(chǔ)單元。D線性表采用存儲(chǔ)，便于插入和刪除操作。18在一個(gè)以 h 為頭的單循環(huán)鏈中，p 指針指向鏈尾的條件是 A 【*理工199

20、8】A p->next=h B p->next=NULLC p->next->next=h D p->data=-119假設(shè)某線性表最常用的操作是存取任一指定序號(hào)的元素和在最后進(jìn)展插入和刪除運(yùn)算，那么利用A 存儲(chǔ)方式最節(jié)省時(shí)間?！?工業(yè) 2001】A 順序表 B雙鏈表 C帶頭結(jié)點(diǎn)的雙循環(huán)鏈表 D單循環(huán)鏈表20某線性表中最常用的操作是在最后一個(gè)元素之后插入一個(gè)元素和刪除第一個(gè)元素，那么采用D 存儲(chǔ)方式最節(jié)省運(yùn)算時(shí)間。 【南開(kāi) 2000】A 單鏈表 B僅有頭指針的單循環(huán)鏈表C雙鏈表 D 僅有尾指針的單循環(huán)鏈表21設(shè)一個(gè)鏈表最常用的操作是在末尾插入結(jié)點(diǎn)和刪除尾結(jié)點(diǎn)，那么

21、選用D最節(jié)省時(shí)間。 【*工業(yè) 2000】專業(yè)資料整理WORD格式A 單鏈表 22線性表B單循環(huán)鏈表C帶尾指針的單循環(huán)鏈表a1, a 2 , ,an以方式存儲(chǔ)時(shí)，訪問(wèn)第D 帶頭結(jié)點(diǎn)的雙循環(huán)鏈表 i 位置元素的時(shí)間復(fù)雜性為C 專業(yè)資料整理WORD格式【*1999】專業(yè)資料整理WORD格式A O i B O 1 C O n D O i-1 23完成在雙循環(huán)鏈表結(jié)點(diǎn)p 之后插入s 的操作是 D ?！颈狈浇煌ˋ p->next:=s ; s->priou:=p; p->next->priou:=s ; s->next:=p->next;B p->next->

22、;priou:=s; p->next:=s; s->priou:=p; s->next:=p->next;C s->priou:=p; s->next:=p->next; p->next:=s; p->next->priou:=s ;D s->priou:=p; s->next:=p->next; p->next->priou:=s ; p->next:=s;1999】專業(yè)資料整理WORD格式24在雙向循環(huán)鏈表中【郵電1998】【*,在 p 指針?biāo)赶虻慕Y(jié)點(diǎn)前插入一個(gè)指針2000】注 :雙向鏈表的結(jié)

23、點(diǎn)構(gòu)造為q 所指向的新結(jié)點(diǎn),其修改指針的操作是llink,data,rlink 。 供選擇的答案：C。專業(yè)資料整理WORD格式A p->llink=q；q->rlink=p；p->llink->rlink=q；q->llink=q；專業(yè)資料整理WORD格式Bp->llink=q；p->llink->rlink=q；q->rlink= p；q->llink=p->llink；專業(yè)資料整理WORD格式Cq->rlink=p；q->llink=p->llink；p->llink->rlink=q; p-&

24、gt;llink=q;專業(yè)資料整理WORD格式Dq->llink=p->llink； q->rlink:=p；p->llink=q； p->llink=q；專業(yè)資料整理WORD格式25在雙向鏈表存儲(chǔ)構(gòu)造中，刪除p 所指的結(jié)點(diǎn)時(shí)需修改指針A p->prior->next=p->nextp->next->prior=p->prior;B p->prior =p-> prior-> priorp-> prior-> next=p;C p-> prior-> prior:=pp-> nex

25、t=p-> next -> nextD p-> next = p-> prior -> priorp-> prior=p-> next-> nextA ?！?電子科技1998】專業(yè)資料整理WORD格式二、填空題專業(yè)資料整理WORD格式1線性表的鏈?zhǔn)酱鎯?chǔ)是用_malloc_ 語(yǔ)句實(shí)現(xiàn)空間單元?jiǎng)討B(tài)分配。專業(yè)資料整理WORD格式2單鏈表是_線性表 _的存儲(chǔ)表示。專業(yè)資料整理WORD格式3頭結(jié)點(diǎn)地址指針為L(zhǎng) 的循環(huán)單鏈表，空表的判別標(biāo)志是_L->next=NULL_。專業(yè)資料整理WORD格式4在一個(gè)單鏈表中刪除p 所指結(jié)點(diǎn)時(shí)，應(yīng)執(zhí)行以下操作：q=p

26、->next;p-專業(yè)資料整理WORD格式>data=p->next->data;p->next=q->next_;free q;專業(yè)資料整理WORD格式5下段程序的功能：有一頭指針為head 的鏈表 ,將new 指針指向的節(jié)點(diǎn)插入到data 域?yàn)? 的節(jié)點(diǎn)的后邊。專業(yè)資料整理WORD格式將程序補(bǔ)充完整。P = head;專業(yè)資料整理WORD格式while P != NULL專業(yè)資料整理WORD格式 if P ->data = 7專業(yè)資料整理WORD格式/* 找到位置插入結(jié)點(diǎn)后跳出循環(huán)*/專業(yè)資料整理WORD格式 1 _new->next=p-&

27、gt;next_;專業(yè)資料整理WORD格式 2 _p->next=new_; _break_ ; else 3 專業(yè)資料整理WORD格式 4 _p=p->next_; /* 指針后移 */if P = NULL 專業(yè)資料整理WORD格式printfn the position isntexist!;專業(yè)資料整理WORD格式6假設(shè)某個(gè)不設(shè)頭指針的無(wú)頭結(jié)點(diǎn)單向循環(huán)鏈表的長(zhǎng)度大于 1， s 為指向鏈表中某個(gè)結(jié)點(diǎn)的指針。算法的功能是，刪除并返回鏈表中指針 s 所指結(jié)點(diǎn)的前驅(qū)。請(qǐng)?jiān)诳杖碧幪钊脒m宜的內(nèi)容，使其成為完整的算法。f 30專業(yè)資料整理WORD格式typedef struct node

28、 DataType data；struct專業(yè)資料整理WORD格式node *next ； *LinkList；專業(yè)資料整理WORD格式DataType f 30 LinkList s 專業(yè)資料整理WORD格式LinkList pre ， p；DataType e ；while 1 _p->next!=s_pre=s ； pre=p;p=s->next；專業(yè)資料整理WORD格式 2 p=p->next_ ;pre ->next= 3_p->next_ ; e=p->data; free p ; return e;專業(yè)資料整理WORD格式三、判斷題（ F 1單

29、鏈表從任何一個(gè)結(jié)點(diǎn)出發(fā)，都能訪問(wèn)到所有結(jié)點(diǎn)。（ F 2線性表的每個(gè)結(jié)點(diǎn)只能是一個(gè)簡(jiǎn)單類型，而鏈表的每個(gè)結(jié)點(diǎn)可以是一個(gè)復(fù)雜類型。四、簡(jiǎn)答題1描述以下幾個(gè)概念：順序存儲(chǔ)構(gòu)造、鏈?zhǔn)酱鎯?chǔ)構(gòu)造、順序表、有序表。2描述以下三個(gè)概念的區(qū)別：頭指針、頭結(jié)點(diǎn)、首元結(jié)點(diǎn)。在單鏈表中設(shè)置頭結(jié)點(diǎn)的作用是什么？3線性表有兩種存儲(chǔ)構(gòu)造：一是順序表，二是鏈表，試問(wèn)：(1) 如果有 n 個(gè)線性表同時(shí)共存，并且在處理過(guò)程中各表的長(zhǎng)度會(huì)動(dòng)態(tài)地發(fā)生變化，線性表的總數(shù)也會(huì)自動(dòng)地改變。在此情況下，應(yīng)選用哪種存儲(chǔ)構(gòu)造？為什么？鏈表(2) 假設(shè)線性表的總數(shù)根本穩(wěn)定，且很少進(jìn)展插入和刪除，但要求以最快的速度存取線性表中的元素，那么應(yīng)采用哪種

30、存取構(gòu)造？為什么？順序表4假設(shè)本測(cè)試中使用的鏈表如圖2.45 所示，結(jié)點(diǎn)定義如下：struct List int data;struct List *next;typedef struct List Node;typedef Node *Link;Link P,Q,R,S,head;Link pointer,back,new;對(duì)以下單鏈表分別執(zhí)行以下程序段，要求分別畫出結(jié)果圖。（ 1 Q=head->next->next;Q指向7（ 2 R->data=P->data;專業(yè)資料整理WORD格式3 變 5（ 3 R->data=P->next->data

31、;3 變 7 4S=P;while S->next!=NULL S->data=S->data*2; S=S->next; 4 101468 5S=P;while S!=NULL S->data=S->data*2; S=S->next; 4 10146165假設(shè)本測(cè)試中使用的鏈表如圖 2.45 所示，結(jié)點(diǎn)定義如第 4 題所示。畫出執(zhí)行如下程序段后各指針及鏈表的示意圖。head= Link malloc sizeof Node ; head->data=0; head-專業(yè)資料整理WORD格式>next=NULL; P=head; for

32、i=1;i<4;i+專業(yè)資料整理WORD格式 new= Link malloc sizeof Node ; new->next=NULL;new->data=2*i;專業(yè)資料整理WORD格式P->next=new;P=new;專業(yè)資料整理WORD格式創(chuàng)立了一個(gè)鏈表，數(shù)據(jù)元素為0,2,4,6，并且p 和new 都指向尾結(jié)點(diǎn)專業(yè)資料整理WORD格式6有一鏈表如以下列圖所示，閱讀程序給出程序的輸出結(jié)果。圖 2.46 6 題圖P = head;while P != NULL printf n data=%d , P-> data ; P = P->next; if

33、P != NULL P = P ->next;Data=1Data=3Data=5五、編程題專業(yè)資料整理WORD格式1一個(gè)單鏈表，其頭指針為head，編寫一個(gè)函數(shù)計(jì)算數(shù)據(jù)域?yàn)閤專業(yè)資料整理WORD格式的節(jié)點(diǎn)個(gè)數(shù)。專業(yè)資料整理WORD格式2單鏈表La 中數(shù)據(jù)元素按非遞減有序排列。按兩種不同情況，分別寫出算法，將元素x 插入到La的合專業(yè)資料整理WORD格式適位置上，保持該表的有序性： 1La 帶頭結(jié)點(diǎn)；2 La 不帶頭結(jié)點(diǎn)。專業(yè)資料整理WORD格式3試寫一個(gè)算法，實(shí)現(xiàn)順序表的就地逆置，即在原表的存儲(chǔ)空間將線性表n- 1,a n逆置為 an ,aa1,a 2 , ,an- 1, a2 ,a1

34、。4設(shè)計(jì)一個(gè)算法，求A 和 B 兩個(gè)單鏈表表示的集合的交集、并集合差集。3.7 習(xí)題3.7.1 知識(shí)點(diǎn)：棧的根本概念一、選擇題1以下哪種數(shù)據(jù)構(gòu)造常用于函數(shù)調(diào)用A。棧隊(duì)列鏈表數(shù)組2編譯器中通常以哪種數(shù)據(jù)構(gòu)造處理遞歸程序調(diào)用C 隊(duì)列數(shù)組C棧D 記錄3以下哪些數(shù)據(jù)構(gòu)造可用來(lái)實(shí)現(xiàn)棧D。 1鏈表 2數(shù)組 3樹(shù) 4圖 2， 32， 4C 1， 4D 1， 24元素的入棧序列是a,b,c,d，那么棧的不可能的輸出序列是C 。A dcbaB abcdC dcabD cbad5棧的最大容量為4。假設(shè)進(jìn)棧序列為1，2， 3， 4，5， 6，且進(jìn)棧和出?？梢源┎暹M(jìn)展,那么可能出現(xiàn)的出棧序列為C。A 5， 4，3，

35、2， 1，6B2， 3，5，6，1，4C 3， 2， 5，4， 1， 6D 1， 4，6， 5， 2，36假設(shè)以 S 和 X 分別表示進(jìn)棧和退棧操作，那么對(duì)初始狀態(tài)為空的?？梢赃M(jìn)展的棧操作系列是D 。A SXSS* B S*SXSSXC SXS*SSXD SSS*S*7對(duì)于棧操作數(shù)據(jù)的原那么是B ?！? 2001】A 先進(jìn)先出B 后進(jìn)先出C 后進(jìn)后出D不分順序8棧在 D 中應(yīng)用?！? 1998】A 遞歸調(diào)用B子程序調(diào)用C表達(dá)式求值D A ，9一個(gè)棧的輸入序列為123 n，假設(shè)輸出序列的第一個(gè)元素是n，輸出第i 1<=i<=n 個(gè)元素是 B ?！?1999】A 不確定B n-i+1C

36、 iD n-i10假設(shè)一個(gè)棧的輸入序列為1,2,3,，,n輸出序列的第一個(gè)元素是i ，那么第 j 個(gè)輸出元素是 D ?！?2000】A i-j-1B i-jC j-i+1D 不確定的11有六個(gè)元素6， 5， 4， 3， 2， 1 的順序進(jìn)棧，問(wèn)以下哪一個(gè)不是合法的出棧序列？C 【北方交通2001】A543612 B453162C346521 D23415612輸入序列為ABC ，可以變?yōu)镃BA 時(shí)，經(jīng)過(guò)的棧操作為B 【* 1999】A push,pop,push,pop,push,popBpush,push,push,pop,pop,popC push,push,pop,pop,push,po

37、pDpush,pop,push,push,pop,pop13設(shè)計(jì)一個(gè)判別表達(dá)式中左，右括號(hào)是否配對(duì)出現(xiàn)的算法，采用D 數(shù)據(jù)構(gòu)造最正確。 【*電子科技1996】專業(yè)資料整理WORD格式A 線性表的順序存儲(chǔ)構(gòu)造B隊(duì)列 C線性表的鏈?zhǔn)酱鎯?chǔ)構(gòu)造D 棧二、填空題1棧是一種特殊的線性表，允許插入和刪除運(yùn)算的一端稱為棧頂 ，不允許插入和刪除運(yùn)算的一端稱為棧底 。2對(duì)于順序存儲(chǔ)的棧，因?yàn)闂５目臻g是有限的，在進(jìn)展入棧運(yùn)算時(shí)，可能發(fā)生棧的上溢，在進(jìn)展出棧運(yùn)算時(shí)，可能發(fā)生棧的下溢。3表達(dá)式求值是棧應(yīng)用的一個(gè)典型例子。4棧是 _一種特殊 _的線性表，其運(yùn)算遵循_先進(jìn)后出 _的原那么。【科技 1997】5設(shè)有一個(gè)空棧，

38、棧頂指針為1000H 十六進(jìn)制 ， 現(xiàn)有輸入序列為1，2，3，4，5，經(jīng)過(guò) PUSH,PUSH,POP,PUSH,POP,PUSH,PUSH 之后，輸出序列是2,3， _ ，而棧頂指針值是_1000C_H 。設(shè)棧為順序棧，每個(gè)元素占4 個(gè)字節(jié)。【*電子科技1998】6用 S 表示入棧操作，X 表示出棧操作，假設(shè)元素入棧的順序?yàn)?234，為了得到 1342 出棧順序，相應(yīng)的S 和X 的操作串為 _sxssxs*_ ?！疚髂辖煌?000】三、判斷題（ F 1棧具有先進(jìn)先出的特性。（ T 2棧用于實(shí)現(xiàn)子程序調(diào)用。（ F 3棧和鏈表是兩種不同的數(shù)據(jù)構(gòu)造。（ T 4棧頂?shù)奈恢檬请S著操作而變化的。（ T

39、5棧和隊(duì)列邏輯上都是線性表。 T 6棧是實(shí)現(xiàn)過(guò)程和函數(shù)等子程序所必需的構(gòu)造?！?工業(yè)2000】（ F 7即使對(duì)不含一樣元素的同一輸入序列進(jìn)展兩組不同的合法的入棧和出棧組合操作，所得的輸出序列也一定一樣?！距]電 1999】 T 8假設(shè)輸入序列為1,2,3,4,5,6,那么通過(guò)一個(gè)?？梢暂敵鲂蛄?,2,5,6,4,1?！?海運(yùn)1995】 F 9假設(shè)輸入序列為1， 2， 3， 4， 5， 6，那么通過(guò)一個(gè)?？梢暂敵鲂蛄?， 5， 4， 6， 2， 3。【*海運(yùn)1999】四、簡(jiǎn)答題1什么是棧？試舉兩個(gè)應(yīng)用實(shí)例。2簡(jiǎn)述棧和線性表的差異。3計(jì)算表達(dá)式6*3/2-5*1 ，要求繪出堆棧的處理過(guò)程。5有 5

40、個(gè)元素，其入棧次序?yàn)椋篈 ， B， C， D ，E，在各種可能的出棧次序中，以元素C，D 最先出棧專業(yè)資料整理WORD格式即C 第一個(gè)且D 第二個(gè)出棧的次序有哪幾個(gè)？【西南交通2000】專業(yè)資料整理WORD格式3.7.2 知識(shí)點(diǎn)：棧的存儲(chǔ)一、選擇題1如果以鏈表作為棧的存儲(chǔ)構(gòu)造，那么入棧操作時(shí)B 。A 必須判別棧是否滿B對(duì)棧不作任何判別C必須判別棧是否空D 判別棧元素的類型2上溢現(xiàn)象通常出現(xiàn)在A 。A 順序棧的入棧操作過(guò)程中B 順序棧的出棧操作過(guò)程中C鏈棧的入棧操作過(guò)程中D 鏈棧的出棧操作過(guò)程中3判定一個(gè)棧ST最多元素為m0為空的條件是B 專業(yè)資料整理WORD格式 ST->top！ =0

41、ST->top= =0 ST->top！ =m0 ST->top= =m04鏈表仿真堆棧時(shí)，棧空的條件是B 。A top<maxsize-1B top= =NULLC 沒(méi)有限制D top<05鏈表仿真堆棧時(shí)，棧滿的條件是C。A top<maxsize-1B top= =NULLC 沒(méi)有限制D top<06在用鏈表仿真堆棧時(shí)假設(shè)stack 為棧頂指針，將new 指針指向的節(jié)點(diǎn)執(zhí)行入棧操作應(yīng)執(zhí)行B new->next=stack->next ； stack=new； new->next=stack ； stack=new； new->

42、;next=stack ； stack=new->next ； stack=new ； stack->next=new->next ；7假設(shè)一個(gè)棧以向量V1 n 存儲(chǔ)，初始棧頂指針top 為 n+1 ，那么下面x 進(jìn)棧的正確操作是C ?！?理工1998 】專業(yè)資料整理WORD格式A top=top+1; V top=x C top=top-1; V top=xB V top =x; top=top+1 D V top=x; top=top-1專業(yè)資料整理WORD格式8執(zhí)行完以下語(yǔ)句段后，i 值為： B ?！? 2000】 int f int x return x>0 " x* f x-1 :2 ; int i ;i =f f 1 ;A2B4C8D無(wú)限遞歸二、填空題1以下語(yǔ)句是堆棧的入棧操作，用全局?jǐn)?shù)組