18秋天大《计算机软件技术基础(2)》在线作业二1(100分）

admin

【奥鹏】[天津大学]《计算机软件技术基础(2)》在线作业二
试卷总分:100    得分:100
第1题,栈结构通常采用的两种存储结构是（ ）   。
A、顺序存储结构和链表存储结构
B、散列方式和索引方式
C、链表存储结构和数组
D、线性存储结构和非线性存储结构



第2题,( )不属于多道程序设计的概念。
A、多个用户同时使用一台计算机的打印设备
B、多个用户同时进入计算机系统，并要求同时处于运行状态
C、一个计算机系统从宏观上进行作业的并行处理，但在微观上仍在串行操作
D、多个作业同时存放在主存并处于运行状态



第3题,判断一个顺序栈ST（最多元素为mo）为空的条件是（ ）。
A、ST-top0
B、ST-top=0
C、st-topmo
D、st-top==mo



第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(Linklist head, int i){  int j;   ListNode *p;  P = head; j=0;   while(p-next && ji){   p = p-next;  j++; }  if(i==j)return(p);  else    return(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题,假设双向链表结点的类型如下： 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、以上均不对



第36题,树的基本遍历策略可分为先根遍历和后根遍历；二叉树的基本遍历策略可分为先序遍历、中序遍历和后序遍历。这里，我们把由树转化得到的二叉树叫做这棵树对应的二叉树。下面结论正确的是( )。
A、树的先根遍历序列与其对应的二叉树的先序遍历序列相同
B、树的先根遍历序列与其对应的二叉树的后序遍历序列相同
C、树的先根遍历序列与其对应的二叉树的中序遍历序列相同
D、以上均不对



第37题,设待排序的记录为(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、堆排序



第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、散列和十字链表