电科20春《数据结构》在线作业1.docx

《电科20春《数据结构》在线作业1.docx》由会员分享，可在线阅读，更多相关《电科20春《数据结构》在线作业1.docx（11页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、电科20春数据结构在线作业120春数据结构在线作业1试卷总分:100得分：100一、单选题（共16道试题，共48分）L通常将链串的结点大小设置为大于工是为 了（）。A.提高存储密度B.提高串匹配效率C.便于插入操作D.便于删除操作2,从顺序表中删除一个元素时，表中所有在 被删元素之后的元素均需（）。A.视情况而定B.后移一个位置C.前移一个位置D.不动3 .在计算机内实现递归算法时所需的辅助数38 .在一个长度为n的单链表L中，删除链表 中*p的前驱结点的时间复杂度为0(n)。39 .假设以行优先顺序存储三维数组A,其中 元素A的地址为1100,并且每一个元素占2个存储单元，则A的地址是126

2、4 o40 .删除二叉排序树中一个结点，再重新插入 上去，一定能得到原来的二叉排序树。据结构是（）。A.队列B.树C.栈D.图 4下面程序段的时间复杂度是()ofor(i=0;in;i+) for(j=l;jm;j+) A=0；A.O(n)B.O(m+n+l)C.O(m+n)D.O(m*n)5 .若进栈序列为1, 2, 3, 4, 5, 6,且进栈 和出栈可以穿插进行，则可能浮现的出栈序列为（）oA.5 ， 6,4,2, 3,B3, 4, 2, 1, 6, 5C3, 2, 6, 1, 4, 5D.1, 2, 5, 3, 4, 66 .已知一棵彻底二叉树有64个叶子结点，则Word文档下载后可自

3、行编辑 该树可能达到的最大深度为（）。 A.9B.8C.7D.107 .已知在一棵度为3的树中，度为2的结点 数为4,度为3的结点数为3,则该树中的 叶子结点数为（）。A.8B.5C.18D.118 .在数据结构中，数据的逻辑结构可以分成 （）oA.线性结构和非线性结构B.紧凑结构和非紧揍结构C.动态结构和静态结构 D.内部结构和外部结构9,若进栈序列为a,b,c,则通过入出栈操作可能得到的a,b,c的不同罗列个数为（）。A.6#7B.5C.410 .在长度为n的顺序表的第i（BKn+l）个位 置上插入一个元素，元素的挪移次数为（）。A.n-i+1B.n-iC.i-1D.i11 .对于哈希函数

4、H（key）=key%13,被称为同义 词的关键字是（）。A.35 和 4112 25 和 51C.23 和 39D.15 和 4412 .在目标串T二xwxxyxy中，对模式串P=xy进行子串定位操作的结果是（）。A.5B.3C.2D.0不改变数据元素13 .在线性表的下列运算中, 之间结构关系的运算是（A.插入B.排序C.定位D删除14 .已知栈的最大容量为4o若进栈序列为1, 2, 3, 4, 5, 6,且进栈和出栈可以穿插进 行，则可能浮现的出栈序列为（）。A.5 , 4 , 3 9 2 ,1, 6B.3, 2, 5, 4, 1, 6C.2, 3, 5, 6, 1, 4D.l, 4,

5、6, 5, 2, 3 15.计算机识别、存储和加工处理的对象被统称为（）。A.数据结构B.数据类型C.数据元素D.数据16 .在头指针为head的非空单循环链表中, 指针P指向尾结点，下列关系成立的是（）。 A.p-next-next=headB.p-next=headC.p-next=NULLD.p=head二、多选题（共2道试题，共8分）17 .算法以下几种特性（）。A.输入和输出B.确定性C.有穷性D.可行性18 . 一个好的算法有（）设计要求。A.正确性B.效率与低存储量要求C.可读性D.茁壮性三、判断题（共22道试题，共44分）19 .已知在一棵含有n个结点的树中，惟独度 为k的分支

6、结点和度为0的叶子结点，则该 树中含有的叶子结点的数目为ko20 .假设以S和X分别表示进栈和退栈操作， 则对输入序列a,b,c,d,e进行一系列栈操作 SSXSXSSXXX之后，得到的输出序列为abbc c d d e d c 。21 .在链表的结点中，数据元素所占的存储量 和整个结点所占的存储量之比称作存储密 度。22 .含n个顶点的无向连通图中至少含有n 条边。23 .在对链队列作出队操作时,不会改变front 指针的值。24 ,对任何一棵二叉树，如果其终端结点数为 nO,度为2的结点数为n2,则n0=n2+lo25 .串 S=I am a worker”的长度是 10。26 .空格串的

7、长度是空格的个数。27 .假设三维数组A按行优先顺序存储，若每 个元素占3个存储单元，且首地址为100, 则元素A的存储地址是501 o28 .若一个算法中的语句频度之和为 T(n)=3720n+4nlogn,则算法的时间复杂度为 0(n)o29 .对一棵有100个结点的彻底二叉树按层 编号，则编号为49的结点，它的左孩子的 编号为98o30 .由于希尔排序的最后一趟与直接插入排 序过程相同，因此前者一定比后者花费的时间多。31 .若一棵满三叉树中含有121个结点，则该 树的深度为6o32 .在一个长度为n的循环链表中，删除其元 素值为X的结点的时间复杂度为0(n)。33 .深度为15的满二叉树上，第11层有2八11 个结点。34 .在无向图中，若从顶点a到顶点b存在通 路，则称a与b之间是连通的。35 .队列的修改是按照先进先出的原则进行 的。36 .在队列中，允许进行插入操作的一端称为 队头。37 .抽象数据类型是指数据逻辑结构及与之 相关的操作。