【在线】电子科大17春《数据结构》在线作业2

《【在线】电子科大17春《数据结构》在线作业2》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、谋学网www.mouxue.com一、单选题（共16道试题，共48分。）V1.在一个具有n个顶点的有向图中，所有顶点的出度之和为Dout，则所有顶点的入度之和为（）。A.DoutB.Dout-1C.Dout+1D.n2.对于哈希函数H(key)=key%13,被称为同义词的关键字是（）。A.35和41B.23和39C.15和44D.25和513.在具有n个结点的有序单链表中插入一个新结点并使链表仍然有序的时间复杂度是（）。A.O(1)B.O(n)C.O(n㏒n)D.O(n2)4.在线性表的下列运算中，不改变数据元素之间结构关系的运算是（）。A.插入

2、B.删除C.排序D.定位5.已知函数Sub(s,i,j)的功能是返回串s中从第i个字符起长度为j的子串，函数Scopy(s,t)的功能为复制串t到s。若字符串S=″SCIENCESTUDY″，则调用函数Scopy(P,Sub(S,1,7))后得到（）。A.P=″SCIENCE″B.P=″STUDY″C.S=″SCIENCE″D.S=″STUDY″6.二叉树中第5层上的结点个数最多为（）。A.8B.15C.16D.327.若算法中语句的最大频度为T(n)=2006n+6n㏒n+29㏒2n,则其时间复杂度为（）。A.O(㏒n)B.O(n)C.O(n㏒n

3、)谋学网www.mouxue.comD.O(㏒2n)8.采用两类不同存储结构的字符串可分别简称为（）。A.主串和子串B.顺序串和链串C.目标串和模式串D.变量串和常量串9.若一棵二叉树有11个叶子结点，则该二叉树中度为2的结点个数是（）。A.10B.11C.12D.不确定的10.在目标串T［0..n-1］=″xwxxyxy″中，对模式串P［0..m-1］=″xy″进行子串定位操作的结果是（）。A.0B.2C.3D.511.若线性表的插入和删除操作频繁地在表头或表尾位置进行，则更适宜采用的存储结构为（）。A.无头结点的双向链表B.带尾指针的循环链表C

4、.无头结点的单链表D.带头指针的循环链表12.下面程序段的时间复杂度为（）。for(i=0;i

5、.子串定位16.若进栈序列为1，2，3，4，5，6，且进栈和出栈可以穿插进行，则可能出现的出栈序列为（）。A.3，2，6，1，4，5B.3，4，2，1，6，5C.1，2，5，3，4，6D.5，6，4，2，3，1二、多选题（共2道试题，共8分。）V1.由于排序过程中涉及的存储器不同，可以将排序方法分为（）。A.稳定排序B.不稳定排序C.内部排序D.外部排序D2.假设按照12345的进栈顺序，下面哪些是可能的出栈顺序（）。A.12345B.54321C.43215D.14325BCD三、判断题（共22道试题，共44分。）V1.在对链队列作出队操作时，不

6、会改变front指针的值。A.错误B.正确2.如果入栈序列是1，3，5，…，97，99，且出栈序列的第一个元素为99，则出栈序列中第30个元素为47。A.错误B.正确谋学网www.mouxue.com3.有向图用邻接矩阵表示后，顶点i的入度等于邻接矩阵中第i列的元素个数。A.错误B.正确4.假设为循环队列分配的向量空间为Q[20]，若队列的长度和队头指针值分别为13和17，则当前尾指针的值为15。A.错误B.正确5.假设三维数组A[10][9][8]按行优先顺序存储，若每个元素占3个存储单元，且首地址为100，则元素A[9][8][7]的存储地址是

7、501。A.错误B.正确6.空格串的长度是空格的个数。A.错误B.正确7.二叉树中必有度为2的结点。A.错误B.正确8.一棵含999个结点的完全二叉树的深度为12。A.错误B.正确9.在队列中，允许进行插入操作的一端称为队头。A.错误B.正确10.在一个长度为n的单链表L中，删除链表中*p的前驱结点的时间复杂度为O(n)。A.错误B.正确11.产生冲突现象的两个关键字称为该散列函数的同义字。A.错误B.正确12.深度为15的满二叉树上，第11层有2^11个结点。A.错误B.正确谋学网www.mouxue.com13.一棵树可以只有1个结点。A.错误

8、B.正确14.队列的修改是按先进先出的原则进行的。A.错误B.正确15.删除二叉排序树中一个结点，再重新插入上去，一定能得