数据结构补充习题

1、复习补充题一、 填空1 数据结构的存储结构包括顺序、链式、索引和散列等四种。2 存储结构是逻辑结构的物理实现。3 在程序运行过程中可以扩充的数组是动态分配的数组。这种数组在声明它时需要使用数组指针。4 在链表中进行插入和删除操作的效率比在顺序存储结构中进行相同操作的效率高。5 栈是一种特殊的线性表，允许插入和删除运算的一端称为栈顶。6 主程序第一次调用递归函数被称为外部调用，递归函数自己调用自己被称为内部调用，它们都需要利用栈保存调用后的返回地址。7 如果一个对象部分地包含自己，或自己定义自己，则称这个对象是递归的对象。8 若一个算法中的语句频度之和为T(n)=n+2nlogn，则算法的时间复

2、杂度为？9 在无向图的邻接矩阵A中，若Ai,j等于1，则Aj,i等于？10 一棵具有n个结点的完全二叉树，它的深度为？11 深度为h的完全二叉树至少有_个结点。12 设有一个顺序栈S，元素1、2、3、4、5、6依次进栈，如果6个元素的出栈顺序为2、3、4、6、5、1，则顺序栈的容量至少应为？13 设栈S和队列Q的初始状态为空，元素e1，e2，e3，e4,e5和e6依次通过栈S，一个元素出栈后即进队列Q，若6个元素出队的序列是e3，e5，e4,e6,e2,e1,则栈S的容量至少应该是 。14 在序列(2,5,8,11,15,16,22,24,27,35,40)中采用折半查找查找元素24，需进行

3、次元素之间的比较。（注意：查找不同元素，次数不同，要按照折半查找的过程来计算）15 在对一组记录（18，6，27，12，52，15，47，29）进行直接插入排序时，当把第6个记录15插入到有序表时，为寻找插入位置需比较 次。二、 选择题1 数据的四种基本逻辑结构是指（ ）A数组、链表、树、图形结构B线性表、链表、栈队列、数组广义表C线性结构、链表、树、图形结构D集合、线性结构、树、图形结构2 线性表采用链式地址时，其地址（ ）A必须是连续的B一定是不连续的C部分地址必须是连续的D连续与否均可以3 在长度为n的顺序表的第i (1in+1)个位置上插入一个元素，元素的移动次数为（ ）An i +

4、1Bn i CiDi - 1 4 链表不具有的特点是（ ）A插入、删除不需要移动元素B可随机访问任一元素C不必事先估计存储空间D所需空间与线性长度成正比5 一个栈的入栈序列是a、b、c、d、e，则栈的不可能的输出序列是（ ）Ae d c b aBd e c b a Cd c e a bDa b c d e6 最大容量为n的循环队列，队尾指针是rear，队头是front，则队空的条件是（ ）。A. (rear+1) MOD n = frontB. (rear-l) MOD n = front Crear+1=frontD. rear=front7 在一个长度为n的顺序表的表尾插入一个新元素的时间

5、复杂度为（ ）AO (n) BO (1)CO (n2 ) DO (log2 n)8 在一棵具有n个结点的二叉树中，所有结点的空子树个数等于（ ）AnBn-1Cn+1D2*n9 已知某二叉树的后序遍历序列是dabec, 中序遍历序列是debac , 它的前序遍历是（ ）。AacbedBdecabCdeabcDcedba10 n个顶点的有向图中含有向边的数目最多为（ ）An-1BnCn(n-1)/2Dn(n-1) 11 要连通具有n个顶点的有向图，至少需要（ ）条边。An-lBnCn+lD2n12 一组记录的值为(12,38,35,25,74,50,63,90),按2路归并排序方法对序列进行一趟归

6、并后的结果为（ ）。A12,38,25,35,50,74,63,90B12,38,35,25,74,50,63,90C12,25,35,38,50,74,63,90D12,35,38,25,63,50,74,90三、 解答题：1 （5分）将下列树转换成为二叉树（只要求给出转换结果）掌握基本原理：第一个儿子是左子树，后续的儿子是第一个儿子的右子树2 设有序列(45，24，53，12，28，90)，请构成一棵二叉排序树，并求其查找成功时的平均查找长度。3 以数据集（9，19，2，6，32，3，21，10）为叶结点的权值，构造一棵哈夫曼树，并计算其带权路径长度。4 已知一组关键字为（39,23,54

7、,25,31,28,55,12,19,51,64），用链地址法解决冲突。假设装填因子=0.75，散列函数的形式为H（K）= K MOD P，回答下列问题：（1）构造出散列函数；（3分）（2）画出插入全部关键字后的链地址散列表（5分）（3）计算出等概率情况下查找成功的平均查找长度（3分）（4）计算出等概率情况下查找失败的平均查找长度（3分）012345678910111239 54 28 55 31 19 23 25 12 51 64 解：（1）由=0.75，得表长m=11/0.75=15，取P=13（p取小于等于表长的最大素数），得 散列函数H（k）=k MOD 13（2）因为p=13，散列地

8、址取0到12，用链地址法解决冲突，实际长就取13，画出链地址表如图（3）查找成功：ASL = (17 + 22 + 31 + 41)/11 = 18/11（4）查找不成功：ASL = (16 + 25 + 31 + 51)/13 = 24/135 已知散列表长度为13，散列函数为H(key)=key % 11，处理冲突的方法为线性探测法，请画出依次插入关键字(10,8,40,27,21,57,46,23,19,56)以后的散列表，并计算查找成功和不成功时的平均查找长度。6 对关键字序列(56，20，23，75，29，61，36，87) 进行堆排序，使之按关键字递增次序排列，请写出排序过程中建初始堆的过程。7 对关键字序列(42，13，24，91，23，16，05，58)进行堆排序，使之按关键字递增次序排列，请写出排序过程中建初始堆的过程。四、 证明题1 写出求