- 相關(guān)推薦
數(shù)據(jù)結(jié)構(gòu)試題及答案
導(dǎo)語：數(shù)據(jù)結(jié)構(gòu)考試會主要考倒什么呢�？忌鷤儾环量纯�。以下是小編搜集并整理的有關(guān)內(nèi)容，希望對大家有所幫助!
一、單項(xiàng)選擇題
1、連續(xù)存儲設(shè)計(jì)時(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ù)組的每個(gè)元素長度為3字節(jié)，i的值為1 到8 ，j的值為1 到10，數(shù)組從內(nèi)存首地址BA開始順序存放，當(dāng)用以列為主存放時(shí)，元素A[5，8]的存儲首地址為( )。
A、 BA+141
B、 BA+180
C、 BA+222
D、 BA+225
4、若某線性表最常用的操作是存取任一指定序號的元素和在最后進(jìn)行插入和刪除運(yùn)算，則利用( )存儲方式最節(jié)省時(shí)間。
A、順序表
B、雙鏈表
C、帶頭結(jié)點(diǎn)的雙循環(huán)鏈表
D、單循環(huán)鏈表
5、某線性表中最常用的操作是在最后一個(gè)元素之后插入一個(gè)元素和刪除第一個(gè)元素，則采用( )存儲方式最節(jié)省運(yùn)算時(shí)間。
A、單鏈表
B、僅有頭指針的單循環(huán)鏈表
C、雙鏈表
D、僅有尾指針的單循環(huán)鏈表
6、線性表( a1,a2,…,an)以鏈接方式存儲時(shí)，訪問第i位置元素的時(shí)間復(fù)雜性為( )。
A、O(i)
B、O(1)
C、O(n)
D、O(i-1)
7、對于一個(gè)頭指針為head的帶頭結(jié)點(diǎn)的單鏈表，判定該表為空表的條件是( )。
A、head==NULL
B、head→next==NULL
C、head→next==head
D、head!=NULL
8、 若已知一個(gè)棧的入棧序列是1,2,3,…,n，其輸出序列為p1,p2,p3，…，pN,若pN是n，則pi是( )。
A、 i
B、 n-i
C、 n-i+1
D、 不確定
9、 有六個(gè)元素6，5，4，3，2，1 的順序進(jìn)棧，問下列哪一個(gè)不是合法的出棧序列?( )。
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)鍵字值計(jì)算轉(zhuǎn)化為記錄的存放地址，因?yà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)中評價(jià)算法的兩個(gè)重要指標(biāo)是 。
3、當(dāng)線性表的元素總數(shù)基本穩(wěn)定，且很少進(jìn)行插入和刪除操作，但要求以最快的速度存取線性表中的元素時(shí)，應(yīng)采用_______存儲結(jié)構(gòu)。
4、線性表L=(a1,a2,…,an)用數(shù)組表示，假定刪除表中任一元素的概率相同，則刪除一個(gè)元素平均需要移動元素的個(gè)數(shù)是________。
5、在一個(gè)長度為n的順序表中第i個(gè)元素(1<=i<=n)之前插入一個(gè)元素時(shí)，需向后移動________個(gè)元素。
6、鏈接存儲的特點(diǎn)是利用________來表示數(shù)據(jù)元素之間的邏輯關(guān)系。
7、 一個(gè)棧的輸入序列是：1，2，3則不可能的棧輸出序列是_______。
8、區(qū)分循環(huán)隊(duì)列的滿與空，只有兩種方法，它們是______和______。
三、判斷題
1、算法可以用不同的語言描述，如果用C 語言或PASCAL語言等高級語言來描述，則算法實(shí)際上就是程序了。( )
2、 數(shù)據(jù)結(jié)構(gòu)的基本操作的設(shè)置的最重要的準(zhǔn)則是，實(shí)現(xiàn)應(yīng)用程序與存儲結(jié)構(gòu)的獨(dú)立。( )
3、 稀疏矩陣壓縮存儲后，必會失去隨機(jī)存取功能。( )
4、 數(shù)組是同類型值的集合。( )
5、 數(shù)組可看成線性結(jié)構(gòu)的一種推廣，因此與線性表一樣，可以對它進(jìn)行插入，刪除等操作。( )
6、 稀疏矩陣壓縮存儲后，必會失去隨機(jī)存取功能。( )
7、 二維以上的數(shù)組其實(shí)是一種特殊的廣義表。( )
8、 文件是記錄的集合，每個(gè)記錄由一個(gè)或多個(gè)數(shù)據(jù)項(xiàng)組成，因而一個(gè)文件可看作由多個(gè)記錄組成的數(shù)據(jù)結(jié)構(gòu)。( )
三、解答題
1、 數(shù)據(jù)結(jié)構(gòu)是一門研究什么內(nèi)容的學(xué)科?
2、數(shù)據(jù)元素之間的關(guān)系在計(jì)算機(jī)中有幾種表示方法?各有什么特點(diǎn)?
3、 有5 個(gè)元素，其入棧次序?yàn)椋篈，B，C，D，E，在各種可能的出棧次序中，以元素C，D最先出棧(即C第一個(gè)且D第二個(gè)出棧)的次序有哪幾個(gè)?
四、程序閱讀題
1、請閱讀以下程序，寫出此程序所要完成的功能，及時(shí)間復(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中每一個(gè)結(jié)點(diǎn)的左右子樹互換的C語言算法如下，其中ADDQ(Q,bt),DELQ(Q),EMPTY(Q)分別為進(jìn)隊(duì)，出隊(duì)和判別隊(duì)列是否為空的函數(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è)計(jì)題
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è)計(jì)題(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;/*將頂點(diǎn)vi加入當(dāng)前路徑path */
if(path[top]==vj) /*存在頂點(diǎn)vi到頂點(diǎn)vj的路徑*/
return 1;
else /*將頂點(diǎn)vi的鄰接點(diǎn)加入當(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--; /*將頂點(diǎn)vi從當(dāng)前路徑path中刪除 */
if(top==0) return 0; /*不存在vi到vj的簡單路徑*/
}
3、算法源代碼如下：
bithrtree insucc(bithrtree p)/*找p結(jié)點(diǎn)的后繼*/
{ if(p->rtag==1) /*后繼線索*/
return p->rchild;
else /*右子樹的最左下結(jié)點(diǎn)*/
{ 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