2018交大数据结构期末复习样卷带答案

第2页共4页上海交通大学继续教育学院网络教育——期末复习样卷答案课程名称：数据结构一、单项选择题（每题2分，共30分）包含64个结点的完全二叉树，其深度为（）(根的层次为1)。A、8 B、7 C、6 D、5关于算法的空间复杂度的理解错误的是（）。A.空间复杂度，即为算法的存储空间需求。B.空间复杂度是指算法在执行过程中所需要的最大的存储空间。C.空间复杂度，包括算法在执行过程中指令、常数、变量、输入数据，以及程序执行过程中所需要的辅助空间。D.算法的空间复杂度与算法无关。数据结构包括3个方面的内容，它们分别是（）。A、数据、数据元素、数据项B、数据元素、数据处理、算法实现C、数据元素、数据的逻辑结构、数据的存储结构D、数据的逻辑结构、数据的存储结构、数据的操作一个栈的入栈序列是a、b、c、d，则下列序列中不可能是栈的输出序列的是（）。A、acbd B、dcba C、acdb D、dbac将5个不同的数据进行插入排序，至多需要比较（）次。A.8 B.9 C.10 D.25栈和队列的共同点是（）。A.都是先进先出 B.都是先进后出C.只允许在端点处插入和删除元素 D.没有共同点设一组初始记录关键字序列(5，2，6，3，8)，以第一个记录关键字5为基准进行一趟快速排序的结果为（）。A、2,3,5,8,6 B、3,2,5,8,6 C、3,2,5,6,8 D、2,3,6,5,8设有一顺序栈S，元素s1,s2,s3,s4,s5,s6依次进栈，如果6个元素出线的顺序是s2,s3,s4,s6,s5,s1,则栈的容量至少应该是（）。A.2 B.3 C.5 D.6设某无向图中有n个顶点e条边，则该无向图中所有顶点的入度之和为（）。A、n B、e C、2n D、2e

设无向图G中有n个顶点e条边，则其对应的邻接表中的表头结点和表结点的个数分别为（）。A.n，e B.e，n C.2n，e D.n，2e下列关键字序列中，()是堆。A、16,72,31,23,94,53 B、94,23,31,72,16,53C、16,53,23,94，31,72 D、16,23,53,31,94,72以下说法错误的是（）。A.一般在哈夫曼树中，权值越大的叶子离根结点越近B.哈夫曼树中没有度数为1的分支结点C.若初始森林中共有n裸二叉树，最终求得的哈夫曼树共有2n-1个结点D.若初始森林中共有n裸二叉树，进行2n-1次合并后才能剩下一棵最终的哈夫曼树设有序表中有1000个元素，则用二分查找法查找元素X最多需要比较（）次。A、25 B、10 C、7 D、1[log2n]+1二叉树是非线性数据结构，所以（）。A.它不能用顺序存储结构存储 B.它不能用链式存储结构存储C.顺序存储结构和链式存储结构都能存储D.顺序存储结构和链式存储结构都不能使用对22个记录的有序表作折半查找，当查找失败时，至少需要比较()次关键字。A、3 B、4 C、5 D、6二、填空题（每空2分，共20分）在线性表中，元素ai(2≤i≤n)被称为是元素ai-1的后继。顺序栈用data[1..n]存储数据，栈顶指针是top,则值为x的元素入栈的操作是__data[++top]=x___。设有一个空栈，栈顶指针为1000H(十六进制)，现有输入序列为1，2，3，4，5，经过PUSH,PUSH,POP,PUSH,POP,PUSH,PUSH后，输出序列是23，而栈顶指针值是100CHH。设栈为顺序栈，每个元素占4个字节。一棵深度为6的满二叉树有31个分支结点和32个叶子。为了能有效地应用HASH查找技术，必须解决的两个问题是构造一个好的HASH函数和确定解决冲突的方法。大多数排序算法都有两个基本的操作：比较和移动。三、简答题（共30分）请解释名词：满二叉树、拓扑排序答：满二叉树：一棵深度为k且有个结点的二叉树。拓扑排序：由某个集合上的一个偏序得到该集合上的一个全序，该操作称为拓扑排序。在各种排序方法中，哪些是稳定的？哪些是不稳定的？各举三个即可。答：稳定：直接插入排序、折半插入排序、二路插入排序、表插入排序、起泡排序不稳定：直接选择排序、希尔排序、快速排序、堆排序假设用于通信的电文仅由8个字母组成，字母在电文中出现的频率分别为0.07，0.19，0.02，0.06，0.32，0.03，0.21，0.10。试为这8个字母设计哈夫曼编码。使用0～7的二进制表示形式是另一种编码方案。对于上述实例，比较两种方案的优缺点。一棵度为2的树与一棵二叉树有何区别？答：度为2的树从形式上看与二叉树很相似，但它的子树是无序的，而二叉树是有序的。即，在一般树中若某结点只有一个孩子，就无需区分其左右次序，而在二叉树中即使是一个孩子也有左右之分。给定二叉树的两种遍历序列，分别是：前序遍历序列：D，A，C，E，B，H，F，G，I；中序遍历序列：D，C，B，E，H，A，G，I，F，试画出二叉树，并写出该二叉树的后序遍历序列。后序遍历序列:B,H,E,C,I,G,F,A,D四、程序设计题（每题10分，共20分）设从键盘输入一整数的序列：a1,a2,a3，…，an,试编写算法实现：用栈结构存储输入的整数，当ai≠-1时，将ai进栈；当ai=-1时，输出栈顶整数并出栈。算法应对异常情况（入栈满等）给出相应的信息。答：#definemaxsize栈空间容量voidInOutS(ints[maxsize]){inttop=0;//top为栈顶指针，定义top=0时为栈空。for(i=1;i<=n;i++)//n个整数序列作处理。{scanf(“%d”,&x);//从键盘读入整数序列。if(x!=-1)//读入的整数不等于-1时入栈。if(top==maxsize-1){printf(“栈满\n”);exit(0);}elses[++top]=x;//x入栈。else//读入的整数等于-1时退栈。{if(top==0){printf(“栈空\n”);exit(0);}elseprintf(“出栈元素是%d\n”,s[top--])；}}}//算法结束。试写一个算法判别读入的一个以‘@’为结束符的字符序列是否是“回文”。intPalindrome_Test()//判别输入的字符串是否回文序列,是则返回1,否则返回0

{

InitStack(S);InitQueue(Q);

while((c=getchar())!='@')

{

Push(S,c);EnQueue(Q,c);//同时使用栈和队列两种结构

}

while(!StackEmpty(S))

{

Pop(S,a);DeQueue(Q,b));

if(a!=b)returnERROR;

}

returnOK;

}//Palindrome_Test编写递归算法，计算二叉树中叶子结点的数目。DLR(liuyu*root)/