《数据结构试卷试卷和答案5套》由会员分享，可在线阅读，更多相关《数据结构试卷试卷和答案5套（12页珍藏版）》请在金锄头文库上搜索。
1、数据结构试卷试1一、 解释下列术语（每小题4分，共20分）1. 头指针 2. 二叉排序树的定义 3. 头结点4. 数据的逻辑结构 5. 排序方法的稳定性二、选择填空（每小题2分，共20分）（在每小题的4 个备选答案中，选出一个正确的答案，多选少选均不得分）1. 在一个长度为n的顺序表中，在第i个元素（1in+1）之前插入一个新元素时顺向后移动( ) 个元素 A.n-i B. n-i+1 C. n-i-1 D.i2. 某个栈的输入序列为1，2，3，4，下面的四个序列中( )不可能是它的输出序列 A.1,2,3,4 B.2,3,4,1 C. 4,3,2,1 D.3,4, 1,2 3. 对二叉排序进
2、行( )遍历可以得到结点的排序序列 A.前序 B.中序 C. 后序 D.按层次4有64个结点的完全二叉树的深度为（ ）。 A 8 B 7 C 6 D 55折半查找法的时间复杂度是( ) A.(n2) B.O(n) C. O(nn) D. O(n)6A(1:5,1:6)的每个元素占5个单元，将其按行优先次序储存在起始地址为1000的连续的内存单元中，则元素A5，5的地址为（ ）。A 1140 B 1145 C 1120 D 11257. 有n个叶子结点的哈夫曼树的结点总数为（ ）。 A 不确定 B 2n C 2n+1 D 2n-18. 已知某二叉树的后序遍历序列是dabec, 中序遍历序列是de
3、bac, 则它的前遍历序列是（ ）。 A acbed B decab C deabc D cedba9若循环队列用数组A(0:m-1)存放其元素值，已知其头、尾指针分别是f和r,则当前队列中的元素个数是（ ）。A (r-f+m)mod m B r-f+1 C r-f-1 D r-f 10. 一个二叉树的先序序列和后序序列正好相反，则该二叉树一定是（ ）的二叉树（树中结点个数大于1）。 A 空或只有一个结点 B 高度等于其结点数 C 任一结点无左孩子 D任一结点无右孩子三， 判断题（每小题2分，对的打，错的打，共10分）1若图G的最小生成树不唯一，则G的边数一定多于n-1，并且权值最小的边有多条
4、（其中n为G的顶点数）。 ( )2对任意一个图，从它的某个顶点出发进行一次深度优先或广度优先遍历可访到该图的每个顶点。( ) 3若某二叉树的叶子结点数为1（树中只有一个结点的情况除外），则其先序序列和后序序列一定相反。（ ）4在队列中，队头指针总是指向第一个数据元素。（ ）5线性表的唯一存储形式是链表。（ ）四，解答题（每小题6分，共24分）a) 从一的平衡二叉树开始，把关键字（5，19，6，22，16，15，30）按出现的先后顺序逐一插入，从而构造一棵平衡二叉树排序树，每插入一个关键字后，若需要进行平衡旋转，则标明其旋转类型及旋转后的结果。b) 满足下列条件的二叉树具有什么形状？i. 前序和
5、中序遍历次序相同；ii. 中序和后序遍历次序相同；iii. 前序和后序遍历次序相同；c) 写出所给数据表，采用快速排序方法按升序排序的每一趟的结果：（25，10，20，31，5，28）。d) 具有144个记录的文件，若采用分块查找法查找，则分成几块最好？每块的最佳长度是多少？假定每块的长度是8，确定所在块、块中均采用顺序查找法查找，则平均查找长度是多少？五、 编写算法（共16分）a) 写出，建立一个具有n个顶点的无向网的邻接矩阵的算法。提示：先将矩阵A的每个元素都初始化成0，然后，读入边及数值（i, j, w）,将A的相应元素置成w。（8分）b) 线性表V采用顺序存储结构，试编写删除V中的第i
6、个元素起的k个元素的算法。（8分）数据结构试卷试2一、填空题（共20分，每空1分）1 数据结构是研究数据元素之间抽象化的相互关系和这种关系在计算机中的存储结构表示，通常有下列四种存储结构： （1） 、 （2） 、 （3） 和 （4） 。2 评价算法的标准很多，通常是以执行算法所需要的 （5） 和所占用的（6） 来判别一个算法的优劣。3 队列操作的原则是（7），栈的插入和删除操作在（8）进行。4 对循环队列Q，它的最大存储空间是MAXSIZE，队头指针是front，队尾指针是rear，采用少用一个存储单元的方法解决假溢出时，队满的判断条件是（9），队空的判断条件是（10）。5 在以 Head 为
7、表头指针的带有头结点的单链表和循环单链表中，判断链表为空的条件分别为 （11） 和 （12）。6 假设二维数组A68，每个元素用相邻的4个字节存储，存储器按字节编址 ，已知A的开始存储位置为100，按行优先顺序存储的元素A25的第一个字节的地址为（13）。7 空格串的长度为串中所包含（14） 字符的个数，空串的长度为 （15） 。8 有向图 G 用邻接矩阵 An，n 存储表示，其第 i 行的所有元素之和等于顶点 i 的 （16） 。 9 在关键字序列 (12 ， 23 ， 34 ， 45 ， 56 ， 67 ， 78 ， 89 ， 91) 中折半查找关键字为 89和25 的结点时，所需进行的比
8、较次数分别为 （17） 和 （18）。10 请说出两种处理哈希冲突的方法 （19） 、_（20）_。二、选择题（共20分，每题2分）1. 对线性表，在下列哪种情况下应采用链式存储结构？（ ）A经常需要随机存取元素 B经常需要进行插入和删除操作C表中元素的个数不变 D表中元素需要占据一片连续的存储空间2. 从一个具有n个结点的单链表中查找其值等于x结点时，在查找成功情况下，则平均比 较（ ）个结点。 An Bn/2 C(n-1)/2 D(n+1)/23. 若对某线性表最常进行的操作是在最后一个元素之后插入和删除第一个元素，则采用（ ）存储方式最节省运算时间。 A单链表 B双链表C仅有头指针的单循
9、环链表 D仅有尾指针的单循环链表4. 在一个单链表中，若要删除p指针所指结点的后继结点，则执行（ ）。Ap- next; p- next=p- next- next； Bp- next=p- next- next；Cp=p- next； Dp=p- next-next；5. 在具有 n 个结点的二叉链表中，非空的链域个数为（ ）。An-1 B n C n+1 D不确定6. 有64个结点的完全二叉树的深度为（ ）（假设根结点的层次为1）。A8 B 7 C 6 D57. 边远山区的那个小村庄，现要为他们建成能互相通信的网 ，并且总的花费最少，这可以归结为什么问题（ ）。 A最短路径 B关键路径 C
10、拓扑排序 D最小生成树8. 折半查找法要求查找表中各元素的键值必须是（ ）。A递增或递减 B递增 C递减 D无序9. 下列排序算法中，（ ）算法在进行一趟相应的排序处理结束后不一定能选出一个元素放到其最终位置上。A直选择排序 B冒泡排序 C归并排序 D堆排序10. 对于键值序列（2，33，21，18，65，38，7，49，24，86），用筛选法建堆，必须从键值为（ ）的结点开始。 A86 B 2 C65 D38三、判断题（共10分，每题2分）1. 已知指针P指向链表L中的某结点，执行语句P=P-next不会删除该链表中的结点。( )2. 如果一个串中的所有字符均在另一串中出现，则说前者是后者的
11、子串。( )3. 若一棵二叉树的任一非叶结点度均为2，则该二叉树为满二叉树。( )4. 任一AOE网中至少有一条关键路径，且是从源点到汇点的路径中最短的一条。( )5. 在采用线性探测法处理冲突的散列表中所有同义词在表中相邻。（ ）四、简答题（共24分,每题8分）1. 二叉树的先序遍历序列为：A B C D E F G H I，中序遍历序列为：B C A E D G H F I，画出这棵二叉树。2. 输入一个结点序列300，100，80，52，40，64，350，试画出构造平衡二叉树的过程，并说明平衡旋转类型。3. 已知一组记录的排序码为（46，79，56，38，40，80，95，24），写出
12、对其进行快速排序的每一趟排序的结果。五、算法设计题（共16分）1 试写一建立单链表的算法。（8分）2 已知一个非空线性链表第一个结点的指针为L，请写一算法，将链表中数据域值最大的那个结点移到链表最后面。（8分）数据结构试卷试3一、填空（20分，每小题2分）1、若用S1Sm作为顺序栈的存储空间，栈空的标志是栈顶指针t=m+1，则每进行一次（ ）操作，需将t的值加1。2、队列的特征是( )。3、在单向链表中增加一个表头节点的目的是（）。、3个结点可以构成（ ）种不同形状的树，可以构成（ ）种不同形状的二叉树。、在平衡二叉排序树中，每个结点的平衡因子等于（ ）。、可以进行拓扑排序的有向图一定是（ ）
13、。、为了实现折半查找，线性表必须采用（ ）方法存储。、若以4,5,6,7,8作为叶子结点的权值构造哈夫曼树，则其带权路径长度是（ ）、在排序过程中，任何情况下都不比较排序码大小的排序方法是（ ）。二、选择填空（20分，每小题2分）1、链表最常用的操作是在最后一个结点之后插入一个结点和删除第一个结点，则采用（ ）存储方式最省时间。 A. 单链表 B. 双链表 C. 单循环链表 D. 带尾指针的单循环链表2、栈和队列都是( ) A顺序存储的线性结构 B链式存储的非线性结构C限制存取点的线性结构 D限制存取点的非线性结构、若对有18个元素的有序表作折半查找。则查找A3的比较序列的下标为（）。A1，2，3 B9，5，2，3 C9，4，2，3 D10，5，4、设n，m为某二叉树上的两
