模拟试题3
一．选择题
1.当初始序列已按健值有序时，用直接插入算法进行排序，需要比较的次数为（ ）
A.n-1 B.log2n C. 2log2n D.n2
冒泡排序 | n2 | |
选择排序 | n2 | |
插入排序 | n2 | |
堆排序 | nlog n | |
归并排序 | nlog2n | |
快速排序 | n2 | |
希尔排序 | n2 | |
2.以下时间复杂性不是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. 12
5.静态查表与动态查表两者的根本差别在于( )…………………………………………….
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 8
8.在无向图中，所有顶点的度数之和是所有边数的（ ）倍。
A.0．5 B.1 C.2 D.4
9.深度为6的二叉树最多有( )个结点.
A.64 B.63 C.32 D.31
10．将含有83个结点的完全二叉树从根结点开始编号，根为1号，后面按从上到下、从左到右的顺序对结点编号，那么编号为41的双亲结点编号为 ( )
A.42 B.40 C.21 D.20
11.已知某二叉树的后序遍历序列是dabec,中序遍历序列是deabc,它的前序遍历序列是（ ）
A.acbed B.deabc C.decab D.cedba
12.设二叉树结点的先根序列、中根序列和后根序列中，所有叶子结点的先后顺序( )
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.出数组]中元素的最大值和次最大值（本小题以数组元素的比较为标准操作）。
2..在数组]中查值为K的元素,若到则输出其位置i(1<=i<=n),否则输出0作为标志。
3.设有数组A[n],n>1,试设计一个算法,求数组A[n]的逆序。
模拟试题4
一、单项选择题
1.下面程序段的时间复杂度是( )
for(i=0;i<n;i++)
for(j=1;j<m;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==NULL B. Q.rear==NULL
C. Q.front==Q.rear D. Q.front!=Q.rear
5.设有两个串T和P，求P在T中首次出现的位置的串运算称作( )
A.联接 B.求子串 C.字符定位 D.子串定位
6.广义表A=(a,(b),(),(c,d,e))的长度为( )
A.4 B.5 C.6 D.7
7.一棵含18个结点的二叉树的高度至少为( )
A.3 B.4 C.5 D.6
8.已知二叉树的先序序列为ABDECF，中序序列为DBEAFC，则后序序列为( )
A.DEBAFC B.DEFBCA C.DEBCFA D.DEBFCA
9.无向图中一个顶点的度是指图中( )
A.通过该顶点的简单路径数 B.与该顶点相邻接的顶点数
C.通过该顶点的回路数 D.与该顶点连通的顶点数
10.在有向图中，所有顶点的入度之和是所有顶点出度之和的（ ）倍。
版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。
发表评论