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

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

2、，则 执行（ ）。 Asf link = 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 到

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

4、) % m C ( front - rear + m) % m D ( rear - front + m) % m 11、一个数组元素 ai 与（ ）的表示 等价。 A * （a+i） B a+i C *a+i D im;i+） for (int j=0;jlink=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，则应 执行下列哪一个操作(

5、) A s-link=p-link; p-link=s; B q-link=s; s-link=p C p-link=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 是指向非空的带表 头结点的

6、 单循环链 表的 尾结点 的指针。若 想 删除链表第一个结点 ，则应执行下列哪一个 操作( 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 为链表当前指针，在循

7、环链 表中 检测 current 是否达到链表表尾的语句 是 ( D ) 。 =null B A current-link first-link=current C 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,b 24、栈的数组表示中， top 为栈顶指针，栈 空的条件是 ( A ) 。 A top=0 B top=maxSize C top=maxSize D top=-1 25、栈和队列的共同特点是 ( C ) 。 A 都

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

9、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 Data Type dataMaxsize; Int front, rear; Q

10、ueue; 若有一个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 计算 fact(n) 需要执行 n 次递归 B fact(7)=5040 C 此递归算法

11、最多只能计算到 fact(8) D 以上结论都不对 32、设有一个递归算法如下 int x (int n) if (n=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的空二叉树的高度

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

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

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

15、（0（ elog 2e） 34、快速排序在平均情况下的时间复杂度为 （0（ 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) ,对其进行快速 排序的第一次划分的结果是( 3840 46567980)。 37、 一个结点的子树的(个数 )称为该 结

16、点的度。度为( 零)的结点称为叶 结点或终端结点。度不为( 零 )的结 点称为分支结点或非终端结点。树中各结点 度的( 最大值 )称为树的度。 38、设 Ki =Kj (1=i=n, 1=j=n,ji) 且在 排序前的序列中 Ri 领先于 Rj (i1) 的各棵树中， 高度 最小的树的高度是多少？它有多少个叶结 点？多少个分支结点？高度最大的树的高 度是多少？它有多少个叶结点？多少个分 支结点？ 答案：结点个数为 n 时，高度最小的树的高 度为 1，有 2 层；它有 n-1 个叶结点， 1 个 分支结点；高度最大的树的高度为 n-1, 有 n 层；它有 1 个叶结点， n-1 个分支结点。 6

17、、一棵高度为h的满k叉树有如下性质：第 h 层上的结点都是叶结点 , 其余各层上每个 结点都有 k 棵非空子树 , 如果按层次自顶向 下, 同一层自左向右 , 顺序从 1 开始对全部 结点进行编号 , 试问 ： (1) 各层的结点个数是多少 ? (2) 编号为 i 的结点的父结点 (若存在 )的 编号是多少 ? (3) 编号为i的结点的第m个孩子结点(若 存在 ) 的编号是多少 ? (4) 编号为i的结点有右兄弟的条件是什 么？其右兄弟结点的编号是多少 ？ (5) 若结点个数为n,则高度h是n的什 么函数关系？ 答案： (1) 各层的结点个数是ki (i=0,1,2,h) (2) 编号为i的结

18、点的父结点(若存在)的 编号是匚(i+k-2)/k (3) 编号为i的结点的第m个孩子结点(若 存在)的编号是(i-1)*k+m+1 (4) 当(i-1)%k0时有右兄弟，右兄弟的 编号为i+1 (5) 若结点个数为n，则高度h和n的关 系为：h=log k(n*(k-1)+1)-1(n=0 时 h=-1) 9、题目： 11、将下面的森林变换成二叉树 K j A 答案: 10、将算术表达式(a+b)+c*(d+e)+f)*(g+ 12、将给定的图简化为最小的生成树，要 求从顶点1出发。(7分) 15 10 12 答案: 1 5 3 3 7 5 4 2 ：6 7 15 13、某子系统在通信联络中

19、只可能出现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个 结点。生成的赫夫曼树为下图所示： 1 1 0 1 29 0 1 1 14 1 8 0 1 0 23 29 1 11 1 5 3 赫夫曼编码为：概率为 0.23的字符编码为： 00 概率为0.11的字符编码为： 010 概率为0.05的字符编码为：0110 概率为0.03的字符编码为：0111 概

20、率为0.29的字符编码为：10 概率为0.14的字符编码 为：110 概率为0.07的字符编码 为：1110 概率为0.08的字符编码 为：1111 14、已知一棵二叉树的前序遍历的结果是 ABECDFGHIJ,中序遍历的结果是 EBCDAFHIGJ, 试画出这棵二叉树，并给出这棵二叉树的后 序遍历序列。 答案：根据序序列能得到唯一 的二叉树，图： 这棵二叉树的后序遍历序列为：EDCBIHJGFA 15、在结点个数为n(n1)的各棵树中，高度 最小的树的高度是多少？它有多少个叶结 点？多少个分支结点？高度最大的树的高 度是多少？它有多少个叶结点？多少个分 支结点？ 答案：结点个数为n时，高度最小的树的高 度为1,有2层；它有n-1个叶结点，1个 分支结点；高度最大的树的高度为n-1,有n 层；它有1个叶结点，n-1个分支结点。 16、对于一个高度为h的AVL树，其最少 结点数是多少？反之，对于一个有 n个结点 的AVL树，其最大高度是多少？最小高度是 多少？ 答案：设高度为h（空树的高度为-1）的AVL 树的最少结点为 2,贝M N1 = F h+3 -1。 Fh是斐波那契数。又设 AVL树有n个结