20121A普教《数据结构》A 数据结构试题

《20121A普教《数据结构》A 数据结构试题》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、湖北文理学院2011－2012学年度下学期《数据结构与算法》试卷A专业：计算机科学与技术姓名：学号：班级：题目一二三四五总分满分1020182230100得分得分评卷人一、判断题（本题共10小题，每小题1分，共计10分）。（正确的打√，错的打×）1、顺序循环队列Q空的条件是：Q.front==Q.rear.()2、关键路径是始点到终点最小长度的路径。()3、序列（5,6,7,20,15,8,9,25,22，13）是一个堆。()4、在插入排序和选择排序中，若原始记录已基本有序，则较适合选用选择排序。()5、顺序表是随机存取，存取操作的

2、时间为O（1）。()6、已知一棵二叉树的先序序列和后序序列，一定能构造出该二叉树。()7、有向图用邻接矩阵表示后，顶点i的出度等于邻接矩阵中第i行的元素个数。()8、归并排序的时间性能不随记录序列中关键字的分布而改变（与初始状态无关）。()9、在数据结构中，数据的基本单位是数据项。（）10、对任意一个图，从某顶点出发进行一次广度优先或深度优先遍历，可访问图的所有顶点。()得分评卷人二、填空题（本题共10小题，每小题2分，共计20分）。（请将正确答案填入空格内，答案是确定和唯一的）1、任意一棵具有n个结点的二叉树，若它有m个叶子，则该

3、二叉树上度为1的结点数为_____个。2、常用算法的描述方法有：自然语言、、和流程图。3、某二叉树的先根遍历序列为IJKLMNO，中根遍历序列为JLKINMO，则该二叉树中根结点的右孩子是。第6页共6页4、堆排序的时间复杂性为，空间复杂性为。5、二维数组A[6，7]，按行优先存储，每个元素占2个字节,A基址为600,则元素A[4,5]的存储地址是。6、对广义表C=（a,（b,c,d））的运算Tail(Tail(Head((Tail(C))))的结果是。7、设有一组初始关键字值序列为（49，81，55，36，44，88），则利用快速排

4、序的方法，以第一个关键字值为基准得到的一次划分为_________________________________________。8、图的存储结构主要有两种，分别是和。9、设一个顺序栈S，元素s1，s2，s3，s4，s5，s6依次进栈，如果6个元素的退栈顺序为s2，s3，s4，s6，s5，s1，则顺序栈的容量至少为________。10、对于一棵满二叉树，若有m个叶子，则树中结点数为____________。得分评卷人三、选择题（本题共18小题，每小题1分，共计18分）。（从下列答案中选出一个正确答案，并将对应的字母填入括号内）1

5、．.循环队列存储在数组元素A[0]至A[m]中，则入队时的操作为()。A.rear=rear+1B.rear=(rear+1)％(m-1)C.rear=(rear+1)％mD.rear=(rear+1)％(m+1)2.元素的进栈次序为a，b，c，d，e，则出栈中不可能的序列是（）。A.a，b，c，d，eB.b，c，d，e，aC.e，a，b，c，dD.e，d，c，b，a3.在已知尾指针的单循环链表中，插入一个新结点使之成为首结点，其算法的时间复杂度为（）。A.O（1）B.O（log2n）C.O（n）D.O(n2)4.在有n个叶子的哈夫

6、曼树中，分支结点数为（）。A、nB、n-1C、n+1D、2n5.有4个顶点的无向完全图的边数为()。A.6B.12C.16D.206.若采用邻接矩阵法存储一个n个顶点的无向图，则该邻接矩阵是一个()。A.上三角矩阵B.稀疏矩阵C.对角矩阵D.对称矩阵7.从逻辑上可以把数据结构分为（　　）。A.动态结构、静态结构B.顺序结构、链式结构C.线性结构、非线性结构D.初等结构、构造型结构第6页共6页8.在单链表中，存储每个结点需要有两个域，一个是数据域，另一个是指针域，指针域指向该结点的（　　）。A.直接前趋B.直接后继C.开始结点D.终端

7、结点9.若用一个有6个单元的数组来实现循环队列，rear和front的初值分别为0和3。则从队列中删除一个元素，再添加两个元素后，rear和front的值分别为（　　）。A.1和5B.2和4C.4和2D.5和110．含有n个结点的二叉树采用二叉链表存储时，空指针域的个数为（　　）。A.n-1B.nC.n+1D.n+211．一个有序表为{13，18，24，35，47，50，62，83，90，115，134}，当二分查找（搜索）值为90的结点时，查找成功时的比较次数为（　　）。A.1B.2C.3D.412．已知一个单链表中，指针q指向指

8、针p的前趋结点，若在指针q所指结点和指针p所指结点之间插入指针s所指结点，则需执行（）。A.q→next=s；p→next=s；B.q→next=s；s→next=p；C.q→next=s；q→next=p；D.q→next=s；s→