青岛理工大学软件应用基础期末复习题及参考答案

一、选择题1.下列正确的标识符是（）。A.-a1B.a[i]C.a2_iD.intt2.在带有头结点的单链表HL中，要向表头插入一个由指针p指向的结点，则执行()。A.p->next=HL->next;HL->next=p;B.p->next=HL;HL=p;C.p->next=HL;p=HL;D.HL=p;p->next=HL;3.以下哪一个不是栈的基本运算？（）A．从栈顶插入一个新元素B．从栈底删除一个元素C．判断一个栈是否为空D．读取栈顶元素的值4.根据二叉树的定义可知二叉树共有（）种不同的形态。A.4 B.5 C.6 D.75.对一个算法的评价，不包括如下（）方面的内容。A．健壮性和可读性B．并行性C．正确性D．时空复杂度6.分别以下列序列构造二叉排序树，与用其它三个序列所构造的结果不同的是（）。A.{100，80，90，60，120，110，130} B.{100，120，110，130，80，60，90}C.{100，60，80，90，120，110，130} D.{100，80，60，90，120，130，110}7.假设系统中所有进程是同时到达，则使进程平均周转时间最短的是（）调度算法。A.先来先服务 B.短进程优先 C.时间片轮转 D.优先级8.设属性A是关系R的主属性，则属性A不能取空值（NULL）。这是（）A.实体完整性规则 B.参照完整性规则C.用户定义完整性规则 D.域完整性规则9.关于DNS下列叙述错误的是（）。A.子节点能识别父节点的IP地址 B.DNS采用客户服务器工作模式C.域名的命名原则是采用层次结构的命名树 D.域名不能反映计算机所在的物理地址10.以下哪个不是Spark的组件。A.SparkStreaming B.Mlib C.Graphx D.SparkR11.若有以下说明语句：structdate{intyear;intmonth;intday;}brithday;则下面的叙述不正确的是（）。A.struct是声明结构体类型时用的关键字B.structdate是用户定义的结构体类型名C.brithday是用户定义的结构体类型名D.year,day都是结构体成员名12.下面关于线性表的叙述错误的是（）。A.线性表采用顺序存储必须占用一片连续的存储空间 B.线性表采用链式存储不必占用一片连续的存储空间C.线性表采用链式存储便于插入和删除操作的实现13.设循环队列中数组的下标范围是0～m-1，其中头尾指针分别是front和rear，则其元素个数是（）。A．rear-frontB．rear-front+1C．(rear-front)MODm+1D．(rear-front+m)MODm14.设n个元素进栈序列是1、2、3、…、n，其输出序列是p1、p2、…、pn，若p1=3，则p2的值为（）。A.一定是2 B.一定是1 C.不可能是1 D.以上都不对15.设某棵二叉树中只有度数为0和度数为2的结点且度数为0的结点数为n，则这棵二叉中共有（）个结点。A.2n B.n+l C.2n-1 D.2n+l16.设二叉排序树中有n个结点，则在二叉排序树的平均平均查找长度为（）。A.O(1) B.O(log2n) C.O(nlog2n) D.O(n2)17.下列关键字序列中（）是堆。A.16,72,31,23,94,53 B.94,23,31,72,16,53C.16,53,23,94，31,72 D.16,23,53,31,94,7218.某系统中有3个并发进程都需要4个同类资源，则该系统必然不会发生死锁的最少资源是（）。A.9 B.10 C.11 D.1219.SELECT语句中，实现投影操作的是（）子句。A.Select B.from C.Where D.groupby20.路由选择是（）的功能。A.网络层 B.传输层 C.应用层 D.数据链路层二、填空题1.软件的发展历史大致分为3个阶段：软件技术发展早期、_____________、______________。2.软件定义：软件=________+________+________。3.队列的插入操作是在队列的_______进行，删除操作是在队列的__________进行。4.用具有n个元素的一维数组存储一个循环队列，则其队首指针总是指向队首元素的___________，该循环队列的最大长度为__________。5.在一个具有n个顶点的无向完全图中，包含有________条边，在一个具有n个顶点的有向完全图中，包含有________条边。6.二叉树是指度为2的____________树。一棵结点数为N的二叉树，其所有结点的度的总和是____________。7.设要将序列（Q,H,C,Y,P,A,M,S,R,D,F,X）中的关键码按字母序的升序重新排列，则：起泡排序一趟扫描的结果是____________。8.在哈希函数H（key）=key%p中，p值最好取____________。9.若对查找表只做“查询某个特定的数据元素是否在查找表中”和“查询某个特定的数据元素的各种属性”操作，则称此类查找表为___________。若在查找过程中同时插入查找表中不存在的数据元素，或者从查找表中删除已存在的某个数据元素，则称此类查找表为___________。10.在哈希存储中，装填因子的值越大，则___________；装填因子的值越小，则___________。11.软件定义：软件=________+________+________。12.后缀算式923+-102/-的值为__________。中缀算式（3+4X）-2Y/3对应的后缀算式为_______________________________。13.在一个具有n个顶点的无向完全图中，包含有________条边，在一个具有n个顶点的有向完全图中，包含有________条边。14.设要将序列（Q,H,C,Y,P,A,M,S,R,D,F,X）中的关键码按字母序的升序重新排列，则：起泡排序一趟扫描的结果是。15.在哈希存储中，装填因子的值越大，则；装填因子的值越小，则。16.实时系统的进程调度，通常采用_______________算法。17.设属性A是关系R的主属性，则属性A不能取空值（NULL）。这是_________完整性规则。18.在实际使用的IP地址中，主机号不能为全“0”和全“1”，那么一个C类IP地址最多能容纳的主机数目为__________。19.软件工程学的三个要素是__________、__________和__________。20.HBase依靠_________保存底层数据。三、综合应用题1.软件的生命周期包括哪些阶段。2.设某商业集团关于商店销售商品的数据库中有三个基本表：商店SHOP（S#，SNAME，AREA，MGR_NAME）其属性是商店编号，商店名称，区域名，经理姓名。销售SALE（S#，G#，QUANTITY）其属性是商店编号，商品编号，销售数量。商品GOODS（G#，GNAME，PRICE）其属性是商品编号，商品名称，单价。（1）试写出下列查询的关系代数表达式、元组表达式和关系逻辑规则：检索销售“冰箱”的商店的编号和商店名称。（2）试写出上面第(1)问的SELECT语句表达形式。（3）试写出下列操作的SQL语句：从SALE表中，把“开开商店”中销售单价高于1000元的商品的销售元组全部删除。（4）写一个断言，要求区域名为“EAST”的商店里销售商品的单价不能低于100元。（5）试写出下列操作的SQL语句：统计区域名为“EAST”的所有商店销售的每一种商品的总数量和总价值。要求显示（G#，GNAME，SUM_QUANTITY，SUM_VALUE），其属性为商品编号、商品名称、销售数量、销售价值。3.在一个段式存储管理系统中，其段表见表1。试求表2中的逻辑地址所对应的物理地址。表1段表表2逻辑地址段号内存起始地址段长02105001235020210090313505904193895段号段内位移04301102500340041125324.给出关键字序列{4,5,1,2,8,6,7,3,10,9}的直接插入排序过程。5.设完全二叉树的顺序存储结构中存储数据ABCDE，要求给出该二叉树的链式存储结构并给出该二叉树的前序、中序和后序遍历序列。6.#include<stdio.h>main(){inti,a[10];for(i=9;i>=0;i--)a[i]=10-i;printf(“%d%d%d”,a[2],a[5],a[8]);}运行结果为：7.#include<stdio.h>main(){chars[]=”abcdefg”;char*p;p=s;printf(“ch=%c\n”,*(p+5));}运行结果为：8.设哈希（Hash）表的地址范围为0～17，哈希函数为：H（K）＝KMOD16。K为关键字，用线性探测法再散列法处理冲突，输入关键字序列：（10，24，32，17，31，30，46，47，40，63，49）造出Hash表，试回答下列问题：（1）画出哈希表的示意图；（2）若查找关键字63，需要依次与哪些关键字进行比较？（3）若查找关键字60，需要依次与哪些关键字比较？（4）假定每个关键字的查找概率相等，求查找成功时的平均查找长度。9.某博物馆最多可容纳500人同时参观，有一个出入口，该出入口一次仅允许一个人通过。参观者的活动描述如下：cobegin参观者进程i:{...进门；...参观；...出门； ...}coend请添加的必要的信号量P、V（或wait()、signal()）操作，以实现上述过程中的互斥与同步。要求写出完整的过程，说明信号量的含义并赋初值。四、编程题1.试写一个判别给定二叉树是否为二叉排序树的算法，设此二叉树以二叉链表作存储结构。且树中结点的关键字均不同。2.假设一个无向图是非连通的，采用邻接表作为存储结构，试设计一个算法，输出图中各连通分量的节点序列。3.已知在两个链表A、B中均不存在相同元素，设计算法求出由仅在A中出现而不再B中出现的元素组成的链表。《软件技术基础》专业综合课试卷B卷答案及评分标准选择题（每题1分，共10分）1-5CABBB6-10CBAAD11-15.CADCC16-20.BDBAA填空题（每题1分，共10分）1.面向对象技术和结构化程序发展时期软件工程技术发展新时期2.程序数据文档3.尾首4.前一个位置；n-15.n(n-1)/2n(n-1)6.有序n-17.HCQPAMSRDFXY8.小于等于表长的质数（素数）9..静态查找表动态查找表10.存取元素时发生冲突的可能性就越大存取元素时发生冲突的可能性就越小11..程序数据文档12.-134X*+2Y*3/-13.n(n-1)/2n(n-1)14.HCQPAMSRDFXY15.存取元素时发生冲突的可能性就越大存取元素时发生冲突的可能性就越小16.抢占式的优先级高者优先17.实体18.25419..方法工具过程 20.HDFS综合应用题（每题10分，共60分）1.［答案］问题定义、可行性分析、概念设计、详细设计、编码、调试和测试、验收与运行、维护升级到废弃。2.［答案］(1)关系代数表达式：πS#，SNAME（σGNAME='冰箱'（SHOP⋈SALE⋈GOODS）） 元组表达式：{t|(u)(v)(w)(SHOP(u)∧SALE(v)∧GOODS(w)∧u[1]=v[1]∧v[2]=w[1]∧w[2]='冰箱'∧t[1]=u[1]∧t[2]=u[2])}关系逻辑规则：W(u1,u2)SHOP(u1,u2,u3,u4)∧SALE(u1,v2,v3)∧GOODS(v2,'冰箱',w3)(2)SELECT语句如下： SELECTA.S#，SNAME FROMSHOPA，SALEB，GOODSCWHEREA.S#=B.S#ANDB.G#=C.G#ANDGNAME='冰箱'；(3)DELETEFROMSALE WHERES#IN（SELECTS# FROMSHOP WHERESNAME='开开商店'） ANDG#IN（SELECTG#FROMGOODS WHEREPRICE>1000）；(4)CREATEASSERTIONASSE8CHECK （100<=ALL（SELECTPRICE FROMSHOPA，SALEB，GOODSC WHEREA.S#=B.S#ANDB.G#=C.G#ANDAREA='EAST'））； 或CREATEASSERTIONASSE8CHECK （NOTEXISTS（SELECT* FROMSHOPA，SALEB，GOODSC WHEREA.S#=B.S#ANDB.G#=C.G#ANDAREA='EAST'ANDPRICE<100））；(5)SELECTC.G#，GNAME，SUM（QUANTITY）ASSUM_QUANTITY，PRICE*SUM（QUANTITY）ASSUM_VALUE FROMSHOPA，SALEB，GOODSC WHEREA.S#=B.S#ANDB.G#=C.G#ANDAREA='EAST' GROUPBYC.G#，GNAME； （注：SELECT子句中的属性C.G#，GNAME应在分组子句中出现）3.［答案］由段表知，第0段内存始址210，段长为500，故逻辑地址（0,430）是合法的，对应的物理地址为210+430=640。由段表知，第1段内存始址2350，段长为20，故逻辑地址（1,10）是合法的，对应的物理地址为2350+10=2360。由段表知，第2段内存始址100，段长为90，故逻辑地址（2,500）的段内位移500已经超过了段长，故为非法地址。由段表知，第3段内存始址1350，段长为590，故逻辑地址（3,400）是合法的，对应的物理地址为1350+400=1750。由段表知，第4段内存始址1938，段长为95，故逻辑地址（4,112）的段内位移112已经超过了段长，故为非法地址。由段表知，不存在第5段，故逻辑地址（5,32）为非法地址。4.［答案］过程如下：第1趟：4,5,1,2,8,6,7,3,10,9第2趟：1,4,5,2,8,6,7,3,10,9第3趟：1,2,4,5,8,6,7,3,10,9第4趟：1,2,4,5,8,6,7,3,10,9第5趟：1,2,4,5,8,6,7,3,10,9第6趟：1,2,4,5,8,6,7,3,10,9第7趟：1,2,3,4,5,6,7,8,10,9第8趟：1,2,3,4,5,6,7,8,10,9第9趟：1,2,3,4,5,6,7,8,9,105.［答案］链式存储结构略，前序ABDEC，中序DBEAC，后序DEBCA。6.［答案］852[解析]首先定义整型变量i，整型数组a,a的长度为10，即a中包含10个整型元素（整型变量）执行for循环语句初值i=9,使得循环条件i>=0成立，执行循环体第1次循环 执行a[i]=10-i等价于a[9]=10-9=1 计算表达式3，即i--，i为8，使得循环条件i>=0成立，继续执行循环体第2次循环 执行a[i]=10-i等价于a[8]=10-8=2 计算表达式3，即i--，i为7，使得循环条件i>=0成立，继续执行循环体第3次循环 执行a[i]=10-i等价于a[7]=10-7=3 计算表达式3，即i--，i为6，使得循环条件i>=0成立，继续执行循环体第4次循环 执行a[i]=10-i等价于a[6]=10-6=4 计算表达式3，即i--，i为5，使得循环条件i>=0成立，继续执行循环体第5次循环 执行a[i]=10-i等价于a[5]=10-5=5 计算表达式3，即i--，i为4，使得循环条件i>=0成立，继续执行循环体第6次循环 执行a[i]=10-i等价于a[4]=10-4=6 计算表达式3，即i--，i为3，使得循环条件i>=0成立，继续执行循环体第7次循环 执行a[i]=10-i等价于a[3]=10-3=7 计算表达式3，即i--，i为2，使得循环条件i>=0成立，继续执行循环体第8次循环 执行a[i]=10-i等价于a[2]=10-2=8 计算表达式3，即i--，i为1，使得循环条件i>=0成立，继续执行循环体第9次循环 执行a[i]=10-i等价于a[1]=10-1=9 计算表达式3，即i--，i为0，使得循环条件i>=0成立，继续执行循环体第10次循环 执行a[i]=10-i等价于a[0]=10-0=10 计算表达式3，即i--，i为-1，使得循环条件i>=0不成立，跳出循环体7.［答案］ch=f[解析]首先定义一个字符型数组s，并用字符串abcdefg对s进行初始化;然后定义一个字符型指针变量p;对p进行初始化，将数组s的地址赋给p。因此此时p中存放的数组s的首地址，即数组中第一个元素s[0]的地址。然后执行printf语句，输出表达式*(p+5)的值。p+5表示以p当前指向的位置起始，之后第5个元素的地址，即a[5]的地址。*(p+5)则表示该地址内所存放的内容，即a[5]的值f,因此输出ch=f8.［答案］（1）画表如下：0011223344556677889911011111211311411511611733211763492044010303146471111663311221111113333（2）查找63,首先要与H(63)=63%16=15号单元内容比较，即63vs31,no;然后顺移，与46,47,32,17,63相比，一共比较了6次。（3）查找60,首先要与H(60)=60%16=12号单元内容比较，但因为12号单元为空（应当有空标记），所以应当只比较这一次即可。（4）ASL=1/11（6＋1*6+2＋3×3）＝23/11=2.099.［答案］出入口一次仅允许一个人通过，设置互斥信号量mutex，初值为1.博物馆最多可同时容纳500个人，故设置信号量empty，初值为500。Semaphoreempty=500;//博物馆可容纳的最多人数Semaphoremutex=1;//用于出入口资源的控制cobegin参观者进程i:{...P(empty);//可容纳人数减1P(mutex);//互斥使用门1进门;V(mutex);参观;P(mutex);//互斥使用门出门；V(mutex);V(empty);//可容纳人数增1...}coend编程题（每题10分，共20分）1.［答案］boolBisortTree(BiTreeT){//其中PRE为指向当前访问结点的前驱的指针。intlast=0,flag=1;//last是全局变量，用来记录前驱结点值，只要每个结点都比前驱大就行。BiTreepre;pre=null;Is_BSTree(T);}intIs_BSTree(BitreeT)//判断二叉树T是否二叉排序树，是则返回1，否则返回0{if(T->lchild&&flag