数据结构试题库

来源网络来源网络来源网络数据结构试题库单项选择题下列程序段所代表的算法的时间复杂度为（D）。x=n;y=0;while(x>=(y+1)*(y+1))y++;(A)O(n)(B)O(n2)(C)O(log2n)(D)O()在一个长度为n的以顺序结构存储的线性表中，假设在线性表的任何位置删除元素的概率相等，则删除一个元素时线性表所需移动元素的平均次数为（B）。(A)n2(B)(n-1)/2(C)(n+1)/2(D)n/2在一个栈顶指针为HS的链栈中插入一个*s结点时，应执行执行操作为（C）。(A)HS->next=s;(B)s->next=HS->next;HS->next=s;(C)s->next=HS;HS=s;(D)s->next=HS;HS=HS>next;假设以带头结点的循环链表表示队列Q，并且队列只设一个头指针front，不设队列尾指针。若要进队一个元素*s，则在下列程序算法的空白处应添加的操作语句是（A）。voidAddQueue(structlinkqueueQ){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->front=s;(C)s->next=p;p->next=Q->front;(D)Q->front->next=s;s->next=p;设高度为h的二叉树上只有度为0和度为2的结点，则此类二叉树中所包含的结点数至少为（B）。(A)2h-1(B)2h-1+1(C)2h-1(D)2h-1-3现有数据集{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,96有一组数值{5,12,9,20,3}，用以构造哈夫曼树，则其带权路径长度WPL值为（D）。(A)93(B)96(C)123(D)103已知一个有向图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^v5v5^v6^v3^v4^v5v5^v6^v1v2v2v2v3^v3v3v6^v6^v4^v5v4v4v6^设有m=2n-1个关键字，假设对每个关键字查找的概率相等，查找失败的概率为0，若采用二分法查找一个关键字，则平均查找长度为（D）。(A)n-1(B)n-n/m(C)(n-1)-n/m(D)(n-1)+n/m已知一个待散列存储的线性表{18,81,58,34,26,75,67,49,93}，散列函数为h(k)=k%11，散列地址空间为0~10。若采用线性探查法解决冲突，则平均查找长度为（A）。(A)5/3(B)13/9(C)16/9(D)3/2下列程序段所代表的算法的时间复杂度为（C）。y=n;x=1;while(x<=y)x*=2;(A)O(n)(B)O(n2)(C)O(log2n)(D)O()在一个长度为n的以顺序结构存储的线性表中，假设在线性表的任何位置插入元素的概率相等，则插入一个元素时线性表所需移动元素的平均次数为（B）。(A)n2(B)(n+1)/2(C)(n-1)/2(D)n/2若对一个已有序的线性表最频繁的操作是查找值为x的元素(假设存在的话)，则采用（D）存储方式实现查找，其算法的时间复杂度为最小。(A)单链表(B)双链表(C)单循环链表(D)顺序表一个带头结点head的循环单链表为空的判断条件是（C）。(A)head==NULL(B)head->next==NULL(C)head->next==head(D)head!=NULL若链队列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从一个栈顶指针为HS的链栈中删除一个结点时，用x保存被删除结点的值，则应执行操作为（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;一棵有n个结点的满二叉树，有m个叶子结点，深度为h，那么n、m和h满足条件（D）。(A)n=m+h(B)h+m=2n(C)m=h-1(D)n=2h-1一棵左、右子树均不为空的二叉树在先序线索化后，其空指针域数为（B）。(A)0(B)1(C)2(D)不确定有一组数值{5,12,9,20,3}，用以构造哈夫曼树，则其带权路径长度WPL值为（C）。(A)49(B)96(C)103(D)125在一个n个结点的二叉排序树中查找一个关键字，进行关键字比较次数最大值为（A）。(A)n(B)n/2(C)log2n(D)n*log2n已知有向图G=(V,E)，其中V={v1,v2,v3,v4,v5,v6}，则下列边集合E中（A）所对应的有向图没有拓扑序列。E={<v2,v1>,<v6,v2>,<v1,v3>,<v2,v3>,<v5,v3>,<v3,v4>,<v4,v6>,<v5,v6>}E={<v1,v2>,<v1,v3>,<v1,v4>,<v3,v5>,<v3,v2>,<v4,v5>,<v6,v5>,<v6,v4>}E={<v1,v3>,<v1,v4>,<v1,v5>,<v2,v3>,<v2,v2>,<v3,v5>,<v3,v6>,<v4,v5>,<v4,v6>,<v5,v6>}E={<v1,v2>,<v1,v3>,<v2,v3>,<v1,v4>,<v2,v5>,<v3,v6>,<v4,v6>,<v5,v6>}冒泡排序算法在最好情况下的时间复杂度为（B）。(A)O(log2n)(B)O(n)(C)O(1)(D)O(n2)在下列内部排序方法中，排序时不稳定的，而且关键字的比较次数与记录的初始排列次序无关的是（D）。(A)快速排序(B)冒泡排序(C)归并排序(D)堆排序已知一个待散列存储的线性表{18,81,58,34,26,75,67,49,93}，散列函数为h(k)=k%11，散列地址空间为0~10。若采用线性探查法解决冲突，则平均查找长度为（C）。(A)5/3(B)13/9(C)16/9(D)3/2下列程序段所代表的算法的时间复杂度为（D）。i=1;j=0;while(i<=n){i+=j;j++;}(A)O(n)(B)O(n2)(C)O(log2n)(D)O()将两个各有n个元素的有序表归并成一个有序表，在最坏的情况下，其比较次数是（A）。(A)2n-1?(B)n???(C)n+1?(D)n-1若某链表中最常用的操作是在最后的一个结点之后插入一个结点或删除最后一个结点，则采用（D）存储方式最节省运行时间。(A)单链表(B)单循环链表(C)无头双向链表(D)带头双向链表已知head是一个非空单链表的头指针，指针p指向单链表的最后一个结点，若要在p之后插入一个新结点*s，并将单链表变为循环单链表，则应执行的操作是（B）。(A)s->next=p->next;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;已知用循环链表表示的队列长度为n，若只设头指针，则出队和入队一个元素的时间复杂度分别是（B）。(A)O(1)和O(1)(B)O(1)和O(n)(C)O(n)和O(1)(D)O(n)和O(n)设链队列Q的头指针和尾指针分别为front和rear，初始时队列为空，若向队列插入一个元素*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;已知一个带权图的顶点集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,(8,6)6},则该图的最小生成树的权值为（C）。(A)24(B)29(C)30(D)31当待排序的关键字个数n很小，且初始排列为逆序时，采用下列排序方法中的（D），算法的时间复杂度最小。(A)直接插入排序(B)简单选择排序(C)冒泡排序(D)快速排序对二叉排序树进行（C）遍历，可以得到该二叉树所有结点构成的排序序列。(A)层次???(B)前序???(C)中序???(D)后序已知一个长度为12的线性表（8，2，5，7，12，3，10，4，1，6，9，11），并将线性表中的元素依次插入到一个原先为空的二叉排序树中去。假设查找每一个元素的概率相同，则查找该二叉树中任一结点的平均查找长度为（A）。(A)10/3(B)13/3(C)37/12(D)13/2一组关键字序列{15，92，124，5，27，28，18，6，36，34，30，26，32，259}，将它们用散列函数H(key)=keyMOD11按顺序散列到HASH表HT（0:10）中，用链地址解决冲突。假设查找每一个元素的概率相同，则查找该HASH表中任一元素的平均查找长度为（C）。(A)3/2(B)10/7(C)11/7(D)9/7以数据集{4，5，6，7，12，18，10}为结点权值所构造的哈夫曼树，则其带权路径长度WPL为（A）。(A)165(B)203(C)124(D)187假定对线性表R[0…n-1]进行分块查找，若将表均匀地分为b块，每块含有n/b个记录；又假定表中每个记录的查找概率相等，并用顺序查找确定所在的块，若要使分块查找的平均查找长度ASL最小，则分块数b的值应为（B）。(A)(B)+1(C)「log2n」(D)「log2n」+1对n个记录进行直接插入排序，所需的关键字比较次数的最大值和最小值分别是（C）。(A)n(n+1)/2和n(B)n(n-1)/2和n-1(C)n(n+1)/2-1和n-1(D)n2和n若在一个具有n个结点的有序单链表中插入一个新结点并仍然有序，则该操作的时间复杂度是（）。(A)O(1)(B)O(n2)(C)O(nlog2n)(D)O(n)在一个头结点为head的空循环链表中插入一个结点s，则指针s应执行操作（）。(A)head->next=s;s->next=NULL;(B)s->next=head;head->next=NULL;(C)head->next=s;s->next=head->next;(D)s->next=head;head->next=s;设链队列Q的头指针和尾指针分别为front和rear，队中元素个数为n(n>1)，指针*p指向队首元素m。若删除元素m，则应进行的指针操作为（）。(A)Q->front->next=p->next(B)Q->rear=Q->front(C)Q->front=p->rear(D)Q->rear=p->next假设二叉树T中有n个叶子结点，且所有非叶子结点都有左、右子树，那么二叉树T共有（）个结点。(A)2n(B)2n-1(C)2n+1(D)2n+2已知有向图G的邻接矩阵如下所示，则下列序列中（）不可能是图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已知一棵二叉树的结点数据采用顺序存储结构，数组内容如下表所示，则该二叉树的后序遍历序列为（）。1123456789101112131415161718192021EAFDGCJIHB(A)ACBDJEFIGH(B)ABCDJEFHGI(C)BCJDAHIGFE(D)EADCBJFGIH若T为n个结点的完全二叉树，则T的叶子结点数为（）。(A)n/2(B)(n-2)/2(C)(n-1)/2(D)(n+1)/2有一组数值14,21,32,15,28，用以构造huffman树，则其WPL值为（）。(A)267(B)189(C)110(D)294采用折半插入排序，关键字的比较次数与移动次数分别为（）。(A)O(n),O(log2n)(B)O(n2),O(log2n)(C)O(log2n),O(n2)(D)O(nlog2n),O(n2)假设结点序列为{60,30,90,50,95,70,40,80}，以此构成一棵二叉排序树，则在该二叉排序树上查找一个结点的平均查找长度为（）。(A)23/8(B)11/4(C)9/2(D)4下面程序段的时间复杂性的量级为（D）。for(i=1;i＜＝n;i++)for(j=1;j＜＝m;j++){c[i][j]=0;for(k=1;k＜＝w;k++)c[i][j]+=a[i][k]*b[k][j]}(A)O(i*j*k)(B)O(n*m*k)(C)O(n*j*k)(D)O(n*m*w)在一个长度为n的线性表中，删除值为x的元素时需要比较元素和移动元素的总次数为（C）。(A)（n+1）/2(B)n/2(C)n(D)n+1利用3，6，8，12，5，7这六个值作为叶子结点的权，生成一棵哈夫曼树，该树的深度为（B）。(A)3(B)4(C)5(D)6一棵二叉树的广义表表示为a(b(c,d),e(,f(g))),则得到的层次遍历序列为（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,f,g若长度为n的线性表采用顺序存储结构，在其第i个位置插入一个新元素的算法的时间复杂度为（）。(1≤i≤n+1)(A)O(0)???(B)O(1)???(C)O(n)???(D)O(n2)若在线性表中采用折半查找法查找元素，该线性表应该（）。(A)元素按值有序???(B)采用顺序存储结构(C)元素按值有序，且采用顺序存储结构(D)元素按值有序，且采用链式存储结构已知一算术表达式的中缀形式为A＋B*C-D/E，后缀形式为ABC*+DE/-，其前缀形式为（）。?(A)–A+B*C/DE???(B)–A+B*CD/E(C)-+*ABC/DE???(D)-+A*BC/DE若二叉树采用二叉链表存储结构，要交换其所有分支结点左右子树的位置，利用（）遍历方法最合适。?(A)前序???(B)中序???(C)后序???(D)按层次对二叉排序树进行（）遍历，可以得到该二叉树所有结点构成的排序序列。?(A)前序???(B)中序???(C)后序???(D)按层次具有n个顶点的有向图最多有（）条边。?(A)n???(B)n(n—1)???Cn(n+1)???(D)n2从未排序序列中依次取出一个元素与已排序序列中的元素依次进行比较，然后将其放在已排序序列的合适位置，该排序方法称为（）排序法。?(A)插入???(B)选择???(C)shell???(D)二路归并排序趟数与序列的原始状态有关的排序方法是（）排序法。?(A)插入???(B)选择???(C)冒泡???(D)快速下面给出的四种排序法中（）排序法是不稳定性排序法。(A)插入???(B)冒泡???(C)二路归并???(D)堆一个对象序列的排序码为{46，79，56，38，40，84}，采用快速排序以位于最左位置的对象为基准而得到的第一次划分结果为（）。(A){38，46，79，56，40，84}(B){38，79，56，46，40，84}(C){40，38，46，56，79，84}(D){38，46，56，79，40，84}线性链表不具有的特点是（）。(A)随机访问(B)不必事先估计所需存储空间大小(C)插入与删除时不必移动元素(D)所需空间与线性表长度成正比设F是一个森林，B是由F转换得到的二叉树，F中有n个非叶结点，则B中右指针域为空的结点有（）个。(A)n-1(B)n(C)n+1(D)n+2具有65个结点的完全二叉树的高度为（）。（根的层次号为0）(A)8(B)7(C)6(D)5若待排序对象序列在排序前已按其排序码递增顺序排序，则采用（）方法比较次数最少。(A)直接插入排序(B)快速排序(C)归并排序(D)直接选择排序在一个无向图中，所有顶点的度数之和等于所有边数的（）倍。(A)3(B)2(C)1(D)1/2对有14个数据元素的有序表R[14]进行折半搜索，搜索到R[3]的关键码等于给定值，此时元素比较顺序依次为（）。(A)R[0]，R[1]，R[2]，R[3](B)R[0]，R[13]，R[2]，R[3](C)R[6]，R[2]，R[4]，R[3](D)R[6]，R[4]，R[2]，R[3]若度为m的哈夫曼树中,其叶结点个数为n,则非叶结点的个数为（）。(A)[(n+1)/(m+1)]-1(B)[n/m]-1(C)[(n-1)/(m-1)](D)[n/(m-1)]-1下面关于算法说法错误的是（）。(A)算法最终必须由计算机程序实现(B)为解决某问题的算法同为该问题编写的程序含义是相同的(C)算法的可行性是指指令不能有二义性(D)以上几个都是错误的以下与数据的存储结构无关的术语是（）。(A)循环队列(B)链表(C)哈希表(D)栈以下数据结构中，哪一个是线性结构（）。(A)广义表(B)二叉树(C)稀疏矩阵(D)串以下那一个术语与数据的存储结构无关？（）(A)栈(B)哈希表(C)线索树(D)双向链表在下面的程序段中，对x的赋值语句的频度为（）。FORi:=1TOnDOFORj:=1TOnDOx:=x+1;(A)O(2n)(B)O(n)(C)O(n2)(D)O(log2n)以下哪个数据结构不是多型数据类型（）。(A)栈(B)广义表(C)有向图(D)字符串连续存储设计时，存储单元的地址（）。(A)一定连续(B)一定不连续(C)不一定连续(D)部分连续，部分不连续?一棵左右子树均不空的二叉树在先序前驱和后序后继线索化后，其空链域数为（A）。(A)0(B)1(C)2(D)不确定设图G采用邻接表存储，则拓扑排序算法的时间复杂度是（B）。(A)O(n)(B)O(n+e)(C)O(n2)(D)O(n*e)下列排序算法中，时间复杂度为O(nlog2n)且占用额外空间最少的是（A）。(A)堆排序(B)冒泡排序(C)快速排序(D)SHELL排序已知数据表A中每个元素距其最终位置不远，则采用（B）排序算法最节省时间。(A)堆排序(B)插入排序(C)快速排序(D)直接选择排序串是（D）。(A)不少于一个字母的序列(B)任意个字母的序列(C)不少于一个字符的序列(D)有限个字符的序列一个栈的输入序列为12345，则下列序列中是栈的输出序列的是（A）。(A)23415(B)54132(C)31245(D)14253设循环队列中数组的下标范围是1~n，其头尾指针分别为f和r，则其元素个数为（D）。(A)r-f(B)r-f+1(C)(r-f)modn+1(D)(r-f+n)modn二叉树在线索化后，仍不能有效求解的问题是（D）。(A)先序线索二叉树中求先序后继(B)中序线索二叉树中求中序后继(C)中序线索二叉树中求中序前驱(D)后序线索二叉树中求后序后继求最短路径的FLOYD算法的时间复杂度为（D）。(A)O(n)(B)O(n+e)(C)O(n2)(D)O(n3)一棵左右子树不空的二叉树在先序线索化后，其空指针域数为（B）。(A)0(B)1(C)2(D)不确定数组A[1..5,1..6]的每个元素占5个单元，将其按行优先顺序存储在起始地址为1000的连续的内存单元中，则元素A[5,5]的地址为（A）。(A)1140(B)1145(C)1120(D)1125在下列排序算法中，在待排序的数据表已经为有序时，花费时间反而最多的是（A）。(A)快速排序(B)希尔排序(C)冒泡排序(D)堆排序对有18个元素的有序表做折半查找，则查找A[3]的比较序列的下标依次为（D）。(A)1-2-3(B)9-5-2-3(C)9-5-3(D)9-4-2-3下列排序算法中，某一趟结束后未必能选出一个元素放在其最终位置上的是（D）。(A)堆排序(B)冒泡排序(C)快速排序(D)直接插入排序在平衡二叉树中插入一个结点后造成了不平衡，设最低的不平衡点为A，并已知A的左孩子的平衡因子为-1，右孩子的平衡因子为0，则做（B）型调整以使其平衡。(A)LL(B)LR(C)RL(D)RR下列各式中，按增长率由小至大的顺序正确排列的是（）。(A),n!,2n,n3/2(B)n3/2,2n,nlogn,2100(C)2n,logn,nlogn,n3/2(D)2100,logn,2n,nn若要在单链表中的结点*p之后插入一个结点*s，则应执行的语句是（）。(A)s-＞next=p-＞next;p-＞next=s;(B)p-＞next=s;s-＞next=p-＞next(C)p-＞next=s-＞next;s-＞next=p;(D)s-＞next=p;p-＞next=s-＞next;若要在O（1）的时间复杂度上实现两个循环链表头尾相接，则应对两个循环链表各设置一个指针，分别指向（）。(A)各自的头结点(B)各自的尾结点(C)各自的第一个元素结点(D)一个表的头结点，另一个表的尾结点栈的两种常用存储结构分别为（）。(A)顺序存储结构和链式存储结构(B)顺序存储结构和散列存储结构(C)链式存储结构和索引存储结构(D)链式存储结构和散列存储结构已知循环队列的存储空间为数组data[21]，且当前队列的头指针和尾指针的值分别为8和3，则该队的当前长度为（）。(A)5(B)6(C)16(D)17已知在如下定义的链串结点中，每个字符占1个字节，指针占4个字节，则该链串的存储密度为（）。typedefstructnode{chardate[8];structnode*next;}LinkStrNode;(A)1/4(B)1/2(C)2/3(D)3/4应用简单的匹配算法对主串s=“BDBABDABDAB”与子串t=“BDA”进行模式匹配，在匹配成功时，进行的字符比较总次数为（）。(A)7(B)9(C)10(D)12二维数组A[20][10]采用列优先的存储方法，若每个元素占2个存储单元，且第1个元素的首地址为200，则元素A[8][9]的存储地址为（）。(A)574(B)576(C)578(D)580对广义表L=((a,b),c,d)进行操作tail(head(L))的结果是（）。(A)(c,d)(B)(d)(C)b(D)(b)已知一棵树的前序序列为ABCDEF，后序序列为CEDFBA，则对该树进行层次遍历得到的序列为（）。(A)ABCDEF(B)ABCEFD(C)ABFCDE(D)ABCDFE一个含n个顶点和e条弧的有向图以邻接矩阵表示法为存储结构，则计算该有向图中某个顶点出度的时间复杂度为（）。(A)O(n)(B)O(e)(C)O(n+e)(D)O(n2)在关键字序列（12，23，34，45，56，67，78，89，91）中二分查找关键字为45，89和12的结点时，所需进行的比较次数分别为（）。(A)4，4，3(B)4，3，3(C)3，4，4(D)3，3，4下列排序方法中，最好与最坏时间复杂度不相同的排序方法是（）。(A)冒泡排序(B)直接选择排序(C)堆排序(D)归并排序已知含10个结点的二叉排序树是一棵完全二叉树，则该二叉排序树在等概率情况下查找成功的平均查找长度等于（）。(A)1.0(B)2.9(C)3.4(D)5.5在下列各种文件中，不能进行顺序查找的文件是（）。(A)顺序文件(B)索引文件(C)散列文件(D)多重表文件下面带有@标记的语句的频度(n>10)是（）。 for(inti=0;i<n-1;i++) for(intj=i+1;j<n;j++) @cout<<i<<j<<endl;(A)n*(n-1)/2(B)n*n/2(C)n*(n+1)/2(D)不确定已知使用顺序表存储数据，表长为n，假设在表中的任意位置插入元素的概率相等，则插入一个元素，平均需要移动的元素个数（）。(A)(n-1)/2(B)n/2(C)(n+1)/2(D)不确定在双向链表p所指结点之后插入s所指结点的操作是（）。(A)p?right=s;s?left=p;p?right?left=s;s?right=p?right;(B)p?right=s;p?right?left=s;s?left=p;s?right=p?right;(C)s?left=p;s?right=p?right;p?right=s;p?right?left=s;(D)s?left=p;s?right=p?right;p?right?left=s;p?right=s;字符串相等的充分必要条件是（）。(A)串长度相等(B)串使用相同的存储结构(C)串相同位置对应的字符相等(D)A和C将一个递归算法改为对应的非递归算法时，通常需要使用（）。(A)数组 (B)栈 (C)队列 (D)二叉树一个栈的入栈序列1,2,3,4,5,则栈的不可能的输出序列是（）。(A)12345(B)54321(C)32514(D)12354设循环队列中数组的下标范围是1~n，其头尾指针分别为f和r，则其元素个数为（）。(A)r-f(B)r-f+1(C)(r-f)modn+1(D)(r-f+n)modn某二叉树的前序遍历结点访问顺序是ABDEFCGH,中序遍历的结点访问顺序是DBFEAGHC,则其后序遍历的结点访问顺序是（）。(A)DFEBHCGA(B)DFEBHGCA(C)DEFBHGCA(D)DFEHBGCA正则二叉树是只有度为0和2的结点的二叉树，已知正则二叉树的叶子结点个数为n，则该二叉树总得结点数为（）。(A)n+1(B)2*n(C)2*n+1(D)2*n-1下面关于排序的说法错误的是（）。(A)快速排序、归并排序都是一种不稳定的排序方法(B)直接插入排序和折半插入排序移动元素的次数相同(C)简单选择排序移动元素的次数最少(D)根据排序需要的平均时间，快速排序是目前最好的一种内部排序方法折半查找有序表（3，4，5，10，13，14，20，30），若查找元素3，则被比较的元素依次为（）。(A)10,20,30(B)10,14,30(C)13,3(D)10,4,3下面关于栈和队列的说法正确的是（）。(A)栈是先进先出的线性表，队列是后进先出的线性表(B)栈是先进先出的线性表，队列也是先进先出的线性表(C)栈是后进先出的线性表，队列是先进先出的线性表(D)栈是后进先出的线性表，队列也是后进先出的线性表两个各有n个元素的有序列表并成一个有序表，其最少的比较次数是（）。

(A)n(B)2n-1(C)2n(D)n-1设循环队列中数组的下标范围是0~n-1，f表示队首元素的前驱位置，r表示队尾元素的位置，则队列中元素个数为（）。

(A)r-f(B)r-f1(C)(r-f1)modn(D)(r-fn)modn一个5行6列的二维数组s采用从最后一行开始，每一行的元素从右至左的方式映射到一维数组a中，s和a的下标均从0开始，则s[3][3]在a中的下标是（）。

(A)7(B)8(C)9(D)10设只含根结点的二叉树的高度为1，则高度为n的二叉树中所含叶子结点的个数最多为（）个。

(A)2n(B)n(C)2n-1(D)2n-1设高度为h的二叉树上只有度为0和度为2的结点，则此二叉树中所包含的结点数至少为（）个（设只含根结点的二叉树的高度为1）。

(A)2h(B)2h-1(C)2h+1(D)h+1对一棵二叉检索树进行（）得到的结点序列是一个有序序列。

(A)前序周游(B)中序周游(C)后序周游(D)层次周游一棵前序序列为1，2，3，4的二叉树，其中序序列不可能是（）。

(A)4,1,2,3(B)4,3,2,1(C)2,4,3,1(D)3,4,2,1在含n个顶点和e条边的有向图的邻接矩阵中，零元素的个数为（）。

(A)e(B)2e(C)n2-e(D)n2-2e具有n个顶点和e条边的图的深度优先搜索算法的时间复杂度为（）。(A)O(n)(B)O(n3)(C)O(n2)(D)O(ne)如果具有n个顶点的图是一个环，则它有（）棵生成树。

(A)n(B)nl(C)n-l(D)2n堆排序算法在平均情况下的时间复杂度为（）。(A)O(n)(B)O(nlogn)(C)O(n2)(D)O(logn)在待排序数据已基本有序的前提下，下述排序方法中效率最高的是（）。(A)直接插入排序(B)直接选择排序(C)快速排序(D)归并排序在理想情况下，散列表中查找元素所需的比较次数为（）。

(A)n(B)O(C)n／2(D)1在一棵m阶B树中，若在某结点中插入一个新关键字而引起该结点分裂，则此结点中原有的关键字的个数是（）。

(A)m(B)m+1(C)m-l(D)m／2设顺序循环队列Q[0：M-1]的头指针和尾指针分别为F和R，头指针F总是指向队头元素的前一位置，尾指针R总是指向队尾元素的当前位置，则该循环队列中的元素个数为（C）。 (A)R-F (B)F-R (C)(R-F+M)％M (D)(F-R+M)％M设某棵二叉树的中序遍历序列为ABCD，前序遍历序列为CABD，则后序遍历该二叉树得到序列为（A）。 (A)BADC (B)BCDA (C)CDAB (D)CBDA设某完全无向图中有n个顶点，则该完全无向图中有（A）条边。 (A)n(n-1)/2 (B)n(n-1) (C)n2 (D)n2-1设某棵二叉树中有2000个结点，则该二叉树的最小高度为（C）。 (A)9 (B)10 (C)11 (D)12设某有向图中有n个顶点，则该有向图对应的邻接表中有（B）个表头结点。 (A)n-1 (B)n (C)n+1 (D)2n-1设一组初始记录关键字序列(5，2，6，3，8)，以第一个记录关键字5为基准进行一趟快速排序的结果为（C）。 (A)2，3，5，8，6 (B)3，2，5，8，6 (C)3，2，5，6，8 (D)2，3，6，5，8设某数据结构的二元组形式表示为A=(D，R)，D={01，02，03，04，05，06，07，08，09}，R={r}，r={<01，02>，<01，03>，<01，04>，<02，05>，<02，06>，<03，07>，<03，08>，<03，09>}，则数据结构A是（B）。 (A)线性结构 (B)树型结构 (C)物理结构 (D)图型结构下面程序的时间复杂为（B）for（i=1，s=0；i<=n；i++）{t=1；for(j=1；j<=i；j++)t=t*j；s=s+t；} (A)O(n) (B)O(n2) (C)O(n3) (D)O(n4)设指针变量p指向单链表中结点A，若删除单链表中结点A，则需要修改指针的操作序列为（A）。 (A)q=p->next；p->data=q->data；p->next=q->next；free(q)；(B)q=p->next；q->data=p->data；p->next=q->next；free(q)； (C)q=p->next；p->next=q->next；free(q)； (D)q=p->next；p->data=q->data；free(q)；设有n个待排序的记录关键字，则在堆排序中需要（A）个辅助记录单元。 (A)1 (B)n (C)nlog2n (D)n2设一组初始关键字记录关键字为(20，15，14，18，21，36，40，10)，则以20为基准记录的一趟快速排序结束后的结果为（A）。(A)10，15，14，18，20，36，40，21 (B)10，15，14，18，20，40，36，21 (C)10，15，14，20，18，40，36，2l (D)15，10，14，18，20，36，40，21设二叉排序树中有n个结点，则在二叉排序树的平均平均查找长度为（B）。 (A)O(1) (B)O(log2n) (C)log2n (D)O(n2)设无向图G中有n个顶点e条边，则其对应的邻接表中的表头结点和表结点的个数分别为（D）。 (A)n，e (B)e，n (C)2n，e (D)n，2e设某强连通图中有n个顶点，则该强连通图中至少有（C）条边。 (A)n(n-1) (B)n+1 (C)n (D)n(n+1)设有5000个待排序的记录关键字，如果需要用最快的方法选出其中最小的10个记录关键字，则用下列（B）方法可以达到此目的。 (A)快速排序 (B)堆排序 (C)归并排序 (D)插入排序下列四种排序中（D）的空间复杂度最大。 (A)插入排序 (B)冒泡排序 (C)堆排序 (D)归并排序设一维数组中有n个数组元素，则读取第i个数组元素的平均时间复杂度为（C）。 (A)O(n) (B)O(nlog2n) (C)O(1) (D)O(n2)设一棵二叉树的深度为k，则该二叉树中最多有（D）个结点。 (A)2k-1 (B)2k (C)2k-1 (D)2k-1设某无向图中有n个顶点e条边，则该无向图中所有顶点的入度之和为（D）。 (A)n (B)e (C)2n (D)2e在二叉排序树中插入一个结点的时间复杂度为（B）。 (A)O(1) (B)O(n) (C)O(log2n) (D)O(n2)设某有向图的邻接表中有n个表头结点和m个表结点，则该图中有（C）条有向边。 (A)n (B)n-1 (C)m (D)m-1设一组初始记录关键字序列为(345，253，674，924，627)，则用基数排序需要进行（A）趟的分配和回收才能使得初始关键字序列变成有序序列。 (A)3 (B)4 (C)5 (D)8设用链表作为栈的存储结构则退栈操作（B）。 (A)必须判别栈是否为满 (B)必须判别栈是否为空 (C)判别栈元素的类型 (D)对栈不作任何判别下列四种排序中（A）的空间复杂度最大。 (A)快速排序 (B)冒泡排序 (C)希尔排序 (D)堆设某二叉树中度数为0的结点数为N0，度数为1的结点数为Nl，度数为2的结点数为N2，则下列等式成立的是（C）。 (A)N0=N1+1 (B)N0=Nl+N2 (C)N0=N2+1 (D)N0=2N1+l设有序顺序表中有n个数据元素，则利用二分查找法查找数据元素X的最多比较次数不超过（A）。 (A)log2n+1 (B)log2n-1 (C)log2n (D)log2(n+1)数据的最小单位是（A）。 (A)数据项 (B)数据类型 (C)数据元素 (D)数据变量设一组初始记录关键字序列为(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设一组初始记录关键字序列为(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设一个有序的单链表中有n个结点，现要求插入一个新结点后使得单链表仍然保持有序，则该操作的时间复杂度为（D）。 (A)O(log2n) (B)O(1) (C)O(n2) (D)O(n)设一棵m叉树中度数为0的结点数为N0，度数为1的结点数为Nl，……，度数为m的结点数为Nm，则N0=（B）。(A)Nl+N2+……+Nm(B)l+N2+2N3+3N4+……+(m-1)Nm(C)N2+2N3+3N4+……+(m-1)Nm(D)2Nl+3N2+……+(m+1)Nm设有序表中有1000个元素，则用二分查找查找元素X最多需要比较（B）次。 (A)25 (B)10 (C)7 (D)1设连通图G中的边集E={(a，b)，(a，e)，(a，c)，(b，e)，(e，d)，(d，f)，(f，c)}，则从顶点a出发可以得到一种深度优先遍历的顶点序列为（B）。 (A)abedfc (B)acfebd (C)aebdfc (D)aedfcb设输入序列是1、2、3、……、n，经过栈的作用后输出序列的第一个元素是n，则输出序列中第i个输出元素是（C）。 (A)n-i (B)n-1-i (C)n+1-i (D)不能确定设一组初始记录关键字序列为(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设一组权值集合W={2，3，4，5，6}，则由该权值集合构造的哈夫曼树中带权路径长度之和为（D）。 (A)20 (B)30 (C)40 (D)45执行一趟快速排序能够得到的序列是（A）。 (A)[41，12，34，45，27]55[72，63] (B)[45，34，12，41]55[72，63，27] (C)[63，12，34，45，27]55[41，72] (D)[12，27，45，41]55[34，63，72]设一条单链表的头指针变量为head且该链表没有头结点，则其判空条件是（A）。(A)head==0 (B)head->next==0(C)head->next==head (D)head!=0时间复杂度不受数据初始状态影响而恒为O(nlog2n)的是（A）。 (A)堆排序 (B)冒泡排序 (C)希尔排序 (D)快速排序设二叉树的先序遍历序列和后序遍历序列正好相反，则该二叉树满足的条件是（D）。 (A)空或只有一个结点 (B)高度等于其结点数 (C)任一结点无左孩子 (D)任一结点无右孩子一趟排序结束后不一定能够选出一个元素放在其最终位置上的是（D）。 (A)堆排序 (B)冒泡排序 (C)快速排序 (D)希尔排序设某棵三叉树中有40个结点，则该三叉树的最小高度为（B）。 (A)3 (B)4 (C)5 (D)6顺序查找不论在顺序线性表中还是在链式线性表中的时间复杂度为（A）。 (A)O(n) (B)O(n2) (C)O(n1/2) (D)O(1og2n)二路归并排序的时间复杂度为（C）。 (A)O(n) (B)O(n2) (C)O(nlog2n) (D)O(log2n)深度为k的完全二叉树中最少有（B）个结点。 (A)2k-1-1 (B)2k-1 (C)2k-1+1 (D)2k-1设指针变量front表示链式队列的队头指针，指针变量rear表示链式队列的队尾指针，指针变量s指向将要入队列的结点X，则入队列的操作序列为（C）。 (A)front->next=s；front=s； (B)s->next=rear；rear=s； (C)rear->next=s；rear=s； (D)s->next=front；front=s；设某无向图中有n个顶点e条边，则建立该图邻接表的时间复杂度为（A）。 (A)O(n+e) (B)O(n2) (C)O(ne) (D)O(n3)设某哈夫曼树中有199个结点，则该哈夫曼树中有（B）个叶子结点。 (A)99 (B)100 (C)101 (D)102设二叉排序树上有n个结点，则在二叉排序树上查找结点的平均时间复杂度为（D）。 (A)O(n) (B)O(n2) (C)O(nlog2n) (D)O(log2n)设用邻接矩阵A表示有向图G的存储结构，则有向图G中顶点i的入度为（B）。 (A)第i行非0元素的个数之和 (B)第i列非0元素的个数之和 (C)第i行0元素的个数之和 (D)第i列0元素的个数之和设某无向图有n个顶点，则该无向图的邻接表中有（B）个表头结点。 (A)2n (B)n (C)n/2 (D)n(n-1)设无向图G中有n个顶点，则该无向图的最小生成树上有（B）条边。 (A)n (B)n-1 (C)2n (D)2n-1设一组初始记录关键字序列为(60，80，55，40，42，85)，则以第一个关键字45为基准而得到的一趟快速排序结果是（C）。 (A)40，42，60，55，80，85 (B)42，45，55，60，85，80 (C)42，40，55，60，80，85 (D)42，40，60，85，55，80（B）二叉排序树可以得到一个从小到大的有序序列。 (A)先序遍历 (B)中序遍历 (C)后序遍历 (D)层次遍历设按照从上到下、从左到右的顺序从1开始对完全二叉树进行顺序编号，则编号为i结点的左孩子结点的编号为（B）。 (A)2i+1 (B)2i (C)i/2 (D)2i-1程序段s=i=0；do{i=i+1；s=s+i；}while(i<=n)；的时间复杂度为（A）。 (A)O(n) (B)O(nlog2n) (C)O(n2) (D)O(n3/2)设带有头结点的单向循环链表的头指针变量为head，则其判空条件是（C）。 (A)head==0 (B)head->next==0 (C)head->next==head (D)head!=0设某棵二叉树的高度为10，则该二叉树上叶子结点最多有（C）。 (A)20 (B)256 (C)512 (D)1024设一组初始记录关键字序列为(13，18，24，35，47，50，62，83，90，115，134),则利用二分法查找关键字90需要比较的关键字个数为（B）。 (A)1 (B)2 (C)3 (D)4设指针变量top指向当前链式栈的栈顶，则删除栈顶元素的操作序列为（D）。 (A)top=top+1; (B)top=top-1; (C)top->next=top; (D)top=top->next;建立一个长度为n的有序单链表的时间复杂度为（C） (A)O(n) (B)O(1) (C)O(n2) (D)O(log2n)设某散列表的长度为100，散列函数H(k)=k%P，则P通常情况下最好选择（B）。 (A)99 (B)97 (C)91 (D)93在二叉排序树中插入一个关键字值的平均时间复杂度为（B）。 (A)O(n) (B)O(log2n) (C)O(log2n) (D)O(n2)设一个顺序有序表A[1:14]中有14个元素，则采用二分法查找元素A[4]的过程中比较元素的顺序为(C)。 (A)A[1]，A[2]，A[3]，A[4] (B)A[1]，A[14]，A[7]，A[4] (C)A[7]，A[3]，A[5]，A[4] (D)A[7]，A[5]，A[3]，A[4]设一棵完全二叉树中有65个结点，则该完全二叉树的深度为（B）。 (A)8 (B)7 (C)6 (D)5设一棵三叉树中有2个度数为1的结点，2个度数为2的结点，2个度数为3的结点，则该三叉链权中有（C）个度数为0的结点。 (A)5 (B)6 (C)7 (D)8设无向图G中的边的集合E={(a，b)，(a，e)，(a，c)，(b，e)，(e，d)，(d，f)，(f，c)}，则从顶点a出发进行深度优先遍历可以得到的一种顶点序列为（A）。 (A)aedfcb (B)acfebd (C)aebcfd (D)aedfbc下列程序段的时间复杂度为（A）。for(i=0；i<m；i++)for(j=0；j<t；j++)c[i][j]=0；for(i=0；i<m；i++)for(j=0；j<t；j++)for(k=0；k<n；k++)c[i][j]=c[i][j]+a[i][k]*b[k][j]； (A)O(m*n*t) (B)O(m+n+t) (C)O(m+n*t) (D)O(m*t+n)设顺序线性表中有n个数据元素，则删除表中第i个元素需要移动（A）个元素。 (A)n-i (B)n+l-i (C)n-1-i (D)i设F是由T1、T2和T3三棵树组成的森林，与F对应的二叉树为B，T1、T2和T3的结点数分别为N1、N2和N3，则二叉树B的根结点的左子树的结点数为（A）。(A)N1-1 (B)N2-1(C)N2+N3 (D)N1+N3利用直接插入排序法的思想建立一个有序线性表的时间复杂度为（C）。(A)O(n) (B)O(nlog2n) (C)O(n2) (D)O(log2n)设指针变量p指向双向链表中结点A，指针变量s指向被插入的结点X，则在结点A的后面插入结点X的操作序列为（D）。 (A)p->right=s；s->left=p；p->right->left=s；s->right=p->right； (B)s->left=p；s->right=p->right；p->right=s；p->right->left=s； (C)p->right=s；p->right->left=s；s->left=p；s->right=p->right； (D)s->left=p；s->right=p->right；p->right->left=s；p->right=s；下列各种排序算法中平均时间复杂度为O(n2)是（D）。 (A)快速排序 (B)堆排序 (C)归并排序 (D)冒泡排序设输入序列1、2、3、…、n经过栈作用后，输出序列中的第一个元素是n，则输出序列中的第i个输出元素是（C）。 (A)n-i (B)n-1-i (C)n+l-i (D)不能确定设散列表中有m个存储单元，散列函数H(key)=key%p，则p最好选择（B）。 (A)小于等于m的最大奇数 (B)小于等于m的最大素数 (C)小于等于m的最大偶数 (D)小于等于m的最大合数设在一棵度数为3的树中，度数为3的结点数有2个，度数为2的结点数有1个，度数为1的结点数有2个，那么度数为0的结点数有（C）个。 (A)4 (B)5 (C)6 (D)7设完全无向图中有n个顶点，则该完全无向图中有（A）条边。(A)n(n-1)/2 (B)n(n-1) (C)n(n+1)/2 (D)(n-1)/2设顺序表的长度为n，则顺序查找的平均比较次数为（C）。 (A)n (B)n/2 (C)(n+1)/2 (D)(n-1)/2设有序表中的元素为(13，18，24，35，47，50，62)，则在其中利用二分法查找值为24的元素需要经过（C）次比较。 (A)1 (B)2 (C)3 (D)4设顺序线性表的长度为30，分成5块，每块6个元素，如果采用分块查找，则其平均查找长度为（D）。 (A)6 (B)11 (C)5 (D)6.5设有向无环图G中的有向边集合E={<1，2>，<2，3>，<3，4>，<1，4>}，则下列属于该有向图G的一种拓扑排序序列的是（A）。 (A)1，2，3，4 (B)2，3，4，1 (C)1，4，2，3 (D)1，2，4，3设有一组初始记录关键字序列为(34，76，45，18，26，54，92)，则由这组记录关键字生成的二叉排序树的深度为（A）。 (A)4 (B)5 (C)6 (D)7下列程序段的时间复杂度为（A）。i=0，s=0；while(s<n){s=s+i；i++；} (A)O(n1/2) (B)O(n1/3) (C)O(n) (D)O(n2)设某链表中最常用的操作是在链表的尾部插入或删除元素，则选用下列（D）存储方式最节省运算时间。 (A)单向链表 (B)单向循环链表(C)双向链表 (D)双向循环链表设指针q指向单链表中结点A，指针p指向单链表中结点A的后继结点B，指针s指向被插入的结点X，则在结点A和结点B插入结点X的操作序列为（B）。(A)s->next=p->next；p->next=-s； (B)q->next=s；s->next=p；(C)p->next=s->next；s->next=p； (D)p->next=s；s->next=q；设输入序列为1、2、3、4、5、6，则通过栈的作用后可以得到的输出序列为（B）。(A)5，3，4，6，1，2 (B)3，2，5，6，4，1(C)3，1，2，5，4，6 (D)1，5，4，6，2，3设有一个10阶的下三角矩阵A（包括对角线），按照从上到下、从左到右的顺序存储到连续的55个存储单元中，每个数组元素占1个字节的存储空间，则A[5][4]地址与A[0][0]的地址之差为（B）。 (A)10 (B)19 (C)28 (D)55设一棵m叉树中有N1个度数为1的结点，N2个度数为2的结点，……，Nm个度数为m的结点，则该树中共有（D）个叶子结点。 (A) (B) (C) (D)二叉排序树中左子树上所有结点的值均（A）根结点的值。 (A)< (B)> (C)= (D)!=设一组权值集合W=(15，3，14，2，6，9，16，17)，要求根据这些权值集合构造一棵哈夫曼树，则这棵哈夫曼树的带权路径长度为（D）。 (A)129 (B)219 (C)189 (D)229设有n个关键字具有相同的Hash函数值，则用线性探测法把这n个关键字映射到HASH表中需要做（D）次线性探测。 (A)n2 (B)n(n+1) (C)n(n+1)/2 (D)n(n-1)/2设某棵二叉树中只有度数为0和度数为2的结点且度数为0的结点数为n，则这棵二叉中共有（C）个结点。 (A)2n (B)n+l (C)2n-1 (D)2n+l设一组初始记录关键字的长度为8，则最多经过（B）趟插入排序可以得到有序序列。 (A)6 (B)7 (C)8 (D)9设一组初始记录关键字序列为(Q，H，C，Y，P，A，M，S，R，D，F，X)，则按字母升序的第一趟冒泡排序结束后的结果是（D）。(A)F，H，C，D，P，A，M，Q，R，S，Y，X(B)P，A，C，S，Q，D，F，X，R，H，M，Y(C)A，D，C，R，F，Q，M，S，Y，P，H，X(D)H，C，Q，P，A，M，S，R，D，F，X，Y设有一个二维数组A[m][n]，假设A[0][0]存放位置在644(10)，A[2][2]存放位置在676(10)，每个元素占一个空间，问A[3][3](10)存放在什么位置？脚注(10)表示用10进制表示。（C）(A)688(B)678(C)692(D)696若有18个元素的有序表存放在一维数组A[19]中，第一个元素放A[1]中，现进行二分查找，则查找A［3］的比较序列的下标依次为（D）。(A)1，2，3 (B)9，5，2，3(C)9，5，3 (D)9，4，2，3对n个记录的文件进行快速排序，所需要的辅助存储空间大致为（C）。(A)O（1）(B)O（n）(C)O（1og2n）(D)O（n2）对于线性表（7，34，55，25，64，46，20，10）进行散列存储时，若选用H（K）=K%9作为散列函数，则散列地址为1的元素有（D）个。(A)1(B)2(C)3(D)4设有6个结点的无向图，该图至少应有（A）条边才能确保是一个连通图。(A)5(B)6(C)7(D)8设哈夫曼树中的叶子结点总数为m，若用二叉链表作为存储结构，则该哈夫曼树中总共有（B）个空指针域。 (A)2m-1 (B)2m (C)2m+1 (D)4m二、判断题数据项是数据的最小单位。（）链表的每个结点都恰好有一个指针。（）同一组不重复输入序列执行不同的入栈出栈组合操作，所得结果也可能相同。（）改进的KMP算法中，字符串”abaaaba”的nextval数组值是0101110。（）用六叉链表表示30个结点的六叉树，则树中共有151个空指针。（）数组是一种线性结构，因此只能用来存储线性表。（）若有向图不存在回路，即使不用访问标志位同一结点也不会被访问两次。（）若装填因子a为1，则向散列表中散列元素时一定会产生冲突。（）若把堆看成是一个完全二叉树，则该树一定是一棵排序二叉树。（）外排中使用置换选择排序的目的，是为了增加初始归并段的长度。（）抽象数据类型与计算机内部表示和实现无关。（Y）线性表的插入和删除总是伴随着大量数据的移动。（N）队列在程序调用是必不可少，因此递归离不开队列。（N）字符串’aababaaaba’(Y)二叉树中有双子女的父结点，在中序遍历中后继一定是其中一个子女结点。（N）不用递归就不能实现二叉树的前序遍历。（N）若有向图有n个顶点，则其强连通分量最多有n个。(Y)平衡二叉树一定是一棵完全二叉树。（N）若某内部排序算法不稳定，则该算法没有使用价值。（N）倒排文件的目的是为了多关键字查找。(Y)已知指针curr指向链表中的某结点，执行语句curr=curr->next；不会删除该链表中的结点。()若二叉树的叶结点数为1，则其高度等于结点数(仅含根结点的二叉树高度为1)。（）按中序周游二叉树时，某个结点的直接后继是它的右子树中第一个被访问的结点。()完全二叉树的某结点若无左孩子，则它必是叶结点。()向二叉检索树中插入一个新结点，需要比较的次数不可能大于此二叉树的高度。()对一个堆按层次周游，一定能得到一个有序序列。()一棵树中的叶子结点数一定等于其对应的二叉树中的叶子结点数。()将一棵树转换为二叉树表示后，该二叉树的根结点没有右子树。()任何有向图的结点都可以排成拓扑序列，而且拓扑序列不唯一。()快速排序在最差情况下的时间复杂度是0(n2)，此时它的性能并不比冒泡排序更好。()AVL树的任何子树都是AVL树。（Y）用相邻矩阵表示图所用的存储空间大小与图的边数成正比。（N）霍夫曼树一定是满二叉树。（Y）栈是一种线性结构。（Y）B＋树既适于随机检索，也适于顺序检索。（N）记录是数据处理的最小单位。（）数据的逻辑结构是指数据的各数据项之间的逻辑关系。()算法的优劣与算法描述语言无关，但与所用计算机有关。（）健壮的算法不会因非法的输入数据而出现莫名其妙的状态。(Y)算法可以用不同的语言描述，如果用C语言或PASCAL语言等高级语言来描述，则算法实际上就是程序了。（）数据的物理结构是指数据在计算机内的实际存储形式。(Y)数据结构的抽象操作的定义与具体实现有关。（）在顺序存储结构中，有时也存储数据结构中元素之间的关系。（）顺序存储方式的优点是存储密度大，且插入、删除运算效率高。（）数据结构的基本操作的设置的最重要的准则是，实现应用程序与存储结构的独立。(Y)数据的逻辑结构说明数据元素之间的顺序关系,它依赖于计算机的储存结构.（）数据结构概念包括数据之间的逻辑结构，数据在计算机中的存储方式和数据的运算三个方面。(Y)线性表中的每个结点最多只有一个前驱和一个后继。(Y)线性的数据结构可以顺序存储，也可以链接存储。非线性的数据结构只能链接存储。()栈和队列逻辑上都是线性表。(Y)单链表从任何一个结点出发，都能访问到所有结点。()设串S的长度为n,则S的子串个数为n(n+1)/2。(Y)一般树和二叉树的结点数目都可以为0。(Y)（101，88，46，70，34，39，45，58，66，10）是堆。......(Y)将一棵树转换成二叉树后，根结点没有左子树。()用树的前序遍历和中序遍历可以导出树的后序遍历。(Y)即使对不含相同元素的同一输入序列进行两组不同的、合法的入栈和出栈组合操作，所得的输出序列也一定相同。()哈夫曼树是带权路径长度最短的树，路径上权值较大的结点离很较近。(Y)数据的基本单位是数据项。()带权的无向连通图的最小生成树是唯一的。()数组元素之间的关系，既不是线性的，也不是树形的。()对于有n个对象的待排序序列进行归并排序，所需平均时间为O（nlog2n）。(Y)用邻接矩阵法存储一个图所需的存储单元数目与图的边数有关。(Y)在霍夫曼编码中，当两个字符出现的频率相同时，其编码也相同，对于这种情况应当特殊处理。()线性表采用顺序存储表示时，必须占用一片连续的存储单元。(Y)由树转化成二叉树，其根的右子女指针总是空的。(Y)直接选择排序是一种稳定的排序方法。()装载因子是散列表的一个重要参数，它反映了散列表的装满程度。(Y)若一个栈的输入序列为123…n，其输出序列的第一个元素为n，则其输出序列的每个元素ai一定满足ai=n-i+1。(i=1,2,...,n)（Y）二叉树中的叶子结点就是二叉树中没有左右子树的结点。（N）一棵树中的叶子结点数一定等于与其对应的二叉树中的叶子结点数。（N）删除二叉排序树中的一个结点，再重新插入上去，一定能得到原来的二叉排序树。（N）线性表就是顺序表。（N）若一棵树中某结点的度为1，则该结点仅有一棵子树。（Y）所谓平衡二叉树是指左右子树的高度差的绝对值不大于1的二叉树。（N）AOE网所表示的工程至少所需的时间等于从源点到汇点的最短路径的长度。（N）若某二叉树的叶子结点数为1，则其先序序列和后序序列一定相反。（Y）在采用线性探测法处理冲突的散列表中，所有的同义词在表中相邻。（N）对B-树中任一非叶子结点中的某关键字K，比K小的最大关键字和比K大的最小关键字一定都在非叶结点的最下层。（Y）若一个连通无向图的以顶点1为起点的深度遍历序列唯一，则可唯一确定该图。（Y）若一个有向图的以顶点1为起点的深度遍历序列唯一，则可唯一确定该图。（N）在数据表基本有序时，冒泡排序算法的时间复杂度一定接近O(n)。（N）设指针p指向单链表中的一个结点，则语句序列u:=p^.next;u:=u^.next将删除一个结点。（N）线性表的长度是线性表所占用的存储空间的大小。（N）双循环链表中，任意一结点的后继指针均指向其逻辑后继。（N）在对链队列做出队操作时，不会改变front指针的值。（N）如果两个串含有相同的字符，则说它们相等。（N）如果二叉树中某结点的度为1，则说该结点只有一棵子树。（Y）已知一棵树的先序序列和后序序列，一定能构造出该树。（N）图G的一棵最小代价生成树的代价未必小于G的其它任何一棵生成树的代价。（Y）图G的拓扑序列唯一，则其弧数必为n-1（其中n为顶点数）。（N）9.对一个堆按层次遍历，不一定能得到一个有序序列。（Y）10.直接选择排序算法满足：其时间复杂度不受数据的初始特性影响，为O(n2)。（Y）如果两个串含有相同的字符，则这两个串相等。（N）数组可以看成线性结构的一种推广，因此可以对它进行插入、删除等运算。（N）在索引顺序表上实现分块查找，在等概率查找情况下，其平均查找长度不仅与表中元素个数有关，而且与每一块中元素个数有关。（Y）在顺序表中取出第i个元素所花费的时间与i成正比。（N）在栈满情况下不能作进栈运算，否则产生“上溢”。(Y）二路归并排序的核心操作是将两上有序序列归并为一个有序序列。（Y）对任意一个图，从它的某个顶点出发，进行一次深度优先或广度优先搜索，即可访问图的每个顶点.（N）二叉排序树或者是一棵空二叉树，或者是具有下列性质的二叉树：若它的左子树非空，则根结点的值大于其左孩子的值;若它的右子树非空，则根结点的值小于其右孩子的值。（N）在执行某个排序算法过程中，出现了排序码朝着最终排序序列位置相反方向移动，则该算法是不稳定的。（N）一个有向图的邻接表和逆邻接表中表结点的个数一定相等。（Y）算法与程序的主要区别是算法满足有穷性??并且算法不一定用机器可执行的程序设计语言书写。（Y）某线性表采用顺序存储结构??元素长度为4??首地址为100??则下标为12的??第13个??元素的存储地址为148。（Y）在任何一种线性链表上都无法进行随机访问。（N）顺序栈是一种规定了元素进栈顺序的栈。（N）循环列表中每一个元素都有后继。（Y）树的先根遍历与该树对应二叉树的前序遍历结果不同。（N）任何有向网络??AOV网络??拓扑排序的结果是唯一的。（N）无向图中的连通分量定义为无向图的极大连通子图。（Y）删除一个二叉树中的一个结点??再重新插入上去??一定能得到原来的二叉排序树。（N）数据结构包括数据间的逻辑结构??数据的存储方式和数据的运算三个方面的内容。（Y）在动态单向链表中??每个结点总是占用一片连续的内存空间。（N）高级语言中通常利用“递归工作栈”来处理递归。（Y）中缀表示式??a+b??*(c+d)的后缀形式为ab+cd+*。（Y）栈和队列都不适合用散列存储法存储。（N）广义表的深度与广义表中含有多少个子表元素有关。（Y）如果树用二叉树链表表示??则判断某个结点是不是树叶的条件是该结点左??右两个指针域的值都为空。（Y）一组关键码已完全有序时??最快的排序方法是快速排序。（Y）n个结点的无向图最多有n*(n-1)/2条边。（Y）线性结构中的结点按前驱??后继关系可以排成一个线性序列。（Y）在动态单向链表中??每个结点总是占用一片连续的内存空间。（N）算法的有穷性是指一个算法无论在什么情况下都应在执行有穷步后结束。（Y）后缀表达式ABC+*的中缀形式为A*??B+C??。（Y）对顺序栈进行插入??删除操作??不涉及元素的前后移动问题。（N）广义表的长度是广义表中元素的个数。（Y）在任何一棵完全二叉树中??叶结点的个数或者和分支结点一样多，或者只比分支结点多一个。（Y）直接选择排序是一种稳定的排序方法。（N）n个顶点的生成树中有n-1条边。（Y）有向图的邻接表和逆邻接表中表结点的个数不一定相等。(错)对链表进行插入和删除操作时不必移动链表中结点。(对)子串“ABC”在主串“AABCABCD”中的位置为2。(对)若一个叶子结点是某二叉树的中序遍历序列的最后一个结点，则它必是该二叉树的先序遍历序列中的最后一个结点。(对)希尔排序算法的时间复杂度为O(n2)。(错)用邻接矩阵作为图的存储结构时，则其所占用的存储空间与图中顶点数无关而与图中边数有关。(错)中序遍历一棵二叉排序树可以得到一个有序的序列。(对)入栈操作和入队列操作在链式存储结构上实现时不需要考虑栈溢出的情况。(对)顺序表查找指的是在顺序存储结构上进行查找。（错）堆是完全二叉树，完全二叉树不一定是堆。（对）调用一次深度优先遍历可以访问到图中的所有顶点。（错）分块查找的平均查找长度不仅与索引表的长度有关，而且与块的长度有关。（对）冒泡排序在初始关键字序列为逆序的情况下执行的交换次数最多。（对）满二叉树一定是完全二叉树，完全二叉树不一定是满二叉树。（对）设一棵二叉树的先序序列和后序序列，则能够唯一确定出该二叉树的形状。（错）层次遍历初始堆可以得到一个有序的序列。（错）设一棵树T可以转化成二叉树BT，则二叉树BT中一定没有右子树。（对）线性表的顺序存储结构比链式存储结构更好。（错）中序遍历二叉排序树可以得到一个有序的序列。（对）快速排序是排序算法中平均性能最好的一种排序。（对）不论是入队列操作还是入栈操作，在顺序存储结构上都需要考虑“溢出”情况。（对）当向二叉排序树中插入一个结点，则该结点一定成为叶子结点。（对）设某堆中有n个结点，则在该堆中插入一个新结点的时间复杂度为O(log2n)。（对）完全二叉树中的叶子结点只可能在最后两层中出现。（对）哈夫曼树中没有度数为1的结点。（对）对连通图进行深度优先遍历可以访问到该图中的所有顶点。（对）先序遍历一棵二叉排序树得到的结点序列不一定是有序的序列。（对）由树转化成二叉树，该二叉树的右子树不一定为空。（错）线性表中的所有元素都有一个前驱元素和后继元素。（错）带权无向图的最小生成树是唯一的。（错）如果两个关键字的值不等但哈希函数值相等，则称这两个关键字为同义词。（对）设初始记录关键字基本有序，则快速排序算法的时间复杂度为O(nlog2n)。（错）分块查找的基本思想是首先在索引表中进行查找，以便确定给定的关键字可能存在的块号，然后再在相应的块内进行顺序查找。（对）二维数组和多维数组均不是特殊的线性结构。（错）向二叉排序树中插入一个结点需要比较的次数可能大于该二叉树的高度。（错）如果某个有向图的邻接表中第i条单链表为空，则第i个顶点的出度为零。（对）非空的双向循环链表中任何结点的前驱指针均不为空。（对）不论线性表采用顺序存储结构还是链式存储结构，删除值为X的结点的时间复杂度均为O(n)。（对）图的深度优先遍历算法中需要设置一个标志数组，以便区分图中的每个顶点是否被访问过。（对）稀疏矩阵的压缩存储可以用一个