一、选择题1、一个n个顶点的无向连通图，其边的个数至少为（）。

A．n-1 B．n C．n+1 D．nlogn2、以下数据结构中，（）是非线性数据结构。

A．树B．字符串C．队列D．栈3、在长度为n的顺序表的第i个位置上插入一个元素（1≤i≤n+1），元素的移动次数为（）。

A．n –i+1 B．n –i C．i D．i-14、与线性表的链接存贮不相符合的特性是（）。

A．便于插、删运算B．需要连续的存贮空间C．只能顺序查找D．存贮空间动态分配5、顺序存放的循环队列的元素以数组A[m]存放,其头尾指针分别为front和rear，则当前队列中的元素个数为（）。

A．(rear-front+m)%m B．rear-front+1C．(front+rear+m)%m D．(rear-front)%m6、一个有n个顶点的无向图最多有( )条边。

A．n(n-1)/2 B．n (n-1) C．n-1 D．n+17、设栈的入栈序列是1，2，3，4，则（）不可能是其出栈序列。

A．1，2，4，3 B．2，1，3，4 C．1，4，3，2 D．4，3，1，2，8、从逻辑上可以把数据结构分为（）两大类。

A．动态结构、静态结构B．初等结构、构造型结构C．线性结构、非线性结构D．树型结构、图型结构9、某二叉树的先序序列和后序序列正好相反，则该二叉树一定是（）A．空或只有一个根结点B．高度等于其结点数C．任一结点无左孩子D．任一结点无右孩子10、已知一个有向图用邻接矩阵表示，要删除所有从第i个结点发出的边，应该（）。

A．将邻接矩阵的第i 行删除B．将邻接矩阵的第i 行元素全部置零C．将邻接矩阵的第i 列删除D．将邻接矩阵的第i 列元素全部置零11、算法分析的两个主要方面是（）A．空间复杂性和时间复杂性B．正确性和简明性C．可读性和文档性D．数据复杂性和程序复杂性12、线性表若采用链式存储结构时，要求内存中可用存储单元的地址( )。

A．必须是连续的B．部分地址必须是连续的C．一定是不连续的D．连续或不连续都可以13、具有6个顶点的无向连通图的生成树应有（）条边。

A．5 B．6 C．7 D．814、设栈的输入序列是A、B、C，则（）不可能是其出栈序列。

A．CBA B．CAB C．BCA D．ACB15、有一个含头结点的单链表，头指针为head，则判断其是否为空的条件为（）。

A．head==NULL B．head->next==NULLC．head->next== head D．head ！=NULL16、栈和队都是（）A．顺序存储的线性结构B．链式存储的非线性结构C．限制存取点的线性结构D．限制存取点的非线性结构17、在下述结论中，正确的是（）①只有一个结点的二叉树的度为0;②二叉树的度为2；③二叉树的左右子树可任意交换;④深度为K的完全二叉树结点个数小于或等于深度相同的满二叉树。

A．①②③B．②③④C．②④D．①④18、以下数据结构中，（）是非线性数据结构。

A．树B．字符串C．队列D．栈19、设森林F中有三棵树，第一，第二，第三棵树的结点个数分别为M1，M2和M3。

与森林F对应的二叉树根结点的右子树上的结点个数是（）。

A．M1 B．M1+M2 C．M3 D．M2+M320、在下面的程序段的时间复杂度为（）。

for (int i=1;i<n;i++)for (int j=1;j<n;j++)a[i][j]=i*j;A．O(m2) B．O(m*n) C．O(n2) D．O(log2n)21、二叉树的第I层上最多含有结点数为（）A．2I B．2I-1-1 C．2I-1D．2I -122、下列排序算法中( )排序在一趟结束后不一定能选出一个元素放在其最终位置上。

A．选择B．冒泡C．归并D．堆23、线性表第一个元素的存储地址是100,每个元素的长度为2,则第5个元素的地址是( )A．110 B．108 C．100 D．12024、栈中元素的进出原则是（）。

Ａ．先进先出Ｂ．后进先出Ｃ．栈空则进Ｄ．栈满则出25、下列字符串中（）不是．．串"ABCABDEABX"的子串。

A．"A BC" B．"BX" C．" AB" D．"AD"26、对稀疏矩阵进行压缩存储目的是（）。

A．便于进行矩阵运算B．便于输入和输出C．节省存储空间D．降低运算的时间复杂度27、设二维数组A[1..5,1..6]的每个元素占5个存储单元，将其按行优先顺序存储在起始地址是1000的连续内存单元中，则A[5,5]的存储地址是（）。

A．1140 B．1145 C．1120 D．112528、外排序是指（）。

A．数据量很大，排序时要借外存进行的排序方法B．不需要使用内存的排序方法C．数据量很大，需要人工干预的排序方法D．没有正确答案29、下列数据中不可能是平衡二叉树上结点的平衡因子的是（）。

A．-1 B．0 C．1 D．230、在下面的程序段的时间复杂度为（）。

for (int i=1;i< m;i++)for (int j=1;j<n;j++)a[i][j]=i*j;A．O(m2) B．O(m*n) C．O(n2) D．O(log2n)31、深度为K的二叉树最多含有结点数为（）A．2k B．2k-1-1 C．2k-1D．2k -132、设二维数组A[0..10,0..20]按行优先顺序存储，每个元素占4个存储单元，A[2,1]的存储地址是1000，则A[5,6]的存储地址是（）。

