數(shù)據(jù)結構1-3習題答案

回顧第一章知識要點：基本概論：數(shù)據(jù)、數(shù)據(jù)元素、數(shù)據(jù)項、數(shù)據(jù)對象數(shù)據(jù)結構(D,S)

邏輯結構：線性結構、樹形結構、圖形結構、集合結構

存儲結構：順序存儲、鏈式存儲、索引存儲、散列存儲

運算：初始化、查找、插入、刪除、遍歷等抽象數(shù)據(jù)類型（D,S,P）回顧第二章知識要點：算法定義及特性算法效率分析

時間復雜度：用語句頻度總和的數(shù)量級描述空間復雜度：用占有存儲空間的數(shù)量級描述回顧第三章知識要點：C語言重點內容：

參數(shù)傳遞、結構類型、指針遞歸直接遞歸、間接遞歸存儲分配方式

靜態(tài)分配（全局靜態(tài)變量區(qū)）、動態(tài)分配（堆區(qū)）、自動分配（棧區(qū)）總結重點：了解數(shù)據(jù)、數(shù)據(jù)元素、數(shù)據(jù)對象、數(shù)據(jù)結構、數(shù)據(jù)結構的邏輯結構、數(shù)據(jù)的存儲結構及抽象數(shù)據(jù)類型概念，熟悉C語言中指針、結構體，學會分析時間復雜度。

1-3章習題1.1-1.3見教材1.4試述數(shù)據(jù)的邏輯結構與存儲結構之間的區(qū)別與聯(lián)系。答：數(shù)據(jù)結構包括數(shù)據(jù)邏輯結構和數(shù)據(jù)物理結構兩個層次，兩者是密切相關、相輔相成的。數(shù)據(jù)的邏輯結構是對數(shù)據(jù)元素之間存在的邏輯關系的一種抽象描述；數(shù)據(jù)的物理結構則為其邏輯結構在計算機中的存儲表示或實現(xiàn)。一種邏輯結構可映射成不同的存儲結構，不同的存儲實現(xiàn)方法其算法不同，實現(xiàn)的效率也不同。1.6什么是抽象數(shù)據(jù)類型？它有什么作用？答：抽象數(shù)據(jù)類型（ADT）是指一個數(shù)學模型以及定義在該模型上的一組操作。抽象數(shù)據(jù)類型的定義僅取決于它的一組邏輯特性，而與其在計算機內部如何表示和實現(xiàn)無關。抽象數(shù)據(jù)類型是用戶定義的數(shù)據(jù)類型，使得其使用和實現(xiàn)分類，提高軟件的復用率。2.1試述算法和程序的區(qū)別。答：算法是指解決問題的一種方法或一個過程，即由若干條指令組成的有窮序列。程序是算法用某種程序設計語言的具體實現(xiàn)。算法中指令的執(zhí)行必須是有窮性的，而程序可以不滿足此要求。2.4判斷下述計算過程是否是一個算法：Step1:開始Step2:n<=0;Step3:n=n+1;Step4:重復步驟3;Step5:結束;答：該計算過程不是一個算法，因為其不滿足算法的有窮性。2.6分析下列程序段的時間復雜度：(1)voidmain(){inti=1,j=0,n;scanf(“%d”,&n);while(i+j<=n){if(i>j)i=i+1;elsej=j+1;}}T(n)=O(n)(2)Intrec(intn){if(n<=1)return1;elsereturnrec(n-1)*rec(n-1);}T(n)=O(2n)2.8在下面兩列中，左側是算法（關于問題規(guī)模）的執(zhí)行時間，右側是一些時間復雜度。請用連線的方式表示每個算法的時間復雜度。100n36n2-12n+11024n+2log2nn(n+1)(n+2)/62n+1+100nT(n)=O(n3)T(n)=O(n2)T(n)=O(1)T(n)=O(n)T(n)=O(n3)T(n)=O(2n)3.1試述你所理解的函數(shù)參數(shù)的“值傳遞”和“地址傳遞”。答：“值傳遞”即在函數(shù)參數(shù)傳遞時將實參賦給形參，而在函數(shù)體中對形參修改后不影響實參原來值；“地址傳遞”即在函數(shù)參數(shù)傳遞時傳遞的是實參的地址，在函數(shù)體中可通過地址直接對實參進行操作。3.3什么是指針？什么是指針的指針？它們之間有本質上的區(qū)別嗎？答：一個變量的地址稱為該變量的指針。指針的指針即指向指針的指針，它們的區(qū)別是：指針存放的是某一數(shù)據(jù)的存放地址，而指針的指針存放的是指針的存放地址，用的是一種“二級間址”方法。3.4試述你所理解的“遞歸”。答：遞歸即一種在函數(shù)/過程/子程序在運行過程序中直接或間接調用自身的編程方式。3.5簡述動態(tài)存儲分配和靜態(tài)存儲分配之間的區(qū)別。答：靜態(tài)存儲分配是指在程序運行前由編譯器在編譯時分配固定的存儲空間，直到整個程序運行結束才釋放存儲空間，如全局變量存儲空間分配；而動態(tài)存儲分配則是在程序運行過程中根據(jù)需要進行動態(tài)的分配和釋放存儲空間。3.2試編寫程序完成：有15個學生，每個學生的信息包括學號、姓名、性別、年齡、班級和3門課程成績，從鍵盤輸入15個學生的信息，要求打印出3門課程的總平均成績，以及最高分的學生的信息（包括學號、姓名、性別、年齡、班級、3門課程成績、平均分）。#include<iostream.h>typedefstruct{ intno; charname[8]; charsex[2]; intage; charcls[14]; intmath; intenglish; intchinese;}student;voidmain(){ studentst[15]; inti,j1=1,j2=1,j3=1,avg1=0,avg2=0,avg3=0,max1=0,max2=0,max3=0; for(i=0;i<154;i++) { cout<<endl<<"請依次輸入第"<<i+1<<"位同學的學號、姓名、性別、年齡、班級、數(shù)學成績、英語成績、語文成績："; cin>>st[i].no>>st[i].name>>st[i].sex>>st[i].age>>st[i].cls>>st[i].math>>st[i].english>>st[i].chinese;} for(i=0;i<15;i++) { avg1+=st[i].math;avg2+=st[i].english;avg3+=st[i].chinese; if(st[i].math>max1){max1=st[i].math;j1=i;} if(st[i].english>max2){max2=st[i].math;j2=i;} if(st[i].chinese>max3){max3=st[i].math;j3=i;} }

