资源描述：
《数据结构模拟试卷一.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]，若采用除留余数法构造散列函数和线性探测法处理冲突，试求出每一元素在
