數(shù)據(jù)結(jié)構(gòu)試卷A

《數(shù)據(jù)結(jié)構(gòu)試卷A》由會(huì)員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在教育資源-天天文庫(kù)。

1、東莞理工學(xué)院城市學(xué)院（本科）試卷（A卷）2013-2014學(xué)年第一學(xué)期開(kāi)課單位：計(jì)算機(jī)與信息科學(xué)系，考試形式：閉卷，允許帶入場(chǎng)科目：數(shù)據(jù)結(jié)構(gòu)班級(jí)：12軟工班姓名：學(xué)號(hào)：題序一二三四五六總分得分評(píng)卷人一、單項(xiàng)選擇題（本大題共15小題，每小題2分，共30分）在每小題列出的四個(gè)備選項(xiàng)中只有一個(gè)是符合題目要求的，請(qǐng)將其代碼填寫(xiě)下表中。1234567891011121314151.在數(shù)據(jù)結(jié)構(gòu)中，從邏輯上可以把數(shù)據(jù)結(jié)構(gòu)分成（C）。A．動(dòng)態(tài)結(jié)構(gòu)和靜態(tài)結(jié)構(gòu)B．緊湊結(jié)構(gòu)和非緊湊結(jié)構(gòu)C．線性結(jié)構(gòu)和非線性結(jié)構(gòu)D．內(nèi)部結(jié)構(gòu)和外部結(jié)構(gòu)2.一個(gè)向量首元素的

2、存儲(chǔ)地址是100，每個(gè)元素的長(zhǎng)度為2，則第5個(gè)元素的地址是（B）。A．110B．108C．100D．1203.在n個(gè)結(jié)點(diǎn)的順序表中，算法的時(shí)間復(fù)雜度是O(1)的操作是（A）。A．訪問(wèn)第i個(gè)結(jié)點(diǎn)（1≤i≤n）和求第i個(gè)結(jié)點(diǎn)的直接前驅(qū)（2≤i≤n）B．在第i個(gè)結(jié)點(diǎn)后插入一個(gè)新結(jié)點(diǎn)（1≤i≤n）C．刪除第i個(gè)結(jié)點(diǎn)（1≤i≤n）D．將n個(gè)結(jié)點(diǎn)從小到大排序4.線性表若采用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)時(shí)，要求內(nèi)存中可用存儲(chǔ)單元的地址（D）。A．必須是連續(xù)的B．部分地址必須是連續(xù)的C．一定是不連續(xù)的D．連續(xù)或不連續(xù)都可以5.將兩個(gè)各有n個(gè)元素的有序表歸并成一

3、個(gè)有序表，其最少的比較次數(shù)是（A）。A．nB．2n-1C．2nD．n-16.在一個(gè)長(zhǎng)度為n的順序表中，在第i個(gè)元素（1≤i≤n+1）之前插入一個(gè)新元素時(shí)須向后移動(dòng)（B）個(gè)元素。A．n-iB．n-i+1C．n-i-1D．i7.在雙向鏈表存儲(chǔ)結(jié)構(gòu)中，刪除p所指的結(jié)點(diǎn)時(shí)須修改指針（A）。A．p->next->prior=p->prior;p->prior->next=p->next;B．p->next=p->next->next;p->next->prior=p;《數(shù)據(jù)結(jié)構(gòu)》A卷第6頁(yè)共6頁(yè)C．p->prior->next=p;p->

4、prior=p->prior->prior;D．p->prior=p->next->next;p->next=p->prior->prior;1.若讓元素1，2，3，4，5依次進(jìn)棧，則出棧次序不可能出現(xiàn)在（C）種情況。A．5，4，3，2，1B．2，1，5，4，3C．4，3，1，2，5D．2，3，5，4，12.對(duì)n個(gè)關(guān)鍵字作快速排序，在最壞情況下，算法的時(shí)間復(fù)雜度是（B）。A．O(n)B．O(n2)C．O(nlog2n)D．O(n3)3.從未排序序列中依次取出元素與已排序序列中的元素進(jìn)行比較，將其放入已排序序列的正確位置上的方法，

5、這種排序方法稱(chēng)為（C）。A．歸并排序B．冒泡排序C．插入排序D．選擇排序4.分別以下列序列構(gòu)造二叉排序樹(shù)，與用其它三個(gè)序列所構(gòu)造的結(jié)果不同的是（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)5.在一個(gè)有向圖中，所有頂點(diǎn)的入度之和等于所有頂點(diǎn)的出度之和的（B）倍。A．1/2B．1C．2D．46.在下列存儲(chǔ)形式中，（B）不是樹(shù)的存儲(chǔ)形式？A．雙親表示法

6、B．孩子鏈表表示法C．孩子兄弟表示法D．順序存儲(chǔ)表示法7.廣義表((a,b,c,d))的表頭是（C），表尾是（B）。A．a(chǎn)B．()C．(a,b,c,d)D．(b,c,d)8.假設(shè)以行序?yàn)橹餍虼鎯?chǔ)二維數(shù)組A=array[1..100,1..100]，設(shè)每個(gè)數(shù)據(jù)元素占2個(gè)存儲(chǔ)單元，基地址為10，則LOC[5,5]=（B）。A．808B．818C．1010D．1020一、填空題(每空1分，共15分)1.假定一棵樹(shù)的廣義表表示為A（C，D（E，F(xiàn)，G），H（I，J）），則樹(shù)中所含的結(jié)點(diǎn)數(shù)為_(kāi)__9個(gè)，樹(shù)的度為_(kāi)3_。2.數(shù)據(jù)的物

7、理結(jié)構(gòu)主要包括順序結(jié)構(gòu)和鏈?zhǔn)浇Y(jié)構(gòu)兩種情況。3.為了能有效地應(yīng)用HASH查找技術(shù)，必須解決的兩個(gè)問(wèn)題是構(gòu)建HASH樹(shù)和解決沖突問(wèn)題。4.一個(gè)算法的效率可分為空間效率和時(shí)間效率。5.下面程序段的時(shí)間復(fù)雜度是n2。s=0;for(i=0;i

8、.top==m-1)printf(“overflow”);《數(shù)據(jù)結(jié)構(gòu)》A卷第6頁(yè)共6頁(yè)else{___stack.top++;__stack.s[stack.top]=x;___}}1.下列算法實(shí)現(xiàn)在二叉排序樹(shù)上查找關(guān)鍵值k，請(qǐng)?jiān)谙聞澗€處填上正確的語(yǔ)句。type