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

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ù)庫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)造可分為四大類，它們分別是集合、 線性、 樹、 圖 。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解決問題的有限運(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è)語句 X+ 的時(shí)間是單位時(shí)間，那么語句：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問題的規(guī)模 B待處

4、理數(shù)據(jù)的初態(tài) CA 和 B6下面關(guān)于算法說法錯(cuò)誤的選項(xiàng)是A 【*理工2000】A算法最終必須由計(jì)算機(jī)程序?qū)崿F(xiàn)B為解決某問題的算法同為該問題編寫的程序含義是一樣的C算法的可行性是指指令不能有二義性D以上幾個(gè)都是錯(cuò)誤的7下面說法錯(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)語言的級(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ù)，那么最后一行的語句頻度在最壞情況下是D 【*理工1998】AOn BOnlog nO3 D O2nn2 C二、填空題1以夾雜自然語言和程序語句的形式來描述解決問題的方法稱為_偽碼 _。2一個(gè)算法的效率可分為_時(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)劣與算法描述語言無關(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ù)以下問題： 1 試指出fn值的大小，并寫出f n值的推導(dǎo)過程； 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 ,以下說法正確的選項(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)展訪問，不能進(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ǔ)的線性表，訪問結(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圍為_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ù)以下問題：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ì)單鏈表表示法,以下說法錯(cuò)誤的選項(xiàng)是C。A 數(shù)據(jù)域用于存儲(chǔ)線性表的一個(gè)數(shù)據(jù)元素。B指針域或鏈域用于存放一個(gè)指向本結(jié)點(diǎn)所含數(shù)據(jù)元素的直接后繼所在結(jié)點(diǎn)的指針。C所有數(shù)據(jù)通過指針的而組織

14、成單鏈表。D NULL 稱為空指針，它不指向任何結(jié)點(diǎn)只起標(biāo)志作用。6以下說法正確的選項(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以下說法錯(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í)行語句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í)行語句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í)行語句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ī)訪問任一元素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 的值無關(guān)C線性表在順序存儲(chǔ)時(shí)，查找第i 個(gè)元素的時(shí)間同i 的值成正比D線性表在順序存儲(chǔ)時(shí)，查找第i 個(gè)元素的時(shí)間同i 的值無關(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í)間。 【南開 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í)，訪問第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_ 語句實(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è)頭指針的無頭結(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ā)，都能訪問到所有結(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)造：一是順序表，二是鏈表，試問：(1) 如果有 n 個(gè)線性表同時(shí)共存，并且在處理過程中各表的長(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)造可用來實(shí)現(xiàn)棧D。 1鏈表 2數(shù)組 3樹 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)棧和出棧可以穿插進(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)為空的棧可以進(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)棧，問以下哪一個(gè)不是合法的出棧序列？C 【北方交通2001】A543612 B453162C346521 D23415612輸入序列為ABC ，可以變?yōu)镃BA 時(shí)，經(jīng)過的棧操作為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)過 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)過程和函數(shù)等子程序所必需的構(gòu)造。【*工業(yè)2000】（ F 7即使對(duì)不含一樣元素的同一輸入序列進(jìn)展兩組不同的合法的入棧和出棧組合操作，所得的輸出序列也一定一樣?！距]電 1999】 T 8假設(shè)輸入序列為1,2,3,4,5,6,那么通過一個(gè)?？梢暂敵鲂蛄?,2,5,6,4,1?！?海運(yùn)1995】 F 9假設(shè)輸入序列為1， 2， 3， 4， 5， 6，那么通過一個(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 ，要求繪出堆棧的處理過程。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 順序棧的入棧操作過程中B 順序棧的出棧操作過程中C鏈棧的入棧操作過程中D 鏈棧的出棧操作過程中3判定一個(gè)棧ST最多元素為m0為空的條件是B 專業(yè)資料整理WORD格式 ST->top！ =0

41、ST->top= =0 ST->top！ =m0 ST->top= =m04鏈表仿真堆棧時(shí)，?？盏臈l件是B 。A top<maxsize-1B top= =NULLC 沒有限制D top<05鏈表仿真堆棧時(shí)，棧滿的條件是C。A top<maxsize-1B top= =NULLC 沒有限制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í)行完以下語句段后，i 值為： B 。【* 2000】 int f int x return x>0 " x* f x-1 :2 ; int i ;i =f f 1 ;A2B4C8D無限遞歸二、填空題1以下語句是堆棧的入棧操作，用全局?jǐn)?shù)組