最新《数据结构》期末考试卷 -B卷.doc

《最新《数据结构》期末考试卷 -B卷.doc》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、__________________________________________________东莞理工学院城市学院（本科）试卷（B卷）2016-2017学年第二学期开课单位：计信系，考试形式：闭卷，允许带入场科目：数据结构班级：15级软件工程1∽6班，姓名：学号：题序一二三四总分得分评卷人一、填空题（每题2分，共12分）1、数据结构在计算机中基本存储方式有结构和结构。2、栈(又称为堆栈)是操作受限的线性结构，其操作的基本原则是，插入和删除元素的一端称为。3、深度为k（根的深度为1）的完全二叉树

2、至少有___________个结点，至多有_____________个结点。4、对于一个有n个顶点的完全无向图，具有条边；而对于一个有n个顶点的完全有向图，具有条弧。5、在进行排序时，最基本的操作是和。6、哈希函数是一种映象，是从到的一种映象。二、单项选择题（请将答案写在题目后的括号中。每题2分，共40分）1、下面结构中，不属于数据逻辑结构的是（）。（A）线性链表（B）树形结构（C）线性结构（D）网状结构2、下面说法正确的是（）。（A）数据元素是数据的最小单位（B）数据项是数据的基本单位（C）数据结

3、构是带有结构的各数据项的集合收集于网络，如有侵权请联系管理员删除__________________________________________________（D）上述说法都是错误的3、有下列算法，其时间复杂度是（）。x=1;while(x<=n)x=x*2;}（A）O(n)（B）O(n2)（C）O(㏒2n)（D）O(n㏒2n)4、线性表若采用链式存储结构，要求内存中可用存储单元的地址是（）。（A）必须是连续的（B）部分地址必须是连续的（C）一定是不连续的（D）连续或不连续都可以5、设p是非空

4、单链表中结点q的直接前驱结点，删除q的正确操作是（）。（A）p->next=q->next；free(p);（B）p->next=q->next；free(q);（C）q->next=p->next；free(p);（D）q->next=p->next；free(q);6、栈和队列的共同点时（）。（A）都是先进先出（B）都是后进先出（C）只允许在端点处插入和删除元素（D）没有共同点7、设有一个栈顶指针为top的顺序栈S，top为0时表示栈空，则向堆栈S中压入一个元素x执行的操作是（）。（A）S[to

5、p++]=x；（B）S[++top]=x；（C）S[--top]=x；（D）S[top--]=x；8、设循环队列Q的最多元素个数为m，队尾指针是rear，队首指针是front，则队列为满的条件是（）。（A）Q.rear==Q.front；（B）Q.rear!=Q.front；（C）(Q.rear+1)%m!=Q.front；（D）(Q.rear+1)%m==Q.front；9、广义表((a),((b),c),(((d,e),(a,b)))))的长度是，深度是。（）（A）4,4（B）4,5（C）3,5

6、（D）3,410、有一个12阶下三角矩阵A，上三角的所有元素均为0，A[0][0]的地址是BA，若每个元素占3个存储单元，采用行优先压缩存储，则A[6][5]的地址是（）。（A）BA+75（B）BA+78（C）BA+81（D）BA+84收集于网络，如有侵权请联系管理员删除__________________________________________________11、在二叉树中，指针P所指的结点是非叶子结点的条件是（）。（A）P->Lchild==NULL&&P->Rchild==NULL；

7、（B）P->Lchild!=NULL&&P->Rchild!=NULL；（C）P->Lchild==NULL&&P->Rchild!=NULL；（D）P->Lchild!=NULL

8、

9、P->Rchild!=NULL；12、将一棵一般的树转换为二叉树后，这棵二叉树的形态是（）。（A）唯一的（B）有多种，但根结点都没有左子结点（C）有多种（D）有多种，但根结点都没有右子结点13、设由n（n≥2）个权值都互不相同的字符构成的哈夫曼树，关于该树的叙述中，错误的是（）。（A）该树一定是一棵完全二叉树（B）树中

10、一定没有度为1的结点（C）树中两个权值最小的结点一定是兄弟结点（D）树中任一非叶子结点的权值一定不小于下一层任一结点的权值14、以下描述中，关于无向图邻接矩阵的特性不正确的是（）。（A）邻接矩阵是对称方阵。（B）若顶点vi在顶点数组中的存储位置为i，则其度数是第i行的非0元素的个数。（C）无向图的边数是上(或下)三角形矩阵中非0元素个数。（D）图的度是矩阵中非0元素个数。15、对于有向图，下述关于图、顶点的度、入度、出度的论述中，错误的是（）。（A）顶点的度是顶点的入