125．设单循环链表中结点的结构为（data，next），且rear是指向非空的带头结点的单循环链表的尾结点的指针。若要删除链表的第一个结点，则应执行下列哪一个操作？( )
A. s=rear; rear=rear->next; free(s); B. rear=rear->next; free(s); C. rear=rear->next->next; free(s);
D s=rear->next->next; rear->next->next=s->next; free(s);
126．下列排序算法中，在每一趟都能选出一个元素放到其最终位置上，并且其时间性能受数据初始特性影响的是：（ ）。
A. 直接插入排序 B. 快速排序 C. 直接选择排序 D. 堆排序 127．在一棵二叉树上，第4层上的结点数最多为( )
A.31 B.8 C.15 D.16
128． 快速排序方法在( )情况下，最不利于发挥其长处 A.要排序的数据量太大 B.要排序的数据含有多个相同值 C.要排序的数据已基本有序 D.要排序的数据个数为奇数 129． 对于无向图的生成树，下列说法不正确的是( )
A.生成树是遍历的产物
B.从同一顶点出发所得的生成树相同 C.生成树是图的极小连通子图 D.不同遍历方法所得到的生成树不同 130．算法分析的目的是( )
A.找出数据结构的合理性 B.研究算法中的输入和输出的关系 C.分析算法的效率以求改进 D.分析算法的易懂性和文档性 131．下列陈述中正确的是( )
A.二叉树是度为2的有序树 B.二叉树中结点只有一个孩子时无左右之分 C.二叉树中必有度为2的结点 D.二叉树中最多只有两棵子树，并且有左右之分 132．判断有向图是否有回路，除了可以用深度优先遍历算法外，还可以用( ) A. 求关键路径的方法 B. 广度优先遍历算法
C. 求最短路径的方法 D. 拓扑排序
133．有一个有序表为{5,8,10,15,32,41,45,62,75,77,82,95,100},当二分查找值为82的数据时( ) 次比较成功。
A.1 B.4 C.2 D.8
134．下列关于AOE网的叙述中，不正确的是（ ）。
A．关键活动不按期完成就会影响整个工程的完成时间 B．任何一个关键活动提前完成，那么整个工程将会提前完成
C．所有的关键活动提前完成，那么整个工程将会提前完成 D．某些关键活动提前完成，那么整个工程将会提前完成
135．采用顺序查找方法查找长度为n的线性表，平均查找长度为 ( )。 A.n B.n/2 C.(n+1)/2 D.(n-1)/2 136．下列哪一种图的邻接矩阵是对称矩阵？（ ）
A．有向图 B．无向图 C．AOV网 D．AOE网 137．对线性表采用折半查找法，该线性表必须 ( )。
A. 采用顺序存储结构 B.采用链式存储结构 C.采用顺序存储结构，且元素按值有序 D.采用链式存储结构，且元素按值有序
138．已知二叉树的前序序列为ABDCEFG，中序序列为DBCAFEG，则后序序列为 ( )。 A.DCBAFGE B.DCBFGEA C.DCBFEGA D.DCBGFEA
139．当利用大小为N 的数组顺序存储一个栈时，假定用top = = N表示栈空，则退栈时，用（ ）语句修改top指针。
A．top++; B．top=0; C．top--; D．top=N;
140．数据序列（2，1，4，9，8，10，6，20）只能是下列排序算法中的( )的两趟排序后的结果。
A. 快速排序 B. 冒泡排序 C. 选择排序 D. 插入排序 141．从一棵B_树删除元素的过程中，若最终引起树根结点的合并，则新树高度是（ ）。
A．原树高度加1 B．原树高度减1 C．原树高度 D．不确定 142．在倒排文件中，通常包含有 倒排表。
A.一个 B.多个 C.两个 D.一个或两个
143．若用冒泡排序方法对序列{10,14,26,29,41,52}从大到小排序，需进行 （ ）次比较。
A. 3 B. 10 C. 15 D. 25
144．循环队列A[0..m-1]存放其元素值，用front和rear分别表示队头及队尾，则当前队列中的元素数是
A.(rear - front + m)%m B.rear - front + 1 C. rear - front - 1 D.rear-front 145．下列说法不正确的是（ ）。
A．图的遍历是从给定的源点出发每一个顶点仅被访问一次
B．图的深度遍历不适用于有向图
C．遍历的基本算法有两种：深度遍历和广度遍历 D．图的深度遍历是一个递归过程
146. 一个队列的入队序列是1、2、3、4，则队列的输出序列是（ ）
A. 4、3、2、1 B.1、2、3、4 C.1、4、3、2 D.3、2、4、1
147.在一个单链表中，已知q所指结点是p所指结点的前驱结点，若在q和p之间插入s结点，则执行（ ）
A. s -> next = p -> next; p->next = s;B.p->next = s->next; s->next = p; C.q->next = s; s->next = p; D.p->next = s; s->next = q;
148．下列排序算法中( )不能保证每趟排序至少能将一个元素放到其最终的位置上。
A.快速排序 B. shell排序 C. 堆排序 D.冒泡排序 149．具有n个顶点的有向图最多有（ ）条边。
A．n B.n(n-1) C.n(n+1) D.n*n
150．在数据结构中，逻辑上数据结构可分为（ ）。
A．动态结构和静态结构 B．线性结构和非线性结构 C．紧凑结构和非紧凑结构 D．内部结构和外部结构 151．在下面的排序方法中，辅助空间为O（n）的是( ) 。
A．希尔排序 B. 堆排序 C. 选择排序 D. 归并排序 152．不便于插入和删除操作的是（ ）。
A．单链表 B．双链表 C．顺序表 D．循环链表
153．在有向图G的拓扑序列中，若顶点Vi在顶点Vj之前，则下列情形不可能出现的是（ ）。
A．G中有弧
B．一个事件的最早开始时间同以该事件为尾的弧的活动最早开始时间相同
C．一个事件的最迟开始时间为以该事件为尾的弧的活动最迟开始时间与该活动的持续时间的差
D．关键活动一定位于关键路径上 155．树最适合用来表示（ ）
A.有序数据元素 B.无序数据元素 C.元素之间具有分支层次关系的数据 D.元素之间无联系的数据 156．具有4个顶点的无向完全图至多有（ ）条边。
A.6 B.12 C.16 D.20
157．具有6个顶点的无向图至少应有（ ）条边才能确保是一个连通图。
A.5 B.6 C.7 D.8
158．假定有k个关键字互为同义词，若用线性探测法把这k个关键字存入散列表中，至少要进行多少次探测？( )
A．k-1次 B. k次 C. k+1次 D. k（k+1）/2次
159．设哈希表长为14，哈希函数是H(key)=key,表中已有数据的关键字为15，38，61，
84共四个，现要将关键字为49的结点加到表中，用二次探测再散列法解决冲突，则放入的位置是( ) A．8 B．3 C．5 D．9
160．设有一组记录的关键字为{19，14，23，1，68，20，84，27，55，11，10，79}，用链
地址法构造散列表，散列函数为H（key）=key MOD 13,散列地址为1的链中有（ ）个记录。 A．1 B. 2 C. 3 D. 4
填空题
二、填空题
1 栈的特点是( )，队列的特点是( )。
2 设二维数组A[-20..30,-30..20], 每个元素占有4 个存储单元, 存储起始地址为200.如按行优先顺序存储,则元素 A[25,18]的存储地址为( )；如按列优先顺序存储,则元素A[-18,-25]的存储地址为( )。
3 一个图的( 邻接矩阵 )表示法是唯一的，而(邻接表 )表示法是不唯一的。 4 二叉树由( )，( )，( )三个基本单元组成。 5树在计算机内的表示方式有( )，( )，( )。 6在二叉树中，指针p所指结点为叶子结点的条件是( )。
7中缀式a+b*3+4*（c-d）对应的前缀式为( )，若a=1，b=2，c=3，d=4，则后缀式db/cc*a-b*+的运算结果为( )。
8二叉树中某一结点左子树的深度减去右子树的深度称为该结点的( )。 9具有256个结点的完全二叉树的深度为( )。
10已知一棵度为3的树有2个度为1的结点，3个度为2的结点，4个度为3的结点，则该树有( )个叶子结点。
11在顺序表（8,11,15,19,25,26,30,33,42,48,50）中，用二分（折半）法查找关键码值20，需做的关键码比较次数为( )。
12深度为H 的完全二叉树至少有( )个结点；至多有( )个结点；H和结点总数N之间的关系是 ( )。
13高度为4的3阶b-树中，最多有( )个关键字。
14在完全二叉树中，编号为i和j的两个结点处于同一层的条件是( )。 15具有n个结点的满二叉树，其叶子结点的个数为( ).
16已知广义表A=(9,7,( 8,10,(99)),12)，试用求表头和表尾的操作Head( )和Tail( )将原子元素99从A中取出来( )。
17已知广义表L=（（x,y,z）,a,(u,t,w)）, 则head(tail(tail(L)))= ( )。 18设有二维数组A[0..9,0..19],其每个元素占两个字节，第一个元素的存储地址为100，若按列优先顺序存储，则元素A[6,6]存储地址为( )。
19．一棵有n个结点的满二叉树有( 0 )个度为1的结点、有( (n-1)/2 )个分支 （非 终端）结点和( (n+1)/2)个叶子，该满二叉树的深度为( )。
20．假设根结点的层数为１，具有ｎ个结点的二叉树的最大高度是( n )。
21．在一棵二叉树中，度为零的结点的个数为N0,度为2的结点的个数为N2,则有N0 =( )。 22设只含根结点的二叉树的高度为0，则高度为k的二叉树的最大结点数为( ),最小结点数为( )。