数据结构模拟试卷、单选题(每小题 2 分，共 20分)1. 在数据结构的讨论中把数据结构从逻辑上分为()。A.内部结构与外部结构B.静态结构与动态结构C. 线性结构与非线性结构D. 紧凑结构与非紧凑结构2. 采用线性链表表示一个向量时，要求占用的存储空间地址()。A. 必须是连续的B. 部分地址必须是连续的C.一定是不连续的D. 可连续可不连续3. 采用顺序搜索方法查找长度为 n 的顺序表时，搜索成功的平均搜索长度为( )。A. nB. n/2 C. (n-1)/2 D. (n+1)/24. 在一个单链表中，若q结点是p结点的前驱结点，若在 q与p之间插入结点s,则执行()。A. s Tlink = p Tlink; p T|i=ks;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中，每一个数组元素 Aij占用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, 1B. 2, 4, 3, 1C. 1, 2, 3, 4D. 3, 2, 1, 410. 在循环队列中用数组 A0.m-1存放队列元素，其队头和队尾指针分别为front和rear，则当前队列中的元素个数是()。A. (front - rear + 1) % mB. (rear - front + 1) % m C. (front - rear + m) % mD. (rear - front + m) % m二、判断题(每小题 2 分，共 20分)( ) 1. 算法的运行时间涉及加、减、乘、除、转移、存、取等基本运算，要想准确地计算总运算时间是不可行的。( ) 2. 二维数组是数组元素为一维数组的线性表，因此二维数组元素之间是线性结构。( ) 3. 线性结构只能用顺序存储方式存放，而非线性结构只能用链式方式存放。( ) 4. 在单链表中，头结点是必不可少的。( ) 5. 栈和队列都是顺序存取的线性表，但它们对存取位置的限制不同。( ) 6. 如果一个二叉树中没有度为一的结点，则必为满二叉树。( ) 7. 在一个大根堆中，最小元素不一定在最后。( ) 8. 在一个有向图中，所有顶点的入度之和等于所有顶点的出度之和。( ) 9. 只要还有可用空间，链栈和链队就不会出现栈满和队满的情况。( ) 10. 内部排序是指排序过程在内存中进行的排序。三、填空题(每小题 2 分，共 32分)1. 对于一个单链表存储的线性表，假定表头指针指向链表的第一个结点，则在表头插入结点的时间复杂度为，在表尾插入结点的时间复杂度为 。2. 假定一棵三叉树(即度为 3 的树)的结点个数为 50，则它的最小高度为 ，假定树根结点为第 0层。3. 一棵高度(假定树根结点为第 0层)为 4的完全二叉树中的结点数最少为 个，最多为 个。4. 在一个具有 n 个顶点的无向图中，要连通所有顶点则至少需要 条边。5. 从有序表 (12,18,30,43,56,78,82,95)中分别折半查找 43 和 56元素时，其查找长度分别为 和。6. 对一棵二叉搜索树进行中序遍历时，得到的结点序列是一个 。7. 在散列表中，处理冲突的方法为 法和法(写出两种即可) 。8. 在堆排序的过程中，对任一分支结点进行调整运算(即调整为子堆的过程)的时间复杂度为，整个堆排序过程的时间复杂度为9. 快速排序在平均情况下的时间复杂度为 ，在最坏情况下的时间复杂度为 10. 在归并排序中，对n个记录进行归并的趟数为 四、简答题(每小题4分，共16分)1. 给定二叉树的两种遍历序列，分别是：前序遍历序列：D，A，C，E，B，H，F，G，I ；中序遍历序列：D，C，B，E，H，A，G，I，F，试画出二叉树T2假定一个线性表为(32,75,29,63,48,94,25,46,18,70)，散列地址空间为 HT13，若采用除留余数法构造散列函数和线性探测法处理冲突，试 求岀每一元素在闭散列表中的初始散列地址和最终散列地址，画岀最后得到的散列表，求岀平均查找长度。3. 已知一组记录为(46,74,53,14,26,38,86,65,27,34)，给出采用希尔排序法进行排序时每一趟的排序结果。4、已知无向图如图1所示：(1) 给岀图的邻接矩阵。(2) 画岀：用普里姆算法，以顶点 V1为岀发点，构造最小生成树的过程五、算法设计题(每小题6分，共12分)1 .创建一 n个整数的单链表，并在单链表第 i个元素之后插入一元素 k2. 有一无序记录序列，请用直接插入排序算法对其排序。数据结构模拟试卷一参考答案三、单选题（每小题2分，共20分)1. C 2. D 3. D 4.D5. B6. B 7. C判断题（每小题2分，共20分)1. V 2. X 3. X 4.X5. V6.X 7. V填空题（每小题2分，共32分)8. A8. V9. C 10. D10.1.0(1)2. 0(n)3. 44. 165.316. n-112. O(log2n)13.O(nlog2n) 14. O(nlog2n)7. 1215. 0(n2)8.39.有序序列 10.链接16. log2n11.开放定址四、简答题（每小题4分，共16分）1.2.123456789101112132918324648756325947029941832467048756325平均查找长度 ASL=(1+2+1+1+1+4+1+1+1+1)/10=7/53.第一趟（k=n/2)(46745314263886652734)第二趟（k=k/2)(38745314264686652734)第三趟（k=k/2)(26142734384653658674)排序结果(14262734384653657486)4.011100101010110111(1)邻接矩阵=101001011001卫01110 一构造最小生成树的过程如下:(b)五、算法设计题（每小题6分，共12分）（略）