数据结构

1．算法是指(   )

A．为解决问题而编写的计算机程序       B．为解决问题而采取的方法与步骤

C．为解决问题而需要采用的计算机语言    D．为解决问题而采用的计算方法

2．设栈S的初始状态为空，现有5个元素组成的序列{1，2，3，4，5}，对该序列在S栈上依次进行如下操作(从序列中的1开始，出栈后不再进栈)：进栈、进栈、进栈、出栈、进栈、出栈、进栈。试问出栈的元素序列是(    )

A．{5，4，3，2，1}     B．{2，1}      C．{2，3}       D．{3，4}

3．设循环队列中数组的下标范围是1-n，其中头尾指针分别是f和r，则其元素个数是(   )

A．r-f         B．r-f+1        C．(r-f) MOD n+1       D．(r-f+n) MOD n

4．在待排序的数据表已经为有序时，下列排序算法中花费时间反而多的是(   )

A．堆排序      B．希尔排序     C．冒泡排序      D．快速排序

5．在有n个子叶节点的哈夫曼树中，其节点总数为(   )

A．不确定         B．2n-1         C．2n+1          D．2n

6．某数列有1000个各不相同的单元，由低到高按序排列，现要对该数列进行二分法检索，在最坏的情况下，需要检视(    )个单元 

A．1000          B．10          C．100         D．500

7、已知数组A中，每个元素A[I，J]在存储时要占3个字节，设I从1变化到8，J从1变化到10，分配内存时是从地址SA开始连续按行存储分配的。试问：A[5，8]的起始地址为(    )

A．SA+141        B．SA+180        C．SA+222        D．SA+225

8．线性表若采用链表存储结构，要求内存中可用存储单元地址(   )

A．必须连续   B．部分地址必须连续   C．一定不连续   D．连续不连续均可

9．下列叙述中，正确的是(   )

A．线性表的线性存储结构优于链表存储结构

B．队列的操作方式是先进后出

C．栈的操作方式是先进先出

D．二维数组是指它的每个数据元素为一个线性表的线性表

10．电线上停着两种鸟(A，B)，可以看出两只相邻的鸟就将电线分为了一个线段。这些线段可公为两类：一类是两端的小鸟相同；另一类是两端的小鸟不相同。已知：电线上两个顶点上正好停着相同的小鸟，试问两端为不同小鸟的线段数目一定是(     )

A．奇数         B．偶数        C．可奇可偶        D．数目固定

11．在列车转辙网络中，有四个车皮编号为1，2，3，4，并按此顺序送入栈中进行调度，这些车皮取出的顺序是(   )

A．4123        B．3241        C．3412         D．4312

12．从未排序序列中挑选元素，并将其依次放入已排序序列（初始时为空）的一端，这种排序方法称为(   )

A．插入排序       B．归并排序         C．选择排序         D．快速排序

13．在计算递归函数，如不用递归过程，则一般情况下必须借助(    )数据结构

A．栈            B．树            C．双向队列            D．广义表

14．使用双向链表存放数据的优点是(   )

A．提高检索速度            B．很方便地插入和删除数据

C．节约存储空间            D．很快回收存储空间

15．对一个满二叉树，m个树叶，l分枝结点，n个结点，则(   )

A．n=l+m           B．l+m=2n           C．m=l-1        D．n=2l-1

16．一维数组与线性表的区别是(   )

A．前者长度固定，后者长度可变      B．后者长度固定，前者长度可变

C．两者长度均固定                  D．两者长度均可变

17.用某种排序方法对线性表25,84,21,47,15,27,68,35,20进行排序，结点变化如下：

(1)25,84,21,47,15,27,68,35,20;       (2)20,15,21,25,47,27,68,35,84;

(3)15,20,21,25,35,27,47,68,84;       (4)15,20,21,25,27,35,47,68,84.

那么，排序方法是(     )            

