资源描述：
《计算机软件基础3.doc》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、2005年计算机软件基础试卷一、选择题（26分）1、线性表是A、一个有限序列，可以为空B、一个有限序列，不能为空C、一个无限序列，可以为空D、一个无限序列，不能为空2、在一个长度为n的顺序存储的线性表中，向第i个元素（i<=n+1&&i>=1）之前插入一个新元素时，需要从后向前依次后移个元素。A、n-iB、n-i+1C、n-i-1D、i3、链表不具备的特点是。A、可随机访问任一个元素B、插入删除不需要移动元素C、不必事先估计存储空间D、所需的空间与线性表的长度成正比4、有一个散列表，表长度m为100，采用除留余数法构造散列
2、函数，即H(K)=KmodP（P≤m），为使散列函数有较好的性能，P的选择应该是_____________。A、99B、97C、91D、935、若让元素1、2、3依次进栈，则出栈次序不可能出现_____________种情况。A、3─2─1B、2─1─3C、3─1─2D、1─3─26、设结点X有左孩子结点Y，右孩子结点Z，用先序、中序、后序三种遍历方法得到的遍历序列中X是Y的前驱，Y是Z的前驱。A、一定B、不C、不一定7、栈和队列的共同点是___。A、都是先进后出B、都是先进先出C、只允许在端点处插入和删除元素D、没有共同
3、点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出发按深度搜索法进行遍历，则可能得到的一种顶点序列为_①__；按广度搜索法进行遍历，则可能得到的一种
4、顶点序列为_②___。 ①A、a,b,e,c,d,fB、a,c,f,e,b,dC、a,e,b,c,f,dD、a,e,d,f,c,b ②A、a,b,c,e,d,fB、a,b,d,e,f,cC、a,e,b,c,f,dD、a,c,e,b,f,d二、判断题（14分） 1、（）顺序存储的线性表可以随机存取。 2、（）理想情况下，在散列表中搜索一个元素的时间复杂度为O（1）。 3、（）软件测试常采用白盒法和黑盒法两种测试方法。 4、（）链表的物理存储结构具有同链表一样的顺序。 5、（）散列法存储的基本思想是由关键字的值决定数据的存储
5、地址。6、（）在索引顺序结构的搜索中，对索引表既可以采取顺序搜索，也可以采取折半搜索。 7、（）若一棵二叉树的任一非叶子结点的度为2，则该二叉树为满二叉树。三、填空题（10分） 1、在线性表的单链接存储结构中，每个结点包含有两个域，一个叫，另一个叫域。 2、在线性表的单链接存储中，若一个元素所在结点的地址为p，则其后继结点的地址为。 3、表示图的三种存储结构为、和。 4、一棵高度为5的满二叉树中的结点数为个。 5、对于一个具有n个顶点的图若采用邻接矩阵表示，则矩阵大小为。 四、写结果 1、指出下列算法的
6、时间复杂度。（2分）intprime(intn){inti=2;intx=(int)sqrt(n);while(i<=x){if(n%i==0)break;i++;}if(i>x)return1;elsereturn0;} 2、写出下图所示的二叉树先序、中序、后序遍历时得到的结点序列。（6分）3、建立一个数据库文件（工资.DBF），包含字段有“序号、姓名、职务、基本工资、补贴、工资总额”，写出完成下列要求的命令。（3分） 4、“软件就是程序”这话对吗？为什么？软件生命周期一般要经历哪些阶段？（4分）五、若待排序的关键字序
7、列为{25，73，12，80，116，05}，给出希尔排序的过程示意图。（6分）六、编程题 1、若单链表数据域中的值≥0，则该结点数据域的值保持不变；若单链表数据域中的值<0，则该结点数据域的值置为0。编写程序，实现该算法。（8分）2、用C语言编写递归函数过程，逐个结点释放二叉树的每个结点。（6分） 《计算机软件基础》本科生考试答案 一、选择题（26分）每项2分1、A2、B3、A4、B5、C6、CA 7、C8、C9、A10、C11、DD 二、判断题（14分）每
8、项2分1、（V）2、（V）3、（V）4、（×）5、（V）6、（V）7、（×）三、填空题（10分）每项2分1、值指针2、p->next3、邻接矩阵，邻接表，逆邻接表4、315、n的平方 四、写结果1、该算法的时间复杂度为O（）。（2分） 2、写出下图所示的二叉树先序、中序、后序遍历时得到的结点序列。（6分
