大大数据结构试卷一及问题详解

《大大数据结构试卷一及问题详解》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、实用文档习题一一、 选择题(每小题2分，共20分)1．下列程序段的时间复杂度为（）。i=0，s=0；while(snext=p->next；

2、p->next=-s；(B)q->next=s；s->next=p；(C)p->next=s->next；s->next=p； (D)p->next=s；s->next=q；4．设输入序列为1、2、3、4、5、6，则通过栈的作用后可以得到的输出序列为（）。(A)5，3，4，6，1，2   (B)3，2，5，6，4，1(C)3，1，2，5，4，6    (D)1，5，4，6，2，35．设有一个10阶的下三角矩阵A（包括对角线），按照从上到下、从左到右的顺序存储到连续的55个存储单元中，每个数组元素占1个字节的存储空间，则A[5][4]地址与A[0]

3、[0]的地址之差为（）。(A)10    (B)19    (C)28    (D)556．设一棵m叉树中有N1个度数为1的结点，N2个度数为2的结点，……，Nm个度数为m的结点，则该树中共有（）个叶子结点。  7.二叉排序树中左子树上所有结点的值均（）根结点的值。(A)<    (B)>     (C)=     (D)!=标准文案实用文档8.设一组权值集合W=(15，3，14，2，6，9，16，17)，要求根据这些权值集合构造一棵哈夫曼树，则这棵哈夫曼树的带权路径长度为（）。(A)129  (B)219   (C)189  (D)2299.设

4、有n个关键字具有相同的Hash函数值，则用线性探测法把这n个关键字映射到HASH表中需要做（）次线性探测。(A)n2   (B)n(n+1)(C)n(n+1)/2(D)n(n-1)/210.设某棵二叉树中只有度数为0和度数为2的结点且度数为0的结点数为n，则这棵二叉中共有（）个结点。(A)2n   (B)n+l   (C)2n-1    (D)2n+l二、填空题(每空 2分，共50分)1.数据元素及其关系在计算机存储器内的表示称为          。2.假设某个带头结点的单链表的头指针为head，则判定该表为空表的条件是          。3

5、.栈是一种操作受限的线性结构，其操作的主要特征是          。若进栈序列为123，则不可能的出栈序列为          。4.已知广义表C=(a，(b，c)，d)，则：tail(head(tail(C)))=          。5.要在单链表中指针p所指向结点后插入s所指的结点，应顺序执行          和          语句。6.具有3个结点的二叉树有          种形态。7.一棵二叉树采用二叉链表存储，则必有          个指针域不空。8.对关键字序列<46，79，56，38，40，84>采用快速排序以位于最左

6、位置的对象为基准而得到的第一次划分结果为          。9.在哈希查找中，处理冲突的方法有          、再哈希法、          和建立公共溢出区。10.在堆排序过程中，由n个待排序记录建成初始堆需要进行          次筛选。11.已知二叉树中叶子结点数为50，则该二叉树的总结点数至少应有          个。标准文案实用文档12.一个具有n个顶点无向连通图最少有          条边，最多有          条边。13.图的深度优先搜索遍历算法类似于二叉树的          遍历，图的广度优先遍历算法类似于二叉树

7、的          遍历。14.在二叉排序树上进行          遍历，可以得到一个关键字的递增序列。15.在图G的邻接表表示中，每个顶点邻接表中所含的结点数，对于无向图来说等于该顶点的          ；对于有向图来说等于该顶点的          。16.若待排序序列中存在多个具有相同关键字的记录，若排序完成后这些记录的相对位置发生改变，则称该排序法是          。写出3种不稳定的排序法          、          、          。三、判断题(每小题1分，共10分)1.单链表的头结点是必不可少的。（）2.如

8、果一个二叉树中没有度为1的结点，则必为满二叉树。（）3．顺序存储结构只能用来存放线性结构，链式存储结构只能用来存放非线性结构。（）4.队