2002 年招收攻读硕士学位研究生入学考试命题专用纸招生专业:计算机科学与应用技术考试科目:数据结构试题编号:418注: 答题（包括填空题、选择题）必须答在专用答题纸上，否则无效)－、单选题（每小题2分，共20分）1.在一个具有n个结点的有序单链表中插入一个新的结点使得单链表仍然有序的时间复杂度为A.O(logn)B.O(1)C.O(n2)D.O(n)2.若线性表最常用的操作是存取第i个元素及其前驱的值，则采用存储方式节省时间。

A.单向链表B.双向链表C.单循环链表D.顺序表3.用单链表表示的链式队列的队头在链表的位置。

A.链头B.链尾C.链中4.对二叉树的结点从1开始进行连续编号，要求每个结点的编号大于其左、右孩子的编号，同一双亲的左、右孩子中，左孩子的编号小于右孩子的编号，则可采用顺序实现编号。

A.前序遍历B.中序遍历C.后序遍历D.层序遍历5.己知一算术表达式的中缀形式为A+ B*C-D/E，后缀形式为ABC*+DE/-，其前缀形式为。

A.-A+B*C/DEB.-A+B*CD/EC.- + *ABC/DED.- +A*BC/DE6.利用逐点插入法建立序列（50，72，43，85，75，20，35，45，65，30）对的二叉排序树以后，查找元素35要进行次元素间的比较。

A.4B.5C.7D.107.对于一个具有n个顶点和e条边的图，来用邻接矩阵表示的空间复杂度为。

A.O(n)B.O(e)C. O(n2)D. (n+e)8.设连通图G的顶点数n，则G的生成树的边数为。

A.nB.n-1C.2n D，2n-19.下列排序算法中，算法可能出现下面的情况:在最后一趟排序开始之前，所有元素都不在最终的位置上。

A.堆排序B.冒泡排序C.快速排序D.插入排序10.设n，m为一棵二叉树上的两个结点，在中序遍历时，n在m前的条件是A.n在m右方B.n是m祖先C.n在m左方D.n是m子孙二、判断题（判断下列各小题的叙述是否正确，若正确打“√”，否则打“×”，每小题1分，共10分）1. 线性表中每个元素都有一个前驱和一个后继。

2. 顺序表中逻辑关系上相邻的两个元素在物理位置上也相邻。

3. 在栈为空的情况下，不能作出栈操作，否则会产生“下溢”。

4. 对广义表A=（a，（b，c），d）的运算head（tail（A））的结果不是b。

5. 图G的一棵最小生成树的代价未必小于G的其他任何一棵生成树的代价。

6. 若从某顶点开始对含有n个顶点的有向图G迸行深度优化先遍历，所得到的遍历序列唯一，则可断定起弧数为n－1。

7. 二叉树不能存储在数组中。

8. 理想情况，在散列表中查找一个元素的时间复杂度为O(1)。

9. 最优二叉树是A VL树（平衡二叉树）10.序列（101，88，46，70，34，39，45，58，66，10）是堆。

二、填空题（每空2分，共20分）1. 在有n个元素的顺序表中，如果要删除第i个元素（1≤i≤n）,那么有个元素必须向表头方向移动。

2.栈的插入和删除只能在栈顶一端进行，后进栈的元素必定先被删除，所以栈又被称为表。

3.已知一棵完全二叉树的第八层有8个结点（根结点在第0层），则该完全二叉树的叶结点数是。

4.具有64个结点的完全二又树共有层。

5.设n行n列的下三角矩阵A已压缩到一维数组s[1..n*(n+1)/2]中，若按行序为主存储，则元素A[i,j]在S中的存储位置是。

6.要将序列{50，16，23，68，94，70，73}建成堆，只需把16与相互交换。

7.具有n个顶点的有向连通图最多有条边，最少有条边。

8.冒泡排序算法在最佳情况下的元素交换次数为。

