计算机软件基础模拟试题

一、选择题（26分）

1、线性表是          

A、一个有限序列，可以为空     B、一个有限序列，不能为空

C、一个无限序列，可以为空     D、一个无限序列，不能为空

 2、在一个长度为n的顺序存储的线性表中，向第i个元素（i<=n+1&&i>=1）之前插入一个新元素时，需要从后向前依次后移          个元素。

A、n-i        B、n-i+1         C、n-i-1        D、i

3、链表不具备的特点是          。

A、可随机访问任一个元素  B、插入删除不需要移动元素

C、不必事先估计存储空间  D、所需的空间与线性表的长度成正比

 4、有一个散列表，表长度m为100，采用除留余数法构造散列函数，即H(K)=

K mod P （P≤m），为使散列函数有较好的性能，P的选择应该是_____________。

A、99       B、97        C、91        D、93

5、若让元素1、2、3依次进栈，则出栈次序不可能出现_____________种情况。

A、 3─2─1     B、 2─1─3       C、 3─1─2      D、 1─3─2

6、设结点X有左孩子结点Y，右孩子结点Z，用先序、中序、后序三种遍历方法得到的遍历序列中X是Y的前驱，Y是Z的前驱。

A、一定      B、不      C、不一定

7、栈和队列的共同点是__     _。

A、都是先进后出                      B、都是先进先出

C、只允许在端点处插入和删除元素      D、没有共同点     

8、向一个栈顶指针为HS（HS所指结点为实际结点）的链栈中插入一个s所指结点时，则执行___    _。A、HS—＞next=s;B、s—＞next=HS—＞next;  HS—＞next=s;

C、s—＞next=HS;    HS=s;D、s—＞next=HS;    HS=HS—＞next;     

 10、二分查找法要求查找表中各元素的关键字值必须是_____________排列。

A、递增       B、递减     C、递增或递减  D、无序

11、已知一个图如图所示，若从顶点a出发按深度搜索法进行遍历，则可能得到的一种顶点序列为_ ①     __； 按广度搜索法进行遍历，则可能得到的一种顶点序列为_②__    _。

①  A、 a , b , e , c , d , f            B、 a , c , f , e , b , d

C、 a , e , b , c , f , d            D、 a , e , d , f , c , b 

②  A、 a , b , c , e , d , f            B、 a , b , d , e , f , c

C、 a , e , b , c , f , d            D、 a , c , e , b, f , d

二、判断题（14分）

 1、（  ）顺序存储的线性表可以随机存取。

 2、（  ）理想情况下，在散列表中搜索一个元素的时间复杂度为O（1）。

 3、（  ）软件测试常采用白盒法和黑盒法两种测试方法。  

 4、（  ）链表的物理存储结构具有同链表一样的顺序。

 5、（  ）散列法存储的基本思想是由关键字的值决定数据的存储地址。

 6、（  ）在索引顺序结构的搜索中，对索引表既可以采取顺序搜索，也可以采取折半搜索。

 7、（  ）若一棵二叉树的任一非叶子结点的度为2，则该二叉树为满二叉树。

三、填空题（10分）

    1、在线性表的单链接存储结构中，每个结点包含有两个域，一个叫         ，另一个叫        域。

    2、在线性表的单链接存储中，若一个元素所在结点的地址为p，则其后继结点的地址为            。

    3、表示图的三种存储结构为           、           和           。

    4、一棵高度为5的满二叉树中的结点数为        个。

    5、对于一个具有n个顶点的图若采用邻接矩阵表示，则矩阵大小为        。

 四、写结果

 1、指出下列算法的时间复杂度。（2分）

    int  prime(int n)

      {     int i=2;

            int x=(int)sqrt(n);

while(i<=x)

               { if(n%i==0) break;

                 i++;}

if(i>x)return 1;

                else  return 0;

      }

 2、写出下图所示的二叉树先序、中序、后序遍历时得到的结点序列。（6分）

 3、建立一个数据库文件（工资.DBF），包含字段有“序号、姓名、职务、基本工资、补贴、工资总额”，写出完成下列要求的命令。（3分）

  4、“软件就是程序”这话对吗？为什么？软件生命周期一般要经历哪些阶段？（4分）

 五、若待排序的关键字序列为{25，73，12，80，116，05}，给出希尔排序的过程示意图。（6分）六、编程题

 1、若单链表数据域中的值≥0，则该结点数据域的值保持不变；若单链表数据域中的值<0，则该结点数据域的值置为0。编写程序，实现该算法。（8分）

2、用C语言编写递归函数过程，逐个结点释放二叉树的每个结点。（6分）

                                《计算机软件基础》本科生

一、选择题（26分）每项2分

1、A  2、B  3、A  4、B  5、C  6、C   A

   7、C  8、C  9、A  10、C  11、D   D

二、判断题（14分）每项2分

1、（ V ） 2、（ V ） 3、（ V ） 4、（ × ） 5、（ V ） 6、（ V ）7、（ × ）

三、填空题（10分）每项2分

1、值 指针2、p->next3、邻接矩阵，邻接表，逆邻接表 4、31  5、n的平方

 四、写结果1、该算法的时间复杂度为O（）。（2分）

 2、写出下图所示的二叉树先序、中序、后序遍历时得到的结点序列。（6分）

 先序遍历为 25，16，8，37，30，28，26，29，32，35，48，60

中序遍历为 8，16，25，26，28，29，30，32，35，37，48，60

后序遍历为 8，16，26，29，28，35，32，30，60，48，37，25

  3、（3分）use工资                            1

disp for职务=“工程师”             1

go 3,  dele,   pack                  1

4、（4分）不对，软件包括程序和文档。         2

问题定义、可行性研究、需求分析、规格说明、软件设计、编码和单元测试、

综合测试、软件维护                2

 五、（6分）希尔排序过程如下：

    2    2

    1     1

六、编程题

1、（8分）      

void assign(head)                        1

struct link *head, p;                      1

{  p=head;                             1

while (p!=NULL)                      2

{ if (p->data<0) p->data=0; 1

p=p->next } 2

} 2、（6分）deletree(tree) struct link *tree; 1{ if (tree->lchild!=NULL) deletree(tree->lchild); 1 if (tree->rchild!=NULL) 1deletree(tree->rchild); f(tree); 1}