郑州大学软件学院 数据结构试题2 附答案

郑州大学软件学院数据结构试题2 附答案 郑州大学软件学院数据结构试题2 附答案是数据结构领域的重要知识点汇总，涵盖了算法评价、链表、栈、AOV 网、散列表、稀疏矩阵、快速排序、二叉搜索树等多个方面。 一、算法评价 * 算法的评价标准包括正确性、健壮性、时空复杂度、并行性等方面。 二、链表 * 在带有头结点的单链表 HL 中，要向表头插入一个由指针 p 指向的结点，则执行 p->next=HL->next; HL->next=p;。 * 在链表中，经常需要进行插入和删除操作时，应当采用链表表示。 三、栈 * 栈的输入序列为 1 2 3，则下列序列中不可能是栈的输出序列的是 1 2 3。 * 快速排序在最坏情况下的时间复杂度为 O(n2)。 四、AOV 网 * AOV 网是一种有向无环图。 五、散列表 * 采用开放定址法处理散列表的冲突时，其平均查找长度低于链接法处理冲突。 * 快速排序在最坏情况下的时间复杂度为 O(n2)。 六、稀疏矩阵 * 在稀疏矩阵的带行指针向量的链接存储中，每个单链表中的结点都具有相同的行号。 七、函数参数 * 若需要利用形参直接访问实参时，应将形参变量说明为引用参数。 八、二叉搜索树 * 从二叉搜索树中查找一个元素时，其时间复杂度大致为 O(log2n)。 九、数据结构 * 数据结构是指数据及其相互之间的关系。 * 当结点之间存在 M 对 N（M：N）的联系时，称这种结构为图。 十、二维数组 * 设 W 为一个二维数组，其每个数据元素占用 4 个字节，行下标 i 从 0 到 7，列下标 j 从 0 到 3，则二维数组 W 的数据元素共占用 128 个字节。 十一、广义表 * 广义表 A= (a,(a,b),((a,b),c)),则它的深度为 3，它的长度为 4。 十二、二叉树 * 二叉树是指度为 2 的树。 * 一棵结点数为 N 的二叉树，其所有结点的度的总和是 2N-2。 * 对一棵二叉搜索树进行中序遍历时，得到的结点序列是一个有序的序列。 十三、完全二叉树 * 若对一棵完全二叉树从 0 开始进行结点的编号，并按此编号把它顺序存储到一维数组 A 中，则 A[i] 元素的左孩子元素为 2*i+1，右孩子元素为 2*i+2，双亲元素为 (i-1)/2。