9.插入、选择、冒泡、快速排序算法中，排序趟数与序列的原始状态有关的排序方法是。

四、解析题（第1小题6分，第2、4小题各8分，第3小题10分，共32分）1. 请解答下列关于堆的一些问题:1.堆的存储表示是顺序的还是链接的。

2.没有一个最小堆，即堆中任意元素的关键码均大于它的左子女和右子女的关键码。

其具有最大值的元素可能在什么地方？3.对n个元素进行建初始堆的过程中，最多做多少次数据比较（不用大O表示法）？2. 一棵二叉树的先序、中序、后序序列如下，其中一部分未标示出，请构造出该二叉树。

先序序列: C D E G H I K中序序列: C B F A J K I G后序序列: E F D B J I H A3. 一项工程P曲Pl，P2，P3，P4，P5，P6六个子工程组成，这些工程之间有下列关系:P1＞P2，Pl＞P3，Pl＞P4，P2＞P3，P2＞P5，P3＞P6，P4＞P6，P5＞P6。

其中符号“＞”表示先于关系，例如:Pl＞P3表示只有Pl完成之后才能进行P3的工作。

请给出工程P的四种可能的施工顺序。

4. 设按如下所述在有序的线性表中查我X:先将X与表中的第4j(j=1，2，3，…)项进行比较，若相等，由查找成功:否则，由某次比较求得比X大的一项4K之后续而和4K-2，然后和4K-3或4K-1项进行比较，直到查找成功。

试画出当表长n＝16时的判定树，并求其平均查找长度（考虑查找元素在等概率的情况下）。

五、算法设计题（可用类PASCAL、C或你所熟悉的高级语言设计算法，第1小题8分，第2小题10分，共18分）1.设计一个函数返回指向一棵二叉树的T的后序序列的第一个结点的指针，要求采用非递归形式，并且不用栈。

2.设计一算法，实现第四大题中第4小题所给出的查找方法。

2003 年招收攻读硕士学位研究生入学考试命题专用纸招生专业:计算机应用技术、计算机软件与理论、软件工程硕士考试科目:数据结构试题编号:418(450)注: 答题（包括填空题、选择题）必须答在专用答题纸上，否则无效一、单项选择题（每小题1分，共15分）1.两个各有n个元素的有序列表并成一个有序表，其最少的比较次数是A.nB.2n-1C.2nD.n-12.设循环队列中数组的下标范围是0~ n-1，f表示队首元素的前驱位置，r表示队尾元素的位置，则队列中元素个数为。

A.r-fB.r-f+1C.(r-f+1)mod nD.(r-f+n)mod n3.一个5行6列的二维数组s采用从最后一行开始，每一行的元素从右至左的方式映射到一维数组a中，s和a的下标均从0开始，则s[3][3]在a中的下标是。

A.7B. 8C. 9D. 104.设只含根结点的二叉树的高度为1，则高度为n的二叉树中所含叶子结点的个数最多为个。

A.2nB.nC.2n -1D.2n-15.设高度为h的二叉树上只有度为0和度为2的结点，则此二叉树中所包含的结点数至少为个（设只含根结点的二叉树的高度为1）。

A.2h B 2h-1 C.2h+1 D.h+16.对一棵二叉检索树进行得到的结点序列是一个有序序列。

A.前序周游B. 中序周游C.后序周游D. 层次周游7.一棵前序序列为1，2，3，4的二叉树，其中序序列不可能是。

A.4,1,2,3B.4,3,2,1C.2,4,3,1D.3,4,2,18.下列编码中不是前缀码。

A.{00，01，10，11}B.{0,1,00,11}C.{0，10，110，111}D.{10，110，1110，1111}9.在含n个顶点和e条边的有向图的邻接矩阵中，零元素的个数为 .A.eB.2eC.n2-eD.n2-2e10.具有n个顶点和e条边的图的深度优先搜索算法的时间复杂度为A.O(n)B.O(n3)C.O(n2)D.O(n+e)11.如果具有n个顶点的图是一个环，则它有棵生成树。

