北语14春《数据结构》作业答案
北语14春《数据结构》作业1试卷总分：100 测试时间：--
一、单选题（共20道试题，共100分。）
1.由权值分别为11,8,6,2,5的叶子结点生成一棵哈夫曼树，它的带权路径长度为___。
A. 24
B. 71
C. 48
D. 53
满分：5分
2.
A. A
B. B
C. C
D. D
满分：5分
3.
A. A
B. B
C. C
D. D
满分：5分
4.对于线性表（7,34,55,25,64,46,20,10）进行散列存储时，若选用H（K）=K%9作为散列函数，则散列地址为1的元素有 ___个。
A. 1
B. 2
C. 3
D. 4
满分：5分
5.
A. A
B. B
C. C
D. D
满分：5分
6.设数据结果A=(D,R)，其中D={1,2,3,4}，R={r}，r={<1,2>，<2,3>，<3,4>，<4,1>}，则数据结构A是___。
A. 线性结构
B. 树型结构
C. 图型结构
D. 集合
满分：5分
7.若有18个元素的有序表存放在一堆数组A中，第一个元素放A中，现进行二分查找，则查找A的比较序列的下标依次为___。
A. 1,2,3
B. 9,5,2,3
C. 9,5,3
D. 9,4,2,3
满分：5分
8.
下列关于数据结构基本概念的叙述中，正确的是______。
A. 数据的逻辑结构分为表结构和树结构
B.
数据的存储结构分为线性结构和非线性结构
C. 数据元素是数据的基本单位
D.
结点是有独立含义的数据最小单位
满分：5分
9.在一个长度为n的顺序线性表中顺序查找值为x的元素时，查找成功时的平均查找长度（即x与元素的平均比较次数，假定查找每个元素的概率都相等）为___。
A. n
B. n/2
C. (n+1)/2
D. (n-1)/2
满分：5分
10.线性表采用链式存储时，结点的存储地址___。
A. 必须是不连续的
B. 连续与否均可
C. 必须是连续的
D. 和头结点的存储地址相连续
满分：5分
11.下面关于线性表的叙述错误的是___。
A. 线性表采用顺序存储必须占用一片连续的存储空间
B. 线性表采用链式存储不必占用一片连续的存储空间
C. 线性表采用链式存储便于插入和删除操作的实现
D. 线性表采用顺序存储便于插入和删除操作的实现
满分：5分
12.
A. A
B. B
C. C
D. D
满分：5分
13.
A. A
B. B
C. C
D. D
满分：5分
14.在一棵度为3的树中，度为3的结点个数为2，度为2的结点个数为1，则度为0的结点个数为___。
A. 4
B. 5
C. 6
D. 7
满分：5分
15.
A. A
B. B
C. C
D. D
满分：5分
16.将长度为n的单链表链接在长度为m的单链表之后的算法的时间复杂度为___。
A. O（1）
B. O（n）
C. O（m）
D. O（m+n）
满分：5分
17.以下数据结构中哪一个是非线性结构___。
A. 队列
B. 线性表
C. 栈
D. 二叉树
满分：5分
18.
A. A
B. B
C. C
D. D
满分：5分
19.
A. A
B. B
C. C
D. D
满分：5分
20.设哈夫曼树中的叶子结点总数为m，若用二叉链表作为存储结构，则该哈夫曼树中总共有___个空指针域。
A. 2m-1
B. 2m
C. 2m+1
D. 4m
14春《数据结构》作业2
试卷总分：100 测试时间：--
一、单选题（共20道试题，共100分。）
1.
A. A
B. B
C. C
D. D
满分：5分
2.若某表最常用的操作是在最后一个结点之后插入一个结点或删除最后一个结点，则采用___存储方式最节省运算时间。
A. 单链表
B. 给出表头指针的单循环链表
C. 双链表
D. 带头结点的双循环链表
满分：5分
3.下列四种排序中___的空间复杂度最大。
A. 插入排序
B. 冒泡排序
C. 堆排序
D. 归并排序
满分：5分
4.
A. A
B. B
C. C
D. D
满分：5分
5.如果最常用的操作是取第i个结点及其前驱，则采用___存储方式最节省时间。
A. 单链表
B. 双链表
C. 单循环链表
D. 顺序表
满分：5分
6.需要分配较大空间，插入和删除不需要移动元素的线性表，其存储结构是___。
A. 单链表
B. 静态链表
C. 线性链表
D. 顺序存储结构
满分：5分
7.
A. A
B. B
C. C
D. D
满分：5分
8.
A. A
B. B
C. C
D. D
满分：5分
9.排序方法中，从未排序序列中依次取出元素与已排序序列中的元素进行比较，将其放入已排序序列的正确位置上的方法，称为___。
A. 希尔排序
B. 冒泡排序
C. 插入排序
D. 选择排序
满分：5分
10.数据结构在计算机内存中的表示是指___。
A. 数据的存储结构
B. 数据结构
C. 数据的逻辑结构
D. 数据元素之间的关系
满分：5分
11.设某有向图中有n个顶点，则该有向图对应的邻接表中有___个表头结点。
A. n-1
B. n
C. n+1
D. 2n-1
满分：5分
12.通常要求同一逻辑结构中的所有数据元素具有相同的特性，这意味着___。
A. 数据元素具有同一特点
B. 不仅数据元素所包含的数据项的个数要相同，而且对应的数据项的类型要一致
C. 每个数据元素都一样
D. 数据元素所包含的数据项的个数要相等
满分：5分
13.
A. a
B. b
C. c
D. d
满分：5分
14.
A. A
B. B
C. C
D. D
满分：5分
15.设一组初始记录关键字序列为（345,253,674,924,627），则用基数排序需要进行___趟的分配和回收才能使得初始关键字序列变成有序序列。
A. 3
B. 4
C. 5
D. 8
满分：5分
16.
A. A
B. B
C. C
D. D
满分：5分
17.在存储数据时，通常不仅要存储各数据元素的值，而且还要存储___。
A. 数据的处理方法
B. 数据元素的类型
C. 数据元素之间的关系
D. 数据的存储方法
满分：5分
18.在一个长度为n（n>1）的单链表上，设有头和尾两个指针，执行___操作与链表的长度有关。
A. 删除单链表中的第一个元素
B. 删除单链表中的最后一个元素
C. 在单链表第一个元素前插入一个新元素
D. 在单链表最后一个元素后插入一个新元素
满分：5分
19.与单链表相比，双链表的优点之一是___。
A. 插入、删除操作更简单
B. 可以进行随机访问
C. 可以省略表头指针或表尾指针
D. 顺序访问相邻结点更灵活
满分：5分
20.设一组初始记录关键字序列（5,2,6,3,8），以第一个记录关键字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
14春《数据结构》作业3
试卷总分：100 测试时间：--
一、单选题（共20道试题，共100分。）
1.下述哪一条是顺序存储结构的优点___。
A. 插入运算方便
B. 可方便地用于各种逻辑结构的存储表示
C. 存储密度大
D. 删除运算方便
满分：5分
2.
A. A
B. B
C. C
D. D
满分：5分
3.
A. A
B. B
C. C
D. D
满分：5分
4.线性表（a1,a2,...,an）以链式方式存储，访问第i位置元素的时间复杂度为___。
A. O（0）
B. O（1）
C. O（n）
D. O（n2）
满分：5分
5.若长度为n的线性表采用顺序存储结构，在其第i个位置插入一个新元素的算法的时间复杂度为___。
A. O（0）
B. O（1）
C. O（n）
D. O（n2）
满分：5分
6.单链表中，增加一个头结点的目的是为了___。
A. 使单链表至少有一个结点
B. 标识表结点中首结点的位置
C. 方便运算的实现
D. 说明单链表是线性表的链式存储
满分：5分
7.
A. A
B. B
C. C
D. D
满分：5分
8.串是一种特殊的线性表，其特殊性体现在___。
A. 可以顺序存储
B. 数据元素是一个字符
C. 可以链式存储
D. 数据元素可以是多个字符
满分：5分
9.线性表的链式存储结构是一种___。
A. 随机存取的存储结构
B. 顺序存取的存储结构
C. 索引存取的存储结构
D. Hash存取的存储结构
满分：5分
10.
A. A
B. B
C. C
D. D
满分：5分
11.输入序列为ABC，可以变为CBA时，经过的栈操作为___。
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
满分：5分
12.用不带头结点的单链表存储队列，其头指针指向队头结点，尾指针指向队尾结点，则在进行出队操作时___。
A. 仅修改队头指针
B. 仅修改队尾指针
C. 队头、队尾指针都可能要修改
D. 队头、队尾指针都要修改
满分：5分
13.对于顺序存储的线性表，访问结点和增加、删除结点的时间复杂度为___。
A. O（n）O（n）
B. O（n）O（1）
C. O（1）O（1）
D. O（1）O（n）
满分：5分
14.
A. A
B. B
C. C
D. D
满分：5分
15.任何一棵二叉树的叶子结点在前序、中序和后序遍历序列中的相对次序___。
A. 不发生改变
B. 发生改变
C. 不能确定
D. 以上都不对
满分：5分
16.设计一个判别表达式中左、右括号是否配对出现的算法，采用___数据结构最佳。
A. 线性表的顺序存储结构
B. 队列
C. 线性表的链式存储结构
D. 栈
满分：5分
17.
A. A
B. B
C. C
D. D
满分：5分
18.对一个满二叉树，m个叶子，n个结点，深度为h，则___。
A. n=h+m
B. h+m=2n
C. m=h-1
D. n=2h-1
满分：5分
19.树最适合用来表示___。
A. 有序数据元素
B. 无序数据元素
C. 元素之间具有分支层次关系的数据
D. 元素之间无联系的数据
满分：5分
20.以下___不是队列的基本运算。
A. 从队尾插入一个新元素
B. 从队列中删除第i个元素
C. 判断一个队列是否为空
D. 读取队头元素的值
14春《数据结构》作业4
试卷总分：100 测试时间：--
一、单选题（共20道试题，共100分。）
1.
A. A
B. B
C. C
D. D
满分：5分
2.广义表（（a），a）的表头是___。
A.
a
B.
()
C.
(a)
D.
((a))
满分：5分
3.
A.
小于m的最大奇数
B.
小于m的最大素数
C.
小于m的最大偶数
D.
小于m的最大合数
满分：5分
4.
A. 索引非顺序文件
B. 索引顺序文件
C. 非顺序文件
D. 哈希文件
满分：5分
5.若一棵二叉树具有10个度为2的结点，5个度为1的结点，则度为0的结点的个数是___。
A. 9
B. 11
C. 15
D. 不能确定
满分：5分
6.
A. A
B. B
C. C
D. D
满分：5分
7.具有10个叶子结点的二叉树中有___个度为2的结点。
A. 8
B. 9
C. 10
D. 11
满分：5分
8.有一个有序表{1,3,9,12,32,41,45,62,75,77,82,95,100}，当折半查找值为82的结点时，___次比较后查找成功。
A. 11
B. 5
C. 4
D. 8
满分：5分
9.采用邻接表存储的图的广度优先遍历算法类似于二叉树的___。
A. 先序遍历
B. 中序遍历
C. 后序遍历
D. 按层遍历
满分：5分
10.顺序查找法适合于存储结构为___的线性表。
A. 散列存储
B. 顺序存储或链式存储
C. 压缩存储
D. 索引存储
满分：5分
11.
有一个有序表{1，4，6，10，18，35，42，53，67，71，78，84，92，99}，当用二分查找法查找键值为84的结点时，经____次比较后查找成功。
A.
2
B.
3
C.
4
D.
12
满分：5分
12.
A. A
B. B
C. C
D. D
满分：5分
13.
有一个长度为12的有序表R,按二分查找法对该表进行查找,在表内各元素等概率情况下查找成功所需的平均比较次数为____。
A.
35/12
B.
37/12
C.
39/12
D.
43/12
满分：5分
14.某二叉树结点的中序序列为ABCDEFG，后序序列为BDCAFGE，则其左子树中结点数目为___。
A. 3
B. 2
C. 4
D. 5
满分：5分
15.具有n个结点的连通图至少有___条边。
A. n-1
B. n
C. n（n-1）/2
D. 2n
满分：5分
16.在一个无向图中，所有顶点的度数之和等于所有边数的___倍。
A. 1/2
B. 1
C. 2
D. 4
满分：5分
17.采用邻接表存储的图的深度优先遍历算法类似于二叉树的___。
A. 先序遍历
B. 中序遍历
C. 后序遍历
D. 按层遍历
满分：5分
18.
A. A
B. B
C. C
D. D
满分：5分
19.对线性表进行折半查找时，要求线性表必须___。
A. 以顺序方式存储
B. 以顺序方式存储，且结点按关键字有序排序
C. 以链式方式存储
D. 以链式方式存储，且结点按关键字有序排序
满分：5分
20.
A. A
B. B
C. C
D. D
满分：5分
页:
[1]