數據結構課程平時作業1一．單項選擇題1．數據結構是一門研究非數值計算的程序設計問題中計算機的①以及它們之間的②和運算等的學科。①A．操作對象B．計算方法C．邏輯存儲D．數據映象②A．結構B．關系C．運算D．算法2．數據結構被形式地定義為（K，R），其中K是①的有限集合，R是K上的②的有限集合。①A．算法B．數據元素C．數據操作D．邏輯結構②A．操作B．映象C．存儲D．關系在數據結構中，從邏輯上可以把數據結構分成()。動態結構和靜態結構B．緊湊結構和非緊湊結構C．線性結構和非線性結構D．內部結構和外部結構4.線性結構是數據元素之間存在一種：A）一對多關系B）多對多關系C）多對一關系D）一對一關系5.數據結構中，與所使用的計算機無關的是數據的結構；A)存儲B)物理C)邏輯D)物理和存儲二.填空題（將正確的答案填在相應的空中）1．在線性結構中，第一個結點①前驅結點，其余每個結點有且只有②個前驅結點；最后一個結點③后續結點，其余每個結點有且只有④個后續結點。2．在樹形結構中，樹根結點沒有①結點，其余每個結點有且只有②個前驅結點；葉子結點沒有③結點，其余每個結點的后續結點可以④。3．在圖形結構中，每個結點的前驅結點數和后續結點數可以①。4．線性結構中元素之間存在①關系，樹形結構中元素之間存在②關系，圖形結構中元素之間存在③關系。5.數據結構包括數據的、數據的和數據的這三個方面的內容。6．下面程序段的時間復雜度是①。for（i=0；i＜n；i++）for（j=0；j＜m；j++）A[i][j]=0；7．下面程序段的時間復雜度是①。S＝0；for（i=0；i<n；i++）for（j=0;j<n;j++）s+=b[i][j]；sum=s;三、簡答題1.數據結構是一門研究什么內容的學科？2.數據元素之間的關系在計算機中有幾種表示方法？各有什么特點？3.設有數據邏輯結構S=（D,R），試按題所給條件畫出這些邏輯結構的圖示，并確定相對于關系R，哪些結點是開始結點，哪些結點是終端結點？D={d1,d2,d3,d4}R={(d1,d2),(d2,d3),(d3,d4)}部分參考答案單選題AB2.BD3.C4.D5.C填空題無，1，無，1前驅，1個，后繼，多個多個一對一，一對多，多對多邏輯結構、物理結構、數據運算6.O(n*m)7.O(n*n)三、簡答題1.略見課件2.略3．d1d2d3d4線性結構數據結構課程平時作業2一．單項選擇題1.線性表L=（a,a,…,a）,下列說法正確的是（）。A．每個元素都有一個直接前驅和一個直接后繼。B．線性表中至少要有一個元素。C．表中諸元素的排列順序必須是由小到大或由大到小。D．除第一個和最后一個元素外,其余每個元素都有一個且僅有一個直接前驅和直接后繼。在線性表的下列運算中，不改變數據元素之間結構關系的運算是（）。

A．插入B．刪除

