西安电子科技大学期末考试真题+解析

题目	题型
单链表为什么要引入头结点？	问答
线性表的链式存储结构有单链表、循环链表、双向链表，试问它们各有什么优点和缺点？	问答
内存中一片连续空间（不妨假设地址从 1 到 m ），提供给两个栈使用，怎样分配这部分存储空间，使得对任一个栈，仅当这部分空间全满时才发生上溢。	问答
假设有一个适当大小的栈 S ，输入栈的序列为 A ， B ， C ， D ， E 。	问答
用向量表示的循环队列的队首和队尾位置分别为 1 和 max_size ，试给出判断队列为空和为满的边界条件。	问答
对二叉树中的结点按层次顺序（每一层自左向右）进行的访问操作称为二叉树的层次遍历。	问答
已知某通信电文仅由 A 、 B 、 C 、 D 、 E 、 F 这 6 个字符构成，其出现的频率分别为 23 、 5 、 14 、 8 、 25 、 7 ，请给出它们的霍夫曼树及其对应的霍夫曼编码。	问答
给定下列图 G 用两种不同表示法画出该图的存储结构图。	问答
针对下图分别用卡鲁斯卡尔及普里姆算法给出该图的最小生成树，画出其逻辑结构	问答
总结直接插入排序、折半插入排序、希尔排序、起泡排序、快速排序、简单选择排序、锦标赛排序、堆排序及归并排序等在最好情况下、最坏情况及平均的时间复杂度，辅助空间复杂度及稳定性。	问答
判断下面的每个结点序列是否表示一个堆，如果不是堆，请把它调整为堆。	问答
已知一序列（ 12 ， 70 ， 33 ， 65 ， 24 ， 56 ， 48 ， 92 ， 86 ， 33 ），问该序列是否是堆？	问答
试为下列情况选择合适的排序算法：	问答
实现一个算法，完成在不带表头结点的单链表第 i 个结点之前插入新元素 x 的操作。	问答
实现一个函数，完成在带表头结点的双向循环链表中，建立一个包含有值 value 的新结点并将其插入到当前结点之后。	问答
实现一个函数完成删除链式栈顶结点，返回被删栈顶元素的值。	问答
对二叉链表，实现一个函数 Parent(BinTreeNode<Type>start, BinTreeNode<Type>curent) 从结点 start 开始，搜索结点 current 的双亲结点，并返回其地址，否则返回 NULL 。	问答
若用二叉链表作为二叉树的存储表示，试针对下列问题编写递归算法：	问答
熟练掌握直接插入排序、折半插入排序、希尔排序、起泡排序、快速排序等其它排序的算法	问答
若以域变量 rear 和 length 分别指示循环队列中队尾元素的位置和队列中元素的个数。	填空

题目

题型

单链表为什么要引入头结点？

问答

线性表的链式存储结构有单链表、循环链表、双向链表，试问它们各有什么优点和缺点？

问答

内存中一片连续空间（不妨假设地址从 1 到 m ），提供给两个栈使用，怎样分配这部分存储空间，使得对任一个栈，仅当这部分空间全满时才发生上溢。

问答

假设有一个适当大小的栈 S ，输入栈的序列为 A ， B ， C ， D ， E 。

问答

用向量表示的循环队列的队首和队尾位置分别为 1 和 max_size ，试给出判断队列为空和为满的边界条件。

问答