数据结构选择题汇总（附答案）

1.下面程序段的时间复杂度为( C  )。

   for(int i=0;inext=q->next;   B、 p=q->next;q->next=p;

C、 p=q->next;p->next=q;         D、 q->next=q->next->next;

6.设一个广义表的A=（a，（）），其表尾为(  B  )。

A、a               B、(( ))               C、( )          D、(a)

7.在一个链队中，假设f和r分别为队首和队尾指针，删除一个结点的运算是( C  )。

A、r = f —>next B、r = r —>next C、f = f —>next D、f = r —>next

8.若用数组S[1..n]作为两个栈S1和S2的共同存储结构，对任何一个栈，只有当S全满时才不能作入栈操作。为这两个栈分配空间的最佳方案是( C   )。

A、S1的栈底位置为0，S2的栈底位置为n+1 B、S1的栈底位置为0，S2的栈底位置为n/2

C、S1的栈底位置为1，S2的栈底位置为n   D、S1的栈底位置为1，S2的栈底位置为n/2

9.在有n个结点的二叉链表中，值为空的链域的个数为(  C  )。

A、n-1　　　　   B、2n-1 C、n+1 D、2n+1

10.设有13个值,用它们组成一棵哈夫曼树,则该哈无曼树的共有(  D )个结点.

A、13           B、12             C、26            D、25 

11.对于具有e条边的无向图，它的邻接表中有(  D  )边结点

A、  e-1         B、  e          C、  2(e-1)        D、  2e

12.用二分查找方法查找长度为n的线性表时，每个元素的平均查找长度为(  B  )。

A、O(n)　         B、O(log2n)　    C、O(n2)　      D、O(1)

13.在一个长度为n的线性表中顺序查找值为x的元素时，查找成功的平均查找长度（即x同元素的平均比较次数，假定查找每个元素的概率都相等）为 ( C   ) 。

 A、 n           B、 n/2       C、 (n+1)/2   D、 (n-1)/2

14.如果想在4092个数据中只需要选择其中的最小的10个，采用(  B  )方法最好。

A、起泡法             B、堆排序           C、直接选择法     D、快速排序

15.若串S=“software”,其真子串的个数是(  C   )。

A．8       B．37       C．36         D．9

16.执行下面程序段时，执行T语句的次数为(  A   )。

   for(int i=1;inext==first  D、first!=NULL

20．栈的插入与删除操作在(  A   )进行。

A、 栈顶   B 、栈底    C、 任意位置    D、 指定位置

21．设一个广义表的A=（a），其表尾为(  C   )。

A、a               B、(( ))               C、( )          D、(a)

22．二维数组M的元素是4个字符（每个字符占一个存储单元）组成的串，行下标i的范

围从0到4，列下标j的范围从0到5，M按行存储时元素M[3][5]的起始地址与M按列存储时元素（ B ）的起始地址相同。

  A、M[2][4]           B、M[3][4]       C、M[3][5]       D、M[4][4]

23．树中所有结点的度之和等于所有结点数加(   C  )。

A、  0            B 、 1           C、  -1         D、  2

24．设有13个值,用它们组成一棵哈夫曼树,则该哈无曼树的共有( D  )个结点.

A、13           B、12             C、26            D、25

25．对于一个具有N个顶点的图，如果我们采用邻接矩阵法表示，则此矩阵的维数应该是( B  )。   A、(N-1)×(N-1)  B、N×N  C、(N+1)×(N+1)  D、不确定 

26．对于一个有向图,其邻接矩阵表示比邻接表表示更易于(  A )

A、求一个顶点的入度　            B、求一个顶点的出边邻接点　

C、进行图的浓度优先遍历　        D、进行图的广度优先遍历

27．向一棵AVL树插入元素，可能引起最小不平衡子树的调整过程，此调整分为（ C ）种。

A、2            B、3           C、4           D、5

28.折半查找要求查找表中各元素的关键字值必须是(  A   )排列。

A、 递增或递减      B、递增        C、递减        D、无序

29.  以下序列不是堆的是(  D )

A、{100,85,98,77,80,60,82,40,20,10,66}

B、{100,98,85,82,80,77,66,60,40,20,10}

C、{10,20,40,60,66,77,80,82,85,98,100}

D、{100,85,40,77,80,60,66,98,82,10,20}

30.若串S=“software”,其子串的个数是(   C  )。

A．8       B．37       C．36         D．9

31．数据的最小单位是（ A ）。

A、 数据项 B、 数据类型 C、 数据元素 D、 数据变量

32. 一个栈的输入序列为1，2，3，4，下面哪一个序列不可能是这个栈的输出序列( C )。

A、 1，3，2，4      B、2，3，4，1   C、 4，3，1，2      D、3，4，2，1

33. 对顺序存储的线性表，设其长度为n，在任何位置上插入或删除操作都是等概率的。插入一个元素时平均要移动表中的（ A ）个元素。

A、 n/2          B、（n+1）/2        C、（n -1）/2       D、 n  

34. 某算法的时间代价为T（n）=100n+10nLog2n+n2+10，其时间复杂度为（ C）。

A、O（n）  B、O(nlog2n)   C、 O(n2)   D 、O(1)

35．设一组初始记录关键字序列为(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

36．设一组初始记录关键字序列为(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

37．函数substr(“DATASTRUCTURE”，5，9)的返回值为（ A  ）。

A、 “STRUCTURE” B、 “DATA”

C、 “ASTRUCTUR” D、 “DATASTRUCTURE”

38．设一个有序的单链表中有n个结点，现要求插入一个新结点后使得单链表仍然保持有序，则该操作的时间复杂度为（  D  ）。

A、 O(log2n) B、 O(1) C、 O(n2) D、 O(n)

39．在有n个结点的二叉链表中，值为非空的链域的个数为（ A ）。

A、n-1　　　　   B、2n-1　　　　　C、n+1　　　　　　　D、2n+1

40．设有序表中有1000个元素，则用二分查找查找元素X最多需要比较（ B  ）次。

A、 25 B、 10   C、 7 D、 1

41．设连通图G中的边集E={(a，b)，(a，e)，(a，c)，(b，e)，(e，d)，(d，f)，(f，c)}，则从顶点a出发可以得到一种深度优先遍历的顶点序列为（  A ）。

A、 abedfc B、 acfebd C、 aebdfc D、 aedfcb

42．设输入序列是1、2、3、……、n，经过栈的作用后输出序列的第一个元素是n，则输出序列中第i个输出元素是（  C  ）。

A、 n-i B、 n-1-i C、 n+1-i D、不能确定

43. 设一组初始记录关键字序列为(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

44. 利用n个权值作为叶子结点的生成的哈夫曼树中共包含(  D )个结点

Ａ、n            B、n+1           Ｃ、2*n          Ｄ、2*n-1

45. 向一棵AVL树插入元素，可能引起最小不平衡子树的调整过程，此调整分为（ C  ）种。

A、2            B、3           C、4           D、5

46.数据的基本单位是（ B  ）。

    A.  数据结构        B.  数据元素         C.  数据项          D.  文件

47. 以下算法的时间复杂度为（ D   ）。

       s=0;

       for (i=0;i