数据结构期末试卷

PAGEAPAGE1第页中南林业科技大学课程重修考试试卷课程名称：数据结构；考试时间：100分钟装订线(答题不得超过此线)计算机科学与技术专业班级1、2，班年级2011姓名学号装订线(答题不得超过此线)试卷得分表题号一二三四五六总分应得分20203030100实得分一、单项选择题(在每小题的四个备选答案中，选出一个正确答案，并将正确答案的序号填在题干的括号内。每小题2分，共20分)1．在数据结构中，从逻辑上可以把数据结构分为（）。A．动态结构和静态结构B．紧凑结构和非紧凑结构C．线性结构和非线性结构D．内部结构和外部结构2.某线性表中最常用的操作是在最后一个元素之后插入元素和删除第一个元素，则最节省运算时间的存储结构是（）。A.单链表B.双链表C.仅有头指针的单循环链表 D.仅有尾指针的单循环链表3.下面关于串的叙述中，正确的是（）。A.串是一种特殊的线性表 B.串中元素只能是字母C.空串就是空白串 D.串的长度必须大于零4.若一棵二叉树有10个度为2的结点，5个度为1的结点，则度为0的结点数是（）。A.9 B.11C.15 D.不确定5.无论待排序列是否有序，排序算法时间复杂度都是O(n2)的排序方法是（）。A.快速排序 B.归并排序C.冒泡排序 D.直接选择排序6.已知二叉排序树G，要输出其结点的有序序列，则采用的遍历方法是（）。A.按层遍历 B.前序遍历C.中序遍历 D.后序遍历7.当采用分块查找时，数据的组织方式为（）。A.数据分成若干块，每块内数据有序B.数据分成若干块，每块中数据个数必须相同C.数据分成若干块，每块内数据有序，块间是否有序均可D.数据分成若干块，每块内数据不必有序，但块间必须有序8．在以下的叙述中，正确的是（）。A．线性表的顺序存储结构优于链表存储结构B．二维数组是其数据元素为线性表的线性表C．栈的操作方式是先进先出D．队列的操作方式是先进后出9.在一个无向图中，所有顶点的度数之和等于所有边数的（）倍。A．1/2B．1C．2D．410.堆是一种有用的数据结构。下列关键码序列（）是一个堆。A．94，31，53，23，16，72B．94，53，31，72，16，23C．16，53，23，94，31，72D．16，31，23，94，53，72二、填空题(每小题2分，共计20分)1．在数据的逻辑结构和存储结构中，与计算机无关的是。2.在一个长度为n的向量中删除第i个元素(1≤i≤n)时，需向前移动_____个元素。3．设栈S和队列Q的初始状态皆为空，元素a1，a2，a3，a4，a5和a6依次通过一个栈，一个元素出栈后即进入队列Q，若6个元素出队列的顺序是a3，a5，a4，a6，a2，a1则栈S至少应该容纳个元素。4.具有n个结点的二叉树，采用二叉链表存储，共有个空链域。5．在双向链表中，每个结点有两个指针域，一个指向其结点，另一个指向其后继结点。6.在无向图G的邻接矩阵A中，若A[i][j]等于1，则A[j][i]等于。7.在散列存储中装填因子的值越小，则。8．设T和P是两个给定的串，在T中寻找等于P的子串的过程称为。9．一组记录的关键字为(46，79，56，38，40，84)，则利用快速排序的方法，以第一个记录为基准得到的一次划分结果为。10．有向图G如下图所示，它的两个拓扑排序序列分别为______和______。三、简答题（每小题6分，共计3０分）1．已知一棵二叉树的前序遍历和中序遍历序列分别为：ABCDEFG和CBDAEGF，请画出此二叉树，并给出后序遍历序列。2．设散列函数为H(key)=key％11，散列地址空间为0～10，对关键字序列(27，13，55，32，18，49，24，38，43)用线性探查法解决冲突，构建散列表。现已有前4个关键字构建的散列表如下所示，请将剩余5个关键字填入表中相应的位置。3．已知如下图所示的带权无向图，请画出用普里姆算法从顶点1开始的最小生成树的构造过程。4．写出下图从顶点A出发进行深度优先搜索与广度优先搜索的遍历序列。（一个顶点有多个未访问的邻接点时按字典序选择）AABCFDHGE深度优先搜索序列：广度优先搜索序列：5．给出下列递归过程的执行结果。（4分）voidunknown(intw){if(w){unknown(w-1);for(inti=1;i<=w;i++)cout<<w;cout<<endl;}