天津大学18秋《数据结构》在线作业一题目

《数据结构》在线作业一

天大作业答案咨询QQ515224986

一、单选题：
1. 数据结构是一门研究非数值计算的程序设计问题中,数据元素的（）、数据信息在计算机中的存储结构以及一组相关的运算等的课程。
    A. 操作对象
    B. 计算方法
    C. 逻辑结构
    D. 数据映象
    正确答案:——C——
2. 设一维数组中有n个数组元素，则读取第i个数组元素的平均时间复杂度为（）。
    A. O(n)
    B. O(nlog2n)
    C. O(1)
    D. O(n2)
    正确答案:——C——
3. 设一组初始记录关键字序列为(345，253，674，924，627)，则用基数排序需要进行（）趟的分配和回收才能使得初始关键字序列变成有序序列。
    A. 3
    B. 4
    C. 5
    D. 8
    正确答案:——A——
4. 如果只想得到1024个元素组成的序列中第5个最小元素之前的部分排序的序列，用（）方法最快。
    A. 起泡排序
    B. 快速排序
    C. 简单选择排序
    D. 堆排序
    正确答案:————
5. 下面程序的时间复杂为（）for（i=1，s=0；i<=n；i++）{t=1；for(j=1；j<=i；j++)t=t*j；s=s+t；}
    A. O(n)
    B. O(n2)
    C. O(n3)
    D. O(n4)
    正确答案:————
6. 在一个单链表中，若p所指结点不是最后结点，在p之后插入s所指结点，则执行（）。
    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;
    正确答案:————
7. 已知某二叉树的后序遍历序列是dabec，中序遍历序列是debac，它的前序遍历序列是（）。
    A. acbed
    B. decab
    C. deabc
    D. cedba
    正确答案:————
8. 二维数组A中，每个元素的长度为3个字节，行下标i从0到7，列下标j从0到9，从首地址SA开始连续存放在存储器内，存放该数组至少需要的字节数是（）。
    A. 80
    B. 100
    C. 240    天大作业答案

    D. 270
    正确答案:————
9. 若已知一个栈的入栈序列是1，2，3，…，n，其输出序列为p1，p2，p3，…，pn，若p1=n，则pi为（）。
    A. i
    B. n=i
    C. n-i+1
    D. 不确定
    正确答案:————
10. 判定一个顺序栈ST（最多元素为m0）为栈满的条件是（）。
    A. top！=0
    B. top==0
    C. top！=m0
    D. top==m0-1
    正确答案:————
11. 在二叉排序树中插入一个结点的时间复杂度为（）。
    A. O(1)
    B. O(n)
    C. O(log2n)
    D. O(n2)
    正确答案:————
12. 设串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))的结果串是（）。
    A. BCDEF
    B. BCDEFG
    C. BCPQRST
    D. BCDEFEF
    正确答案:————
13. 在用循环单链表表示的链式队列中，可以不设队头指针，仅在链尾设置队尾指针。
    A. 正确
    B. 错误
    正确答案:————
14. 非空的循环单链表head的尾结点（由p所指向）满足（）。
    A. p->next==NULL
    B. p==NULL
    C. p->next==head
    D. p==head
    正确答案:————
15. 某二叉树的前序遍历结点访问顺序是abdgcefh，中序遍历的结点访问顺序是dgbaechf，则其后序遍历的结点访问顺序是（）。
    A. bdgcefha
    B. gdbecfha
    C. bdgaechf
    D. gdbehfca
    正确答案:————
16. 带头结点的单链表head为空的判定条件是（）。
    A. head==NULL
    B. head->next==NULL
    C. head->next==head
    D. head!=NULL
    正确答案:————
17. 进行折半搜索的表必须是顺序存储的有序表。
    A. 正确
    B. 错误
    正确答案:————
18. 设串的长度为n，则它的子串个数为（）。
    A. n
    B. n(n+1)
    C. n(n+1)/2
    D. n(n+1)/2+1
    正确答案:————
19. 常对数组进行的两种基本操作是（）。
    A. 建立与删除
    B. 索引和修改
    C. 对数据元素的存取和修改
    D. 查找与索引
    正确答案:————
20. 设某无向图中有n个顶点e条边，则该无向图中所有顶点的入度之和为（）。
    A. n
    B. e
    C. 2n
    D. 2e
    正确答案:————
21. 向一个栈顶指针为HS的链栈中插入一个s所指结点时，则执行（）。(不带空的头结点)
    A. HS—＞next=s;
    B. s—＞next=HS—＞next;HS—＞next=s;
    C. s—＞next=HS;HS=s;
    D. s—＞next=HS;HS=HS—＞next;
    正确答案:————
