南开大学数据结构学院b-2006.doc

2005-2006学年度第二学期数据结构期末试题(B) 专业： 姓名： 学号： a 单项选择题（20分） 下列排序算法中， 、 属于稳定排序， 、 属于不稳定排序（4分） A. 选择排序 B. 快速排序 C. 插入排序 D. 堆排序 简单队列对数据处理的方式是 （2分） A. 先来先服务 B. 后来先服务 C. 先来后服务 D. 以上均不对 基数排序算法的时间复杂性可达到线性时间，超过快速排序等高效排序算法，其原因是 （2分） A. 设计了巧妙的元素比较交换方法 B. 避免了元素的比较交换，通过元素值进行划分 一棵有根树节点数为n，其边的数量为 （2分） A. n/2 B. n - 1 C. n D. n + 1 一棵二叉有哪些信誉好的足球投注网站树中，节点n是节点m的后代，则节点n的关键字值与节点m的关键字值相比 （3分） A. 一定更大 B. 一定更小 C. 一定相等 D. 不确定 高度为2的5阶B－树，最少包含多少个关键字 （3分） A. 3 B. 4 C. 5 D. 6 对下面哪种输入序列，插入排序性能最差 （2分） A. 有序 序列 B. 完全逆序序列 C. 随机序列 对有向图G的某个顶点v，求其所有的入边(u, v)，此操作在如下哪种描述方式下性能最好 （2分） A. 邻接矩阵 B. 邻接压缩表 C. 邻接链表 D. 十字链表 画出下面程序段运行过程中，栈的变化情况（5分） #include stack stackchar s; char x, y, z; s.push(a); s.push(b); while (!s.empty()) { x = s.top(); s.pop(); }s.push(c);s.pop();s.push(a);s.pop();s.push(b);s.pop(); 对下面的整数列表，执行插入排序算法整理为递增序列，写出算法执行过程中每次插入操作后列表的变化情况，及最终排序结果（8分） 49 38 65 97 76 13 27 52 对下面的二叉树（14分） 指出根节点和叶节点（4分） 指出节点3的父节点、孩子节点和兄弟节点（4分） 给出二叉树的先序、中序、后序遍历结果（6分） 对下面的无向图（19分） 给出每个顶点的入度和出度（5分） 画出邻接链表描述（5分） 给出从顶点1开始的深度优先有哪些信誉好的足球投注网站和宽度优先有哪些信誉好的足球投注网站结果（4分） 给出5种不同的拓扑序列（5分） 在下面AVL树中，删除节点g，画出结果，标出每个节点的平衡因子（12分） 将下面森林转换为二叉树的描述形式（10分） 索引二叉有哪些信誉好的足球投注网站树节点类定义如下所示，设计索引二叉有哪些信誉好的足球投注网站树的删除算法，能够在正确删除节点的同时，正确更新其他节点的索引值。设计Delete函数实现你的算法，其中root为索引二叉有哪些信誉好的足球投注网站树根节点指针，x为删除关键字。（12分） template class T class IndexedBSTreeNode { friend void Delete(IndexedBSTreeNodeT *root, const T x); public: IndexedBSTreeNode(const T e) {data = e; LeftChild = RightChild = 0;} private: T data; IndexedBSTreeNodeT *LeftChild, *RightChild; int index; //节点索引值 };  B1 ――――――――――――――――――草稿―――――――――――――――――