数据结构试题库 Last updated on the afternoon of January 3, 2021
数据结构试题库
一、单项选择题
1．下列程序段所代表的算法的时间复杂度为（D）。
x=n;
y=0;
while(x>=(y+1)*(y+1))
y++;
(A)O(n)(B)O(n2)(C)O(log2n)(D)O(n)
2．在一个长度为n的以顺序结构存储的线性表中，假设在线性表的任何位置删除元素的概率相等，则删除一个元素时线性表所需移动元素的平均次数为（B）。
(A)n2(B)(n-1)/2(C)(n+1)/2(D)n/2
3．在一个栈顶指针为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;
4．假设以带头结点的循环链表表示队列Q，并且队列只设一个头指针front，不设队列尾指针。若要进队一个元素*s，则在下列程序算法的空白处应添加的操作语句是（A）。
voidAddQueue(structlinkqueueQ)
{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;
5．设高度为h的二叉树上只有度为0和度为2的结点，则此类二叉树中所包含的结点数至少为（B）。
(A)2h-1(B)2h-1+1(C)2h-1(D)2h-1-3
6．现有数据集{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
7．有一组数值{5,12,9,20,3}，用以构造哈夫曼树，则其带权路径长度WPL值为（D）。
(A)93(B)96(C)123(D)103
8．已知一个有向图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
9．设有m=2n-1个关键字，假设对每个关键字查找的概率相等，查找失败的概率为0，若采用二分法查找一个关键字，则平均查找长度为（D）。
(A)n-1(B)n-n/m(C)(n-1)-n/m(D)(n-1)+n/m
10．已知一个待散列存储的线性表{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
11．下列程序段所代表的算法的时间复杂度为（C）。
y=n;
x=1;
while(x<=y)
x*=2;
(A)O(n)(B)O(n2)(C)O(log2n)(D)O(n)
12．在一个长度为n的以顺序结构存储的线性表中，假设在线性表的任何位置插入元素的概率相等，则插入一个元素时线性表所需移动元素的平均次数为（B）。
(A)n2(B)(n+1)/2(C)(n-1)/2(D)n/2
13．若对一个已有序的线性表最频繁的操作是查找值为x的元素(假设存在的话)，则采用（D）存储方式实现查找，其算法的时间复杂度为最小。
(A)单链表(B)双链表(C)单循环链表(D)顺序表
14．一个带头结点head的循环单链表为空的判断条件是（C）。
(A)head==NULL(B)head->next==NULL
(C)head->next==head(D)head!=NULL
15．若链队列HQ中只有一个结点，则队列的头指针和尾指针满足下列条件（D）。
(A)HQ->rear->next==HQ->front(B)HQ->front->next==HQ->rear->next
(C)HQ->front==HQ->rear(D)HQ->front->next==HQ->rear
16．从一个栈顶指针为HS的链栈中删除一个结点时，用x保存被删除结点的值，则应执行操作为（A）。
(A)x=HS->data;HS=HS->next;(B)x=HS->data;HS->NEXT=NULL;
(C)HS=HS->next;x=HS->data;(D)x=HS->data;HS=NULL;
17．一棵有n个结点的满二叉树，有m个叶子结点，深度为h，那么n、m和h满足条件（D）。
(A)n=m+h(B)h+m=2n(C)m=h-1(D)n=2h-1
18．一棵左、右子树均不为空的二叉树在先序线索化后，其空指针域数为（B）。
(A)0(B)1(C)2(D)不确定
19．有一组数值{5,12,9,20,3}，用以构造哈夫曼树，则其带权路径长度WPL值为（C）。
(A)49(B)96(C)103(D)125
20．在一个n个结点的二叉排序树中查找一个关键字，进行关键字比较次数最大值为（A）。
(A)n(B)n/2(C)log2n(D)n*log2n
21．已知有向图G=(V,E)，其中V={v1,v2,v3,v4,v5,v6}，则下列边集合E中
（A）所对应的有向图没有拓扑序列。
(A)E={,,,,,,,}
(B)E={,,,,,,,}
(C)E={,,,,,,,,,}
(D)E={,,,,,,,}
22．冒泡排序算法在最好情况下的时间复杂度为（B）。
(A)O(log2n)(B)O(n)(C)O(1)(D)O(n2)
23．在下列内部排序方法中，排序时不稳定的，而且关键字的比较次数与记录的初始排列次序无关的是（D）。
(A)快速排序(B)冒泡排序(C)归并排序(D)堆排序
24．已知一个待散列存储的线性表{18,81,58,34,26,75,67,49,93}，散列函数为h(k)=k%11，散列地址空间为0~10。若采用线性探查法解决冲突，则平均查找长度为（C）。
(A)5/3(B)13/9(C)16/9(D)3/2
25．下列程序段所代表的算法的时间复杂度为（D）。
i=1;j=0;
while(i<=n){
i+=j;
