数据结构模拟试卷一.doc

数据结构模拟试卷一.doc

ID:51767600

大小:71.00 KB

页数:4页

时间:2020-03-15

数据结构模拟试卷一.doc_第1页
数据结构模拟试卷一.doc_第2页
数据结构模拟试卷一.doc_第3页
数据结构模拟试卷一.doc_第4页
资源描述:

《数据结构模拟试卷一.doc》由会员上传分享,免费在线阅读,更多相关内容在教育资源-天天文库

1、数据结构模拟试卷一一、单选题(每小题2分,共20分)1.在数据结构的讨论中把数据结构从逻辑上分为()。  A.内部结构与外部结构  B.静态结构与动态结构  C.线性结构与非线性结构  D.紧凑结构与非紧凑结构2.采用线性链表表示一个向量时,要求占用的存储空间地址()。  A.必须是连续的  B.部分地址必须是连续的  C.一定是不连续的  D.可连续可不连续3.采用顺序搜索方法查找长度为n的顺序表时,搜索成功的平均搜索长度为()。  A.n  B.n/2  C.(n-1)/2  D.(n+1)/24.在一个单链表中,若q结点是p

2、结点的前驱结点,若在q与p之间插入结点s,则执行()。  A.s→link=p→link;p→link=s;  B.p→link=s;s→link=q;  C.p→link=s→link;s→link=p;  D.q→link=s;s→link=p;5.如果想在4092个数据中只需要选择其中最小的10个,采用()方法最好。  A.冒泡排序  B.堆排序  C.直接插入排序  D.快速排序6.设有两个串t和p,求p在t中首次出现的位置的运算叫做()。  A.求子串  B.模式匹配  C.串替换  D.串连接7.在数组A中,每一个数组

3、元素A[i][j]占用3个存储单元,行下标i从1到8,列下标j从1到10。所有数组元素相继存放于一个连续的存储空间中,则存放该数组至少需要的存储单元是()。  A.80  B.100  C.240  D.2708.将一个递归算法改为对应的非递归算法时,通常需要使用()。  A.栈  B.队列  C.循环队列  D.优先队列9.一个队列的进队列顺序是1,2,3,4,则出队列顺序为()。  A.4,3,2,1  B.2,4,3,1  C.1,2,3,4  D.3,2,1,410.在循环队列中用数组A[0..m-1]存放队列元素,其队头

4、和队尾指针分别为front和rear,则当前队列中的元素个数是()。  A.(front-rear+1)%m  B.(rear-front+1)%m  C.(front-rear+m)%m  D.(rear-front+m)%m二、判断题(每小题2分,共20分)()1.算法的运行时间涉及加、减、乘、除、转移、存、取等基本运算,要想准确地计算总运算时间是不可行的。()2.二维数组是数组元素为一维数组的线性表,因此二维数组元素之间是线性结构。()3.线性结构只能用顺序存储方式存放,而非线性结构只能用链式方式存放。()4.在单链表中,头

5、结点是必不可少的。()5.栈和队列都是顺序存取的线性表,但它们对存取位置的限制不同。()6.如果一个二叉树中没有度为一的结点,则必为满二叉树。()7.在一个大根堆中,最小元素不一定在最后。()8.在一个有向图中,所有顶点的入度之和等于所有顶点的出度之和。()9.只要还有可用空间,链栈和链队就不会出现栈满和队满的情况。()10.内部排序是指排序过程在内存中进行的排序。三、填空题(每小题2分,共32分)1.对于一个单链表存储的线性表,假定表头指针指向链表的第一个结点,则在表头插入结点的时间复杂度为________,在表尾插入结点的时间

6、复杂度为________。2.假定一棵三叉树(即度为3的树)的结点个数为50,则它的最小高度为________,假定树根结点为第0层。3.一棵高度(假定树根结点为第0层)为4的完全二叉树中的结点数最少为________个,最多为________个。4.在一个具有n个顶点的无向图中,要连通所有顶点则至少需要________条边。5.从有序表(12,18,30,43,56,78,82,95)中分别折半查找43和56元素时,其查找长度分别为________和________。6.对一棵二叉搜索树进行中序遍历时,得到的结点序列是一个___

7、_____。7.在散列表中,处理冲突的方法为________法和____________法(写出两种即可)。8.在堆排序的过程中,对任一分支结点进行调整运算(即调整为子堆的过程)的时间复杂度为________,整个堆排序过程的时间复杂度为________。9.快速排序在平均情况下的时间复杂度为________,在最坏情况下的时间复杂度为________。10.在归并排序中,对n个记录进行归并的趟数为________。四、简答题(每小题4分,共16分)1.给定二叉树的两种遍历序列,分别是:前序遍历序列:D,A,C,E,B,H,F,G

8、,I;中序遍历序列:D,C,B,E,H,A,G,I,F,试画出二叉树T。2假定一个线性表为(32,75,29,63,48,94,25,46,18,70),散列地址空间为HT[13],若采用除留余数法构造散列函数和线性探测法处理冲突,试求出每一元素在

当前文档最多预览五页,下载文档查看全文

此文档下载收益归作者所有

当前文档最多预览五页,下载文档查看全文
温馨提示:
1. 部分包含数学公式或PPT动画的文件,查看预览时可能会显示错乱或异常,文件下载后无此问题,请放心下载。
2. 本文档由用户上传,版权归属用户,天天文库负责整理代发布。如果您对本文档版权有争议请及时联系客服。
3. 下载前请仔细阅读文档内容,确认文档内容符合您的需求后进行下载,若出现内容与标题不符可向本站投诉处理。
4. 下载文档时可能由于网络波动等原因无法下载或下载错误,付费完成后未能成功下载的用户请联系客服处理。