江西師范大學(xué)2023年碩士研究生入學(xué)考試初試科目

PAGE第4頁，共9頁江西師范大學(xué)2023年碩士研究生入學(xué)考試初試科目

考試大綱科目代碼、名稱:865、數(shù)據(jù)結(jié)構(gòu)與程序設(shè)計(jì)適用專業(yè):083500軟件工程（學(xué)術(shù)）、085400電子信息（計(jì)算機(jī)技術(shù)、軟件工程、人工智能、大數(shù)據(jù)技術(shù)與工程、網(wǎng)絡(luò)與信息安全）一、考試形式與試卷結(jié)構(gòu)（一）試卷滿分及考試時(shí)間本試卷滿分為150分，考試時(shí)間為180分鐘。（二）答題方式答題方式為閉卷、筆試。試卷由試題和答題紙組成；答案必須寫在答題紙相應(yīng)的位置上。（三）試卷題型結(jié)構(gòu)1．單項(xiàng)選擇題：10小題，每小題2分，共20分2．填空題：10小題，每小題2分，共20分3．程序填空與程序分析題題：4小題，每小題6分，共24分4．解答題：4小題，第小題10分，共40分5．算法與程序設(shè)計(jì)題：3小題，第1、2小題每小題14分，第3小題18分，共46分二、考查目標(biāo)（復(fù)習(xí)要求）全日制攻讀碩士學(xué)位研究生入學(xué)考試數(shù)據(jù)結(jié)構(gòu)與程序設(shè)計(jì)科目考試內(nèi)容包括《數(shù)據(jù)結(jié)構(gòu)》課程主要內(nèi)容，要求考生系統(tǒng)掌握相關(guān)學(xué)科的基本知識、基礎(chǔ)理論和基本方法，并能運(yùn)用相關(guān)理論和方法分析、解決程序設(shè)計(jì)中的實(shí)際問題。三、考查范圍或考試內(nèi)容概要第一章概論1．?dāng)?shù)據(jù)結(jié)構(gòu)的基本概念與術(shù)語2．算法與算法分析第二章線性表及其順序存儲1．線性表2．順序表及其應(yīng)用3．棧的概念及其應(yīng)用4．隊(duì)列的概念及其應(yīng)用第三章線性表及其鏈?zhǔn)酱鎯?．鏈?zhǔn)酱鎯?．單鏈表3．帶頭結(jié)點(diǎn)的單鏈表及其應(yīng)用4．循環(huán)單鏈表與雙鏈表5．鏈?zhǔn)綏Ｅc鏈?zhǔn)疥?duì)列第四章字符串、數(shù)據(jù)與特殊矩陣1．字符串及模式匹配2．特殊矩陣的壓縮存儲3．稀疏矩陣第五章遞歸1．遞歸的基本概念與遞歸程序設(shè)計(jì)2．遞歸程序設(shè)計(jì)執(zhí)行過程的分析3．遞歸程序到非遞歸程序的轉(zhuǎn)換第六章樹1．樹的概念2．樹的存儲結(jié)構(gòu)3．樹的遍歷第七章二叉樹1．二叉樹的基本概念2．二叉樹的存儲結(jié)構(gòu)3．二叉樹的遍歷（遞歸與非遞歸）4．穿線二叉樹的基本概念與構(gòu)造5．樹、森林和二叉樹的轉(zhuǎn)換第八章圖1．圖的基本概念2．圖的存儲結(jié)構(gòu)（鄰接矩陣法、鄰接表法）3．圖的遍歷4．生成樹與最小生成樹5．最短路徑6．拓?fù)渑判?．關(guān)鍵路徑第九章檢索1．檢索的基本概念2．線性表的檢索3．二叉排序樹4．平衡二叉排序樹5．Huffman樹6．B-樹7．散列表的檢索8．查找算法的分析及應(yīng)用第十章排序1．排序的基本概念2．插入排序（直接插入排序、折半插入排序、希爾排序）3．選擇排序（簡單選擇排序、堆排序）4．交換排序（冒泡排序、快速排序）5．二路歸并排序（mergesort）6．基數(shù)排序7．各種內(nèi)部排序算法的比較8．內(nèi)部排序算法的應(yīng)用參考教材或主要參考書：1．《數(shù)據(jù)結(jié)構(gòu)》（C語言版）第三版，李云清，楊慶紅，揭安全編著，人民郵電出版社，ISBN:978-7-115-36463-0

