1、2018年数据结构试题一、选择题30分1下列程序段的时间复杂度为。AOMNTBOMNTCOMNTDOMTN2设顺序线性表中有N个数据元素，则删除表中第I个元素需要移动个元素。ANIBNLICN1IDI3设F是由T1、T2和T3三棵树组成的森林，与F对应的二叉树为B，T1、T2和T3的结点数分别为N1、N2和N3，则二叉树B的根结点的左子树的结点数为。AN11BN21CN2N3DN1N34利用直接插入排序法的思想建立一个有序线性表的时间复杂度为。AONBONLOG2NCON2DO1OG2N5设指针变量P指向双向链表中结点A，指针变量S指向插入的结点X，则在结点A的后面插入结点X的操作序列为。AP
2、RIGHTSSLEFTPPRIGHTLEFTSSRIGHTPRIGHTBSLEFTPSRIGHTPRIGHTPRIGHTSPRIGHTLEFTSCPRIGHTSPRIGHTLEFTSSLEFTPSRIGHTPRIGHTDSLEFTPSRIGHTPRIGHTPRIGHTLEFTSPRIGHTS6下列各种排序算法中平均时间复杂度为ON2是。A快速排序B堆排序C归并排序D冒泡排序7设输入序列1、2、3、N经过栈作用后，输出序列中的第一个元素是N，则输出序列中的第I个输出元素是。ANIBN1ICNLID不能确定8设散列表中有M个存储单元，散列函数HKEYKEYP，则P最好选择。A小于等于M的最大奇数B
3、小于等于M的最大素数C小于等于M的最大偶数D小于等于M的最大合数9设在一棵度数为3的树中，度数为3的结点数有2个，度数为2的结点数有1个，度数为1的结点数有2个，那么度数为0的结点数有个。A4B5C6D710设完全无向图中有N个顶点，则该完全无向图中有条边。ANN1/2BNN1CNN1/2DN1/211设顺序表的长度为N，则顺序查找的平均比较次数为。ANBN/2CN1/2DN1/212设有序表中的元素为13，18，24，35，47，50，62，则在其中利用二分法查找值为24的元素需要经过次比较。A1B2C3D413设顺序线性表的长度为30，分成5块，每块6个元素，如果采用分块查找，则其平均查找
4、长度为。A6B11C5D6514设有向无环图G中的有向边集合E，则下列属于该有向图G的一种拓扑排序序列的是。A1，2，3，4B2，3，4，1C1，4，2，3D1，2，4，315设有一组初始记录关键字序列为34，76，45，18，26，54，92，则由这组记录关键字生成的二叉排序树的深度为。A4B5C6D7二、填空题30分1设指针P指向单链表中结点A，指针S指向插入的结点X，则在结点A的前面插入结点X时的操作序列为1SNEXT_2PNEXTS3TPDATA4PDATA_5SDATAT2设某棵完全二叉树中有100个结点，则该二叉树中有_个叶子结点。3设某顺序循环队列中有M个元素，且规定队头指针F指
5、向队头元素的前一个位置，队尾指针R指向队尾元素的当前位置，则该循环队列中最多存储_队列元素。4对一组初始关键字序列40，50，95，20，15，70，60，45，10进行冒泡排序，则第一趟需要进行相邻记录的比较的次数为_，在整个排序过程中最多需要进行_趟排序才可以完成。5在堆排序和快速排序中，如果从平均情况下排序的速度最快的角度来考虑应最好选择_排序，如果从节省存储空间的角度来考虑则最好选择_排序。6设一组初始记录关键字序列为20，12，42，31，18，14，28，则根据这些记录关键字构造的二叉排序树的平均查找长度是_。7设一棵二叉树的中序遍历序列为BDCA，后序遍历序列为DBAC，则这棵二
6、叉树的前序序列为_。8设用于通信的电文仅由8个字母组成，字母在电文中出现的频率分别为7、19、2、6、32、3、21、10，根据这些频率作为权值构造哈夫曼树，则这棵哈夫曼树的高度为_。9设一组记录关键字序列为80，70，33，65，24，56，48，则用筛选法建成的初始堆为_。1010设无向图G如右图所示，则其最小生成树上所有边的权值之和为_。三、判断题20分1有向图的邻接表和逆邻接表中表结点的个数不一定相等。2对链表进行插入和删除操作时不必移动链表中结点。3子串“ABC”在主串“AABCABCD”中的位置为2。4若一个叶子结点是某二叉树的中序遍历序列的最后一个结点，则它必是该二叉树的先序遍历序列中的最后一个结点。5希尔排序算法的时间复杂度为ON2。6用邻接矩阵作为图的存储结构时，则其所占用的存储空间与图中顶点数无关而与图中边数有关。7中序遍历一棵二叉排序树可以得到一个有序的序列。8入栈操作和入队列操作在链式存储结构上实现时不需要考虑栈溢出的情况。9顺序表查找指的是在顺序存储结构上进行查找。10堆是完全二叉树，完全二叉树不一定是堆。四、算法设计题20分1设计计算二叉树中所有结点值之和的算法。2设计将所有奇数移到所有偶数之前的算法。3设计判断单链表中元素是否是递增的算法。
