《《数据结构》模拟试卷1》由会员分享，可在线阅读，更多相关《《数据结构》模拟试卷1（7页珍藏版）》请在金锄头文库上搜索。
1、数据结构数据结构模拟试卷模拟试卷 1 1不要为已消尽之年华叹息，必须正视匆匆溜走的时光。 布莱希特数据结构模拟试卷 1一、 单项选择题（本大题共 15 小题，每小题 2 分，共 30 分）在每小题列出的四个备选答案中，选出一个正确的答案，并将其号码填在题干后的括号内。错选或未选均无分。1. 线性表定义为 ( )A. 一个无限序列，可以为空 B. 一个无限序列，不能为空C. 一个有限序列，可以为空 D. 一个有限序列，不能为空2. 以二叉链表作为二叉树的存贮结构时，在具有 n 个结点的二叉链表中(n0)，空指针域的个数为 ( )A2n-1 B. n+1 C. n-1 D. 2n+13. 若一个序
2、列的进栈顺序为 1,2,3,4, 那么不可能的出栈序列是 ( )A. 4,2,3,1 B. 3,2,1,4 C. 4,3,2,1 D. 1,2,3,44. 具有 65 个结点的完全二叉树其深度为（根的层次号为 1） ( )A. 8 B. 7 C. 6. D. 55. 下列排序算法中, 排序在每趟结束后不一定能选出一个元素放到其排好的最终位置上的算法是 ( )A. 选择排序 B. 冒泡排序 C. 归并排序 D. 堆排序6. 设有向图有 n 个顶点和 e 条边，进行拓扑排序时，总的计算时间为 ( )A. O(nlog2e) B. O(elog2n) C. O(en) D. O(n+e)7. 如果要
3、求一个线性表既能较快的查找，又能适应动态变化的要求，则可采用的查找方法是 ( )A.顺序 B. 分块 C. 折半 D. 其它8. 链表不具有的特点是 ( )A. 所需空间与线笥表成正比 B. 不必事先估计存储空间C. 插入删除时不需移动元素 D. 随机访问9. 设有两个子串 S 和 T, 求 T 在 S 中首次出现的位置的运算称为 ( ) A. 连接 B. 求子串 C. 模式匹配 D. 求串长10.设有 98 个元素,采用二分法查找时,最大比较次数是 ( )A. 49 B. 15 C. 20. D. 711.如果以链表作为栈的存储结构,则出栈操作时 ( )A. 必须判别栈是否为空 B. 判别栈
4、元素的类型C. 必须判别栈是否为满 D. 对栈不必作任何判别12.下列存储表示中,哪一个不是树的存储形式 ( )A.双亲表示法 B. 孩子链表表示法C. 顺序存储表示法 D. 孩子兄弟表示法13.对 n 个记录的文件进行堆排序，最坏情况下的执行时间为 ( )A. O(log2n) B. O(nlog2n) C. O(n) D. O(n2)14.一个记录的关键字为（46，79，56，38，42，88） ，采用快速排序以第一个记录为基准得到的第一次划分结果为 ( )A.(38,42,46,56,79,88) B.(42,38,46,79,56,88)C.(42,38,46,56,79,88) D.
5、(42,38,46,56,79,88)15.设有向图有 n 个顶点和 e 条边，进行拓扑排序时，总的计算时间为 ( )A. O(nlog2e) B. O(ne) C. O(en) D. O(n+e)二、填空题（本大题共 10 小题，每小题 2 分，若有两个空格，每个空格 1 分，共 20 分）不写解答过程，将正确的答案写在每小题的空格内。错填或不填均无分。1.在一个算法中，一条语句重复执行的次数称为_。2数据结构的三个要素是数据的逻辑结构、 (1) 和 (2) 。3在单链表中，指针 p 所指结点为最后一个结点的条件是 。4带头结点的单链表中，除头结点外，任一结点的存储位置（地址）是在 。5多个
6、值相同的元素只分配一个存储空间，零元素不分配空间，称为 。6已知二叉树的前序遍历序列为 ABDCEFG，中序遍历序列为DBCAFEG，则后序遍历序列为 。7如要将序列52,18,25,70,96,72,75建成小根堆，则只需把18 与 相互交换。8利用直接选择排序算法对 n 个记录进行排序，在最坏情况下，记录交换的次数为 。9由二叉树的 (1) 序列或 (2) 序列可以唯一确定一棵二叉树。10文件的基本操作主要是指 (1) 和 (2) 。三、解答题（本大题共 4 小题，每小题 5 分，共 20 分）1 已知一组关键字为25,7,32,98,93,17,49,93,27对以上关键字进行冒泡排序，
7、写出每一次排序结果的排列次序（5分） 。2 设有一组关键码68,31,120,49,98,53需插入到表长为 12 的散列表中(1) 设计一个适当的散列函数；（2 分）(2)用设计的散列函数将上述关键码插入散列表。画出建好的散列表结构（假定用线性探测法解决冲突） ；（3 分）3. 已知序列7,8,5,12,4,7,给出二叉排序树的构造过程。 （5分）4. 分别按前序、中序、后序遍历下图所示的二叉树，给出相应的结点序列（5 分） 。四、算法阅读题（本大题共 4 小题，每小题 5 分，共 20 分）1下列算法是对一个用链表表示的文件进行直接选择排序，请填入合适的内容，使其成为一个完整的算法。voi
8、d SelectSort(LinkList head) /链表结构的直接选择排序（降序）ListNode * p=head；/p 为未排序的第一个结点指针while(p!=NULL) m=p; /m 为当前最大值时遍历未排序表的指针pos=p; /pos 为当前最大值结点指针while(m-next!=NULL) if( (1) ) q=m; pos=m-next; /q 为 pos 的前趋(2) ；if(pos!=p) (3) ;if(p=head)(4) ;else(5) ;s=pos;else s=p; p=p-next; /s 为 p 的前趋2. 用顺序存储结构实现将两个有序表合并成一
9、个有序表，合并后的结果不另设新表存储，写出算法的空缺部分。说明：A,B 为整型有序表，合并后的结果仍放在 A 中。void merge(SeqList * A, SeqList B);不要为已消尽之年华叹息，必须正视匆匆溜走的时光。 布莱希特 int n ,m ;n=A-length; m=B.length;/A,B 表的长度分别赋给n,mwhile(m0) if(n=0 | A-datan-1datan+m-1=B.datam-1;(1) ; else (2) ; n=n-1; (3) ;3.下列算法求出指定结点*p 在二叉排序树中所在的层次，请填上适当的内容，使之成为完整的算法。int S
10、earchLevel(BSTree T, BSTNode * p) int level=0;if(T=NULL)return(0);else leavl=level+1;while( (1) ) if(T-datadata) T=T-rchild;else (2) ;(3) ;return level;4. 设不带头结点单链表的结点是按关键字从小到大排列的，试对下面链表的查找算法填空，使之成为完整的算法。void search(LinkList head, DataType x)/有序链表上的查找，查找成功返回结点指针，否则返回NULLListNode * p=head;while( (1) if( (3) )return p;elsereturn NULL;五、算法设计题（本题共 10 分）试编写算法将一个带头结点单循环链表 A 分解为两个具有相同结构的链表 B、C，其中，B 表中结点是 A 表中值为奇数的结点，而 C 表中结点是 A 表中值为偶数的结点(要求利用原表结点空间)。第 1 页不要为已消尽之年华叹息，必须正视匆匆溜走的时光。 布莱希特
