尾元素的当前位置，队列的最大容量为MAXSIZE，则队列满的条件为（ D ）。 A．sq．front= sq．rear B．sq．front= sq．rear+1
C．（sq．front +1）mod MAXSIZE= sq．rear D．（sq．rear+1）mod MAXSIZE= sq．front
13、循环队列sq中，用数组elem存放数据元素，sq．front指示队头元素的前一个位置，sq．rear指示队尾元素的当前位置，队列的最大容量为MAXSIZE，则在队列未满时元素x入队列的主要操作为（ A ）。 A．sq．rear= （sq．rear+1）mod MAXSIZE； sq．elem[sq．rear]=x；
B．sq．elem[sq．rear]=x； sq．rear= （sq．rear+1）mod MAXSIZE； C．sq．front= （sq．front+1）mod MAXSIZE； sq．elem[sq．front]=x；
D．sq．elem[sq．front]=x； sq．front= sq．front+1；
14、循环队列sq中，用数组elem[0‥25]存放数据元素，sq．front指示队头元素的前一个位置，sq．rear指示队尾元素的当前位置，设当前sq．front为20，sq．rear为12，则当前队列中的元素个数为（ ）。 A．8 B．16 C．17 D．18
15、设循环队列的元素存放在一维数组Q[0‥30]中，队列非空时，front指示队头元素的前一个位置，rear指示队尾元素。如果队列中元素的个数为11，front的值为25，则rear应指向（ ）元素。 A．Q[4] B．Q[5] C．Q[14] D．Q[15] 16、队列操作的原则是（A ）。
A．先进先出 B．后进先出 C．只能进行插入 D．只能进行删除 17、一个队列的入列序列是1234，则队列的输出序列是（ B）。 A．4321 B．1234 C．1432 D．3241 18、下列关于串的叙述中，不正确的是（ ）。 A．串是字符的有限序列 B．空串是由空格构成的串
C．模式匹配是串的一种重要运算
D．串既可以采用顺序存储，也可以采用链式存储
二、填空题
1、对于栈只能在（栈顶 ）插入和删除元素。
2、设有一空栈，现有输入序列1，2，3，4，5，6，经过push，push，pop，push，pop，push，push后，输出序列是（ 2，3 ）。 、有一个循环队列如下图，其队满条件是（front=(rear+1)%n），队列空的条件是（rear=front）。
三、程序填空题
1、链队列的存储结构为：
struct nodetype
{ ELEMTP data； struct nodetype *next； } struct linkqueue
{struct nodetype *front，*rear； } /*front和rear分别为队列的头指针和尾指针*/ 完成下列删除队头元素的算法。
delq（struct linkqueue *r，ELEMTP *x） {q=*r；
6
if（q.front= =q.rear）printf（“QUEUE IS EMPTY\\n“）； else{p=q.front->next； q.front->next=p->next； if（p->next= =NULL） q.rear=q.front；
*x=p->data；free（p）； }
2.4数组
1、设6行8列的二维数组A6×8=（aij）按行优先顺序存储，若第一个元素的存储位置为200，且每个元素占3个存储单元，则元素a54的存储位置为（B ）。 A．308 B．305 C．266 D．269
2、设有一个10阶的对称矩阵A，采用压缩存储方式，以行序为主存储，a11为第一个元素，其存储地址为1，每元素占1个地址空间，则a85的地址为（B ）。
A．13 B．33 C．18 D．40
3、设二个数组为A[0‥7]、B[-5‥2，3‥8]，则这两个数组分别能存放的字符的最大个数是（ C ）。 A．7和35 B．1和5 C．8和48 D．1和6
4、二维数组M[i，j]的元素是4个字符（每个字符占一个存储单元）组成的串，行下标i的范围从0到4，列下列j的范围从0到5。M按行存储时元素M[3，5]的起始地址与M按列存储时元素（ B）的起始地址下同。
A．M[2，4] B．M[3，4] C．M[3，5] D．M[4，4]
5、设二维数组为M[0‥8，0‥10]，每个元素占2L个存储单元，以行序为主序存储，第一个元素的存储位置为P。存储位置为P+50L的元素为（ A ）。 A．M[2，3] B．M[2，2] C．M[3，3] D．M[3，4]
6、设二维数组A的维数界偶定义为[1‥8，0‥10]，起始地址为LOC，每个元素占2L个存储单元，以行序为主序存储方式下，某数据元素的地址为LOC+50L，则在列序为主序存储方式下，该元素的存储地址为（D）。 A．LOC+28L B．LOC+36L C．LOC+50L D．LOC+52L
7、数组A[1‥40，1‥30]采用三元组表示，设数组元素与下标均为整型，则在非零元素个数小于（ D ）时，才能节省存储空间。
A．1200 B．401 C．399 D．400 8、一维数组通常采用顺序存储结构，这是因为（C ）。 A．一维数组是一种线性数据结构 B．一维数组是一种动态数据结构
C．一旦建立了数组，则数组中的数据元素之间的关系不再变动 D．一维数组只能采用顺序存储结构
9、对稀疏矩阵进行压缩存储的目的是（B ）。
A．方便存储 B．节省存储空间 C．方便运算 D．节省运算时间
10、设二维数组a[0‥5，0‥6]按行存储，每个元素占d个存储单元，如果每个元素改为2d个存储单元，起始地址不变，则元素a[2，6]的存储地址将要增加（ A）个存储单元。 A．20d B．21d C．38d D．39d 11、一维数组与线性表的区别是（ ）。
A．前者长度固定，后者长度可变 B．后者长度固定，前者长度可变 C．两者长度均固定 D．两者长度均可变 二、填空
7
1、一个稀疏矩阵为，
则对应的三元组线性表为（（（0，2，2），（1，0，3），（2，2，-1），（2，3，5）））。
2、设有二维数组A[0‥9，0‥19]，其每个元素占两个字节，数组按列优先顺序存储，第一个元素的存储地址为100，那么元素A[6，6]的存储地址为（232）。
2.5树和二叉树
一、选择题
1、下列树的度为（ ）。
A．2 B．3 C．5 D．8 2、含10个结点的二叉树中，度为0的结点有4个，则度为2的结点有（ ）个。
A．3 B．4 C．5 D．6
3、对一棵有100个结点的完全二叉树按层编号，则编号为49的结点，它的左孩子的编号为（ ）。 A．98 B．99 C．97 D．50 4、一棵深度为8（根的层次号为1）的满二叉树有（ ）个结点。
A．256 B．255 C．128 D．127
5、设二叉树根结点的层数为1，若一棵高（深）度为h的二叉树只有度为0与度为2的结点，则其结点数至少为（ ）。 A．h B．2h-1 C．2h D．2h+1
6、对下列二叉树进行先根次序遍历，所得次序为（ ）。
A．ABCDEF B．ADCBFE C．BCDAFE D．DCBFEA 7、一棵二叉树的前（先）序序列为ABCDEFG，则它的中序序列不可能为（ ）。 A．CBDAFEG B．DCBAEFG C．CDBAGEF D．BDCAFGE B．4 C．5 D．6 9、具有n个结点的二叉树，有（ ）条边。
A．n B．n-1 C．n+1 D．2n 10、在具有n个结点的二叉树的二叉链表表示中，2n个孩子指针域中，只用到（ ）个域。 A．n B．n-1 C．n+1 D．2n 11、对哈夫曼树，下列说法错误的是（ ）。 A．哈夫曼树是一类带树路径长度最短的树。 B．给出一组数，构造的哈夫曼树唯一。
C．给出一组数，构造的哈夫曼树的带树路径长度不变。
8、若先序遍历二叉树的结果为结点序列A，B，C，则有（ ）棵不同的二叉树可以得到这一结果。 A．3
D．哈夫曼树的带权路径长度为每个叶子的路径长度与该叶子权值乘积之和。
12、假定在一棵二叉树中，双分支结点数为15个，单分支结点数为30个，则叶子结点数为（ ）。 A．15 B．16 C．17 D．47
13、假定一棵三叉树的结点数为50，则它的最小高度为（ ）。
A．3 B．4 C．5 D．6
14、由带权为9，2，5，7的四个叶子结点构造一棵哈夫曼树，该树的带权路径长度为（ ）。
A．23 B．37 C．46 D．44
15、二叉树的先序遍历为EFHIGJK，中序遍历为HFIEJKG，则该二叉树根的右子树的根是（ ）。 A．E
8
B．F C．G D．H
16、在完全二叉树中，若一个结点是叶结点，则它没有（ ）。
A．左孩子结点 B．右孩子结点
C．左孩子和右孩子结点 D．左孩子结点，右孩子结点和兄弟结点
17、（ ）二叉树，可以唯一地转化成一棵一般树。
A．根结点无左孩子 B．根结点无右孩子 C．根据结点有两个孩子 D．没有一棵 18、具有65个结点的完全二叉树其深度为（ ）。 A．8 B．7 C．6 D．5
19、某二叉树的先序序列和后序序列正好相反，则该二叉树一定是（ ）的二叉树。 A．空或只有一个结点 B．高度等于其结点数
C．任一结点无左孩子 D．任一结点无右孩子 20、下面叙述中，不正确的是（ ）。
A．线性表中除第一个元素和最后一个元素外，其他每个元素都有且仅有一个直接前驱和一个直接后继 B．树中有且仅有一个结点没有前驱
C．环形队列中任何一个元素都有且仅有一个直接前驱和一个直接后继 D．在树中，一个结点可以有多个直接后继
21、有m个叶子结点的哈夫曼树，其结点总数是（ ）。 A．2m B．2m+1 C．2m-1 D．2（m+1） 二、填空题
1、在一棵二叉排序树上按（ ）遍历得到的结点序列是一个有序序列。
2、对于一棵具有n个结点的二叉树，当进行链接存储时，其二叉链表中的指针域的总数为2n个，其中（ ）个用于链接孩子结点。
3、对于下面的二叉树，按后序遍历得到的结点序列为（ ）。 三、程序填空题
1、下面算法实现，用一棵二叉树中的结点建立一个按关键字值从小到大次序排列的带表头结点的双向循环链表。二叉树的结点结构如下所示：其中，p是指向结点的指针；p->key表示结点的关键字域，p->left和p->right分别表示结点的左、右孩子的指针域。 void fromtreetolist（p，l）
/*p，h是指向二叉树中结点的指针，*/ /*l是指向双向循环链表表头结点的指针*/ {if (p!=NULL) { fromtreetolist（p->left，l）； fromtreetolist（p-> right，l）；
h=l；
while （h->right!=l）&&（h->right->key
void buildlisttree（root，l）
/*root是指向二叉树根结点的指针，*/
/*l是指向双向循环链表表头结点的指针*/
{l=（struct nodetype *）malloc（sizeof（struct nodetype））；
9
l->left=l； l->right=l；
fromtreetolist（root，l）； }
2.6、图
1、设图的邻接矩阵为 ，则该图有（ ）个顶点。 A．3 B．4 C．6 D．9
2、设图的邻接矩阵为 ，则该图为（ ）。 A．有向图 B．无向图 C．强连通图 D．完全图
3、设图的邻接链表如下图所示，则该图有（ ）条边。
A．4 B．5 C．10 D．20 4、设有6个结点的无向图，该图至少应有（B）条边才能确保是一个连通图。 A．5 B．6 C．7 D．8
5、已知一有向图的邻接表存储结构如下，则根据有向图的深度优先遍历算法，从顶点V1出发，不能得到的顶点序列是（ ）。
A．V1V2V3V5V4 B．V1 V3 V4V5V2 C．V1V2V4V5V3
D．V1 V4V3V5V2
6、下列图的深度优先遍历序列为（ ）。 A．ABCDEFGH B．ABDHECFG
C．ABEDHCFG D．ABCFGEDH
7、对一个具有n个顶点的图，采用邻接矩阵表示则该矩阵的大小为（D）。 A．n B．（n-1）2 C．（n+1）2 D．n2 二、填空题
1、设无向图G的顶点数为n，图G最少有（ ）边。 2、对下列图
它的生成树有（ ）棵。
10
计算机软件技术基础
第二章 智能0801班 2.1数据结构概论
一、选择题
1、数据的逻辑结构是（ A ）。 A．数据的组织形式 B．数据的存储形式 C．数据的表示形式
D．数据的实现形式
2、组成数据的基本单位是（ C ）。
A．数据项 B．数据类型 C．数据元素 D．数据变量 3、下面程序的时间复杂度为（ ）。 x=0；
for（i=1；i x++； A．O（ ） B．O（n2） C．O（1） D．O（n） 4、下面程序的时间复杂度为（ ）。 for（i=0；i D．O（m+n） 5、下面程序段的执行次数为（ ）。 for（i=0；i 6、下面程序的时间复杂度为（A ）。 for（i=0；i for（k=0；k c[i][j]=c[i][j]+a[i][k]*b[k][j]； 1 A．O（m×n×t） B．O（m+n+t） C．O（m+n×t） D．O（m×t+n） 二、填空 1、数据结构按逻辑结构可分为两大类，它们分别是（线性）和（非线性）。 2、算法的计算量的大小称为（ 时间复杂度 ）。 2.2线性表 1、与顺序存储结构相比，链式存储结构的存储密度（ ）。 A．大 B．小 C．相同 D．以上都不对 2、对于存储同样一组数据元素而言，（ ）。 A．顺序存储结构比链接结构多占空间 B．在顺序结构中查找元素的速度比在链接结构中查找要快 C．与链接结构相比，顺序结构便于安排数据元素 D．顺序结构占用整块空间而链接结构不要求整块空间 4、设顺序表共有n个元素，用数组elem存储，实现在第i个元素之前插入一个元素e的操作，其主要语句为（ ）。 A．FOR j=n DOWNTO i DO elem[j]=elem[j+1]； elem[i]=e； B．FOR j=i TO n DO elem[j]=elem[j+1]； elem[i]=e； C．FOR j=i TO n DO elem[j+1]=elem[j]； elem[i]=e； D．FOR j=n DOWNTO i DO elem[j+1]=elem[j]； elem[i]=e； 5、顺序表有5个元素，设在任何位置上插入元素是等概率的，则在该表中插入一个元素时所需移动元素的平均次数为（ C ）。 A．3 B．2 C．2．5 D．5 6、设顺序表有9个元素，则在第3个元素前插入一个元素所需移动元素的个数为（ C ）。 A．9 B．4．5 C．7 D．6 7、设顺序表有19个元素，第一个元素的地址为200，且每个元素占3个字节，则第14个元素的存储地址为（ B ）。 A．236 B．239 C．242 D．245 8、设顺序表的第5个元素的存储地址为200，且每个元素占一个存储单元，则第14个元素的存储地址为（ B ）。 A．208 B．209 C．210 D．214 9、设p为指向双向循环链表中某个结点的指针，p所指向的结点的两个链域分别用p->llink和p->rlink表示，则下列等式中（D ）成立。 A．p=p->llink B．p=p->rlink C．p=p->llink->llink D．p=p->llink->rlink 10、线性表采用链式存储时，其地址（ D ）。 A．必须是连续的 B．一定是不连续的 C．部分地址必须是连续的 D．连续与否均可以 11、线性表是（ A ）。 A．一个有限序列，可以为空 B．一个有限序列，不可以为空 C．一个无限序列，可以为空 D．一个无限序列，不可以为空 12、链式存储的线性表中的指针指向其（ B ）。 A．前趋结点 B．后继结点 C．物理前趋 D．物理后继 13、设在链式存储的线性表中，设结点结构为 data link ，欲在p结点后插入一个结点q的关键步骤为（ A ）。 A．q->link=p->link； p->link=q； B．p->link=q->link； p->link=q； C．q->link=p->link； q->link=p； D．p->link=q->link； q->link=p； 14、设有指针head指向的带表头结点的单链表，现将指针p指向的结点插入表中，使之成为第一个结点，其 2 操作是（ A）（其中，p->next、head->next分别表示p、head所指结点的链域）。 A．p->next=head->next； head->next=p； B．p->next=head->next； head=p； C．p->next=head； head=p； D．p->next=head； p= head； 二、填空 1、顺序存储的线性表，设其长度为n，在任何位置上插入或删除操作的时间代价基本上都是等效的。则插入一个元素大约要移动表中的（ N/2 ）个元素。 2、线性表的长度是（ 数据元素个数 ）。 3、在带有头结点的双链表L中，指针p所指结点是第一个元素结点 的条件是（p—>llink=h或h->r link=p）。 4、某链表如下所示 若要删除值为C的结点，应做操作（ p->link=p->link->link ）。 三、程序填空题 1、设顺序存储的线性表存储结构定义为： struct sequnce {ELEMTP elem[MAXSIZE]； int len； /*线性表长度域*/ } 将下列简单插入算法补充完整。 void insert（struct sequnce *p，int i，ELEMTP x） {v=*p； if（i<1）||（i>v.len+1） printf（“Overflow“）； else { for（j=v.len；j>=i；j- -） v.elem[j+1]=v.elem[j]； v.elem[i]= x ；v.len=v.len+1； } } 2、设线性链表的存储结构如下： struct node {ELEMTP data； /*数据域*/ struct node *next； /*指针域*/ } 试完成下列在链表中值为x的结点前插入一个值为y的新结点的算法。如果x不存在，则把新结点插在表尾。 void inserty（struct node *head，ELEMTP x，ELEMTP y） {s=（struct node *）malloc（sizeof（struct node））； s->data=y； if（head->data= =x） {s->next=head；head=s；} else { q=head；p=q->next； while（p->data!=x && p->next!=NULL） 3 {q=p；p=p->next；} if（p->data= = x） {q->next=s；s->next=p；} else {p->next=s；s->next=NULL；} } } 3、设线性链表的存储结构如下： struct node {ELEMTP data； /*数据域*/ struct node *next； /*指针域*/ } 试完成下列建立单链表的算法。 creat（） {char var； head=（struct node *）malloc（sizeof（struct node））； head->next= NULL ； while ( (var =getchar ( ) )!= ‘\\n’) { ptr=（ struct node *）malloc（sizeof（struct node））； ptr->data= var ； ptr->next = head->next； head->next= ptr ； } } 4、下列算法将单链表中值重复的结点删除，使所得的结果表中各结点值均不相同，试完成该算法。 void DelSameNode（LinkList L） //L是带头结点的单链表，删除其中的值重复的结点// {ListNode * p，*q，*r； p = L->next； //p初始指向开始结点// while（p） //处理当前结点p// { q = p； r = q->next； do { //删除与结点*p的值相同的结点// while（r&&r->data!=p->data）{ q = r； r = r->next； } if（r）{ //结点*r的值与*p的值相同，删除*r// q->next = r->next； free（r）； r = q->next； } }while（ r ）； p = p->next； } } 4 2.3栈、队列、串 一、填空题 1、在栈中，下列说法正确的是（A ）。 A．每次插入总是在栈顶，每次删除也总是在栈顶。 B．每次插入总是在栈顶，每次删除总是在栈底。 C．每次插入总是在栈底，每次删除总是在栈顶。 D．每次插入总是在栈底，每次删除也总是在栈底。 2、设有一个栈，按A、B、C的顺序进栈，则下列（ C ）为不可能的出栈序列。 A．ABC B．CBA C．CAB D．ACB 3、设有一个栈，按A、B、C、D的顺序进栈，则下列（D ）为可能的出栈序列。 A．DCAB B．CDAB C．DBAC D．ACDB 4、顺序栈的上溢是指（ B ）。 A．栈满时作退栈运算 B．栈满时作进栈运算 C．栈空时作退栈运算 D．栈空时作进栈运算 5、顺序栈S中top为栈顶指针，指向栈顶元素所在的位置，elem为存放栈的数组，则元素e进栈操作的主要语句为（ D）。 A．s．elem[top]=e； s．top=s．top+1； B．s．elem[top+1]=e； s．top=s．top+1； C．s．top=s．top+1； s．elem[top+1]=e； D．s．top=s．top+1； s．elem[top]=e； 6、设有5个元素A，B，C，D，E顺序进栈（进栈过程中可以出栈），出栈后依出栈次序进入队列，已知其出队次序为D，C，E，B，A，则该栈容量必定不小于（C ）。 A．2 B．3 C．4 D．5 7、设栈S的初始状态为空，现有五个元素组成的序列1，2，3，4，5，对该序列在栈S上依次进行PUSH，PUSH，POP，PUSH，POP，PUSH，PUSH操作，出栈的元素序列是（ C）。 A．5，4，3，2，1 B．2，1 C．2，3 D．3，4 8、在一个具有n个单元的顺序栈中，假定以地址低端（即0单元）作为栈底，以top为栈顶指针，则当做出栈处理时，top变化为（ ）。 A．top不变 B．top=0 C．top- - D．top++ 9、向一个栈顶指针为hs的链栈中插入一个*s结点时，应执行（ B）。 A．hs->next=s； B．s->next=hs；hs=s； C．s->next=hs->next；hs->next=s； D．s->next=hs；hs=hs->next； 10、在队列中，下列说法正确的是（A ）。 A．每次插入总是在队尾，每次删除总是在队头。 B．每次插入总是在队尾，每次删除也总是在队尾。 C．每次插入总是在队头，每次删除也总是在队头。 D．每次插入总是在队头，每次删除总是在队尾。 11、在带头结点的链队列q中，用q．front表示队头指针，q．rear表示队尾指针，结点结构为data next ，删除链队列的队头结点的主要语句为（B ）。 A．s=q．front； q．front->next= s．next； B．s=q．front->next； q．front->next= s．next； C．s=q．front->next； q．front= s．next； D．s=q； q．front->next= s．next； 12、循环队列sq中，用数组elem存放数据元素，sq．front指示队头元素的前一个位置，sq．rear指示队 5 三、程序填空题 1、下列算法将图的邻接矩阵存储结构转换为如下图所示的邻接表存储结构。图中左侧的记录数组的每个结点有两个域：el和fst；右侧链表中的结点是类型为node的记录类开，每个结点有两个域：adj和link。若指针p指向node类型的结点，则对该结点的adj、link域的引用表示为：p->adj、p->link。 void Convert（c，g） /*c是邻接矩阵，n为阶数。g是上图所示的邻接表*/ /*p、q是指向node类型结点的指针*/ /*i，j为整型*/ { for（i=1；i<=n；i++） { g[i].fst=NULL； for（j=1；j<=n ；j++） if（c[i，j]!=0） { q=（struct nodetype *）malloc（sizeof（struct nodetype））； q->link=NULL； q->adj=j； if（q[i].fst=NULL） { q[i].fst=q ； p=q } else { p->link=q； p=q； } } } } 2.7查找 一、选择 1、对含n个记录的顺序表进行顺序查找，在最坏情况下需要比较（ ）次。 A．n-1 B．n C．（n+1）/2 D．n（n-1）/2 2、对含n个记录的有序表进行折半查找，设每个记录的查找概率相等，则平均查找长度的数量级为（ ）。 A．O（n） B．O（n2） C．O（log2n） D．O（1） 3、有一棵二叉树如下图，该树是（ ）。 A．二叉平衡树 B．二叉排序树 C．堆的形状 D．以上都不是 4、已知10个数据元素（50，30，15，35，70，65，95，60，25，40），按照依次插入结点的方法生成一棵二叉排序树后，在查找成功的情况下，查找每个元素的平均比较次数（又称平均查找长度）为（ ）。 A．2.5 B．3.2 C．2.9 D．2.7 5、在顺序存储的线性表R[0‥29]上进行分块查找（设分为5块）的平均查找长度为（ ）。 A．6 B．11 C．5 D．6.5 6、已知一个线性表（38，25，74，63，52，48），假定采用h（k）=k%7计算散列地址进行散列存储，若引用线性探测的开放定地址法解决冲突，则在该散列表上进行查找的平均查找长度为（ ）。 11 A．1.5 B．1.7 C．2 D．2.3 7、设散列地址空间为0~m-1，k为关键字，用P去除k，将余数作为k的散列地址，即：h（k）=k%P，为了减少发生冲突的可能性，一般取P为（ ）。 A．小于m的最大奇数 B．小于m的最大素数 C．小于m的最大偶数 D．小于m的最大合数 8、设散列表表长m=14，散列函数为h（k）=k，表中已有4个记录，如果用二次探测再散列处理冲突，关键字为49的记录的存储地址是（ ）。 A．8 B．3 C．5 D．9 二、填空 1、设有两个散列函数H1（K）=K mod 13和H2（K）=K mod 11+1，散列表为T[0‥12]，用双重散列法（又称二次散列法）解决冲突。函数H1用来计算散列地址，当发生冲突时，H2作为计算下一个探测地址的地址增量。假定某一时刻散列表T的状态为： 下一个被插入的关键码为42，其插入位置是（ ）。 2.8排序 一、选择 1、已知8个元素（34，76，45，18，26，54，92，65），按照依次插入结点的方法生成一棵二叉排序树，该树的深度为（C）。 A．4 B．5 C．6 D．7 2、直接插入排序算法的时间复杂度为（ ）。 A．O（n） B．O（n2） C．O（） D．O（1） 3、设记录关键字序列为（84，67，21，50，33，79），采用对半插入排序方法自小到大进行排序时，记录的移动次数为（ ）。 A．9 B．10 C．19 D．25 4、下列四个序列中，（ ）不是快速排序第一趟的可能结果。 A．[68，11，69，23，18，70，73] 93 B．11 [68，69，23，18，70，73，93] C．[68，11，69，23，18] 70 [93，73] D．[18，11，23] 93 [68，70，69，73] 5、下列四个关键字序列中，（ ）不是堆。 A．{05，23，16，68，94，72，71，73} B．{05，16，23，68，94，72，71，73} C．{05，23，16，73，94，72，71，68} D．{05，23，16，68，73，71，72，94} 6、从未排序序列中依次取出元素与已排序序列中的元素作比较，将其放入已排序序列中的正确位置上，此方法称为（ ）。 A．归并排序 B．选择排序 C．交换排序 D．插入排序 7、在所有排序方法中，关键字的比较次数与记录的初始排列无关的是（ ）。 A．Shell排序 B．冒泡排序 C．直接插入排序 D．直接选择排序 8、下列排序算法中，第一趟排序后，任一元素都不能确定其最终位置的算法是（ ）。 A．选择 B．插入 C．冒泡 D．快速 12 9、采用下列排序算法对n个元素进行排序，其排序趟数肯定为n-1趟的排序方法有（ ）。 A．选择和插入 B．冒泡和快速 C．插入和快速 D．选择和冒泡 10、若用冒泡排序方法对序列{10，14，26，29，41，52}从大到小进行排序，需要进行（ ）次比较。 A．5 B．10 C．15 D．25 11、用直接插入排序方法对下面四个序列进行排序（由小到大），元素比较次数最少的是（ ）。 A．94，32，40，90，80，46，21，69 B．32，40，21，46，69，94，90，80 C．21，32，46，40，80，69，90，94 D．90，69，80，46，21，32，94，40 二、填空题 1、已知一棵二叉排序树如下图所示，则在查找成功的情况下查找每个元素的平均查找长度为（ 三、程序填空题 1、在下面冒泡排序算法中填入适当内容，以使该算法在发现有序时能及时停止。 bubble（R） Rectype R[n]； {int i，j，exchang； Rectype temp； i=1； do {exchang=False； for（j=n；j>= i+1 ；j- -） if（R[j] exchang=True ； } i=i+1 ； }while（exchang=False ）； } 2、完成下列折半插入排序算法。 Void binasort（struct node r[MAXSIZE]，int n） { for（i=2；i<=n；i++） { r[0]=r[i]； low=1； high=i-1； while（low<=high） { mid=（low+high）/2； if（r[0].key ）。 13 else low=mid+1 ； } for（j=i-1；j>=low；j- -） r[j+1]=r[j] ； r[low]=r[0] ； } } 第三章、操作系统 第一节 一、选择题 1、存储器管理是操作系统的重要组成部分之一，这里存储器是指 。 A．计算机内存 B. 计算机外存 C. 计算机内存和外存 D. 高速缓存 2、计算机存储器可分为三级，其中Cache与主存的存取速度相比较 。 A．两者速度相同 B. Cache速度大于主存 C. Cache速度小于主存 D. 不一定 3、“单一连续区”存储管理对内存分配方式所采用的是 。 A．静态分配方式 B. 动态分配方式 C. 动静态结合方式 D. 不分配 4、“单一连续区”存储管理若用户进程大于可用空闲区，则 。 A．等待直到其它进程释放内存 C．开辟虚拟存储空间 B. 将当前进程分为若干块装入 D. 无法执行该进程 5、固定分区分配法是指 。 A．在作业执行前预先将分区划分为若干大小相等的连续区域 B．在作业执行前预先将分区划分为若干大小不等的连续区域 C．在作业执行时根据具体情况将分区划分为若干大小相等的连续区域 D．在作业执行时根据具体情况将分区划分为若干大小不等的连续区域 6、动态可变分区法是指 。 A．在作业执行前不分区，作业执行时再根据具体要求分区 B．在作业执行前不分区，作业执行时系统自动划分若干大小不等的区域 C．在作业执行前先分区，作业执行时再根据具体要求调整 D．在作业执行前先分区，作业执行时分区将不再变化 7、空闲区分配算法中，从空闲链表开头查找，若将找到的第一个不小于所需空闲块分配给用户的算法称 。 A．首次适应算法 B. 下次适应算法 C. 最佳适应算法 D. 最坏适应算法 8、空闲区分配算法中，从空闲链表开头查找，若找到一个不小于且最接近所需空闲块时，将其分配给用户的算法称 。 A．首次适应算法 B. 下次适应算法 C. 最佳适应算法 D. 最坏适应算法 9、可变分区其空闲区分配算法中，最差适应算法是指 。 A．将最小的一个空闲块分配给用户 B. 将最大的一个空闲块分配给用户 C．将最后的一个空闲块分配给用户 D. 是空闲区分配算法中最差的一种 10、下列空闲区分配算法中，哪种算法通常将所有空闲块按大小顺序升序排列 。 A．首次适应算法 B. 下次适应算法 C. 最佳适应算法 D. 最差适应算法 14 11、下列空闲区分配算法中，哪种算法通常将所有空闲块按大小顺序降序排列 。 A．首次适应算法 B. 下次适应算法 C. 最佳适应算法 D. 最差适应算法 12、覆盖与交换技术是用于扩充内存的两种方式，其中 。 A．覆盖技术由用户完成，而交换技术由操作系统完成 B．覆盖技术由操作系统完成，而交换技术由用户完成 C．覆盖技术和交换技术均由用户完成 D．覆盖技术和交换技术均由操作系统完成 13、交换技术是将 。 A．处于等待状态的进程换出内存 B. 处于就绪状态的进程换出内存 C．处于运行状态的进程换出内存 D. 处于完成状态的进程换出内存 14、分页存储管理的“页”是指 。 A．每页的大小固定，所有的页均完全相等 B. 每页的大小不定，页与页间不相等 C．每页的大小固定，但页与页间不相等 D. 页随进程的大小而变化 15、分页式存储管理与分区式存储管理相比 。 A．分页式存储管理易于产生碎片 B. 分区式存储管理易于产生碎片 C．分页式和分区式存储管理均易产生碎片 D. 分页式和分区式存储管理均不易产生碎片 16、分页式存储管理与分区式存储管理相比 。 A．分页式存储管理其硬件开销大 B. 分区式存储管理其硬件开销大 C．分页式和分区式存储管理硬件开销相同 D. 不一定 17、请求式分页管理其基本思想是 。 A．运行一个作业时首先将该作业全部调入内存 B．不要求将作业全部调入内存，当需要该页时再调入 C．不要求将作业全部调入内存，当需要该页时首先淘汰内存中的老页面再调入新页面 D．不要求将作业全部调入内存，当需要该页时若内存不满，则直接调入，否则首先淘汰内存中的老页面再调入新页面 18、采用请求式分页管理的FIFO（先进先出）算法，会出现分配的页面数增多缺页次数反而增加的奇怪现象，我们称该现象为 。 A．死锁现象 B. 等待现象 C. Belady现象 D. Denning现象 19、请求式分页管理的LRU算法表示 。 A．最近没有使用页面淘汰算法 B. 最不经常使用页面淘汰算法 C．最近最久未使用页面淘汰算法 D. 将来再也不使用的页面淘汰算法 20、请求式分页管理的OPT算法表示 。 A．最近没有使用页面淘汰算法 B. 最不经常使用页面淘汰算法 C．最近最久未使用页面淘汰算法 D. 将来再也不使用的页面淘汰算法 15 21、在请求式分页管理中，要完全实现LRU算法是一种十分困难的事情，因此在实际系统中往往使用近似的算法，NUR就是一种近似算法，它表示 。 A．最近没有使用页面淘汰算法 B. 最不经常使用页面淘汰算法 C．最近最久未使用页面淘汰算法 D. 将来再也不使用的页面淘汰算法 22、在请求式分页管理中，要完全实现LRU算法是一种十分困难的事情，因此在实际系统中往往使用近似的算法，LFU就是一种近似算法，它表示 。 A．最近没有使用页面淘汰算法 B. 最不经常使用页面淘汰算法 C．最近最久未使用页面淘汰算法 D. 将来再也不使用的页面淘汰算法 23、下列哪种算法作为理想型算法，只是在理论研究中被提出，而在实际应用中根本无法实现 。 A．OPT B. LRU C. LFU D. NUR 24、请求式分页管理中页号表示 。 A．每个作业在虚拟空间中的分页编号 B. 每个作业在内存空间中的分页编号 C．不在内存中的页面编号 D. 被淘汰的页面编号 25、请求式分页管理中的块号（页架号）表示 。 A．每个作业在虚拟空间中的分页编号 B. 每个作业在内存空间中的分页编号 C．不在内存中的页面编号 D. 被淘汰的页面编号 26、请求式分页管理中的页表由若干控制信息构成，其中状态位（缺页中断位）表示 。 A．要访问的页是否在内存 B. 要访问的页是否在外存 C．该页内容进入内存后是否被访问过 D．该页内容进入内存后是否被修改过 27、请求式分页管理中的页表由若干控制信息构成，其中引用位表示 。 A．要访问的页是否在内存 B. 要访问的页是否在外存 C．该页内容进入内存后是否被访问过 D．该页内容进入内存后是否被修改过 28、采用FIFO算法，当一个进程的页面走向为1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5若内存中的存储块数为M=3，每次只能从外存调入一页，内存初始页面数为0，则在执行该进程过程中发生的缺页次数和缺页率为 。 A．9次，52.9% B. 9次，75% C. 10次，52.9% D. 10次，75% 29、采用LRU算法，当一个进程的页面走向为1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5若内存中的存储块数为M=3，每次只能从外存调入一页，内存初始页面数为0，则在执行该进程过程中发生的缺页次数和缺页率为 。 A．9次，75% B. 9次，83.3% C. 10次，75% D. 10次，83.3% 30、采用FIFO算法，内存中的存储块数M=3，现有2, 3, 4三页在内存中，若当前该进程继续将1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5调入内存时，规定每次只能从外存调入一页，则当前访问后续页面过程中发生的缺 16 页次数和缺页率为 。 A．6次，40% B. 6次，50% C. 9次，50% D. 9次，75% 31、采用LRU算法，内存中的存储块数M=3，现有2, 3, 4三页在内存中，若当前该进程继续将1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5调入内存时，规定每次只能从外存调入一页，则当前访问后续页面过程中发生的缺页次数和缺页率为 。 A．7次，58.3% B. 7次，83.3% C. 10次，58.3% D. 10次，83.3% 32、采用FIFO算法，内存中的存储块数M=4，现有2, 3, 4三页在内存中，若当前该进程继续将1, 2, 3, 4, 5, 1, 2, 3, 4, 5, 2, 1调入内存时，规定每次只能从外存调入一页，则当前访问后续页面过程中发生的缺页次数和缺页率为 。 A．6次，40% B. 6次，50% C. 9次，50% D. 9次，75% 33、用LRU算法，内存中的存储块数M=4，现有2, 3, 4三页在内存中，若当前该进程继续将1, 2, 3, 4, 5, 1, 2, 3, 4, 5, 2, 1调入内存时，规定每次只能从外存调入一页，则当前访问后续页面过程中发生的缺页次数和缺页率为 。 A．8次，53.3% B. 8次，66.7% C. 9次，75% D. 9次，83.3% 34、采用FIFO算法，当一个进程的页面走向为2, 2, 2, 2, 3, 3, 3, 3, 2, 3, 4, 5若内存中的存储块数为M=4，每次只能从外存调入一页，内存初始页面数为0，则在执行该进程过程中发生的缺页次数和缺页率为 。 A．4次，33.3% B. 6次，50% C. 9次，75% D. 10次，83.3% 35、采用LRU算法，当一个进程的页面走向为2, 2, 2, 2, 3, 3, 3, 3, 2, 3, 4, 5若内存中的存储块数为M=4，每次只能从外存调入一页，内存初始页面数为0，则在执行该进程过程中发生的缺页次数和缺页率为 。 A．4次，33.3% B. 6次，50% C. 9次，75% D. 10次，83.3% 36、采用FIFO算法，当一个进程的页面走向为4, 3, 2, 1, 4, 3, 5, 4, 3, 2, 1, 5若内存中的存储块数为M=4，每次只能从外存调入一页，内存初始页面数为0，则在执行该进程过程中发生的缺页次数和缺页率为 。 A．7次，58.3% B. 8次，66.7% C. 9次，75% D. 10次，83.3% 37、采用LRU算法，当一个进程的页面走向为4, 3, 2, 1, 4, 3, 5, 4, 3, 2, 1, 5若内存中的存储块数为M=4，每次只能从外存调入一页，内存初始页面数为0，则在执行该进程过程中发生的缺页次数和缺页率为 。 A．7次，58.3% B. 8次，66.7% C. 9次，75% D. 10次，83.3% 38、采用FIFO算法，当一个进程的页面走向为1, 2, 3, 1, 2, 4, 5, 1, 2, 3, 4, 5若内存中的存储块数为M=5，每次只能从外存调入一页，内存初始页面数为0，则在执行该进程过程中发生的缺页次数和缺页率为 。 A．5次，41.7% B. 6次，50% C. 7次，58.3% D. 8次，66.7% 39、采用LRU算法，当一个进程的页面走向为1, 2, 3, 1, 2, 4, 5, 1, 2, 3, 4, 5若内存中的存储块数为M=5，每次只能从外存调入一页，内存初始页面数为0，则在执行该进程过程中发生的缺页次数和缺页率为 。 17 A．5次，41.7% B. 6次，50% C. 7次，58.3% D. 8次，66.7% 40、段式管理中的每一个段其特点是 。 A．段的大小是固定的，其尺寸由操作系统自身决定 B．段的大小是固定的，其尺寸由内存容量的大小决定 C．段的大小是不固定的，其尺寸由用户的程序单位决定 D．段的大小是不固定的，其尺寸由使用者决定 41、页式管理与段式管理比较 。 A．页有其特定的逻辑意义而段没有意义 B. 段页有其特定的逻辑意义而页没有意义 C．页和段均有其逻辑意义 D. 页和段均没有其逻辑意义 42、段页式管理对地址空间的分配方式是 。 A．先分段，每段中再采用分页方式 B. 先分页，每页中再采用分页方式 C．分段与分页同时进行 D. 分页与分段的先后次序无所谓 43、下列四种存储管理方法，哪种方式不易产生碎片 。 A．固定分区 B. 可变分区 C．分页式管理 D. 分段式管理 二、填空题 1、存储器管理分为 分区、分页、分段、段页式管理 四种方式。 2、存储器管理的主要功能包括 内存分配、地址转换、存储保护、内存扩充 四个部分。 3、存储管理中的分区管理技术通常可分为 固定分区管理、可变分区管理 。 4、操作系统的分区存储管理过程中，为了提高存储器的使用效率常采用可重定位分区分配措施，主要包括 存储区紧缩、重定位 两种方式。 5、操作系统的存储管理技术包括实存和虚存管理，其中虚存管理技术主要有 分页技术、分段技术、段页技术 。 6、操作系统的存储管理中通常采用的内存扩充技术包括 覆盖和交换技术、虚存技术。 第三章、2 一、填空题 1、下列关于进程和程序的描述正确的是 。 A．进程是静态的，程序存在是暂时的 B．进程是静态的，程序存在是永久的 C．进程是动态的，程序存在是暂时的 D．进程是动态的，程序存在是永久的 2、下列关于进程和程序的描述正确的是 。 A．程序是静态的，进程存在是暂时的 B．程序是静态的，进程存在是永久的 C．程序是动态的，进程存在是暂时的 D．程序是动态的，进程存在是永久的 3、在多道环境下，处理器指令系统可分为两类，即特权指令和非特权指令 。 A．特权指令只能供操作系统使用，而非特权指令可供一般用户使用 B．非特权指令供操作系统使用，而特权指令供一般用户使用 C．特权指令和非特权指令均可供一般用户使用 D．特权指令和非特权指令均只供操作系统使用 18 4、处理器在哪种状态下不能执行特权指令 。 A．管态 B. 目态 C. 主态 B. 执行状态 5、下列哪种状态处理器处于用户执行状态 。 A．管态 B. 目态 C. 主态 B. 执行状态 6、下列操作系统调度中，哪种调度属于高级调度 。 A．作业调度 B. 交换调度 C. 进程调度 D. 处理器调度 7、下列操作系统调度中，哪种调度属于低级调度 。 A．作业调度 B. 交换调度 C. 进程调度 D. 处理器调度 8、作业的生命周期从开始到结束通常经过四个状态，其排列次序依次为 。 A．提交、后备（收容）、执行、完成 B. 后备（收容）、提交、执行、完成 C．执行、后备（收容）、提交、完成 D. 后备（收容）、执行、提交、完成 9、作业存在的主要标志是 。 A．FCB B. JCB C. PCB D. DCT 10、进程存在的主要标志是 。 A．FCB B. JCB C. PCB D. DCT 11、通常一个作业刚进入内存后作为进程处于 。 A．就绪状态 B. 运行状态 C. 阻塞状态 D. 完成状态 12、通常对于单CPU系统任何时刻 。 A．只能有一个进程处于就绪状态 B. 只能有一个进程处于运行状态 C．只能有一个进程处于阻塞状态 D. 最多有三个进程分别处于就绪、运行、阻塞状态 13、下列哪种进程的状态转换不可能发生 。 A．就绪→运行 B. 运行→就绪 C. 就绪→阻塞D. 阻塞→就绪 14、若某进程获得除CPU以外的各种必需的运行资源，则该进程处于 。 A．就绪状态 B. 运行状态 C. 阻塞状态 D. 完成状态 15、若系统根据某种调度算法将CPU分配给某个进程，则可能发生的状态转换为 。A．运行→阻塞 B. 阻塞→就绪C. 就绪→运行 D. 运行→就绪 16、由于分配的CPU时间片已到，进程必须交出CPU则可能发生的状态转换为 。 A．运行→阻塞 B. 阻塞→就绪 C. 就绪→运行 D. 运行→就绪 17、由于进程要等待I/O设备或发生某种错误，则可能发生的状态转换为 。 A．运行→阻塞 B. 阻塞→就绪 C. 就绪→运行 D. 运行→就绪 18、若某I/O完成，则可唤醒某一进程，使之可能发生的状态转换为 。 A．运行→阻塞 B. 阻塞→就绪 C. 就绪→运行 D. 运行→就绪 19、一个处于运行状态的进程 ，而处于阻塞状态的进程 。 A．可以调用阻塞原语阻塞自己，可以调用唤醒原语唤醒自己 B．可以调用阻塞原语阻塞自己，不可以调用唤醒原语唤醒自己 C．不可以调用阻塞原语阻塞自己，可以调用唤醒原语唤醒自己 D．不可以调用阻塞原语阻塞自己，不可以调用唤醒原语唤醒自己 20、操作系统所规定的原语是指 。 A．用于完成某一特定功能的命令，在执行期间可以中断 B．用于完成某一特定功能的程序，在执行期间可以中断 C．用于完成某一特定功能的命令，在执行期间不允许中断 D．用于完成某一特定功能的程序，在执行期间不允许中断 21、操作系统进程管理中的P、V操作其功能为 。 A．P、V操作均用于申请资源 19 B. P、V操作均用于释放资源 C．P操作用于申请资源而V操作用于释放资源 D．P操作用于释放资源而V操作用于申请资源 22、P、V操作可以实现对多个进程的控制，因此 。 A．P、V操作可以实现进程的同步但不能实现互斥 B．P、V操作可以实现进程的互斥但不能实现同步 C．P、V操作可以实现进程的同步和互斥 D．P、V操作不能实现进程的同步和互斥 23、操作系统中有关临界区的概念是指 。 A．内存中的某种缓冲区 B. 外存的某个区域 C．某种独享资源 D. 进程中不能并发执行的一段程序 24、用于进程间相互制约的典型例子“生产者-消费者问题”属于 。 A．进程间的互斥 B. 进程间的同步 C. 进程间的互斥与同步 D. 以上都不是 25、下列哪个特点不是程序顺序执行的特点 。 A．顺序性 B. 并发性 C. 封闭性 D. 可再现性 26、下列哪个条件不是产生死锁的必要条件 。 A．独享条件 B. 互斥条件 C. 不剥夺条件 D. 环路条件 27、若能破坏死产生的必要条件，将是防止死锁发生的最有效方法，但下列哪种条件几乎很难打破 。 A．互斥条件（非共享）B. 不剥夺条件 C. 部分分配条件 D. 环路条件 28、用P、V操作实现进程互斥，若S表示信号量（资源数），则进程由运行状态进入阻塞状态的条件是 。 A．开始进入P原语时S>2 B. 开始进入P原语时S>1 C．开始进入P原语时S>0 D. 开始进入P原语时S=0 29、用P、V操作实现进程互斥，若S表示信号量（资源数），则可以将某进程从阻塞状态唤醒的条件是 。 A．开始进入V原语时S>1 B. 开始进入V原语时S>0 C．开始进入V原语时S=0 D. 开始进入V原语时S<0 30、若S表示信号量（资源数），S初值为3，开始进入P原语时S为-1表示有 资源被占用。 A．1个 B. 2个 C. 3个 D. 4个 31、若S表示信号量（资源数），S初值为3，开始进入V原语时S为-2表示有 进程处于阻塞状态。 A．1个 B. 2个 C. 3个 D. 4个 32、操作系统中存在着不同对象和范围的调度，其中决定将哪些后备队列中的作业调入内存中的调度称 。 A．作业调度 B. 交换调度 C. 进程调度 D. 设备调度 33、操作系统中存在着不同对象和范围的调度，其中决定就绪队列中哪个进程首先获得处理器的调度称 。 A．作业调度 B. 交换调度 C. 进程调度 D. 设备调度 二、填空 1、常用进程调度的算法主要有 优先数法、轮转调度法、分级调度法 。 2、进程通常具有 、动态性、并发性、相互制约 三个重要特征。 3、对于不同的指令系统，处理器通常有 管态、目态 两种执行状态。 4、在多道环境下，操作系统其指令可分为 、特权指令、非特权指令 两类。 5、操作系统中，作业通常具有 提交、收容（后备）、执行、完成 四种状态。 6、操作系统中，进程通常具有 就绪、运行、等待（阻塞） 三种状态。 7、操作系统中原语是指 一种特殊的系统调用命令，用于完成某一特定功能，在执行期间不允许被打断 。 8、进程控制的原语主要有 创建、阻塞（挂起）、唤醒（激活）、撤消 。 9、操作系统中多个进程并发执行所采用的相互制约方式主要有 同步与互斥 两种。 20 10、消除死锁的方法主要有 、资源剥夺、撤消进程 两种。 11、程序顺序执行的特点为 、顺序性、封闭性、可再现性 。 12、操作系统中调度可分为 作业调度、中级调度、进程调度 三级。 13、产生死锁的主要原因有 系统资源不足、进程推进顺序不当 两种。 第三章、3 一、选择题 1、下列哪种设备为独享设备 。 A．CD-ROM B. 硬盘 C. 显示器 D. 打印机 2、下列哪种设备为共享设备 。 A．CD-ROM B. 绘图仪 C. 针式打印机 D. 激光打印机 3、下列哪种设备为虚拟设备 。 A．CD-ROM B. 硬盘 C. 显示器 D. 打印机 4、下列哪种处理方式不属于计算机访问外围设备的处理方式 。 A．循环测试I/O方式 B. 程序中断I/O方式 C. 脱机I/O方式 D. 通道I/O方式 5、所谓设备独立性是指 。 A．程序与设备相互独立互不干涉 B. 程序运行时不调用相关设备 C．程序中只使用相对代号来表示设备而不使用绝对设备名称 D．程序中只使用逻辑地址来表示设备而不使用物理地址 6、下列哪个符号名不是设备符号名 。 A．CON B. COM C. BAT D. LPT 7、操作系统缓冲技术中其缓冲区通常指 。 A．在计算机内存中开辟的一个区域 B. 在计算机外存中开辟的一个区域 C．在计算机内存和外存间增加一个专门设备 D. 在计算机内存和外存间开辟I/O通道 8、操作系统中所说的虚拟设备是指 。 A．某类假象实际并不存在的设备 B. 某种低速设备 C．某种独占设备 D. 磁盘 9、通过虚拟设备技术可以解决下列哪个问题 。 A．可以把低速设备变为高速设备，独占设备变为共享设备 B．可以把低速设备变为高速设备，但不能把独占设备变为共享设备 C．可以把独占设备变为共享设备，但不能把低速设备变为高速设备 D．既不能把独占设备变为共享设备，也不能把低速设备变为高速设备 10、若CHCT表示通道控制表、COCT控制器控制表、DCT设备控制表、SDT系统设备表，则设备分配程序的工作流程先后顺序为 。 A．CHCT、COCT、DCT、SDT B. SDT、DCT、COCT、CHCT C．DCT、SDT、CHCT、COCT D. DCT、SDT、COCT、CHCT 11、设备处理程序本身也是一个进程，若没有I/O请求或I/O中断，则该进程处于 。 A．就绪状态B. 运行状态 C. 阻塞状态 D. 完成状态 12、从资源管理角度出发，可把I/O设备分为独占设备、 和虚拟设备。 A．系统设备 B. 用户设备 C. 共享设备 D. 直接设备 13、操作系统中采用以空间换取时间的技术是 。 A．SPOOLing技术 B. 虚拟存储技术C. 交换技术 D. 通道技术 14、采用缓冲技术，当进程结束输入/输出处理后，则将该数据缓冲区置于 。 21 A．输入/输出缓冲队列头部 B. 输入/输出缓冲队列末尾 C．空白缓冲队列头部 D. 空白缓冲队列末尾 15、I/O通道实际上是一种 。 A．专用计算机接口 B. 专用计算机总线 C. 专用计算机软件 D. 专用计算机 二、填空题 1、从操作系统资源管理角度，设备可分为 三类。 2、数据传输控制方式（访问外设的方式）包括 。 3、缓冲区通常包括 。 4、SPOOLing技术称为 第三章、4 一、选择题 1、从用户角度看，文件系统的最基本目标是 ，它主要通过鉴定目录管理功能来实现的。 A．实现对文件的按名存取 B. 保护用户和系统文档 C．文件保护及文件安全性 D. 用户对文件的共享 2、按文件的逻辑结构可以把文件分为 和流式结构文件 A．读/写文件 B. 记录结构文件 C. 索引结构文件D. 字符文件 3、为了便于对文件进行存取和管理，在文件系统中采用 管理文件。 A．文件使用权限 B. 文件系统调度 C. 存储空间 D. 目录 4、由于单级目录结构中存在对用户文件的命名冲突问题，因而采用 管理文件。 A．命名约定法 B. 多级目录 C. 路径 D. 索引 5、通常文件管理系统中有一张 ，它是利用二进制的“位”来表示磁盘中一个块的使用情况的。A．文件描述符表 B. 链接指针表 C. 空闲区表 D. 位示图 6、磁盘文件通常以 为单位进行读写。 A．块 B. 记录 C. 柱面 D. 磁道 7、文件系统规定，使用文件前必须先 。 A．命名文件 B. 建立文件 C. 打开文件 D. 备份文件 8、文件系统的层次模型结构中，最上层模块为 。 A．符号文件系统 B. 基本文件系统 C. 存取控制模块 D. 用户接口部分 9、下列哪种设备只适合于顺序存取 。 A．磁盘 B. 磁带 C. 磁鼓 D. 光盘 1、实现文件共享的主要方式有 。 2、文件按其用途可分为 。 3、文件按存取权限可分为 。 4、文件按逻辑结构可分为 。 5、文件按其物理结构可分为 。 6、文件存储空间管理的常用方法有 。 第三章、5 1、UNIX面向用户提供的应用（程序级）界面是 。 A．Shell B. 系统解释 C. 系统调用 D. 语言处理程序 2、UNIX系统的绝大多数代码均采用 编写。 A．B语言 B. C语言 C. PASCAL语言 D. 汇编语言 3、下面均是UNIX系统的特点，除 之外。 A．多用户操作系统B. 交互式操作系统C. 分时操作系统 D. 实时操作系统 4、下面哪一项不是WINDOWS 95/98操作系统所具备的功能 。 22 A．可视化及图形处理 B. 多用户处理C. 多任务并行处理 D. 多服务器处理 1、DOS系统的三个层次模块为 IO.SYS、MSDOS.SYS、COMMAND.COM 。 2、UNIX操作系统主要由 内核、外壳（Sell） 两部分组成。 第四章、数据库系统 1.假定学生关系是S(S#,SNAME,SEX,AGE), 课程关系是C(C#,CNAME,TEACHER), 学生选课关系是SC(S#,C#,GRADE)。 要查找选修\课程的女学生的姓名，将涉及到关系( )。 A)S B)SC,C C) S,SC D)S,C,SC 2.数据库技术的奠基人之一，E.F.CODD于1970年起发表过多篇论文，主要论述的是( ) A)层次数据模型 B)网络数据模型 C)关系数据模型 D)面向对象数据模型 3.数据库管理系统通常提供授权功能来控制不同用户访问数据的权限。这主要是为了实现数据库的( )。 A)可靠性 B)一致性 C)完整性 D)安全性 4.根据关系数据库规范化理论，关系数据库中的关系要满足第一范式。下面\部门\关系中，因哪个属性而使它不满足第一范式？( ) ? 部门（部门号，部门名，部门成员，部门总经理） A)部门总经理 B)部门成员 C)部门名 D)部门号 5.ER图是数据库设计的工具之一，它一般适用于数据库的( )。 A)概念模型 B)结构模型 C)物理模型 D)逻辑模型 6.数据库三级模式体系结构的划分，有利于保持数据库的( )。 A)独立性 B)完整性 C)安全性 D)集成性 7.数据库系统的体系结构是数据库系统的总体框架，一般来说数据库系统应具有三级模式体系结构，它们是（） A)外模式，模式和内模式 B)子模式，用户模式和存储模式 C)模式，子模式和概念模式 D)子模式，模式和用户模式 8.规范化理论是关系数据库进行逻辑设计的理论依据，依此，关系数据库中的关系必须满足：其每一属性都是（） A)互不相关的 B)不可分解的 C)长度可变的 D)互相关联的 9.单用户数据库管理系统与多用户数据库管理系统之间的最明显的也是最重要的差别：是否支持多个用户（）数据库 A)查询 B)定义 C)修改 D)共享 10.已知教学环境中，一名学生可以选择多门课程，一门课程可能有多名学生选修。说明学生记录型与课程记录型的联系是（） A)一对一 B)一对多 C)多对多 D)未知 11.已知在某公司有多个部门，每个部门又有多名职工，而每位职工只能属于一个部门，则职工与部门之间的关系是（） A)一对一 B)一对多 23 C)多对多 D)未知 12.DBTG使用的是（）模型。 A)关系数据 B)层次数据 C)网状数据 D)E-R模型 13.DBMS是（）。 A)数据库 B)数据库系统 C)数据处理 D)数据库管理系统 14.数据独立性是指（）。 A)数据库的数据依赖于用户的应用程序 B)DBMS和DB相互独立 C)用户应用程序与数据库的数据相互独立 D)用户应用程序与DBMS相互独立 15.数据库中存储（）。 A)数据 B)数据与数据之间的关系 C)信息 D)数据模型的定义 16.数据库系统常用的数据模型有（）三种。 A)网状模型，链状模型和层次模型 B)层次模型，环状模型和关系模型 C)层次模型，网状模型和关系模型 D)层次模型，网状模型和语义模型 17.设有关系R（S，D，M），其函数依赖集F=|S->D，D->M|。则关系至多满足() A） 1NF B） 2NF C） 3NF D） BCNF 19.用二维数据来表示实体之间联系的模型叫做( ) A). 网状模型 B) 层次模型 C) 关系模型 D) 实体--联系模型 20.数据库系统的核心是( ) A). 数据库管理系统 B) 数据库 C) 操作系统 D) 数据 21.构成数据库系统的是数据库,计算机硬件系统,用户和（ ） A) 操作系统 B) 文件系统 C) 数据集合 D) 数据库管理系统 22.设有关系R（A，B，C，D，E），A、B、C、D、E都不可以再分，则R属于（ ） A） 1NF B） 2NF C） 3NF D） 以上三个答案都不对 23.在现实世界中，某种商品的名称对应于计算机世界中的（ ） A） 个体 B） 属决策 C） 数据项 D） 性质 D 24.如果把学生看作实体，某个学生的姓名叫\张三\，则张三应看成（ ） A） 记录型 B） 记录值 C） 属性型 D） 属性值 25.从E-R图导出关系模型时，如果两实体间的联系是m：n的，下列说法中正确的是（A） 将m 方关键字和联系的属性纳入n方的属性中 B） 将n 方关键字和联系的属性纳入m方的属性中 C） 在m方属性和n方属性中均增加一个表示级别的属性 。 24 ）D） 增加一个关系表示联系，其中纳入m放和n方的关键字 D 26.对某个单位来说，正确的是（ ） A） E-R图是唯一的 B） 数据模型是唯一的 C） 数据库文件是唯一的 D） 以上三个都不是唯一的 27.若两个实体间的联系是M：N，则（ ）导入第三个交叉关系 A） 需要 B） 不需要 C） 可有可无 D） 合并两个实体 28.若两个实体间的联系是1：n，则实现1：n的方法是（ ） A． 将\端实体转换的关系中，加入\端实体转换关系的码 B． 将\端实体转换的关系的码，加入到\端的关系中 C． 在两个实体转换的关系中，分别加入另一个关系的码 D． 将两个实体转换成一个关系 29.根据关系数据库规范化理论，关系数据库中的关系要满足第一范式，下面\部门\关系中，因哪个属性使它不满足第一范式（ ） A． 部门经理 B． 部门成员 C． 部门名 D． 部门号 30.在数据库的三级模式结构中描述数据库中全体逻辑结构和特性的是（ ） A． 外模式 B． 内模式 C． 存储模式 D． 模式 31.当前数据库技术的发展已形成各种类型的数据库应用技术，如下所述： Ⅰ.应用的移动 Ⅱ.多种技术与数据库技术相结合 Ⅲ.关系数据库的研究基础 哪些是这种发展的推动力？（ ） A． Ⅰ B． Ⅱ C． Ⅲ D． Ⅰ，Ⅱ和Ⅲ 32.在数据库管理技术发展过程中，文件系统与数据库系统的重要区别是数据库系统具有（ ） A． 数据可共享 B． 数据无冗余 C． 特定的数据模型 D． 专门的数据管理软件 33.在数据库技术中，面向对象数据模型是一种（ ） A． 概念模型 B． 结构模型 C． 物理模型 D． 形象模型 34.以下所列的条目中哪些是数据库管理员的职责？（ ） Ⅰ负责管理企业的数据库资源 Ⅱ收集和确定有关用户的需求 Ⅲ设计和实现数据库并按需要修改和转换数据 Ⅳ为用户提供资料和培训方面的帮助 A． Ⅰ、Ⅱ B． Ⅱ、Ⅲ C． Ⅰ、Ⅳ D． 全部 35.数据库概念设计的ER方法中，用属性描述实体的特征，属性在ER图中，一般使用如下所列的哪种图形表示？（ ） A． 矩形 B． 四边形 C． 菱形 D． 椭圆形 36.从ER模型向关系模型转换，一个N：M的联系转换成一个关系模式时，该关系模式的键是（ ） A． N 端实体的键 B． M 端实体的键 C． N 端实体的键与M 端实体的键组合 D． 重新选取其他属性 37.在数据库设计中用关系模型来表示实体和实体间的联系。关系模型的结构是（ ） 25 GROUP BY Sno HAVING count(*)>3; 3）数据操作 （1）插入：INSERT INTO <表名>（列名） VALUES(列表值) （2）更新：UPDATE <表名> SET 数据项名=更新数据 WHERE <条件> （3） 删除：DELETE FROM <表名> WHERE <条件> [例1] 将一个新学生记录 （学号：95020；姓名：陈冬；性别：男；所在系：IS；年龄：18岁）插入到Student表中。 INSERT INTO Student VALUES ('95020'，'陈冬'，'男'，'IS'，18)； [例1] 将学生95001的年龄改为22岁。 UPDATE Student SET Sage=22 WHERE Sno=' 95001 ' [例2] 将所有学生的年龄增加1岁。 UPDATE Student SET Sage= Sage+1； [例1] 删除学号为95019的学生记录。 DELETE FROM Student WHERE Sno='95019' [例2] 删除计算机科学系所有学生的选课记录。 DELETE FROM SC WHERE sno IN (SELETE distinct sno FROM Student WHERE Sdept=?computer?)； 4）数据控制 （1）授权语句： GRANT <授权内容> ON TABLE <表名> TO <用户名> （2）撤消授权： REVOKE <授权内容> ON TABLE <表名> FROM <用户名> [例1] 把查询Student表权限授给用户U1 GRANT SELECT ON TABLE Student TO U1 [例2] 把对Student表和Course表的全部权限授予用户U2和U3 GRANT ALL PRIVILIGES ON TABLE Student, Course TO U2, U3 [例3] 把用户U4修改学生学号的权限收回 REVOKE UPDATE(Sno) ON TABLE Student FROM U4 36 百度搜索“yundocx”或“云文档网”即可找到本站免费阅读全部范文。收藏本站方便下次阅读，云文档网，提供经典综合文库计算机软件技术基础总复习在线全文阅读。
最新更新：
