您好,欢迎访问三七文档
当前位置:首页 > 行业资料 > 能源与动力工程 > 数据结构试卷3数组和广义表
题目部分,(卷面共有95题,608.0分,各大题标有题量和总分)一、单项选择题(22小题,共44.0分)(2分)[1]设有一个10阶的对称矩阵A,采用压缩存储方式,以行序为主存储,a11为第一元素,其存储地址为1,每个元素占一个地址空间,则a85的地址为A、13B、33C、18D、40(2分)[2]二维数组A的每个元素是由6个字符组成的串,其行下标i=0,1,…,8,列下标j=1,2,…,10。若A按行先存储,元素A[8,5]的起始地址与当A按列先存储时的元素()的起始地址相同。设每个字符占一个字节。A、A[8,5]B、A[3,10]C、A[5,8]D、A[0,9](2分)[3]已知广义表:A=(a,b),B=(A,A),C=(a,(b,A),B),求下列运算的结果:tail(head(tail(C)))=A、(a)B、AC、aD、(b)E、bF、(A)(2分)[4]下面说法不正确的是A、广义表的表头总是一个广义表B、广义表的表尾总是一个广义表C、广义表难以用顺序存储结构D、广义表可以是一个多层次的结构(2分)[5]设广义表L=((a,b,c)),则L的长度和深度分别为A、1和1B、1和3C、1和2D、2和3(2分)[6]广义表((a,b,c,d))的表头是(),表尾是A、aB、bC、(a,b,c,d)D、(b,c,d)(2分)[7]广义表运算式Tail(((a,b),(c,d)))的操作结果是A、(c,d)B、c,dC、((c,d))D、d(2分)[8]已知广义表LS=((a,b,c),(d,e,f)),运用head和tail函数取出LS中原子e的运算是A、head(tail(LS))B、tail(head(LS))C、head(tail(head(tail(LS)))D、head(tail(tail(head(LS))))(2分)[9]对稀疏矩阵进行压缩存储目的是A、便于进行矩阵运算B、便于输入和输出C、节省存储空间D、降低运算的时间复杂度(2分)[10]数组A[0..4,-1..-3,5..7]中含有元素的个数A、55B、45C、36D、16(2分)[11]设二维数组A[1..m,1..n](即m行n列)按行存储在数组B[1..m*n]中,则二维数组元素A[i,j]在一维数组B中的下标为A、(i-1)*n+jB、(i-1)*n+j-1C、i*(j-1)D、j*m+i-1(2分)[12]A[N,N]是对称矩阵,将下面三角(包括对角线)以行序存储到一维数组T[N(N+1)/2]中,则对任一上三角元素a[i][j]对应T[k]的下标k是A、i(i-1)/2+jB、j(j-1)/2+iC、i(j-i)/2+1D、j(i-1)/2+1(2分)[13]广义表A=(a,b,(c,d),(e,(f,g))),则下面式子的值为Head(Tail(Head(Tail(Tail(A)))))A、(g)B、(d)C、cD、d(2分)[14]对于以行为主序的存储结构来说.在数组A[c1..d1,c2..d2]中,c1和d1分别为数组A的第一维下标的下、上界,c2和d2分别为第二维下标的下、上界.每个数据元素占k个存储单元,二维数组中任一元素a[i,j]的存储位置可由()确定。A、Loc[i,j]=[(d2-c2+1)(i-c1)+(j-c2)]×kB、Loc[i,j]=[Loc[c1,c2]+[(d2-c2+1)(i-c1)+(j-c2)]×kC、Loc[i,j]=A[c1,c2]+[(d2-c2+1)(i-c1)+(j-c2)]×kD、Loc[i,j]=Loc[0,0]+[(d2-c2+1)(i-c1)+(j-c2)]×k(2分)[15]二维数组A的每个元素是由6个字符组成的串,其行下标i=0、1、…、8.列下标i=1、2、…、10。若A按行先存储,元素A[8,5]的起始地址与当A按列先存储时的元素()的起始地址相同。设每个字符占一个字节。A、A[8,5]B、A[3,10]C、A[5,8]D、A[0,9](2分)[16]若广义表A满足Head(A)=Tail(A),则A为A、()B、(())C、((),())D、((),(),())(2分)[17]将一个A[l..100,1...100]的三角矩阵,按行优先存入一维数组B[1...298]中,A中素(即该元素下标i=66,j=65)在B数组中的位置k为A、198B、195C、197(2分)[18]已知广义表L=((x,y,z),a,(u,t,w)),从L表中取出原子项t的运算是A、head(tail(tail(L)))B、tail(head(head(tail(L))))C、head(tail(head(tail(L))))D、head(tail(head(tail(tail(L)))))(2分)[19]设有一个10阶的对称矩阵A,采用压缩破除计方式,以行序为主存储,a1,1为第一个元素,其存储地址为1,每个元素占1个地址空间,则a8,5的地址为。A、13B、33C、18D、40(2分)[20]用数组r存储静态链表,结点的next域指向后继,工作指针j指向链中结点,使j沿链移动的操作为。A、j=r[j].nextB、j=j+1C、j=j-nextD、j=r[j]-next(2分)[21]稀疏矩阵一般的压缩存储方法有两种,即。A、二维数组和三维数组B、三元组和散列C、三元组和十字链表D、散列和十字链表(2分)[22]数组的基本操作主要包括。A、建立与删除B、索引与修改C、访问与修改D、访问与索引二、算法设计题(35小题,共449.0分)(10分)[1]给定一个整数数组b[0..N-1],6中连续的相等元素构成的子序列称为平台。试设计算法,求出b中最长平台的长度。(12分)[2]给定有m个整数的递增有序数组a[l..m]和有n个整数的递减有序数组b[l..n],试写出算法将数组a和b归并为递增有序数组c[1..m+n]。(要求算法的时间复杂度为o(m+n)(12分)[3]试编写建立广义表存储结构的算法,要求在输入广义表的同时实现判断、建立。设广义表如下形式输入(a1,a2,a3…,)n==0,其中或为单字母表示的原子或为广义表,n=0时为只含空格字符的空表。(10分)[4]设有大小不等的n个数据组(n个数据组中数据的总数为m)顺序存放在空间区D内,每个数据占据一个存储单元。数据组的首地址由数组S给出(如下图所示),试编写将新数据x插入到第i个数据组的末尾且属于第i个数据组的算法,插入后,空间区D和数组S的相互关系仍保持正确。(15分)[5]试设计一个不带回溯的稀疏矩阵(用三元组表存储)转置算法(18分)[6]编写子程序,将一维数组A[1:n×n](n≤10)中的元素.按蛇形方式存放在一维数组B[1:n,1:n]中。B(1,1)=A(1),B(1,2)=A(2),B(2,1)=A(3),B(3,1)=A(4)B(2,2)=A(5),B(1,3)=A(6),......依此类推,如下图所示。(12分)[7]设一系列正整数存放在一个数组中,试设计算法,将所有奇数存放在数组的前半部分,将所有的偶数存放在数组的后半部分。要求尽可能少用临时存储单元并使时间最少。(15分)[8]试设计一个算法,将数组A[0…n-1]中的元素循环右移k行.并要求只用一个元素大小的存储空间,元素移动或交换的次数为0(n)(18分)[9]试设计一算法,输入一个有m行n列的整数矩阵,然后将每一行的元素按非递减次序输出例如,若输入435629812871238则输出:23456l288912378(21分)[10]已知A[n]为整数数组,试写出实现下列运算的递归算法:(1)求数组A中的最大整数。(2)求n个整数的和。(3)求n个整数的平均值。(15分)[11]假设稀疏矩阵A和B均以三元组顺序表作为存储结构。试写出满足以下条件的矩阵相加的算法:假设三元组顺序表A的空间足够大,将矩阵B加到矩阵A上,不增加A,B之外的附加空间,你的算法能否达到O(m+n)的时间复杂度?其中m和n分别为矩阵A,B中非零元的数目。(20分)[12]假设稀疏矩阵A和B均以三元组顺序表作为存储结构。试写出矩阵相加的算法,另设三元组表C存放结果矩阵。(15分)[13]若将稀疏矩阵A的非零元素以行序为主序的顺序存于一维数组V中,并用二维数组B表示A中的相应元素是否为零元素(以0和1分别表示零元素和非零元素)。试写一算法,实现在上述表示法中实现矩阵相加的运算。并分析你的算法的时间复杂度。(10分)[14]试编写一个以三元组形式输出用十字链表表示的稀疏矩阵中非零元素及其下标的算法。(16分)[15]三元组顺序表的另一种变型是,不存矩阵元素的行、列下标,而存非零元在矩阵中以行为主序时排列的顺序号,即在LOC(0,0)=1,l=1时按教科书5.2节中公式(5-2)计算出的值。试写一算法,由矩阵元素的小标值i,j求元素的值。(10分)[16]试编写算法,依次从左至右输出广义表中第l层的原子项。(10分)[17]试编写递归算法,逆转广义表中的数据元素。(9分)[18]试编写递归算法,输出广义表中所有原子项及其所在层次。(10分)[19]试编写判别两个广义表是否相等的递归算法。(21分)[20]已知f为单链表的表头指针,链表中存储的都是整型数据,试写出实现下列运算的递归算法:(1)求链表中的最大整数。(2)求链表的结点个数。(3)求所有整数的平均值。(14分)[21]设在初始状态下在国际象棋棋盘上没有任何棋子(皇后)。然后顺序在第1行,第2行,…。第8行上布放棋子。在每一行中有8个可选择位置,但在任一时刻,棋盘的合法布局都必须满足3个限制条件,即任何两个棋子不得放在棋盘上的同一行、或者同一列、或者同一斜线上。试编写一个递归算法,求解并输出此问题的所有合法布局。(提示:用回溯法。在第n行第j列安放一个棋子时,需要记录在行方向、列方向、正斜线方向、反斜线方向的安放状态,若当前布局合法,可向下一行递归求解,否则可移走这个棋子,恢复安放该棋子前的状态,试探本行的第j+1列。)(12分)[22]【背包问题】设有一个背包可以放入的物品的重量为s,现有n件物品,重量分别为w[1],w[2],…,w[n]。问能否从这n件物品中选择若干件放入此背包中,使得放入的重量之和正好为s。如果存在一种符合上述要求的选择,则称此背包问题有解(或称其解为真);否则称此背包问题无解(或称其解为假)。试用递归方法设计求解背包问题的算法。(提示:此背包问题的递归定义如下:)(18分)[23]已知Ackerman函数定义如下:(1)根据定义,写出它的递归求解算法;(2)利用栈,写出它的非递归求解算法。(14分)[24]编写一个算法frequency,统计在一个输入字符串中各个不同字符出现的频度。用适当的测试数据来验证这个算法。(10分)[25]设整数x1,x2,…,xN已存放在数组A中,编写一PASCAL递归过程,输出从这n个数中取出所有k个数的所有组合(k=n)。例:若A中存放的数是1,2,3,4,5,k为3,则输出结果应为:543,542,541,532,531,521,432,431,421,321。类似本题的另外叙述有:(1)题目基本相同,只是叙述不同,要求用PASCAL语言。(10分)[26]设A[1..100]是一个记录构成的数组,B[1..100]是一个整数数组,其值介于1至100之间,现要求按B[1..100]的内容调整A中记录的次序,比如当B[1]=ll时,则要求将A[1]的内容调整到A[11]中去。规定可使用的附加空间为O(1)。(9分)[27]设数组A[1..n]中,A[n-2k+1..n-k]和[n-k+1..n]中元素各自从小到大排好序,试设计一个算法使A[n-2k+1..n]按从小到大次序排好序。并分析算法所需的计算时间。(8分)[28]广义表GL=(a1,a2,…,an),其中ak(k=1,2,...,n)或是单个数据元素(原子),或仍然是个广义表。给定如下有关广义表的
本文标题:数据结构试卷3数组和广义表
链接地址:https://www.777doc.com/doc-2429519 .html