北京理工大学813计算机专业基础模拟题4.docx

本资料由理硕教育整理，理硕教育是全国唯一专注于北理工考研辅导的学校，相对于其它机构理硕教育有得天独厚的优势。丰富的理工内部资料资源与人力资源确保每个学员都受益匪浅，确保理硕教育的学员初试通过率89%以上，复试通过率接近100%，理硕教育现开设初试专业课VIP一对一，假期集训营，复试VIP一对一辅导，满足学员不同的需求。因为专一所以专业，理硕教育助您圆北理之梦。详情请查阅理硕教育官网数据结构试卷（四）选择题（每题1分，共20分）设一维数组中有n个数组元素，则读取第i个数组元素的平均时间复杂度为（）O(n) B.O(nlog2n) C.O(1) D.O(n2)设一棵二叉树的深度为k，则该二叉树中最多有（）个结点。A.2k-1 B.2k C.2k-1 D.2e设谋无向图中有n个顶点e条边，则该无向图中所有顶点的入度之和为（）n B.e C.2n D.2e在二叉排序树种插入一个结点的时间复杂度为（）A.O(1) B.O(n) C.O(nlog2n) D.O(n2)5、设某有向图的邻接表中有n个表头结点和m个表结点，则该图中有（）条有向边。A.n B.n-1 C.m D.m-16、设一组初始记录关键字序列为（345，253，674，924，627），则用基数排序需要进行（）趟的分配和回收才能使得初始关键字序列变成有序序列。A.3 B.4 C.5 D.8设用链表作为栈的存储结构则退栈操作（）必须判别栈是否为满 B.必须判别栈是否为空 C.判别栈元素的类型 D.对栈不做任何判别下列四种排序中（）的空间复杂度最大。快速排序 B.冒泡排序 C.希尔排序 D.堆设某二叉树中度数为0 的结点数位N0，度数为1的结点数位N1，度数为2的结点树为N2，则下列灯饰成立的是（）N0=N1+1 B.N0=N1+N2 C.N0=N2+1 D.N0=2N1+1设有许顺序表中有n个数据元素，则利用二分查找法查找数据元素X的最多比较次数不超过（）log2n+1 B.log2n-1 C.log2n D.log2(n+1)填空题（每空1分，共20分）设有n 个无序的记载关键字，则直接插入排序的时间复杂度为_________________,快速排序的平均时间复杂度为_________________。设指针变量p的指向双向循环链表中的结点X，则删除结点X需要执行的语句序列为___________________________________________________（设结点中的两个指针域分别为link和rlink）。根据初始关键字序列（19，22，01，38，10）建立的二叉排序树的高度为_________________。深度为k的完全二叉树中最少有_________________个结点。设初始记录关键字序列为（K1,K2,.......Kn）,则用筛选法思想建堆必须从第_________________个元素开始进行筛选。设哈夫曼树种共有99个结点，则该树中有_________________个叶子结点，若采用而插件表作为存储结构，则该树中有_________________个空指针域。设有一个顺序循环队列中有M个存储单元，则该循环队列中最多能够存储_________________个队列元素，当前实际存储_________________个队列元素（设头指针F指向当前对头元素的前一个位置，尾指针指向当前队尾元素的位置）。设顺序线性表中有n个数据元素，则第i 个位置上插入一个数据元素需要移动表中_________________个数据元素，删除第i个位置上的数据元素需要移动表中__________个元素。设一组初始记录关键字序列为（20，18，22，16，30，19），则以20为中轴的一趟快速排序结果为_________________设一组初始记录关键字序列为（20，18，22，16，30，19），则根据这些初始关键字序列建成的初始堆为_________________。设某无向图G中有n个顶点，用邻接矩阵A作为该图的存储结构，则顶点i和顶点j互为邻接点的条件是_________________。设无向图对应的邻接矩阵为A，则A中第i上非0元素的个数_________________第i列上非0元素的个数（填等于，大于或小于）。设前序遍历某二叉树的序列为ABCD，