(答案)数据结构复习试卷一.doc

《数 据 结 构》答 案（试 卷1） 简述下列术语（14分） 数据类型：是一个值的集合和定义在这个值集上的一组操作的总称。在用高级程序语言编写的程序中，必须对程序中出现的每个变量、常量或表达式，明确说明它们所属的数据类型。 时间复杂度：假如随着问题规模 n 的增长，算法执行时间的增长率和 f(n) 的增长率相同，则可记作：T (n) = O(f(n)) ，称T (n) 为算法的(渐近)时间复杂度。 串：是由零个或多个字符组成的有限序列。一般记为 s=‘a1a2a3…an’ (n≥0) 其中，s是串名，单引号括起来的字符序列是串的值； 满二叉树：深度为k且含有2 k - 1个结点的二叉树，其特点是每一层上的结点数都是最大结点数。 连通分量：若无向图为非连通图，则图中各个极大连通子图称作此图的连通分量。 顺序文件：记录按其在文件中的逻辑顺序依次进入存储介质而建立的文件，即文件物理结构中记录的排列顺序和文件的逻辑结构中记录的排列顺序一致。 主关键字：用来唯一地标识一个数据元素（或记录）的某个数据项的值，称为主关键字。 简答题： 线性表的顺序存储结构和链式存储结构各有那些特点？（6分） 顺序存储结构的特点： 表中相邻的两个元素其物理存储位置也相邻。即以元素在计算机内物理位置上的相邻来表示线性表中数据元素之间相邻的逻辑关系。 顺序存储结构的优缺点： ⑴ 无需为表示数据元素之间的关系而增加额外存储空间，存储密度高； ⑵ 可以随机存取表中任一元素，它的存储位置可用一个简单直观的公式来表示； ⑶ 插入和删除运算时，必须移动大量元素，尤其是当线性表的数据元素含有复杂信息时，移动工作量很大，效率较低； ⑷ 必须预先为线性表分配空间，表容量难以扩充，必须按线性表最大可能长度分配空间。若是线性表长度变化较大时，则使存储空间不能得到充分利用；且有时难以准确估计线性表最大长度，估计过小导致溢出，估计过大又会造成存储空间浪费。 链式存储结构的特点： 数据元素之间的逻辑关系是由结点中的指针来指示的，逻辑上相邻的两元素其物理位置不要求紧邻。 链式存储结构的优缺点： ⑴ 插入和删除运算时，无须移动表中元素的位置，只需修改有关结点的指针内容； ⑵ 不能随机访问表中元素，访问时间与元素在表中的位置有关； ⑶ 不需要一块连续的存储空间，只要能存放一个数据元素的空闲结点就可以被利用； ⑷ 表的规模易扩充。 解答题：用堆栈对算术表达式求值：3*（7-2），写出堆栈的操作顺序和过程（6分） 答案请参考教材P54例3-1。 画出一个采用链式存储结构的队列示意图，分别写出其进队和出队的算法（10分） 链队列示意图请参考教材P61图3.10。 链队列的入列算法： void enqueue (linkqueue Q, elemtype x) { p=(queueptr*)malloc(sizeof(qnode)); p (data=x; p (next=NULL; Q.rear (next =p; Q.rear =p; } 链队列的出列算法： status delqueue (linkqueue Q) { if (Q.front= =Q.rear) return NULL; // 队空 p =Q.front (next; // p指向队头元素 Q.front (next= p ( next; // 修改头结点指针域，指向新的队头元素 x= p (data; if (Q.rear= =p) Q.rear=Q.front; free(p); // 释放被删掉的原队头元素 return OK; } 对于给出的数据序列：{12，6，15，9，13，22，7，3，18}，请构造其对应的二叉排序树（6分） 请简述快速排序的基本思想；并对于下列给定数据：{49，38，65，97，12，76，13，27，36，68}，指出使用快速排序后第一趟的结果（10分） 找一个记录，以它的关键字作为“枢轴”，凡其关键字小于枢轴的记录均移动至该记录之前，反之，凡关键字大于枢轴的记录均移动至该记录之后。致使一趟排序之后，记录的无序序列分割成两个子序