数据结构(C++)模拟试题.doc

《数据结构(C++)模拟试题.doc》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、数据结构(C++)模拟试题一．填空题1.若待排序的序列中存在多个记录具有相同的键值，经过排序，这些记录的相对次序仍然保持不变，则称这种排序方法是________的，否则称为________的。2.按照排序过程涉及的存储设备的不同，排序可分为________排序和________排序。3.直接插入排序是稳定的，它的时间复杂性为________，空间复杂度为________。4.对于n个记录的集合进行冒泡排序，其最坏情况下所需的时间复杂度是________。5.二叉排序树是一种特殊的、增加了限制条件的二叉树，其限制条件是任

2、一结点的键值________于其左孩子（及其子孙）的键值且________于其右孩子（及其子孙）的键值。6.中根遍历一棵二叉排序树所得的结点访问序列是键值的________序列。7.平衡二叉排序树上任一结点的平衡因子只可能是________、________或________。8.采用散列技术时需要考虑的两个主要问题是：一、________？二、________？9.一个具有n个顶点的完全无向图的边数为________。一个具有n个顶点的完全有向图的弧度数为________。10.遍历图的基本方法有________优先

3、搜索和________优先搜索两种。11.在无向图中，如果从顶点v到顶点v’有路径，则称v和v’是_______的。如果对于图中的任意两个顶点vi,vj∈V，且vi和vj都是连通的，则称G为________。12.二叉树第i(i>=1)层上至多有______个结点。13.深度为k(k>=1)的二叉树至多有______个结点。14.具有n个结点的二叉树中,一共有________个指针域,其中只有________个用来指向结点的左右孩子，其余的________个指针域为NULL。15．有m个叶子结点的哈夫曼树，其结点总数为

4、________。16．需要压缩存储的矩阵可分为___________矩阵和___________矩阵两种。17．队称为___________线性表。18.从某种意义是说，数据、数据元素和数据项实际反映了数据组织的三个层次，数据可由若干个__________构成，数据元素可由若干个__________构成。19.常见时间复杂性的量级有：常数阶O(___________)、对数阶O(________)线性阶O(___________)、平方阶O(___________)、和指数阶O(___________)。20.线性结

5、构的基本特征是若至少含有一个结点，则除起始结点没有直接______外，其他结点有且仅有一个直接______;除终端结点没有直接______外，其它结点有且仅有一个直接______.二．选择题1.当初始序列已按健值有序时，用直接插入算法进行排序，需要比较的次数为（）A.n-1B.log2nC.2log2nD.n2冒泡排序n2选择排序n2插入排序n2堆排序nlogn归并排序nlog2n快速排序n2希尔排序n22.以下时间复杂性不是O(n2)的排序方法是()A.直接插入排序B.二路归并排序C.冒泡排序D.直接选择排序3.．对

6、采用二分查找法进行查找运算的查找表，要求按（）方式进行存储。A.顺序存储B链式存储C.顺序存储且结点按关键字有序D.链式存储且结点按关键字有序4.设有序表的关键字序列为{1，4，6，10，18，35，42，53，67，71，78，84，92，99}，当用二分查找法查找健值为84的结点时，经（）次比较后查找成功。A.2B.3C.4D.125.静态查找表与动态查找表两者的根本差别在于()…………………………………………….A.逻辑结构不同B.存储实现不同C.施加的操作不同D.数据元素的类型不同6．用顺序查找法对具有n个结点

7、的线性表查找的时间复杂性量级为A.O（n2）B.O(nlog2n)C.O（n）D.O(log2n)7.设有6个结点的无向图，该图至少应有（）条边能确保是一个连通图。A.5B.6C.7D88.在无向图中，所有顶点的度数之和是所有边数的（）倍。A.0．5B.1C.2D.49.深度为6的二叉树最多有()个结点.A.64B.63C.32D.3110．将含有83个结点的完全二叉树从根结点开始编号，根为1号，后面按从上到下、从左到右的顺序对结点编号，那么编号为41的双亲结点编号为()A.42B.40C.21D.2011.已知某二叉

8、树的后序遍历序列是dabec,中序遍历序列是deabc,它的前序遍历序列是（）A.acbedB.deabcC.decabD.cedba12.设二叉树结点的先根序列、中根序列和后根序列中，所有叶子结点的先后顺序()A.都不相同B.完全相同C.先序和中序相同，而与后序不同D.中序和后序相同，而与先序不同13．如果以链表作为栈的存储结构