1、 第 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/2 3 在一个 栈 顶指针为 HS 的链栈中插入一个 *s 结点时，应执行执行操作为 （ C ） 。 (A)HS
2、-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-fro
3、nt=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,1
4、2,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)v
5、1,v2,v5,v3,v4,v6 v1 v2 v3 v4 v5 v6 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 下列程序段所代表的算法的
6、时间复杂度为 （ C ） 。 y=n; x=1; v2 v5 v4 v3 v5 v4 v6 v6 v3 第 3 页 共 100 页 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 保存被删除结
7、点的值，则应执行操作为 （ 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
8、,3，用以构造哈夫曼树，则其带权路径长度 WPL 值为（ C ） 。 第 4 页 共 100 页 (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(log
9、2n) (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/2 25 下列程序段所代表的算法的时间复杂度为 （ D ） 。 i=1;j=0; while(inext=p-n
10、ext;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-
11、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
12、, (8,6)6, 则该图的最小生成树的权值为 （ C ）。 (A)24 (B)29 (C)30 (D)31 32 当待排序的关键字个数 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），并将线性表中的元素依次插入
13、到一个原先为空的二叉排序树中去。假设查找每一个元素的概率相同，则查找该二叉树中任一结点的平均查找长度为 （ 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 以
14、数据集 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)n(B)n+1 (C) log2n (D) log2n +1 38 对 n 个记录进行直接插入排序，所需的关键字比较次数的最大值和最小值分别是 （ C ）。 (A)n(n+1
15、)/2 和 n (B)n(n-1)/2 和 n-1 (C) n(n+1)/2-1 和 n-1 (D)n2和 n 39 若在一个具有 n 个结点的有序单链表中插入一个新结点并仍然有序，则该操作的时间复杂度是 （ D ）。 (A)O(1) (B)O(n2) (C)O( nlog2n) (D)O(n) 40 在一个头结点为 head 的空循环链表中插入一个结点 s，则指针 s 应执行操作第 7 页 共 100 页 （ D ）。 (A)head-next=s;s-next=NULL; (B)s-next=head;head-next=NULL; (C)head-next=s;s-next=head-n
16、ext; (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 共有 （ B ）个结点。 (A)2n (B)2n-1 (C)2n+1 (D)2n+2 43 已知有向图 G 的邻
17、接矩阵如下所示，则下列序列中 （ ）不可能是图 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 0 1 1 1 0 00 0 0 0 0 00 1 0 0 1 00 0 0 0 1 00 0 0 0 0 00 0 0 1 1 044 已知一棵二叉树的结点数据采用顺序存储结构，数 组内容如下表所示，则该二叉树的后序遍历序列为 （ C ）。 1 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 E A F
18、 D G C J I H B (A)ACBDJEFIGH (B)ABCDJEFHGI (C)BCJDAHIGFE (D)EADCBJFGIH 第 8 页 共 100 页 45 若 T 为 n 个结点的完全二叉树，则 T 的叶子结点数为 （ D）。 (A)n/2 (B)(n-2)/2 (C)(n-1)/2 (D)(n+1)/2 46 有一组数值 14,21,32,15,28，用以构造 huffman 树，则其 WPL 值为 （ 249 ）。 (A)267 (B)189 (C)110 (D)294 47 采用折半插入排序，关键字的比较次数与移动次数分别为 （ D ）。 (A)O(n),O(log2
19、n) (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;i n; i+) for(j=1;j m; j+) cij=0; for(k=1;k w;k+) cij+=aik*bkj (A)O(i*j*k) (B)O(n*m*k) (C)O(n*j*k) (D)O(n
20、*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),则得到的层次遍历序列为 第 9 页 共 100 页 （ 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
21、,f,g 53 若长度为 n 的线性表采用顺序存储结构，在其第 i 个位置插入一个新元素的算法的时间复杂度为（ C ） 。 (1in+1) (A)O(0) (B)O(1) (C)O(n) (D)O(n2) 54 若在线性表中采用折半查找法查找元素，该线性表应该（ C） 。 (A)元素按值有序 (B)采用顺序存储结构 (C)元素按值有序，且采用顺序存储结构 (D)元素按值有序，且采用链式存储结构 55 已知一算术表达式的中缀形式为 A B *C-D/E，后缀形式为 ABC *+DE/-，其前缀形式为（ D ） 。 (A)A+B*C/DE (B)A+B*CD/E (C)-+*ABC/DE (D)-
22、+A*BC/DE 56 若二 叉树采用二叉链表存储结构，要交换其所有分支结点左右子树的位置，利用（ C ） 遍历方法最合适。 (A)前序 (B)中序 (C)后序 (D)按层次 57 对二叉排序树进行（ B ） 遍历，可以得到该二叉树所有结点构成的排序序列。 (A) 前序 (B)中序 (C)后序 (D)按层次 58 具有 n 个顶点的有向图最多有（ B ）条边。 (A)n (B)n(n1) C n(n+1) (D)n2 59 从未排序序列中依次取出一个元素与已排序序列中的元素依次进行比较，然后将 其放在已排序序列的合适位置，该排序方法称为（ A ）排序法。 (A)插入 (B)选择 (C)shel
23、l (D)二路归并 60 排序趟数与序列的原始状态有关的排序方法是（ A）排序法。 (A)插入 (B)选择 (C)冒泡 (D)快速 61 下面给出的四种排序法中（ D ）排序法是不稳定性排序法。 第 10 页 共 100 页 (A)插入 (B)冒泡 (C)二路归并 (D)堆 62 一个对象序列的排序码为 46， 79， 56， 38， 40， 84，采用快速排序以位于最左位置的对象为基准而得到的第一次划分结果为（ C ）。 (A)38， 46， 79， 56， 40， 84 (B)38， 79， 56， 46， 40， 84 (C)40， 38， 46， 56， 79， 84 (D)38， 4
24、6， 56， 79， 40， 84 63 线性链表不具有的特点是（ A ）。 (A)随机访问 (B)不必事先估计所需存储空间大小 (C)插入与删除时不必移动元素 (D)所需空间与线性表长度成正比 64 设 F 是一个森林， B是由 F 转换得到的二叉树， F 中有 n 个非叶结点，则 B中右指针域为空的结点有（ C ）个。 (A)n-1 (B)n (C)n+1 (D)n+2 65 具有 65 个结点的完全二叉树的高度为（ B）。（根的层次号为 0） (A)8 (B)7 log2n（ 65） 1 (C)6 (D)5 66 若待排序对象序列在排序前已按其排序码递增顺序排序，则采用（ A ）方法比较
25、次数最少。 (A)直接插入排序 (B)快速排序 (C)归并排序 (D)直接选择排序 67 在一个无向图中，所有顶点的度数之和等于所有边数的（ B ）倍。 (A)3 (B)2 (C)1 (D)1/2 68 对有 14 个数据元素的有序表 R14进行折半搜索，搜索到 R3的关键码等于给定值，此时元素比较顺序依次为（ C ）。 (A)R0， R1， R2， R3 (B)R0， R13， R2， R3 (C)R6， R2， R4， R3 (D)R6， R4， R2， R3 69 若度为 m 的哈夫曼树中 ,其叶结点个数为 n,则非叶结点的个数为 （ C ） 。 (A)(n+1)/(m+1)-1 (B)n/m-1 (C)(n-1)/(m-1) (D)n/(m-1)-1
