合肥工业大学研究报告生软件技术基础总复习题及参考答案

-.z.一、选择题软件技术根底总复习题及参考答案-.z.1、线性表假设是采用链式存储构造时，要求内存中可用存储单元的地址D。A、必须是连续的 B、局部地址必须是连续的C、一定是不连续的 D、连续或不连续都可以2、栈和队列都是B 。A、顺序存贮的线性构造 B、限制存取点的线性构造C、存贮的线性构造 D、限制存取点的非线性构造3、与线性表的存贮不相符合的特性是C 。A、便于插、删运算 B、存贮空间动态分配C、需要连续的存贮空间D、只能顺序查找4、设二叉树的根为第一层，则第i层上的结点数最多有d。i iA、２i iC、２i-１D、２i-15、如将一棵有n个结点的完全二叉树按顺序存放方式存放在下标编号为0,1,…,n-1的一维数组中设*结点下标为k(k>0)则其双亲结点的下标是AA、(k-1)/2B、(k+1)/2C、k/2D、k-16、由权值分别为3,8,6,2,5的叶子结点生成一棵霍夫曼树，它的带权路径长度为A。A、53 B、48C、72 D、247、设I和O分别表示入栈和出栈操作，栈的初态和终态都为空，则以下操作序列合法的有_D__。A、IOIOOIOIB、IOOIOIIOC、IIIOIOIOOD、IIOIIOOO8、二叉树的前序序列为EFHIGJK中序序列为HFIEJKG则二叉树的根为 C A、K B、GC、E D、H9、对有序表{-1,0,1,3,4,6,8,10,12}进展折半查找，则查找12需要比拟的次数为 B 。A、3 B、4C、5 D、610、q结点是pq与p之间插入结点s，则执行D 。A、s→link=p→link;p→link=s;B、p→link=s;s→link=q;C、p→link=s→link;s→link=p;D、q→link=s;s→link=p;11、一个栈的入栈序列为a，b，c，则出栈序列不可能的是C。A、c,b,aB、b,a,c-.z.C、c,a,bD、a,c,b12、如果将一棵有n个结点的完全二叉树按层次遍历次序，存放在下标编号为0,1,…,n-1k(k0则其左孩子结点的下标是 C 。A、2k–1B、2kC、2k+1D、2k+213、用整数5,7,3,6,4作为五个树叶的权值，可以构造一棵带权路径长度值为 C 的霍夫曼树。A、78B、62C、57D、2514、设单链表中结点构造为(data,link)，假设想删除结点*p的直接后继，则应执行以下哪一个操作A。A、p->link=p->link->link;B、p=p->link;p->link=p->link->link;C、p->link=p->link;D、p=p->link->link;15、顺序表是线性表的B。A、链式存储构造B、顺序存储构造C、索引存储构造D、散列存储构造16、假设*线性表中最16、常用的操作是取第i个元素和找第i个元素的前趋元素，则采用A存储方式最节省时间。A、顺序表B、单链表C、双链表D、单循环链表17、当利用大小为ntop==n个栈插入一个元素时，首先应执行B语句修改top指针。A、top++; B、top--; C、top=0; D、top;18、对于任何一棵二叉树T，如果其终端结点数为2的结点为n2.,则AA、n0=n2+1B、n2=n0+1C、n0=2n2+1D、n2=2n0+119、具有35个结点的完全二叉树的深度为A。A、5B、6C、7D、820、在有向图中，所有顶点的入度之和是所有顶点出度之和的B倍。A、0.5B、1C、2D、421、假设用冒泡排序法对序列〔18，14，6，27，8，12，16，52，10，26，47，29，41，24〕从小到大进展排序，共要进展B次比拟。A、33B、45C、70D、9122、对含有B个结点的非空二叉树，采用任何一种遍历方式，其结点访问序列均一样。A、0B、1C、2D、不存在这样的二叉树-.z.23、数据构造是一门研究非数值计算的程序设计问题中计算机的A 以及它们之间的 B 和运算等的学科。①A.数据元素B.计算方法C.逻辑存储D.数据映像②A.构造B.关系C.运算D.算法24、数据构造在计算机内存中的表示是指 A 。A.数据的存储构造B.数据构造C.数据的逻辑构造D.数据元素之间的关系25、在存储数据时，通常不仅要存储各数据元素的值，而且还要存储C 。A.数据的处理方法B.数据元素的类型C.数据元素之间的关系D.数据的存储方法26、在数据构造中，从逻辑上可以把数据构造分成C。A.动态构造和静态构造B.紧凑构造和非紧凑构造C.线性构造和非线性构造D.内部构造和外部构造27、带头结点的单链表head为空的判定条件是B。A.head==NULLB.head->ne*t==NULLC.head->ne*t==headD.head!＝NULL28、在循环双链表的p所指结点之前插入s所指结点的操作是D。A.p->prior=s；s->ne*t=p；p->prior>ne*t=s；s->prior=p->prior；B.p->prior=s；p->prior->ne*t=s；s->ne*t=p；s->prior=p->prior；C.s->ne*t=p；s->prior=p->prior；p->prior=s；p->right->ne*t=s；D.s->ne*t=p；s->prior=p->prior；p->prior>ne*t=s；p->prior=s；29、需要分配较大空间，插入和删除不需要移动元素的线性表，其存储构造是B。A.单链表B.静态链表C.线性链表D.顺序存储构造30、栈和队列的共同点是C。A.都是先进后出B.都是先进先出C.只允许在端点处插入和删除元素D.没有共同点31、向一个栈顶指针为hs的链栈中插入一个s所指结点时，则执行C。A.hs->ne*t=s;B.s->ne*t=hs->ne*t;hs->ne*t=s;C.s->ne*t=hs;hs=s;D.s->ne*t=hs;hs=hs->ne*t;32、判定一个环形队列qu〔最多元素为Ma*Size〕为空的条件是C。A.qu->rear-qu->front==Ma*SizeB.qu->rear-qu->front-l==Ma*SizeC.qu->front==qu->rearD.qu->front==qu->rear+l33、假设用一个大小为6的一维数组来实现环形队列，且当前rear和front的值分别为0和3。当从队列中删除一个元素，再参加两个元素后，rear和front的值分别是B。A.1和5B.2和4C.4和2D.5和134、在一个链队中，假设f和r分别为队头和队尾指针，则删除一个结点的运算是C。A.r=f->ne*t;B.r=r->ne*t;C.f=f->ne*t;D.f=r>ne*t;35、以下图所示二叉树的中序遍历序列是B。A.abcdgefB.dfebagcC.dbaefcgD.defbagc-.z.36、深度为5的二叉树至多有C个结点。A.16 B.32 C.31 D.1037、对一个满二叉树，m个树叶，n个结点，深度为h，则D。A.n=h+m B.h+m=2n C.m=h-1 D.n=2h-138、以下说法正确的选项是 A 。A、链栈没有容量限制B、顺序栈没有容量限制C、链队有容量限制D、单向链表有容量限制39、在一个无向图中，所有顶点的度数之和等于所有边数的 C 倍。A.1/2 B.1 C.2 D.440、对于一个具有n个顶点的无向图，假设采用邻接矩阵表示，则该矩阵的大小是D 。A.n B.(n-1)2 C.n-1 D.n241、一个图如以下图所示，假设从顶点a出发按深度搜索法进展遍历，则可能得到的一种顶点序列为 D 种顶点序列为 B 。①A. a，b，e，c,d，f B.a，c，f，e，b，dC. a，e，b，c，f，d D.a，e，d，f，c，b②A. a，b，c，e，d，f B.a，b，c，e，f，dC. a，e，b，c，f，d D.a，c，f,d，e，b42、顺序查找法适合于存储构造为B的线性表。A.散列存储B.顺序存储或链式存储C.压缩存储D.索引存储43、采用折半查找法查找长度为n的线性表时每个元素的平均查找长度为DA.O(n2)B.O(nlog2n)C.O(n)D.O(log2n)44、对有18个元素的有序表作折半查找，则查找A[3]的比拟序列的下标为D。-.z.A.1、2、3B.9,5、2、3C.9、5、3D.9,4、2、345、有一数列2、3、4、5，按2、3、4、5顺序入队，出队的顺序是 A 。A.2345B.3245C.5342D.243546、在排序方法中，从未排序序列中依次取出元素与已排序序列〔初始时为空〕中的元素进展比拟，将其放入已排序序列的正确位置上的方法，称为C。A.希尔排序B.冒泡排序C.插入排序D.选择排序47、在以下算法中，C算法可能出现以下情况：在最后一趟开场之前，所有的元素都不在其最终的位置上。A.堆排序B.冒泡排序C.插入排序D.快速排序48、在对n个元素进展冒泡排序的过程中最好情况下的时间复杂度为DA.O(1)B.O(log2n)C.O(n2)D.O(n)49、在决定选取何种存储构造时，一般不考虑A。A.各结点的值如何．B.结点个数的多少C.对数据有哪些运算D.所用编程语言实现这种构造是否方便50、通常要求同一逻辑构造中的所有数据元素具有一样的特性这意味着BA.数据元素具有同一特点B.不仅数据元素所包含的数据项的个数要一样而且对应的数据项的类型要一致C.每个数据元素都一样D.数据元素所包含的数据项的个数要相等51、不带头结点的单链表head为空的判定条件是A。A.head==NULLB.head->ne*t==NULLC.head->ne*t＝headD.head!=NULL52、非空的循环单链表head的尾结点〔由p所指向〕满足C。A.p->ne*t==NULLB.p==NULL->ne*t==headD.p==head53、*线性表最常用的操作是在最后一个结点之后插入一个结点或删除第一个结点，故采用D存储方式最节省运算时间。A.单链表B．仅有头结点的单循环链表C.双链表D.仅有尾指针的单循环链表54、如果最常用的操作是取第i个结点及其前驱，则采用D存储方式最节省时间。A.单链表B.双链表C.单循环链表D.顺序表55、设线性表有n个元素，以下算法中，A在顺序表上实现比在链表上实现效率更高。A.输出第i(0<=i<=n-1)个元素值B:交换第0个元素与第1个元素的值C.顺序输出这n个元素的值D.输出与给定值*相等的元素在线性表中的序号56、最不适合用作链栈的链表是D。-.z.A.只有表头指针没有表尾指针的循环双链表B.只有表尾指针没有表头指针的循环双链表C.只有表尾指针没有表头指针的循环单链表D.只有表头指针没有表尾指针的循环单链表57、栈的特点是B，队列的特点是A。A.先进先出B.先进后出58、一个队列的入队序列是1，2，3，4，则队列的输出序列是B。A.4，3，2，1B.1，2，3，4C.1，4，3，2D.3，2，4，159、环形顺序队列中是否可以插入下一个元素，A。A、与队头指针和队尾指针的值有关B.只与队尾指针的值有关，与队头指针的值无关C.只与数组大小有关，与队首指针和队尾指针的值无关D.与曾经进展过多少次插入操作有关60、环形队列用数组front和rear.则当前队列中的元素个数是A。A.(rear-front+Ma*Size)％Ma*SizeB.rear-front+lC.(rear-front-1)％Ma*SizeD.(rear-front)％Ma*Size61、在一个链队中，假设f和r分别为队头和队尾指针，则插入s所指结点的运算是B。A.f->ne*t=s；f=s;B.r->ne*t=s；r=s;C.s->ne*t=r；r=s;D.s->ne*t=f；f=s;62、按照二叉树的定义，具有3个结点的二叉树有C种。A.3B.4C.5D.663、任何一棵二叉树的叶子结点在先序、中序和后序遍历序列中的相对次序A。A.不发生改变B.发生改变C.不能确定D.以上都不对64、一个有n个顶点的无向图最多有C条边。A.nB.n(n-1)C.n(n-1)/2D.2n65、在一个具有n个顶点的无向图中，要连通全部顶点至少需要C条边。A.nB.n+lC.n-1D.n/266、对*个无向图的邻接矩阵来说，A。A．第i行上的非零元素个数和第i列的非零元素个数一定相等B.矩阵中的非零元素个数等于图中的边数C.第i行上，第i列上非零元素总数等于顶点Vi的度数D.矩阵中非全零行的行数等于图中的顶点数67、采用邻接表存储的图的深度优先遍历算法类似于二叉树的A。A.先序遍历B.中序遍历C.后序遍历D.按层遍历68、采用顺序查找法查找长度为nCA.nB.n/2C.(n+1)/2D.(n-1)/269、有一个有序表｛13912241456275778295100当折半查找值82的结点时，C次比拟后查找成功。A.1B.2C.4D.870、在待排序的元素序列根本有序的前提下，效率最高的排序方法是A。-.z.A.插入排序B.选择排序C.快速排序D.归并排序71、排序方法中，从未排序序列中挑选元素，并将其依次放入己排序序列〔初始时为空〕的一端的方法，称为D。A.希尔排序B.归并排序C.直接插入排序D.直接选择排序72、下面程序段的时间复杂度为A。m=0;for(i=1;i<=n;i++)for(j=2*i;j<=n;j++)m=m+1;A．o(n2)Ｂ．o(n3)Ｃ．o(n)Ｄ．o(nlogn)73、线性表采用链式地址时，其地址D。A.必须是连续的B.一定是不连续的C.局部地址必须是连续的D.连续与否均可以74、链表不具有的特点是B。A．插入、删除不需要移动元素B．可随机访问任一元素C．不必事先估计存储空间D．所需空间与线性长度成正比75、有六个元素6，5，4，3，2，1的顺序进栈，问以下C不是合法的出栈序列。A.543612B.453126C.346521D.23415676、*二叉树的后序遍历序列是dabec,中序遍历序列是debac,它的前序遍历是D。A．acbedB．decabC．deabcD．cedba77、一棵具有n个结点的完全二叉树的树高度〔深度〕是A。A．logn+1B．logn+1C．lognD．logn-178、具有12个关键字的有序表，折半查找的平均查找长度为A。A.3.1B.4C.2.5D.579、在一个单链表中，假设删除p所指结点的后续结点，则执行C。A.p->ne*t=p->ne*t;B.p=p->ne*t->ne*t；C.p->ne*t=p->ne*t->ne*t；D.p=p->ne*t;p->ne*t=p->ne*t->ne*t80、在一非空二叉树的中序遍历序列中，根结点的右边A。A．只有右子树上的所有结点Ｂ．只有右子树上的局部结点Ｃ．只有左子树上的局部结点Ｄ．只有左子树上的所有结点81、在一个图中，所有顶点的度数之和等于所有边数的C倍。A．1/2Ｂ．1Ｃ．2Ｄ．482、从逻辑上可以把数据构造分为C两大类。A．动态构造、静态构造B．顺序构造、链式构造C．线性构造、非线性构造D．初等构造、构造型构造83、下面关于线性表的表达中，错误的选项是B。A．线性表采用顺序存储，必须占用一片连续的存储单元B．线性表采用顺序存储，便于进展插入和删除操作C．线性表采用存储，不必占用一片连续的存储单元-.z.D．线性表采用存储，便于插入和删除操作84、有关二叉树以下说法正确的选项是B。A．二叉树的度为2B．一棵二叉树的度可以小于2C．二叉树中至少有一个结点的度为2D．二叉树中任何一个结点的度都为285、以下说法不正确的选项是C。A．图的遍历是从给定的源点出发每一个顶点仅被访问一次B．遍历的根本算法有两种：深度遍历和广度遍历C．图的深度遍历不适用于有向图D．图的深度遍历是一个递归过程86、利用二叉链表存储树，则根结点的右指针是C。A．指向最左孩子B．指向最右孩子C．空D．非空87、下面关于二分查找的表达正确的选项是D。A.表必须有序，表可以顺序方式存储，也可以链表方式存储B.表必须有序且表中数据必须是整型，实型或字符型C.表必须有序，而且只能从小到大排列D.表必须有序，且表只能以顺序方式存储88、以下B不是队列的根本运算。A．从队尾插入一个新元素B.从队列中删除第i个元素C.判断一个队列是否为空D.读取队头元素的值89、在长度为n的顺序表的第i个位置上插入一个元素〔1≤i≤n+1，元素的移动次数为A。A.n–i+1B.n–iC.iD.i–190、将一棵有100个结点的完全二叉树从根这一层开场，每一层从左到右依次对结点进展编号，根结点编号为1，则编号最大的非叶结点的编号为C。A.48B.49 C.50 D.5191、*二叉树结点的中序序列为G、E，则其左子树中结点数目为C。A．3B.2C.4D.592、栈和队列都是B。A、顺序存储的线性构造B、限制存取点的线性构造C、链式存储的线性构造D、限制存取点的非线性构造93、用顺序查找方法查找长度为n的线性表时，在等概率情况下的平均查找长度为D。A、n B、n/2 C、(n-1)/2 D、(n+1)/294、以下有关线性表的表达中，正确的选项是 A 。A、一个线性表是n个数据元素的有限序列B、线性表中任何一个元素有且仅有一个直接前驱C、线性表中任何一个元素有且仅有一个直接后继D、以上说法都不正确95、对线性表进展二分查找时，要求线性表必须 C 。A、以顺序方式存储B、以方式存储C、以顺序方式存储，且数据元素有序-.z.D、以方式存储，且数据方式有序96、一个队列的入列序列是１，２，３，４，则队列的输出序列是 B 。A、4,3,2,1B、1,2,3,4C、1,4,3,2D、3,2,1,497、从一个长度为n的顺序表中删除第i个元素(1≤i≤n)时,需向前移动A个元素。A、n-i B、n-i+1C、n-i-1 D、i98、按照二叉树的定义，具有3个结点的二叉树有 A 种。A、3 B、4 C、5 D、699、一个栈的入栈序列是a,b,c,d,e,则栈的不可能的输出序列是 C 。A、edcba B、decba C、dceab D、abcde100、采用线性链表表示一个向量时，要求占用的存储空间地址 D 。A 必须是连续的B 局部地址必须是连续的C 一定是不连续的D 可连续可不连续101、在一个单链表中假设q结点是p结点的前驱结点假设在q与p之间插入结点s，则执行 D 。s→ne*t=p→ne*t; p→ne*t=s;p→ne*t=s; s→ne*t=q;p→ne*t=s→ne*t; s→ne*t=p;q→ne*t=s; s→ne*t=p;102、下面程序段的时间复杂度为 C 。for(inti=0;i<m;i++)for(intj=0;j<n;j++)a[i][j]=i*j;A O(m2) BO(n2) C O(m*n) D O(m+n)103、数据构造的定义为(D，S)，其中D是 B 的集合。A 算法B数据元素C 数据操作D逻辑构造104、栈的数组表示中，top为栈顶指针，栈空的条件是 A 。A top=0 B top=ma*Size Ctop=ma*Size Dtop=-1105、下面B的时间复杂性最好，即执行时间最短。A.O(n) B.O(logn) C. O(nlogn) D.O(n2)106、深度为k的完全二叉树至多有 A 个结点。A. 2k-1 B. 2k-2 C. 2k-1 D. 2k-2把第7个记录60插入到有序表时，为寻找插入位置需比拟 C 次。A. 1 B. 2 C. 3 D. 4108、折半查找有序〔6153037656870728999假设查找元素37，需依次与表中元素 D 进展比拟。A. 65，15，37 B. 68，30，37 C. 65，15，30 D. 65，15，30，37109、如下图的4棵二叉树中， A 不是完全二叉树。-.z.〔A〕(B) (C) (D)110、计算机算法指的是 C 。A.计算方法B.排序方法C.解决问题的有序序列D.调度方法111、关系数据库是用D实现数据之间的联系的。A.关系B.指针C.表D.公共属性112、逻辑模型独立于B。A.E-R模型B.硬件设备C.DBMSD.操作系统和DBMS、113、鉴定用户身份、设置口令、控制用户存取权限、数据加密等是A采取的措施。A.数据平安性控制B.数据完整性控制C.故障恢复D.并发控制114、数据库应用系统的核心是B。A.数据库文件B.数据库管理系统A.编辑程序D.操作系统115、在数据管理技术开展过程中，文件系统与数据库系统的重要区别是数据库系统具有C。A.数据可共享B.数据无冗余C.特定的数据模型D.专门的数据管理软件116、关系数据库的数据操作语言(DML)主要包括D两类操作。A.删除和插入 B.查询和检索C.统计和修改 D.检索和更新117、数据库的三级体系构造是对C抽象的3个级别。A．存储器 B.数据库系统C.数据 D.数据库管理系统数据库管理系统是C。A.采用了数据库技术的计算机系统B.包括数据库管理人员、计算机软硬件以及数据库的系统C.位于用户与操作系统之间的一层数据管理软件D.包含操作系统在内的数据管理软件系统119、五种根本关系代数运算是C。A.并、差、笛卡尔积、投影、联接B.并、差、笛卡尔积、选择、联接C.并、差、笛卡尔积、投影、选择D.并、差、笛卡尔积、除法、投影120、数据库管理系统通常提供授权功能来控制不同用户访问数据的权限，这主要是为了实现数据库的D。A.可靠性B.一致性C.完整性D.平安性121、数据的完整性为D。A.数据的可靠性B.数据的独立性、可能性-.z.C.数据的一致性D.数据的正确性和相容性122、数据模型的三要素包括数据构造、数据操作和D。A.联系B.正确性 C.一致性 D.完整性约束。123、在数据库设计过程中，画E－R图是在B阶段完成的。A.需求分析B.概念构造设计C.逻辑构造设计 D.数据库物理设计124、以下表达正确的为D。A.主码是一个属性，它能唯一表识一列B.主码是一个属性，它能唯一表识一行C.主码是一个属性或属性集，它能唯一表识一列D.主码是一个属性或属性集，它能唯一表识一行125、有关系R和S，R∩S的运算等价于B。A.S-(R-S)B.R-(R-S)C.(R-S)∪SD.R∪(R-S)126、要保证数据库逻辑数据独立性，需要修改的是C。A.模式 B.模式与内模式的映射 C.模式与外模式的映射 D.内模式127、以下四项中，不属于数据库特点的是C。A.数据共享 B.数据完整性 C.数据冗余很高 D.数据独立性高128、学生社团可以接纳多名学生参加，但每个学生只能参加一个社团，从社团到学生之间的联系类型是D。A.多对多 B.一对一C.多对一 D.一对多129、反映现实世界中实体及实体间联系的信息模型是D。A.关系模型 B.层次模型C.网状模型 D.E-R模型130、对数据库并发操作有可能带来的问题包括A。A.读出"脏数据〞 B.带来数据的冗余 C.未被授权的用户非法存取数据 D.破坏数据独立性131、关系数据模型的三个组成局部中，不包括D。A.完整性规则 B.数据构造C.数据操作 D.并发控制132、 SQL中"DELETEFROM表名〞表示 A。A、从根本表中删除所有元组 B、从根本表中删除所有属性C、从数据库中撤消这个根本表D、从根本表中删除重复元组133、有多名职员，从职员到部门的联系类型是D。A、多对多B、一对一C、多对一D、一对多134、关系笛卡尔积运算记号R×S，D。A、R为关系名，S为属性名 B、R和S均为属性名C、R为属性名，S为关系名 D、R和S均为关系名135、如果有9个不同的实体集，它们之间存在着12个不同的二元联系〔二元联系是指两个实体集之间的联系，其中4个1:1联系，4个1:N联系，4个M:N-.z.联系，则根据ER模型转换成关系模型的规则，这个ER构造转换成的关系模式个数至少为 B。A、9个B、13个C、17个D、21个136、SQL中，聚合函数COUNT〔列名〕用于 C 。A、计算元组个数 B、计算属性的个数C、对一列中的非空值计算个数 D、对一列中的非空值和空值计算个数137、SQL语言通常称为A。A.构造化查询语言 B.构造化控制语言 C.构造化定义语言 D.构造化操纵语言138、SQL中，以下涉及空值的操作，不正确的选项是C。A．AGEISNULLB．AGEISNOTNULLC．AGE=NULLD．NOT(AGEISNULL)139、一个1：n联系可以转换为一个独立的关系模式，关系的码为C。A．实体的码B.各实体码的组合C.n端实体的码D.每个实体的码140、一个关系中的候选关键字B。A．至多一个B．可多个C．必须多个D．至少3个141、有12154个是1:1联系类型，5个是1:N联系类型，6个M:N联系类型，则根据转换规则，这个ER构造转换成的关系模式有B 。A、17个B、18个C、23个D、27个142、设有两个关系R〔A，B〕和S〔B，C，与以下SELECT语句SELECTA，B FROMR WHEREBNOTIN〔SELECTBFROMSWHEREC='C56'；等价的关系代数表达式是C 。A、πA，B〔σC≠C6〔RS〕 B、πA，B〔R6C、R－πA，B〔σC5'〔RS D、R－πA，B〔σC≠5'〔RS143、学生之间的联系类型是D 。A、多对多B、一对一C、多对一D、一对多144、在以下根本表的定义中，数值５表示〔C〕CREATETABLEstudent(Snochar(5)notnull，Snamechar(2))；A、表中有５条记录B、表中有５列C、表中字符串Sno的长度D、表格的大小145、在数据库设计中，将ER图转换成关系数据模型的过程属于B。A、需求分析阶段B、逻辑设计阶段-.z.C、概念设计阶段D、物理设计阶段146、数据独立性是指D。A.数据依赖于程序B.数据库系统C.数据库管理系统D.数据不依赖于程序147、以下说法中，C是正确的。A.外模式、概念模式、内模式都只有一个B.外模式只有一个，概念模式和内模式有多个C.外模式有多个，概念模式和内模式只有一个D.外模式和概念模式有多个，内模式只有一个148、关系数据模型D。A.只能表示实体间一对一的联系B.只能表示实体间一对多的联系C.只能表示实体间多对多的联系D.能表示实体之间的任意联系方式149、关系数据库系统中所使用的数据库构造是D。A.树B.图C.表格D.二维表150、*进程在运行过程中需要等待从磁盘上读入数据，此时该进程的状态是C。A、从就绪变为运行B、从运行变为就绪C、从运行变为阻塞D、从阻塞变为运行151、假设信号量S的初值为2，当前值为-1，则表示有B个等待进程。A、0 B、1C、2 D、3152、为A。A、分时操作系统B、批处理操作系统C、实时操作系统D、多处理机操作系统153、以下的进程状态变化中，C变化是不可能发生的。A、运行→就绪B、运行→等待C、等待→运行D、等待→就绪154、分页式存储管理系统中，地址的构成为C。A、页号B、页内地址C、页号和页内地址D、段号155、下面哪些程序是操作系统的核心程序B。A、调试程序B、进程程序C、图形界面程序D、数学子程序库156、以下储存空间管理方法中，A会产生大量的碎片。A、单一连续储存管理B、可变分区管理C、可重定位分区D、页式存储管理-.z.二、填空题1、将插入限定在表的一端，而删除限定在表的另一端进展的线性表称为队列；允许插入的一端称为队尾。2、折半查找要求待查表为有序表。3、n个记录按其关键字大小递增或递减的次序排列起来的过程称为排序。4、数据的存储构造被分为顺序构造、构造、索引构造、散列构造四种。5、在插入和选择排序中，假设初始数据根本正序，则选择插入排序，假设初始数据根本反序，则最好选择选择排序。6、在一个无向图中，所有顶点的度数之和等于所有边数的２倍。在一个具有n个顶点的无向完全图中，包含有n(n-1)/2条边，在一个具有n个顶点的有向完全图中，包含有n(n-1)条边。7、完全二叉树的第8层有8个结点，则其叶子结点数是68。假设完全二叉树的第7层有10个叶子结点，则整个二叉树的结点数最多是235。8、栈中存取数据的原则后进先出，队列中存取数据的原则先进先出9、没有1个前驱结点；最后一个结点没有后续结点，其余每个结点有且只有1个后续结点。10、结点和数据域。这个断言是正确的。11、向一个长度为n的顺序表中的第i个元素(0<=i<=n-1)之前插入一个元素时，需向后移动 n-i+l 个元素。12、在单链表中，要删除*一指定的结点，必须找到该结点的前驱结点。13、在一个单链表中删除P所指结点时，应执行以下操作：q=p->ne*t；p->data=p->ne*->data；p->ne*t=p->ne*t->ne*t ；ree〔q14、通常元素进栈的操作是先移动栈顶指针，后存入元素。15、一个栈的输入序列是12345，则栈的输出序列12345是可能的。16、在具有nMa*SizeMa*Size-1 个元素。17、现有按中序遍历二叉树的结果为abc,有 5 种不同形态的二叉树可以得到这一遍历结果这些二叉树分别是见图(提示用图画出各种形态)18、有如以下图所示的二叉树，答复以下问题。-.z.〔1〕其中序遍历序列为dgbaechif；〔2〕其先序遍历序列为abdgcethi；〔3〕其后序遍历序列为gdbeihfca；19、如果*二叉树的先序遍历序列为stuwv,中序遍历序列为uwtvs。该二叉树的后序遍历序列wuvts。20、在n个顶点的无向图中，假设边数>n-1，则该图必是连通图。此断言是错误的。21、一个图的邻接矩阵表示法是惟一的，而邻接表表示法是不惟一的。22、在有n个顶点的有向图中，每个顶点的度最大可达2(n-1)。23、图的深度优先搜索序列和广度优先搜索序列不是惟一的。此断言是正确的。24、用折半法查找一个线性表时，该线性表必须具有的特点是顺序存储且有序；而分块查找法要求将待查找的表均匀地分成假设干块且块中诸记录的顺序可以是任意的，但块与块之间有序。25、一个数据构造在计算机中表示〔映像〕称为存储构造。26、在树形构造中，树根结点没有结点，其余每个结点有且只有1个前驱结点；叶子结点没有子〔后续〕结点，其余每个结点的后续结点可以有多个。27、在一个长度为n的顺序表中删除第i个元素(0<=i<=n-1)时，需向前移动n-i+1个元素。28、访问单链表中的结点，必须沿着头结点依次进展。29、数据逻辑构造包括线性构造、树形构造和图形构造三种类型，树形构造和图形构造合称为非线性构造。30、图形构造中，每个结点的前驱结点数和后续结点数可以任意多个。31、在单链表中设置头结点的作用是简化插入、删除算法。32、在双链表中，每个结点有两个指针域，一个指向前驱结点，另一个指向后续结点。33、在一个单链表中的P所指结点之前插入一个s所指结点时，可执行如下操作：〔1〕s->ne*t=p->ne*t；〔2〕p->ne*t=s;〔3〕t=p->data;(4)p->data=s->data；〔5〕s->data=t：34、对于一个具有n结点后插入一个新结点的时间复杂度是-.z.O(1)；在给定值为、的结点后插入一个新结点的时间复杂度是O(n)35、栈和队列的区别仅在于删除运算的不同。36、一个栈的输入序列是12345，则栈的输出序列43512是不可能的。37、设栈采用顺序存储构造，假设i-1个元素进栈，则将第i个元素进栈时，进栈算法的时间复杂度为O(1)。38、设栈S和队列Q的初始状态为空，元素a1，a2，a3，a4,a5，a6,a7和a8依次通过栈S,一个元素出栈后立即进入队列Q。假设8个元素出队列的顺序是a3，a6，a5,a8，a4,S的容量至少应该是多少5〔即至少应该容纳多少个元素〕？39、从概念上讲，树与二叉树是两种不同的数据构造，将树转化为二叉树的根本目的是使树可采用二叉树的存储构造并利用二叉树的已有算法解决树的有关问题。40、no,度为2的结点的个数为n2,则有n0=n2+1。41、在无向图G的邻接矩阵A中，假设A[i][j]等于1,则A[j][i]等于1。42、3个顶点的连通图至少2条边。43、具有10个顶点的无向图，边的总数最多为45。44、己知一个图的邻接矩阵表示，删除所有从第i个结点出发的边的方法是将矩阵第i行全部置为0。45、在分块查找方法中，首先查找索引表，然后再查找相应的块表。46、对于双向链表在两个结点之间插入一个新结点需修改的指针共4个，单链表为2个。47、带头结点的双循环链表 L 中只有一个元素结点的条件是L->ne*t->ne*t==L。48、链队列的头尾指针分别是f和r，则将值*入队的操作序列是〔r->ne*t=s;r=s。49、二叉树中叶子数为40，仅有一个孩子的结点数为20，则总结点数为(99)。50、N个顶点的连通图用邻接矩阵表示时,该矩阵至少有2〔N-1〕个非零元素。51、在有向图的邻接矩阵表示中，计算第i个顶点入度的方法是第i列非零元素个数。52、在有序表A[1..12]中，采用二分查找算法查等于A[12]的元素，所比拟的元素下标依次为6,9,11,12_。53、监视哨的作用是免去查找过程中每一步都要检测整个表是否查找完毕，提高了查找效率。54、设*二叉树的前序和中序序列均为ABCDE，则它的后序序列是EDCBA55、存储的特点是利用_指针来表示数据元素之间的逻辑关系。56、带头结点的双循环链表L为空表的条件是：_L->ne*t==L&&L->prior==L。57、对带有头结点的链队lq，判定队列中只有一个数据元素的条件是-.z.1q->front->ne*t=lq->rear。58、设高度为h的二又树只有度为O和2的结点，则此类二叉树的结点数至少为〔2h-1，至多为〔2n-1。59、在图G的邻接表表示中，每个顶点邻接表中所含的结点数，对于无向图来说等于该顶点的度；对于有向图来说等于该顶点的_出度。60、在有序表A[1..20]中，按二分查找方法进展查找，查找长度为5的元素个数是 5 。61、Huffman树的根结点权值为30。62、当待排数据本身已排好序时，快速排序算法的时间复杂性最差63、n(n>0)个结点构成的二叉树，假设二叉树有m个叶结点，则度为2的结点有m-1个。64、直接插入排序，起泡排序和快速排序三种方法中，快速排序所需的平均执行时间最小。65、假设对序列〔7，3，1，8，6，2，4，5〕按从小到大排序，请写出冒泡排序的第一趟结果31762458。66、栈的特点是先进后出，队列的特点是后进先出。67、在一棵完全二叉树中，假设编号为i的结点有右孩子，则该右孩子结点的编号为2i+1。68、8个数据元素〔34764182654926按照依次插入结点的方法生成一棵二叉排序树，则该树的深度为5。69、在二叉树的第i层上至多有2i-1结点70、数据的存储构造被分为顺序构造、构造、索引构造、散列构造四种。71、线性构造反映结点间的逻辑关系是一对一的，图中的数据元素之间的关系是多对多的，树形构造中数据元素间的关系是一对多的。72、栈、队列逻辑上都是线性存储构造。73、在一个无向图中，所有顶点的度数之和等于所有边数的２倍。在一个具有n个顶点的无向完全图中，包含有n(n-1)/2条边，在一个具有n个顶点的有向完全图中，包含有n(n-1)条边。74、在插入和选择排序中，假设初始数据根本正序，则选择插入排序，假设初始数据根本反序，则最好选择选择排序。75、35假定一组记录的排序码〔４６７９５６３８４００对其进展归并排序的过程中第二趟排序后的结果是［３８４６５６７９］［４０８０］。76、实体完整性要求主属性不能取空值，这一点可以通过定义主码来保证。-.z.77、关系模型的根本数据构造是，其数据库存储时的基-.z.本组织方式是文件。-.z.78、实体完整性规则是对的约束。79、关系代数的理论根底是主码_的约束参照完整性规则是对外码集合论〔或集合代数〕_ 。-.z.80、。81、数据库是长期存储在计算机内、有组织的、可_共享_的数据集合。82、**键字是系编号。83、SQL语言提供数据库定义、数据操纵_ 、数据控制等功能。-.z.84、数据库保护问题包括：多方面。平安性保护、完整性、故障恢复和并发控制等-.z.85、关系代数中专门的关系运算包括：选择、投影、连接和除法。86、假设关系中的*一属性组〔或单个属性〕的值能惟一标识一个元组，则称该属性-.z.组〔或属性〕为候选码。-.z.87、数据库的完整性是指数据的正确性和相容性。88、在关系数据模型中，两个关系R1与R2之间存在1∶M的联系，可以通过-.z.在一个关系R2中的中检索相对应的记录。外部关键字值在相关联的另一个关系R1-.z.89、数据库的逻辑模型设计阶段，任务是将E-R模型转换成关系模型。-.z.90、关系中主码的取值必须唯一且非空，这条规则是实体整性规则91、在关系代数中，交操作可由差操作组合而成。92、设一个关系A具有a1个属性和a2个元组关系B具有b1个属性和b2个元组，则关系A×B具有 a1+b1 个属性和 a2*b2 个元组。93、关系的完整性包括实体、参照和用户定义三个方面的完整性94、数据库系统的三级模式构造由外模式、概念模式和内模式组成。95、关系中主码的取值必须唯一且非空，这条规则是实体完整性规则。96、构成数据模型的三大要素是数据构造数据操作和数据完整性约束97、专门的关系运算包括选择、投影、连接和除四种。-.z.三、简答题1、简述一个算法具有哪些重要特性？参考答案：有穷性：执行有穷步后完毕；确定性：具有一条惟一的执行路径；可行性：算法实施后能得到预期的解；输入：有零个或多个输入；输出：应有一个或多个输出。2、简述算法设计有哪些要求？参考答案：正确性：能满足具体问题的需求；可读性：利于理解；强健性：对非法输入也能作出适当反响；效率高与低在存储量需求：执行时间短，最大存储空间要求低3、在一般的顺序队列中，什么是假溢出？怎样解决假溢出问题？参考答案：当队尾到达数组最后一个单元时，就认为队满，但此时数组前面可能还有空单元，因此叫假溢出；解决的方法是采用循环队列，即令最后一个单元的后继是第一个单元。4、线性构造与非线性构造有何差异？参考答案：线性构造的前驱与后继之间为一对一关系，非线性构造的前驱与后继之间通常为一对多或多对多关系。5、何时选用顺序表、何时选用链表作为线性表的存储构造为宜"参考答案：1)从空间上来看，当线性表的长度变化较大、难以估计其规模时，选用动态的链表作为存储构造比拟适宜，但链表除了需要设置数据域外，还要额外设置指针域，因此当线性表长度变化不大、易于事先确定规模时，为了节约存储空间，宜采用顺序存储构造。-.z.2)从时间上看，假设线性表的操作主要是查找，很少进展插入和删除操作时，应选用顺序表。对于频繁进展插入和删除操作的线性表，宜采用链表作为存储构造。6、说明在图的遍历中，设置访问标志数组的作用。参考答案：图中结点可能有多个前驱设置访问标志数组主要是为了防止重复访问同一个结点7、简述顺序表和链表存储方式的特点。参考答案：顺序表的优点是可以随机访问数据元素；缺点是大小固定，不利于增减结点〔增减操作需要移动元素。链表的优点是采用指针方式增减结点，非常方便〔只需要改变指针指向，不移动结点。其缺点是不能进展随机访问，只能顺序访问；另外，每个结点上增加指针域，造成额外存储空间增大。8、设教学数据库中，有两个根本表：学生表：S〔S#，SNAME，AGE，SE*〕学习表：SC〔S#，C#，GRADE〕现有一个SQL语句：SELECTSE*，AGE，AVG〔GRADE〕 FROMS，SC WHERES.S#=SC.S# GROUPBYSE*，AGE ORDERBY3DESC；试写出与此语句等价的汉语查询语句。参考答案：检索每一性别每一年龄的学生的平均成绩；显示时，按平均成绩降序排列。9、设教学数据库中，有两个根本表：学生表：S〔S#，SNAME，AGE，SE*〕学习表：SC〔S#，C#，GRADE〕现有一个SQL语句：SELECTS# FROMS WHERES#NOTIN〔SELECTS#-.z.FROMSCWHEREC#IN〔'C2','C4'〕〕；试写出与此语句等价的汉语查询语句。参考答案：查询语句为：检索至少不选修编号为C2和C4课程的学生**。检索………学生**至少不选修编号为C2和C4课程10、什么是实体完整性？怎样实现实体完整性？参考答案：实体完整性是关系模型必须满足的完整性约束条件之一。设属性A是根本表R的主码组成成份〔主属性，则属性A不能取空值，实体完整性是针对根本表的。通过实体完整性规则来约束：即关系的主码不能取空值。11、解释下面术语a.实体b.属性c.实体集d.数据库参考答案：实体：是指一个存在的物体以区别这个物体所具有的属性和这个物体与其他物体的联系。在表中为一行。属性：是相对实体而言的，是实体所具有的特性。在表中为一列。实体集：由一组相关实体组成的表。数据库：存储在计算机中的有组织的数据集合。12、请画出数据库系统的3级模式构造图。参考答案：-.z.应用应用A1应用En应用C2外模式/模式映像模式/内模式映像内模式……数据库应用B应用D13、简述关系数据库系统采用三级模式和两级映象体系构造的主要作用是什么？参考答案：数据库系统采用"三级模式和两级映射〞保证了数据库中的数据具有较高的逻辑独立性和物理独立性。其优点是当数据的逻辑构造变了，用户程序可以不变；当数据的物理构造改变了，应用程序也可以不变。14、进展数据库系统需求分析时，数据字典的内容和作用是什么"参考答案：数据字典是各类数据描述的集合，通常包括数据项、数据构造、数据流、数据存储和处理过程5个局部。数据字典有助于数据的管理和控制，为设计人员和数据库管理员在数据库设计、实现和运行阶段控制有关数据提供依据。15、简述数据模型的三个组成局部和参照完整性规则。参考答案：数据模型通常由数据构造、数据操作、完整性约束三局部组成。参照完整性规则：假设属性(或属性组)F是关系R的外码，它与关系S的主码相对应(关系R和S不一定是不同的关系)，则对于R中的每个元组在F上的值必须为：取空值(F的每个属性值均为空值)或者等于S中*个元组的主码值16、数据库设计分哪几个阶段？参考答案：物理设计，数据库实施，数据库运行和维护。-.z.17、简述关系的数据完整性规则参考答案:关系的数据完整性规则。它是对关系的一些限制和规定。它包括实体完整性、参照完整性和用户定义完整性。实体完整性：这条规定的现实意义是，关系模型对应的是现实世界的数据实体，而关键字是实体惟一性的表现，没有关键字就没有实体，所有关键字不能是空值。这是实体存在的最根本的前提，所以称之为实体完整性。参照完整性：参照完整性规则也可称为引用完整性规则。这条规则是对关系外部关键字的规定，要求外部关键字的取值必须是客观存在的，即不允许在一个关系中引用另一个关系不存在的元组。用户定义完整性：由用户根据实防情况，对数据库中数据的内容所作的规定称为用户定义的完整性规则。通过这些限制数据库中承受符合完整性约束条件的数据值，不承受违反约束条件的数据，从而保证数据库的数据合理可靠。18、简述数据独立性包括的内容及其内涵.参考答案:数据独立性是数据库领域的一个常用术语，包括数据的物理独立性和数据的逻辑独立性。数据的物理独立性是指用户的应用程序与存储在磁盘上的数据库中的数据是相互独立的，也就是说，当数据的物理存储构造改变时，应用程序不用改变。数据的逻辑独立性是指用户的应用程序与数据库的逻辑构造是相互独立的，也就是说，数据的逻辑构造改变了，用户程序也可以不变。19、请简述进程调度中的优先级调度策略参考答案：是指每个进程赋予一个优先级，根据优先级上下来分配CPU。静态优先级：进程创立后得到的优先级保持不变；动态优先级：系统根据需要可动态改变进程的优先级20、进程有哪些根本状态？它们的变化关系是怎样的？参考答案：进程有3种根本状态，一个进程在任何时刻总是处于其中的一种状态。为了便于管理，根据进程在执行过程中不同时刻的状态，可归结为以下3种根本状态：〔1)等待状态，等待*个事件的完成；-.z.〔2〕就绪状态，等待系统分配处理器以便运行；〔3)运行状态，占有处理器正在运行。进程在执行过程中不断发生变化，每个进程在执行过程中的任意时刻总是处于上述3种状态之一。进程状态的变化情况如下。〔1〕运行状态>等待状态。一个进程运行中启动了外围设备，它就变成等待外围设备传输信息的状态；进程在运行中申请资源〔主存储空间及外围设备〕得不到满足时变成等待资源状态；进程在运行中出现了故障〔程序出错或主存储器读写错等〕时变成等待干预状态。等待等待的资源能得到满足〔另一个进程归还了资源则等待资源者就完毕等待；故障排除后让等待干预的进程完毕等待；任何一个完毕等待的进程必须先变成就绪状态，待分配到处理器后才能运行。(3)运行状态>就绪状态。进程完成了一个使用处理器的时间后，强迫进程暂时让出处理器；当有更高优先权的进程要运行时，也迫使正在运行的进程让出处理器；由于自身或外界原因成为就绪状态的进程让出处理器时，它的状态就变成就绪状态。(4)就绪状态>运行状态。对等待分配处理器的进程，系统按一种选定的策略从处于就绪状态的进程中选择一个进程，让它占用处理器，这个被选定的进程就变成了运行状态。21、n个用户进程中,处于运行态的进程最多有几个"处于等待态的进程最多有几个"为什么"参考答案：在单机多用户环境的n个用户进程中,处于运行态的进程最多有1个。因为处理机只有一个。处于等待状态的进程最多有n个。因为有可能n不一样。22、常用的进程调度算法有哪些？参考答案：先来先效劳；短进程优先；优先级调度策略；时间片轮转法；多队列调度和多重时间片队列调度23、简述操作系统的主要特点和主要功能。-.z.参考答案：特点：并发性共享性虚拟性功能：处理器管理存储器管理作业管理设备管理文件管理24、比拟进程与程序的异同。参考答案：程序是静态的，而进程是动态的。的存在是永久的，而进程的存在是暂时的，它动态地产生和消亡。一个进程可以执行一个或几个程序，一个程序亦可以构成多个进程。-.z.四、综合题1、以下为单链表的删除运算，请分析算法voiddelete_lklist(lklisthead,inti){p=find_lklist(head,i-1);if((p!=NULL)&&(p->ne*t!=NULL) )//①{q= p->ne*t;p->ne*t=p->ne*t;free(q);}elseerror("不存在第i个结点〞)}〔1〕请在处填上正确的语句；〔2〕解释①处语句的含义。参考答案：〔1〕见上；〔2〕判断第i-1个和第i个结点是否为空。2、一棵二叉树的前序遍历的结果是ABECDFGHIJ,中序遍历的结果是EBCDAFHIGJ,试画出这棵二叉树，并给出这棵二叉树的后序遍历序列。参考答案：根据前序序列和中序序列能得到唯一的二叉树，所得二叉树如图：ABFGDH J这棵二叉树的后序遍历序列为：EDCBIHJGFAI3、首先将如以下图所示的无向图给出其存储构造的邻接链表表