数据结构试题A201312答案.doc

陕西科技大学 试题纸A（参考答案及评分标准） 课程 数据结构 班级 信息、数学11 　　　　 学号 姓名 题号 一 二 三 四 五 六 七 八 九 十 总分 得分 阅卷人 一、简答题（每小题5分，共15分） 1. 说明在带头结点单链表L中一下三个概念的关系：头指针、头结点、首元素结点。 答：在带头结点单链表L中，头指针是指向单链表的头结点的指针；头结点是单链表中的第一个结点；首元素结点是单链表中的第一个元素结点，在头结点之后。 2. 简述在一般的顺序队列中的“假溢出”问题及解决方法。 答：在一般的顺序队列中，当rear==MAXSIZE时，认为队满。但此时不一定是真的队满，因为随着部分元素的出队，数组前面会出现一些空单元。由于只能在队尾入队，使得上述空单元无法使用。这种现象称为假溢出。 为解决此问题，可借助于求余运算rear=（rear+1）mod MAXSIZE；front=（front+1）mod MAXSIZE，实现队尾指针和队头指针的循环变化。留出一个单元不使用，队空条件为front=rear，队满条件为（rear+1）mod MAXSIZE=front。 3. 简述排序算法的稳定性。举例说明某个排序算法是不稳定的。 答：多个具有相同关键字的记录采用某种排序算法排序，在排序前后的序列中的位置领先顺序不变，则称所采用的排序算法是稳定的，否则是不稳定的。 希尔排序是不稳定的，假设待排序序列{2，4，1，2}，采用希尔排序，设d1=2，则得到一趟排序结果为{1，2，2，4}，这说明希尔排序算法是不稳定的。 二、选择题（每小题2分，共20分） 请在每小题的四个备选答案中，选出一个正确的答案，并将其号码填在括号内。 某队列允许在其两端进行入队操作，但仅允许在一端进行出队操作，元素1,2,3,4,5依次入队，则所得的输出序列不可能是（B）。 A．21345 B．42315 C．42135 D．53214 设一个栈的输入序列为1，2，3，4，则借助一个栈所得的输出序列不可能是（D）。 A．1，2，3，4 B．4，3，2，1 C．1，3，4，2 D．4，1，2，3 3. 将一棵有110个节点的完全二叉树从根这一层开始，每一层上从左到右依次对结点进行编号，根节点的编号为1，则编号为49的结点的父亲节点编号为（D）。 A．99 B．98 C．25 D．24 4. 在长度为n的顺序存储的线性表中，删除第i个元素（1≤i ≤n）时，需要从前向后依次前移（B）个元素。 A．n-i+1 B．n-i C．n-i-1 D．i 5. 栈的插入操作在（B）进行。 A．栈底 B．栈顶 C．任意位置 D．指定位置 6. 链表不具有的特点是（A）。 A．可随机访问任一个元素 B．插入删除不需要移动元素 C．不必事先估计存储空间 D．所需空间与线性表的长度成正比 7. 深度为4(根结点的层次为1)的二叉树至多有（D）个结点。 　　A．16 B． C． D． 8. 任何一个无向连通图的最小生成树（C）。 A．一定有多棵 B．只有一棵 C．有一棵或多棵 D．可能不存在 9.线性表若采用链式存储结构时，要求内存中可用存储单元的地址（C）。 A．必须是连续的 B．一定是不连续的 C．连续或不连续都可以 D．部分地址必须是连续的 10.若某线性表中最常用的操作是取第i个数据元素，则采用（B）存储方式最节省时间。 A．单链表 B．顺序表 C．单向循环 D．双链表 三、填空题（每空2分，共20分） 1. 下列算法中加下划线语句的语句频度为 n(n+1)(n+2)/6 ，算法的时间复杂度T（n）= O(n3)。 for(i=1;i=n;i++) for(j=1;j=i;j++) for(k=1;k=j;k++) x=x+1; 2. 数据的逻辑结构被分为 集合结构 、 线性结构 、 树形结构 和 图结构 四种。 3. 具有n个叶结点的哈夫曼树 (Huffman) 的分支总数为。. 若连通图的顶点个数为n，则该图的生成树的边数为。 . 假设有6行8列的二维数组A（下标从1开始），每个元素占用6个字节，存储器按字节编址。已知A的基地址为1000