数据结构试题库

第1页共100页数据结构试题库一、单项选择题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/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）。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第2页共100页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,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,v6v1v2^v3v4^v5v6^9．设有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，散列地址空间为0~10。若采用线性探查法解决冲突，则平均查找长度为（A）。(A)5/3(B)13/9(C)16/9(D)3/211．下列程序段所代表的算法的时间复杂度为（C）。y=n;x=1;v2v5v4^v3v5^v4v6^v6^v3^第3页共100页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/213．若对一个已有序的线性表最频繁的操作是查找值为x的元素(假设存在的话)，则采用（D）存储方式实现查找，其算法的时间复杂度为最小。(A)单链表(B)双链表(C)单循环链表(D)顺序表14．一个带头结点head的循环单链表为空的判断条件是（C）。(A)head==NULL(B)head-next==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）。第4页共100页(A)49(B)96(C)103(D)12520．在一个n个结点的二叉排序树中查找一个关键字，进行关键字比较次数最大值为（A）。(A)n(B)n/2(C)log2n(D)n*log2n21．已知有向图G=(V,E)，其中V={v1,v2,v3,v4,v5,v6}，则下列边集合E中（A）所对应的有向图没有拓扑序列。(A)E={v2,v1,v6,v2,v1,v3,v2,v3,v5,v3,v3,v4,v4,v6,v5,v6}(B)E={v1,v2,v1,v3,v1,v4,v3,v5,v3,v2,v4,v5,v6,v5,v6,v4}(C)E={v1,v3,v1,v4,v1,v5,v2,v3,v2,v2,v3,v5,v3,v6,v4,v5,v4,v6,v5,v6}(D)E={v1,v2,v1,v3,v2,v3,v1,v4,v2,v5,v3,v6,v4,v6,v5,v6}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/225．下列程序段所代表的算法的时间复杂度为（D）。i=1;j=0;while(i=n){i+=j;j++;}(A)O(n)(B)O(n2)(C)O(log2n)(D)O(n)第5页共100页26．将两个各有n个元素的有序表归并成一个有序表，在最坏的情况下，其比较次数是（A）。(A)2n-1(B)n(C)n+1(D)n-127．若某链表中最常用的操作是在最后的一个结点之后插入一个结点或删除最后一个结点，则采用（D）存储方式最节省运行时间。(A)单链表(B)单循环链表(C)无头双向链表(D)带头双向链表28．已知head是一个非空单链表的头指针，指针p指向单链表的最后一个结点，若要在p之后插入一个新结点*s，并将单链表变为循环单链表，则应执行的操作是（B）。(A)s-next=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），算法的时间复杂度最小。第6页共100页(A)直接插入排序(B)简单选择排序(C)冒泡排序(D)快速排序33．对二叉排序树进行（C）遍历，可以得到该二叉树所有结点构成的排序序列。(A)层次(B)前序(C)中序(D)后序34．已知一个长度为12的线性表（8，2，5，7，12，3，10，4，1，6，9，11），并将线性表中的元素依次插入到一个原先为空的二叉排序树中去。假设查找每一个元素的概率相同，则查找该二叉树中任一结点的平均查找长度为（A）。(A)10/3(B)13/3(C)37/12(D)13/235．一组关键字序列{15，92，124，5，27，28，18，6，36，34，30，26，32，259}，将它们用散列函数H(key)=keyMOD11按顺序散列到HASH表HT（0:10）中，用链地址解决冲突。假设查找每一个元素的概率相同，则查找该HASH表中任一元素的平均查找长度为（C）。(A)3/2(B)10/7(C)11/7(D)9/736．以数据集{4，5，6，7，12，18，10}为结点权值所构造的哈夫曼树，则其带权路径长度WPL为（A）。(A)165(B)203(C)124(D)18737．假定对线性表R[0…n-1]进行分块查找，若将表均匀地分为b块，每块含有n/b个记录；又假定表中每个记录的查找概率相等，并用顺序查找确定所在的块，若要使分块查找的平均查找长度ASL最小，则分块数b的值应为（B）。(A)n(B)n+1(C)「log2n」(D)「log2n」+138．对n个记录进行直接插入排序，所需的关键字比较次数的最大值和最小值分别是（C）。(A)n(n+1)/2和n(B)n(n-1)/2和n-1(C)n(n+1)/2-1和n-1(D)n2和n39．若在一个具有n个结点的有序单链表中插入一个新结点并仍然有序，则该操作的时间复杂度是（）。(A)O(1)(B)O(n2)(C)O(nlog2n)(D)O(n)40．在一个头结点为head的空循环链表中插入一个结点s，则指针s应执行操作第7页共100页（）。(A)head-next=s;s-next=NULL;(B)s-next=head;head-next=NULL;(C)head-next=s;s-next=head-next;(D)s-next=head;head-next=s;41．设链队列Q的头指针和尾指针分别为front和rear，队