一、单项选择题
1．下列说法正确的是 （ ）
A）数据是数据元素的基本单位 B）数据元素是数据项中不可分割的最小标识单位 C）数据可由若干个数据元素构成 D）数据项可由若干个数据元素构成 2．数据的基本单位是 （ ）
A）数据项 B）数据类型 C）数据元素 D）数据变量 3．数据元素及其关系在计算机存储器内的表示，称为数据的 （ ） A）逻辑结构 B）存储结构 C）线性结构 D）非线性结构 4．数据的存储结构是指 （ ）
A）数据所占的存储空间量 B）数据的逻辑结构在计算机中的表示 C）数据在计算机中的顺序存储方式 D）存储在外存中的数据
5．根据数据元素的关键字直接计算出该元素存储地址的存储方法是 （ ） A）顺序存储方法 B）链式存储方法 C）索引存储方法 D）散列存储方法 6．算法的时间复杂度是指 （ ）
A）执行算法程序所需要的时间 B）算法程序的长度
C）算法执行过程中所需要的基本运算次数 D）算法程序中的指令条数 7．算法的空间复杂度是指 （ ）
A）算法程序的长度 B）算法程序中的指令条数
C）算法程序所占的存储空间 D）算法执行过程中所需要的存储空间 8．下列程序的时间复杂度为 （ ）
i=0；s=0； while（s 9．以下数据结构中不属于线性数据结构的是 （ ） A）队列 B）线性表 C）二叉树 D）栈 10．下列叙述中正确的是 （ ） A）线性表是线性结构 B）栈与队列是非线性结构 C）线性链表是非线性结构 D）二叉树是线性结构 11．若在长度为n的顺序表中插入一个结点，则其结点的移动次数 （ ） A）最少为0，最多为n B）最少为1，最多为n C）最少为0，最多为n+1 D）最少为1，最多为n+1 12．对于长度为n的顺序表执行删除操作，则其结点的移动次数 （ ） A）最少为0，最多为n B）最少为1，最多为n C）最少为0，最多为n-1 D）最少为1，最多为n-1 13．顺序存储的线性表（a1,a2,?,an），在任一结点前插入一个新结点时所需移动结点的平均次数为 （ ） A）n B）n/2 C）n+1 D）(n+1)/2 14．从一个长度为n的顺序表中删除第i个元素（1≤i≤n）时，需向前移动的元素的个数是 （ ） A）n-i B）n-i+1 C）n-i-1 D）i 15．在以单链表为存储结构的线性表中，数据元素之间的逻辑关系用 （ ） A）数据元素的相邻地址表示 B）数据元素在表中的序号表示 C）指向后继元素的指针表示 D）数据元素的值表示 1 16．在单链表中，增加头结点的目的是 （ ） A）方便运算的实现 B）使单链表至少有一个结点 C）标识表结点中首结点的位置 D）说明单链表是线性表的链式存储实现 17．若某线性表中最常用的操作是在最后一个元素之后插入一个元素和删除第一个元素，则最节省运算时间的存储方式是 （ ） A）单链表 B）仅有头指针的单循环链表 C）双链表 D）仅有尾指针的单循环链表 18．某带头结点的单链表的头指针为head，判定该链表为非空的条件是 （ ） A）head==NULL B）head->next==NULL C）head!=NULL D）head->next!=NULL 19．若不带头结点的单链表的头指针为head，则该链表为空的判定条件是 （ ） A）head==NULL B）head->next==NULL C）head!=NULL D）head->next==head 20．在一个单链表中，若p所指结点不是最后结点，s指向已生成的新结点，则在p之后插入s所指结点的正确操作是 （ ） A）s–>next=p–>next; p–>next=s; B）p–>next=s–>next; s–>next=p; C）s–>next=p; p–>next=s; D）s–>next=p–>next; p=s; 21．在一个单链表中，若p所指结点是q所指结点的前驱结点，则在结点p、q之间插入结点s的正确操作是 （ ） A）s->next=q；p->next=s->next B）p->next=q；p->next=s C）s->next=q->next；p->next=s D）s->next=q->next；p->next=s->next 22．设p指向单链表中的一个结点，s指向待插入的结点，则下述程序段的功能是 （ ） s -> next = p -> next; p -> next = s; t = p -> data; p -> data = s -> data; s ->data = t; A）结点*p与结点*s的数据域互换 B）在p所指结点的元素之前插入元素 C）在p所指结点的元素之后插入元素 D）在结点*p之前插入结点*s 23．非空的单循环链表的头指针为head，尾指针为rear，则下列条件成立的是 （ ） A）rear->next= =head B）rear->next->next= =head C）head->next= =rear D）head->next->next= =rear 24．有关栈的描述，正确的是 （ ） A）栈是一种先进先出的特殊的线性表 B）只能从栈顶执行插入、删除操作 C）只能从栈顶执行插入、栈底执行删除 D）栈顶和栈底均可执行插入、删除操作 25．下列关于队列的叙述中正确的是 （ ） A）在队列中只能插入数据 B）在队列中只能删除数据 C）队列是先进先出的线性表 D）队列是先进后出的线性表 26．若允许表达式内多种括号混合嵌套，则为检查表达式中括号是否正确配对的算法，通常选用的辅助结构是 （ ） A）栈 B）线性表 C）队列 D）二叉排序树 27．若有三个字符的字符串序列执行入栈操作，则其所有可能的输出排列共有 （ ） A）3种 B）4种 C）5种 D）6种 28．若进栈序列为1，2，3，4，5，6，且进栈和出栈可以穿插进行，则可能出现的出栈序列为 （ ） A）3，2，6，1，4，5 B）3，4，2，1，6，5 C）1，2，5，3，4，6 D）5，6，4，2，3，1 29．若进栈序列为1，2，3，4，5，6，且进栈和出栈可以穿插进行，则不可能出现的出栈序列是 （ ） A） 2，4，3，1，5，6 B） 3，2，4，1，6，5 C） 4，3，2，1，5，6 D） 2，3，5，1，6，4 30．已知循环队列的存储空间为数组data[21]，且当前队列的头指针和尾指针的值分别为8 2 和3，则该队列的当前长度为 （ ） A）5 B）6 C）16 D）17 31．循环队列sq中，用数组elem［0··25］存放数据元素，sq.front指示队头元素的前一个位置，sq.rear指示队尾元素的当前位置，设当前sq.front为20，sq.rear为12，则当前队列中的元素个数为 （ ） A）8 B）16 C）17 D）18 32．设数组A[m]为循环队列Q的存储空间，front为队头指针，rear为队尾指针，则判定Q为空队列的条件是 （ ） A）(rear-front)%m= =1 B）front= =rear C）(rear-front)%m= =m-1 D）front= =(rear+1)%m 33．在具有m个单元的循环队列中，队头指针为front，队尾指针为rear，则队满的条件是（ ） A）front==rear B）(front+1)%m==rear C）rear+1==front D）(rear+1)%m==front 34．二维数组A按行优先顺序存储，其中每个元素占1个存储单元。若A［1］［1］的存储地址为420，A［3］［3］的存储地址为446，则A［5］［5］的存储地址为 （ ） A）470 B）471 C）472 D）473 35．二维数组A［5］［6］采用按列为主序的存储方式，每个元素占3个存储单元，若A［0］［0］的存储地址是100，则A［4］［3］的存储地址是 （ ） A）127 B）142 C）150 D）157 36．设有一5阶上三角矩阵A［1..5，1..5］，现将其上三角中的元素按列优先顺序存放在一 维数组B［1..15］中。已知B［1］的地址为100，每个元素占用2个存储单元， 则A［3，4］的地址为 （ ） A）116 B）118 C）120 D）122 37．关于串的叙述中，正确的是 （ ） A）空串是只含有零个字符的串 B）空串是只含有空格字符的串 C）空串是含有零个字符或含有空格字符的串 D）串是含有一个或多个字符的有穷序列 28．串s=″Data Structure″中长度为3的子串的数目是 （ ） A）9 B）11 C）12 D）14 39．执行下列程序段后，串X的值为 （ ） S=〞abcdefgh〞; T=〞xyzw〞; substr (X,S,2,strlen(T)); substr (Y,S, stelen(T),2); strcat (X,Y); A）〞cdefgh〞 B）〞cdxyzw〞 C）〞cdefxy〞 D）〞cdefef〞 40．已知串s=″aabacbabcaccab″，串t1=″abc″,串t2=″cba″,函数index(s,t)的返回值为串t在串s中首次出现的位置，则能求得串″abcacba″的操作序列为 （ ） A）substr (s1,s,6,index(s,t1)); substr (s2,s,index(s,t1),1);strcat(s1,s2); B）substr (s1,s,7,index(s,t1)); substr (s2,s,index(s,t1),1);strcat(s2,s1); C）substr(s1,s,6,index(s,t2)); substr(s2,s,index(s,t2),3);strcat(s1,s2); D）substr(s1,s,6,index(s,t2)); substr(s2,s,index(s,t2),3);strcat(s2,s1); 41．除根结点外，树上每个结点 （ ） A）可有任意多个孩子、任意多个双亲 B）可有任意多个孩子、一个双亲 C）可有一个孩子、任意多个双亲 D）只有一个孩子、一个双亲 42．根据定义，树的叶子结点其度数 （ ） A）必大于 0 B）必等于0 C）必等于1 D）必等于2 43．具有4个结点的二叉树可有 （ ） 3 A）4种形态 B）7种形态 C）10种形态 D）11种形态 44．具有100个结点的二叉树中，若用二叉链表存储，其指针域部分用来指向结点的左、右孩子，指针域为空的个数有 （ ） A）50 个 B）99个 C）100个 D）101个 45．二叉树若采用二叉链表存储，则对于n个结点的二叉树一定有 （ ） A）2n个指针域，其中n个指针为NULL B）2n个指针域，其中n+1个指针为NULL C）2n-1个指针域，其中n个指针为NULL D）2n-1个指针域，其中n+1个指针为NULL 46．含有10个结点的二叉树中，度为0的结点数为4，则度为2的结点数为 （ ） A）3 B）4 C）5 D）6 47．若一棵二叉树有11个叶子结点，则该二叉树中度为2的结点个数是 （ ） A）10 B）11 C）12 D）不确定的 48．除第一层外，满二叉树中每一层结点个数是上一层结点个数的 （ ） A）1/2倍 B）1倍 C）2倍 D）3倍 49．已知一棵完全二叉树有64个叶子结点，则该树可能达到的最大深度为 （ ） A）7 B）8 C）9 D）10 50．在深度为5的满二叉树中，叶子结点的个数为 （ ） A）32 B）31 C）16 D）15 51．一棵有16结点的完全二叉树，对它按层编号，则对编号为7的结点X，它的双亲结点及右孩子结点的编号分别为 （ ） A）2，14 B）2，15 C）3，14 D）3，15 52．假设一棵完全二叉树按层次遍历的顺序依次存放在数组BT[m]中，其中根结点存放在BT[0]，若BT[i]中的结点有左孩子，则左孩子存放在 （ ） A）BT[i/2] B）BT[2*i-1] C）BT[2*i] D）BT[2*i+1] 53．右图所示二叉树的中序序列是 ( ) A）DHEBAFIJCG B）DHEBAFJICG C）DBHEAFCJIG D）DBHEAFJICG 54．对于如图所示二叉树采用中根遍历，正确的遍历序列应为 （ ） A）ABCDEF B）ABECDF C）CDFBEA D）CBDAEF 55．在按层次遍历二叉树的算法中，需要借助的辅助数据结构是 （ ） A）队列 B）栈 C）线性表 D）有序表 56．由m棵结点数为n的树组成的森林，将其转化为一棵二叉树，则该二叉树中根结点的右子树上具有的结点个数是 （ ） A）mn B）mn-1 C）n(m-1) D）m(n-1) 57．在一个无向图中，所有顶点的度数之和等于边数的 （ ） A）1倍 B）2倍 C）3倍 D）4倍 4 58．具有n个顶点的无向图，若要连通全部顶点，至少需要 （ ） A）（n-1）条边 B） n条边 C）n(n-1)条边 D）n(n-1)/2条边 59．在一个具有n个顶点的无向图中，每个顶点度的最大值为 （ ） A）n B）n-1 C）n+1 D）2(n-1) 60．具有10个顶点的有向完全图应具有 （ ） A）20条弧 B）50条弧 C）90条弧 D）100条弧 61．有n个结点的有向完全图的弧数是 （ ） A）n2 B）2n C）n(n-1) D）2n(n+1) 62．关于无向图的邻接矩阵的说法中正确的是 （ ） A）矩阵中非全零元素的行数等于图中的顶点数 B）第i行上与第i列上非零元素总和等于顶点Vi的度数 C）矩阵中的非零元素个数等于图的边数 D）第i行上非零元素个数和第i列上非零元素个数一定相等 63．若用邻接矩阵表示一个有向图，则其中每一列包含的“1”的个数为 （ ） A）图中每个顶点的入度 B）图中每个顶点的出度 C）图中弧的条数 D）图中连通分量的数目 64．对于有向图，其邻接矩阵表示相比邻接表表示更易于进行的操作为 （ ） A）求一个顶点的邻接点 B）求一个顶点的度 C）深度优先遍历 D）广度优先遍历 65．如果某图的邻接矩阵是对角线元素均为零的上三角矩阵，则此图是 （ ） A）有向完全图 B）连通图 C）强连通图 D）有向无环图 66．已知有向图G=(V,E)，其中V={V1,V2,V3,V4,V5,V6,V7}， E={ A)V1,V3,V4,V6,V2,V5,V7 B）V1,V3,V2,V6,V4,V5,V7 C）V1,V3,V4,V5,V2,V6,V7 D）V1,V2,V5,V3,V4,V6,V7 67. 在有向图G的拓扑序列中，若顶点Vi在顶点Vj之前，则下列情形不可能出现的是（ ） A）G中有弧 A）连通分量是无向图中的极小连通子图。 B）强连通分量是有向图中的极大强连通子图。 C）在一个有向图的拓扑序列中，若顶点a在顶点b之前，则图中必有一条弧。 D）对有向图G,如果从任意顶点出发进行一次深度优先或广度优先搜索能访问到每个顶点，则该图一定是完全图。 69．在图采用邻接表存储时，深度优先查找遍历图的时间复杂度为( )。 23 A）O(n) B） O(n+e) C）O(n) D）O(n) 70.设有无向图G=（V，E）和G’=（V’,E’）,如G’为G的生成树，则下面不正确的说法是（ ） A）G’为G的子图 B）G’为G的连通分量 C）G’为G的极小连通子图且V’=V D）G’是G的无环子图 71．设图的邻接链表如下图所示，则该图的边的数目是（ ） A）4 B）5 C）10 D）20 5