软件技术基础试题举例

1、在软件结构设计中，要力求降低各个模块之间的耦合性，提高模块内部的____________。内聚性

2、通常软件测试需要经历4个步骤，即________________、集成测试（子系统测试和系统测试）、确认测试（验收测试）和新旧的平行运行。单元测试

3、下列程序段的时间复杂度为____________。O(n2)

x=0;

for(i=1; ifor(j=0; j<=2*n; j++)  x++; }

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{ while(iif(iwhile(iif(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 for(j=0;j           e=e+g->arcs[i][j];

    return e/2;

}