数据结构试题库一、 单项选择题1 下列程序段所代表的算法的时间复杂度为（ D ）。x=n; y=0;while (x=(y+1)*(y+1) y+;(A)O(n) (B)O(n2) (C)O(log2n) (D)O()2 在一个长度为n的以顺序结构存储的线性表中，假设在线性表的任何位置删除元素的概率相等，则删除一个元素时线性表所需移动元素的平均次数为（ B ）。(A) n2 (B)(n-1)/2 (C)(n+1)/2 (D)n/23 在一个栈顶指针为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=HSnext;4 假设以带头结点的循环链表表示队列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;5 设高度为h的二叉树上只有度为0和度为2的结点，则此类二叉树中所包含的结点数至少为（ B ）。(A)2h-1 (B)2h-1+1 (C)2h-1 (D)2h-1-36 现有数据集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,967 有一组数值5,12,9,20,3，用以构造哈夫曼树，则其带权路径长度WPL值为（ D ）。(A)93 (B)96 (C)123 (D)1038 已知一个有向图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,v6v3 v4 v5v5 v6 v1v2v2v3v3v6 v4v5v4v69 设有m=2n-1个关键字，假设对每个关键字查找的概率相等，查找失败的概率为0，若采用二分法查找一个关键字，则平均查找长度为（ D ）。(A)n-1 (B) n-n/m (C) (n-1)-n/m (D) (n-1)+n/m10 已知一个待散列存储的线性表18,81,58,34,26,75,67,49,93，散列函数为h(k)=k%11，散列地址空间为010。若采用线性探查法解决冲突，则平均查找长度为（ A ）。(A)5/3 (B)13/9 (C)16/9 (D)3/211 下列程序段所代表的算法的时间复杂度为（ C ）。y=n;x=1;while(xnext=NULL(C)head-next=head (D)head!=NULL15 若链队列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-rear16 从一个栈顶指针为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-118 一棵左、右子树均不为空的二叉树在先序线索化后，其空指针域数为 （ B ）。(A)0 (B)1 (C)2 (D)不确定19 有一组数值5,12,9,20,3，用以构造哈夫曼树，则其带权路径长度WPL值为（ C ）。(A)49 (B)96 (C)103 (D)12520 在一个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，散列地址空间为010。若采用线性探查法解决冲突，则平均查找长度为（ A）。(A)5/3 (B)13/9 (C)16/9 (D)3/225 下列程序段所代表的算法的时间复杂度为（ D ）。 i=1;j=0; while(inext=p-next;p-next=s; (B)s-next=head;p-next=s;(C)s-next=p-next;p-next=head; (D)s-next=p-next; s-next=p;29 已知用循环链表表示的队列长度为n，若只设头指针，则出队和入队一个元素的时间复杂度分别是（ B ）。(A)O(1)和O(1) (B)O(1)和O(n) (C)O(n)和O(1) (D)O(n) 和O(n)30 设链队列Q的头指针和尾指针分别为front和rear，初始时队列为空，若向队列插入一个元素*s，则应执行的指针操作为（ C ）。(A)Q-front-next=s;s-next=Q-rear;Q-rear=NULL;(B)s-next=Q-front;Q-rear-next=s;Q-rear=NULL;(C)Q-rear-next=s;Q-rear=s;s-next=NULL;(D)Q-front-next=s;Q-rear=s;s-next=NULL;31 已知一个带权图的顶点集V和边集G分别为： V=1,2,3,4,5,6,7,8; E=(3,1)6，(3,4)7，(3,7)5，(1,2)3，(1,4)4，(4,7)8，(4,5)4，(7,8)5，(2,6)3，(2,5)5, (5,8)8, (5,6)5, (8,6)6, 则该图的最小生成树的权值为（ C ）。(A)24 (B)29 (C)30 (D)3132 当待排序的关键字个数n很小，且初始排列为逆序时，采用下列排序方法中的（ D ），算法的时间复杂度最小。(A)直接插入排序 (B)简单选择排序(C)冒泡排序 (D)快速排序33 对二叉排序树进行（ C ）遍历，可