数据结构模拟抽卷.docVIP

一、单项选择题 (每题2分,共20分) 1. 如果最常用的操作是提取第i个结点及其前驱，则采用（ ）存储方式最节省时间。 A．单链表　 B.顺序表　 C.循环链表　　D.双链表 2. 在一个链队中，假设f和r分别为队首和队尾指针，则插入s所指结点的运算是（ ）。 A.f-next=s;f=s; B.r-next=s;r=s;C.s-next=r;r=s; D.s-next=f;f=s; 3. 一棵有124个叶子结点的完全二叉树，至多有（ ）个结点。 A．251 B．250 C．248 D．247 4. 适用于对动态查找表进行高效率查找的组织结构是（ ） A．有序表 B．分块有序表 C．二叉排序树 D．线性链表 5. 由同一关键字集合构造的各棵二叉排序树 ( ) A. 其形态不一定相同，但平均查找长度相同 B. 其形态不一定相同，平均查找长度也不一定相同 C. 其形态均相同，但平均查找长度不一定相同 D. 其形态均相同，平均查找长度也都相同 6. 在一个单链表中已知q所指的结点是p所指结点的前驱结点，若在q和p之间插入s结点，则执行（ ）。　　 A. s-next=p-next;p-next=s;B.p-next=s-next;s-next=p;C. q-next=s;s-next=p;D.p-next=s;s-next=q; 7. 由同一关键字集合构造的各棵二叉排序树（ ）。 与第5题相同 A. 其形态不一定相同，但平均查找长度相同 B. 其形态不一定相同，平均查找长度也不一定相同 C. 其形态均相同，但平均查找长度不一定相同 D. 其形态均相同，平均查找长度也都相同 8. 假设一个有n个顶点和e条弧的有向图用邻接表表示,则删除与某个顶点vi相关的所有弧的时间复杂度是（ ）。 A．O(n) B．O(e) C．O(n+e) D．O(n*e) 9. 数据的存储结构包括顺序、链接、散列和（ ）4种基本类型。 我们的教材上没有相关内容 A.向量 B.数组 C.集合 D.索引 10. 在长度为n的顺序表中插入一个元素时,等概率情况下的平均移动元素的次数是（　） 。 A.（n-1）/2 B.n/2 C.n*(n-1)/2 D.(n+1)/2 二、判断题 (每题1分,共10分) 1. 如果有向图中各个顶点的度都大于2，则该图中必有回路。( ) 2. 二叉树中每个结点的两棵子树的高度差等于1。( ) 3. 一个无向连通图的生成树是图的极小的连通子图。（ ） 4. 向一棵B树插入关键码的过程中，若最终引起树根结点的分裂，则新树比原树的高度减少1。( ) 5. 邻接表只能用于有向图的存储，邻接矩阵对于有向图和无向图的存储都适用。( ) 6. 强连通分量是有向图中的极大强连通子图。( ) 7. 进行折半查找的表必须是顺序存储的有序表。( ) 8. 对于同一组记录，生成二叉排序树的形态与插入记录的次序无关。( ) 9. 如果采用如下方法定义一维字符数组： 此题可以删除 int maxSize = 30; char * a = new char[maxSize]; 则这种数组在程序执行过程中不能扩充。（ ） 10. 使用三元组表示稀疏矩阵中的非零元素能节省存储空间。（ ） 三、填空题 (每空2分,共20分) 1. 设关键字序列（17,8,13,25,24,16,3，19，1），用希尔排序法按升序排序，用初始增量4进行一趟排序后的结果是( )。 2. n个顶点的连通无向图的生成树含有( )条边。 3. 利用三元组表存放稀疏矩阵中的非零元素，则在三元组表中每个三元组元素对应一个非零元素的行号、列号和( )。 4. 在一个最小堆中，堆顶结点的值是所有结点中的( )。 5. 若设一个n的矩阵A的开始存储地址LOC(0, 0) 及元素所占存储单元数d已知，按行存储时其任意一个矩阵元素a[i][j]的存储地址为( )。 6. 在一个最大堆中，堆顶结点的值是所有结点中的( )。 7. 普里姆算法适用于求（ ）的网的最小生成树。 8. 设序列{25,36,40,45,48,56,60,68,72,85}，当用折半查找方法查找36时，所需比较的次数为（ ）。 9. 设关键字序列{7,12,26,30,47,58,66,70,82,90}，当用折半查找方法查找时，所需比较的次数为3次的关键字分别是（ ）。 10. 在无向图G的邻接矩阵表示中，第j列中非零元的个数等于该