北语17春《数据结构》作业答案
北语17春《数据结构》作业4一、单选题：
1. (满分:5)
A. A
B. B
C. C
D. D
2.采用邻接表存储的图的广度优先遍历算法类似于二叉树的。 (满分:5)
A. 先序遍历
B. 中序遍历
C. 后序遍历
D. 按层遍历
3.在一个有向图中，所有顶点的入度之和等于所有顶点的出度之和的倍。 (满分:5)
A. 1/2
B. 1
C. 2
D. 4
4.某二叉树结点的中序序列为ABCDEFG，后序序列为BDCAFGE，则其左子树中结点数目为。 (满分:5)
A. 3
B. 2
C. 4
D. 5
5.若一棵二叉树具有10个度为2的结点，5个度为1的结点，则度为0的结点的个数是。 (满分:5)
A. 9
B. 11
C. 15
D. 不能确定
6.有一个有序表{1,3,9,12,32,41,45,62,75,77,82,95,100}，当折半查找值为82的结点时，次比较后查找成功。 (满分:5)
A. 11
B. 5
C. 4
D. 8
7.有一个有序表{1，4，6，10，18，35，42，53，67，71，78，84，92，99}，当用二分查找法查找键值为84的结点时，经( )次比较后查找成功。 (满分:5)
A. 2
B. 3
C. 4
D. 12
8.顺序查找法适合于存储结构为的线性表。 (满分:5)
A. 散列存储
B. 顺序存储或链式存储
C. 压缩存储
D. 索引存储
9.具有n个结点的连通图至少有条边。 (满分:5)
A. n-1
B. n
C. n（n-1）/2
D. 2n
10. (满分:5)
A. A
B. B
C. C
D. D
11. (满分:5)
A. A
B. B
C. C
D. D
12.对线性表进行折半查找时，要求线性表必须。 (满分:5)
A. 以顺序方式存储
B. 以顺序方式存储，且结点按关键字有序排序
C. 以链式方式存储
D. 以链式方式存储，且结点按关键字有序排序
13. (满分:5)
A. A
B. B
C. C
D. D
14.采用邻接表存储的图的深度优先遍历算法类似于二叉树的。 (满分:5)
A. 先序遍历
B. 中序遍历
C. 后序遍历
D. 按层遍历
15. (满分:5)
A. 索引非顺序文件
B. 索引顺序文件
C. 非顺序文件
D. 哈希文件
16. (满分:5)
A. A
B. B
C. C
D. D
17.广义表（（a），a）的表头是。 (满分:5)
A. a
B.( )
C.(a)
D.((a))
18.有一个长度为12的有序表R,按二分查找法对该表进行查找,在表内各元素等概率情况下查找成功所需的平均比较次数为( )。 (满分:5)
A. 35/12
B. 37/12
C. 39/12
D. 43/12
19. (满分:5)
A. A
B. B
C. C
D. D
20. (满分:5)
A. A
B. B
C. C
D. D
17春《数据结构》作业3
一、单选题：
1. (满分:5)
A. A
B. B
C. C
D. D
2.输入序列为ABC，可以变为CBA时，经过的栈操作为。 (满分:5)
A. push
pop
push
pop
push
pop
B. push
push
push
pop
pop
pop
C. push
push
pop
push
pop
D. push
pop
push
push
pop
pop
3.设计一个判别表达式中左、右括号是否配对出现的算法，采用数据结构最佳。 (满分:5)
A. 线性表的顺序存储结构
B. 队列
C. 线性表的链式存储结构
D. 栈
4.线性表（a1,a2,...,an）以链式方式存储，访问第i位置元素的时间复杂度为。 (满分:5)
A. O（0）
B. O（1）
C. O（n）
D. O（n2）
5.线性表的链式存储结构是一种。 (满分:5)
A. 随机存取的存储结构
B. 顺序存取的存储结构
C. 索引存取的存储结构
D. Hash存取的存储结构
6.串是一种特殊的线性表，其特殊性体现在。 (满分:5)
A. 可以顺序存储
B. 数据元素是一个字符
C. 可以链式存储
D. 数据元素可以是多个字符
7.栈和队列的共同点是。 (满分:5)
A. 都是先进后出
B. 都是先进先出
C. 只允许在端点处插入和删除元素
D. 没有共同点
8. (满分:5)
A. A
B. B
C. C
D. D
9. (满分:5)
A. A
B. B
C. C
D. D
10.对一个满二叉树，m个叶子，n个结点，深度为h，则。 (满分:5)
A. n=h+m
B. h+m=2n
C. m=h-1
D. n=2h-1
11.任何一棵二叉树的叶子结点在前序、中序和后序遍历序列中的相对次序。 (满分:5)
A. 不发生改变
B. 发生改变
C. 不能确定
D. 以上都不对
12.对于只在表的首、尾两端进行插入操作的线性表，宜采用的存储结构为。 (满分:5)
A. 顺序表
B. 用头指针表示的循环单链表
C. 用尾指针表示的循环单链表
D. 单链表
13.允许对队列进行的操作有。 (满分:5)
A. 对队列中的元素排序
B. 取出最近进队的元素
C. 在队头元素之前插入元素
D. 删除队头元素
14.队列的先进先出特性是指。 (满分:5)
A. 最早插入队列中的元素总是最后被删除
B. 当同时进行插入、删除操作时，总是插入操作优先
C. 每当有删除操作时，总是要先做一次插入操作
D. 每次从队列中删除的总是最早插入的元素
15.若已知一个栈序列是1,2,3,...,n，其输出序列为p1,p2,p3,...,pn，若p1=n，则pi为。 (满分:5)
A. i
B. n-i
C. n-i+1
D. 不确定
16. (满分:5)
A. A
B. B
C. C
D. D
17. (满分:5)
A. A
B. B
C. C
D. D
18. (满分:5)
A. A
B. B
C. C
D. D
19.单链表中，增加一个头结点的目的是为了。 (满分:5)
A. 使单链表至少有一个结点
B. 标识表结点中首结点的位置
C. 方便运算的实现
D. 说明单链表是线性表的链式存储
20.树最适合用来表示。 (满分:5)
A. 有序数据元素
B. 无序数据元素
C. 元素之间具有分支层次关系的数据
D. 元素之间无联系的数据
17春《数据结构》作业2
一、单选题：
1.设一组初始记录关键字序列（5,2,6,3,8），以第一个记录关键字5为基准进行一趟快速排序的结果为。 (满分:5)
A. 2
3
5
8
6
B. 3
2
5
8
6
C. 3
2
5
6
8
D. 2
3
6
5
8
2.需要分配较大空间，插入和删除不需要移动元素的线性表，其存储结构是。 (满分:5)
A. 单链表
B. 静态链表
C. 线性链表
D. 顺序存储结构
3. (满分:5)
A. A
B. B
C. C
D. D
4.设某棵二叉树中有2000个结点，则该二叉树的最小高度为。 (满分:5)
A. 9
B. 10
C. 11
D. 12
5.设有5000个待排序的记录关键字，如果需要用最快的方法选出其中最小的10个记录关键字，则用下列方法可以达到此目的。 (满分:5)
A. 快速排序
B. 堆排序
C. 归并排序
D. 插入排序
6.算法分析的两个主要方面是。 (满分:5)
A. 空间复杂度和时间复杂度
B. 正确性和简明性
C. 可读性和文档性
D. 数据复杂性和程序复杂性
7. (满分:5)
A. a
B. b
C. c
D. d
8.在一个长度为n（n>1）的单链表上，设有头和尾两个指针，执行操作与链表的长度有关。 (满分:5)
A. 删除单链表中的第一个元素
B. 删除单链表中的最后一个元素
C. 在单链表第一个元素前插入一个新元素
D. 在单链表最后一个元素后插入一个新元素
9.下列四种排序中的空间复杂度最大。 (满分:5)
A. 插入排序
B. 冒泡排序
C. 堆排序
D. 归并排序
10.在长度为n的顺表表的第i个位置上插入一个元素（1≤i≤n+1），元素的移动次数为。 (满分:5)
A. n-i+1
B. n-i
C. i
D. i-1
11. (满分:5)
A. A
B. B
C. C
D. D
12.数据结构在计算机内存中的表示是指。 (满分:5)
A. 数据的存储结构
B. 数据结构
C. 数据的逻辑结构
D. 数据元素之间的关系
13.算法分析的目的是。 (满分:5)
A. 找出数据结构的合理性
B. 研究算法中的输入和输出的关系
C. 分析算法的效率以求改进
D. 分析算法的易读性和文档性
14. (满分:5)
A. A
B. B
C. C
D. D
15.设一组初始记录关键字序列为（345,253,674,924,627），则用基数排序需要进行趟的分配和回收才能使得初始关键字序列变成有序序列。 (满分:5)
A. 3
B. 4
C. 5
D. 8
16. (满分:5)
A. A
B. B
C. C
D. D
17. (满分:5)
A. A
B. B
C. C
D. D
18. (满分:5)
A. A
B. B
C. C
D. D
19. (满分:5)
A. A
B. B
C. C
D. D
20.设二维数组A，每个数组元素占用4个存储单元，若按行优先顺序存放数组元素，a的存储地址为860，则a的存储地址是。 (满分:5)
A. 1000
B. 860
C. 1140
D. 1200
17春《数据结构》作业1
一、单选题：
1.由权值分别为11,8,6,2,5的叶子结点生成一棵哈夫曼树，它的带权路径长度为。 (满分:5)
A. 24
B. 71
C. 48
D. 53
2.数组的逻辑结构不同于下列的逻辑结构。 (满分:5)
A. 线性表
B. 栈
C. 队列
D. 树
3.设有以下四种排序方法，则的空间复杂度最大。 (满分:5)
A. 冒泡排序
B. 快速排序
C. 堆排序
D. 希尔排序
4.对于线性表（7,34,55,25,64,46,20,10）进行散列存储时，若选用H（K）=K%9作为散列函数，则散列地址为1的元素有 个。 (满分:5)
A. 1
B. 2
C. 3
D. 4
5. (满分:5)
A. A
B. B
C. C
D. D
6.设数据结果A=(D,R)，其中D={1,2,3,4}，R={r}，r={，，，}，则数据结构A是。 (满分:5)
A. 线性结构
B. 树型结构
C. 图型结构
D. 集合
7. (满分:5)
A. A
B. B
C. C
D. D
8.下列关于数据结构基本概念的叙述中，正确的是( )。 (满分:5)
A. 数据的逻辑结构分为表结构和树结构
B. 数据的存储结构分为线性结构和非线性结构
C. 数据元素是数据的基本单位
D. 结点是有独立含义的数据最小单位
9. (满分:5)
A. A
B. B
C. C
D. D
10.在一棵度为3的树中，度为3的结点个数为2，度为2的结点个数为1，则度为0的结点个数为。 (满分:5)
A. 4
B. 5
C. 6
D. 7
11.以下数据结构中哪一个是非线性结构。 (满分:5)
A. 队列
B. 线性表
C. 栈
D. 二叉树
12.栈的插入和删除操作在进行。 (满分:5)
A. 栈顶
B. 栈底
C. 任意位置
D. 指定位置
13.不定长文件是指。 (满分:5)
A. 文件的长度不固定
B. 记录的长度不固定
C. 字段的长度不固定
D. 关键字项的长度不固定
14.将长度为n的单链表链接在长度为m的单链表之后的算法的时间复杂度为。 (满分:5)
A. O（1）
B. O（n）
C. O（m）
D. O（m+n）
15.算法指的是。 (满分:5)
A. 计算机程序
B. 解决问题的计算方法
C. 排序算法
D. 解决问题的有限运算序列
16. (满分:5)
A. A
B. B
C. C
D. D
17. (满分:5)
A. A
B. B
C. C
D. D
18. (满分:5)
A. A
B. B
C. C
D. D
19.栈和队列的共同特点是。 (满分:5)
A. 只允许在端点处插入和删除元素
B. 都是先进后出
C. 都是先进先出
D. 没有共同点
20.设结点A有3个兄弟结点且结点B为结点A的双亲结点，则结点B的度数为。 (满分:5)
A. 3
B. 4
C. 5
D. 1
在做作业，求解题参考资料。
页:
[1]