数据结构与算法-考试样卷.doc

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