搜索
合肥学院2013至2014学年第2学期数据结构与算法设计课程考试（A）卷系级专业学号姓名题号一二三四五六七八九十总分得分阅卷一、选择题：（2分×15=30分）1．栈和队列的共同特点是(A)。A、只允许在端点处插入和删除元素B、都是先进后出C、都是先进先出D、没有共同点2．以下数据结构中哪一个是非线性结构？(D)A、队列B、栈C、线性表D、二叉树3．下面程序的时间复杂为（B）。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)4．在一个单链表中，已知q结点是p结点的前趋结点，若在q和p之间插入s结点，则须执行（B）。A．s-next=p-next;p-next=sB．q-next=s;s-next=pC．p-next=s-next;s-next=pD．p-next=s;s-next=q5.设一组初始记录关键字序列为(45，80，55，40，42，85)，则以第一个记录关键字45为基准而得到一趟快速排序的结果是（C）。A、40，42，45，55，80，83B、42，40，45，80，85，88C、42，40，45，55，80，85D、42，40，45，85，55，806．设一个有序的单链表中有n个结点，现要求插入一个新结点后使得单链表仍然保持有序，则该操作的时间复杂度为（D）。A、O(log2n)B、O(1)C、O(n2)D、O(n)7.设有6个结点的无向图，该图至少应有(A)条边才能确保是一个连通图。A、5B、6C、7D、88．设连通图G中的边集E={(a，b)，(a，e)，(a，c)，(b，e)，(e，d)，(d，f)，(f，c)}，则从顶点a出发可以得到一种深度优先遍历的顶点序列为（A）。A、abedfcB、acfebdC、aebdfcD、aedfcb9.设散列表长m=14,散列函数H（K）=K％11，已知表中已有4个结点：r(15)=4;r(38)=5;r(61)=6；r(84)=7，其他地址为空，如用二次探测再散列处理冲突，关键字为49的结点地址是(D)。A、8B、3C、5D、910.设用邻接矩阵A表示有向图G的存储结构，则有向图G中顶点i的入度为（B）。A、第i行非0元素的个数之和B、第i列非0元素的个数之和C、第i行0元素的个数之和D、第i列0元素的个数之和11.设指针变量top指向当前链式栈的栈顶，则删除栈顶元素的操作序列为（D）。大题得分装订线命题教师胡春玲共5页，第1页A、top=top+1B、top=top-1C、top-next=top;D、top=top-next12.二叉树的第K层的结点数最多为(D)。A、2k-1B、2K+1C、2K-1+1D、2k-113.设有向无环图G中的有向边集合E={1，2，2，3，3，4，1，4}，则下列属于该有向图G的一种拓扑排序序列的是（A）。A、1，2，3，4B、2，3，4，1C、1，4，2，3D、1，2，4，314.设有一组初始记录关键字序列为(34，76，45，18，26，54，92)，则由这组记录关键字生成的二叉排序树的深度为（A）。A、4B、5C、6D、715.图的深度优先遍历类似于二叉树的(A)。A.先序遍历B.中序遍历C.后序遍历D.层次遍历二、填空题：（2分×10=20分）1．设顺序线性表中有n个数据元素，则在第i个位置上插入一个数据元素需要移动表中数据元素个数是n-i+1。2．设指针变量p指向单链表中结点A，指针变量s指向被插入的新结点X，则在p后进行插入操作的语句序列为（s-next=p-next;p-next=s）（设结点的指针域为next）。3.设有一组初始关键字序列为(24，35，12，27，18，26)，则第3趟直接插入排序结束后的结果的是122427351826。4．设某无向图G中有n个顶点，用邻接矩阵A作为该图的存储结构，则顶点i和顶点j互为邻接点的条件是A[i][j]=1。5.设二叉排序树的高度为h，则在该树中查找关键字key最多需要比较h次。6.设一组初始记录关键字序列(k1，k2，……，kn)是小根堆，则对i=1，2，…，n/2而言满足的条件为ki≤k2i且ki≤k2i+1(2i+1≤n)。7.下面程序段的功能是实现二分查找算法，请在下划线处填上正确的语句。structrecord{intkey;intothers;};intbisearch(structrecordr[],intk){intlow=0,mid,high=n-1;while(low=high){mid=(low+high)/2;if(r[mid].key==k)return(mid+1);elseif(kL-r[mid].key)high=mid-1;elselow=mid+1;}return(0);}8．若要对某二叉排序树进行遍历，保证输出所有结点的值序列有序排列，应对该二叉排序树采用______中序_遍历法。三、应用题：（5分×5=25分）1．设一棵树T中边的集合为{(A，B)，(A，C)，(A，D)，(B，E)，(C，F)，(C，G)}，要求用孩子兄弟表示法（二叉链表）表示出该树的存储结构并将该树转化成对应的二叉树。大题得分大题得分小题得分2．请画出下图的邻接矩阵和邻接表。3．设有一组初始记录关键字为(45，80，48，40，22，78)，要求构造一棵二叉排序树并给出构造过程。4．设有无向图G，要求给出用普里姆算法构造最小生成树和所走过的边的集合。小题得分小题得分小题得分装订线共5页，第2页5、假设一棵二叉树的先序序列是ABCDEFGHIJ和中序序列是CDBFEAIHGJ,请画出该树。四、算法阅读题：（12分）1、LinkListmynote(LinkListL)（7分）{//L是不带头结点的单链表的头指针if(L&&L-next){q=L；L=L－next；p=L；S1：while(p－next)p=p－next；S2：p－next=q；q－next=NULL；}returnL;}请回答下列问题：（1）说明语句S1的功能。查询链表的尾结点（2）说明语句组S2的功能。将第一个结点连接到链表的尾部，作为新的尾结点（3）设链表表示的线性表为（a1,a2,…,an）,写出算法执行后的返回值所表示的线性表。返回的线性表为：（a2,a3,…an,a1）2．voidABC(BTNode*BT)（5分）{ifBT{ABC(BT-left);ABC(BT-right);visit(BT);}}该算法的功能是：后序遍历二叉树递归算法五、算法设计题：（13分）1．设计两个有序单链表的合并排序算法。（7分）小题得分大题得分小题得分小题得分大题得分小题得分共5页，第3页共5页，第4页2.设计在链式存储结构上交换二叉树中所有结点左右子树的算法。（6分）小题得分共5页，第5页装订线