数据结构考试试题

一、单项选择题(共40分，每题2分)1.树形结构是数据元素之间存在一种（D）。A.一对一关系B.多对多关系C.多对一关系D.一对多关系2.设语句x++的时间是单位时间，则以下语句的时间复杂度为（B）。for(i=1;i=n;i++)for(j=i;j=n;j++)x++;A.O(1)B.O(2n)C.O(n)D.O(3n)3.线性表是（A）。A．一个有限序列，可以为空B．一个有限序列，不可以为空C．一个无限序列，可以为空D．一个无限序列，不可以为空4.在顺序表中，只要知道（D），就可在相同时间内求出任一结点的存储地址。A．基地址B．结点大小C．向量大小D．基地址和结点大小5.设有一个栈，元素的进栈次序为A,B,C,D,E,下列是不可能的出栈序列（C）。A．A,B,C,D,EB．B,C,D,E,AC．E,A,B,C,DD．E,D,C,B,A6.一个子串在包含它的主串中的位置是指（D）。A.子串的最后那个字符在主串中的位置B.子串的最后那个字符在主串中首次出现的位置C.子串的第一个字符在主串中的位置D.子串的第一个字符在主串中首次出现的位置7.已知二维数组A10×10中，元素a20的地址为560，每个元素占4个字节，则元素a10的地址为（A）。A.520B.522C.524D.5188.假设在一棵二叉树中，双分支结点数为15，单分支结点数为30个，则叶子结点数为（B）个。A.15B.16C.17D.479.在一棵二叉树上第4层的结点数最多为（D）。A.2B.4C.6D.810.已知一棵完全二叉树的结点总数为9个，则最后一层的结点数为（B）。A.1B.2C.3D.411.下面叙述正确的是（D）。A.二叉树是特殊的树B.二叉树等价于度为2的树C.完全二叉树必为满二叉树D.二叉树的左右子树有次序之分12.在一个具有n个顶点的有向图中，若所有顶点的出度数之和为s，则所有顶点的入度数之和为(A)。A.sB.s-1C.s+1D.n13.在一个具有n个顶点的无向完全图中，所含的边数为(C)。A.nB.n(n-1)C.n(n-1)/2D.n(n+1)/214.在一个无向图中，若两顶点之间的路径长度为k，则该路径上的顶点数为(B)。A.kB.k+1C.k+2D.2k15.对于长度为18的顺序存储的有序表，若采用折半查找，则查找第15个元素的比较次数为(B)。A.3B.4C.5D.616.若根据查找表(23,44,36,48,52,73,64,58)建立哈希表，采用h(K)=K%13计算哈希地址，则元素64的哈希地址为(C)。A.4B.8C.12D.1317.假定对元素序列（7,3,5,9,1,12,8,15）进行快速排序，则进行第一次划分后，得到的左区间中元素的个数为（B）。A.2B.3C.4D.518.假定对元素序列（7,3,5,9,1,12）进行堆排序，并且采用小根堆，则由初始数据构成的初始堆为（B）。A.1,3,5,7,9,12B.1,3,5,9,7,12C.1,5,3,7,9,12D.1,5,3,9,12,719.设有广义表D=(a,b,D)，其长度为（B），深度为（A）。A.无穷大B.3C.2D.520.假定在数组A中，每个元素的长度为3个字节，行下标i从1到8，列下标j从1到10，从首地址SA开始连续存放在存储器内，存放该数组至少需要的单元数为（C）。A.80B.100C.240D.270二、填空题(共10分,每题1分)1.线性结构中元素之间存在_____一对一_____关系；树型结构中元素之间存在_____一对多____关系；图型结构中元素之间存在_______多对多______关系。2.一个算法的效率可分为_______时间______效率和_____空间_____效率。3.顺序表中逻辑上相邻的元素的物理位置__也相邻_____。4.由三个结点构成的二叉树，共有__5__种不同的形态5.设有一空栈，现有输入序列1，2，3，4，5，经过push,push,pop,push,pop,push,push后，输出序列是___23541______。6.一个广义表为(a,(a,b),d,e,((i,j),k))，则该广义表的长度为__5___，深度为___3__。7.对于一棵具有n个结点的二叉树，若一个结点的编号为i(1≤i≤n)，则它的左孩子结点的编号为____2i____，右孩子结点的编号为____2i+1____，双亲结点的编号为i/2（或i/2）。8.表示图的两种存储结构为_____邻接矩阵_____和___邻接表_______。9.图中的一条路径长度为k，该路径所含的顶点数为__k+1______。10.对线性表(18,25,63,50,42,32,90)进行哈希存储时，若选用H(K)=K%9作为哈希函数，则哈希地址为0的元素有____3____个，哈希地址为5的元素有_____2___个。三、简答题(共30分)1.线性表的定义及其两种存储方式参考答案：线性表是n个数据元素的有限序列，其中n（n≥0）为线性表的长度。顺序表是指线性表的顺序存储结构，即用一组连续的存储单元依次存放线性表的数据元素。链表是线性表的链式存储结构。链表是用一组任意的存储单元（可以是连续的，也可以是不连续的）存放线性表的数据元素。2.一棵度为2的树与一棵二叉树有什么区别？参考答案：度为2的树有两个分支，但分支没有左右之分；一棵二叉树也有两个分支，但有左右之分，左右子树的次序不能交换。3.假定用于通信的电文由8个字符A、B、C、D、E、F、G、H组成，各字母在电文中出现的概率为5％、25％、4％、7％、9％、12％、30％、8％，试为这8个字母设计哈夫曼编码。参考答案：第七步：2530954918712815274357第八步：2595491843307128152757100设计哈夫曼编码利用得到的哈夫曼树，规定左分支用0表示，右分支用1表示，字母A、B、C、D、E、F、G、H的哈夫曼编码如下表示：A:0011B:01C:0010D:1010E:000F:100G:11H:10114.对于如下图所示的带权无向图，用图示说明：（1）利用prim算法从顶点a开始构造最小生成树的过程；（2）利用kruskal算法构造最小生成树的过程。3e1fdcbag97946218548带权无向图参考答案：1、利用Prim算法从顶点a开始构造最小生成树的过程如图所示。aefdcbg初始状态aefdcbg连通e2aefdcbg连通g21aefdcbg连通d2133aefdcbg连通f2143aefdcbg连通b2146图6-9用Prim算法构造最小生成树的过程3aefdcbg连通c214612、利用Kruskal算法构造最小生成树的过程如图所示。aefdcbg初始状态aefdcbg增加第2条边11aefdcbg增加第1条边13aefdcbg增加第5条边21413aefdcbg增加第4条边211aefdcbg增加第3条边211图6-10用Kruskal算法构造最小生成树的过程3aefdcbg增加第6条边21461四、算法实现题(共20分)(请考生根据自己所学的语言编写，可以用C、C++、JAVA、C#、PHP中任一种语言实现，如果采用伪代码实现功能成绩减半)1、在整型顺序表的某个位置删除一个值为a的整型元素。参考答案：publicbooleandelete(inti){intj;if(i0||i=length){//检查删除位置是否存在System.out.println(Thepositionismistake.);returnfalse;}for(j=i;jlength;j++){data[j]=data[j+1];length--;returntrue;}}2、折半查找程序实现参考答案：publicclassHalfSearch{publicintBinary_Search(inta[],intk){intlow,high,mid,flag=0;low=1;high=a.length;while(low=high){mid=(low+high)/2;if(ka[mid])high=mid-1;elseif(ka[mid])low=mid+1;else{flag=mid;System.out.println(flag);break;}}returnflag;}一、单项选择题(共40分，每题2分)1.计算机内部数据处理的基本单位是（B）。A.数据B.数据元素C.数据项D.数据库2.设语句x++的时间是单位时间，则以下语句的时间复杂度为（B）。for(i=1;i=n;i++)for(j=i;j=n;j++)x++;A.O(1)B.O(2n)C.O(n)D.O(3n)3.线性表采用链式存储时，其地址（D）。A．必须是连续的B．一定是不连续的C．部分地址必须是连续的D．连续与否均可以4.以下关于线性表的说法不正确的是（C）。A．线性表中的数据元素可以是数字、字符、记录等不同类型。B．线性表中包含的数据元素个数不是任意的。C．线性表中的每个结点都有且只有一个直接前趋和直接后继。D．存在这样的线性表：表中各结点都没有直接前趋和直接后继。5.设有一个栈，元素的进栈次序为A,B,C,D,E,下列是不可能的出栈序列（C）。A．A,B,C,D,EB．B,C,D,E,AC．E,A,B,C,DD．E,D,C,B,A6.两个字符串相等的条件是（D）。A.两串的长度相等B.两串包含的字符相同C.两串的长度相等，并且两串包含的字符相同D.两串的长度相等，并且对应位置上的字符相同7.已知二维数组A10×10中，元素a20的地址为560，每个元素占4个字节，则元素a10的地址为（A）。A.520B.522C.524D.5188.用顺序存储的方法将完全二叉树中的所有结点逐层存放在数组中R[1..n]，结点R[i]若有左孩子，其左孩子的编号为结点（B）。A.R[2i+1]B.R[2i]C.R[i/2]D.R[2i-1]9.下面叙述正确的是（D）。A.二叉树是特殊的树B.二叉树等价于度为2的树C.完全二叉树必为满二叉树D.二叉树的左右子树有次序之分10.已知一棵完全二叉树的结点总数为9个，则最后一层的结点数为（B）。A.1B.2C.3D.411.在一个具有n个顶点的有向图中，若所有顶点的出度数之和为s，则所有顶点的度数之和为(D)。A.sB.s-1C.s+1D.2s12.在一个具有n个顶点的无向图中，若具有e条边，则所有顶点的度数之和为(D)。A.nB.eC.n+eD.2e13.在一个具有n个顶点的有向完全图中，所含的边数为(B)。A.nB.n(n-1)C.n(n-1)/2D.n(n+1)/214.若要把n个顶点连接为一个连通图，则至少需要(C)条边。A.nB.n+1C.n-1D.2n15.对于顺序存储的有序表(5,12,20,26,37,42,46,50,64)，若采用折半查找，则查找元素26的比较次数为(C)。A.2B.3C.4D.516.若根据查找表(23,44,36,48,52,73,64,58)建立哈希表，采用h(K)=K%7计算哈希地址，则哈希地址等于3的元素个数(B)。A.1B.2C.3D.417.数组A中，每个元素的长度为3个字节，行下标i从1到8，列下标j从1到10，从首地址SA开始连续存放在存储器内，该数组按行存放时，元素A[8][5]的起始地址为（C）。A.SA+141B.SA+144C.SA+222D.SA+22518.假定对元素序列（7,3,5,9,1,12）进行堆排序，并且采用小根堆，则由初始数据构成的初始堆为（B）。A.1,3,5,7,9,12B.1,3,5,9,7,12C.1,5,3,7,9,12D.1,5,3,9,12,719.假定对元素序列（7,3,5,9,1,12,8,15）进行快速排序，则进行第一次划分后，得到的左区间中元素的个数为（B）。A.2B.3C.4D.520.下面的说法中，只有（C）是正确的。A.字符串的长度是指串中包含的字母的