C．排序D．定位在一個長度為n的順序表中，在第i個元素（1<=i<=n+1）之前插入一個新元素時需向后移動（）個元素．A．n-1 B．n-i+1 C．n-i-1 D．I4.一個數組第一個元素的存儲地址是100，每個元素的長度為2，則第5個元素的地址是（）A．110B．108C．100D．1205.線性表若采用鏈式存儲結構時，要求內存中可用存儲單元的地址（）。A．必須是連續的B．部分地址必須是連續的C．一定是不連續的D．連續或不連續都可以6.在一個單鏈表中，已知q所指結點是p所指結點的前驅結點，若在q和p之間插入s結點，則執行語句（）。A．s->next=p->next;p->next=s;B．p->next=s->next;s->next=p;C．q->next=s;s->next=p;D．p->next=s;s->next=q;7．若已知一個棧的進棧序列是1，2，3，…，n，其輸出序列為p1，p2，p3，...，pn，若p1＝3，則p2為()。A可能是2B一定是2C可能是1D一定是18.有六個元素6，5，4，3，2，1的順序進棧，問下列哪一個不是合法的出棧序列？（）A.543612B.453126C.346521D.2341569.設有一順序棧S，元素s1,s2,s3,s4,s5,s6依次進棧，如果6個元素出棧的順序是s2,s3,s4,s6,s5,s1,則棧的容量至少應該是()A.2B.3C.5D.610.若棧采用順序存儲方式存儲，現兩棧共享空間V[1..m]，top[i]代表第i個棧(i=1,2)棧頂，棧1的底在v[1]，棧2的底在V[m]，則棧滿的條件是（）。A.|top[2]-top[1]|=0B.top[1]+1=top[2]C.top[1]+top[2]=mD.top[1]=top[2]二.填空題（將正確的答案填在相應的空中）1.向一個長度為n的向量中刪除第i個元素（1≤i≤n）時，需向前移動_______個元素。2.帶頭結點的單鏈表head為空的判定條件是。3.對于順序存儲的線性表，訪問結點和增加、刪除結點的時間復雜度為。4.線性表（a,a,…,a）以鏈接方式存儲時，訪問第i位置元素的時間復雜性為。5.棧是的線性表，其運算遵循的原則。6.一個棧的輸入序列是：1，2，3則不可能的棧輸出序列是。7.用S表示入棧操作，X表示出棧操作，若元素入棧的順序為1234，為了得到1342出棧順序，相應的S和X的操作串為。8.隊列是限制插入只能在表的一端，而刪除在表的另一端進行的線性表，其特點是。部分參考答案單選題D2.D3.B4.B5.D6.C7.A8.C9.B10.B填空題n-i2.head->next==NULL3.O(n)4.O(1)5.訪問受限，后進先出6.3,1,27.SXSSXSXX8.先進先出數據結構課程平時作業3一．單項選擇題1．下面關于串的的敘述中，哪一個是不正確的？（）A．串是字符的有限序列B．空串是由空格構成的串C．模式匹配是串的一種重要運算D．串既可以采用順序存儲，也可以采用鏈式存儲2．串是一種特殊的線性表，其特殊性體現在（）。A．可以順序存儲B．數據元素是一個字符C．可以鏈接存儲D．數據元素可以是多個字符3．串的長度是指（）A．串中所含不同字母的個數B．串中所含字符的個數C．串中所含不同字符的個數D．串中所含非空格字符的個數4．設有兩個串p和q，其中q是p的子串，求q在p中首次出現的位置的算法稱為（）A．求子串B．聯接C．匹配D．求串長5．若串S=“software”,其子串的個數是（）。A．8B．37C．36D．96.廣義表（（a,b,c,d））的表頭是（），表尾是（）。A.aB.（）C.（a,b,c,d）D.（b,c,d）7.設廣義表L=（（a,b,c）），則L的長度和深度分別為（）。A.1和1B.1和3C.1和2D.2和38.設有一個10階的對稱矩陣A，采用壓縮存儲方式，以行序為主存儲，a11為第一元素，其存儲地址為1，每個元素占一個地址空間，則a85的地址為（）。A.13B.33C.18D.409.設有數組A[i,j]，數組的每個元素長度為3字節，i的值為1到8，j的值為1到10，數組從內存首地址BA開始順序存放，當用以列為主存放時，元素A[5，8]的存儲首地址為()。A.BA+141B.BA+180C.BA+222D.BA+22510.假設以行序為主序存儲二維數組A=array[1..100，1..100]，設每個數據元素占2個存儲單元，基地址為10，則LOC[5，5]=（）。A.808B.818C.1010D.1020二.填空題（將正確的答案填在相應的空中）1．含零個字符的串稱為()串。任何串中所含()的個數稱為該串的長度。2．當且僅當兩個串的()相等并且各個對應位置上的字符都()時，這兩個串相等。一個串中任意個連續字符組成的序列稱為該串的()串。3．INDEX（‘DATASTRUCTURE’，‘STR’）=（）。4.數組的存儲結構采用（）存儲方式。5.設二維數組A[-20..30,-30..20],每個元素占有4個存儲單元,存儲起始地址為200。如按行優先順序存儲,則元素A[25,18]的存儲地址為（）；如按列優先順序存儲,則元素A[-18,-25]的存儲地址為（）。6.將整型數組A[1..8，1..8]按行優先次序存儲在起始地址為1000的連續的內存單元中，則元素A[7，3]的地址是（）。7.設廣義表L=((),()),則head(L)是（）；tail(L)是（）；L的長度是（）；深度是（）。8.廣義表(a,(a,b),d,e,((i,j),k))的長度是（），深度是（）。部分參考答案單選題B2.B3.B4.C5.B6.C.B7.C8.B9.B10.B填空題空，字符2.長度，串值，子串3.54.順序存儲5.9392，12086.12007.（），（），2,28.5,3數據結構課程平時作業4一．單項選擇題1.按照二叉樹的定義，具有3個結點的二叉樹有（）種。A．3B.4C.５D.62.有關二叉樹下列說法正確的是（）A．二叉樹的度為2B．一棵二叉樹的度可以小于2C．二叉樹中至少有一個結點的度為2D．二叉樹中任何一個結點的度都為23．若一棵二叉樹具有10個度為2的結點，5個度為1的結點，則度為0的結點個數是（）A．9B．11C．15D．不確定4.深度為５的二叉樹至多有（）個結點。A.16B.32C.31D.105．在一棵高度為k的滿二叉樹中，結點總數為（）A．2k-1B．2kC．2k-1D．log2k+11.設有無向圖6.G=（V，E）和G’=（V’,E’）,如G’為G的生成樹，則下面不正確的說法是（）A．G’為G的子圖B．G’為G的連通分量C．G’為G的極小連通子圖且V’=VD．G’是G的無環子圖7.任何一個帶權的無向連通圖的最小生成樹（）A．只有一棵B．有一棵或多棵C．一定有多棵D．可能不存在8．以下說法正確的是（）A．連通分量是無向圖中的極小連通子圖。B．強連通分量是有向圖中的極大強連通子圖。C．在一個有向圖的拓撲序列中，若頂點a在頂點b之前，則圖中必有一條弧<a,b>。D．對有向圖G,如果從任意頂點出發進行一次深度優先或廣度優先搜索能訪問到每個頂點，則該圖一定是完全圖。9．圖中有關路徑的定義是（）。A．由頂點和相鄰頂點序偶構成的邊所形成的序列B．由不同頂點所形成的序列C．由不同邊所形成的序列D．上述定義都不是10．設無向圖的頂點個數為n，則該圖最多有（）條邊。A．n-1B．n(n-1)/2C．n(n+1)/2D．0E．n2二.填空題（將正確的答案填在相應的空中）１．樹是n個結點的有限集合，當n=0時稱為（）。2．具有256個結點的完全二叉樹的深度為（）。3.如果結點A有3個兄弟，而且B是A的雙親，則B的度是()。4.設F是由T1,T2,T3三棵樹組成的森林,與F對應的二叉樹為B,已知T1,T2,T3的結點數分別為n1,n2和n3則二叉樹B的左子樹中有()個結點，右子樹中有()個結點。5.具有N個結點的二叉樹，采用二叉鏈表存儲，共有（）個空鏈域。6．具有10個頂點的無向圖，邊的總數最多為()。7．對于一個具有n個頂點e條邊的無向圖的鄰接表的表示，則表頭向量大小為（），鄰接表的邊結點個數為（）。8.在有n個頂點的有向圖中，若要使任意兩點間可以互相到達，則至少需要（）條弧。9．下圖中的強連通分量的個數為（）個。10．N個頂點的連通圖用鄰接矩陣表示時,該矩陣至少有（）個非零元素。三.簡答題1.已知某二叉樹的前序遍歷序列為：ABCDEFG和中序遍歷序列為：CBEDAFG，求后續遍歷。（1）每個頂點的入度、出度；（2）鄰接矩陣；（（1）每個頂點的入度、出度；（2）鄰接矩陣；（3）鄰接表；（4）逆鄰接表；（5）強連通分量。部分參考答案一、單選題C2.B3.B4.C5.A6.B7.B8.B9.A10.B二、填空題空樹2.93.44.n1,n2+n35.N+16.457.n,2e8.n9.310.2(N-1)簡答題1.CEDBAGF2.（1）頂點入度出度130222312413521623（2）

