2015年春季数据结构期末试卷(A卷)

《2015年春季数据结构期末试卷(A卷)》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、装订线华南农业大学期末考试试卷（A卷）2014-2015学年第2学期　考试科目：数据结构考试类型：（闭卷）考试　　　考试时间：　120　分钟学号姓名年级专业题号一二三四总分得分评阅人考生须知：1.答案必须写在“答卷”上，写在试卷上不得分；2.考试结束时，只回收答卷，不回收试卷；3.必须在答卷上正确填写班级、学号、姓名等内容，否则没有考试成绩。得分一、选择题（本大题共10小题，每小题2分，共20分）1、在存储数据时，通常不仅要存储各数据元素的值，而且还要存储（）。A．数据的处理方法B．数据元素的类型C．数据元素间的关系D．数据的存储方法2、某链表最常用的操作是在最后一个节点之后插入

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

3、*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+15装订线8、下列程序段的时间复杂度是（）。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的有序表上应用折半查找

4、法，在各元素查找概率相同的情况下平均查找长度为（）。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、一

5、份电文中使用了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、判断以下两序列是否为最小化堆？如不是，将其调整为堆，并采用图

6、的方式展示堆调整的过程。（1）（3，10，12，22，36，18，28，40）5装订线（2）（5，8，11，15，23，20，32，7）1、依据整数序列（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=(

7、BiTNode*)malloc(sizeof(BiTNode))))returnERROR;（1）（2）（3）}returnOK;}2、利用字符栈s，从终端接收一行并送至调用过程的数据区，#为退格符，&为退行符voidLineEdit(){SqStacks;charch,c;InitStack(&s);printf("请输入一个文本文件,^Z结束输入:");ch=getchar();while(ch!=EOF){while(ch!=EOF&&ch!=''){switch(