数据结构试题库.pdf

数据结构试题库 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/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=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-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 v3 v4 v5 v5 v6 v1 v2 v3 v4 v5 v6 v2 v3 v6 v4 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，散列地址空间为010。若采用线性探查 法解决冲突，则平均查找长度为（ A ）。 (A)5/3 (B)13/9 (C)16/9 (D)3/2 11 下列程序段所代表的算法的时间复杂度为（ C ）。 y=n; x=1; while(xnext=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，散列地址空间为010。若采用线性探查 法解决冲突，则平均查找长度为（ C ）。 (A)5/3 (B)13/9 (C)16/9 (D)3/2 25 下列程序段所代表的算法的时间复杂度为（ 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)31 32 当待排序的关键字个数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），并将线性表中的元素依次插入到一个原先为 空的二叉排序树中去。假设查找每一个元素的概率相同，则查 找该二叉树中任一结点的平均查找长度为（ A ）。 (A)10/3 (B)13/3 (C)37/12 (D)13/2 35 一组关键字序列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/7 36 以数据集4，5，6，7，12，18，10为结点权值所构造的哈夫 曼树，则其带权路径长度WPL为（ A ）。 (A)165 (B)203 (C)124 (D)187 37 假定对线性表R0n-1进行分块查找，若将表均匀地分为b 块，每块含有n/b个记录；又假定表中每个记录的查找概率相 等，并用顺序查找确定所在的块，若要使分块查找的平均查找 长度ASL最小，则分块数b的值应为（ B ）。 (A) (B)+1 (C)log2n (D)log2n+1 38 对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和n 39 若在一个具有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，则应进行的 指针操作为（ ）。 (A)Q-front-next=p-next (B)Q-rear=Q-front (C)Q-front=p-rear (D)Q-rear=p-next 42 假设二叉树T中有n个叶子结点，且所有非叶子结点都有左、右 子树，那么二叉树T共有（ ）个结点。 (A)2n (B)2n-1 (C)2n+1 (D)2n+2 43 已知有向图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,v2 44 已知一棵二叉树的结点数据采用顺序存储结构，数组内容如下 表所示，则该二叉树的后序遍历序列为（ ）。 1 1 2 345 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 E A F D G CJ IH B (A)ACBDJEFIGH (B)ABCDJEFHGI (C)BCJDAHIGFE (D)EADCBJFGIH 45 若T为n个结点的完全二叉树，则T的叶子结点数为（ ）。 (A)n/2 (B)(n-2)/2 (C)(n-1)/2 (D)(n+1)/2 46 有一组数值14,21,32,15,28，用以构造huffman树，则其WPL值 为（ ）。 (A)267 (B)189 (C)110 (D)294 47 采用折半插入排序，关键字的比较次数与移动次数分别为（ ）。 (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)4 49 下面程序段的时间复杂性的量级为（ 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*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+1 51 利用3，6，8，12，5，7这六个值作为叶子结点的权，生成一 棵哈夫曼树，该树的深度为（ B ）。 (A)3 (B)4 (C)5 (D)6 52 一棵二叉树的广义表表示为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,g 53 若长度为n的线性表采用顺序存储结构，在其第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/DE 56 若二叉树采用二叉链表存储结构，要交换其所有分支结点左右 子树的位置，利用（ ）遍历方法最合适。 (A)前序 (B)中序 (C)后序 (D)按层次 57 对二叉排序树进行（ ）遍历，可以得到该二叉树所有结点构 成的排序序列。 (A) 前序 (B)中序 (C)后序 (D)按层次 58 具有n个顶点的有向图最多有（ ）条边。 (A)n (B)n(n1) C n(n+1) (D)n2 59 从未排序序列中依次取出一个元素与已排序序列中的元素依次 进行比较，然后将其放在已排序序列的合适位置，该排序方法 称为（ ）排序法。 (A)插入 (B)选择 (C)shell (D)二路归并 60 排序趟数与序列的原始状态有关的排序方法是（ ）排序法。 (A)插入 (B)选择 (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，84 63 线性链表不具有的特点是（ ）。 (A)随机访问 (B)不必事先估计所需存储空间大小 (C)插入与删除时不必移动元素 (D)所需空间与线性表长度成正比 64 设F是一个森林，B是由F转换得到的二叉树，F中有n个非叶结 点，则B中右指针域为空的结点有（ ）个。 (A)n-1 (B)n (C)n+1 (D)n+2 65 具有65个结点的完全二叉树的高度为（ ）。（根的层次号为 0） (A)8 (B)7 (C)6 (D)5 66 若待排序对象序列在排序前已按其排序码递增顺序排序，则采 用（ ）方法比较次数最少。 (A)直接插入排序 (B)快速排序 (C)归并排序 (D)直接选择排序 67 在一个无向图中，所有顶点的度数之和等于所有边数的（ ） 倍。 (A)3 (B)2 (C)1 (D)1/2 68 对有14个数据元素的有序表R14进行折半搜索，搜索到R3的 关键码等于给定值，此时元素比较顺序依次为（ ）。 (A)R0，R1，R2，R3 (B)R0，R13，R2，R3 (C)R6，R2，R4，R3 (D)R6，R4，R2，R3 69 若度为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)栈 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)不一定连续 (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)直接选择排序 81 串是（ D ）。 (A)不少于一个字母的序列 (B)任意个字母的序列 (C)不少于一个字符的序列 (D)有限个字符的序列 82 一个栈的输入序列为12345，则下列序列中是栈的输出序列的 是（ A ）。 (A)23415 (B)54132 (C)31245 (D)14253 83 设循环队列中数组的下标范围是1n，其头尾指针分别为f和r， 则其元素个数为（ D ）。 (A)r-f (B)r-f+1 (C)(r-f) mod n +1 (D)(r-f+n) mod n 84 二叉树在线索化后，仍不能有效求解的问题是（ D ）。 (A)先序线索二叉树中求先序后继 (B)中序线索二叉树中求中序后继 (C)中序线索二叉树中求中序前驱 (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)1125 88 在下列排序算法中，在待排序的数据表已经为有序时，花费时 间反而最多的是（ A ）。 (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 90 下列排序算法中，某一趟结束后未必能选出一个元素放在其最 终位置上的是（ D ）。 (A)堆排序 (B)冒泡排序 (C)快速排序 (D)直接插入排序 91 在平衡二叉树中插入一个结点后造成了不平衡，设最低的不平 衡点为A，并已知A的左孩子的平衡因子为-1，右孩子的平衡因 子为0，则做（ B ）型调整以使其平衡。 (A)LL (B)LR (C)RL (D)RR 92 下列各式中，按增长率由小至大的顺序正确排列的是（ ）。 (A),n!,2n,n3/2 (B)n3/2,2n,nlogn,2100 (C)2n, logn, nlogn, n3/2 (D)2100, logn, 2n, nn 93 若要在单链表中的结点*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)各自的头结点 (B)各自的尾结点 (C)各自的第一个元素结点 (D)一个表的头结点，另一个表的尾结点 95 栈的两种常用存储结构分别为（ ）。 (A)顺序存储结构和链式存储结构 (B)顺序存储结构和散列存储结构 (C)链式存储结构和索引存储结构 (D)链式存储结构和散列存储结构 96 已知循环队列的存储空间为数组data21，且当前队列的头指针 和尾指针的值分别为8和3，则该队的当前长度为（ ）。 (A)5 (B)6 (C)16 (D)17 97 已知在如下定义的链串结点中，每个字符占1个字节，指针占4 个字节，则该链串的存储密度为（ ）。 typedef struct node char date8; struct node * next; LinkStrNode; (A)1/4 (B)1/2 (C)2/3 (D)3/4 98 应用简单的匹配算法对主串s=“BDBABDABDAB”与子串 t=“BDA”进行模式匹配，在匹配成功时，进行的字符比较总次 数为（ ）。 (A)7 (B)9 (C)10 (D)12 99 二维数组A2010采用列优先的存储方法，若每个元素占2个 存储单元，且第1个元素的首地址为200，则元素A89的存储 地址为（ ）。 (A)574 (B)576 (C)578 (D)580 100 对广义表L=(a,b),c,d)进行操作tail (head (L)的结果是（ ）。 (A)(c,d ) (B)(d ) (C)b (D)(b) 101 已知一棵树的前序序列为ABCDEF，后序序列为CEDFBA， 则对该树进行层次遍历得到的序列为（ ）。 (A)ABCDEF (B)ABCEFD (C)ABFCDE (D)ABCDFE 102 一个含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 (D)3，3，4 104 下列排序方法中，最好与最坏时间复杂度不相同的排序方法 是（ ）。 (A)冒泡排序 (B)直接选择排序 (C)堆排序 (D)归并排序 105 已知含10个结点的二叉排序树是一棵完全二叉树，则该二叉 排序树在等概率情况下查找成功的平均查找长度等于（ ）。 (A)1.0 (B)2.9 (C)3.4 (D)5.5 106 在下列各种文件中，不能进行顺序查找的文件是（ ）。 (A)顺序文件 (B)索引文件 (C)散列文件 (D)多重表文件 107 下面带有标记的语句的频度(n10)是（ ）。 for(int i=0;in-1;i+) for(int j=i+1;jn;j+) coutijendl; (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;prightleft=s; (D)sleft=p;sright=pright;prightleft=s;pright=s; 110 字符串相等的充分必要条件是（ ）。 (A)串长度相等 (B)串使用相同的存储结构 (C)串相同位置对应的字符相等 (D)A和C 111 将一个递归算法改为对应的非递归算法时，通常需要使用（ ）。 (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 n 114 某二叉树的前序遍历结点访问顺序是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-1 116 下面关于排序的说法错误的是（ ）。 (A)快速排序、归并排序都是一种不稳定的排序方法 (B)直接插入排序和折半插入排序移动元素的次数相同 (C)简单选择排序移动元素的次数最少 (D)根据排序需要的平均时间，快速排序是目前最好的一种内部 排序方法 117 折半查找有序表（3，4，5，10，13，14，20，30），若查找 元素3， 则被比较的元素依次为（ ）。 (A)10,20,30 (B)10,14,30 (C)13,3 (D)10, 4, 3 118 下面关于栈和队列的说法正确的是（ ）。 (A)栈是先进先出的线性表，队列是后进先出的线性表 (B)栈是先进先出的线性表，队列也是先进先出的线性表 (C)栈是后进先出的线性表，队列是先进先出的线性表 (D)栈是后进先出的线性表，队列也是后进先出的线性表 119 两个各有n个元素的有序列表并成一个有序表，其最少的比较 次数是（ ）。 (A)n (B)2n-1 (C)2n (D)n-1 120 设循环队列中数组的下标范围是0 n-1，f表示队首元素的前 驱位置，r表示队尾元素的位置，则队列中元素个数为（ ）。 (A)r-f (B)r-f 1 (C)(r-f 1)mod n (D)(r-f n)mod n 121 一个5行6列的二维数组s采用从最后一行开始，每一行的元素 从右至左的方式映射到一维数组a中，s和a的下标均从0开始， 则s33在a中的下标是（ ）。 (A)7 (B)8 (C)9 (D)10 122 设只含根结点的二叉树的高度为1，则高度为n的二叉树中所 含叶子结点的个数最多为（ ）个。 (A)2n (B)n (C)2n -1 (D)2n-1 123 设高度为h的二叉树上只有度为0和度为2的结点，则此二叉树 中所包含的结点数至少为（ ）个（设只含根结点的二叉树的 高度为1）。 (A)2h (B)2h-1 (C)2h+1 (D)h+1 124 对一棵二叉检索树进行（ ） 得到的结点序列是一个有序序 列。 (A)前序周游 (B)中序周游 (C)后序周游 (D)层次周游 125 一棵前序序列为1，2，3，4的二叉树，其中序序列不可能是 （ ） 。 (A)4,1,2,3 (B)4,3,2,1 (C)2,4,3,1 (D)3,4,2,1 126 在含n个顶点和e条边的有向图的邻接矩阵中，零元素的个数 为（ ）。 (A)e (B)2e (C)n2-e (D)n2-2e 127 具有n个顶点和e条边的图的深度优先搜索算法的时间复杂度 为（ ）。 (A)O(n) (B)O(n3) (C)O(n2) (D)O(n e) 128 如果具有n个顶点的图是一个环，则它有（ ）棵生成树。 (A)n (B)n l (C)n-l (D)2n 129 堆排序算法在平均情况下的时间复杂度为（ ）。 (A)O(n) (B)O(nlogn) (C)O(n2) (D)O(logn) 130 在待排序数据已基本有序的前提下，下述排序方法中效率最 高的是（ ）。 (A)直接插入排序 (B)直接选择排序 (C)快速排序 (D)归并排序 131 在理想情况下，散列表中查找元素所需的比较次数为（ ）。 (A)n (B)O (C)n2 (D)1 132 在一棵m阶B树中，若在某结点中插入一个新关键字而引起该 结点分裂，则此结点中原有的关键字的个数是（ ）。 (A)m (B)m +1 (C)m-l (D)m2 133 设顺序循环队列Q0：M-1的头指针和尾指针分别为F和R，头 指针F总是指向队头元素的前一位置，尾指针R总是指向队尾 元素的当前位置，则该循环队列中的元素个数为（ C ）。 (A) R-F (B) F-R (C) (R-F+M)M (D) (F-R+M)M 134 设某棵二叉树的中序遍历序列为ABCD，前序遍历序列为 CABD，则后序遍历该二叉树得到序列为（ A ）。 (A) BADC (B) BCDA (C) CDAB (D) CBDA 135 设某完全无向图中有n个顶点，则该完全无向图中有（ A ）条 边。 (A) n(n-1)/2 (B) n(n-1) (C) n2 (D) n2-1 136 设某棵二叉树中有2000个结点，则该二叉树的最小高度为（C ）。 (A) 9 (B) 10 (C) 11 (D) 12 137 设某有向图中有n个顶点，则该有向图对应的邻接表中有（ B ）个表头结点。 (A) n-1 (B) n (C) n+1 (D) 2n-1 138 设一组初始记录关键字序列(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，8 139 设某数据结构的二元组形式表示为A=(D，R)，D=01，02， 03，04，05，06，07，08，09，R=r，r=， ， ，则数据结构A是（ B ）。 (A) 线性结构 (B) 树型结构 (C) 物理结构 (D) 图型结构 140 下面程序的时间复杂为（ B ） for（i=1，s=0； idata=q-data；p-next=q-next；free(q)； (B) q=p-next；q-data=p-data；p-next=q-next；free(q)； (C) q=p-next；p-next=q-next；free(q)； (D) q=p-next；p-data=q-data；free(q)； 142 设有n个待排序的记录关键字，则在堆排序中需要（ A ）个辅 助记录单元。 (A) 1 (B) n (C) nlog2n (D) n2 143 设一组初始关键字记录关键字为(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 144 设二叉排序树中有n个结点，则在二叉排序树的平均平均查找 长度为（ B ）。 (A) O(1) (B) O(log2n) (C) log2n (D) O(n2) 145 设无向图G中有n个顶点e条边，则其对应的邻接表中的表头结 点和表结点的个数分别为（ D ）。 (A) n，e (B) e，n (C) 2n，e (D) n，2e 146 设某强连通图中有n个顶点，则该强连通图中至少有（ C ）条 边。 (A) n(n-1) (B) n+1 (C) n (D) n(n+1) 147 设有5000个待排序的记录关键字，如果需要用最快的方法选 出其中最小的10个记录关键字，则用下列（ B ）方法可以达 到此目的。 (A) 快速排序 (B) 堆排序 (C) 归并排序 (D) 插入排序 148 下列四种排序中（ D ）的空间复杂度最大。 (A) 插入排序 (B) 冒泡排序 (C) 堆排序 (D) 归并排序 149 设一维数组中有n个数组元素，则读取第i个数组元素的平均时 间复杂度为（ C ）。 (A) O(n) (B) O(nlog2n) (C) O(1) (D) O(n2) 150 设一棵二叉树的深度为k，则该二叉树中最多有（ D ）个结 点。 (A) 2k-1 (B) 2k (C) 2k-1 (D) 2k-1 151 设某无向图中有n个顶点e条边，则该无向图中所有顶点的入 度之和为（ D ）。 (A) n (B) e (C) 2n (D) 2e 152 在二叉排序树中插入一个结点的时间复杂度为（ B ）。 (A) O(1) (B) O(n) (C) O(log2n) (D) O(n2) 153 设某有向图的邻接表中有n个表头结点和m个表结点，则该图 中有（ C ）条有向边。 (A) n (B) n-1 (C) m (D) m-1 154 设一组初始记录关键字序列为(345，253，674，924，627)， 则用基数排序需要进行（ A ）趟的分配和回收才能使得初始 关键字序列变成有序序列。 (A) 3 (B) 4 (C) 5 (D) 8 155 设用链表作为栈的存储结构则退栈操作（ B ）。 (A) 必须判别栈是否为满 (B) 必须判别栈是否为空 (C) 判别栈元素的类型 (D) 对栈不作任何判别 156 下列四种排序中（ A ）的空间复杂度最大。 (A) 快速排序 (B) 冒泡排序 (C) 希尔排序 (D) 堆 157 设某二叉树中度数为0的结点数为N0，度数为1的结点数为 Nl，度数为2的结点数为N2，则下列等式成立的是（ C ）。 (A) N0=N1+1 (B) N0=Nl+N2 (C) N0=N2+1 (D) N0=2N1+l 158 设有序顺序表中有n个数据元素，则利用二分查找法查找数据 元素X的最多比较次数不超过（ A ）。 (A) log2n+1 (B) log2n-1 (C) log2n (D) log2(n+1) 159 数据的最小单位是（ A ）。 (A) 数据项 (B) 数据类型 (C) 数据元素 (D) 数据变量 160 设一组初始记录关键字序列为(50，40，95，20，15，70， 60，45)，则以增量d=4的一趟希尔排序结束后前4条记录关键 字为（ B ）。 (A) 40，50，20，95 (B) 15，40，60，20 (C) 15，20，40，45 (D) 45，40，15，20 161 设一组初始记录关键字序列为(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，25，35，50，80，85，20，36，40，70 (D) 15，25，35，50，80，20，36，40，70，85 162 设一个有序的单链表中有n个结点，现要求插入一个新结点后 使得单链表仍然保持有序，则该操作的时间复杂度为（ D ）。 (A) O(log2n) (B) O(1) (C) O(n2) (D) O(n) 163 设一棵m叉树中度数为0的结点数为N0，度数为1的结点数为 Nl，度数为m的结点数为Nm，则N0=（ B ）。 (A) Nl+N2+Nm (B) l+N2+2N3+3N4+(m-1)Nm (C) N2+2N3+3N4+(m-1)Nm (D) 2Nl+3N2+(m+1)Nm 164 设有序表中有1000个元素，则用二分查找查找元素X最多需要 比较（ B ）次。 (A) 25 (B) 10 (C) 7 (D) 1 165 设连通图G中的边集E=(a，b)，(a，e)，(a，c)，(b，e)，(e， d)，(d，f)，(f，c)，则从顶点a出发可以得到一种深度优先遍 历的顶点序列为（ B ）。 (A) abedfc (B) acfebd (C) aebdfc (D) aedfcb 166 设输入序列是1、2、3、n，经过栈的作用后输出序列 的第一个元素是n，则输出序列中第i个输出元素是（ C ）。 (A) n-i (B) n-1-i (C) n+1-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 168 设一组权值集合W=2，3，4，5，6，则由该权值集合构造 的哈夫曼树中带权路径长度之和为（ D ）。 (A) 20