中国石油大学955数据结构历年考研试题

数据结构试题一、单选题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，则执行（）。

A s→link = p→link;p→link = s;B p→link = s; s→link = q;C p→link = s→link;s→link = p;D q→link = s;s→link = p;5、如果想在4092个数据中只需要选择其中最小的5个，采用（）方法最好。

A 起泡排序B 堆排序C 锦标赛排序D 快速排序6、设有两个串t和p，求p在t中首次出现的位置的运算叫做（）。

A 求子串B 模式匹配C 串替换D 串连接7、在数组A中，每一个数组元素A[i][j]占用3个存储字，行下标i从1到8，列下标j从1到10。

所有数组元素相继存放于一个连续的存储空间中，则存放该数组至少需要的存储字数是（）。

A 80B 100C 240D 2708、将一个递归算法改为对应的非递归算法时，通常需要使用（）。

A 栈B 队列C 循环队列D 优先队列9、一个队列的进队列顺序是1, 2, 3, 4，则出队列顺序为（）。

10、在循环队列中用数组A[0..m-1] 存放队列元素，其队头和队尾指针分别为front和rear，则当前队列中的元素个数是（）。

A ( front - rear + 1) % mB ( rear - front + 1) % mC ( front - rear + m) % mD ( rear - front + m) % m11、一个数组元素a[i]与（）的表示等价。

目　录2000年中国石油大学（北京）数据结构考研真题2001年中国石油大学（北京）数据结构考研真题2002年中国石油大学（北京）数据结构考研真题2003年中国石油大学（北京）数据结构考研真题2004年中国石油大学（北京）数据结构考研真题2000年中国石油大学（北京）数据结构考研真题石油大学（北京）二000年研究生入学试题糙明数据结构共2页适用专业：计算机应用-、求解下^问题(7X6分〉1、判别以下序列是否为堆(小顶堆或大顶堆).如果不是,则把它调整为堆(要求记录交换次数最少).⑴<100,86,48,73,35,39,42,57,/66,21)<2)《05,56.20,23.40.38,29,61,35,76.28,100)(3)(103,97,56,38,66,23,42,12,30,52,06,的)2、宿线性浪进行二分法粉索的先决编中是什么？简述二分法检索的基本汶程及草平均检索长度，3、按照四则运算加、减、m,除和慕运算（t）优先关系的惯例，即出对下列算术衰达式求值时操作数栈和运算待栈的变化过程：A-BXC/D+E tF4、己知下列各始为广义表的存赭结构图，其结点的结构为,Uj数据结构的主要区别是什么，（2）分配算法的主要区别是什么？⑶回收算法的主要区别是什么？6、画出与下列己知序列时应的森林F：森林的先序次序访问序列为：ABCDEFGHIJKL森林的中序次序访问序列为：CBEFDGAJIKLH7、画出上面有向图的十字链袤.I''>■**，-*二、写算法（2X12分）1、从循环双向链表中新除第i<i^l）个结点，试写出其算法.2、已知一棵以链表存储的二叉材，如欲姚结点起，由上而下，逐孱打印各结瘁的数据，同一是结点宜左而右打印，试写出其算法.（要求所用变量必须注解）】*l,t土|>”.1三，分析与推导L一棵深度为H的满k义村有如下性质：第H层上•钓结点都是叶于结点,其余各层上每个嬉点都有! k棵非空亍树.如果按层次倾序从1开殖对全部结点编号，网（12分）（D各层的结点数目是多少？•⑵编号为p的结点的父结点（若存在〉的编号是多少？⑶编号为P的绪点的第i个儿子结点（若存在）的编号是多少？⑴漏号为p的结点宥兄弟的条件是什么？其兄弟的编号是什么？2、.画出下图所示的无向图的邻接多重表，使得其中母个无向边绡点宇曾一个顶点号小于第二个顶点号，旦每个顶点的各邻接边的链接顾序为它所邻接的顶点序号或'到大莉前序.列出深度优先和广度优先搜索遍历该图所得顶*律列和边序列.（12分）3、什么姑平衡二又树|?平衡二叉树有什么优点，用在什么堕方？试推导含12个结点的平衡二叉树%"的最大深陌,芥皿出一棵这样的平衡二又树.no分｝2001年中国石油大学（北京）数据结构考研真题石油大学（北京）2001年研究生入学试题考试科目：数据结构共2页适用专业：计算机应用求解下列间题'（8X6分）1.画出广义表（a.（（）,b）,（（（e））））的存储结构图.2.若二棵树中有度为1至m的结点数分别为m,任，…，n.（&衷示及数为m的结点个数）*谄推导也该树中有多少个叶结点n“的公式.3.请给出下而稀疏炬阵的漆——列表示法（即十字镂表法）存储结构.勺200。

