1中国石油大学数据结构试题及答案

1、数据结构试题一、 单选题1、 在数据结构的讨论中把数据结构从逻辑上分为 （ ） a 内部结构与外部结构 b 静态结构与动态结构 c 线性结构与非线性结构 d 紧凑结构与非紧凑结构。2、采用线性链表表示一个向量时，要求占用的存储空间地址（） a 必须是连续的 b 部分地址必须是连续的 c 一定是不连续的 d 可连续可不连续3、采用顺序搜索方法查找长度为n的顺序表时，搜索成功的平均搜索长度为（ ）。 a n b n/2 c (n-1)/2 d (n+1)/24、在一个单链表中，若q结点是p结点的前驱结点，若在q与p之间插入结点s，则执行（ ）。a slink = plink; plink = s;

2、 b plink = s; slink = q;c plink = slink; slink = p; d qlink = s; slink = p;5、如果想在4092个数据中只需要选择其中最小的5个，采用（ ）方法最好。 a 起泡排序 b 堆排序 c 锦标赛排序 d 快速排序 6、设有两个串t和p，求p在t中首次出现的位置的运算叫做（ ）。 a 求子串 b 模式匹配 c 串替换 d 串连接7、在数组a中，每一个数组元素aij占用3个存储字，行下标i从1到8，列下标j从1到10。所有数组元素相继存放于一个连续的存储空间中，则存放该数组至少需要的存储字数是（ ）。a 80 b 100 c 24

3、0 d 2708、将一个递归算法改为对应的非递归算法时，通常需要使用（ ）。a 栈 b 队列 c 循环队列 d 优先队列9、一个队列的进队列顺序是1, 2, 3, 4，则出队列顺序为（ ）。10、在循环队列中用数组a0.m-1 存放队列元素，其队头和队尾指针分别为front和rear，则当前队列中的元素个数是（ ）。 a ( front - rear + 1) % m b ( rear - front + 1) % mc ( front - rear + m) % m d ( rear - front + m) % m11、一个数组元素ai与（ ）的表示等价。a *（a+i） b a+i c

4、*a+i d &a+i 12、若需要利用形参直接访问实参，则应把形参变量说明为（ ）参数。a 指针 b 引用 c 值 d 变量13、下面程序段的时间复杂度为（ ） for (int i=0;i<m;i+) for (int j=0;j<n;j+) aij=i*j;a o(m2) b o(n2) c o(m*n) d o(m+n)14、下面程序段的时间复杂度为（ ） int f(unsigned int n) if(n= =0 | n= =1) return 1; else return n*f(n-1); a o(1) b o(n) c o(n2) d o(n !)15、线

5、性表若是采用链式存储结构时，要求内存中可用存储单元的地址( )。a 必须是连续的b   部分地址必须是连续的c 一定是不连续的d   连续或不连续都可以16、数据结构的定义为(d，s)，其中d是( )的集合。a 算法 b数据元素 c 数据操作 d 逻辑结构17、算法分析的目的是( )。a    找出数据结构的合理性b    研究算法中输入和输出的关系c    分析算法的效率以求改进d   分析算法的易懂性和文档性18、在一个单链表中，若p所指结点不是最后结点，在p之

6、后插入s所指结点，则执行( )。a s->link=p;p->link=s;b s->link=p->link;p->link=s;c s->link=p->link;p=s;d p->link=s;s->link=p;19、设单链表中结点结构为(data,link).已知指针q所指结点是指针p所指结点的直接前驱，若在*q 与*p之间插入结点*s，则应执行下列哪一个操作（ ）a s->link=p->link; p->link=s; b q->link=s; s->link=pc p->link

7、=s->link;s->link=p; d p->link=s; s->link=q;20、设单链表中结点结构为(data,link).若想摘除结点*p的直接后继，则应执行下列哪一个操作（ ）a p->link=p->link->link; b p=p->link; p->link=p->link->link;c p->link=p->link; d p=p->link->link;21、设单循环链表中结点的结构为（data,link）,且rear是指向非空的带表头结点的单循环链表的尾结点的指针。若想删除

