重大2015年數(shù)據結構 ( 第3次作業(yè) )

1、第3次作業(yè)次作業(yè)一、填空題（本大題共一、填空題（本大題共1010分，共分，共5小題，每小題小題，每小題2分）分）1.多重表文件和倒排文件都歸屬于______文件。2.數(shù)據結構被形式地定義為（DR），其中D是______的有限集合，R是D上的______有限集合。3.在棧的出棧操作中，要先判斷棧是否空，否則會產生______現(xiàn)象。4.在n個結點的單鏈表中要刪除已知結點p，需找到它的______，其時間復雜度為______。5.已知一個圖的

2、廣度優(yōu)先生成樹如右圖所示，則與此相應的廣度優(yōu)先遍歷序列為______。二、程序閱讀題（本大題共二、程序閱讀題（本大題共4040分，共分，共5小題，每小題小題，每小題8分）分）1.求下列廣義表運算的結果：head((phw))。2.指出下述程序段的功能是什么SeqStackS1S2tmpDataTypex...假設棧tmp和S2已做過初始化while(!StackEmpty(Push(while(!StackEmpty(Push(Push

3、(3.寫出下列程序段的輸出結果（棧的元素類型SElemType為）。voidmain()StackSxyInitStack(S)X=’c’y=’k’Push(Sx)Push(S’a’)Push(Sy)Pop(Sx)Push(S’t’)Push(Sx)Pop(Sx)Push(S’s’)while(!StackEmpty(S))Pop(Sy)printf(y)Printf(x)4.下述算法的功能是什么LinkListDemo(LinkLis

4、tL)L是無頭結點單鏈表ListNodeQPif(LL=LnextP=Lwhile(Pnext)P=PnextPnext=QQnext=NULLreturnLDemo5.閱讀下列C程序段，寫出相應的執(zhí)行結果題目：longintfact(n)intnlongfif(n1)f=nfact(n1)elsef=1return(f)main()intnlongyn=5y=fact(n)printf(“%d%ldn”ny)三、簡答題（本大題共三、簡

5、答題（本大題共2020分，共分，共4小題，每小題小題，每小題5分）分）1.鏈棧中為何不設置頭結點2.什么是程序的空間復雜度？解題方案：解題方案：評分標準：評分標準：每空2分5.參考答案：參考答案：Abefcdg解題方案：解題方案：評分標準：評分標準：每空2分二、程序閱讀題（二、程序閱讀題（4040分，共分，共5題，每小題題，每小題8分）分）1.參考答案：參考答案：head((phw))=p。解題方案：解題方案：評分標準：評分標準：2.參

6、考答案：參考答案：程序段的功能是利用tmp棧將一個非空棧s1的所有元素按原樣復制到一個棧s2當中去。解題方案：解題方案：評分標準：評分標準：3.參考答案：參考答案：答：輸出為“stack”。解題方案：解題方案：答：輸出為“stack”。評分標準：評分標準：54.參考答案：參考答案：答：該算法的功能是：將開始結點摘下鏈接到終端結點之后成為新的終端結點，而原來的第二個結點成為新的開始結點，返回新鏈表的頭指針。解題方案：解題方案：答：該算法的