A．选择排序     B．希尔排序     C．合并排序     D．快速排序

18．具有12个记录的序列，采用冒泡排序最少的比较次数是(   )

A．1            B．144         C．11         D．66

19．下面关于二叉树的叙述正确的是(   )

A．一棵二叉树中叶子结点的个数等于度为2的结点个数加1

B．一棵二又树中的结点个数大于0

C．二叉树中任何一个结点要么是叶，要么恰有两个子女

D．二叉树中，任何一个结点的左子树和右子树上的结点个数一定相等

20．先序序列和中序序列相同的二叉树为空树或(   )

A．任一结点均无右孩子的非空二叉树            B．仅有两个结点的二叉树

C．任一结点均无左孩子的非空二叉树            D．不存在这样的二叉树

21．设有三个元素A、B、C顺序进栈，在进栈过程中可以出栈，出栈次序错误的排列是(   )

A．ABC       B．BCA        C．CAB       D．CBA

22．下面四种内排序方法中，要求内存容量最大的是(   )

A．插入排序       B．选择排序        C．快速排序       D．归并排序

23．设有序列F：（49，38，65，97，76，13，27，50），使用快速排序法，其趟数为(   )

A．3          B．2          C．1          D．4

24．给出一组整型数28、10、37、63、35、30、23，请用二叉树对它进行排序。为此，首先要生成一棵二叉树，规则是把第一数放在根处，接着凡比它小的数放在左子树，比它大的数放在右子树，直到把所有的数均安排好。然后对此二叉树进行(    )，得到的就是按照升序排列好的序列。

A．前序遍历        B．中序遍历        C．后序遍历        D．横向遍历

25．用某种排序方法对线性表(84,47,25,15,21)进行排序，结点序列的变化如下 (1)84,47,25,15,21;(2)15,47,25,84,21;

(3)15,21,25,84,47;(4)15,21,25,47,84

那么，所采用的排序方法是(     )

A．选择排序         B．冒泡排序        C．插入排序        D．快速排序

26．设二叉树根结点的层次为0，一棵高度为b的满二叉树中结点的个数是(   )

A．2^b            B．2^(b-1)        C．2^b-1         D．2^(b+1)-1

27．深度为5的二叉树至多有( )个结点(   )

A．16            B．32           C．31          D．10

28．下面关于线性表的描述，错误的是(   )

A．栈是线性表的一种

B．任给一索引I（1<=I<=表中元素个数），就能在线性表中唯一确定一个元素

C．线性表的任一元素都有前驱和后继

D．线性表是一个线性序列

29．带权路径长度最小的二叉树是(   )

A．顺序二叉树        B．二叉排序树        C．判定树       D．哈夫曼树

30．有12个结点的平衡二叉树的最大深度是(   )

A．4          B．5            C．6           D．3

31．若用冒泡排序法对序列18，14，6，27，8，12，16，52，10，26，47，29，41，24从小到大进行排序，共要进行(    )次比较。

A．33           B．45           C．70            D．91

32．设n，m为某二叉树上的两个结点，在中序遍历时，n在m前的条件是(   )

A．n在m右方      B．n是m祖先      C．n在m左方       D．n是m子孙

33．下列四种排序方法，如果被排序的序列中诸元素恰好已经按要求（由小到大或由大到小排序，就元素的比较次数和移动次数而言，哪种方法最少？(   )

A．冒泡排序       B．直接选择排序     C．直接插入排序     D．归并排序

34．如果某二叉树的前序为STUWV，中序为UWTVS，那么该二叉树的后序是(   )

A．WUVTS        B．UWVTS        C．VWUTS         D．WUTSV

35．按照二叉树的定义，具有3个结点的二叉树有(   )

A．3种           B．4种            C．5种            D．6种

36．对以下关键字序列用快速排序法进行排序，速度最慢的情况是(   )

A．{19，23，3，15，7，21，8}            B．{23，21，28，15，19，3，7}