8、链表第一个结点，则应执行下列哪一个操作（ d ）a s=rear; rear=rear->link; delete s; b rear=rear->link; delete rear; c rear=rear->link->link; delete rear; d s=rear->link->link; rear->link->link=s->link; delete s;s为第一个结点硫22、设单循环链表中结点的结构为（data,link）,且first为指向链表表头的指针，current为链表当前指针，在循环链表中检测current是否

9、达到链表表尾的语句是( d )。a current->link =null b first->link=currentc first=current d current->link=first？23、一个栈的入栈序列为a，b，c，则出栈序列不可能的是( c )。a     c,b,a b b,a,c c c,a,b d a,c,b24、栈的数组表示中，top为栈顶指针，栈空的条件是( a )。a    top=0 b top=maxsize c  top=maxsize d top=-125、栈和队列的共同

10、特点是( c )。a     都是先进后出 b 都是先进先出c    只允许在端点处插入和删除 d 没有共同点26、假定一个顺序存储的循环队列的队头和队尾指针分别为f和r ,则判断队空的条件为( d ).a f+1= =r b r+1= =f c f= =0 d f= =r27、当利用大小为n 的数组顺序存储一个队列时，该队列的最大长度为（ b ）a n-2 b n-1 c n d n+128、当利用大小为n 的数组顺序存储一个栈时，假定用top= =n 表示栈空，则向这个栈插入一个元素时，首先应执行（ ）语句修改top指针。a to

11、p+; b top-; c top=0; d top;29、设链式栈中结点的结构为（data, link）,且top是指向栈顶的指针。若想摘除链式栈的栈顶结点，并将被摘除结点的值保存到x中，则应执行下列（ a ）操作。a x=top->data; top=top->link; b top=top->link; x=top->data; c x=top; top=top->link; d x=top->data;30、设循环队列的结构是： const int maxsize=100; typedef int data type; typedef struct

12、data type datamaxsize; int front, rear; queue;若有一个queue类型的队列q，试问判断队列满的条件应是下列哪一个语句（ d ）a q.front= = q.rear; b q.front - q.rear= = maxsize; c q.front + q.rear= = maxsize; d q.front= = (q.rear+1)% maxsize;31、设有一个递归算法如下：int fact (int n ) if (n<=0) return 1;else return n*fact(n-1);下面正确的叙述是（ b ）a 计算fac

13、t(n) 需要执行n次递归 b fact(7)=5040 c 此递归算法最多只能计算到fact(8) d 以上结论都不对32、设有一个递归算法如下int x (int n) if (n<=3) return 1;else return x(n-2)+x(n-4)+1;试问计算 x(x(8)时需要计算（ d ）次x函数。a 8 次 b 9次 c 16次 d 18次33、设有广义表d(a,b,d),其长度为（ b ），深度为（ a ）a b 3 c 2 d 534、广义表a(a),则表尾为（ c ）a a b ( ) ) c 空表 d （a）35、下列广义表是线性表的有（ c ）a e（a,

14、(b,c)） b e(a,e) c e (a,b) d e(a,l( ) )36、递归表、再入表、纯表、线性表之间的关系为（ c ）a 再入表>递归表>纯表>线性表 b 递归表>线性表>再入表>纯表 c 递归表>再入表>纯表>线性表 d递归表>再入表>线性表>纯表37、某二叉树的前序和后序序列正好相反，则该二叉树一定是（b）的二叉树。a 空或只有一个结点 b 高度等于其结点数 c 任一结点无左孩子 d 任一结点无右孩子38、对于任何一棵二叉树t，如果其终端结点数为n0，度为2的结点为n2.,则( a )a n0= n2+1

15、 b n2= n0+1 c n0= 2n2+1 d n2=2n0+1 39、 由权值分别为11，8，6，2，5的叶子结点生成一棵哈夫曼树，它的带权路径长度为（b ）a 24 b 73 c 48 d 5340、已知一个顺序存储的线性表，设每个结点需占m个存储单元，若第一个结点的地址为da1,则第i 个结点的地址为（a）。a da1+(i-1)*m b da1+i*m c da1-i*m d da1+(i+1)*m41、34 具有35个结点的完全二叉树的深度为( a )a 5 b 6 c 7 d 842、对线性表进行折半搜索时，要求线性表必须（ c ）a 以链接方式存储且结点按关键码有序排列 b

