江西師范大學(xué)碩士研究生入學(xué)考試試題樣卷

1、江西師范大學(xué)碩士研究生入學(xué)考試試題(樣卷)專業(yè)：081200 計算機科學(xué)與技術(shù) 科目:數(shù)據(jù)纟齣與歸設(shè)計注：考生答題時，請寫在考點下發(fā)的答題紙上,寫在本試題紙或其它答題紙上的一律無效!(木試題共計頁)一、選擇題(每小題2分，共20分)1、若語句S的執(zhí)行時間為0(1),那么下列程序段的時間復(fù)雜度為：()for (i=0; in; i-H-)for (j=O;jnext=s; snext=p;(D) s-next=p-next; p-next=s;3、設(shè)高度為h的二義樹上只有度為0和度為2的結(jié)點，則此類二叉樹中所包含的結(jié)點數(shù)至少 為()(注：只含有一個根結(jié)點的樹高為1)(A)2h(B) 2h-l(C

2、) 2h十1(D) h+14、一組記錄的關(guān)鍵碼為(46, 79, 56, 38, 40, 84),則利用堆排序的方法建立的初始堆為 ( )。(A) 84, 79, 56, 38, 40, 46(B) 79, 46, 56, 38, 40, 80(C)84, 79, 56, 46, 40, 38(D) 84, 56, 79, 40, 46, 385、設(shè)二義排序樹中關(guān)鍵字由1至1000的整數(shù)構(gòu)成，現(xiàn)要檢索關(guān)鍵字為363的結(jié)點，下述關(guān)鍵字序列哪一個不可能是二叉排序樹上搜索到的序列()。(A) 2,252,401,398,330,344,397,363(B)924,220, 911,244,898,2

3、58,362,363(C)952,202, 911,240,912,245,363(D) 2,399,387,219,266,382,381,278,3636、已知某完全二叉樹釆用順序存儲結(jié)構(gòu)，結(jié)點數(shù)據(jù)信息A、B、C、D、E、F、G、H,順序存放在數(shù)組的前8個單元，則該完全二叉樹的后序遍歷序列為()。(A) HDEBFGCA (B) HEDBFGCA (C) HDEBAFGC (D) HDEFGBCA7、稀疏矩陣一般的壓縮存儲方法有()兩種。(A)二維數(shù)組和三維數(shù)組(B)三元組和散列表(C)三元組和十字鏈表(D)散列表和十字鏈表(A) s-next=p; p-next=s;(C) s-next

4、=p next; p=s;第2頁，共6頁8、下列哪棵樹不是AVL樹()。9、設(shè)有一個有向圖如圖1所示，請指出下列哪個序列不是該圖的拓撲排序序列()。(A) EAFBGDC (B) AEBCGFD (C) ABCGEFD (D) EABGFCD10、判斷一個有向圖是否存在回路除了可以利用拓撲排序方法外，還可以利用()o(A)單源最短路Dijkstia算法(B)所有頂點對最短路Floyd算法(C)廣度優(yōu)先遍歷算法(D)深度優(yōu)先遍歷算法二、填空題(每小題2分，共20分)1、數(shù)據(jù)的存儲結(jié)構(gòu)一般分為順序存儲、鏈?zhǔn)酱鎯?、_和_ 四種方式。2、中綴表達式(A+B)*D + E/(F十A*D)十C對應(yīng)的后綴表

5、達式是_ 。3、KMP算法是解決模式匹配的有效算法，設(shè)數(shù)組下標(biāo)從0從始，則模式串“babbabbab”對應(yīng)的next值是_:.4、一棵具有46個葉結(jié)點的完全二叉樹，最多有_個結(jié)點。5、若p已指向了二叉樹t的樹根，則讓p指向這棵二叉樹的中序首點(中序遍歷下的第一個結(jié)點)可以用以下的語句實現(xiàn)：_6、編號為1, 2, 3, 4的四列火車通過一個棧式的列車調(diào)度站，可能得到的調(diào)度結(jié)果有 種。7、_排序方法采用的是二分法的思想，_ 排序方法其數(shù)據(jù)結(jié)構(gòu)的組織釆用的是完全二叉樹結(jié)構(gòu)。8、若函數(shù)mt max (inta, mtn)用于求長度為n (n0)的整型組a中的最大值，其遞歸定義可以表示為：_o9、若一棵

6、度為7的樹有8個度為1的結(jié)點，有7個度為2的結(jié)點，有6個度為3的結(jié)點，有5個度為4的結(jié)點，有4個度為5的結(jié)點，有3個度為6的結(jié)點，有2個度為7的結(jié)點，該 樹一共有_ 個葉結(jié)點。10、_ 散列函數(shù)_ 以為自變量，函數(shù)值作為結(jié)點的_o(A)(B)(C)(D)第3頁，共6頁三、程序填空與程序分析題(每小題6分，共24分)1、函數(shù)frequency ()的功能統(tǒng)計字符串s中各個不同字符出現(xiàn)的頻度，數(shù)組n記錄s中不同 的字符，數(shù)組c中記錄每一種字符的出現(xiàn)次數(shù)，k返回不同字符的總數(shù)，請將程序補充完整。void frequency(char s,char a jnt c,int *k) int i,jjen

7、=strlen(s);if (!len)/*原字符串為空*/ prmtf(HThe string is empty.nM); *k = 0;第4頁，共6頁return;else/*原字符串不為空*/a0 = s0;c0= 1;*k= 1;for ( i = 1; i len; i+)for (i = l;ilen; i+)/*對s中剩余字符進行檢測*/j = 0;while (j next;wliile (p)Pie=p；s=p-next;while (s!=NULL)while(s&s-data!=p-data)/*從結(jié)點p后找與其相同的結(jié)點*/f s=s-next;if=NULL)

8、嚴(yán)找到了與p相同的結(jié)點屮/ pre Anext=s Anext;/*處理第一個字符審嚴(yán)數(shù)組c初始化審第5頁，共6頁p=p-next;return head;3、二叉排序樹鏈?zhǔn)酱鎯Y(jié)構(gòu)定義如下：typedef mt datatype;typedef stiuct node datatype key;/*結(jié)點值*/stnict node *lchild,*rcliild;/*左、右孩子指針bsnode;typedef bsnode *bstree;函數(shù)iiisertbstree ()的功能是在二叉排序樹t中插入一個新結(jié)點x(若樹中存在相同結(jié)點 則不做插入操作)，請將其補充完整。void msei-

9、tbstree(bstree *t,datatype x) bstree f,p;(10)while (p)/*查找插入位置*/ if(x=p-key) (ID/*若二叉排序樹t中已有key,則無需插入*/匸p；/*f用于保存新結(jié)點的最終插入位置*/p=(xkey)?(p=(bstree) malloc(sizeof(bsnode);/*生成待插入的新結(jié)點*/p-key=x;_ (1_ if(*t=NULL) (14)/* 原樹為空審/elseif (xrchild=p;4、閱讀下面的遞歸程序，說明這個函數(shù)的功能是什么？如果數(shù)組的大小為n,則該程序的時 間復(fù)朵度是多少？設(shè)數(shù)組a的初始值是21,30,52,35,69/70,90,61,78,99,則執(zhí)行changel(a,0,9)后， 數(shù)組a的內(nèi)容是什么？v