數(shù)據(jù)結構隨堂測驗(帶答案)

數(shù)據(jù)結構隨堂測驗(帶答案)數(shù)據(jù)結構隨堂測驗(帶答案)數(shù)據(jù)結構隨堂測驗(帶答案)數(shù)據(jù)結構隨堂測驗(帶答案)編制僅供參考審核批準生效日期地址：電話：傳真:郵編:第1次測驗算法的時間復雜度取決于（C）A．問題的規(guī)模B.待處理數(shù)據(jù)的初態(tài)C.A和B從邏輯上可以把數(shù)據(jù)結構分為（C）兩大類。A．動態(tài)結構、靜態(tài)結構B．順序結構、鏈式結構C．線性結構、非線性結構D．初等結構、構造型結構以下屬于邏輯結構的是（C）。A．順序表B.哈希表C.有序表D.單鏈表下述哪一條是順序存儲結構的優(yōu)點（A）A．存儲密度大B．插入運算方便C．刪除運算方便D．可方便地用于各種邏輯結構的存儲表示若某線性表最常用的操作是存取任一指定序號的元素和在最后進行插入和刪除運算，則利用（A）存儲方式最節(jié)省時間。A．順序表B．雙鏈表C．帶頭結點的雙循環(huán)鏈表D．單循環(huán)鏈表某線性表中最常用的操作是在最后一個元素之后插入一個元素和刪除第一個元素，則采用（D）存儲方式最節(jié)省運算時間。A．單鏈表B．僅有頭指針的單循環(huán)鏈表C．雙鏈表D．僅有尾指針的單循環(huán)鏈表若某表最常用的操作是在最后一個結點之后插入一個結點或刪除最后一個結點。則采用（D）存儲方式最節(jié)省運算時間。A．單鏈表B．雙鏈表C．單循環(huán)鏈表D．帶頭結點的雙循環(huán)鏈表鏈表不具有的特點是（B）A．插入、刪除不需要移動元素B．可隨機訪問任一元素C．不必事先估計存儲空間D．所需空間與線性長度成正比對于順序表，訪問第i位置結點和增加、刪除結點的時間復雜度為（C）。A.O(n)O(n)B.O(n)O(1)C.O(1)O(n)D.O(1)O(1)線性表以鏈接方式存儲時，訪問第i位置元素的時間復雜性為（C）A．O(i)B．O(1)C．O(n)D．O(i-1)下面程序段的時間復雜度是O(n)。inti=1,k=100;while(i<n){ k=k+1; i+=2;}在單鏈表L中，指針p所指結點有后繼結點的條件是：________。長度為n的順序表，在其第i個元素（1≤i≤n+1）之前插入一個元素時，需向后移動個元素，刪除第i個元素（1≤i≤n）時，需向前移動__個元素。請寫出順序表的類型定義。請寫出單鏈表的類型定義。第2次測驗一、選擇題對于棧操作數(shù)據(jù)的原則是（B）。A.先進先出B.后進先出C.后進后出D.不分順序一個棧的輸入序列為123…n，若輸出序列的第一個元素是n，輸出第i（1<=i<=n）個元素是（B）。A.不確定B.n-i+1C.iD.n-i若一個棧的輸入序列為1,2,3,…,n，輸出序列的第一個元素是i，則第j個輸出元素是（D）。A.i-j-1B.i-jC.j-i+1D.不確定的有六個元素6，5，4，3，2，1的順序進棧，問下列哪一個不是合法的出棧序列（C）A.543612B.453126C.346521D.234156棧在（D）中應用。A.遞歸調用B.子程序調用C.表達式求值D.A，Ｂ，Ｃ一個遞歸算法必須包括（B）。A.遞歸部分B.終止條件和遞歸部分C.迭代部分D.終止條件和迭代部分表達式a*(b+c)-d的后綴表達式是(B)。A．abcd*+-B.abc+*d-C.abc*+d-D.-+*abcd設計一個判別表達式中左，右括號是否配對出現(xiàn)的算法，采用（D）數(shù)據(jù)結構最佳。A．線性表的順序存儲結構B.隊列C.線性表的鏈式存儲結構D.棧用鏈接方式存儲的隊列，在進行刪除運算時（D）。A.僅修改頭指針 B.僅修改尾指針C.頭、尾指針都要修改 D.頭、尾指針可能都要修改假設以數(shù)組A[m]存放循環(huán)隊列的元素,其頭尾指針分別為front和rear，則當前隊列中的元素個數(shù)為（A）。A．(rear-front+m)%mB．rear-front+1C．(front-rear+m)%mD．(rear-front)%m循環(huán)隊列存儲在數(shù)組A[0..m]中，則入隊時的操作為（D）。A.rear=rear+1B.rear=(rear+1)mod(m-1)C.rear=(rear+1)modmD.rear=(rear+1)mod(m+1)若用一個大小為6的數(shù)組來實現(xiàn)循環(huán)隊列，且當前rear和front的值分別為0和3，當從隊列中刪除一個元素，再加入兩個元素后，rear和front的值分別為多少(B)A.1和5B.2和4C.4和2D.5和1最大容量為n的循環(huán)隊列，隊尾指針是rear，隊頭是front，則隊空的條件是（B）。A.(rear+1)MODn=frontB.rear=frontC．rear+1=frontD.(rear-l)MODn=front棧和隊列都是（C）A．順序存儲的線性結構B.鏈式存儲的非線性結構C.限制存取點的線性結構D.限制存取點的非線性結構設棧S和隊列Q的初始狀態(tài)為空，元素e1，e2，e3，e4,e5和e6依次通過棧S，一個元素出棧后即進隊列Q，若6個元素出隊的序列是e2，e4，e3,e6,e5,e1則棧S的容量至少應該是(C)。A．6B.4C.3D.2下面關于串的的敘述中，哪一個是不正確的（B）A．串是字符的有限序列B．空串是由空格構成的串C．模式匹配是串的一種重要運算D．串既可以采用順序存儲，也可以采用鏈式存儲設有兩個串p和q，其中q是p的子串，求q在p中首次出現(xiàn)的位置的算法稱為（C）A．求子串B．聯(lián)接C．匹配D．求串長串的長度是指（B）A．串中所含不同字母的個數(shù)B．串中所含字符的個數(shù)C．串中所含不同字符的個數(shù)D．串中所含非空格字符的個數(shù)設有一個10階的對稱矩陣A，采用壓縮存儲方式，以行序為主存儲，a11為第一元素，其存儲地址為1，每個元素占一個地址空間，則a85的地址為（B）。A.13B.33C.18D.40設有數(shù)組A[i,j]，數(shù)組的每個元素長度為3字節(jié)，i的值為1到8，j的值為1到10，數(shù)組從內存首地址BA開始順序存放，當用以列為主存放時，元素A[5，8]的存儲首地址為(B)。A.BA+141B.BA+180C.BA+222D.BA+225有一個100*90的稀疏矩陣，非0元素有10個，設每個整型數(shù)占2字節(jié)，則用三元組表示該矩陣時，所需的字節(jié)數(shù)是（B）。A.60B.66C.18000D.33已知廣義表L=（（x,y,z），a，（u，t，w）），從L表中取出原子項t的運算是（D）。A.head（tail（tail（L）））B.tail（head（head（tail（L））））C.head（tail（head（tail（L））））D.head（tail(head（tail（tail（L）））））廣義表運算式Tail(((a,b),(c,d)))的操作結果是（C）。A.(c,d)B.c,dC.((c,d))D.d設廣義表L=（（a,b,c）），則L的長度和深度分別為（C）。A.1和1B.1和3C.1和2D.2和3下面說法不正確的是(A)。A.廣義表的表頭總是一個廣義表B.廣義表的表尾總是一個廣義表C.廣義表難以用順序存儲結構D.廣義表可以是一個多層次的結構第3次測驗在下述結論中，正確的是（D）。①只有一個結點的二叉樹的度為0;②二叉樹的度為2；③二叉樹的左右子樹可任意交換;④深度為K的完全二叉樹的結點個數(shù)小于或等于深度相同的滿二叉樹。A．①②③B．②③④C．②④D．①④有關二叉樹下列說法正確的是（B）。A．二叉樹的度為2B．一棵二叉樹的度可以小于2C．二叉樹中至少有一個結點的度為2D．二叉樹中任何一個結點的度都為2設樹T的度為4，其中度為1，2，3和4的結點個數(shù)分別為4，2，1，1則T中的葉子數(shù)為（D）。A．5B．6C．7D．8一棵完全二叉樹上有1001個結點，其中葉子結點的個數(shù)是（E）。A．250B．500C．254D．505E．以上答案都不對一棵二叉樹高度為h,所有結點的度或為0，或為2，則這棵二叉樹最少有(B)結點。A．2hB．2h-1C．2h+1D．h+1設森林F對應的二叉樹為B，它有m個結點，B的根為p,p的右子樹結點個數(shù)為n,森林F中第一棵樹的結點個數(shù)是（A）。A．m-nB．m-n-1C．n+1D．條件不足，無法確定利用二叉鏈表存儲樹，則根結點的右指針是（C）。A．指向最左孩子B．指向最右孩子C．空D．非空在下列存儲形式中，哪一個不是樹的存儲形式（D）。A．雙親表示法B．孩子鏈表表示法C．孩子兄弟表示法D．順序存儲表示法已知一棵二叉樹的前序遍歷結果為ABCDEF,中序遍歷結果為CBAEDF,則后序遍歷的結果為（A）。A．CBEFDAB．FEDCBAC．CBEDFAD．不定引入二叉線索樹的目的是（A）。A．加快查找結點的前驅或后繼的速度B．為了能在二叉樹中方便的進行插入與刪除C．為了能方便的找到雙親D．使二叉樹的遍歷結果唯一線索二叉樹是一種（C）結構。A．邏輯B．邏輯和存儲C．物理D．線性設給定權值總數(shù)有n個，其哈夫曼樹的結點總數(shù)為(D)。A．不確定B．2nC．2n+1D．2n-1設無向圖的頂點個數(shù)為n，則該圖最多有（B）條邊。A．n-1B．n(n-1)/2C．n(n+1)/2D．0E．n2一個n個頂點的連通無向圖，其邊的個數(shù)至少為（A）。A．n-1B．nC．n+1D．nlogn一個有n個結點的圖，最少有（B）個連通分量，最多有（D）個連通分量。A．0B．1C．n-1D．n在一個無向圖中，所有頂點的度數(shù)之和等于所有邊數(shù)（B）倍，在一個有向圖中，所有頂點的入度之和等于所有頂點出度之和的（C）倍。A．1/2B．2C．1D．4下列哪一種圖的鄰接矩陣是對稱矩陣（B）A．有向圖B．無向圖C．AOV網D．AOE網一個有向無環(huán)圖的拓撲排序序列（B）是唯一的。一定B．不一定第4次測驗對N個元素的表做順序查找時，若查找每個元素的概率相同，則平均查找長度為（A）。A．（N+1）/2B.N/2C.ND.[（1+N）*N]/2下面關于二分查找的敘述正確的是（D）。A.表必須有序，表可以順序方式存儲，也可以鏈表方式存儲B.表必須有序且表中數(shù)據(jù)必須是整型，實型或字符型C.表必須有序，而且只能從小到大排列D.表必須有序，且表只能以順序方式存儲當采用分塊查找時，數(shù)據(jù)的組織方式為（B）。A．數(shù)據(jù)分成若干塊，每塊內數(shù)據(jù)有序B．數(shù)據(jù)分成若干塊，每塊內數(shù)據(jù)不必有序，但塊間必須有序，每塊內最大（或最?。┑臄?shù)據(jù)組成索引塊C.數(shù)據(jù)分成若干塊，每塊內數(shù)據(jù)有序，每塊內最大（或最?。┑臄?shù)據(jù)組成索引塊D.數(shù)據(jù)分成若干塊，每塊（除最后一塊外）中數(shù)據(jù)個數(shù)需相同二叉查找樹的查找效率與二叉樹的(（1）)有關,在(（2）)時其查找效率最低。（C）(1):A.高度B.結點的多少C.樹型D.結點的位置(2):A.結點太多B.完全二叉樹C.呈單支樹D.結點太復雜分別以下列序列構造二叉排序樹，與用其它三個序列所構造的結果不同的是(C)。A．（100，80，90，60，120，110，130）B.（100，120，110，130，80，60，90）C.（100，60，80，90，120，110，130）D.(100，80，60，90，120，130，110)設有一組記錄的關鍵字為{19，14，23，1，68，20，84，27，55，11，10，79}，用鏈地址法構造散列表，散列函數(shù)為H（key）=keyMOD13,散列地址為1的鏈中有（D）個記錄。A．1B.2C.3D.4若采用鏈地址法構造散列表，散列函數(shù)為H（key）=keyMOD17，則需(（1）)個鏈表。這些鏈的鏈首指針構成一個指針數(shù)組，數(shù)組的下標范圍為(（2）)。(AC)（1）A．17B.13C.16D.任意（2）A．0至17B.1至17C.0至16D.1至16假定有k個關鍵字互為同義詞，若用線性探測法把這k個關鍵字存入散列表中，至少要進行多少次探測(D)。A．k-1次B.k次C.k+1次D.k（k+1）/2次散列表的地址區(qū)間為0-16,散列函數(shù)為H(K)=Kmod17。采用線性探測法處理沖突，并將關鍵字序列26，25，72，38，8，18，59依次存儲到散列表中。（1）元素59存放在散列表中的地址是（D）。A．8B.9C.10D.11（2）存放元素59需要搜索的次數(shù)是（C）。A．2B.3C.4D.5某內排序方法的穩(wěn)定性是指(D)。A．該排序算法不允許有相同的關鍵字記錄B．該排序算法允許有相同的關鍵字記錄C．平均時間為0（nlogn）的排序方法D．以上都不對下列內部排序算法中：A．快速排序B.直接插入排序C.二路歸并排序D.直接選擇排序E.起泡排序F.堆排序（1）其比較次數(shù)與序列初態(tài)無關的算法是（CD）（2）在初始序列已基本有序（除去n個元素中的某k個元素后即呈有序，k<<n）的情況下，排序效率最高的算法是（B）（3）排序的平均時間復雜度為O(n?logn)的算法是（ACF）,為O(n?n)的算法是（BDE）數(shù)據(jù)序列（8，9，10，4，5，6，20，1，2）只能是下列排序算法中的()兩趟排序后的結果。(C)A．選擇排序B.冒泡排序C.插入排序D.堆排序數(shù)據(jù)序列（2，1，4，9，8，10，6，20）只能是下列排序算法中的()的兩趟排序后的結果。(A