数据结构(C语言描述)期末试卷.doc

院（系） 班级 姓名 学号 装订线 专业数据结构（C语言描述）期末试卷（ 学年 第 学期）题号总分得分一、填空题（每空 1 分，共 15 分） 1、 实现数据结构的基本存储方法有： ， 。 顺序存储结构； 链接存储结构2、 若算法中的语句执行次数之和为 T ( n )=3525 n +4 n log n ，则算法的时间复杂度是 。 O （ n log n ）3、 假设以 S 和 X 分别表示进栈和出栈操作，则对输入序列 a , b , c , d , e 进行一系列操作 SSXSXSSXXX 之后，得到的输出序列为。 b , c , e d , a4、 在串 S=structure 中，以 t 为首字符的子串有 个。 125、 下三角矩阵 A n n 按行优先存储在一维数组 B 中，实现随机存取下三角中元素 A i j 的地址公式是 。（注意元素下标是从 0 开始） i ( i+1 ) /2+j 6、 广义表 ( a , b ), c , d, ( e , ( f , g ) 的表头是 ，表尾是 ，表的长度为 ，表的深度为 。 ( a , b ) ； ( c , d, ( e , ( f , g ) ； 4 ； 37、 包含 n 个结点的二叉树，深度最大为 ，深度最小为 。 n ； log 2 n +18、 含有 n 个结点和 e 条边的无向图的邻接矩阵中，零元素的个数为 。 n 2 - 2 e 9、 快速排序在 的初始状态下，时间效率最差，其时间复杂度为 O （ n 2 ）。平均情况下快速排序的时间复杂度为 。 正序或逆序； O （ n log n ）二、简答题（每小题 5 分，共 20 分） 1、 数据结构中研究的经典结构有那些？各有什么特点？ 答：根据数据元素之间逻辑关系的不同，数据结构分为四类： 集合 数据元素之间就是“属于同一个集合”，除此之外，没有任何关系； 线性结构 数据元素之间存在着一对一的线性关系； 树形结构 数据元素之间存在着一对多的层次关系； 图型结构 数据元素之间存在着多对多的任意关系。2、 栈上有那些基本运算？请写出链栈的抽象数据类型定义。（提示：先定义结点结构，再定义链栈类，在类中只给出函数声明，不需要定义函数） 答：栈上有的基本运算有：入栈、出栈、取栈顶元素、判断栈是否为空、初始化等。 template struct Node T data; Node *next; ; template class LinkStack public: LinkStack ( ) top= NULL ; LinkStack ( ); void Push (T x); T Pop ( ); T GetTop ( ) if (top!= NULL ) return top - data; bool Empty ( ) top= NULL ?return 1:return 0; private: Node *top; / 栈顶指针即链栈的头指针 ;3、 什么叫稳定排序？请列举出三种实现稳定排序的排序算法名称。 答：假定在待排序的记录序列中，存在多个具有相同键值的记录，若经过排序，这些记录的相对次序保持不变，即在原序列中， k i = k j ，且 r i 在 r j 之前，而在排序后的序列中， r i 仍在 r j 之前，则称这种排序算法是稳定的；否则称为不稳定的。 稳定的排序有：直接插入排序、起泡排序、直接选择排序和归并排序等。 4、 散列函数的设计原则是什么？有那些常用的散列函数设计方法？ 答：设计散列函数一般应遵循以下原则： 计算简单。散列函数不应该有很大的计算量，否则会降低查找效率。 函数值（即散列地址）尽量分布均匀。函数值要尽量均匀散布在地址空间，这样才能保证存储空间的有效利用，并减少冲突。 常用的散列函数设计方法有：直接定址法、平方取中法、除留余数法、数字分析法等。三、 假设在长度大于 1 的循环链表中，即无头结点也无头指针， S 为指向链表中某个结点的指针，试编写算法删除结点 S 的前趋结点。（ 8 分） 答：算法如下：（ 8 分） void delete( LinkList s ) pre=s; q=pre next; while (q next!=s) pre=q; q=q next; pre next=s; free(q); /delete 四、 已知叶子结点（ a , b , c , d , e , f ）及对应的权值（ 12, 5, 3, 20, 9, 10 ），请画出哈夫曼树并给出各叶子结点的哈夫曼编码。（ 10 分） 答：（ 10 分，其中哈夫曼树 8 分，编码 2 分） WPL=5*4+3*4+9*3+10*3+12*3+20*1=145 a ： 011 b ： 0000c ： 0001 d ： 1 e ： 001 f ： 010 五、 已知有如下二叉树：（共 15 分） (1) 画出该二叉树的二叉链表存储示意图；（ 4 分） (2) 写出前序遍历的递归算法；（ 5 分） (3) 写出前序、中序、后序遍历得到的结点序列（ 6 分） 答：已知有如下二叉树：（共 15 分） 1 、（ 4 分）2 、前序遍历的递归算法：（ 5 分） template void BiTree:PreOrder （ BiNode *root ） if (root = NULL ) return; else 输出 root - data; PreOrder （ root - lchild ） ; PreOrder （ root - rchild ） ; 3 、遍历序列（ 2 3 分） 前序： ABDEHICFG 中序： DHEIBAFCG 后序： HIEDBFGCA 六、 已知有向图：（共 15 分） G= （ V ， E ） V= a , b , c , d , e , f , g E=, (1) 画出此有向图的邻接表存储结构图示；（ 5 分） (2) 写出一个拓扑序列；（ 2 分） (3) 假设初始时各顶点的入度已经存放在邻接表的 in 域中，请用伪代码写出拓扑排序算法。（ 8 分）答：1 、（ 5 分） 2 、拓扑序列：（ 2 分）a b c d e f g 3 、拓扑排序算法。（ 8 分） 七、 已知散列函数为： H ( k )= k mod 7 ，用拉链法处理冲突，请画出依次插入 23, 14, 9, 6, 18, 30, 49, 12, 34 后的散列表，并求出检索成功的平均检索长度。（ 9 分） 答：（ 7 分） AVL= （ 5*1+3*2+1*3 ） /9=14/9 （ 2 分）八、 设有八枚硬币，分别表示为 a ， b