天津大学18秋《计算机软件技术基础(2)》在线作业二题目

《计算机软件技术基础(2)》在线作业二

天大作业答案


一、单选题：
1. 栈结构通常采用的两种存储结构是（）。
    A. 顺序存储结构和链表存储结构
    B. 散列方式和索引方式
    C. 链表存储结构和数组
    D. 线性存储结构和非线性存储结构
    正确答案:——A——
2. ()不属于多道程序设计的概念。
    A. 多个用户同时使用一台计算机的打印设备
    B. 多个用户同时进入计算机系统，并要求同时处于运行状态
    C. 一个计算机系统从宏观上进行作业的并行处理，但在微观上仍在串行操作
    D. 多个作业同时存放在主存并处于运行状态
    正确答案:——A——
3. 判断一个顺序栈ST（最多元素为mo）为空的条件是（）。
    A. ST->top<>0
    B. ST->top=0
    C. st->top<>mo
    D. st->top==mo
    正确答案:——B——
4. 设高度为h的二叉树上只有度为0或度为2的结点，则此类二叉树中所包含的结点数至少为()。
    A. 2h
    B. 2h-1
    C. 2h+1
    D. h+1
    正确答案:————
5. 设有两个串p和q，求q在p中首次出现的位置的运算称作()。
    A. 连接
    B. 模式匹配
    C. 求子串
    D. 求串长
    正确答案:————