avg1=avg1/15;avg2=avg2/15;avg3=avg3/15; cout<<endl<<"數(shù)學課的平均成績?yōu)椋?<<avg1; cout<<endl<<"該課程最高分同學信息為："<<st[j1].no<<""<<st[j1].name<<""<<st[j1].sex<<""<<st[j1].age<<""<<st[j1].cls<<""<<st[j1].math<<""<<st[j1].english<<""<<st[j1].chinese; cout<<endl<<"英語課的平均成績?yōu)椋?<<avg2; cout<<endl<<"該課程最高分同學信息為："<<st[j2].no<<""<<st[j2].name<<""<<st[j2].sex<<""<<st[j2].age<<""<<st[j2].cls<<""<<st[j2].math<<""<<st[j2].english<<""<<st[j2].chinese; cout<<endl<<"語文課的平均成績?yōu)椋?<<avg3; cout<<endl<<"該課程最高分同學信息為："<<st[j3].no<<""<<st[j3].name<<""<<st[j3].sex<<""<<st[j3].age<<""<<st[j3].cls<<""<<st[j3].math<<""<<st[j3].english<<""<<st[j3].chinese;}順序存儲：初始化、插入、刪除、查找運算鏈式存儲：初始化、插入、刪除、查找運算單鏈表

靜態(tài)鏈表

雙向鏈表

循環(huán)鏈表線性表存儲方式特點：能隨機存取，但插入、刪除數(shù)據(jù)元素移動量大特點：插入、刪除無需移動數(shù)據(jù)元素，但不能隨機存取，浪費存儲空間第四章知識回顧重點：熟練掌握順序表和單鏈表上實現(xiàn)的各種基本算法及相關的時間性能分析難點：能夠使用本章所學到的基本知識設計有效算法解決與線性表相關的應用問題。課堂練習1、在什么情況下用順序表比鏈表好?2、畫出執(zhí)行下列各行語句后各指針及鏈表的示意圖。L=(LinkList)malloc(sizeof(LNode));//等價于L=newLNode;P=L;For(i=1;i<=4;i++){P->next=(LinkList)malloc(sizeof(LNode));P=P->next;P->data=i*2-1;}P->next=NULL;For(i=4;i>=1;i--)Ins_LinkList(L,i+1,i*2);For(i=1;i<=3;i++)Del_LinkList(L,i);湖北工業(yè)大學理學院173、已知L是帶頭結點的非空單鏈表的頭指針，且P結點既不是首元結點，也不是尾元結點，試從提供的答案1-14中選擇適當?shù)恼Z句系列填空。(1)刪除p結點的直接后繼結點的語句序列是()(2)刪除p結點的直接前趨結點的語句序列是()(3)刪除p結點的語句序列是()(4)刪除首元結點的語句序列是()(5)刪除尾元結點的語句序列是()第一章緒論一、選擇題（下列各小題均有一個答案是正確的）A、問題的規(guī)模B、待處理數(shù)據(jù)的初態(tài)1、算法的時間復雜度取決于C、問題的規(guī)模和處理數(shù)據(jù)的初態(tài)（）A、動態(tài)結構和靜態(tài)結構B、緊湊結構和非緊湊結構C、線性結構和非線性結構D、內部結構和外部結構2、數(shù)據(jù)結構中，從邏輯上可以把數(shù)據(jù)結構分成（）A、找出數(shù)據(jù)結構的合理性B、分析算法的效率和時間復雜度C、研究算法的輸入和輸出的關系D、分析算法的易懂性和文檔性3、算法分析的目的是（）A、T1（n）=nlog2n+1000log2nB、T2（n）=nlog23-1000log2nC、T3（n）=n2-1000log2nD、T4（n）=2nlog2n-1000log2n4、下列函數(shù)中漸近時間復雜度最小的是（）A、計算方法B、排序方法C、計算方法和排序方法D、解決問題的有限序列5、計算機算法是指（）CCBBD二、填空題（請用正確答案填充下列空白）1、數(shù)據(jù)的邏輯結構包括＿＿＿＿＿、＿＿＿＿＿和＿＿＿＿＿三種；2、從利用計算機資源角度看，評價算法的性能主要是從＿和＿＿＿方面進行分析和研究的；

