电子科技大学软件技术基础试题带答案

1、、填空题（共 20分，共10题，每空1分）若经常需要对线性表进行插入和删除运算，则最好采用.链式 _存储结构，若经常需要对线性表进行查找运算，则最好采用 _顺序 存储结构。2 在操作过程中会出现 “假溢出”现象的是顺序队列 结构，解决此问题的方法是 采用循环对列。地址编号12345678910111213结点ABCDEFGH3 已知一棵二叉树的顺序存储结构为则元素G的父结点是_D4.假定一个有向图的顶点的集合为1,2,3,4,5,6,边的集合为<1,2> , <1,3> , <2,5> , <3,2> ,<3,4> , <4,6

2、> , <5,1> , <5,6>,则出度为 2的顶点个数为 _3，入度为1的顶点个数为4。5 .二分查找算法适用于顺序存储的数据结构，且数据的组织应该按查找的关键字有序。6.虚拟存储方式分为：分页存储、 分段存储、段页存储。7.用户通过操作系统提供的命令接口、系统调用、图形用户接口来使用计算机。8.文件的物理结构分为：连续、链接、索引。9.因特网是由许多大小不冋、类型不同的网络互连而成。10. 有表score (stuid , name,engish ),写出查询姓名和英语成绩的查询语句 Select n ame,E nglish from score11. 主

3、建、选择题（共 30分，共30题，每题1 分）.线性表若采用链式存储结构时，要求内存中可用存储单兀的地址（A.必须是连续的B.C. 一定是不连续的D.2 .下面哪个结构不是线性结构（部分地址必须是连续的连续或不连续都可以）。精选资料，欢迎下载A.队列 B. 图C线性表D.3 一个下图所示的双链表，定义P 为指针变量，则P-> next-next->.prior禾口 P->prior->next扌旨向的数据域的值分别是（B ）A.80 和 20 B. 64和 47 C. 64 和 20 D. 80 和 474 .在一个无向图中，所有顶点的度数之和等于所有边数（C）倍。A.

4、 1/2 B. 1C. 2 D . 45 .一棵树中，树的的深度是（A ）。A. 结点的最大层次值B .子树总的数目C .结点的数目 D .结点子树的最大数6 .一棵二叉树采用顺序存储结构，数组下标从0开始，若存放某结点的数组元素下标为11,则存放它的父结点的数组元素下标为（ C ）。A . 3 B . 4 C . 5 D . 67 .对链式存储的数据实现平均速度较快的查找，应该将数据以（D）形式存放。A .双链表B.循环链表C.二叉链表D.二叉排序树& 一个栈的入栈序列是a,b,c,d,e ，且每个字符只进栈一次，则栈的不可能的输出序列是（C ）A e,d,c,b,a B. d,e,

5、c,b,a C. d,c,e,a,b D. a,b,c,d,e9 .一个所有非终端节点都有非空的左右子树的二叉树，叶子节点的个数为n,那么二叉树上的节点总数为（D ）A. 不确定 B . 2n C . 2n+1 D . 2n-110 .在排序算法中设置一个变量来记录排序过程中是否有元素交换存放位置，从而可以提前结束排序操作的是（A）。A. 冒泡排序B.归并排序C.简单插入排序D.简单选择排序11. 进程的状态是可以转换的，而以下哪个状态转换是不可能的（c ）。A.就绪执行B.执行就绪C.等待执行D.等待就绪A.并发性B.共享性C.虚拟性D.确定性13.临界资源是（b）。A.以同步关系使用的共享

6、资源B.以互斥关系使用的共享资源C.以共享关系使用的资源D.允许多个进程使用的共享资源14.进程由程序块、进程控制块和（AA.数据块B.作业C.文件D.设备15.作为编程人员，在程序设计中可以通过（A.命令接口B.作业调度C.进程调度D.系统调用16.下面哪一种说法对IP地址而言是正确的12.下面（d ）不是操作系统的特征。）三部分组成。D）获得操作系统服务。A. 它恰好分为两类B. 它包含一个长度固定的主机地址C. 它是层次结构的地址D. 它有48比特长17. 网络中ARP的作用是在给定D时找到A. 域名，IP地址B. 物理地址，IP地址C. IP地址，域名D. IP地址，物理地址18. 以

7、下哪种类型的寻址方式是专门为传输层所用的？CA. 物理地址B. IP地址C. 应用程序端口D. A 和 B19. 域名解析实现_BA. 域名到物理地址的解析B. 域名到IP地址的解析C. IP地址到物理地址的解析D. A 和 B20. 如果IP地址为22 ，则该工作站的子网掩码可能为：_CA. B. C. D.4021.在局域网中，计算机接收带有如下地址的帧DA.目标地址为广播地址B.目标地址为网络地址C.目标地址为该计算机硬件地址D.A和C22.以太网采用D来确定对传输介质的控制

