软件技术基础试题举例.doc

一、填空题（每空2分，共30分）1、在软件结构设计中，要力求降低各个模块之间的耦合性，提高模块内部的_。内聚性2、通常软件测试需要经历4个步骤，即_、集成测试（子系统测试和系统测试）、确认测试（验收测试）和新旧的平行运行。单元测试3、下列程序段的时间复杂度为_。O(n2)x=0;for(i=1; in; i+) y=y+1;for(j=0; jtop=M-1) printf(Stack overflow); else _; 答案：stack-s+stack-top=x7、设目标串S=“abccdcdccbaa”，模式串T=“cdcc”，则第_趟匹配成功。68、假设二维数组A68按行优先的顺序存储，每个元素占用4个字节。已知A的起始地址为1000，末尾元素A57的第一个字节地址为1188；元素A34的第一个字节地址为_。1000+(3*8+4)*4=11129、若二叉树中有41个结点，度为1的结点有10个，那么叶子结点有_个。1610、若深度为6的完全二叉树的第6层有3个叶子结点，则该二叉树一共有_个结点。3411、若某二叉树的中序遍历序列为ABCD，先序遍历序列为CABD，那么该二叉树的后序遍历序列应当是_。BADC12、以下算法在指针t所指向的二叉排序树中查找关键字值等于k的结点。查找成功，返回该结点的指针；查找不成功，返回空指针。请将算法补充完整。 typedef struct nodekeytype key; struct node *lchild,*rchild;bitree;bitree *BstSearch(bitree *t, keytype k) while(t!=NULL&t-key!=k) if(t-keyk) t=t-lchild;else t=t-rchild;if(t!=NULL) _; else return NULL; 答案：return t13、若两个不同的关键字通过散列函数的计算得到同一个散列地址，这种现象称为_。冲突14、设一组初始记录关键字序列5，2，6，3，8，以第一个记录关键字5作为基准进行一趟快速排序的结果为_。3,2,5,6,815、影响排序效率的两个主要因素是关键字的_次数和记录的移动次数。比较二、单项选择题（每小题1分，共12分）1、以下哪一项不属于软件危机的范畴。（ ）CA.对软件开发成本以及进度的估计常常很不准确B.软件常常是不可维护的C.软件开发生产率提高的速度快D.软件成本在计算机系统总成本中所占的比例逐年上升2、若有一个计算类型的程序，它的输入量只有一个，其范围是-1.01.0。如果对该程序进行黑盒法测试，从输入的角度考虑一组测试用例：-1.001、-1.0、1.0、1.001，设计这组测试用例的方法属于（ ）。CA条件覆盖法B等价分类法C边界值分析法D错误推测法3、提高测试的有效性非常重要,成功的测试是指（ ）。DA证明了被测试程序正确无误B说明了被测试程序符合相应的要求C未发现被测程序的错误D发现了至今为止尚未发现的错误4、某算法的语句执行频度为T(n)=3n+nlog2n+n2+8,其时间复杂度应当是（ ）。AO(n)BO(nlog2n)CO(n2)DO(n+nlog2n+n2)5、在单链表中，已知q所指结点是p所指结点的直接前趋结点，若在*q与*p之间插入一个由s指向的结点，则需执行（ ）。As-next=p-next; p-next=s;Bq-next=s; s-next=p;Cp-next=s-next; s-next=p;Dp-next=s; s-next=q;6、若用一个大小为6的数组来实现循环队列，且当前rear和front的值分别为0和3。当从队列中删除一个元素，再加入两个元素后，rear和front的值分别为（ ）。BA1和52和4C4和2D5和17、将递归算法转换成对应的非递归算法时，通常需要使用（ ）。AA栈B队列C链表D数组8、按照输入序列（18、12、9、23、45、57、16、22）构造一棵二叉排序树。若在这棵二叉排序树中查找值为46的结点，需要比较（ ）次才能确定查找不成功。A. 3B. 4C. 5D. 69、下面关于哈夫曼树的说法，不正确的是( )。A.对应于一组权值构造出的哈夫曼树不一定唯一B.哈夫曼树具有最小带权路径长度C.哈夫曼树中没有度为1的结点D.哈夫曼树一定是完全二叉树10、若邻接表中有奇数个结点，则（ ）。A图中有奇数个顶点B图中有偶数个顶点C图为无向图D图为有向图11、采用拉链法解决冲突的散列表中，查找的平均查找长度( )。A直接与关键字个数有关B直接与装填因子有关C直接与表的容量有关D直接与散列函数有关12在以下排序算法中，算法空间复杂度为O(n)的是（ ）。A直接选择排序B归并排序C起泡排序D快速排序三、简答、分析算法题（每小题6分，共42分）1、输入三整数判断是否可以构成三角形。如构成三角形，则输出三条边的值；否则输出“不能构成三角形”。根据程序的流程图、程序图、路径以及测试用例中输入的数据，在实现路径覆盖的测试用例表中填写预期的输出和覆盖的路径。实现路径覆盖的测试用例表测试用例输入的数据预期的输出覆盖的路径1A=2，B=3，C=4A=2，B=3，C=4路径12A=2，B=2，C=4不能构成三角形路径23A=2，B=4，C=2不能构成三角形路径34A=4，B=2，C=2不能构成三角形路径42、设一棵树T中边的集合为(A，B)，(A，C)，(A，D)，(B，E)，(C，F)，(C，G)，要求画图说明：（1）用孩子兄弟表示法（二叉链表）表示出该树的存储结构；（2）将该树转化成对应的二叉树。3、无向网络G如图所示，试给出该图的最小生成树上边的集合E，并计算最小生成树上边的权值之和W。答案：E=(A,E), (B,E), (C,E), (C,D) W=2+1+1+6=104、算法是对带有头结点的单链表的运算，单链表的初始状态如图所示，要求画图表示算法运行之后的单链表。typedef struct node datatype data; struct node *next;lklist;void lklist_OP(lklist*L) lklist *p, *q; if(L-next-next!=NULL) q=L-next; L-next=L-next-next; p=L-next; while(p-next!=NULL) p=p-next; p-next=q; q-next=NULL; 答案：5、以下算法是关于二叉排序树的运算，试分析算法的功能。typedef struct node int key;struct node *lchild, *rchild; bitree;int n=0;void BST(bitree *bt, int x) if(bt!=NULL) n+; if(bt-key=x) return;else if(bt-keyx) BST(bt-lchild, x);else BST(bt-rchild, x); 答案：求结点x在二叉排序树中的层次。6、试给出算法执行后顺序表r的值，并说明算法的功能。int r =46,78,39,54,32,20,17,50;void Algorithm( ) int i=0,j=7,x=r0; while(ij) while(ij&rj%2=0) j=j-1; if(ij) ri+=rj; while(ij&ri%2=1) i=i+1; if(inext; while(p-next!=NULL) s=p-next; if(s-data=p-data) p-next=s-next; free(s); else p=p-next; 2、若无向图采用邻接矩阵存储，邻接矩阵的类型定义如下：typedef structvextype vexsn; /顶点数组 adjtype arcsnn; /邻接矩阵graph;/邻接矩阵类型试写出算法计算无向图中边的个数。函