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

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

2、ink = p link ;pf link = s;Bpf link = s;sf link = q;Cpf link = sf link ; sf link = p;D qflink = s;sflink = 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。所有数组

3、元素相继存放于一 个连续的存储空间中 ,则存放该数组至少需 要的存储字数是（ ）。A 80B 100 C 240D 2708、将一个递归算法改为对应的非递归算法 时 ,通常需要使用（ ）。A 栈B 队列 C 循环队列D 优先队列9、 一个队列的进队列顺序是1, 2, 3, 4, 则出队列顺序为（ ）。 10、在循环队列中用数组 A0. m-1 存放队 列元素，其队头和队尾指针分别为 front 和 rear ，则当前队列中的元素个数是 （ ）。A(front- rear+ 1) %mB(rear -front+ 1) %mC(front- rear+ m) %mD(rear -front+ m

4、) %m11、一个数组元素 ai 与（ ）的表示 等价。A * （a+i） B a+i C *a+iD &a+i12、若需要利用形参直接访问实参，则应把 形参变量说明为（ ）参数。A 指针 B 引用 C 值 D 变量13、下面程序段的时间复杂度为（）for （int i=0;i<m;i+）for (int j=0;j<n;j+) aij=i*j;22A O(m 2)B O(n 2)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(

5、n-1);A O(1) B O(n) C O(n2)D O(n !)15、线性表若是采用 链式存储结构 时，要求 内存中可用存储单元的地址 ( ) 。A 必须是连续的B 部分地址必须是连续的C 一定是不连续的D 连续或不连续都可以16、数据结构的定义为(D ,S)，其中D是() 的集合。A 算法B 数据元素 C 数据操作 D 逻辑结构17、算法分析的目的是 ()。A 找出数据结构的合理 性B 研究算法中输入和输出的关系C 分析算法的效率以求改进D 分析算法的易懂性和文档性18、在一个单链表中，若 p 所指结点不是最 后结点，在 p 之后插入 s 所指结点，则执行 ( ) 。A s->li

6、nk=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=s->link; s->link=

7、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; deletes;B rear=rear->link; delete rear;C rear=rear->link->link; deleterear;D s=rear->link->link;rear->link->link=s->link; delete s; s 为第一个结点硫22 、 设 单 循 环 链 表 中 结 点 的 结 构 为 (data,link ), 且 first 为指向链表表头的 指针， current 为链表当前指针，在循

9、环链 表中 检测 current 是否达到链表表尾的语句是 ( D ) 。=null BA current->link first->link=currentC first=current 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=-1 25、栈和队列的共同特点是 ( C ) 。

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

11、结点的结构为 （ 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;Dx=top->data;30、设循环队列的结构是：const int Maxsize=100;typedef int Data Type; typedef struct Data Type dataMaxsize;Int front

12、, rear; Queue;若有一个Queue类型的队列Q试问判断队 列满的条件应是下列哪一个语句( D )A Q.front= = Q.rear;BQ.front - Q.rear= = Maxsize;C Q.front + Q.rear= = Maxsize;DQ.front= = (Q.rear+1)% Maxsize;31、设有一个递归算法如下： int fact (int n ) if (n<=0) return 1; else return n*fact(n-1); 下面正确的叙述是( B )A 计算 fact(n) 需要执行 n 次递归B fact(7)=5040C 此递

13、归算法最多只能计算到 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 次 C16 次 D 18 次33、设有广义表 D(a,b,D), 其长度为( B )， 深度为( A )A gB 3C 2D 534、广义表 A(a), 则表尾为( C )A a B ( ) ) C 空表D ( a )35、下列广义表是线性表的有( C ) A E ( a,(b,c) ) B E(a,E) C E