8、A.令牌B.优先级C.先后次序D.载波侦听冲突检测23. 当数据链路层将帧从一条链路发送到另一条链路时，它检查DA.主机地址B.IP地址C.域名D.物理地址在这几个阶24. 在数据管理技术的发展过程中，经历了人工管理阶段，文件系统阶段和数据库系统阶段。段中，（C）是数据独立性最高的阶段A. 人工B. 文件系统C. 数据库系统D. 数据项管理25. 数据库中存储的是 CA. 数据B. 数据模型C. 数据以及数据之间的联系D. 信息26. 数据库的特点之一是数据的共享，严格的讲，这里的数据共享是指DA. 同一个应用中的多个程序共享一个数据集合B. 多个用户、同一种语言共享数据C. 多个用户共享一个

9、数据文件D. 多种应用、多种语言、多个用户相互覆盖地使用数据集合27. 关于数据库系统的正确叙述AA. 数据库系统减少了数据冗余B. 数据库系统避免了一切冗余C. 数据库系统中数据的一致性是数据类型的一致D. 数据库系统比文件系统能管理更多的数据28. 数据库管理系统（DBMS是：CA. 数学软件B. 应用软件C. 系统软件D. 操作系统的一部分29. 常见的数据模型有：DA.大型、中型、小型B. 数据、图形、多媒体C. 西文、中文、兼容D. 层次，网状、关系30. 下面那个协议是应用层协议DA. IPB. TCPC. UDPD. HTTP共36分）2、3、4、5依次进栈，在输出端得到序列32

10、451,给出应进行的各入栈和出栈Push 1; push 2; push 3; pop 3; pop 2; push 4; pop 4; push 5; pop 5; pop 1（每句 0.5分）2 .设单链表结点结构定义如下，现要在单链表中删除指针p所指结点的直接后继（此结点及其直接后继均存在），给出各操作语句。（5分）struct node int data;struct node *n ext;（1 分）（1分）（2 分）（1 分）struct node *q;q=p->n ext;p->n ext=p->n ext- >n ext;free（q）;（6分）3 给

11、出下图二叉树的先序、中序和后序遍历序列，其中左右子树的遍历先左后右。先:2,8, 12, 16,20,13,32,9,10中:12,16,8, 20,2,13,9,32,10后:16,12,20, 8,9,10,32,13,2精选资料，欢迎下载281312203216910（每个2 分）4 .以关键字序列（53, 12, 80, 64, 32, 92, 17, 75, 45, 26）为例，写出快速排序的各趟结 果。（8分）26 , 12, 45, 17, 32 53 92, 75, 64, 8017 , 12 26 45, 32 53 80, 75, 64 9212, 17,26,32,45,

12、53 64 , 75809212, 17,26,32,45,53, 64, 75,80,92（每趟2分）5.已知一个图的边集为（ 1, 2）,（ 1 , 4）,（ 1, 7）,（ 2 , 3）,（ 2 , 4）,（ 3 , 5）,（ 3 , 6）,（ 4 ,5）, （ 5 , 8）, （6 , 8）, （ 7 , 8） ,画出这张图的邻接矩阵和邻接表结构示意图，并给出从2开始的深度优先和广度优先遍历序列（邻接点编号小的先访问）。（8分）0101001010110000010011001100100000110001001000011000000100001110（2 分）（2 分）深度：2,

13、1, 4, 5, 3, 6, 8, 7（2 分）广度：2, 1, 3, 4, 7, 5, 6, 8（2 分）6 .已知有一组序列为 （17,26,38,27,46,72,82,93）,设哈希表长 m=14,哈希函数 H（key）=key%11。利用二次探测再散列处理冲突，建立哈希表。（4分）地址012345678910111213key4682263817277293（每个0.5分）四、编程题（共14分）对一个班级学生数学成绩进行管理：由给出的数据结构和初始化的按数学成绩递增有序的成绩表,编写程序：1. 完成插入一个学生数据的函数，要求插入操作后学生数据依然递增有序。要插入的学生数据为：stu

14、dyid: 21; name:王强；mathscore: 872. 完成主函数main:实现成绩表数据的初始化（调用给出的初始化函数：数据插入操作（调用第1题中编写的函数）并输出成绩表中的所有数据。（5分）initlist ）、实现成绩表（9分）#include "string.h"#defi ne STUDENTNUMBER 30/学生数据结构typedef struct int studyid;char n ame10;float mathscore;STUDENT;精选资料，欢迎下载/ 班级学生表结构 typedef structSTUDENT dataSTUDENT

15、NUMBER;int num;listtype;/ 初始化班级学生表中数据void initlist(listtype *p) p->data0.studeyid=10;strcpy(p->," 李一 "); p->data0.mathscore=82;p->data1.studeyid=2;strcpy(p->," 张二 "); p->data1.mathscore=85;p->data2.studeyid=5;strcpy(p->," 赵三 "); p->data2.mathscore=88;20 位*/*班级中按数学成绩递增有序的学生总共有p->num=20;void charu(listtype *p, STUDENT x) int i;for(i=p->num-1;p->datai.mathscore>=x.mathscore;i-) p->datai+1=p->datai;p-datai+1=x;p->num+;int main(