3、數(shù)據(jù)類型是一個＿＿＿和定義在這個＿上的一組操作；

4、算法的五個特性是＿、可行性、輸入和輸出；5、數(shù)據(jù)結構是一門研究＿＿計算的程序設計問題中計算機的＿＿以及它們之間＿＿＿和運算等學科；

6、下面程序段的時間復雜度分別是＿＿＿＿＿。for(i=0;i<n;i++)i=1;for(j=0;j<m;j++)while(i<=n)A[i][j]=0;i=i*3;

線性結構、樹形結構、圖形結構和集合結構問題規(guī)模輸入數(shù)據(jù)集合集合確定行、＿有窮性非數(shù)值操作的對象關系O(n2)、＿O(log3n)第二章線性表一、選擇題（下列各小題均有一個答案是正確的）A、P==NullB、P->next==Null1、不帶頭結點的單鏈表P為空的判斷條件是C、P->next=PD、P!=Null（）A、P->next=NullB、P==NullC、P->next=HeadD、P==Head2、非空循環(huán)單鏈表Head的尾結點（由P指向）滿足（）A、n個結點B、n/2個結點C、(n-1)/2個結點D、(n+1)/2個結點3、在n個結點的單鏈表中查找等于X的結點，需平均比較（）A、P->next=p->next->nextB、P=P->next;P->next=p->next->nextC、P->next=P->nextD、P=P->next->next4、一個單鏈表中若刪除P所指的后繼結點，則執(zhí)行（）A、S->next=P->next;P-next=S;B、P->next=S->next;S->next=PC、Q->next=S;S->next=PD、P->next=S;S->next=Q5、某單鏈表中Q是P的前趨，若Q和P之間插入結點S則（）ACDACA、必須是連續(xù)的B、部分地址必須是連續(xù)的6、線性表采用鏈式存儲，要求所用的存儲地址C、一定不是連續(xù)的D、連續(xù)與否都可以（）A、數(shù)據(jù)項B、數(shù)據(jù)對象C、數(shù)據(jù)元素D、表元素7、線性表是具有N個（）的有限序列（）A、O(1)B、O(n)C、O(n*n)D、O(log2n)8、在一有n個結點的有序單鏈表中插入一結點的時間復雜度（）A、數(shù)據(jù)項B、數(shù)據(jù)對象C、數(shù)據(jù)元素D、數(shù)據(jù)信息9、數(shù)據(jù)的最小單位是（）A、P->prior=P->next=P;B、P->prior=P;P->next=Null;C、P->prior=P->next=Null;D、P->prior=Null;P->next=P;10、雙向循環(huán)鏈表P判斷為空的條件是（）DCBAA二、填空題（請用正確答案填充下列空白）1、順序表中插入或刪除一個元素，需要平均移動＿＿＿元素，具體移動元素的個數(shù)與＿＿＿＿有關；

2、單鏈表中設置頭結點的作用是＿＿＿＿；

3、在非空雙向循環(huán)鏈表中的結點Q前插入結點P的過程如下，補充完整

P->prior=Q->prior;____P->next=Q;________________4、在單鏈表中首元結點外任一結點的存儲位置是由＿＿指示的；5、鏈式存儲結構既可以通過＿＿來實現(xiàn)也可以通過＿＿＿＿來實現(xiàn)；6、在雙向鏈表中，每個結點都有兩個指針域，其中一個指向＿＿＿另一個指向＿＿＿＿＿；6、程序段：i