2022年北京航空航天大学计算机软件技术基础试题 .pdf

《2022年北京航空航天大学计算机软件技术基础试题 .pdf》由会员分享，可在线阅读，更多相关《2022年北京航空航天大学计算机软件技术基础试题 .pdf（5页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、说明：请在试卷册封面和本页分别填写清楚学号和姓名，请勿遗忘。学号：姓名：（A）卷缺考标记 _ 一、填空题：（本题共计 30 分）1、 线性表、树和图是指数据的逻辑结构；顺序、链式存储是指数据的存储结构。(2 分)2、 计算机中的算法是指解决某一问题的有限运算序列。(1 分)3、 以下代码片段的时间复杂度为 O(n2) 。(2 分)for(i=0;in;i+) for(j=0; jlink; free(p); 。(2 分)6、 已知某二叉树的前序遍历序列为：C,B,F,E,G,A,D,H,I,J; 中序遍历序列为: F,B,G,E,C,H,D,I,J,A; 该二叉树的后序遍历序列为: F,G ,

2、E,B,H,J,I,D,A,C 。(2 分)7、 对于一个图 ,需要存储的信息包括: 结点信息、边信息和边的权值信息。(3 分)8、 在顺序表 2 、 5、7、10、14、 15、18、23、35、41、52 中用二分法查找关键字5，需做4 或 3 次 关键字比较。(2 分)9、 一个非空双链表，其结点类型为：struct list int data; struct list *llink; struct list *rlink;，若要删除指针q 指向的一个中间结点，需要执行的语句序列为：(q-llink)-rlink=q-rlink;(q-rlink)-llink=q-llink; free

3、(q); 。(3 分)10、在索引表中 ，若 一个索引项 对应主表中的一条记录，则称此索引为_ _ 稠密 _ 索引，若对应主表中的若干条记录，则称此索引为_非稠密 _索引。(2 分)11、数据库系统 一般由数据库、数据库管理系统、应用系统、数据库管理员和用户几个部分组成。(2 分)12、E-R 图中，矩形表示实体，椭圆表示实体和联系的属性。(2 分)13、关系模型的完整性是指 实体完整性、 参照完整性和 用户（自）定义完整性。(3 分)14、程序调试中设置变量观察窗的目的是观察程序运行过程中变量值。(1 分)15、VC 调试环境中，快捷键F5 的作用是开始调试或运行到断点。(1 分)名师资料总

4、结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 1 页，共 5 页 - - - - - - - - - 二、选择题：（每个小题2 分，本题共计20 分）请将答案填写在下面的方框中，填写在题目后面无效：1 2 3 4 5 6 7 8 9 10 1、SQL语言中的表（ table ）是数据库体系结构中的（ B ）(A) 内模式 (B)模式 (C)外模式 (D)物理模式2、程序通过编译检查后，说明程序（D ）(A) 完全正确 (B)没有逻辑错误 (C)没有运行时错误 (D)没有语法错误3、链表中每个

5、链结点所占用的存储单元（ A ）(A) 一定连续 (B) 部分地址连续 (C) 一定不连续 (D) 连续与否无所谓4、n 个顶点、 e条边的无向图采用邻接表存储方法，该邻接表中共有（B ）个边结点。(A) e (B) 2e (C) n (D) 2n5、若频繁地对线性表进行插入和删除操作，该线性表应该采用（C ）存储结构合适。(A) 顺序 (B) 散列 (C) 链式 (D) 索引6、已知待排序序列的关键字顺序如下： 12 ，04，29，50，06，38，47，10。快速排序过程中第一趟排序结束后的结果为（C ） 。 (A) 04,12,06,29,50,38,47,10 (C) 06, 04,

6、10,12, 50, 38,47, 29 (B) 04,06,10,12,29,38,47,50 (D) 04,06,29,50,12,38,47,10 7、用顺序存储方法将完全二叉树中所有结点存放在数组RN 中，如果结点Ri 有右子树，则该右子树的根结点为（ D ）(A) R2i+1 (B) R2i (C) Ri/2 (D) R2i28、图的邻接表如下图所示，从顶点V1 出发进行广度优先搜索的顶点序列是（B）(A) V1,V2,V3,V4,V6,V5 (C) V1,V2, V4,V3,V6,V5 (B) V1,V2,V3,V4,V5,V6 (D) V1,V2,V4,V3,V5,V6 9、设计

7、一个递归问题的非递归算法通常需要设置（C）结构。(A) 线性表 (B) 数组 (C)堆栈 (D)队列10、调试程序的目的是为了（C） 。(A) 排除程序中所有错误 (C)尽可能排除程序中的错误 (B)证明程序完全正确 (D)让用户放心2 V1 V2 V3 V4 V5 V6 3 4 5 5 4 2 3 2 3 4 4 5 6 1 1 5 6 vertex edgelist 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 2 页，共 5 页 - - - - - - - - - 三、解答题

8、：（根据要求作答，共五题，共计50 分）1、 已知一线性表中数据元素的数据项为学号 ,成绩 ，采用单链表存储该线性表。根据以下要求写出相应的算法。（要求用 C 语言描述）（ 12 分）（ 1）该链表的结点类型；（2 分）struct student int sno; int score; struct student *next; ; （ 2）已知表头指针list，在链表上查找并打印成绩最高的学号;（5 分）void search(struct student *list) struct student *p; p=list; max=0; num=0; while (p !=NULL) /

9、查找链表2 分if (p-score max) / 找最大值2 分 max= p-score; num= p-sno; p=p-next; printf( “ %d%d” , num, max); / 打印1 分return; （ 3）已知表头指针list，在链表的表尾插入一个新元素（学号为x，成绩为 y） 。 （5 分）void insert(int x,inty) struct student *p,*q; p=list; while(p-next!=NULL) /找到插入位置2 分p=p-next; q=( struct student *)malloc(sizeof(struct st

10、udent); /申请结点1 分if(q!=NULL) q-sno=x; q-score=y; q-next=NULL; / 正确插入2 分p-next=q; return; 2、已知一线性表中数据元素的数据项有学号 ,成绩 ，将该线性表存放在顺序表 ST中，其中有n 个元素，且按照成绩递减有序排列。设计一算法，将一个新数据元素s插入到顺序表ST的适当位置，同时保持顺序表的有序性。 （要求用 C 语言描述）（10 分）(1) 算法相关的数据定义和声明；（ 2 分） #define Max 100; struct node int sno; int score; / 1分 struct node

11、 ST Max; / 1 分（ 2）插入算法（8 分） void insert(struct node ST , struct node s, int n) int k; k=n-1; if( STk.score s.score) / 直接插入到最后元素后：2 分 STk+1.sno=s.sno; STk+1.score=s.score; n+; 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 3 页，共 5 页 - - - - - - - - - else while(STk.sc

12、ore =0) / 移动找到插入位置： 4 分 STk+1.sno= STk.sno; STk+1.score= STk.score; k-; STk+1.sno= s.sno; / 正确插入： 2 分STk+1. score= s.score; n+; 3、 要求：设计一个容量为100 的循环队 ，队结点的数据项学号 ,成绩 。根据以下要求写出相应的算法。 （要求用 C 语言描述）（6 分）（ 1）算法中的数据定义和声明；（2 分）define M 100 struct student int sno; int score; / 1 分struct student queuemax; / 1

13、 分int front, rear; （ 2）新元素（学号为x，成绩为 y）入队操作； （4 分）int addq ( int x, int y) if(rear+1)% M= front) / 队满：2 分 printf( “ The queue is full. ” ); return 0; else rear=rear+1; / 入队： 2 分queuerear.sno=x; queuerear.score=y; return 1; 4、 已知一棵二叉树的前序遍历序列和中序遍历序列(结点号 )分别保存在两个顺序表中，设计一算法从前序和中序序列建立该二叉树的二叉链表。（要求用 C 语言描述

14、）（12 分）(1)算法相关的数据定义和声明；（4 分）#define n 100; int preordern; /前序序列表： 1 分int inordern; / 中序序列表：1 分struct BTnode int num; struct node * lchild,*rchild; ; /二叉树结点定义：2 分(2)算法；（8 分）Bitree Build_BT (int Pre_Start, int Pre_End, Int In_Start,int In_End) struct BTnode *root; root=( struct BTnode *)malloc(sizeof(

15、struct BTnode); /根结点： 1 分root-num =preorderPre_Start; for(i=In_Start; inorderi!=root-num;i+); /在中序序列中查找子树根：1 分leftlen=i-In_Start; rightlen=In_End-i; if(leftlen) lroot=Build_Sub(Pre_Start+1,Pre_Start+leftlen,In_Start,In_Start+leftlen-1); root-lchild=lroot ； /建左子树： 1分名师资料总结 - - -精品资料欢迎下载 - - - - - - -

