




版權(quán)說明:本文檔由用戶提供并上傳,收益歸屬內(nèi)容提供方,若內(nèi)容存在侵權(quán),請進行舉報或認領(lǐng)
文檔簡介
1、1 緒論一、選擇題:1、下列算法的時間復雜度是( ) for(i=0;i<n;i+ +) ci=i; AO(1) BO(n) CO(log2n) DO(nlog2n)2、數(shù)據(jù)在計算機存儲器內(nèi)表示時,根據(jù)結(jié)點的關(guān)鍵字直接計算出該結(jié)點的存儲地址,這種方法稱為( ) A索引存儲方法 B順序存儲方法 C鏈式存儲方法 D散列存儲方法 解析: 數(shù)據(jù)結(jié)構(gòu)在計算機中的表示(映像)稱為數(shù)據(jù)的物理(存儲)結(jié)構(gòu)。它包括數(shù)據(jù)元素的表示和關(guān)系的表示。數(shù)據(jù)元素之間的關(guān)系有兩種不同的表示方法:順序映象和非順序映象,并由此得到兩種不同的存儲結(jié)構(gòu):順序存儲結(jié)構(gòu)和鏈式存儲結(jié)構(gòu)。順序存儲方法:它是把邏輯上相鄰的結(jié)點存儲在物理
2、位置相鄰的存儲單元里,結(jié)點間的邏輯關(guān)系由存儲單元的鄰接關(guān)系來體現(xiàn),由此得到的存儲表示稱為順序存儲結(jié)構(gòu)。順序存儲結(jié)構(gòu)是一種最基本的存儲表示方法,通常借助于程序設(shè)計語言中的數(shù)組來實現(xiàn)。鏈式存儲方法:它不要求邏輯上相鄰的結(jié)點在物理位置上亦相鄰,結(jié)點間的邏輯關(guān)系是由附加的指針字段表示的。由此得到的存儲表示稱為鏈式存儲結(jié)構(gòu),鏈式存儲結(jié)構(gòu)通常借助于程序設(shè)計語言中的指針類型來實現(xiàn)。索引存儲方法:除建立存儲結(jié)點信息外,還建立附加的索引表來標識結(jié)點的地址。散列存儲方法:就是根據(jù)結(jié)點的關(guān)鍵字直接計算出該結(jié)點的存儲地址。數(shù)據(jù)結(jié)構(gòu)中,邏輯上(邏輯結(jié)構(gòu):數(shù)據(jù)元素之間的邏輯關(guān)系)可以把數(shù)據(jù)結(jié)構(gòu)分成線性結(jié)構(gòu)和非線性結(jié)構(gòu)。線
3、性結(jié)構(gòu)的順序存儲結(jié)構(gòu)是一種隨機存取的存儲結(jié)構(gòu),線性表的鏈式存儲結(jié)構(gòu)是一種順序存取的存儲結(jié)構(gòu)。線性表若采用鏈式存儲表示時所有結(jié)點之間的存儲單元地址可連續(xù)可不連續(xù)。邏輯結(jié)構(gòu)與數(shù)據(jù)元素本身的形式、內(nèi)容、相對位置、所含結(jié)點個數(shù)都無關(guān)。3、以下哪一個術(shù)語與數(shù)據(jù)的存儲結(jié)構(gòu)無關(guān)?( )。A.順序表 B.鏈表C.散列表 D.隊列4、算法在發(fā)生非法操作時可以做出處理的特性稱為( )。A正確性B易讀性C健壯性D高效性5、邏輯結(jié)構(gòu)是指數(shù)據(jù)元素的( )。A關(guān)聯(lián)方式 B存儲方式C結(jié)構(gòu)D數(shù)據(jù)項6、研究數(shù)據(jù)結(jié)構(gòu)就是研究( )。A數(shù)據(jù)的邏輯結(jié)構(gòu)B數(shù)據(jù)的存儲結(jié)構(gòu)C數(shù)據(jù)的邏輯結(jié)構(gòu)和存儲結(jié)構(gòu)D數(shù)據(jù)的邏輯結(jié)構(gòu)、存儲結(jié)構(gòu)及其數(shù)據(jù)的運算
4、7、從邏輯上可以把數(shù)據(jù)結(jié)構(gòu)分為( )。A.動態(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.內(nèi)部結(jié)構(gòu)和外部結(jié)構(gòu)8、以下有關(guān)數(shù)據(jù)的敘述中錯誤的是( )。A計算機能夠處理的數(shù)據(jù)包括整數(shù)、實數(shù)、字符、聲音、圖像等B數(shù)據(jù)的邏輯結(jié)構(gòu)是從邏輯關(guān)系上描述數(shù)據(jù),它取決于數(shù)據(jù)的存儲方式C數(shù)據(jù)存儲結(jié)構(gòu)的實現(xiàn)依賴于計算機語言D數(shù)據(jù)的運算是定義在數(shù)據(jù)的邏輯結(jié)構(gòu)上的9、數(shù)據(jù)的基本單位是( )。A.數(shù)據(jù)結(jié)構(gòu) B.數(shù)據(jù)元素C.數(shù)據(jù)項 D.文件10、下列算法的時間復雜度是( ) for(i=0;i<m;i+ +) for(j=0;j<n;j+ +) aij=i*j; AO(m2) BO(n
5、2) CO(m×n) DO(m+n)11、算法分析的兩個主要方面是( )。A正確性和簡明性 B數(shù)據(jù)復雜性和程序復雜性C可讀性和可維護性D時間復雜性和空間復雜性二、填空題:1、數(shù)據(jù)結(jié)構(gòu)是相互之間存在一種或多種特定關(guān)系的數(shù)據(jù)元素的集合,它包括三方面的內(nèi)容,分別是數(shù)據(jù)的邏輯結(jié)構(gòu)、( )和( )。2、數(shù)據(jù)的邏輯結(jié)構(gòu)是從邏輯關(guān)系上描述數(shù)據(jù),它與數(shù)據(jù)的()無關(guān),是獨立于計算機的。3、( )結(jié)構(gòu)與數(shù)據(jù)元素本身的內(nèi)容和形式無關(guān)。 4、程序段“for(i=1;i<=n;i+) k+; for(j=1;j<=n;j+) x=x+k;”的時間復雜度為( )。5、數(shù)據(jù)的存儲結(jié)構(gòu)(物理結(jié)構(gòu))可以用
6、( )、( )、( )及散列存儲等四種存儲方法表示。三、 判斷題:1、順序存儲方式優(yōu)點是存儲密度大,且插入和刪除運算效率高。 ( )2、順序存儲結(jié)構(gòu)屬于靜態(tài)存儲結(jié)構(gòu),鏈式存儲結(jié)構(gòu)屬于動態(tài)存儲結(jié)構(gòu)。 ( )3、線性表的鏈接存儲,表中元素的邏輯順序與物理順序一定相同。 ( )4、數(shù)據(jù)的機內(nèi)表示稱為數(shù)據(jù)的存儲結(jié)構(gòu)。 ( )5、在線性表的順序存儲結(jié)構(gòu)中,邏輯上相鄰的兩個元素在物理位置上并不一定相鄰。( )6、數(shù)據(jù)元素是數(shù)據(jù)的最小單位。 ( )7、基于某種邏輯結(jié)構(gòu)之上的運算,其實現(xiàn)是惟一的。 ( )參考答案(緒論)一、選擇題1234567891011BDDCADCBACD二、填空題1、數(shù)據(jù)結(jié)構(gòu)是相互之間
7、存在一種或多種特定關(guān)系的數(shù)據(jù)元素的集合,它包括三方面的內(nèi)容,分別是數(shù)據(jù)的邏輯結(jié)構(gòu)、(存儲結(jié)構(gòu))和(運算)。2、數(shù)據(jù)的邏輯結(jié)構(gòu)是從邏輯關(guān)系上描述數(shù)據(jù),它與數(shù)據(jù)的()無關(guān),是獨立于計算機的。3、(邏輯)結(jié)構(gòu)與數(shù)據(jù)元素本身的內(nèi)容和形式無關(guān)。 4、程序段“for(i=1;i<=n;i+) k+; for(j=1;j<=n;j+) x=x+k;”的時間復雜度為(O(n2)。5、數(shù)據(jù)的存儲結(jié)構(gòu)(物理結(jié)構(gòu))可以用(順序)、(鏈式)、(索引)及散列存儲等四種存儲方法表示。三、判斷題1、順序存儲方式優(yōu)點是存儲密度大,且插入和刪除運算效率高。 (×)2、順序存儲結(jié)構(gòu)屬于靜態(tài)存儲結(jié)構(gòu),鏈式存儲
8、結(jié)構(gòu)屬于動態(tài)存儲結(jié)構(gòu)。 (×)3、線性表的鏈接存儲,表中元素的邏輯順序與物理順序一定相同。 ( )4、數(shù)據(jù)的機內(nèi)表示稱為數(shù)據(jù)的存儲結(jié)構(gòu)。 ()5、在線性表的順序存儲結(jié)構(gòu)中,邏輯上相鄰的兩個元素在物理位置上并不一定相鄰。(×) 6、數(shù)據(jù)元素是數(shù)據(jù)的最小單位。 (×)7、基于某種邏輯結(jié)構(gòu)之上的運算,其實現(xiàn)是惟一的。 (×)2 線性表一、 選擇題:1、在表長為n的順序表上做插入運算,平均要移動的結(jié)點數(shù)為( )。 An Bn/2 Cn/3 Dn/42、在一個單鏈表中,若P所指結(jié)點不是最后結(jié)點,在P之后插入S所指結(jié)點,則執(zhí)行( ) AS->next=P-&g
9、t;next;P->next=S BP->next=S->next;S->next=P; CP->next=P;P->next=S; DP->next=S;S->next=P;3、在已知頭指針的單鏈表中,要在其尾部插入一新結(jié)點,其算法所需的時間復雜度為( ) A(1) B(log2n) CO(n) DO(n2) 解析:單就插入運算而言,算法時間復雜度為(1),但要將指針定位到鏈表末尾,指針移動的時間復雜度為O(n);4、對于只在表的首、尾兩端進行插入操作的線性表,宜采用的存儲結(jié)構(gòu)為( ) A順序表 B用頭指針表示的單循環(huán)鏈表 C用尾指針表示的單循
10、環(huán)鏈表 D單鏈表 解析:尾指針是指向終端結(jié)點的指針,用它來表示單循環(huán)鏈表可以使得查找鏈表的開始結(jié)點和終端結(jié)點都很方便,設(shè)一帶頭結(jié)點的單循環(huán)鏈表,其尾指針為rear,則開始結(jié)點和終端結(jié)點的位置分別是rear->next->next 和 rear, 查找時間都是O(1)。若用頭指針來表示該鏈表,則查找終端結(jié)點的時間為O(n)。5、線性表是( ) A一個有限序列,可以為空 B一個有限序列,不能為空 C一個無限序列,可以為空 D一個無限序列,不能為空6、在n個結(jié)點的雙鏈表的某個結(jié)點前插入一個結(jié)點的時間復雜度是( ) AO(n) BO(1) CO(log2n) DO(n2)7、線性表采用鏈式
11、存儲時,結(jié)點的地址( ) A必須是連續(xù)的 B必須是不連續(xù)的 C連續(xù)與否均可 D必須有相等的間隔8、在單鏈表中,增加頭結(jié)點的目的是( ) A使單鏈表至少有一結(jié)點 B標志表中首結(jié)點位置 C方便運算的實現(xiàn) D說明單鏈表是線性表的鏈式存儲實現(xiàn)9、帶頭結(jié)點的單鏈表head為空的判定條件是( ) Ahead = NULL; Bhead - > next = NULL; Chead - > next = head; Dhead ! = NULL;10、在一個具有n個結(jié)點的有序單鏈表中插入一個新結(jié)點并仍然有序的時間復雜度為( ) A(1) B(n) C(n2) D(log2n)11、下列有關(guān)線性表
12、的敘述中,正確的是( ) A線性表中的元素之間是線性關(guān)系 B線性表中至少有一個元素 C線性表中任何一個元素有且僅有一個直接前趨 D線性表中任何一個元素有且僅有一個直接后繼12、在單鏈表中,存儲每個結(jié)點需有兩個域,一個是數(shù)據(jù)域,另一個是指針域,它指向該結(jié)點的( ) A直接前趨 B直接后繼 C開始結(jié)點 D終端結(jié)點13、將兩個各有n個元素的有序表歸并成一個有序表,其最少的比較次數(shù)是( )。An B.2n-1 C.2n D.n-114、鏈表不具有的特點是( )。A隨機訪問 B不必事先估計存儲空間C插入刪除時不需移動元素 D所需的空間與線性表成正比15、在一個單鏈表中,已知q所指結(jié)點是p所指結(jié)點的直接前
13、趨,若在p,q之間插入s結(jié)點,則執(zhí)行的操作是( )。 As->next=p->next;p->next=s; Bq->next=s;s->next=p;Cp->next=s->next;s->next=p; Dp->next=s;s->next=q;16、鏈表具有的特點是( )。A可隨機訪問任一元素B插入、刪除需要移動元素C不必事先估計存儲空間D存儲空間是靜態(tài)分配的17、一個順序表一旦說明,其中可用空間大?。?)A已固定B可以改變C不能固定D動態(tài)變化18、若某線性表中最常用的操作是取第i個元素和找第i個元素的前趨元素,則采用( )存儲
14、方式最節(jié)省時間。A 順序表B單鏈表C雙向鏈表D單循環(huán)鏈表19、兩個指針P和Q,分別指向單鏈表的兩個元素,P所指元素是Q所指元素的前驅(qū)的條件是( )。AP->next=QBQ->next=PCP=QDP->next=Q->next20、鏈表不具有的特點是( )。A可隨機訪問任一元素 B插入、刪除不需要移動元素C不必事先估計存儲空間 D所需空間與線性表長度成正比21、下面關(guān)于線性表的敘述中,錯誤的是( )。A線性表采用順序存儲,必須占用一片連續(xù)的存儲單元B線性表采用順序存儲,便于進行插入和刪除操作C線性表采用鏈接存儲,不必占用一片連續(xù)的存儲單元D線性表采用鏈接存儲,便于進行
15、插入和刪除操作22、在n個結(jié)點的順序表中,算法的時間復雜度是O(1)的操作是( )。A訪問第i個結(jié)點(1in)和求第i個結(jié)點的直接前趨(2in)B在第i個結(jié)點后插入一個新結(jié)點(1in)C刪除第i個結(jié)點(1in)D將n個結(jié)點從小到大排序23、在一個單鏈表中,若刪除p指向結(jié)點的后繼結(jié)點,則執(zhí)行的操作為( )。Aq=p->next;p->next=p->next->next;free(q);Bp=p->next;q=p->next;p=q->next;free(q);Cq=p->next->next;p=p->next;free(q);Dp
16、=p->next->next;q=p->next;free(q);二、 填空題:1、在雙鏈表中要刪除已知結(jié)點*p,其時間復雜度為()。2、在僅有尾指針R指示的單循環(huán)鏈表R中,在表尾插入一個結(jié)點S的語句序列是( )。3、在帶頭結(jié)點的雙鏈表中,指針所指結(jié)點是開始結(jié)點的條件是()。4、在具有n個結(jié)點的雙鏈表中做插入、刪除運算,平均時間復雜度為()。5、在一個長度為n的順序表中第i個元素(1 i n)之前插入一個元素時,需向后移動()個元素。6、在雙循環(huán)鏈表中,若要在指針p所指結(jié)點之前插入指針s所指的結(jié)點,則需執(zhí)行下列語句:s->prior=p->prior;p->
17、prior->next=s;( )和p->prior=s;。7、已知指針p指向雙向鏈表中的一個結(jié)點(非首結(jié)點、非尾結(jié)點),則將結(jié)點s插入在p結(jié)點的直接后繼位置的語句是( )s->prior=p;s->next->prior=s;p->next=s;8、已知帶表頭結(jié)點的單鏈表L,指針p指向L鏈表中的一個結(jié)點(非首結(jié)點、非尾結(jié)點),則刪除結(jié)點p的直接后繼結(jié)點的語句是( );刪除首結(jié)點的語句是( )。三、 判斷題1、在有序的順序表和有序的鏈表上,均可以使用折半查找法來提高查找速度。( )2、順序存儲的線性表可以隨機存取。 ( )3、線性表采用順序存儲,必須占用一片
18、連續(xù)的存儲單元。 ( )四、 程序設(shè)計題數(shù)據(jù)結(jié)構(gòu)的數(shù)據(jù)類型定義如下: 順序存儲: typedef struct int *base; int length; int listsize; sqlist; 鏈式存儲: typedef struct LinkList int data; struct LinkList *next; Node,*LinkList; 1、已知帶頭結(jié)點的單鏈表head中的結(jié)點是按整數(shù)值遞增排序的,寫一算法將值為x的結(jié)點插入到表head中,使head仍然有序。2、用尾插法建立帶頭結(jié)點的單鏈表。3、用頭插法建立帶頭結(jié)點的單鏈表。4、對給定的單鏈表L,編寫一個刪除L中值為x的結(jié)
19、點的直接前趨結(jié)點算法。5、用順序存儲結(jié)構(gòu)實現(xiàn)線性表的就地逆置算法,即將(a1,a2, ai,an)逆置為(an,ai,a2,a1);6、用鏈式存儲結(jié)構(gòu)實現(xiàn)線性表的就地逆置算法,即將(a1,a2, ai,an)逆置為(an,ai,a2,a1);7、使用順序存儲結(jié)構(gòu)分別實現(xiàn)A=AB和A=AB運算;參考答案(線性表)一、選擇題1234567891011121314151617181920212223BABCABCCBBABBABCBAAABAA二、填空題1、在雙鏈表中要刪除已知結(jié)點*p,其時間復雜度為(O(1))。2、在僅有尾指針R指示的單循環(huán)鏈表R中,在表尾插入一個結(jié)點S的語句序列是(P=R; w
20、hile(P->next!=NULL) P=P->next; P->next=S; S->next=NULL;)。3、在帶頭結(jié)點的雙鏈表中,指針所指結(jié)點是開始結(jié)點的條件是(P= =L)。4、在具有n個結(jié)點的雙鏈表中做插入、刪除運算,平均時間復雜度為(O(1))。5、在一個長度為n的順序表中第i個元素(1 i n)之前插入一個元素時,需向后移動(n-i+1)個元素。6、在雙循環(huán)鏈表中,若要在指針p所指結(jié)點之前插入指針s所指的結(jié)點,則需執(zhí)行下列語句:s->prior=p->prior;p->prior->next=s;( s->next=p;
21、)和p->prior=s;。7、已知指針p指向雙向鏈表中的一個結(jié)點(非首結(jié)點、非尾結(jié)點),則將結(jié)點s插入在p結(jié)點的直接后繼位置的語句是(p->next=s;)s->prior=p;s->next->prior=s;p->next=s;8、已知帶表頭結(jié)點的單鏈表L,指針p指向L鏈表中的一個結(jié)點(非首結(jié)點、非尾結(jié)點),則刪除結(jié)點p的直接后繼結(jié)點的語句是(q=p->next; p->next=q->next; free(q););刪除首結(jié)點的語句是(q=L->next; L=L->next; free(q);)。三、判斷題1、在有序的
22、順序表和有序的鏈表上,均可以使用折半查找法來提高查找速度。(×)2、順序存儲的線性表可以隨機存取。 ()3、線性表采用順序存儲,必須占用一片連續(xù)的存儲單元。 ()四、程序設(shè)計題1、已知帶頭結(jié)點的單鏈表head中的結(jié)點是按整數(shù)值遞增排序的,寫一算法將值為x的結(jié)點插入到表head中,使head仍然有序。P=head->next;While(p->next!=NULL&&p->data<x) p=p->next;/指針定位p->next=x;x->next=p->next;2、用尾插入法建立帶頭結(jié)點的單鏈表。 請參考教材“數(shù)據(jù)
23、結(jié)構(gòu)-清華大學嚴尉敏著評p29-p30”;3、用頭插入法建立帶頭結(jié)點的單鏈表。請參考教材“數(shù)據(jù)結(jié)構(gòu)-清華大學嚴尉敏著評p29-p30”;4、對給定的單鏈表L,編寫一個刪除L中值為x的結(jié)點的直接前趨結(jié)點算法。/算法思路:先判斷L中是否存在值為x的結(jié)點,若不存在,返回錯誤(-1);若存在,用一指針p定位到值為x的第一結(jié)點,用另一個指針q定位到值為x的第一結(jié)點的前驅(qū)結(jié)點,然后實施刪除操作;重點語句為:p=L->next;/p指向第一個結(jié)點whili(p->data!=x&&p->next!=NULL) p=p->next;if(p= =NULL) ruturn
24、 error;/不存在else p=L->next; while(p->next->next->data!=x) p=p->next; q=p->next; p->next=p->next->next; free(q);5、用順序存儲結(jié)構(gòu)實現(xiàn)線性表的就地逆置算法,即將(a1,a2, ai,an)逆置為(an,ai,a2,a1);重點語句: for(i=0;i<sqlist.length/2;i+) sqlist.baseißàsqlist.basesqlist.length-i;/第i個元素和第length-i元素
25、交換存儲6、用鏈式存儲結(jié)構(gòu)實現(xiàn)線性表的就地逆置算法(不帶頭結(jié)點的單鏈表),即將(a1,a2, ai,an)逆置為(an,ai,a2,a1);參考答案: Node *fun(Node *h)/h指向單鏈表的第一個結(jié)點 Node *p,*q,*r; P=h; If(p=NULL) Return NULL; q=pànext;/q指針指向第二個結(jié)點 pànext=NULL; while(q) r=qànext;/第一次循環(huán)時,r指向第三個結(jié)點 qànext=p;/第二個結(jié)點的NEXT指向第一個結(jié)點 p=q;/p總是指向逆置后的第一個結(jié)點 q=r;/q總是指向剩
26、余單鏈表的第一個結(jié)點,為將其作為逆置單鏈表的第一個結(jié)點作準備 return p; 兩外,解決本體還有另外一種思路,將結(jié)點數(shù)據(jù)域拷貝到一個一維數(shù)組中,然后反過來填充單鏈表結(jié)點的數(shù)據(jù)域。7、使用順序存儲結(jié)構(gòu)分別實現(xiàn)A=AB和A=AB運算;請參考清華大學出版社出版,嚴尉敏編著數(shù)據(jù)結(jié)構(gòu)C語言版P20例2-1;3 棧和隊列一、 選擇題:1、循環(huán)隊列是空隊列的條件是( ) AQ . rear = = Q . front B(Q . rear + 1)%maxsize = = Q .front CQ . rear = = 0 DQ. front = = 02、鏈棧與順序棧相比,比較明顯的優(yōu)點是( ) A通常
27、不會出現(xiàn)棧滿的情況 B通常不會出現(xiàn)棧空的情況C插入操作更加方便 D刪除操作更加方便分析不管是鏈棧還是順序棧,其插入、刪除操作都是在棧頂進行的,都比較方便,所以不可能選C),D)。對鏈棧來講,當棧中沒有元素而又要執(zhí)行出棧操作時,就會出現(xiàn)??宅F(xiàn)象,故B)也是不正確的。只要內(nèi)存足夠大,鏈棧上就不會出現(xiàn)棧滿現(xiàn)象。而對順序棧來講,由于其大小是事先確定好的,因此可能會出現(xiàn)棧滿現(xiàn)象。所以A)是正確的。3、若一個棧的輸入序列是,n,輸出序列的第一個元素是,則第個輸出元素是( ) An - i Bn i + 1 Ci D不確定4、棧與一般線性表的區(qū)別主要在( ) A元素個數(shù) B元素類型 C邏輯結(jié)構(gòu) D插入、刪除
28、元素的位置5、一個鏈棧的棧頂指針是top,則執(zhí)行出棧操作時(棧非空),用x保存被刪除結(jié)點,則執(zhí)行( ) Ax = top; top = top ànext; Bx = topàdata; Ctop = top ànext;x = top à data; Dx = topà data;top = topà next;分析棧頂元素出棧后,應該從棧底位置即第一個結(jié)點開始重新定位,執(zhí)行語句是:q=base ; while(qànext!=top) q=qànext; free(top); top=q;6、對于一個棧,給定輸
29、入序列為1,2,3,則下列不可能為輸出序列的是( ) A1,2,3 B3,2,1 C3,1,2 D2,1,3分析 每個元素進棧后立即出棧,結(jié)果是答案A;三個元素全部進棧后再出棧,得到答案B;1和2進棧后出棧,然后3入棧后出棧,得到答案D;而C答案不可能的原因是:3出棧后,說明1、2還在棧中,1出棧后2還在棧中,說明2的入棧次序在1之前。7、在鏈接隊列執(zhí)行入隊操作( ) A需判別隊是否空 B需判別隊是否滿 C限制在鏈表頭p進行 D限制在鏈表尾p進行8、以下不屬于棧的基本運算是( )。 A刪除棧頂元素 B刪除棧底元素C判斷棧是否為空 D將棧置為空棧9、一個棧的入棧序列是a,b,c,d,e,則棧的不
30、可能的輸出序列是( )。Ae,d,c,b,a Bd,e,c,b,a Cd,c,e,a,b Da,b,c,d,e10、設(shè)計一個判別表達式中左、右括號是否配對出現(xiàn)的算法,采用( )數(shù)據(jù)結(jié)構(gòu)最佳。A線性表的順序存儲結(jié)構(gòu) B棧 C隊列 D線性表的鏈式存儲結(jié)構(gòu)11、循環(huán)隊列的特點之一是不會產(chǎn)生( )。 A上溢出 B下溢出 C隊滿 D假溢出12、設(shè)數(shù)組Datan作為循環(huán)隊列Q的存儲空間,front為隊頭指針,rear為隊尾指針,則執(zhí)行入隊操作的語句為( )。Arear=(rear+1)%(n+1) Bfront=(front+1)% n Crear=(rear+1)% n Dfront=(front+1)
31、%(n+1)13、棧是限定在( )處進行插入或刪除操作的線性表。A端點 B棧底 C棧頂 D中間14、容量是10的循環(huán)隊列的隊頭位置qàfront為2,隊列中的數(shù)據(jù)元素個數(shù)為5,則隊的第一個數(shù)據(jù)元素的位置是( )A2B7C1D0分析 (front-rear+10)%10=5,并且front和rear的取值范圍均是09,所以只有(7-2+10)%10=5。 15、循環(huán)隊列的出隊操作是( )Aqàfront=(qàfront+1)%maxsize; Bqàfront=qàfront+1;Cqàrear=(qàrear+1)%max
32、size; Dqàrear=qàrear+1;16、當循環(huán)隊列q是滿隊列時,存放隊列元素的數(shù)組data有n個元素,則data中存放( )個數(shù)據(jù)元素。AnB. n-1C. n-2D.0分析 容量為maxsize的循環(huán)隊列最多只能存放maxsize-1個數(shù)據(jù)元素,當隊列滿時,隊尾指針再往前走一步就追上隊頭指針,即(rear+1)% maxsize=front;17、以下哪一個不是隊列的基本運算( )。A從隊尾插入一個新元素 B從隊列中刪除第i個元素C判斷一個隊列是否為空 D讀取隊頭元素的值18、在一個鏈隊列中,若f , r分別為隊首、隊尾指針,則插入s所指結(jié)點的操作為( )。A
33、fànext=s;f=sBrànext=s;r=s;Csànext=r;r=s; Dsànext=f;f=s19、循環(huán)隊列的入隊操作應為( )。Aqàrear=qàrear+1;qàdataqàrear=x;Bqàdataqàrear+=x;Cqàrear=(qàrear+1)%maxsize; qàdataqàrear=x;Dqàdataqàrear=x;q->rear=(qàrear+1)%maxsize;20、棧和
34、隊列都是( )。A限制存取點的線性結(jié)構(gòu) B限制存取點的非線性結(jié)構(gòu)C順序存儲的線性結(jié)構(gòu) D鏈式存儲的線性結(jié)構(gòu)21、實現(xiàn)遞歸調(diào)用屬于( )的應用。A隊列 B棧 C 數(shù)組 D樹二、 填空題: 1、循環(huán)隊列用數(shù)組datam存放其元素值,已知其頭、尾指針分別是front和rear,則當前隊列中元素的個數(shù)是()。2、棧頂?shù)奈恢檬请S著()操作而變化的。3、假設(shè)以S和X分別表示進棧和退棧操作,則對輸入序列a,b,c,d,e進行一系列棧操作SSXSXSSXXX之后,得到的輸出序列為()。4、隊列的隊尾位置隨著()而變化。5、在( )的情況下,鏈隊列的出隊操作需要修改尾指針。6、從棧頂指針為top的鏈棧中刪除一個
35、結(jié)點,并將被刪除的結(jié)點的值保存在x中,其操作步驟為( );top=top->next;。7、用數(shù)組Am來存放循環(huán)隊列q的元素,且它的頭、尾指針分別為front和rear,隊列滿足條件(q.rear+1)%m=q.front,則隊列中當前的元素個數(shù)為( )。8、順序棧s存儲在數(shù)組s->datamax中,對s進行出棧操作,執(zhí)行的語句序列是( )。9、以下運算實現(xiàn)在循環(huán)隊列中的初始化操作void initqueue(seqqueue *q)q->front=0;( );三、 判斷題:1、循環(huán)隊列中無上溢現(xiàn)象。 ( )2、循環(huán)隊列只有下溢,沒有上溢。 ( )3、對順序棧而言,在棧滿狀
36、態(tài),如果此時再作進棧運算,則會發(fā)生“下溢”。 ( )4、順序隊列和循環(huán)隊列的隊滿和隊空的條件是一樣的。 ( )5、為解決隊列“假滿”問題,可以采用循環(huán)數(shù)組實現(xiàn)隊列存儲。 ( )6、隊列是后進先出表。 ( )7、棧是后進先出表。 ( )四、 應用題:1、 設(shè)有一個棧,元素進棧的次序為A,B,C,D,E,寫出下列出棧序列的操作序列。(1)CBADE(2)ACBED,其中I為進棧操作,O為出棧操作。2、如果編號為1、2、3的三輛列車進入一個棧式結(jié)構(gòu)的站臺,那么可能得到的三輛列車出站序列有哪些?不可能出現(xiàn)的序列是什么?五、 程序設(shè)計題:1、寫出循環(huán)隊列入隊操作的函數(shù)。參考答案(棧和隊列)一、選擇題12
37、3456789101112131415161718192021AABDBCDBCBDCCBABBBCAB二、填空題1、循環(huán)隊列用數(shù)組datam存放其元素值,已知其頭、尾指針分別是front和rear,則當前隊列中元素的個數(shù)是((rear-front+maxsize)%maxsize)。2、棧頂?shù)奈恢檬请S著(入棧和出棧)操作而變化的。3、假設(shè)以S和X分別表示進棧和退棧操作,則對輸入序列a,b,c,d,e進行一系列棧操作SSXSXSSXXX之后,得到的輸出序列為(bceda)。4、隊列的隊尾位置隨著(入隊列操作變化)而變化。5、在(鏈隊列為空)的情況下,鏈隊列的出隊操作需要修改尾指針。 分析:Q.
38、rear=h;6、從棧頂指針為top的鏈棧中刪除一個結(jié)點,并將被刪除的結(jié)點的值保存在x中,其操作步驟為(x=top->data)。7、用數(shù)組Am來存放循環(huán)隊列q的元素,且它的頭、尾指針分別為front和rear,隊列滿足條件(q.rear+1)%m=q.front,則隊列中當前的元素個數(shù)為(0)。8、順序棧s存儲在數(shù)組s->datamax中,對s進行出棧操作,執(zhí)行的語句序列是(sàtop-)。9、以下運算實現(xiàn)在循環(huán)隊列中的初始化操作void initqueue(seqqueue *q)q->front=0;( qàbase=(qelemtype *)mal
39、loc(maxsize*sizeof(qelemtype); qàrear=0;);三、判斷題1、循環(huán)隊列中無上溢現(xiàn)象。 (×)2、循環(huán)隊列只有下溢,沒有上溢。 (×)3、對順序棧而言,在棧滿狀態(tài),如果此時再作進棧運算,則會發(fā)生“下溢”。 (×)4、順序隊列和循環(huán)隊列的隊滿和隊空的條件是一樣的。 (×)5、為解決隊列“假滿”問題,可以采用循環(huán)隊列實現(xiàn)隊列存儲。 ()6、隊列是后進先出的線性表。 (×)7、棧是后進先出表。 ()四、應用題1、設(shè)有一個棧,元素進棧的次序為A,B,C,D,E,寫出下列出棧序列的操作序列。(1)CBADE(2
40、)ACBED,其中I為進棧操作,O為出棧操作。參考答案:(1)IIIOOOIOIO (2)IOIIOOIIOO2、如果編號為1、2、3的三輛列車順序進入一個棧式結(jié)構(gòu)的站臺,那么可能得到的三輛列車出站序列有哪些?不可能出現(xiàn)的序列是什么?參考答案:可能得到的三輛列車出站序列有1,2,3; 1,3,2;2,1,3;2,1,3;2,3,1;其他3個數(shù)字的另外1個排列不可能出現(xiàn),即3,1,2。五、程序設(shè)計題1、寫出循環(huán)隊列入隊操作的函數(shù)。請參考清華大學出版社嚴蔚敏編著的數(shù)據(jù)結(jié)構(gòu)C語言版p65。4 串和數(shù)組(含參考答案)一、單選題 1下列那些為空串( ) A)S=“ ” B)S=“” C)S=“” D)S
41、=“” 答案:B 2S1=“ABCD”,S2=“CD”則S2在S3中的位置是( ) A)1 B)2 C)3 D)4 答案:C 3假設(shè)S=“abcaabcaaabca”,T=“bca”,Index (S,T,3) 的結(jié)果是( ) A)2 B)6 C)11 D)0 答案:B 4在串中,對于SubString(&Sub,S,pos,len)基本操作,pos和len的約束條件是( ) A)0<pos<StrLength(S)+1且1<=len<=StrLength(S)-pos+1 B)0<pos<StrLength(S)+1且0<=len<=S
42、trLength(S)-pos-1 C)1<=pos<=StrLength(S) 且0<=len<=StrLength(S)-pos+1 D)1<=pos<=StrLength(S) 且1<=len<=StrLength(S)-pos-1 答案:C 5串是一種特殊的線性表,其特殊性體現(xiàn)在( )。 A可以順序存儲 B. 數(shù)據(jù)元素是一個字符 C可以鏈接存儲 D. 數(shù)據(jù)元素可以是多個字符 答:B 6串是( )。 A少于一個字母的序列 B. 任意個字母的序列 C不少于一個字符的序列 D. 有限個字符的序列 答:D 7 串的長度是( )。 A串中不同字母的
43、個數(shù) B. 串中不同字符的個數(shù) C串中所含的字符的個數(shù) D. 串中所含字符的個數(shù),且大于0 答:C 8 設(shè)有S1=ABCDEFG,S2=PQRST,函數(shù)con(x,y)返回x和y串的連接串,subs(I,j)返回串S的從序號I的字符開始的j個字符組成的子串,len(s)返回串s的長度,則con(subs(S1,2,len(S2),subs(S1,len(S2),2)的結(jié)果是( )。 ABCDEF B. BCDEFG C. BCPQRST D. BCDEFEF 答:D 9 若某串的長度小于一個常數(shù),則采用( )存儲方式最為節(jié)省空間。 A鏈式 B. 堆結(jié)構(gòu) C. 順序表 答:C 二、填空題: 1串
44、是每個結(jié)點僅由一個字符組成的_。 答:線性表 2在串中,SubString (“student”,5,0) 的結(jié)果是_。 答:“” 3假設(shè)S=“abcaabcaaabca”,T=“bca”,V=“x”,Replace (S,T,V)結(jié)果是_。 答:“axaxaax” 4在串中,對于StrCompare(S,T)基本操作,若S<T,返回值_。 答:<0 5在串順序存儲結(jié)構(gòu)中,實現(xiàn)串操作的原操作為_。答:字符序列的復制6串與線性表在邏輯結(jié)構(gòu)上極為相似,區(qū)別僅在于_ ;在基本操作上差別很大,線性表的基本操作大多數(shù)以_ 作為操作對象,而串的基本操作通常以 作為操作對象。 答:串的數(shù)據(jù)對象約
45、束為字符集 “單個元素” “串的整體” 7兩個串相等的充分必要條件是_ 且_ 。 答:兩個串的串長相等 各個對應位置的字符都相等 8空串是指_,空格串是指_。 答:不含任何字符的串 僅含空格字符的串 三、判斷題1空串是由空白字符組成的串( FALSE ) 2串的定長順序結(jié)構(gòu)是用一組地址連續(xù)的存儲單元存儲串值的字符序列,按照預定義的大小,為每個定義的串變量分配一個固定長度的存儲區(qū)。(TRUE ) 3串的堆分配存儲表示是用一組地址連續(xù)的存儲單元存儲串值的字符序列,但它們的存儲空間是在程序執(zhí)行過程中動態(tài)分配得到的。(TRUE ) 4串中StrInsert(&S,pos,T)基本操作是最小的操
46、作子集(FALSE) 5串是由有限個字符構(gòu)成的連續(xù)序列,串長度為串中字符的個數(shù),子串是主串中字符構(gòu)成的有限序列。(FALSE) (錯:子串是主串中連續(xù)的字符構(gòu)成的有限序列) (題源:胡元義,C版數(shù)據(jù)結(jié)構(gòu)課程輔導與習題解析,p80,4.2.1(判斷題)_1) 6如果一個串中的所有字符均在另一串中出現(xiàn),那么則說明前者是后者的子串。(FALSE) ( 錯:是否連續(xù)是關(guān)鍵) (題源:陳明,C版實用數(shù)據(jù)結(jié)構(gòu)基礎(chǔ),p109,(判斷題)_2) 7串類型的最小操作子集不能利用其他串操作來實現(xiàn),反之,其他串操作(除串清除ClearString和串銷毀DestroyString外)均可在最小操作子集上實現(xiàn)。(TR
47、UE) (題源:根據(jù)教材p72自編) 四、簡答題1已知串s=(xyz)*,t=(x+z)*y,試利用串的基本運算將s串轉(zhuǎn)化為t串,t串轉(zhuǎn)化為s串。 (題源:寧正元,C版題解,p40,4.2_3) 答:concat ( replace (substring (sub,s,1,5),y,+), replace (substring (sub,s,6,1),*,*y) concat(replace(substring(sub,t,1,5),+,y),replace(substring(sub,t,6,2),*y,*) 2串是字符組成的,長度為1的串和字符是否概念相同?為什么? (題源:朱戰(zhàn)立,C版題
48、解,p86,4.2.1(典型題解)_2) 答:由于字符的長度固定為1,長度概念可以隱含,所以存儲時只需存儲該字符即可;而長度為1的串其長度概念不能隱含,必須顯示地表示出來,所以存儲時要同時存儲該字符和值為1的長度值。 五、算法設(shè)計題1設(shè)串s和串t采用順序存儲結(jié)構(gòu),編寫函數(shù)實現(xiàn)串s和串t的比較操作,要求比較結(jié)果包括大于、小于和等于三種情況。 (題源:朱戰(zhàn)立,C版題解,p87,4.2.1(典型題解)_7) 提示 算法思想:循環(huán)逐個比較兩個串,一旦兩個串的某個字符比較不相等則說明兩個串不相等,此時進一步比較這兩個不相等字符的大于和小于情況來決定串s和串t比較的大于和小于情況;當串s的n個字符和串t的m個字符比較全部相等時,還需進一步判斷此時串s或串t是否還有剩余字符沒有比較,來決定串s和
溫馨提示
- 1. 本站所有資源如無特殊說明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請下載最新的WinRAR軟件解壓。
- 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶所有。
- 3. 本站RAR壓縮包中若帶圖紙,網(wǎng)頁內(nèi)容里面會有圖紙預覽,若沒有圖紙預覽就沒有圖紙。
- 4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
- 5. 人人文庫網(wǎng)僅提供信息存儲空間,僅對用戶上傳內(nèi)容的表現(xiàn)方式做保護處理,對用戶上傳分享的文檔內(nèi)容本身不做任何修改或編輯,并不能對任何下載內(nèi)容負責。
- 6. 下載文件中如有侵權(quán)或不適當內(nèi)容,請與我們聯(lián)系,我們立即糾正。
- 7. 本站不保證下載資源的準確性、安全性和完整性, 同時也不承擔用戶因使用這些下載資源對自己和他人造成任何形式的傷害或損失。
最新文檔
- 25年公司安全管理人員安全培訓考試試題【培優(yōu)】
- 2024-2025企業(yè)員工安全培訓考試試題(一套)
- 2024-2025公司安全培訓考試試題答案4A
- 2025家居裝修合同示范文本
- 2025家具采購合同范本
- 2025員工違反保密合同泄露商業(yè)機密詐騙賠償金法律途徑維權(quán)被判刑
- 2025心理咨詢師合同協(xié)議書范本
- 2025年燒結(jié)釹鐵硼永磁材料合作協(xié)議書
- 2025技術(shù)合作開發(fā)合同模板樣本
- 2025企業(yè)貸款合同簡化版
- 2024華能四川能源開發(fā)有限公司下屬單位招聘筆試參考題庫附帶答案詳解
- 2025怎樣正確理解全過程人民民主的歷史邏輯、實踐邏輯與理論邏輯?(答案3份)
- 鋼結(jié)構(gòu)高處作業(yè)安全管理
- JJF 2221-2025導熱系數(shù)瞬態(tài)測定儀校準規(guī)范
- 華為手機協(xié)議合同
- 甘肅省隴南市禮縣第六中學2024-2025學年八年級下學期第一次月考數(shù)學試卷(無答案)
- 公司兩班倒管理制度
- 2025年武漢數(shù)學四調(diào)試題及答案
- 人教版小學四年級語文下冊2024-2025學年度第二學期期中質(zhì)量檢測試卷
- 七年級下冊道德與法治(2025年春)教材變化詳細解讀
- 雞頭黃精栽培技術(shù)規(guī)程
評論
0/150
提交評論