数据结构试题库

1、精选优质文档-倾情为你奉上精选优质文档-倾情为你奉上专心-专注-专业专心-专注-专业精选优质文档-倾情为你奉上专心-专注-专业数据结构试题库一、单项选择题下列程序段所代表的算法的时间复杂度为（D）。x=n;y=0;while (x=(y+1)*(y+1) y+;O(n)(B)O(n 2)(C)O(log 2n)(D)O(n )在一个长度为n 的以顺序结构存储的线性表中，假设在线性表的任何位置删除元素的概率相等，则删除一个元素时线性表所需移动元素的平均次数为（B ） 。(A) n2(B)(n-1)/2(C)(n+1)/2(D)n/2在一个栈顶指针为HS的链栈中插入一个*s结点时，应执行执行操作为

2、（ C）。HS-next=s;(B)s-next=HS-next;HS-next=s;(C)s-next=HS;HS=s;(D)s-next=HS;HS=HSnext;假设以带头结点的循环链表表示队列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;

3、(C)s-next=p;p-next=Q-front;(D)Q-front-next=s;s-next=p;设高度为h 的二叉树上只有度为0 和度为 2 的结点，则此类二叉树中所包含的结点数至少为（B ） 。(A)2 h-1(B)2 h-1 +1(C)2 h-1(D)2 h-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

4、(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,v6v5v4v1v2v5v2v3v3v6v6v3v4v5v4v6设有 m=2 n-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/2下列程序段所代表的算法的时间复杂度为（C ） 。y=n;x=1;nwhile(xnext=NULL(C)head-next=head(D)head!=NUL

6、L若链队列HQ中只有一个结点，则队列的头指针和尾指针满足下列条件（ D）。HQ-rear-next=HQ-front(B)HQ-front-next=HQ-rear-next (C)HQ-front=HQ-rear(D)HQ-front-next=HQ-rear从一个栈顶指针为HS 的链栈中删除一个结点时，用x 保存被删除结点的值， 则应执行操作为（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;一棵有n 个结点的满二叉树，有m 个叶子结点，深

7、度为h，那么 n、m 和 h满足条件（D）。(A)n=m+h(B)h+m=2n(C)m=h-1(D)n=2h-1一 棵左 、右子树均不为空 的二 叉树在先序线索化 后， 其空指针域数为（ B ） 。(A)0(B)1(C)2(D) 不确定 有一组数值 5,12,9,20,3，用以构造哈夫曼树，则其带权路径长度WPL值为（ C）。(A)49(B)96(C)103(D)12519在一个 n 个结点的二叉排序树中查找一个关键字，进行关键字比较次数最大值为（A ） 。n(B)n/2(C)log 2 n(D)n*log 2 n已知有向图G=(V,E) ，其中 V=v1,v2,v3,v4,v5,v6，则下列

8、边集合E 中（ A ）所对应的有向图没有拓扑序列。(A) E=, (B) E=, (C) E=,(D) E=,冒泡排序算法在最好情况下的时间复杂度为（B ） 。(A)O(log 2n)(B)O(n)(C)O(1)(D)O(n 2)在下列内部排序方法中，排序时不稳定的， 而且关键字的比较次数与记录的初始排列次序无关的是（D）。快速排序(B) 冒泡排序(C) 归并排序(D) 堆排序24 已知一个待散列存储的线性表18,81,58,34,26,75,67,49,93，散列函数为(A)5/3(B)13/9(C)16/9(D)3/2 下列程序段所代表的算法的时间复杂度为（D ） 。i=1;j=0;whi

9、le(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;已知用循环链表表示的队列长度为n，若只设头指针，则出队和入队一个元素的时间复杂度分别是（B）。(A)O(1) 和 O(1)(B)O(1) 和 O(n)(C)O(n) 和 O(1)(D)O(n)和 O(n)设链队列Q 的头指针和尾指针分别为front 和 rear ，初始时队列为空，若向队列插入一个元素*s ，则应执行的指针操作为（C ） 。(A)Q-front-next=s;s-nex

10、t=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;已知一个带权图的顶点集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,则该

11、图的最小生成树的权值为（C） 。 (A)24(B)29(C)30(D)31当待排序的关键字个数n 很小，且初始排列为逆序时，采用下列排序方法中的（ D），算法的时间复杂度最小。直接插入排序(B) 简单选择排序(C) 冒泡排序(D) 快速排序对二叉排序树进行（ C ）遍历， 可以得到该二叉树所有结点构成的排序序列。层次(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)=keyMOD11按顺序散列到HASH表 HT（ 0:10 ）中，用链地址解决冲突。假设查找每一个元素的概率相同，则查找该HASH表中任一元素的平均查找长度为（C）。(A)3/2(B)10/7(C)11/7(D)9/7以数据集 4 ， 5 ， 6， 7， 12 ， 18， 10 为结点权值所构造的哈夫曼树，则其带权路径长度WPL 为（A ） 。(A)165(B)203

13、(C)124(D)187假定对线性表R0n-1 进行分块查找， 若将表均匀地分为b 块，每块含有n/b个记录；又假定表中每个记录的查找概率相等，并用顺序查找确定所在的块，若要使分块查找的平均查找长度ASL 最小，则分块数b 的值应为（B ） 。n(B)n(A)+1(C) log 2n(D) log 2 n+1对 n 个记录进行直接插入排序，所需的关键字比较次数的最大值和最小值分别是（C ） 。(A)n(n+1)/2和 n(B)n(n-1)/2和 n-1(C) n(n+1)/2-1和 n-1(D)n 2 和 n若在一个具有n 个结点的有序单链表中插入一个新结点并仍然有序，则该操作的时间复杂度是（

14、）。2O(1)(B)O(n 2 )(C)O(nlog n)(D)O(n)在一个头结点为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;设链队列Q 的头指针和尾指针分别为front 和 rear ，队中元素个数为n(n1) ， 指针 *p 指向队首元素m。若删除元素m，则应进行的指针操作为（）。Q-front-next=p-next(B)Q-rea

15、r=Q-front(C)Q-front=p-rear(D)Q-rear=p-next假设二叉树T 中有 n 个叶子结点，且所有非叶子结点都有左、右子树，那么二叉树 T 共有（）个结点。(A)2n(B)2n-1(C)2n+1(D)2n+2已知有向图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,v2011100000000010010000010000000000110已知一棵二叉树的结点数据采用顺序存储结构，数组内容如下表

16、所示，则该二叉树的后序遍历序列为（）。123456789101112131415161718192021EAFDGCJIHB (A)ACBDJEFIGH(B)ABCDJEFHGI(C)BCJDAHIGFE(D)EADCBJFGIH若 T 为 n 个结点的完全二叉树，则T 的叶子结点数为（）。(A)n/2(B)(n-2)/2(C)(n-1)/2(D)(n+1)/2有一组数值14,21,32,15,28，用以构造huffman树，则其WPL 值为（）。(A)267(B)189(C)110(D)294采用折半插入排序，关键字的比较次数与移动次数分别为（）。O(n),O(log2n)(B)O(n 2)

17、,O(log 2n)(C)O(log 2 n),O(n 2)(D)O(nlog 2 n),O(n 2 )48 假设结点序列为60,30,90,50,95,70,40,80，以此构成一棵二叉排序树，则在该二叉排序树上查找一个结点的平均查找长度为（）。(A)23/8(B)11/4(C)9/2(D)4下面程序段的时间复杂性的量级为（D）。for(i=1;i n; i+) for(j=1;j m; j+)cij=0;for(k=1;k w;k+) cij+=aik*bkjO(i*j*k)(B)O(n*m*k)(C)O(n*j*k)(D)O(n*m*w)在一个长度为n 的线性表中， 删除值为 x 的元素

18、时需要比较元素和移动元素的总次数为（C）。(A) （ n+1 ） /2(B)n/2(C)n(D)n+1利用 3， 6， 8， 12 ，5， 7 这六个值作为叶子结点的权，生成一棵哈夫曼树， 该树的深度为（B ） 。(A)3(B)4(C)5(D)6一棵二叉树的广义表表示为a(b(c,d),e(,f(g),则得到的层次遍历序列为（ D）。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,g若长度为n 的线性表采用顺序存储结构，在其第 i 个位置插入一个新元素的算法的时间复杂度为（）。(1 in+1)(A)O(0)(B)O(1)(

19、C)O(n)(D)O(n2)若在线性表中采用折半查找法查找元素，该线性表应该（）。元素按值有序(B) 采用顺序存储结构元素按值有序，且采用顺序存储结构元素按值有序，且采用链式存储结构已知一算术表达式的中缀形式为AB *C-D/E ，后缀形式为ABC *+DE/-，其前缀形式为（）。A+B*C/DE(B) A+B*CD/E (C)-+*ABC/DE(D)-+A*BC/DE若二叉树采用二叉链表存储结构，要交换其所有分支结点左右子树的位置，利用（）遍历方法最合适。前序(B) 中序(C) 后序(D) 按层次对二叉排序树进行（）遍历，可以得到该二叉树所有结点构成的排序序列。前序(B) 中序(C) 后序(

20、D) 按层次具有 n 个顶点的有向图最多有（）条边。(A)n(B)n(n 1)C n(n+1)(D)n2从未排序序列中依次取出一个元素与已排序序列中的元素依次进行比较，然后将其放在已排序序列的合适位置，该排序方法称为（）排序法。插入(B) 选择(C)shell(D) 二路归并排序趟数与序列的原始状态有关的排序方法是（）排序法。(A) 插入(B) 选择(C) 冒泡(D) 快速下面给出的四种排序法中（）排序法是不稳定性排序法。插入(B) 冒泡(C) 二路归并(D) 堆一个对象序列的排序码为46 ， 79 ， 56， 38 ， 40， 84 ，采用快速排序以位于(A)38 ， 46 ，79 ， 56

21、， 40， 84(B)38 ， 79， 56， 46 ，40 ， 84(C)40 ， 38， 46 ， 56， 79， 84(D)38 ， 46 ，56 ， 79， 40 ，84 线性链表不具有的特点是（）。(A) 随机访问(B) 不必事先估计所需存储空间大小(C) 插入与删除时不必移动元素(D) 所需空间与线性表长度成正比最左位置的对象为基准而得到的第一次划分结果为（）。63设 F 是一个森林， B 是由 F 转换得到的二叉树，F 中有 n 个非叶结点，则B中右指针域为空的结点有（）个。(A)n-1(B)n(C)n+1(D)n+2具有 65 个结点的完全二叉树的高度为（）。（根的层次号为0

22、） (A)8(B)7(C)6(D)5若待排序对象序列在排序前已按其排序码递增顺序排序，则采用 （）方法比较次数最少。直接插入排序(B) 快速排序(C) 归并排序(D) 直接选择排序在一个无向图中，所有顶点的度数之和等于所有边数的（）倍。(A)3(B)2(C)1(D)1/2对有 14 个数据元素的有序表R14 进行折半搜索，搜索到R3 的关键码等于给定值，此时元素比较顺序依次为（）。(A)R0 ，R1 ， R2 ， R3(B)R0 ， R13 ， R2 ，R3(C)R6 ， R2 ， R4 ，R3(D)R6 ， R4 ， R2 ，R3若度为 m 的哈夫曼树中 ,其叶结点个数为n, 则非叶结点的个

23、数为（）。(A)(n+1)/(m+1)-1(B)n/m-1(C)(n-1)/(m-1)(D)n/(m-1)-1下面关于算法说法错误的是（）。算法最终必须由计算机程序实现为解决某问题的算法同为该问题编写的程序含义是相同的算法的可行性是指指令不能有二义性以上几个都是错误的以下与数据的存储结构无关的术语是（）。循环队列(B) 链表(C) 哈希表(D) 栈以下数据结构中，哪一个是线性结构（）。广义表(B) 二叉树(C) 稀疏矩阵(D)串以下那一个术语与数据的存储结构无关？（）栈(B) 哈希表(C) 线索树(D)双向链表在下面的程序段中，对x 的赋值语句的频度为（）。FOR i:=1TOnDO FOR

24、j:=1TOnDOx:=x+1;(A) O(2n)(B)O(n)(C)O(n2)(D)O(log 2 n)以下哪个数据结构不是多型数据类型（）。栈(B) 广义表(C) 有向图(D) 字符串连续存储设计时，存储单元的地址（）。一定连续(B) 一定不连续(C) 不一定连续(D) 部分连续，部分不连续一棵左右子树均不空的二叉树在先序前驱和后序后继线索化后，其空链域数为（A ） 。(A)0(B)1(C)2(D) 不确定设图 G 采用邻接表存储，则拓扑排序算法的时间复杂度是（B ） 。(A)O(n)(B)O(n+e)(C)O(n2)(D)O(n*e)下列排序算法中，时间复杂度为O(nlog2n) 且占用

25、额外空间最少的是（A ） 。堆排序(B) 冒泡排序(C) 快速排序(D)SHELL排序已知数据表A 中每个元素距其最终位置不远，则采用（B ）排序算法最节省时间。堆排序(B) 插入排序(C) 快速排序(D) 直接选择排序串是（D）。不少于一个字母的序列(B) 任意个字母的序列(C) 不少于一个字符的序列(D) 有限个字符的序列一个栈的输入序列为12345 ，则下列序列中是栈的输出序列的是（A ） 。(A)23415(B)54132(C)31245(D)14253设循环队列中数组的下标范围是1n ，其头尾指针分别为f 和 r，则其元素个数为（D）。r-f(B)r-f+1(C)(r-f) mod

26、n +1(D)(r-f+n) mod n二叉树在线索化后，仍不能有效求解的问题是（D ） 。先序 线 索 二 叉 树中 求 先 序 后 继(B) 中 序 线 索 二 叉 树 中求 中 序 后 继(C) 中序线索二叉树中求中序前驱(D) 后序线索二叉树中求后序后继求最短路径的FLOYD 算法的时间复杂度为（D）。(A)O(n)(B)O(n+e)(C)O(n2)(D)O(n3)一棵左右子树不空的二叉树在先序线索化后，其空指针域数为（B ） 。(A)0(B)1(C)2(D) 不确定数组 A1.5,1.6的每个元素占5 个单元，将其按行优先顺序存储在起始地址为 1000 的连续的内存单元中，则元素A5

27、,5 的地址为（A ） 。(A)1140(B)1145(C)1120(D)1125在下列排序算法中，在待排序的数据表已经为有序时，花费时间反而最多的是（ A ） 。快速排序(B) 希尔排序(C) 冒泡排序(D) 堆排序89 对有18个元素的有序表做折半查找，则查找A3 的比较序列的下标依次为（ D）。(A)1-2-3(B)9-5-2-3(C)9-5-3(D)9-4-2-3下列排序算法中，某一趟结束后未必能选出一个元素放在其最终位置上的是（ D）。堆排序(B) 冒泡排序(C) 快速排序(D) 直接插入排序在平衡二叉树中插入一个结点后造成了不平衡，设最低的不平衡点为A，并已知 A 的左孩子的平衡因

28、子为-1 ，右孩子的平衡因子为0，则做（B ）型调整以使其平衡。LL(B)LR(C)RL(D)RR下列各式中，按增长率由小至大的顺序正确排列的是（）。n(A),n!,2n,n3/2(B)n3/2,2n,nlogn,2100(C)2n, logn, nlogn, n3/2(D)2100, logn, 2n, nn若要在单链表中的结点*p 之后插入一个结点*s ，则应执行的语句是（）。s- next=p- next; p- next=s;p- next=s; s- next=p- nextp- next=s- next; s- next=p; (D)s- next=p;p- next=s- nex

29、t;若要在 O（ 1 ）的时间复杂度上实现两个循环链表头尾相接，则应对两个循环链表各设置一个指针，分别指向（）。各自的头结点(B) 各自的尾结点(C) 各自的第一个元素结点(D) 一个表的头结点，另一个表的尾结点栈的两种常用存储结构分别为（）。顺序存储结构和链式存储结构(B) 顺序存储结构和散列存储结构(C) 链式存储结构和索引存储结构(D) 链式存储结构和散列存储结构已知循环队列的存储空间为数组data21 ，且当前队列的头指针和尾指针的值分别为 8 和 3 ，则该队的当前长度为（）。(A)5(B)6(C)16(D)17已知在如下定义的链串结点中，每个字符占1 个字节，指针占4 个字节，则该

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

31、l (head (L)的结果是（）。(A)(c,d )(B)(d )(C)b(D)(b)已知一棵树的前序序列为ABCDEF ，后序序列为CEDFBA ，则对该树进行层次遍历得到的序列为（）。ABCDEF(B)ABCEFD(C)ABFCDE(D)ABCDFE一个含 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 的结点时，所需进行的比较次

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

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

34、t=p right;p right=s;p right left=s; (D)s left=p;s right=p right;p right left=s;p right=s;110字符串相等的充分必要条件是（）。(A) 串长度相等(C) 串相同位置对应的字符相等(B) 串使用相同的存储结构(D)A 和 C将一个递归算法改为对应的非递归算法时，通常需要使用（）。数组 (B)栈(C)队列 (D) 二叉树一个栈的入栈序列1, 2, 3, 4, 5,则栈的不可能的输出序列是（）。(A) 12345(B)54321(C)32514(D)12354设循环队列中数组的下标范围是1n ，其头尾指针分别为f

35、 和 r，则其元素个数为（）。r-f(B)r-f+1(C)(r-f) mod n +1(D)(r-f+n) mod n某二叉树的前序遍历结点访问顺序是ABDEFCGH,中序遍历的结点访问顺序是 DBFEAGHC,则其后序遍历的结点访问顺序是（）。DFEBHCGA(B)DFEBHGCA(C)DEFBHGCA(D)DFEHBGCA正则二叉树是只有度为0 和 2 的结点的二叉树，已知正则二叉树的叶子结点个数为n，则该二叉树总得结点数为（）。(A)n+1(B)2*n(C) 2*n+1(D)2*n-1下面关于排序的说法错误的是（）。快速排序、归并排序都是一种不稳定的排序方法直接插入排序和折半插入排序移动

36、元素的次数相同简单选择排序移动元素的次数最少根据排序需要的平均时间，快速排序是目前最好的一种内部排序方法117折半查找有序表（3 ，4，5 ，10 ，13 ，14 ，20，30），若查找元素3 ，则被比较的元素依次为（）。(A)10,20,30(B)10,14,30(C)13,3(D)10, 4, 3118下面关于栈和队列的说法正确的是（）。栈是先进先出的线性表，队列是后进先出的线性表栈是先进先出的线性表，队列也是先进先出的线性表栈是后进先出的线性表，队列是先进先出的线性表栈是后进先出的线性表，队列也是后进先出的线性表119两个各有n个元素的有序列表并成一个有序表，其最少的比较次数是（）。(A

37、)n(B)2n-1(C)2n(D)n-1设循环队列中数组的下标范围是0 n-1 ， f 表示队首元素的前驱位置，r 表示队尾元素的位置，则队列中元素个数为（）。r-f(B)r-f 1(C)(r-f 1)mod n(D)(r-f n)mod n一个 5 行 6 列的二维数组s 采用从最后一行开始，每一行的元素从右至左的方式映射到一维数组a 中，s 和 a 的下标均从0 开始， 则 s33 在 a 中的下标是（）。(A)7(B)8(C)9(D)10设只含根结点的二叉树的高度为1 ，则高度为n 的二叉树中所含叶子结点的个数最多为（）个。(A)2n(B)n(C)2n -1(D)2n-1设高度为h 的二

38、叉树上只有度为0 和度为 2 的结点，则此二叉树中所包含的结点数至少为（）个（设只含根结点的二叉树的高度为1）。(A)2h(B)2h-1(C)2h+1(D)h+1对一棵二叉检索树进行（） 得到的结点序列是一个有序序列。前序周游(B) 中序周游(C) 后序周游(D) 层次周游一棵前序序列为1 ， 2 ，3， 4 的二叉树，其中序序列不可能是（） 。(A)4,1,2,3(B)4,3,2,1(C)2,4,3,1(D)3,4,2,1在含 n 个顶点和e 条边的有向图的邻接矩阵中，零元素的个数为（）。(A)e(B)2e(C)n2-e(D)n2-2e具有 n 个顶点和e 条边的图的深度优先搜索算法的时间复

39、杂度为（）。(A)O(n)(B)O(n3)(C)O(n2)(D)O(n e)如果具有n 个顶点的图是一个环，则它有（）棵生成树。n(B)n l(C)n-l(D)2n堆排序算法在平均情况下的时间复杂度为（）。O(n)(B)O(nlogn)(C)O(n2)(D)O(logn)在待排序数据已基本有序的前提下，下述排序方法中效率最高的是（）。直接插入排序(B) 直接选择排序(C) 快速排序(D) 归并排序在理想情况下，散列表中查找元素所需的比较次数为（）。(A)n(B)O(C)n 2(D)1在一棵 m 阶 B 树中，若在某结点中插入一个新关键字而引起该结点分裂， 则此结点中原有的关键字的个数是（）。(

40、A)m(B)m +1(C)m-l(D)m 2设顺序循环队列Q0 ： M-1 的头指针和尾指针分别为F 和 R，头指针F 总是指向队头元素的前一位置，尾指针R 总是指向队尾元素的当前位置，则该循环队列中的元素个数为（C）。(A) R-F(B) F-R(C) (R-F+M) M(D) (F-R+M) M设某棵二叉树的中序遍历序列为ABCD ，前序遍历序列为CABD ，则后序遍历该二叉树得到序列为（A ） 。BADC(B) BCDA(C) CDAB(D) CBDA设某完全无向图中有n 个顶点，则该完全无向图中有（A ）条边。(A) n(n-1)/2(B) n(n-1)(C) n2(D) n2-1设某

41、棵二叉树中有2000 个结点，则该二叉树的最小高度为（C）。(A) 9(B) 10(C) 11(D) 12设某有向图中有n 个顶点，则该有向图对应的邻接表中有（B ）个表头结点。(A) n-1(B) n(C) n+1(D) 2n-1设一组初始记录关键字序列(5 ，2，6 ，3 ，8) ，以第一个记录关键字5 为基准进行一趟快速排序的结果为（C ） 。(A) 2 ，3 ， 5 ，8， 6(B) 3 ，2 ， 5，8 ， 6(C) 3 ，2 ， 5， 6， 8(D) 2 ，3 ， 6， 5， 8139设某数据结构的二元组形式表示为A=(D ，R) ，D=01 ，02 ，03， 04 ， 05，06

42、， 07 ，08 ， 09 ，R=r ， r= ， ， ， ， ， ， ， ，则数据结构A 是（B）。线性结构 (B)树型结构 (C) 物理结构 (D)图型结构下面程序的时间复杂为（B ）for （ i=1 ， s=0 ； i=n ； i+） t=1 ；for(j=1 ； jnext； p-data=q-data；p-next=q-next； free(q) ；q=p-next； q-data=p-data； p-next=q-next； free(q) ；q=p-next；p-next=q-next；free(q) ；q=p-next；p-data=q-data； free(q) ；设有n

43、个待排序的记录关键字，则在堆排序中需要（A）个辅助记录单元。1(B) n(C) nlog2n(D) n2143设一组初始关键字记录关键字为(20， 15 ，14，18 ，21，36 ，40 ，10) ，则以 20 为基准记录的一趟快速排序结束后的结果为（A ） 。(A) 10 ， 15 ，14 ， 18， 20 ， 36 ，40 ， 21 (B) 10 ， 15 ，14 ， 18， 20， 40 ， 36， 21(C) 10 ， 15， 14 ， 20， 18， 40 ，36 ， 2l (D) 15 ， 10， 14 ， 18， 20， 36 ，40 ， 21设二叉排序树中有n个结点，则在二叉

44、排序树的平均平均查找长度为（ B ） 。O(1) (B) O(log2n)(C) log2n(D) O(n2)设无向图G 中有 n 个顶点 e 条边， 则其对应的邻接表中的表头结点和表结点的个数分别为（D ） 。n ，e (B) e ，n (C) 2n ， e(D) n ， 2e设某强连通图中有n 个顶点，则该强连通图中至少有（C ）条边。(A) n(n-1)(B) n+1(C) n(D) n(n+1)设有5000个待排序的记录关键字，如果需要用最快的方法选出其中最小的 10 个记录关键字，则用下列（B ）方法可以达到此目的。快速排序 (B)堆排序(C)归并排序 (D)插入排序下列四种排序中（

45、D ）的空间复杂度最大。插入排序 (B)冒泡排序 (C) 堆排序(D)归并排序设一维数组中有n 个数组元素，则读取第i 个数组元素的平均时间复杂度为（C ） 。(A) O(n) (B) O(nlog2n)(C) O(1) (D) O(n2)设一棵二叉树的深度为k，则该二叉树中最多有（D）个结点。(A) 2k-1(B) 2k(C) 2k-1 (D) 2k-1设某无向图中有n个顶点e 条边，则该无向图中所有顶点的入度之和为（ D）。n(B) e(C) 2n(D) 2e在二叉排序树中插入一个结点的时间复杂度为（B ） 。(A) O(1) (B) O(n) (C) O(log2n)(D) O(n2)设

46、某有向图的邻接表中有n 个表头结点和m 个表结点， 则该图中有 （ C ） 条有向边。(A) n(B) n-1(C) m(D) m-1154设一组初始记录关键字序列为(345 ， 253 ， 674 ， 924 ， 627) ，则用基数排序需要进行（A ）趟的分配和回收才能使得初始关键字序列变成有序序列。(A) 3(B) 4(C) 5(D) 8设用链表作为栈的存储结构则退栈操作（B ） 。必须判别栈是否为满(B)必须判别栈是否为空(C)判别栈元素的类型(D)对栈不作任何判别下列四种排序中（A ）的空间复杂度最大。快速排序 (B)冒泡排序 (C) 希尔排序 (D)堆设某二叉树中度数为0 的结点数

47、为N 0，度数为 1 的结点数为N l，度数为 2的结点数为N2，则下列等式成立的是（C ） 。(A) N0=N1+1(B) N0=Nl+N2(C) N0=N2+1( D) N0=2N1+l设有序顺序表中有n 个数据元素，则利用二分查找法查找数据元素X 的最多比较次数不超过（A ） 。log2n+1(B) log2n-1 ( C) log2n(D) log2(n+1)数据的最小单位是（A ） 。数据项(B)数据类型 (C) 数据元素 (D)数据变量160设一组初始记录关键字序列为(50 ，40 ，95 ，20， 15 ，70，60 ，45)，则以增量 d=4 的一趟希尔排序结束后前4 条记录关

48、键字为（B）。(A) 40 ， 50 ，20 ， 95(B) 15 ， 40 ， 60， 20(C) 15 ， 20， 40 ， 45(D) 45 ， 40 ， 15， 20161设一组初始记录关键字序列为(25 ， 50， 15， 35 ，80 ， 85， 20， 40 ，36 ，70) ，其中含有5 个长度为2 的有序子表，则用归并排序的方法对该记录关键字序列进行一趟归并后的结果为（A ） 。(A) 15 ， 25 ， 35， 50 ， 20， 40 ， 80， 85， 36 ，70 (B) 15 ， 25 ， 35， 50 ， 80， 20 ， 85， 40， 70 ，36 (C) 15

49、 ， 25 ，35 ， 50 ， 80， 85 ，20 ， 36， 40 ，70 (D) 15 ， 25 ，35 ， 50 ， 80， 20 ，36 ， 40， 70 ，85设一个有序的单链表中有n 个结点，现要求插入一个新结点后使得单链表仍然保持有序，则该操作的时间复杂度为（D ） 。(A) O(log2n)(B) O(1)(C) O(n2)(D) O(n)设一棵 m 叉树中度数为0 的结点数为N 0，度数为 1 的结点数为Nl， 度数为 m 的结点数为Nm ，则 N0 =（ B ）。Nl+N2+Nm(B) l+N2+2N3+3N4+(m-1)Nm (C) N2+2N3+3N4+(m-1)N

50、m (D) 2Nl+3N2+(m+1)Nm设有序表中有1000 个元素，则用二分查找查找元素X 最多需要比较 （ B ） 次。(A) 25(B) 10(C) 7(D) 1165设连通图G 中的边集E=(a ，b) ，(a，e) ，(a ，c) ，(b ，e) ，(e ，d) ，(d ，f)，(f， c)，则从顶点a 出发可以得到一种深度优先遍历的顶点序列为（B ） 。abedfc(B) acfebd(C) aebdfc(D) aedfcb166设输入序列是1、2、3、n，经过栈的作用后输出序列的第一个元素是 n，则输出序列中第i 个输出元素是（C ） 。n-i(B) n-1-i(C) n+1-

51、i(D)不能确定167设一组初始记录关键字序列为(45 ，80 ， 55， 40 ， 42，85) ，则以第一个记录关键字45 为基准而得到一趟快速排序的结果是（C ） 。(A) 40 ， 42 ，45 ， 55， 80， 83(B) 42 ， 40， 45， 80 ， 85， 88(C) 42 ， 40， 45 ， 55， 80， 85(D) 42 ， 40， 45 ， 85 ，55 ， 80设一组权值集合W=2 ， 3 ，4， 5， 6 ，则由该权值集合构造的哈夫曼树中带权路径长度之和为（D）。(A) 20(B) 30(C) 40(D) 45执行一趟快速排序能够得到的序列是（A ） 。(A

52、) 41 ， 12， 34， 45 ，27 55 72 ， 63(B) 45 ， 34， 12， 41 55 72 ， 63 ，27(C) 63 ，12 ， 34， 45， 27 55 41 ， 72(D) 12 ，27 ， 45， 41 55 34 ， 63 ， 72设一条单链表的头指针变量为head且该链表没有头结点，则其判空条件是（A ） 。head=0(B) head-next=0(C) head-next=head(D) head!=0时间复杂度不受数据初始状态影响而恒为O(nlog 2 n) 的是（A ） 。堆排序(B)冒泡排序 (C) 希尔排序 (D)快速排序设二叉树的先序遍历序

53、列和后序遍历序列正好相反，则该二叉树满足的条件是（D）。空或只有一个结点(B) 高度等于其结点数(C)任一结点无左孩子(D)任一结点无右孩子一趟排序结束后不一定能够选出一个元素放在其最终位置上的是（D ） 。堆排序(B)冒泡排序 (C) 快速排序 (D)希尔排序设某棵三叉树中有40 个结点，则该三叉树的最小高度为（B ） 。(A) 3(B) 4(C) 5(D) 6顺序查找不论在顺序线性表中还是在链式线性表中的时间复杂度为（ A ） 。(A) O(n)(B) O(n2)(C) O(n1/2)(D) O(1og2n)二路归并排序的时间复杂度为（C）。O(n)(B) O(n2)(C) O(nlog

54、2n)(D) O(log 2n)深度为 k 的完全二叉树中最少有（B ）个结点。(A) 2k-1-1(B) 2k-1(C) 2k-1+1(D) 2k-1设指针变量front 表示链式队列的队头指针，指针变量rear 表示链式队列的队尾指针，指针变量s指向将要入队列的结点X ，则入队列的操作序列为（ C）。front-next=s； front=s ；(B) s-next=rear； rear=s ；(C) rear-next=s； rear=s ；(D) s-next=front； front=s ；设某无向图中有n 个顶点e条边，则建立该图邻接表的时间复杂度为（ A ） 。(A) O(n+e

55、)(B) O(n2)(C) O(ne)(D) O(n3)设某哈夫曼树中有199 个结点，则该哈夫曼树中有（B ）个叶子结点。(A) 99(B) 100(C) 101(D) 102设二叉排序树上有n 个结点，则在二叉排序树上查找结点的平均时间复杂度为（D）。O(n)(B) O(n2)(C) O(n log 2n)(D) O(log 2 n)设用邻接矩阵A 表示有向图G 的存储结构， 则有向图G 中顶点 i 的入度为（ B ） 。第 i 行非 0 元素的个数之和(B)第 i 列非 0 元素的个数之和(C)第 i 行 0 元素的个数之和(D)第 i 列 0 元素的个数之和设某无向图有n 个顶点，则该

56、无向图的邻接表中有（B ）个表头结点。(A) 2n(B) n(C) n/2(D) n(n-1)设无向图G 中有 n 个顶点，则该无向图的最小生成树上有（B ）条边。(A) n(B) n-1(C) 2n(D) 2n-1185设一组初始记录关键字序列为(60 ，80 ， 55， 40 ， 42，85) ，则以第一个关键字 45 为基准而得到的一趟快速排序结果是（C）。(A) 40 ， 42 ，60 ， 55， 80， 85(B) 42 ， 45， 55， 60 ， 85， 80 (C) 42 ， 40， 55 ， 60， 80， 85(D) 42 ， 40， 60 ， 85 ，55 ， 80（ B

57、）二叉排序树可以得到一个从小到大的有序序列。先序遍历 (B)中序遍历 (C) 后序遍历 (D)层次遍历设按照从上到下、从左到右的顺序从1 开始对完全二叉树进行顺序编号， 则编号为i 结点的左孩子结点的编号为（B ） 。(A) 2i+1(B) 2i(C) i/2(D) 2i-1程序段 s=i=0 ；do i=i+1 ； s=s+i ；while(inext=0(C) head-next=head(D) head!=0设某棵二叉树的高度为10，则该二叉树上叶子结点最多有（C ） 。(A) 20(B) 256(C) 512(D) 1024191设一组初始记录关键字序列为(13 ， 18， 24， 3

58、5 ，47 ， 50， 62， 83 ，90 ，115 ， 134), 则利用二分法查找关键字90 需要比较的关键字个数为（B ） 。(A) 1(B) 2(C) 3(D) 4设指针变量top指向当前链式栈的栈顶，则删除栈顶元素的操作序列为（ D）。top=top+1;(B) top=top-1;(C) top-next=top;(D) top=top-next;建立一个长度为n 的有序单链表的时间复杂度为（C ）(A) O(n) (B) O(1)(C) O(n2)(D) O(log 2n)设某散列表的长度为100 ，散列函数H(k)=k % P ，则 P 通常情况下最好选择（B ） 。(A)

59、99(B) 97(C) 91(D) 93在二叉排序树中插入一个关键字值的平均时间复杂度为（B ） 。O(n) (B) O(log2n)(C) O(log 2n)(D) O(n2)设一个顺序有序表A1:14 中有 14 个元素，则采用二分法查找元素A4 的过程中比较元素的顺序为( C ) 。(A) A1 ， A2 ，A3 ， A4 (B) A1， A14 ，A7 ， A4(C) A7 ， A3 ，A5 ， A4 (D) A7 ， A5， A3 ， A4设一棵完全二叉树中有65 个结点，则该完全二叉树的深度为（B ） 。(A) 8(B) 7(C) 6(D) 5设一棵三叉树中有2 个度数为1 的结点

60、， 2 个度数为2 的结点， 2 个度数为 3 的结点，则该三叉链权中有（C ）个度数为0 的结点。(A) 5(B) 6(C) 7(D) 8设无向图G 中的边的集合E=(a ， b) ， (a ， e) ，(a ， c)， (b ， e) ， (e ， d) ， (d ， f)， (f ，c) ，则从顶点a 出发进行深度优先遍历可以得到的一种顶点序列为（ A ） 。aedfcb(B) acfebd(C) aebcfd(D) aedfbc下列程序段的时间复杂度为（A ） 。for(i=0 ； im ； i+) for(j=0 ； jt ； j+) cij=0；for(i=0；im ；i+)for