软件技术基础试题库.doc

一、填空（30分）： 1、 二维数组A10,20采用以行为主的方式存储，每个元素占一个存储单元，并且A1,1的存储地址是200，则A6,12的地址是_。2、 线性表、栈和队列都是_结构，栈的特点是_，队列的特点是_。3、 在一个长度为n的线性表中删除第i个元素(1in)时，需向前移动 个元素。4、 对分查找的存储结构仅限于_，且是_。5、 在双向链表中，每个结点有两个指针域，一个指向_，另一个指向_。6、 已知一个有向图的邻接矩阵表示，计算第i个结点的入度的方法是_。7、 已知某二叉树的前序遍历序列是“stuwv”，中序遍历序列是“uwtvs”，它的后序遍历序列是_。8、 下列程序段的时间复杂性是_。For i = 1 To nFor j = 1 To m A(i,j) = 09、 以数据集4，5，6，7，10，12，18为结点权值所构造的Huffman树的带权路径长度为_。10、n个顶点的连通图至少有 条边。11、数据结构被形式地定义为（D，R），其中D是_的有限集合，R是D上_的有限集合。12、 线性表的逻辑顺序与存储顺序总是一致的，这种说法是否正确，_。13、 数据结构的存储方式主要有_和_两种？它们之间的本质区别是_。14、 栈的操作方式是_，队列的操行方式是_。15、 数据的逻辑结构包括_、_和_三种类型。16、 在图形结构中，每个结点的前件结点数和后件结点数可以有_。17、 判定一个队列Q（最多元素为m0）为空队列的条件是_，为满队列的条件是_；判定一个循环队列Q（最多元素为m0）为空队列的条件是_，为满队列的条件是_。18、 已知某二叉树的后序遍历序列是“dabec”，中序遍历序列是“debac”，它的前序遍历序列是_。19、 如果对于给定的一组权值，所构造出的二叉树的带权路径长度最小，则称该树为 。20、 向一个长度为n的线性表的第i个元素（1in+1）之前插入一个元素时，需向后移动_个元素。21、 设栈S和队列Q的初始状态为空，元素a1、a2、a3、a4、a5和a6依次通过栈S，一个元素出栈后即进入队列Q，若6个元素出队的顺序是a2、a4、a3、a6、a5、a1，则栈的容量至少应该是_。 22、 二维数组A10,20采用以行为主的方式存储，每个元素占一个存储单元，并且A1,1的存储地址是200，则A6,12的地址是_。23、 线性表、栈和队列都是_结构，可以在线性表的_位置插入和删除元素；对于栈只能在_插入和删除元素；对于队列只能在_插入元素和_删除元素。24、 对分查找的存储结构仅限于_，且是_。25、 在双向链表中，每个结点有两个指针域，一个指向_，另一个指向_。27、对于长度为n的线性表，若进行顺序查找，则时间复杂性为O (n)，若采用二分查找法，则时间复杂性为O (log2n)，若采用分块法查找，时间复杂性介于 和 之间。28、二维数组A10,20采用以列为主的方式存储，每个元素占一个存储单元，并且A1,1的存储地址是200，则A6,12的地址是_。29、 在分块查找方法中首先查找_，然后再查找相应的_。 30、 一组序列为46、79、56、38、40、84，利用堆排序的方法建立的初始堆为_。31、 设循环队列的容量为50(序号从1到50),现经过一系列的入队和退队运算后,有front=20,rear=15,循环队列中有_个元素。32、 数据结构的存储方式主要有_和_两种,这两种存储结构的本质区别是_。 33、 将递归算法转换为非递归算法时,通常需要使用_来存储尚待处理的元素。34、 在无向图G的邻接矩阵A中,若Ai,j=1 , 则Aj,i 等于_。 35、 n个顶点的连通图至少有 条边。36、 已知一个图的邻接矩阵表示，删除所有从第i个结点出发的边的方法是 。（将矩阵第i行全部置为零）37、 若数据元素序列 (K1, K2, K3, , Kn) 是一个堆，则序列中元素的关系是_。38、 二叉树的前序遍历序列中,任何一个结点均处在其子女结点的前面，这种说法是否正确_；而对于中序遍历序列，这种说法是否正确_。39、 对于一个具有n个顶点的无向图，若采用邻接矩阵表示，则该矩阵的大小是_。40、 在一个双向链表的p结点之后插入s结点的操作是_。41、 设n行n列的下三角矩阵A已压缩到一维数组B1：n(n+1)/2中，若以行为主存储，则Ai , j ( i j ) 对应的B中的存储位置是_。40、有一个有序表为1，3，9，12，32，41，45，62，75，77，82，95，100，当用二 分查找法查找值为82的结点时，_次比较后查找成功。41、采用链式存储结构的有序表能否用二分查找法进行查找_。43、 排序方法中，从未排序序列中依次取出元素与已排序序列(初始为空)中的元素进行比较，将其放入已排序序列的正确位置上的方法，称为_。44、 一组序列为46、79、56、38、40、84，利用堆排序的方法建立的初始堆为_。48、下列程序段的时间复杂性是_。for i = 1 To n-1y=y+1for j = 1 To 2*n x = x + 149、下列程序段的时间复杂性是_。Sum=0 ;for i = 1 To np=1 ;for j = 1 To i p = p * j ; sum = sum + p ;49、数据逻辑结构可分为两大类，它们分别是 和 。50、数据结构的存储应存储两方面的内容，它们分别是 和 ；数据存 储结构也可分为两大类，它们分别是 和 。51、设栈S和队列Q的初始状态为空，元素a1、a2、a3、a4、a5、a6、a7和a8依次通过栈S，一个元素出栈后即进入队列Q，若8个元素出队的顺序是a4、a6、a5、a7、a3、 a2、a8、a1，则栈的容量至少应该是_。 52、线性表L=a1、a2、an，如删除表中任一元素的概率相同，则删除一个元素平均需要移动元素的个数是 。53、若二叉树前遍历访问结点顺序为abdgcefh，中序遍历访问结点顺序为dgbaechf，则其 后序遍历访问结点顺序为 。54、二维数组A10,20采用以列为主的方式存储，每个元素占一个存储单元，并且A1,1的存储地址是100，则A8,12的地址是_。55、 如要求一个线性表既能很快地查找，又能适应动态变化的要求，在分块查找法、顺序查找法和二分查找法中最好采用哪种方法_。 56、已知一个有向图的邻接矩阵表示，计算第i个结点的出度的方法是_。57、线性表的逻辑顺序与存储顺序总是一致的，这种说法是否正确 。58、设n行n列的下三角矩阵A已压缩到一维数组S1, n*(n+1)/2中，若按行为主存储，则Ai , j 对应的S中的存储位置是 。（ i*(i-1)/2+j ）59、有一个10阶对称矩阵A，采用压缩存储方式存储（以行为主存储，且A1,1=1），则A8,5的地址为 。 （ 33 ）60、在一个有向图中，所有顶点的入度之和等于所有顶点的出度之和的 倍。61、在一个具有n个顶点的无向图中，要连通全部顶点至少需要 条边。62、对于一个具有n个顶点的无向图，若采用邻接矩阵表示，则该矩阵的大小是 。63、根据所用数据模型的不同，数据库系统可以分为_、_、_三类。64、关系模型中，一个关系的_称为关系模式。65、在关系模型中，把数据库看成是一个二维表，每一个二维表称为一个_，表中每一行称为_，表中每一列称为_。66、E-R图称为_，它是用于描述数据库_的有效工具，用E-R图可以简单明了地描述_。67、关系数据库中有三种基本操作，从表中取出满足条件的属性的操作称为 ；从表中选出满足某种条件的元组的操作称为 ；将两个关系中具有共同属性值的元组连接到一起，构成新表称为 。68、假设学生关系为S（学号，姓名，性别），课程关系为C（课程号，课程名，教师），学生选课关系为SC（学号，课程号，分数），要查找选修“物理”课的男学生姓名，将涉及到关系 。69、在关系代数中，对一个关系做投影操作后，新关系的元组个数是“大于、小于、等于还是小于等于” 原来关系的元组个数。（小于等于）70、当分E-R图合并为初步E-R图时，可能会出现冲突，冲突可能会出现在那几个方面 。数据库管理系统（DBMS）是 。关系模型用 来表示实体本身及其相互之间的联系。在关系模型中，元组表示 ；属性表示 ；关系模式表示 。三、（20分）设线性表中的各元素均为实数，长度为n，且顺序存放在数组A(1：m)中，试编写下列算法：(1)、在线性表的第i个元素之前插入一个元素b；(2)、在线性表中删除第i个元素。四、（15分）设有一线性链表，试写出一个算法，找出链表中的最小值和最大值并输出，然后将它们从链表中删除。 五、（15分）设有一棵二叉排序树，头指针在TH中，编一算法在二叉排序树中查找值为“x”的结点，查到后打印出“x”的值，如查不到，则打印“无此结点”。 （20分）设L(1: n)是一个包含n个元素的有序表，写出用对分查找法查找元素x的算 法。（20分）写出逆序线性链表的算法。（15分）写出计算线性链表长度的算法，并考虑表为空的情况。（15分）编写链式存储结构下的冒泡排序算法。（20分）设有一个学生选修课程数据库，包括“学生”、“选修”和“课程”三个关系模式： 学生（学号，姓名，性别，年龄，系，电话） 选修（学号，课程号，分数） 课程（课程号，课程名，教师）现要求：（1）、查找年龄大于21岁的女同学的学号和姓名。（2）、查找所有成绩在80分及以上的学生姓名及所在的系。设有一数据库，包括供应商表S、零件表P、工程项目表J和供应情况表SPJ四个关系模式： S ( 供应商代码，供应商名，供应商电话，供应商所在的城市 )； P ( 零件代码，零件名，颜色，重量 )； J ( 工程项目代码，工程项目名，工程项目所在的城市 )； SPJ ( 供应商代码，零件代码，工程项目代码，供应量 )；其中供应量表示某供应商供应某种零件给某工程项目的数量。现要求：（1）、查找供应工程J1零件为红色的供应商代码；（2）、查找没有使用上海供应商生产的红色零件的工程项目代码。（20分）用简单插入排序法对有n个元素的线性表进行排序，写出其算法。（15分）依次输入序列（18、12、9、23、45、57、16、22），构造一棵二叉排序树。 若在这棵二叉排序树中寻找值为46的结点，需要比较多少次？（20分）有一个单链表，其结点的元素值以非递减有序排列，编写一个过程删除该单 链表中多余的元素值相同的结点。（20分）设L(1: n)是一个包含n个元素的有序表，写出用对分查找法查找元素x的算 法五、20分）已知一个单链表如图所示，编写一个过程将该单链表复制一个拷贝。a10Hana3a2有一个有序单链表（从小到大排列），表头指针为head，编写一个过程向该单链表中插入一个元素为x的结点，使插入后该链表仍然有序。设有一个产品生产管理系统，涉及到如下实体：工人：代号，姓名，工种，工资产品：产品代号，产品名，性能参数零件：零件代号，零件名，产地材料：材料代号，材料名，单价，库存量他们之间有如下关系：每个工人生产一种产品，每种产品可由不同的工人生产，每个工人生产产品的类型和数量登记在册；产品由某些零件和材料组成，一种产品可使用多种零