数据结构课程习题汇编解答

A．都不相同 B．完全相同

C．先序和中序相同，而与后序不同 D．中序和后序相同，而与先序不同 102．某二叉树的前序序列和后序序列正好相反，则该二叉树一定是（）的二叉树。

A．空或只有一个结点 B．任一结点无左子树 C．高度等于其结点数 D．任一结点无右子树

103．若线性表最常用的操作是存取第i个元素及其前驱的值，则采用 （ ） 存储方式节省时间。

A. 单向链表 B.双向链表 C.单循环链表 D.顺序表

104．对二叉树的结点从1开始进行连续编号，要求每个结点的编号大于其左、右孩子的编号，同一双亲的左、右孩子中，左孩子的编号小于右孩子的编号，则可采用（ ） 顺序实现编号。

A. 前序遍历 B.中序遍历 C.后序遍历 D.层序遍历 105．设连通图G的顶点数n，则G的生成树的边数为 （ ） 。

A.n B.n-1 C.2n D，2n-1

106．若长度为n的线性表采用顺序存储结构，删除一元素需要移动元素的平均个数为（ ）

A (n-1)/2 B n C n-1 D n/2

107．设A是n*n的对称矩阵，将A的对角线及对角线上方的元素以列为主的次序存放在一维数组B[1..n(n+1)/2]中，对上述任一元素aij(1≤i，j≤n，且i≤j)在B中的位置为( )。

A. i(i-l)/2+j B. j(j-l)/2+i C. j(j-l)/2+i-1 D. i(i-l)/2+j-1 108．设栈的输入序列为（1，2，3，4），则不可能的出栈序列为（ ）

A 1234 B 2134 C 1432 D 4312

109．从一棵深度为h的二叉排序树中查找一个元素时，其时间复杂度为 ( )。

A．O(h) B．O(h2) C．O(log2h) D．O(n*log2h)

110．一个循环队列的队首和队尾指针分别是front和rear,则判别队空的条件是（ ） A.front+1==rear C.front==0

B.front==rear+1 D.front==rear

111．由两个栈共享一个向量空间的好处是（ ）

A、减少存取时间，降低下溢发生的机率 B、节省存取空间，降低上溢发生的机率 C、减少存取时间，降低上溢发生的机率 D、节省存取空间，降低下溢发生的机率 112．如下陈述中正确的是（ ）

A、串是一种特殊的线性表 B、串的长度必须大于零 C、串中元素只能是字母 D、空串就是空白串

113． 引入二叉线索树的目的是（ ）

A．加快查找结点的前驱或后继的速度 B．为了能在二叉树中方便的进行插入与删除 C．为了能方便的找到双亲 D．使二叉树的遍历结果唯一 114．线索二叉树是一种（ ）结构。

A． 逻辑 B． 逻辑和存储 C． 物理 D．线性 115．n个结点的线索二叉树上含有的线索数为（ ）

A．2n B．n－l C．n＋l D．n 116．二叉树在线索后，仍不能有效求解的问题是（ ）。

A．前（先）序线索二叉树中求前（先）序后继 B．中序线索二叉树中求中序后继 C．中序线索二叉树中求中序前驱 D．后序线索二叉树中求后序后继

117． 设F是一个森林，B是由F变换得的二叉树。若F中有n个非终端结点，则B中右指针域为空的结点有（ ）个。

A． n-1 B．n C． n+1 D． n+2

118．如果T2是由有序树T转换而来的二叉树，那么T中结点的后序就是T2中结点的（ ）。

A．先序 B．中序 C．后序 D．层次序

119、无向图G=（V，E），其中：V={ a,b,c,d,e,f} ,E={(a,b),(a,e),(a,c),(b,e),(c,f),(f,d),(e,d)} 对该图进行深度优先遍历，得到的顶点序列正确的是（ ） A.a,b,e,c,d,f B.a,c,f,e,b,d

C.a,e,b,c,f,d D.a,e,d,f,c,b

120．对序列{15，9，7，8，20，-1，4}进行排序，进行一趟后数据的排列变为{4，9，-1，8，20，7，15}；则采用的是（ ）排序。

A. 选择 B. 快速 C. 希尔 D. 冒泡

121．设哈希表长为14，哈希函数是H(key)=key,表中已有数据的关键字为15,38,61,84共四个，现要将关键字为49的结点加到表中，用二次探测再散列法解决冲突，则放入的位置是（ ）

A. 8 B.3 C.5 D.9

122． 用数组 r 存储静态链表, 结点的 next 域指向后继, 工作指针 j 指向链中结点,使 j 沿链移动的操作为（ ）

A. j=r[j].next B. j=j+1 C. j=j->next D. j=r[j]->next

123．判定一个有图是否存在回路，除了可以利用拓扑排序的方法外，还可以利用( )。 A.求关键路径的方法 B.求最短路径的Dijkstra方法

C.深度优先遍历算法 D.广度优先遍历算法

124．为查找某一特定单词在文本中出现的位置，可应用的串运算是( )

A.插入 B.删除 C.串联接 D.子串定位

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，则队列的输出序列是（ ）