數(shù)據(jù)結(jié)構(gòu)試題及答案

　　導(dǎo)語：數(shù)據(jù)結(jié)構(gòu)考試會主要考倒什么呢�？忌鷤儾环量纯�。以下是小編搜集并整理的有關(guān)內(nèi)容，希望對大家有所幫助!

　　一、單項選擇題

　　1、連續(xù)存儲設(shè)計時，存儲單元的地址( )。

　　A、一定連續(xù)

　　B、一定不連續(xù)

　　C、不一定連續(xù)

　　D、部分連續(xù)，部分不連續(xù)

　　2、以下屬于邏輯結(jié)構(gòu)的是( )。

　　A、順序表

　　B、 哈希表

　　C、有序表

　　D、 單鏈表

　　3、 設(shè)有數(shù)組A[i,j]，數(shù)組的每個元素長度為3字節(jié)，i的值為1 到8 ，j的值為1 到10，數(shù)組從內(nèi)存首地址BA開始順序存放，當(dāng)用以列為主存放時，元素A[5，8]的存儲首地址為( )。

　　A、 BA+141

　　B、 BA+180

　　C、 BA+222

　　D、 BA+225

　　4、若某線性表最常用的操作是存取任一指定序號的元素和在最后進(jìn)行插入和刪除運算，則利用( )存儲方式最節(jié)省時間。

　　A、順序表

　　B、雙鏈表

　　C、帶頭結(jié)點的雙循環(huán)鏈表

　　D、單循環(huán)鏈表

　　5、某線性表中最常用的操作是在最后一個元素之后插入一個元素和刪除第一個元素，則采用( )存儲方式最節(jié)省運算時間。

　　A、單鏈表

　　B、僅有頭指針的單循環(huán)鏈表

　　C、雙鏈表

　　D、僅有尾指針的單循環(huán)鏈表

　　6、線性表( a1,a2,…,an)以鏈接方式存儲時，訪問第i位置元素的時間復(fù)雜性為( )。

　　A、O(i)

　　B、O(1)

　　C、O(n)

　　D、O(i-1)

　　7、對于一個頭指針為head的帶頭結(jié)點的單鏈表，判定該表為空表的條件是( )。

　　A、head==NULL

　　B、head→next==NULL

　　C、head→next==head

　　D、head!=NULL

　　8、 若已知一個棧的入棧序列是1,2,3,…,n，其輸出序列為p1,p2,p3，…，pN,若pN是n，則pi是( )。

　　A、 i

　　B、 n-i

　　C、 n-i+1

　　D、 不確定

　　9、 有六個元素6，5，4，3，2，1 的順序進(jìn)棧，問下列哪一個不是合法的出棧序列?( )。

　　A、 5 4 3 6 1 2

　　B、 4 5 3 1 2 6

　　C、 3 4 6 5 2 1

　　D、 2 3 4 1 5 6

　　10、 散列文件使用散列函數(shù)將記錄的關(guān)鍵字值計算轉(zhuǎn)化為記錄的存放地址，因為散列函數(shù)是一對一的關(guān)系，則選擇好的( )方法是散列文件的關(guān)鍵。

　　A、 散列函數(shù)

　　B、 除余法中的質(zhì)數(shù)

　　C、 沖突處理

　　D、 散列函數(shù)和沖突處理

　　二、填空題

　　1、數(shù)據(jù)的物理結(jié)構(gòu)包括 的表示和 的表示。

　　2、數(shù)據(jù)結(jié)構(gòu)中評價算法的兩個重要指標(biāo)是 。

　　3、當(dāng)線性表的元素總數(shù)基本穩(wěn)定，且很少進(jìn)行插入和刪除操作，但要求以最快的速度存取線性表中的元素時，應(yīng)采用_______存儲結(jié)構(gòu)。

　　4、線性表L=(a1,a2,…,an)用數(shù)組表示，假定刪除表中任一元素的概率相同，則刪除一個元素平均需要移動元素的個數(shù)是________。

　　5、在一個長度為n的順序表中第i個元素(1<=i<=n)之前插入一個元素時，需向后移動________個元素。

　　6、鏈接存儲的特點是利用________來表示數(shù)據(jù)元素之間的邏輯關(guān)系。

　　7、 一個棧的輸入序列是：1，2，3則不可能的棧輸出序列是_______。

　　8、區(qū)分循環(huán)隊列的滿與空，只有兩種方法，它們是______和______。

　　三、判斷題

　　1、算法可以用不同的語言描述，如果用C 語言或PASCAL語言等高級語言來描述，則算法實際上就是程序了。( )

　　2、 數(shù)據(jù)結(jié)構(gòu)的基本操作的設(shè)置的最重要的準(zhǔn)則是，實現(xiàn)應(yīng)用程序與存儲結(jié)構(gòu)的獨立。( )

　　3、 稀疏矩陣壓縮存儲后，必會失去隨機存取功能。( )

　　4、 數(shù)組是同類型值的集合。( )

　　5、 數(shù)組可看成線性結(jié)構(gòu)的一種推廣，因此與線性表一樣，可以對它進(jìn)行插入，刪除等操作。( )

　　6、 稀疏矩陣壓縮存儲后，必會失去隨機存取功能。( )

　　7、 二維以上的數(shù)組其實是一種特殊的廣義表。( )

