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

本资料由理硕教育整理，理硕教育是全国唯一专注于北理工考研辅导的学校，相对于其它机构理硕教育有得天独厚的优势。丰富的理工内部资料资源与人力资源确保每个学员都受益匪浅，确保理硕教育的学员初试通过率89%以上，复试通过率接近100%，理硕教育现开设初试专业课VIP一对一，假期集训营，复试VIP一对一辅导，满足学员不同的需求。因为专一所以专业，理硕教育助您圆北理之梦。详情请查阅理硕教育官网数据结构试卷（三）选择题（每题1分，共20分）设谋数据结构的二元组形式表示为A=（D,R），D={01，02，03，04，05，06，07，08，09}，R={r}，r={01，02，01，03,01,04,02,05,02,06,03,07,03,07,03,08,03，09},则数据结构A是（）线性结构B.树型结构C.物理结构D.图型结构下面程序的时间复杂为（）for (i=1,s=0;i=n;i++) {t=1;for(j=1;j=i;j++)s=s+t;}O(n) B.O(n2) C.O(n3) D.O(n4)设指针变量p指向单链表中结点A，若删除单链表中结点A，则需要修改指针的操作序列为（）q=p-next;p-data=q-data;p-next=q-next;free(q)q=p-next;q-data=p-data;p-next=q-next;free(q)C.q=p-next;p-next=q-next;free(q)D.q=p-next;p-data=q-data;free(q)设有n个待排序的记录关键字，则在堆排序中需要（）个辅助记录单元。A.1 B.n C.nlog2n D.n2设一组初始关键字记录关键字为（20，15，14，18，21，36，40，10），则以20为基准记录的一趟快速排序结束后的结果为（）A.10,15,14,18,20,36,40,21B.10,15,14,18,20,40,36,21C.10,15,14,20,18,40,36,21D.15,10,14,18,20,36,40,21设二叉排序树中有n个结点，则在二叉排序树的平均查找长度为（）A.O（1） B.O(LOG2n) C. D.O（n2）7、设无向图G中有n个顶点e条边，则其对应的邻接表中的表头结点和表结点的个数分别为（）n,e B.e,n C.2n,e D.n,2e设某强连通图中有n个顶点，则该强连通图中至少有（）条边。n(n-1) B.n+1 C.n D.n(n+1)设有5000个待排序的记录关键字，如果需要用最快的方法选出其中最小的10个记录关键字，则用下列（）方法可以达到此目的。快速排序 B. 堆排序 C.归并排序 D.插入排序下列四种排序中（）的空间负责度最大。A.插入排序 B. 冒泡排序 C.堆排序 D.归并排序二、填空题（每空1分，共20分）1、数据的物理结构主要包括_________________和_________________两种情况。2、设一棵完全二叉树中有500个结点，则该二叉树的深度为_________________；若用二叉链表作为该完全二叉树的存储结构，则共有_________________个空指针域。3、设输入序列为1，2，3，则经过找的作用后可以得到_________________种不同的输出序列。4、设有向图G用邻接矩阵A[n][n]作为存储结构，则该邻接矩阵中第i行商所有元素之和等于顶点i的_________________，第i列上所有元素之和等于顶点i的_________________。5、设哈夫曼树种共有n个结点，则该哈夫曼树中有_________________个度数为1的结点。6、设有向图G中有n个顶点e条有向边，所有顶点入度数之和为d，则e和d的关系为_________________。设有xian_________________遍历二叉排序树中的结点可以得到一个递增的关键字序列（填先序、中序或后序）设查找表中有100个元素，如果用二分法查找方法查找数据元素X，则最多需要比较_________________次就可以断定数据元素X是否在查找表中。不论是顺序存储结构的栈还是链式存储结构的栈，其入栈和出栈操作的时间复杂度均为_________________。设有n个结点的完全二叉树，如果按照从上到下，从左到右从1开始顺序编号，则第i个结点的双亲结点编号为_________________，右孩子结点的编号为_________________。设一组初始记录关键字为（72，73，71，23，94，16，5），