数据结构模拟练习题2参考答案.docxVIP

数据结构模拟练习题2参考答案一、单项选择题（每小题2分，共30分）1、算法的时间复杂度取决于（ C ）A．问题的规模 B. 待处理数据的初态 C. A和B2、在存储数据时，通常不仅要存储各数据元素的值，而且还要存储（C）Ａ.数据的处理方法 B.数据元素的类型C.数据元素之间的关系 D.数据的存储方法3、链表不具有的特点是（ B ） A．插入、删除不需要移动元素 B．可随机访问任一元素 C．不必事先估计存储空间 D．所需空间与线性长度成正比4、在下面的程序段中，对x的赋值语句的频度为（ C ）for (i=1;i=n;i++) for (j=1;j=n;j++) x=x+1;A． O(2n) B．O(n) C．O(n2) D．O(log2n)5、判断一个顺序栈S（最多元素为m）为满的条件是（C）。A．S.top==0 B．S.top!=0 C．S.top==m D．S.top!=m6、串的长度是指（ B ）A．串中所含不同字母的个数 B．串中所含字符的个数C．串中所含不同字符的个数 D．串中所含非空格字符的个数7、循环队列的队满条件为 ( C )A. (sq.rear+1) % maxsize ==(sq.front+1) % maxsize;B. (sq.front+1) % maxsize ==sq.rearC. (sq.rear+1) % maxsize ==sq.frontD.sq.rear ==sq.front8、将一棵有49个结点的完全二叉树从上到下，从左到右依次对结点进行编号，根结点的编号为1，则编号为25的结点的左孩子编号为（D ）。A．45 B．48 C．49 D．不存在9、已知某二叉树的后序遍历序列是dabec, 中序遍历序列是debac , 它的前序遍历是（ D ）。A．acbed B．decab C．deabc D．cedba 10、下面哪一方法可以判断出一个有向图是否有环（回路）（B）A．深度优先遍历 B. 拓扑排序 C. 求最短路径 D. 求关键路径11、如果要缩小关键路径的长度，有效的处理办法是（C ）。A．缩短任意一个活动的持续时间B．缩短关键路径上任意一个关键活动的持续实践C．缩短多条关键路径共有关键活动的持续时间D．没有办法12、如果要求一个线性表既能较快的查找，又能适应动态变化的要求，则可采用( A )查找法。A. 分快查找 B. 顺序查找 C. 折半查找 D. 基于属性13、将10个元素散列到100000个单元的哈希表中，则（ C ）产生冲突。A. 一定会 B. 一定不会 C. 仍可能会14、一组记录的关键码为（46，79，56，38，40，84），则利用快速排序的方法，以第一个记录为基准得到的一次划分结果为（ C ）。A．(38,40,46,56,79,84) B. (40,38,46,79,56,84)C．(40,38,46,56,79,84) D. (40,38,46,84,56,79)15、 有一组数据（15，9，7，8，20，-1，7，4），用堆排序的筛选方法建立的初始堆为 （ C ）A．-1，4，8，9，20，7，15，7 B．-1，7，15，7，4，8，20，9C．-1，4，7，8，20，15，7，9 D．A，B，C均不对。二、判断题（在各题后填写“√”或“×”，10分）1、数据的逻辑结构是指数据的各数据项之间的逻辑关系；( × ) 2、在顺序存储结构中，有时也存储数据结构中元素之间的关系。( × )3、循环队列就是队列的一种循环的链式存储结构。（×）4、树型结构是一种非线性结构，因此只能用顺序存储方式。（N）5、完全二叉树中，若一个结点没有左孩子，则它必是树叶。( √ )6、无向图用邻接矩阵表示后，该矩阵一定是对称矩阵。(√)7、若某有向图不存在拓扑序列，则该有向图一定有回路。(√)8、快速排序的速度在所有排序方法中最快，而且所需附加空间也最少。（ × ）9、堆排序是稳定的排序方法。（ × ）10、将一个新结点插入到二叉排序树中，该结点一定成为叶子结点。(√)三、 填空题（每空１分，共10分）1、线性表的常见链式存储结构有___单链表___、_双链表___和_循环链表__。2、循环队列的引入，目的是为了克服___假溢出时大量移动数据元素____。 3、 以下运算实现在链栈上的进栈，请在处用请适当句子予以填充。Void Pus