2017年算法與數(shù)據(jù)結(jié)構(gòu)試題及參考答案
試題是算法與數(shù)據(jù)結(jié)構(gòu)課程學(xué)習(xí)過程中的必備資料。以下是陽光網(wǎng)小編要與大家分享的2017年算法與數(shù)據(jù)結(jié)構(gòu)試題，供大家參考!
2017年算法與數(shù)據(jù)結(jié)構(gòu)試題一.是非題
(每題1分共10分)
1. 線性表的鏈?zhǔn)酱鎯Y(jié)構(gòu)優(yōu)于順序存 儲結(jié)構(gòu)。 F
2. 棧和隊(duì)列也是線性表。 如果需要，可對它們中的任一元素進(jìn)行操作。F
3. 字符串是數(shù)據(jù) 對象特定的線性表。T
4. 在單鏈表P指針?biāo)?指結(jié)點(diǎn)之后插入S結(jié)點(diǎn)的操作是：P->next= S ; S-> next = P->next; F
5. 一個(gè)無向圖的連通分量是其極大的連通子圖。T
6. 鄰接表可以表示 有向圖，也可以表示無向圖。T
7. 假設(shè)B是一棵樹，B′是對應(yīng)的二叉樹。則B的后根遍歷相當(dāng)于B′的中序遍歷。 T
8. 通常，二叉樹的第i層上有2i-1個(gè)結(jié)點(diǎn)。F
9. 對于一棵m階的B-樹,樹中每個(gè)結(jié)點(diǎn)至多有m 個(gè)關(guān)鍵字。除根之外的所有非終端結(jié)點(diǎn)至少有ém/2ù個(gè)關(guān)鍵字。F
10.對于任何待排序序列 來說，快速排序均快于起泡排序。F
2017年算法與數(shù)據(jù)結(jié)構(gòu)試題二.選擇題
(每題2分共28分)
1.在下列排序方法中，( c )方法平均時(shí)間復(fù)雜度為0(nlogn)，最壞情況下時(shí)間復(fù)雜度為0(n2);( d )方法所有情況下時(shí)間復(fù)雜度均為0(nlogn)。
a. 插入排序 b. 希爾排序 c. 快速排序 d. 堆排序
2. 在有n個(gè)結(jié)點(diǎn)的二叉樹的二叉鏈表表示中，空指針數(shù)為( b )。
a.不定 b.n+1 c.n d.n-1
3. 下列二叉樹中，( a )可用于實(shí)現(xiàn)符號不等長高效編碼。
a.最優(yōu)二叉樹 b.次優(yōu)查找樹 c.二叉平衡樹 d.二叉排序樹
4. 下列查找方法中，( a )適用于查找有序單鏈表。
a.順序查找 b.二分查找 c.分塊查找 d.哈希查找
5. 在順序表查找中，為避免查找過程中每一步都檢測整個(gè)表是否查找完畢，可采用( a )方法。
a.設(shè)置監(jiān)視哨 b.鏈表存貯 c.二分查找 d.快速查找
6. 在下列數(shù)據(jù)結(jié)構(gòu)中， ( c )具有先進(jìn)先出特性，( b )具有先進(jìn)后出特性。
a.線性表 b.棧 c.隊(duì)列 d.廣義表
7.具有m個(gè)結(jié)點(diǎn)的二叉排序樹，其最大深度為( f )，最小深度為( b )。
a. log 2 m b. └ log2 m ┘ +1 c. m/2
d .┌ m/2 ┐ -1 e. ┌ m/2 ┐ f. m
8.已知一組待排序的.記錄關(guān)鍵字初始排列如下：56,34,58,26,79,52,64,37,28,84,57。
下列選擇中( c )是快 速排序一趟排序的結(jié)果。
( b )是希爾排序(初始步長為4)一趟排序的結(jié)果。
( d )是基數(shù)排序一趟排序的結(jié)果。
( a )是初始堆(大堆頂)。
a. 84，79，64，37，57，52，58，26，28，34，56。
b. 28，34，57，26，5 6，52，58，37，79，84，64。
c. 28，34，37，26，52，56，64，79，58，84，57。
d. 52，34，64，84，56，26，37，57，58，28，79。
e. 34，56，26，58，52，64，37，28，79，57，84。
f. 34，56，26，58，52，79，37，64，28，84，57。
2017年算法與數(shù)據(jù)結(jié)構(gòu)試題三.填空題
(每題2分共 20分)
1.有向圖的存儲結(jié)構(gòu)有(鄰接矩陣)、(鄰接表)、(十字鏈表)等方法。
2.已知某二叉樹的先序遍歷次序?yàn)閍fbcdeg，中序遍歷次序?yàn)閏edbgfa。
其后序遍歷次序?yàn)?ed cgbfa)。層次遍歷次序?yàn)?afbcgde)。
3.設(shè)有二維數(shù)組A 5 x 7 ,每一元素用相鄰的4個(gè)字節(jié)存儲，存儲器按字節(jié)編址。已知A00的存儲地址為100。則按行存儲時(shí)，元素A14的第一個(gè)字節(jié)的地址是(144);按列存儲時(shí)，元素A14的第一個(gè)字節(jié)的地址是(184)。
4.請?jiān)谙聞澗�上填入適當(dāng)?shù)恼Z句，完成以下法算。
Status Preordertraverse(Bitree T,Status(*Visit)(Telemtype e)){
//先序非遞歸遍歷二叉樹。
Initstack ( S ); Push ( S,T );
While ( !stackempty( S ) )
{ While ( gettop( S, p )&& p ) { visit (p->data ) ; push(S, p->lchild ;}
Pop ( S , p );
If ( !stackempty(s) ) { pop(S, p) ; push( S, p->rchild ); }
}
retu rn ok;
2017年算法與數(shù)據(jù)結(jié)構(gòu)試題四、算法設(shè)計(jì)題
(共17分)
1. 單鏈表結(jié)點(diǎn)的 類型定義如下：
typedef str uct LNode {
int data;
struct LNode *next;
} LNode, *Linklist;
寫一算法，將帶頭結(jié)點(diǎn)的有 序單鏈表A和B合并成一新的有序表C。(注:不破壞A和B的原有結(jié)構(gòu).)
Merge(Linklist A, Linklist B, Linklist &C )
void Merge( Linklist A, Linklist B, Linklist &C)
{ C=(Linklist)malloc(sizeof(LNode));
pa=A->n ext; pb=B->next; pc=C;
while(pa&&pb)
{ pc->next=(Linklist)malloc(sizeof(LNode));
pc=pc->next;
if(pa->data<=pb->data)
{ pc->data=pa->data; pa=pa->next;}
else
{ pc->d ata=pb->data; pb=pb->next;}
}
if(!pa) pa=pb;
while(pa)
{ pc->next=(Linklist)malloc(sizeof(LNode));
pc=pc- >next;
pc->data=pa->data; pa=pa->next;
}
pc->next=NULL;
}
2. 二叉樹用二叉鏈表存儲表示。
typedef struct BiTNode {
Tel emType data;
Struct BiTNode *lchild, *rchild;
} BiTNode, *BiTree;
編寫一個(gè)復(fù)制一棵二叉樹的遞歸算法。
BiTree CopyTree(BiTree T) {
if (!T ) return NULL;
if (!( newT = (BiTNode*)malloc(sizeof(BiTNode))))
exit(Overflow);
newT-> data = T-> data;
newT-> lchild = CopyTree(T-> lchild);
newT-> rchild = CopyTree(T-> rchild);
return newT;
看過“2017年算法與數(shù)據(jù)結(jié)構(gòu)試題”的人還看了：
1.數(shù)據(jù)結(jié)構(gòu)試題及答案
2.算法與數(shù)據(jù)結(jié)構(gòu)答案
【2017年算法與數(shù)據(jù)結(jié)構(gòu)試題及參考答案】相關(guān)文章：
1.算法與數(shù)據(jù)結(jié)構(gòu)模擬試題及參考答案
2.算法與數(shù)據(jù)結(jié)構(gòu)試題及答案
3.算法與數(shù)據(jù)結(jié)構(gòu)模擬試題及答案
4.《算法數(shù)據(jù)結(jié)構(gòu)》期末試題及答案
5.2017年算法與數(shù)據(jù)結(jié)構(gòu)模擬試題及答案