西交21春《数据结构》在线作业【标准答案】
发布网友
发布时间：3小时前
共1个回答
热心网友
时间：2小时前
西交《数据结构》在线作业标准答案
一、单选题
1. 设顺序表的长度为n，则顺序查找的平均比较次数为（C）。
2. 在二叉排序树中插入一个关键字值的平均时间复杂度为（B）。
3. 任何一个非空二叉树中的叶子结点，在前序遍历、中序遍历和后序遍历中的相对位置（B）不会发生改变。
4. 队列是一种（A）的线性表。
5. 下列存储形式中，（C）不是树的存储形式
6. 设某二叉树中度数为0的结点数为N0，度数为1的结点数为Nl，度数为2的结点数为N2，则下列等式成立的是（C）。
7. 下面关于线性表的叙述错误的是（D）。
8. 设用链表作为栈的存储结构则退栈操作（B）必须判别栈是否为空
9. 下列各种排序算法中平均时间复杂度为O（n）是（D）。
10. 深度为h的满二叉树,第i层有( A )个结点。
11. 设某哈夫曼树中有199个结点，则该哈夫曼树中有（B）个叶子结点。
12. 设一棵完全二叉树中有65个结点，则该完全二叉树的深度为（B）。
13. 下述陈述中正确的是（A）串是一种特殊的线性表
14. {图}答案为（D）D
15. 设树T的度为4，其中度为1，2，3和4的结点个数分别为4，2，1，1 则T中的叶子数为（D）8
16. 执行一趟快速排序能够得到的序列是（A）[41，12，34，45，27]55[72，63]
17. 设有6个结点的无向图，该图至少应有（A）5条边才能确保是一个连通图。
18. 设指针变量p指向单链表中结点A，若删除单链表中结点A，则需要修改指针的操作序列为（A）q=p->next；p->data=q->data；p->next=q->next；free(q)；
19. 图的深度优先遍历算法类似于二叉树的（A）前序遍历
20. 栈的插入和删除操作在（A）栈顶进行。
21. 设某强连通图中有n个顶点，则该强连通图中至少有（C）n条边。
22. 判断一个图中是否存在回路可以利用（C）拓扑排序方法。
23. 一个栈的输入序列为123…n，若输出序列的第一个元素是n，则第i个输出的元素是（B）n-i+1
24. 将长度为n的单链表链接在长度为m的单链表之后的算法的时间复杂度为（C）O（m）
25. 某堆栈的输入序列为1，2，3，……，n-1，n，输出序列的第一个元素是n，则第i个输出的元素是（A）n-i+1
26. 在一个长度为n的顺序线性表中顺序查找值为x的元素时，查找成功时的平均查找长度为（C）(n+1)/2
27. （B）中序遍历可以得到一个从小到大的有序序列。
28. 判断一个图中是否存在回路可以利用（D）图的遍历方法。
29. {图}答案为（D）D
30. 栈和队列的相同之处在于（C）只允许在端点进行插入和删除
二、判断题
31. 对具有n个元素的序列来采用冒泡排序法进行排序，排序的趟数为n-1。正确
32. 一棵m阶B树中每个结点最多有m个关键码，最少有2个关键码。错误
33. 设一棵二叉树的先序序列和后序序列，则能够唯一确定出该二叉树的形状。正确
34. 采用循环链表作为存储结构的队列称为循环队列。正确
35. 图可以没有边，但不能没有顶点。正确
36. 子串“ABC”在主串“AABCABCD”中的位置为3。错误
37. 从本质上看，文件是一种非线性结构。错误
38. 满二叉树一定是完全二叉树，完全二叉树不一定是满二叉树。正确
39. 哈夫曼树中有度数为1的结点。错误
40. 若一个叶子结点是某二叉树的中序遍历序列的最后一个结点，则它必是该二叉树的先序遍历序列中的最后一个结点。正确
41. 用邻接矩阵作为图的存储结构时，则其所占用的存储空间与图中顶点数无关而与图中边数有关。错误
42. 在线性表的链式存储结构中，逻辑上相邻的两个元素在物理位置上并不一定紧邻。正确
43. 为度量一个搜索算法的性能，需要在时间和空间方面进行权衡。正确
44. 栈和队列都是存取点的线性结构。正确
45. {图}答案为（D）D
46. 在链队列上做出队操作时，会改变front指针的值。正确
47. 设串S的长度为n,则S的子串个数为n(n+1)/2。正确
48. 单链表形式的队列,头指针F指向队列的第一个结点,尾指针R指向队列的最后一个结点。正确
49. 向二叉排序树中插入一个结点需要比较的次数可能大于该二叉树的高度。正确
50. 除了插入和删除操作之外，数组的操作还包括存取、修改、检索和排序。正确
热心网友
时间：2小时前
西交《数据结构》在线作业标准答案
一、单选题
1. 设顺序表的长度为n，则顺序查找的平均比较次数为（C）。
2. 在二叉排序树中插入一个关键字值的平均时间复杂度为（B）。
3. 任何一个非空二叉树中的叶子结点，在前序遍历、中序遍历和后序遍历中的相对位置（B）不会发生改变。
4. 队列是一种（A）的线性表。
5. 下列存储形式中，（C）不是树的存储形式
6. 设某二叉树中度数为0的结点数为N0，度数为1的结点数为Nl，度数为2的结点数为N2，则下列等式成立的是（C）。
7. 下面关于线性表的叙述错误的是（D）。
8. 设用链表作为栈的存储结构则退栈操作（B）必须判别栈是否为空
9. 下列各种排序算法中平均时间复杂度为O（n）是（D）。
10. 深度为h的满二叉树,第i层有( A )个结点。
11. 设某哈夫曼树中有199个结点，则该哈夫曼树中有（B）个叶子结点。
12. 设一棵完全二叉树中有65个结点，则该完全二叉树的深度为（B）。
13. 下述陈述中正确的是（A）串是一种特殊的线性表
14. {图}答案为（D）D
15. 设树T的度为4，其中度为1，2，3和4的结点个数分别为4，2，1，1 则T中的叶子数为（D）8
16. 执行一趟快速排序能够得到的序列是（A）[41，12，34，45，27]55[72，63]
17. 设有6个结点的无向图，该图至少应有（A）5条边才能确保是一个连通图。
18. 设指针变量p指向单链表中结点A，若删除单链表中结点A，则需要修改指针的操作序列为（A）q=p->next；p->data=q->data；p->next=q->next；free(q)；
19. 图的深度优先遍历算法类似于二叉树的（A）前序遍历
20. 栈的插入和删除操作在（A）栈顶进行。
21. 设某强连通图中有n个顶点，则该强连通图中至少有（C）n条边。
22. 判断一个图中是否存在回路可以利用（C）拓扑排序方法。
23. 一个栈的输入序列为123…n，若输出序列的第一个元素是n，则第i个输出的元素是（B）n-i+1
24. 将长度为n的单链表链接在长度为m的单链表之后的算法的时间复杂度为（C）O（m）
25. 某堆栈的输入序列为1，2，3，……，n-1，n，输出序列的第一个元素是n，则第i个输出的元素是（A）n-i+1
26. 在一个长度为n的顺序线性表中顺序查找值为x的元素时，查找成功时的平均查找长度为（C）(n+1)/2
27. （B）中序遍历可以得到一个从小到大的有序序列。
28. 判断一个图中是否存在回路可以利用（D）图的遍历方法。
29. {图}答案为（D）D
30. 栈和队列的相同之处在于（C）只允许在端点进行插入和删除
二、判断题
31. 对具有n个元素的序列来采用冒泡排序法进行排序，排序的趟数为n-1。正确
32. 一棵m阶B树中每个结点最多有m个关键码，最少有2个关键码。错误
33. 设一棵二叉树的先序序列和后序序列，则能够唯一确定出该二叉树的形状。正确
34. 采用循环链表作为存储结构的队列称为循环队列。正确
35. 图可以没有边，但不能没有顶点。正确
36. 子串“ABC”在主串“AABCABCD”中的位置为3。错误
37. 从本质上看，文件是一种非线性结构。错误
38. 满二叉树一定是完全二叉树，完全二叉树不一定是满二叉树。正确
39. 哈夫曼树中有度数为1的结点。错误
40. 若一个叶子结点是某二叉树的中序遍历序列的最后一个结点，则它必是该二叉树的先序遍历序列中的最后一个结点。正确
41. 用邻接矩阵作为图的存储结构时，则其所占用的存储空间与图中顶点数无关而与图中边数有关。错误
42. 在线性表的链式存储结构中，逻辑上相邻的两个元素在物理位置上并不一定紧邻。正确
43. 为度量一个搜索算法的性能，需要在时间和空间方面进行权衡。正确
44. 栈和队列都是存取点的线性结构。正确
45. {图}答案为（D）D
46. 在链队列上做出队操作时，会改变front指针的值。正确
47. 设串S的长度为n,则S的子串个数为n(n+1)/2。正确
48. 单链表形式的队列,头指针F指向队列的第一个结点,尾指针R指向队列的最后一个结点。正确
49. 向二叉排序树中插入一个结点需要比较的次数可能大于该二叉树的高度。正确
50. 除了插入和删除操作之外，数组的操作还包括存取、修改、检索和排序。正确
