数据结构与算法试卷A答案

《数据结构与算法》期末试卷本卷共3页第4页专业：专业：年级/班级：姓名：学号：装订线内不要答题地理信息系统、测绘工程、地理科学专业（本）11级《数据结构与算法》A卷（时间120分钟）题号一二三四五六七八总分分值3010103020100得分选择题（每题1.5分，共30分）1、下面哪一个不是线性表的特性（D）A.除第一个元素外，每个元素都有前驱B.除最后一个元素外，每个元素都有后继C.线性表是数据的有限序列D.线性表的长度为n，并且n不等于02、在一个单链表中，已知q结点是p结点的前驱结点，若在q和p之间插入s结点，则执行（C）A.s->next=p->next;p->next=s;B.p->next=s->next;s->next=p;C.q->next=s;s->next=p;D.p->next=s;s->next=q;3、若线性表采用链式存储，则表中各元素的存储地址（D）A.必须是连续的B.部分地址是连续的C.一定是不连续的D.不一定是连续的4、串是（D）A.一些符号构成的序列B.一些字母构成的序列C.一个以上字符构成的序列D.任意有限个字符构成的序列5、设输入的序列为1、2、3、4，则借助于一个栈可以得到的输出序列是（A）A.1342B.3142C.4312D.41236、栈和队列都是（C）A.顺序存储的线性表B.链式存储的线性表C.限制插入和删除位置的线性表D.限制插入和删除的非线性表7、将8阶对称矩阵A的下三角部分逐行存储到起始地址为1000的内存单元中，已知每个元素占4个字节，下标下界都为0，则A[7][4]的地址为（D）A.35B.36C.3400D.11288、有100个结点的完全二叉树，由根开始从上到下，从左到右对结点进行编号，根节点为1，则编号43的结点的左孩子的编号是（D）A.50B.48C.98D.869、对一颗n个结点的树，则该树中结点的度之和为（B）A.nB.n-1C.n+1D.不确定10、霍夫曼树中度为1的结点个数为（A）A.0B.1C.2D.不确定11、具有n个顶点的无向完全图，边的总数为（D）A.nB.n-1C.n+1D.n（n-1）/212、有n个顶点的连通图的最小生成树有（A）条边A.n-1B.nC.n+1D.不确定13、以邻接表作为图的存储结构，其深度优先遍历和广度优先遍历的时间复杂度都为（D）A.O(e)B.O(n)C.O(n-e)D.O(n+e)14、下列排序算法中，第一趟排序结束后，其最大或最小元素一定在其最终位置上的算法是（D）A.归并排序B.直接插入排序C.快速排序D.起泡排序15、快速排序的平均时间复杂度为（C）A.O(log2n)B.O(n)C.O(nlog2n)D.O(n2)16、数据元素是数据的基本单位，其内（C）数据项。A、只能包括一个B、不包含C、可以包含多个D、必须包含多个17、算法能正确地实现预定功能的特性称为（A）A、正确性B、易读性C、健壮D、高效率18、栈是限定在（C）处进行插入或删除操作的线性表。A、端点B、栈底C、栈顶D、中间19、队列是限定在（C）进行插入操作的线性表。A、端点B、队头C、队尾D、中间20、队列的特点是（A）A、先进先出B、后进先出C、先进后出D、不进不出二、判读正误题（每题1分，共10分）（√）1、O(1)+O(1)=O(1)（√）2、顺序表可以对存储其中的数据进行排序操作，链表也能进行排序操作（×）3、因为栈是一种线性表，所以线性表的所有操作都适用于栈（√）4、队列的“假溢出”现象是可以解决的（×）5、两个稀疏矩阵的和仍为稀疏矩阵（√）6、满二叉树是完全二叉树（×）7、后序遍历一个二叉树等于中序遍历其对应的树（×）8、霍夫曼树是完全二叉树（√）9、有n个顶点的连通图用邻接矩阵表示时，该矩阵至少有n个非零元素（×）10、对n个记录进行直接插入排序，其平均时间复杂度为O（nlog2n）三、算法阅读填空题（每题5分，共10分）1、写出算法划线语句的执行次数和x的结果x=0;for(i=0;i<10;i++){for(j=0;j<=i;j++)x=x+1;}执行次数55次x的结果552、循环队列入队intenqueue(cqueue*cq,ElemTypex){if((cq->rear+1)%MAXCSIZE==cq->front)return0;cq->base[cq->rear]=x;cq->rear=(cq->rear+1)%MAXSIZE;return1;}四、计算操作题（每题10分，共30分）1、给定如图1所示的带圈无向图G1.画出该图的邻接表存储结构；画出该图的邻接矩阵；给出prim算法构造最小生成树过程图1答：图的邻接表为：不带权值扣2分。图的邻接矩阵表示为：不带权值或权值都为1扣2分。Prim算法构造过程：结点1为初始点。2、已知一颗二叉树的中序遍历序列和后序遍历序列分别为：中序：CBEDAFIGH，后序：CEDBIFHGA。试画出这颗二叉树，并写出其先序遍历序列。答：此树为：此树的先序遍历序列为：ABCDEGFIH3、设权值集合W={10、4、8、13、5、18}，以W为基础，建立一颗霍夫曼树，并求出其WPL的值。答：此树的建立过程如下图所示：W={10,4,8,13,5,18}12346WPL=18*2+8*3+(4+5)*4+(10+13)*2=142五、算法设计题（每题10分，共20分）1、编写算法，删除单链表L中p指针指向结点的直接前驱。typedefintElemType;typedefstructNode{

ElemTypedata;

structNode*next;}LinkList//一级指针也可以。但p必须是指针变量，非指针扣1分。voidDelPreNode(LinkList*L,LinkList*p);voidDelPreNode(LinkList**L,LinkList*p)

{

LinkList**q=L;

while(q&&*q){

if((*q)->next==p){

*q=p->next;

free(p);

}(*q)=(*q)->next;

}

}2、设计一个算法，实现在顺序表上的起泡排序。参考答案：#defineMAXSIZE20//排序表的最大容量enumBOOL{False,True};//可以是int表示typedefstruct//定义排序表的结构{intelemword[MAXSIZE];//数据元素关键字intcount;//表中当前元素的个数}SeqList;voidBubbleSort(SeqList&L){//对顺序表L做起泡排序。inti,j,t;BOO