数据结构模拟题(今天练习)

数据结构模拟卷一、选择题1．下面关于线性表的叙述错误的是（D）。(A)线性表采用顺序存储必须占用一片连续的存储空间(B)线性表采用链式存储不必占用一片连续的存储空间(C)线性表采用链式存储便于插入和删除操作的实现(D)线性表采用顺序存储便于插入和删除操作的实现2．设顺序循环队列Q[0：M-1]的头指针和尾指针分别为F和R，头指针F总是指向队头元素的前一位置，尾指针R总是指向队尾元素的当前位置，则该循环队列中的元素个数为（D）。0123456789ABCRF0123456789CDABFR（2-8+10）%10=4(A)R-F(B)F-R(C)(R-F+M)％M(D)(F-R+M)％M3．设某棵二叉树的中序遍历序列为ABCD，前序遍历序列为CABD，则后序遍历该二叉树得到序列为（A）。(A)BADC(B)BCDA(C)CDAB(D)CBDA4．设某完全无向图中有n个顶点，则该完全无向图中有（A）条边。(A)n(n-1)/2(B)n(n-1)(C)n2(D)n2-15．设一组初始记录关键字序列(5，2，6，3，8)，以第一个记录关键字5为基准进行一趟快速排序的结果为（C）。(A)2，3，5，8，6(B)3，2，5，8，6(C)3，2，5，6，8(D)2，3，6，5，8二、简答题1、什么是数据结构？列举5种数据结构栈，图，串，队列，二叉树，堆，链表，哈希表，数组，树2、链式结构有什么优缺点？举例说明链式结构有哪些应用链表，邻接表，链式队列，链栈，线索二叉树ARR三、应用题1、设指针变量p指向双向链表中结点A，指针变量q指向被插入结点B，要求给出在结点A的后面插入结点B的操作序列（设双向链表中结点的两个指针域分别为llink和rlink）。q.rlink=p.rlink;p.rlink=q;q.llink=p;q.rlink.llink=q;2、设有无向图G（如下图所示），要求给出用普里姆算法构造最小生成树所走过的边的集合。(1,3)(2,3)(3,5)(5,6)(4,6)2+3+4+1+1=113、设有一组初始记录关键字为(45，80，48，40，22，78)，要求构造一棵二叉排序树并给出构造过程。四、算法设计题1．设有一组初始记录关键字序列（K0，K1，…，Kn-1），要求设计一个算法能够在O(n)的时间复杂度内将线性表划分成两部分，其中左半部分的每个关键字均小于Kn-1，右半部分的每个关键字均大于等于Kn-1。publicvoidfun(intk[]){454080224878}