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

1、学习 好资料上海交通大学继续教育学院网络教育期末复习样卷答案课程名称：数据结构、单项选择题（每题 2分,共 30 分）1、A、包含 64 个结点的完全二叉树,其深度为（8B、 7）（ 根的层次为C、61）。D、52、A.B.关于算法的空间复杂度的理解错误的是（空间复杂度,即为算法的存储空间需求。 空间复杂度是指算法在执行过程中所需要的最大的存储空间。 空间复杂度,包括算法在执行过程中指令、常数、变量、输入数据,）。C. 中所需要的辅助空间。以及程序执行过程D.算法的空间复杂度与算法无关。3、A、B、C、D、数据结构包括 3 个方面的内容,它们分别是（ 数据、数据元素、数据项 数据元素、数据处理

2、、算法实现 数据元素、数据的逻辑结构、数据的存储结构 数据的逻辑结构、数据的存储结构、数据的操作）。4、A、一个栈的入栈序列是 a、b、 c、 acbdB、 dcbad,则下列序列中不可能是栈的输出序列的是（C、acdbD、 dbac）。将 5 个不同的数据进行插入排序,A. 8B. 95、至多需要比较（C. 10）次。D. 256、 A. C.栈和队列的共同点是（都是先进先出 只允许在端点处插入和删除元素）。B. 都是先进后出D. 没有共同点7、A、设一组初始记录关键字序列 （5 , 2, 快速排序的结果为（ ）。2,3,5,8,6B、 3,2,5,8,66,3, 8） ,以第一个记录关键字

3、 5 为基准进行一趟C、 3,2,5,6,8D、 2,3,6,5,88、A.2设有一顺序栈S,元素s1,s2,s3,s4,s5,s6依次进栈，如果s2,s3,s4, s6 , s5,s1, 则栈的容量至少应该是（）。B.3C.56 个元素出线的顺序是D.69、A、设某无向图中有 n 个顶点 e 条边,则该无向图中所有顶点的入度之和为（nB、 eC、 2nD、 2eC、 2n）。更多精品文档学习-好资料10、设无向图G中有n个顶点e条边，则其对应的邻接表中的表头结点和表结点的个数分别 为（）。A. n ， eB. e ， nC. 2n ， eD. n ， 2e11、 下列关键字序列中，（） 是堆

4、。A、16, 72, 31,23, 94, 53B、94, 23, 31,72, 16, 53C、16, 53, 23, 94，31,72D 16, 23, 53, 31, 94, 7212、以下说法错误的是（）。A. 一般在哈夫曼树中，权值越大的叶子离根结点越近B. 哈夫曼树中没有度数为1的分支结点C. 若初始森林中共有 n裸二叉树，最终求得的哈夫曼树共有2n-1个结点D. 若初始森林中共有 n裸二叉树，进行2n-1次合并后才能剩下一棵最终的哈夫曼树13、 设有序表中有1000个元素，则用二分查找法查找元素X最多需要比较（）次。A、25B、10C、7D、1Iog2 n+114、二叉树是非线性

5、数据结构，所以（）。A. 它不能用顺序存储结构存储B. 它不能用链式存储结构存储C. 顺序存储结构和链式存储结构都能存储D. 顺序存储结构和链式存储结构都不能使用15、 对22个记录的有序表作折半查找，当查找失败时，至少需要比较 （）次关键字。A、3B、4C、5D、6二、填空题（每空 2分，共20分）1、 在线性表中，元素 ai（2 < i w n）被称为是元素的_后继。2、 顺序栈用data1.n 存储数据，栈顶指针是top,则值为x的元素入栈的操作是_data+top=x 。3、 设有一个空栈，栈顶指针为1000H（十六进制），现有输入序列为1, 2, 3, 4, 5,经过PUSH,

6、PUSH,POP,PUSH,POP,PUSH,PU后H输出序列是 23,而栈顶指针值是 _ 100CH_H。 设栈为顺序栈，每个元素占4个字节。4、 一棵深度为6的满二叉树有_ 31 _个分支结点和_32_ 个叶子。5、 为了能有效地应用 HASH查找技术，必须解决的两个问题是构造一个好的 HASH函数和 确定解决冲突的方法。6、 大多数排序算法都有两个基本的操作：比较_和_移动_。三、简答题（共30分）1、请解释名词：满二叉树、拓扑排序答：满二叉树：一棵深度为 k且有2k -1个结点的二叉树。拓扑排序：由某个集合上的一个偏序得到该集合上的一个全序，该操作称为拓扑排序。学习-好资料 2、在各种

7、排序方法中，哪些是稳定的？哪些是不稳定的？各举三个即可。答：稳定：直接插入排序、折半插入排序、二路插入排序、表插入排序、起泡排序 不稳定：直接选择排序、希尔排序、快速排序、堆排序3、假设用于通信的电文仅由8个字母组成，字母在电文中出现的频率分别为0.07，0.19 ,0.02 , 0.06 , 0.32 , 0.03 , 0.21 , 0.10。试为这 8个字母设计哈夫曼编码。使用07的二进制表示形式是另一种编码方案。对于上述实例，比较两种方案的优缺点。5)更多精品文档4、一棵度为2的树与一棵二叉树有何区别?答：度为2的树从形式上看与二叉树很相似， 但它的子树是无序的， 而二叉树是有序的。 即

8、，在一般树中若某结点只有一个孩子， 就无需区分其左右次序， 而在二叉树中即使是 一个孩子也有左右之分。5、给定二叉树的两种遍历序列，分别是：前序遍历序列：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分）1、设从键盘输入一整数的序列：a1, a2, a3,，an,试编写算法实现：用栈结构存储输入的整数，当ai工-1时，将ai进栈；当ai=-1时，输出栈顶整数并出栈。算法应对异常情况 （入栈

9、满等）给出相应的信息。学习 好资料void InOutS( int smaxsize) int top=0; /top for (i=1; i<=n; i+) /n scanf(“ %d” ,&x); /if (x!=-1) /答： #define maxsize 栈空间容量为栈顶指针，定义 top=0 时为栈空。个整数序列作处理。 从键盘读入整数序列。 读入的整数不等于 -1 时入栈。if (top=maxsize-1)printf(“栈满 n ”);exit(0);else s+top=x; /x 入栈。else / 读入的整数等于-1 时退栈。if (top=0)print

10、f( “栈 空 n ” );exit(0);else printf( “ 出 栈 元 素是 %dn” ,stop-) ；/算法结束。2、 试写一个算法判别读入的一个以 '为结束符的字符序列是否是“回文” 。int Palindrome_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) return ERROR;return OK;/Palindrome_Test3、4、 编写递归算法，计算二叉树中叶子结点的数目。 DLR(liuyu *root)/* 中序遍历 递归函数 */if(r