《2013-2014第二学期数据结构期末试卷A卷.doc》由会员分享，可在线阅读，更多相关《2013-2014第二学期数据结构期末试卷A卷.doc（6页珍藏版）》请在金锄头文库上搜索。
1、 合肥学院20 13 至20 14 学年第 2 学期 数据结构与算法设计 课程考试（ A ）卷 系 级 专业 学号 姓名 题号一二三四五六七八九十总 分得分阅卷大题得分一、选择题：（2分15=30分）1栈和队列的共同特点是( )。A、只允许在端点处插入和删除元素 B、都是先进后出 C、都是先进先出 D、没有共同点2以下数据结构中哪一个是非线性结构？( )A、 队列 B、 栈 C、 线性表 D、 二叉树3下面程序的时间复杂为（ ）。for（i=1，s=0； i=n； i+） t=1；for(j=1；jnext=p-next; p-next=s Bq-next=s; s-next=pCp-next
2、=s-next; s-next=p Dp-next=s; s-next=q5. 设一组初始记录关键字序列为(45，80，55，40，42，85)，则以第一个记录关键字45为基准而得到一趟快速排序的结果是（ ）。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个结点，现要求插入一个新结点后使得单链表仍然保持有序，则该操作的时间复杂度为（ ）。A、 O(log2n)B、 O(1)C、 O(n2)D、 O(n)7. 设有6个结点的无向图，该图至少应有( )条边才能
3、确保是一个连通图。A、5 B、6 C、7 D、88设连通图G中的边集E=(a，b)，(a，e)，(a，c)，(b，e)，(e，d)，(d，f)，(f，c)，则从顶点a出发可以得到一种深度优先遍历的顶点序列为（ ）。A、 abedfc B、 acfebdC、 aebdfcD、 aedfcb9. 设散列表长m=14,散列函数H（K）=K11，已知表中已有4个结点：r(15)=4; r(38)=5; r(61)=6；r(84)=7，其他地址为空，如用二次探测再散列处理冲突，关键字为49的结点地址是( )。 A、 8 B 、3 C、 5 D 、910. 设用邻接矩阵A表示有向图G的存储结构，则有向图G
4、中顶点i的入度为（ ）。A、 第i行非0元素的个数之和B、 第i列非0元素的个数之和C、 第i行0元素的个数之和 D、 第i列0元素的个数之和命题教师 胡春玲 共 5 页，第 1 页11.设指针变量top指向当前链式栈的栈顶，则删除栈顶元素的操作序列为（ ）。A、 top=top+1 B、 top=top-1C、 top-next=top;D、 top=top-next 12. 二叉树的第K层的结点数最多为( )。A、2k-1 B、2K+1 C、2K-1 +1 D、 2k-113. 设有向无环图G中的有向边集合E=，则下列属于该有向图G的一种拓扑排序序列的是（ ）。A、 1，2，3，4B、 2
5、，3，4，1C、 1，4，2，3D、1，2，4，314. 设有一组初始记录关键字序列为(34，76，45，18，26，54，92)，则由这组记录关键字生成的二叉排序树的深度为（ ）。A、 4B、 5C、 6D、 715.图的深度优先遍历类似于二叉树的( )。 A.先序遍历 B.中序遍历 C.后序遍历 D.层次遍历大题得分二、填空题：（2分10=20分）1设顺序线性表中有n个数据元素，则在第i个位置上插入一个数据元素需要移动表中 数据元素个数是 。2设指针变量p指向单链表中结点A，指针变量s指向被插入的新结点X，则在p后进行插入操作的语句序列为（ ; ）（设结点的指针域为next）。3.设有一组
6、初始关键字序列为(24，35，12，27，18，26)，则第3趟直接插入排序结束后的结果的是 。4设某无向图G中有n个顶点，用邻接矩阵A作为该图的存储结构，则顶点i和顶点j互为邻接点的条件是 。5.设二叉排序树的高度为h，则在该树中查找关键字key最多需要比较 次。6.设一组初始记录关键字序列(k1，k2，kn)是小根堆，则对i=1，2，n/2而言满足的条件为 。7.下面程序段的功能是实现二分查找算法，请在下划线处填上正确的语句。struct recordint key; int others;int bisearch(struct record r , int k) int low=0,mi
7、d,high=n-1; while(lownext) q=L；L=Lnext；p=L； S1： while(pnext) p=pnext； S2： pnext=q；qnext=NULL； return L； 请回答下列问题： （1）说明语句S1的功能。 （2）说明语句组S2的功能。 （3）设链表表示的线性表为（a1,a2, ,an）,写出算法执行后的返回值所表示的线性表。 小题得分2void ABC(BTNode * BT) （5分） if BT ABC (BT-left); ABC (BT-right); visit(BT); 该算法的功能是： 大题得分五、算法设计题：（13分）小题得分1设计两个有序单链表的合并排序算法。（7分）共 5 页，第 4 页 装 订 线小题得分2.设计在链式存储结构上交换二叉树中所有结点左右子树的算法。（6分） 共 5 页，第 5 页
