数据结构试题库(共99页).doc

《数据结构试题库(共99页).doc》由会员分享，可在线阅读，更多相关《数据结构试题库(共99页).doc（99页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。

1、精选优质文档-倾情为你奉上数据结构试题库一、 单项选择题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-ne

2、xt;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;(

3、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 有一组

4、数值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个关键字，假设对每个关键字查找的概率相等，查

5、找失败的概率为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中只有

6、一个结点，则队列的头指针和尾指针满足下列条件 （ 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个叶子结点，

7、深度为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

8、,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。若采用线性探查法解决冲突，则平均查找长度为

9、（ C ）。(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的头指针和尾

10、指针分别为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

11、,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 ）遍历，可以得到该二叉树所有结点构成的排序序列。(A)层次 (B)前序 (C)中序 (D)后序34 已知一个长度为12的线性表（8，2，5，7，12，3，10，4，1，6，9，11），并将线性表

12、中的元素依次插入到一个原先为空的二叉排序树中去。假设查找每一个元素的概率相同，则查找该二叉树中任一结点的平均查找长度为（ 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)=key MOD 11 按顺序散列到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

13、为结点权值所构造的哈夫曼树，则其带权路径长度WPL为（ A ）。 (A)165 (B)203 (C)124 (D)18737 假定对线性表R0n-1进行分块查找，若将表均匀地分为b块，每块含有n/b个记录；又假定表中每个记录的查找概率相等，并用顺序查找确定所在的块，若要使分块查找的平均查找长度ASL最小，则分块数b的值应为（ B ）。(A) (B)+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 若

14、在一个具有n个结点的有序单链表中插入一个新结点并仍然有序，则该操作的时间复杂度是（ ）。(A)O(1) (B)O(n2) (C)O(nlog2n) (D)O(n)40 在一个头结点为head的空循环链表中插入一个结点s，则指针s应执行操作（ ）。(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，队中元素个数为n(n1)，指针*p指向队首元素m。若删除元素m

15、，则应进行的指针操作为（ ）。(A)Q-front-next=p-next (B)Q-rear=Q-front(C)Q-front=p-rear (D)Q-rear=p-next42 假设二叉树T中有n个叶子结点，且所有非叶子结点都有左、右子树，那么二叉树T共有（ ）个结点。(A)2n (B)2n-1 (C)2n+1 (D)2n+243 已知有向图G的邻接矩阵如下所示，则下列序列中（ ）不可能是图G的拓扑序列。(A)v1,v6,v3,v4,v2,v5 (B)v1,v6,v4,v3,v2,v5(C)v1,v3,v2,v4,v6,v5 (D)v1,v3,v6,v4,v5,v244 已知一棵二叉树的

16、结点数据采用顺序存储结构，数组内容如下表所示，则该二叉树的后序遍历序列为（ ）。1 123456789101112131415161718192021EAFDGCJIHB(A)ACBDJEFIGH (B)ABCDJEFHGI(C)BCJDAHIGFE (D)EADCBJFGIH45 若T为n个结点的完全二叉树，则T的叶子结点数为（ ）。 (A)n/2 (B)(n-2)/2 (C)(n-1)/2 (D)(n+1)/246 有一组数值14,21,32,15,28，用以构造huffman树，则其WPL值为（ ）。 (A)267 (B)189 (C)110 (D)29447 采用折半插入排序，关键字的

17、比较次数与移动次数分别为（ ）。 (A)O(n),O(log2n) (B)O(n2),O(log2n) (C)O(log2n),O(n2) (D)O(nlog2n),O(n2)48 假设结点序列为60,30,90,50,95,70,40,80，以此构成一棵二叉排序树，则在该二叉排序树上查找一个结点的平均查找长度为（ ）。(A)23/8 (B)11/4 (C)9/2 (D)449 下面程序段的时间复杂性的量级为（ D ）。for(i=1;in; i+) for(j=1;jm; j+) cij=0; for(k=1;kw;k+) cij+=aik*bkj (A)O(i*j*k) (B)O(n*m*

18、k) (C)O(n*j*k) (D)O(n*m*w)50 在一个长度为n的线性表中，删除值为x的元素时需要比较元素和移动元素的总次数为（ C ）。 (A)（n+1）/2 (B)n/2 (C)n (D)n+151 利用3，6，8，12，5，7这六个值作为叶子结点的权，生成一棵哈夫曼树，该树的深度为（ B ）。 (A)3 (B)4 (C)5 (D)652 一棵二叉树的广义表表示为a(b(c,d),e(,f(g),则得到的层次遍历序列为 （ D ）。 (A)a,b,c,d,e,f,g (B)c,b,d,a,e,g,f (C)c,d,b,g,f,e,a (D)a,b,e,c,d,f,g53 若长度为n

19、的线性表采用顺序存储结构，在其第i个位置插入一个新元素的算法的时间复杂度为（ ）。(1in+1) (A)O(0) (B)O(1) (C)O(n) (D)O(n2)54 若在线性表中采用折半查找法查找元素，该线性表应该（ ）。 (A)元素按值有序 (B)采用顺序存储结构 (C)元素按值有序，且采用顺序存储结构 (D)元素按值有序，且采用链式存储结构55 已知一算术表达式的中缀形式为AB *C-D/E，后缀形式为ABC *+DE/-，其前缀形式为（ ）。 (A)A+B*C/DE(B)A+B*CD/E (C)-+*ABC/DE (D)-+A*BC/DE56 若二叉树采用二叉链表存储结构，要交换其所有

20、分支结点左右子树的位置，利用（ ）遍历方法最合适。 (A)前序 (B)中序 (C)后序 (D)按层次57 对二叉排序树进行（ ）遍历，可以得到该二叉树所有结点构成的排序序列。 (A) 前序 (B)中序 (C)后序 (D)按层次58 具有n个顶点的有向图最多有（ ）条边。(A)n (B)n(n1) C n(n+1) (D)n259 从未排序序列中依次取出一个元素与已排序序列中的元素依次进行比较，然后将其放在已排序序列的合适位置，该排序方法称为（ ）排序法。(A)插入 (B)选择 (C)shell (D)二路归并60 排序趟数与序列的原始状态有关的排序方法是（ ）排序法。(A)插入 (B)选择 (

21、C)冒泡 (D)快速61 下面给出的四种排序法中（ ）排序法是不稳定性排序法。 (A)插入 (B)冒泡 (C)二路归并 (D)堆62 一个对象序列的排序码为46，79，56，38，40，84，采用快速排序以位于最左位置的对象为基准而得到的第一次划分结果为（ ）。(A)38，46，79，56，40，84 (B)38，79，56，46，40，84(C)40，38，46，56，79，84 (D)38，46，56，79，40，8463 线性链表不具有的特点是（ ）。(A)随机访问 (B)不必事先估计所需存储空间大小(C)插入与删除时不必移动元素 (D)所需空间与线性表长度成正比64 设F是一个森林，B

22、是由F转换得到的二叉树，F中有n个非叶结点，则B中右指针域为空的结点有（ ）个。(A)n-1 (B)n (C)n+1 (D)n+265 具有65个结点的完全二叉树的高度为（）。（根的层次号为0） (A)8 (B)7 (C)6 (D)566 若待排序对象序列在排序前已按其排序码递增顺序排序，则采用（ ）方法比较次数最少。(A)直接插入排序 (B)快速排序(C)归并排序 (D)直接选择排序67 在一个无向图中，所有顶点的度数之和等于所有边数的（ ）倍。(A)3 (B)2 (C)1 (D)1/268 对有14个数据元素的有序表R14进行折半搜索，搜索到R3的关键码等于给定值，此时元素比较顺序依次为（

23、 ）。 (A)R0，R1，R2，R3 (B)R0，R13，R2，R3 (C)R6，R2，R4，R3 (D)R6，R4，R2，R369 若度为m的哈夫曼树中,其叶结点个数为n,则非叶结点的个数为（ ）。 (A)(n+1)/(m+1)-1 (B)n/m-1 (C)(n-1)/(m-1) (D)n/(m-1)-1 70 下面关于算法说法错误的是（ ）。 (A)算法最终必须由计算机程序实现(B)为解决某问题的算法同为该问题编写的程序含义是相同的(C)算法的可行性是指指令不能有二义性 (D)以上几个都是错误的71 以下与数据的存储结构无关的术语是（ ）。(A)循环队列 (B)链表 (C)哈希表 (D)栈

24、72 以下数据结构中，哪一个是线性结构（ ）。(A)广义表 (B)二叉树 (C)稀疏矩阵 (D) 串73 以下那一个术语与数据的存储结构无关？（ ）(A)栈 (B)哈希表 (C)线索树 (D) 双向链表74 在下面的程序段中，对x的赋值语句的频度为（ ）。FOR i:=1 TO n DO FOR j:=1 TO n DO x:=x+1;(A) O(2n) (B)O(n) (C)O(n2) (D)O(log2n) 75 以下哪个数据结构不是多型数据类型（ ）。 (A)栈 (B)广义表 (C)有向图 (D)字符串76 连续存储设计时，存储单元的地址（ ）。 (A)一定连续 (B)一定不连续 (C)

25、不一定连续 (D)部分连续，部分不连续77 一棵左右子树均不空的二叉树在先序前驱和后序后继线索化后，其空链域数为（ A ）。(A)0 (B)1 (C)2 (D)不确定78 设图G采用邻接表存储，则拓扑排序算法的时间复杂度是（ B ）。(A)O(n) (B)O(n+e) (C)O(n2) (D)O(n*e)79 下列排序算法中，时间复杂度为O(nlog2n)且占用额外空间最少的是（ A ）。(A)堆排序 (B)冒泡排序 (C)快速排序 (D)SHELL排序80 已知数据表A中每个元素距其最终位置不远，则采用（ B ）排序算法最节省时间。(A)堆排序 (B)插入排序 (C)快速排序 (D)直接选择

26、排序81 串是（ D ）。(A)不少于一个字母的序列 (B)任意个字母的序列(C)不少于一个字符的序列 (D)有限个字符的序列82 一个栈的输入序列为12345，则下列序列中是栈的输出序列的是（ A ）。(A)23415 (B)54132 (C)31245 (D)1425383 设循环队列中数组的下标范围是1n，其头尾指针分别为f和r，则其元素个数为（ D ）。(A)r-f (B)r-f+1 (C)(r-f) mod n +1 (D)(r-f+n) mod n84 二叉树在线索化后，仍不能有效求解的问题是（ D ）。(A)先序线索二叉树中求先序后继 (B)中序线索二叉树中求中序后继 (C)中序

27、线索二叉树中求中序前驱 (D)后序线索二叉树中求后序后继85 求最短路径的FLOYD算法的时间复杂度为（ D ）。(A)O(n) (B)O(n+e) (C)O(n2) (D)O(n3)86 一棵左右子树不空的二叉树在先序线索化后，其空指针域数为（ B ）。(A)0 (B)1 (C)2 (D)不确定87 数组A1.5,1.6的每个元素占5个单元，将其按行优先顺序存储在起始地址为1000的连续的内存单元中，则元素A5,5的地址为（ A ）。(A)1140 (B)1145 (C)1120 (D)112588 在下列排序算法中，在待排序的数据表已经为有序时，花费时间反而最多的是（ A ）。(A)快速排

28、序 (B)希尔排序 (C)冒泡排序 (D)堆排序89 对有18个元素的有序表做折半查找，则查找A3的比较序列的下标依次为（ D ）。(A)1-2-3 (B)9-5-2-3 (C)9-5-3 (D)9-4-2-390 下列排序算法中，某一趟结束后未必能选出一个元素放在其最终位置上的是（ D ）。(A)堆排序 (B)冒泡排序 (C)快速排序 (D)直接插入排序91 在平衡二叉树中插入一个结点后造成了不平衡，设最低的不平衡点为A，并已知A的左孩子的平衡因子为-1，右孩子的平衡因子为0，则做（ B ）型调整以使其平衡。(A)LL (B)LR (C)RL (D)RR92 下列各式中，按增长率由小至大的顺

29、序正确排列的是（ ）。(A),n!,2n,n3/2 (B)n3/2,2n,nlogn,2100(C)2n, logn, nlogn, n3/2 (D)2100, logn, 2n, nn93 若要在单链表中的结点*p之后插入一个结点*s，则应执行的语句是（ ）。(A)s-next=p-next; p-next=s;(B)p-next=s; s-next=p-next(C)p-next=s-next; s-next=p; (D)s-next=p;p-next=s-next;94 若要在O（1）的时间复杂度上实现两个循环链表头尾相接，则应对两个循环链表各设置一个指针，分别指向（ ）。(A)各自的头

30、结点 (B)各自的尾结点(C)各自的第一个元素结点 (D)一个表的头结点，另一个表的尾结点95 栈的两种常用存储结构分别为（ ）。(A)顺序存储结构和链式存储结构 (B)顺序存储结构和散列存储结构 (C)链式存储结构和索引存储结构 (D)链式存储结构和散列存储结构96 已知循环队列的存储空间为数组data21，且当前队列的头指针和尾指针的值分别为8和3，则该队的当前长度为（ ）。(A)5 (B)6 (C)16 (D)1797 已知在如下定义的链串结点中，每个字符占1个字节，指针占4个字节，则该链串的存储密度为（ ）。typedef struct nodechar date8;struct no

31、de * next; LinkStrNode;(A)1/4 (B)1/2 (C)2/3 (D)3/498 应用简单的匹配算法对主串s=“BDBABDABDAB”与子串t=“BDA”进行模式匹配，在匹配成功时，进行的字符比较总次数为（ ）。(A)7 (B)9 (C)10 (D)1299 二维数组A2010采用列优先的存储方法，若每个元素占2个存储单元，且第1个元素的首地址为200，则元素A89的存储地址为（ ）。(A)574 (B)576 (C)578 (D)580100 对广义表L=(a,b),c,d)进行操作tail (head (L)的结果是（ ）。(A)(c,d ) (B)(d ) (C

32、)b (D)(b)101 已知一棵树的前序序列为ABCDEF，后序序列为CEDFBA，则对该树进行层次遍历得到的序列为（ ）。(A)ABCDEF (B)ABCEFD (C)ABFCDE (D)ABCDFE102 一个含n个顶点和e条弧的有向图以邻接矩阵表示法为存储结构，则计算该有向图中某个顶点出度的时间复杂度为（ ）。(A)O(n) (B)O(e) (C)O(n+e) (D)O(n2)103 在关键字序列（12，23，34，45，56，67，78，89，91）中二分查找关键字为45，89和12的结点时，所需进行的比较次数分别为（ ）。(A)4，4，3 (B)4， 3， 3 (C)3，4，4 (

33、D)3，3，4104 下列排序方法中，最好与最坏时间复杂度不相同的排序方法是（ ）。(A)冒泡排序 (B)直接选择排序 (C)堆排序 (D)归并排序105 已知含10个结点的二叉排序树是一棵完全二叉树，则该二叉排序树在等概率情况下查找成功的平均查找长度等于（ ）。(A)1.0 (B)2.9 (C)3.4 (D)5.5106 在下列各种文件中，不能进行顺序查找的文件是（ ）。(A)顺序文件 (B)索引文件 (C)散列文件 (D)多重表文件107 下面带有标记的语句的频度(n10)是（ ）。 for(int i=0;in-1;i+) for(int j=i+1;jn;j+) coutijendl;

34、(A)n*(n-1)/2 (B)n*n/2 (C) n*(n+1)/2 (D)不确定108 已知使用顺序表存储数据，表长为n，假设在表中的任意位置插入元素的概率相等，则插入一个元素，平均需要移动的元素个数（ ）。(A)(n-1)/2 (B)n/2 (C)(n+1)/2 (D)不确定109 在双向链表p所指结点之后插入s所指结点的操作是（ ）。(A)pright=s;sleft=p;prightleft=s;sright=pright;(B)pright=s;prightleft=s;sleft=p;sright=pright;(C)sleft=p;sright=pright;pright=s;

35、prightleft=s;(D)sleft=p;sright=pright;prightleft=s;pright=s;110 字符串相等的充分必要条件是（ ）。 (A)串长度相等 (B)串使用相同的存储结构 (C)串相同位置对应的字符相等 (D)A和C111 将一个递归算法改为对应的非递归算法时，通常需要使用（ ）。 (A) 数组(B) 栈 (C) 队列(D)二叉树112 一个栈的入栈序列1, 2, 3, 4, 5, 则栈的不可能的输出序列是（ ）。(A) 12345 (B)54321 (C)32514 (D)12354 113 设循环队列中数组的下标范围是1n，其头尾指针分别为f和r，则其元素个数为（ ）。(A)r-f (B)r-f+1 (C)(r-f) mod n +1 (D)(r-f+n) mod n114 某二叉树的前序遍历结点访问顺序是ABDEFCGH, 中序遍历的结点访问顺序是DBFEAGHC, 则其后序遍历的结点访问顺序是（ ）。(A) DFEBHCGA (B)DFEBHGCA (C)DEFBHGCA (D)DFEHBGCA 115 正则二叉树是只有度为0和2的结点的二叉树，已知正则二叉树的叶子结点个数为n，则该二叉树总得结点数为（ ）。(A) n+1 (B)2*n (C) 2*n+1 (D)2*n-1116 下面关于排序的说法错误的是（