　　8、 文件是記錄的集合，每個記錄由一個或多個數(shù)據(jù)項組成，因而一個文件可看作由多個記錄組成的數(shù)據(jù)結(jié)構(gòu)。( )

　　三、解答題

　　1、 數(shù)據(jù)結(jié)構(gòu)是一門研究什么內(nèi)容的學(xué)科?

　　2、數(shù)據(jù)元素之間的關(guān)系在計算機中有幾種表示方法?各有什么特點?

　　3、 有5 個元素，其入棧次序為：A，B，C，D，E，在各種可能的出棧次序中，以元素C，D最先出棧(即C第一個且D第二個出棧)的次序有哪幾個?

　　四、程序閱讀題

　　1、請閱讀以下程序，寫出此程序所要完成的功能，及時間復(fù)雜度。

　　int compare( SqList A, SqList B )

　　{ j=0;

　　while ( j

　　if ( A、elem[j] < B、elem[j] ) return(-1);

　　else if ( A、elem[j] > B、elem[j] ) return(1);

　　else j++;

　　if ( A、length == B、length ) return (0);

　　else if ( A、length < B、length ) return(-1);

　　else return(1);

　　}

　　2、將二叉樹bt中每一個結(jié)點的左右子樹互換的C語言算法如下，其中ADDQ(Q,bt),DELQ(Q),EMPTY(Q)分別為進(jìn)隊，出隊和判別隊列是否為空的函數(shù)，請?zhí)顚懰惴ㄖ械每瞻滋�，完成其功能�?/p>

　　typedef struct node

　　{int data ; struct node *lchild, *rchild; }btnode;

　　void EXCHANGE(btnode *bt)

　　{btnode *p, *q;

　　if (bt){ADDQ(Q,bt);

　　while(!EMPTY(Q))

　　{p=DELQ(Q); q=(1)_; p->rchild=(2)___; (3)___=q;

　　if(p->lchild) (4)___; if(p->rchild) (5)___;

　　}

　　}

　　}

　　五、算法設(shè)計題

　　1、寫出廣度優(yōu)先搜索遍歷的遍歷算法。

　　數(shù)據(jù)結(jié)構(gòu)模擬試題1參考答案

　　一、選擇題(20分)

　　1-5 A B C A C

　　6-10 D D C B B

　　二、填空題(20分)

　　l、(n-2)(n+3)/2

　　2、n0=n2+1

　　3、3 1 4

　　4、n1-1 n2+n3

　　5、50 4

　　6、直接插入排序和冒泡排序

　　三、判斷題(10分)

　　1、× 2、× 　　3、√ 4、√ 5、×

　　6、√ 7、√ 8、 × 9、× 10、√

　　四、應(yīng)用題(20分)

　　1、參考答案如下：

　　2、參考答案如下：

　　3、參考答案如下：

　　4、參考答案如下：

　　1)

　　2)帶權(quán)路徑長度269

　　5、參考答案如下：

　　1) A B C D E G

　　2) A B C E D G

　　6、參考答案如下：

　　五、算法設(shè)計題(30分)

　　1、算法源代碼如下：

　　int flag=1;

　　int max;

　　void sortbitree(bitree T)

　　{ if(T)

　　{ sortbitree(T->lchild);

　　k++;

　　if(k==1) max=T->data;

　　else

　　{ if(T->data>max) max=T->data;

　　else flag=0; }

　　sortbitree(T->rchild);

　　}

　　}

　　2、算法源代碼如下：

　　int pathed[MAX_VERTEX_NUM];

　　int top=0;

　　int path[MAX_VERTEX_NUM];

　　int ispath(algraph graph,int vi,int vj)

　　{ arcptr p;

　　int j;

　　pathed[vi]=1; path[++top]=vi;/*將頂點vi加入當(dāng)前路徑path */

　　if(path[top]==vj) /*存在頂點vi到頂點vj的路徑*/

　　return 1;

　　else /*將頂點vi的鄰接點加入當(dāng)前路徑*/

　　for(p=graph、vertices[vi]、firstarc;p;p=p->nextarc)

　　if(!pathed[p->adjvex]) return ispath(graph,p->adjvex,vj);

　　pathed[vi]=0; top--; /*將頂點vi從當(dāng)前路徑path中刪除 */

　　if(top==0) return 0; /*不存在vi到vj的簡單路徑*/

　　}

　　3、算法源代碼如下：

　　bithrtree insucc(bithrtree p)/*找p結(jié)點的后繼*/

　　{ if(p->rtag==1) /*后繼線索*/

　　return p->rchild;

　　else /*右子樹的最左下結(jié)點*/

　　{ p=p->rchild;

　　while(p->ltag==0) p=p->lchild;

　　return p; }

　　}

【數(shù)據(jù)結(jié)構(gòu)試題及答案】相關(guān)文章：

經(jīng)典java筆試題及答案09-26

閱讀理解試題及答案11-14

軍校面試試題及答案09-25

客服面試試題及答案09-26

銷售面試試題與答案09-26

外企面試的經(jīng)典試題及答案09-25

邏輯學(xué)試題及答案09-26

Java經(jīng)典筆試題（含答案）09-26

中考英語各類試題及答案09-25

銷售行業(yè)面試試題及答案09-26