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

pop（i），其中

i=1、2，分別表示棧

s1和

s2。要求：僅當整個空間stack［1m］占滿時才產生上溢。

（12分）typedef

ElemTypeint;inttop[3];

//位置

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