《数据结构》2.对于哈希函数H(key)=key%13,被称为同义词的关...

奥鹏网院作业

电科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<m; i++)for(j=0; j<n; j++)A[i][j]=i*j;          (满分:3)
    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. 正确