《奥赛数据结构题汇总》由会员分享，可在线阅读，更多相关《奥赛数据结构题汇总（25页珍藏版）》请在金锄头文库上搜索。
1、数据结构练习一一、单项选择题1 若某链表中最常用的操作是在最后一个结点之后插入一个结点和删除最后一个结点，则 采用存储方式最节省运算时间。(1) 单链表(2)双链表(3)单循环链表(4)带头结点的双循环链表2. 设一个栈的输入序列为A, B, C, D,则借助一个栈所得到的输出序列不可能 (1)A，B，C，D(2)D，C，B，A(3)A，C，D，B(4)D，A， B， C3 .串是。(1)不少于一个字母的序列(2)任意个字母的序列(3)不少于一个字符的序列(4)有限个字符的序列4. 链表不具有的特点 。(1)可随机访问任一元素(2)插入删除不需要移动元素(3)不必事先估计存储空间 (4)所需空
2、间与线性表长度成正比5. 在有n个叶子结点的哈夫曼树中，其结点总数为。(1)不确定(2)2n(3)2n+1(4)2n-16. 任何一个无向连通图的最小生成 (1)只有一棵(2)有一棵或多棵(3) 定有多棵 (4)可能不存在7. 将一棵有 100 个结点的完全二叉树从根这一层开始,每一层上从左到右依次对结点进行编号，根结点的编号为1,则编号为49的结点的左孩子编号为。(1)98(2)99(3)50(4)48&下列序列中，是执行第一趟快速排序后得到的序列(排序的关键字类型是字符串)。(1)da,ax,eb ,de,bbffha,gc(2)cd,eb,ax,daffha,gc , bb(3)gc,a
3、x,eb,cd,bbffda,ha(4)ax,bb,cd,daffeb,gc, ha9用n个键值构造一棵二叉排序树，最低高度为。(1)n/2(2)n(3)logn(4)logn+110. 二分查找法要求查找表中各元素的键值必须排列。(1)递增或递减(2)递增(3)递减(4)无序11. 对于键值序列(12, 13, 11, 18, 60, 15, 7, 18, 25, 100),用筛选法建堆,必须从键值为的结点开始。(1)100(2)12(3)60(4)15三、填空题1在带有头结点的单链表L中，第一个元素结点的指针 。2. 在双循环链表中，在指针P所指结点前插入指针S所指的结点，需执行下列语句：
4、S f .next：二 P；S f. prior： = P f. prior；Pf. prior： = S；: = S；ABC/ DE3. 1.maxsize为一个顺序存储的栈，变量top指示栈顶位置，栈为空的条件 栈为满的条件是4. 具有100个结点的完全二叉树的深度为。5. 有向图G用邻接矩阵A1. n, 1.n存储，其第i行的所有元素之和等于顶点i的。6. 在顺序文件中，要存取第i个记录，必须先存取。7. 对于下面的二叉树，按中序遍历所得到的结点序列为。8. 分别采用堆排序、快速排序、插入排序和归并排序算法对初始状态为递增序列的表按递增顺序排序，最省时间的 算法，最费时间的 算法。9对下
5、图所示的网，执行prim算法可得到最小生成树，试在下表的空白处填上括当的内容, 以说明该算法的执行过程。顶点134UV（U，V） 代价(2,1)OO(2,3)4(2,4)221,3,4（U，V） 代价(2,3)42,41,3（U，V） 代价(3,1)12,3,41（U，V） 代价2,3,4,110.设散列函数为H （key），用拉链（链地址）法解决冲突，H的值域为0,，n-1，构造的 散列表类型如下：TYPE link = f node；Node = RECORDkey：keytype；next：link；END；Openhash = array0. n-1 of link；请在下列算法划线处
6、填上适当内容，以完成在散列表HP中查找键值等于K的结点，若查 找成功，返回该结点的指针，否则返回空指针。Function research（K：keytype； HP：openhash）：link；BEGINI：= H（K）； SUC：= false；while（PNIL）and（not suc）doif P f .keyKthenelse suc：= true； return（P）END四、应用题1. 已知二叉树的后序和中序序列如下，构造出该二叉树。后序序列: ABCDEFG中序序列：ACBGEDF2. 有一组关键码序列（38， 19， 65， 13， 97， 49， 41， 95， 1，
7、73），采用冒泡排序方法由小 到大进行排序，请写出每趟的结果。3设图 G=(V，E)，V=1，2，3，4，5，6，E=1，2，1，3，2，5，3，6，6，5， 5, 4，6, 4。请写出图G中顶点的所有拓扑序列。4. 设散列函数为H(K)=Kmod7，闭散列表的地址空间为0,，6,开始时散列表为空，用 线性探测法解决冲突，请画出依次插入键值23， 14， 9， 6， 30， 12， 18后的散列表。5对下面两棵二叉树，分别画出它们的顺序存储结构。A/BC D E F GIJKABCD E FIJ6. 已知图G的邻接表如下，画出图G的所有连通分量。数据结构练习二一、选择题1在下列备选答案中选出一
8、个正确的，将其号码填在“”上。1 若线性表最常用的操作是存取第i个元素及其前趋的值，则采用存储方式节省时间。a.单链表 b双链我c.单循环链表 d.顺序表2对二叉树从 1 开始进行连续编号，要求每个结点的编号大于其左右孩子的编号，同一 个结点的左右孩子中，其左孩子的编号小于其右孩子的编号，则可采用.次序的遍历实现编号。a.先序b中序c.后序d.从根开始的层次遍历3. 某二叉树的先序序列和后序序列正好相反，则该二叉树一定是的二叉树。a.空或只有一个结点b高度等于其结点数c任一结点无左孩子d.任一结点无右孩子4. 下列排序算法中，时间复杂度不受数据初始状态影响，恒为O(nlogzn)的是。a.堆排
9、序 b冒泡排序c.直接选择排序d.快速排序5. 下列排序算法中，算法可能会出现下面情况：初始数据有序时，花费的时间反而最多。a.堆排序b.冒泡排序c.快速排序d. SHELL排序三、填空1. 在单链表中，删除指针P所指结点的后继结点的语句 。2. 取出广义表A： （x, y, 2）, （a, b, c, d）中原子b的函数是。3. 已知完全-y.树的第八层有8个结点，则其叶子结点数是。4. 将下三角矩阵A1. 8, L. 8的下三角部分逐行地存储到起始地址为1000的内存单元中，已知每个元素占4个单元，则A?, 5的地址为。5. 有n个顶点的强连通有向图G至少有条弧。6. 求最短路径的DIJK
10、STRA算法的时间复杂度为。7. 高度为5的三阶B树至少有个结点。8. 在有序表A1. .20中，采用二分查找算法查找元素值等于A12的元素，所比较过的元素的下标依次为。9. 直接选择排序算法所执行的元素交换次数最多为。10. 下列排序算法中，稳定的排序算法是（选择排序，堆排序，快速排序，直接插入排序）。四、解答下列各题（30分）1. 一棵二叉树的先序序列和中序序列分别如下，画出该二叉树。 （5分）先序序列 ABCDEFGHIJ中序序列CBEDAGHFJl2. 对下面给出的数据序列，构造一棵哈夫曼树，并求出其带权路径长度。 （6分）4，5，6，7，10，12，15，18，233. 图G的邻接表
11、如下页，完成下列各题：（7分）（1）画出从顶点 5 出发进行广度遍历所生成的生成树。（2）判断其中是否存在有向回路，若不存在，求出其拓扑序列。4. 对下列数据表，写出采用快速排序算法排序的每一趟的结果。 （6分）（60， 20， 3l， 1， 5， 44， 55， 61， 200， 30， 80， 150， 4， 29）5. 已知哈希表地址空间为0.8,哈希函数为H（k）=kmod7,采用线性探查法处理冲突。 将下面数据序列依次存入该散列表中，并求出在等概率下的平均查找长度。（6 分 ）100, 20, 21, 35, 3, 78, 99, 45012345678五、算法设计（共 30 分）1
12、已知单循环链表L中至少有两个结点，每个结点的两个字段为data和next,其中字 段data的类型为整型。设计算法以判断该链表中的每个元素的值是否小于其后续两个结点的 值的和，若满足，返回true，否则返回false。（8分）2设计算法按后序次序打印二叉树T中所有叶子结点的值，并返回其结点数。（8分）3写出在二叉排序树中查找值为x的元素的算法。（6分）4设计算法按层次遍历二叉树T。（8分）模拟试卷三一、选择题（每小题2分，共20分），在下列备选答案中选出一个正确的，将其号码填在“ ”上。1. 一个栈的输入序列为1 2 3 4 5，则下列序列中不可能是栈的输出序列的 是。a2 3 4 1 5b5
13、 4 1 3 2c2 3 1 4 5d.1 5 4 3 22. 设循环队列中数组的下标范围是ln,其头尾指针分别为f和r,则其元素个数为a. r-f bo r-f+1c. (r-f)mod n+l d. (r-f+n) mod n3. 若某链表最常用的操作是在最后一个结点之后插入一个结点和删除最后一个结点,则采用存储方式最节省时间。a.单链表 b.双链表c.带头结点的双循环链表d.单循环链表4. 一棵非空的二叉树的先序序列和后序序列正好相反,则该二叉树一定满足oa.其中任意一结点均无左孩子b.其中任意一结点均无右孩子c.其中只有一个叶子结点d.是任意一棵-y.树5. 棵左右子树均不空的二叉树在
14、先序线索化后，其空指针域数为oa. 0b. 1c. 2d. 不确定6. 数组Al.5, 1.6的每个元素占5个单元，将其按行优先次序存储在起始地址为1000的连续的内存单元中，则元素A5, 5的地址为oa. 1140b. 1145c. 1120d. 11257. 求最短路径的DIJKSTRA算法的时间复杂度为oa. 0(n)b. 0(n+e) c. 0(n2)d. 0(n*e)8. 对有18个元素的有序表作二分查找，则查找A3的比较序列的下标为oa. 1, 2, 3 b. 9, 5, 2, 3 c. 9, 5, 3d. 9, 4, 2, 39 .快速排序算法在最好情况下的时间复杂度为oa. O(n)b. O(nlogn)c. O(n2)d. O(1Ogn)10.下列 排序算法中,某一趟结 束后未必能
