搜索
模拟试题3一．选择题1.当初始序列已按健值有序时，用直接插入算法进行排序，需要比较的次数为（）A.n-1B.log2nC.2log2nD.n2冒泡排序n2选择排序n2插入排序n2堆排序nlogn归并排序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.2B.3C.4D.125.静态查找表与动态查找表两者的根本差别在于()…………………………………………….A.逻辑结构不同B.存储实现不同C.施加的操作不同D.数据元素的类型不同6．用顺序查找法对具有n个结点的线性表查找的时间复杂性量级为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.已知某二叉树的后序遍历序列是dabec,中序遍历序列是deabc,它的前序遍历序列是（）A.acbedB.deabcC.decabD.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,vj∈V，且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.找出数组A[1..n]中元素的最大值和次最大值（本小题以数组元素的比较为标准操作）。2..在数组A[1..n]中查找值为K的元素,若找到则输出其位置i(1=i=n),否则输出0作为标志。3.设有数组A[n],n1,试设计一个算法,求数组A[n]的逆序。模拟试题4一、单项选择题1.下面程序段的时间复杂度是()for(i=0;in;i++)for(j=1;jm;j++)A[i][j]=0；A.O(n)B.O(m+n+1)C.O(m+n)D.O(m*n)2.在单链表中，指针p指向元素为x的结点，实现“删除x的后继”的语句是()A.p=p-next;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==NULLB.Q.rear==NULLC.Q.front==Q.rearD.Q.front!=Q.rear5.设有两个串T和P，求P在T中首次出现的位置的串运算称作()A.联接B.求子串C.字符定位D.子串定位6.广义表A=(a,(b),(),(c,d,e))的长度为()A.4B.5C.6D.77.一棵含18个结点的二叉树的高度至少为()A.3B.4C.5D.68.已知二叉树的先序序列为ABDECF，中序序列为DBEAFC，则后序序列为()A.DEBAFCB.DEFBCAC.DEBCFAD.DEBFCA9.无向图中一个顶点的度是指图中()A.通过该顶点的简单路径数B.与该顶点相邻接的顶点数C.通过该顶点的回路数D.与该顶点连通的顶点数10.在有向图中，所有顶点的入度之和是所有顶点出度之和的（）倍。A.0．5B.1C.2D.411.在下列排序方法中，平均时间复杂度为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,35}C.{25,36,48,72,16,23,35,40,79,82}D.{16,23,25,35,36,40,48,72,79,82}13.设有序表的关键字序列为{1，4，6，10，18，35，42，53，67，71，78，84，92，99}，当用二分查找法查找健值为84的结点时，经（）次比较后查找成功。A.2B.3C.4D.1214．以下说法正确的是（）A.查找表中数据元素的任何数据项都可以作为关键字。B.采用二分查找法对有序表进行查找总比采用顺序查找法对其进行查找要快C.二叉排序数的查找和二分查找时间的性能相同。D.最佳二叉排序树一定是平衡二叉树15.倒排文件的主要优点是()A.便于进行插入和删除运算B.便于进行文件的恢复C.便于进行多关键字查询D.节省存储空间二、填空题1.抽象数据类型的特点是将____________和____________封装在一起，从而现实信息隐藏。2.从顺序表中删除一个元素时，表中所有在被删元素之后的元素均需____________一个位置。3.在队列中，允许进行插入操作的一端称为____________，允许进行删除操作的一端称为____________。4.对于顺序栈而言，在栈满状态下，如果此时再做进栈运算，则会发生“________”。5.设S1=good,S2=,S3=book，则S1，S2和S3依次联接后的结果是____________。6.假设三维数组A[10][9][8]按行优先顺序存储，若每个元素占3个存储单元，且首地址为100，则元素A[9][8][7]的存储地址是____________。7.已知在一棵含有n个结点的树中，只有度为k的分支结点和度为0的叶子结点，则该树中含有的叶子结点的数目为____________。8.能够成功完全拓扑排序的图一定是一个____________。9.如果在排序前，关键字序列已接近正序或逆序，则在堆排序和快速排序两者之中，选用____________较为适当。10.散列文件删除记录时，仅需对被删记录________即可。三、解答题1.假设通信电文使用的字符集为{a,b,c,d,e,f}，名字符在电文中出现的频度分别为：34，5，12，23，8，18，试为这6个字符设计哈夫曼编码。请先画出你所构造的哈夫曼树(要求树中左孩子结点的权值小于右孩子结点的权值)，然后分别写出每个字符对应的编码。2.已知两个4×5的稀疏矩阵的三元组表分别如下：014160113212218122－22234－2522569342283342544251请画出这两个稀疏矩阵之和的三元组表。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．假设一个算术表达式中可以包含三中括号：圆括号“（”和“）”，方括号“[”和“]”以及花括号与“{”和“}”，且这三种括号可按任意的次序嵌套试用，如（...[...{...}...[...]...]...(...