2013年计算机软件基础试题A卷.doc

《2013年计算机软件基础试题A卷.doc》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、北京信息科技大学2012~2013学年第二学期《计算机软件基础》课程考试试卷A卷课程所在学院：自动化学院适用专业班级：智能1101-1103考试形式：笔试(闭卷)班级：姓名：学号：注意事项：1、请将全部答案写在答题纸上，并写清题号，否则无效一．单选题（每题2分，共20分）1.数据的逻辑结构可分为（　　　）A．顺序结构和链式结构B．简单结构和复杂结构C．线性结构和非线性结构D．动态结构和静态结构2.若一个栈的输入序列是1，2，3，…，n，输出序列的第一个元素是n，则第i个输出元素是（　　）A．n-iB．n-i+1C．iD．n-i-13.有一个长度为13的有序

2、表：{1,3,9,12,32,41,45,62,75,77,82,95,100}，用二分（折半）方法查找值为82的元素，查找成功时关键字的比较次数为（　　　）A．1B．2C．4D．84.一个进程如果处于运行状态，说明该进程（　　　）A．正在占用处理机B．正在输入数据C．正在输出数据D．PCB被系统收回5.在软件开发中，数据流图描述了（　　　）A．加工的数据B．加工步骤C．加工的激发条件D．加工的控制条件6.二叉树的第i（i≥1）层上结点个数至多有（　　　）A．2i-1-1B．2i-1C．2i-1D．2i7.采用结构化方法设计，要提高模块结构的相对独立性，则

3、应该（　　　）A．增加块间联系，减小块内联系B．减少块间联系，减少块内联系C．增加块间联系，增加块内联系D．减少块间联系，增大块内联系8.带头结点的单链表Head为空的判定条件是（　　　）A．Head=NULLB．Head->next=NULL：C．Head->next=HeadD．均不正确；9.在一个单链表HL中，若要删除由指针q所指向的后继结点，则执行（）。A.p=q->next;p->next=q->next;B.p=q->next;q->next=p;C.p=q->next;q->next=p->next;D.q->next=q->next->ne

4、xt;q->next=q;10.下面关于进程队列说法不正确的是（）。A．系统中可以存在多个等待队列B．系统中可以有多个运行队列C．系统中只能有一个运行队列D．系统中只能有一个就绪队列二、程序填空题（在空格处填上语句，组成完整的算法，每一空格只写一条语句,共18分）。1．下面是一个反向建立链表算法。请在算法的______处填上正确的语句，完成该算法。#defineNm/*m为链表中数据元素的个数*/intA[N];NODE*creatlink1(){NODE*head,*s;inti;head=(NODE*)malloc(sizeof(NODE));head

5、->next=NULL;for((1);i>=0;i--){s=(NODE*)malloc(sizeof(NODE));s->data=A[i];(2);(3);}returnhead;}2．下面是一个冒泡排序算法。请在算法的______处填上正确的语句，完成该算法。#defineMAXLENn+1……voidbubblesort(RECORDR[],intn)/*注意待排记录放在R[1]到R[n]中*/{inti,j;RECORDtemp;for(i=1;i

6、1]=temp;}}三、简答题（共32分）1.设哈希函数H(key)=keyMOD6，哈希表的地址空间为0～5，对关键字序列（19，23，31，68，91，16）按线性探测再散列法解决冲突建立哈希表。对线性探测再散列法说明如下：Hi=(H(key)+di)MODm，其中，di=1～m-1，i=1～k,km-1,m为哈希表长。要求有计算过程（8分）2.已知某二叉树的先序遍历为：ABCDEFGHI，中序遍历为：CBEDFAHGI，请画出该树，并写出该树的后序遍历序列。（7分）3.以关键码（46，55，13，42，94，05，17，70）为例，手工执行以下排序算

7、法，写出第二趟排序结束时的关键码状态。a．直接插入排序b．简单选择排序c.冒泡排序d.快速排序。（8分）4.已知某无向图的邻接矩阵为，请画出该无向图，并求出每个顶点的度，并给出从第一个节点出发的深度优先生成树，并作出该图的邻接表。（9分）四、程序设计题（本题14分）有一线性表存储在一个带头结点的双向链表L中（不知道头结点指针），已知其中某结点的指针P，写出计算线性表中元素个数的算法。五、综合分析设计题（本题16分）试设计某工厂产品存放数据库，该数据库中存放产品的产品号P#，产品名PN，产品规格PS等信息。对仓库有仓库号W#，仓库名WN，地址WA。同时还需要

8、存储仓库中存放产品的数量QTY。要求：   （1）画出该E-R图，