重庆大学网院数据结构第1次作业答案
重庆大学网院数据结构第1次作业答案一、单项选择题（本大题共60分，共 20 小题，每小题 3 分）
1. 将线性表的数据元素进行扩充，允许是带结构的线性表是( )。
A. 串
B. 树
C. 广义表
D. 栈
2. 一棵树中，（ ）没有前驱结点。
A. 分支结点
B. 叶结点
C. 树根结点
D. 空结点
3. 孩子兄弟表示法中，若要访问结点x的第i个孩子，则要先从firstchild域找到第1个孩子结点，然后沿着孩子结点的nextsibling域连续走（ ）步，便可找到x的第i个孩子。
A. 1
B. 2
C. i-1
D. i
4. 建堆是将所有元素按照初始顺序填充到一个（ ）中。
A. 二叉树
B. 平衡二叉树
C. 红黑树
D. 完全二叉树
5. 若n个顶点的无向图采用邻接矩阵存储方法，该邻接矩阵为一个什么矩阵？（）
A. 对称矩阵
B. 一般矩阵
C. 稀疏矩阵
D. 对角矩阵
6. 由3个结点所构成的二叉树有（ ）种形态。
A. 3
B. 4
C. 5
D. 6
7. 排序算法的作用是（ ）。
A. 让元素以递增的顺序排列
B. 让元素以递减的顺序排列
C. 让无序的数据组合变成有序的数据组合
D. 以上都不对
8. 下面关于折半查找的叙述正确的是 ( ) 。
A. 表必须有序，表可以顺序方式存储，也可以链表方式存储
B. 表必须有序且表中数据必须是整型，实型或字符型
C. 表必须有序，而且只能从小到大排列
D. 表必须有序，且表只能以顺序方式存储
9. 图中有关路径的定义是（ ）。
A. 由顶点和相邻顶点序偶构成的边所形成的序列
B. 由不同顶点所形成的序列
C. 由不同边所形成的序列
D. 上述定义都不是
10. 采用邻接表存储的图的深度优先遍历算法类似于二叉树的（）。
A. 先序遍历
B. 中序遍历
C. 后序遍历
D. 按层遍历
11. 设有50行60列的二维数组A，其元素长度为4字节，按行优先顺序存储，基地址为200，则元素A的存储地址为（ ）。
A. 3700
B. 4376
C. 3900
D. 4620
12. 迪杰斯特拉(Dijkstra)算法用于求解图上的单源点最短路径。本质上说，该算法是一种基于（）策略的算法。
A. 分治
B. 动态规划
C. 贪心
D. 回溯
13. 简单选择排序是一种（ ）。
A. 稳定的排序算法
B. 不稳定的排序算法
C. 无法确定其是否稳定
D. 以上都不对
14. 分别以下列序列构造二叉排序树，与用其它三个序列所构造的结果不同的是( ）。
A. （100，80， 90， 60， 120，110，130）
B. （100，120，110，130，80， 60， 90）
C. （100，60， 80， 90， 120，110，130）
D. (100，80，60， 90， 120，130，110)
15. 任何一个带权的无向连通图的最小生成树（ ）。
A. 只有一棵
B. 有一棵或多棵
C. 一定有多棵
D. 可能不存在
16. 弗罗伊德(Floyd)算法时间复杂度是（ ）。
A. file:///C:/Users/ADMINI~1/AppData/Local/Temp/msohtmlclip1/01/clip_image002.jpg
B.
file:///C:/Users/ADMINI~1/AppData/Local/Temp/msohtmlclip1/01/clip_image004.jpg
C.
file:///C:/Users/ADMINI~1/AppData/Local/Temp/msohtmlclip1/01/clip_image006.jpg
D.
file:///C:/Users/ADMINI~1/AppData/Local/Temp/msohtmlclip1/01/clip_image008.jpg
17. 设F是一个森林，B是由F转换得到的二叉树，F中有n个非叶结点，则B中右指针域为空的结点有（ ）个。
A. n-1
B. n
C. n+1
D. n+2
18. 设一个广义表中结点的个数为n，则求广义表深度算法的时间复杂度为（ ）。
A. O(1)
B. O(n)
C. O(n2)
D. O(log2n)
19. 设要将序列（q,h,c,y,p,a,m,s,r,d,f,x）中的关键码按字母升序重新排序，第一次交换位置的是（）。
A. a和x
B. p和f
C. p和d
D. y和r
20. 对于长度为n的顺序存储的线性表，访问结点和插入、删除结点的平均时间复杂度为（ ）。
A.
O(0)
B. O(1)
C. O(n)
D. O(n2)
二、判断题（本大题共40分，共 20 小题，每小题 2 分）
1. 任一查找树(二叉分类树)的平均查找时间都小于用顺序查找法查找同样结点的线性表的平均查找时间。
2. 对无序表用折半查找比顺序查找快。
3. 对于无向图来说，若深度优先遍历过程中遇到回边（即指向已访问过的顶点的边），则必定存在环。
4. 对一棵二叉排序树按前序方法遍历得出的结点序列是从小到大的序列。
5. 线性结构中，每一个结点都至少有一个直接前驱和一个直接后继。
6. 排序的稳定性是指排序算法中的比较次数保持不变，且算法能够终止。
7. n个顶点的连通图至少n-1条边。
8. Dijkstra最短路径算法从源点到其余各顶点的最短路径的路径长度按递增次序依次产生。
9. 二叉排序树删除一个结点后，仍是二叉排序树。
10. 二叉树中每个结点的两棵子树的高度差等于1。
11. 树中的每个结点有不唯一的一个双亲结点。
12. 克鲁斯卡尔算法适应范围为稀疏图。
13. 在稀疏矩阵的顺序存储中，利用一个数组来存储非零元素，该数组的长度应等于对应三元组线性表的长度。
14. 在有n个顶点的有向图中，若要使任意两点间可以互相到达，则至少需要n条弧。
15. 图的遍历算法有深度优先搜索算法和广度优先搜索算法。
16. 已知单链表中某一结点由p指向，求此后继结点存储地址的操作为p=p->next。
17. 在散列检索中，“比较”操作一般也是不可避免的。
18. 在广义表的存储结构中，每个结点均包含有3个域。
19. 求有向图G=(V，E)中每一对顶点间的最短路径，用Dijkstra算法和弗罗伊德算法，时间复杂度都是O(n3) 。
20. 用顺序方法存储一般的二叉树,若在树中需要经常插入和删除结点时，有大量的移动结点。
答案：
页:
[1]