第一篇：数据结构试题大题编程及参考答案
数据结构考试题参考答案
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)，则利用筛选法建立的初始堆为___________________________。 v1324v213v31428.8.设某无向图G的邻接表为v413，则从顶点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
点击咨询 