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

模拟试题3一选择题1.当初始序列已按健值有序时，用直接插入算法进行排序，需要比较的次数为（ ）A.n-1 B.log2n C. 2log2n D.n2冒泡排序n2选择排序n2插入排序n2堆排序nlog n归并排序nlog2n快速排序n2希尔排序n22.以下时间复杂性不是O(n2)的排序方法是( )A.直接插入排序 B.二路归并排序 C.冒泡排序 D.直接选择排序3.对采用二分查找法进行查找运算的查找表，要求按（ ）方式进行存储。A.顺序存储 B 链式存储C.顺序存储且结点按关键字有序 D.链式存储且结点按关键字有序4.设有序表的关键字序列为1，4，6，10，18，35，42，53，67，71，78，84，92，99，当用二分查找法查找健值为84的结点时，经（ ）次比较后查找成功。A.2 B. 3 C. 4 D. 125.静态查找表与动态查找表两者的根本差别在于( ). A.逻辑结构不同 B.存储实现不同C.施加的操作不同 D.数据元素的类型不同6用顺序查找法对具有n个结点的线性表查找的时间复杂性量级为 A.O（n2） B. O(nlog2n) C. O（n） D.O(log2n)7.设有6个结点的无向图，该图至少应有（ ）条边能确保是一个连通图。A. 5 B. 6 C. 7 D 88.在无向图中，所有顶点的度数之和是所有边数的（ ）倍。A.05 B.1 C.2 D.4 9.深度为6的二叉树最多有( )个结点.A.64 B.63 C.32 D.3110将含有83个结点的完全二叉树从根结点开始编号，根为1号，后面按从上到下、从左到右的顺序对结点编号，那么编号为41的双亲结点编号为 ( )A.42 B.40 C.21 D.2011.已知某二叉树的后序遍历序列是dabec,中序遍历序列是deabc,它的前序遍历序列是（ ）A.acbed B.deabc C.decab D.cedba12.设二叉树结点的先根序列、中根序列和后根序列中，所有叶子结点的先后顺序( )A.都不相同 B.完全相同 C.先序和中序相同，而与后序不同 D.中序和后序相同，而与先序不同13如果以链表作为栈的存储结构，做退栈操作时( )A.必须判别栈是否满 B.必须判别栈是否空C.判别栈元素的类型 D.对栈不做任何操作14链栈与顺序栈相比，有一个比较明显的优点即（ ）A.插入操作更方便 B. 通常不会出现栈满的情况C.不会出现栈空的情况 D. 删除操作更方便 15.线性结构中的一个结点代表一个（ ） A. 数据元素 B. 数据项 C. 数据 D. 数据结构二填空题1.若待排序的序列中存在多个记录具有相同的键值，经过排序，这些记录的相对次序仍然保持不变，则称这种排序方法是_的，否则称为_的。2.按照排序过程涉及的存储设备的不同，排序可分为_排序和_排序。3.直接插入排序是稳定的，它的时间复杂性为_，空间复杂度为_。4.对于n个记录的集合进行冒泡排序，其最坏情况下所需的时间复杂度是_。5.二叉排序树是一种特殊的、增加了限制条件的二叉树，其限制条件是任一结点的键值_于其左孩子（及其子孙）的键值且_于其右孩子（及其子孙）的键值。6.中根遍历一棵二叉排序树所得的结点访问序列是键值的_序列。7.平衡二叉排序树上任一结点的平衡因子只可能是_、_或_。8.采用散列技术时需要考虑的两个主要问题是：一、_？二、_？9.一个具有n个顶点的完全无向图的边数为_。一个具有n个顶点的完全有向图的弧度数为_。10.遍历图的基本方法有_优先搜索和_优先搜索两种。11.在无向图中，如果从顶点v到顶点v有路径，则称v和v是_的。如果对于图中的任意两个顶点vi,vjV，且vi和vj都是连通的，则称G为_。12.二叉树第i(i=1)层上至多有_个结点。13.深度为k(k=1)的二叉树至多有_个结点。14.具有n个结点的二叉树中,一共有_个指针域,其中只有_个用来指向结点的左右孩子，其余的_个指针域为NULL。15有m个叶子结点的哈夫曼树，其结点总数为_。16需要压缩存储的矩阵可分为_矩阵和_矩阵两种。17队称为_线性表。18.从某种意义是说，数据、数据元素和数据项实际反映了数据组织的三个层次，数据可由若干个_构成，数据元素可由若干个_构成。19.常见时间复杂性的量级有：常数阶O(_)、对数阶O(_)线性阶O(_)、平方阶O(_)、和指数阶O(_)。20.线性结构的基本特征是若至少含有一个结点，则除起始结点没有直接_外，其他结点有且仅有一个直接_;除终端结点没有直接_外，其它结点有且仅有一个直接_.三名词解释题 1.排序 2.堆 3. .查找长度 4.无向完全图 5.有向完全图6. 二叉树 7. 满二叉树 8.栈 9.队列 10.链表 四简答题1. 什么是二叉排序树?2. 什么是顺序表?3. 什么叫稀疏矩阵?4. 静态查找表与动态查找表的区别是什么?5. 什么叫无向图?五解答题1判断下列两序列是否为堆？若不是，按照建堆的思想把它调整为堆，并用图表示建堆的过程。（1）（3，10，12，22，36，18，28，40）；（2）（5，8，11，15，23，20，32，7）。2已知数据序列为（12，5，9，20，6，31，24），对该数据序列进行排序，试写出插入排序和冒泡排序每趟的结果。3.对长度为20的有序表进行二分查找，请画出它的一棵判定树，并求等概率情况下的平均查找长度。六算法设计题1.找出数组A1.n中元素的最大值和次最大值（本小题以数组元素的比较为标准操作）。2.在数组A1.n中查找值为K的元素,若找到则输出其位置i(1=i1,试设计一个算法,求数组An的逆序。模拟试题4一、单项选择题1.下面程序段的时间复杂度是( )for(i=0;in;i+) for(j=1;jnext; B.p-next=p-next-next;C.p-next=p; D.p=p-next-next;3.在头指针为head且表长大于1的单循环链表中，指针p指向表中某个结点，若p-next-next=head,则( )A.p指向头结点 B.p指向尾结点C.*p的直接后继是头结点 D.*P的直接后继是尾结点4.判定“带头结点的链队列为空”的条件是( )A. Q.front=NULL B. Q.rear=NULLC. Q.front=Q.rear D. Q.front!=Q.rear5.设有两个串T和P，求P在T中首次出现的位置的串运算称作( )A.联接 B.求子串 C.字符定位 D.子串定位6.广义表A=(a,(b),(),(c,d,e)的长度为( )A.4 B.5 C.6 D.77.一棵含18个结点的二叉树的高度至少为( )A.3 B.4 C.5 D.68.已知二叉树的先序序列为ABDECF，中序序列为DBEAFC，则后序序列为( )A.DEBAFC B.DEFBCA C.DEBCFA D.DEBFCA9.无向图中一个顶点的度是指图中( )A.通过该顶点的简单路径数 B.与该顶点相邻接的顶点数C.通过该顶点的回路数 D.与该顶点连通的顶点数10.在有向图中，所有顶点的入度之和是所有顶点出度之和的（ ）倍。 A.05 B. 1 C. 2 D.4 11.在下列排序方法中，平均时间复杂度为O(nlogn)且空间性能最好的是( )A.快速排序 B.堆排序 C.归并排序 D.基数排序12.已知一组关键字为25,48,36,72,79,82,23,40,16,35，其中每相邻两个为有序子序列。对这些子序列进行一趟两两归并的结果是( )A.25,36,48,72,23,40,79,82,16,35 B.25,36,48,72,16,23,40,79,82,35C.25,36,48,72,16,23,35,40,79,82 D.16,23,25,35,36,40,48,72,79,8213.设有序表的关键字序列为1，4，6，10，18，35，42，53，67，71，78，84，92，99，当用二分查找法查找健值为84的结点时，经（ ）次比较后查找成功。A.2 B. 3 C. 4 D. 1214以下说法正确的是 （ ）A.查找表中数据元素的任何数据项都可以作为关键字。B.采用二分查找法对有序表进行查找总比采用顺序查找法对其进行查找要快C.二叉排序数的查找和二分查找时间的性能相同。D.最佳二叉排序树一定是平衡二叉树15.倒排文件的主要优点是( )A.便于进行插入和删除运算 B.便于进行文件的恢复C.便于进行多关键字查询 D.节省存储空间二、填空题1.抽象数据类型的特点是将_和_封装在一起，从而现实信息隐藏。2.从顺序表中删除一个元素时，表中所有在被删元素之后的元素均需_一个位置。3.在队列中，允许进行插入操作的一端称为_，允许进行删除操作的一端称为_。4.对于顺序栈而言，在栈满状态下，如果此时再做进栈运算，则会发生“_”。5.设S1=good,S2= ,S3=book，则S1，S2和S3依次联接后的结果是_。6.假设三维数组A1098按行优先顺序存储，若每个元素占3个存储单元，且首地址为100，则元素A987的存储地址是_。7.已知在一棵含有n个结点的树中，只有度为k的分支结点和度为0的叶子结点，则该树中含有的叶子结点的数目为_。8.能够成功完全拓扑排序的图一定是一个_。9.如果在排序前，关键字序列已接近正序或逆序，则在堆排序和快速排序两者之中，选用_较为适当。10.散列文件删除记录时，仅需对被删记录_即可。三、解答题1.假设通信电文使用的字符集为a,b,c,d,e,f，名字符在电文中出现的频度分别为：34，5，12，23，8，18，试为这6个字符设计哈夫曼编码。请先画出你所构造的哈夫曼树(要求树中左孩子结点的权值小于右孩子结点的权值)，然后分别写出每个字符对应的编码。2.已知两个45的稀疏矩阵的三元组表分别如下：014160113212218122222342522569342283342544251请画出这两个稀疏矩阵之和的三元组表。3.从空树起，依次插入关键字40，8，90，15，62，95，12，23，56，32，构造一棵二叉排序树。(1)画出该二叉排序树(2)画出删去该树中元素值为90的结点之后的二叉排序树。四、算法设计题1.假设以带头结点的单循环链表作非递减有序线性表的存储结构。请设计一个时间复杂度为O(n)的算法，删除表中所有数值相同的多余元素，并释放结点空间。例如：(7，10，10，21，30，42，42，42，51，70)经算法操作后变为(7，10，21，30，42，51，70)2稀疏矩阵用三元组的表示形式，试写一算法实现两个稀疏矩阵相加，结果仍用三元组表示。3假设一个算术表达式中可以包含三中括号：圆括号“（”和“）”，方括号“”和“”以及花括号与“”和“”，且这三种括号可按任意的次序嵌套试用，如（. . . . . . . .( . . . .)。试利用栈的运算编写判断给定表达式中所含括号是否正确 配对出现的算法（可设表达式已存入字符型数组中）。内蒙古财经学院期末考试数据结构试卷（A）一、 单项选择题（110=10分）：、对于一个N个顶点的图,若采用邻接矩阵存储,则矩阵的大小为_ (A) N2 (B) N (C) N+1 (D) N-1 、每次从无序表中取一个元素,把它插到有序表的合适位置,此种排序为_; 每次从无序表挑选出一个最大或最小的,把它与第一个位置或最后一个位置交换,此种排序为_;每次比较两个相邻的元素,若出现逆序,则交换这两个元素的位置, 此种排序为_;每次把相邻的两个有序表合成一个有序表的方法是_. (A) 堆排序 (B)快速排序 (C)插入排序 (D) 交换排序 (E) 基数排序 (F)冒泡排序 (G)希尔排序 (H)归并排序、解决散列中出现冲突问题的常采用的方法是_ (A)数字分析法 、除留余数法、平方取中法 (B) 数字分析法 、除留余数法、线性探测法 (C)数字分析法、线性探测法、双散列法 (D) 线性探测法、二次探测法、链地址法、已知某二叉树先序遍历序列为ABDCE则它可能的中序遍历序列为 。(A)BCADE (B)CBADE(C)BEACD (D)BDAEC5、若树中用一个分支把两个结点连接起来，则 。（A）不一定出现环 （B）一定出现环（C）使树的度数增一 （D）前面说法都不正确、设散列地址空间为0-M-1， K为表项的关键码，散列函数采用除留余数法，HASH（K）= K % P 。为减少冲突的频率，一般P为_ (A) M (B) 小于M的最大质数 (C) 大于M的最大质数 (D) 小于M的最大合数、在一般情况下，将递归转化为非递归算法应该设置（ ）（）栈 （）队列 （）栈或队列 （）数组二、判断题：（110=10分）、若有一个结点是二叉树中某个子树的中序遍历的最后一个结点，则它一定是该子树的子树前序遍历的最后一个结点。（ ）、邻接表只能用于有向图的存储, 邻接矩阵对于有向图和无向图的存储都适用. （ ）、设N为哈夫曼树的叶子结点数目，则该哈夫曼树共有2*N+1个结点。 （ ）、二叉树的中序遍历的和后序遍历可以唯一决定一棵二叉树 （ ）、线性表的逻辑顺序与物理顺序总是一致的。 （ ）、带表头的单链表比不带表头的单链表操作更简单。 （ ）、有N ( N 1 ) 个顶点的无向连通图至少有N-1条边. （ ）、外部排序只能选用归并排序 （ ）、快速排序和冒泡排序都是不稳定排序 （ ）、二叉树是特特殊的树 （ ）四、简答题：（30分）1、线性表有两种存储结构：一是顺序表，二是链表。试问：（1）如果有n个线性表同时存在，并且在处理过程中各表的长度会动态变化，线性表的总数也会自动地改变。在此情况下，应选用哪种存储结构？为什么？（2）若线性表的总数基本稳定，且很少进行插入和删除，但要求以最快的速度存取线性表中的元素，那么应选用哪种存储结构？为什么？（5分）2、采用折半查找方法进行查找的数据文件应满足什么条件？（5分）3、设双向循环链表中结点的结构为（data , llink, rllink）,且不带表头结点。若想在指针p所指结点之后插入指针s 所指结点，则应执行怎样的操作？（5分）4、已知一棵二叉树的前序便历的结果是ABECDFGHIJ，中序便历的结果是EBCDAFHIGJ，试画出这棵二叉树。（5分）5、给定权值集合15，03，14，02，06，09，16，17，构造相应的霍夫曼树，并计算它的带权外部路径长度。（5分）五、由如下的网络邻接矩阵，画出一棵最小生成树。（7分）六、给定一个关键字序列24，19，32，43，38，6，13，22，请写出快速排序第一趟的结果，堆排序时所建的初始堆，归并排序的全过程。然后回答上述三种排序方法中哪一种使用的辅助空间最少？在最坏情况下哪一种方法的时间复杂度最差？（10分）七、编写程序（33分）、统计二叉树结点的个数的算法。（11分）、设一个带表头结点的单链表中所有元素结点的数据值无序排列，试编写一个函数，删除表中值为X的元素（若存在）。（12分）3、写出冒泡排序算法（10分）注：试卷与答题纸一起交内蒙古财经学院期末考试 数据结构试卷(A)答案一、 单项选择题：、(A)、(CDFH)、D、D、C、B 、A二、判断题：、 ( X ) 、 ( X ) 、 （ V ）、 （ X ）、 （ V ）、 （ V ）、 （ V ）、 （ V ）、 （ X ）、 （ V ）四、简答题：、(1)链表 (2) 顺序表、顺序存储,且有序、s-rlink=p-rlink; s-llink=p; p-rlink-llink=s; p-rlink=s;4、5、wpl=229 树的根权值为82五、包含 6 7 11 10 12 COST=46六、快速排序的第一趟结果 22 19 6 13 24 32 43 38 小顶堆 6 19 13 22 38 32 24 43大顶堆 43 38 32 22 24 6 13 19归并结果 19 24 32 43 6 38 13 22 6 13 19 22 24 32 38 43 七、：1、template class BinTreeNodefriend class BinTree; Type data; BinTreeNode *leftchild,*rightchild;template class