6. 如果某二叉树的前序为stuwv，中序为uwtvs，则该二叉树后序为(）。
    A. uwvts
    B. vwuts
    C. wuvts
    D. wutsv
    正确答案:————
7. 每次把待排序的区间划分为左、右两个子区间，其中左区间中元素的排序码均小于等于基准元素的排序码，右区间中元素的排序码均大于等于基准元素的排序码，此种排序方法叫做()。
    A. 堆排序
    B. 快速排序    奥鹏答案

    C. 冒泡排序
    D. 希尔排序
    正确答案:————
8. 对于一个栈，给出输入项A,B,C。如果输入项序列由A,B,C所组成，则不可能产生的输出序列是（）。
    A. CAB
    B. CBA
    C. ABC
    D. ACB
    正确答案:————
9. 在文件局部有序或文件长度较小的情况下，最佳内部排序的方法是（）。
    A. 直接插入排序
    B. 冒泡排序
    C. 简单选择排序
    正确答案:————
10. 分时系统追求的目标是()。
    A. 高吞吐率
    B. 充分利用内存
    C. 快速响应
    D. 减少系统开销
    正确答案:————
11. 在所有排序方法中，关键码（即关键字）比较的次数与记录的初始排列次序无关的是（）。
    A. 希尔排序
    B. 冒泡排序
    C. 直接插入排序
    D. 直接选择排序
    正确答案:————
12. 已知一棵权集W={2,3,4,7,8,9}的哈夫曼树，其加权路径长度WPL为()。
    A. 20
    B. 40
    C. 80
    D. 160
    正确答案:————
13. 在一个长度为n的顺序表中，向第i个元素之前插入一个新元素，需向后移动（）个元素。
    A. n-i
    B. n-i+1
    C. n-i-1
    D. i
    正确答案:————
14. 下面关于临界区的说法中，错误的是()。
    A. 进程中，访问临界资源的程序是临界区
    B. 同时进行临界区的进程必须互斥
    C. 进入临界区内的两个进程访问临界资源时必须互斥
    D. 在同一时刻，只允许一个进程进入临界区
    正确答案:————
15. 如果T2是由有序树T转换而来的二叉树，则T中结点的前序就是T2中结点的()。
    A. 前序
    B. 中序
    C. 后序
    D. 层次序
    正确答案:————
16. 算法分析的目的是（）。
    A. 找出数据结构的合理性
    B. 研究算法中输入和输出的关系
    C. 分析算法的效率以求改进
    D. 分析算法的易懂性和文档性
    正确答案:————
17. 某二叉树前序遍历结点的访问顺序是ABCDEFG，中序遍历结点的访问顺序是CBDAFGE，则其后序遍历结点的访问顺序是()。
    A. CDBGFEA
    B. CDGFEAB
    C. CDBAGFE
    D. CDBFAGE
    正确答案:————
18. 在一棵二叉树上，度为0的结点个数为n0，度为2的结点数为n2，则n0=()。
    A. n2+1
    B. n2-1
    C. n2
    D. n2/2
    正确答案:————
19. 直接插入排序在最好情况下的时间复杂度为（）。
    A. O(logn)
    B. O(n)
    C. O(nlogn)
    D. O(n2)
    正确答案:————
20. 在单处理机系统中，若同时存在有10个进程，则处于就绪队列中的进程最多为()个。
    A. 0
    B. 6
    C. 9
    D. 10
    正确答案:————
21. 下面关于进程控制块的说法中，错误的是（）。
    A. 进程控制块对每个进程仅有一个
    B. 进程控制块记录进程的状态及名称等
    C. 进程控制块位于主存储区内
    D. 进程控制块的内容、格式及大小均相同
    正确答案:————
22. 数据结构是一门研究非数值计算的程序设计问题中，计算机的（）以及它们之间的关系和运算等的学科。
    A. 操作对象
    B. 计算方法
    C. 逻辑存储
    D. 数据映象
    正确答案:————
23. 若已知一个栈的入栈序列是1,2,3,?,n，其输出序列为P1,P2,P3,?,Pn，若P1=n，则Pi为（）。
    A. i
    B. n-i
    C. n-i+1
    D. 不确定
    正确答案:————
24. 一个线性顺序表第一个元素的存储地址是100，每个元素的长度为2，则第5个元素的地址为（）。
    A. 110
    B. 108
    C. 100
    D. 120
    正确答案:————
25. 已知一棵度为m的树中有n1个度为1的结点，n2个度为2的结点，?，nm个度为m的结点，问这棵树中叶子结点为()。
    A. 1+ni(I-1)
    B. 1+ni(I+1)
    C. n1+n2+?+nm
    D. m·nm
    正确答案:————
26. 在数据结构中，从逻辑上可以把数据结构分成（）。
    A. 动态结构和静态结构
    B. 紧凑结构和非紧凑结构
    C. 线性结构和非线性结构
    D. 内部结构和外部结构
    正确答案:————
27. 一组记录的排序代码为{46,79,56,38,40,84}，则利用快速排序的方法，以第一个记录为基准得到的一次划分结果为()。
    A. {38,40,46,56,79,84
    B. {40,38,46,79,56,84
    C. {40,38,46,56,79,84
    D. {40,38,46,84,56,79
    正确答案:————
28. 设有如下的单链表的按序号查找的算法，其时间复杂度为（）。LinkNode*GetNode(Linklisthead,inti){intj;ListNode*p;P=head;j=0;while(p->next&&j<i){p=p->next;j++;}if(i==j)return(p);elsereturn(NULL);}
    A. O(n2)
    B. O(2n)
    C. O(n3)
    D. O(logn
    正确答案:————
29. 若需在O(nlogn)的时间内完成对数组的排序，且要求排序是稳定的，则可选择的排序方法是（）。
    A. 快速排序
    B. 堆排序
    C. 归并排序
    D. 希尔排序
    正确答案:————
30. 快速排序方法在()情况下最不利于发挥其长处。
    A. 要排序的数据量太大
    B. 要排序的数据中含有多个相同值
    C. 要排序的数据已基本有序
    D. 要排序的数据个数为整数
    正确答案:————
31. 对下图所示的二叉表，按先根次序遍历得到的结点序列为()。
    A. ABCDHEIFG
    B. ABDHIECFG
    C. HDIBRAFCG
    D. HIDBEFGAC
    正确答案:————
32. 工业过程控制系统中，运行的操作系统最好是()。
    A. 分时系统
    B. 实时系统
    C. 分布式操作系统
    D. 网络操作系统
    正确答案:————
33. 若在线性表中采用折半查找法查找元素，该线性表应该()
    A. 元素按值有序
    B. 采用顺序存储结构
    C. 元素按值有序，且采用顺序存储结构
    D. 元素按值有序，且采用链式存储结构
    正确答案:————
34. 在一个单链表中，已知q所指结点是p所指结点的前驱结点，若在p和q之间插入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;
    正确答案:————
35. 假设双向链表结点的类型如下：typedefstructLinknode{intdata;structLinknode*lLink;/*前驱结点指针*/structLinknode*rLink;/*后继结点指针*/}下面给出的算法是要把一个q所指新结点，作为非空双向链表中的p所指的结点前驱结点插入到该双向链表中，能正确完成要求的算法段是（）。
    A. q->rLink=p;q->lLink=p->lLink;p->lLink=q;p->lLink->rLink=q;
    B. p->lLink=q,q->rLink=p;p->lLink->rLink=q;q->lLink=p->lLink;
    C. q->lLink=p->lLink;q->rLink=p;p->lLink->rLink=q;p->lLink=q;
    D. 以上均不对
    正确答案:————
36. 树的基本遍历策略可分为先根遍历和后根遍历；二叉树的基本遍历策略可分为先序遍历、中序遍历和后序遍历。这里，我们把由树转化得到的二叉树叫做这棵树对应的二叉树。下面结论正确的是()。
    A. 树的先根遍历序列与其对应的二叉树的先序遍历序列相同
    B. 树的先根遍历序列与其对应的二叉树的后序遍历序列相同
    C. 树的先根遍历序列与其对应的二叉树的中序遍历序列相同
    D. 以上均不对
    正确答案:————
37. 设待排序的记录为(20,16,13,14,19)，经过下列过程将这些记录排序。20,16,13,14,1916,20,13,14,1913,16,20,14,1913,14,16,20,1913,14,16,19,20所用的排序方法是（）。
    A. 直接插入排序
    B. 冒泡排序
    C. 希尔排序
    D. 堆排序
    正确答案:————
38. 不带头结点的单链表head为空表的判定条件是（）。
    A. head==NILL
    B. head->next==NULL
    C. head->next==head
    D. head!=NULL
    正确答案:————
39. 如果要求一个线性表既能较快地查找，又能适应动态变化的要求，则可采用的方法是()。
    A. 分块法
    B. 顺序法
    C. 二分法
    D. 哈希法
    正确答案:————
40. 稀疏矩阵一般的压缩存储方法有两种，即()。
    A. 二维数组和三维数组
    B. 三元组和散列
    C. 三元组和十字链表
    D. 散列和十字链表
    正确答案:————
奥鹏作业答案