南昌大学数据结构2009～2010学年第1学期期末试卷B.doc

第  PAGE 7 页 共  NUMPAGES 7页 南昌大学 2009～2010学年第一学期期末考试试卷 试卷编号： ( B )卷 课程编号： 课程名称： 数据结构 考试形式： 闭卷 适用班级： 姓名： 学号： 班级： 学院： 专业： 考试日期： 题号一二三四五六七八九十总分累分人 签名题分2020202020 100得分 考生注意事项：1、本试卷共 6页，请查看试卷中是否有缺页或破损。如有立即举手报告以便更换。 2、考试结束后，考生不得将试卷、答题纸和草稿纸带出考场。 单项选择题 (每小题1分，共20分) 得分评阅人 1．下列选项中，不是算法基本特征的是 。 A．可行性 B. 有穷性 C. 确定性 D.高效率 2.一个栈的入栈序列是a,b,c,d,e，则栈的不可能输出序列是 。 A．edcba B. decba C. dceab D. abcde 3．用数组A[m]存放循环队列的元素值，若其头尾指针分别为front和rear，则循环队列中当前元素的个数为 。 A．(rear+front)%m B．(rear-front+m)%m C．(rear-front)%m D．(rear-front+1)%m 4. 栈和队列的共同点是 。 A. 都是先进后出 B. 都是先进先出 C. 只允许在端点处插入和删除元素 D. 没有共同点 5. 按照二叉树的定义，具有3个结点的二叉树共有 种。 A. 3 B. 4 C. 5 D. 6 6. 深度为5的二叉树至多有 个结点。 A. 16 B. 32 C. 31 D. 10 7. 对一棵满二叉树，有m个树叶，n个结点，深度为h，则 。 A. n=h+m B. h+m=2n C. m=h-1 D. n=2h-1 8. 在一棵二叉树中有30个叶子结点，仅有一个孩子的结点有20个，则该二叉树共有 个结点 A、79 B、76 C、56 D、81 9. 采用线性链表表示一个向量时，要求占用的存储空间地址___________。 A. 必须是连续的 B. 部分地址必须是连续的 C. 一定是不连续的 D. 可连续可不连续 10. 在一个单链表中，若q结点是p结点的前驱结点，若在q与p之间插入结点s，则执行_________________。 A. s→link = p→link; p→link = s; B. p→link = s; s→link = q; C. p→link = s→link; s→link = p; D. q→link = s; s→link = p; 11. 如果想在4092个数据中只需要选择其中最小的10个，采用（ ）方法最好。 A. 起泡排序 B. 堆排序 C. 直接选择排序 D. 快速排序 12． 一个有2n个顶点的无向图最多有 条边。 A. n B. n(2n-1) C. n(n-1)/2 D. 2n 13. 对于哈希函数H(key)=key%13,被称为同义词的关键字是 A. 35和41 B. 23和39 C. 15和44 D. 25和51 14. n 个顶点的连通图至少有 条边。