北语17秋《数据结构》作业1234题目
17秋《数据结构》作业1一、单选题:【20道,总分:100分】
1. (满分:5)
A. A
B. B
C. C
D. D
2. (满分:5)
A. A
B. B
C. C
D. D
3.下面关于线性表的叙述错误的是。 (满分:5)
A. 线性表采用顺序存储必须占用一片连续的存储空间
B. 线性表采用链式存储不必占用一片连续的存储空间
C. 线性表采用链式存储便于插入和删除操作的实现
D. 线性表采用顺序存储便于插入和删除操作的实现
4. (满分:5)
A. A
B. B
C. C
D. D
5.数据结构有( )种基本逻辑结构。 (满分:5)
A. 1
B. 2
C. 3
D. 4
6.设哈夫曼树中的叶子结点总数为m，若用二叉链表作为存储结构，则该哈夫曼树中总共有个空指针域。 (满分:5)
A. 2m-1
B. 2m
C. 2m+1
D. 4m
7.设结点A有3个兄弟结点且结点B为结点A的双亲结点，则结点B的度数为。 (满分:5)
A. 3
B. 4
C. 5
D. 1
8.由权值分别为11,8,6,2,5的叶子结点生成一棵哈夫曼树，它的带权路径长度为。 (满分:5)
A. 24
B. 71
C. 48
D. 53
9. (满分:5)
A. A
B. B
C. C
D. D
10.用链接方式存储的队列，在进行插入运算时。 (满分:5)
A. 仅修改头指针
B. 头、尾指针都要修改
C. 仅修改尾指针
D. 头、尾指针可能都要修改
11. (满分:5)
A. A
B. B
C. C
D. D
12. (满分:5)
A. A
B. B
C. C
D. D
13.对于线性表（7,34,55,25,64,46,20,10）进行散列存储时，若选用H（K）=K%9作为散列函数，则散列地址为1的元素有 个。 (满分:5)
A. 1
B. 2
C. 3
D. 4
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.设有6个结点的无向图，该图至少应有条边才能确保是一个连通图。 (满分:5)
A. 5
B. 6
C. 7
D. 8
20.以下数据结构中哪一个是非线性结构。 (满分:5)
A. 队列
B. 线性表
C. 栈
D. 二叉树
17秋《数据结构》作业2
一、单选题:【20道,总分:100分】
1. (满分:5)
A. A
B. B
C. C
D. D
2. (满分:5)
A. A
B. B
C. C
D. D
3.若某表最常用的操作是在最后一个结点之后插入一个结点或删除最后一个结点，则采用存储方式最节省运算时间。 (满分:5)
A. 单链表
B. 给出表头指针的单循环链表
C. 双链表
D. 带头结点的双循环链表
4.设有5000个待排序的记录关键字，如果需要用最快的方法选出其中最小的10个记录关键字，则用下列方法可以达到此目的。 (满分:5)
A. 快速排序
B. 堆排序
C. 归并排序
D. 插入排序
5. (满分:5)
A. A
B. B
C. C
D. D
6.与单链表相比，双链表的优点之一是。 (满分:5)
A. 插入、删除操作更简单
B. 可以进行随机访问
C. 可以省略表头指针或表尾指针
D. 顺序访问相邻结点更灵活
7.设某有向图的邻接表中有n个表头结点和m个表结点，则该图中有条有向边。 (满分:5)
A. n
B. n-1
C. m
D. m-1
8.需要分配较大空间，插入和删除不需要移动元素的线性表，其存储结构是。 (满分:5)
A. 单链表
B. 静态链表
C. 线性链表
D. 顺序存储结构
9.通常要求同一逻辑结构中的所有数据元素具有相同的特性，这意味着。 (满分:5)
A. 数据元素具有同一特点
B. 不仅数据元素所包含的数据项的个数要相同，而且对应的数据项的类型要一致
C. 每个数据元素都一样
D. 数据元素所包含的数据项的个数要相等
10.下列四种排序中的空间复杂度最大。 (满分:5)
A. 插入排序
B. 冒泡排序
C. 堆排序
D. 归并排序
11.算法分析的目的是。 (满分:5)
A. 找出数据结构的合理性
B. 研究算法中的输入和输出的关系
C. 分析算法的效率以求改进
D. 分析算法的易读性和文档性
12.在存储数据时，通常不仅要存储各数据元素的值，而且还要存储。 (满分:5)
A. 数据的处理方法
B. 数据元素的类型
C. 数据元素之间的关系
D. 数据的存储方法
13. (满分:5)
A. A
B. B
C. C
D. D
14. (满分:5)
A. A
B. B
C. C
D. D
15. (满分:5)
A. A
B. B
C. C
D. D
16.如果最常用的操作是取第i个结点及其前驱，则采用存储方式最节省时间。 (满分:5)
A. 单链表
B. 双链表
C. 单循环链表
D. 顺序表
17.设一组初始记录关键字序列（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
18.如果对线性表的操作只有两种，即删除第一个元素，在最后一个元素的后面插入新元素，则最好使用。 (满分:5)
A. 只有表头指针没有表尾指针的循环单链表
B. 只有表尾指针没有表头指针的循环单链表
C. 非循环双链表
D. 循环双链表
19. (满分:5)
A. A
B. B
C. C
D. D
20.在长度为n的顺表表的第i个位置上插入一个元素（1≤i≤n+1），元素的移动次数为。 (满分:5)
A. n-i+1
B. n-i
C. i
D. i-1
17秋《数据结构》作业3
一、单选题:【20道,总分:100分】
1.单链表中，增加一个头结点的目的是为了。 (满分:5)
A. 使单链表至少有一个结点
B. 标识表结点中首结点的位置
C. 方便运算的实现
D. 说明单链表是线性表的链式存储
2.树最适合用来表示。 (满分:5)
A. 有序数据元素
B. 无序数据元素
C. 元素之间具有分支层次关系的数据
D. 元素之间无联系的数据
3. (满分:5)
A. A
B. B
C. C
D. D
4.以下不是队列的基本运算。 (满分:5)
A. 从队尾插入一个新元素
B. 从队列中删除第i个元素
C. 判断一个队列是否为空
D. 读取队头元素的值
5. (满分:5)
A. A
B. B
C. C
D. D
6.若已知一个栈序列是1,2,3,...,n，其输出序列为p1,p2,p3,...,pn，若p1=n，则pi为。 (满分:5)
A. i
B. n-i
C. n-i+1
D. 不确定
7. (满分:5)
A. A
B. B
C. C
D. D
8.栈和队列的共同点是。 (满分:5)
A. 都是先进后出
B. 都是先进先出
C. 只允许在端点处插入和删除元素
D. 没有共同点
9.对一个满二叉树，m个叶子，n个结点，深度为h，则。 (满分:5)
A. n=h+m
B. h+m=2n
C. m=h-1
D. n=2h-1
10.队列的先进先出特性是指。 (满分:5)
A. 最早插入队列中的元素总是最后被删除
B. 当同时进行插入、删除操作时，总是插入操作优先
C. 每当有删除操作时，总是要先做一次插入操作
D. 每次从队列中删除的总是最早插入的元素
11.用不带头结点的单链表存储队列，其头指针指向队头结点，尾指针指向队尾结点，则在进行出队操作时。 (满分:5)
A. 仅修改队头指针
B. 仅修改队尾指针
C. 队头、队尾指针都可能要修改
D. 队头、队尾指针都要修改
12.若长度为n的线性表采用顺序存储结构，在其第i个位置插入一个新元素的算法的时间复杂度为。 (满分:5)
A. O（0）
B. O（1）
C. O（n）
D. O（n2）
13.串是一种特殊的线性表，其特殊性体现在。 (满分:5)
A. 可以顺序存储
B. 数据元素是一个字符
C. 可以链式存储
D. 数据元素可以是多个字符
14. (满分:5)
A. A
B. B
C. C
D. D
15.允许对队列进行的操作有。 (满分:5)
A. 对队列中的元素排序
B. 取出最近进队的元素
C. 在队头元素之前插入元素
D. 删除队头元素
16.线性表是具有n个的有限序列。 (满分:5)
A. 字符
B. 数据元素
C. 数据项
D. 表元素
17. (满分:5)
A. A
B. B
C. C
D. D
18.线性表（a1,a2,...,an）以链式方式存储，访问第i位置元素的时间复杂度为。 (满分:5)
A. O（0）
B. O（1）
C. O（n）
D. O（n2）
19.输入序列为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
20.串的长度是指。 (满分:5)
A. 串中所含不同字母的个数
B. 串中所含字符的个数
C. 串中所含不同字符的个数
D. 串中所含非空格字符的个数
17秋《数据结构》作业4
一、单选题:【20道,总分:100分】
1. (满分:5)
A. A
B. B
C. C
D. D
2.有一个长度为12的有序表R,按二分查找法对该表进行查找,在表内各元素等概率情况下查找成功所需的平均比较次数为( )。 (满分:5)
A. 35/12
B. 37/12
C. 39/12
D. 43/12
3.具有10个叶子结点的二叉树中有个度为2的结点。 (满分:5)
A. 8
B. 9
C. 10
D. 11
4.在一个有向图中，所有顶点的入度之和等于所有顶点的出度之和的倍。 (满分:5)
A. 1/2
B. 1
C. 2
D. 4
5.采用邻接表存储的图的广度优先遍历算法类似于二叉树的。 (满分:5)
A. 先序遍历
B. 中序遍历
C. 后序遍历
D. 按层遍历
6. (满分:5)
A. A
B. B
C. C
D. D
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.若一棵二叉树具有10个度为2的结点，5个度为1的结点，则度为0的结点的个数是。 (满分:5)
A. 9
B. 11
C. 15
D. 不能确定
9.具有n个结点的连通图至少有条边。 (满分:5)
A. n-1
B. n
C. n（n-1）/2
D. 2n
10.在一个无向图中，所有顶点的度数之和等于所有边数的倍。 (满分:5)
A. 1/2
B. 1
C. 2
D. 4
11. (满分:5)
A. 索引非顺序文件
B. 索引顺序文件
C. 非顺序文件
D. 哈希文件
12. (满分:5)
A. 小于m的最大奇数
B. 小于m的最大素数
C. 小于m的最大偶数
D. 小于m的最大合数
13.顺序查找法适合于存储结构为的线性表。 (满分:5)
A. 散列存储
B. 顺序存储或链式存储
C. 压缩存储
D. 索引存储
14. (满分:5)
A. A
B. B
C. C
D. D
15.某二叉树结点的中序序列为ABCDEFG，后序序列为BDCAFGE，则其左子树中结点数目为。 (满分:5)
A. 3
B. 2
C. 4
D. 5
16.采用邻接表存储的图的深度优先遍历算法类似于二叉树的。 (满分:5)
A. 先序遍历
B. 中序遍历
C. 后序遍历
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.有一个有序表{1,3,9,12,32,41,45,62,75,77,82,95,100}，当折半查找值为82的结点时，次比较后查找成功。 (满分:5)
A. 11
B. 5
C. 4
D. 8
页:
[1]