16、以数组方式存储 c 以数组方式存储且结点按关键码有序排列 d以链接方式存储43、顺序搜索算法适合于存储结构为（ b ）的线性表。a 散列存储 b 顺序存储或链接存储 c 压缩存储 d 索引存储44、采用折半搜索算法搜索长度为n的有序表时，元素的平均搜索长度为（ c ）a o（n2） b o（n log2n） c o（log2n） d o（n）45、对于一个具有n个顶点和e条边的无向图，进行拓扑排序时，总的时间为( a )a n b n+1 c n-1 d n+e46、判断一个有向图是否存在回路，除了可以利用拓扑排序方法外，还可以利用（c ）。a 求关键路径的方法 b 求最短路径的dijkstr

17、a方法 c 深度优先遍历算法 d 广度优先遍历算法47、在10阶b-树中根结点所包含的关键码个数最多为（c ），最少为( a )a 1 b 2 c 9 d 1048、对包含n 个元素的散列表进行搜索，平均搜索长度为（ c ）a o（log2n） b o（n）c 不直接依赖于n d 上述都不对二、 填空题（）1、   数据的逻辑结构被分为集合结构、线性结构、树形结构、图形结构 四种 2、   数据的存储结构被分为顺序结构、链接结构、索引结构、散列结构 四种3、一种抽象数据类型包括（数据 ）和（操作 ）两个部分。4、 设有两个串

18、p和q，求p在q中首次出现的位置的运算称为（模式匹配） 5、    栈、队列逻辑上都是（线性存储）结构。6、 线性结构反映结点间的逻辑关系是（一对一）的，图中的数据元素之间的关系是（多对多）的，树形结构中数据元素间的关系是（一对多）的。7、栈中存取数据的原则（后进先出），队列中存取数据的原则（先进先出）8、串是由（零个或多个）字符组成的序列。（长度为零的串）称为空串，（由一个或多个空格组成的串）称为空格串。9、设目标串t=”abccdcdccbaa”,模式p=”cdcc”则第（6）次匹配成功。10、一维数组的逻辑结构是（线性结构），存储结构是（顺序存储表示）。对于二维数组，

19、有（行优先顺序）和（列优先顺序）两种不同的存储方式，对于一个二维数组amn,若采用按行优先存放的方式，则任一数组元素aij相对于a00的地址为（ n*i+j）。11、向一个顺序栈插入一个元素时，首先使（ 栈顶指针 ）后移一个位置，然后把待插入元素（ 写 ）到这个位置上。从一个顺序栈删除元素时，需要前移一位（栈顶指针）。12、在一个循环队列q中，判断队空的条件为（q.front= =q.rear）, 判断队满的条件为（ (q.rear+1)%maxsize= =q.front ）13、对于一棵具有n个结点的树，该树中所有结点的度数之和为（ n-1 ）。14、一棵高度为5的满二叉树中的结点数为（

20、63 ）个，一棵高度为3满四叉树中的结点数为（ 85 ）个。15、若对一棵二叉树从0开始进行结点编号，并按此编号把它顺序存储到一维数组中，即编号为0的结点存储到a0中，其余类推，则ai元素的左子女结点为（ 2*i+1），右子女结点为（ 2*i+2 ），双亲结点（i>=1 ）为（(i-1)/2 ）.16、在一个最大堆中，堆顶结点的值是所有结点中的（最大值），在一个最小堆中，堆顶结点的值是所有结点中的（最小值）。17、已知具有n个元素的一维数组采用顺序存储结构，每个元素占k个存储单元，第一个元素的地址为loc(a1)，那么，loc(ai)= loc(a1)+(i-1)*k 。18、