《数据结构》考研真题及解答目录2009 年试题 (1)填空题 (1)解答题 (2)2010 年试题 (2)填空题 (2)解答题 (4)2011 年试题 (4)填空题 (4)解答题 (5)2012 年试题 (6)填空题 (6)解答题 (7)2013 年试题 (8)填空题 (8)解答题 (9)2014 年试题 (10)填空题 (10)解答题 (11)2015 年试题 (12)填空题 (12)解答题 (14)2009 年试题填空题1.为解决计算机与打印机之间速度不匹配的问题，通常设置一个打印数据缓冲区，主机将要输出的数据依次写入该缓冲区，而打印机则依次从该缓冲区中取出数据。

该缓冲区的逻辑结构应该是A.栈B.队列C.树D.图2.设栈 S 和队列 Q 的初始状态均为空，元素 abcdefg 依次进入栈 S。

若每个元素出栈后立即进入队列 Q，且7 个元素出队的顺序是 bdcfeag，则栈 S 的容量至少是A．1 B.2 C.3 D.43.给定二叉树图所示。

设 N 代表二叉树的根，L代表根结点的左子树，R代表根结点的右子树。

若遍历后的结点序列为 3，1，7，5，6，2，4，则其遍历方式是A．LRN B.NRL C.RLN D.RNL4.下列二叉排序树中，满足平衡二叉树定义的是5.已知一棵完全二叉树的第 6 层（设根为第 1 层）有8 个叶结点，则完全二叉树的结点个数最多是A．39 B.52 C.111 D.1196.将森林转换为对应的二叉树，若在二叉树中，结点u 是结点v 的父结点的父结点，则在原来的森林中，u 和v 可能具有的关系是I．父子关系II.兄弟关系III.u 的父结点与v 的父结点是兄弟关系A.只有IIB.I 和IIC.I 和IIID.I、II 和III7.下列关于无向连通图特性的叙述中，正确的是I．所有顶点的度之和为偶数II.边数大于顶点个数减1 III.至少有一个顶点的度为1A.只有IB.只有IIC.I 和IID.I 和III8.下列叙述中，不符合 m 阶B 树定义要求的是A．根节点最多有m 棵子树 B.所有叶结点都在同一层上C．各结点内关键字均升序或降序排列 D.叶结点之间通过指针链接9.已知关键序列 5，8，12，19，28，20，15，22 是小根堆（最小堆），插入关键字 3，调整后得到的小根堆是A．3，5，12，8，28，20，15，22，19B.3，5，12，19，20，15，22，8，28C．3，8，12，5，20，15，22，28，19D.3，12，5，8，28，20，15，22，1910.若数据元素序列 11，12，13，7，8，9，23，4，5 是采用下列排序方法之一得到的第二趟排序后的结果，则该排序算法只能是A．起泡排序 B.插入排序 C.选择排序 D.二路归并排序解答题41.（10 分）带权图（权值非负，表示边连接的两顶点间的距离）的最短路径问题是找出从初始顶点到目标顶点之间的一条最短路径。