《数据结构模拟试题(1)75980.doc》由会员分享，可在线阅读，更多相关《数据结构模拟试题(1)75980.doc（9页珍藏版）》请在金锄头文库上搜索。
1、数据结构模拟试题(1)75980很多人的理想是要改变这个世界,但却很少有人愿意去改变自己。数据结构模拟试题（1）一、填空题:06分，每题02分 1、 从一个具有n个结点的单链表中搜索其值等于x的结点时, 在搜索成功的情况下, 需平均比较_次。2、 根据一组记录(56,42,50,64,48)依次插入结点生成一棵AVL树时，当插入到值为_的结点时需要进行旋转调整。3、 根据一组记录(56,74,63,64,48)依次插入结点生成一棵AVL树时，当插入到值为63的结点时需要进行_调整。单选题:10分，每题02分4、 某算法的时间代价为T(n)=100n+10nlog2n+n2+10，其时间复杂度为
2、（ ）。A:O(n)B:O(nlog2n)C:O(n2)D:O(1)5、从一个长度为n的顺序表中顺序搜索一个值为x的元素时，在等概率的情况下，搜索成功时的平均比较次数为（ ）。A:nB:n/2C:(n+1)/2D:(n-1)/26、在一个长度为n的顺序表中删除第i个元素（0in-1）时，需要从前向后依次前移（ ）个元素。A:n-IB:n-I+1C:n-i-1D:I7、 不带头结点的单链表first为空的判定条件是( )。A:first = NULL;B:first-link = NULL;C:first-link = first;D:D. first != NULL;8、 树中所有结点的度之和
3、等于所有结点数加( )。A:0B:1C:1D:29、 一棵具有35个结点的完全二叉树的高度为( )。假定空树的高度为 -1。A:5B:6C:7D:810、 对于具有e条边的无向图，它的邻接表中有 ( ) 个边结点。A:e-1B:eC:2(e-1)D:2e11、 图的深度优先搜索类似于树的（ ）次序遍历。A:先根B:中根C:后根D:层次12、 设有向图有n个顶点和e条边，采用邻接表作为其存储表示，在进行拓扑排序时，总的计算时间为（ ）。A:O(nlog2e)B:O(n+e)C:O(ne) D:O(n2)13、 在下列排序算法中，( )算法使用的附加空间与输入序列的长度及初始排列无关。A:锦标赛排
4、序B:快速排序C:基数排序D:归并排序二、判断题:10分，每题01分14、 数组是一种静态的存储空间分配，就是说，在程序设计时必须预先定义数组的数据类型和存储空间大小，由编译程序在编译时进行分配。15、 在顺序表中，逻辑上相邻的元素在物理位置上不一定相邻。16、 每次从队列中取出的是具有最高优先权的元素, 这种队列就是优先级队列。17、 若让元素1,2,3依次进栈，则出栈次序1,3,2是不可能出现的情况。18、 递归的算法简单、易懂、容易编写，而且执行效率也高。19、 用非递归方法实现递归算法时一定要使用递归工作栈。20、 一个广义表的表头总是一个广义表。21、 对用顶点表示活动的网络（AOV
5、网）进行拓扑排序必然得到唯一的结果。22、 堆排序是一种稳定的排序算法。23、 在散列法中采取开散列（链地址）法来解决冲突时, 其装载因子的取值一定在(0,1)之间。三、中型计算题:10分，每题10分24、 设有一个nn的对称矩阵A，将其上三角部分按列压缩存放于一个一维数组B中：B=A00, A01, A11, A02, A12, A22, ., A0 n-1, A1 n-1, A2 n-1, ., An-1 n-1同时有两个函数：max(i,j)和min(i,j)，分别计算下标i和j中的大者与小者。试利用它们给出求任意一个Aij在B中存放位置的公式。（若式中没有max(i,j)和min(i,
6、 j) 则不给分）参考答案：max(i,j)*(max(i,j)+1)/2+min(i,j)25、 设有一个三维数组A102015，按页/行/列存放于一个连续的存储空间中，每个数组元素占4个存储字，首元素A000的存储地址是1000，求A8410的地址。参考答案：10880答案解释：对于三维数组，若第一、第二、第三维的元素个数为m1、m2、m3，每个元素所占存储字数为d，首地址为LOC(0,0,0)，则对于任一数组元素Aijk，它的存储地址为LOC(i,j,k)=LOC(0,0,0)+(i*m2*m3+j*m3+k)*d根据题意，m1=10, m2=20, m3=15, d=4, LOC(0,
7、0,0)=1000，则有LOC(8,4,10)=LOC(0,0,0)+(8*20*15+4*15+10)*4=1000+2470*4=1088026、 下图是一个3阶B树，试给出依次插入65和15之后B树的单关键码结点数和双关键码结点数。单关键码结点数：双关键码结点数：参考答案：单关键码结点数：9 双关键码结点数：2 四、小型计算题:40分，每题08分27、 设有一个二维数组A1020，按列存放于一个连续的存储空间中，A00的存储地址是200，每个数组元素占1个存储字，则A62的地址是多少。参考答案：226答案说明： 按列存储时，计算Aij地址的公式为 LOC(i,j)=LOC(0,0)+(j
8、*m+i)*d 其中首地址LOC(0,0)=200, 每个数组元素的存储占用数d=1, 二维数组的行数m=10，则数组元素A62的存储地址为 LOC(6,2)=200+(2*10+6)*1=22628、 设有一个1010的对称矩阵A，将其上三角部分按行存放在一个一维数组B中，A00存放于B0中，那么A85存放于B中什么位置。参考答案：43答案说明： 很多人的理想是要改变这个世界,但却很少有人愿意去改变自己。根据题意，矩阵A中当元素下标I与J满足IJ时，任意元素AIJ在一维数组B中的存放位置为(2*nI1)*I/2+J但当IJ时，需要计算其对称元素AJI在B中的存放位置(2*nJ1)*J/2+I
9、因此，A85在数组B中对称元素AJI的位置为(2*1051)*5/2+8=4329、 已知一个有序表(15,26,34,39,45,56,58,63,74,76,83,94)顺序存储于一维数组a12中，根据折半搜索过程填写成功搜索下表中所给元素34, 56, 58, 63, 94时的比较次数。参考答案：元素 34 56 58 63 94比较次数 2 1 3 4 4 30、 已知一棵二叉搜索树的广义表表示为：28(12(,16),49(34(30),72(63)，求出从中依次删除72,12,49,28结点，最后得到的二叉搜索树的广义表表示。广义表表示：参考答案：广义表表示：30(16,63(34
10、)31、 已知一个数据表为48,25,56,32,40，请写出在进行快速排序的过程中每次划分后数据表的变化。 (0) 48 25 56 32 40(1) (2)(3)参考答案：(0) 48 25 56 32 40(1) 40 25 32 48 56(2) 32 25 40 48 56(3) 25 32 40 48 56 32、 已知有一个数据表为30,18,20,15,38,12,44,53,46,18*,26,86，给出进行归并排序的过程中每一趟排序后的数据表变化。(0) 30 18 20 15 38 12 44 53 46 18* 26 86(1)(2)(3)(4)参考答案：(0) 30
11、18 20 15 38 12 44 53 46 18* 26 86(1) 18 3015 2012 3844 5318* 4626 86(2) 15 18 20 3012 38 44 5318* 26 46 86(3) 12 15 18 20 30 38 44 5318* 26 46 86(4) 12 15 18 18* 20 26 30 38 44 46 53 8633、 设散列表为HT17, 待插入关键码序列为Jan, Feb, Mar, Apr, May, June, July, Aug,Sep,Oct,Nov,Dec，散列函数为H(key)=?i/2?，其中i是关键码第一个字母在字母表
12、中的序号（字母A在字母表中的序号为1，以下类推），采用线性探查法解决冲突。根据建立的闭散列表，搜索长度大于等于3的关键码有那些？搜索长度大于等于3的关键码有：参考答案：搜索长度大于等于3的关键码有：June,July,Oct,Nov五、综合题:20分，每题10分34、 已知二叉树中的结点类型BinTreeNode定义为: struct BinTreeNode ElemType data; BinTreeNode *left, *right;其中data为结点值域，left和right分别为指向左、右子女结点的指针域。参数bt指向一棵二叉树，引用参数x一开始具有的值小于树中所有结点的值。试根据下面的函数定义指出此算法的功能。 int JB(BinTreeNode* bt, ElemType& x) if(bt=NULL) return 1; else if(JB(bt-left,x)=0) return 0; if(bt-datadata; if(JB(bt-right,x)=0) return 0; else return 1; 算法功能：参考答案：算法功能：判断二叉树bt是否为一棵二叉搜索树，若是则返回1否则返回0。六、填空题(主观):04分，每题02分35、 快速排序在平均情况下的空间复杂度为
