- 相關推薦
數據結構試題及答案
導語：數據結構考試會主要考倒什么呢。考生們不妨看看。以下是小編搜集并整理的有關內容，希望對大家有所幫助!
一、單項選擇題
1、連續存儲設計時，存儲單元的地址( )。
A、一定連續
B、一定不連續
C、不一定連續
D、部分連續，部分不連續
2、以下屬于邏輯結構的是( )。
A、順序表
B、 哈希表
C、有序表
D、 單鏈表
3、 設有數組A[i,j]，數組的每個元素長度為3字節，i的值為1 到8 ，j的值為1 到10，數組從內存首地址BA開始順序存放，當用以列為主存放時，元素A[5，8]的存儲首地址為( )。
A、 BA+141
B、 BA+180
C、 BA+222
D、 BA+225
4、若某線性表最常用的操作是存取任一指定序號的元素和在最后進行插入和刪除運算，則利用( )存儲方式最節省時間。
A、順序表
B、雙鏈表
C、帶頭結點的雙循環鏈表
D、單循環鏈表
5、某線性表中最常用的操作是在最后一個元素之后插入一個元素和刪除第一個元素，則采用( )存儲方式最節省運算時間。
A、單鏈表
B、僅有頭指針的單循環鏈表
C、雙鏈表
D、僅有尾指針的單循環鏈表
6、線性表( a1,a2,…,an)以鏈接方式存儲時，訪問第i位置元素的時間復雜性為( )。
A、O(i)
B、O(1)
C、O(n)
D、O(i-1)
7、對于一個頭指針為head的帶頭結點的單鏈表，判定該表為空表的條件是( )。
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 的順序進棧，問下列哪一個不是合法的出棧序列?( )。
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、 散列文件使用散列函數將記錄的關鍵字值計算轉化為記錄的存放地址，因為散列函數是一對一的關系，則選擇好的( )方法是散列文件的關鍵。
A、 散列函數
B、 除余法中的質數
C、 沖突處理
D、 散列函數和沖突處理
二、填空題
1、數據的物理結構包括 的表示和 的表示。
2、數據結構中評價算法的兩個重要指標是 。
3、當線性表的元素總數基本穩定，且很少進行插入和刪除操作，但要求以最快的速度存取線性表中的元素時，應采用_______存儲結構。
4、線性表L=(a1,a2,…,an)用數組表示，假定刪除表中任一元素的概率相同，則刪除一個元素平均需要移動元素的個數是________。
5、在一個長度為n的順序表中第i個元素(1<=i<=n)之前插入一個元素時，需向后移動________個元素。
6、鏈接存儲的特點是利用________來表示數據元素之間的邏輯關系。
7、 一個棧的輸入序列是：1，2，3則不可能的棧輸出序列是_______。
8、區分循環隊列的滿與空，只有兩種方法，它們是______和______。
三、判斷題
1、算法可以用不同的語言描述，如果用C 語言或PASCAL語言等高級語言來描述，則算法實際上就是程序了。( )
2、 數據結構的基本操作的設置的最重要的準則是，實現應用程序與存儲結構的獨立。( )
3、 稀疏矩陣壓縮存儲后，必會失去隨機存取功能。( )
4、 數組是同類型值的集合。( )
5、 數組可看成線性結構的一種推廣，因此與線性表一樣，可以對它進行插入，刪除等操作。( )
6、 稀疏矩陣壓縮存儲后，必會失去隨機存取功能。( )
7、 二維以上的數組其實是一種特殊的廣義表。( )
8、 文件是記錄的集合，每個記錄由一個或多個數據項組成，因而一個文件可看作由多個記錄組成的數據結構。( )
三、解答題
1、 數據結構是一門研究什么內容的學科?
2、數據元素之間的關系在計算機中有幾種表示方法?各有什么特點?
3、 有5 個元素，其入棧次序為：A，B，C，D，E，在各種可能的出棧次序中，以元素C，D最先出棧(即C第一個且D第二個出棧)的次序有哪幾個?
四、程序閱讀題
1、請閱讀以下程序，寫出此程序所要完成的功能，及時間復雜度。
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中每一個結點的左右子樹互換的C語言算法如下，其中ADDQ(Q,bt),DELQ(Q),EMPTY(Q)分別為進隊，出隊和判別隊列是否為空的函數，請填寫算法中得空白處，完成其功能。
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)___;
}
}
}
五、算法設計題
1、寫出廣度優先搜索遍歷的遍歷算法。
數據結構模擬試題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、√
四、應用題(20分)
1、參考答案如下：
2、參考答案如下：
3、參考答案如下：
4、參考答案如下：
1)
2)帶權路徑長度269
5、參考答案如下：
1) A B C D E G
2) A B C E D G
6、參考答案如下：
五、算法設計題(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加入當前路徑path */
if(path[top]==vj) /*存在頂點vi到頂點vj的路徑*/
return 1;
else /*將頂點vi的鄰接點加入當前路徑*/
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從當前路徑path中刪除 */
if(top==0) return 0; /*不存在vi到vj的簡單路徑*/
}
3、算法源代碼如下：
bithrtree insucc(bithrtree p)/*找p結點的后繼*/
{ if(p->rtag==1) /*后繼線索*/
return p->rchild;
else /*右子樹的最左下結點*/
{ p=p->rchild;
while(p->ltag==0) p=p->lchild;
return p; }
}
【數據結構試題及答案】相關文章：
經典java筆試題及答案09-26
閱讀理解試題及答案11-14
軍校面試試題及答案09-25
客服面試試題及答案09-26
銷售面試試題與答案09-26
外企面試的經典試題及答案09-25
邏輯學試題及答案09-26
Java經典筆試題（含答案）09-26
中考英語各類試題及答案09-25
銷售行業面試試題及答案09-26