华农-117年第1学期-数据结构期末考试试卷A

1、华南农业大学期末考试试卷（A卷）2016-2017学年第1学期考试科目：数据结构考试类型：（闭卷）考试考试时间：120分钟学号姓名年级专业题号一二三四五总分得分评阅人得分一、选择题（本大题共10小题，每小题2分，共20分）1、数据结构是一门研究（）的程序设计问题中计算机的操作对象以及它们之间的关系和运算等的学科。A.数值计算B.非数值计算C.集合D.非集合2、在一个单链表中，若p所指结点不是最后结点，在p之后插入s所指结点，则执行（）。A.s->next=p;p->next=s;B.p->next=s;s->next=p;C.s->next=p->next;

2、p=s;D.s->next=p->next;p->next=s;）°B.删除操作更加方便D.通常不会出现栈满的情况3、链式栈与顺序栈相比，一个比较明显的优点是（A.插入操作更加方便C.通常不会出现栈空的情况4、串的长度是指（）。A.串中所含不同字母的个数C.串中所含字符的个数B.串中所含不同字符的个数D.串中所含非空格字符的个数5、设A是n*n的下三角矩阵（见右图）角线下方的元素以列为主序存放在一维数组,将A的对角线及对B中，则数组元素个数至少需要A.n*（n+1）/2C.n*ndll。31a22a32父分B.D.n*n/2(n+1)*(n+1)/26、在一棵具有5

3、层的满二叉树中结点总数为B.31()C.327、具有n个顶点的有向完全图有（）条弧。A.nB.n*n+1C.n*(n-1)D.n*n8、n个顶点的连通图至少有()条边。A.n-1B.nC.n+1D.09、就平均查找速度而言，下列几种查找速度从慢至快的关系是()。A.顺序查找B.顺序查找C.索引查找D.顺序查找折半查找索引查找折半查找哈希查找哈希查找折半查找哈希查找索引查找索引查找哈希查找顺序查找折半查找10、在下列算法中，(都不在其最终的位置上。)算法可能出现下列情况：在最后一趟开始之前，所有的元素A.堆排序B.冒泡排序C.插入排序D.选择排序得分二、判断题(本大题共10小题，每小题1分，共1

4、0分，注意：对的打，错的打“X”)()1、数据元素是数据的最小单位。()2、在单链表中，要取得某个元素，只要知道该元素指针即可，因此单链表是随机存储结构。()3、栈和队列都是线性表的一种，但它们对存取位置的限制不同。()4、串可以采用顺序存储，但不适宜采用链式存储。()5、二维数组是数组元素为一维数组的线性表，因此它是线性结构。()6、已知二叉树的前序遍历和后序遍历并不能唯一的确定这棵树，因为并不知道树的根结点是哪一个。()7、二叉树只能用二叉链表表示。()8、连通分量是无向图中的极小连通子图。()9、折半查找适用于有序的顺序表，不适用于有序的链表。()10、快速排序和归并排序在最坏情况下的比

5、较次数都是O(Nlog2N)。得分三、应用题(本大题共8小题，每小题5分，共40分)1、说出以下几种时间复杂度谁快谁慢：O(logn)、O(nlogn)、O(n)、O(10n)、O(n2)。2、设循环队列Q的最大长度为M,队头指针为Q.front,队尾指针Q.rear：(1)给出循环队列中元素个数的计算式。(2)给出循环队列的队空条件。(3)给出循环队列的队满条件。3、有一个二维数组A0:8,0:5,每个数组元素占用4个字节，假设存储数组元素A0,0的首地址是0,若按行存储，则A3,5的首地址是多少？若按列存储，则A5,3的首地址是多少？4、已知一棵二叉树的先序遍历序列为：AEFBGCDHIK