21、在霍夫曼编码中，若编码长度只允许小于等于4,则除掉已对两个字符编码为0和10外，还可以最多对（ 4 ）个字符编码。19、设高度为h的空二叉树的高度为-1，只有一个结点的二叉树的高度为0，若设二叉树只有度为2上度为0的结点，则该二叉树中所含结点至少有（2h+1）个。20、由一棵二叉树的前序序列和（中序序列）可唯一确定这棵二叉树。 21、以折半搜索方法搜索一个线性表时，此线性表必须是（顺序）存储的（有序）表。22、已知完全二叉树的第8层有8个结点，则其叶子结点数是（68）。若完全二叉树的第7有10个叶子结点，则整个二叉树的结点数最多是（235）23、对于折半搜索所对应的判定树，它既是一棵（二叉搜索

22、树），又是一棵（理想平衡树）。24、假定对长度n=50的有序表进行折半搜索，则对应的判定树高度为（），判定树中前层的结点数为（），最后一层的结点数为（）。25、在一个无向图中，所有顶点的度数之和等于所有边数的（）倍。在一个具有n个顶点的无向完全图中，包含有（ n(n-1)/2 ）条边，在一个具有n个顶点的有向完全图中，包含有（ n(n-1) ）条边。26、对于一个具有n个顶点和e条边的连通图，其生成树中的顶点数和边数分别为（n）和（n-1）。27、设线性表中元素的类型是实型，其首地址为1024，则线性表中第6个元素的存储位置是( 1044)。28、在插入和选择排序中，若初始数据基本正序，则选择

23、（插入排序），若初始数据基本反序，则最好选择（选择排序）。29、算法是对特定问题的求解步驟的一种描述，它是（指令）的有限序列，每一条（指令）表示一个或多个操作。30、对于一个具有n个顶点肯e 条边的无向图，进行拓朴排序时，总的进间为（n）31、构造哈希函数有三种方法，分别为(平方取中)法、(除留余数)法、(折迭移位)法。32、处理冲突的三种方法，分别为(线性探测)、（ 随机探测 ）、（ 链地址法）。33、对于含有n个顶点和e条边的无向连通图，利用普里姆算法产生的最小生成树，其时间复杂度为（ （n2） ）、利用克鲁斯卡尔算法产生的最小生成树，其时间复杂度为（elog2e） ）34、快速排序在平均

24、情况下的时间复杂度为（nlog2n），在最坏情况下的时间复杂度为（n2）；快速排序在平均情况下的空间复杂度为（log2n），在最坏情况下的空间复杂度为（n）。35、假定一组记录的排序码为（，），对其进行归并排序的过程中，第二趟排序后的结果是（）36、假定一组记录的排序码为（，），对其进行快速排序的第一次划分的结果是（）。37、一个结点的子树的（ 个数 ）称为该结点的度。度为（ 零 ）的结点称为叶结点或终端结点。度不为（ 零 ）的结点称为分支结点或非终端结点。树中各结点度的（ 最大值 ）称为树的度。38、设ki=kj (1<=i<=n, 1<=j<=n,j<>

25、i)且在排序前的序列中ri领先于rj (i<j),若排序后的序列中ri仍领先于rj，则这种排序方法是（稳定的），反之是（不稳定的）。40 、在堆排序的过程中，对任一分支结点进行调整运算的时间复杂度为（log2n），整个排序过程的时间复杂度为（nlog2n）。41、在索引表中，每个索引项至少包含有（关键码值）域和（子表地址）域这两项。42、假定一个线性表为（”abcd”,”baabd”,”bcef”,”cfg”,”ahij”,”bkwte”,”ccdt”,”aayb”）,若按照字符串的第一个字母进行划分，使得同一个字母被划分在一个子表中，则得到的a,b,c三个子表的长度分别为（），（），（

26、）。43、对于包含个关键码的阶b-树，其最小高度为（），最大高度为（）。44、从一棵b-树删除关键码的过程，若最终引起树根结点的合并，则新树比原树的高度（减）45、假定要对长度n=100的线性表进行散列存储，并采用开散列法处理冲突，则对于长度m=20的散列表，每个散列地址的同义词子表的长度平均为（）。46、在散列存储中，装载因子又称为装载系数，若用m表示散列表的长度，n表示待散列存储的元素的个数，则等于（n/m）。47、在有向图的邻接矩阵中，第i行中“1”的个数是第i个顶点的（出度），第i列中“1”的个数是第i个顶点的（入度）。在无向图的邻接矩阵中，第i行（列）中“1”的个数是第i个顶点的（度

