2016年江西師范大學數(shù)據(jù)結(jié)構(gòu)與程序設計考研真題

》》》》》》2023年整理歷年要考研試題資料《《《《《《》》》》》》2023年整理歷年要考研試題資料《《《《《《/》》》》》》2023年整理歷年要考研試題資料《《《《《《2016年江西師范大學數(shù)據(jù)結(jié)構(gòu)與程序設計考研真題一、單項選擇題（每小題2分，共20分）1.對于邏輯結(jié)構(gòu)B,如果它只有一個開始結(jié)點和一個終端結(jié)點，而其他的每一個結(jié)點有且僅-有一個前驅(qū)和一個后繼，則稱為（）A.網(wǎng)狀結(jié)構(gòu)B.線性結(jié)構(gòu) C.圖形結(jié)構(gòu)D.樹型結(jié)構(gòu)2.線性表若采用鏈式存儲結(jié)構(gòu)時，要求內(nèi)存中可用存儲單元的地址（）A.必須是連續(xù)的 B.部分地址必須是連續(xù)的C.一定是不連續(xù)的 D,連續(xù)不連續(xù)都可以3.隊列是一種特殊的線性表，具有（）的性質(zhì)。A.先進先出B.先進后出 C.后進后出 D.順序進出4.設非空的循環(huán)單鏈表head的尾結(jié)點由p所指向，則該尾結(jié)點滿足（）A.p->next==NULLB.p==NULLC.p->next==headD.p==head5.一棵具有5層的滿二叉樹所包含的結(jié)點個數(shù)為（）A.15B.31-C.63D.326.將一棵有100個結(jié)點的完全二叉樹，按照從上到T、、同…-層次上按從左到右的順序?qū)λ薪Y(jié)點從1開始編號，則編號為49的結(jié)點，其左孩子編號為（）A.98B.99C.50D.487.若無向圖G是具有6個頂點的連通圖，則至少具有（）條邊。A.5B.6C.7D.88.適用于二分法檢索的表的存儲方式及元素排列要求為（）A.鏈式方式存儲，元素無序 B.鏈式方式存儲，元素有序C.順序方式存儲，元素無序D.順序方式存儲，元素有序9.在關鍵字序列｛1,3,9,12,32,找關鍵字為81,45,62,75,78,81,93,99｝中，二分査的結(jié)點81時，通過（）次比較后査找成功。A.1B.2C.4D.810.下面幾種排序方法中，空間復雜度最高的是（）A.快速排序B.選擇排序C.歸并排序D.插入排序二、填空題（每小題2分，共20分）1.數(shù)據(jù)的存儲結(jié)構(gòu)主要有4種?：順序存儲、鏈式存儲、（）和（）2.一個算法的復雜度可分為（）復雜度和（）雜度。3.設棧S的初始狀態(tài)為空，元素T、2、3、4、5依次全部進棧，然后所有元素依次出棧，則出棧序列為（）.4.表達式A*（B+C）/（D-E+F）的后綴表達式是（）。5.在一個單鏈表中，若p所指結(jié)點不是最后結(jié)點，在p之后插入s所指結(jié)點，應執(zhí)行語句（）6.對于一個循環(huán)單鏈表，若首指針為head,指針p指向表中的某個結(jié)點，則p所指結(jié)點是該表中最后一個結(jié)點的特征是（）7.一棵非空二叉樹的第i(>1)層上最多有（）個結(jié)點。8.在無向圖G的鄰接矩陣A中，若A[i][j]^于1,則等于（）.。9.設圖G是一個具有n個頂點的無向連通圖，則G的生成樹的邊數(shù)為（）10.要解決散列引起的沖突問題，常用的3種方法是開放定址法、（）和（）三、程序填空與程序分析題(每小題6分，共24分)1.閱讀下列程序，寫出程序運行的輸出結(jié)果。#include<stdio.h>voidmain()(inti,j;i=l；while(i<4)(for(j-1;j<2*i+l;j++)printf(H%c"/'#1);printf("\n"); *i++；))2.設單鏈表的存儲結(jié)構(gòu)定義如下：typedefintdatatype;typedefstructlink_node{datatypeinfo; 'structlink_node*next;)node;typedefnode*linklist;閱讀以下程序，并回答程序后的問題：node*fun(node*headzdatatypex){node*pm=head,q=head->next;while(q&&q->info!=x)(pre=q;q=q->next;}if(q){pre->next=q->next;free(q);}returnhead;(1)請描述函數(shù)fun()的功能;(2)定義變量如下：linklisthead;設head鏈表如圖1所示。請畫出執(zhí)行函數(shù)調(diào)用語句head=fun(head,2)之后的head鏈表。3.設二叉樹的存儲結(jié)構(gòu)定義如下：typedefstructnode(/*二叉樹結(jié)點定義*/datatypedata;structnode*lchildz*rchild;)bintnode;typedefbintnode*bintree;函數(shù)isequal的功能是判斷給定的兩棵二叉樹tl和t2是否等價，并返回0或丄的結(jié)果。請將程序空白處補充完整。intisequal(bintreetlzbintreet2)(intb=0;if(tl==NULL&&t2==NULL)(1) ;elseif(tl!t2!=NULL)if(tl->data== (2) )if(isequal(tl->lchildzt2->lchild)b= (3) ;returnb;}4.設順序表的結(jié)構(gòu)定義如下:#defineMAXSIZE100typedefintdatatype;typedefstruct(datatypea[MAXSIZE];.intsize;}seqlist;函數(shù)split的功能是將給定順序表LI中的數(shù)據(jù)進行分類，奇數(shù)存放到存