6、J，中序遍历序列为：EFAGBCHKIJD。试画出该二叉树的形态，并写出此二叉树的后序遍历序列。5、分别有权值为1、4、9、16、25、36、49、64的8个终端结点，请构造出一棵具有最小带权路径长度WPL的二叉树。6、设散列函数H(k尸Kmod7，散列表的地址空间为0-6,对关键字序列32,13,49,18,22,38,21按线性探测再散列法处理冲突的办法构造哈希表，并计算等概率下查找成功的平均查找长度ASL。7、画出为15个元素进行折半查找的判定树，并求出等概率下查找成功的平均查找长度ASL。8、已知一关键码序列为：3,87,12,61,70,97,26,45。试根据堆排序原理，填写完整下

7、示各步骤结果。建立初始堆结构：交换与调整：(1) 877026614512397;(3) 614526312708797;(4);261234561708797;(6);312264561708797。得分四、程序填空题(本大题共4小题，共10个空白处，每空2分，共20分，注意：每空只填一个语句)1、以下算法用于在顺序表L中第i个元素之前插入新元素e。相关定义如下：# defingOK1# defingERROR0# defineOVERFLOW-2typedefintStatus;typedefintElemType;typedefstructElemType*elem;/存储空间基地int

8、length;当前长度intlistsize;SqList;当前分配的存储容量StatusListInsert_Sq(SqList&L,inti,ElemTypee)/i的合法值为i>=1且i<=L.length+1if(1)returnERROR;/i值不合法if(L.length>=L.listsize)当前存储空间已满，增加分配newbase=(ElemType*)realloc(L.elem,(L.listsize+10)*sizeof(ElemType);if(!newbase)exit(OVERFLOW);L.elem=newbase;L.listsize

9、+=10;q=&(L.elemi-1);for(p=&(L.elemL.length-1);p>=q;-p)(2);# q=e;(3);returnOK;存储分配失败新基址增加存储容量/q为插入位置插入位置及之后的元素后移插入e/表长增12、以下函数用于在一个递增有序数组相关定义如下：ST中采用折半查找法确定元素位置的算法。/ListInsert_SqtypedefintKeyType;typedefstruct数据元素存储空间基址表长度KeyType*elem;intlength;SSTable;intSearch_Bin(SSTableST,KeyTypekey)/在

10、有序表ST中折半查找其关键字等于key的数据元素。若找到，则函数值为该元/素在表中的位置，否则为0。low=1;high=ST.length;/置区间初值while(low<=high)mid=(low+high)/2;if(key=ST.elemmid)找到待查元素returnmid;elseif(4);继续在前半区间进行查找high=mid-1;else(5);/继续在后半区间进行查找return0;顺序表中不存在待查元素/Search_Bin3、以下程序用于行编辑程序:接受用户从终端输入的字符,当用户发现刚刚键入的一个字符是错的时候，可补进一个退格符错较多时，可键入一个退行符相关定

11、义如下：“#'；表示前一个字符无效；如果发现当前键入的字符差“,表示当前行中的字符均无效。typedefintStatus;typedefintSElemType;typdefstructSElemType*base;SElemType*top;intstacksize;SqStack;StatusInitStack(SqStack&S);/栈基址栈顶指针栈的当前容量StatusPop(SqStack&S,SElemType&e);StatusPush(SqStack&S,SelemTypee);StatusStackTraverse(SqStackS,

12、visit);StatusClearStack(SqStack&S);StatusDestroyStack(SqStack&S);/构造一个空栈S若栈不空则删除S的栈顶元素插入元素e为新的栈顶元素将从栈底到栈顶的栈内字符输出重置S为空栈销毁栈SvoidLineEdit()/利用字符栈s,从终端接收一行并送至调用过程的数据区InitStack(S);scanf("%d",&n);ch=getchar();for(i=1;i<=n;i+)ch=getchar();while(ch!='n')switch(6)case'#&#

13、39;:Pop(S,c);break;case'':ClearStack(S);break;default:(8)构造空栈S输入需要接收处理的字符行数控制需要接收的字符行数/仅当栈非空时退栈/重置s为空栈/有效字符进栈/从终端接收下一个字符StackTraverse(S,visit);ClearStack(S);DestroyStack(S);/LineEdit/将从栈底到栈顶的栈内字符输出/重置s为空栈4、以下算法用于对一个无序序列进行冒泡排序。相关定义如下：#defineMAXSIZE20#defineTRUE1#defineFALSE0typedefintKeyType;

14、typedefstructKeyTyperMAXSIZE+1;intlength;SqList;/r0闲置或用作哨兵单位顺序表长度顺序表类型voidBubble(SqList&L)将顺序表L中的关键字序列重新排列成自小至大有序的整数序列for(i=L.length-1,change=TRUE;i>=1&&change;-i)(9);用于判断是否中止排序for(j=1;j<=i;+j)if(aj>aj+1)ajaj+1;交换位置(10);交换标志重置/Bubble得分五、算法设计题（本大题共1小题，每题10分，共10分，注意:先叙述算法设计思想，再写具体实现算法）1、设已有一个带头结点的单链表用来存放整数（无序），其头指针为L,要求编写一个函数查找表中数据域最小的结点，把它删除，并把其值用形参e返回给主调函数