22. 深度为5的二叉树至多有（）个结点。
    A. 16
    B. 32
    C. 31
    D. 10
    正确答案:————
23. 设有6个结点的无向图，该图至少应有()条边才能确保是一个连通图。
    A. 5
    B. 6
    C. 7
    D. 8
    正确答案:————
24. 设顺序循环队列Q[0：M-1]的头指针和尾指针分别为F和R，头指针F总是指向队头元素的前一位置，尾指针R总是指向队尾元素的当前位置，则该循环队列中的元素个数为（）。
    A. R-F
    B. F-R
    C. (R-F+M)％M
    D. (F-R+M)％M
    正确答案:————
25. 在一个单链表中，已知q所指结点是p所指结点的前驱结点，若在q和p之间插入s结点，则执行（）。
    A. s->next=p->next;p->next=s;
    B. p->next=s->next;s->next=p;
    C. q->next=s;s->next=p;
    D. p->next=s;s->next=q;
    正确答案:————
26. 设无向图G中有n个顶点，则该无向图的最小生成树上有（）条边。
    A. n
    B. n-1
    C. 2n
    D. 2n-1
    正确答案:————
27. 链式存储在插入和删除时需要保持物理存储空间的顺序分配，不需要保持数据元素之间的逻辑顺序。
    A. 正确
    B. 错误
    正确答案:————
28. 对于线性表（7，34，55，25，64，46，20，10）进行散列存储时，若选用H（K）=K%9作为散列函数，则散列地址为1的元素有（）个.
    A. 1
    B. 2
    C. 3
    D. 4
    正确答案:————
29. 设某棵二叉树中有2000个结点，则该二叉树的最小高度为（）。
    A. 9
    B. 10
    C. 11
    D. 12
    正确答案:————
30. 设某完全无向图中有n个顶点，则该完全无向图中有（）条边。
    A. n(n-1)/2
    B. n(n-1)
    C. n2
    D. n2-1
    正确答案:————
31. 在以下的叙述中，正确的是（）。
    A. 线性表的顺序存储结构优于链表存储结构
    B. 线性表的顺序存储结构适用于频繁插入/删除数据元素的情况
    C. 线性表的链表存储结构适用于频繁插入/删除数据元素的情况
    D. 线性表的链表存储结构优于顺序存储结构
    正确答案:————
32. 在线索化二叉树中，t所指结点没有左子树的充要条件是（）。
    A. t—＞left=NULL
    B. t—＞ltag=1
    C. t—＞ltag=1且t—＞left=NULL
    D. 以上都不对
    正确答案:————
33. 二维数组A中，每个元素A的长度为3个字节，行下标i从0到7，列下标j从0到9，从首地址SA开始连续存放在存储器内，该数组按行存放时，数组元素A[7][4]的起始地址为（）。
    A. SA+141
    B. SA+144
    C. SA+222
    D. SA+225
    正确答案:————
34. 从一个栈顶指针为HS的链栈中删除一个结点时，用x保存被删结点的值，则执行（）。(不带空的头结点)
    A. x=HS;HS=HS＞next;
    B. x=HS＞data;
    C. HS=HS＞next;x=HS＞data;
    D. x=HS＞data;HS=HS＞next;
    正确答案:————
35. 设二叉排序树中有n个结点，则在二叉排序树的平均平均查找长度为（）。
    A. O(1)
    B. O(log2n)
    C. O(n4)
    D. O(n2)
    正确答案:————
36. 按照二叉树的定义，具有3个结点的不同形状的二叉树有（）种。
    A. 3
    B. 4
    C. 5
    D. 6
    正确答案:————
37. 具有五层结点的二叉平衡树至少有（）个结点。
    A. 10
    B. 12
    C. 15
    D. 17
    正确答案:————
38. 串是一中特殊的线性表，其特殊性体现在（）。
    A. 可以顺序存储
    B. 数据元素是一个字符
    C. 可以链接存储
    D. 数据元素可以是多个字符
    正确答案:————
39. 下面关于线性表的叙述错误的是（）。
    A. 线性表采用顺序存储必须占用一片连续的存储空间
    B. 线性表采用链式存储不必占用一片连续的存储空间
    C. 线性表采用链式存储便于插入和删除操作的实现
    D. 线性表采用顺序存储便于插入和删除操作的实现
    正确答案:————
40. 数据结构DS(DataStruct)可以被形式地定义为DS=（D，R），其中D是（）有限集合，R是D上的关系有限集合。
    A. 算法
    B. 数据元素
    C. 数据操作
    D. 数据对象
    正确答案:————
奥鹏作业答案