17春《数据结构》在线作业1 一、单选题: 1.从顺序表中删除一个元素时,表中所有在被删元素之后的元素均需( )。 (满分:3) A. 前移一个位置 B. 后移一个位置 C. 不动 D. 视情况而定 答案下载请进下面的地址 2.已知栈的最大容量为4。若进栈序列为1,2,3,4,5,6,且进栈和出栈可以穿插进行,则可能出现的出栈序列为( )。 (满分:3) A. 5,4,3,2,1,6 B. 2,3,5,6,1,4 C. 3,2,5,4,1,6 D. 1,4,6,5,2,3 3.逻辑上通常可以将数据结构分为( )。 (满分:3) A. 动态结构和静态结构 B. 顺序结构和链式结构 C. 线性结构和非线性结构 D. 初等结构和组合结构 4.执行下列程序段后,串X的值为( )。 S=〞abcdefgh〞; T=〞xyzw〞; substr(X,S,2,strlen(T)); substr(Y,S, stelen(T),2); strcat(X,Y); (满分:3) A. 〞cdefgh〞 B. 〞cdxyzw〞 C. 〞cdefxy〞 D. 〞cdefef〞 5.在单链表中,指针p指向元素为x的结点,实现“删除x的后继”的语句是( )。 (满分:3) A. p=p->next B. p->next=p->next->next C. p->next=p D. p=p->next->next; 6.已知指针p和q分别指向某单链表中第一个结点和最后一个结点。假设指针s指向另一个单链表中某个结点,则在s所指结点之后插入上述链表应执行的语句为( )。 (满分:3) A. q->next=s->next;s->next=p B. s->next=p;q->next=s->next C. p->next=s->next;s->next=q D. s->next=q;p->next=s->next 7.算法分析的目的是( )。 (满分:3) A. 辨别数据结构的合理性 B. 评价算法的效率 C. 研究算法中输入与输出的关系 D. 鉴别算法的可读性 8.与线性表相比,串的插入和删除操作的特点是( )。 (满分:3) A. 通常以串整体作为操作对象 B. 需要更多的辅助空间 C. 算法的时间复杂度较高 D. 涉及移动的元素更多 9.若线性表的插入和删除操作频繁地在表头或表尾位置进行,则更适宜采用的存储结构为( )。 (满分:3) A. 无头结点的双向链表 B. 带尾指针的循环链表 C. 无头结点的单链表 D. 带头指针的循环链表 10.下面程序段的时间复杂度为( )。for(i=0; i A. O(m2) B. O(n2) C. O(m*n) D. O(m+n) 11.设串sl=″Data Structures with Java″,s2=″it″,则子串定位函数index(s1,s2)的值为( )。 (满分:3) A. 15 B. 16 C. 17 D. 18 12.在以单链表为存储结构的线性表中,数据元素之间的逻辑关系用( )。 (满分:3) A. 数据元素的相邻地址表示 B. 数据元素在表中的序号表示 C. 指向后继元素的指针表示 D. 数据元素的值表示 13.n个顶点的有向完全图中含有向边的数目最多为( )。 (满分:3) A. n-1 B. n C. n(n-1)/2 D. n(n-1) 14.栈和队列都是( )。 (满分:3) A. 限制存取位置的线性结构 B. 顺序存储的线性结构 C. 链式存储的线性结构 D. 限制存取位置的非线性结构 15.计算机识别、存储和加工处理的对象被统称为( )。 (满分:3) A. 数据 B. 数据元素 C. 数据结构 D. 数据类型 16.无向图中一个顶点的度是指图中( )。 (满分:3) A. 通过该顶点的简单路径数 B. 与该顶点相邻接的顶点数 C. 通过该顶点的回路数 D. 与该顶点连通的顶点数 二、多选题: 1.假设按照12345的进栈顺序,下面哪些是可能的出栈顺序( )。 (满分:4) A. 12345 B. 54321 C. 43215 D. 14325 2.数据的逻辑结构通常包括( )。 (满分:4) A. 集合 B. 线性 C. 树 D. 图 三、判断题: 1.在最好和最坏情况下的时间复杂度均为O(nlogn)且稳定的排序方法是堆排序。 (满分:2) A. 错误 B. 正确 2.二叉树中必有度为2的结点。 (满分:2) A. 错误 B. 正确 3.二叉树中的叶子结点就是二叉树中没有左右子树的结点。 (满分:2) A. 错误 B. 正确 4.假设为循环队列分配的向量空间为Q[20],若队列的长度和队头指针值分别为13和17,则当前尾指针的值为15。 (满分:2) A. 错误 B. 正确 5.对一棵有100个结点的完全二叉树按层编号,则编号为49的结点,它的左孩子的编号为98。 (满分:2) A. 错误 B. 正确 6.有向图用邻接矩阵表示后,顶点i的入度等于邻接矩阵中第i列的元素个数。 (满分:2) A. 错误 B. 正确 7.在一个长度为n的单链表L中,删除链表中*p的前驱结点的时间复杂度为 O(n)。 (满分:2) A. 错误 B. 正确 8.二叉树中结点只有一个孩子时无左右之分。 (满分:2) A. 错误 B. 正确 9.深度为15的满二叉树上,第11层有2^11个结点。 (满分:2) A. 错误 B. 正确 10.在链表的结点中,数据元素所占的存储量和整个结点所占的存储量之比称作存储密度。 (满分:2) A. 错误 B. 正确 11.给出不同的输入序列建造二叉排序树,一定得到不同的二叉排序树。 (满分:2) A. 错误 B. 正确 12.数据的逻辑结构描述数据元素之间的逻辑关系,与存储方式无关。 (满分:2) A. 错误 B. 正确 13.设S1="good",S2=" ",S3="book",则S1,S2和S3依次联接后的结果是”good book” 。 (满分:2) A. 错误 B. 正确 14.在最好和最坏情况下的时间复杂度均为O(nlogn)且稳定的排序方法是归并排序。 (满分:2) A. 错误 B. 正确 15.二叉树是度为2的有序树。 (满分:2) A. 错误 B. 正确 16.若一个算法中的语句频度之和为T(n)=3720n+4nlogn,则算法的时间复杂度为 O(n)。 (满分:2) A. 错误 B. 正确 17.假设以行优先顺序存储三维数组A[5][6][7],其中元素A[0][0][0]的地址为1100,且每个元素占2个存储单元,则A[4][3][2]的地址是1264。 (满分:2) A. 错误 B. 正确 18.在文本编辑程序中查找某一特定单词在文本中出现的位置,可以利用串的定位操作。 (满分:2) A. 错误 B. 正确 19.在队列中,允许进行插入操作的一端称为队头。 (满分:2) A. 错误 B. 正确 20.抽象数据类型是指数据逻辑结构及与之相关的操作。 (满分:2) A. 错误 B. 正确 21.含n个顶点的无向连通图中至少含有n条边。 (满分:2) A. 错误 B. 正确 22.两个串相等的充分必要条件是两个串的长度相等且字母相同。 (满分:2) A. 错误 B. 正确 17春《数据结构》在线作业2 一、单选题: 1.在一个具有n个顶点的有向图中,所有顶点的出度之和为Dout ,则所有顶点的入度之和为( )。 (满分:3) A. Dout B. Dout-1 C. Dout+1 D. n 2.对于哈希函数H(key)=key%13,被称为同义词的关键字是( )。 (满分:3) A. 35和41 B. 23和39 C. 15和44 D. 25和51 3.在具有n个结点的有序单链表中插入一个新结点并使链表仍然有序的时间复杂度是( )。 (满分:3) A. O(1) B. O(n) C. O(n㏒n) D. O(n2) 4.在线性表的下列运算中,不改变数据元素之间结构关系的运算是( )。 (满分:3) A. 插入 B. 删除 C. 排序 D. 定位 5.已知函数Sub(s,i,j)的功能是返回串s中从第i个字符起长度为j的子串,函数Scopy(s,t)的功能为复制串t到s。若字符串S=″SCIENCESTUDY″,则调用函数Scopy(P,Sub(S,1,7))后得到( )。 (满分:3) A. P=″SCIENCE″ B. P=″STUDY″ C. S=″SCIENCE″ D. S=″STUDY″ 6.二叉树中第5层上的结点个数最多为( )。 (满分:3) A. 8 B. 15 C. 16 D. 32 7.若算法中语句的最大频度为T(n)=2006n+6n㏒n+29㏒2n,则其时间复杂度为( )。 (满分:3) A. O(㏒n) B. O(n) C. O(n㏒n) D. O(㏒2n) 8.采用两类不同存储结构的字符串可分别简称为( )。 (满分:3) A. 主串和子串 B. 顺序串和链串 C. 目标串和模式串 D. 变量串和常量串 9.若一棵二叉树有11个叶子结点,则该二叉树中度为2的结点个数是( )。 (满分:3) A. 10 B. 11 C. 12 D. 不确定的 10.在目标串T[0..n-1]=″xwxxyxy″中,对模式串P[0..m-1]=″xy″进行子串定位操作的结果是( )。 (满分:3) A. 0 B. 2 C. 3 D. 5 11.若线性表的插入和删除操作频繁地在表头或表尾位置进行,则更适宜采用的存储结构为( )。 (满分:3) A. 无头结点的双向链表 B. 带尾指针的循环链表 C. 无头结点的单链表 D. 带头指针的循环链表 12.下面程序段的时间复杂度为( )。for(i=0; i A. O(m2) B. O(n2) C. O(m*n) D. O(m+n) 13.高度为5的完全二叉树中含有的结点数至少为( )。 (满分:3) A. 16 B. 17 C. 31 D. 32 14.已知一棵含50个结点的二叉树中只有一个叶子结点,则该树中度为1的结点个数为( )。 (满分:3) A. 0 B. 1 C. 48 D. 49 15.设有两个串T和P,求P在T中首次出现的位置的串运算称作( )。 (满分:3) A. 联接 B. 求子串 C. 字符定位 D. 子串定位 16.若进栈序列为1,2,3,4,5,6,且进栈和出栈可以穿插进行,则可能出现的出栈序列为( )。 (满分:3) A. 3,2,6,1,4,5 B. 3,4,2,1,6,5 C. 1,2,5,3,4,6 D. 5,6,4,2,3,1 二、多选题: 1.由于排序过程中涉及的存储器不同,可以将排序方法分为( )。 (满分:4) A. 稳定排序 B. 不稳定排序 C. 内部排序 D. 外部排序 2.假设按照12345的进栈顺序,下面哪些是可能的出栈顺序( )。 (满分:4) A. 12345 B. 54321 C. 43215 D. 14325 三、判断题: 1.在对链队列作出队操作时,不会改变front指针的值。 (满分:2) A. 错误 B. 正确 2.如果入栈序列是1,3,5,…,97,99,且出栈序列的第一个元素为99,则出栈序列中第30个元素为47。 (满分:2) A. 错误 B. 正确 3.有向图用邻接矩阵表示后,顶点i的入度等于邻接矩阵中第i列的元素个数。 (满分:2) A. 错误 B. 正确 4.假设为循环队列分配的向量空间为Q[20],若队列的长度和队头指针值分别为13和17,则当前尾指针的值为15。 (满分:2) A. 错误 B. 正确 5.假设三维数组A[10][9][8]按行优先顺序存储,若每个元素占3个存储单元,且首地址为100,则元素A[9][8][7]的存储地址是501。 (满分:2) A. 错误 B. 正确 6.空格串的长度是空格的个数。 (满分:2) A. 错误 B. 正确 7.二叉树中必有度为2的结点。 (满分:2) A. 错误 B. 正确 8.一棵含999个结点的完全二叉树的深度为12。 (满分:2) A. 错误 B. 正确 9.在队列中,允许进行插入操作的一端称为队头。 (满分:2) A. 错误 B. 正确 10.在一个长度为n的单链表L中,删除链表中*p的前驱结点的时间复杂度为 O(n)。 (满分:2) A. 错误 B. 正确 11.产生冲突现象的两个关键字称为该散列函数的同义字。 (满分:2) A. 错误 B. 正确 12.深度为15的满二叉树上,第11层有2^11个结点。 (满分:2) A. 错误 B. 正确 13.一棵树可以只有1个结点。 (满分:2) A. 错误 B. 正确 14.队列的修改是按先进先出的原则进行的。 (满分:2) A. 错误 B. 正确 15.删除二叉排序树中一个结点,再重新插入上去,一定能得到原来的二叉排序树。 (满分:2) A. 错误 B. 正确 16.含n个顶点的无向连通图中至少含有n条边。 (满分:2) A. 错误 B. 正确 17.二叉树是度为2的有序树。 (满分:2) A. 错误 B. 正确 18.数据的逻辑结构在计算机存储器内的表示,称为数据的逻辑结构。 (满分:2) A. 错误 B. 正确 19.两个串相等的充分必要条件是两个串的长度相等且字母相同。 (满分:2) A. 错误 B. 正确 20.串S=”I am a worker″的长度是10。 (满分:2) A. 错误 B. 正确 21.二叉树中结点只有一个孩子时无左右之分。 (满分:2) A. 错误 B. 正确 22.栈下溢是指在栈空时进行出栈操作 (满分:2) A. 错误 B. 正确 17春《数据结构》在线作业3 一、单选题: 1.在线性表的下列运算中,不改变数据元素之间结构关系的运算是( )。 (满分:3) A. 插入 B. 删除 C. 排序 D. 定位 2.设串sl=″Data Structures with Java″,s2=″it″,则子串定位函数index(s1,s2)的值为( )。 (满分:3) A. 15 B. 16 C. 17 D. 18 3.从顺序表中删除一个元素时,表中所有在被删元素之后的元素均需( )。 (满分:3) A. 前移一个位置 B. 后移一个位置 C. 不动 D. 视情况而定 4.下面程序段的时间复杂度为( )。for(i=0; i A. O(m2) B. O(n2) C. O(m*n) D. O(m+n) 5.在头指针为head且表长大于1的单循环链表中,指针p指向表中某个结点,若p->next->next=head,则( )。 (满分:3) A. p指向头结点 B. p指向尾结点 C. *p的直接后继是头结点 D. *P的直接后继是尾结点 6.在数据结构中,数据的逻辑结构可以分成( )。 (满分:3) A. 内部结构和外部结构 B. 线性结构和非线性结构 C. 紧凑结构和非紧揍结构 D. 动态结构和静态结构 7.下面程序段的时间复杂度是( )。for(i=0;i A. O(n) B. O(m+n+1) C. O(m+n) D. O(m*n) 8.对于只在表的首、尾两端进行插入操作的线性表,宜采用的存储结构为( )。 (满分:3) A. 顺序表 B. 用头指针表示的单循环链表 C. 用尾指针表示的单循环链表 D. 单链表 9.已知栈的最大容量为4。若进栈序列为1,2,3,4,5,6,且进栈和出栈可以穿插进行,则可能出现的出栈序列为( )。 (满分:3) A. 5,4,3,2,1,6 B. 2,3,5,6,1,4 C. 3,2,5,4,1,6 D. 1,4,6,5,2,3 10.若一棵二叉树有11个叶子结点,则该二叉树中度为2的结点个数是( )。 (满分:3) A. 10 B. 11 C. 12 D. 不确定的 11.在计算机内实现递归算法时所需的辅助数据结构是( )。 (满分:3) A. 栈 B. 队列 C. 树 D. 图 12.判断两个串大小的基本准则是( )。 (满分:3) A. 两个串长度的大小 B. 两个串中首字符的大小 C. 两个串中大写字母的多少 D. 对应的第一个不等字符的大小 13.已知函数Sub(s,i,j)的功能是返回串s中从第i个字符起长度为j的子串,函数Scopy(s,t)的功能为复制串t到s。若字符串S=″SCIENCESTUDY″,则调用函数Scopy(P,Sub(S,1,7))后得到( )。 (满分:3) A. P=″SCIENCE″ B. P=″STUDY″ C. S=″SCIENCE″ D. S=″STUDY″ 14.栈是一种操作受限的线性结构,其操作的主要特征是( )。 (满分:3) A. 先进先出 B. 后进先出 C. 进优于出 D. 出优于进 15.若算法中语句的最大频度为T(n)=2006n+6n㏒n+29㏒2n,则其时间复杂度为( )。 (满分:3) A. O(㏒n) B. O(n) C. O(n㏒n) D. O(㏒2n) 16.若进栈序列为1,2,3,4,5,6,且进栈和出栈可以穿插进行,则可能出现的出栈序列为( )。 (满分:3) A. 3,2,6,1,4,5 B. 3,4,2,1,6,5 C. 1,2,5,3,4,6 D. 5,6,4,2,3,1 二、多选题: 1.一个好的算法有( )设计要求。 (满分:4) A. 正确性 B. 可读性 C. 健壮性 D. 效率与低存储量要求 2.构造最小生成树的两个基本算法是( )。 (满分:4) A. 普里姆算法 B. 克鲁斯卡尔算法 C. 迪杰斯特拉算法 D. 哈希算法 三、判断题: 1.在最好和最坏情况下的时间复杂度均为O(nlogn)且稳定的排序方法是堆排序。 (满分:2) A. 错误 B. 正确 2.在最好和最坏情况下的时间复杂度均为O(nlogn)且稳定的排序方法是基数排序。 (满分:2) A. 错误 B. 正确 3.在有向图中,以顶点v为终点的边的数目称为v的入度。 (满分:2) A. 错误 B. 正确 4.深度为k的二叉树至多有2k-1个结点。 (满分:2) A. 错误 B. 正确 5.设S1="good",S2=" ",S3="book",则S1,S2和S3依次联接后的结果是”good book” 。 (满分:2) A. 错误 B. 正确 6.二叉树是度为2的有序树。 (满分:2) A. 错误 B. 正确 7.队列的队尾位置通常是随着入队操作而变化的。 (满分:2) A. 错误 B. 正确 8.由于希尔排序的最后一趟与直接插入排序过程相同,因此前者一定比后者花费的时间多。 (满分:2) A. 错误 B. 正确 9.串S=”I am a worker″的长度是10。 (满分:2) A. 错误 B. 正确 10.不含任何字符的串称为空串。 (满分:2) A. 错误 B. 正确 11.栈下溢是指在栈空时进行出栈操作 (满分:2) A. 错误 B. 正确 12.在二叉树的第i层上至多可以有2i个结点。 (满分:2) A. 错误 B. 正确 13.二叉树中的叶子结点就是二叉树中没有左右子树的结点。 (满分:2) A. 错误 B. 正确 14.已知完全二叉树T的第5层只有7个结点,则该树共有15个叶子结点。 (满分:2) A. 错误 B. 正确 15.一棵树可以只有1个结点。 (满分:2) A. 错误 B. 正确 16.假设以S和X分别表示进栈和退栈操作,则对输入序列a,b,c,d,e进行一系列栈操作SSXSXSSXXX之后,得到的输出序列为 a b b c c d d e d c 。 (满分:2) A. 错误 B. 正确 17.对一棵有100个结点的完全二叉树按层编号,则编号为49的结点,它的左孩子的编号为98。 (满分:2) A. 错误 B. 正确 18.结点数为20的二叉树可能的最大高度为4。 (满分:2) A. 错误 B. 正确 19.字符串“sgabacbadfgbacst” 中存在有6个与字符串“ba”相同的子串. (满分:2) A. 错误 B. 正确 20.一个具有4个顶点的无向完全图有6条边。 (满分:2) A. 错误 B. 正确 21.在对链队列作出队操作时,不会改变front指针的值。 (满分:2) A. 错误 B. 正确 22.空格串的长度是空格的个数。 (满分:2) A. 错误 B. 正确 答案下载请进下面的地址 |