C、O（n） D、O（n2）8、数据结构中，通常采用两种方法衡量算法的时间复杂性，即(D) A、最大时间复杂性和最小时间复杂性 B、最好时间复杂性和最坏时间复杂性 C、部分时间复杂性和总体时间复杂性 D、平均时间复杂性和最坏时间复杂性 9、数据结构的基本任务是（D） A、逻辑结构和存储结构的设计 B、数据结构的运算实现 C、数据结构的评价与选择 D、数据结构的设计与实现
10、为了最快地对线性结构的数据进行某数据元素的读取操作，则其数据存储结构宜采用（A）方式。 A、顺序存储 B、链式存储
C、索引存储 D、散列存储 11、数据结构可以形式化地定义为（S，△），其中S指某种逻辑结构，△是指（C） A、S上的算法 B、S的存储结构
C、在S上的一个基本运算集 D、在S上的所有数据元素
12、设某二维数组A［1..n，1..n］，则在该数组中用顺序查找法查找一个元素的时间复杂性的量级为（D） A、O（log2n） B、O(n) C、O(nlog2n) D、O(n2)
13、在线性表的下列存储结构中，读取元素花费时间最少的是（D） A、单链表 B、双链表 C、循环链表 D、顺序表
14、为了方便地在线性结构的数据中插入一个数据元素，则其数据结构宜采用（B）方式。 A、顺序存储 B、链式存储 C、索引存储 D、散列存储 15、下列说法正确的是（B）
A、线性表的逻辑顺序与存储顺序总是一致的
B、线性表的链式存储结构中，要求内存中可用的存储单元可以是连续的，也可以不连续 C、线性表的线性存储结构优于链式存储结构
D、每种数据结构都具有插入、删除和查找三种基本运算 16、下列关于线性表的叙述中，不正确的是(C) A、线性表是n个结点的有穷序列 B、线性表可以为空表
C、线性表的每一个结点有且仅有一个前趋和一个后继 D、线性表结点间的逻辑关系是1:1的联系
17、若某线性表中最常用的操作是在最后一个元素之后插入一个元素和删除第一个元素，则最节省运算时间的存储方式是（D）
A、单链表 B、仅有头指针的单循环链表 C、双链表 D、仅有尾指针的单循环链表 18、从一个长度为n的顺序表中删除第i个元素 （1≤i≤n）时，需向前移动的元素的个数是（A） A、n-i B、n-i+1 C、n-i-1 D、i
19、在一个单链表中，若p所指结点不是最后结点，则删除p所指结点的后继结点的正确操作是(C) A、p=p->next B、p->next=p->next C、p->next=p->next->next D、p->next=p
20、在一个具有n个结点的双链表中插入一个新结点，则该操作的时间复杂性的量级为（A） A、O(1) B、O(n) C、O(nlog2n) D、O(n2)
21、设非空单链表的数据域为data，指针域为next，指针p指向单链表中第i个结点，s指向已生成的新结点，现将s结点插入到单链表中，使其成为第i个结点，下列算法段能正确完成上述要求的是（C） A、s->next=p->next;p->next=s； B、p->next=s;s->next=p->next；
C、s->next=p->next;p->next=s;交换p->data和s->data； D、p=s;s->next=p； 22、栈和队列(C)
A、共同之处在于二者都是先进先出的特殊的线性表 B、共同之处在于二者都是先进后出的特殊的线性表 C、共同之处在于二者都只允许在顶端执行删除操作 D、没有共同之处
23、若有一串数字5、6、7、8入栈，则其不可能的输出序列为(C) ．．．
A.5、6、7、8 B.8、7、6、5 C.8、7、5、6 D.5、6、8、7
24、我们通常把队列中允许删除的一端称为队头。 25、有关栈的描述，正确的是（B） A、栈是一种先进先出的特殊的线性表 B、只能从栈顶执行插入、删除操作 C、只能从栈顶执行插入、栈底执行删除 D、栈顶和栈底均可执行插入、删除操作
26、顺序栈S中top为栈顶指针，指向栈顶元素所在的位置，elem为存放栈的数组，则元素e进栈操作的
主要语句为（D）
A、s.elem［top］=e； s.top=s.top+1； B、s.elem［top+1］=e； s.top=s.top+1； C、s.top=s.top+1； s.elem［top+1］=e； D、s.top=s.top+1； s.elem［s.top］=e； 27、循环队列sq中，用数组elem［0··25］存放数据元素，sq.front指示队头元素的前一个位置，sq.rear
指示队尾元素的当前位置，设当前sq.front为20，sq.rear为12，则当前队列中的元素个数为（D） A、8 B、16 C、17 D、18 28、深度为k的二叉树至多有(B) A、2k个叶子 B、2k-1个叶子 C、2k-1个叶子 D、2k-1-1个叶子 28、关于二叉树性质的描述，正确的是（A） A、二叉树结点的个数可以为0 B、二叉树至少含有一个根结点
C、二叉树若存在两个结点，则必有一个为根，另一个为左孩子
D、二叉树若存在三个结点，则必有一个为根，另两个分别为左、右孩子 29、具有4个结点的二叉树可有（12种形态??） A、4种形态 B、7种形态 C、10种形态 D、11种形态
30、树形结构的特点是：一个结点可以有（B）。 A、多个直接前趋 B、多个直接后继 C、多个前趋 D、一个后继
31、将一棵有50个结点的完全二叉树按层编号，则对编号为25的结点x，该结点（B） A、无左、右孩子 B、有左孩子，无右孩子 C、有右孩子，无左孩子 D、有左、右孩子
32、具有100个结点的完全二叉树的深度为（B） A、6 B、7 C、8 D、9
33、一棵有16结点的完全二叉树，对它按层编号，则对编号为7的结点X，它的双亲结点及右孩子结点的编号分别为（D） A、2，14 B、2，15 C、3，14 D、3，15 34、除根结点外，树上每个结点（B） A、可有任意多个孩子、任意多个双亲 B、可有任意多个孩子、一个双亲 C、可有一个孩子、任意多个双亲 D、只有一个孩子、一个双亲 35、具有100个结点的二叉树中，若用二叉链表存储，其指针域部分用来指向结点的左、右孩子，其余（D）个指针域为空。 A、50 B、99 C、100 D、101 36、顺序查找法与二分查找法对存储结构的要求是（D） A、顺序查找与二分查找均只适用于顺序表
B、顺序查找与二分查找既适用于顺序表，也适用于链表 C、顺序查找只适用于顺序表
D、二分查找只适用于有序的顺序表
37、对于静态表顺序查找算法，若在表头设置岗哨，则正确的查找方式为（C）。 A、从第0个元素往后查找该数据元素 B、从第1个元素往后查找该数据元素
C、从第n个元素开始往前查找该数据元素 D、与查找顺序无关
38、在对查找表的查找过程中，若被查找的数据元素不存在，则把该数据元素插入到集合中。这种方式主
要适合于（B） A、静态查找表 B、动态查找表 C、静态查找表与动态查找表 D、两种表都不适合
39、若用二分查找法取得的中间位置元素键值大于被查找值，说明被查找值位于中间值的前面，下次的查找区间为从原开始位置至（B） A、该中间位置 B、该中间位置－1 C、该中间位置＋1 D、该中间位置／2 40、下列程序段的时间复杂性量级是o(n2)。 for (i=1;i41、在顺序存储的线性表（a1,a2…，an）中的第i (1≤i≤n)个元素之前插入一个元素，则需向后移动n-i+1个元素。42、在栈的顺序实现中，若栈不满，则进栈操作可以用下列算法片断实现： sq->top++；
sq -> data[sq -> top]=x；
43、链队列实际上是一个同时带有头指针和尾指针的单链表，尾指针指向该单链表的队尾结点。
44、如图所示，输入元素为A，B，C，在栈的输出端得到一个输出序列ABC，求出在栈的输入端所有可能的输入序列。（5分）
答：ABC，CBA，CAB，BAC，ACB
45、分别写出下列二叉树的先根、中根、后根遍历序列。
答：先根：
ABCEDFGH
，中根ECGHFDBA
CEBDGFHA
后
根：
：，
