《數(shù)據(jù)結(jié)構(gòu)》期中試題

PAGEPAGE1南京大學(xué)金陵學(xué)院期中試卷2007~2008學(xué)年第二學(xué)期課程名稱：《數(shù)據(jù)結(jié)構(gòu)》教師姓名：彭成磊試卷類型：開學(xué)號：__________姓名：_________專業(yè)：___________成績：_____一、選擇題（共16題，每題2.5分，計40分）1.組成數(shù)據(jù)的基本單位是（）A．?dāng)?shù)據(jù)項 B．?dāng)?shù)據(jù)類型 C．?dāng)?shù)據(jù)元素 D．?dāng)?shù)據(jù)變量2.數(shù)據(jù)結(jié)構(gòu)是研究數(shù)據(jù)的（）以及它們之間的相互關(guān)系。A．理想結(jié)構(gòu)，物理結(jié)構(gòu) B．理想結(jié)構(gòu)，抽象結(jié)構(gòu)C．物理結(jié)構(gòu)，邏輯結(jié)構(gòu) D．抽象結(jié)構(gòu)，邏輯結(jié)構(gòu)3.向一個有127個元素的順序表中插入一個新元素并保持原來順序不變，平均要移動（）個元素。A．64 B．63 C．63.5 D．75.線性表采用鏈?zhǔn)酱鎯Y(jié)構(gòu)時，其地址（）。A．必須是連續(xù)的 B．部分地址必須是連續(xù)的C．一定是不連續(xù)的 D．連續(xù)與否均可以6.在一個單鏈表中，若刪除p所指結(jié)點的后續(xù)結(jié)點，則執(zhí)行（）。A．p->next=p->next->next; B．p=p->next;p->next=p->next->next;C．p->next=p->next;D．p=p->next->next;7.一個棧的入棧序列是a,b,c,d,e,則棧的不可能的輸出序列是（）。A．edcba B．decba C．dceab D．a(chǎn)bcde8.一個隊列的入列序列是1,2,3,4,則隊列的輸出序列是（）。A．4,3,2,1 B．1,2,3,4 C．1,4,3,2 D．3,2,4,19.以數(shù)組Q[0..m－1]存放循環(huán)隊列中的元素，變量rear和qulen分別指示循環(huán)隊列中隊尾元素的實際位置和當(dāng)前隊列中元素的個數(shù)，隊列第一個元素的實際位置是（）。A．rear－qulen B．rear－qulen＋mC．m－qulen D．1＋（rear＋m－qulen）%m10.下列關(guān)于串的敘述中，正確的是（）A．一個串的字符個數(shù)即該串的長度 B．一個串的長度至少是1C．空串是由一個空格字符組成的串 D．兩個串S1和S2若長度相同，則這兩個串相等11.數(shù)組A[8][10]中,每個元素A的長度為3個字節(jié),從首地址SA開始連續(xù)存放在存儲器內(nèi),該數(shù)組按行存放時,元素A[7][4]的起始地址為（）。A．SA+141 B．SA+144 C．SA+222 D．SA+22512.稀疏矩陣一般的壓縮存儲方法有兩種,即（）和十字鏈表。A．二維數(shù)組 B．三維數(shù)組 C．三元組 D．散列13.設(shè)矩陣A是一個對稱矩陣,為了節(jié)省存儲,將其下三角部分按行序存放在一維數(shù)組B[1,n(n+1)/2]中,對下三角部分中任一元素ai,j(i>=j)(1=<i,j<=n),在一組數(shù)組B的下標(biāo)位置k的值是（）。A．i(i-1)/2+j-1 B．i(i-1)/2+j C．i(i+1)/2+j-1 D．i(i+1)/2+j14.設(shè)高度為h的二叉樹上只有度為0和度為2的結(jié)點,則此類二叉樹中所包含的結(jié)點數(shù)至少為（）。A．2h B．2h-1 C．2h+1 D．h+115.已知某二叉樹的后序遍歷序列是dabec。中序遍歷序列是deabc,它的前序遍歷序列是（）。A．a(chǎn)cbed B．decab C．deabc D．cedba16.對一個滿二叉樹,m個樹葉,n個結(jié)點,深度為h,則（）。A．n=h+m B．h+m=2n C．m=h-1 D．n=2^h-1二、判斷題（共6題，每題2.5分，計15分）1.算法就是程序。（）2.數(shù)據(jù)元素是數(shù)據(jù)的最小單位。（）3.線性結(jié)構(gòu)的特點是只有一個結(jié)點沒有前驅(qū)，只有一個結(jié)點沒有后繼，其余的結(jié)點只有一個前驅(qū)和后繼。（）4.線性表的鏈接存儲，表中元素的邏輯順序與物理順序一定相同。（）5.語句p=p->next完成了指針賦值并使p指針得到了p指針?biāo)负罄^結(jié)點的數(shù)據(jù)域值（）6.二叉樹中任何一個結(jié)點的度都是2。（）三、填空題（共18空，每空2.5分，計45分）1.線性結(jié)構(gòu)中元素之間存在________關(guān)系,樹形結(jié)構(gòu)中元素之間存在________關(guān)系,圖形結(jié)構(gòu)中元素之間存在________關(guān)系。2.算法的五個重要特性是________、________、________、________、________。3.設(shè)有一批數(shù)據(jù)元素,為了最快的存儲某元素,數(shù)據(jù)結(jié)構(gòu)宜用________結(jié)構(gòu),為了方便插入一個元素,數(shù)據(jù)結(jié)構(gòu)宜用________結(jié)構(gòu)。4.順序表中邏輯上相鄰的元素物理位置()相鄰，單鏈表中邏輯上相鄰的元素物理位置________相鄰。5.在非空雙向循環(huán)鏈表中，在結(jié)點q的前面插入結(jié)點p的過程如下：p->prior=q->prior;q->prior->next=p;p->next=q;_______________;6.已知L是無表頭結(jié)點的單鏈表，請從下列提供的答案中選擇合適的語句序列，實現(xiàn)表尾插入s結(jié)點________。A．p->next=s; B．p=L; C．L=s;D．p->next=s->next; E．s->next=p->next;F．s->next=L; G．s->next=null; H．while(p->next!=0)p=p->next;I．while(p->next!=null)p=p->next;7.棧的特點是______________，隊列的特點是________________。8.設(shè)棧S和隊列Q的初始狀態(tài)皆為空，元素a1，a2，a3，a4，a5和a6依次通過一個棧，一個元素出棧后即進(jìn)入隊列Q，若6個元素出隊列的順序是a3，a5，a4，a6，a2，a1則棧S至少應(yīng)該容納________個元素。9.己知二維數(shù)組A[m][n]采用行序為主方式存儲,每個元素占k個存儲單元,并且第一個元素的存儲地址是LOC(A[0][0]),則A[i][j]的地址是________。10.一棵二叉樹有67個結(jié)點，這些結(jié)點的度要么是0，要么是2。這棵二叉樹中度為2的結(jié)點有________個。20080423數(shù)據(jù)結(jié)構(gòu)期中考試參考答案選擇1.C2.C3.C5.D6.A7.C8.B9.D10.A