A.nB.n+lC.n-lD.2n12堆排序算法在平均情况下的时间复杂度为。

A.O(n) B.O(nlogn) C.O(n2)D.O(logn)13.在待排序数据已基本有序的前提下，下述排序方法中效率最高的是。

A.直接插入排序 B.直接选择排序 C.快速排序 D.归并排序14.在理想情况下，散列表中查找元素所需的比较次数为。

A.nB.OC.n/2D.115.在一棵m阶B树中，若在某结点中插入一个新关键字而引起该结点分裂，则此结点中原有的关键字的个数是。

A.mB.m+1C.m—lD.m/2二、判断题(判断下列各题是否正确，若正确，在括号内打“√”，否则打“╳”；每小题1分，共10分)1.已知指针curr指向链表中的某结点，执行语句curr=curr->next；不会删除该链表中的结点。

( )2.若二叉树的叶结点数为1，则其高度等于结点数(仅含根结点的二叉树高度为1)。

（）3.按中序周游二叉树时，某个结点的直接后继是它的右子树中第一个被访问的结点。

( )4.完全二叉树的某结点若无左孩子，则它必是叶结点。

( )5.向二叉检索树中插入一个新结点，需要比较的次数不可能大于此二叉树的高度。

( )6.对一个堆按层次周游，一定能得到一个有序序列。

( )7.一棵树中的叶子结点数一定等于其对应的二叉树中的叶子结点数。

( )8.将一棵树转换为二叉树表示后，该二叉树的根结点没有右子树。

( )9.任何有向图的结点都可以排成拓扑序列，而且拓扑序列不唯一。

( )10.快速排序在最差情况下的时间复杂度是0(n2)，此时它的性能并不比冒泡排序更好。

( )三、填空题（每空2分，共20分）1.具有100个结点的完全二叉树的叶子结点树为。

2.由权值分别为3，9，6，2，8的叶子结点生成一棵哈夫曼树，它的外部带权路径长度为＿＿＿。

3.对含n个结点的完全二叉树按自上而下，从左到右的顺序结点编号（从0开始），则编号最小的叶子结点的编号是。

4.n个顶点的连通无向图的邻接矩阵至少有个非零元素。

5.在有序表A[1..20]中，若需查找的元素位于A[12]，则采用折半查找算法所比较的元素的下标依次为6.要将序列{60，10，8，40，90，70，100}建成堆，只需把8与相交换。

7.从一维数组a[n]中顺序查找出一个最大值元素的时间复杂度为。

8.已知广义表L=（（a，b，c），（d，e，f）），则运算head(tail(head(tail(L))))的结果是.9.模式串P=“abaa”的next函数值序列为。

10.一个两层100阶的B+树，最多可以有条记录四、解析题（共55分）1.对二叉树中结点进行按层次顺序（每一层从左至右）的访问操作称为二叉树的层次遍历，遍历所得到的结点序列称为二叉树的层次序列。

现已知一棵二叉树的层次序列为ABCDEFGHIJ，中序序列为DBGEHJACIF，请画出该二叉树。

（7分）2.证明若二叉排序树中的一个结点存在两个孩子，则（8分）1它的中序后继结点没有左孩子。

2它的中序前趋结点没有右孩子。

3.对下面的带权无向图采用prim算法从顶点1开始构造最小生成树。

（写出假如生成树顶点集合S和选择边Edge的顺序）（10分）19 1082 34 5 6 711 8④⑤⑥S: 顶点号Edge: (顶点，顶点，权值)1 （，，）1 （，，）1 （，，）1 （，，）1 （，，）1 （，，）4.已知一组关键字序列为:（17，31，13，11，20，35，25，8，4，11，24，40，27），按照依次插入结点的方法生成一棵平衡二叉排序树。