数据结构试题库

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-next； HS-next=s；(C)s-next=H

2、S； HS=s； (D)s-next=HS； HS=HSnext；4 .假定以开头节点的循环链表表示队列q，并且在队列中仅设置一个开头指针front，不设置队列的末尾指针。 要排队元素*s，在下一个程序算法的空栏中添加的动作语句是(a )。void添加队列(结构链路队列q ) p=Q-front；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的

3、二叉树中只有度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 .存在用于构建哈夫曼树的一系列数值 5

4、，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 v5系列v5 v6 v1v2v2v3v3v6 v4v5系列v4v6设有m=2n-1个关键字，假设对每个关键字检索的概率相等，检索失败的概率为0，若使用二分法

5、检索1个关键字，则平均检索长度为(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，散列地址空间为0到10。 用线性探测法解决冲突后，平均查找长度为(a )。(A)5/3 (B)13/9 (C)16/9 (D)3/211 .以下一段为代表的算法的时间复杂度为(c )。y=n；x=1；while(x=y )x*=2；(A)O(n) (B)O(n2) (C)O(log2n) (D)O ()12 .在以长度n的顺序结构存储的线性表中，假

6、设在线性表的某处插入要素的概率相等，则在插入要素时线性表移动的要素的平均次数为(b )。(A)n2 (B)(n 1)/2 (C)(n-1)/2 (D)n/213 .如果对有秩序的线性表最频繁的操作是找值x的要素，就用(d )存储方式实现检索，其算法的时间复杂性最小。(a )单链表(b )双链表(c )单链表(d )顺序表14 .开头节点head的循环链表为空的判断条件为(c )。(a )头=null (b )头下一个=null(c )头下一个=头头！=空值15 .如果链队列HQ中只有一个节点，则队列的开头指针和末尾指针满足以下条件(d ) :(a ) HQ-rear-next=HQ-front

7、 (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 -数据hs -下一个=空；(C)HS=HS-next； x=HS-data； (d ) x=hs -数据hs=空；17.1根有n个节点的满二叉树，如果有m个叶节点，深度为h，则n、m和h满足条件(d )。(a ) n=MH (b ) hm=2n (c ) m=h-1

8、 (d ) n=2h-118.1根左、右子树不为空的二叉树先被线索化后，该空的指针域数为(b )。(A)0 (B)1 (C)2 (D )不确定性19 .存在用于构建哈夫曼树的一系列数值 5，12，9，20，3 ，其带宽加权路径长度WPL的值为(c )。(A)49 (B)96 (C)103 (D)12520 .在1个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=，

9、(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，散列地址空间为- 0到10。 用线性探测法解决冲突后，平均寻道长度为(c )。(A)5/3 (B)13/9 (C)16/9 (D)3/2

10、25 .由下一段表示的算法的时间复杂度为(d )。i=1； j=0；while(i=n) i=j；j；以下(A)O(n) (B)O(n2) (C)O(log2n) (D)O ()26 .把各有n个要素的规则表汇总成一个规则表，最坏的情况下，其比较次数是(a )。(A)2n-1 (B)n (C)n 1 (D)n-127 .在某链表中最常用的操作在最后的节点之后插入节点、或删除最后的节点时，使用(d )存储方式，最节省执行时间。(a )单链表(b )单链表(c )无头双向链表(d )无头双向链表28 .已知head是非空链表的开头指针，并且指针p指向链表的最后一个节点。 要在p之后插入新节点*s，

11、使链表成为循环链表，应该执行的操作是(b )。(A)s-next=p-next； p-next=s； (b ) s-next=头部； p-next=s；(C)s-next=p-next； p-next=头部； (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(n)、(C)O(n )和O(n )。30 .链队列q的开头指针和末尾指针分别为front和rear，在初始时使队列为空，若向队列中插入

12、元素*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

13、、(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 )，其

14、中，线性表的元素被顺序地插入到原始的空二叉树中。 假设搜索各个要素的概率相同，则搜索该二叉树中的任一节点的平均搜索长度为(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顺序地散列到散列表HT(0:10 )中若检索各要素的概率相同，则检索该混列表任一个要素的平均检索长度为(c )。(A)3/2 (B)10/7 (C)11/7 (D)9/736 .把数据集合 4，5，6，7，12，18，10 构造为节点权重值的霍夫曼树的带宽权重路径长度为(a )。(A)165 (B)203 (C)124 (D)18737 .假定对线性表R0n-1进行块搜索，将表均匀地分割到b块中，假定每块包含n/b个记录，并且在表中的每条记录中检索概率相等，则按顺序检索块(a ) (b )1(c )“log2n”(d )“log2n”138 .直接插入排序n个记录，所需的关键字比较次数的最大值和最小值