21年春北理工《数据结构与算法》在线作业（答案）

skystar

[北京理工大学]北理工《数据结构与算法》在线作业
试卷总分:100    得分:100
第1题,顺序查找适合于存储结构为()的查找表。
A、压缩存储
B、散列存储
C、索引存储
D、顺序存储或链式存储
正确答案:


第2题,栈是一种()的数据结构。
A、存取受限的线性结构
B、存取不受限的线性结构
C、存取受限的非线性结构
D、存取不受限的非线性结构
正确答案:


第3题,设有50行60列的二维数组A[50][60]，其元素长度为4字节，按行优先顺序存储，基地址为200，则元素A[18][25]的存储地址为()。
A、3700
B、4376
C、3900
D、4620
正确答案:


第4题,判定一个队列Q(最多元素为m0)为满队列的条件是()
A、rear-front= = m0
B、rear-front-1= =m0
C、front= =rear
D、front= =rear+1
正确答案:


如果想在4092个数据中只需要选择其中最小的5个，采用()方法最好。
A、冒泡排序
B、堆排序
C、锦标赛排序
D、快速排序
正确答案:


第6题,若已知一棵二叉树先序序列为ABCDEFG，中序序列为CBDAEGF，则其后序序列为()。
A、CDBGFEA
B、CDBFGEA
C、CDBAGFE
D、BCDAGFE
正确答案:


第7题,当两个元素比较出现反序时就相互交换位置的排序方法称为()。
A、归并排序
B、选择排序
C、交换排序
D、插入排序
正确答案:


第8题,若某线性表最常用的操作是在最后一个结点之后插入一个结点或删除最后一个结点，则采用哪一种存储结构算法的时间效率最高?()
A、单链表
B、给出表头指针的单循环链表
C、双向链表
D、给出表尾指针的双向循环链表
正确答案:


第9题,稀疏矩阵一般的压缩存储方法有两种，即()。
A、二维数组和三维数组
B、三元组表和散列表
C、三元组表和十字链表
D、散列表和十字链表
正确答案:


以下说法错误的是()
A、每个存储结点只能存放一个数据元素
B、数据元素之间的关联方式可由存储结点之间的关联方式直接表达
C、一种存储结构可以在两个级别上讨论。其一是机器级，其二是语言级
D、语言级描述可经编译自动转换成机器级 因此也可以看成是一种机内表示
正确答案:


第11题,在线性表顺序存储结构下，在第i个元素之前插入新元素一般需要()
A、移动元素
B、修改头指针
C、队头指针
D、申请新的结点空间
正确答案:


A、顺序存储结构
B、链式存储结构
C、线性链表
D、栈
正确答案:


第13题,从1000个元素中选出其中五个最大值元素()排序最适合。
A、冒泡
B、快速排序
C、堆排序
D、选择排序
正确答案:


第14题,学习数据结构主要目的是()。
A、处理数值计算问题
B、研究程序设计技巧
C、选取合适数据结构，写出更有效的算法
D、是计算机硬件课程的基础
正确答案:


一个数组第一个元素的存储地址是100，每个数组元素的长度为2，则第5个元素的地址是()。
A、110
B、108
C、100
D、120
正确答案:


第16题,采用顺序搜索方法查找长度为n的顺序表时，搜索成功的平均搜索长度为()。
A、n
B、n/2
C、（n-1）/2
D、（n+1）/2
正确答案:


第17题,快速排序属于那种排序类型()。
A、选择排序
B、插入排序
C、交换排序
D、基数排序
正确答案:


第18题,数组的数据元素类型DataType可根据实际需要而定义。以下说法完全正确的是()
A、数组的读运算可以读取一个数据元素整体,写运算只能修改一个数据元素的一部分
B、数组的读、写运算可以读取或修改一个数据元素的一部分或一个整体
C、数组的读、写运算只能读取或修改一个数据元素的一部分
D、数组的读、写运算只能读取或修改一个数据元素整体
正确答案:


第19题,()是HASH查找的冲突处理方法。
A、求余法
B、平方取中法
C、二分法
D、开放定址法
正确答案:


对线性表进行二分查找时，要求线性表必须()。
A、以顺序方式存储
B、以链接方式存储
C、以顺序方式存储，且结点按关键字有序排列
D、以链接方式存储，且结点按关键字有序排列
正确答案:


