湖北省计算机类专业人才培养合作联盟联合考试试卷(数据结构b卷).doc

…………………………密……………………封……………………线………………………………学院专业级学号姓名…………………………密……………………封……………………线………………………………一、判断题(每小题1分,共10分)。2. 凡是为空的单链表都是不含任何节点的。3. 对顺序栈进行进栈、出栈操作,不涉及元素的前、后移动问题。4. 含有n个字符的字符串中所有子串的个数为n*(n+1)/2+1。5. 递归算法的执行效率比功能相同的非递归算法的执行效率高。6. 在n(n>3)阶三对角矩阵中,每一行都有三个非零的元素。7. 霍夫曼树中不存在度为1的节点。8. 强连通图不能进行拓扑排序。9. 二叉排序树是用来进行排序的。10. 排序的稳定性是指排序算法中比较的次数保持不变,且算法能够终止。二、填空题(每小题1分,共10分)1. 一个算法具备的5个特性分别是可行性、有穷性、______、输入和输出。2. 在有n个元素的顺序表中的任意位置插入一个元素所需移动元素的平均次数为______。3. 栈是一种具有______特性的线性表。4. 无论是顺序队列还是链式队列,插入和删除运算的时间复杂度都是______。5. 递归函数f(1)=1,f(n)=f(n-1)+n(n>1)的递归出口是______。6. 完全二叉树中节点个数为n,则编号最大的分支节点的编号是______。7. 对n个顶点的连通图来说,它的生成树一定有______边。8. 采用哈希存储方法时,用于计算节点存储地址的是______。9. 对二叉排序树进行______遍历,可以得到按关键字从小到大排列的节点顺序。,不比较关键字大小的排序方法是______。三、单向选择题(每小题2分,共30分)1. 算法的时间复杂度与______有关。A、问题规模 B、计算机硬件性能C、编译程序质量 D、程序设计语言2. 链表不具有的特点是______。A、可随机访问任一元素 B、插入删除不需要移动元素C、不必事先估计存储空间 D、所需空间与线性表长度成正比…………………………密……………………封……………………线………………………………学院专业级学号姓名3. 已知一个栈的进栈顺序是1,2,3,...,n,其输出序列是P1,P2,...,Pn,若P1=n,则Pi的值为______。A、i B、n-iC、n-i+1 D、不确定4. 设顺序循环队列中数组的下标是0~N-1,其头、尾指针分别为f(指向队头元素的前一个位置)和r(指向队尾元素),则其元素个数为______。A、r-f B、r-f-1C、(r-f)%N+1 D、(r-f+N)%N5. 将递归算法转换成对应的非递归算法时,通常需要使用______保存中间结果。A、队列 B、栈C、链表 D、树6. 若3叉树中有a个度为1的节点、b个度为2的节点、c个度为3的节点,则该树有______个叶子节点。A、1+2b+3c B、1+2b+3cC、2b+3c D、1+b+2c7. 若二叉树的中序遍历序列是abcdef,且c为根节点,则______。A、c左子树中有两个节点 B、二叉树有两个度为0的节点C、二叉树的高度为5 D、以上都不对8. 无向图的邻接矩阵是一个______。A、对称矩阵 B、零矩阵C、上三角矩阵 D、对角矩阵9. 在如图1所示的平衡二叉树中插入关键字50后,得到一棵新平衡二叉树,在新平衡二叉树中,关键字37所在的节点的左右孩子节点中保存的关键字分别是______。A、13,50 B、24,50C、24,53 D、24,90图1一棵平衡二叉树10. 如果从无向图的任一顶点出发进行一次深度优先搜索即可访问所有顶点,则该图一定是______。A、完全图 B、连通图C、有回路 D、一棵树11. 采用分块查找时,若线性表中共有625个元素,查找每个元素的概率相同,假设采用顺序查找来确定节点所在的块,则每块分为______个节点最佳。A、9 B、25C、6 D、512. 具有5层节点的AVL树至少有______个节点。A、10 B、12C、15 D、1713. N条记录中按关键字大小找出TopK(k<<N)条记录,使用下列______方法最节省时间。A、堆排序 B、希尔排序…………………………密……………………封……………………线………………………………学院专业级学号姓名C、快速排序 D、基数排序14. 若表R在排序前已按关键字正序排列,则______方法的比较次数最少。A、直接插入排序 B、快速排序C、归并排序 D、简单选择排序15. 用某种排序方法对线性表{25,84,21,47,15,27,68,35,20}进行排序时,排序过程如下:(1) 25,84,21,47,15,27,35