16、 - - - - - - - - - - - 名师精心整理 - - - - - - - 第 4 页，共 5 页 - - - - - - - - - if(rightlen) rroot=Build_Sub(Pre_End-rightlen+1,Pre_End,In_End-rightlen+1,In_End); root-rchild=rroot ； /建右子树： 1 分 return root; / 返回子树根，整体思路4 分 5、已知某单位人事管理系统中数据库表设计如下：员工表（员工编号，姓名，身份证号，住址，联系电话）部门表（部门编号，部门名称，负责人）工作表（部门编号，员工编号，工资）

17、根据以下要求写出对应的SQL 语句：（10 分）1.创建 工作表（字段属性自定）; （2 分）create table 工作表 ( 部门编号char(8) not null , 员工编号char(10) not null, 工资int); 2.增加 一个新员工的 记录 （属性值自定）（2 分）insert into 员工表values (,0201? ,? 李二 ?,? 100108198808087320? ,?北航 10 楼 302? ,? 62316666?) ; 3.删除 员工“贾鹏”的记录 （2 分）Delete from 员工表Where 姓名 =贾鹏4.查询 员工“王大卫”的所在部门的名称；（2 分）select 部门 .部门名称from 员工表，部门表，工作表where 员工 .姓名 ? 王大卫 ? and 员工 .员工编号工作.员工编号and工作 .部门编号部门.部门编号 ; 5.查询 员工“王大卫”的身份证号；（2 分）select 姓名，身份证号from 员工表where 姓名 ? 王大卫 ?; 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 5 页，共 5 页 - - - - - - - - -