第一篇：數(shù)據(jù)結(jié)構(gòu)試卷及參考答案_10
數(shù)據(jù)結(jié)構(gòu)試卷
（十）一、選擇題(24分)1．下列程序段的時間復(fù)雜度為（）。
i=0，s=0； while(s (A)單向鏈表 (B)單向循環(huán)鏈表(C)雙向鏈表 (D)雙向循環(huán)鏈表 3．設(shè)指針q指向單鏈表中結(jié)點A，指針p指向單鏈表中結(jié)點A的后繼結(jié)點B，指針s指向被插入的結(jié)點X，則在結(jié)點A和結(jié)點B插入結(jié)點X的操作序列為（）。(A)s->next=p->next；p->next=-s；(B)q->next=s； s->next=p；(C)p->next=s->next；s->next=p；(D)p->next=s；s->next=q； 4．設(shè)輸入序列為1、2、3、4、5、6，則通過棧的作用后可以得到的輸出序列為（）。(A)5，3，4，6，1，2(B)3，2，5，6，4，1(C)3，1，2，5，4，6(D)1，5，4，6，2，3 5．設(shè)有一個10階的下三角矩陣A（包括對角線），按照從上到下、從左到右的順序存儲到連續(xù)的55個存儲單元中，每個數(shù)組元素占1個字節(jié)的存儲空間，則A[5][4]地址與A[0][0]的地址之差為（）。 (A)10(B)19(C)28(D)55 6．設(shè)一棵m叉樹中有N1個度數(shù)為1的結(jié)點，N2個度數(shù)為2的結(jié)點，……，Nm個度數(shù)為m的結(jié)點，則該樹中共有（）個葉子結(jié)點。 (A)?(i?1)Ni?1mi(B) ?Ni?1mi(C) ?Ni?2mi(D)1??(i?1)Ni?2mi 7.二叉排序樹中左子樹上所有結(jié)點的值均（）根結(jié)點的值。 (A)<(B)>(C)=(D)!= 8.設(shè)一組權(quán)值集合W=(15，3，14，2，6，9，16，17)，要求根據(jù)這些權(quán)值集合構(gòu)造一棵哈夫曼樹，則這棵哈夫曼樹的帶權(quán)路徑長度為（）。 (A)129(B)219(C)189(D)229 9.設(shè)有n個關(guān)鍵字具有相同的Hash函數(shù)值，則用線性探測法把這n個關(guān)鍵字映射到HASH表中需要做（）次線性探測。 (A)n2(B)n(n+1)(C)n(n+1)/2(D)n(n-1)/2 10.設(shè)某棵二叉樹中只有度數(shù)為0和度數(shù)為2的結(jié)點且度數(shù)為0的結(jié)點數(shù)為n，則這棵二叉中共有（）個結(jié)點。 (A)2n(B)n+l(C)2n-1(D)2n+l 11.設(shè)一組初始記錄關(guān)鍵字的長度為8，則最多經(jīng)過（）趟插入排序可以得到有序序列。 (A)6(B)7(C)8(D)9 12.設(shè)一組初始記錄關(guān)鍵字序列為(Q，H，C，Y，P，A，M，S，R，D，F(xiàn)，X)，則按字母升序的第一趟冒泡排序結(jié)束后的結(jié)果是（）。(A)F，H，C，D，P，A，M，Q，R，S，Y，X(B)P，A，C，S，Q，D，F(xiàn)，X，R，H，M，Y(C)A，D，C，R，F(xiàn)，Q，M，S，Y，P，H，X(D)H，C，Q，P，A，M，S，R，D，F(xiàn)，X，Y 二、填空題(48分，其中最后兩小題各6分)1.設(shè)需要對5個不同的記錄關(guān)鍵字進(jìn)行排序，則至少需要比較_____________次，至多需要比較_____________次。 2.快速排序算法的平均時間復(fù)雜度為____________，直接插入排序算法的平均時間復(fù)雜度為___________。 3.設(shè)二叉排序樹的高度為h，則在該樹中查找關(guān)鍵字key最多需要比較_________次。4.設(shè)在長度為20的有序表中進(jìn)行二分查找，則比較一次查找成功的結(jié)點數(shù)有_________個，比較兩次查找成功有結(jié)點數(shù)有_________個。 5.設(shè)一棵m叉樹脂的結(jié)點數(shù)為n，用多重鏈表表示其存儲結(jié)構(gòu)，則該樹中有_________個空指針域。 6.設(shè)指針變量p指向單鏈表中結(jié)點A，則刪除結(jié)點A的語句序列為： q=p->next；p->data=q->data；p->next=___________；feee(q)； 7.數(shù)據(jù)結(jié)構(gòu)從邏輯上劃分為三種基本類型：___________、__________和___________。8.設(shè)無向圖G中有n個頂點e條邊，則用鄰接矩陣作為圖的存儲結(jié)構(gòu)進(jìn)行深度優(yōu)先或廣度優(yōu)先遍歷時的時間復(fù)雜度為_________；用鄰接表作為圖的存儲結(jié)構(gòu)進(jìn)行深度優(yōu)先或廣度優(yōu)先遍歷的時間復(fù)雜度為_________。 9.設(shè)散列表的長度為8，散列函數(shù)H(k)=k %7，用線性探測法解決沖突，則根據(jù)一組初始關(guān)鍵字序列(8，15，16，22，30，32)構(gòu)造出的散列表的平均查找長度是________。10.設(shè)一組初始關(guān)鍵字序列為(38，65，97，76，13，27，10)，則第3趟冒泡排序結(jié)束后的結(jié)果為_____________________。 11.設(shè)一組初始關(guān)鍵字序列為(38，65，97，76，13，27，10)，則第3趟簡單選擇排序后的結(jié)果為______________________。 12.設(shè)有向圖G中的有向邊的集合E={<1，2>，<2，3>，<1，4>，<4，5>，<5，3>，<4，6>，<6，5>}，則該圖的一個拓?fù)湫蛄袨開________________________。 13.下面程序段的功能是建立二叉樹的算法，請在下劃線處填上正確的內(nèi)容。 typedefstruct node{int data;struct node*lchild;________________;}bitree;void createbitree(bitree *&bt){ scanf(“%c”,&ch);if(ch=='#')___________;else { bt=(bitree*)malloc(sizeof(bitree));bt->data=ch;________;createbitree(bt->rchild);} } 14.下面程序段的功能是利用從尾部插入的方法建立單鏈表的算法，請在下劃線處填上正確的內(nèi)容。 typedef struct node {int data;struct node *next;} lklist;void lklistcreate(_____________ *&head){ for(i=1;i<=n;i++){ p=(lklist *)malloc(sizeof(lklist));scanf(“%d”,&(p->data));p->next=0;if(i==1)head=q=p;else {q->next=p;____________;} } } 三、算法設(shè)計題(22分)1． 設(shè)計在鏈?zhǔn)酱鎯Y(jié)構(gòu)上合并排序的算法。2． 設(shè)計在二叉排序樹上查找結(jié)點X的算法。 3． 設(shè)關(guān)鍵字序列(k1，k2，…，kn-1)是堆，設(shè)計算法將關(guān)鍵字序列(k1，k2，…，kn-1，x)調(diào)整為堆。 數(shù)據(jù)結(jié)構(gòu)試卷 （十）參考答案 一、選擇題 1．A 2．D 7．A 8．D 3．B 9．D 4．B 10．C 5．B 11．B 6．D 12．D 二、填空題 1.4，10 2.O(nlog2n)，O(n2)3.n 4.1，2 5.6.7.8.n(m-1)+1 q->next 線性結(jié)構(gòu)，樹型結(jié)構(gòu)，圖型結(jié)構(gòu) O(n2)，O(n+e)9.8/3 10.(38，13，27，10，65，76，97)11.(10，13，27，76，65，97，38)12.124653 13.struct node *rchild，bt=0，createbitree(bt->lchild)14.lklist，q=p 三、算法設(shè)計題 1.設(shè)計在鏈?zhǔn)酱鎯Y(jié)構(gòu)上合并排序的算法。 void mergelklist(lklist *ha,lklist *hb,lklist *&hc){ lklist *s=hc=0; while(ha!=0 && hb!=0) if(ha->data else {if(s==0)hc=s=hb;else {s->next=hb;s=hb;};hb=hb->next;} if(ha==0)s->next=hb;else s->next=ha;} 2.設(shè)計在二叉排序樹上查找結(jié)點X的算法。 bitree *bstsearch1(bitree *t, int key){ bitree *p=t; while(p!=0)if(p->key==key)return(p);else if(p->key>key)p=p->lchild;else p=p->rchild; return(0);} 3.設(shè)關(guān)鍵字序列(k1，k2，…，kn-1)是堆，設(shè)計算法將關(guān)鍵字序列(k1，k2，…，kn-1，x)調(diào)整為堆。 void adjustheap(int r[ ],int n){ int j=n,i=j/2,temp=r[j-1]; while(i>=1)if(temp>=r[i-1])break;else{r[j-1]=r[i-1];j=i;i=i/2;} r[j-1]=temp;} 一、選擇題（每小題2分，共30分）1.數(shù)據(jù)結(jié)構(gòu)是（D）。 A．一種數(shù)據(jù)類型 B．?dāng)?shù)據(jù)的存儲結(jié)構(gòu) C．一組性質(zhì)相同的數(shù)據(jù)元素的集合 D．相互之間存在一種或多種特定關(guān)系的數(shù)據(jù)元素的集合 2．以下與數(shù)據(jù)的存儲結(jié)構(gòu)無關(guān)的術(shù)語是（D）。 A．鏈隊列 B.鏈表 C.順序表 D.棧 3．以下數(shù)據(jù)結(jié)構(gòu)中，（A）是非線性數(shù)據(jù)結(jié)構(gòu) A．樹 B．字符串 C．隊 D．棧 4．一個順序存儲線性表的第一個元素的存儲地址是90，每個元素的長度是2，則第6個元素的存儲地址是（B）。 A．98 B．100 C．102 D．106 5．在線性表的下列運算中，不改變數(shù)據(jù)元素之間結(jié)構(gòu)關(guān)系的運算是（D）。A．插入 B．刪除 C．排序 D．查找 6．線性表采用鏈?zhǔn)酱鎯r，其地址(D)。 A．必須是連續(xù)的 B．一定是不連續(xù)的 C．部分地址必須連續(xù) D．連續(xù)與否均可以 7．線性表是(A)。 A．一個有限序列，可以為空 B．一個有限序列，不可以為空 C．一個無限序列，可以為空 D．一個無限序列，不可以為空 8．若進(jìn)棧序列為1，2，3，4，5，6，且進(jìn)棧和出?？梢源┎暹M(jìn)行，則可能出現(xiàn)的出棧序列為（B）。 A．3，2，6，1，4，5 B．3，4，2，1，6，5 C．1，2，5，3，4，6 D．5，6，4，2，3，1 9.若一個棧的輸人序列是1，2，3，…，n，輸出序列的第一個元素是n，則第k個輸出元素是（C）。 A．k B．n-k-1 C．n-k+1 D．不確定 10.對于隊列操作數(shù)據(jù)的原則是（A）。 A.先進(jìn)先出 B.后進(jìn)先出 C.先進(jìn)后出 D.不分順序 11.棧和隊列的共同點是（C）。 A.都是先進(jìn)先出 B.都是先進(jìn)后出 C.只允許在端點處插入和刪除元素 D.沒有共同點 12．在一個鏈隊列中，假定front和rear分別為頭指針和尾指針，刪除一個結(jié)點的操作是（A）。 A．front=front->next B．rear=rear->next C．rear->next=front D．front->next＝rear 13.空串與空格串（B）。 A．相同 B．不相同 C．可能相同 D．無法確定 14.串與普通的線性表相比較，它的特殊性體現(xiàn)在（C）。A．順序的存儲結(jié)構(gòu) B．鏈接的存儲結(jié)構(gòu) C．?dāng)?shù)據(jù)元素是一個字符 D．?dāng)?shù)據(jù)元素可以任意 15.串的長度是指（B）。 A.串中所含不同字母的個數(shù) B.串中所含字符的個數(shù) C.串中所含不同字符的個數(shù) D.串中所含非空格字符的個數(shù) 二、填空題（每空2分，共20分） 1． 線性表、棧和隊列，串都是__線性_____結(jié)構(gòu)。2． 數(shù)據(jù)的基本單位是__數(shù)據(jù)元素_______________。 3． 當(dāng)線性表的元素總數(shù)基本穩(wěn)定，且很少進(jìn)行插入和刪除操作，但要求以最快的速度存取線性表中的元素時，應(yīng)采用_順序______存儲結(jié)構(gòu)。4． 已知具有n個元素的一維數(shù)組采用順序存儲結(jié)構(gòu)，每個元素占k個存儲單元，第一個元素的地址為Loc(a1)，那么，第i個元素的存儲地址Loc(ai)= Loc(a1)+(i-1)*k。5． 棧（stack）是限定在表尾進(jìn)行插人或刪除操作的線性表。在棧中，允許插人和刪除操作的一端稱為__棧頂________，而另一端稱為_棧底________。6． 一個循環(huán)隊列Q中，頭指針和尾指針分別為Q.front和Q.rear，且最大隊列長度為MaxQSize，則判斷隊空的條件為 Q.rear==Q.front,判斷隊滿的條件為(Q.rear+1)%MaxQSize==Q.front。隊列的長度為(.rear-Q.front+MaxQSize)%MaxQSize 7． 兩個串相等的充分必要條件是 兩個串的長度相等，且各個對應(yīng)位置的字符都相等。 三、程序填空題（每空3分，共30分） 1.在帶頭結(jié)點的單鏈表L中第i個數(shù)據(jù)元素之前插入數(shù)據(jù)元素e的C語言描述算法如下，其中L為鏈表頭結(jié)點指針。請?zhí)畛渌惴ㄖ袠?biāo)出的空白處，完成其功能。 typedef struct node {int data； struct node *next； }linknode,*link； int ListInsert_L(link &L, int i, int e){ Linknode *p；int j； p = L； j = 0； while(p && j < i-1){ p=p->next ； ++j； } // 尋找第i-1個結(jié)點 if(!p || j > i-1)return 0； s=(link)malloc(sizeof(linknode))；// 生成新結(jié)點s s->data = e； s->next=p->next ； p->next = s； // 插入L中 return 1； } 2.對順序棧的C語言描述算法如下，其中top為棧頂指針，請?zhí)畛渌惴ㄖ袠?biāo)出的空白處，插入元素e為新的棧頂元素。 #define STACK_INIT_SIZE 100 #define STACKINCREMENT 10 typedef struct{ char *base;char *top;int stacksize;}SqStack; int Push(SqStack &S, char e){ // if((s.top-s.base)>=s.stacksize)//棧滿，追加存儲空間 { S.base=(SElemType *)realloc(S.base,S.stacksize+STACKINCREMENT)*sizeof(SElemType))； if(!S.base)return 0； S.top = s.base+s.stacksize ； //修改棧頂指針 S.stacksize += STACKINCREMENT； } *s.top++=e ；//插入元素 return 1； } 3.對鏈隊列的C語言描述算法如下，請?zhí)畛渌惴ㄖ袠?biāo)出的空白處，刪除隊列Q 的隊頭元素并用e返回其值。typedef struct QNode{ QElemType data； struct QNode *next； }QNode, *QueuePtr； typedef struct { QueuePtr front； QueuePtr rear； }LinkQueue； int DeQueue(LinkQueue &Q, QElemType &e){ Linknode *p； if(Q.front==Q.rear)retrun 0；//隊列空，返回 p = Q.front-> next； e = p->data； Q.front-> next=p->next；//修改指針 if(Q.rear==p)Q.rear= Q.front ； //隊列只有一個元素的情況 free(p)；//釋放結(jié)點空間 return 1； } 三、算法設(shè)計與分析題（每題10分，共20分） 1、簡述下列算法實現(xiàn)的功能：（每題5分，共10分）（1）typedef struct LNode{ Char data; struct LNode *next;}LNode,*LinkList;LinkList Demo(LinkList &L){ // L 是無頭結(jié)點單鏈表 LNode *Q,*P;if(L&&L->next){ Q=L;L=L->next;P=L;while(P->next)P=P->next; P->next=Q;Q->next=NULL; } return L;}// Demo 答：將單鏈表的第一個結(jié)點刪除，放到鏈尾。 ——————————————————————————————————————————————————— （2）#define STACK_INIT_SIZE 100 #define STACKINCREMENT 10 typedef struct{ int *base;int *top;int stacksize; } Stack;void Demo1(Stack &S, int m){ Stack T;int i; InitStack(T);//初始化棧 while(!StackEmpty(S))//判斷棧是否為空 if((i=Pop(S))!=m)Push(T,i);//入棧操作 while(!StackEmpty(T)) { i=Pop(T);//出棧操作 Push(S,i); } } 答：刪除棧S中所有值為m的數(shù)據(jù)元素 2.有一個帶頭結(jié)點的單鏈表，頭指針為head，編寫一個算法計算所有數(shù)據(jù)域為X的結(jié)點的個數(shù)（不包括頭結(jié)點）。typedef struct node {int data;struct node *next;}linknode,*link;int sample(link head, int X){ int count=0;link p=head->next;while(p){if(p->data==X)count++;p=p->next;} return count;} 2014－2015學(xué)第一學(xué)期《數(shù)據(jù)結(jié)構(gòu)》 期中考試試卷 一、選擇題（每題2分，共20分） 1.計算機(jī)內(nèi)部數(shù)據(jù)處理的基本單位是（B）。 A.數(shù)據(jù) B.數(shù)據(jù)元素 C.數(shù)據(jù)項 D.數(shù)據(jù)庫 2.設(shè)語句x++的時間是單位時間，則以下語句的時間復(fù)雜度為（B）。 for(i=1;i<=n;i++)for(j=i;j<=n;j++)x++;A.O(1)B.O(n)C.O(n) D.O(n) 33.在一個長度為n的順序表中刪除第i個元素(0<=i<=n)時，需向前移動（A）個元素。 A．n-i B．n-i+l C．n-i-1 D．i 4.在一個單鏈表中，已知q結(jié)點是p結(jié)點的前趨結(jié)點，若在q和p之間插入s結(jié)點，則須執(zhí)行（B）。 A．s->next=p->next;p->next=s B．q->next=s;s->next=p C．p->next=s->next;s->next=p D．p->next=s;s->next=q 5.在一個具有n個單元的順序棧中，假定以地址低端（即0單元）作為棧底，以top作為棧頂指針，當(dāng)做出棧處理時，top變化為______。C A．top不變 B．top=0 C．top--D．top++ 6.在具有n個單元的順序存儲的循環(huán)隊列中，假定front和rear分別為隊頭指針和隊尾指針，則判斷隊滿的條件為________。D A．rear％n= = front B．（front+l）％n= = rear C．rear％n-1= = front D．(rear+l)％n= = front 7.兩個字符串相等的條件是（D）。 A.兩串的長度相等 B.兩串的長度相等，并且兩串包含的字符相同 C.兩串包含的字符相同 D.兩串的長度相等，并且對應(yīng)位置上的字符相同 8.數(shù)組A中，每個元素的長度為3個字節(jié)，行下標(biāo)i從1到8，列下標(biāo)j從1到10，從首地址SA開始連續(xù)存放在存儲器內(nèi)，該數(shù)組按行存放時，元素A[8][5]的起始地址為（C）。A.SA+141 B.SA+144 C.SA+222 D.SA+225 9.設(shè)有廣義表D=(a,b,D)，其長度為（B），深度為（A）。A.無窮大 B.3 C.2 D.5 10.假設(shè)在一棵二叉樹中，雙分支結(jié)點數(shù)為15，單分支結(jié)點數(shù)為30個，則葉子結(jié)點數(shù)為（B）個。 A.15 B.16 C.17 D.47 二、填空題（每空1分，共20分） 1.數(shù)據(jù)的邏輯結(jié)構(gòu)有四種基本形態(tài)，分別是________________、__________________、__________________和__________________。2.集合，線性，樹，圖 2.一個算法的效率可分為__________________效率和__________________效率。4.時間，空間 3.當(dāng)對一個線性表經(jīng)常進(jìn)行存取操作，而很少進(jìn)行插入和刪除操作時，則采用_______存儲結(jié)構(gòu)為宜。相反，當(dāng)經(jīng)常進(jìn)行的是插入和刪除操作時，則采用_______存儲結(jié)構(gòu)為宜。7．順 （第1頁，共3頁） 序，鏈接 4.對于一個具有n個結(jié)點的單鏈表，在已知的結(jié)點p后插入一個新結(jié)點的時間復(fù)雜度為______，在給定值為x的結(jié)點后插入一個新結(jié)點的時間復(fù)雜度為_______。12．O(1)，O(n)5.可以在線性表的______位置插入和刪除元素；對于棧只能在_______位置刪除元素；對于隊列只能在_______位置插入元素。9任何，棧頂，隊尾 6.設(shè)字符串S1= “ABCDEF”，S2= “PQRS”，則運算S=CONCAT（SUB（S1，2，LEN（S2）），SUB（S1，LEN（S2），2））后的串值為___________________。3.“BCDEDE” 7.一維數(shù)組的邏輯結(jié)構(gòu)是______________，存儲結(jié)構(gòu)是______________；對于二維或多維數(shù)組，分為______________和______________兩種不同的存儲方式。1.線性結(jié)構(gòu)，順序結(jié)構(gòu)，以行為主序，以列為主序 8.三維數(shù)組R[c1?d1,c2?d2,c3?d3]共含有______________個元素。（其中：c1≤d1,c2≤d2,c3≤d3）9.（d1-c1+1）×（d2-c2+1）×（d3-c3+1） 9.數(shù)組A[1?10，-2?6，2?8]以行優(yōu)先的順序存儲，設(shè)第一個元素的首地址是100，每個元素占3個存儲長度的存儲空間，則元素A[5，0，7]的存儲地址為______________。10.913 三、簡答題（每題6分，共18分）1.已知L是無表頭結(jié)點的單鏈表，且P結(jié)點既不是首元結(jié)點也不是尾元結(jié)點，試寫出合適的語句序列。(1)在P結(jié)點后插入S結(jié)點。(2)在表首插入S結(jié)點。(3)在表尾插入S結(jié)點。2已知L是帶表頭結(jié)點的非空單鏈表，且P結(jié)點既不是首元結(jié)點也不是尾元結(jié)點，試寫出合適的語句序列。(1)刪除P結(jié)點的直接后繼結(jié)點。(2)刪除P結(jié)點。（3）刪除尾元結(jié)點。3． LinkList mynote(LinkList L){//L是不帶頭結(jié)點的單鏈表的頭指針 if(L&&L->next){ q=L；L=L－>next；p=L； S1： while(p－>next)p=p－>next； S2： p－>next=q；q－>next=NULL； } return L； } 請回答下列問題：（1）說明語句S1的功能；（2）說明語句組S2的功能；（3）設(shè)鏈表表示的線性表為（a1,a2, ?,an）,寫出算法執(zhí)行后的返回值所表示的線性表。 該算法的功能是：將開始結(jié)點摘下鏈接到終端結(jié)點之后成為新的終端結(jié)點，而原來的第二個結(jié)點成為新的開始結(jié)點，返回新鏈表的頭指針。 四、算法設(shè)計題（每題14分，共42分）1.假設(shè)有一個循環(huán)鏈表的長度大于1，且表中既無頭結(jié)點也無頭指針，已知p為指向鏈表中某結(jié)點的指針，設(shè)計在鏈表中刪除p所指結(jié)點的前趨結(jié)點的算法。 解：可引入一個指針q，當(dāng)q->next=p時，說明此時q所指的結(jié)點為p所指結(jié)點的前趨結(jié)點，從而可得算法如下： void delete(LinkList *p){ //在鏈表中刪除p所指結(jié)點的前趨結(jié)點 LinkList *q,*t; q=p; while(q->next->next!=p)//q->next不是p的前趨結(jié)點 （第2頁，共3頁） q=q->next; t=q->next;//t指向要刪除結(jié)點 q->next=p;//刪除t結(jié)點 free(t);｝ 2.已知線性表的元素是無序的，且以帶頭結(jié)點的單鏈表作為存儲結(jié)構(gòu)。設(shè)計一個刪除表中所有值小于max但大于min的元素的算法。 2．算法描述如下： delete(LinkList *head, int max, int min){ LinkList *p,*q; q=head; p=head->next; while(p!=NULL) if((p->data<=min)||(p->data>=max)) { q=p; p=p->next; } else { q->next=p->next;free(p);p=q->next;} } 3.假設(shè)表達(dá)式有單字母變量和雙目四則運算符構(gòu)成。試寫一個算法，對一個通常書寫形式且書寫正確的表達(dá)式求值。 （第3頁，共3頁） 數(shù)據(jù)結(jié)構(gòu)試卷 （一）一、選擇題（20分） 1．組成數(shù)據(jù)的基本單位是（）。 (A)數(shù)據(jù)項(B)數(shù)據(jù)類型(C)數(shù)據(jù)元素(D)數(shù)據(jù)變量 2．設(shè)數(shù)據(jù)結(jié)構(gòu)A=(D，R)，其中D={1，2，3，4}，R={r}，r={<1，2>，<2，3>，<3，4>，<4，1>}，則數(shù)據(jù)結(jié)構(gòu)A是（）。 (A)線性結(jié)構(gòu)(B)樹型結(jié)構(gòu)(C)圖型結(jié)構(gòu)(D)集合 3．?dāng)?shù)組的邏輯結(jié)構(gòu)不同于下列（）的邏輯結(jié)構(gòu)。 (A)線性表(B)棧(C)隊列(D)樹 4．二叉樹中第i(i≥1)層上的結(jié)點數(shù)最多有（）個。 ii-1(A)2i(B)2(C)2(D)2i-1 5．設(shè)指針變量p指向單鏈表結(jié)點A，則刪除結(jié)點A的后繼結(jié)點B需要的操作為（）。 (A)p->next=p->next->next(B)p=p->next (C)p=p->next->next(D)p->next=p 6．設(shè)棧S和隊列Q的初始狀態(tài)為空，元素E1、E2、E3、E4、E5和E6依次通過棧S，一個元素出棧后即進(jìn)入隊列Q，若6個元素出列的順序為E2、E4、E3、E6、E5和E1，則棧S的容量至少應(yīng)該是（）。 (A)6(B)4(C)3(D)2 7．將10階對稱矩陣壓縮存儲到一維數(shù)組A中，則數(shù)組A的長度最少為（）。 (A)100(B)40(C)55(D)80 8．設(shè)結(jié)點A有3個兄弟結(jié)點且結(jié)點B為結(jié)點A的雙親結(jié)點，則結(jié)點B的度數(shù)數(shù)為（）。 (A)3(B)4(C)5(D)1 9．根據(jù)二叉樹的定義可知二叉樹共有（）種不同的形態(tài)。 (A)4(B)5(C)6(D)7 10.設(shè)有以下四種排序方法，則（）的空間復(fù)雜度最大。 (A)冒泡排序(B)快速排序(C)堆排序(D)希爾排序 二、填空題(30分)1.設(shè)順序循環(huán)隊列Q[0：m-1]的隊頭指針和隊尾指針分別為F和R，其中隊頭指針F指向當(dāng)前隊頭元素的前一個位置，隊尾指針R指向當(dāng)前隊尾元素所在的位置，則出隊列的語句為F =____________。 2.設(shè)線性表中有n個數(shù)據(jù)元素，則在順序存儲結(jié)構(gòu)上實現(xiàn)順序查找的平均時間復(fù)雜度為___________，在鏈?zhǔn)酱鎯Y(jié)構(gòu)上實現(xiàn)順序查找的平均時間復(fù)雜度為___________。3.設(shè)一棵二叉樹中有n個結(jié)點，則當(dāng)用二叉鏈表作為其存儲結(jié)構(gòu)時，該二叉鏈表中共有________個指針域，__________個空指針域。 4.設(shè)指針變量p指向單鏈表中結(jié)點A，指針變量s指向被插入的結(jié)點B，則在結(jié)點A的后面插入結(jié)點B的操作序列為______________________________________。 5.設(shè)無向圖G中有n個頂點和e條邊，則其對應(yīng)的鄰接表中有_________個表頭結(jié)點和_________個表結(jié)點。 6.設(shè)無向圖G中有n個頂點e條邊，所有頂點的度數(shù)之和為m，則e和m有______關(guān)系。7.設(shè)一棵二叉樹的前序遍歷序列和中序遍歷序列均為ABC，則該二叉樹的后序遍歷序列為__________。 8.設(shè)一棵完全二叉樹中有21個結(jié)點，如果按照從上到下、從左到右的順序從1開始順序編號，則編號為8的雙親結(jié)點的編號是___________，編號為8的左孩子結(jié)點的編號是_____________。 9.下列程序段的功能實現(xiàn)子串t在主串s中位置的算法，要求在下劃線處填上正確語句。 int index(char s[ ], char t[ ]){ i=j=0;while(i 三、應(yīng)用題（30分） 1．設(shè)完全二叉樹的順序存儲結(jié)構(gòu)中存儲數(shù)據(jù)ABCDE，要求給出該二叉樹的鏈?zhǔn)酱鎯Y(jié)構(gòu)并給出該二叉樹的前序、中序和后序遍歷序列。 2．設(shè)給定一個權(quán)值集合W=(3，5，7，9，11)，要求根據(jù)給定的權(quán)值集合構(gòu)造一棵哈夫曼樹并計算哈夫曼樹的帶權(quán)路徑長度WPL。 3．設(shè)一組初始記錄關(guān)鍵字序列為(19，21，16，5，18，23)，要求給出以19為基準(zhǔn)的一趟快速排序結(jié)果以及第2趟直接選擇排序后的結(jié)果。 4．設(shè)一組初始記錄關(guān)鍵字集合為(25，10，8，27，32，68)，散列表的長度為8，散列函數(shù)H(k)=k mod 7，要求分別用線性探測和鏈地址法作為解決沖突的方法設(shè)計哈希表。5．設(shè)無向圖G（所右圖所示），要求給出該圖的深度優(yōu)先和廣度優(yōu)先遍歷的序列并給出該圖的最小生成樹。 四、算法設(shè)計題(20分)1.設(shè)計判斷單鏈表中結(jié)點是否關(guān)于中心對稱算法。2.設(shè)計在鏈?zhǔn)酱鎯Y(jié)構(gòu)上建立一棵二叉樹的算法。3.設(shè)計判斷一棵二叉樹是否是二叉排序樹的算法。 數(shù)據(jù)結(jié)構(gòu)試卷 （一）參考答案 一、選擇題 1.C 2.C 3.D 4.C 5.A 6.C 7.C 8.B 9.B 10.B 二、填空題 1.(F+1)% m 2.O(n)，O(n)3.2n，n+1 4.s->next=p->next;s->next=s 5.n, 2e 6.m=2e 7.CBA 8.4，16 9.i-j+1，0 10.n-1 三、應(yīng)用題 1.鏈?zhǔn)酱鎯Y(jié)構(gòu)略，前序ABDEC，中序DBEAC，后序DEBCA。2.哈夫曼樹略，WPL=78 3.(18,5,16,19,21,23)，(5，16，21，19，18，23) h0h1??8h2012345674.線性探測： 鏈地址法：h3??10 ?8?1025322768h4??25??32h5??68h6??275.深度：125364，廣度：123456，最小生成樹T的邊集為E={(1，4)，(1，3)，(3，5)，(5，6)，(5,6)} 四、算法設(shè)計題 1.設(shè)計判斷單鏈表中結(jié)點是否關(guān)于中心對稱算法。 typedef struct {int s[100];int top;} sqstack;int lklistsymmetry(lklist *head){ sqstack stack;stack.top=-1;lklist *p; for(p=head;p!=0;p=p->next){stack.top++;stack.s[stack.top]=p->data;} for(p=head;p!=0;p=p->next)if(p->data==stack.s[stack.top])stack.top=stack.top-1;else return(0); return(1);} 2.設(shè)計在鏈?zhǔn)酱鎯Y(jié)構(gòu)上建立一棵二叉樹的算法。 typedef char datatype;typedef struct node {datatype data;struct node *lchild,*rchild;} bitree;void createbitree(bitree *&bt){ char ch;scanf(“%c”,&ch); if(ch=='#'){bt=0;return;} bt=(bitree*)malloc(sizeof(bitree));bt->data=ch;createbitree(bt->lchild);createbitree(bt->rchild);} 3.設(shè)計判斷一棵二叉樹是否是二叉排序樹的算法。 int minnum=-32768,flag=1;typedef struct node{int key;struct node *lchild,*rchild;}bitree;void inorder(bitree *bt){ if(bt!=0) {inorder(bt->lchild);if(minnum>bt->key)flag=0;minnum=bt->key;inorder(bt->rchild);} } 《數(shù)據(jù)結(jié)構(gòu)》自考復(fù)習(xí)思考試題 一、單項選擇題(本大題共15小題，每小題2分，共30分)在每小題列出的四個備選項中只有一個是符合題目要求的，請將其代碼填寫在題后的括號內(nèi)。錯選、多選或未選均無分。 1.若將數(shù)據(jù)結(jié)構(gòu)形式定義為二元組(K，R)，其中K是數(shù)據(jù)元素的有限集合，則R是K上（） A.操作的有限集合B.映象的有限集合 C.類型的有限集合D.關(guān)系的有限集合 2.在長度為n的順序表中刪除第i個元素(1≤i≤n)時，元素移動的次數(shù)為（）A.n-i+1 B.i C.i+1 D.n-i 3.若不帶頭結(jié)點的單鏈表的頭指針為head，則該鏈表為空的判定條件是（）A.head==NULL B.head->next==NULL C.head!=NULL D.head->next==head 4.引起循環(huán)隊列隊頭位置發(fā)生變化的操作是（）A.出隊 B.入隊 C.取隊頭元素 D.取隊尾元素 5.若進(jìn)棧序列為1，2，3，4，5，6，且進(jìn)棧和出棧可以穿插進(jìn)行，則不可能出現(xiàn)的出棧序列是（）A.2，4，3，1，5，6 B.3，2，4，1，6，5 C.4，3，2，1，5，6 D.2，3，5，1，6，4 6.字符串通常采用的兩種存儲方式是（）A.散列存儲和索引存儲 B.索引存儲和鏈?zhǔn)酱鎯?C.順序存儲和鏈?zhǔn)酱鎯?/p> D.散列存儲和順序存儲 7.設(shè)主串長為n，模式串長為m(m≤n)，則在匹配失敗情況下，樸素匹配算法進(jìn)行的無效位移次數(shù)為（）A.m B.n-m C.n-m+1 D.n 8.二維數(shù)組A［12］［18］采用列優(yōu)先的存儲方法，若每個元素各占3個存儲單元，且第1個元素的地址為150，則元素A［9］［7］的地址為（）A.429 B.432 C.435 D.438 9.對廣義表L=((a,b),(c,d),(e,f))執(zhí)行操作tail(tail(L))的結(jié)果是（）A.(e,f) B.((e,f))C.(f) D.()10.下列圖示的順序存儲結(jié)構(gòu)表示的二叉樹是（）11.n個頂點的強(qiáng)連通圖中至少含有（）A.n-1條有向邊 B.n條有向邊 C.n(n-1)/2條有向邊 D.n(n-1)條有向邊 12.對關(guān)鍵字序列(56，23，78，92，88，67，19，34)進(jìn)行增量為3的一趟希爾排序的結(jié)果為（）A.(19，23，56，34，78，67，88，92) B.(23，56，78，66，88，92，19，34)C.(19，23，34，56，67，78，88，92) D.(19，23，67，56，34，78，92，88)13.若在9階B-樹中插入關(guān)鍵字引起結(jié)點分裂，則該結(jié)點在插入前含有的關(guān)鍵字個數(shù)為（） A.4 B.5 C.8 D.9 14.由同一關(guān)鍵字集合構(gòu)造的各棵二叉排序樹（）A.其形態(tài)不一定相同，但平均查找長度相同 B.其形態(tài)不一定相同，平均查找長度也不一定相同 C.其形態(tài)均相同，但平均查找長度不一定相同 D.其形態(tài)均相同，平均查找長度也都相同 15.ISAM文件和VSAM文件的區(qū)別之一是（）A.前者是索引順序文件，后者是索引非順序文件 B.前者只能進(jìn)行順序存取，后者只能進(jìn)行隨機(jī)存取 C.前者建立靜態(tài)索引結(jié)構(gòu)，后者建立動態(tài)索引結(jié)構(gòu) D.前者的存儲介質(zhì)是磁盤，后者的存儲介質(zhì)不是磁盤 二、填空題(本大題共10小題，每空2分，共20分)16.數(shù)據(jù)的邏輯結(jié)構(gòu)在計算機(jī)存儲器內(nèi)的表示，稱為數(shù)據(jù)的____________。17.刪除雙向循環(huán)鏈表中*p的前驅(qū)結(jié)點(存在)應(yīng)執(zhí)行的語句是____________。18.棧下溢是指在____________時進(jìn)行出棧操作。 19.已知substr(s,i,len)函數(shù)的功能是返回串s中第i個字符開始長度為len的子串，strlen(s)函數(shù)的功能是返回串s的長度。若s=″ABCDEFGHIJK″,t=″ABCD″,執(zhí)行運算substr(s,strlen(t), strlen(t))后的返回值為____________。 20.去除廣義表LS=(a1,a2,a3,??，an)中第1個元素，由其余元素構(gòu)成的廣義表稱為LS的____________。 21.已知完全二叉樹T的第5層只有7個結(jié)點，則該樹共有____________個葉子結(jié)點。22.在有向圖中，以頂點v為終點的邊的數(shù)目稱為v的____________。 23.當(dāng)關(guān)鍵字的取值范圍是實數(shù)集合時，無法進(jìn)行箱排序和____________排序。24.產(chǎn)生沖突現(xiàn)象的兩個關(guān)鍵字稱為該散列函數(shù)的____________。 25.假設(shè)散列文件中一個桶能存放m個記錄，則桶“溢出”的含義是，當(dāng)需要插入新的記錄時，該桶中____________。 三、解答題(本大題共4小題，每小題5分，共20分)26.假設(shè)以數(shù)組seqn［m］存放循環(huán)隊列的元素，設(shè)變量rear和quelen分別指示循環(huán)隊列中隊尾元素的位置和元素的個數(shù)。(1)寫出隊滿的條件表達(dá)式；(2)寫出隊空的條件表達(dá)式； (3)設(shè)m=40,rear=13,quelen=19,求隊頭元素的位置；(4)寫出一般情況下隊頭元素位置的表達(dá)式。 27.已知一棵二叉樹的中序序列為ABCDEFG，層序序列為BAFEGCD，請畫出該二叉樹。28.畫出下圖所示有向圖的所有強(qiáng)連通分量。 29.對7個關(guān)鍵字進(jìn)行快速排序，在最好的情況下僅需進(jìn)行10次關(guān)鍵字的比較。(1)假設(shè)關(guān)鍵字集合為{1,2,3,4,5,6,7}，試舉出能達(dá)到上述結(jié)果的初始關(guān)鍵字序列；(2)對所舉序列進(jìn)行快速排序，寫出排序過程。 四、算法閱讀題(本大題共4小題，每小題5分，共20分)30.閱讀下列算法，并回答問題：(1)設(shè)順序表L=(3,7,11,14,20,51)，寫出執(zhí)行f30(&L,15)之后的L；(2)設(shè)順序表L=(4,7,10,14,20,51)，寫出執(zhí)行f30(&L,10)之后的L；(3)簡述算法的功能。 void f30(SeqList*L, DataType x){ int i =0, j; while(i if(i for(j=i+1;j L->data［j-1］=L->data［j］; L->length--; } else { for(j=L->length;j>i;j--) L->data［j］=L->data［j-1］; L->data［i］=x; L->length++; } } 31.已知圖的鄰接表表示的形式說明如下： #define MaxNum //圖的最大頂點數(shù) typedef struct node { int adjvex; //鄰接點域 struct node *next; //鏈指針域 } EdgeNode; //邊表結(jié)點結(jié)構(gòu)描述 typedef struct { char vertex; //頂點域 EdgeNode *firstedge; //邊表頭指針 } VertexNode; //頂點表結(jié)點結(jié)構(gòu)描述 typedef struct { VertexNode adjlist［MaxNum］; //鄰接表 int n, e; //圖中當(dāng)前的頂點數(shù)和邊數(shù) } ALGraph; //鄰接表結(jié)構(gòu)描述 下列算法輸出圖G的深度優(yōu)先生成樹(或森林)的邊。閱讀算法，并在空缺處填入合適的內(nèi)容，使其成為一個完整的算法。 typedef enum {FALSE, TRUE} Boolean;Boolean visited［MaxNum］;void DFSForest(ALGraph *G){ int i; for(i=0;i (1) ; for(i=0;i EdgeNode *p; visited［i］=TRUE; p=G->adjlist［i］.firstedge; while(p!=NULL){ if(!visited［p->adjvex］){ printf(″<%c,%c>″,G->adjlist［i］.vertex，G->adjlist［p->adjvex］.vertex); (2) ; } (3) ; } } 32.閱讀下列算法，并回答問題： (1)假設(shè)數(shù)組L［8］={3,0,5,1,6,4,2,7}，寫出執(zhí)行函數(shù)調(diào)用f32(L，8)后的L；(2)寫出上述函數(shù)調(diào)用過程中進(jìn)行元素交換操作的總次數(shù)。void f32(int R［］,int n){ int i,t; for(i=0;i while(R［i］!=i){ t=R［R［i］］; R［R［i］］=R［i］; R［i］=t; } } 33.已知帶頭結(jié)點的單鏈表中的關(guān)鍵字為整數(shù)，為提高查找效率，需將它改建為采用拉鏈法處理沖突的散列表。設(shè)散列表的長度為m，散列函數(shù)為Hash(key)=key%m。鏈表的結(jié)點結(jié)構(gòu)為：。請在空缺處填入適當(dāng)內(nèi)容，使其成為一個完整算法。void f33(LinkList L, LinkList H［］, int m){//由帶頭結(jié)點的單鏈表L生成散列表H，散列表生成之后原鏈表不再存在 int i,j; LinkList p,q; for(i=0;i H［i］= (1) ; p=L->next; while(p) { q=p->next; j=p->key%m; (2) ; H［j］=p; (3) ; } free(L); } 五、算法設(shè)計題(本大題10分)34.假設(shè)以帶雙親指針的二叉鏈表作為二叉樹的存儲結(jié)構(gòu)，其結(jié)點結(jié)構(gòu)的類型說明如下所示： typedef char DataType;typedef struct node { DataType data; struct node *lchild, *rchild; //左右孩子指針 struct node *parent; //指向雙親的指針 } BinTNode;typedef BinTNode *BinTree;若px為指向非空二叉樹中某個結(jié)點的指針，可借助該結(jié)構(gòu)求得px所指結(jié)點在二叉樹的中序序列中的后繼。 (1)就后繼的不同情況，簡要敘述實現(xiàn)求后繼操作的方法； (2)編寫算法求px所指結(jié)點的中序序列后繼，并在算法語句中加注注釋。數(shù)據(jù)結(jié)構(gòu)標(biāo)準(zhǔn)答案 一、單項選擇題 1.(B)2.(D)3.(A)4.(A)5.(D)6.(C)7.(C)8.(A)9.(B)10.(A)11.(B)12.(D)13.(C)14.(B)15.(C) 二、填空題(本大題共10小題，每空2分，共20分)16.存儲結(jié)構(gòu) 17.q = p->pre;q->pre->next = p;p->pre = q->pre;free(q);18.棧空 19.“DEFG” //注意雙引號不能少 20.表尾 21.２^(I-2)+M/2 葉子結(jié)點． 22.入度 23.基數(shù) 24.同義詞 25.已有m個同義詞記錄 三、解答題(本大題共4小題，每小題5分，共20分)26.(1)quelen == m(2)quelen == 0(3)(13quelen + m)% m 27.B / A F / E G / C D 28.3個: a、bce、dfg 29.我們知道，對n個關(guān)鍵自序列進(jìn)行一趟快速排序，要進(jìn)行n-1次比較，也就是基準(zhǔn)和其他n-1個關(guān)鍵字比較。 這里要求10次，而71)= 10，這就要求2趟快速排序后，算法結(jié)束。所以，列舉出來的序列，要求在做partition的時候，正好將序列平分(1)4 1 3 2 6 5 7 或 4 1 3 7 6 5 2 或 4 5 3 7 6 1 2 或 4 1 3 5 6 2 7.......(2)自己列吧 :) 四、算法閱讀題(本大題共4小題，每小題5分，共20分)30.(1)L=(3,7,11,14,15,20,51)(2)L=(4,7,14,20,51)(3)在順序表L中查找數(shù)x, 找到，則刪除x，沒找到，則在適當(dāng)?shù)奈恢貌迦離，插入后，L依然有序.31.(1)FALSE //初始化為未訪問 (2)DSFTree(G, p->adjvex);//從相鄰結(jié)點往下繼續(xù)深度搜索(3)p = p->next;//下一個未訪問的相鄰結(jié)點 32.(1)L = { 0, 1, 2, 3, 4, 5, 6, 7 };(2)5次 33.(1)NULL //初始化 (2)p->next = H[ j ] //和下面一句完成頭插法(3)p = q; //繼續(xù)遍歷L 五、算法設(shè)計題(本大題10分)34.1) a)*px 有右孩子，則其右孩子為其中序序列中的后繼 b)*px 無右孩子，從*px開始回溯其祖先結(jié)點，找到第1個身份為左孩子的結(jié)點，找到，則該結(jié)點的父結(jié)點為*px的中序序列中的后繼。找不到，則無后繼。2)BinTNode * fintNext(BinTNode * px){ if(px-> rchild)return px->rchild;//*px 有右孩子 BinTNode *q, *qp; q = px;while(qp = q->parent){ //未回溯到根結(jié)點 if(qp->lchild == q)return qp;//找到1)b)所述結(jié)點 q = qp;//往上回溯 } return NULL;//未找到 }第二篇：數(shù)據(jù)結(jié)構(gòu)期中試卷及答案
第三篇：數(shù)據(jù)結(jié)構(gòu)期中考試試卷答案
第四篇：數(shù)據(jù)結(jié)構(gòu)試卷(一)及答案
第五篇：數(shù)據(jù)結(jié)構(gòu)試題及答案10
點擊咨詢 