数据结构与算法考试样卷

样卷公开本样卷仅对考试题型进展说明，不代表最终考试内容。请根据考试大纲全面复习。第20XX-20XX学年第X学期考试卷课程代码：SS1005课程名称：数据构造与算法考试时间：90分钟考试形式：闭卷试卷类型：A学分：4题次分数评分一30二20三30四20总分100评卷人一、单项选择题〔共15小题，每题2分，共30分〕在每题列出的选项中只有一个选项符合题目要求，将正确选项前的字母填写在答题纸上。1.数据三种最主要的逻辑构造是树形构造和〔〕。A.线性表、二叉树C.线性表、图B.线性构造、图状构造D.树形构造、堆2.以下数据构造中，〔〕是线性数据构造。A．树B．图C．堆D．栈3.下面关于线性表的表达中，错误的选项是哪一个？〔〕A．假设线性表采用顺序存储构造，那么必须占用一片连续的存储单元。B．假设线性表采用顺序存储构造，那么便于进展插入和删除操作。C．假设线性表采用链接存储构造，那么不必占用一片连续的存储单元。D．假设线性表采用链接存储构造，那么便于插入和删除操作。4.p是指向单链表头结点的指针，假设该链表是空表，下面正确的说法是()。A.p==NULLB.p!=NULLC.p->next==NULLD.p->next==NULL5.在指针p指向单链表结点之后插入s所指结点的操作是：〔〕。A．p->next=s;B．s->next=p->next;p->next=s;C．s->next=p;D．s->next=p->next;6.存取数据时采用先进先出的原那么的数据构造是〔〕。A.队列B.栈C.字符串D.线性表7.假定栈用单链表的存储构造表示，栈的栈顶指针为top，当结点x入栈时执行的操作为()。A.x->next=top;C.top=x;B.top->next=x;top=x;D.x->next=top;top=x;8.队列的数据出队操作在〔〕进展。A.队尾位置B.队头位置C.任意位置D.中间位置9.树的度是指〔〕。A.树的结点数B.树的后继个数C.树中任一结点最大的后继数D.以上都不是10.具有8个叶子结点的二叉树中有〔〕个双支结点。A．7B．8C．9D．1011.下面对完全二叉树描述正确的选项是〔〕。A.所有层的结点数都必须是满的B.除最后一层，其它层上的结点数都必须是满的C.最后一层的结点数不能是满的D.以上都不是12.将100个元素散列到10000个单元的散列表中，那么〔〕产生冲突。A.一定会B.一定不会C.仍可能会13.假定利用数组a表示一个栈，用top保存栈顶位置，top=-1表示栈空，栈中有数据，当元素x进栈时的操作为〔〕。A.a[--top]=x;B.a[top--]=x;C.a[++top]=x;D.a[top++]=x;14.n个顶点的无向图，至多有〔〕条边。A．n-lB．n(n-1)/2C．n(n+l)D．2n15.无向图G=(V,E),其中：V={a,b,c,d},E={(a,b),(a,c),(b,d),(c,d)}，对该图进展广度优先遍历，得到的顶点序列正确的选项是〔〕。A．a,c,b,dB．a,d,c,bC．a,c,d,bD．a,b,d,c二、填空题〔每空2分，共20分〕答案写在答题纸上1．数据三种最主要的逻辑构造是线性构造、树形构造、图形构造。2．在线性构造中，第一个结点没有直接前驱，最后一个结点没有直接后继3．在定义一个过程或函数时出现调用本过程或本函数的成分，称之为递归。。4．分析下面程序段中带下划语句的执行次数4。inti=0;s=0;n=300;do{i=i+1;s=s+10*i;}while(i<n&&s<n);5．采用顺序存储构造的线性表中，表的长度为n，删除线性表中第i个元素〔1<=i<=n〕一个元素时，需向前移动____n-i+1______个元素。6．在二分〔折半〕查找算法的前提条件是查找表中的数据必须是表中元素必须有序。7．表达式a/(b+c)*d对应的后缀表达式是abc+*d-。8．写出下面二叉树的后序遍历结果DBFGCA。三、简答题〔4小题，共30分〕将答案写在答题纸上1．设对数据ABCD执行一系列的进出操作，假设数据出栈的顺序是BACD，写出相应的数据进出栈的操作顺序。〔6分〕2．一组数据的排序码为：｛46，53，40，38，74，16，88｝，要求排序后数据从小到大升序排列，写出利用简单项选择择排序的方法排序时经过3趟排序后的结果。〔8分〕3．画出下面图所对应的邻接矩阵〔8分〕4．设给定关键字输入序列为〔48，27，61，95,38〕,散列表的存储地址范围是0～10，如采用开放地址法线性探查法解决冲突。〔8分〕a.设计合理的散列函数；b.构造出包含给定关键字的散列表。四、设计题〔共2小题，共20分〕将答案写在答题纸上1．数组A和数组B中的数据分别是有序，编写算法将数组A和B中的数据合并到数组C中，并保证C中的数据也是有序的，用文字描述算法执行的步骤。(10分)2．设计函数Node*Get