更多"给定一个有n个元素的有序线性表。若采用顺序存储结构,则在等概率前提下,"的相关试题:
[填空题]给定一个具有n个元素的向量,建立一个有序单链表的时间复杂度是()。
[单项选择]线性表若采用链表存储结构,要求内存中可用存储单元地址 (35) 。
A. 必须连续
B. 部分地址必须连续
C. 一定不连续
D. 连续不连续均可
[单项选择]在等概率前提下,向一个采用顺序存储结构的n个元素线性表插入一个元素需要移动的元素个数平均为 (102) 。
A. n+1
B. n/2
C. (n+1)/2
D. n
[填空题]线性表若采用链式存储结构时,要求内存中可用存储单元的地址 【5】 。
[单项选择]将两个各有n个元素的有序表归并成一个有序表,其最少的比较次数是 (28) 。
A. n-1
B. n
C. 2n-1
D. 2n
[单项选择]对n个元素的有序表A[1..n]进行二分(折半)查找,则成功查找到表中的任意一个元素时,最多与A中的______个元素进行比较。
A. n-1
B. n/2
C. (log2n)-1
D. (log2n)+1
[单项选择]设有n个元素的向量,逐个输入其中的元素值,建立一个有序单链表的时间复杂度是()。
A. O(1)
B. O(n)
C. O(n2)
D. O(nlog2n)
[单项选择]
对长度为N的线性表进行查找,若采用顺序查找法,那么在最坏情况下所需要的比较次数为();若采用折半查找法,那么在最坏隋况下所需比较的次数为()。
若采用折半查找法,那么在最坏隋况下所需比较的次数为()。
A. N
B. N+1
C. N/2
D. (N+1)/2
[简答题]任意给定1,2,…,n指定为一棵树的先根遍历序列;同时任意给定这n个数值(1,2,…,n)的一个排列p1,p2,…pn为这棵树的后根遍历序列。
(1)根据这样的先根遍历序列和后根遍历序列,是否都可以得到一棵树如果能够,请简述理由(不要求形式化证明)。如果不能,请给出一个简单反例。
(2)如果能得到树,所得到的树是否唯一如果能够,请简述理由(不要求形式化证明)。如果不能,请给出一个简单反例。
[单项选择]对具有n个元素的有序序列进行二分查找时,______。
A. 查找元素所需的比较次数与元素的位置无关
B. 查找序列中任何一个元素所需要的比较次数不超过[log2(n+1)]
C. 元素位置越靠近序列后端,查找该元素所需的比较次数越少
D. 元素位置越靠近序列前端,查找该元素所需的比较次数越少
[填空题]在一个有n个元素的顺序表的第i个元素(1≤i≤n)之前插入一个新元素时,需要向后移动 【1】 个元素
[填空题]在一个有n个元素的顺序表的第i个元素(1≤i≤n)之前插入一个新元素时,需要向后移动 【2】 个元素。