C．{19，7，15，28，23，21，3}           D．{3，7，15，19，21，23，28}

37．数组A中，每个元素A[I，j]的长度为3个字节，行下标I为1到8，列下标j从1到10。从首地址SA开始连续存放在存储器中，存放该数组至少需要的单元数是(    )

A．80           B．100           C．240             D．270

38．树的基本遍历策略可分为先根遍历和后根遍历；二叉树的基本遍历策略可分为先序遍历、中序遍历和后序遍历。这里，我们把由树转化得到的二叉树叫做这棵树对应的二叉树。正确的结论是(   )            

A．树的先根遍历序列与其对应的二叉树的先序遍历序列相同

B．树的先根遍历序列与其对应的二叉树的中序遍历序列相同

C．树的后根遍历序列与其对应的二叉树的先序遍历序列相同

D．树的后根遍历序列与其对应的二叉树的后序遍历序列相同

39．在数据结构中，从逻辑上可以把数据结构分成(   )

A．动态结构和静态结构         B．线性结构和非线性结构

C．内部结构和外部结构         D．紧凑结构和非紧凑结构

40．如果T2是由有序树T转换而来的二叉树，那么T中结点的后序就是T2中结点的(   )

A．前序        B．中序       C．后序       D．层次序

41．某二叉树的前序遍历结点访问顺序是abdgcefh，中序遍历的结点访问

顺序是dgbaechf，则其后序遍历的结点访问顺序是(   )

A．bdgcefha      B．gdbecfha      C．bdgaechf      D．gdbehfca

42．从未排序序列中挑选元素，并将其依次放入已排序序列（初始时为空）的一端，这种排序方法称为(   )

A．插入排序         B．选择排序     C．归并排序        D．快速排序

43．快速排序方法在(    )情况下最不利于发挥其长处

A．被排序的数据量太大               B．被排序数据中含有多个相同值

C．被排序数据已基本有序             D．被排序数据数目为奇

44．下面关于数据结构的叙述中，正确的叙述是(   )

A．顺序存储方式的优点是存储密度大，且插入、删除运算效率高

B．链表中的每一个结点都包含一个指针

C．包含n个结点的二叉排序树的最大检索长度为log＼-2n

D．将一棵树转换为二又树后，根结点没有右子树

45．在计算机科学领域中,算法分为两类:数值型算法和非数值型算法。下面的算法，哪一个属于数值算法类(   )

A．迭代法         B．冒泡法          C．黑盒法      D．杂凑（Hash）法

46．若已知一个栈的输入序列为1，2，3…，n，其输出序列为P1，P2，…，Pn。若P1=n，则Pi为(   )

A．I            B．n+I            C．n-I+1         D．不确定

47．带头结点的单链表Head为空的判定条件是(   )

A．Head=NIL    B．Head^.Next=NIL   C．Head^.Next=Head    D．Head=Head

48．二维数组a的成员是6个字符组成的串，行下标I的范围从0到8，列下标j的范围从1到10，则存放a至少需要(     )个字节

A．90            B．180         C．240            D．540

49．由3个结点可以构造出多少种不同的有向树(   )

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

50．二维数组M[I，j]的元素是4个字符（每个字符占一个存储单元）组成的串，行下标I的范围从0到4，列下标j的范围从0到5。M按行存储元素M[3，5]的起始地址与M按列存储时元素(    )_的起始地址相同。

A．m[2,4]         B．m[3,4]        C．m[3,5]         D．m[4,4]

51．判断一有向图是否存在回路除可以利用拓扑排序方法外，还可以利用(   )

A．求关键路径的方法            B．求最短路径的方法

C．广度优先遍历方法            D．深度优先遍历方法

52．在一非空二叉树的中序遍历序列中，根结点的右边(   )

A．只有右子树上的所有结点            B．只有右子树上的部分结点

C．只有左子树上的所有结点            D．只有左子树上的部分结点