14、 (a,b) D E(a,L( ) )36、递归表、再入表、纯表、线性表之间的 关系为( C )A 再入表 递归表 纯表 线性表B递归表 线性表 再入表 纯表C 递归表 再入表 纯表 线性表D 递归表 再入表 线性表 纯表37、某二叉树的前序和后序序列正好相反，则该二叉树一定是(B)的二叉树。A空 或 只有一个结点B 高度等于其结点数C任 一 结点无左孩子D 任一结点无右孩子38、对于任何一棵二叉树T,如果其终端结点数为n。,度为2的结点为n2.,则（A ）A n 0= n 2+1 B n 2= n 0+1 C n 0= 2n 2+1D n2=2n0+139、 由权值分别为 11，8，6，2，

15、5 的叶子 结点生成一棵哈夫曼树，它的带权路径长度 为（ B ）A 24 B 73 C48 D 5340、已知一个顺序存储的线性表，设每个结点需占m个存储单元，若第一个结点的地址为 da1, 则第 I 个结点的地址为（ A ）。A da1+（I-1）*mB da1+I*mC da1-I*mD da1+（I+1）*m41、34 具有 35 个结点的完全二叉树的深度 为 （ A ）A 5 B 6 C 7 D 842、对线性表进行折半搜索时，要求线性表 必须（ C ）A 以链接方式存储且结点按关键码有序排列 B 以数组方式存储C 以数组方式存储且结点按关键码有序排列 D 以链接方式存储43、顺序搜索

16、算法适合于存储结构为 （ B ）的线性表。A 散列存储 或链接存储B顺序存储C 压缩存储D索引存储44、采用折半搜索算法搜索长度为n 的有序表时，元素的平均搜索长度为（C ）2A O （ n2）B O （n log 2n） CO（ log 2n） D O （ n）45、对于一个具有 n 个顶点和 e 条边的无向 图，进行拓扑排序时，总的时间为 （ A ） A n B n+1 C n-1D n+e46、判断一个有向图是否存在回路，除了可 以利用拓扑排序方法外，还可以利用（C ）A 求关键路径的方法 B 求最短路径的 Dijkstra 方法C 深度优先遍历算法 D 广 度优先遍历算法47、在10阶

17、B-树中根结点所包含的关键码 个数最多为（ C ），最少为 （ A ）A 1B 2C 9D 1048、对包含n个元素的散列表进行搜索，平 均搜索长度为（C ）A O （log 2n）B O（n）C 不直接依赖于n D上述都不对二、填空题（1、 数据的逻辑结构被分为集合结构、线性结构、树形结构、图形结构四种2、 数据的存储结构被分为顺接结构、索弓丨结构、散列结构四种3、一种抽象数据类型包括（数据 ）和（操 作）两个部分。4、设有两个串p和q,求p在q中首次出 现的位置的运算称为（模式匹配）5、栈、队列逻辑上都是（线性存储）结 构。6、线性结构反映结点间的逻辑关系是（一 对一）的，图中的数据元素之

18、间的关系是（多对多）的，树形结构中数据元素间的 关系是（一对多）的。7、栈中存取数据的原则（后进先出），队列中存取数据的原则（先进先出 ）8、 串是由（零个或多个）字符组成的序 列。（长度为零的串）称为空串，（由 一个或多个空格组成的串）称为空格串。9、设目标串 T=” abccdcdccbaa ” ,模式 P=” cdcc”则第（6）次匹配成功。10、一维数组的逻辑结构是（线性结构）， 存储结构是（顺序存储表示）。对于二维数 组，有（行优先顺序）和（列优先顺序）两 种不同的存储方式，对于一个二维数组 Am n,若采用按行优先存放的方式，则任 一数组元素Aij 相对于A00的地址 为（n*i+

19、j ）。11、向一个顺序栈插入一个元素时，首先使（栈顶指针）后移一个位置，然后把待插 入元素（写）到这个位置上。从一个顺序 栈删除元素时，需要前移一位（栈顶指针）。12、在一个循环队列 Q中，判断队空的条件为（Q.front= =Q.rear ）,判断队满的条件 为（Q.rear+1）%MaxSize= =q.fro nt）13、对于一棵具有n个结点的树，该树中所有结点的度数之和为（n-1）。14、一棵高度为5的满二叉树中的结点数为（63 ）个，一棵高度为 3满四叉树中的 结点数为（85）个。15、若对一棵二叉树从0开始进行结点编号，并按此编号把它顺序存储到一维数组中，即 编号为0的结点存储到

