计算机软件技术基础总复习
计算机软件技术基础
第二章智能0801班
2.1数据结构概论
一、选择题
1、数据的逻辑结构是（ A ）。
A．数据的组织形式
B．数据的存储形式
C．数据的表示形式
D．数据的实现形式
2、组成数据的基本单位是（ C ）。
A．数据项 B．数据类型 C．数据元素 D．数据变量
3、下面程序的时间复杂度为（）。
x=0；
for（i=1；i for（j=i+1；j<=n；j++） x++； A．O（） B．O（n2） C．O（1） D．O（n） 4、下面程序的时间复杂度为（）。 for（i=0；i for（j=0；j A[i][j]=i*j； A．O（m2） B．O（n2） C．O（m×n） D．O（m+n） 5、下面程序段的执行次数为（）。 for（i=0；i for（j=0；j>i；j++） state； A．n（n+1）/2 B．（n-1）（n+2）/2 C．n（n+1）/2 D．（n-1）（n+2） 6、下面程序的时间复杂度为（A ）。 for（i=0；i for（j=0；j c[i][j]=0； for（i=0；i for（j=0；j for（k=0；k c[i][j]=c[i][j]+a[i][k]*b[k][j]； 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指向的结点插入表中，使之成为第一个结点，其 操作是（ 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） {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； } } 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指示队 尾元素的当前位置，队列的最大容量为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； 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．两者长度均可变 二、填空 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 8、若先序遍历二叉树的结果为结点序列A，B，C，则有（）棵不同的二叉树可以得到这一结果。A．3 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．给出一组数，构造的哈夫曼树的带树路径长度不变。 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 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 h=h->right； p->right=h->right； p->left=h； h->right->left=p； h->rihght=p； } } void buildlisttree（root，l） /*root是指向二叉树根结点的指针，*/ /*l是指向双向循环链表表头结点的指针*/ {l=（struct nodetype *）malloc（sizeof（struct nodetype））； 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、对下列图 它的生成树有（）棵。 三、程序填空题 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计算散列地址进行散列存储，若引用线性探测的开放定地址法解决冲突，则在该散列表上进行查找的平均查找长度为（）。 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%11，表中已有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．快速 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] {temp=R[j-1]； R[j-1]=R[j]； R[j]=temp； 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 high=mid-1 ； 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. 最差适应算法 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. 将来再也不使用的页面淘汰算法 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调入内存时，规定每次只能从外存调入一页，则当前访问后续页面过程中发生的缺 页次数和缺页率为。 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，则在执行该进程过程中发生的缺页次数和缺页率为。 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．特权指令和非特权指令均只供操作系统使用 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操作均用于申请资源 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、操作系统中多个进程并发执行所采用的相互制约方式主要有同步与互斥两种。 软件技术基础试题及答案 软件技术基础 系班级姓名成绩 得分评卷 人一、填空题（每空1分，共25分） 1.数据结构作为一门学科，主要研究数据 的、存储结构以及 三方面内容。 2.当对一个线性表经常进行插入或删除操作时，则 宜采用存储结构；而经常进行的是访问操作，而很少进行插入或删除操作时，则宜采用存储结构。 3.在线性结构中，首结点有个前驱结点， 其余每个结点有且只有个前驱结点。4.限定在表的一端进行插入，在表的另一端进行删 除的线性表称为；限定在表的一端进行插入和删除运算的线性表称为。 5.一个8阶的下三角矩阵B按行优先顺序压缩存储 第2页，共19页 6. 第3页，共19页 7. 8.操作系统通过记载、跟 踪、控制进程的执行，它是进程存在的唯一标志。 作业调度程序是从处于状态的作业中选取一个作业并把它装入主存。 12A.软件生命周期瀑布模型一般可分为问题分析、、、 和软件维护五个阶段。 , 得分评卷 人二、选择题（每小题1分，共10分）下列语句正确的是（）。 A. int *p=&x; B. int *p=x; C. int p=&x; D. int *p=*x; 2. int a[ ]={1,2,3,4,5},b[5],*p; 则下列语句中不 正确的语句是（）。 A. p=b+1; B.p=&a[3]; C. p=a; D.b=a; 3. 设有以下说明语句 struct node{ int a；float b；}；struct node node1,node2,*pnode; 则下列语句中正确是（）。 A. node1=node2； B. 第4页，共19页 软件技术基础模拟试题（第二十次省统考） 一、是非判断题（正确选填A，错误选填B）（每小题1分，共10分） 1、数据元素是数据的基本单位，数据项是数据的最小单位。（） 2、栈是特殊的线性表，须用一组地址连续的存储单元来存储其元素。（） 3、引入虚拟存储技术后，逻辑内存总容量是由地址总线的位置确定的。（） 4、编译程序是一种常用应用软件。（） 5、顺序文件和链接文件的长度都可以动态变化。（） 6、在文件系统中采用目录管理文件。（） 7、允许多用户在其终端上同时交互地使用计算机的操作系统称为实时系统。（） 8、程序、数据、和进程控制块是构成一个进程的三要素。（） 9、黑盒测试时，既要考虑程序的内部逻辑结构又要考虑其外部特性。（） 10、软件的总体设计和详细设计都要用PAD图形工具。（） (参考答案：1~10：ABABB ABABB) 二、单项选择题：（每小题1分，共5分） 1、允许用户把若干作业提交计算机系统集中处理的操作系统称为（）。 A分时操作系统B实时操作系统C网络操作系统D批处理操作系统2、分配到必要资源并获得了处理机时的进程的状态称为（）。 A就绪状态B执行状态C等待状态D阻塞状态 3、利用通道技术可以在（）之间直接交换数据。 A内存与CPU B CPU与外设C内存与外设D内存、CPU和外设三者4、以下的准则中哪个不是软件设计的准则（）。 A编程语言选择准则B信息屏蔽准则 C结构化和模块化准则D抽象准则 5、有一数列：97657613294958经过一趟排序后得到： 65971376294958请问使用的是何种排序方法？（） A简单插入排序B冒泡排序C2路归并排序D快速排序 (参考答案：DBCAC) 软件技术基础模拟试题（第十九次省统考） 一、是非判断题（正确选填A，错误选填B）（每小题1分，共10分） 1、在目前，用于保证软件质量的主要手段是进行软件测试。（） 2、使用DMA方式传送数据期间不需要CPU干预。（） 3、线性顺序队列会产生“假溢出”，而线性循环队列则不会。（） 4、对同一种算法，用高级语言编写的程序比用低级语言编写的程序运行速度快。（） 5、在线性表中，数据的存储方式有顺序和链接两种。（） 6、进程由程序块、文件控件块和数据块三部分组成。（） 7、在面向对象的程序设计中，派生类只能从一个基类产生。（） 8、操作系统是用户和硬件的接口。（） 9、个人计算机中可配置的最大内存容量受地址总线位数的限制。（） 10、软件维护中最困难的问题是软件配置不全。（） (参考答案：1~10：A、A、A、B、A、B、A、A、A、B) 二、单项选择题：（每小题1分，共5分） 《软件技术基础》教学大纲 课程编号：23000840 适用专业：电子信息类（非计算机专业） 学时数： 40 学分数： 2.5 开课学期：第4学期 先修课程：《C语言》 考核方式：笔试（闭卷） 执笔者：沈晓峰编写日期：2015年3月审核人（教学副院长）： 一、课程性质和目标 授课对象：电子信息工程专业大学二年级本科生 课程类别：学科拓展课程 教学目标： 本课程是针对工科电子信息类本科生开设的一门学科拓展课程。着重培养学生在软件设计领域的基本素质，基本方法和设计理念。授课对象为大学二年级学生，课程任务是通过本课程的学习和相关实验的练习，使学生掌握数据结构、操作系统等软件技术的基本理论知识，具有一定的软件开发能力。 二、教学内容和要求 1、课堂理论教学要求和学时安排（32学时） 1）C程序设计（4学时） （1）C语言回顾，指针的基本概念、运算方法和使用（2学时）。 （2）结构体的基本概念和使用方法（2学时）。 2）数据结构（20学时） （1）数据结构的基本概念（2学时）：理解数据结构的基本概念；理解线性和非线性结构的概念。 （2）线性数据结构（9学时）：理解表、栈、队列等线性数据结构的概念，存储方式及基于不同存储方式的相关操作的实现方法。 a.理解表的概念及顺序表的存储特点，掌握其创建、插入、删除等实现方法（2 学时）； b.掌握单链表、双链表、循环链表的创建、插入、删除方法（2学时）； c.理解栈的概念及结构特点，掌握顺序栈及链栈的出栈、入栈操作的实现方法 （2学时）； d．理解队列的概念及特点，掌握顺序、循环队列的创建、出队、入队、判空、判满等操作。掌握链队列的创建及出队、入队（2学时）； e．理解数组的概念及二维数组的存放方式，掌握对称矩阵及稀疏矩阵的压缩存储方法（1学时）。 （3）非线性数据结构（5学时）：了解典型非线性数据结构的基本概念、存储和访问方式。 a．理解二叉树、满二叉树、完全二叉树的概念及基本性质（1学时）； b．掌握二叉树的三种遍历算法、树和二叉树的转换方法（2学时）； c．理解图的基本概念及性质，掌握图的邻接矩阵、邻接图存储方式（2学时）。 （4）结构查找和排序（4学时）：理解查找和排序的基本概念，掌握三种查找（顺序、二分、分块）和三种排序（简单插入，简单选择和冒泡）方法和实现。 3）操作系统（8学时） (1)操作系统的基本概念（2学时）：了解操作系统的基本概念，操作系统发展的历 程和现代操作系统的基本特征。 (2)处理机管理（4学时）；理解进程、进程的状态、描述方式、进程控制的手段， 进程的同步和互斥，进程通信和死锁等基本概念，理解进程调度的相关方法。 (3)作业管理（2学时）：理解作业、作业的状态、描述方式、作业控制的手段，等 基本概念，理解作业调度的相关方法。 通过这一章的学习同学们应该理解一个用户作业提交给计算机之后，操作系统控制计算机来执行该用户作业的基本流程。 2、实验安排（8学时） 共设置5组实验，分为上机实验和课外实验两部分：上机实验包括两个实验，课外实验包括3个实验，详细实验内容见实验教学大纲。 三、考核方式 课程最后成绩构成包括：期末考试卷面成绩（70%），平时成绩（10%），实验成绩（20%）。 实验部分的考核包含上机实验和课外实验，实验成绩采用实验出勤、实验考核、实验报告和实验程序验证相结合的方式给出。 四、教材和参考资料 1、教材 《软件技术基础》，黄迪明，电子科技大学出版社，1998年 2、参考资料 软件技术基础模拟试题（第二十四次省统考） 一、是非判断题（正确选填A，错误选填B）（每小题1分，共10分） 1. 顺序表和线性链表的物理存贮形式都是顺序存贮。( 1 ) 2. 数据类型是某种程序设计语言中已实现的数据结构。( 2 ) 3. 如果通过软件测试没有发现错误，则说明软件是完全正确的。( 3 ) 4. 快速原型模型可以有效地适应用户需求的动态变化。( 4 ) 5. 不同进程之间的动作在时间上不能重叠。( 5 ) 6. 分区式存储管理能够进行存储空间共享。( 6 ) 7. 链接文件和索引文件都可以非连续存放。( 7 ) 8. 中断处理一般分为中断响应和中断处理两个步骤。前者由软件实施，后者主要由硬件实施。( 8 ) 9. 在C++语言中，“重载”表达了最简单的多态性。( 9 ) 10.进程调度根据一定的调度算法，从等待队列中挑选出合适的进程。( 10 ) (参考答案：1~10：ABBAB BABAB ) 二、单项选择题：（每小题1分，共5分） 1. 在数据结构中，一个存储结点存放一个（11 ）。 11 (A) 数据项(B) 数据元素(C) 数据结构(D) 数据类型 2. 把逻辑地址转变为存储的物理地址的过程称作（12 ）。 12 (A) 编译(B) 连接(C) 运行(D) 重定位 3. SPOOLing技术可以实现设备的（13 ）分配。 13 (A) 虚拟(B) 共享(C) 独占(D) 物理 4. 允许用户把若干作业提交计算机系统集中处理的操作系统称为（14 ）。 14 (A) 分时操作系统(B) 实时操作系统 (C) 网络操作系统(D) 批处理操作系统 5. 进程从运行状态进入就绪状态的原因可能是（15 ）。 15 (A) 被选中占有处理机(B) 时间片用完 (C) 等待的事件已发生(D) 等待某一事件 (参考答案：BBADB) 软件技术基础模拟试题（第二十三次省统考） 一、是非判断题（正确选填A，错误选填B）（每小题1分，共10分） 1. 数据在计算机内在中的表示是指数据的存储结构。( 1 ) 2. 能影响中断响应次序的技术是中断优先级和中断屏蔽。( 2 ) 3. 链表可以随机访问任意一个结点，而顺序表则不能。( 3 ) 4. 作业与进程的主要区别是前者是由用户提交，后者是由系统自动生成。( 4 ) 5. Windows、OS/2、Linux微机操作系统都是多用户多任务操作系统。( 5 ) 6. 数据的逻辑结构是从逻辑关系上描述数据，它与数据的存储结构无关，是独立于计算机的。 ( 6 ) 7. 流式文件和记录式文件都以字符为基本单位进行存取。( 7 ) 8. 不定长文件是指字段的长度不固定。( 8 ) 9. 软件工程的三要素包括方法、工具和环境。( 9 ) 10.软件结构是以指令为基础而组成的一种控制层次结构。( 10 ) (参考答案：1~10：AABAB ABBBB) 二、单项选择题：（每小题1分，共5分） 1. 若进栈序列为1,2,3,4，且进栈过程中可以出栈，则不可能出栈的序列是 ( 11 ). 11 (A) 1,4,3,2 (B) 2,3,4,1 (C) 3,1,4,2 (D) 3,4,2,1 软件技术基础复习总结1 第一章数据结构 1、什么是数据结构？ 数据结构是讨论计算机系统中数据的组织形式及其相互关系。 *在计算机系统中数据不仅包含了通常数值的概念，还包括将客观事物采用计算机进行识别，存储和加工所进行的描述。 2、研究数据结构的主要内容： （1）数据元素之间的逻辑关系 （2）选用什么样的存储结构 （3）用算法效率最高的操作 3、数据结构的基本概念： 通常把运用数据结构来描述数据元素之间的逻辑关系，数据在计算机系统中的存储方式和数据的运算抽象成数据结构的三个层次：数据的逻辑结构，数据的存储结构，数据操作集合。 数据逻辑结构：线性结构（有且仅有一个开始数据元素和一个终点数据元素，且所有数据元素仅有一个直接前驱和一个直接后继） 非线性结构（多个直接前驱和后继） 数据的存储方法：顺序存储方法、链接存储法、索引存储法、散列存储法常用的数据处理与运算：遍历、插入、更新、删除、查找、排序。 4、算法的基本概念与算法效率 一个算法必须具备有穷性、确定性，数据输入、信息输出、可行性五项基本特征。 顺序表 线性链表 单向链表 双链表 循环链表 算法效率包括时间效率和空间效率。 程序=算法+数据结构 5、线性结构：线性表、堆栈、队列、数组、串 线性结构特点是数据元素有序并有限。 6、线性表 7、顺序表： 设在顺序表中每个元素占用k 个存储单元，索引号为1的数据元素a1的内存地址为Loc （a1），则索引号为i 的数据元素ai 的内存地址为： Loc （a1）=Loc （a1）+（i+1）*k 存储地址是该元素在表中索引号的线性函数。顺序表的存储结构是一种可 线性表 复习题 一、判断题（每题2分，共30分） 1.螺旋模型是在瀑布模型和增量模型的基础上增加了风险分析 活动。（对） 2.数据字典是对数据流图中的数据流，加工、数据存储、数据的源和终点进行详细定义。（错） 3.JAVA语言编译器是一个CASE工具。（对）。 4.软件是指用程序设计语言（如PASCAL ,C,VISUAL BASIC 等）编写的程序，软件开发实际上就是编写程序代码。（错） 5.软件模块之间的耦合性越弱越好。（对） 6.数据库设计说明书是一个软件配置项（对） 7.在面向对象的软件开发方法中，每个类都存在其相应的对象，类是对象的实例，对象是生成类的模板。（错） 8.过程描述语言可以用于描述软件的系统结构。（错） 9.如果通过软件测试没有发现错误，则说明软件是正确的。（错） 10.快速原型模型可以有效地适应用户需求的动态变化。（对） 11.模块化，信息隐藏，抽象和逐步求精的软件设计原则有助于得到高内聚，低耦合度的软件产品。（对） 12.集成测试主要由用户来完成。（错） 13.确认测试计划应该在可行性研究阶段制定（错） 14.白盒测试无需考虑模块内部的执行过程和程序结构，只要了解模块的功能即可。（错） 15.软件概要设计包括软件系统结构设计以及数据结构和数据库设计。（对） 16.在可行性研究中最难决断和最关键的问题是经济可行性。（╳） 17.耦合是指一个模块内各个元素彼此结合的紧密程度。（╳） 18. 一笔交易、一个动作、甚至操作人员按一个按钮都可以看做是一次事物。（√） 19.概要设计阶段完成的主要文档是概要设计说明书。（√） 20.过大的模块可能是由于分解不充分造成的，即使降低模块独立性也必须继续分解。（╳） 21.程序设计语言中应绝对禁止使用GOTO语句。（╳） 22.类是关于对象性质的描述，由方法和数据组成。（√） 23.随着软件技术的发展，人们逐渐认识到编码不仅要强调效率还要强调清晰。（√） 25.为保证程序的安全，必须做到程序中没有任何错误存在，即容错。（╳） 26.如果把软件开发所需的资源画成一个金字塔，人是最基本的资源。（√） 名词解释 1.数据词典——是描述数据信息的集合，它对数据流图中的各 个元素按规定格式进行详细的描述和确切的解释,是数据流图的补充工具。 2.数据流图——他以图形的方式反映系统的数据流程 3.白盒测试——按照程序内部的结构测试程序，检验程序中的 每条路径是否都能按预定要求正确工作。有两种测试法既逻辑覆盖测试法和路径测试法 4.黑盒测试——按照程序的功能测试程序，检验与程序功能有 关的输入、输出与程序执行是否正确。有四种方法既等价分类法、边界值分析法、错误猜测法和因果图法 5.完善性维护——为了适应用户业务和机构的发展变化而对软 件的功能、性能进行修改、扩充的过程称为完善性维护。因为各种用户的业务和机构在相当长的时期内不可能是一成不变的，所以功能、性能的增加是不可避免的，而且这种维护活动在整个维护工作中所占的比重很大 6.软件可靠性——指在给定的时间内，程序按照规定的条件成 功地运行的概率 7.软件配置——是一个软件在生存周期内，他的各种形式、各 种版本的文档与程序的总称 《操作系统》 选择题： （bs30）1. 分页式存储管理的主要特点是（B）。 (A) 要求作业全部同时装入内存(B) 不要求作业装入到内存的连续区域 (C) 要求扩充外存容量(D) 不要求处理缺页中断 （bs30）2. 进程从运行状态进入就绪状态的原因可能是（D）。 (A) 被选中占有处理机(B) 等待某一事件(C) 等待的事件已发生(D) 时间片用完 （bs30）3. 多道程序设计是指（D）。 (A) 在实时系统中并发运行多个程序(B) 在分布系统工程中同一时刻运行多个程序 (C) 在一台处理机上同一时刻运行多个程序(D) 在一台处理机上并发运行多个程序 （bs29）2. 进程从运行状态进入就绪状态的原因可能是（ A ）。 (A) 时间片用完(B) 等待某一事件(C) 等待的事件已发生(D) 被选中占有处理机（bs29）4. 以下（D）不是实时操作系统的特点。 (A) 高可靠性(B) 及时响应(C) 高效性(D) 通用性 （bs28）3. 任何两个并发进程之间（ A ）。 (A) 可能存在同步或互斥关系(B) 一定存在同步关系 (C) 一定彼此独立无关(D) 一定存在互斥关系 （bs28）4. 以下的哪个特征不是分时操作系统的主要特征（B）。 (A) 分时性(B) 独占性(C) 交互性(D) 多路性 （bs27）2. 以下（D）不是实时操作系统的特点。 (A) 高可靠性(B) 及时响应(C) 中断管理(D) 独立性 （bs27）3. 若当前进程因时间片用完而让出处理机时，该进程应转变为（B）状态。 (A) 运行(B) 就绪(C) 等待(D) 完成 （bs26）3. 在多道程序设计系统中，处于后备状态的作业要经过（D）调度后才能真正执行。 (A) 作业调度(B) 作业调度和设备调度(C) 进程调度(D) 作业调度和进程调度 （bs25）1. 把高级语言的源程序翻译成二进制代码的过程称为：（A）。 (A) 编译(B) 连接(C) 运行(D) 重定位 （bs25）2. 把逻辑地址转变为内存的物理地址的过程称作（D）。 (A) 地址分配(B) 地址连接(C) 地址调用(D) 地址变换 （bs25）4. 在操作系统中，进程最基本的特征是（A）。 (A) 动态性和并发性(B) 顺序性和可再现性 (C) 与程序的对应性(D) 执行过程的封闭性 （bs24）2. 把逻辑地址转变为存储的物理地址的过程称作（D）。 (A) 编译(B) 连接(C) 运行(D) 重定位 （bs24）3. SPOOLing技术可以实现设备的（B）分配。 (A) 虚拟(B) 共享(C) 独占(D) 物理 （bs24）4. 允许用户把若干作业提交计算机系统集中处理的操作系统称为（D）。 (A) 分时操作系统(B) 实时操作系统 (C) 网络操作系统(D) 批处理操作系统 （bs24）5. 进程从运行状态进入就绪状态的原因可能是（B）。 (A) 被选中占有处理机(B) 时间片用完 (C) 等待的事件已发生(D) 等待某一事件 （bs23）2. 任何两个并发进程之间( D) (A) 一定存在互斥关系(B) 一定存在同步关系 (C) 一定彼此独立无关(D) 可能存在同步或互斥关系 线性表的习题 1．下述哪一条是顺序存储结构的优点？ C A．插入运算方便 B．可方便地用于各种逻辑结构的存储表示 C．存储密度大 D．删除运算方便 2．下面关于线性表的叙述中，错误的是：B A．线性表采用顺序存储，必须占用一片连续的存储单元 B．线性表采用顺序存储，便于进行插入和删除操作 C．线性表采用链式存储，不必占用一片连续的存储单元 D．线性表采用链式存储，便于插入和删除操作。 3．某线性表中最常用的操作是在最后一个元素之后插入一个元素和删除第一个元素，则采用_______存储方式最节省运算时间。D A．单链表 B．仅有头指针的单循环链表 C．双链表 D．仅有尾指针的单循环链表 4．链表不具有的特点是：B A．插入、删除不需要移动元素 B．可随机访问任一元素 C．不必事先估计存储空间 D．所需空间与线性长度成正比 5．在n个节点的线性表的数组实现中，算法的时间复杂度是O(1) 的操作是：A A．访问第i个结点和求第i个结点的直接前驱 B．在第i个节点后插入一个新节点 O(n) C．删除第i个节点 O(n) D．以上都不对 6．在一个以h为头的单循环链表中，p指针指向链尾的条件是：A A．p->next==h B．p->next==null C．p->next->next==h D．p->data==-1 7．在非空双向循环链表中q所指的结点前插入一个由p所指的链结点的过程依次为：rlink(p)←q; llink(p)←llink(q);llink(q)←p;___________ A．rlink(q)←p; B．rlink(llink(q))←p; C．rlink(llink(p))←p; 一、填空 1、多媒体的英文是multimedia，Virtual Reality的含义是虚拟现实。 2、Windows95(98)系统中播放声音的软件有：CD播放器、媒体播放机和录音机。 3、文本、声音、图形、图像和动画等信息的载体中的两个或多个的组合构成了多 媒体。 4、图形也称矢量图，是由诸如直线、曲线、圆或曲面等几何图形（称 为图形）形成的从点、线、面到三维空间的黑白或彩色几何图。 5、音频有时也泛称声音，包括语音说明、背景音乐和效果音响。 6、计算机中保存声音文件的格式有多种，常用的有：波形音频文件（WAV）和 数字音频文件（MIDI）。 7、波形音频文件是真实声音数字化后的数据文件。 8、数字音频文件又称乐器数字接口，是以一系列指令来表示声音的，可看成 是声音的符号表示。 9、多媒体系统可分成6个层次：多媒体外围设备、多媒体计算机硬件系 统、多媒体核心系统、媒体制作平台与工具、创作/编辑软件、 应用系统。 10、构建一个多媒体系统，硬件是基础，软件是灵魂。 11、多媒体外围设备包括：音频、视频等多种媒体的输入/输出设备和装置，通 讯（网络）传输设备及装置。 12、多媒体计算机硬件系统，包括多媒体计算机主机系统（MPC）及各种外围设 备的接口部件。 13、多媒体核心系统，其实质就是多媒体操作系统，也包括设备的驱动程序。 14、媒体制作平台与工具，就是多媒体素材准备工具。 15、多媒体编辑与创作系统，该层是开发多媒体应用系统的平台或环境，可以 实现各种媒体的综合利用。 16、多媒体关键技术一般分成二类：多媒体应用所涉及的关键技术、研制多媒 体计算机系统本身要解决的关键技术。 17、研制多媒体计算机系统要解决的关键技术包括：多媒体数据压缩技术、 多媒体专用芯片技术、多媒体输入/输出技术、多媒体存储技术、 多媒体系统软件技术。 18、多媒体应用涉及的关键技术包括：多媒体素材采集/制作技术、多媒体应 用程序开发技术、多媒体创作工具及开发环境、多媒体界面设计与人 机交互技术、多媒体网络通讯技术、虚拟现实技术。 19、目前常用的压缩编码方法分为两类：无损压缩法（或冗余压缩法/熵编码）和有 损压缩法（或熵压缩法）。 20、多媒体通讯是多媒体技术和通讯技术结合的产物，它将计算机的交互 性、通讯的分布性和广播、电视的真实性融为一体。如普通电话到可视电 话。 21、现有的通讯网络包括：电话网、计算机局域网、综合业务数字网、宽 带综合业务数字网、有线电视网等。 计算机基础复习题 基础知识复习题 一、单选题 ( 本大题 25 道小题，每小题 1 分，共 25 分），从下面题目给出的A、B、C、D 四个可供选择的答案中选择一个正确答案。 1._______ 是正确的。C A.ViaVoice是IBM公司推出的较为成熟的中文语音合成系统 B.使计算机具有“听懂”语音的能力，这是语音合成技术 C.使用语音合成技术，计算机便具有了“讲话”的能力，用声音输出结果 D.语音合成技术主要用声音来代替键盘输入和 编辑文字 2.________标记用来标识一个HTML文件中的表格。 D A.〈p〉〈/p〉 B.〈body〉〈/body〉 C.〈html〉〈/html〉 D.〈table〉〈/table〉 3.________类型的图像文件具有动画功能。 C A.JPG B.BMP C.GIF D.TIF 4.________是Photoshop的专用文件格式，支持图层、通道、蒙板、色彩模式等几乎所有的图像信息。 C A.JPG B.BMP C.PSD D.GIF 5.________是利用人类视觉心理特性的编码方法。 D A.空间冗余编码 B.时间冗余编码 C.图像冗余编码 D.视觉冗余编码 6.________为网络中的数据交换建立了规定、标准或约定。 D A.摩尔定律 B.分辨率 C.ISO标准 D.网络协议 7.________为网络中的数据交换建立了规则、标准或约定。 A A.网络协议 B.超媒体 C.传输介质 D.以太网 8._______标准是静态数字图像数据压缩标准。C A．MPEG B．PEG C．JPEG 数据结构习题答案 第一节概论 一、选择题 1．要求同一逻辑结构的所有数据元素具有相同的特性，这意味着( )。 A．数据元素具有同一的特点 *B．不仅数据元素包含的数据项的个数要相同，而且对应数据项的类型要一致 C．每个数据元素都一样 D．数据元素所包含的数据项的个数要相等 2．数据结构是一门研究非数值计算的程序设计问题中计算机的( (1) )以及它们之间的( (2) )和运算的学科。 (1) A．操作对象 B．计算方法 *C．物理存储D．数据映像 (2) A．结构 *B．关系 C．运算 D．算法3．数据结构被形式地定义为(D，R)，其中D是( (1) )的有限集合，R是D上( (2) )的有限集合。 (1) A．算法 *B．数据元素 C．数据操作D．逻辑结构 (2)A．操作 B．映像 C．存储 *D．关系4．在数据结构中，从逻辑上可以把数据结构分为( )。A．动态结构和静态结构 B．紧凑结构和非紧凑结构*C．线性结构和非线性结构 D．部结构和外部结构5．线性表的顺序存储结构是一种( )的存储结构。 *A．随机存取 B．顺序存取 C．索引存取 D．Hash 存取 6．算法分析的目的是( )。 A．找出数据结构的合理性 B．研究算法中的输入和输出的关系 *C．分析算法的效率以求改进 D．分析算法的易懂性和文档性 7．计算机算法指的是( (1) )，它必须具备输入、输出和( (2) )等五个特征。 (1) A．计算方法 B．排序方法 *C．解决某一问题的有限运算序列 D．调度方法 (2) A．可行性、可移植性和可扩充性 *B．可行性、确定性和有穷性 C．确定性，有穷性和稳定性 D．易读性、稳定性和安全性 8．线性表若采用链表存储结构，要求存中可用存储单元的地址( )。 A．必须是连续的 B．部分必须是连续的 C．一定是不连续的 *D．连续不连续都可以 9．在以下的叙述中，正确的是( )。 A．线性表的线性存储结构优于链式存储结构*B．二维数组是它的每个数据元素为一个线性表的线性表 C．栈的操作方式是先进先出 D．队列的操作方式是先进后出 10．根据数据元素之间关系的不同特性，以下四类基本的逻辑结构反映了四类基本的数据组织形式，其中解释错误的是( )。 软件技术基础 系班级姓名成绩得分评卷人 一、填空题（每空1分，共25分） 1.数据结构作为一门学科，主要研究数据的、存储结构以及 三方面内容。 2.当对一个线性表经常进行插入或删除操作时，则宜采用存储结构；而经常进 行的是访问操作，而很少进行插入或删除操作时，则宜采用存储结构。 3.在线性结构中，首结点有个前驱结点，其余每个结点有且只有个前驱结点。 4.限定在表的一端进行插入，在表的另一端进行删除的线性表称为；限定在表 的一端进行插入和删除运算的线性表称为。 5.一个8阶的下三角矩阵B按行优先顺序压缩存储在一维数组中，则数组的大小应设 为。 6.按照二叉树的定义，具有3个结点的二叉树形态有种；具有65个结点的完全二叉 树其深度为; 深度为10的完全二叉树最多有个结点 7.在长度为n的顺序表的第i个位置上插入一个元素，元素的移动次数为；删除 第i个元素时，需要从前向后依次前移个元素。(1≤i≤n+1) 8. 顺序存储结构的循环队列中，设front 和rear分别为队头和队尾指示器，该队列中能存放的 最大元素的个数为M AX-1，则判断队列为满的条件为，而判断队列为空的条件是。 9. 设D={A，B，C，D，E}，R={ 和软件维护五个阶段。 , 得分评卷人 二、选择题（每小题1分，共10分） 1. 已知：int x; 下列语句正确的是（）。 A. int *p=&x; B. int *p=x; C. int p=&x; D. int *p=*x; 2. int a[ ]={1,2,3,4,5},b[5],*p; 则下列语句中不正确的语句是（）。 A. p=b+1; B.p=&a[3]; C. p=a; D.b=a; 3. 设有以下说明语句 struct node{ int a；float b；}； struct node node1,node2,*pnode; 则下列语句中正确是（）。 A. node1=node2； B. pnode.a=10； C. return (node1+node2)； D. scanf(“%d %f”,node1); 4. 线性链表不具有的特点是（）。 A. 可随机访问任一个结点B．不必事先估计所需存储空间大小 C. 插入与删除时不必移动元素D．所需空间与线性表长度成正比 5. 若让元素1，2，3依次进栈，则出栈次序不可能出现（）种情况。 A．3，2，1 B．2，1，3 C．3，1，2 D．1，3，2 6. 有向图的邻接表中，顶点Vi的出度是（）。 A. 依附于Vi的弧数 B.Vi链表中的邻接结点个数 C. Vi在表结点中出现的次数 D. Vi度的一半 7. 某二叉树的先序序列和后序序列正好相反，则该二叉树一定是（）的二叉树。 A．空或只有一个结点B．深度等于其结点数 C．任一分支结点均无左子树D．任一分支结点均无右子树 《软件技术基础》复习题 一、填空题（每空1分，共20分） 1、当今计算机基本都以原理为基础，其五大功能部件为； 2、使用汇编语言（或者高级语言）写出的程序称为；将以上程序翻译成机器语言的程序称为；经过翻译转换后能由计算机直接执行的机器指令程序称为； 3、从计算机系统角度来看，Windows XP属于软件；Office 2003属于软件； 4、数据结构是研究的一门学科；它包括三方面的容：、、； 5、数据在存储器中的存储有四种基本的映像方法，它们是：、、、； 6、对于数据的插入、删除等操作，堆栈式结构遵循的原则，而队式结构遵循的原则； 7、设s[1，…，max]为一个顺序结构栈，变量top指示栈顶位置，栈为空的条件是，栈为满的条件是。 8、具有100个结点的完全二叉树的深度为。 9、有n个叶子结点的哈夫曼树中，总结点数是。 10、3个结点可以构成棵不同形态的树。 11、从资源分配的角度看P.V操作，P操作意味着向系统资源，而V操作意味着向系统资源。 12、设某进程的访问页面走向为1，3，1，2，4，页架数为3，按FIFO页面替换算法，当访问到4号页面时，应淘汰号页面。 13、DBMS就是它是位于和之间的一层管理软件。 14、数据独立性又可分为和。 15、现实世界的事物反映到人的头脑中经过思维加工成数据，这一过程要经过三个领域，它们依次是、和。 16、关系代数运算中，专门的关系运算有、和。 17、一个作业从进入系统到运行结束，一般要经历、、、 4种状态。 18、进程的基本状态是、和。 19、存储分配策略分为、和三种。 20、文件的存取方法有和。 二、单项选择题（每题2分，共20分） 1、算法指的是（） A计算机程序B解决问题的计算方法 C排序方法D解决问题的有限运算序列 2、数据的存储结构包括顺序、、散列和（）4种基本类型 A索引B数组C集合D向量 3、执行下面程序段时，S语句的执行次数为（）。 for(int i=1;i<=n;i++) for(int j=1,j<=i;j++) S; A.n(n-1)/2 B.n(n+1)/2 C.n2/2 D.n 4、在一个长度为n的线性表中，删除值为x的元素时需要比较元素和移动元素的总次数为（）。 A.(n+1)/2 B.n/2 C.n D.n+1 5、一个栈输入序列为1，2，3，4，5，则下列序列中不可能是栈的输出序列是（）。 （A）1 2 3 4 5 （B）5 4 3 2 1 （C）2 3 4 5 1 （D）4 1 2 3 5 6、有64个结点的完全二叉树深度为（） （A）8 （B）7 （C）6 （D）5 7、在有n个结点的二叉链表中，值为非空的域的个数为（）。 （A）n-1 （B）2n-1 （C）n+1 （D）2n+1 8、在操作系统中P.V操作是一种（）。 （A）机器指令（B）系统调用命令 （C）作业控制命令（D）低级进程通信原语 9、把作业地址空间中的逻辑地址变为存中物理地址称为（）。 （A）加载（B）重定位（C）物理化（D）逻辑化10、文件系统使用（）组织文件。 （A）堆栈（B）指针（C）目录（D）路径 11、在操作系统中死锁的出现是因为（）。 (A)计算机系统发生重大故障 1、计算机系统与软件的关系：软件是计算机系统的一部分，体现了计算机应用能力与水平 2、软件的三层含义？个体含义：特指具体的软件；整体含义：个体含义的全体；学科含义：软件理论、 方法与技术所组成的学科。 3、软件特性：抽象性、知识性、复杂性、复用性。 4、软件分类？软件理论：算法理论与数据理论；软件系统：应用软件、支撑软件与系统软件；软件开发： 软件工程。 第二章 5、算法是一类问题过程的一种求解方法，该方法可用一组有序的计算机步骤或过程表示。 6、算法不是程序，算法高于程序。算法是程序的框架与灵魂，而程序是算法的实现。 7、算法的五大特征：能行性、确定性、有穷性、输入、输出。 8、算法的两大基本要素？算法的操作：四种基本操作（算法、逻辑、比较、传输）；算法的控制：三种基 本控制（顺序、选择、循环）。 9、四种常用的算法设计方法？枚举法：穷举所有可能的方法；递归法：自己调用自己的方法；分治法： 将问题分解成若干的方法；回溯法：试探性的求解方法。 10、算法的评价：算法的正确性；算法的时间效率分析；算法的空间效率分析。 11、算法的时间效率分析，用T（n）=O（f（n））表示,常用六种：常用阶O（l）；对数阶O（log2n）；线性阶O（n）；线性对数阶O（n log2n）.；平方阶（立方或K方阶）O（n2），O（n3），O（n k）；指数阶O （2n）。 12、六个完整算法表示：算法名、算法输入、算法输出、算法流程、算法正确性、算法分析 第三章 13、数据是按一定规则组织的符号串，并被识别。 14、数据是由数据结构与数据值组成。 15、数据的三个结构层次？客观世界：事物与事物之间的关联；逻辑世界：数据逻辑结构与逻辑值；物理世界：数据物理结构与物理值。 16、数据元素是命名的数据单位。 17、数据操作：数据操作的总称。 18、数据操作分为？数据值操作：定位、读及增加、删除、修改操作；数据结构操作：创建、删除、查询、修改操作。 19、数据结构：以（狭义）数据结构为核心所构成的数据与数据操纵的结合体，也广义结构。 20、数据的五个特征？时间角度分析：挥发性/持久性数据；使用广度分析：私有/共享数据；数据值性质分析：标量/集合量数据；数据量：大量/小量/海量数据；管理角度分析：严格/松散/不管理数据。 21、数据按特性分类？依赖型数据：不独立，依赖程序的数据；独立型数据：独立的数据组织、数据库数据；半独立数据：属操作系统、文件数据。 22、三类数据的不同使用方式？依赖型数据：程序直接调用；独立型数据：通过外部接口与程序关联；半独立型数据：通过内部接口与程序关联。 第四章 23、数据元素的概念：数据结构中不可以再分的基本数据单位。 24、数据的逻辑结构：从应用问题角度组织数据结构或用户数据视图；主要有线性结构、树和图三种结构。 25、数据的物理结构：数据在计算机存储器上存储结构；主要有顺序和链式存储结构。 26、线性表：数据元素只有后继关系的数据结构；顺序存储结构存储的线性表称为顺序表；链式存储结构存储的线性表称为链表；链表又有单链表、环链表和双向链表等。相关算法主要有插入、删除和查找。27、栈：是限制插入和删除只在同一端进行的线性表，也称为后进先出表；顺序存储结构的栈称为顺序栈；链式存储结构的栈称为链表；相关算法主要有压栈、弹栈和读栈等。 28、队列：是限制插入在一端、删除在另一端进行的线性表；顺序存储结构的队列称为顺序队列；首尾相 1.有一函数Function F(ByVal a As Integer, ByVal b As Integer) As Integer,()在调用时将发生错误。 A.Call F(1, 2) B.Y = F(F(2, 3), 4) C.Z = F(2.3, 5) D.X = F(3) 【参考答案】: D 2.表达式1.5 + 3 \ 2 > 2 Or 7 Mod 3 < 4 的运算结果是()。 A.True B.0 C.1 D.False 【参考答案】: A 3.结构化程序设计所规定的三种基本控制结构是(?)。 A.输入、处理、输出 B.树形、网形、环形 C.顺序、选择、循环 D. 主程序、子程序、函数 【参考答案】: C 4.int(198.555*100+0.5)/100的值()。 A.是198 B.是199.6 C.是198.56 D.是200 【参考答案】: C 5.加载窗体时触发的事件是( )。 A.Click B.Load C.Gotfocus D.DoubleClick 【参考答案】: B 6.下面叙述不正确的是()。 A.一个控件只能有一个事件处理过程 B.用户与应用交互可以触发事 件 C.Visual https://www.wendangku.net/doc/286822026.html, 是集成了事件驱动的编程模型 D.即使用户与应用程序不进行交互，有些事件也可能发生 【参考答案】: A 7.设X=lO,y=7,表达式x\6+y*3的值为()。 A.24 B.22 C.25 D.0 【参考答案】: B 8.鼠标的移动触发()事件。 A.Click B.Mousedown C.MouseUp D.MouseMove 【参考答案】: D 9.在https://www.wendangku.net/doc/286822026.html,窗体第一次显示之前,下列()窗体事件发生。 A.Activated B.GotFocus C.Click D.Load 【参考答案】: D 10.文本框的( )属性用于设置或返回文本框中的文本内容。 A.Text B.(名称) C.Caption https://www.wendangku.net/doc/286822026.html, 【参考答案】: A 11.已知A$="12345678",则表达式Val(Mid(A, 1, 4) + Mid(A, 4, 2))的值为 ()。 A.123456 B.123445 C.8 D.6 【参考答案】: B 12.DrawArc方法绘制的图形是()。 A.圆 B.椭圆 C.弧 D.扇形 【参考答案】: C 《计算机软件技术基础》试题 1.线性表的链式存储结构与顺序存储结构相比优点是 CD 。 A. 所有的操作算法实现简单 B. 便于随机存取 C. 便于插入和删除 D. 便于利用零散的存储器空间 2.线性表是具有n 个 C 的有限序列。 A. 表元素 B. 字符 C. 数据元素 D. 数据项 E. 信息项 3.若长度为n 的线性表采用顺序存储结构，在其第I 个位置插入一个新元素的算法的时间复杂度为 C 。（1≤I ≤n+1） A. O(0) B. O(1) C. O(n) D. O(n 2 ) 4.设A 是一个线性表(a 1,a 2,…,a n )，采用顺序存储结构，则在等概率的前提下，平均每插入一个元素需要移动的元素个数为 B ，平均每删除一个元素需要移动的元素个数为 A ；若元素插在a i 与a i+1之间(0≤I ≤n-1)的概率为 ) 1() (2+-n n i n ，则平均每插入一个 元素所要移动的元素个数为 C ； A. 21 -n B. 2n C. 3 12+n D. 4 13+n 5.下列函数中，按它们在∞→n 时的无穷大阶数，最大的是 D 。 A. log n B. nlog n C. 2n/2 D. n! 6.将下图所示的s所指结点加到p所指的结点之后，其语句应为： D 。 A. s->next=p+1; p->next=s; B. (*p).next=s; (*s).next=(*p).next; C. s->next=p->next; p->next=s->next; D. s->next=p->next; p->next=s; 7.将两个各有n个元素的有序表归并为一个有序表时，其最少的比较次数是 A 。 A. n B. 2n-1 C. n-1 D. 2n 8.下面的程序段是合并两个无头结点链表(ha和 hb)为一个无头结点链表ha的过程，作为参数的两个链表都是按结点的data域由大到小链接的。合并后新链表的结点仍按此方式链接。请填写下述空框，使程序能正确运行。 1. #define NULL 0 typedef struct node{ int data; struct node *next; }node, linklisttype; void combine(linklisttype *ha, linklisttype *hb){ linklisttype *h, *p; h = (linklisttype *)malloc(sizeof(linklisttype)); h->next = NULL; p = h; 一、填空（30分）： 1、二维数组A[10,20]采用以行为主的方式存储，每个元素占一个存储单元，并 且A[1,1]的存储地址是200，则A[6,12]的地址是_______________。 2、线性表、栈和队列都是___________结构，栈的特点是____________，队列 的特点是____________。 3、在一个长度为n的线性表中删除第i个元素(1≤i≤n)时，需向前移动 个元素。 4、对分查找的存储结构仅限于________________，且是______________。 5、在双向链表中，每个结点有两个指针域，一个指向________________，另一 个指向________________。 6、已知一个有向图的邻接矩阵表示，计算第i个结点的入度的方法是 ________________。 7、已知某二叉树的前序遍历序列是“stuwv”，中序遍历序列是“uwtvs”，它的 后序遍历序列是_________________。 8、下列程序段的时间复杂性是_________________。 For i = 1 To n For j = 1 To m A(i,j) = 0 9、以数据集{4，5，6，7，10，12，18}为结点权值所构造的Huffman树的带权 路径长度为____________。 10、n个顶点的连通图至少有条边。 11、数据结构被形式地定义为（D，R），其中D是______________的有限集合，R是D 上____________的有限集合。 12、线性表的逻辑顺序与存储顺序总是一致的，这种说法是否正确，_________。 13、数据结构的存储方式主要有______________和_____________两种它们之间 的本质区别是_______________。 14、栈的操作方式是________________，队列的操行方式是 __________________。 15、数据的逻辑结构包括_____________、________________和______________ 三种类型。 16、在图形结构中，每个结点的前件结点数和后件结点数可以有____________。 17、判定一个队列Q（最多元素为m0）为空队列的条件是________________，为 满队列的条件是________________；判定一个循环队列Q（最多元素为m0）为空队列的条件是________________，为满队列的条件是________________。 18、已知某二叉树的后序遍历序列是“dabec”，中序遍历序列是“debac”，它的 前序遍历序列是_________________。 19、如果对于给定的一组权值，所构造出的二叉树的带权路径长度最小，则称该 树为。 20、向一个长度为n的线性表的第i个元素（1≤i≤n+1）之前插入一个元素时， 需向后移动______________个元素。 21、设栈S和队列Q的初始状态为空，元素a1、a2、a3、a4、a5和a6依次通过 栈S，一个元素出栈后即进入队列Q，若6个元素出队的顺序是a2、a4、a3、a6、a5、a1，则栈的容量至少应该是_______________。 22、二维数组A[10,20]采用以行为主的方式存储，每个元素占一个存储单元，并 且A[1,1]的存储地址是200，则A[6,12]的地址是_______________。软件技术基础试题及答案
软件技术基础模拟试题及参考答案
软件技术基础教学大纲
软件技术基础模拟试题
软件技术基础复习总结1
软件工程基础(复习题及答案)
软件技术基础试题(含答案)
中国石油大学(华东)软件技术基础复习题
多媒体技术基础复习试题(含答案)
计算机基础复习题
计算机软件技术基础课后题答案
软件技术基础试题及答案
软件技术基础复习题集
软件技术基础考试复习题(含答案)
2020年春季考试《计算机软件技术基础(1)》在线考核试题_13.doc
《计算机软件技术基础》试题答案
软件技术基础试题库