數(shù)據(jù)結(jié)構(gòu)與算法期中考試卷(含答案)

1、玉林師范學(xué)院期中課程考試試卷（2010——2011學(xué)年度第一學(xué)期）命題教師：命題教師：劉恒劉恒命題教師所在系：命題教師所在系：數(shù)計(jì)系數(shù)計(jì)系課程名稱：課程名稱：數(shù)據(jù)結(jié)構(gòu)與算法數(shù)據(jù)結(jié)構(gòu)與算法考試專業(yè)：考試專業(yè)：信計(jì)信計(jì)考試年級(jí)：考試年級(jí)：0909級(jí)題號(hào)一二三四五總分應(yīng)得分3010104010滿分：100實(shí)得分評(píng)分：評(píng)卷人簽名一、單項(xiàng)選擇題（每題一、單項(xiàng)選擇題（每題2分，共分，共30分，把正確答案填入表格中）分，把正確答案填入表格中）1234

2、5678CBCCDACA9101112131415CDBBBAD1、在數(shù)據(jù)結(jié)構(gòu)中，從邏輯上可以把數(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)線性結(jié)構(gòu)和非線性結(jié)構(gòu)D、邏輯結(jié)構(gòu)和存儲(chǔ)結(jié)構(gòu)2、結(jié)構(gòu)中的數(shù)據(jù)元素之間存在一個(gè)對(duì)多個(gè)的關(guān)系，稱為(B)結(jié)構(gòu)。A、線性B、樹(shù)形樹(shù)形C、圖狀D、網(wǎng)狀3、以下關(guān)于線性表的說(shuō)法不正確的是(C)。A、線性表中的數(shù)據(jù)元素可以是數(shù)字、字符、記錄等不同類型。B、線性表中包含

3、的數(shù)據(jù)元素個(gè)數(shù)不是任意的。C、線性表中的每個(gè)結(jié)點(diǎn)線性表中的每個(gè)結(jié)點(diǎn)都有都有且只有一個(gè)直接前驅(qū)和直接后繼。且只有一個(gè)直接前驅(qū)和直接后繼。D、存在這樣的線性表：表中各結(jié)點(diǎn)都沒(méi)有直接前驅(qū)和直接后繼。4、關(guān)于單鏈表的說(shuō)法，請(qǐng)選出不正確的一項(xiàng)(C)。A、邏輯相鄰、物理不一定相鄰B、不能隨機(jī)存取C、插入與刪除需移動(dòng)大量元素插入與刪除需移動(dòng)大量元素D、表容量易于擴(kuò)充5、關(guān)于順序表的說(shuō)法，請(qǐng)選出不正確的一項(xiàng)(D)。A、邏輯相鄰、物理相鄰B、可實(shí)現(xiàn)隨機(jī)存

4、取C、存儲(chǔ)空間使用緊湊D、表容量易于擴(kuò)充表容量易于擴(kuò)充6、設(shè)N為正整數(shù)，試確定下列程序段中前置以記號(hào)@語(yǔ)句的頻度為(A)。x=91y=100while(y0)@if(x100)x=10yelsexA、11001100B、9100C、110D、9107、在順序表中刪除一個(gè)元素，平均需要移動(dòng)(C)元素，設(shè)表長(zhǎng)為n。A、n21B、n21C、n2n2D、(n1)28、對(duì)單鏈表執(zhí)行下列程序段，請(qǐng)選出正確的一項(xiàng)(A)。2573┅84^PQRST=P

5、While(Tnext!=NULL)T—data=T—data2T=T—nextA、Rdata=4Rdata=4B、Rdata=8C、Hdata=4D、Qdata=79、若一個(gè)棧的輸入序列是1，2，3，┅，n，輸出序列的第一個(gè)元素是n則第k個(gè)輸出元素是(C)。A、kB、nk1Cnk1nk1D、不確定10、判斷一個(gè)順序棧S(最多有n個(gè)元素)為滿的條件是()D。A、s.top!=0B、s.top==0C、s.top!=nD、s.top==n

6、考試時(shí)間年月日下午系(院):年級(jí):專業(yè):班別:學(xué)號(hào):姓名:座位號(hào):——————————————————————————————————————————————————————密封線內(nèi)不要答題∞裝訂∞線∞H四、解答題（每題四、解答題（每題5分，共分，共40分）分）1、分別寫出循環(huán)隊(duì)列中判斷隊(duì)空和隊(duì)滿的條件（設(shè)循環(huán)隊(duì)列的最大存儲(chǔ)空間是M）。隊(duì)空：隊(duì)空：front=front==rear=rear（2.52.5分）分）隊(duì)滿：隊(duì)滿：(rear1

7、)%M=(rear1)%M==front=front（2.52.5分）分）2、已知L是帶表頭結(jié)點(diǎn)的非空單鏈表，且P結(jié)點(diǎn)既不是第一個(gè)元素結(jié)點(diǎn)，也不是最后一個(gè)元素結(jié)點(diǎn)，請(qǐng)寫出刪除P結(jié)點(diǎn)的直接后繼結(jié)點(diǎn)的語(yǔ)句序列：La1┅Panai┅Q=PnextQ=Pnext（2分）分）Pnext=pnextnextPnext=pnextnext（2分）分）free(Q)free(Q)（1分）3、簡(jiǎn)述以下算法的功能：Statusalgo(Stacksinte

8、)StackTintdInitStack(T)while(!StackEmpty(S))Pop(Sd)if(d!=e)push(Td)while(!StackEmpty(T))Pop(Td)Push(Sd)借助棧T把棧s中與e相等的元素刪掉（5分）p223.4(2)4、寫出下列程序段的輸出結(jié)果（隊(duì)列中的元素類型QElemType為）。voidmain()QueueQInitQueue(Q)x=’e’y=’c’EnQueue(Q’h’)E

9、nQueue(Q’r’)EnQueue(Qy)DeQueue(Qx)EnQueue(Qx)DeQueue(Qx)EnQueue(Q’a’)While(!QueueEmpty(Q))DeQueue(Qy)printf(y)printf(x)（5分）p233.125、已知下列字符串:a=’THIS’f=’ASAMPLE’C=’GOOD’D=’NE’b=’’s=Concat(aConcat(SubString(f27)Concat(bSubS

10、tring(a32))))t=Replace(fSubString(f36)c)AGOODGOODu=Concat(SubString(c31)D)ONEONEg=’IS’v=Concat(sConcat(bConcat(tConcat(bu))))THISTHISSAMPLESAMPLEISISAGOODGOODONEONE試問(wèn)：svStrLength(s)Index(vg)Index(ug)各是什么？s:THISSAMPLEIS（1

11、分）v:THISSAMPLEISAGOODONE（1分）StrLength(s)=14（1分）Index(vg)=3（1分）Index(ug)=0（1分）6、下面算法實(shí)現(xiàn)串的基本操作Str(S[posT[0]…S[0]T[0]]=S[pos…S[0]]S[pos…posT[0]1]=T[1…T[0]]T[1…T[0]]（2.5分）S[0]=S[0]T[0]S[0]T[0]（2.5分）ReturnOK7、設(shè)有3個(gè)元素A，B，C依次進(jìn)棧，給