20、a0中，其余类推， 则ai元素的左子女结点为（2*i+1），右子女结点为（2*i+2），双亲结点（i>=1）为（i-1）/2 n ）.16、在一个最大堆中，堆顶结点的值是所有 结点中的（最大值），在一个最小堆中，堆 顶结点的值是所有结点中的（最小值）。17、已知具有n个元素的一维数组采用顺序 存储结构，每个元素占k个存储单元，第一个元素的地址为L0C（a1），那么，LOC（ai）= L0C（a1）+（i-1）*k。18、在霍夫曼编码中，若编码长度只允许小于等于4,则除掉已对两个字符编码为0和10夕卜，还可以最多对（4）个字符编码。19、 设高度为h的空二叉树的高度为-1，只 有一个结点的

21、二叉树的高度为0,若设二叉树只有度为2上度为0的结点，则该二叉树 中所含结点至少有（2h+1）个。20、由一棵二叉树的前序序列和 （中序序列） 可唯一确定这棵二叉树。21、以折半搜索方法搜索一个线性表时，此 线性表必须是（顺序）存储的（有序）表。22、已知完全二叉树的第 8 层有 8 个结点， 则其叶子结点数是（ 68）。若完全二叉树的 第 7 有 10 个叶子结点，则整个二叉树的结 点数最多是（ 235）23、对于折半搜索所对应的判定树，它既是 一棵（二叉搜索树） ，又是一棵（理想平衡 树）。24、假定对长度 n=50 的有序表进行折半搜 索，则对应的判定树高度为（5），判定树中前5层的结点

22、数为（31），最后一 层的结点数为（19）。25、在一个无向图中，所有顶点的度数之和等于所有边数的（2）倍。在一个具有n个顶点的无向完全图中， 包含有（ n（n-1）/2）条边，在一个具有 n 个顶点的有向完全图中， 包含有（ n（n-1） ）条边。26、对于一个具有 n 个顶点和 e 条边的连通 图，其生成树中的顶点数和边数分别为（ n） 和（ n-1 ）。27、设线性表中元素的类型是实型，其首地 址为 1024，则线性表中第 6 个元素的存储位 置是（ 1044） 。28、在插入和选择排序中，若初始数据基本 正序，则选择（插入排序） ，若初始数据基 本反序，则最好选择（选择排序） 。29、

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

