天津大学19春《计算机软件技术基础(2)》在线作业二（含答案）

易百网

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

奥鹏作业答案
奥鹏天津大学作业

一、单选题：
1.[单选题]假设双向链表结点的类型如下： typedef struct Linknode{  int data;  struct Linknode *lLink;   /*前驱结点指针*/  struct Linknode *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.以上均不对
    正确答案:——C——
2.[单选题]一组记录的排序代码为{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}
    正确答案:——C——
3.[单选题]判断一个顺序栈ST（最多元素为mo）为空的条件是（ ）。
    A.ST-＞top＜＞0
    B.ST-＞top=0
    C.st-＞top＜＞mo
    D.st-＞top==mo
    正确答案:——B——
4.[单选题]若已知一个栈的入栈序列是1,2,3,?,n，其输出序列为P1,P2,P3,?,Pn，若P1=n，则Pi为      （ ）。
    A.i
    B.n-i
    C.n-i+1
    D.不确定
    正确答案:————
5.[单选题]树最适合用来表示(  )。
    A.有序数据元素
    B.无序数据元素
    C.元素之间具有分支层次关系的数据
    D.元素之间无联系的数据
    正确答案:————
6.[单选题]在下述排序算法中，所需辅助存储空间最多的是(  )。
    A.快速排序   
易百教育
    B.归并排序
    C.堆排序
    D.希尔排序
    正确答案:————
7.[单选题]( )不属于多道程序设计的概念。
    A.多个用户同时使用一台计算机的打印设备
    B.多个用户同时进入计算机系统，并要求同时处于运行状态
    C.一个计算机系统从宏观上进行作业的并行处理，但在微观上仍在串行操作
    D.多个作业同时存放在主存并处于运行状态
    正确答案:————
8.[单选题]一组记录的排序代码为{46,79,56,38,40,84}，则利用堆排序的方法建立的初始堆为( )。
    A.{79,46,56,38,40,80}
    B.{84,79,56,38,40,46}
    C.{84,79,56,46,40,38}
    D.{84,56,79,40,46,38}
    正确答案:————
9.[单选题]设有1000个无序的元素，希望用最快的速度挑选出其中前10个最大的元素，最好选用( )排序法。
    A.冒泡排序
    B.快速排序
    C.堆排序
    D.希尔排序
    正确答案:————
10.[单选题]如下图所示的二叉树的中序遍历序列是      (  )。
    A.abcdgef
    B.dfebagc
    C.dbaefcg
    D.defbagc
    正确答案:————
11.[单选题]某二叉树前序遍历结点的访问顺序是ABCDEFG，中序遍历结点的访问顺序是CBDAFGE，则其后序遍历结点的访问顺序是      (  )。
    A.CDBGFEA
    B.CDGFEAB
    C.CDBAGFE
    D.CDBFAGE
    正确答案:————
12.[单选题]常对数组进行的两种基本操作是(  )  。
    A.建立和删除
    B.索引和修改
    C.查找和修改
    D.索引和查找
    正确答案:————
13.[单选题]若S是P、V操作的信号量，当S＜0时，其绝对值表示( )。
    A.排列在信号量等待队列中的进程数
    B.可供使用的临界资源数
    C.无资源可用
    D.无进程排队等待
    正确答案:————
14.[单选题]设有如下的单链表的按序号查找的算法，其时间复杂度为（ ）。 LinkNode *GetNode(Linklist head, int i){  int j;   ListNode *p;  P = head; j=0;   while(p-＞next && j＜i){   p = p-＞next;  j++; }  if(i==j)return(p);  else    return(NULL);  }
    A.O(n2)
    B.O(2n)
    C.O(n3 )
    D.O(logn
    正确答案:————
15.[单选题]设串s1=”ABCDEFG”，s2=”PQRST”，函数con(x,y)返回x和y串的连接串，subs(s,I,j)返回串s的从序号i的字符开始的j个字符组成的子串，len(s)返回串s的长度，则con(sub(s1,2,len(s2)),sub(s1,len(s2),2))的结果是(  )。
    A.BCDEF
    B.BCDEFG
    C.BCPQRST
    D.BCDEFEF
    正确答案:————
16.[单选题]对一个满二叉树，m个树叶,n个结点，深度为h，则(  )。
    A.n=h+m
    B.h+m=2n
    C.m=h-1
    D.n=2h -1
    正确答案:————
17.[单选题]从一个长度为n的顺序表中删除第i个元素时，需向前移动（ ）个元素。
    A.n-i
    B.n-i+1
    C.n-i-1
    D.i
    正确答案:————
18.[单选题]二维数组Amn按行序为主顺序存放在内存中，每个数组元素占1个存储单元，则元素aij的地址计算公式是（ ）。
    A.LOC(aij) = LOC(a11)+[(i-1)*m+(j-1)]
    B.LOC(aij) = LOC(a11)+[(j-1)*m+(i-1)]
    C.LOC(aij) = LOC(a11)+[(i-1)*n+(j-1)]
    D.LOC(aij) = LOC(a11)+[(j-1)*n+(i-1)]
    正确答案:————
19.[单选题]若在线性表中采用折半查找法查找元素，该线性表应该 (  )
    A.元素按值有序
    B.采用顺序存储结构
    C.元素按值有序，且采用顺序存储结构
    D.元素按值有序，且采用链式存储结构
    正确答案:————
20.[单选题]以下哪一个不是队列的基本运算（ ） 。
    A.从队尾插入一个新元素
    B.从队列中删除第i个元素
    C.判断一个队列是否为空
    D.读取队头元素的值
    正确答案:————
21.[单选题]一棵有124个叶结点的完全二叉树，最多有      (  )个结点.
    A.247
    B.248
    C.249
    D.251
    正确答案:————
22.[单选题]栈结构通常采用的两种存储结构是（ ）   。
    A.顺序存储结构和链表存储结构
    B.散列方式和索引方式
    C.链表存储结构和数组
    D.线性存储结构和非线性存储结构
    正确答案:————
23.[单选题]（ ）是信息的载体，它能够被计算机识别、存储和加工处理。
    A.数据
    B.数据元素
    C.结点
    D.数据项
    正确答案:————
24.[单选题]数据结构是一门研究非数值计算的程序设计问题中，计算机的（ ）以及它们之间的关系和运算等的学科。
    A.操作对象
    B.计算方法
    C.逻辑存储
    D.数据映象
    正确答案:————
25.[单选题]在一个单链表中，已知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;
    正确答案:————
26.[单选题]设待排序的记录为(20,16,13,14,19)，经过下列过程将这些记录排序。  20,16,13,14,19 16,20,13,14,19 13,16,20,14,19 13,14,16,20,19 13,14,16,19,20  所用的排序方法是      （）。
    A.直接插入排序
    B.冒泡排序
    C.希尔排序
    D.堆排序
    正确答案:————
27.[单选题]下面程序段的时间复杂度为（ ）。 a=0;b=1;  for(i=2;i＜=n;i++){  s=a+b;  b=a;  a=s; }
    A.O(1)
    B.O(n)
    C.O(log2n)
    D.O(n2 )
    正确答案:————
28.[单选题]操作系统中，当(  )时，进程从执行状态转变为就绪状态。
    A.进程被进程调度程序选中
    B.时间片到
    C.等待某一事件
    D.等待的事件发生
    正确答案:————
29.[单选题]( )不是引入进程的直接目的。
    A.多道程序同时在主存中运行
    B.程序需从头至尾执行
    C.主存中各程序之间存在着相互依赖，相互制约的关系
    D.程序的状态不断地发生变化
    正确答案:————
30.[单选题]信号量S的初始值为8，在S上调用10次P操作和6次V操作后，S的值为( )。
    A.10
    B.8
    C.6
    D.4
    正确答案:————
31.[单选题]算法分析的目的是（ ）。
    A.找出数据结构的合理性
    B.研究算法中输入和输出的关系
    C.分析算法的效率以求改进
    D.分析算法的易懂性和文档性
    正确答案:————
32.[单选题]若从二叉树的任一结点出发到根的路径上所经过的结点序列按其关键字有序，则该二叉 树是(  )
    A.满二叉树
    B.哈夫曼树
    C.堆
    D.二叉查找树
    正确答案:————
33.[单选题]从一个具有n个结点的单链表中查找其值等于x的结点时，在查找成功的情况下，需平均比较（ ）个结点。
    A.n
    B.n/2
    C.(n-1)/2
    D.(n+1)/2
    正确答案:————
34.[单选题]在一棵二叉树上，度为0的结点个数为n0，度为2的结点数为n2，则n0=(  )。
    A.n2+1
    B.n2-1
    C.n2
    D.n2/2
    正确答案:————
35.[单选题]直接插入排序在最好情况下的时间复杂度为      （ ）。
    A.O(logn)
    B.O(n)
    C.O(nlogn)
    D.O(n2 )
    正确答案:————
36.[单选题]前序遍历和中序遍历结果相同的二叉树为      (  )
    A.一般二叉树
    B.只有根结点的二叉树
    C.根结点无左孩子的二叉树
    D.所有结点只有右孩子的二叉树
    正确答案:————
37.[单选题]下列不属于临界资源的是( )。
    A.CPU
    B.公共变量
    C.公用数据
    D.输入输出设备
    正确答案:————
38.[单选题]每次把待排序的区间划分为左、右两个子区间，其中左区间中元素的排序码均小于等于基准元素的排序码，右区间中元素的排序码均大于等于基准元素的排序码，此种排序方法叫做(  )。
    A.堆排序
    B.快速排序
    C.冒泡排序
    D.希尔排序
    正确答案:————
39.[单选题]快速排序在最坏情况下时间复杂度是O(n2 )，比（  ）的性能差。
    A.堆排序
    B.冒泡排序
    C.简单选择排序
    正确答案:————
40.[单选题]算法分析的两个主要方面是（ ） 。
    A.间复杂性和时间复杂性
    B.正确性和简明性
    C.可读性和文档性
    D.数据复杂性和程序复杂性
    正确答案:————
奥鹏作业答案