18秋北理工《数据结构与算法》在线作业答案满分答案
北理工《数据结构与算法》在线作业-0005
试卷总分:100 得分:0
一、 单选题 (共 40 道试题,共 100 分)
1.采用顺序搜索方法查找长度为n的顺序表时，搜索成功的平均搜索长度为()。
A.n
B.n/2
C.（n-1）/2
D.（n+1）/2
2.在一个长度为n的顺序线性表中顺序查找值为x的元素时，查找成功时的平均查找长度（即x与元素的平均比较次数，假定查找每个元素的概率都相等）为().
A.n
B.n/2
C.(n+1)/2
D.(n-1)/2
3.下述几种排序方法中，平均查找长度最小的是()。
A.插入排序
B.选择排序
C.快速排序
D.归并排序
4.对于经常要存取线性表任意指定位置元素的应用，线性表应采用()存储结构。
A.顺序存储结构
B.链式存储结构
C.线性链表
D.栈
5.设有一个二维数A[m][n]，以行序为主序存储。假设A[0][0]存放位置在644(10)，A[2][2]存放位置在676(10)，每个元素占一个空间，则A[4][5]在()位置，(10)表明用10进数表示。
A.692(10)
B.626(10)
C.709(10)
D.724(10)
6.下列关于AOE网的叙述中，不正确的是()。
A.关键活动不按期完成就会影响整个工程的完成时间
B.任何一个关键活动提前完成，那么整个工程将会提前完成
C.所有的关键活动提前完成，那么整个工程将会提前完成
D.某些关键活动提前完成，那么整个工程将会提前完成
7.含4个结点（元素值均不相同）的二叉搜索树有()种。
A.12
B.14
C.5
D.15
8.有一个有序表为｛1，3，9，12，32，41，45，62，75，77，82，95，100｝，当采用折半查找值为82的节点时，()次比较后查找成功。
A.1
B.2
C.4
D.8
9.在有序表（3,8,13,15,16,17,21,24,45）中，用二分查找法查找关键字21，所需进行关键字比较的次数为()。
A.2
B.3
C.4
D.5
10.一个数组第一个元素的存储地址是100，每个数组元素的长度为2，则第5个元素的地址是()。
A.110
B.108
C.100
D.120
11.下列说法哪个是不正确的()。
A.快速排序属于不稳定排序。
B.希尔排序属于不稳定排序。
C.直接插入排序属于不稳定排序。
D.堆排序属于不稳定排序。
12.若一个具有n个结点、k条边的非连通无向图是一个森林(n>k)，则该森林中必有()棵树。
A.k
B.n
C.n-k
D.n+k
13.数组的数据元素类型DataType可根据实际需要而定义。以下说法完全正确的是()
A.数组的读运算可以读取一个数据元素整体,写运算只能修改一个数据元素的一部分
B.数组的读、写运算可以读取或修改一个数据元素的一部分或一个整体
C.数组的读、写运算只能读取或修改一个数据元素的一部分
D.数组的读、写运算只能读取或修改一个数据元素整体
14.对哈希(HASH)函数H(k)= k MOD m, 一般来说，m应取()。
A.素数
B.很大的数
C.偶数
D.奇数
15.队列的操作特点是()。
A.先进先出
B.后进先出
C.先进后出
D.只能从队尾出队
16.下列说法正确的是()
A.堆栈是在两端操作、先进后出的线性表
B.堆栈是在一端操作、先进后出的线性表
C.队列是在一端操作、先进先出的线性表
D.队列是在两端操作、后进先出的线性表
17.评价排序算法好坏的标准主要是()。
A.执行时间
B.辅助空间
C.算法本身的复杂度
D.执行时间和所需的辅助空间
18.设数组Data[0..m]作为循环队列SQ的存储空间，front为队头指针，rear为队尾指针，则执行出队操作的语句为()
A.front=front+1
B.front=(front+1)% m
C.rear=(rear+1)%m
D.front=(front+1)%(m+1)
19.n 个顶点的连通图至少有()条边。
A.n-1
B.n
C.n+1
D.0
20.下列不属于栈基本运算的是()。
A.入栈
B.删除栈底元素
C.判断栈是否为空
D.建立一个空栈
21.已知A=(a,b), B=(A,A),那么GetHead(GetHead(GetTail(B)))=()。
A.(a)
B.A
C.a
D.(A)
22.当待排序列基本有序时，下列排序方法中()最好。
A.直接插入排序
B.快速排序
C.堆排序
D.归并排序
23.下列排序算法中，其中()是稳定的。
A.堆排序，冒泡排序
B.快速排序，堆排序
C.直接选择排序，希尔排序
D.归并排序，冒泡排序
24.以下排序方法中，稳定的排序方法是()。
A.直接插入排序和希尔排序
B.直接插入排序和冒泡排序
C.希尔排序和快速排序
D.冒泡排序和快速排序
25.A算法的时间复杂度为O（n^3），B算法的时间复杂度为O（2n），则说明()。
A.对于任何的数据量，A算法的时间开销都比B算法小
B.随着问题规模n的增大，A算法比B算法有效
C.随着问题规模n的增大，B算法比A算法有效
D.对于任何数据量，B算法的时间开销都比A算法小
26.在以下栈的基本运算中，不是加工型运算的是()
A.lnitStack(S)
B.Push(S,X)
C.Pop(S)
D.empty(S)
27.顺序表是线性表的()
A.链式存储结构
B.顺序存储结构
C.索引存储结构
D.散列存储结构
28.线性表采用链式存储时，结点的存储地址()
A.必须是不连续的
B.连续与否均可
C.必须是连续的
D.和头结点的存储地址相连续
29.用链接方式存储的队列，在进行插入运算时()。
A.仅修改头指针
B.头、尾指针都要修改
C.仅修改尾指针
D.头、尾指针可能都要修改
30.某二叉树的前序遍历序列为abdgcefh，中序遍历序列为dgbaechf，则其后序遍历序列为()。
A.bdgecefha
B.gdbecfha
C.bdgaechf
D.gdbehfca
31.下面四种内排序方法中，要求容量最大的是()。
A.插入排序
B.选择排序
C.快速排序
D.归并排序
32.已知一栈的进栈序列为：1234，则下列序列中不可能的出栈序列是()。
A.1234
B.4321
C.2143
D.4123
33.用线性链表存储线性表时，要求存储空间()
A.必须是连续的
B.连续不连续都可以
C.部分元素的存储空间必须是连续的
D.必须是不连续的
34.图的存储结构不包括()
A.数组表示
B.邻接表
C.邻接多重表
D.孩子兄弟表示
35.以下不稳定的排序方法是()
A.直接插入排序
B.冒泡排序
C.直接选择排序
D.二路归并排序
36.设有一个矩阵A8×6，以行序为主序存储，a11为第一个元素，其存储地址为1，每个元素占一个地址空间，则a56地址为()。
A.23
B.30
C.31
D.45
37.栈的插入和删除操作在()进行。
A.栈顶
B.栈底
C.任意位置
D.指定位置
38.根据二叉树的定义可知二叉树共有()种不同的形态。
A.4
B.5
C.6
D.7
39.一个n*n对称矩阵，如果以行或列为主序存入内存，则其容量为()。
A.n*n
B.n*n/2
C.n*（n+1）/2
D.（n+1）*（n+1）/2
40.线性表若采用链表存储结构时，要求内存中可用存储单元的地址()。
A.必须是连续的
B.部分地址必须是连续的
C.一定是不边疆的
D.连续不连续都可以
18秋北理工《数据结构与算法》在线作业答案历年参考题目如下：