24、（ nlog 2n） ） ，在最坏情况下的时间复 杂度为（0（ n2）;快速排序在平均情况 下的空间复杂度为(0( log 2n),在最坏 情况下的空间复杂度为(0( n)。35、假定一组记录的排序码为 ( 4 6,7 9,56.38.40.80) ，对其进行归并排序的过程中，第二趟排序后的结果是(3 84656794080)36、假定一组记录的排序码为 (46,79,56.38.40.80) ,对其进行快速排序的第一次划分的结果是( 384046567980)。37、 一个结点的子树的(个数 )称为该结点的度。度为( 零)的结点称为叶结点或终端结点。度不为( 零 )的结 点称为分支结点或非终

25、端结点。树中各结点 度的( 最大值 )称为树的度。38、设 Ki=Kj (1<=i<=n, 1<=j<=n,j<>i) 且在 排序前的序列中 Ri 领先于 Rj (i<j), 若排序 后的序列中R仍领先于R，则这种排序方法 是(稳定的) ,反之是(不稳定的) 。40 、在堆排序的过程中,对任一分支结点 进行调整运算的时间复杂度为 (0( log 2n), 整个排序过程的时间复杂度为(0( nlog 2n)。41、在索引表中， 每个索引项至少包含有 （关 键码值）域和（子表地址）域这两项。42、假定一个线性表为/ " u11rr ” I ”（

26、”abcd”, ”baabd”, ”bcef ”, ”cfg ”, ”ahij ”, ”b kwte ”，”ccdt ”，”aayb”）,若按照字符串的第 一个字母进行划分，使得同一个字母被划分 在一个子表中，则得到的 a,b,c 三个子表的 长度分别为（3） ,（3）,（2）。43、对于包含5 0个关键码的3阶 B-树，其 最小高度为（4），最大高度为（5）。44、从一棵B-树删除关键码的过程，若最终 引起树根结点的合并，则新树比原树的高度（减1）45、假定要对长度 n=100 的线性表进行散列 存储，并采用开散列法处理冲突，则对于长 度m=20的散列表，每个散列地址的同义词 子表的长度平均

27、为（5） 。46、在散列存储中，装载因子a又称为装载 系数，若用m表示散列表的长度，n表示待 散列存储的元素的个数，则a等于（n/m）。47、在有向图的邻接矩阵中，第 i 行中“ 1” 的个数是第 i 个顶点的（出度） ，第 i 列中 “1”的个数是第 i 个顶点的（入度） 。在无 向图的邻接矩阵中，第i行（列）中“1” 的个数是第i个顶点的（度），矩阵中“ 1” 的个数的一半是图中的（边数）。48、在对m阶B-树中，每个非根结点的关键 码数最少为（m/2-1 ）个，最多为（m-1） 个，其子树棵数最少为（m/2n），最多为（m）。二、判断题四、运算应用题1、在一个有n个元素的顺序表的第i个

28、元素（1 i n）之前插入一个新元素 时，需要向后移动多少个元素？答案：需要向后移动n-i + 1个兀素2、当一个栈的进栈序列为1234567时，可能的出栈序列有多少种？6457321是否是合理的出栈序列？答案：丄齢 1 14 13 12 11 10 9 8 4297 187 6 5 4 3 2 1可能的出栈序列有种，6457321不是合理的出栈序列。4、设有序顺序表为 10, 20, 30, 40, 50,60, 70 ，采用折半搜索时，搜索成功的平均搜索长度是多少？答案：ASLsucc = (1*1 + 2*2 + 3*4 ) / 7 = 17/ 75、在结点个数为 n(n>1) 的

29、各棵树中， 高度 最小的树的高度是多少？它有多少个叶结 点？多少个分支结点？高度最大的树的高 度是多少？它有多少个叶结点？多少个分 支结点？答案：结点个数为 n 时，高度最小的树的高 度为 1，有 2 层；它有 n-1 个叶结点， 1 个 分支结点；高度最大的树的高度为 n-1, 有 n 层；它有 1 个叶结点， n-1 个分支结点。6、一棵高度为h的满k叉树有如下性质：第 h 层上的结点都是叶结点 , 其余各层上每个 结点都有 k 棵非空子树 , 如果按层次自顶向 下, 同一层自左向右 , 顺序从 1 开始对全部 结点进行编号 , 试问 ：(1) 各层的结点个数是多少 ?(2) 编号为 i

30、的结点的父结点 (若存在 )的 编号是多少 ?(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时有右兄弟，右兄弟的 编号为i+1(5)若结点个数为n，则高度h和n的关系为：h=log k(n*(k-1)+

31、1)-1(n=0 时h=-1)9、题目：11、将下面的森林变换成二叉树KjA答案:10、将算术表达式(a+b)+c*(d+e)+f)*(g+12、将给定的图简化为最小的生成树，要 求从顶点1出发。(7分)151012答案:1533742：671513、某子系统在通信联络中只可能出现8种字符，其出现的概率分别为0.05 , 0.29 ,0.07，0.08，0.14，0.23，0.03，0.11 试设 计赫夫曼编码。答案： 为方便起见，设各种字符的权值w=5,29,7,8,14,23,3,11。因为 n=8,所以要构造的赫夫曼树共有 m=2n-仁2*8-仁15个结点。生成的赫夫曼树为下图所示：11

32、012901114180102329111153赫夫曼编码为：概率为 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, 试画出这棵二叉树，并给出这棵二叉树的后 序遍历序列。答案：根据序序列能得到唯一的二叉树，图：这棵二叉树的后序遍历序列为：EDCBIHJGFA15、在结点个数为n(n>1)的各棵树中，高度 最小的树的高度