2012-2019年三峽大學(xué)836數(shù)據(jù)結(jié)構(gòu)真題合輯

2012-2019年三峽大學(xué)836數(shù)據(jù)結(jié)構(gòu)真題合輯三峽大學(xué)2012年研究生入學(xué)考試試題(A卷)科目代碼：838科目名稱：數(shù)據(jù)結(jié)構(gòu)（考生必須將答案寫在答題紙上，總分150分，考試時間180分鐘）一、選擇題(每小題2分，共40分)1、線性表采用鏈?zhǔn)酱鎯r，結(jié)點的存儲地址（）。A.必須是不連續(xù)的B.連續(xù)與否均可C.必須是連續(xù)的D.和頭結(jié)點的存儲地址相連續(xù)2、已知指針q所指結(jié)點是指針p所指結(jié)點的直接前驅(qū)，若在*q與*p之間插入結(jié)點*s，則應(yīng)執(zhí)行（）操作。A.s->next=p->next;p->next=sB.q->next=s;s->next=pC.p->next=s->next;s->next=pD.p->next=s;s->next=q3、設(shè)有一個順序棧S,元素按S1,S2,S3,S4,S5,S6順序進棧，若6個元素的出棧順序為S2,S3,S4,S6,S5,S1,則順序棧的容量至少應(yīng)為（）。A.2B.3C.4D.54、如下陳述中正確的是（）。A.串是一種特殊的線性表B.串的長度必須大于零C.串中元素只能是字母D.空串就是空白串5、設(shè)有一個二維數(shù)A[m][n]，假設(shè)A[0][0]寄存位置在544，A[5][5]寄存位置在624，每個元素占一個空間，A[2][2]在（）位置。A.592B.586C.576D.6086、設(shè)有5個字符呈現(xiàn)的頻度分別為1,2,3,5,4，則對應(yīng)的哈夫曼樹的帶權(quán)途徑長度為（）。A.34B.33C.35D.157、含n個頂點和e條邊的無向圖的鄰接矩陣中非零元素的個數(shù)為（）。A.eB.2eC.n2-eD.n2-2e第2頁8、長度為500的有序表采用折半查找時，查找成功最大比力次數(shù)為（）。A.8B.9C.10D.119、快速排序在下列哪種情況下最易發(fā)揮其長處（）。A.被排序的數(shù)據(jù)中含有多個相同排序碼B.被排序的數(shù)據(jù)已基本有序C.被排序的數(shù)據(jù)完全無序D.被排序的數(shù)據(jù)中的最大值和最小值相差懸殊10、下列關(guān)鍵字序列中，（）是堆。A.16,72,31,23,94,53B.94,23,31,72,16,53C.16,53,23,94，31,72D.16,23,53,31,94,7211、若已知一個棧的入棧序列是1，2，3，…，n，其輸出序列為p1,p2,p3,…,pn,若p1=n，則pi為（）。A.iB.n=iC.n-i+1D.不確定12、具有n(n>0)個結(jié)點的完全二叉樹的深度為（）。A.log2(n)B.log2(n)+1C.log2(n)+1D.log2(n)-114、用鄰接表表示圖進行廣度優(yōu)先遍歷時，通常是采用（）數(shù)據(jù)結(jié)構(gòu)來實現(xiàn)算法的。A.棧B.隊列C.樹D.圖15、深度優(yōu)先遍歷類似于二叉樹的（）。A.先序遍歷B.中序遍歷C.后序遍歷D.條理遍歷16、有8個結(jié)點的無向圖最多有（）條邊。A.14B.28C.56D.11217、折半查找有序表（4，6，10，12，20，30，50，70，88，100）。若查找表中元素58，則它將依次與表中哪些元素比較大小，查找結(jié)果是失敗。（）A.20，70，30，50B.30，88，70，50C.20，50D.30，88，50第3頁18、任何一個無向連通圖的最小生成樹（）。A.只要一棵B.一棵或多棵C.肯定有多棵D.可能不存在19、鏈表合用于哪類查找（）。A.順序B.二分法C.順序，也能二分法D.隨機20、把一棵樹轉(zhuǎn)換為二叉樹后，這棵二叉樹具有什么樣的形態(tài)特征（）。A.是唯一的B.有多種C.有多種，但根結(jié)點都沒有左孩子D.有多種，但根結(jié)點都沒有右孩子二、填空題(每小題1分，共30分)1、對于一個表長為n的順序表，在表頭插入元素的時間復(fù)雜度為，在表尾插入元素的時間復(fù)雜度為。（要求用大O表示法表示）2、神槍手依次壓入10顆子彈進入槍膛，編號分別為1-10，則消滅第4個敵人的子彈編號是。3、已知一采用空閑單元法的循環(huán)隊列容量為20，隊列的首、尾指針分別用f和r表示，f＝3，r＝18時隊列的長度為，f＝15，r＝7時隊列的長度為。4、設(shè)有一個10階的對稱矩陣A[10][10]，每個數(shù)據(jù)占2個字節(jié)，A[0][0]的存儲地點是24，則A[3][8]的地點是，若采用緊縮存儲體式格局按即將矩陣中下三角部分的元素存入一維數(shù)組B中，A[0][0]存入B[0]中，則A[8][5]在B[]中的下標(biāo)是，A[5][8]在B[]中的下標(biāo)是。5、一棵深度為6的滿二叉樹有個分支結(jié)點和個葉子結(jié)點。6、是被限定為只能在表的一端進行插入和刪除運算的線性表。7、已知某二叉樹的中序遍歷結(jié)果是：DEBAC，后序遍歷結(jié)果是：EDBCA，則該樹的先序遍歷序列是，層序遍歷序列是。8、若采用基于二叉樹的遞歸遍歷辦法編寫建立和銷毀樹的函數(shù)，那末建立應(yīng)該基于遍歷函數(shù)修改，而銷毀樹應(yīng)該基于遍歷函數(shù)修改。9、稀疏圖適合采用存儲布局，其對應(yīng)的最小天生樹算法是基于歸并的，最好用算法來求解。第4頁10、假設(shè)有二維數(shù)組A6×8，每個元素用相鄰的6個字節(jié)存儲，存儲器按字節(jié)編址。已知A的起始存儲位置（基地址）為1000，則數(shù)組A的體積（存儲量）為；末尾元素A57的第一個字節(jié)地址為；若按行存儲時，元素A14的第一個字節(jié)地址為；若按列存儲時，元素A47的第一個字節(jié)地點為。11、設(shè)數(shù)組a[1…60,1…70]的基地址為2048，每個元素占2個存儲單元，若以列序為主序順序存儲，則元素a[32,58]的存儲地址為。12、如果一棵完全二叉樹具有1000個結(jié)點，則此完全二叉樹有個葉子結(jié)點，有個度為2的結(jié)點，有個結(jié)點只有非空左子樹，有個結(jié)點只有非空右子樹。13、GetHead【GetTail【((a,b),(c,d))】】=。14、寫出下列程序段的時間復(fù)雜度，要求用大O表示法表示。s=0;i=1;fori=0;i<n;i++)while(i<=n)for(j=0;j<n;j++)i=i*3;s+=B[i][j];sum=s;答：答：三、綜合題(共50分)1、試寫出模式串T=“FGFFGF”的next函數(shù)值和nextval函數(shù)值(6分)。jTnext[j]nextval[j]1F2G3F4F5G6F第5頁2.根據(jù)下圖回答下列問題。（14分）V2a1=3a3=4V1a4=2a2=2V3a8=5V4a7=4V6a6=5V7a10=3a5=6V5a9=5(1)要完成該AOE網(wǎng)中工程，最短時間是多少？（不考慮單位）（5分）(2)上圖中的關(guān)鍵路徑是什么（用頂點序列表示）？將活動a10的時間改成2可否提前完成？（3分）(3)若忽略邊的權(quán)值將上圖看成一個AOV網(wǎng)，并約定當(dāng)存在多個入度為的結(jié)點時先輸出編號較小的結(jié)點，則請寫出拓撲排序結(jié)果。（3分）(4)若忽略邊的方向性將上圖看成無向網(wǎng)，各邊權(quán)值為經(jīng)濟代價，請給出該無向網(wǎng)的一棵最小天生樹。（3分）3、已知數(shù)據(jù)序列為：2，，3，5，8，7，4，6，2（10分）(1)在一個初始值為空的二叉排序樹中順次查找這些結(jié)點（動態(tài)查找，無則插入），請畫出該二叉排序樹的最終形態(tài)。（4分）(2)如果在查找過程中需要對該二叉排序樹舉行動態(tài)平衡化，請畫出從空樹到最終的平衡二叉樹的組織過程，要求標(biāo)明結(jié)點平衡因子。（6分）4、待散列的線性表為（42，7，34，21，20），散列用的一維地點空間為[0..6]，假定選用的散列函數(shù)是H（K）=K%7，若發(fā)生沖突采用線性探查法處理。（5分）(1)計算出每個元素的散列地點并在下圖中填寫出散列表：（3分）0123456(2)求出在查找每一個元素概率相等情況下的平均查找長度。（2分）5、已知待排序關(guān)鍵字序列是38，19，50，61，32，23，11，14，15請回答下列排序問題(要求排成升序序列)：（10分）(1)若采用間接插入排序，第一個位置前移的元素樞紐字是？(2分)(2)若采用希爾排序(di＝5,3,1),第一個位置前移的元素樞紐字是？(2分)(3)若采用間接選擇排序，第一個位置前移的元素樞紐字是？(2分)第6頁(4)若采用快速排序，第一個位置前移的元素關(guān)鍵字是？(2分)(5)若采用堆排序，利用篩選操作建堆過程中最先交換的兩個元素關(guān)鍵字是？(2分)6、一棵度為k的樹中有n1個度為1的結(jié)點，n2nk個度為k的結(jié)點，則該樹中有多少個葉子結(jié)點，并證明。（5分）四、程序題(共30分)1、已知x和y是整型全局變量，初值均為，root為二叉樹的根結(jié)點。（8分）voidABC(NODE*root){if(root){ABC(root->lchild);if(!root->lchild&&!root->rchild)x++;if(!root->lchild||!root->rchild)y++;ABC(root->rchild);}}（1）該算法是在二叉樹哪種遍歷程序基礎(chǔ)上修改成的？（2分）（2）執(zhí)行該算法后x和y中保存的值分別是什么？（3分）（3）試用x和y表示二叉樹的總結(jié)點數(shù)n。（3分）2、閱讀程序，回答問題。（12分）（1）voidproc_1(adjlistGL,inti,intn){printf(“%d”,i);visited[i]=true;edgenode*p=GL[i];while(p!=NULL){intj=p->adjvex;if(!visited[j])proc_1(GL,j,n);p=p->next;}}第7頁該函數(shù)實現(xiàn)的是()的()操縱，采用的存儲布局是()，算法履行時系統(tǒng)內(nèi)部需要調(diào)用()數(shù)據(jù)結(jié)構(gòu)。（4分）（2）voidproc_2(StackS,inte){StackT;intd;InitStack(&T);While(!EmptyStack(S)){Pop(&S,&d);if(d!=e)Push(&T,d);}While(!EmptyStack(T)){Pop(&T,&d);Push(&S,d);}}簡述proc_2的功能。（4分）（3）voidproc_3(Queue*Q){StackS;intd;InitStack(&S);While(!EmptyQueue(*Q)){DeleteQueue(Q,&d);Push(&S,d);}While(!EmptyStack(S)){Pop(&S,&d);EnterQueue(Q,d);}}簡述proc_3的功能。（4分）第8頁3、算法填空，使之可以對降序序列進行二分查找,要求找到則返回元素在查找表中位置，否則返回。（10分）intbinarysearch(splistst,intn,keytypekey)｛//降序序列函數(shù)，st順序表n表長key關(guān)鍵字intmid,low,high,find;find=0;low=1;high=n;while((low<=high)＆＆（find==0）)｛(1);if(key>st[mid].key)(2);elseif(key<st[mid].key)(3);else｛(4);//找到printf(“findst[%d].key==%d\n”,mid,key);(5);//返回｝｝if(find==0)return(0);｝/*binarysearch二分查找*/第1頁共5頁三峽大學(xué)2013年研究生入學(xué)測驗試題(A卷)科目代碼：838科目名稱：數(shù)據(jù)結(jié)構(gòu)（考生必須將答案寫在答題紙上，總分150分，考試時間180分鐘）一、選擇題(每小題2分，共40分)1、線性表采用鏈?zhǔn)酱鎯r，結(jié)點的存儲地址（）。A.必須是不連續(xù)的B.連續(xù)與否均可C.必須是連續(xù)的D.和頭結(jié)點的存儲地址相連續(xù)2、已知指針q所指結(jié)點是指針p所指結(jié)點的直接前驅(qū)，若在*q與*p之間插入結(jié)點*s，則應(yīng)執(zhí)行（）操作。A.s->next=p->next;p->next=sB.q->next=s;s->next=pC.p->next=s->next;s->next=pD.p->next=s;s->next=q3、設(shè)有一個按次棧S,元素按S1,S2,S3,S4,S5,S6按次進棧，若6個元素的出棧按次為S2,S3,S4,S6,S5,S1,則按次棧的容量至少應(yīng)為（）。A.2B.3C.4D.54、設(shè)有兩個串p和q，求q在p中首次出現(xiàn)的位置的運算稱作（）。A.連接B.模式匹配C.求子串D.求串長5、設(shè)有一個二維數(shù)A[m][n]，假設(shè)A[0][0]寄存位置在544，A[5][5]寄存位置在624，每個元素占一個空間，A[2][2]在（）位置。A.592B.586C.576D.6086、設(shè)有5個字符出現(xiàn)的頻度分別為2,7,5,4，則對應(yīng)的哈夫曼樹的帶權(quán)路徑長度為（）。A.34B.33C.35D.157、含n個頂點和e條邊的無向圖的鄰接矩陣中非零元素的個數(shù)為（）。A.eB.2eC.n2-eD.n2-2e第2頁8、長度為500的有序表采用折半查找時，查找成功最大比力次數(shù)為（）。A.8B.9C.10D.119、快速排序在下列哪種情況下最易發(fā)揮其長處（）。A.被排序的數(shù)據(jù)中含有多個相同排序碼B.被排序的數(shù)據(jù)已基本有序C.被排序的數(shù)據(jù)完全無序D.被排序的數(shù)據(jù)中的最大值和最小值相差懸殊10、下列關(guān)鍵字序列中，（）是堆。A.16,72,31,23,94,53B.94,23,31,72,16,53C.16,53,23,94，31,72D.16,23,53,31,94,7211、若已知一個棧的入棧序列是1，2，3，…，n，其輸出序列為p1,p2,p3,…,pn,若p1=n，則pi為（）。A.iB.n=iC.n-i+1D.不確定12、一棵具有257個結(jié)點的完全二叉樹，它的深度為（）。。A.7B.8C.9D.1014、用鄰接表表示圖進行廣度優(yōu)先遍歷時，通常是采用（）這種數(shù)據(jù)結(jié)構(gòu)來實現(xiàn)算法的。A.棧B.隊列C.樹D.圖15、深度優(yōu)先遍歷相似于二叉樹的（）。A.先序遍歷B.中序遍歷C.后序遍歷D.層次遍歷16、有8個結(jié)點的無向圖最多有（）條邊。A.14B.28C.56D.11217、折半查找有序表（4，6，10，12，20，30，50，70，88，100）。若查找表中元素58，則它將依次與表中哪些元素比較大小，查找結(jié)果是失敗。（）A.20，70，30，50B.30，88，70，50C.20，50D.30，88，50第3頁18、任何一個無向連通圖的最小生成樹（）。A.只有一棵B.一棵或多棵C.一定有多棵D.可能不存在19、鏈表適用于哪種查找（）。A.順序B.二分法C.順序，也能二分法D.隨機20、把一棵樹轉(zhuǎn)換為二叉樹后，這棵二叉樹具有什么樣的形態(tài)特征（）。A.是唯一的B.有多種C.有多種，但根結(jié)點都沒有左孩子D.有多種，但根結(jié)點都沒有右孩子二、填空題(每小題2分，共30分)1、對于一個表長為n的順序表，在表頭插入元素的時間復(fù)雜度為，在表尾插入元素的時間復(fù)雜度為。（要求用大O表示法表示）2、神槍手依次壓入10顆子彈進入槍膛，編號分別為1-10，則消滅第4個敵人的子彈編號是。3、一棵深度為6的滿二叉樹有個分支結(jié)點和個葉子結(jié)點。4、是被限定為只能在表的一端進行插入和刪除運算的線性表。5、已知某二叉樹的中序遍歷結(jié)果是：DEBAC，后序遍歷結(jié)果是：EDBCA，則該樹的先序遍歷序列是。6、設(shè)數(shù)組a[1…60,1…70]的基地址為2048，每個元素占2個存儲單元，若以列序為主序順序存儲，則元素a[32,58]的存儲地址為。7、如果一棵完全二叉樹具有1000個結(jié)點，則此完全二叉樹有個葉子結(jié)點，有個度為2的結(jié)點，有個結(jié)點只有非空左子樹，有個結(jié)點只有非空右子樹。8、由3個結(jié)點所構(gòu)成的二叉樹有種形態(tài)。9、寫出下列程序段的時間復(fù)雜度，要求用大O表示法表示。s=0;i=1;fori=0;i<n;i++)while(i<=n)for(j=0;j<n;j++)i=i*3;s+=B[i][j];sum=s;答：答：第4頁3、綜合題(共60分)1、試比較順序存儲結(jié)構(gòu)和鏈?zhǔn)酱鎯Y(jié)構(gòu)的優(yōu)缺點。在什么情況下用順序表比鏈表好？(10分)2、說明線性表、棧與隊的異同點。（10分）3、根據(jù)下圖回答下列問題。（20分）V2a1=3a3=4V1a4=2a2=2V3a8=5V4a7=4V6a6=5V7a10=3a5=6V5a9=5(5)要完成該AOE網(wǎng)中工程，最短時間是多少？（不考慮單位）（5分）(6)上圖中的關(guān)鍵路徑是什么（用頂點序列表示）？將活動a10的時間改成2可否提前完成？（5分）(7)若忽略邊的權(quán)值將上圖看成一個AOV網(wǎng)，并約定當(dāng)存在多個入度為的結(jié)點時先輸出編號較小的結(jié)點，則請寫出拓撲排序結(jié)果。（5分）(8)若疏忽邊的方向性將上圖看成無向網(wǎng)，各邊權(quán)值為經(jīng)濟代價，請給出該無向網(wǎng)的一棵最小生成樹。（5分）4、待排序樞紐字序列是38，19，50，61，32，23，11，14，15請回答下列排序問題(要求排成升序序列)：（10分）(5)若采用間接插入排序，第一個位置前移的元素樞紐字是？(3分)(6)若采用間接選擇排序，第一個位置前移的元素樞紐字是？(3分)(7)若采用快速排序，第一個位置前移的元素樞紐字是？(2分)(4)若采用堆排序，利用篩選操作建堆過程中最先交換的兩個元素關(guān)鍵字是？(2分)5、已知數(shù)據(jù)序列為：2，，3，5，8，7，4，6，2在一個初始值為空的二叉排序樹中順次插入這些結(jié)點，請畫出該二叉排序樹的最終形態(tài)。（10分）第5頁四、閱讀程序，回答問題。（20分，每題10分）（4）voidproc_1(StackS,inte){StackT;intd;InitStack(&T);While(!EmptyStack(S)){Pop(&S,&d);if(d!=e)Push(&T,d);}While(!EmptyStack(T)){Pop(&T,&d);Push(&S,d);}}簡述proc_1的功能。（10分）（5）voidproc_2(Queue*Q){StackS;intd;InitStack(&S);While(!EmptyQueue(*Q)){DeleteQueue(Q,&d);Push(&S,d);}While(!EmptyStack(S)){Pop(&S,&d);EnterQueue(Q,d);}}簡述proc_2的功能。（10分）三峽大學(xué)2013年研究生入學(xué)測驗試題(A卷)科目代碼：839科目名稱：計算機網(wǎng)絡(luò)（考生必須將答案寫在答題紙上）（注：本科目總分150分，測驗工夫為180分鐘。）一、填空題(每空1分，共10分，在答題紙上按按次寫上題號和答案)(1)是將各類息傳感裝備經(jīng)由過程互聯(lián)網(wǎng)，把物品與物品結(jié)合起來而形成的一個巨大收集，被譽為環(huán)球經(jīng)濟興起的下一個增長點。(2)第三代移動通（3G）采用IMT-2000國際標(biāo)準(zhǔn)，是在中國TD-SCDMA、美國CDMA2000和歐洲WCDMA三個標(biāo)準(zhǔn)提案綜合談判基礎(chǔ)上形成的，其技術(shù)核心是。(3)NGN支持多種業(yè)務(wù)，能夠?qū)崿F(xiàn)業(yè)務(wù)與傳送分離，控制功能獨立，接口開放，具有服務(wù)質(zhì)量(QoS)保證和支持通用移動性，其核心技術(shù)是基于。(4)采用802.11系列協(xié)議Wi-Fi成為互聯(lián)網(wǎng)一種重要補充網(wǎng)絡(luò)。它在MAC層采用的道爭用和談是。(5)現(xiàn)代密碼技術(shù)中解決數(shù)字簽名、密鑰分配、認證等主要依靠體制。(6)本地專用網(wǎng)需要采用技術(shù)才能實現(xiàn)訪問互聯(lián)網(wǎng)。(7)具有四層體系結(jié)構(gòu)，是Internet采用的標(biāo)準(zhǔn)協(xié)議體系。(8)是IETF設(shè)計的下一代互聯(lián)網(wǎng)和談，提議供給與mobileip和ipsec保持兼容的移動性和安全性。(9)是具有自我復(fù)制、破壞計算機功能或者數(shù)據(jù)的程序代碼。(10)加密技術(shù)的安全性主要取決于的長度和密文分析的時間代價。二、單項選擇題(每小題1分，共10分,在答題紙上按順序?qū)懮项}號和答案)(1)Internet所采用的交換技術(shù)是__A.電路交換B.報文交換C.分組交換D．程控交換(2)下面協(xié)議中,用于WWW傳輸控制的是__A.URLB.SMTPC.HTMLD.HTTP(3)從通訊和談的角度來看，路由器是在__上實現(xiàn)收集互聯(lián)A.物理層B.鏈路層C.收集層D.傳輸層(4)PPP協(xié)議在SONET/SDH中使用零比特填充法實現(xiàn)同步傳輸?shù)谋忍卮疄椋瑒t在接收站提交給數(shù)據(jù)鏈路層的代碼為：__A.B.C.D.A.全雙工B.半雙工C.單工D.上述三種均不是(6)以下不屬于內(nèi)部網(wǎng)關(guān)協(xié)議的是A．RIPB.OSPFC.BGPD.RIP2(7)與10Bast-T以太網(wǎng)相比，100Base-T以太網(wǎng)中傳輸?shù)淖钚L__A.為10Bast-T以太網(wǎng)的最小幀長的十分之一B.與10Bast-T以太網(wǎng)的最小幀不異C.為10Bast-T以太網(wǎng)的最小幀長的十分之一D.由于速度進步，因而無最小幀長的限制A、調(diào)制解調(diào)器B、網(wǎng)卡C、收集線D、都不是(10)DNS的中文含義是__。A、郵件體系B、地名體系C、服務(wù)器體系D、域名服務(wù)體系3、判斷題(每題1分，共10分。在答紙上順次寫上答案，精確打?，毛病打×)（1）物理層的義務(wù)就是透亮地傳送幀。（2）所有交換機都是工作在數(shù)據(jù)鏈路層以下的。（3）在IP網(wǎng)絡(luò)中，網(wǎng)絡(luò)層交換的數(shù)據(jù)單元是IP分組。（4）時延帶寬積的物理意義透露表現(xiàn)鏈路的極限數(shù)據(jù)容量。（5）是內(nèi)網(wǎng)地址。（6）IPV4是32位地址,而IPV6是64位地址。（7）UDP報文中地址是32位表示的端口號,用來區(qū)分應(yīng)用層進程的。（8）防火墻用于兩個網(wǎng)絡(luò)之間的接入控制，主要解決內(nèi)網(wǎng)的安全問題。（9）IP地址是16位表示的是全球唯一的地址,每個主機都只能有一個唯一的IP地址。（10）無線傳感器網(wǎng)絡(luò)具有完整的網(wǎng)絡(luò)體系結(jié)構(gòu)，包括物理層、MAC層、網(wǎng)絡(luò)層、傳輸層和應(yīng)用層五層結(jié)構(gòu)。四、問答題（每小題10分，共40分）1）分類IP地點體系中經(jīng)常利用IP地點有哪幾類？各類地點的起止地點為幾何？2）試說明計算機收集拓撲布局。有哪幾種常見的收集拓撲類型？3）什么叫做以太網(wǎng)？以太網(wǎng)有哪兩個主要標(biāo)準(zhǔn)？4）OSI體系結(jié)構(gòu)包括哪幾層？1、設(shè)有一電話線路，當(dāng)前的道帶寬為3.1kHz,道的極限速率為31kbps?，F(xiàn)在想對其進行改造，準(zhǔn)備將極限速率增加50%，試問：（10分）1）噪比至少增加多少倍？2）根據(jù)上題計算結(jié)果，進步收集的極限傳輸速率與與噪比有何聯(lián)系關(guān)系？2、設(shè)某CIDR路由器建立了以下路由表:（10分）目的網(wǎng)絡(luò)網(wǎng)絡(luò)前綴22()23()25(28)25(28)194.5.153.(92)-*(默認)分別為下列目的地址的分組計算其下一跳:1)652)13)22六、綜合應(yīng)用題（20+20，共40分）1、設(shè)有一網(wǎng)絡(luò)拓撲如右下圖所示。圓形圖中字母表示路由器節(jié)點。各結(jié)點鏈路之間的帶寬開銷標(biāo)示在鏈路上(假設(shè)所有網(wǎng)絡(luò)到鄰近路由節(jié)點的帶寬開銷為0)。試寫出(1)(2)題中A點的路由表(目的網(wǎng)絡(luò)，距離，下一跳路由)，并用路由節(jié)點順序表示各條目的路由路徑，如N4,2,D,（AD）（20分）(1)若采用RIP路由協(xié)議；(2)若改用OSPF路由和談（帶寬為開銷）；下一跳接口接口1R1R2R3R44CN13EN3A23B37N23DN421F3N52、現(xiàn)有一單位的網(wǎng)絡(luò)規(guī)劃如右下圖。單位只申請到一個C類地點擬分派C類地點數(shù)：剩下的IP地點作為后備擴大用?，F(xiàn)在有如下限制條件：（20分）1）N2有計算機60臺，需要劃分2個vlan,且PC0需要外網(wǎng)訪問服務(wù)器SV0；2）網(wǎng)絡(luò)內(nèi)部可以使用堆疊的hub或交換機舉行局域網(wǎng)擴大；3）路由器和三層交換機SW1都支持CIDR協(xié)議。請根據(jù)上述基本條件，進行如下網(wǎng)絡(luò)實施設(shè)計：1）提出合理的地址劃分方案；2）申明N2的Vlan施行步驟，若何實現(xiàn)PC0需要外網(wǎng)拜候服務(wù)器SV0。SW1N2PC0SV0R2R4N4R01R02N1R1R3N3三峽大學(xué)2014年研究生入學(xué)考試試題(A卷)科目代碼：838科目稱號：數(shù)據(jù)布局考試時間為3小時，卷面總分為150分答案必須寫在答題紙上一、填空題(每小題2分，共30分)1.有一算法的計算次數(shù)f（n）=+0.001n2+1000nlgn，則該算法的復(fù)雜度用大O表示法應(yīng)該是（）A.O()B.O(1)C.O(n2)D.O(nlgn)2、鏈表的特征是（）A．邏輯連續(xù),物理連續(xù)B.邏輯連續(xù),物理不連續(xù)C．邏輯不繼續(xù),物理繼續(xù)D.邏輯繼續(xù),物理不肯定繼續(xù)3、已知鏈表中某結(jié)點指針為p，在其后插入一個指針s指向的新結(jié)點，則需執(zhí)行下列哪個指令A(yù)．p->next=sB.p->next=s;s->next=p->next;C.s->next=p->next;p->next=s;D.s->next=p->next;s->next=p;4.設(shè)有一個順序棧P，元素按P1,P2,P3,P4.P5順序進棧，若5個元素的出棧順序為P2,P3,P5,P4,P1，則順序棧的容量至少應(yīng)為（）。A.2B.3C.4D.55、設(shè)有一個二維數(shù)A[10][10]，假設(shè)A[2][0]的寄存位置在1020，按行優(yōu)先存儲，每個元素占2空間，A[5][5]在（）位置。A．1102B.1100C.1088D.10906、結(jié)點的權(quán)重分別是1,2,3,3,3，則對應(yīng)哈弗曼樹的帶權(quán)途徑長度為（）A.26B.27C.28D.307、已知某二叉樹先序遍歷結(jié)果為ABCDEF，中序遍歷果為BCAEFD，則其后序遍歷結(jié)果是（）.A．BCDEFAB.CBFEDAC.ABDCEFD.BCEFDA8、在10個頂點的無向圖的鄰接表中，除頭結(jié)點外，共有（）個鏈表結(jié)點。A.10B.20C.30D.159.在單鏈表中刪除一個指定元素的復(fù)雜度是（）A、O(n)B.O(n2)C.O(1)D.O(nlog2n)第2頁10、在長度為100的二叉排序樹中舉行查找一個存在的元素，最多比力（）次。A.8B.7C.6D.111、圖的廣度優(yōu)先遍歷過程中，需要用到（）作為輔助數(shù)據(jù)布局包管同層結(jié)點拜候的精確按次。A、按次表B、鏈表C、棧D、隊列12、待散列的線性表為（98，35，27，42，67，56），假定選用的散列函數(shù)是H（K）=K%7，則與98沖突元素個數(shù)是（）A、B、1C、2D、313、快速排序最壞情況下的復(fù)雜度是（）A、O(n)B.O(n2)C.O(1)D.O(nlog2n)14、下列算法中屬于穩(wěn)定排序的是（）A.堆排序B.簡單選擇排序C.快速排序D.二分插入排序15、對于數(shù)據(jù)量不大且接近有序時，適合采用（）A.堆排序B.間接插入排序C.快速排序D.冒泡排序二、判斷題題(每題2分，共20分,對的打√，錯的打×)1.數(shù)據(jù)結(jié)構(gòu)的邏輯結(jié)構(gòu)決定了其存儲結(jié)構(gòu)。（）2.比較算法復(fù)雜度需在同一運行環(huán)境下的運行比較時間（）3.對于最大指數(shù)很大，非零項很少的一元多項式加法適合采用鏈?zhǔn)酱鎯Y(jié)構(gòu)存儲。（）4.當(dāng)隊中有元素時，隊尾元素不克不及出隊。（）5.除了內(nèi)存溢出，鏈棧一般不會滿。（）6.給定二叉樹先序遍歷序列和后序遍歷序列一般不能唯一確定樹結(jié)構(gòu)。（）7.圖的非關(guān)鍵活動時間可以任意安排。（）8.稠密圖采用毗鄰矩陣的存儲效力要高于毗鄰表。（）9.二分查找辦法不成以對鏈表舉行。（）10.當(dāng)排序長度大且數(shù)據(jù)隨機但不要求穩(wěn)定時，最適合采用堆排序算法。（）3、填空題(每個空2分，共30分)1．用21把鑰匙試開1把鎖（只有一把能開），平均需要試（）次。2.15輛車依次開進了一個死胡同，但第5輛車要開走，后面需要退出（）輛車。3.采用空閑單元法的循環(huán)隊列容量為100，若f=25，r=47，則隊長（），若f=55，r=25，則隊長是（）。4.數(shù)組A[10][10]采用列優(yōu)先存儲，每個數(shù)據(jù)占4個字節(jié)，A[0][0]起始地址是2000，該數(shù)組的存儲空間需要（）個字節(jié)；A[8][7]的存儲地址是（）.第3頁5、設(shè)一棵完全二叉樹具有1001個結(jié)點，則它有()個葉子結(jié)點，有()個度為2的結(jié)點，有()個結(jié)點只要非空左子樹，第4個葉子結(jié)點編號是()．6.10個頂點的無向完全圖有（）條邊，9個頂點有向完全圖有（）條邊。7.在長度為11的遞增有序表中二分查找第5個元素，需要比力（）次。8.稠密圖適合采用（）存儲布局，對應(yīng)的最小天生樹算法應(yīng)該是基于（）歸并較好。四、計算題。（共50分）1.建二叉排序樹的序列是：2，4，1，3，9，請畫出該二叉排序樹結(jié)構(gòu)，并計算基于該樹進行查找的平均查找長度。（10分）2.根據(jù)下圖回答下列問題（20分）V4a1=2V1a2=2a4=2V7a8=6V5a3=4a5=5a7=4V6a6=4V3a9=2V2a10=4（1）要完成該AOE網(wǎng)中工程，最短時間是多少？（不考慮單位）（5分）（2）上圖中的關(guān)鍵路徑是什么（用頂點序列表示）？將活動a8的時間改成5可否提前完成？（5分）（3）若忽略邊的權(quán)值將上圖看成一個AOV網(wǎng)，并約定當(dāng)存在多個入度為的結(jié)點時先輸出編號較小的結(jié)點，則請寫出拓撲排序結(jié)果。（5分）（4）若疏忽邊的方向性將上圖看成無向網(wǎng)，各邊權(quán)值為經(jīng)濟代價，請給出該無向網(wǎng)的一棵最小天生樹。（5分）3.已知待排序關(guān)鍵字序列是38，19，50，61，32，23，11，15，14請回答下列排序問題(要求排成升序序列)：（20分）(1)若采用直接插入排序，第二個位置前移的元素關(guān)鍵字是？(4分)(2)若采用希爾排序(di＝5,3,1),第二個位置前移的元素關(guān)鍵字是？(4分)(3)若采用簡單選擇排序，第二個位置前移的元素關(guān)鍵字是？(4分)(4)若采用快速排序，第二個位置前移的元素樞紐字是？(4分)(5)若采用堆排序，利用篩選操作建堆過程中第二次交換的兩個元素關(guān)鍵字是？(4分)第4頁五、程序題(每題10分，共20分)1.x和y是整型全局變量，初值均為，root為二叉樹的根結(jié)點。（10分）voidABC(NODE*root){if(root){ABC(root->lchild);ABC(root->rchild);if(root->lchild&&root->rchild)x++;if(root->lchild||root->rchild)y++;}}（1）該算法是在二叉樹哪類遍歷程序根蒂根基上修改成的？（3分）（2）履行該算法后x和y中儲存的值分別是什么？（4分）（3）試用x和y表示二叉樹的總結(jié)點數(shù)n。（3分）2.算法填空，使之可以對降序序列進行二分查找,要求找到則返回元素在查找表中位置，否則返回（5分）。intbinarysearch(splistst,intn,keytypekey)｛//降序序列函數(shù)，st按次表n表長key樞紐字intmid,low,high,find;find=0;low=1;high=n;while((low<=high)＆＆（find==0）)｛（1）;if(key>st[mid].key)（2）;elseif(key<st[mid].key)(3);else｛(4);//找到printf(“findst[%d].key==%d\n”,mid,key);(5);//返回位置｝｝return(0);｝/*binarysearch二分查找*/三峽大學(xué)2015年研究生入學(xué)測驗試題(B卷)科目代碼：838科目名稱：數(shù)據(jù)結(jié)構(gòu)考試時間為3小時，卷面總分為150分答案必須寫在答題紙上（本套試題出現(xiàn)的代碼采用C語言規(guī)定）一、單選題（每題2分，共30分）1.某線性表中最經(jīng)常利用的操縱是存取第i個元素及其先驅(qū)的值，采用（）存儲體式格局最省工夫。A.按次表B.帶頭結(jié)點的單向鏈表C.帶頭結(jié)點的雙向循環(huán)鏈表D.帶尾指針的單向循環(huán)鏈表2.下列選項中，（）是鏈表不具有的特點。A.插入和刪除運算不需要移動元素B.所需存儲空間與線性表的長度成正比C.不必事先估計存儲空間大小D.可以隨機訪問表中任意元素3.設(shè)棧S和隊列Q的初始狀態(tài)均為空，元素a,b,c,d,e,f,g依次進入棧S,如果每個元素出棧后立即進入隊列Q,且7個元素出隊的順序為b,d,c,f,e,a,g,則棧S的容量至少是（）A.2B.3C.5D.74.設(shè)隊列中有A,B,C,D,E這5個元素，個中隊首元素為A.如果對這個隊列反復(fù)履行下列操縱：1）輸出隊首元素；2）把隊首元素插入到隊尾；3）刪除隊首元素；4）再次刪除隊首元素。前述操縱直到隊空為止，則可能取得輸出序列（）A.ACECCB.ACEC.ACECCCD.ACEC5.下列排序算法中，（）算法可能會出現(xiàn)下面的情況，即當(dāng)初始數(shù)據(jù)有序時，花費時間反而最多。A.堆排序B.冒泡排序C.快速排序D.希爾排序6.在關(guān)鍵字隨機分布的前提下，用平衡的二叉排序樹進行查找，其平均查找長度同（）數(shù)量級相當(dāng)。A.按次查找B.二分查找C.快速查找D.都不精確7.對于一個有向圖，若一個頂點的度為k1,出度為k2,則對應(yīng)的鄰接表中，該結(jié)點單鏈表的邊結(jié)點數(shù)目為（）A.k1B.k2C.k1-k2D.k1+k2第2頁8.已知一個有向圖G具有n個頂點和e條弧，用鄰接表來存儲表示需要（）個弧結(jié)點。A.nB.n2C.eD.2e9.哈希表的長度m=10,哈希函數(shù)H(key)=key%7,樞紐字為k的記實在定址時發(fā)生了沖突，若采用開放地點法（也稱再散列法）辦理沖突，則新地點的計算公式為（）A.(H(k)+di)/10B.(H(k)+di)/7C.(H(k)+di)%10D.(H(k)+di)%710.一個帶頭結(jié)點的非空循環(huán)單鏈表，其尾指針是R,則其首元素結(jié)點的地點為（）A.R->nextB.*(R->next->next)C.&(R->next->next)D.R->next->next11.下列樞紐字序列，不成能構(gòu)成某二叉排序樹的查找途徑的序列是（）A.95,22,91,24,94,71B.92,20,91,34,88,35C.21,89,77,29,36,38D.12,25,71,68,33,3412.若7個頂點的無向圖是連通的，則其邊數(shù)至少是（）A.6B.7C.8D.1413.一個完全二叉樹的第6層（樹根為第1層）有8個葉子結(jié)點，則該樹的結(jié)點個數(shù)最多為（）A.39B.52C.111D.11914．快速排序在下列()情況下最容易發(fā)揮其長處。A.被排序的數(shù)據(jù)中含有多個排序碼B.被排序數(shù)據(jù)已基本有序C.被排序數(shù)據(jù)完全無序D.被排序數(shù)據(jù)的最大值和最小值相差懸殊15.對n個不同的元素進行冒泡排序，在下列（）情況下?lián)Q位次數(shù)最多。A.元素從小到大排列好B.元素從大到小排列好C.元素?zé)o序D.元素根本有序二、填空題（每空2分，共30分）1.在n個元素的按次表中刪除一個元素，需要均勻移動（）次。2.循環(huán)單鏈表以list為頭指針，結(jié)點的指針域next,指針p所指結(jié)點為表尾結(jié)點的條件是（）。3．一個長度為N的數(shù)組空間存放循環(huán)隊列，頭尾指示器分別為front和rear,則該隊列元素個數(shù)為（）。4．廣義表（（a,b），（a,(b)））的深度是（）。5.如果結(jié)點A有3個兄弟，B是A的雙親，則B的度是（）。6.有一個圖的毗鄰矩陣按行順次是[[0,1,1,1],[1,0,1,0],[1,1,0,1],[1,0,1,0]]，圖中有（）條邊，度最大的的極點的度是（）。7.在一組記實（54,38,96,23,15,72,60,45,83）舉行插入排序時，當(dāng)把第7個記實60插入到有序表時，為尋覓插入位置需比力（）次第3頁8.對于n個記錄的集合進行冒泡排序，在最壞情況下所需時間是（），若對其進行快速排序，在最壞情況下所需時間是()9.假設(shè)用循環(huán)單鏈表實現(xiàn)隊列，結(jié)點指針域為next,若隊列非空，且尾指針為R,則將新結(jié)點S加入隊列時，需履行三條語句（）；（）；R=S;.10.n個極點的連通無向圖至少有（）條邊，最多有（）條邊11.在程序段：for(i=1;i<=n;i++)for(j=i+1;j<=n;j++)x++;中，x++履行了（）次。3、計算題（每題10分，共50分）1.假設(shè)有6行8列的二維數(shù)組A(下標(biāo)從開始),每個元素占6個字節(jié)，存儲器按字節(jié)編址。已知A的首地址為1000,計算：1)數(shù)組A共占用多少字節(jié)。（2分）2）數(shù)組A的最后一個元素地址（3分）3）按行存儲時A[3][6]的地址（2分）按列存儲時A[3][6]的地址(3分)。2.一棵度為k的樹中n1個度為1的結(jié)點，n2個度為2的結(jié)點，…，nk個度為k的結(jié)點，則該樹中有多少個葉子結(jié)點(5分)并證明之（5分）。3.二叉樹的先根次序訪問序列為GFKDAIEBCHJ，中根次序訪問序列為DIAEKFCJHBG，畫出這個樹（10分）。4.對圖一，從頂點開始訪問，給出深度優(yōu)先和廣度優(yōu)先搜索結(jié)果（各5分）。12435圖16785.給定關(guān)鍵字序列（8,3,25,19,12,30,47,34），按次序插入建立一個二叉排序樹，畫出這個樹（10分）。四、程序題（每題20分，共40分）1已知一個帶有表頭結(jié)點的單鏈表，結(jié)點結(jié)構(gòu)為{data,link}。假設(shè)鏈表中只給出了頭指針list.在不改變鏈表的前提下，設(shè)計一個盡可能高效的算法，查找鏈表中倒數(shù)第k個位置上的結(jié)點（k為正整數(shù)）。若查找成功，算法獲得該結(jié)點的data的值，并返回1；否則返回回0.采用C語言實現(xiàn)函數(shù)intsearch(RecordType*list,intk，DataType*d)。（不得使用額外大內(nèi)存）2二叉樹的數(shù)據(jù)為正整數(shù)，按按次體式格局存儲與數(shù)組A中，對比完全二叉樹缺失結(jié)點的地方存0.編寫C言語函數(shù)intCount（intA[]）計算二叉樹中非葉子結(jié)點的數(shù)目。第1頁共4頁三峽大學(xué)2016年研究生入學(xué)考試試題(A卷)科目代碼：838科目名稱：數(shù)據(jù)結(jié)構(gòu)考試時間為3小時，卷面總分為150分答案必須寫在答題紙上一、選擇題(每題3分，共60分)1、數(shù)據(jù)在存儲器內(nèi)表示時，物理地址與邏輯地址相同且連續(xù)，稱為（）。A.存儲結(jié)構(gòu)B.邏輯結(jié)構(gòu)C.順序存儲結(jié)構(gòu)D.鏈?zhǔn)酱鎯Y(jié)構(gòu)2、一個向量第一個元素的存儲地址是100，每個元素的長度為2，則第5個元素的地址是（）。A.110B.108C.100D.1203、棧中元素的進出原則是（）。A.先進先出B.后進先出C.?？談t進D.棧滿則出4、如下陳述中正確的是（）。A.串是一種特殊的線性表B.串的長度必須大于零C.串中元素只能是字母D.空串就是空白串5、設(shè)有一個二維數(shù)B[m][n]，假設(shè)B[0][0]存放位置在544，B[2][2]存放位置在576，每個元素占一個空間，B[5][5]在（）位置。A.592B.586C.624D.6086、設(shè)5個字符的頻度分別為1,2,3,4,5，其哈夫曼樹的帶權(quán)途徑長度為（）。A.34B.33C.35D.377、鏈?zhǔn)酱鎯Φ拇鎯Σ季炙即鎯臻g：（）。A．分兩部分，一部分存放結(jié)點值，另一部分存放表示結(jié)點間關(guān)系的指針B．只有一部分，存放結(jié)點值第2頁C．只有一部分，存儲表示結(jié)點間關(guān)系的指針D．分兩部分，一部分存放結(jié)點值，另一部分存放結(jié)點所占單元數(shù)8、下述幾種排序方法中，要求內(nèi)存最大的是（）。A．插入排序B．快速排序C．歸并排序D．選擇排序9、二叉樹長短線性數(shù)據(jù)布局，關(guān)于它的存儲，以下哪個描述精確（）。A．它不克不及用按次存儲布局存儲B．按次存儲布局和鏈?zhǔn)酱鎯Σ季侄寄艽鎯．按次存儲布局和鏈?zhǔn)酱鎯Σ季侄疾豢瞬患袄肈．它不克不及用鏈?zhǔn)酱鎯Σ季执鎯?0、用改進的起泡排序算法對n個元素舉行排序時最多比力次數(shù)為()。A.nB.n-1C.n2D.n(n-1)/211、若已知一個棧的入棧序列是1，2，3，…，n，其輸出序列為p1,p2,p3,…,pn,若p1=n，則pi為（）。A.iB.n=iC.n-i+1D.不確定12、若一組記錄的排序碼為（46,79,56,38,40,84），則利用堆排序的方法建立的初始堆為（）。A.79,46,56,38,40,84B.84,79,56,38,40,46C.84,79,56,46,40,38D.84,56,79,40,46,3813、線性表Ｌ在什么情況下適用于使用鏈?zhǔn)浇Y(jié)構(gòu)實現(xiàn)（）。A．需經(jīng)常修改Ｌ中的結(jié)點值B．需不斷對Ｌ進行刪除插入C．Ｌ中含有大量的結(jié)點D．Ｌ中結(jié)點結(jié)構(gòu)復(fù)雜14、向一個有128個元素的順序表中插入一個新元素并保持原來順序不變，平均要移動多少個元素（）。A．8B．62C．63D．6415、深度優(yōu)先遍歷類似于二叉樹的（）。A.先序遍歷B.中序遍歷C.后序遍歷D.條理遍歷16、任何一個無向連通圖的最小生成樹（）。A.只有一棵B.一棵或多棵C.一定有多棵D.可能不存在第3頁17、有7個結(jié)點的無向圖最多有多少條邊（）。A.14B.28C.56D.2118、折半查找有序表（4，6，10，12，20，30，50，70，88，100）。若查找表中元素58，則它將依次與表中哪些元素比較大小，查找結(jié)果是失敗（）。A.20，70，30，50B.30，88，70，50C.20，50D.30，88，5019、鏈表適用于哪種查找（）。A.按次B.二分法C.按次，也能二分法D.隨機20、把一棵樹轉(zhuǎn)換為二叉樹后，這棵二叉樹具有什么樣的形態(tài)特征（）。A.是唯獨的B.有多種C.有多種，但根結(jié)點都沒有左孩子D.有多種，但根結(jié)點都沒有右孩子二、填空題(每小題2分，共30分)1、快速排序的平均時間復(fù)雜度是，它在最壞情況下的時間復(fù)雜度是。（要求用大O表示法表示）2、一棵具有257個結(jié)點的完全二叉樹，它的深度為。3、已知一采用空閑單元法的循環(huán)隊列容量為20，隊列的首、尾指針分別用f和r表示，f＝3，r＝18時隊列的長度為，f＝15，r＝7時隊列的長度為。4、三元素組表中的每個結(jié)點對應(yīng)于稀疏矩陣的一個非零元素，它包含有三個數(shù)據(jù)項，分別表示該元素的、和。5、如果一棵完全二叉樹具有500個結(jié)點，則此完全二叉樹有個葉子結(jié)點，有個度為2的結(jié)點，有個結(jié)點只要非空左子樹，有個結(jié)點只要非空右子樹。6、由3個結(jié)點所構(gòu)成的二叉樹有種形態(tài)。7、在對一組記實（54，38，96，23，15，72，60，45，83）舉行間接插入排序時，當(dāng)把第7個記實60插入到有序表時，為了尋覓插入位置至少需要比力次。8、稠密圖適合采用存儲布局。第4頁3、綜合題(共60分)1、描述以下三個概念的區(qū)別：頭指針、頭結(jié)點、首元結(jié)點（第一個元素結(jié)點）。在單鏈表中設(shè)置頭結(jié)點的作用是什么？（15分）2、根據(jù)下圖回答問題（15分）V2a1=3a3=4V1a4=2a2=2V3a5=6V5a9=5V4a7=4a6=5V7a10=3V6a8=5（1）要完成該AOE網(wǎng)中工程，最短時間是多少？（不考慮單位）（5分）（2）上圖中的關(guān)鍵路徑是什么（用頂點序列表示）？將活動a10的時間改成2能否提前完成？（5分）（3）若忽略邊的權(quán)值將上圖看成一個AOV網(wǎng)，并約定當(dāng)存在多個入度為的結(jié)點時先輸出編號較小的結(jié)點，則請寫出拓撲排序結(jié)果。（5分）3、假設(shè)用于通的電文僅由8個字母組成，字母在電文中出現(xiàn)的頻率分別為0.07，0.19，0.02，0.06，0.32，0.03，0.21，0.10。試為這8個字母設(shè)計哈夫曼編碼。使用～7的二進制表示形式是另一種編碼方案。對于上述實例，比較兩種方案的優(yōu)缺點。（15分）4、已知一棵度為k的樹中有n1個度為1的結(jié)點，n2n6個度為6的結(jié)點，則該樹中有多少個葉子結(jié)點，并證明。（5分）5、請對下圖的無向帶權(quán)圖,要求寫出詳細過程：（10分）（1）按普里姆算法求其最小天生樹；（從極點a開始）（5分）（2）按克魯斯卡爾算法求其最小生成樹。（5分）三峽大學(xué)2017年研究生入學(xué)考試試題(A卷)科目代碼：836科目名稱：數(shù)據(jù)結(jié)構(gòu)考試時間為3小時，卷面總分為150分答案必須寫在答題紙上一、填空題（每空2分，共20分）1）__________是組成數(shù)據(jù)的基本單位，是數(shù)據(jù)集合的個體。2）數(shù)據(jù)布局的存儲布局分為按次存儲布局和__________兩種。3）以下程序段:for(i=1;i<=9;i++)for(j=i+1;j<=10;j++)x++;個中語句x++履行的次數(shù)為__________。4)在帶頭結(jié)點循環(huán)單鏈表L（L同時透露表現(xiàn)頭指針，結(jié)點指針域用next透露表現(xiàn)）中，判斷指針p所指結(jié)點是否為表尾結(jié)點的條件是__________。5）當(dāng)兩個對頂棧共享一個存儲區(qū)時，可利用一維數(shù)組stack[M]實現(xiàn)（下標(biāo)從到M-1），兩個棧的棧頂指針分別為top[1]和top[2]，則棧滿的條件是__________。6）若用一個大小為6的數(shù)組來實現(xiàn)循環(huán)隊列，且當(dāng)前的rear和front的值分別為和3，當(dāng)從隊列中刪除2個元素后，再加入3個元素后，rear的值為______。7）設(shè)一個哈希表表長M為200，用除留余數(shù)法構(gòu)造哈希函數(shù)，及H（K）=K%P，為使函數(shù)具有較好機能，P應(yīng)選_________。8）在樹布局中，一個結(jié)點的子樹個數(shù)稱為此結(jié)點的_________。9）圖遍歷中的兩種主要遍歷方法分別是_________和廣度優(yōu)先搜索。10）為肯定數(shù)據(jù)元素在列表中的位置，需和給定值舉行比力的樞紐字個數(shù)的盼望值，稱為查找算法在查找成功時的_________。第2頁二、單項選擇題（每小題3分，共30分）1）有一個帶頭結(jié)點的單鏈表L，則判斷其是否為空鏈表的條件是（）A.L==NULLB.L->next==NULLC.L->next==LD.L!=NULL2）若線性表最經(jīng)常利用的操縱是存取第i個元素及其先驅(qū)的值，可采用（）存儲體式格局最節(jié)流工夫。A.單向鏈表B.雙向鏈表C.單向循環(huán)鏈表D.順序表3）某個棧的入棧的序列為A,B,C,D,E,F,G，則可能的出棧序列為（）A.ABCDEFGB.GABCDEFC.DCBAGEFD.BAFDCEG4）評價一個算法性能好壞的重要標(biāo)準(zhǔn)是（）A.算法易于調(diào)試B.算法易于理解C.算法的精確性D.算法的工夫復(fù)雜度5）已知哈希表的長度m=20，哈希函數(shù)H(key)=key%19，關(guān)鍵字為k的記錄在定位時產(chǎn)生了沖突，若采用開放定址解決沖突，則新地址的計算公式為（）A.(H(k)+di)%20C.(H(k)+di)/19B.(H(k)+di)%19D.(H(k)+di)/206）棧和隊列的共同特點是（）A.只允許在端點處插入和刪除元素B.都是先進后出C.都是后進先出D.沒有共同點7）以下數(shù)據(jù)結(jié)構(gòu)中哪一個是非線性結(jié)構(gòu)？（）A.隊列B.棧C.線性表D.二叉樹8）鏈表不具備的特點是（）A.可隨機訪問任一結(jié)點B.插入刪除不需要移動元素C.不用事先估計存儲空間D.所需空間與其長度成反比9）與單鏈表相比，雙鏈表的長處之一是（）A.插入、刪除操作更簡單B.可以進行隨機訪問C.可以省略表頭指針或表尾指針D.順序訪問相鄰結(jié)點更靈活10）若長度為n的線性表采用順序存儲結(jié)構(gòu)，在其第i個位置插入一個新元素的算法的時間復(fù)雜度為（）A.O(0)B.O(1)C.O(n)D.O(n2)第3頁三、簡答題（每小題10分，共50分）1、給出四種根本數(shù)據(jù)布局稱號及其干系圖示。2、數(shù)據(jù)結(jié)構(gòu)研究內(nèi)容主要包括數(shù)據(jù)的邏輯結(jié)構(gòu)和數(shù)據(jù)的物理結(jié)構(gòu)。請分別簡述邏輯布局和物理布局的含義，并扼要指出線性表的兩種常見物理布局。3、一棵二叉樹的中序序列和后序序列分別以下，請畫出該二叉樹。中序序列：DIGJLKBAECHF后序序列：ILKJGDBEHFCA4、給定表（19，14，22，15，20，21，56，10）1）按元素在表中的次序，建立一棵二叉排序樹；2）對1）中所建立的二叉排序樹進行中序遍歷，寫出遍歷序列；5、已知一維數(shù)組中的數(shù)據(jù)為（18，12，25，53，18），1）試寫出插入排序（升序）過程，2）并指出具有n個元素的插入排序的工夫復(fù)雜度是幾何？4、組織題（共30分）1、對以下樞紐字序列建立一個長度為20的哈希表（ZuoPing,ZuoWencheng,LiuJinqiao,LiMengting,LiWeiwen,ZhuZequn,WanQiubo），哈希函數(shù)為H(K)=(K中第一個字母在字母表中的序號)%19，用線性探測法解決沖突。要求給出如下結(jié)果：1）計算出每個關(guān)鍵字對應(yīng)的哈希地址，如果有沖突，需要給出線性探測法解決沖突后的哈希地址。需要給出每個哈希地址的計算過程，并繪制構(gòu)造好的哈希表。2）計算在等幾率情形下查找成功時的均勻查找長度。五、編程美滿程序（共20分）下列c語言編寫的程序，主要完成如下功能：1）初始化三個帶頭結(jié)點的單鏈表La，Lb，Lc；2）連續(xù)讀入一組整數(shù)（比如123-1-2-34-4-550），并將非零整數(shù)第4頁依次存儲在單鏈表La中（注意：碰到第一個結(jié)束輸入）；3）將La分解成兩個帶頭結(jié)點的單鏈表Lb和Lc，個中Lb中寄存負整數(shù)，Lc中寄存正整數(shù)。要求Lb和Lc利用La中的結(jié)點空間。4）在分解后，能表現(xiàn)Lb中所有的負整數(shù)，Lc中所有的正整數(shù)。請根據(jù)上述已知條件，并結(jié)合下面的代碼，完成下面三個問題：1）在voidDisplayList(LinkListL)函數(shù)體中，寫出代碼，使之能顯示單鏈表L中的數(shù)據(jù)元素；2）voidDivideList(LinkListLa,LinkListLb,LinkListLc)函數(shù)體中，寫出代碼，使之能將La分解成滿足上述要求的Lb和Lc。3）假定在主函數(shù)中調(diào)用CreateFromTail(La)時，輸入的整數(shù)系列是：123-1-2-34-4-550，請給出主函數(shù)調(diào)用DivideList(La,Lb,Lc);后，調(diào)用DisplayList(Lb);和DisplayList(Lc);后的屏幕輸出結(jié)果。//----------------------------------------------代碼-------------------------------------------------#include<stdio.h>#include<stdlib.h>#defineElemTypeintstructtag_node/*結(jié)點類型定義*/{ElemTypedata;structtag_node*next;};typedefstructtag_nodeNode;typedefstructtag_node*LinkList;voidInitList(LinkList*L);voidCreateFromTail(LinkListL);voidDisplayList(LinkListL);voidDivideList(LinkListLa,LinkListLb,LinkListLc);第5頁main(){LinkListLa,Lb,Lc;InitList(&La);//初始化單鏈表LaInitList(&Lb);//初始化單鏈表LbInitList(&Lc);//初始化單鏈表Lcprintf("組織鏈表La:請輸入一系列整數(shù)，并以輸入整數(shù)竣事輸入\n");CreateFromTail(La);//輸入數(shù)據(jù)，構(gòu)造單鏈表LaDivideList(La,Lb,Lc);//將La分解成Lb和Lcprintf("\nAfterdividing:");DisplayList(Lb);//顯示LbDisplayList(Lc);//顯示Lc}voidInitList(LinkList*L){*L=(LinkList)malloc(sizeof(Node));(*L)->next=NULL;}voidCreateFromTail(LinkListL){Node*r,*s;intc;intflag=1;r=L;while(flag)/*flag初值為1，當(dāng)輸入時，置flag為，建表結(jié)束*/{scanf("%d",&c);if(c!=0){s=(Node*)malloc(sizeof(Node));/*建立新結(jié)點s*/s->data=c;r->next=s;第6頁r=s;}else{flag=0;s->next=NULL;}}}voidDisplayList(LinkListL){//請寫出代碼，實現(xiàn)表現(xiàn)單鏈表L中所有數(shù)據(jù)元素的功能//注意，答案寫在答題紙上}voidDivideList(LinkListLa,LinkListLb,LinkListLc){//請寫出代碼，實現(xiàn)將La分解成兩個帶頭結(jié)點的單鏈表Lb和Lc的功能//注意，答案寫在答題紙上}//第3問的答案也寫在答題紙上三峽大學(xué)2019年碩士研究生入學(xué)測驗試題(A卷)科目代碼：836科目稱號：數(shù)據(jù)布局考試時間為3小時，卷面總分為150分答案必須寫在答題紙上一、選擇題(每題3分，共60分)1、一個向量第一個元素的存儲地址是100，每個元素的長度為2，則第5個元素的地址是（）。A.110B.108C.100D.1202、數(shù)據(jù)在計算機存儲器內(nèi)表示時，物理地址與邏輯地址相同并且是連續(xù)的，稱為（）。A.存儲布局B.邏輯布局C.按次存儲布局D.鏈?zhǔn)酱鎯Σ季?、棧中元素的進出原則是（）。A.先進先出B.后進先出C.棧空則進D.棧滿則出4、如下陳述中正確的是（）。A.串是一種特殊的線性表B.串的長度必須大于零C.串中元素只能是字母D.空串就是空缺串5、設(shè)有一個二維數(shù)B[m][n]，假設(shè)B[0][0]存放位置在544，B[2][2]存放位置在576，每個元素占一個空間，B[5][5]在（）位置。A.592B.586C.624D.6086、設(shè)有5個字符出現(xiàn)的頻度分別為1,2,3,4,5，則對應(yīng)的哈夫曼樹的帶權(quán)路徑長度為（）。A.34B.33C.35D.377、鏈接存儲的存儲結(jié)構(gòu)所占存儲空間：（）。A．分兩部分，一部分存放結(jié)點值，另一部分存放表示結(jié)點間關(guān)系的指針B．只有一部分，存放結(jié)點值第2頁C．只有一部分，存儲表示結(jié)點間關(guān)系的指針D．分兩部分，一部分存放結(jié)點值，另一部分存放結(jié)點所占單元數(shù)8、下述幾種排序方法中，要求內(nèi)存最大的是（）。A．插入排序B．快速排序C．歸并排序D．選擇排序9、二叉樹長短線性數(shù)據(jù)布局，關(guān)于它的存儲，以下哪個描述精確（）。A．它不克不及用按次存儲布局存儲B．按次存儲布局和鏈?zhǔn)酱鎯Σ季侄寄艽鎯．按次存儲布局和鏈?zhǔn)酱鎯Σ季侄疾豢瞬患袄肈．它不克不及用鏈?zhǔn)酱鎯Σ季执鎯?0、一組記實的樞紐字為{46,79,56,38,40,84}，利用快速排序的辦法，以第一個記實為基準(zhǔn)取得的一次劃分結(jié)果為()。A.{38,40,46,56,79,84}B.{40,38,46,79,56,84}C.{40,38,46,56,79,84}D.{40,38,46,84,56,79}11、若一個棧的入棧序列是1，2，3，…，n，其輸出序列為p1,p2,p3,…,pn,若p1=n，則pi為（）。A.iB.n=iC.n-i+1D.不確定12、若一組記實的排序碼為{46,79,56,38,40,84}，則利用堆排序的辦法建立的初始堆為（）。A.{79,46,56,38,40,84}B.{84,79,56,38,40,46}C.{84,79,56,46,40,38}D.{84,56,79,40,46,38}13、線性表Ｌ在什么情形下合用于利用鏈?zhǔn)讲季謱崿F(xiàn)（）。A．需常常修改Ｌ中的結(jié)點值B．需不竭對Ｌ舉行刪除插入C．Ｌ中含有大量的結(jié)點D．Ｌ中結(jié)點結(jié)構(gòu)復(fù)雜14、向一個有128個元素的按次表中插入一個新元素并保持原先按次穩(wěn)定，均勻要移動幾何個元素（）。A．8B．62C．63D．6415、深度優(yōu)先遍歷相似于二叉樹的（）。A.先序遍歷B.中序遍歷C.后序遍歷D.層次遍歷16、任何一個無向連通圖的最小天生樹（）。A.只有一棵B.一棵或多棵C.一定有多棵D.可能不存在第3頁17、有8個結(jié)點的無向圖最多有幾何條邊（）。A.14B.28C.56D.2818、折半查找有序表（4，6，10，12，20，30，50，70，88，100）。若查找表中元素58，則它將依次與表中哪些元素比較大小，查找結(jié)果是失?。ǎ?。A.20，70，30，50B.30，88，70，50C.20，50D.30，88，5019、鏈表適用于哪種查找（）。A.按次B.二分法C.按次，也能二分法D.隨機20、把一棵樹轉(zhuǎn)換為二叉樹后，這棵二叉樹具有什么樣的形態(tài)特征（）。A.是唯獨的B.有多種C.有多種，但根結(jié)點都沒有左孩子D.有多種，但根結(jié)點都沒有右孩子二、填空題(每空2分，共30分)1、快速排序的平均時間復(fù)雜度是，它在最壞情況下的時間復(fù)雜度是。（要求用大O表示法表示）2、一棵具有257個結(jié)點的完全二叉樹，它的深度為。3、已知一個采用空閑單元法的循環(huán)隊列容量為20，隊列的首、尾指針分別用f和r表示，f＝3，r＝18時隊列的長度為，f＝15，r＝7時隊列的長度為。4、三元素組表中的每個結(jié)點對應(yīng)于稀疏矩陣的一個非零元素，它包含有三個數(shù)據(jù)項，分別表示該元素的、和。5、如果一棵完全二叉樹具有500個結(jié)點，則此完全二叉樹有個葉子結(jié)點，有個度為2的結(jié)點，有個結(jié)點只要非空左子樹，有個結(jié)點只要非空右子樹。6、由3個結(jié)點所構(gòu)成的二叉樹有種形態(tài)。7、在對一組記實（54，38，96，23，15，72，60，45，83）舉行間接插入排序時，當(dāng)把第7個記實60插入到有序表時，為了尋覓插入位置至少需要比力次。8、稠密圖適合采用存儲結(jié)構(gòu)。第4頁三、綜合題(共60分)1、描述以下三個概念的區(qū)別：頭指針、頭結(jié)點、首元結(jié)點（第一個元素結(jié)點）。在單鏈表中設(shè)置頭結(jié)點的作用是什么？（10分）2、給定二叉樹的兩種遍歷序列，分別是：前序遍歷序列：D，A，C，E，B，H，F(xiàn)，G，I；中序遍歷序列：D，C，B，E，H，A，G，I，F(xiàn)，試畫出二叉樹，并給出后序遍歷序列。（10分）3、已知二維數(shù)組Am,m采用按行優(yōu)先順序存放，每個元素占K個存儲單元，并且第一個元素的存儲地址為Loc(a11)，請寫出求Loc(aij)的計算公式。如果采用列優(yōu)先順序存放呢？（10分）4、當(dāng)輸入為abc#時，寫出調(diào)用pr函數(shù)的輸出結(jié)果。（10分）voidpr(){charch;scanf(“%c”,&ch);if(ch!=‘#’)pr();printf(“%c”,ch);}5、請對下圖的無向帶權(quán)圖：（10分）（1）按普里姆算法求其最小生成樹；（從頂點a開始）（5分）（2）按克魯斯卡爾算法求其最小天生樹。（5分）要求寫出詳細過程6、已知一棵度為k的樹中有n1個度為1的結(jié)點，n26個度為6的結(jié)點，則該樹中有幾何個葉子結(jié)點，并證明。（10分）第1頁共4頁三峽大學(xué)2014年研究生入學(xué)考試試題(A卷)科目代碼：938科目稱號：數(shù)據(jù)布局（考生必須將答案寫在答題紙上，總分150分，考試時間180分鐘）一、選擇題(每題3分，共60分)1、線性表采用鏈?zhǔn)酱鎯r，結(jié)點的存儲地點（）。A.必須是不繼續(xù)的B.繼續(xù)與否都可C.必須是繼續(xù)的D.和頭結(jié)點的存儲地點相繼續(xù)2、已知指針q所指結(jié)點是指針p所指結(jié)點的直接前驅(qū)，若在*q與*p之間插入結(jié)點*s，則應(yīng)執(zhí)行（）操作。A.s->next=p->next;p->next=sB.q->next=s;s->next=pC.p->next=s->next;s->next=pD.p->next=s;s->next=q3、設(shè)有一個按次棧S,元素按S1,S2,S3,S4,S5,S6按次進棧，若6個元素的出棧按次為S2,S3,S4,S6,S5,S1,則按次棧的容量至少應(yīng)為（）。A.2B.3C.4D.54、設(shè)有兩個串p和q，求q在p中首次呈現(xiàn)的位置的運算稱作（）。A.毗連B.形式匹配C.求子串D.求串長5、設(shè)有一個二維數(shù)A[m][n]，假設(shè)A[0][0]寄存位置在544，A[5][5]寄存位置在624，每個元素占一個空間，A[2][2]在（）位置。A.592B.586C.576D.6086、設(shè)有5個字符呈現(xiàn)的頻度分別為2,7,5,4，則對應(yīng)的哈夫曼樹的帶權(quán)途徑長度為（）。A.34B.33C.35D.157、含n個頂點和e條邊的無向圖的鄰接矩陣中非零元素的個數(shù)為（）。A.eB.2eC.n2-eD.n2-2e第2頁8、長度為500的有序表采用折半查找時，查找成功最大比較次數(shù)為（）。A.8B.9C.10D.119、快速排序在下列哪種情況下最易發(fā)揮其長處（）。A.被排序的數(shù)據(jù)中含有多個不異排序碼B.被排序的數(shù)據(jù)已根本有序C.被排序的數(shù)據(jù)完全無序D.被排序的數(shù)據(jù)中的最大值和最小值相差差異10、下列樞紐字序列中，（）是堆。A.16,72,31,23,94,53B.94,23,31,72,16,53C.16,53,23,94，31,72D.16,23,53,31,94,7211、若已知一個棧的入棧序列是1，2，3，…，n，其輸出序列為p1,p2,p3,…,pn,若p1=n，則pi為（）。A.iB.n=iC.n-i+1D.不肯定12、一棵具有257個結(jié)點的完全二叉樹，它的深度為（）。。A.7B.8C.9D.1014、用毗鄰表透露表現(xiàn)圖舉行廣度優(yōu)先遍用時，平日是采用（）這類數(shù)據(jù)布局來實現(xiàn)算法的。A.棧B.隊列C.樹D.圖15、深度優(yōu)先遍歷相似于二叉樹的（）。A.先序遍歷B.中序遍歷C.后序遍歷D.層次遍歷16、有8個結(jié)點的無向圖最多有（）條邊。A.14B.28C.56D.11217、折半查找有序表（4，6，10，12，20，30，50，70，88，100）。若查找表中元素58，則它將順次與表中哪些元素比力大小，查找結(jié)果是失利。（）A.20，70，30，50B.30，88，70，50C.20，50D.30，88，50第3頁18、