1、在软件结构设计中，要力求降低各个模块之间的耦合性，提高模块内部的____________。内聚性
2、通常软件测试需要经历4个步骤，即________________、集成测试（子系统测试和系统测试）、确认测试（验收测试）和新旧的平行运行。单元测试
3、下列程序段的时间复杂度为____________。O(n2)
x=0;
for(i=1; i 4、数据的逻辑结构在计算机存储器内的表示，称为数据的_________________。存储结构 5、已知链表结点定义如下： typedef struct node{ char data［16］； struct node *next； }LinkNode； 如果每个字符占1个字节，指针占4个字节，则该链表的存储密度是___________。0.8或80% 6、以下算法的功能实现数据x进栈，在划线处补充算法。 typedef struct{ int s[M]; int top;}sqstack; void push(sqstack*stack,int x) { if(stack->top==M-1) printf("Stack overflow"); else ______________________; } 答案： stack->s[++stack->top]=x 7、设目标串S=“abccdcdccbaa”，模式串T=“cdcc”，则第__________趟匹配成功。6 8、假设二维数组A6×8按行优先的顺序存储，每个元素占用4个字节。已知A的起始地址为1000，末尾元素A[5][7]的第一个字节地址为1188；元素A[3][4]的第一个字节地址为____________。1000+(3*8+4)*4=1112 9、若二叉树中有41个结点，度为1的结点有10个，那么叶子结点有___________个。16 10、若深度为6的完全二叉树的第6层有3个叶子结点，则该二叉树一共有______个结点。34 11、若某二叉树的中序遍历序列为ABCD，先序遍历序列为CABD，那么该二叉树的后序遍历序列应当是_________________。BADC 12、以下算法在指针t所指向的二叉排序树中查找关键字值等于k的结点。查找成功，返回该结点的指针；查找不成功，返回空指针。请将算法补充完整。 typedef struct node { keytype key; struct node *lchild,*rchild; }bitree; bitree *BstSearch(bitree *t, keytype k) { while(t!=NULL&&t->key!=k) if(t->key>k) t=t->lchild; else t=t->rchild; if(t!=NULL) ______________________; else return NULL; } 答案：return t 13、若两个不同的关键字通过散列函数的计算得到同一个散列地址，这种现象称为___________。冲突 14、设一组初始记录关键字序列{5，2，6，3，8}，以第一个记录关键字5作为基准进行一趟快速排序的结果为______________________。{3,2,5,6,8} 15、影响排序效率的两个主要因素是关键字的___________次数和记录的移动次数。比较 二、单项选择题（每小题1分，共12分） 1、以下哪一项不属于软件危机的范畴。（ ）C A.对软件开发成本以及进度的估计常常很不准确 B.软件常常是不可维护的 C.软件开发生产率提高的速度快 D.软件成本在计算机系统总成本中所占的比例逐年上升 2、若有一个计算类型的程序，它的输入量只有一个，其范围是-1.0~1.0。如果对该程序进行黑盒法测试，从输入的角度考虑一组测试用例：-1.001、-1.0、1.0、1.001，设计这组测试用例的方法属于（ ）。C A．条件覆盖法 B．等价分类法 C．边界值分析法 D．错误推测法 3、提高测试的有效性非常重要,成功的测试是指（ ）。D A．证明了被测试程序正确无误 B．说明了被测试程序符合相应的要求 C．未发现被测程序的错误 D．发现了至今为止尚未发现的错误 4、某算法的语句执行频度为T(n)=3n+nlog2n+n2+8,其时间复杂度应当是（ ）。 A．O(n) B．O(nlog2n) C．O(n2) D．O(n+nlog2n+n2) 5、在单链表中，已知q所指结点是p所指结点的直接前趋结点，若在*q与*p之间插入一个由s指向的结点，则需执行（ ）。 A．s->next=p->next; p->next=s; B．q->next=s; s->next=p; C．p->next=s->next; s->next=p; D．p->next=s; s->next=q; 6、若用一个大小为6的数组来实现循环队列，且当前rear和front的值分别为0和3。当从队列中删除一个元素，再加入两个元素后，rear和front的值分别为（ ）。B A．1和5 Ｂ．2和4 C．4和2 D．5和1 7、将递归算法转换成对应的非递归算法时，通常需要使用（ ）。A A．栈 B．队列 C．链表 D．数组 8、按照输入序列（18、12、9、23、45、57、16、22）构造一棵二叉排序树。若在这棵二叉排序树中查找值为46的结点，需要比较（ ）次才能确定查找不成功。 A. 3 B. 4 C. 5 D. 6 9、下面关于哈夫曼树的说法，不正确的是( )。 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、输入三整数判断是否可以构成三角形。如构成三角形，则输出三条边的值；否则输出“不能构成三角形”。根据程序的流程图、程序图、路径以及测试用例中输入的数据，在实现路径覆盖的测试用例表中填写预期的输出和覆盖的路径。 （1）用孩子兄弟表示法（二叉链表）表示出该树的存储结构； （2）将该树转化成对应的二叉树。 3、无向网络G如图所示，试给出该图的最小生成树上边的集合E，并计算最小生成树上边的权值之和W。 答案：E={(A,E), (B,E), (C,E), (C,D)} W=2+1+1+6=10 4、算法是对带有头结点的单链表的运算，单链表的初始状态如图所示，要求画图表示算法运行之后的单链表。 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->key>x) 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=r[0]; while(i r[i]=x; } 答案：r(17, 39, 46, 54, 32, 20, 78, 50) 在r中将所有奇数移到所有偶数之前。 7、设有一组记录的关键字序列为{12，16，19，23，26，40，47，52，63}，试给出折半查找判定树，并分别说明查找47和45的比较次数。 查找47比较2次，查找45比较3次。 四、算法设计题（每小题8分，共16分） 1、设有一个带有头结点的单链表，其结点的数据域值非递减有序，编写一个算法删除数据域值相同的多余结点，即使得单链表中结点的数据域值互不相同。单链表结点的类型定义以及函数原型如下： typedef struct node { datatype data; struct node *next; }lklist; void DelRedundant(lklist*head); 答案： void DelRedundant(lklist*head); { lklist *p, *s; p=head->next; while(p->next!=NULL) { s=p->next; if(s->data==p->data){ p->next=s->next; free(s); } else p=p->next; } } 2、若无向图采用邻接矩阵存储，邻接矩阵的类型定义如下： typedef struct{ vextype vexs[n]; //顶点数组 adjtype arcs[n][n]; //邻接矩阵 }graph;//邻接矩阵类型 试写出算法计算无向图中边的个数。函数原型为int Calculate_E (graph *g, int n )；g是指向图的结构体指针，边的个数通过返回值带回，邻接矩阵的元素值为1或0。 int Calculate_E(graph*g, int n) { int i,j,e=0; for(i=0;i return e/2; }下载本文
2、设一棵树T中边的集合为{(A，B)，(A，C)，(A，D)，(B，E)，(C，F)，(C，G)}，要求画图说明：实现路径覆盖的测试用例表 测试用例 输入的数据 预期的输出 覆盖的路径 1 A=2，B=3，C=4 A=2，B=3，C=4 路径1 2 A=2，B=2，C=4 不能构成三角形 路径2 3 A=2，B=4，C=2 不能构成三角形 路径3 4 A=4，B=2，C=2 不能构成三角形 路径4