鄰接矩陣

（3）鄰接表（4）逆鄰接表（5）強連通分量數據結構課程平時作業5一．單項選擇題1.若在線性表中采用二分查找法查找元素，該線性表應該(

)。A．元素按值有序

B．采用順序存儲結構C．元素按值有序，且采用順序存儲結構D．元素按值有序，且采用鏈式存儲結構2.利用逐點插入法建立序列(51，71，43，81，74，20，34，45，64，30)對應的二叉排序樹以后，查找元素34要進行(

)元素間的比較。A．4次

B．5次

C.7次

D．103.散列函數有一個共同性質，即函數值應按(

)取其值域的每一個值。A.最大概率

B.最小概率

C.同等概率

D.平均概率4.一個哈希函數被認為是“好的”，如果它滿足條件()。A．哈希地址分布均勻B.保證不產生沖突C.所有哈希地址在表長范圍內D.滿足B和C5.平均查找長度最短的查找方法是()。A.折半查找B.順序查找C.哈希查找D.其他6.若對n個元素進行直接插入排序，在進行第i趟排序時，假定元素r[i+1]的插入位置為r[j]，則需要移動元素的次數為（）。A.j-iB.i-j-1C.i-jD.i-j+17.若對n個元素進行直接插入排序，則進行任一趟排序的過程中，為尋找插入位置而需要的時間復雜度為（）。A.O(1)B.O(n)C.O(n2)D.O(log2n)8.在對n個元素進行冒泡排序的過程中，第一趟排序至多需要進行（）對相鄰元素之間的交換。A.nB.n-1C.n+1D.n/29.在對n個元素進行冒泡排序的過程中，最好情況下的時間復雜度為（）。A.O(1)B.O(log2n)C.O(n2)D.O(n)10.在對n個元素進行快速排序的過程中，第一次劃分最多需要移動（）次元素，包括開始把支點元素移動到臨時變量的一次在內。A.n/2B.n-1C.nD.n+1二.填空題（將正確的答案填在相應的空中）1.()法構造的哈希函數肯定不會發生沖突。2.線性有序表（a1，a2，a3，…，a256)是從小到大排列的，對一個給定的值k，用二分法檢索表中與k相等的元素，在查找不成功的情況下，最多需要檢索()次。設有100個結點，用二分法查找時，最大比較次數是()。3.對n個關鍵字進行冒泡排序，時間復雜度為（）。4．折半查找有序表（4，6，12，20，28，38，50，70，88，100），若查找表中元素20，它將依次與表中元素()比較大小。5.在各種查找方法中，平均查找長度與結點個數n無關的查找方法是()。6.若待排序的序列中存在多個記錄具有相同的鍵值，經過排序，這些記錄的相對次序仍然保持不變，則稱這種排序方法是（）的，否則稱為（）的。7.按照排序過程涉及的存儲設備的不同，排序可分為（）排序和（）排序。8.直接插入排序用監視哨的作用是（）。9.對n個記錄的表r[1..n]進行簡單選擇排序，所需進行的關鍵字間的比較次數為（）。10.在插入排序和選擇排序中，若初始數據基本正序，則選用（）較好。三.簡答題1．對于給定的一組鍵值：83，40，63，13，84，35，96，57，39，79，61，15，分別畫出應用直接插入排序、直接選擇排序、快速排序、歸并排序對上述序列進行排序中各趟的結果。部分參考答案一、單選題C2.A3.C4.D5.C6.D7.C8.B9.D10.B二、填空題直接定址法2.9，73.O(n2)4.28,12,205.哈希表6.穩定的，非穩定的7.內部排序，外部排序8.防止數組越界9.n(n-1)/210.插入排序簡答題①直接插入排序序號123456789101112關鍵字834063138435965739796115i=24083[63138435965739796115]i=3406383[138435965739796115]i=413406383[8435965739796115]i=51340638384[35965739796115]i=6133540638384[965739796115]i=713354063838496[5739796115]i=81335405763838496[39796115]i=9133539405763838496[796115]i=1013353940576379838496[6115]i=111335394057616379838496[15]i=12131535394057616379838496②直接選擇排序序號123456789101112關鍵字834063138435965739796115i=113[4063838435965739796115]i=21315[63838435965739796140]i=3131535[838463965739796140]i=413153539[8463965783796140]i=51315353940[63965783796184]i=6131535394057[966383796184]i=713153539405761[6383799684]i=81315353940576163[83799684]i=9131535394057616379[839684]i=1013153539405761637983[9684]i=111315353940576163798384[96]③快速排序關鍵字834063138435965739796115第一趟排序后[154063136135795739]83[9684]第二趟排序后[13]15[63406135795739]8384[96]第三趟排序后1315[3940613557]63[79]838496第四趟排序后1315[35]39[614057]6379838496第五趟排序后13153539[5740]616379838496第六趟排序后1315353940[57]616379838496第七趟排序后131535394057616379838496④歸并排序關鍵字834063138435965739796115第一趟排序后[4083][1363][3584][5796][3979][1561]第二趟排序后[13406383][35578496][15396179]第三趟排序后[1335405763838496][15396179]第四趟排序后131535394057616379838496國家開放大學(中央廣播電視大學)《國家開放大學學習指南》課程教學大綱第一部分大綱說明一、課程性質與任務《國家開放大學學習指南》是國家開放大學（中央廣播電視大學）在本、專、一村一所有專業的一年級第一學期開設的、起到基礎導學作用的一門統設必修課。課程任務是：以完成學習任務的過程為導向，從學習者如何完成國家開放大學規定的專業學習任務的角度，讓學習者學會如何完成一門課程的學習、一個專業的學習，同時描述國家開放大學基本的學習方式，說明國家開放大學的學習環境，解釋國家開放大學學習平臺上基本術語的涵義，使學生能使用學習平臺的基本工具輔助完成學習活動，并且了解國家開放大學學生相關事務與管理規定。使學生初步具備利用現代遠程技術在國家開放大學進行學習的能力。二、先修課要求無三、課程的教學要求理解國家開放大學課程、專業平臺，熟練基本的遠程技術學習操作技能，掌握遠程學習的學習方法，較好利用國家開放大學資源和學習支持服務。四、課程的教學方法和教學形式建議1.本課程的特點是：網絡課程完善、課程內容新、課程形式豐富、實踐性強、涉及面廣，因此建議通過網絡，在計算機教室（或計算機多媒體教室）進行授課、答疑和討論。講授與實踐統一考慮。2.為加強和落實動手能力的培養，應保證上機機時不少于本教學大綱規定的學時。3.對于重要概念、關鍵技能和方法等問題可輔以網上答疑討論的形式。五、教學要求的層次課程的教學要求大體上分為三個層次：了解、理解和掌握。了解：能正確判別有關概念和方法。理解：能正確表達有關概念和方法的含義。掌握：在理解的基礎上加以靈活應用。第二部分教學媒體與教學過程建議一、課程教學總學時數、學分數課程教學總學時數為18學時，1學分。其中網絡課程為13學時，課堂練習和實驗為5學時。二、課程呈現方式課程以網絡課程為主，這是學生學習的主要媒體形式，因此課程呈現方式以視頻、動畫為主，配以必要的文字說明，每段視頻、動畫不超過8分鐘。視頻以學習發生的場景為主，也可以是學生訪談，體現一定交互性。課程內容可以在手機、PAD、計算機、電視等多種終端上呈現。根據課程呈現方式，課程要做到只選取完成國家開放大學學習的必備知識，擯棄過多的理論知識，盡可能簡捷。實用、方便、模塊化設計，基于問題、案例形式呈現。概念清晰、條理分明、深入淺出、便于自學。在內容上要緊密圍繞培養目標，突出重點、兼顧一般，反映當代最新技術及應用。三、主要教學媒體的使用與學時分配章節序號教學內容網絡課程學時課堂練習和實驗學時1認識國家開放大學312完成專業學習313完成課程學習314網上學習操作技能215學生事務服務21合計135四、考核本課程采用上機操作的考核方式，100%國家開放大學考核。開放教育的學生應嚴格執行該課程的有關考核文件。第三部分教學內容和教學要求1、學習活動一：認識國家開放大學（3學時）【教學內容】：任務一走進國家開放大學（一）基本介紹介紹國開的歷史，辦學模式，提供的學科門類等。（二）案例導入由國家開放大學的學生講述參加國家開放大學學習的體會與收獲（由學生講，把國家開放大學學習的特點和優勢講出來，包括學習時間、學習方式等等。）（三）國家開放大學的學習環境1.在線學習平臺；2.教師（教師群體與角色）；3.學習者（個人角色與學習小組創建）；4.學習資源（文字教材、錄像、網絡課程、流媒體資源、全媒體數字教材、小課件等）；5.學習活動（網上教學活動、論壇討論）；6.支持服務（獲得途徑：面對面的服務、電話、短信、電子郵件、網上論壇、在線即時答疑系統）；（四）拓展內容報名渠道，獲得學習資源，買書，有困難時候如何尋求幫助。任務二如何有效學習（一）學習策略1.紙質學習和電子學習的認知策略；2.制定計劃、自我監控與調節；3.學習時間管理、學習資源與環境利用、互動空間與手段（QQ群、課程論壇、學習空間）、學業求助策略。（二）學習方式1.自學（自己閱讀學習資源，做測試與練習）；2.聽講（聽看講課視頻或音頻、面授）；3.體驗；4.探究；5.問題解決；任務三學前準備了解并完成一些學前準備工作，從學習方法、知識儲備、計算機技能、學習環境等多方面了解自身的情況，為日后學習奠定基礎。【教學要求】：了解：國家開放大學的基本介紹，教學環境；掌握：國家開放大學的學習策略與方式；掌握：在國家開放大學進行學習的學前準備；2、學習活動二：完成專業學習（3學時）【教學內容】：任務一走進專業1．專業概況、專業培養方案及實施細則，專業學習的知識、能力要求。2．本專業師資隊伍、學生概況、畢業生風采。任務二專業學習過程和評價1.本專業的學習過程及主要環節2.該專業與社會證書或社會考試的接軌，學分互換等問題。任務三學位授予及其他1.申請學位相關要求。2.了解轉專業、轉學等相關政策。【教學要求】：了解：國家開放大學的專業概況及師生概況；掌握：國家開放大學專業學習過程及主要環節了解：國家開放大學的學位授予資格、轉學與轉專業相關要求3、學習活動三：完成課程學習（3學時）【教學內容】：任務一選擇課程通過學習風格測試、咨詢學業顧問、體驗課程學習，進一步明確個人的學習要求，找