天津大学17秋《计算机软件技术基础(2)》在线作业二（答案）
《计算机软件技术基础(2)》在线作业二一、单选题:【40道,总分:100分】天津大学
1.哈希表的地址区间为0-17，哈希函数为H(k)=k mod 17。采用线性探测法处理冲突，并将关键字序列{26,25,72,38,8,18,59}依次存储到哈希表中。如果要访问元素59，则需要的搜索次数是( )。 (满分:2.5)
A. 2
B. 3
C. 4
D. 5
2.树最适合用来表示( )。 (满分:2.5)
A. 有序数据元素
B. 无序数据元素
C. 元素之间具有分支层次关系的数据
D. 元素之间无联系的数据
3.在一个长度为n的顺序表中，向第i个元素之前插入一个新元素，需向后移动( )个元素。 (满分:2.5)
A. n-i
B. n-i+1
C. n-i-1
D. i
4.对一个满二叉树，m个树叶,n个结点，深度为h，则( )。 (满分:2.5)
A. n=h+m
B. h+m=2n
C. m=h-1
D. n=2h -1
5.( )不是引入进程的直接目的。 (满分:2.5)
A. 多道程序同时在主存中运行
B. 程序需从头至尾执行
C. 主存中各程序之间存在着相互依赖，相互制约的关系
D. 程序的状态不断地发生变化
6.已知一棵权集W={2,3,4,7,8,9}的哈夫曼树，其加权路径长度WPL为( )。 (满分:2.5)
A. 20
B. 40
C. 80
D. 160
7.一组记录的排序码为{25,48,16,35,79,82,23,40,36,72}，其中，含有5个长度为2的有序表，按归并排序方法对该序列进行一趟归并后的结果为( )。 (满分:2.5)
A. 16,25,35,48,23,40,79,82,36,72
B. 16.25,35,48,79,82,23,36,40,72
C. 16,25,48,35,79,82,23,36,40,72
D. 16,25,35,48,79,23,36,40,72,82
8.每次把待排序的区间划分为左、右两个子区间，其中左区间中元素的排序码均小于等于基准元素的排序码，右区间中元素的排序码均大于等于基准元素的排序码，此种排序方法叫做( )。 (满分:2.5)
A. 堆排序
B. 快速排序
C. 冒泡排序
D. 希尔排序
9.( )不属于多道程序设计的概念。 (满分:2.5)
A. 多个用户同时使用一台计算机的打印设备
B. 多个用户同时进入计算机系统，并要求同时处于运行状态
C. 一个计算机系统从宏观上进行作业的并行处理，但在微观上仍在串行操作
D. 多个作业同时存放在主存并处于运行状态
10.下面关于进程创建原语的说法中，错误的是 ( )。 (满分:2.5)
A. 创建原语的作用是自行建立一个进程
B. 创建原语的工作是为被创建进程形成一个进程控制块
C. 创建原语不能自己单独执行
D. 创建原语都是由进程调用执行
11.在具有n个单元的顺序存储的循环队列中，假定front和rear分别为队首指针和队尾指针，则判断队空的条件是( )。 (满分:2.5)
A. front=rear+1
B. front=rear
C. front+1=rear
D. front=0
12.前序遍历和中序遍历结果相同的二叉树为 ( ) (满分:2.5)
A. 一般二叉树
B. 只有根结点的二叉树
C. 根结点无左孩子的二叉树
D. 所有结点只有右孩子的二叉树
13.如果只想得到1000个元素组成的序列中第5个最小元素之前的部分排序的序列，用( )方法最快。 (满分:2.5)
A. 冒泡排序
B. 快速排序
C. 希尔排序
D. 堆排序
14.一个线性顺序表第一个元素的存储地址是100，每个元素的长度为2，则第5个元素的地址为( )。 (满分:2.5)
A. 110
B. 108
C. 100
D. 120
15.常对数组进行的两种基本操作是( )。 (满分:2.5)
A. 建立和删除
B. 索引和修改
C. 查找和修改
D. 索引和查找
16.对处理事件有严格时间限制的系统是( )。 (满分:2.5)
A. 分时系统
B. 实时系统
C. 分布式操作系统
D. 网络操作系统
17.直接插入排序在最好情况下的时间复杂度为 ( )。 (满分:2.5)
A. O(logn)
B. O(n)
C. O(nlogn)
D. O(n2 )
18.已知某二叉树的后序遍历序列是dabec，中序遍历序列是debac，则其前序遍历序列为( )。 (满分:2.5)
A. acbed
B. decab
C. deabc
D. cedba
19.如下图所示的二叉树的中序遍历序列是 ( )。 (满分:2.5)
A. abcdgef
B. dfebagc
C. dbaefcg
D. defbagc
20.若要尽可能快地完成对实数数组的排序，且要求排序是稳定的，则应选( )。 (满分:2.5)
A. 快速排序
B. 堆排序
C. 归并排序
D. 希尔排序
21.下面程序段的时间复杂度为( )。 i=1;while(i<=n) i=i*2; (满分:2.5)
A. O(1)
B. O(n)
C. O(n2)
D. O(log2n)
22.算法分析的两个主要方面是( ) 。 (满分:2.5)
A. 间复杂性和时间复杂性
B. 正确性和简明性
C. 可读性和文档性
D. 数据复杂性和程序复杂性
23.以下结点序列是堆的为( )。 (满分:2.5)
A. 100,90,80,60,85,75,20,25,10,70,65,50
B. 100,70,50,20,90,75,60,25,10,85,65,80
C. 100,80,90,60,85,75,20,25,10,70,65,50
D. 100,90,20,60,85,75,80,25,10,70,65,50
24.假设双向链表结点的类型如下： typedef struct Linknode{int data;struct Linknode *lLink; /*前驱结点指针*/struct Linknode *rLink; /*后继结点指针*/ }下面给出的算法是要把一个q所指新结点，作为非空双向链表中的p所指的结点前驱结点插入到该双向链表中，能正确完成要求的算法段是( )。 (满分:2.5)
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. 以上均不对
25.若已知一个栈的入栈序列是1,2,3,?,n，其输出序列为P1,P2,P3,?,Pn，若P1=n，则Pi为 ( )。 (满分:2.5)
A. i
B. n-i
C. n-i+1
D. 不确定
26.用某种排序方法对线性表{25,84,21,47,15,27,68,35,20}进行排序时，元素序列的变化情况如下： (1) 25,84,21,47,15,27,68,35,20(2) 20,15,21,25,47,27,68,35,84(3) 15,20,21,25,35,27,47,68,84(4) 15,20,21,25,27,35,47,68,84 则所采用的排序方法是( )。 (满分:2.5)
A. 选择排序
B. 希尔排序
C. 归并排序
D. 快速排序
27.若在线性表中采用折半查找法查找元素，该线性表应该( ) (满分:2.5)
A. 元素按值有序
B. 采用顺序存储结构
C. 元素按值有序，且采用顺序存储结构
D. 元素按值有序，且采用链式存储结构
28.设有两个串p和q，求q在p中首次出现的位置的运算称作( )。 (满分:2.5)
A. 连接
B. 模式匹配
C. 求子串
D. 求串长
29.下面关于进程控制块的说法中，错误的是( )。 (满分:2.5)
A. 进程控制块对每个进程仅有一个
B. 进程控制块记录进程的状态及名称等
C. 进程控制块位于主存储区内
D. 进程控制块的内容、格式及大小均相同
30.( )是信息的载体，它能够被计算机识别、存储和加工处理。 (满分:2.5)
A. 数据
B. 数据元素
C. 结点
D. 数据项
31.下面关于临界区的说法中，错误的是( ) 。 (满分:2.5)
A. 进程中，访问临界资源的程序是临界区
B. 同时进行临界区的进程必须互斥
C. 进入临界区内的两个进程访问临界资源时必须互斥
D. 在同一时刻，只允许一个进程进入临界区
32.设有1000个无序的元素，希望用最快的速度挑选出其中前10个最大的元素，最好选用( )排序法。 (满分:2.5)
A. 冒泡排序
B. 快速排序
C. 堆排序
D. 希尔排序
33.在一非空二叉树的中序遍序序列中，根结点的右边( )。 (满分:2.5)
A. 只有右子树的所有结点
B. 只有右子树的部分
C. 只有左子树的部分结点
D. 只有左子树的所有结点
34.若需在O(nlogn)的时间内完成对数组的排序，且要求排序是稳定的，则可选择的排序方法是( )。 (满分:2.5)
A. 快速排序
B. 堆排序
C. 归并排序
D. 希尔排序
35.稀疏矩阵一般的压缩存储方法有两种，即( )。 (满分:2.5)
A. 二维数组和三维数组
B. 三元组和散列
C. 三元组和十字链表
D. 散列和十字链表
36.下面关于进程和程序的叙述中，错误的是( )。 (满分:2.5)
A. 进程是程序的执行过程，程序是代码的集合
B. 进程是动态的，程序是静态的
C. 进程可为多个程序服务，而程序不能为多个进程服务
D. 一个进程是一个独立的运行单位，而一个程序段不能作为一个独立的运行单位
37.信号量S的初始值为8，在S上调用10次P操作和6次V操作后，S的值为( )。 (满分:2.5)
A. 10
B. 8
C. 6
D. 4
38.若把操作系统看作计算机系统资源的管理者，下列( )不属于操作系统所管理的资源。 (满分:2.5)
A. 程序
B. 内存
C. CPU
D. 中断
39.假定有K个关键字互为同义词，若用线性探测法把这K个关键字存入散列表中，至少要 进行( )次探测。 (满分:2.5)
A. K-1次
B. K次
C. K+1次
D. K(K+1)/2次
40.设n，m为一棵二叉树上的两个结点，在中序遍历时，n在m前的条件是( )。 (满分:2.5)
A. n在m的右方
B. n是m的祖先
C. n在m的左方
D. n是m的子孙
更多学习资料请登录www.openhelp100.com
页:
[1]