天津大学17秋《数据结构》在线作业一（答案）

《数据结构》在线作业一
一、单选题:【40道,总分:100分】


1.二维数组A中，每个元素A的长度为3个字节，行下标i从0到7，列下标j从0到9，从首地址SA开始连续存放在存储器内，该数组按列存放时，元素A[4][7]的起始地址为(    )。          (满分:2.5)
    A. SA+141
    B. SA+180
    C. SA+222
    D. SA+225
2.设二叉排序树中有n个结点，则在二叉排序树的平均平均查找长度为(    )。          (满分:2.5)
    A. O(1)
    B. O(log2n)
    C. O(n4)
    D. O(n2 )
3.假定在一棵二叉树中，双分支结点数为15，单分支结点数为30个，则叶子结点数为(    )个。          (满分:2.5)
    A. 15
    B. 16
    C. 17
    D. 47
4.下面关于线性表的叙述错误的是(    )。          (满分:2.5)
    A. 线性表采用顺序存储必须占用一片连续的存储空间
    B. 线性表采用链式存储不必占用一片连续的存储空间
    C. 线性表采用链式存储便于插入和删除操作的实现
    D. 线性表采用顺序存储便于插入和删除操作的实现
5.设有6个结点的无向图，该图至少应有(    )条边才能确保是一个连通图。          (满分:2.5)
    A. 5
    B. 6
    C. 7
    D. 8
6.设某完全无向图中有n个顶点，则该完全无向图中有(    )条边。          (满分:2.5)
    A. n(n-1)/2
    B. n(n-1)
    C. n2
    D. n2 -1
7.下列四种排序中(    )的空间复杂度最大。          (满分:2.5)
    A. 插入排序
    B. 冒泡排序
    C. 堆排序
    D. 归并排序
8.判定一个顺序栈ST（最多元素为m0）为栈满的条件是(    )。          (满分:2.5)
    A. top！=0
    B. top= =0
    C. top！=m0
    D. top= =m0-1
9.设某二叉树中度数为0的结点数为N0，度数为1的结点数为Nl，度数为2的结点数为N2，则下列等式成立的是(    )。          (满分:2.5)
    A. N0=N1+1
    B. N0=Nl+N2
    C. N0=N2+1
    D. N0=2N1+l
10.设一维数组中有n个数组元素，则读取第i个数组元素的平均时间复杂度为(    )。          (满分:2.5)
    A. O(n)
    B. O(nlog2n)
    C. O(1)
    D. O(n2 )
11.设有序顺序表中有n个数据元素，则利用二分查找法查找数据元素X的最多比较次数不 超过(    )。          (满分:2.5)
    A. log2n+1
    B. log2n-1
    C. log2n
    D. log2(n+1)
12.若已知一个栈的入栈序列是1，2，3，…，n，其输出序列为p1，p2，p3，…，pn，若p1=n，则pi为(    )。          (满分:2.5)
    A. i
    B. n=i
    C. n-i+1
    D. 不确定
13.在一非空二叉树的中序遍历序列中，根结点的右边(    )。          (满分:2.5)
    A. 只有右子树上的所有结点
    B. 只有右子树上的部分结点
    C. 只有左子树上的部分结点
    D. 只有左子树上的所有结点
14.判定一个循环队列QU（最多元素为m0）为空的条件是(    )。          (满分:2.5)
    A. rear - front= =m0
    B. rear-front-1= =m0
    C. front= = rear
    D. front= = rear+1
15.设顺序循环队列Q[0：M-1]的头指针和尾指针分别为F和R，头指针F总是指向队头元素的前一位置，尾指针R总是指向队尾元素的当前位置，则该循环队列中的元素个数为(    )。          (满分:2.5)
    A. R-F
    B. F-R
    C.(R-F+M)％M
    D.(F-R+M)％M
16.在以下的叙述中，正确的是(    )。          (满分:2.5)
    A. 线性表的顺序存储结构优于链表存储结构
    B. 线性表的顺序存储结构适用于频繁插入/删除数据元素的情况
    C. 线性表的链表存储结构适用于频繁插入/删除数据元素的情况
    D. 线性表的链表存储结构优于顺序存储结构
17.当从一个小根堆（最小堆）中删除一个元素时，需要把堆尾元素填补到堆顶位置，然后再按条件把它逐层向下调整，直到调整到合适位置为止。          (满分:2.5)
    A. 正确
    B. 错误
18.串是一中特殊的线性表，其特殊性体现在(    )。          (满分:2.5)
    A. 可以顺序存储
    B. 数据元素是一个字符
    C. 可以链接存储
    D. 数据元素可以是多个字符
19.数据结构是一门研究非数值计算的程序设计问题中,数据元素的(    )、数据信息在计算机中的存储结构以及一组相关的运算等的课程。          (满分:2.5)
    A. 操作对象
    B. 计算方法
    C. 逻辑结构
    D. 数据映象
