數據結構與算法期中考試卷(含答案)

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

2、5678CBCCDACA9101112131415CDBBBAD1、在數據結構中，從邏輯上可以把數據結構分成(C)。A、動態(tài)結構和靜態(tài)結構B、緊湊結構和非緊湊結構C、線性結構和非線性結構線性結構和非線性結構D、邏輯結構和存儲結構2、結構中的數據元素之間存在一個對多個的關系，稱為(B)結構。A、線性B、樹形樹形C、圖狀D、網狀3、以下關于線性表的說法不正確的是(C)。A、線性表中的數據元素可以是數字、字符、記錄等不同類型。B、線性表中包含

3、的數據元素個數不是任意的。C、線性表中的每個結點線性表中的每個結點都有都有且只有一個直接前驅和直接后繼。且只有一個直接前驅和直接后繼。D、存在這樣的線性表：表中各結點都沒有直接前驅和直接后繼。4、關于單鏈表的說法，請選出不正確的一項(C)。A、邏輯相鄰、物理不一定相鄰B、不能隨機存取C、插入與刪除需移動大量元素插入與刪除需移動大量元素D、表容量易于擴充5、關于順序表的說法，請選出不正確的一項(D)。A、邏輯相鄰、物理相鄰B、可實現隨機存

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

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

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

7、)%M=(rear1)%M==front=front（2.52.5分）分）2、已知L是帶表頭結點的非空單鏈表，且P結點既不是第一個元素結點，也不是最后一個元素結點，請寫出刪除P結點的直接后繼結點的語句序列：La1┅Panai┅Q=PnextQ=Pnext（2分）分）Pnext=pnextnextPnext=pnextnext（2分）分）free(Q)free(Q)（1分）3、簡述以下算法的功能：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、寫出下列程序段的輸出結果（隊列中的元素類型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試問：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、下面算法實現串的基本操作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、設有3個元素A，B，C依次進棧，給