资源描述：
《数据结构复习题答案》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。
1、一、选择题1.栈和队列的共同特点是（）。A.只允许在端点处插入和删除元素B.都是先进后出C.都是先进先岀I）.没有共同点2.用链接方式存储的队列，在进行插入运算时（）.A.仅修改头指针B.头、尾指针都要修改C.仅修改尾指针D.头、尾指针可能都要修改3.以下数据结构中哪一个是非线性结构？（）A.队列B.栈C.线性表D.二叉树4.设有一个二维数组［/?］，假设劇［0］存放位置在644⑽，刈2］［2］存放位置在676（,o>,每个元素占一个空间，问爪3］［3］⑽存放在（）位置，脚注⑽表示用10进制表示。A.688B.678C.6
2、921）.6965.树最适合用来表示（）oB.无序数据元素D.元素之间无联系的数据D.2k_lA.有序数据元素C.元素之间具有分支层次关系的数据6.二叉树的第k层的结点数最多为（）.A.2-1B.2K+1C.2K-17.若有18个元素的有序表存放在一维数组A［19］屮，第一个元素放A［l］屮，现进行二分查找，则查找A［3］的比较序列的下标依次为（）A.1，2,3C.9,5,3B.9,5,2,3D.9，4,2,38.对n个记录的文件进行快速排序，所需要的辅助存储空间大致为（）A.0（1）B.0（n）C.0（log^n）D.0
3、（n2）9.对于线性表（7，34，55,25,64,46,20,10）进行散列存储时，若选用H（K）=K%9作为散列函数，则散列地址为1的元素有（）个，A.1B.2C.3D.410.设有6个结点的无向图，该图至少应有（）条边冰能确保是一个连通图。A.5B.6C.7D.811.一个链队列中，f,r分别为队首、队尾指针，则插入s所指结点的操作为（）。A)f-〉next二c;f二s;B)r—>next=s;r=s；C）s-〉next=r;r=s；12.下列说法正确的是（）。A）二叉树屮每个结点的度都为2C）一棵二叉树的度可小于2
4、D）s-〉next=f;f=s；B）二叉树的度为2D）二叉树中至少有一个结点的度213.—棵非空二叉树先序遍历与后序遍历序列正好相反，则该二叉树（）。A）所有的结点均无左孩子C）只有一个叶子结点B）所有的结点均无右孩子D）是任意一棵二叉树A)左指针为空C)左右指针均为空15.n个顶点的强连通阁至少有(D)左右指针均非空八)n-1B)n)条边。C)n+1D)n(n~l)13.二叉排序树中，键值最小的结点一定()。B)右指针为空16.在一个有向图中，顶点入度之和与顶点出度之和的比值()。A)1/2B)1C)2D)417.高度为
5、h的二叉树只有度为0和2的结点，则此二叉树至少为()结点A)2*hB)2*h-lC)2*h+lD)h+118.设某完全无向阁屮有n个顶点，则该完全无向阁屮有()条边。(A)n(n~l)/2(B)n(n~l)(C)n2(D)n2-l19.设某棵二叉树中有2000个结点，则该二叉树的最小高度为()。(A)9⑻10(C)11(D)1220.设某有向图中有n个顶点，则该有叫图对应的邻接表中有()个表头结点。(A)n-1⑻n(C)n+1(D)2n~l21.设一组初始记录关键字序列(5,2,6,3,8),以第一个记录关键字5为基准进行
6、一趟快速排序的结果为()。(A)2,3,5,8,6(B)3,2,5,8,6(C)3,2,5,6,8(D)2,3,6,5,822.按照二叉树的定义，具有3个结点的二叉树有()种形态八)3B)4C)5D)623.下列排序算法中，可能会出现在最后一趟开始之前，所有元素都不在其最终位罝上是().A)堆排序B)冒泡排序C)快速排序D)插入排序24.一组记录的排序码为46,79,56,38,40,84。用堆排序方法建立的初始堆为()。A)79,46,56,38,40,80B)84,79,56,38,40,46C)84,79,56,46
7、,40,38D)84,56,79,40,46,3825.将递归算法转换成对应的非递归算法时，通常需要使用()。A)栈B)队列C)链表D)树23.有10个结点的连通无向图，其边数至少有()。A)8条B)9条C)10条D)11条27.一个栈的入栈序列是a,b,c，d,e，A)edcbaB)decba则栈的不可能的输山序列是(C)dceabD))。abode28.岛度为h的完全二叉树屮所包含的结点数至少为()。A)2*h个B)2h_i个C)2朴+1个D)h+1个29.设一维数组中有n个数组元素，则读取第i个数组元素的平均时间复杂
8、度为()。(A)0(n)(B)0(nlog2n)(C)0(1)(D)0(n2)30.设一棵二叉树的深度为k，则该二叉树中最多有()个结点。(A)2k-l(B)2k(C)2k_1(D)2-131.设某无向图中有n个顶点e条边，则该无向图中所有顶点的入度之和为()。(八)n(B)e(C)2n(D)2e32.
