UC知道关于数据结构的几个问题!!!
来源：百度知道 编辑：UC知道 时间：2024/06/04 15:09:58
1.顺序存储的线性表{a1,a2,..an}中删除一个节点,则该运算时间复杂度为
A:O(1) B:O(log2n) C:O(n) D:O(n~2)
2:设有一个顺序栈S,元素S1,S2,S3,S4,S5,S6依次入栈,若6个元素出栈的顺序是S2,S3,S4,S6,S5,S1,则该栈容量至少是()
A:2 B:3 C:4 D:5
3.在一个连队中,假设f和r分别为队首和队尾指针,则插入s所指节点的预算是()
A:f->next=s;f=s; B:r->next=s;r=s;
C:s->next=r;r=s C:f->next=f;f=f;
4.将递归算法转换成对应的非递归算法时,通常要使用()
A:栈 B队列 C连表 D树
5在对n个元素进行直接插入排序的过程中,共需要进行()趟
A:n B:n+1 Cn-1 D2n
6.仅带尾指针rear的单循环连表,表空的条件为_______
7.对于一个具有N个节点的单连表,在p所指节点之后插入一个新节点的时间复杂度为______,在给定值为X的节点之后插入一个新节点的时间复杂度为______
8.假定一组记录为(46,79,56,64,38,40,84,43)在冒泡排序的过程中进行第一趟排序时,元素79将最终下沉到第__个元素的位置
9.假定一组记录为(46,79,56,64,38,40,84,43),对其进行快速排序的第一次划分后,右区间内元素个数为___
第8题我感觉应该没变啊 ,因为79不是最大的数字也不是最小的数字,第一趟应该只把最大或者最小元素放第一个啊!其他不太懂望高手回答!
A:O(1) B:O(log2n) C:O(n) D:O(n~2)
2:设有一个顺序栈S,元素S1,S2,S3,S4,S5,S6依次入栈,若6个元素出栈的顺序是S2,S3,S4,S6,S5,S1,则该栈容量至少是()
A:2 B:3 C:4 D:5
3.在一个连队中,假设f和r分别为队首和队尾指针,则插入s所指节点的预算是()
A:f->next=s;f=s; B:r->next=s;r=s;
C:s->next=r;r=s C:f->next=f;f=f;
4.将递归算法转换成对应的非递归算法时,通常要使用()
A:栈 B队列 C连表 D树
5在对n个元素进行直接插入排序的过程中,共需要进行()趟
A:n B:n+1 Cn-1 D2n
6.仅带尾指针rear的单循环连表,表空的条件为_______
7.对于一个具有N个节点的单连表,在p所指节点之后插入一个新节点的时间复杂度为______,在给定值为X的节点之后插入一个新节点的时间复杂度为______
8.假定一组记录为(46,79,56,64,38,40,84,43)在冒泡排序的过程中进行第一趟排序时,元素79将最终下沉到第__个元素的位置
9.假定一组记录为(46,79,56,64,38,40,84,43),对其进行快速排序的第一次划分后,右区间内元素个数为___
第8题我感觉应该没变啊 ,因为79不是最大的数字也不是最小的数字,第一趟应该只把最大或者最小元素放第一个啊!其他不太懂望高手回答!
1.C
2.B
3.B
4.A
5.C
6.rear==NULL
7.O(1),O(n)
8.6
9.4
8。注意是冒泡排序，不是选择排序，你说的位置不变，可能因为你当初选择排序了。
1.D 2.B 3.C 4.A 5.C 6.rear==NULL 7.O(1),O(n) 8.6 9.4
第3题应该选择C，原因链队列插入只在尾部插入，只修改队尾指针即可，故只修改r。
第1题应该是O(n/2),也可说是O(n)，答案D如果是O(n/2)，应该选D，如果D是O(n^2)，则不该选D，而应该选C。