53．一个队列的入列序列是1，2，3，4，则队列的输出序列是(   )

A．4，3，2，1            B．1，2，3，4

C．1，4，3，2            D．3，2，4，1

54．邻接表存储结构下图的深度优先遍历算法结构类似于二叉树的(   )

A．先序遍历      B．中序遍历        C．后序遍历        D．按层遍历

55．设待排序的记录为(20,16,13,14,19)，经过下列过程将这些记录排序：

(1)20,16,13,14,19;(2)16,20,13,14,19;

(3)13,16,20,14,19;(4)13,14,16,20,19;

(5)13,14,16,19,20.所用的排序方法是(    )           

A．直接插入排序       B．冒泡排序      C．希尔排序       D．堆排序

56．计算机算法一般被划分为数值算法和非数值算法两大类，下列叙述中，

哪个不属于数值算法(   )

A．迭代法         B．直接法       C．杂凑（Hash）法      D．消去法

57．用归并排序方法对线性表（49，38，65，97，76，13，27，49，55，04）

进行排序时，其第三趟的排序结果为(   )

A．12，27，38，49，49，65，76，97，04，55

B．38，49，65，97，13，27，49，76，04，55

C．38，49，65，97，13，76，27，49，04，55

D．01，13，27，38，49，49，55，65，76，97

58．栈和队列都是(   )

A．顺序存储的线性结构            B．链式存储的非线性结构

C．限制存取点的线性结构            D．限制存取点的非线性结构

59．对N个结点的线性表进行查找，用顺序查找的时间复杂性为(   )

A．N*N         B．Nlog2n        C．n      D．log2n

60．若进栈序列为1，2，3．4假定进栈和出栈可以穿插进行，则可能的出栈序列是(   )

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

61．设计一判别表达式中左、右括号是否配对的算法，采用(  )数据结构最佳A．线性表的顺序存储结构    B．栈    C．队列   D．线性表的链式存储结构

62．设一棵二叉树，其叶子结点分别带权10，12，4，7，5，18，2则其带权路径长度最小为(   )

A．120           B．130           C．140           D．150

63．以下关于数据结构的叙述，正确的是(   )

A．线性表的线性存储结构优于链式结构

B．二叉树的第I层上有2的（I-1）次幂个结点，深度为K的二叉树上有2的（k-1）次幂个结点

C．二维数组是其数据元素为线性表的线性表

D．栈的操作方式是先进先出

64．循环队列用数组A[0…m-1]存放其元素值，已知其头尾指针分别是front和rear，则当前队列中的元素个数是(   )

A．（rear-front+m）MOD m    B．rear-front-1 

C．rear-front+1             D．rear-front

65．把一般树转化为二叉树的方法是：对每一结点的子树，在其根之间加水平连线，然后仅保留(    )而抹掉该结点和其它子树之间的连线，最后以树的根结点为轴，将树顺时针转45度即可

A．最右子树      B．右子树        C．左子树         D．最左子树

66．下列哪一种图的邻接矩阵是对称矩阵(   )

A．有向图            B．无向图          C．AOV网          D．AOE网

67．计算机算法必须具备的三个特性是(   )

A．可执行性、可移植性和可扩充性      B．可执行性、确定性和有穷性

C．确定性、有穷性和稳定性            D．易读性、稳定性和安全性

68．对长度为10的有序表进行折半查找，设在等概率时查找成功的平均查找长度是(   )

A．2.9            B．3.1            C．3.4            D．2.6

69．设有6个结点的无向图，该图至少应该有(     )条边才能确保是一连通图

A．5            B．6            C．7            D．8

70．有6个元素按6，5，4，3，2．1的顺序进栈，问下列哪一个不是合法的出栈序列(   )

A．5，4，3，6，1，2            B．4，5，3，1，2，6

C．3，4，6，5，2，1            D．2，3，1，4，5，6