搜索
1装订线华南农业大学期末考试试卷（A卷）2014-2015学年第2学期考试科目：数据结构考试类型：（闭卷）考试考试时间：120分钟学号姓名年级专业题号一二三四总分得分评阅人考生须知：1.答案必须写在“答卷”上，写在试卷上不得分；2.考试结束时，只回收答卷，不回收试卷；3.必须在答卷上正确填写班级、学号、姓名等内容，否则没有考试成绩。一、选择题（本大题共10小题，每小题2分，共20分）1、在存储数据时，通常不仅要存储各数据元素的值，而且还要存储（）。A．数据的处理方法B．数据元素的类型C．数据元素间的关系D．数据的存储方法2、某链表最常用的操作是在最后一个节点之后插入节点或删除节点，则采用（）存储方式最节省运算时间。A．单链表B．给出表头指针的单循环链表C．双链表D．有头结点的双循环链表3、一个栈的进栈序列是a、b、c、d、e，则不可能的出栈序列是（）。A．edcbaB．decbaC．dceabD．abcde4、二维数组M的每一个元素占用4个字节的存储空间，行下标i的范围从0到4，列下标j的范围从0到5，M按行优先存储时元素M[3][5]的地址与M按列优先存储时元素（）的地址相同。A．M[2][4]B．M[3][4]C．M[4][4]D．M[3][5]5、一个n*n的对称矩阵采用压缩存储，以行优先的方式放入内存，则占用的存储空间为()。A．n*nB．n*n/2C.n*(n+1)/2D．n*(n-1)/26、用希尔排序对一个数据序列进行排序时，若第1趟排序结果为9,1,4,13,7,8,20,23,15，则该趟排序采用的增量（间隔）可能是（）。A．2B．3C．4D．5。7、设高度为h的二叉树只有度为0和度为2的结点，则此类二叉树结点数至少为（）。A．2hB．2h-1C．2h+1D．h+1得分28、下列程序段的时间复杂度是（）。x=0;for(k=1;k=n;k=k*2)for(j=1;j=n;j++)x++;A.O(log2n)B.O(nlog2n)C.O(n2)D.O(n)9、在长度为12的有序表上应用折半查找法，在各元素查找概率相同的情况下平均查找长度为（）。A.35/12B.37/12C.39/12D.41/1210、一组记录的关键字为（41,79,56,38,40,84），使用快速排序法，以第一个记录为界点进行第一次划分后得到的结果是()。A．40,38,41,56,79,84B．40,38,41,79,56,84C．38,40,41,56,79,84D．40,38,41,84,56,79二、应用题（本大题共5小题，每小题6分，共30分，要求写出解题过程）1、已知一棵二叉树的中序序列为cbedahgijf，后序序列为cedbhjigfa，画出这棵树，并写出它的先序序列。2、一份电文中使用了8种字符a，b，c，d，e，f，g，h，每个字符出现的频率分别是7，19，2，6，32，3，21，10，为这8个字符设计哈夫曼编码，并画出对应的哈夫曼树。3、连通图有5个顶点V1、V2、V3、V4、V5，其邻接矩阵如下，画出这一连通图并使用普里姆算法求出它的最小生成树（要给出过程）。4、有一组关键字{19，1，23，14，55，2，84，27，68，11，10，78}，采用哈希函数：H（key）=key%13，采用线性探测再散列方法解决冲突，请在地址为0~18的存储空间中构建哈希表，并计算平均查找长度。5、判断以下两序列是否为最小化堆？如不是，将其调整为堆，并采用图的方式展示堆调整的过程。（1）（3，10，12，22，36，18，28，40）（2）（5，8，11，15，23，20，32，7）得分3装订线6、依据整数序列（1,12,5,8,10,7,13,9）的先后次序构造一棵平衡二叉树，画出每一次插入及平衡化处理的过程。三、程序填空题（本大题共5小题，共15个空白处，每空2分，共30分，注意：每空只填一个语句）1、以递归的方法先序创建二叉树，结点的值为字符型，’#’字符表示空树StatusCreateBiTree(BiTree&T){charch;scanf(%c,&ch);if(ch=='#')T=NULL;else{if(!(T=(BiTNode*)malloc(sizeof(BiTNode))))returnERROR;（1）（2）（3）}returnOK;}2、利用字符栈s，从终端接收一行并送至调用过程的数据区，#为退格符，&为退行符voidLineEdit(){SqStacks;charch,c;InitStack(&s);printf(请输入一个文本文件,^Z结束输入:\n);ch=getchar();while(ch!=EOF){while(ch!=EOF&&ch!='\n'){switch(ch){case'#':（4）break;case'@':ClearStack(&s);break;default:（5）}（6）}StackTraverse(s,copy);/*将从栈底到栈顶的栈内字符传送至文件*/ClearStack(&s);/*重置s为空栈*/得分4fputc('\n',fp);if(ch!=EOF)ch=getchar();}DestroyStack(&s);}3、输入n个元素的值，按输入次序建立带头结点的单链表voidCreateList(LinkList*L,intn){inti;LinkListp,q;*L=(LinkList)malloc(sizeof(structLNode));/*生成头结点*/(*L)-next=NULL;q=*L;printf(请输入%d个数据\n,n);for(i=1;i=n;i++){（7）scanf(%d,&p-data);（8）q=q-next;}（9）}4、对顺序表L作快速排序voidQSort(SqList*L,intlow,inthigh){/*对顺序表L中的子序列L.r[low..high]作快速排序。算法10.7*/intpivotloc;if(（10）){/*长度大于1*/pivotloc=Partition(L,low,high);/*将L.r[low..high]一分为二*/（11）/*对低子表递归排序，pivotloc是枢轴位置*/（12）/*对高子表递归排序*/}}voidQuickSort(SqList*L){/*对顺序表L作快速排序*/QSort(L,1,(*L).length);}5、对顺序表L作折半插入排序voidBInsertSort(SqList*L){inti,j,m,low,high;for(i=2;i=(*L).length;++i){(*L).r[0]=(*L).r[i];/*将L.r[i]暂存到L.r[0]*/5装订线low=1;high=i-1;while(（13）){/*在r[low..high]中折半查找有序插入的位置*/m=(low+high)/2;/*折半*/ifLT((*L).r[0].key,(*L).r[m].key)/*小于中点*/（14）;else（15）;}for(j=i-1;j=high+1;--j)(*L).r[j+1]=(*L).r[j];/*记录后移*/(*L).r[high+1]=(*L).r[0];/*插入*/}}四、算法设计题（本大题共2小题，每小题10分，共20分。请先简要说明算法思想，然后写出算法的C语言源代码实现）1、将头指针为a的单链表A分解成两个单链表A和B，表A头指针为a，表B的头指针为b，表A含有原单链表A序号为奇数的元素，而表B含有原单链表A序号为偶数的元素，且均保持原来的相对次序。单链表存储结构定义如下：structLNode{intdata;structLNode*next;};typedefstructLNode*LinkList;统一使用函数名：voidSplit(LinkList&A，LinkList&B)2、一个具有n个结点的完全二叉树采用顺序存储方式，其数据存放在整型一维数组a中，编写非递归算法对其进行先序遍历。算法可以直接调用栈的基本操作：初始化：InitStack(SqStack&S)入栈：Push(SqStack&S,inte)出栈：Pop(SqStack&S,int&e)判断栈空：Empty（SqStackS）统一使用函数名：voidpreorder(inta[],intn)得分