27、），矩阵中“1”的个数的一半是图中的（边数）。48、在对m阶b-树中，每个非根结点的关键码数最少为（m/2-1）个，最多为（m-1）个，其子树棵数最少为（m/2），最多为（m）。三、 判断题四、运算应用题 1、在一个有n个元素的顺序表的第i个元素（1 £ i £ n）之前插入一个新元素时，需要向后移动多少个元素？答案：需要向后移动 n- i + 1个元素2、 当一个栈的进栈序列为1234567时，可能的出栈序列有多少种？6457321是否是合理的出栈序列？答案： 可能的出栈序列有种，6457321不是合理的出栈序列。4、设有序顺序表为 10, 20, 30, 40, 50,

28、 60, 70 ，采用折半搜索时，搜索成功的平均搜索长度是多少？答案： aslsucc = (1*1 + 2*2 + 3*4 ) / 7 = 17 / 75、 在结点个数为n(n>1)的各棵树中，高度最小的树的高度是多少？它有多少个叶结点？多少个分支结点？高度最大的树的高度是多少？它有多少个叶结点？多少个分支结点？答案：结点个数为n时，高度最小的树的高度为1，有2层；它有n-1个叶结点，1个分支结点；高度最大的树的高度为n-1,有n层；它有1个叶结点，n-1个分支结点。6、 一棵高度为h的满k叉树有如下性质: 第h层上的结点都是叶结点, 其余各层上每个结点都有k棵非空子树, 如果按层次自

29、顶向下, 同一层自左向右, 顺序从1开始对全部结点进行编号, 试问:(1) 各层的结点个数是多少?(2) 编号为i的结点的父结点(若存在)的编号是多少?(3) 编号为i的结点的第m个孩子结点(若存在)的编号是多少?(4) 编号为i的结点有右兄弟的条件是什么? 其右兄弟结点的编号是多少?(5) 若结点个数为 n, 则高度h是n 的什么函数关系?答案：（1）各层的结点个数是ki (i=0,1,2,.,h)（2）编号为i的结点的父结点(若存在)的编号是 (i+k-2)/k（3）编号为i的结点的第m个孩子结点(若存在)的编号是(i-1)*k+m+1（4）当(i-1)%k<>0时有右兄弟，

30、右兄弟的编号为 i+1（5）若结点个数为 n ，则高度h和n 的关系为：h=logk(n*(k-1)+1)-1 (n=0时h=-1)9、题目：11、将下面的森林变换成二叉树（7分）。acdbfekjghiacdbfekjghi答案：10、将算术表达式 (a+b)+c*(d+e)+f)*(g+h) 转化为二叉树。（7分）*+f+*+cbahgde答案：12、 将给定的图简化为最小的生成树，要求从顶点1出发。（7分）13254768515310122796 答案: 1325476515362713、某子系统在通信联络中只可能出现8种字符，其出现的概率分别为0.05，0.29，0.07，0.08，0

31、.14，0.23，0.03，0.11试设计赫夫曼编码。答案： 为方便起见，设各种字符的权值w=5,29,7,8,14,23,3,11。因为n=8，所以要构造的赫夫曼树共有m=2n-1=2*8-1=15个结点。生成的赫夫曼树为下图所示：23115329147800000001111111赫夫曼编码为：概率为0.23的字符编码为：00概率为0.11的字符编码为：010概率为0.05的字符编码为：0110概率为0.03的字符编码为：0111概率为0.29的字符编码为：10 概率为0.14的字符编码为：110 概率为0.07的字符编码为：1110 概率为0.08的字符编码为：111114、已知一棵二叉树的前序遍历的结果是abecdfghij, 中序遍历的结果是ebcdafhigj, 试画出这棵二叉树，并给出这棵二叉树的后序遍历序列。abfgecdhji、答案：根据前序序列和中序序列能得到唯一的二叉树，所得二叉树如图： 这棵二叉树的后序遍历序列为：edcbihjgfa15、在结点个数为n(n>1)的各棵树中，高度最小的树的高度是多少？它有多少个