浙江師范大學(xué)2008年計(jì)算機(jī)考研數(shù)據(jù)結(jié)構(gòu)試題匯總

浙江師范大學(xué)2008年計(jì)算機(jī)考研數(shù)據(jù)結(jié)構(gòu)試題數(shù)據(jù)結(jié)構(gòu)一、判斷題用√和×表示對(duì)和錯(cuò)（每小題1.5分，共15分）數(shù)據(jù)元素是數(shù)據(jù)的最小單位。（×）當(dāng)待排序記錄已經(jīng)從小到大排序或者已經(jīng)從大到小排序時(shí)，快速排序的執(zhí)行時(shí)間最省。（×）數(shù)組可看成線(xiàn)性結(jié)構(gòu)的一種推廣，因此與線(xiàn)性表一樣，可以對(duì)它進(jìn)行插入、刪除等操作。（×）在樹(shù)中，如果從結(jié)點(diǎn)K出發(fā)，存在兩條分別到達(dá)K’，K”的長(zhǎng)度相等的路徑，則結(jié)點(diǎn)K’和k”互為兄弟。（√）5.最佳兩叉排序樹(shù)的任何子樹(shù)都是最佳的。 （√）6.算法和程序沒(méi)有區(qū)別，所以在數(shù)據(jù)結(jié)構(gòu)中兩者是通用的。 （×）7.順序存儲(chǔ)方式只能用于存儲(chǔ)線(xiàn)性結(jié)構(gòu)。 （×）8.在線(xiàn)性表鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)中， 邏輯上相鄰的元素在物理位置上不一定相鄰。 （√）9.如果某種排序算法是不穩(wěn)定的，則該算法沒(méi)有實(shí)際意義。 （ ×）10.當(dāng)兩個(gè)字符出現(xiàn)的頻率相同時(shí)，則其哈夫曼編碼也相同。 （×）二、單項(xiàng)選擇題（每小題3分，共60分）某個(gè)向量第一元素的存儲(chǔ)地址為100，每個(gè)元素的長(zhǎng)度為2，則第五個(gè)元素的地址是______。A.110 B.108 C.100 D.120棧和隊(duì)列的共同特點(diǎn)是______。A.都是先進(jìn)后出 B.都是先進(jìn)先出 C.只允許在端點(diǎn)處插入和刪除元素 D.沒(méi)有共同點(diǎn)3.對(duì)線(xiàn)性表進(jìn)行二分查找時(shí)，要求線(xiàn)性表必須 ______。A.以順序方式存儲(chǔ) B.以鏈接方式存儲(chǔ) C.以順序方式存儲(chǔ)，且結(jié)點(diǎn)按關(guān)鍵字有序排序D.以鏈接方式存儲(chǔ)，且結(jié)點(diǎn)按關(guān)鍵字有序排序一組記錄的排序碼為（47、78、61、33、39、80），則利用堆排序的方法建立的初始堆為_(kāi)_____。A.78、47、61、33、39、80 B.80、78、61、33、39、47C.80、78、61、47、39、33 D.80、61、78、39、47、335.將一棵有 50個(gè)結(jié)點(diǎn)的完全二叉樹(shù)按層編號(hào)，則對(duì)編號(hào)為 25的結(jié)點(diǎn)x，該結(jié)點(diǎn)______。A.無(wú)左、右孩子 B.有左孩子，無(wú)右孩子 C.有右孩子，無(wú)左孩子 D.有左、右孩子用快速排序方法對(duì)包含有n個(gè)關(guān)鍵字的序列進(jìn)行排序，最壞情況下的時(shí)間復(fù)雜度為_(kāi)_____。A.O（n） B.O（log2n） C.O（nlog2n） D.O（n2）7.在最壞的情況下，查找成功時(shí)二叉排序樹(shù)的平均查找長(zhǎng)度 __（n+1）/2____。A.小于順序表的平均查找長(zhǎng)度 B.大于順序表的平均查找長(zhǎng)度 C.與順序表的平均查找長(zhǎng)度相同 D.無(wú)法與順序表的平均查找長(zhǎng)度比較對(duì)序列（22，86，19，49，12，30，65，35，18）進(jìn)行一趟排序后得到的結(jié)果如下：（18，12，19，22，49，30，65，35，86），則可以認(rèn)為使用的排序方法是 ______。A.選擇排序 B.冒泡排序 C.快速排序 D.插入排序在線(xiàn)性表的下列存儲(chǔ)結(jié)構(gòu)中，讀取元素花費(fèi)時(shí)間最少的是______。A.順序表 B.雙鏈表 C.循環(huán)鏈表 D.單鏈表具有100個(gè)結(jié)點(diǎn)的二叉樹(shù)中，若用二叉鏈表存儲(chǔ)，其指針域部分用來(lái)指向結(jié)點(diǎn)的左、右孩子，其余______個(gè)指針域?yàn)榭铡.50 B.99 C.100 D.101(二叉樹(shù)中除根結(jié)點(diǎn)外都有一個(gè)分支進(jìn)入，共 n-1個(gè)指針)從邏輯上可以把數(shù)據(jù)結(jié)構(gòu)劃分為_(kāi)_____。A.動(dòng)態(tài)結(jié)構(gòu)和靜態(tài)結(jié)構(gòu) B.緊湊結(jié)構(gòu)和非緊湊結(jié)構(gòu) C.線(xiàn)性結(jié)構(gòu)和非線(xiàn)性結(jié)構(gòu) D.內(nèi)部結(jié)構(gòu)和外部結(jié)構(gòu)以下數(shù)據(jù)結(jié)構(gòu)中屬于非線(xiàn)性結(jié)構(gòu)的是______。A.樹(shù) B.字符串 C.隊(duì)列 D.棧在單鏈表中，若*P節(jié)點(diǎn)不是最后節(jié)點(diǎn)，在*P之后插入節(jié)點(diǎn)*S，則其操作是______。A.s->next=p;p->next=s; B.s->next=p->next;p->next=s; C.s->next=p->next;p=s; D.p->next=s;s->next=p;棧是一種操作受限的數(shù)據(jù)結(jié)構(gòu)，其插入和刪除必須在______進(jìn)行。A.棧頂 B.棧底 C.任意位置 D.指定位置設(shè)T為一顆深度為6的二叉樹(shù)，則T擁有的最多結(jié)點(diǎn)數(shù)是______。A.64 B.63 C.32 D.31若用冒泡法對(duì)序列（18,14,6,27,8,12,16,52,10,26,47,29,41,24）進(jìn)行從小到大排序，共要進(jìn)行的比較次數(shù)為_(kāi)_____。A.33 B.45 C.70 D.91算法的時(shí)間復(fù)雜度取決于______。A.問(wèn)題的規(guī)模 B.待處理數(shù)據(jù)的初態(tài) C.計(jì)算機(jī)的配置 D.A和B對(duì)序列（22，86，19，49，12，30，65，35，18）進(jìn)行一趟排序后得到的結(jié)果如下：（18，12，19，22，49，30，65，35，86），則可以認(rèn)為使用的排序方法是 ______。A.選擇排序 B.希爾排序 C.快速排序 D.插入排序19.若用一個(gè)大小為6的數(shù)組來(lái)實(shí)現(xiàn)循環(huán)隊(duì)列，且當(dāng)前的rear和front的值分別為0和3，當(dāng)從隊(duì)列中刪除一個(gè)元素，再插入兩個(gè)元素后，rear和front的值分別為_(kāi)_____。A.1，5 B.2，4 C.4，2 D.5，1 （隊(duì)頭front刪除，隊(duì)尾 rear插入）20.對(duì)長(zhǎng)度為 3的順序表進(jìn)行搜索，若搜索第一、第二、第三個(gè)元素的概率分別為 1/2，1/3和1/6，則搜索任一元素的平均搜索長(zhǎng)度為 ______。A.5/3 B.2 C.7/3 D.4/3 （順序表查找是從最后一個(gè)元素順次向前比較。最后一個(gè)比較1次，最前邊比較 n次。ASL=nP1+(n-1)P2+?? +2Pn-1+Pn）三、算法閱讀選擇題（每小題3分，共30分）【算法填空 1】在畫(huà)有橫線(xiàn)的地方填寫(xiě)合適的內(nèi)容，并依據(jù)以下提供選擇的答案，回答（1）～（5）中的問(wèn)題。對(duì)順序存儲(chǔ)的有序表進(jìn)行二分查找的遞歸算法。intBinsch（ElemTypeA[],intlow,inthigh,KeyTypeK ）{if（low<=high）{intmid= （1）D（low+high）/2;if（K==A[mid].key ）returnmid;elseif（K<A[mid].key）return（2）C.Binsch（A,low,mid-1,K ）;elsereturn（3）B.Binsch（A,mid+1,high,K ）;}Elsereturn（4）A1～4問(wèn)題可供選擇的答案：A.1 B.Binsch（mid+1,high） C.Binsch（low,mid-1） D.（low+high）/25、試問(wèn)該遞歸算法的漸近時(shí)間復(fù)雜度是（ 5）。A.O（n）B.O（log2n）C.O（nlog2n）2）D.O（n【算法填空 2】在畫(huà)有橫線(xiàn)的地方填寫(xiě)合適的內(nèi)容， 并依據(jù)以下提供選擇的答案， 回答（6）～10）中的問(wèn)題。位數(shù)對(duì)調(diào)：輸入一個(gè)三位自然數(shù)，把這個(gè)數(shù)的百位與個(gè)位數(shù)對(duì)調(diào)，輸出對(duì)調(diào)后的數(shù)。例如：輸入3位自然數(shù)：234，輸出n=432。//輸入的數(shù)據(jù)為整數(shù)//ProgramThreebit#include<stdio.h>voidmain（）{intx,n,a,b,cprintf（"Input3bitnaturedata:"）scanf（"%d",&n）if（n>99&&n<1000）{a=（6） //求百位數(shù) n/100b=（7） //求十位數(shù) (n-a*100)/10c=（8） //求個(gè)位數(shù) n%10x=（9） //求新數(shù)X c*100+b*10+aprintf（"Number=%d/n",x）;}elseprintf（"Inputerror!/n"）;}6～9問(wèn)題可供選擇的答案如下：A.n/100 B.（n-a*100）/10 C.n%10 D.c*100+b*10+a10、試問(wèn)該算法的漸近時(shí)間復(fù)雜度是（ 10）。A.O（n） B.O（log2n） C.O（nlog2n） D.O（1）四、應(yīng)用題（每小題6分，共24分）給定二叉樹(shù)的中序遍歷結(jié)果為abc，請(qǐng)畫(huà)出能得到此中序遍歷結(jié)果的二叉樹(shù)的所有形態(tài)。對(duì)應(yīng)的幾種先根序： bac，acb,abc,cba,cab請(qǐng)畫(huà)出下面無(wú)向圖的鄰接矩陣和鄰接表。1000011101010111011101010111001123^12024^230134^34024^45123^已知序列{15,18,60,41,6,32,83,75,95}。請(qǐng)給出采用冒泡排序法對(duì)該序列作升序排序時(shí)的每一趟的結(jié)果。15,18,41,6,32,60,75,83,9515,18,6,32,41,60,75,8315,6,18,32,41,60,756,15,18,32,41,606,15,18,32,41intflg=1;//如果上一趟比較沒(méi)有交換，終止比較inti,j;For(i=0;i<n-1&&flg==1;i++){flg=0;for(j=0;j<n-1-i;j++){if(A[j]>A[j+1]){t=A[j];A[j]=A[j+1];A[j+1]=t;flg=1;}}}有一份電文中共使用五個(gè)字符：a、b、c、d、e,它們的出現(xiàn)頻率依次為8、14、10、4、18，請(qǐng)構(gòu)造相應(yīng)的哈夫曼樹(shù)（左子樹(shù)根結(jié)點(diǎn)的權(quán)小于等于右子樹(shù)根結(jié)點(diǎn)的權(quán)），求出每個(gè)字符的哈夫曼編碼。A:001 B:10 C:01 D:000 E:11WPL=3*(4+8)+2*(10+14+18)=3*12+2*42=36+84=122五、算法設(shè)計(jì)題（ 21分）1.以鄰接表為存儲(chǔ)結(jié)構(gòu)，寫(xiě)出連通圖的深度優(yōu)先搜索算法。（9分）//------------鄰接表結(jié)構(gòu)typedefstructArcNode{

------------------intintintstruct

adjvex;weight;*info;ArcNode

*nextarc;}ArcNode;typedefstructVNode{VertexType data;ArcNode *firstarc;}VNode,AdjList[MAX_VERTEX_NUM];typedef struct{AdjList vertices;int vexnum,arcnum;int kind;}ALGraph;Intvisited[MaxSize];深度優(yōu)先遍歷void dfs(ALGraph G,int v){ArcNode *p;cout<<v<<"visited[v]=1;

";p=G.vertices[v].firstarc;while(p!=NULL){if(!visited[p->adjvex])dfs(G,p->adjvex);p=p->nextarc;}return ;}void

dfs1(ALGraph

G){int i;cout<<"深度優(yōu)先遍歷 :"<<endl;for(i=0;i<G.vexnum;i++)visited[i]=0;for(i=0;i<G.vexnum;i++)if(visited[i]==0)dfs(G,i);}2.如下圖所示，設(shè)有兩個(gè)棧 s1和s2共亨同一數(shù)組存儲(chǔ)空間 stack［1m］，其中棧s1的棧底設(shè)在 stack［1］處，而棧 s2的棧底設(shè)在 stack［m］處，請(qǐng)編寫(xiě)棧 s1和s2的進(jìn)棧操作push（i,x）和退棧操作

pop（i），其中

i=1、2，分別表示棧

s1和

s2。要求：僅當(dāng)整個(gè)空間stack［1m］占滿(mǎn)時(shí)才產(chǎn)生上溢。

（12分）typedef

ElemTypeint;inttop[3];

//位置

0未用ElemTypestack[m+1];//位置0未用initStack(){top[1]=0;top[2