算法与数据结构样卷-精品文档资料整理.doc

-密-封-线- （答题不能超出密封装订线）班级（学生填写）：姓名：学号：命题：审题：审批：20172018学年第 2 学期 算法与数据结构 科目 考试 试题 样卷闭卷考试；时间120分钟；可以使用没有记忆功能的普通计算器：否使用班级（老师填写）： 考务电话：2923688题号一二三四五六总分得分阅卷人一、单项选择题（本大题共15小题，每小题2分，共30分）。在每小题列出的四个选项中只有一个是符合题目要求的，请将其代码填在题后的括号内。错选或未选均无分。1. 算法指的（ ）A.计算机程序 B. 解决问题的计算方法 C. 排序算法 D. 解决问题的有限运算序列2. 线性表采用链式存储时，结点的存储地址（ ）A.必须是不连续的 B.连续与否均可 C.必须是连续的 D.和头结点的存储地址相连续3. 将长度为n的单链表链接在长度为m的单链表之后的算法的时间复杂度为（ ）A. O(1) B. O(n) C. O(m) D. O(m+n)二、填空题（本大题共10小题，每小题2分，若有两个空格，每个空格1分，共20分）。不写解答过程，将正确的答案写在每小题的空格内。错填或不填均无分。1数据的逻辑结构是从逻辑关系上描述数据，它与数据的 无关，是独立于计算机的。2在一个带头结点的单向循环链表中，p指向尾结点的直接前驱，则指向头结点的指针head可用p表示为head 。三、判断题（每题1分，共10分，在括号中填入“ü”或者“û”）( ) 1.不带头结点的单链表head为空的判定条件是head->next=NULL。( ) 2.散列法存储的基本思想是由关键码的值决定数据的存储地址。四、解答题（本大题共4小题，每小题5分，共20分）。1画出下列广义表的共享结构图形表示 P=(z),(x,y),(x,y),x),(z)ABCDEFGIJK2.请画出与下列二叉树对应的森林。 五、综合体（本大题共3小题，共20分）。rear0rear1front1front01假设两个队列共享一个循环向量空间（参见右下图）其类型Queue2定义如下：typedef struct DataType dataMaxSize; int front2,rear2; Queue2;对于i=0或1，fronti和reari分别为第i个队列的头指针和尾指针。请对以下算法填空，实现第i个队列的入队操作。（5分） int InQueue(Queue2 *Q,int i,DataType x) /若第i个队列不满。则元素x入队列，/并返回1；否则返回0if(i<0 | i>1) return 0;if(Q.>reari=Q->front return 0; Q->data =x; Q->reari= ; return 1; 2、阅读下列函数（10分） int arrange(int a,int l,int h,int x) /l和h分别为数据区的下界和上界 int i,j,t; i=l; j=h; while(i<j) while(i<j &&aj>=x) j-; while(i<j &&ai<x) i+; if(i<j) t=aj; aj=ai; ai=t; if (ai<x) return i; else return i-1; （1） 写出该函数的功能；（5分）（2） 写一个调用上述函数实现下列功能的算法：对一整数数组bn中的元素进行重新排列，将所有负数均调整到数组的低下标端，将所有正数均调整到数组的高下标端，若有零值，则置于两者之间，并返回数组中零元素的个数。（5分）第 5 页 共 5 页