第一篇：數據結構試題大題編程及參考答案
數據結構考試題參考答案
1、設順序表L中的數據元素遞增有序。試寫一算法，將數據元素x插入到順序表L的適當位置，以保持該表的有序性。
解：存儲結構為：
typedef struct
SeqList { DataType *data;
int MaxLen;
int len;}SeqList;算法如下：
void insertLx(SeqList &L, DataType x){ if(L.len==L.maxlen)return;int i=L.len-1;while(i>=0 && x 2、試寫一個算法，在帶頭結點的單鏈表L的元素x前插入一個結點y。解：存儲結構如下： typedef struct Lnode {ElemType data;struct Lnode *next;}Lnode, *LinkList;算法如下： void insert_y_before_x(LinkList L, ElemType x, ElemType y){ Lnode *q, *p=L; while(p->next && p->next->data!=x)p=p->next;//找x的前驅結點p;if(!p->next)return;// 若不存在結點x，則返回； q=new Lnode;q->data=y;q->next=p->next;p->next=q;} 3、試寫一個算法，統計帶頭指針的單鏈表L的元素個數。解：存儲結構如下： typedef struct Lnode {ElemType data;struct Lnode *next;}Lnode, *LinkList;算法如下： int length(LinkList L){ int len=0;Lnode *p=L;while(p){ len++;p=p->next;} return len;} 注：如果單鏈表是帶頭結點的，則算法如下： int length(LinkList L){ int len=0;Lnode *p=L->next;;while(p){ len++;p=p->next;} return len;} 4、試寫一個算法，在帶頭結點的單鏈表L的第k個結點后插入一個結點x。解： 存儲結構如下： typedef struct Lnode {ElemType data;struct Lnode *next;}Lnode, *LinkList;算法如下： void insert_after_k(LinkList L, int k, ElemType x){ if(k<0)return;Lnode *q, *p=L;int i=0;while(p && i q=new Lnode;q->data=x;q->next=p->next;p->next=q;} 注：如果是在L的第k個結點前插入一個結點，則找第k-1個結點p，然后插入。５、試寫一個算法，在帶頭結點的單鏈表Ｌ中刪除所有的數據元素為x的結點。解： 存儲結構如下： typedef struct Lnode {ElemType data;struct Lnode *next;}Lnode, *LinkList;算法如下： void Delete_all_x(LinkList L, Elemtype x){ Lnode *p, *q;p=L;while(p){ if(p->next && p->next->data==x){q=p->next;p->next=q->next;delete q;} else p=p->next;} } 注意：要刪除所有的值為x的結點。６、假設一個單循環鏈表Ｌ的數據域為整型，設計一個算法，求該表中所有結點的數據之和。解： 存儲結構如下： typedef struct Lnode {ElemType data;struct Lnode *next;}Lnode, *LinkList; 假設Ｌ帶頭結點，且Ｌ指向頭結點，則算法如下： int sum_Of_Data(LinkList L){ int s=0;Lnode *p=L->next;while(p!=L){s+=p->data;p=p->next;} return s;} 假設Ｌ不帶頭結點，且Ｌ指向循環鏈表中任何一個結點，則算法如下： int sum_of_data(LinkList L){ int s=0;Lnode *p=L;if(L){ s+=p->data;p=p->next;while(p!=L){ s+=p->data;p=p->next;} } return s;} 注：以上兩種情形，只要給出其中一種情形的解即可。 ７、假設二叉樹用二叉鏈表存儲，設計一個算法，求二叉樹的結點個數。解：存儲結構如下： typedef struct bitnode {ElemType data;struct bitnode *lchild, *rchild;}bitnode, *bitree;算法如下： int nodes(bitree T){ if(!T)return 0;else return(1+nodes(T->lchild)+nodes(T->rchild));} ８、寫一個算法，建立二叉樹的二叉鏈表。解：存儲結構如下： typedef char ElemType;typedef struct bitnode {ElemType data;struct bitnode *lchild, *rchild;}bitnode, *bitree;算法如下： void creat_bitree(bitree &T){ //按擴展的先序序列輸入結點，輸入‘＃’表示空。ElemType ch; cin>>ch;if(ch==’#’)T=0;else { T=new bitnode;T->data=ch;creat_bitree(T->lchuild);creat_bitree(T->rchild);} } 或者寫成以下算法： bitree creat_bitree(void){ //按擴展的先序序列輸入結點，輸入‘＃’表示空。bitree T;ElemType ch; cin>>ch;if(ch==’#’)T=0;else { T=new bitnode;T->data=ch;creat_bitree(T->lchuild);creat_bitree(T->rchild);} return T;} 9、假設一棵二叉樹的先序序列為EBADCFHGIKJ，中序序列為ABCDEFGHIJK，請畫出該二叉樹，并寫出后序序列。解：該二叉樹如下： 后序序列為：ACDBGJKIHFE。 10、假設一棵二叉樹的層次序列為ABCDEFGHIJ，中序序列為DBGEHJACIF，請畫出該二叉樹，并寫出其先序序列和后序序列。解：該二叉樹如下： 先序序列為：ABDEGHJCFI； 后序序列為：DGJHEBIFCA。 11、編寫一個遞歸算法，將用二叉鏈表表示的二叉樹的所有結點的左、右子樹交換。解：存儲結構如下： typedef char ElemType;typedef struct bitnode {ElemType data;struct bitnode *lchild, *rchild;}bitnode, *bitree;算法如下： void exchange(bitree &T){if(!T)return;bitree temp;temp=T->lchild;T->lchild=T->rchild;T->rchild=temp;exchange(T->lchild);exchange(T->rchild);} 12、試寫出二叉鏈表表示的二叉樹的先序遍歷的非遞歸算法。解：存儲結構如下： typedef char ElemType;typedef struct bitnode {ElemType data;struct bitnode *lchild, *rchild;}bitnode, *bitree;算法如下： void preorder(bitree T){ //先序遍歷，當前結點入棧。#define MaxNum 20 bitree stack[MaxNum];int top=0;//指向棧頂的下一位置。bitnode *p;p=T;while(p || top>0){while(p){cout< data;stack[top++]=p;p=p->lchild;} if(top>0){ p=stack[--top];p=p->rchild;} } cout< 數據結構試卷 （二）一、選擇題(24分)1．下面關于線性表的敘述錯誤的是（）。 (A)線性表采用順序存儲必須占用一片連續的存儲空間 (B)線性表采用鏈式存儲不必占用一片連續的存儲空間(C)線性表采用鏈式存儲便于插入和刪除操作的實現(D)線性表采用順序存儲便于插入和刪除操作的實現 2．設哈夫曼樹中的葉子結點總數為m，若用二叉鏈表作為存儲結構，則該哈夫曼樹中總共有（）個空指針域。 (A)2m-1(B)2m(C)2m+1(D)4m 3．設順序循環隊列Q[0：M-1]的頭指針和尾指針分別為F和R，頭指針F總是指向隊頭元素的前一位置，尾指針R總是指向隊尾元素的當前位置，則該循環隊列中的元素個數為（）。 (A)R-F(B)F-R(C)(R-F+M)％M(D)(F-R+M)％M 4．設某棵二叉樹的中序遍歷序列為ABCD，前序遍歷序列為CABD，則后序遍歷該二叉樹得到序列為（）。 (A)BADC(B)BCDA(C)CDAB(D)CBDA 5．設某完全無向圖中有n個頂點，則該完全無向圖中有（）條邊。 (A)n(n-1)/2(B)n(n-1)(C)n 2(D)n2-1 6．設某棵二叉樹中有2000個結點，則該二叉樹的最小高度為（）。 (A)9(B)10(C)11(D)12 7．設某有向圖中有n個頂點，則該有向圖對應的鄰接表中有（）個表頭結點。 (A)n-1(B)n(C)n+1(D)2n-1 8．設一組初始記錄關鍵字序列(5，2，6，3，8)，以第一個記錄關鍵字5為基準進行一趟快速排序的結果為（）。 (A)2，3，5，8，6(B)3，2，5，8，6(C)3，2，5，6，8(D)2，3，6，5，8 二、填空題(24分)1.1.為了能有效地應用HASH查找技術，必須解決的兩個問題是____________________和__________________________。 2.2.下面程序段的功能實現數據x進棧，要求在下劃線處填上正確的語句。 typedef struct {int s[100];int top;} sqstack;void push(sqstack &stack,int x){ if(stack.top==m-1)printf(“overflow”); else {____________________;_________________;} } 3.3.中序遍歷二叉排序樹所得到的序列是___________序列（填有序或無序）。4.4.快速排序的最壞時間復雜度為___________，平均時間復雜度為__________。5.5.設某棵二叉樹中度數為0的結點數為N0，度數為1的結點數為N1，則該二叉樹中度數為2的結點數為_________；若采用二叉鏈表作為該二叉樹的存儲結構，則該二叉樹中共有_______個空指針域。 6.6.設某無向圖中頂點數和邊數分別為n和e，所有頂點的度數之和為d，則e=_______。 7.7.設一組初始記錄關鍵字序列為(55，63，44，38，75，80，31，56)，則利用篩選法建立的初始堆為___________________________。 v1??3??2??4v2??1??3v3??1??4??28.8.設某無向圖G的鄰接表為v4??1??3，則從頂點V1開始的深度優先遍歷序列為___________；廣度優先遍歷序列為____________。 三、應用題(36分)1． 1． 設一組初始記錄關鍵字序列為(45，80，48，40，22，78)，則分別給出第4趟簡單選擇排序和第4趟直接插入排序后的結果。 2． 2． 設指針變量p指向雙向鏈表中結點A，指針變量q指向被插入結點B，要求給出在結點A的后面插入結點B的操作序列（設雙向鏈表中結點的兩個指針域分別為llink和rlink）。 3． 3． 設一組有序的記錄關鍵字序列為(13，18，24，35，47，50，62，83，90)，查找方法用二分查找，要求計算出查找關鍵字62時的比較次數并計算出查找成功時的平均查找長度。 4． 4． 設一棵樹T中邊的集合為{(A，B)，(A，C)，(A，D)，(B，E)，(C，F)，(C，G)}，要求用孩子兄弟表示法（二叉鏈表）表示出該樹的存儲結構并將該樹轉化成對應的二叉樹。5． 5． 設有無向圖G（如右圖所示），要求給出用普里姆算法構造最小生成樹所走過的邊的集合。 6． 6． 設有一組初始記錄關鍵字為(45，80，48，40，22，78)，要求構造一棵二叉排序樹并給出構造過程。 數據結構試卷 （二）參考答案 一、選擇題 1.D 2.B 3.C 4.A 5.A 6.C 7.B 8.C 二、填空題 1.1.構造一個好的HASH函數，確定解決沖突的方法 2.2.stack.top++，stack.s[stack.top]=x 3.3.有序 4.4.O(n2)，O(nlog2n)5.5.N0-1，2N0+N1 6.6.d/2 7.7.(31，38，54，56，75，80，55，63)8.8.(1，3，4，2)，(1，3，2，4) 三、應用題 1.1.(22，40，45，48，80，78)，(40，45，48，80，22，78)2.2.q->llink=p;q->rlink=p->rlink;p->rlink->llink=q;p->rlink=q;3.3.2,ASL=91*1+2*2+3*4+4*2)=25/9 4.4.樹的鏈式存儲結構略，二叉樹略 5.5.E={(1，3)，(1，2)，(3，5)，(5，6)，(6，4)} 6.6.略 數據結構試卷 （三）一、選擇題(30分)1．設某數據結構的二元組形式表示為A=(D，R)，D={01，02，03，04，05，06，07，08，09}，R={r}，r={<01，02>，<01，03>，<01，04>，<02，05>，<02，06>，<03，07>，<03，08>，<03，09>}，則數據結構A是（）。 (A)線性結構(B)樹型結構(C)物理結構(D)圖型結構 2．下面程序的時間復雜為（） for（i=1，s=0； i<=n； i++）{t=1；for(j=1；j<=i；j++)t=t*j；s=s+t；}(A)O(n)(B)O(n2)(C)O(n3)(D)O(n4)3．設指針變量p指向單鏈表中結點A，若刪除單鏈表中結點A，則需要修改指針的操作序列為（）。 (A)q=p->next；p->data=q->data；p->next=q->next；free(q)；(B)q=p->next；q->data=p->data；p->next=q->next；free(q)； (C)q=p->next；p->next=q->next；free(q)； (D)q=p->next；p->data=q->data；free(q)； 4．設有n個待排序的記錄關鍵字，則在堆排序中需要（）個輔助記錄單元。 (A)1(B)n(C)nlog2n(D)n2 5．設一組初始關鍵字記錄關鍵字為(20，15，14，18，21，36，40，10)，則以20為基準記錄的一趟快速排序結束后的結果為()。(A)10，15，14，18，20，36，40，21(B)10，15，14，18，20，40，36，21(C)10，15，14，20，18，40，36，2l(D)15，10，14，18，20，36，40，21 6．設二叉排序樹中有n個結點，則在二叉排序樹的平均平均查找長度為（）。(A)O(1)(B)O(log2n)(C)(D)O(n)7．設無向圖G中有n個頂點e條邊，則其對應的鄰接表中的表頭結點和表結點的個數分別為（）。 (A)n，e(B)e，n(C)2n，e(D)n，2e 8.設某強連通圖中有n個頂點，則該強連通圖中至少有（）條邊。 (A)n(n-1)(B)n+1(C)n(D)n(n+1)9．設有5000個待排序的記錄關鍵字，如果需要用最快的方法選出其中最小的10個記錄關鍵字，則用下列（）方法可以達到此目的。 (A)快速排序(B)堆排序(C)歸并排序(D)插入排序 10.下列四種排序中（）的空間復雜度最大。 (A)插入排序(B)冒泡排序(C)堆排序(D)歸并排序 二、填空殖(48分，其中最后兩小題各6分)1.1.數據的物理結構主要包括_____________和______________兩種情況。 2.2.設一棵完全二叉樹中有500個結點，則該二叉樹的深度為__________；若用二叉鏈表作為該完全二叉樹的存儲結構，則共有___________個空指針域。 3.3.設輸入序列為1、2、3，則經過棧的作用后可以得到___________種不同的輸出序列。 4.4.設有向圖G用鄰接矩陣A[n][n]作為存儲結構，則該鄰接矩陣中第i行上所有元素之和等于頂點i的________，第i列上所有元素之和等于頂點i的________。 5.5.設哈夫曼樹中共有n個結點，則該哈夫曼樹中有________個度數為1的結點。6.6.設有向圖G中有n個頂點e條有向邊，所有的頂點入度數之和為d，則e和d的關系為_________。 7.7.__________遍歷二叉排序樹中的結點可以得到一個遞增的關鍵字序列（填先序、中序或后序）。 8.8.設查找表中有100個元素，如果用二分法查找方法查找數據元素X，則最多需要比較________次就可以斷定數據元素X是否在查找表中。 9.9.不論是順序存儲結構的棧還是鏈式存儲結構的棧，其入棧和出棧操作的時間復雜度均為____________。 10.10.設有n個結點的完全二叉樹，如果按照從自上到下、從左到右從1開始順序編號，則第i個結點的雙親結點編號為____________，右孩子結點的編號為___________。11.11.設一組初始記錄關鍵字為(72，73，71，23，94，16，5)，則以記錄關鍵字72為基準的一趟快速排序結果為___________________________。 12.12.設有向圖G中有向邊的集合E={<1，2>，<2，3>，<1，4>，<4，2>，<4，3>}，則該圖的一種拓撲序列為____________________。 13.13.下列算法實現在順序散列表中查找值為x的關鍵字，請在下劃線處填上正確的語句。 struct record{int key;int others;};int hashsqsearch(struct record hashtable[ ],int k){ int i,j;j=i=k % p;while(hashtable[j].key!=k&&hashtable[j].flag!=0){j=(____)%m;if(i==j)return(-1);} if(_______________________)return(j);else return(-1);} 14.14.下列算法實現在二叉排序樹上查找關鍵值k，請在下劃線處填上正確的語句。 typedef struct node{int key;struct node *lchild;struct node *rchild;}bitree;bitree *bstsearch(bitree *t, int k){ if(t==0)return(0);else while(t!=0)if(t->key==k)_____________;else if(t->key>k)t=t->lchild;else_____________;} 數據結構試卷 （三）參考答案 一、選擇題 1.B 2.B 3.A 4.A 5.A 6.B 7.D 8.C 9.B 10.D 第3小題分析：首先用指針變量q指向結點A的后繼結點B，然后將結點B的值復制到結點A中，最后刪除結點B。 第9小題分析：9快速排序、歸并排序和插入排序必須等到整個排序結束后才能夠求出最小的10個數，而堆排序只需要在初始堆的基礎上再進行10次篩選即可，每次篩選的時間復雜度為O(log2n)。 二、填空題 1.1.順序存儲結構、鏈式存儲結構 2.2.9，501 3.3.5 4.4.出度，入度 5.5.0 6.6.e=d 7.7.中序 8.8.7 9.9.O(1)10.10.i/2，2i+1 11.11.(5，16，71，23，72，94，73)12.12.(1，4，3，2)13.13.j+1，hashtable[j].key==k 14.14.return(t)，t=t->rchild 第8小題分析：二分查找的過程可以用一棵二叉樹來描述，該二叉樹稱為二叉判定樹。在有序表上進行二分查找時的查找長度不超過二叉判定樹的高度1+log2n。 } 數據結構試卷 （四）一、選擇題(30分)1．設一維數組中有n個數組元素，則讀取第i個數組元素的平均時間復雜度為（）。(A)O(n)(B)O(nlog2n)(C)O(1)(D)O(n)2．設一棵二叉樹的深度為k，則該二叉樹中最多有（）個結點。 (A)2k-1(B)2k(C)2k-1(D)2k-1 3．設某無向圖中有n個頂點e條邊，則該無向圖中所有頂點的入度之和為（）。 (A)n(B)e(C)2n(D)2e 4．在二叉排序樹中插入一個結點的時間復雜度為（）。 (A)O(1)(B)O(n)(C)O(log2n)(D)O(n2)5．設某有向圖的鄰接表中有n個表頭結點和m個表結點，則該圖中有（）條有向邊。 (A)n(B)n-1(C)m(D)m-1 6．設一組初始記錄關鍵字序列為(345，253，674，924，627)，則用基數排序需要進行（）趟的分配和回收才能使得初始關鍵字序列變成有序序列。 (A)3(B)4(C)5(D)8 7．設用鏈表作為棧的存儲結構則退棧操作（）。 (A)必須判別棧是否為滿(B)必須判別棧是否為空 (C)判別棧元素的類型(D)對棧不作任何判別 8．下列四種排序中（）的空間復雜度最大。 (A)快速排序(B)冒泡排序(C)希爾排序(D)堆 9．設某二叉樹中度數為0的結點數為N0，度數為1的結點數為Nl，度數為2的結點數為N2，則下列等式成立的是（）。 (A)N0=N1+1(B)N0=Nl+N2(C)N0=N2+1(D)N0=2N1+l 10.設有序順序表中有n個數據元素，則利用二分查找法查找數據元素X的最多比較次數不超過（）。 (A)log2n+1(B)log2n-1(C)log2n(D)log2(n+1) 二、填空題(42分)1． 1． 設有n個無序的記錄關鍵字，則直接插入排序的時間復雜度為________，快速排序的平均時間復雜度為_________。 2． 2． 設指針變量p指向雙向循環鏈表中的結點X，則刪除結點X需要執行的語句序列為_________________________________________________________（設結點中的兩個指針域分別為llink和rlink）。3． 3． 根據初始關鍵字序列(19，22，01，38，10)建立的二叉排序樹的高度為____________。4． 4． 深度為k的完全二叉樹中最少有____________個結點。5． 5． 設初始記錄關鍵字序列為(K1，K2，…，Kn)，則用篩選法思想建堆必須從第______個元素開始進行篩選。 6． 6． 設哈夫曼樹中共有99個結點，則該樹中有_________個葉子結點；若采用二叉鏈表作為存儲結構，則該樹中有_____個空指針域。 7． 7． 設有一個順序循環隊列中有M個存儲單元，則該循環隊列中最多能夠存儲________個隊列元素；當前實際存儲________________個隊列元素（設頭指針F指向當前隊頭元素的前一個位置，尾指針指向當前隊尾元素的位置）。 8． 8． 設順序線性表中有n個數據元素，則第i個位置上插入一個數據元素需要移動表中_______個數據元素；刪除第i個位置上的數據元素需要移動表中_______個元素。9． 9． 設一組初始記錄關鍵字序列為(20，18，22，16，30，19)，則以20為中軸的一趟快速排序結果為______________________________。 10．10．設一組初始記錄關鍵字序列為(20，18，22，16，30，19)，則根據這些初始關鍵字序列建成的初始堆為________________________。 11．11．設某無向圖G中有n個頂點，用鄰接矩陣A作為該圖的存儲結構，則頂點i和頂點j互為鄰接點的條件是______________________。 12．12．設無向圖對應的鄰接矩陣為A，則A中第i上非0元素的個數_________第i列上非0元素的個數（填等于，大于或小于）。 13．13．設前序遍歷某二叉樹的序列為ABCD，中序遍歷該二叉樹的序列為BADC，則后序遍歷該二叉樹的序列為_____________。 14．14．設散列函數H(k)=k mod p，解決沖突的方法為鏈地址法。要求在下列算法劃線處填上正確的語句完成在散列表hashtalbe中查找關鍵字值等于k的結點，成功時返回指向關鍵字的指針，不成功時返回標志0。 typedef struct node {int key;struct node *next;} lklist;void createlkhash(lklist *hashtable[ ]){ int i,k;lklist *s;for(i=0;i 數據結構試卷 （四）參考答案 一、選擇題 1．C 2．D 3．D 4．B 5．C 6．A 7．B 8．A 9．C 10．A 二、填空題 1.1.O(n2)，O(nlog2n)2.2.p>llink->rlink=p->rlink;p->rlink->llink=p->rlink 3.3.3 4.4.2k-1 5.5.n/2 6.6.50，51 7.7.m-1，(R-F+M)%M 8.8.n+1-i，n-i 9.9.(19，18，16，20，30，22)10.10.(16，18，19，20，32，22)11.11.A[i][j]=1 12.12.等于 13.13.BDCA 14.14.hashtable[i]=0，hashtable[k]=s 數據結構試卷 （五）一、選擇題(30分) 1．數據的最小單位是（）。 (A)數據項(B)數據類型(C)數據元素(D)數據變量 2．設一組初始記錄關鍵字序列為(50，40，95，20，15，70，60，45)，則以增量d=4的一趟希爾排序結束后前4條記錄關鍵字為（）。 (A)40，50，20，95(B)15，40，60，20(C)15，20，40，45(D)45，40，15，20 3．設一組初始記錄關鍵字序列為(25，50，15，35，80，85，20，40，36，70)，其中含有5個長度為2的有序子表，則用歸并排序的方法對該記錄關鍵字序列進行一趟歸并后的結果為（）。 (A)15，25，35，50，20，40，80，85，36，70(B)15，25，35，50，80，20，85，40，70，36(C)15，25，35，50，80，85，20，36，40，70(D)15，25，35，50，80，20，36，40，70，85 4．函數substr(“DATASTRUCTURE”，5，9)的返回值為（）。 (A)“STRUCTURE”(B)“DATA” (C)“ASTRUCTUR”(D)“DATASTRUCTURE” 5．設一個有序的單鏈表中有n個結點，現要求插入一個新結點后使得單鏈表仍然保持有序，則該操作的時間復雜度為（）。 (A)O(log2n)(B)O(1)(C)O(n2)(D)O(n)6．設一棵m叉樹中度數為0的結點數為N0，度數為1的結點數為Nl，……，度數為m的結點數為Nm，則N0=（）。 (A)Nl+N2+……+Nm (B)l+N2+2N3+3N4+……+(m-1)Nm(C)N2+2N3+3N4+……+(m-1)Nm(D)2Nl+3N2+……+(m+1)Nm 7．設有序表中有1000個元素，則用二分查找查找元素X最多需要比較（）次。 (A)25(B)10(C)7(D)1 8．設連通圖G中的邊集E={(a，b)，(a，e)，(a，c)，(b，e)，(e，d)，(d，f)，(f，c)}，則從頂點a出發可以得到一種深度優先遍歷的頂點序列為（）。 (A)abedfc(B)acfebd(C)aebdfc(D)aedfcb 9．設輸入序列是1、2、3、……、n，經過棧的作用后輸出序列的第一個元素是n，則輸出序列中第i個輸出元素是（）。 (A)n-i(B)n-1-i(C)n+1-i(D)不能確定 設一組初始記錄關鍵字序列為(45，80，55，40，42，85)，則以第一個記錄關鍵字45為基準而得到一趟快速排序的結果是（）。 (A)40，42，45，55，80，83(B)42，40，45，80，85，88(C)42，40，45，55，80，85(D)42，40，45，85，55，80 二、填空題(共30分)1.1.設有一個順序共享棧S[0：n-1]，其中第一個棧項指針top1的初值為-1，第二個棧頂指針top2的初值為n，則判斷共享棧滿的條件是____________________。 2.2.在圖的鄰接表中用順序存儲結構存儲表頭結點的優點是____________________。 3.3.設有一個n階的下三角矩陣A，如果按照行的順序將下三角矩陣中的元素（包括對角線上元素）存放在n(n+1)個連續的存儲單元中，則A[i][j]與A[0][0]之間有_______個數據元素。 4.4.棧的插入和刪除只能在棧的棧頂進行，后進棧的元素必定先出棧，所以又把棧稱為__________表；隊列的插入和刪除運算分別在隊列的兩端進行，先進隊列的元素必定先出隊列，所以又把隊列稱為_________表。 5.5.設一棵完全二叉樹的順序存儲結構中存儲數據元素為ABCDEF，則該二叉樹的前序遍歷序列為___________，中序遍歷序列為___________，后序遍歷序列為___________。 6.6.設一棵完全二叉樹有128個結點，則該完全二叉樹的深度為________，有__________個葉子結點。 7.7.設有向圖G的存儲結構用鄰接矩陣A來表示，則A中第i行中所有非零元素個數之和等于頂點i的________，第i列中所有非零元素個數之和等于頂點i的__________。 8.8.設一組初始記錄關鍵字序列(k1，k2，……，kn)是堆，則對i=1，2，…，n/2而言滿足的條件為_______________________________。 9.9.下面程序段的功能是實現冒泡排序算法，請在下劃線處填上正確的語句。void bubble(int r[n]){ for(i=1;i<=n-1;i++){ for(exchange=0,j=0;j<_____________;j++) if(r[j]>r[j+1]){temp=r[j+1];______________;r[j]=temp;exchange=1;} if(exchange==0)return； } } 10.10.下面程序段的功能是實現二分查找算法，請在下劃線處填上正確的語句。struct record{int key;int others;};int bisearch(struct record r[ ], int k){ int low=0,mid,high=n-1; while(low<=high){ ________________________________; if(r[mid].key==k)return(mid+1);else if(____________)high=mid-1;else low=mid+1; } return(0);} 三、應用題(24分) 1.1.設某棵二叉樹的中序遍歷序列為DBEAC，前序遍歷序列為ABDEC，要求給出該二叉樹的的后序遍歷序列。2.2.設無向圖G（如右圖所示），給出該圖的最小生成樹上邊的集合并計算最小生成樹各邊上的權值之和。 3.3.設一組初始記錄關鍵字序列為(15，17，18，22，35，51，60)，要求計算出成功查找時的平均查找長度。 4.4.設散列表的長度為8，散列函數H(k)=k mod 7，初始記錄關鍵字序列為(25，31，8，27，13，68)，要求分別計算出用線性探測法和鏈地址法作為解決沖突方法的平均查找長度。 數據結構試卷 （五）參考答案 一、選擇題 1．A 2．B 3．A 4．A 5．D 6．B 7．B 8．B 9．C 10．C 二、填空題 1.1.top1+1=top2 2.2.可以隨機訪問到任一個頂點的簡單鏈表 3.3.i(i+1)/2+j-1 4.4.FILO，FIFO 5.5.ABDECF，DBEAFC，DEBFCA 6.6.8，64 7.7.出度，入度 8.8.ki<=k2i && ki<=k2i+1 9.9.n-i，r[j+1]=r[j] 10.10.mid=(low+high)/2，r[mid].key>k 三、應用題 1.1.DEBCA 2.2.E={(1,5),(5,2),(5,3),(3,4)},W=10 3.3.ASL=(1*1+2*2+3*4)/7=17/7 4.4.ASL1=7/6，ASL2=4/3 數據結構試卷 （六）一、選擇題(30分)1． 設一組權值集合W={2，3，4，5，6}，則由該權值集合構造的哈夫曼樹中帶權路徑長度之和為（）。 (A)20(B)30(C)40(D)45 2．執行一趟快速排序能夠得到的序列是（）。 (A)[41，12，34，45，27] 55 [72，63](B)[45，34，12，41] 55 [72，63，27](C)[63，12，34，45，27] 55 [41，72](D)[12，27，45，41] 55 [34，63，72] 3．設一條單鏈表的頭指針變量為head且該鏈表沒有頭結點，則其判空條件是（）。(A)head==0(B)head->next==0(C)head->next==head(D)head!=0 4．時間復雜度不受數據初始狀態影響而恒為O(nlog2n)的是（）。 (A)堆排序(B)冒泡排序(C)希爾排序(D)快速排序 5．設二叉樹的先序遍歷序列和后序遍歷序列正好相反，則該二叉樹滿足的條件是（）。 (A)空或只有一個結點(B)高度等于其結點數 (C)任一結點無左孩子(D)任一結點無右孩子 6．一趟排序結束后不一定能夠選出一個元素放在其最終位置上的是（）。 (A)堆排序(B)冒泡排序(C)快速排序(D)希爾排序 7．設某棵三叉樹中有40個結點，則該三叉樹的最小高度為（）。 (A)3(B)4(C)5(D)6 8．順序查找不論在順序線性表中還是在鏈式線性表中的時間復雜度為（）。 21/2(A)O(n)(B)O(n)(C)O(n)(D)O(1og2n)9．二路歸并排序的時間復雜度為（）。(A)O(n)(B)O(n)(C)O(nlog2n)(D)O(1og2n)10.深度為k的完全二叉樹中最少有（）個結點。 (A)2k-1-1(B)2k-1(C)2k-1+1(D)2k-1 11.設指針變量front表示鏈式隊列的隊頭指針，指針變量rear表示鏈式隊列的隊尾指針，指針變量s指向將要入隊列的結點X，則入隊列的操作序列為（）。 (A)front->next=s；front=s；(B)s->next=rear；rear=s； (C)rear->next=s；rear=s；(D)s->next=front；front=s； 12.設某無向圖中有n個頂點e條邊，則建立該圖鄰接表的時間復雜度為（）。(A)O(n+e)(B)O(n)(C)O(ne)(D)O(n)13.設某哈夫曼樹中有199個結點，則該哈夫曼樹中有（）個葉子結點。 (A)99(B)100(C)101(D)102 14.設二叉排序樹上有n個結點，則在二叉排序樹上查找結點的平均時間復雜度為（）。(A)O(n)(B)O(n)(C)O(nlog2n)(D)O(1og2n)15.設用鄰接矩陣A表示有向圖G的存儲結構，則有向圖G中頂點i的入度為（）。 (A)第i行非0元素的個數之和(B)第i列非0元素的個數之和 (C)第i行0元素的個數之和(D)第i列0元素的個數之和 二、判斷題(20分)1．調用一次深度優先遍歷可以訪問到圖中的所有頂點。（） 2．分塊查找的平均查找長度不僅與索引表的長度有關，而且與塊的長度有關。（）3．冒泡排序在初始關鍵字序列為逆序的情況下執行的交換次數最多。（）4．滿二叉樹一定是完全二叉樹，完全二叉樹不一定是滿二叉樹。（） 5．設一棵二叉樹的先序序列和后序序列，則能夠唯一確定出該二叉樹的形狀。（）6．層次遍歷初始堆可以得到一個有序的序列。（） 7．設一棵樹T可以轉化成二叉樹BT，則二叉樹BT中一定沒有右子樹。（）8．線性表的順序存儲結構比鏈式存儲結構更好。（） 9．中序遍歷二叉排序樹可以得到一個有序的序列。（）10.快速排序是排序算法中平均性能最好的一種排序。（） 三、填空題(30分)1．for(i=1，t=1，s=0；i<=n；i++){t=t*i；s=s+t；}的時間復雜度為_________。 2．設指針變量p指向單鏈表中結點A，指針變量s指向被插入的新結點X，則進行插入操作的語句序列為__________________________（設結點的指針域為next）。3．設有向圖G的二元組形式表示為G =（D，R），D={1，2，3，4，5}，R={r}，r={<1,2>，<2,4>，<4,5>，<1,3>，<3,2>，<3,5>}，則給出該圖的一種拓撲排序序列__________。4．設無向圖G中有n個頂點，則該無向圖中每個頂點的度數最多是_________。5．設二叉樹中度數為0的結點數為50，度數為1的結點數為30，則該二叉樹中總共有_______個結點數。 6．設F和R分別表示順序循環隊列的頭指針和尾指針，則判斷該循環隊列為空的條件為_____________________。 7．設二叉樹中結點的兩個指針域分別為lchild和rchild，則判斷指針變量p所指向的結點為葉子結點的條件是_____________________________________________。8．簡單選擇排序和直接插入排序算法的平均時間復雜度為___________。 9．快速排序算法的空間復雜度平均情況下為__________，最壞的情況下為__________。10.散列表中解決沖突的兩種方法是_____________和_____________。 數據結構試卷 （六）參考答案 一、選擇題 1．D 2．A 3．A 4．A 5．D 6．D 7．B 8．A 9．C 10．B 11．C 12．A 13．B 14．D 15．B 二、判斷題 1．錯 2．對 3．對 4．對 5．錯 6．錯 7．對 8．錯 9．對 10．對 三、填空題 1.1.O(n)2.2.s->next=p->next;p->next=s 3.3.(1，3，2，4，5)4.4.n-1 5.5.129 6.6.F==R 7.7.p->lchild==0&&p->rchild==0 8.8.O(n2)9.9.O(nlog2n)，O(n)10.10.開放定址法，鏈地址法 數據結構試卷 （七）一、選擇題(30分)1．設某無向圖有n個頂點，則該無向圖的鄰接表中有（）個表頭結點。 (A)2n(B)n(C)n/2(D)n(n-1)2．設無向圖G中有n個頂點，則該無向圖的最小生成樹上有（）條邊。 (A)n(B)n-1(C)2n(D)2n-1 3．設一組初始記錄關鍵字序列為(60，80，55，40，42，85)，則以第一個關鍵字45為基準而得到的一趟快速排序結果是（）。 (A)40，42，60，55，80，85(B)42，45，55，60，85，80(C)42，40，55，60，80，85(D)42，40，60，85，55，80 4．（）二叉排序樹可以得到一個從小到大的有序序列。 (A)先序遍歷(B)中序遍歷(C)后序遍歷(D)層次遍歷 5．設按照從上到下、從左到右的順序從1開始對完全二叉樹進行順序編號，則編號為i結點的左孩子結點的編號為（）。 (A)2i+1(B)2i(C)i/2(D)2i-1 6．程序段s=i=0；do {i=i+1； s=s+i；}while(i<=n)；的時間復雜度為（）。(A)O(n)(B)O(nlog2n)(C)O(n)(D)O(n/2)7．設帶有頭結點的單向循環鏈表的頭指針變量為head，則其判空條件是（）。 (A)head==0(B)head->next==0(C)head->next==head(D)head!=0 8．設某棵二叉樹的高度為10，則該二叉樹上葉子結點最多有（）。 (A)20(B)256(C)512(D)1024 9．設一組初始記錄關鍵字序列為(13，18，24，35，47，50，62，83，90，115，134),則利用二分法查找關鍵字90需要比較的關鍵字個數為（）。 (A)1(B)2(C)3(D)4 10.設指針變量top指向當前鏈式棧的棧頂，則刪除棧頂元素的操作序列為（）。 (A)top=top+1;(B)top=top-1;(C)top->next=top;(D)top=top->next; 三、填空題(30分)1.1.設指針變量p指向雙向鏈表中的結點A，指針變量s指向被插入的結點X，則在結點A的后面插入結點X的操作序列為_________=p；s->right=p->right；__________=s； p->right->left=s；（設結點中的兩個指針域分別為left和right）。2.2.設完全有向圖中有n個頂點，則該完全有向圖中共有________條有向條；設完全無向圖中有n個頂點，則該完全無向圖中共有________條無向邊。 3.3.設關鍵字序列為(Kl，K2，…，Kn)，則用篩選法建初始堆必須從第______個元素開始進行篩選。 4.4.解決散列表沖突的兩種方法是________________和__________________。 5.5.設一棵三叉樹中有50個度數為0的結點，21個度數為2的結點，則該二叉樹中度數為3的結點數有______個。 6.6.高度為h的完全二叉樹中最少有________個結點，最多有________個結點。7.7.設有一組初始關鍵字序列為(24，35，12，27，18，26)，則第3趟直接插入排序結束后的結果的是__________________________________。 8.8.設有一組初始關鍵字序列為(24，35，12，27，18，26)，則第3趟簡單選擇排序結束后的結果的是__________________________________。 9.9.設一棵二叉樹的前序序列為ABC，則有______________種不同的二叉樹可以得到這種序列。 10.10.下面程序段的功能是實現一趟快速排序，請在下劃線處填上正確的語句。 struct record {int key;datatype others;};void quickpass(struct record r[], int s, int t, int &i){ int j=t;struct record x=r[s];i=s; while(i while(i while(____________________)i=i+1;if(i } _________________;} 數據結構試卷 （七）一、選擇題 1．B 2．B 3．C 4．B 6．A 7．C 8．C 9．B 三、填空題 1.1.s->left=p，p->right 2.2.n(n-1)，n(n-1)/2 3.3.n/2 4.4.開放定址法，鏈地址法 5.5.14 6.6.2h-1，2h-1 7.7.(12，24，35，27，18，26)8.8.(12，18，24，27，35，26)9.9.5 10.10.i 5．B 10．D 數據結構試卷 （八）一、選擇題(30分)1.1.字符串的長度是指（）。 (A)串中不同字符的個數(B)串中不同字母的個數 (C)串中所含字符的個數(D)串中不同數字的個數 2.2.建立一個長度為n的有序單鏈表的時間復雜度為（） (A)O(n)(B)O(1)(C)O(n2)(D)O(log2n)3.3.兩個字符串相等的充要條件是（）。 (A)兩個字符串的長度相等(B)兩個字符串中對應位置上的字符相等 (C)同時具備(A)和(B)兩個條件(D)以上答案都不對 4.4.設某散列表的長度為100，散列函數H(k)=k % P，則P通常情況下最好選擇（）。 (A)99(B)97(C)91(D)93 5.5.在二叉排序樹中插入一個關鍵字值的平均時間復雜度為（）。(A)O(n)(B)O(1og2n)(C)O(nlog2n)(D)O(n)6.6.設一個順序有序表A[1:14]中有14個元素，則采用二分法查找元素A[4]的過程中比較元素的順序為()。 (A)A[1]，A[2]，A[3]，A[4](B)A[1]，A[14]，A[7]，A[4](C)A[7]，A[3]，A[5]，A[4](D)A[7]，A[5]，A[3]，A[4] 7.7.設一棵完全二叉樹中有65個結點，則該完全二叉樹的深度為（）。 (A)8(B)7(C)6(D)5 8.8.設一棵三叉樹中有2個度數為1的結點，2個度數為2的結點，2個度數為3的結點，則該三叉鏈權中有（）個度數為0的結點。 (A)5(B)6(C)7(D)8 9.9.設無向圖G中的邊的集合E={(a，b)，(a，e)，(a，c)，(b，e)，(e，d)，(d，f)，(f，c)}，則從頂點a出發進行深度優先遍歷可以得到的一種頂點序列為（）。 (A)aedfcb(B)acfebd(C)aebcfd(D)aedfbc 10.10.隊列是一種（）的線性表。 (A)先進先出(B)先進后出(C)只能插入(D)只能刪除 三、填空題(30分)1． 1． 設一組初始記錄關鍵字序列為(49，38，65，97，76，13，27，50)，則以d=4為增量的一趟希爾排序結束后的結果為_____________________________。 2． 2． 下面程序段的功能是實現在二叉排序樹中插入一個新結點，請在下劃線處填上正確的內容。 typedef struct node{int data;struct node *lchild;struct node *rchild;}bitree;void bstinsert(bitree *&t,int k){ if(t==0){____________________________;t->data=k;t->lchild=t->rchild=0;} else if(t->data>k)bstinsert(t->lchild,k);else__________________________;} 3． 3． 設指針變量p指向單鏈表中結點A，指針變量s指向被插入的結點X，則在結點A的后面插入結點X需要執行的語句序列：s->next=p->next;_________________。4． 4． 設指針變量head指向雙向鏈表中的頭結點，指針變量p指向雙向鏈表中的第一個結點，則指針變量p和指針變量head之間的關系是p=_________和head=__________（設結點中的兩個指針域分別為llink和rlink）。 5． 5． 設某棵二叉樹的中序遍歷序列為ABCD，后序遍歷序列為BADC，則其前序遍歷序列為__________。 6． 6． 完全二叉樹中第5層上最少有__________個結點，最多有_________個結點。7． 7． 設有向圖中不存在有向邊 8． 8． 設一組初始記錄關鍵字序列為(49，38，65，97，76，13，27，50)，則第4趟直接選擇排序結束后的結果為_____________________________。 9． 9． 設連通圖G中有n個頂點e條邊，則對應的最小生成樹上有___________條邊。10． 10． 設有一組初始記錄關鍵字序列為(50，16，23，68，94，70，73)，則將它們調整成初始堆只需把16與___________相互交換即可。 數據結構試卷 （八）參考答案 一、選擇題 1．C 2．C 3．C 4．B 5．B 6．C 7．B 8．C 9．A 10．A 三、填空題 1.1.(49，13，27，50，76，38，65，97)2.2.t=(bitree *)malloc(sizeof(bitree))，bstinsert(t->rchild,k)3.3.p->next=s 4.4.head->rlink，p->llink 5.5.CABD 6.6.1，16 7.7.0 8.8.(13，27，38，50，76，49，65，97)9.9.n-1 10.10.50 1、串的邏輯結構與（D）的邏輯結構不相同。A）線性表 B）棧 C）隊列 D）集合 2、廣義表head(((a,b),(c,d)))的運算結果為（A）。A）(a,b)B）(c,d)C）空表 D）（（a,b）,(c,d)） 3、鏈式存儲的存儲結構所占存儲空間（A）。 A）分兩部分，一部分存放結點值，另一部分存放表示結點間關系的指針 B）只有一部分，存放結點值 C）只有一部分，存儲表示結點間關系的指針 D）分兩部分，一部分存放結點值，另一部分存放結點所占單元數 4、設單鏈表中指針p指向結點m，若要刪除m之后的結點（若存在），則需修改指針的操作為（A）。 A）p->next=p->next->next;B）p=p->next;C）p=p->next->next;D）p->next=p; 5、在一個具有n個單元的順序棧中，假定以地址低端（即0單元）作為棧底，以top作為棧頂指針，當做出棧處理時，top變化為（C）。 A）top不變 B）top=0 C）top--D）top++ 6、數據結構研究的內容是（D）。 A）數據的邏輯結構 B）數據的存儲結構 C）建立在相應邏輯結構和存儲結構上的算法 D）包括以上三個方面 7、向一個棧頂指針為hs的鏈棧中插入一個s結點時，應執行（D）。A)hs->next=s; B)s->next=hs->next;hs->next=s;C)s->next=hs;hs=s;D)s->next=hs;hs=hs->next; 8、設一數列的順序為1，2，3，4，5，6，通過棧結構不可能排成的順序數列為（B）。A）3，2，5，6，4，1 B）1，5，4，6，2，3 C）2，4，3，5，1，6 D）4，5，3，6，2，1 9、廣義表head(((a,b),(c,d)))的運算結果為（A）。A）(a,b)B）(c,d)C）空表 D）（（a,b）,(c,d)） 10、若一棵二叉樹具有10個度為2的結點，5個度為1的結點，則度為0的結點的個數是(B)。A）9 B）11 C）15 D）不能確定 11、在一個鏈隊列中，假定front和rear分別為隊首和隊尾指針，則刪除一個結點的操作為（B）。A)rear=rear->next;B)front=front->next;C)rear=front->next; D)front=rear->next; 12、n個頂點的圖的最小生成樹必定（D），是不正確的描述。A）不唯一 B）權的總和唯一 C）不含回路 D）有n條邊 13、串的邏輯結構與（D）的邏輯結構不同。A）線性表 B）棧 C）隊列 D）樹 管理學原理試題和大題答案 一、單項選擇[請從所給出的四個選項中，選擇一個正確答案的字母填入括號。1．關于管理的含義，下列詞語中()的表述不確切。A.激勵、約束 B．協調、溝通 C.放任、自由 D．理順、調整 2．在TL茨劃分的幾種主要的管理學理論流振中，()主張通過分析案例來研究管理學問題。A．管理過程學派 B.經驗學派 C.系統管理學派 D．管理科學學派 3．管理學界對行為科學的研究是在()的基礎上發展起來的，并迅速成為影響巨大的理論流派。A.科學管理理論 B．人際關系學說 C.經營管理理論 D.權變理論學派 4．下列關于計劃的描述正確的是()。 A．企業目標是追逐利潤，因此計劃工作只需考慮經濟效益 B．計劃工作至關重要，因此必須面面俱到 C.計劃與決策沒有什么必然的聯系 D．計劃工作在各級管理工作中普遍存在 5．銷售人員意見綜合預測方法主要適用于()。A.丸市場預測 B．技術預測 c．戰略規劃預測 D．財務預測 6．某企業生產同種產品有三種方案可供選擇，已知各方案的固定成本和單位變動成本分別為：甲方案5000 511 100；乙方案15000{r11 60；丙方案25000和 40，目前企業的產量可以達到610，那么企業應該選擇()才能實現成本最低。A．甲方案 B.乙方案 C.丙方案 D．無法碗定 7．下列關于管理幅度與管理層次的描述正確的是()。A.管理幅度與管理層次共同決定組織規模 B．為了保證管理效果，管理幅度越大越好 c.當組織規模一定時，管理幅度與管理規模成正比關系 D．管理幅度越窄，管理層次就越多，組織結構就呈扁平型 8．領導是領導者向下屬施加影響的行為，領導的實質在于()。A．影響 B．權利 C.職位 D.職責 9．控制系統是由控制主體、控制客體和控制媒體組成，符合控制目的，具有自身功能的管理系統，其中控制主體是指()。 A．具有上次之分的一個組織的全部行為活動 B.控制行為所需的媒介物或方式 C.控制活動所針對的人、財、物和信息 D．控制活動中的各級管理人員及其所屬的職能部門 10．下列對現代沖突理論的理解不確切的是()。A.沖突可以為組織帶來活力，因此管理者要制造各種沖突 B．管理者的任務主要是管理好沖突，減少不利影響 C.沖突具有正面和反面、建設性和破壞性兩種性質 D．適當的沖突可以給組織帶來好處 11．管理的最終目的是()。 A.實現人與人之間關系的協調 B．有效地組織資源和組織活動 C.以最少的投入獲得最大的產出 D.制定組織目標 12．諸葛亮“借東風”給周瑜的典故說明了()的重要性。A．預測 B．決策 C.計劃 D．聯合 13．激勵手段之一是“工作豐富化”，其含義是()。A.增加工作內容 B．使工作具有挑戰性且富有意義 C.工作內容更具挑戰性 D．消除工作的單調乏味 14．組織結構設計的出發點和依據是()。A.企業目標 D．權責利關系 C.分工合作關系 D．一項管理職能 15．上級與下級的溝通中，如果上級發問：“你有意見嗎?”“你明白嗎?”這說明領導者在溝通中()。A.善于積極傾聽 B．比較謙虛 C.態度積極友好 D．善于運用反饋 二、判斷正誤(下列各題有對有錯，對的劃√；錯的劃X并改正。每小 題2分，共20分)1．管理的一般職能來源于管理的科學性性質，內容是合理組織生產力和維護生產關系。()2．企業戰略管理的核心是對企業現在和未來的整體效益活動實行全局性管理。()3．計劃工作事關重大，因此，企業高層管理者一定要做好計劃工作，中下級管理人員不必做計劃。()4．頭腦風暴法進行預測關鍵是要取得參與人員的一致意見。()5．區分事業部制組織結構和控股型組織結構的最明顯特征是分支機構(事業部和子公司)是否是獨立法人。()6．扁平型組織結構有利于領導控制，但會影響下屬的工作積極性。()7．在一個組織中，領導的工作績效是由領導者個人的工作成績表現出來的。()8．根據期望理論，如果激勵的效價足夠大，則可以達到很高的激勵水平。()9．為了實現有效控制的要求，控制工作一定要嚴格按照計劃的標準來檢查，應加強剛性原則，避免靈活性原則。()10．非正式溝通容易傳播小道消息，因此組織要極力避免。() 三、簡答題(每小題lo分，共30分。要點應展開，否則酌情扣分)1．簡述泰羅科學管理理論的主要內容。2．管理人員培訓的內容有哪些? 3．簡述馬斯洛的需要層次理論。 四、案例分析(20分)陳華已經在一家IT公司工作了5個年頭。在這期間，他從普通編程員升到資深的編程分析員。他對自己所服務的這家公司相當滿意，不管是工作職位還是收入，都讓陳華感到有成就感，而且他還為工作中的創造性要求所激勵。 一個周末的下午，陳華和他的朋友及同事王迪一起打高爾夫球。他了解到他所在的部門新雇了一位剛從大學畢業的編程分析員。盡管陳華是個好脾氣的人，但當他聽說這位新來者的起薪僅比他現在的工資少30元時，不禁發火了。 下周一的早上，陳華找到了人事部主任李江林，問他自己聽說的事是不是真的，李江林帶有歉意地說，確有這么回事，但他試圖解釋公司的處境：“陳華，編程分析員的市場相當緊俏，為使公司能吸引合格的人雖，我們不得不提供較高的起薪。我們非常需要增加一名編程分析員，因此我們只能這么做。” 陳華問能否相應調高他的工資。李江林回答說：“你的工資需按照正常的績效評估時間評定后再調。你干得非常不錯!我相信老板到時會給你提薪的。”陳華在向李扛林道了聲“打擾了!”便離開了他的辦公室，邊走邊不停地搖頭，很對自己在公司的前途感到疑慮。問題： 1．本例描述的事件對陳華的工作動力會產生什么樣的影響?(4分)2．哪一種激勵理論可以更好地解釋陳華的困惑?簡述其理論內容。(s分)3．你覺得李江林的解釋會讓陳華感到滿意嗎，請說明理由．(4分)4．你認為公司應當對陳華采取什么措施?為什么?(4分) 管理學基礎 試題答案及評分標準 一、單項選擇(請從所給出的四個選項中，選擇一個正確答案的字母填入括號。每小題2分，共 30分)1．C 2．B 3．B 4．D 5．A 6．C 7．A 8．A 9，D 10．A 11．B 12．A 13．B 14．A 15．D 二、判斷正誤(下列各題有對有錯，對的劃√；錯的劃X并改正。每小題2分，共20分)1．(X)把“科學性”改為“二重性” 2．(√) 3．(X)計劃工作在各級管理人員的工作中普遍存在，均很重要 4．(X)關鍵是引起思維共振，產生創造性思維 5．(√) 6．(X)扁平型組織結構有利于信息溝通，有利于調動下級人員的積極性 7．(X)是由被領導者的群體活動的成效表現出來的 8．(X)效價和期望值都較高時，才能取得較高的激勵水平 9．(X)控制工作應該有一定的彈性，要遵循靈活性原則，及時糾正計劃中的疏忽，才可以適應環境的變化。10．(X)非正式溝通是溝通的重要形式，充分利用可以成為正式溝通的重要補充。 三、簡答題(每小題10分，共30分。要點應展開，否則酌情扣分)1．簡述泰羅科學管理理論的內容。 科學管理理論是美國古典管理理論的代表，是由科學管理之父泰羅提出的。其主要內容有：(1)制定科學的作業方法；(2)科學的選擇和培訓工人；(3)實行有差別的計件工資制；(4)將計劃職能和執行職能分開；(5)實行職能工長制；(6)在管理上實行例外原則。2．管理人員培訓的內容有哪些? 管理人員培訓的內容主要有：(1)業務培訓；(2)管理理論；(3)管理能力； (4)交際能力及心理素質等方面。3．簡述馬斯洛的需要層次理論。馬斯洛把人類的需要分為五大層次： 第一層次的需要是生理上的需要。是為維持人類自身生命的基本需要，如食物、水、衣著、住所和睡眠。第二層次的需要是安全的需要。是有關人類避免危險的需要。 第三層次是友愛和歸屬的需要．當生理及安全得到相當的滿足，友愛和歸屬方面的需要 便占據主要地位。第四層次的需要是尊重的需要。人們一旦滿足了歸屬的需要，他們就會產生尊重的需要，即自尊和受到別人的尊重。 第五層次的需要是自我實現的需要，這是最高層次的需要。 馬斯洛認為，一般的人都是按照這個層次從低級到高級，一層一層地去追求并使自己的需要得到滿足。 四、案例分析(20分)解答提示： 1．事件會對陳華的工作動力產生非常消極的影響，因為對于陳華來說，他在工作中所獲得的激勵主要來自于成就激勵和創造性激勵，而體現他的成就的重要表現或者說重要標志之一就是薪水，當他感覺自己的固成就感而帶來的自信受到打擊，處境很尷尬時，一個有成就需要的人就會有很強的受挫感，會影響其工作的動力。 2．亞當斯的公平理論． 理論內容； 公平理論是美國心理學家亞當斯于20世紀60年代首先提出了一種激勵理論，又稱為社會比較理論。公平理論認為，激勵中的一個重要因素是個人的報酬是否公平，個人主觀地將自己投入(諸如努力、經濟、教育等許多因素)同別人相比，看自己所得的報酬是否公正或公平。如果認為自己所獲得的報酬不公平，就可能產生不滿，降低產出的數量、質量，甚至離開這個組織；如果認為報酬是公平的，就會繼續在同樣的產出水平上工作；如果認為個人報酬比認為的公平報酬大，則會更加努力地工作。 該理論還指出，職工的某些不公平感雖然可以暫時忍耐，但如果長時間維持，將會帶來嚴重的后果。3．這種解釋不會讓陳華感到滿意，可以說沒有什么作用．因為陳華需要的不是對這件事本身給出一個復雜或簡單的理由，而是需要對這個事件所反映的深層次的問題給予解釋，即長久以來以及今后自己在公司中處于什么樣的地位的問題，李江華的解釋只能使陳華理解為“在公司里你無所謂，只是非常普通的一個成員”，同時還透露了一個更加不好的信息，“公司非常需要編程分析員，你不是公司可以依賴的力量，你還不如一個新人”，那么賴以支撐其努力工作的力量就不復存在了。4.如果重視老員工的作用，就不應當忽視他們的心理需求，公司有許多措施可以采取，最主要的是增加陳華的公平感。如果按照程序無法盡快增加陳華的薪水，那么就應該采用其他方式提高其成就滿足感覺，讓其心理狀態至少感覺公平．比如職務提升、工作豐富化、委任陳華擔任新聘人員的指導教師等等。 四、簡答題(本大題共4小題，每小題5分，共20分)1.甲、乙兩人一同大學畢業后進了同一家企業并同在一間科室工作，兩人的工資也被定在同一檔次：每月1000元。一年試用期過后，甲的工資被定為每月1200元，而乙的工資被定為每月1500元。甲拿到1200元工資后很高興，因為比原來工資增加了200元，但當他得知乙的月工資是1500元后，則十分氣憤，工作積極性明顯下降。試通過公平理論分析甲的心理以及管理者的對策。答：（1）公平理論認為，職工的工作動機主要受工資報酬的影響，包括絕對報酬（自己實際收入的數量）與相對報酬（自己實際收入與他人實際收入的比值）兩種。每個人都會自覺或不自覺地把自己付出的勞動和所得報酬與他人付出的勞動和所得報酬進行橫向比較，也會把自己現在付出的勞動和所得報酬與自己過去付出的勞動和報酬進行縱向比較。通過比較，如果發現自己的收支比例與他人的收支比例相等，便認為是正常的、合理的，因而心情舒暢，安心工作；如果發現自己的收支比例低于他人的收支比例，或現在的收支比例低于過去的收支比例，就會產生不公平感，就會對工作態度、工作積極性產生消極影響。在本案例中，甲做縱向比較時的高興在于與過去比其工資增加了200元；但當他與乙進行橫向比較時，發覺自己的工資比乙少了300元，由此產生不公平感，導致工作積極性明顯下降。 （2）管理者應對甲、乙兩人的工資差異進行認真分析，如果原因在于乙比甲能力強、貢獻大，應時及對甲作出解釋，使甲重新認定自我、找出差距所在、明確努力的方向，激發甲的工作積極性；如果原因在于管理者對甲、乙的能力與貢獻判斷失誤，應及時、果斷的糾正失誤，重新制定甲、乙的工資標準。 2.俗話說“貨比三家”，消費者購物時往往在心理上要經歷一個復雜的過程。在購買商品時，消費者首先借助感知與表象獲得感性認識，再經過思維獲得理性認識，再加以反復比較，以決定是否購買。試由以上過程分析認識中感知與思維的關系。答：（1）人們對事物的認識過程，也就是人們對客觀事物個別屬性的各種不同感覺加以聯系和綜合的反映過程，這個過程主要是通過人的感覺、知覺、記憶、思維等心理活動來完成的。消費者對商品的認識過程，就是從感知到思維的過程，感知是形成表象并產生思維的直接基礎。 （2）感覺是對事物個別屬性的認識，是認識過程的開端；在感覺的基礎上，人們對事物的個別屬性加以綜合分析，形成知覺，對事物有了較完整的形象。感覺、知覺是認識的初級階段――感性認識階段。 （3）人們為加強對事物的認識，還借助記憶把過去生活實踐感知過的東西、體驗過的情感或知識經驗，在頭腦中重復反映出來。人們對事物的認識過程，不僅通過感知去認識事物的外在聯系，琮以表象的形式向思維過渡，進一步認識事物的一般特征和內在聯系，全面地、本質地把握事物的本質。這個思維過程（包括記憶過程）是人們對客觀事物在頭腦中概括的、間接的反映，是認識的高級階段――理性認識階段。 3.心理學家曾作過一項實驗，這項實驗分兩段進行：第一段，向四組大學生介紹一個陌生人。對第一組說，這是一個外傾型的人；對第二組說，這個人是內傾型的；在第三組，先講述這個人的我外傾特征，后講述他的內傾特征；在第四組，先講述這個人的內傾特征，后講述他的外傾特征。然后，讓這四個組學生分別想象出對這個陌生人的印象。第一組和第二組學生得到的印象是顯然易見的。在第三和第四組中，關于這個陌生人的印象完全符合提供信息的順序，總是先提供的信息占優勢。也就是說，第三組學生普遍把陌生人想象為外傾型，第四組普通把他想象為內傾型。第二段，給另外兩級學生按上述第三和第四組同樣的順序描述一個人，所不同的是在先描述他的內傾或外傾特征之后，中間插做其他事情，如讓學生作一些不太復雜的數學習題，然后再描述相反的性格特征。在這種情況下，最后描述的特征會使學生留下深刻的印象。試分析該實驗所提示的心理效應。答：（1）該實驗證明了優先效應和近因效應的客觀存在。其中，第一段實驗說明了優先效應的存在；第二段實驗說明了近因效應的存在。優先效應是指一個人最先給人留下的印象有強烈的影響，它與第一印象的作用是相同的；近因效應則是指最后給人留下的印象具有強烈的影響。 （2）該實驗不僅證明了優先效應和近因效應的客觀存在，而且證明了兩種效應發生作用的不同條件。一般來說，在感知陌生人時優先效應起著更大的作用；而在感知熟悉的人時，如果在熟悉的人的行為上出現某種新異的表現，則近因效應起更大的作用。 4.當我們看到教室的講臺時，我們幾乎在獲得該講臺的知覺的同時，賦予了這張講臺在教學工具方面的意義。這是思維的結果，講臺是直接的、具體的，但教學工具則是間接的，抽象的。試分析上述現象所表明的知覺與思維的關系。 答：該材料表明，在人的心理活動過程中，知覺與思維密不可分：知覺是思維的“窗口”，為思維提供感學信息；思維對感覺信息進行加工處理，把知覺組織起來，使知覺獲得一定的意義。思維是對客觀事物間接的、抽象的反映，知覺則是對客觀事物直接的、具體的反映。 案例題2： 7.一企業有兩個生產同類產品的車間，A車間的凝聚力明顯弱于B車間，但A車間的生產效率又明顯高于B車間。 請分析以上現象的成因以及上級主管部門提高B車間生產效率的對策。答：（1）對群體凝聚力與群體生產效率之間的關系的研究表明，凝聚力的狀況對生產效率有著重大的影響，誘是除凝聚力外的另一重要變量，兩者共同影響生產效率。無論凝聚力強弱如何，積極誘導都能提高生產效率，并且在凝聚力強的組生產效率更高；而消極誘導則明顯降低了生產效率，并且在凝聚力強的組生產效率更低。此外，凝聚力強的群體比凝聚力弱的群體更易受誘導因素的影響，在積極誘導條件下凝聚力強的群體的生產效率更高，在消極誘導條件下凝聚力強的群體的生產效率反而更低。在本案例中，A車間雖然凝聚力弱于B車間，但車間主管理采取的是積極誘導方式；而B車間雖然凝聚力強于A車間，但車間主管采取的是消極誘導方式，而且正因為其凝聚力強，所以在消極誘導下，其生產效率則更低。（2）從管理角度講，上級主管部門應對B車間主管的思想狀況、態度、動機等方面進行了解，在此基礎上對其進行教育，勸其糾正自己對車間群體的誘導方式；如拒不糾正，可考慮撤換其職務。 8.知識分子階層出身的人，舉止比較文雅、有修養，待人禮貌，但愛幻想，不大喜歡深交，遇事缺乏果斷性；農民階層出身的人，作風樸素，不怕苦和累，憨厚老實，但有時有自卑感，有點倔強固執；工人階層出身的人，集體主義強、守紀律，情感較強烈直爽，講究實際。上述材料反映了什么現象？試分析其原因。答：（1）上述材料表明：不同階層的人具有明顯的個性差異。 （2）階級和階層因素是影響個性形成的重要因素。人總是生活在一定的社會中，在階級社會或有階級的社會里又必然是屬于一一的階級或階層的成員，作為階級或階層的成員，所形成的個性不可避免地要打上本階級或階層的烙印。 9.美國社會心理學家阿希做了一個實驗。他給被試者看一張列有聰明、靈巧、勤奮、堅定、熱情等五種品質的表格，要求被試者想像一個具有這五種品質的人。被試者普遍把具有這五種品質的人想像為一個理想的友善的人。然后，他把這張表格中的熱情換為冷酷，再要求被試者根據這五種品質想像出一個適合的人。結果發現，被試者普遍推翻了原來的形象，而產生了一個完全不同的形象。上述實驗說明了什么問題？如何克服該實驗所揭示的效應？ 答：（1）該實驗表明：表格所列的最后那種品質起著暈輪作用，影響了對一個人的總體印象。暈輪效應是指我們在觀察某個人時，對于他的某種品質或特征有清晰明顯的知覺，由于這一特征或品質從觀察者的角度來看非常突出，從而掩蓋了對這個人其他特征和品質的知覺，由一點作出對這個人整體面貌的判斷。 （2）暈輪效應的產生，往往是個體在掌握有關知覺對象信息很少的情況下作出總體判斷的結果，或是只從自己的偏好出發，帶著個人偏見去衡量別人的結果。要克服暈輪效應，必須在社會知覺過程中，堅持認識人與事的全面性、動態性和客觀性。①要在深入了解和全面觀察、分析一個人的言行后，才對其作出評價；②要用發展的眼光看待人與事，切忌用靜止的眼光和成見去“蓋棺定論”；③要以客觀的標準評價人，不以自己的好惡為標準。 10.原蘇聯心理學家彼得羅夫斯基設計了一個實驗：被試者是一些四年級、七年級和九年級的學生。給學生一張問卷，其中有幾條關于道德問題的判斷，學生應對這些判斷表示贊成或反對。問題很簡單，每個學生都能根據公認的準則作出回答。過了一段時間之后，把這些道德的判斷列入一張更長的項目單之中，而在學生回答之前給予暗示，指明其他人都贊成的錯誤的判斷。在這種情況下，只有極少接受暗示、屈從壓力而改變其原來的主意，絕大多數人并沒有改變主意。試分析這一實驗所揭示的問題。答：（1）該實驗表明，群體的壓力并不是人們改變主意的關鍵因素，在這種情況下關鍵因素是遵循集體的崇高思想、目的和價值觀念，具有“集體主義自決”品質的人只在非原則性問題上表現出順從，而在原則性問題上則堅持已見。 （2）一個人接受多數人的意見，可能是屈服于壓力，怕被孤立；也可能是為了實現群體的理想和信念而采取與群體保持一致的措施，即“集體主義自決”。“集體主義自決”指的是以集體主義思想為指導，對群體的意見經過獨立分析之后所作出的行為瓜，當認為群體的意見正確時予以支持，并非由群體的壓力改變了他的意見；當認為群體的意見是一種原則性錯誤時，則抗拒群體的壓力，堅持不從眾。 31.指出管理過程學派的創始者，并簡要說明該學派的基本觀點。 答案：管理過程學派的創始者是法約爾。法約爾的著述很多，1916年出版的《工業管理和一般管理》是其最主要的代表作，標志著一般管理理論的形成。他的研究則是從辦公桌前的總經理出發的，把辦公桌前的總經理當作管理者作為研究對象。他認為，管理理論是指有關管理的、得到普遍承認的理論，是經過普遍經驗檢驗并得到論證的一套有關原則、標準、方法、程序等內容的完整體系。 法約爾將管理活動分為計劃、組織、指揮、協調和控制等五大管理職能，并進行了相應的分析和討論。法約爾認為管理的五大職能并不是企業管理者個人責任，它同企業經營的其它五大活動一樣，是一種分配于領導人與整個組織成員之間的工作。 32.簡要說明例行問題及處理例行問題的特點。 答案：例行問題的特點：從根本上說，不是要每次都作決策，而是要建立某些制度、規則或政策，使得當問題重復發 生時，不必再作決策，而只需根據已有的制度和規則按例行程序處理即可。 33.簡述管理工作中應如何適當地限制職能職權。答案：適當限制職能職權的使用： 限制使用范圍——限于解決如何做、何時做等方面的問題，再擴大就會取消直線人員的工作； 限制使用級別——下一級職能職權不應越過上一級直線職權 34.簡要說明主管間輪換的優缺點。 答案：在主管職位間輪換。這種輪換是在組織的同一層次上的各個不同部門的主管職務上進行的。這種輪換的目的是使將要提拔到較高層次的主管人員，在不同的職務上根據各部門的不同特點，學習實際的管理經驗。這種方法不要求主管人員對部門活動有很深的了解，而是強調他們全面管理技能的提高，使他們積累在不同管理部門的經驗，以勝任較高層次上的管理工作。這種輪換的優點是可以開闊主管人員的視野，了解各部門的特點及其相互關系，培養全面綜合管理能力；同時，也可以從中考察他們的適應能力和實際的管理能力。缺點則是這種輪換會影響各個部門的相對穩定性。 2008—2009學第一學期《管理學基礎》試題及答案 1．關于管理的含義，下列選項中(C)的表述不確切。A.激勵、約束 B．協調、溝通 C．放任、自由 D.理順、調整 2．梅奧等人通過霍桑試驗提出了不同于古典管理理論的新觀點和新思想，創立了(B)A.人文關系學說 B．人際關系學說 C.行為科學學說 D．社會關系學說 3．下列關于計劃工作基本特征的描述不準確的是(A)。A．計劃是高層管理者的職責范疇 B．計劃工作居首要地位 C.計劃工作是有目的的行為 D．計劃工作要講究效率 4．企業目標并不是一成不變的，應根據外部環境的變化及時調整與修正，使其更好 地實現企業的宗旨，這就是確定企業目標的(C)原則。A．現實性 B．協調性 C.權變性 D．關鍵性 5．下面決策方法中，選項(D)具有“匿名性”的特點。A.群眾評議法 B．哥頓法 C.頭腦風暴法 D．特爾菲法 6．銷售人員意見綜合預測方法主要適用于(A)。A．市場預測 B．長期預測 C．戰略規劃預測 D．財務預測 7．某產品有三個生產方案，其成本狀況為：甲方案固定成本為5000，單位變動成本為lOO；乙方案固定成本為12000，單位變動成本為60；丙方案固定成本為30000，單位變動成本為30。若丙方案為最佳方案，則產量為(D)。A．150 B．300 C.500 D．700 8．20世紀初期，有一位社會學家提出了建立“理想的組織模式”的設想，他就是(C)A.巴納德 B．孔茨 C.韋伯 D．厄威克 9．如果企業進行小批量產品的生產，那么，它需要根據顧客的要求進行設計、生產，對企業人員技術水平要求較高，這種企業適于采用(B)組織形式。A.集權式 B．分權式 C.均權式 D．不確定 lo．評價管理者的領導能力和影響能力，有關信息的獲得來源于(B)。A.上級人員 B．下屬人員 C.高層領導 D．協作部門 11．領導理論的發展大致經歷了三個階段，(A)側重于研究領導人的性格、素質方面的特征。A．性格理論階段 B．行為理論階段 C.效用領導階段 D．權變理論階段 12．布萊克和莫頓在管理方格理論中對最具代表性的五種領導類型進行了詳細分析，其中任務式領導的特點是(A)。A．對生產和工作的完成情況很關心，很少注意下屬的士氣、情緒和發展狀況 B．對生產和人的關心度都很小，領導僅扮演“信使”的角色 C.注重創造一種良好的人際環境，不關心任務完成情況 D．對人和任務都給予中等程度的關心，維持正常的生產效率和說得過去的土氣 13．控制系統是由控制主體、控制客體和控制媒體組成的具有自身目標和功能的管理系統。其中控制主體是指(D)。A．具有主次之分的一個組織的全部行為活動 B．控制行為所需的媒介物或方式 C.控制活動所針對的人、財、物和信息 D．控制活動中的各級管理人員及其所屬的職能部門 14.下列對現代沖突理論的理解不確切的是(A)。A．沖突可以為組織帶來活力，因此管理者要制造各種沖突 B．管理者的任務主要是管理好沖突，減少不利影響 C．沖突具有正面和反面、建設性和破壞性兩種性質 D．適當的沖突可以給組織帶來好處 15．下列關于管理幅度與管理層次的描述正確的是(A)。A．管理幅度與管理層次共同決定組織規模 B.為了保證管理效果，管理幅度越大越好 C．當組織規模一定時，管理幅度與管理規模成正比關系 D。管理幅度越窄，管理層次就越多，組織結構就呈扁平型 二、判斷并改錯(下列各題有對有錯，對的劃√；錯的劃X并改正。16．泰羅科學管理的中心問題就是提高勞動生產率。() 17，計劃工作是講求效率的。因此，制定計劃時必須考慮經濟效益，其他的都是次要的。()18．組織作為人的集合，就是每個人的加總。()19．運用頭腦風暴法進行預測關鍵是要取得參與人員的一致意見。()20．當外部環境處于劇烈變化狀態時，企業可以通過建立一些臨時性的部門、通暢的信息傳遞、分權程度的提高，發揮員工的潛力，減少外部環境對企業造成的不利影響。()21．扁平型組織結構有利于領導控制，但會影響下屬的工作積極性。()22．阿吉利斯認為，領導方式會影響人的成熟過程，如果讓職工長期從事簡單的重 復性工作會造成依賴心理，從而阻礙其向成熟發展。()23．表彰和獎勵能起到激勵的作用，批評和懲罰不能起到激勵的作用。()24，全面質量管理強調的是全員參與和全過程的質量管理。()25．現代沖突理論認為，管理者應盡可能防止和消除沖突。() 一、單項選擇(請從四個選項中選擇一個最優答案的字母填入括號。每小題2分，共30分)1．C 2．B 3．A 4．C 5．D 6．A 7．D 8．C 9．B 10．B 11．A 12．A 13．D 14．A 15．A 二、判斷并改錯(下列各題有對有錯，對的劃√；錯的劃X并改正。每小題2分，共20分)16．(√)。17．(X)制定計劃時除了考慮經濟效益外，還要考慮非經濟方面的因素。18．(X)組織作為人的集合，不是簡單的毫無關聯的個人的加總，而是為了實現一定目的，有意識地協同勞動而產生的群體。19．(X)運用頭腦風暴法進行預測的關鍵是引起思想共振，產生創造性思維。20．(√)21．(X)扁平型組織結構有利于信息溝通，有利于調動下級人員的積極性。22．(√)23．(X)獎勵和懲罰不一定能起到激勵作用，只有得當的獎勵和懲罰，才能起到有效的激勵作用。24．(√)25．(X)現代沖突理論認為，管理者要管理好沖突，減少不利影響，充分發揮積極作用。 《數據結構》自考復習思考試題 一、單項選擇題(本大題共15小題，每小題2分，共30分)在每小題列出的四個備選項中只有一個是符合題目要求的，請將其代碼填寫在題后的括號內。錯選、多選或未選均無分。 1.若將數據結構形式定義為二元組(K，R)，其中K是數據元素的有限集合，則R是K上（） A.操作的有限集合B.映象的有限集合 C.類型的有限集合D.關系的有限集合 2.在長度為n的順序表中刪除第i個元素(1≤i≤n)時，元素移動的次數為（）A.n-i+1 B.i C.i+1 D.n-i 3.若不帶頭結點的單鏈表的頭指針為head，則該鏈表為空的判定條件是（）A.head==NULL B.head->next==NULL C.head!=NULL D.head->next==head 4.引起循環隊列隊頭位置發生變化的操作是（）A.出隊 B.入隊 C.取隊頭元素 D.取隊尾元素 5.若進棧序列為1，2，3，4，5，6，且進棧和出棧可以穿插進行，則不可能出現的出棧序列是（）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.索引存儲和鏈式存儲 C.順序存儲和鏈式存儲 D.散列存儲和順序存儲 7.設主串長為n，模式串長為m(m≤n)，則在匹配失敗情況下，樸素匹配算法進行的無效位移次數為（）A.m B.n-m C.n-m+1 D.n 8.二維數組A［12］［18］采用列優先的存儲方法，若每個元素各占3個存儲單元，且第1個元素的地址為150，則元素A［9］［7］的地址為（）A.429 B.432 C.435 D.438 9.對廣義表L=((a,b),(c,d),(e,f))執行操作tail(tail(L))的結果是（）A.(e,f) B.((e,f))C.(f) D.()10.下列圖示的順序存儲結構表示的二叉樹是（）11.n個頂點的強連通圖中至少含有（）A.n-1條有向邊 B.n條有向邊 C.n(n-1)/2條有向邊 D.n(n-1)條有向邊 12.對關鍵字序列(56，23，78，92，88，67，19，34)進行增量為3的一趟希爾排序的結果為（）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-樹中插入關鍵字引起結點分裂，則該結點在插入前含有的關鍵字個數為（） A.4 B.5 C.8 D.9 14.由同一關鍵字集合構造的各棵二叉排序樹（）A.其形態不一定相同，但平均查找長度相同 B.其形態不一定相同，平均查找長度也不一定相同 C.其形態均相同，但平均查找長度不一定相同 D.其形態均相同，平均查找長度也都相同 15.ISAM文件和VSAM文件的區別之一是（）A.前者是索引順序文件，后者是索引非順序文件 B.前者只能進行順序存取，后者只能進行隨機存取 C.前者建立靜態索引結構，后者建立動態索引結構 D.前者的存儲介質是磁盤，后者的存儲介質不是磁盤 二、填空題(本大題共10小題，每空2分，共20分)16.數據的邏輯結構在計算機存儲器內的表示，稱為數據的____________。17.刪除雙向循環鏈表中*p的前驅結點(存在)應執行的語句是____________。18.棧下溢是指在____________時進行出棧操作。 19.已知substr(s,i,len)函數的功能是返回串s中第i個字符開始長度為len的子串，strlen(s)函數的功能是返回串s的長度。若s=″ABCDEFGHIJK″,t=″ABCD″,執行運算substr(s,strlen(t), strlen(t))后的返回值為____________。 20.去除廣義表LS=(a1,a2,a3,??，an)中第1個元素，由其余元素構成的廣義表稱為LS的____________。 21.已知完全二叉樹T的第5層只有7個結點，則該樹共有____________個葉子結點。22.在有向圖中，以頂點v為終點的邊的數目稱為v的____________。 23.當關鍵字的取值范圍是實數集合時，無法進行箱排序和____________排序。24.產生沖突現象的兩個關鍵字稱為該散列函數的____________。 25.假設散列文件中一個桶能存放m個記錄，則桶“溢出”的含義是，當需要插入新的記錄時，該桶中____________。 三、解答題(本大題共4小題，每小題5分，共20分)26.假設以數組seqn［m］存放循環隊列的元素，設變量rear和quelen分別指示循環隊列中隊尾元素的位置和元素的個數。(1)寫出隊滿的條件表達式；(2)寫出隊空的條件表達式； (3)設m=40,rear=13,quelen=19,求隊頭元素的位置；(4)寫出一般情況下隊頭元素位置的表達式。 27.已知一棵二叉樹的中序序列為ABCDEFG，層序序列為BAFEGCD，請畫出該二叉樹。28.畫出下圖所示有向圖的所有強連通分量。 29.對7個關鍵字進行快速排序，在最好的情況下僅需進行10次關鍵字的比較。(1)假設關鍵字集合為{1,2,3,4,5,6,7}，試舉出能達到上述結果的初始關鍵字序列；(2)對所舉序列進行快速排序，寫出排序過程。 四、算法閱讀題(本大題共4小題，每小題5分，共20分)30.閱讀下列算法，并回答問題：(1)設順序表L=(3,7,11,14,20,51)，寫出執行f30(&L,15)之后的L；(2)設順序表L=(4,7,10,14,20,51)，寫出執行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 //圖的最大頂點數 typedef struct node { int adjvex; //鄰接點域 struct node *next; //鏈指針域 } EdgeNode; //邊表結點結構描述 typedef struct { char vertex; //頂點域 EdgeNode *firstedge; //邊表頭指針 } VertexNode; //頂點表結點結構描述 typedef struct { VertexNode adjlist［MaxNum］; //鄰接表 int n, e; //圖中當前的頂點數和邊數 } ALGraph; //鄰接表結構描述 下列算法輸出圖G的深度優先生成樹(或森林)的邊。閱讀算法，并在空缺處填入合適的內容，使其成為一個完整的算法。 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)假設數組L［8］={3,0,5,1,6,4,2,7}，寫出執行函數調用f32(L，8)后的L；(2)寫出上述函數調用過程中進行元素交換操作的總次數。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.已知帶頭結點的單鏈表中的關鍵字為整數，為提高查找效率，需將它改建為采用拉鏈法處理沖突的散列表。設散列表的長度為m，散列函數為Hash(key)=key%m。鏈表的結點結構為：。請在空缺處填入適當內容，使其成為一個完整算法。void f33(LinkList L, LinkList H［］, int m){//由帶頭結點的單鏈表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); } 五、算法設計題(本大題10分)34.假設以帶雙親指針的二叉鏈表作為二叉樹的存儲結構，其結點結構的類型說明如下所示： typedef char DataType;typedef struct node { DataType data; struct node *lchild, *rchild; //左右孩子指針 struct node *parent; //指向雙親的指針 } BinTNode;typedef BinTNode *BinTree;若px為指向非空二叉樹中某個結點的指針，可借助該結構求得px所指結點在二叉樹的中序序列中的后繼。 (1)就后繼的不同情況，簡要敘述實現求后繼操作的方法； (2)編寫算法求px所指結點的中序序列后繼，并在算法語句中加注注釋。數據結構標準答案 一、單項選擇題 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.存儲結構 17.q = p->pre;q->pre->next = p;p->pre = q->pre;free(q);18.棧空 19.“DEFG” //注意雙引號不能少 20.表尾 21.２^(I-2)+M/2 葉子結點． 22.入度 23.基數 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個關鍵自序列進行一趟快速排序，要進行n-1次比較，也就是基準和其他n-1個關鍵字比較。 這里要求10次，而71)= 10，這就要求2趟快速排序后，算法結束。所以，列舉出來的序列，要求在做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中查找數x, 找到，則刪除x，沒找到，則在適當的位置插入x，插入后，L依然有序.31.(1)FALSE //初始化為未訪問 (2)DSFTree(G, p->adjvex);//從相鄰結點往下繼續深度搜索(3)p = p->next;//下一個未訪問的相鄰結點 32.(1)L = { 0, 1, 2, 3, 4, 5, 6, 7 };(2)5次 33.(1)NULL //初始化 (2)p->next = H[ j ] //和下面一句完成頭插法(3)p = q; //繼續遍歷L 五、算法設計題(本大題10分)34.1) a)*px 有右孩子，則其右孩子為其中序序列中的后繼 b)*px 無右孩子，從*px開始回溯其祖先結點，找到第1個身份為左孩子的結點，找到，則該結點的父結點為*px的中序序列中的后繼。找不到，則無后繼。2)BinTNode * fintNext(BinTNode * px){ if(px-> rchild)return px->rchild;//*px 有右孩子 BinTNode *q, *qp; q = px;while(qp = q->parent){ //未回溯到根結點 if(qp->lchild == q)return qp;//找到1)b)所述結點 q = qp;//往上回溯 } return NULL;//未找到 }第二篇：數據結構試題及答案
第三篇：2013臺灣省數據結構試題及答案（推薦）
第四篇：管理學原理試題和大題答案
第五篇：數據結構試題及答案10
點擊咨詢 