A．1021 B．1056 C．1260 D．120033、有三个结点的二叉树的基本形态有（）种。

A．2 B．3 C．4 D．534、有三个结点的树的基本形态有（）种。

A．2 B．3 C．4 D．535、若一棵二叉树具有10个度为2的结点，5个度为1的结点，则度为0的结点个数是（）A．9 B．11 C．15 D．不确定36、在一棵度为4的树T中，若有20个度为4的结点，10个度为3的结点，1个度为2的结点，10个度为1的结点，则树T的叶节点个数是（）A．41 B．82 C．113 D．12237、对n(n大于等于2)个权值均不相同的字符构成哈夫曼树，关于该树的叙述中，错误的是（）A ．该树一定是一棵完全二叉树B ．树中一定没有度为1的结点C ．树中两个权值最小的结点一定是兄弟结点D ．树中任一非叶结点的权值一定不小于下一任一结点的权值38、顺序存放的循环队列的元素以数组A[m]存放,其头尾指针分别为front 和rear ，则当前队列中的元素个数为（ ）。

A ．(rear-front+m)%mB ．rear-front+1C ．(front+rear+m)%mD ．(rear-front)%m39、若元素a,b,c,d,e,f 依次进栈，允许进栈、退栈操作交替进行。

但不允许连续三次进行退栈工作，则不可能得到的出栈序列是（ ）A ．dcebfaB ．cbdaefC ．dbcaefD ．afedcb40、某队列允许在其两端进行入队操作，但仅允许在一端进行出队操作，则不可能得到的顺序是（ ）A ．bacdeB ．dbaceC ．dbcaeD ．ecbad41、散列表中的冲突是指（ ）A ．两个元素具有相同的序号B ．两个元素的关键字相同，而其他属性相同C ．相同的关键字对应不相同的存储地址D ．数据元素的地址相同42、下面关于线性表的叙述中，错误的是哪一个？（ ）A ．线性表采用顺序存储，必须占用一片连续的存储单元。

B ．线性表采用顺序存储，便于进行插入和删除操作。

C ．线性表采用链接存储，不必占用一片连续的存储单元。

D ．线性表采用链接存储，便于插入和删除操作。

43、非空的循环单链表head 的尾结点p ↑满足（ ）。

A ．p ↑.link=headB ．p ↑.link=NILC ．p=NILD ．p= head44、在单链表指针为p 的结点之后插入指针为s 的结点,正确的操作是（ ）。

A ．p->next=s;s->next=p->next;B ．s->next=p->next;p->next=s;C ．p->next=s;p->next=s->next;D ．p->next=s->next;p->next=s;45、设栈的输入序列是1，2，3，4,则（）不可能是其出栈序列。

A ．1，2，4，3，B ．2，1，3，4，C ．1，4，3，2，D ．4，3，1，2，E ．3，2，1，4，46、栈在（ ）中应用。

A ．递归调用B ．子程序调用C ．表达式求值D ．A ，B ，C47、下列哪一种图的邻接矩阵是对称矩阵？（ ）A ．有向图B ．无向图C ．AOV 网D ．AOE 网48、下述哪一条是顺序存储结构的优点？（ A ）A ．存储密度大B ．插入运算方便C ．删除运算方便D ．可方便地用于各种逻辑结构的存储表示49、线性表是具有n 个（ C ）的有限序列（n>0）。

A ．表元素B ．字符C ．数据元素D ．数据项E ．信息项50、输入序列为ABC ，可以变为CBA 时，经过的栈操作为（ B ）A. push,pop,push,pop,push,popB. push,push,push,pop,pop,popC. push,push,pop,pop,push,popD. push,pop,push,push,pop,pop51、从邻接阵矩可以看出，该图共有（ ）个顶点；如果是有向图该图共有（ ）条弧；如果是无向图，则共有（ ）条边。

①．A ．9 B ．3 C ．6 D ．1 E ．以上答案均不正确②．A ．5 B ．4 C ．3 D ．2 E ．以上答案均不正确③．A ．5 B ．4 C ．3 D ．2 E ．以上答案均不正确52、最大容量为n 的循环队列，队尾指针是rear ，队头是front ，则队满的条件是（ A ）。

A. (rear+1) %n=frontB. rear=frontC ．rear+1=front D. (rear-l) % n=front⎥⎥⎥⎦⎤⎢⎢⎢⎣⎡=010101010A53、循环队列A[0..m-1]存放其元素值，用front和rear分别表示队头和队尾，则当前队列中的元素数是( A )。

A. (rear-front+m)%mB. rear-front+1C. rear-front-1D. rear-front54、最大容量为n的循环队列，队尾指针是rear，队头是front，则队空的条件是（ B ）。

A. (rear+1) %n=frontB. rear=frontC．rear+1=front D. (rear-l) % n=front55、设树T的度为4，其中度为1，2，3和4的结点个数分别为4，2，1，1 则T中的叶子数为（ C ）A．5 B．6 C．7 D．856、有n个叶子的哈夫曼树的结点总数为（ D ）。