正文描述:《数据结构试题_试卷一_已填答案.docx》由会员上传分享,免费在线阅读,更多相关内容在教育资源-天天文库。
1、模拟试题一模拟试题一 一、选择题(30分) 1.组成数据的基本单位是( C)。 A)数据项 B)数据类型 C)数据元素 D)数据变量 2.线性表采用链式存储结构时,要求内存中可用存储单元的地址( D)。 A)必须是连续的 B)部分地址必须是连续的 C)一定是不连续的 D)连续或不连续都可以 3.在一个具有n个结点的有序单链表中插入一个新结点并仍然有序的时间复杂度是( B)。 A)O(1) B)O(n) C)O(n2) D)O(nlog2n)
2、4.栈结构通常采用的两种结构是( A)。 A)顺序存储结构和链表存储结构 B)散列方式和索引方式 C)链表存储结构和数组 D)线性链表结构和非线性存储结构 5.表达式a*(b+c)-d的后缀表达式是( B)。 A)abcd+- B)abc+*d- C)abc*+d- D)一十*abcd 6.栈和队列的共同特点是(C )。 A)都是先进先出 B)都是先进后出 C)只允许在端点处插入和删除元素 D)没有共同点 7.已知一棵二叉树前序遍历和中序遍历分
3、别为ABDEGCFH和DBGEACHF,则该二叉树的后序遍历为( B)。 A)GEDHFBCA B)DGEBHFCA C)ABCDEFGH D)ACBFEDHG 8.链表不具有的特点是( B), A)不必事先估计存储空间 B)可随机访问任一元素 C)插入删除不需要移动元素 D)所需空间与线性表长度成正比 9.在深度为5的满二叉树中,叶子结点的个数为( C)。 A)32 B)31 C)16
4、 D)15 10.最简单的交换排序方法是( D)。 A)快速排序 B)选择排序 C)堆排序 D)冒泡排序 11.数据结构是研究数据的( C)以及它们之间的相互关系。 A)理想结构,物理结构 B)理想结构,抽象结构 C)物理结构,逻辑结构 D)抽象结构,逻辑结构 12.线性表采用链式存储时,其地址( D)。 A)必须是连续的 B)部分地址必须是连续的 C)-定是不连续的 D)连续与否均可以 13.设循环队列Q[l...n-l
5、]的首尾指针为f和r,当插入元素时尾指针r加1,首指针F总是指在队列中第一个元素的前一个位置,则队列中元素计数为( D)。 A)r-f B)n-(r-f) C)(r-f+n)%n D)(f-r+n)%n 14.完成堆排序的全过程需要( A)个记录大小的辅助空间。 A)1 B)n C)nlog2n D)
6、_nlog2n_
7、 15.若给定的关键字集合为{20,15,14,18,21,36,40,10},一趟快速排序结束时,键值的排列为( A)。 A
8、)10,15,14,18,20,36,40,21 B)10,15,14,18,20,40,36,21 C)10,15,14,20,18,40,36,21 D)15,10,14,18,20,36,40,21 二、填空题(22分) 1.一棵完全二叉树的第5层有5个结点,则共有_____20_____个结点。 2.有向图G用邻接矩阵A{1…n,1...n}存储,其第i列的所有元素等于顶点i的____入度即ID(i)______。 3.设有一空栈,栈顶指针为IOOOH(十六进制),现有输入序列为1,2,3,4,
9、5,经过Push,Push,Pop,Push,Pop,Push,Push操作后,输出序列为___2,3,5,41. 4.在具有n(n≥1)个结点的k叉树中,有__n(k-l)+l个空指针。 5.模式中“ababbabbab”的前缀函数为_Next[j]=(0 1 1 23 1 2312)__。 6.设图G的顶点数为n,边数为e,第i个顶点的度数为D(vi),则e=__即边数与各项点的度数之间的关系)。 7.按___中序___遍历二叉树,可以得到按值递增的关键值序列,在下图所示的二叉树中,检索关键值85的过程中,需与85
10、进行比较的关键码序列为__509057 7585a__。 8.下列算法实现二叉树排序树上的查找,请在空格处填上适当的语句,完成上述功能。 bitreptr*bstsearch(bitreptr *t, keytypek) { if
显示全部收起