20.设串s1='ABCDEFG'，s2='PQRST'，函数con(x,y)返回x和y串的连接串，subs(s,i,j)返回串s的从序号i的字符开始的j个字符组成的子串，len(s)返回串s的长度，则con(subs(s1,2,len(s2)),subs(s1,len(s2),2))的结果串是(    )。          (满分:2.5)
    A. BCDEF
    B. BCDEFG
    C. BCPQRST
    D. BCDEFEF
21.二叉树的第k层的结点数最多为(    ).          (满分:2.5)
    A. 2k-1
    B. 2K+1
    C. 2K-1
    D. 2k-1
22.按照二叉树的定义，具有3个结点的不同形状的二叉树有(    )种。          (满分:2.5)
    A. 3
    B. 4
    C. 5
    D. 6
23.设指针变量p指向单链表中结点A，若删除单链表中结点A，则需要修改指针的操作序列为(    )。          (满分:2.5)
    A. q=p->next；p->data=q->data；p->next=q->next；free(q)；
    B. q=p->next；q->data=p->data；p->next=q->next；free(q)；
    C. q=p->next；p->next=q->next；free(q)；
    D. q=p->next；p->data=q->data；free(q)
24.具有五层结点的二叉平衡树至少有(    )个结点。          (满分:2.5)
    A. 10
    B. 12
    C. 15
    D. 17
25.从一个具有n个结点的单链表中查找其值等于x结点时，在查找成功的情况下，需平均比较(    )个结点。          (满分:2.5)
    A. n
    B. n/2
    C.(n-1)/2
    D.(n+1)/2
26.以下叙述中正确的是(    )。          (满分:2.5)
    A. 串是一种特殊的线性表
    B. 串的长度必须大于零
    C. 串中无素只能是字母
    D. 空串就是空白串
27.在一棵具有5层的满二叉树中结点数为(    )          (满分:2.5)
    A. 33
    B. 32
    C. 31
    D. 31
28.非空的循环单链表head的尾结点（由p所指向）满足(    )。          (满分:2.5)
    A. p->next= =NULL
    B. p= =NULL
    C. p->next= =head
    D. p= =head
29.设一组初始关键字记录关键字为(20，15，14，18，21，36，40，10)，则以20为基准记录的一趟快速排序结束后的结果为(    )。          (满分:2.5)
    A. 10，15，14，18，20，36，40，21
    B. 10，15，14，18，20，40，36，21
    C. 10，15，14，20，18，40，36，2l
    D. 15，10，14，18，20，36，40，21
30.设某棵二叉树中有2000个结点，则该二叉树的最小高度为(    )。          (满分:2.5)
    A. 9
    B. 10
    C. 11
    D. 12
31.判定一个顺序栈ST（最多元素为m0）为空的条件是(    )。          (满分:2.5)
    A. top!=0
    B. top= =0
    C. top!=m0
    D. top= =m0-1
32.设a,b为一棵二叉树上的两个结点，在中序遍历时，a在b前的条件是(    )。          (满分:2.5)
    A. a在b的右方
    B. a在b的左方
    C. a是b的祖先
    D. a是b的子孙
33.设有两个串p和q，求q在p中首次出现的位置的运算称作(    )。          (满分:2.5)
    A. 连接
    B. 模式匹配
    C. 求子串
    D. 求串长
34.数据结构DS(Data Struct)可以被形式地定义为DS=（D，R），其中D是(    )有限集合，R是D上的关系有限集合。          (满分:2.5)
    A. 算法
    B. 数据元素
    C. 数据操作
    D. 数据对象
35.设一棵二叉树的深度为k，则该二叉树中最多有(    )个结点。          (满分:2.5)
    A. 2k-1
    B. 2k
    C. 2k-1
    D. 2k -1
36.哈希表中的冲突可以通过改变哈希函数完全避免。          (满分:2.5)
    A. 正确
    B. 错误
37.在一个单链表中，若p所指结点不是最后结点，在p之后插入s所指结点，则执行(    )。          (满分:2.5)
    A. s->next=p;p->next=s;
    B. s->next=p->next;p->next=s;
    C. s->next=p->next;p=s;
    D. p->next=s;s->next=p;
38.设某强连通图中有n个顶点，则该强连通图中至少有(    )条边。          (满分:2.5)
    A. n(n-1)
    B. n+1
    C. n
    D. n(n+1)
39.设哈夫曼树中的叶子结点总数为m，若用二叉链表作为存储结构，则该哈夫曼树中总共有(    )个空指针域。          (满分:2.5)
    A. 2m-1
    B. 2m
    C. 2m+1
    D. 4m
40.对一个满二叉树，m个树叶，n个结点，深度为h，则(    )。          (满分:2.5)
    A. n=h+m
    B. h+m=2n
    C. m=h-1
    D. n=2的h次方-1
更多学习资料请登录www.openhelp100.com