文档介绍：数据结构试题库
单项选择题
下列程序段所代表的算法的时间复杂度为( D )。
x=n;
y=0;
while (x>=(y+1)*(y+1))
y++;
(A)O(n) (B)O(n2) (C)O(log2n) (D)O()
在一个长度为n的以顺序结构存储的线性表中,假设在线性表的任何位置删除元素的概率相等,则删除一个元素时线性表所需移动元素的平均次数为( B )。
(A) n2 (B)(n-1)/2 (C)(n+1)/2 (D)n/2
在一个栈顶指针为HS的链栈中插入一个*s结点时,应执行执行操作为( C )。
(A)HS->next=s; (B)s->next=HS->next;HS->next=s;
(C)s->next=HS;HS=s; (D)s->next=HS;HS=HS>next;
假设以带头结点的循环链表表示队列Q,并且队列只设一个头指针front,不设队列尾指针。若要进队一个元素*s,则在下列程序算法的空白处应添加的操作语句是( A )。
void AddQueue(struct linkqueue Q)
{ p=Q->front;
while(p->next!=Q->front) p=p->next;
}
(A)p->next=s;s->next=Q->front;
(B)Q->front->next=s;Q->front=s;
(C)s->next=p;p->next=Q->front;
(D)Q->front->next=s;s->next=p;
设高度为h的二叉树上只有度为0和度为2的结点,则此类二叉树中所包含的结点数至少为( B )。
(A)2h-1 (B)2h-1+1 (C)2h-1 (D)2h-1-3
现有数据集{53,30,37,12,45,24,96},从空二叉树逐个插入数据形成二叉排序树,若希望查找此二叉树中任一结点的平均查找长度最小,则应选择下面哪个序列输入( C )。
(A)45,24,53,12,37,96,30 (B) 30,24,12,37,45,96,53
(C) 37,24,12,30,53,45,96 (D) 12,24,30,37,45,53,96
有一组数值{5,12,9,20,3},用以构造哈夫曼树,则其带权路径长度WPL值为( D )。
(A)93 (B)96 (C)123 (D)103
已知一个有向图G的顶点v={v1,v2,v3,v4,v5,v6},其邻接表如下图所示,根据有向图的深度优先遍历算法,从顶点v1出发,所得到的顶点遍历序列是( B )。
(A)v1,v2,v3,v6,v4,v5 (B)v1,v2,v3,v6,v5,v4
(C)v1,v2,v5,v6,v3,v4 (D)v1,v2,v5,v3,v4,v6
v3 ^
v4 ^
v5
v5 ^
v6 ^
v1
v2
v2
v3
^
v3
v6 ^
v4
^
v5
v4
v6
^
设有m=2n-1个关键字,假设对每个关键字查找的概率相等,查找失败的概率为0,若采用二分法查找一个关键字,则平均查找长度为( D )。
(A)n-1 (B) n-n/m (C) (n-1)-n/m (D) (n-1)+n/m
已知一个待散列存储的线性表{18,81,58,34,26,75,67,49,93},散列函数为h(k)=k%11,散列地址空间为0~10。若采用线性探查法解决冲突,则平均查找长度为( A )。
(A)5/3 (B)13/9 (C)16/9 (D)3/2
下列程序段所代表的算法的时间复杂度为( C )。
y=n;
x=1;
while(x<=y)
x*=2;
(A)O(n) (B)O(n2) (C)O(log2n) (D)O()
在一个长度为n的以顺序结构存储的线性表中,假设在线性表的任何位置插入元素的概率相等,则插入一个元素时线性表所需移动元素的平均次数为( D )。
(A)n2 (B)(n+1)/2 (C)(n-1)/2 (D)n/2(p23)
若对一个已有序的线性表最频繁的操作是查找值为x的元素(假设存在的话),则采用( D )存储方式实现查找,其算法的时间复杂度为最小。(怀疑)
(A)单链表(B)双链表(C)单循环链表(D)顺序表
一个带头结点head的循环单链表为空的判断条件是( C )。
(A)head==NULL (B)head->next==NULL
(C)head->next==head (D)head!=NULL
若链队列HQ中只有一个结点,则队列的头指针和尾指针满足下列条件( D )。
(A)HQ->rear->next==HQ->front