四、樣卷江西師范大學(xué)碩士研究生入學(xué)考試試題（樣卷）專業(yè):083500軟件工程（學(xué)術(shù)）、085400電子信息（計(jì)算機(jī)技術(shù)、軟件工程、人工智能、大數(shù)據(jù)技術(shù)與工程、網(wǎng)絡(luò)與信息安全）科目：數(shù)據(jù)結(jié)構(gòu)與程序設(shè)計(jì)注：考生答題時(shí)，請寫在考點(diǎn)下發(fā)的答題紙上，寫在本試題紙或其它答題紙上的一律無效?。ū驹囶}共計(jì)頁）一、選擇題（每小題2分，共20分）1、若語句S的執(zhí)行時(shí)間為O（1），那么下列程序段的時(shí)間復(fù)雜度為：（） for（i=0;i<n;i++） for（j=0;j<=i;j++) S;（A）O（n）（B）O（n2）（C）O（nlogn）（D）O（n*i）2、在一個(gè)單鏈表中，若p所指結(jié)點(diǎn)不是最后結(jié)點(diǎn)，在p之后插入s所指結(jié)點(diǎn)，則執(zhí)行的語句序列是（）。（A）s->next=p;p->next=s;（B）p->next=s;s->next=p;（C）s->next=p->next;p=s;（D）s->next=p->next;p->next=s;3、設(shè)高度為h的二叉樹上只有度為0和度為2的結(jié)點(diǎn)，則此類二叉樹中所包含的結(jié)點(diǎn)數(shù)至少為（）（注：只含有一個(gè)根結(jié)點(diǎn)的樹高為1）2h（B）2h-1（C）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é)點(diǎn)，下述關(guān)鍵字序列哪一個(gè)不可能是二叉排序樹上搜索到的序列（）。（A）2，252，401，398，330，344，397，363（B）924，220，911，244，898，258，362，363（C）952，202，911，240，912，245，363（D）2，399，387，219，266，382，381，278，3636、已知某完全二叉樹采用順序存儲結(jié)構(gòu)，結(jié)點(diǎn)數(shù)據(jù)信息A、B、C、D、E、F、G、H，順序存放在數(shù)組的前8個(gè)單元，則該完全二叉樹的后序遍歷序列為（）。（A）HDEBFGCA（B）HEDBFGCA（C）HDEBAFGC （D）HDEFGBCA7、稀疏矩陣一般的壓縮存儲方法有（）兩種。（A）二維數(shù)組和三維數(shù)組（B）三元組和散列表（C）三元組和十字鏈表（D）散列表和十字鏈表（A）（B）（C）（D）8、下列哪棵樹不是AVL樹（（A）（B）（C）（D）9、設(shè)有一個(gè)有向圖如圖1所示，請指出下列哪個(gè)序列不是該圖的拓?fù)渑判蛐蛄校ǎ?。圖1（A）EAFBGDC（B）AEBCGFD（C）ABCGEFD（D）EABGFCD圖110、判斷一個(gè)有向圖是否存在回路除了可以利用拓?fù)渑判蚍椒ㄍ?，還可以利用（）。（A）單源最短路Dijkstra算法（B）所有頂點(diǎn)對最短路Floyd算法（C）廣度優(yōu)先遍歷算法（D）深度優(yōu)先遍歷算法二、填空題（每小題2分，共20分）1、數(shù)據(jù)的存儲結(jié)構(gòu)一般分為順序存儲、鏈?zhǔn)酱鎯Α⒑退姆N方式。2、中綴表達(dá)式(A+B)*D+E/(F+A*D)+C對應(yīng)的后綴表達(dá)式是。3、KMP算法是解決模式匹配的有效算法，設(shè)數(shù)組下標(biāo)從0從始，則模式串“babbabbab”對應(yīng)的next[]值是。4、一棵具有46個(gè)葉結(jié)點(diǎn)的完全二叉樹，最多有個(gè)結(jié)點(diǎn)。5、若p已指向了二叉樹t的樹根，則讓p指向這棵二叉樹的中序首點(diǎn)（中序遍歷下的第一個(gè)結(jié)點(diǎn)）可以用以下的語句實(shí)現(xiàn)：。6、編號為1，2，3，4的四列火車通過一個(gè)棧式的列車調(diào)度站，可能得到的調(diào)度結(jié)果有種。7、排序方法采用的是二分法的思想，排序方法其數(shù)據(jù)結(jié)構(gòu)的組織采用的是完全二叉樹結(jié)構(gòu)。8、若函數(shù)intmax（inta[]，intn）用于求長度為n（n>0）的整型組a中的最大值，其遞歸定義可以表示為：。9、若一棵度為7的樹有8個(gè)度為1的結(jié)點(diǎn)，有7個(gè)度為2的結(jié)點(diǎn)，有6個(gè)度為3的結(jié)點(diǎn)，有5個(gè)度為4的結(jié)點(diǎn)，有4個(gè)度為5的結(jié)點(diǎn)，有3個(gè)度為6的結(jié)點(diǎn)，有2個(gè)度為7的結(jié)點(diǎn)，該樹一共有_________個(gè)葉結(jié)點(diǎn)。10、散列函數(shù)以為自變量，函數(shù)值作為結(jié)點(diǎn)的。三、程序填空與程序分析題（每小題6分，共24分）1、函數(shù)frequency（）的功能統(tǒng)計(jì)字符串s中各個(gè)不同字符出現(xiàn)的頻度，數(shù)組a記錄s中不同的字符，數(shù)組c中記錄每一種字符的出現(xiàn)次數(shù)，k返回不同字符的總數(shù)，請將程序補(bǔ)充完整。voidfrequency(chars[],chara[],intc[],int*k){inti,j,len=strlen(s);if(!len)/*原字符串為空*/{printf("Thestringisempty.\n");*k=0;return;}else/*原字符串不為空*/{a[0]=s[0];c[0]=1;*k=1;/*處理第一個(gè)字符*/for(i=1;i<len;i++) =1\*GB3① /*數(shù)組c初始化*/for(i=1;i<len;i++){ /*對s中剩余字符進(jìn)行檢測*/j=0; while(j<*k&&a[j]!=s[i])/*檢查s[i]是否已在a[]中*/=2\*GB3② if(j==*k)/*s[i]不在a中*/{a[*k]==3\*GB3③c[*k]==4\*GB3④(*k)==5\*GB3⑤} else=6\*GB3⑥ /*s[i]已在a中*/}}}2、設(shè)帶頭結(jié)點(diǎn)的單鏈表的存儲結(jié)構(gòu)定義如下：typedefchardatatype;typedefstructnode{datatypedata;structnode*next;}listnode;typedeflistnode*linklist;函數(shù)deletelist（）的功能是將帶頭結(jié)點(diǎn)的單鏈表head中的重復(fù)結(jié)點(diǎn)刪除（即data域相同的結(jié)點(diǎn)只保留第一個(gè)結(jié)點(diǎn)），請將程序補(bǔ)充完整。linklistdeletelist(linklisthead){linklistp,pre,s;p=head->next;while(p){pre=p;s=p->next;while(s!=NULL){while(s&&s->data!=p->data)/*從結(jié)點(diǎn)p后找與其相同的結(jié)點(diǎn)*/{=7\*GB3⑦s=s->next;}if(s!=NULL)/*找到了與p相同的結(jié)點(diǎn)s*/{pre->next=s->next;=8\*GB3⑧}=9\*GB3⑨}p=p->next;}returnhead;}3、二叉排序樹鏈?zhǔn)酱鎯Y(jié)構(gòu)定義如下：typedefintdatatype;typedefstructnode{datatypekey;/*結(jié)點(diǎn)值*/structnode*lchild,*rchild;/*左、右孩子指針*/}bsnode;typedefbsnode*bstree;函數(shù)insertbstree（）的功能是在二叉排序樹t中插入一個(gè)新結(jié)點(diǎn)x（若樹中存在相同結(jié)點(diǎn)則不做插入操作），請將其補(bǔ)充完整。voidinsertbstree(bstree*t,datatypex){bstreef,p;=10\*GB2⑽while(p)/*查找插入位置*/{if(x==p->key)=11\*GB2⑾/*若二叉排序樹t中已有key，則無需插入*/f=p;/*f用于保存新結(jié)點(diǎn)的最終插入位置*/p=(x<p->key)?=12\*GB2⑿}p=(bstree)malloc(sizeof(bsnode));/*生成待插入的新結(jié)點(diǎn)*/p->key=x;=13\*GB2⒀if(*t==NULL)=14\*GB2⒁/*原樹為空*/elseif(x<f->key)=15\*GB2⒂elsef->rchild=p;}4、閱讀下面的遞歸程序，說明這個(gè)函數(shù)的功能是什么？如果數(shù)組的大小為n，則該程序的時(shí)間復(fù)雜度是多少？設(shè)數(shù)組a的初始值是21,30,52,35,69,70,90,61,78,99，則執(zhí)行change1（a,0,9）后，數(shù)組a的內(nèi)容是什么？voidchange1(inta[],intlow,inthigh){inti,j,t;i=low;j=high;if(i<j){while(i<j&&a[i]%2!=0)i++;while(i<j&&a[j]%2==0)j--;if(i!=j){t=a[i];a[i]=a[j];a[j]=t;}change1(a,i+1,j-1);}}四、解答題（每小題10分，共40分）一棵前序序列為1，2，3，4的二叉樹，其中序序列可能是4，1，2，3嗎？設(shè)一棵二叉樹的前序序列為1，2，3，4，5，6，7，8，9，其中序序列為2，3，1，5，4，7，8，6，