数据结构历年试题及答案

《数据结构历年试题及答案》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、试卷代号：1252中央广播电视大学2012-2013学年度第二学期“开放本科”期末考试数据结构【本）试题一、单项选择题（每小题2分，共30分）1．在C语言中，顺序存储长度为3的字符串，需要占用()个字节。A．4B．3C．6D．122。串函数StrCat(a，b)的功能是进行串()。A．比较B．复制C。赋值D．连接3．-棵有n个结点采用链式存储的二叉树中，共有()个指针域为空。A．n+lB．nC．n-lD．n-24．设一棵哈夫曼树共有n个非叶结点，则该树有()个叶结点。A．nB．n+lC．n-lD．2n5．从一个栈顶指针为top的链栈中删除一个结点时，用变量x保存被删结

2、点的值，则执行()。A.x=top->data;top=top->nextB.x=top->dataC.top=top->next;x=top->dataD.top=top->next;x=data6．一棵完全二叉树共有5层，且第5层上有六个结点，该树共有()个结点。A．30B．20C．21D．237．在一个无向图中，所有顶点的度数之和等于边数的()倍。^．O上；．Z．3C．1.5D．28．已知如图1所示的一个图，若从顶点V，出发，按深度优先搜索法进行遍历，则可能得到的一种顶点序列为()。9．已知如图2所示的一个图，若从顶点a出发，按广度优先搜索法进行遍历，则可能得到

3、的一种顶点序列为()。A.abcedfB.abcefdC.aebcfdD.acfdeb10.对二叉排序树进行()遍历，可以使遍历所得到的序列是有序序列。A．按层次B．后序C．中序D．前序11．在有序表(2，4，7，14，34，43，47，64，75，80，90，97，120)中，用折半查找法查找值80时，经()次比较后查找成功。A．4B．2赢“C．3D．512．有一个长度为9的有序表，按折半查找对该表进行查找，在等概率情况下查找成功的平均比较次数为()。A．25/10B．25/9C．20/9D．17/913.排序算法中，从未排序序列中依次取出元素与已排序序殂（初始为空

4、）中的元素进行比较（要求比较次数尽量少），然后将其放入已排序序列的正确位置的方法是()。A．冒泡B。直接插入C．折半插入D．选择排序14．一组记录的关键字序列为(46，79，56，38，40，84)，利用快速排序，以第一个关键字为分割元素，经过一次划分后结果为()。A．40,38946,79956,84B．40,38946,56,79,84C．40，38,46,84,56,79D．38，40,46956,79,8415.排序方法中，从尚未排序序列中挑选元素，并将其依次放人已排序序列（初始为空）的一端的方法，称为()排序。A．归并B．插入C．快速D．选择二、填空题（每小

5、题2分。共24分）16.在二叉树的链式存储结构中，通常每个结点中设置三个域，它们是——、、右指针。17.-棵二叉树中顺序编号为i的结点，若它存在左、右孩子，则左、右孩子编号分别为.__.____.....____．一、____......____..．一O18.串的两种最基本的存储方式是一和——一。19.-棵有2n-l个结点的二叉树，其每一个非叶结点的度数都为2，则该树共有——个叶结点。20.对于一棵具有n个结点的二叉树，其相应的链式存储结构中共有——个指针域为空。21．____遍历二叉排序树可得到一个有序序列。22．如图3所示的二叉树，其后序遍历序列为≥%图323．

6、如图4所示的二叉树，其先序遍历序列为妒图424.图的深度优先搜索和广度优先搜索序列不一定是唯一的。此断言是一的。（回答正确或不正确）25.二叉树为二叉排序的充分必要条件是其任一结点的值均大于其左孩子的值、小于其右孩子的值。这种说法是的。（回答正确或不正确）26.对记录序列排序是指按记录的某个关键字排序，记录序列按____排序结果是唯一的。27.按某关键字对记录序列排序，若在排序前和排序后仍保持它们的前后关系，则排序算法是稳定的，否则是不稳定的。三、综合题（每小题10分。共30分）28．设查找表为(16，15，20，53，64，7)，(1)用冒泡法对该表进行排序（要求升

7、序排列），写出每一趟的排序过程，通常对n个元素进行冒泡排序要进行多少趟冒泡？第j趟要进行多少次元素间的比较？(2)在排序后的有序表的基础上，画出对其进行折半查找所对应的判定树。（要求以数据元素作为树结点）。29．(1)设有查找表{5，14，2，6，18，7，4，16，3），依次取表中数据，构造一棵二叉排序树。(2)说明如何由序列的二叉排序树得到相应序列的排序结果。30．(1)对给定权值2，1，3，3，4，5，构造哈夫曼树（要求每个结点的左子树根结点的权小于等于右子树根结点的权）。(2)给出各权值的哈夫曼编码。四、程序填空题【每空2分。共16分）32.