20121a普教《数据结构》a 数据结构试题.doc

湖北文理学院 2011－2012 学年度下学期 《数据结构与算法》试卷A 专业：计算机科学与技术 姓名： 学号： 班级： 题 目 一 二 三 四 五 总分 满 分 10 20 18 22 30 100 得 分 得分 评卷人 一、判断题（本题共10小题，每小题1分，共计10分）。 （正确的打√，错的打×） 1、顺序循环队列Q空的条件是：Q.front==Q.rear.( ) 2、关键路径是始点到终点最小长度的路径。( ) 3、序列（5, 6, 7, 20, 15, 8, 9, 25, 22，13）是一个堆。( ) 4、在插入排序和选择排序中，若原始记录已基本有序，则较适合选用选择排序 10、对任意一个图，从某顶点出发进行一次广度优先或深度优先遍历，可访问图的所有顶点。( ) 得分 评卷人 二、填空题（本题共10小题，每小题 2 分，共计 20分）。 （请将正确答案填入空格内，答案是确定和唯一的） 1、任意一棵具有n个结点的二叉树，若它有m个叶子，则该二叉树上度为1的结点数为_____个。 2、常用算法的描述方法有：自然语言 、 、 和流程图。 3、某二叉树的先根遍历序列为IJKLMNO，中根遍历序列为JLKINMO，则该二叉树中根结点的右孩子是 。 4、堆排序的时间复杂性为 ，空间复杂性为 。 5、二维数组A[6，7]，按行优先存储，每个元素占2个字节,A基址为600,则元素A[4,5]的存储地址是 。 6、对广义表C=（a,（b,c,d））的运算 Tail(Tail(Head((Tail(C))))的结果是 。 7、设有一组初始关键字值序列为（49，81，55，36，44，88），则利用快速排序的方法，以第一个关键字值为基准得到的一次划分为_________________________________________。 8、图的存储结构主要有两种，分别是 和 。 9、设一个顺序栈S，元素s1，s2，s3，s4，s5，s6依次进栈，如果6个元素的退栈顺序为s2，s3，s4，s6，s5，s1，则顺序栈的容量至少为________。对于一棵满二叉树，若有m个叶子，则树中结点数为____________。 三、选择题（本题共18小题，每小题 1分，共计 18 分）。 （从下列答案中选出一个正确答案，并将对应的字母填入括号内） 1．.循环队列存储在数组元素A[0]至A[m]中，则入队时的操作为( ) 。 A. rear=rear+1 B. rear=(rear+1)％(m-1)C. rear=(rear+1)％mD. rear=(rear+1)％(m+1)D. O(n2) 4. 在有n个叶子的哈夫曼树中，分支结点数为（ ）。 A、n B、n-1 C、n+1 D、2n 5. 有4个顶点的无向完全图的边数为( ) 。 A. 6 B. 12 C. 16 D. 20 6. 若采用邻接矩阵法存储一个n个顶点的无向图，则该邻接矩阵是一个 ( )。 A. 上三角矩阵 B. 稀疏矩阵 C. 对角矩阵 D. 对称矩阵 7. 从逻辑上可以把数据结构分为（　　）。 A. 动态结构、静态结构 B. 顺序结构、链式结构 C. 线性结构、非线性结构 D. 初等结构、构造型结构 8. 在单链表中，存储每个结点需要有两个域，一个是数据域，另一个是指针域，指针域指向该结点的（　　）。 A. 直接前趋 B. 直接后继 C. 开始结点 D. 终端结点 9. 若用一个有6个单元的数组来实现循环队列，rear和front的初值分别为0和3。则从队列中删除一个元素，再添加两个元素后，rear和front的值分别为（　　）。 A. 1和5 B. 2和4 C. 4和2 D. 5和1 10．含有n个结点的二叉树采用二叉链表存储时，空指针域的个数为（　　） 。 A. n-1 B. n C. n+1 D. n+2 11．一个有序表为{13，18，24，35