北理工17春《数据结构与算法》在线作业答案参考
北理工《数据结构与算法》在线作业一、单选题：
1.线性链表是通过( )方式表示元素之间的关系 (满分:2.5)
A. 后继元素地址
B. 元素的存储顺序
C. 左、右孩子地址
D. 元素的相对存储位置
2.n 个顶点的连通图至少有( )条边。 (满分:2.5)
A. n-1
B. n
C. n+1
D. 0
3.在一个长度为n的顺序线性表中顺序查找值为x的元素时，查找成功时的平均查找长度（即x与元素的平均比较次数，假定查找每个元素的概率都相等）为( ). (满分:2.5)
A. n
B. n/2
C.(n+1)/2
D.(n-1)/2
4.下列存储表示中,哪一个不是树的存储形式( )。 (满分:2.5)
A. 双亲表示法
B. 孩子链表表示法
C. 顺序存储表示法
D. 孩子兄弟表示法
5.对线性表进行二分查找时，要求线性表必须( )。 (满分:2.5)
A. 以顺序方式存储
B. 以链接方式存储
C. 以顺序方式存储，且结点按关键字有序排列
D. 以链接方式存储，且结点按关键字有序排列
6.下列说法哪个是不正确的( )。 (满分:2.5)
A. 快速排序属于不稳定排序。
B. 希尔排序属于不稳定排序。
C. 直接插入排序属于不稳定排序。
D. 堆排序属于不稳定排序。
7.以二叉链表作为二叉树的存贮结构时，在具有n个结点的二叉链表中(n>0)，空指针域的个数为( )。 (满分:2.5)
A. 2n-1
B. n+1
C. n-1
D. 2n+1
8.当待排序列基本有序时，下列排序方法中( )最好。 (满分:2.5)
A. 直接插入排序
B. 快速排序
C. 堆排序
D. 归并排序
9.长度为256的表,采用分块查找,每块最佳长度为( )。 (满分:2.5)
A. 14
B. 16
C. 18
D. 26
10.如果结点a有三个兄弟，而且b为a的双亲，则b的度为( )。 (满分:2.5)
A. 3
B. 4
C. 5
D. 2
11.采用顺序搜索方法查找长度为n的顺序表时，搜索成功的平均搜索长度为( )。 (满分:2.5)
A. n
B. n/2
C. （n-1）/2
D. （n+1）/2
12.判定一个队列Q(最多元素为m0)为满队列的条件是( ) (满分:2.5)
A. rear-front= = m0
B. rear-front-1= =m0
C. front= =rear
D. front= =rear+1
13.具有 n 个顶点的有向完全图有( )条弧。 (满分:2.5)
A. n
B. n*(n-1)
C. n*(n+1)
D. n*n
14.具有线性结构的数据结构是( ) (满分:2.5)
A. 赫夫曼树
B. 栈
C. 图
D. 树
15.若构造一棵具有n个结点的二叉排序树，最坏情况下，其深度不会超过( )。 (满分:2.5)
A. n/2
B. n
C.(n+1)/2
D. n+1
16.以下不稳定的排序方法是( ) (满分:2.5)
A. 直接插入排序
B. 冒泡排序
C. 直接选择排序
D. 二路归并排序
17.设有50行60列的二维数组A，其元素长度为4字节，按行优先顺序存储，基地址为200，则元素A的存储地址为( )。 (满分:2.5)
A. 3700
B. 4376
C. 3900
D. 4620
18.从1000个元素中选出其中五个最大值元素( )排序最适合。 (满分:2.5)
A. 冒泡
B. 快速排序
C. 堆排序
D. 选择排序
19.以下关于线性表的说法不正确的是( )。 (满分:2.5)
A. 线性表中的数据元素可以是数字、字符、记录等不同类型
B. 线性表中包含的数据元素个数不是任意的
C. 线性表中的每个结点都有且只有一个直接前趋和直接后继
D. 存在这样的线性表：表中各结点都没有直接前趋和直接后继
20.设有7000个无序的元素,希望用最快的速度挑选出其中前5个最大的元素,最好选用( )法。 (满分:2.5)
A. 冒泡排序
B. 快速排序
C. 堆排序
D. 基数排序
21.( )是HASH查找的冲突处理方法。 (满分:2.5)
A. 求余法
B. 平方取中法
C. 二分法
D. 开放定址法
22.评价排序算法好坏的标准主要是( )。 (满分:2.5)
A. 执行时间
B. 辅助空间
C. 算法本身的复杂度
D. 执行时间和所需的辅助空间
23.快速排序属于那种排序类型( )。 (满分:2.5)
A. 选择排序
B. 插入排序
C. 交换排序
D. 基数排序
24.队列的操作特点是( )。 (满分:2.5)
A. 先进先出
B. 后进先出
C. 先进后出
D. 只能从队尾出队
25.稀疏矩阵一般的压缩存储方法有两种，即( )。 (满分:2.5)
A. 二维数组和三维数组
B. 三元组表和散列表
C. 三元组表和十字链表
D. 散列表和十字链表
26.一棵高度（假定树根结点为第0层）为4的完全二叉树中的结点数最少为( )。 (满分:2.5)
A. 15
B. 16
C. 17
D. 31
27.具有65个结点的完全二叉树其深度为（根的层次号为1）( )。 (满分:2.5)
A. 8
B. 7
C. 6
D. 5
28.已知一栈的进栈序列为：1234，则下列序列中不可能的出栈序列是( )。 (满分:2.5)
A. 1234
B. 4321
C. 2143
D. 4123
29.从未排序序列中依次取出一个元素与已排序序列中的元素依次进行比较，然后将其放在已排序序列的合适位置，该排序方法称为( )排序法。 (满分:2.5)
A. 插入
B. 选择
C. 交换
D. 二路归并
30.若某线性表最常用的操作是在最后一个结点之后插入一个结点或删除最后一个结点，则采用哪一种存储结构算法的时间效率最高?( ) (满分:2.5)
A. 单链表
B. 给出表头指针的单循环链表
C. 双向链表
D. 给出表尾指针的双向循环链表
31.顺序查找适合于存储结构为( )的查找表。 (满分:2.5)
A. 压缩存储
B. 散列存储
C. 索引存储
D. 顺序存储或链式存储
32.向一个栈顶指针为HS的链栈中将一个S指针所指的结点入栈，执行( )。 (满分:2.5)
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
33.一个n*n对称矩阵，如果以行或列为主序存入内存，则其容量为( )。 (满分:2.5)
A. n*n
B. n*n/2
C. n*（n+1）/2
D. （n+1）*（n+1）/2
34.用链接方式存储的队列，在进行插入运算时( )。 (满分:2.5)
A. 仅修改头指针
B. 头、尾指针都要修改
C. 仅修改尾指针
D. 头、尾指针可能都要修改
35.某二叉树的前序遍历序列为abdgcefh，中序遍历序列为dgbaechf，则其后序遍历序列为( )。 (满分:2.5)
A. bdgecefha
B. gdbecfha
C. bdgaechf
D. gdbehfca
36.下述几种排序方法中，平均查找长度最小的是( )。 (满分:2.5)
A. 插入排序
B. 选择排序
C. 快速排序
D. 归并排序
37.关键路径是指AOE(Activity On Edge)网中( )。 (满分:2.5)
A. 最长的回路
B. 最短的回路
C. 从源点到汇点(结束顶点)的最长路径
D. 从源点到汇点(结束顶点)的最短路径
38.一个栈的入栈序列是abcde，则栈的不可能的输出序列是( )。 (满分:2.5)
A. edcba
B. decba
C. dceab
D. abcde
39.栈是一种( )的数据结构。 (满分:2.5)
A. 存取受限的线性结构
B. 存取不受限的线性结构
C. 存取受限的非线性结构
D. 存取不受限的非线性结构
40.有一个有序表为｛1，3，9，12，32，41，45，62，75，77，82，95，100｝，当采用折半查找值为82的节点时，( )次比较后查找成功。 (满分:2.5)
A. 1
B. 2
C. 4
D. 8
页:
[1]