數(shù)據(jù)結構09級信本期中試卷201155

河北北方學院2021-2021學年第二學期期中考試一試卷?數(shù)據(jù)構造?_〔供醫(yī)學信息本科專業(yè)使用〕___本卷須知：___1．請按要求在試卷的密封區(qū)填寫專業(yè)、班級、姓名和學號。_號2．請認真閱讀各樣題目的答題要求，在規(guī)定的地點填寫答案。學3．不要在試卷上亂寫亂畫，不要在密封區(qū)填寫無關的內容。___題號一二三四五總分_____得分__名姓總分合計人：復核人：___得分評卷人一、填空___〔共20分，每空1分?！砡_級1.宏觀地講，數(shù)據(jù)構造是一門研究非數(shù)值性程序設計上當算機操作的班________________________的學科。2.下面程序段的時間復雜度為________。___for(inti=0;i<m;i++)__for(intj=0;j<n;j++)___a[i][j]=i*j;業(yè)3.我們以程序語句的__________即_______作為時間量度，專來做為程序效率剖析的標準。4.設有一個次序棧S，元素s1,s2,s3,s4,s5,s6依次進棧，如精選果6個元素的出棧次序為s3,s2,s5,s6,s4,s1，那么次序棧的層數(shù)起碼為_______。一個鏈行列中，假定front指針等于NULL往常為_____，rear指針等于NULL往常為_____。n維數(shù)組是一個同構的數(shù)據(jù)構造，即它的每一個數(shù)據(jù)元素均屬于_______________或。假定將結點New插入單鏈表中，*p指向欲插入結點，將New插入后來端,語句如下：p->Next=New；New->Next=p->Next；那么會產(chǎn)生的問題是____________。關于數(shù)組仿真的堆棧，假定預先分派的存儲空間為Maxsize=Maxtop+1，表示指針的向量為top，那么push操作中產(chǎn)生上溢的指針情況________________，如此可能產(chǎn)生的情況是___________。假定以temp做為暫存出棧元素的變量，請描繪pop操作的主要步驟：。使用環(huán)狀行列解決空間利用問題，假定以數(shù)組描繪行列，預先分派的存儲空間長度為Maxsize，那么環(huán)狀行列的有效利用空間為___________；隊首〔或隊尾〕指針的前移方式為：______________。函數(shù)調用過程中，調用函數(shù)和被調函數(shù)之間的鏈接和信息互換需要通過_____來進行。當有多個函數(shù)組成嵌套調用時，按照____________原那么。普通樹形構造與二叉樹的二叉鏈表的表示法中，唯一不同就是其右指針指向的是_______________。當以二叉鏈表作為樹或森林的存儲構造時，能夠使用二叉樹的兩種方式遍歷一棵樹或森林。13.中序線索滿二叉樹中非終端結點的直接前驅是___________________。得分評卷人二、選擇題〔共10分，每題1分。〕精選1.循環(huán)單鏈表不擁有的特點是【】A．具備隨機接見特性B．插入刪除不需要移動元素C．不必預先估計存儲空間D．循環(huán)單鏈表可由頭點或尾結點確定2.堆棧和行列都是【】A．次序存儲的線性構造B．鏈式存儲的次序構造C．限制存取點的線性構造D．限制存取點的非線性構造設三個函數(shù)f、g、h，函數(shù)式分別為：f(n)＝100n3＋n2＋1000g(n)＝25n3＋5000n2h(n)＝n1.5＋5000nlgn。以下關系中不建立的是【】A.f(n)＝O(g(n))B．g(n)＝O(f(n))C．h(n)＝O(n1.5)D．h(n)＝O(nlgn)4.往常不屬于行列應用范圍的是【】A．優(yōu)先行列B．操作系統(tǒng)中的工作調動C．辦理子函數(shù)的調用D．用于打印緩沖“spooling〞在一棵二叉樹的二叉鏈表中，空指針域數(shù)等于非空指針域數(shù)加【】A．2B．1C．0D．–1在一個單鏈表中，假定q結點是p結點的前驅結點，假定在q與p之間插入結點s，那么履行【】A．s→link=p→link;q→link=s;B．p→link=s;s→link=q;C．p→link=s→link;s→link=p;D．s→link=p；q→link=s;7.關于樹的特性，描繪有誤的是【】A．樹是層次構造B．樹結點具備唯一的前趨與后繼C．遞歸是樹固有的特性D．N元樹的分支度即為N8.相關如下聲明，以下那個語句的指定是正確的？【】char*s1=〞hello!〞;char*s2=〞excellent〞;char*string;chars1[20];精選A．s1=s2;B．s2=string;C．string=s1;D．s1[20]=*s2;關于次序存儲的行列，存儲空間大小為n，頭指針為F，尾指針為R。假定在邏輯上看一個環(huán)，那么行列中元素的個數(shù)為【】A.R-FB.n+R-FC.(R-F+1)modnD.(n+R-F)modn10.設有一個nn的對稱矩陣A，將其上三角局部按行寄存在一個一維數(shù)組B中，A[0][0]寄存于B[0]中，那么第i行的對角元素A[i][i]寄存于B中〔〕處。A.(i+3)*i/2B.(i+1)*i/2C.(2n-i+1)*i/2D.(2n-i-1)*i/2得分評卷人三、判斷題〔共10分，每題1分?！?、在數(shù)組構造中，可根據(jù)給出的索引值，找到該數(shù)組的內容值，因此說數(shù)組中的數(shù)據(jù)具備隨機存取性。........................................〔〕2、線性表的邏輯次序與物理次序一致。...........................〔〕3、鑒于鏈棧的元素序列，插入與刪除運算只能在序列首進行。.......〔〕4、對含有n個結點、樹高為h的二叉樹實施前、中、后序遍歷，空間復雜度均為O(h)。.......................................................〔〕5、C語言中，字符串在函數(shù)間是以傳址調用的方式進行傳達的，形參就是字符串的名稱。....................................................〔〕6、擁有n個結點的完全二叉樹的深度為不大于log2n的整數(shù)。.......〔〕7、在程序運行過程中能夠擴大的數(shù)組是動向分派的構造數(shù)組。這種數(shù)組在聲明它時需要使用數(shù)組指針。........................................〔〕8、線性的數(shù)據(jù)構造能夠次序存儲，也能夠鏈接存儲。非線性的數(shù)據(jù)構造只能鏈接存儲。......................................................〔〕9、往常遞歸的算法簡單、易懂、容易編寫，而且履行的效率也高。...〔〕10、關于樹進行后序遍歷的結果等于對其相應的二叉樹中序遍歷的結果；樹的精選先序遍歷結果等于對其相應二叉樹先序遍歷的結果。....〔〕得分評卷人四、綜合題〔共35分。每題占分在題后標明?！?、有一稀疏矩陣如右下表所示。請描繪其存儲方式。〔7分〕0123456780003020000110040007020500060003000000000400090008050000000002、設有一個長整型的二維數(shù)組共有7行8列，在內存中的開端地點為100。懇求出以列為主序進行數(shù)據(jù)存儲時，第5行第6列的元素的內存地點?！?分〕3、現(xiàn)有一個班級40個同學的姓名、性別、年紀和地址,請將學生資料定義成一個構造數(shù)組。并列出對構造數(shù)組成員的接見形式〔列出一二項即可〕?！?分〕精選4、請將前序表達式“*/+A*BCD－E/FG〞變換為中序、后序表達式?！?分〕5、設有廣義表F(A(a,(b,c,d)),B(e))，請描繪其存儲構造，并會出其鏈式存儲構造邏輯圖?！?分〕6、有一二叉樹如下，請分別寫出對其前序、中序、后序遍歷的次序?！?分〕+－*a/ef－cd精選得分評卷人五、算法及剖析題〔共25分。每題占分在題后標明?！?、二叉查找樹中的結點種類B_TreeNode定義為:structB_TreeNode{intdata;B_TreeNode*left,*right;};其中data為結點值域，left和right分別為指向左、右子結點的指針域。參數(shù)t指向一棵二叉查找樹，該樹的廣義表表示為:(25(10(5,16(12)),40(32(,38))))。根據(jù)下面算法按標號把答案填寫到算法后邊相應標號的地點?！裁靠?分，本題合計6分〕intLN(B_TreeNode*t,intX){if(t==NULL)return0;elseif(t->data==X)return1;elseif(t->data>X)return1+LN(t->left,X);elsereturn1+LN(t->right,X);}履行LN(pt,40)調用后返回的值為__________。履行LN(pt,38)調用后返回的值為__________。履行LN(pt,5)調用后返回的值為_________。2、試寫出使用鏈表構造描繪“輸入限制性雙端行列〞的算法?！脖绢}13分