第21题,快速排序方法在()情况下最不利于发挥其长处。
A、被排序的数据量太大
B、被排序数据中含有多个相同值
C、被排序数据已基本有序
D、被排序数据数目为奇数
正确答案:


第22题,3个结点的无向完全连通图至少有()条边。
A、3
B、4
C、5
D、6
正确答案:


第23题,已知广义表 LS=(A,(B,C,D),E)运用head和tail函数，取出LS中B的运算()。
A、Gethead(Gethead(LS))
B、Gettail(Gethead(LS))
C、Gethead(Gethead(Gettail(LS)))
D、Gethead(Gettail(LS))
正确答案:


第24题,栈与一般的线性表的区别在于()。
A、数据元素的类型不同
B、运算是否受限制
C、数据元素的个数不同
D、逻辑结构不同
正确答案:


若构造一棵具有n个结点的二叉排序树，最坏情况下，其深度不会超过()。
A、n/2
B、n
C、(n+1)/2
D、n+1
正确答案:


第26题,线性链表是通过()方式表示元素之间的关系
A、后继元素地址
B、元素的存储顺序
C、左、右孩子地址
D、元素的相对存储位置
正确答案:


第27题,中序遍历一棵二叉排序树所得到的结点序列是键值的()序列。
A、递增或递减
B、递减
C、递增
D、无序
正确答案:


第28题,在以下栈的基本运算中，不是加工型运算的是()
A、lnitStack(S)
B、Push(S,X)
C、Pop(S)
D、empty(S)
正确答案:


第29题,有一个有序表为｛1，3，9，12，32，41，45，62，75，77，82，95，100｝，当采用折半查找值为82的节点时，()次比较后查找成功。
A、1
B、2
C、4
D、8
正确答案:


A、逻辑
B、存储
C、逻辑和存储
D、物理
正确答案:


第31题,向一个栈顶指针为HS的链栈中将一个S指针所指的结点入栈，执行()。
A、HS-next=s
B、S-next=HS-next;HS-next=s
C、S-next=HS;HS=s
D、S-next=HS;HS=HS-next
正确答案:


第32题,具有 n 个顶点的有向完全图有()条弧。
A、n
B、n*(n-1)
C、n*(n+1)
D、n*n
正确答案:


第33题,设连通图G中的边集E={(a，b)，(a，e)，(a，c)，(b，e)，(e，d)，(d，f)，(f，c)}，则从顶点a出发可以得到一种深度优先遍历的顶点序列为()
A、abedfc
B、acfebd
C、aebdfc
D、aedfcb
正确答案:


第34题,若采用邻接矩阵法存储一个n个顶点的无向图，则该邻接矩阵是一个()。
A、上三角矩阵
B、稀疏矩阵
C、对角矩阵
D、对称矩阵
正确答案:


第35题,线性表采用链式存储时，结点的存储地址()
A、必须是不连续的
B、连续与否均可
C、必须是连续的
D、和头结点的存储地址相连续
正确答案:


第36题,A算法的时间复杂度为O（n^3），B算法的时间复杂度为O（2n），则说明()。
A、对于任何的数据量，A算法的时间开销都比B算法小
B、随着问题规模n的增大，A算法比B算法有效
C、随着问题规模n的增大，B算法比A算法有效
D、对于任何数据量，B算法的时间开销都比A算法小
正确答案:


第37题,关键路径是指AOE(Activity On Edge)网中()。
A、最长的回路
B、最短的回路
C、从源点到汇点(结束顶点)的最长路径
D、从源点到汇点(结束顶点)的最短路径
正确答案:


第38题,下列排序算法中，其中()是稳定的。
A、堆排序，冒泡排序
B、快速排序，堆排序
C、直接选择排序，希尔排序
D、归并排序，冒泡排序
正确答案:


第39题,以二叉链表作为二叉树的存贮结构时，在具有n个结点的二叉链表中(n0)，空指针域的个数为()。
A、2n-1
B、n+1
C、n-1
D、2n+1
正确答案:


第40题,线性表若采用链表存储结构时，要求内存中可用存储单元的地址()。
A、必须是连续的
B、部分地址必须是连续的
C、一定是不边疆的
D、连续不连续都可以
正确答案: