精华内容
下载资源
问答
  • 数据结构-排序-练习

    千次阅读 2018-09-10 21:49:17
    1、选择(1)直接插入排序算法的时间复杂度为( )A.O(N) B.O(1) C.O(N2) D.O(LOGN)(2)下列排序方法中,从平均时间而言最佳的是( )A.快速 B.希尔 C.基数 D.归并(3)下列是稳定的排序方法的( )A.快速 B....

    1选择题

    (1)直接插入排序算法的时间复杂度为(     )

    A.O(N)  B.O(1)    C.O(N2)    D.O(LOGN)

    (2)下列排序方法中,从平均时间而言最佳的是(    )

    A.快速    B.希尔    C.基数    D.归并

    (3)下列是稳定的排序方法的(   )

    A.快速    B.希尔    C.堆    D.基数

    (4)所需辅助空间为O(N)的排序方法为(    )

    A.快速    B.希尔    C.基数    D.归并

    (5)如果只想得到1024个元素组成的序列中第5个最小元素之前的部分排序的序列,用(    )方法最快。

       A.起泡排序

       B.快速排序

       C.简单选择排序

       D.堆排序

    (6)下列选项中,(    )需要的附加存储开销最大。

       A.快速排序

       B.堆排序

       C.归并排序

       D.插入排序

    参考答案: (1 C    (2 A     (3 D    (4D     (5C    (6)C

    2选择排序的基本思想是什么?给定初始关键字 [49 38 65 97 76 13 27 49],请写出具体排序过程及程序实现。

    基本思想:

    ①初始状态:无序区为R[1..n],有序区为空。
    ②第1趟排序
    在无序区R[1..n]中选出关键字最小的记录R[k],将它与无序区的第1个记录R[1]交换,使R[1..1]和R[2..n]分别变为记录个数增加1个的新有序区和记录个数减少1个的新无序区。
    ……
    ③第i趟排序
    第i趟排序开始时,当前有序区和无序区分别为R[1..i-1]和R[i..n](1≤i≤n-1)。该趟排序从当前无序区中选出关键字最小的记录R[k],将它与无序区的第1个记录R交换,使R[1..i]和R[i+1..n]分别变为记录个数增加1个的新有序区和记录个数减少1个的新无序区.这样,n个记录的文件的直接选择排序可经过n-1趟直接选择排序得到有序结果。
    优点:稳定,比较次数与冒泡排序一样;
    缺点:相对之下还是慢。

    初始关键字 [49 38 65 97 76 13 27 49]
    第一趟排序后 13 [38 65 97 76 49 27 49]
    第二趟排序后 13 27 [65 97 76 49 38 49]
    第三趟排序后 13 27 38 [97 76 49 65 49]
    第四趟排序后 13 27 38 49 [49 97 65 76]
    第五趟排序后 13 27 38 49 49 [97 76 76]
    第六趟排序后 13 27 38 49 49 76 [76 97]
    第七趟排序后 13 27 38 49 49 76 76 [ 97]
    最后排序结果 13 27 38 49 49 76 76 97

    参考代码如下:

    #include <iostream>
    using namespace std;
    void main()
    {
    int i,j,k,t;
    int R[8]={49,38,65,97,76,13,27,49};
    for(i=0;i<7;i++)
    {
    k=i;
    for(j=i+1;j<8;j++)
    if(R[j]<R[k])
    k=j;
    if(k!=i)
    {

    t=R[j];R[j]=R[k];R[k]=t;

    }
    }
    for(i=0;i<8;i++)
    cout<<R<<endl;
    }

    3描述 493827673987快速排序的过程

    下面是具体算法步骤:

    设要排序的数组是A[0]……A[N-1],首先任意选取一个数据(通常选用第一个数据)作为关键数据,然后将所有比它小的数都放到它前面,所有比它大的数都放到它后面,这个过程称为一趟快速排序。一趟快速排序的算法是:

    1)设置两个变量I、J,排序开始的时候:I=0,J=N-1;

    2)以第一个数组元素作为关键数据,赋值给X,即 X=A[0];

    3)从J开始向前搜索,即由后开始向前搜索(J=J-1),找到第一个小于X的值,让该值与X交换(找到就行.找到后i大小不变);

    4)从I开始向后搜索,即由前开始向后搜索(I=I+1),找到第一个大于X的值,让该值与X交换(找到就行.找到后j大小不变);

    5)重复第3、4步,直到 I=J; (3,4步是在程序中没找到时候j=j-1,i=i+1。找到并交换的时候i, j指针位置不变。另外当i=j这过程一定正好是i+或j+完成的最后另循环结束)

    下面是排序结果:

    49      38   65    97    76    13      27     

    27    38    13      49     76    97       65     49

    13     27     38     49    65      76     97

    来源:我是码农,转载请保留出处和链接!

    本文链接:http://www.54manong.com/?id=355

    '); (window.slotbydup = window.slotbydup || []).push({ id: "u3646208", container: s }); })();
    '); (window.slotbydup = window.slotbydup || []).push({ id: "u3646147", container: s }); })();
    展开全文
  • 一、选择 1. 算法的计算量的大小称为计算的( )。【北京邮电大学2000 二、3 (20/8 分)】 A.效率 B. 复杂性 C. 现实性 D. 难度 2. 算法的时间复杂度取决于( )【中科院计算所 1998 二、1 (2 分)】 A....
  • 数据结构习题及解析一

    千次阅读 多人点赞 2018-12-20 09:51:36
    数据结构习题解析解析:本考点是顺序表的基本特点。 顺序表是在计算机内存中以数组的形式保存的线性表,是指用一组地址连续的存储单元依次存储数据元素的线性结构。线性表采用顺序存储的方式存储就称之为顺序表。...

    来源:我是码农,转载请保留出处和链接!
    本文链接:数据结构习题解析一
    一、选择题
    1、顺序表是线性表的( )
    A.链式存储结构
    B.顺序存储结构
    C.索引存储结构
    D.散列存储结构
    解析:本题考点是顺序表的基本特点。
    顺序表是在计算机内存中以数组的形式保存的线性表,是指用一组地址连续的存储单元依次存储数据元素的线性结构。线性表采用顺序存储的方式存储就称之为顺序表。顺序表是将表中的结点依次存放在计算机内存中一组地址连续的存储单元中。
    因此,本题参考答案是B。
    2、以下说法错误的是( )
    A.求表长、定位这二种运算在采用顺序存储结构时实现的效率不比采用链式存储结构时实现的效率低
    B.顺序存储的线性表可以随机存取
    C.由于顺序存储要求连续的存储区域,所以在存储管理上不够灵活
    D.线性表的链式存储结构优于顺序存储结构
    解析:本题考点是线性表相关基本概念。
    “线性表的链式存储结构优于顺序存储结构"这种说法是不准确的,可能在某种情况下是对的。比如在随机查找时,顺序表比较有优势。因此,本题参考答案是D。
    3、某二叉树的前序和后序序列正好相同,则该二叉树一定是( )的二叉树。
    A.空或只有一个结点
    B.高度等于其结点数
    C.任一结点无左孩子
    D.任一结点无右孩子
    解析:本题考点是二叉树的基本特点。
    二叉树的每个结点至多只有二棵子树(不存在度大于2的结点),二叉树的子树有左右之分,次序不能颠倒。某二叉树的前序和后序序列正好相同,则该二叉树一定是空或只有一个结点的二叉树。
    因此,本题参考答案是A。
    4、以下说法错误的是( )
    A.每个存储结点只能存放一个数据元素
    B.数据元素之间的关联方式可由存储结点之间的关联方式直接表达
    C.一种存储结构可以在两个级别上讨论。其一是机器级,其二是语言级
    D.语言级描述可经编译自动转换成机器级,因此也可以看成是一种机内表示
    解析:本题考点是数据结构相关基本概念。
    数据元素之间的关联方式不可以由存储结点之间的关联方式直接表达。
    因此,本题参考答案是B。
    5、用链接方式存储的队列,在进行插入运算时( )。
    A.仅修改头指针
    B.头、尾指针都要修改
    C.仅修改尾指针
    D.头、尾指针可能都要修改
    解析:本题考点是队列的操作。
    队列是一种特殊的线性表,特殊之处在于它只允许在表的前端(front)进行删除操作,而在表的后端(rear)进行插入操作,和栈一样,队列是一种操作受限制的线性表。进行插入操作的端称为队尾,进行删除操作的端称为队头。用链接方式存储的队列,在进行插入运算时头、尾指针可能都要修改。
    因此,本题参考答案是D。
    6、循环队列的出队操作为( )
    A.sq.front=(sq.ftont+1)% maxsize
    B.sq.front=sq.front+1
    C.sq.rear=(sq.rear+1)% maxsize
    D.sq.rear=sq.rear+1
    解析:本题考点是循环队列的基本操作。
    循环队列中,由于入队时尾指针向前追赶头指针;出队时头指针向前追赶尾指针,造成队空和队满时头尾指针均相等。因此,无法通过条件front==rear来判别队列是"空"还是"满”。循环队列的出队操作为sq.front=(sq.ftont+1)% maxsize。
    因此,本题参考答案是A。
    7、下列排序算法中,其中( )是稳定的。
    A.堆排序,冒泡排序
    B.快速排序,堆排序
    C.直接选择排序,希尔排序
    D.归并排序,冒泡排序
    解析:本题考点是算法稳定性的度量。
    假定在待排序的记录序列中,存在多个具有相同的关键字的记录,若经过排序,这些记录的相对次序保持不变,即在原序列中,ri=rj,且ri在rj之前,而在排序后的序列中,ri仍在rj之前,则称这种排序算法是稳定的;否则称为不稳定的。归并排序,冒泡排序是稳定的。
    因此,本题参考答案是D。
    8、最小堆是一个键值序列{k1,k2,…, kn},对i=1,2,…,|n/2|,满足( )
    A.ki≤k2i≤k2i+1
    B.ki<k2i+1<k2i
    C.ki≤k2i且ki≤k2i+1(2i+1≤n)
    D.ki≤k2i 或ki≤k2i+1(2i+1≤n)
    解析:本题考点是最小堆的基本概念。
    堆是一种经过排序的完全二叉树,其中任一非终端节点的数据值均不大于(或不小于)其左孩子和右孩子节点的值。最大堆和最小堆是二叉堆的两种形式。 最大堆:根结点的键值是所有堆结点键值中最大者。 最小堆:根结点的键值是所有堆结点键值中最小者。
    因此,本题参考答案是C。
    9、设数组Data[0…m]作为循环队列SQ的存储空间,front为队头指针,rear为队尾指针,则执行出队操作的语句为( )
    A.front=front+1
    B.front=(front+1)% m
    C.rear=(rear+1)%m
    D.front=(front+1)%(m+1)
    解析:本题考点是队列的出队操作。
    队列是一种特殊的线性表,特殊之处在于它只允许在表的前端(front)进行删除操作,而在表的后端(rear)进行插入操作,和栈一样,队列是一种操作受限制的线性表。进行插入操作的端称为队尾,进行删除操作的端称为队头。出队操作的语句为front=(front+1)%(m+1)。
    因此,本题参考答案是D。
    10、以下说法错误的是( )
    A.树形结构的特点是一个结点可以有多个直接前趋
    B.线性结构中的一个结点至多只有一个直接后继
    C.树形结构可以表达(组织)更复杂的数据
    D.树(及一切树形结构)是一种"分支层次"结构
    解析:本题考点是树形结构的特点。
    树形结构的特点是一个结点最多有一个直接前趋。
    因此,本题参考答案是A。
    二、判断题
    1、中序遍历二叉排序树可以得到一个有序的序列( )
    A正确
    B错误
    解析:本题考点是二叉排序树的遍历。
    二叉排序树或者是一棵空树,或者是具有下列性质的二叉树:
    (1)若左子树不空,则左子树上所有结点的值均小于它的根结点的值;
    (2)若右子树不空,则右子树上所有结点的值均大于或等于它的根结点的值;
    (3)左、右子树也分别为二叉排序树;
    (4)没有键值相等的节点。 中序遍历二叉排序树可以得到一个有序的序列。
    因此,本题参考答案是A。
    2、用非递归方法实现递归算法时一定要使用递归工作栈。( )
    A正确
    B错误
    解析:本题考点是递归算法的非递实现。
    用非递归方法实现递归算法时不一定要使用递归工作栈,使用普通数组模拟栈即可。
    因此,本题参考答案是B。
    3、将f = 1 + 1/2 + 1/3+ … + 1/n转化为递归函数时,递归部分为f (n) = f (n-1) + 1/n,递归结束条件为f (1) = 1。( )
    A正确
    B错误
    解析:本题考点是递归函数的转化。
    程序调用自身的编程技巧称为递归。递归做为一种算法在程序设计语言中广泛应用。一个过程或函数在其定义或说明中有直接或间接调用自身的一种方法,它通常把一个大型复杂的问题层层转化为一个与原问题相似的规模较小的问题来求解,递归策略只需少量的程序就可描述出解题过程所需要的多次重复计算,大大地减少了程序的代码量。根据题意,递归结束条件为f (1) = 1。
    因此,本题参考答案是A。
    4、一个广义表的表头总是一个广义表。( )
    A正确
    B错误
    解析:本题考点是广义表的特点。
    广义表的表头是指表的第一个元素,表尾是指除表头外的其余元素构成的表,所以表尾是广义表,而表头不一定是。
    因此,本题参考答案是B。
    5、层次遍历初始堆可以得到一个有序的序列。( )
    A正确
    B错误
    数据结构习题解析解析:本题考点是初始堆的层次遍历。
    根据堆的定义,层次遍历初始堆不一定得到一个有序的序列。
    因此,本题参考答案是B。
    6、线性表的顺序存储表示优于链式存储表示。( )
    A正确
    B错误
    解析:本题考点是线性表的存储表示。
    线性表的顺序存储表示优于链式存储表示,这种说法是不准确的,比如对线性表进行插入和删除时,链式存储有优势。
    因此,本题参考答案是B。
    7、一个广义表 ( (a), ( (b), c), ( ( (d) ) ) ) 的表尾是 ( (b), c), ( ( (d) ) )。( )
    A正确
    B错误
    解析:本题考点是广义表相关基本概念。
    一个广义表 ( (a), ( (b), c), ( ( (d) ) ) ) 的表尾是( ( (b), c), ( ( (d) ) ))。
    因此,本题参考答案是B。
    8、当向一个最小堆插入一个具有最小值的元素时,该元素需要逐层向上调整,直到被调整到堆顶位置为止。( )
    A正确
    B错误
    解析:本题考点是堆的调整过程。
    堆是一种经过排序的完全二叉树,其中任一非终端节点的数据值均不大于(或不小于)其左孩子和右孩子节点的值。最大堆和最小堆是二叉堆的两种形式。 最大堆:根结点的键值是所有堆结点键值中最大者。 最小堆:根结点的键值是所有堆结点键值中最小者。 当向一个最小堆插入一个具有最小值的元素时,该元素需要逐层向上调整,直到被调整到堆顶位置为止。
    因此,本题参考答案是A。
    9、线性表的插入和删除总是伴随着大量数据的移动( )
    A正确
    B错误
    解析:本题考点是线性表的基本操作。
    线性表的插入和删除并不总是伴随着大量数据的移动,例如线性表是链式存储时移动代价较小。
    因此,本题参考答案是B。
    10、二叉树是一棵无序树。( )
    A正确
    B错误
    解析:本题考点是二叉树的定义和特点。
    二叉树是每个结点最多有两个子树的有序树。二叉树常被用于实现二叉查找树和二叉堆。值得注意的是,二叉树不是树的特殊情形。
    因此,本题参考答案是B。
    三、分析题
    1、设将整数a、b、c、d依次进栈,而只要栈非空,就可以将出栈操作夹入其中。请问能否得到出栈序列adbc和dcba?为什么?
    解析:本题考点是进栈和出栈的特点。
    栈是一种运算受限的线性表。其限制是仅允许在表的一端进行插入和删除运算。这一端被称为栈顶,相对地,把另一端称为栈底。向一个栈插入新元素又称作进栈、入栈或压栈,它是把新元素放到栈顶元素的上面,使之成为新的栈顶元素;从一个栈删除元素又称作出栈或退栈,它是把栈顶元素删除掉,使其相邻的元素成为新的栈顶元素。栈是一种后进先出的数据结构。 因此,本题答题要点如下:
    能得到dcba:push, push, push,push,pop, pop, pop,pop
    但不能得到adbc: 因为d出来的时候 b,c还在栈内,次序必然b在下c在上,因此紧跟d下一个出栈的必然是c而不是b。
    2、写出下列二叉树的前序序列、中序序列和后序序列。
    二叉树
    解析:本题考点是二叉树的前序、中序和后序遍历算法的基本思想。
    遍历是对树的一种最基本的运算,所谓遍历二叉树,就是按一定的规则和顺序走遍二叉树的所有结点,使每一个结点都被访问一次,而且只被访问一次。由于二叉树是非线性结构,因此,树的遍历实质上是将二叉树的各个结点转换成为一个线性序列来表示。
    先序遍历是首先访问根,再先序遍历左(右)子树,最后先序遍历右(左)子树。
    中序遍历是首先中序遍历左(右)子树,再访问根,最后中序遍历右(左)子树。
    后序遍历是首先后序遍历左(右)子树,再后序遍历右(左)子树,最后访问根。
    因此,本题答题要点如下:
    前序序列:CABEFDHG
    中序序列:ABFECHDG
    后序序列:BFEAHGDC
    3、简述链队的类型定义。
    数据结构习题解析解析:本题考点是队列的链式存储结构的表示。
    队列是一种特殊的线性表,特殊之处在于它只允许在表的前端(front)进行删除操作,而在表的后端(rear)进行插入操作,和栈一样,队列是一种操作受限制的线性表。进行插入操作的端称为队尾,进行删除操作的端称为队头。在队列的形成过程中,可以利用线性链表的原理,来生成一个队列。基于链表的队列,要动态创建和删除节点,效率较低,但是可以动态增长。因此,本题答题要点如下:
    typedef struct linked_queue
    {
    DataType data;
    struct linked_queue *next;
    }LqueueTp;
    typedef struct queueptr
    {
    LqueueTp *front, *rear;
    }QueptrTp;
    QueptrTp lq;
    4、把下图中的二叉树转化为森林。
    image.png
    数据结构习题解析解析:本题考点是二叉树转化为森林的基本方法。
    比如,若二叉树为空,树也为空;否则,由二叉树的根结点开始,延右指针向下走,直到为空,途经的结点个数是相应森林所含树的棵数;若某个结点的左指针非空,说明这个结点在树中必有孩子,并且从二叉树中该结点左指针所指结点开始,延右指针向下走,直到为空,途经的结点个数就是这个结点的孩子数目。因此,本题答题要点如下:
    二叉树转化成的森林为:
    森林

    展开全文
  • 数据结构面试

    千次阅读 多人点赞 2018-01-22 10:21:28
    数据结构面试 1.数据结构与算法常见笔试    第一章 数据结构与算法 一.算法的基本概念 计算机解题的过程实际上是在实施某种算法,这种算法称为计算机算法。 1.算法的基本特征:可行...
    数据结构面试题

    1.数据结构与算法常见笔试题  

     

    第一章 数据结构与算法

    .算法的基本概念

    计算机解题的过程实际上是在实施某种算法,这种算法称为计算机算法。

    1.算法的基本特征:可行性,确定性,有穷性,拥有足够的情报。

    2.算法的基本要素:算法中对数据的运算和操作、算法的控制结构。

    3.算法设计的基本方法:列举法、归纳法、递推、递归、减半递推技术、回溯法。

    4.算法设计的要求:正确性、可读性、健壮性、效率与低存储量需求


    .算法的复杂度

    1.算法的时间复杂度:指执行算法所需要的计算工作量

    2.算法的空间复杂度:执行这个算法所需要的内存空间


    .数据结构的定义

    1.数据的逻辑结构:反映数据元素之间的关系的数据元素集合的表示。数据的逻辑结构包括集合、线形结构、树形结构和图形结构四种。

    2.数据的存储结构:数据的逻辑结构在计算机存储空间种的存放形式称为数据的存储结构。常用的存储结构有顺序、链接、索引等存储结构。


    .数据结构的图形表示

    在数据结构中,没有前件的结点称为根结点;没有后件的结点成为终端结点。插入和删除是对数据结构的两种基本运算。还有查找、分类、合并、分解、复制和修改等。


    .线性结构和非线性结构

    根据数据结构中各数据元素之间前后件关系的复杂程度,一般将数据结构分为两大类型:线性结构和非线性结构。

    线性结构:非空数据结构满足:有且只有一个根结点;每个结点最多有一个前件,最多只有一个后件。非线性结构:如果一个数据结构不是线性结构,称之为非线性结构。

    常见的线性结构:线性表、栈、队列


    .线性表的定义

    线性表是n个元素构成的有限序列(A1A2A3……)。表中的每一个数据元素,除了第一个以外,有且只有一个前件。除了最后一个以外有且只有一个后件。即线性表是一个空表,或可以表示为(a1,a2,……an,其中ai(I=1,2,……n)是属于数据对象的元素,通常也称其为线性表中的一个结点。

    非空线性表有如下一些特征:

    1)有且只有一个根结点a1,它无前件;

    2)有且只有一个终端结点an,它无后件;

    3)除根结点与终端结点外,其他所有结点有且只有一个前件,也有且只有一个后件。线性表中结点的个数n称为线性表的长度。当n=0时称为空表。


    6.1线性表的顺序存储结构

    线性表的顺序表指的是用一组地址连续的存储单元依次存储线性表的数据元素。

    线性表的顺序存储结构具备如下两个基本特征:

    1.线性表中的所有元素所占的存储空间是连续的;

    2.线性表中各数据元素在存储空间中是按逻辑顺序依次存放的。

    线性表逻辑上相邻、物理也相邻,则已知第一个元素首地址和每个元素所占字节数,则可求出任一个元素首地址。

    假设线性表的每个元素需占用K个存储单元,并以所占的第一个单元的存储地址作为数据元素的存储位置。则线性表中第i+1个数据元素的存储位置LOC(ai+1)和第i个数据元素的存储位置LOC(ai)之间满足下列关系:

    LOC(ai+1)=LOC(ai)+K

    LOC(ai)=LOC(a1)+(i-1)*K     

    其中,LOC(a1)是线性表的第一个数据元素a1的存储位置,通常称做线性表的起始位置或基地址。

    因为在顺序存储结构中,每个数据元素地址可以通过公式①计算得到,所以线性表的顺序存储结构是随机存取的存储结构。

    在线性表的顺序存储结构下,可以对线性表做以下运算:

    插入、删除、查找、排序、分解、合并、复制、逆转


    6.1.1顺序表的插入运算

    线性表的插入运算是指在表的第i个位置上,插入一个新结点x,使长度为n的线性表(a1,a2aian)变成长度为n+1的线性表(a1,a2x,aian).

    该算法的时间主要花费在循环的结点后移语句上,执行次数是n-I+1

    I=n+1,最好情况,时间复杂度o(1)I=1,最坏情况,时间复杂度o(n)

    算法的平均时间复杂度为o(n)


    6.1.2顺序表的删除运算

    线性表的删除运算是指在表的第I个位置上,删除一个新结点x,使长度为n的线性表(a1,a2aian)变成长度为n-1的线性表(a1,a2ai-1,ai+1an).

    I=n,时间复杂度o(1),I=1,时间复杂度o(n) ,平均时间复杂度为o(n)


    6.2栈及其基本运算

    1. 什么是栈? 栈实际上也是一个线性表,只不过是一种特殊的线性表。栈是只能在表的一端进行插入和删除运算的线性表,通常称插入、删除这一端为栈顶(TOP),另一端为 栈底(BOTTOM)。当表中没有元素时称为空栈。栈顶元素总是后被插入的元素,从而也是最先被删除的元素;栈底元素总是最先被插入的元素,从而也是最后 才能被删除的元素。

    假设栈S=a1,a2,a3,……an),则a1称为栈底元素,an称为栈顶元素。栈中元素按a1,a2,a3……an的次序进栈,退栈的第一个元素应该是栈顶元素。即后进先出。


    6.2.1栈的顺序存储及其运算

    S1M)作为栈的顺序存储空间。M为栈的最大容量。

    栈的基本运算有三种:入栈、退栈与读栈顶元素。

    入栈运算:在栈顶位置插入一个新元素。

    首先将栈顶指针进一(TOP+1),然后将新元素插入到栈顶指针指向的位置。

    退栈运算:指取出栈顶元素并赋给一个指定的变量。

    首先将栈顶元素赋给一个指定的变量,然后将栈顶指针退一(TOP-1

    读栈顶元素:将栈顶元素赋给一个指定的变量。栈顶指针不会改变。

    6.3.队列及其基本运算

    1.什么是队列

    队列是只允许在一端删除,在另一端插入的顺序表,允许删除的一端叫做对头,允许插入的一端叫做对尾。

    队列的修改是先进先出。往队尾插入一个元素成为入队运算。从对头删除一个元素称为退队运算。

    2.循环队列及其运算

     实际应用中,队列的顺序存储结构一般采用循环队列的形式。所谓循环队列,就是将队列存储空间的最后一个位置绕到第一个位置,形成逻辑上的环状空间。在循环队列中,,用队尾指针rear指向队列中的队尾元素,用排头指针front指向排头元素的前一个位置,因此,从排头指针front指向的后一个位置直到队 尾指针 rear指向的位置之间所有的元素均为队列中的元素。

    在实际使用循环队列时,为了能区分队满还是队列空,通常需要增加一个标志S

    队列空,则S=0rear=front=m     队列满,则S=1rear=front=m

    循环队列主要有两种基本运算:入队运算和退队运算

    入队运算

    指在循环队列的队尾加入一个新元素,首先rear=rear+1,rear=m+1时,置rear=1,然后将新元素插入到队尾指针指向的位置。当S=1rear=front,说明队列已满,不能进行入队运算,称为“上溢”。

    退队运算

    指在循环队列的排头位置退出一个元素并赋给指定的变量。首先front=front+1,并当front=m+1时,置front=1,然后将排头指针指向的元素赋给指定的变量。当循环队列为空S=0,不能进行退队运算,这种情况成为“下溢”。


    6.4线性单链表的结构及其基本运算

    1.线性单链表的基本概念

    组任意的存储单元存储线性表的数据元素,因此,为了表示每个数据元素ai与其直接后继数据元素ai+1之间的逻辑关系,对数据元素ai来说,除了存储其本身的信息之外,还需存储一个指示其直接后继的信息(即直接后继的存储位置)。这两部分信息组成数据元素ai的存储映象,成为结点。它包括两个域:其中存储数据元素信息的域称为数据域,存储直接后继存储位置的域称为指针域。指针域中存储的信息称做指针或链。n个结点链结成一个链表,即为线性表(a1, a2,……,an)的链式存储结构。又由于此链表的每个结点中只包含一个指针域,故又称线性链表或单链表。

    有时,我们在单链表的第一个结点之前附设一个结点,称之为头结点,它指向表中第一个结点。头结点的数据域可以不存储任何信息,也可存储如线性表的长度等类的附加信息,头结点的指针域存储指向第一个结点的指针(即第一个元素结点的存储位置)。

    在单链表中,取得第I个数据元素必须从头指针出发寻找,因此,单链表是非随机存取的存储结构  链表的形式:单向,双向

    2.线性单链表的存储结构

    3.带列的栈与队列

    栈也是线性表,也可以采用链式存储结构。

    队列也是线性表,也可以采用链式存储结构。


    6.4.1线性链表的基本运算1.线性链表的插入2.线性链表的删除


    6.5双向链表的结构及其基本运算

    在双向链表的结点中有两个指针域,其一指向直接后继,另一指向直接前驱。


    6.6循环链表的结构及其基本运算

    是另一种形式的链式存储结构,它的特点是表中最后一个结点的指针域指向头结点,整个链表形成一个环。因此,从表中任一结点出发均可找到表中其他结点。


    7.树的定义

    树是一种简单的非线性结构。树型结构的特点:

    1.每个结点只有一个前件,称为父结点,没有前件的结点只有一个,称为树的根结点。

    2.每一个结点可以有多个后件结点,称为该结点的子结点。没有后件的结点称为叶子结点

    3.一个结点所拥有的后件个数称为树的结点度

    4.树的最大层次称为树的深度。


    7.1二叉树的定义及其基本性质

    7.1.1二叉树是另一种树型结构,它的特点是每个结点至多只有二棵子树(即二叉树中不存在度大于2的结点),并且,二叉树的子树有左右之分,其次序不能任意颠倒。

    7.1.2二叉树的基本性质

    ①在二叉树的第I层上至多有2i-1个结点。

    ②深度为k的二叉树至多有2k-1个结点(k>=1)

    ③在任意一个二叉树中,度为0的结点总是比度为2的结点多一个;

    ④具有个结点的二叉树,其深度至少为[log2n]+1

    一棵深度为k且有2k-1个结点的二叉树称为满二叉树。这种树的特点是每一层上的结点数都是最大结点数。

    7.1.3满二叉树与完全二叉树

    满二叉树:除最后一层以外,每一层上的所有结点都有两个子结点。在满二叉树的第K层上有2K-1个结点,且深度为M的满二叉树右2M-1个结点

    完全二叉树:除最后一层以外,每一层上的结点数均达到最大值;在最后一层上只缺少右边的若干结点。具有N个结点的完全二叉树的深度为[log2n]+1

    完全二叉树总结点数为N

    N为奇数,则叶子结点数为(N+1/2N为偶数,则叶子结点数为N/2

    7.1.4二叉树的存储结构

    二叉树通常采用链式存储结构

    二叉树具有下列重要特性:

        性质在二叉树的第i层上至多有2i-1个结点(i1)

         利用归纳法容易证得此性质。

         i=1时,只有一个根结点。 显然,2i-1=20=1是对的。

         现在假定对所有的j1j

         由归纳假设:第i-1层上至多有2i-2个结点。由于二叉树的每个结点的度至多为2,故在第i层上的最大结点数为第i-1层上的最大结点数的2倍,即2*2i-2=2i-1

        性质深度为k的二叉树至多有2k-1个结点,(k1)

        由性质1可见,深度为k的二叉树的最大结点数为

    k                        k

    (i层上的最大结点数) =2i-1=2k -1

    i=1                     i=1

        性质对任何一棵二叉树T,如果其终端结点数为n0,度为2的结点数为n2,则n0=n2+1

     

         n1为二叉树T中度为1的结点数。因为二叉树中所有结点的度均小于或等于2所以其结点总数为

     

    n=n0+n1+n2 (61) 

         再看二叉树中的分支数。除了根结点外,其余结点都有一个分支进入,设B为分支总数,则n=B+1。由于这些分支是由度为12的结点射出的,所以又有B=n1+ 2n2

     

    n=n1+2*n2+1 (62) 

         于是得由式(61)(62)n0=n2+1

     

    7.1.5二叉树的遍历

    就是遵从某种次序,访问二叉树中的所有结点,使得每个结点仅被访问一次。一般先左后右。

    1.前序遍历DLR首先访问根结点,然后遍历左子树,最后遍历右子树。

    2.中序遍历LDR首先遍历左子树,然后根结点,最后右子树

    3.后序遍历LRD首先遍历左子树,然后遍历右子树,最后访问根结点。


    8.查找

    8.1顺序查找与二分查找

    1.顺序查找 在两种情况下只能用顺序查找:线性表为无序表、链式存储结构的有序表

    2.二分查找 只适用于顺序存储的有序表(从小到大)。

    对于长度为N的有序线性表,在最坏情况下,二分查找只需要比较log2N次,而顺序查找要比较N次。 排序:指将一个无序序列整理成按值非递减顺序排列的有序序列。


    8.2交换类排序法

    冒泡排序与快速排序法属于交换类的排序方法

    1.冒泡排序法 假设线性表的长度为N,则在最坏的情况下,冒跑排序需要经过N/2遍的从前往后的扫描和N/2遍的从后往前的扫描,需要的比较次数为NN-1/2

    2.快速排序法

    8.3选择类排序法 1.简单选择排序法2.堆排序法

    8.4插入类排序法 1.简单插入排序法2.希尔排序法

                             最坏情况下      最好情况下     说明

     交换排序      冒泡排序     n(n-1)/2            最简单的交换排序。在待排序的元素序列基本有序的前提下,效率最高

         快速排序      n(n-1)/2      O(Nlog2 N)     

     插入排序      简单插入排序     n(n-1)/2            每个元素距其最终位置不远时适用

         希尔排序      O(n1.5)           

     选择排序      简单选择排序     n(n-1)/2           

         堆排序      O(nlog2n)            适用于较大规模的线性表


    练习:

    1.栈和队列的共同特点是(只允许在端点处插入和删除元素)

    2.如果进栈序列为e1,e2,e3,e4,则可能的出栈序列是(e2,e4,e3,e1

    3.栈底至栈顶依次存放元素ABCD,在第五个元素E入栈前,栈中元素可以出栈,则出栈序列可能是(DCBEA

    4.栈通常采用的两种存储结构是(线性存储结构和链表存储结构)

    5.下列关于栈的叙述正确的是(D

         A.栈是非线性结构B.栈是一种树状结构C.栈具有先进先出的特征D.栈有后进先出的特征

    6.链表不具有的特点是(BA.不必事先估计存储空间      B.可随机访问任一元素

    C.插入删除不需要移动元素      D.所需空间与线性表长度成正比

    7.用链表表示线性表的优点是(便于插入和删除操作)

    8.在单链表中,增加头结点的目的是(方便运算的实现)

    9.循环链表的主要优点是(从表中任一结点出发都能访问到整个链表)

    10.线性表L=(a1,a2,a3,……ai,……an),下列说法正确的是(D

         A.每个元素都有一个直接前件和直接后件   B.线性表中至少要有一个元素

         C.表中诸元素的排列顺序必须是由小到大或由大到小

         D.除第一个和最后一个元素外,其余每个元素都有一个且只有一个直接前件和直接后件

    11.线性表若采用链式存储结构时,要求内存中可用存储单元的地址(D

    A.必须是连续的 B.部分地址必须是连续的C.一定是不连续的D.连续不连续都可以

    12.线性表的顺序存储结构和线性表的链式存储结构分别是(随机存取的存储结构、顺序存取的存储结构)

    13.树是结点的集合,它的根结点数目是(有且只有1

    14.在深度为5的满二叉树中,叶子结点的个数为(31

    15.具有3个结点的二叉树有(5种形态)

    16.设一棵二叉树中有3个叶子结点,有8个度为1的结点,则该二叉树中总的结点数为(13

    17.已知二叉树后序遍历序列是dabec,中序遍历序列是debac,它的前序遍历序列是(cedba

    18.已知一棵二叉树前序遍历和中序遍历分别为ABDEGCFHDBGEACHF,则该二叉树的后序遍历为(DGEBHFCA

    19.若某二叉树的前序遍历访问顺序是abdgcefh,中序遍历访问顺序是dgbaechf,则其后序遍历的结点访问顺序是(gdbehfca

    20.数据库保护分为:安全性控制、 完整性控制 、并发性控制和数据的恢复。

     

    1. 在计算机中,算法是指(解题方案的准确而完整的描述)

    2.在下列选项中,哪个不是一个算法一般应该具有的基本特征(无穷性)

    说明:算法的四个基本特征是:可行性、确定性、有穷性和拥有足够的情报。

    3. 算法一般都可以用哪几种控制结构组合而成(顺序、选择、循环)

    4.算法的时间复杂度是指(算法执行过程中所需要的基本运算次数)

    5. 算法的空间复杂度是指(执行过程中所需要的存储空间)

    6. 算法分析的目的是(分析算法的效率以求改进)

    7. 下列叙述正确的是(C

    A.算法的执行效率与数据的存储结构无关

    B.算法的空间复杂度是指算法程序中指令(或语句)的条数

    C.算法的有穷性是指算法必须能在执行有限个步骤之后终止

    D.算法的时间复杂度是指执行算法程序所需要的时间

    8.数据结构作为计算机的一门学科,主要研究数据的逻辑结构、对各种数据结构进行的运算,以及(数据的存储结构)

    9. 数据结构中,与所使用的计算机无关的是数据的(C

    A.存储结构   B.物理结构    C.逻辑结构    D.物理和存储结构

    10. 下列叙述中,错误的是(B

    A.数据的存储结构与数据处理的效率密切相关

    B.数据的存储结构与数据处理的效率无关

    C.数据的存储结构在计算机中所占的空间不一定是连续的

    D.一种数据的逻辑结构可以有多种存储结构

    11. 数据的存储结构是指(数据的逻辑结构在计算机中的表示)

    12. 数据的逻辑结构是指(反映数据元素之间逻辑关系的数据结构)

    13. 根据数据结构中各数据元素之间前后件关系的复杂程度,一般将数据结构分为(线性结构和非线性结构)

    14. 下列数据结构具有记忆功能的是(CA.队列B.循环队列C.栈D.顺序表

    15. 下列数据结构中,按先进后出原则组织数据的是(B

    A.线性链表   B.栈           C.循环链表       D.顺序表

    16. 递归算法一般需要利用(队列)实现。

    17. 下列关于栈的叙述中正确的是(DA.在栈中只能插入数据B.在栈中只能删除数据

    C.栈是先进先出的线性表            D.栈是先进后出的线性表

    18. 栈底至栈顶依次存放元素ABCD,在第五个元素E入栈前,栈中元素可以出栈,则出栈序列可能是(DCBEA

    19.如果进栈序列为e1,e2,e3,e4,则可能的出栈序列是(e2,e4,e3,e1

    20. 由两个栈共享一个存储空间的好处是(节省存储空间,降低上溢发生的机率)

    21. 应用程序在执行过程中,需要通过打印机输出数据时,一般先形成一个打印作业,将其存放在硬盘中的一个指定(队列)中,当打印机空闲时,就会按先来先服务的方式从中取出待打印的作业进行打印。

    22.下列关于队列的叙述中正确的是(CA.在队列中只能插入数据B.在队列中只能删除数据  C.队列是先进先出的线性表           D.队列是先进后出的线性表

    23.下列叙述中,正确的是(DA.线性链表中的各元素在存储空间中的位置必须是连续的

    B.线性链表中的表头元素一定存储在其他元素的前面 C.线性链表中的各元素在存储空间中的位置不一定是连续的,但表头元素一定存储在其他元素的前面D.线性链表中的各元素在存储空间中的位置不一定是连续的,且各元素的存储顺序也是任意的

    24.下列叙述中正确的是(AA.线性表是线性结构     B.栈与队列是非线性结构

    C.线性链表是非线性结构                                 D.二叉树是线性结构

    25. 线性表L=(a1,a2,a3,……ai,……an),下列说法正确的是(D

    A.每个元素都有一个直接前件和直接后件      B.线性表中至少要有一个元素

    C.表中诸元素的排列顺序必须是由小到大或由大到小D.除第一个元素和最后一个元素外,其余每个元素都有一个且只有一个直接前件和直接后件

    26.线性表若采用链式存储结构时,要求内存中可用存储单元的地址(连续不连续都可以)

    27. 链表不具有的特点是(BA.不必事先估计存储空间           B.可随机访问任一元素

    C.插入删除不需要移动元素            D.所需空间与线性表长度成正比

    28. 非空的循环单链表head的尾结点(由p所指向),满足(p->next=head

    29.与单向链表相比,双向链表的优点之一是(更容易访问相邻结点)

    30. 在(D)中,只要指出表中任何一个结点的位置,就可以从它出发依次访问到表中其他所有结点。A.线性单链表           B.双向链表           C.线性链表           D.循环链表

    31. 以下数据结构属于非线性数据结构的是(CA.队列     B.线性表C.二叉树     D.栈

    32.树是结点的集合,它的根结点数目是(有且只有1

    33.具有3个结点的二叉树有(5种形态)

    34. 在一棵二叉树上第8层的结点数最多是(128) 注:2K-1

    35. 在深度为5的满二叉树中,叶子结点的个数为(16) 注:2n-1

    36. 在深度为5的满二叉树中,共有(31)个结点。 注:2n1

    37.设一棵完全二叉树共有699个结点,则在该二叉树中的叶子结点数为(350

    说明:完全二叉树总结点数为N,若N为奇数,则叶子结点数为(N+1/2;若N为偶数,则叶子结点数为N/2

    38. 设有下列二叉树,对此二叉树中序遍历的结果是(B

    AABCDEF     

    BDBEAFC

    CABDECF     

    DDEBFCA

    39.已知二叉树后序遍历序列是dabec,中序遍历序列debac,它的前序遍历序列是(cedba

    40. 已知一棵二叉树前序遍历和中序遍历分别为ABDEGCFHDBGEACHF,则该二叉树的后序遍历为(DGEBHFCA

    41.若某二叉树的前序遍历访问顺序是abdgcefh,中序遍历访问顺序是dgbaechf,则其后序遍历的结点访问顺序是(gdbehfca

    42. 串的长度是(串中所含字符的个数)

    43.设有两个串pq,求qp中首次出现位置的运算称做(模式匹配)

    44. N个顶点的连通图中边的条数至少为(N-1

    45.N个顶点的强连通图的边数至少有(N

    46.对长度为n的线性表进行顺序查找,在最坏情况下所需要的比较次数为(N

    47. 最简单的交换排序方法是(冒泡排序)

    48.假设线性表的长度为n,则在最坏情况下,冒泡排序需要的比较次数为(n(n-1)/2

    49. 在待排序的元素序列基本有序的前提下,效率最高的排序方法是(冒泡排序)

    50. 在最坏情况下,下列顺序方法中时间复杂度最小的是(堆排序)

    51. 希尔排序法属于(插入类排序)

    52. 堆排序法属于(选择类排序)

    53. 在下列几种排序方法中,要求内存量最大的是(归并排序)

    54. 已知数据表A中每个元素距其最终位置不远,为节省时间,应采用(直接插入排序)

    55. 算法的基本特征是可行性、确定性、 有穷性   和拥有足够的情报。

     

     

    1.一个算法通常由两种基本要素组成:一是对数据对象的运算和操作,二是算法的控制结构。

    1. 算法的复杂度主要包括时间复杂度和 空间 复杂度。

    2. 实现算法所需的存储单元多少和算法的工作量大小分别称为算法的空间复杂度和时间复杂度 。

    3.所谓数据处理是指对数据集合中的各元素以各种方式进行运算,包括插入、删除、查找、更改等运算,也包括对数据元素进行分析。

    4.数据结构是指相互有关联的 数据元素 的集合。

    5.数据结构分为逻辑结构与存储结构,线性链表属于 存储结构 。

    6.数据结构包括数据的 逻辑 结构和数据的存储结构。

    7. 数据结构包括数据的逻辑结构、数据的 存储结构 以及对数据的操作运算。

    8.数据元素之间的任何关系都可以用 前趋和后继 关系来描述。

    9.数据的逻辑结构有线性结构和非线性结构两大类。

    10.常用的存储结构有顺序、链接、 索引 等存储结构。

    11. 顺序存储方法是把逻辑上相邻的结点存储在物理位置   相邻 的存储单元中。

    12. 栈的基本运算有三种:入栈、退栈与读栈顶元素 。

    13. 队列主要有两种基本运算:入队运算与 退队运算 。

    14. 在实际应用中,带链的栈可以用来收集计算机存储空间中所有空闲的存储结点,这种带链的栈称为 可利用栈 。

    15.栈和队列通常采用的存储结构是 链式存储和顺序存储   

    16.当线性表采用顺序存储结构实现存储时,其主要特点是 逻辑结构中相邻的结点在存储结构中仍相邻 。

    17. 循环队列主要有两种基本运算:入队运算与退队运算。每进行一次入队运算,队尾指针就 进1

    18.当循环队列非空且队尾指针等于对头指针时,说明循环队列已满,不能进行入队运算。这种情况称为 上溢  

    19.当循环队列为空时,不能进行退队运算,这种情况称为 下溢 。

    20. 在一个容量为25的循环队列中,若头指针front=16,尾指针rear=9,则该循环队列中共有18个元素。注:当rear

    rear>front时,元素个数=rearfront

    21. 在一个容量为15的循环队列中,若头指针front=6,尾指针rear=9,则该循环队列中共有3个元素。

    22.顺序查找一般是指在 线性表 中查找指定的元素。

    23.在计算机中存放线性表,一种最简单的方法是 顺序存储 。

    24.在程序设计语言中,通常定义一个 一维数组 来表示线性表的顺序存储空间。

    25.在链式存储方式中,要求每个结点由两部分组成:一部分用于存放数据元素值,称为数据域,另一部分用于存放指针,称为 指针域 。其中指针用于指向该结点的前一个或后一个结点(即前件或后件)。

    26.在 线性单链表中 ,每一个结点只有一个指针域,由这个指针只能找到后继结点,但不能找到前驱结点。

    27. 为了要在线性链表中插入一个新元素,首先要给该元素分配一个 新结点 ,以便用于存储该元素的值。

    28. 在线性链表中删除一个元素后,只需要改变被删除元素所在结点的前一个结点的 指针域 即可。

    29. 用链表表示线性表的突出优点是 便于插入和删除操作 。

    30. 在树形结构中,树根结点没有   前件 。

    31. 在树结构中,一个结点所拥有的后件个数称为该结点的度。叶子结点的度为 0

    32. 设一棵二叉树中有3个叶子结点,8个度为1的结点,则该二叉树中总的结点数为13

    33. 设一棵完全二叉树共有739个结点,则在该二叉树中有370个叶子结点。

    34. 设一棵完全二叉树共有700个结点,则在该二叉树中有350个叶子结点。

    35. 在先左后右的原则下,根据访问根结点的次序,二叉树的遍历可以分为三种:前序遍历、 中序 遍历和后序遍历。

    36. 若串S="Program",则其子串的数目是29。 注:n(n+1)/2+1

    37. 若串S=MathTypes”,则其子串的数目是46

    38. 对长度为n的线性表进行插入一个新元素或删除一个元素时,在最坏情况下所需要的比较次数为n

    39. 在长度为n的有序线性表中进行顺序查找。最坏的情况下,需要的比较次数为  n   

    40. 在长度为n的有序线性表中进行二分查找。最坏的情况下,需要的比较次数为log2n

    41. 长度为n的顺序存储线性表中,当在任何位置上插入一个元素概率都相等时,插入一个元素所需移动元素的平均个数为n/2

    42. 排序是计算机程序设计中的一种重要操作,常见的排序方法有插入排序、 交换排序 和选择排序等。

    43. 快速排序法可以实现通过一次交换而消除多个 逆序 。

    44. 快速排序法的关键是对线性表进行 分割 。

    45. 冒泡排序算法在最好的情况下的元素交换次数为 0

    46. 在最坏情况下,冒泡排序的时间复杂度为 n(n-1) /2

    47. 对于长度为n的线性表,在最坏情况下,快速排序所需要的比较次数为n(n-1) /2

    48.在最坏情况下,简单插入排序需要比较的次数为 n(n-1) /2

    49.在最坏情况下,希尔排序需要比较的次数为 O(n1.5)。注:括号里是n1.5次方。

    50. 在最坏情况下,简单选择排序需要比较的次数为 n(n-1) /2

    51. 在最坏情况下,堆排序需要比较的次数为 o(nlog2n)

    52.对于输入为N个数进行快速排序算法的平均时间复杂度是O(Nlog2 N) 


    展开全文
  • 数据结构计算题

    千次阅读 2020-08-07 13:20:51
    1、将下列函数按它们在 n 时的无穷大阶数,从小到大排列。 ...2、对下列用二元组表示的数据结构 , 试分别画出对应的逻辑结构图, 并指出属于何种结构。 ⑴ A=(D,R), 其中 D={a1, a2, a3, a4} ,R

    1、将下列函数按它们在 n 时的无穷大阶数,从小到大排列。
    n, n-n3+7n5, nlogn, 2n/2, n3, log2n, n1/2+log2n, (3/2)n, n!,
    n2+log2n
    【解答】 log2n, n1/2+log2n, n, nlog2n, n2+log2n, n3, n-n3+7n5,
    2n/2, (3/2)n, n!
    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述

    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述

    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述

    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述

    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述

    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述

    2、对下列用二元组表示的数据结构 , 试分别画出对应的逻辑结构图,

    并指出属于何种结构。
    ⑴ A=(D,R), 其中 D={a1, a2, a3, a4} ,R={ }
    ⑵ B=(D,R), 其中 D={a, b, c, d, e, f} ,R={,}
    ⑶ C=( D ,R),其中 D={a,b,c,d,e,f} ,R={,}
    ⑷ D=(D,R), 其中 D={1, 2, 3, 4, 5, 6} ,
    R={(1, 2) ,(1, 4) ,(2, 3) ,(2, 4) ,(3, 4) ,(3, 5) ,(3, 6) ,
    (4, 6)}
    【解答】⑴ 属于集合,其逻辑结构图如图 1-4(a) 所示;⑵ 属于线
    性结构,其逻辑结构图如图 1-4(b) 所示;
    ⑶ 属于树结构,其逻辑结构图如图 1-4© 所示;⑷ 属于图结构,
    其逻辑结构图如图 1-4(d) 所示。
    在这里插入图片描述
    在这里插入图片描述
    3、证明:对任一满二叉树,其分枝数 B=2(n0-1) 。(其中,n0 为终
    端结点数)
    【解答】因为在满二叉树中没有度为 1 的结点,所以有:
    n=n0+n2
    设 B为树中分枝数,则
    n=B+1
    所以
    B=n0 +n2-1
    再由二叉树性质:
    n0=n2+1
    代入上式有:
    B=n0+n0-1-1=2(n0-1)
    在这里插入图片描述
    4、证明:已知一棵二叉树的前序序列和中序序列,则可唯一确定该
    二叉树。
    【解答】证明采用归纳法。
    设二叉树的前序遍历序列为 a1a2a3, an,中序遍历序列为 b1b2b3,
    bn。
    当 n=1 时,前序遍历序列为 a1,中序遍历序列为 b1,二叉树只有一
    个根结点,所以, a1= b1,可以唯一
    确定该二叉树;
    假设当 n<=k时,前序遍历序列 a1a2a3, ak 和中序遍历序列 b1b2b3,
    bk 可唯一确定该二叉树,下面证
    明当 n=k+1 时,前序遍历序列 a1a2a3, akak+1 和中序遍历序列
    b1b2b3, bk bk+1 可唯一确定一棵二叉树。
    在前序遍历序列中第一个访问的一定是根结点, 即二叉树的根结点是
    a1,在中序遍历序列中查找值为 a1的结点,
    假设为 bi ,则 a1=bi 且 b1b2, bi-1 是对根结点 a1 的左子树进行中序遍历的结果,前序遍历序列a2a3, ai 是对根结点 a1 的左子树进行前序遍历的结果,
    由归纳假设,前序遍历序列 a2a3, ai 和中序遍历序列 b1b2, bi-1 唯一确定了根结点的左子树, 同样可证前序遍历序列 ai+1ai+2 , ak+1 和中序遍历序列bi+1bi+2 , bk+1 唯一确定了根结点的右子树。
    在这里插入图片描述
    5、已知一棵度为 m的树中有: n1 个度为 1 的结点,n2 个度为 2 的结
    点,, , nm个度为 m的结点,问该树中共有多少个叶子结点?
    【解答】设该树的总结点数为 n,则
    n=n0+n1+n2+,+nm
    又:
    n=分枝数+1=0×n0+1×n1+2×n2+, +m×nm+1
    由上述两式可得:
    n0= n2+2n3+,+(m -1)nm+1
    在这里插入图片描述
    6、对给定的一组权值 W=(5,2,9,11,8,3,7),试构造相应
    的哈夫曼树,并计算它的带权路径长度。
    【解答】构造的哈夫曼树如图 5-13 所示。
    zzzz
    树的带权路径长度为:
    WPL=2 ×4+3×4+5×3+7×3+8×3+9×2+11×2
    =120
    在这里插入图片描述
    7、已知某字符串 S中共有 8 种字符,各种字符分别出现 2 次、1 次、
    4 次、5 次、7 次、3 次、4 次和 9 次,对该字符串用 [0 ,1] 进行前缀编码,问该字符串的编码至少有多少位。
    【解答】以各字符出现的次数作为叶子结点的权值构造的哈夫曼编码
    树如图 5-14 所示。其带权路径长度
    =2×5+1×5+3×4+5×3+9×2+4×3+4×3+7×2=98,所以,该字符 z
    在这里插入图片描述
    8、已知散列函数 H(k)=k mod 12 ,键值序列为 (25, 37, 52, 43, 84,
    99, 120, 15, 26, 11, 70, 82) ,采用拉链法处理冲突,试构造开散列表,并计算查找成功的平均查找长度。
    【解答】 H(25)=1, H(37)=1, H(52)=4, H(43)=7, H(84)=0, H(99)=3,
    H(120)=0, H(15)=3, H(26)=2, H(11)=11, H(70)=10, H(82)=10
    构造的开散列表如下:
    平均查找长度 ASL=(8×1+4×2)/12=16/12
    在这里插入图片描述

    9、已知关键码序列为( Jan, Feb, Mar, Apr, May, Jun, Jul, Aug,

    Sep, Oct, Nov, Dec ),散列表的地址空间
    为 0~16,设散列函数为 H(x)= ,其中 i 为关键码中第一个字母在字
    母表中的序号,采用线性探测
    法和链地址法处理冲突, 试分别构造散列表, 并求等概率情况下查找
    成功的平均查找长度。
    【 解 答 】 H(Jan)=10/2=5, H(Feb)=6/2=3, H(Mar)=13/2=6,
    H(Apr)=1/2=0
    H(May)=13/2=6, H(Jun)=10/25, H(Jul)=10/25, H(Aug)=1/2=0
    H(Sep)=19/2=8, H(Oct) =15/2=7, H(Nov) =14/2=7, H(Dec) =4/2=2
    采用线性探测法处理冲突,得到的闭散列表如下:
    平均查找长度 =(1+1+1+1+2+4+5+2+3+5+6+1)/12=32/12
    采用链地址法处理冲突,得到的开散列表如下:
    平均查找长度 =(1×7+2×4+3×1)/12=18/12 Image
    在这里插入图片描述

    10、试推导含有 12 个结点的平衡二叉树的最大深度, 并画出以棵这样

    的树。
    【解答】令 Fk 表示含有最少结点的深度为 k 的平衡二叉树的结点树
    目,则:
    F1=1,F2=2,, , Fn= Fn-2+Fn-1+1。含有 12 个结点的平衡二叉树的最大深度为 5,例如:
    在这里插入图片描述

    11、如果只想得到一个序列中第 k 个最小元素之前的部分排序序列,

    最好采用什么排序方法?为什么?对于序列{57, 40, 38, 11, 13, 34, 48, 75, 25, 6, 19, 9, 7} ,得到其第 4 个最小元素之前的部分序列 {6,7,9,11} ,使用所选择的排序算法时,要执行多少次比较?
    【解答】采用堆排序最合适, 依题意可知只需取得第 k 个最小元素之
    前的排序序列时,堆排序的时间复杂度Ο(n+klog2n) ,若 k≤nlog2n ,则得到的时间复杂性是 Ο(n) 。
    对于上述序列得到其前 4 个最小元素, 使用堆排序实现时, 执行的比较次数如下:
    初始建堆:比较 20 次,得到 6;
    第一次调整:比较 5 次,得到 7;
    第二次调整:比较 4 次,得到 9;
    第三次调整:比较 5 次,得到 11。
    在这里插入图片描述

    12、. 写出计算单链表 head(head 为单链表的表头)中数据域 data 值为 m的结点个数的算法。

    int count (Node *head)
    // 计算单链表 head 中数据域 data 值为 m的结点个数
    { Node *p=head->next;
    int n=0;
    while (p!=NULL)
    {if (p->data==m)
    n++;
    p=p->next;
    }
    return n;
    }// count
    在这里插入图片描述

    13、 已知非空单链表 head,试设计一个算法,交换 p 所指结点与其后继结点在链表中的位置。

    解答:
    int revers(listnode *head, listnode p)
    /
    交换 p 所指结点与其后继结点在链表中的位置 */
    { if (p->next==NULL) return 0 ;
    listnode *q=head;
    while (q->next!=p) q=q->next;
    {r=p->next ;q->next=r;
    p->next =r->next ; r->next=p;
    return 1;
    }// revers
    在这里插入图片描述

    14、 线性表用带头结点的单向链表示,试写出删除表中所有 data 域为零的元素的算法。

    解答:
    解: int DeleteItem(Node * head)
    { Node *p=head;
    // 声明指针 p,并令其指向链表头结点
    while (p->next!=NULL)
    {if(p->nex->data==0)
    p->next=p->next->next.
    else p=p->next; // 指针下移
    }
    }
    在这里插入图片描述

    15、试设计一算法,计算带头结点的单链表 head(head 指向表头 ) 的结点个数。

    解答:
    int Length( )
    // 计算带表头结点的单链表 head 的长度
    {Node *p=head->next;
    int count=0;
    while (p!=NULL)
    {p=p->next; count ++;}
    return count;
    }
    在这里插入图片描述

    16、试设计一算法,计算带头结点的单链表 head(head 指向表头 ) 的结点个数。

    解答:
    int Length( )
    // 计算带表头结点的单链表 head 的长度
    {Node *p=head->next;
    int count=0;
    while (p!=NULL)
    {p=p->next; count ++;}
    return count;
    }
    在这里插入图片描述

    17、判断单链表 head(head 指向表头 ) 是否是递增的。

    解答:【编者注: 链表无头结点】
    int order(Node *head)
    {Node *p=head;
    while(p->next!=NULL)
    if(p->datanext->data)
    p=p->next;
    else
    break;
    if(p->next==NULL)
    return 1;
    else
    return 0;
    }
    在这里插入图片描述

    18、设计一个算法,在一个单链表 head 中找出值最小的元素。

    解答:【编者注: 链表无头结点】

    int Min(Node * head )
    // 在单链表 head 中找出值最小的元素
    { Node *p=head;
    int min=p->data;
    while (p->next!=NULL)
    { if(p->next->data<min) min=p->next->data;
    p=p->next;
    }
    return min;
    }
    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述

    19、设有两个单链表 L 和 L1, 其结点结构为 (data,next), 试编写算法判断链表 L1 中的各元素是否都是单链表

    L 中的元素。
    解答:
    int SubLnk(Node *L, Node *L1)
    {Node *p1=L1;
    while(p1!=NULL)
    {Node *p=L;
    while((p!=NULL)&&(p1->data!=p->data))
    p=p->next;
    if (p==NULL) return 0; // 【编者注: L1 中元素未在 L 中】
    else p1=p1->next;
    }
    return 1;
    }
    在这里插入图片描述
    在这里插入图片描述

    20、设有一个正整数序列组成带头结点的单链表 head,试编写算法确定在序列中比正整数 x 大的数有几个。

    (8 分)
    解答:
    int count (Node * head ,int x )
    ∥在带头结点的单链表 head 中,确定序列中比正整数 x 大的数有几个
    {
    Node p=head->next;
    int count=0;
    while (p!=NULL)
    { if (p->data>x) count ++;
    p=p->next;
    }
    return count;
    } ∥算法 count 结束
    在这里插入图片描述
    在这里插入图片描述
    21、对于一个队列,如果输入项序列由 1,2,3,4 所组成,试给出全部可能的输出序列。
    答: 1,2,3,4
    22、将算术表达式 a+b
    (c+d/e )转为后缀表达式。
    答: B .abcde/++
    在这里插入图片描述
    23、将表达式 ((a+b)-c
    (d+e)-f)(g+h) 改写成后缀表达式。
    答:后缀表达式为: ab+cde+
    -f-gh+*
    在这里插入图片描述
    24、将算术表达式 a*(b+c)-d 转为后缀表达式。
    答: abc+*d-
    在这里插入图片描述
    25、 写出中缀表达式 A-(B+C/D)*E 的后缀形式。
    答:中缀表达式 A-(B+C/D)E 的后缀形式是: ABCD/+E-。
    在这里插入图片描述
    26、 设一棵二叉树以二叉链表为存储结构,设计一个算法交换二叉树中每个结点的左子女和右子女。 (12 分)
    解答:
    void exchange(BinTreeNode * t)
    {if (t!=NULL)
    BinTreeNode * temp;
    if((t->lchild!=NULL)||(t->rchild!=NULL))
    {temp= t->lchild;
    t->lchild= t->rchild;
    t->rchild= temp;
    exchange(t->lchild);
    exchange(t->rchild);
    }
    }
    在这里插入图片描述
    在这里插入图片描述
    27、 设一棵二叉树以二叉链表为存储结构,试设计一个算法计算二叉树中叶子结点的个数。
    (12 分)
    解答: void countleaf(BinTreeNode * t,int &count)
    { if(t!=NULL)
    {if((t->lchild= =NULL)&&(t->rchild= =NULL))
    count++; (2 分)
    countleaf(t->lchild,count);
    countleaf(t->rchild ,count);
    }
    }
    在这里插入图片描述
    在这里插入图片描述
    28、设一棵二叉树以二叉链表为存储结构,试写一算法求该二叉树上度为 2 的结点个数。
    (12 分)
    解答:
    void count2(bitreptr t ,int count)
    {if (t!=NULL)
    {if ((t->lchild != NULL) && (t->rchild != NULL))
    count++;
    count2(t->lchild,count) ;
    count2(t->rchild,count) ;
    }
    }// count2
    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述
    29、 设一棵二叉树以二叉链表为存储结构,试写一算法求该二叉树中最大值(元) 。(12 分)
    解答:
    void maxnode(bitreptr t ,int max)
    {if(t!=NULL) (2 分)
    {if(t-> data>max) max=t->data; (4 分)
    max= maxnode(t->lchild,max) ;(2 分)
    max= maxnode(t->rchild,max) ;(2 分)
    }
    return max; (2 分)
    }// maxnode
    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述
    30、组记录的关键字为 (52, 56, 26, 12, 69, 85, 33, 48, 70) ,给出快速排序的过程。
    解答: 【编者: 本书对快速排序与其它书不一样】
    解: 52, 56, 26, 12, 69, 85, 33, 48, 70 错误
    第一趟排序 33, 48, 26, 12, 52, 85, 69, 56, 70
    第二趟排序 26, 12, 33, 48, 52, 69, 56, 70, 85
    第三趟排序 12, 26, 33, 48, 52, 56, 70, 69, 85
    第四趟排序 12, 26, 33, 48, 52, 56, 70, 69, 85
    第五趟排序 12, 26, 33, 48, 52, 56, 70, 69, 85
    在这里插入图片描述
    31、对半查找是否适合于以链接结构组织的表?
    答:对半查找不适合于以链接结构组织的表。 。
    30. 请指出中序遍历二叉查找树的结点可以得到什么样的结点序列。
    答:中序遍历二叉查找树的结点就可以得到从小到大排序的结点序列。
    在这里插入图片描述
    32、已知待排记录的关键字序列为 {25, 96,11,63,57,78,44} ,请回答下列问题:
    (1)画出堆排序的初始堆(大根堆) ;
    (2)画出第二次重建堆之后的堆。
    在这里插入图片描述
    33、.要在[ 0…n-l]的向量空间中建立两个栈 stackl和stack2,请回答:
    (1)应该如何设计这两个栈才能充分利用整个向量空间?
    (2)若stackl的栈顶指针为 topl,stack2的栈顶指针为 top2,如果需要充分利用整个向量空间,则:
    栈stackl空的条件是: ___________;
    栈stack2空的条件是: ___________;
    栈stackl和栈 stack2满的条件是: ___________。
    在这里插入图片描述

    34、27.已知广义表如下:
    A=(B,y)
    B=(x ,L)
    L=(a,b)
    要求:
    第 12 页
    (1)写出下列操作的结果
    tail(A)=_.
    head(B)=

    (2)请画出广义表 A对应的图形表示。
    在这里插入图片描述

    35、已知二叉树如下:
    在这里插入图片描述
    请画出该二叉树对应的森林。
    在这里插入图片描述
    36、.请回答下列问题:
    (1)英文缩写 DAG 的中文含义是什么?
    (2)请给出下面 DAG 图的全部拓扑排序。
    在这里插入图片描述

    37、已知线性表 (a1,a2,a3…,an)按顺序存放在数组 a中,每个元素均为整数,下列程序的功能是将所有小于 0的元素移
    到全部大于等于 0的元素之前。例如,有 7个整数的原始序列为 (x,x,-x,-x,x,x,-x) ,变换后数组中保存的序列是
    (-x,-x,-x,x,x,x,x) 。请在程序处填入合适的内容,使其成为完整的算法。
    f30(int a[], int n)
    { int k,m,temp;
    m= (1) ;
    while (a[m]<0 &&m<n)
    m= (2) ;
    k=m;
    while (k<n)
    { while(a [k]>=0&&k<n)
    k= (3) ;
    if(k<n)
    { temp=a[k];
    a[k]=a[m];
    a[m]= (4) ;
    m= (5) ;
    }
    }
    }
    在这里插入图片描述
    (1)
    (2)
    (3)
    (4)
    (5)
    38、
    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述

    39、阅读下列程序,并回答问题:

    #include<stdio.h>
    substr(chart,chars,int pos,int len)
    { while (len>0&&*s )
    { t=(s+pos-l);
    第 14 页
    t++;s++;len–;
    }
    t=’\0’;
    }
    char f31(chars)
    { char t[100];
    if (strlen(s)=1)
    return s;
    substr(t,s,1,1);
    substr(s,s,2,strlen(s)-1);
    f31(s);
    return strcat(s,t);
    }
    main( )
    { char str[100]= ‘‘String’’;
    printf(’’%s\n’’,f31(str));
    }
    (1)请写出执行该程序后的输出结果;
    (2)简述函数 f31的功能。
    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述
    40、下面程序实现插入排序算法。
    typedef struct{
    int key;
    Info otherinfo;
    }SeqList;
    void InsertSort(SeqList R[] ,int n)
    {/
    待排序列保存在 R[ 1…n]中 */
    SeqList x;
    int i,j,k,lo,hi,mi;
    for (i=2 ;i<=n ;i++)
    {
    (1) ;
    lo=1 ;
    第 15 页
    hi=i-l;
    while (lo<=hi)
    {
    mi=(lo+hi)/2;
    if ( (2) ) break;
    if (R[mi].key>x.key) hi=mi-l;
    else lo=mi+l;
    }
    if (mi=lo) k=i - mi;
    else k=i - mi-1;
    for (j=0 ;j<k ;j++)
    (3) ;
    R[i-j ]=x;
    }
    }
    在空白处填写适当的内容,使该程序功能完整。

    答 :
    在这里插入图片描述

    在这里插入图片描述

    在这里插入图片描述

    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述
    41、已知二叉树的定义如下:
    typedef struct node{
    int data;
    struct node *lchild, *rchild;
    }*Bitptr ;
    编写递归算法求二叉树的高度。函数原型为: int f34(Bitptr t);
    在这里插入图片描述
    42、29稀疏矩阵 A 如下,写出矩阵 A 的三元组表及矩阵 A 的转置矩阵的三元组表。
    答 :在这里插入图片描述
    在这里插入图片描述
    43、一棵二叉树的前根遍历序列为 ABCDEFG ,中根遍历序列为 CBDAEGF ,试构造出该二叉树。
    在这里插入图片描述

    44、31.下述矩阵表示一个无向连通网,试画出它所表示的连通网及该连通网的最小生成树。
    在这里插入图片描述
    答 :
    在这里插入图片描述
    45、32给定表( 80, 90,50,70,75,60,40,100),试按元素在表中的顺序将它们依次插入一棵初始时为空的二叉排
    序树,画出插入完成后的二叉排序树。
    答:
    在这里插入图片描述
    46、试写出一组键值( 46,58,15, 45,90,18,10,62)应用直接插入排序算法从小到大排序后各趟的结果。
    在这里插入图片描述

    47、试写出一组键值( 46,58,15, 45,90,18,10,62)应用直接插入排序算法从小到大排序后各趟的结果。
    在这里插入图片描述

    48、试分别写出二叉树的先根遍历和中根遍历的递归算法
    在这里插入图片描述
    49、试编写以单链表为存储结构实现直接选择排序的算法。
    在这里插入图片描述
    50、在栈的输入端元素的输入顺序为 1,2,3,4,5,6,进栈过程中可以退栈,则退栈时能否排成序列 3,2,5,6,
    4,1 和 1,5,4, 6,2,3,若能,写出进栈、退栈过程,若不能,简述理由。 (用 push(x)表示 x 进栈, pop(x)
    表示 x 退栈)
    在这里插入图片描述
    51、已知一棵二叉树的中根遍历序列为 CBEDFAGH ,后根遍历序列为 CEFDBHGA ,画出该二叉树。
    在这里插入图片描述
    52、给定表( 15,11,8,20, 14,13),试按元素在表中的顺序将它们依次插入一棵初始时为空的二叉排序树,画
    出插入完成后的二叉排序树,并判断该二叉排序树是否为平衡二叉排序树,若为非平衡二叉排序树,将它调整为
    平衡二叉排序树。
    在这里插入图片描述
    在这里插入图片描述

    53、如题 32 图所示无向图, (1)写出其邻接矩阵; (2)写出三种以顶点 A 为起点的深度优先搜索顶点序列。

    在这里插入图片描述

    在这里插入图片描述

    54、、用冒泡排序法对数据序列( 49, 38,65,97,76,134,27,49)进行排序,写出排序过程。并说明冒泡排序是否为稳定排序
    在这里插入图片描述
    55、编写计算二叉树中叶子结点数目的算法。
    在这里插入图片描述

    56、开散列表的类型定义如下:

    typedef struct tagnode
    {keytype key;
    struct tagnode*next;
    }*pointer,node;
    typedef pointer openhash[ n];
    试写出开散列表上的查找算法。
    在这里插入图片描述

    57、
    在这里插入图片描述

    在这里插入图片描述

    58、
    在这里插入图片描述
    答 :
    在这里插入图片描述

    59、
    在这里插入图片描述
    答:领接矩阵
    在这里插入图片描述

    60、
    在这里插入图片描述
    答 :
    在这里插入图片描述

    61、
    在这里插入图片描述
    答 :
    在这里插入图片描述

    62、在这里插入图片描述
    答 :
    在这里插入图片描述

    63、
    在这里插入图片描述
    答:在这里插入图片描述

    64、设某文件有 14个记录,其关键字分别为{25,75,125,93,241,203,19,198,121,173,218,80,214,329} 。桶的容量 M=3,此时采用除留余数法构造散列函数,且散列函数为 h(k)=k%5, 画出该散列文件的结构图,并说明如何对其进行删除
    或插入、检索等操作。
    答案:由于散列函数 h(k)=k%5, 从而可得按散列函数方法组织的文件结构如下 ( 可选桶数为
    (14/3 )×(1+10%)=5);
    当需对该散列文件中的记录进行检索时,可首先根据给定记录的关键字值,用散列函数求出其对应的散列地址,此地址即为桶的编号,然后按照散列表中第 i 项给出的地址把该桶中的所有记录读入内存,并对这些记录进行顺序检索。若找到说明检索成功,否则,若该桶不满或其指针域为空,说明检索失败。此时若其指针域不空,则该指针把第一个溢出桶的记录读入内存,继续检索
    直到检索成功或失败时为止。当要对散列文件中的记录进行删除操作时,同样可首先利用散列函数求出该记录所在的存储桶并
    把它读入内存,接着把该记录与最后一个记录对调,然后把该桶重新写回到外存储器的原来的位置。当从最后一个桶中删除最后一个记录时,可将此空桶释放回系统,以节省存储空间。当要对散列文件中的记录进行更新或修改时,可首先检索该记录所在的存储桶,并把该桶记录读入内存,接着检索该记录,并修改,然后把修改过的桶重新写回到原来的位置即可。

    65、写出二分查找的递归算法。
    答案: int binlist (datatype a [n];int s,t;datatype x)/*n 为元素个数, s,t 分别为查找区
    间的上、下界 /
    { if(S>t) return(0);/
    查找失败 /
    else { mid=(s+t)/2;
    switch(mid)of
    { x<a [mid]:return (binlist(a,s,mid-1,x));/
    在低端区间上递归 /
    x==a[mid]:return (mid);/
    查找成功 /
    x>a[mid]:return(binlist(a,mid+1,t,x));/
    在高端区间上递归 */
    }
    }
    }

    66、对于如下一个有序的关键字序列 {5,9,12,18,23,31,37,46,59,66,71,78,85}, 现在要求用二
    分法进行查找值为 18的关键字,则经过几次比较之后能查找成功 ?
    答案:根据二分查找的过程,我们可以得到如下的比较结果:
    第一次比较:[ 5,9,12,18,23,31,37,46,59,66,71,78,85,]

    第二次比较:[ 5,9,12,18,23,31],37,46,59,66,71,78,85

    第三次比较: 5,9,12[18,23,31],37,46,59,66,71,78,85

    第四次比较: 5,9,12[18]23,31,37,46,59,66,71,78,85

    则从上面的比较过程我们可以看出:经过四次比较之后,就可以查找到值为 18的关键字。

    67、在一棵二叉树中,度为 0的结点个数与度为 2的结点个数和度数之间有什么关系 ?在一棵完全二叉树中,如果共有 200个结点,则能判断出叶结点的个数吗 ?如果能,请指出会有多少个叶结点,多少个度为2的结点 ?多少个度为 1的结点?如果有 201个结点呢?

    答案:在一棵二叉树中,度数为 0的结点 ( 叶结点 )的个数总是比度为 2的结点的个数多 1。根据完
    全二叉树的定义:若一棵二叉树至多只有最下面的两层上结点的度数可以小于 2,并且最下一层上的结点都集中在该层最左边的若干位置上,
    则我们可以得出这样一个结论:在一棵完全二叉树上,或者没有度为 1的结点。则根据以上分析,我们可以这样计算此题:设度数为 2的结点有 n个,则必有 n+1个度为 0的结点,即度数为 2和度数为 0的结点数之和为 2n+1(是奇数 ) ,
    于是得出,如果一棵完全二叉树的结点总数为奇数,则此树中必然不存在度为 1的结点,若完全二叉树中结点总数为偶数,则必然有 1个度为 1的结点存在,于是若完全二叉树中有 200个结点,就必有 100个对结点,99个度数为 2的结点, 12个度数为 1的结点,如果二叉树中有 201个结点,则必有 101个叶结点, 100个度数为 2的结点,没有度数为 1的结点。

    68、以下运算实现在循环队上取队头,请在 ___处用适当的语句予以填充。
    int GetHead(CycqueueTp sq,DataType *x)
    { if(sq.rear==___return(0);
    else { *x=sq.data [___];
    return(1);
    }
    }
    答案: sq.front (sq.front+1)% maxsize

    69、以下运算实现在链栈上的初始化,请在 ___处用适当的语句予以填充。
    void InitStack (LStackTp *ls){;___}
    答案: ls=NULL

    70、以下算法在开散列表 HP中查找键值等于 K的结点,成功时返回指向该点的指针,不成功时返
    回空指针。请分析程序,并在 ___上填充合适的语句。
    pointer research-openhash(keytype K,openhash HP)
    { i=H(K);/* 计算K的散列地址 /
    p=HP[i ];/i 的同义词子表表头指针传给 p/
    while(___)p=p->next;/
    未达到表尾且未找到时,继续扫描 */
    ______;
    }
    答案: (p!=NULL)&&(p->key!=K) return§

    71、写出向某个有序文件中插入一个记录的程序。
    答案:所谓有序文件是指文件的记录按关键字由小到大 (或由大到小 )顺序存放。为方便起见,可
    设文件的每一个记录是一个整数,文件上数据是按由小到大顺序存放。设插入数据是命令行的第
    3个参数,且设为 d。若原文件中没有数据,则 d写入文件;若有数据,则找到第 1个比d大的数据
    i ,先写入 d,再将 i 和其后各数据写回文件中,可通过调用 fseek 函数来实现插入。相应程序为:
    #include <stdio.h>
    #include <stdlib.h>
    #include <io.h>
    #include <fcntl.h>
    #define LEN sizeof(int)
    void main(int argi,char * * argc)
    { int fp,i,d;
    if (argi<3)
    { printf( ″filename int n″)
    exit(0);
    }
    d=atoi (argc [2]);
    fp=open(argc [1],O_CREAT |O_RDWR |O_BINARY,s-IREAD |S_IWRITE);
    while(1)
    { if ( read(fp,&I,LEN) !=LEN)
    {write (fp,&d,LEN)😕* 文件结束, d添加到文件尾端 /
    break; }
    if (i>=d)/
    文件中读出数据 i ,若i>=d,则先存 d*/
    { do
    { fseek(fp,-1Llen,SEEK_CUR);/ 文件指针后退 1个记录 */
    write(fp,&d,LEN);/*d 写到文件中 /
    d=i;/
    原i 作d,以便处理其他数据 /
    }while (read(fp,&i,LEN)==LEN);
    write(fp,&d,LEN);/
    继续读数据,并判别文件是否结束 */
    break;
    }
    }
    close (fp);
    }/main/

    72、对题 26 图中所给的二叉排序树 T回答下列问题。
    (1) 给出能生成 r 的 2 种关键字插入序列;
    (2) 给出 r 的前序遍历序列。
    在这里插入图片描述

    在这里插入图片描述

    73、对题 27 图所示的无向带权图 G,回答下列问题。
    (1) 给出图 G的邻接矩阵;
    (2) 给出图 G的一棵最小生成树。
    在这里插入图片描述
    答 :

    在这里插入图片描述
    在这里插入图片描述

    74、现有 5 个权值分别是 20、31、 16、7 和 l5 的叶结点,用它们构造一棵哈夫曼树,画出该树。
    在这里插入图片描述

    75、对于给定的一组关键字序列 {26 ,l8 ,60,65,45,13,32} ,写出使用直接选择排序方法将其排成升序序列的过程。
    在这里插入图片描述

    76、设非空双向循环链表 L 的头指针为 head,表结点类型为 DLNode,定义如下。
    在这里插入图片描述

    初始时, L 中所有结点的 prior 域均为空 (NULL),next 域和 data 域中已经正确赋
    值。如题 30 图 a 所示
    在这里插入图片描述

    函数 f30 完成的功能是:将 L 中各结点的 prior 域正确赋值,使 L 成为双向循环链表。如题 30 图 b 所示。
    在这里插入图片描述

    将空白处应填写的内容答在答题卡上。
    在这里插入图片描述

    在这里插入图片描述

    77、已知二叉树的二叉链表类型定义如下,阅读程序,并回答问题。

    在这里插入图片描述

    若二叉树如下所示,写出调用 f31(T) 的输出结果
    在这里插入图片描述

    在这里插入图片描述

    78、阅读下列程序,写出 f32 的输出结果。
    在这里插入图片描述

    在这里插入图片描述

    79、阅读程序,回答下列问题。
    在这里插入图片描述

    在这里插入图片描述

    80、已知单链表类型定义如下:
    在这里插入图片描述
    单链表 L 中结点数不少于 2。设计算法判断 L 中存储的全部 n 个数据是否是斐波那契序列的前 n 项。如果是,则
    函数返回 1,否则返回 0。函数原型如下
    在这里插入图片描述

    在这里插入图片描述

    81、已知 n 阶对称矩阵 A的元素为 a i,j (0≤i ,j ≤n 一 1),采用“按行优先”将下三角部分
    的元素 ( 含主对角线 ) 保存在一维数组 sa 中,且约定元素 a 0,0 保存在 sa[0] 中,元素 a i,j ( ≤i ,
    j ≤n-1) 保存在 sa[k] 中,请给出由下标 i ,j 计算下标 k 的计算公式。
    在这里插入图片描述

    82、己知二又树 T 如题 27 图所示。
    在这里插入图片描述

    请问答下列问题:
    (1) 画出该二叉树对应的森林。
    (2) 写出对森林进行前序遍历的遍历序列 i
    答 :
    在这里插入图片描述

    83、题 28 图所示为一棵含 2 个关键字的 3 阶 B树 T。现将关键字序列 {40 ,60,70,20,10}依次插入到 T 中,画出每插入一个关键字后得到的树型。
    在这里插入图片描述

    答 :
    在这里插入图片描述

    84、给定无向带权连通图 G如题 29 图所示,从顶点 v 0 开始,使用普里姆 (Prim) 算法,求 G的最小生成树 T。请回答下列问题。在这里插入图片描述

    (1) 画出最小生成树 T。
    (2) 计算 T中各边权值之和。
    在这里插入图片描述

    85、请写出下列程序段的输出结果。
    在这里插入图片描述

    在这里插入图片描述

    答:
    在这里插入图片描述

    86、己知存储稀疏矩阵三元组表的类型定义如下:
    在这里插入图片描述
    在这里插入图片描述
    答:
    在这里插入图片描述

    87、已知二叉树的二叉链表类型定义如下:
    在这里插入图片描述

    答:
    在这里插入图片描述

    88、函数 f33 的参数 t 指向题 33 图所示的二叉排序树的根,阅读程序,回答下列问题。
    在这里插入图片描述

    1. 若连续 3 次调用函数 f33 ,参数 K的值依次取 10、25、10,写出每次调用后函数的输
      出结果;
      (2) 说明函数 f33 的功能。
      在这里插入图片描述

    89、已知顺序表 SeqList 定义如下:
    typedef struct{
    KeyType key ;
    InfoType otherinf0 ;
    }RecType :
    typedef RecType SeqList[MAXSIZE+1] ;
    编写函数,用冒泡排序法将 n个元素的待排序列 R按关键字降序排序。函数原型为:
    int f34(SeqList R ,int n)
    在这里插入图片描述

    90、
    在这里插入图片描述

    在这里插入图片描述

    91、
    在这里插入图片描述

    在这里插入图片描述
    在这里插入图片描述

    92、
    在这里插入图片描述
    在这里插入图片描述

    93、
    在这里插入图片描述

    在这里插入图片描述

    94、
    在这里插入图片描述

    答 :
    在这里插入图片描述
    95、
    在这里插入图片描述

    在这里插入图片描述

    答 :
    在这里插入图片描述

    96、
    在这里插入图片描述

    在这里插入图片描述
    答 :
    在这里插入图片描述

    97、
    在这里插入图片描述

    在这里插入图片描述

    98、在这里插入图片描述
    答 :
    在这里插入图片描述
    99、
    在这里插入图片描述
    100、
    在这里插入图片描述
    101、
    在这里插入图片描述
    102、
    在这里插入图片描述
    103、
    在这里插入图片描述

    104、
    在这里插入图片描述

    105、
    在这里插入图片描述
    106、
    在这里插入图片描述

    107、
    在这里插入图片描述

    108、
    在这里插入图片描述
    109、
    在这里插入图片描述

    110、
    在这里插入图片描述
    111、
    在这里插入图片描述
    112、
    在这里插入图片描述

    113、
    在这里插入图片描述
    114、
    在这里插入图片描述
    115、
    在这里插入图片描述
    116、
    在这里插入图片描述
    117、
    在这里插入图片描述

    118、
    在这里插入图片描述

    119、
    在这里插入图片描述
    在这里插入图片描述

    120、
    在这里插入图片描述
    121、
    在这里插入图片描述

    122、
    在这里插入图片描述
    123、
    在这里插入图片描述
    124、
    在这里插入图片描述
    125、
    在这里插入图片描述
    126、
    在这里插入图片描述
    127、
    在这里插入图片描述
    128、
    在这里插入图片描述
    129、
    在这里插入图片描述

    130、
    在这里插入图片描述

    131、
    在这里插入图片描述
    132、
    在这里插入图片描述

    133、
    在这里插入图片描述

    134、
    在这里插入图片描述
    135、
    在这里插入图片描述

    136、已知某二叉树如下图所示,试给出其二叉链表及顺序存储结构表示。
    在这里插入图片描述

    答 :
    在这里插入图片描述
    在这里插入图片描述

    137、在这里插入图片描述
    答 :
    在这里插入图片描述

    138、已知某二叉排序树 10 个结点的值依次为 1~10,其结构如图所示,试标出该二叉树各结点所对应的具体值。
    在这里插入图片描述

    答 :
    在这里插入图片描述

    139、已知一组键值序列( 28,47,35,42,53,60,34,22),试给出采用直接插入排序法对该组序列作升序排序的每一趟结果。
    在这里插入图片描述

    140、.已知一组键值序列( 3,6, 8,9,2,7,4,3),试采用快速排序法对该组序列作升序排序,并给出每一趟的排序结果。
    在这里插入图片描述

    141、设某单链表中,存在多个结点其数据值均为 D,试编写一算法统计该类结点的个数。
    在这里插入图片描述

    142、35叉树存储结构采用二叉链表表示,试编写一算法,计算一棵二叉树的所有结点数。
    在这里插入图片描述

    143、假设二叉树的 RNL遍历算法定义如下:
    若二叉树非空,则依次执行如下操作:
    (1) 遍历右子树;
    (2) 访问根节点;
    (3) 遍历左子树。
    已知一棵二叉树如图所示,请给出其 RNL遍历的结果序列。

    答 :
    该树的 RNL遍历结果序列为: GCFABD

    144、已知一个无向图 G=(V,E),其中 V={A,B,C,D,E,F},邻接矩阵表示如下所示。
    请回答下列问题:
    (1) 请画出对应的图 G。
    (2) 画出图 G的邻接表存储结构。

    答:
    在这里插入图片描述

    145、已知一组待排记录的关键字序列为 (16, 12,18,60,15,36,14,18,25,85) ,用堆排序方法建小根堆,请给出初始建堆后的序列。


    初始堆序列是 (12 ,15,14,18,16,36,18,60,25,85)

    146、已知一棵二叉排序树如图所示。

    请回答下列问题:
    (1) 画出插入元素 23 后的树结构;
    (2) 请画出在原图中删除元素 57 后的树结构
    在这里插入图片描述
    答:
    在这里插入图片描述

    147、二叉树的存储结构类型定义如下

    typedef struct node{
    int data;
    struct node
    *
    lchild ,

    • rchild ;
      } BinNode ;
      typedef BinNode

    BinTree;
    编写递归算法,求只有一个孩子结点的结点总数,并计算这些结点的数据值的和。
    函数的原型为: void f34(BinTree T, int

    • count,
      int

    sum)
    *
    count 和

    • sum 的初值为
      0。
      答 :
      在这里插入图片描述

    148、30.已知下列程序, Ls 指向带头结点的单链表。

    Typedefstruct node {
    DataType data;
    struct node * next;
    } * LinkList;
    void f30( LinkList Ls )
    { LinkList p, q;
    q = Ls->next;
    if ( q && q->next ) {
    Ls->next = q->next;
    p=q
    while ( p->next )
    p = p->next;
    p->next = q;
    q->next = NULL;
    }
    }
    请回答下列问题:
    (1) 当 Ls 指向的链表如下图所示,请画出执行本函数之后的链表的结果。
    在这里插入图片描述

    (2) 请简述算法的功能
    答 :
    在这里插入图片描述
    (2) 将单链表的首结点(第一个结点)移到链尾(作为最后一个结点) 。
    或将链头元素移到链尾。

    149、已知字符串处理函数 f31 程序如下。

    int f31(charstrl , charstr2)
    { while(*strl==*str2&&(*strl!= ’\0’)){
    strl++ ;
    str2++ ;
    }
    return(*strl-*str2 ? l ∶0);
    }
    请回答下列问题:
    (1) 若调用语句是 f31( ”abcde”,” abcdf ’) ,则函数的返回值是什么 ?若调用语句是
    f31( ”abcde”,” abcde”) ,则函数的返回值是什么 ?
    (2) 简述该函数的功能。

    31. (1)1 , 0 (2 分)
    (2) 判断两个字符串是否相等。若串相等,则返回 O,否则返回 1。

    32.数组 A[] 中存储有 n 个整数,请阅读下列程序。

    void f32(intA[] ,int n)
    { inti ,j , k,x;
    k=n-l ;
    while(k>0){
    i=k ; k=0 ;
    for(j=O ;j<i ;j++)
    if(A[j]>A[j+1]){
    x=A[j] ;
    A[j]=A[j+l] ;
    A[j+1]=x ;
    k=j ;
    } // end of if
    } // end of while
    return ;
    }
    请回答下列问题:
    (1) 当 A[]={10 ,8, 2,4,6,7} 时,执行 f32(A ,6)后,数组 A中存储的结果是什么 ?
    (2) 说明该算法的功能。

    答32.(1)A[]={2,4,6,7,8,10) (3 分)
    (2) 该算法实现了对数组 A进行冒泡排序。

    150、下面程序实现二分查找算法。
    Typedef struct{
    KeyType key ;
    InfoType otherinfo ;
    }SeqList[N+1] ;
    int BinSearch(SeqList R, int n ,KeyType K)
    { int low=1 ,high=n ;
    while( (1) ){
    mid=(1ow+high) /2;
    if( (2) )
    return mid ;
    if(R[mid] .key>K)
    high=mid-1 ;
    else
    (3) ;
    }
    return O ;
    } // BinSearch
    请在空白处填写适当内容,使该程序功能完整。
    (1)
    (2)
    (3)

    答:
    33. (1) low<=high (2 分)
    (2) R[mid].key==K (2 分)
    (3) low=mid+l

    151、已知二叉树采用二叉链表存储,其结点结构定义如下:
    typedef struct Node{
    ElmType data ;
    struct Node *lchild ,*rchild ;
    }*BiTree ;
    请编写递归函数 SumNodes(BiTree T) ,返回二叉树 T 的结点总数。

    参考答案
    int SumNodes( BiTree T)
    { inti ,j ;
    if( !T) retumO ; (空树处理, 2 分)
    i=SumNodes( T->lchild) ; (左右子树递归, 6 分)
    j=SumNodes( T->rchild);
    retum (i+j+1) ; (返回结果计算, 2 分)
    } //endofSumNodes(…)

    152、顺序表类型定义如下:

    typedef int SeqList[100] ;
    阅读下列算法,并回答问题:
    void f33(SeqList r, int n)
    { int a, b,i;
    if (r[0]<r[1])
    { a=r[0] ;b=r[1] ; >
    else { a=r[1] ; b=r[0] ; }
    for (i=2 ;i<n ;i++)
    if (r[i]<a) a=r[i];
    else if (r[i]>b) b=r[i] ;
    printf( " a=%d,b=%d。 n", a, b);
    }
    (1)给出该算法的功能;
    (2)给出该算法的时间复杂度。

    在这里插入图片描述

    153、阅读下列算法,并回答问题:

    void f32(int r[] , int n)
    {
    Int i, j;
    for (i=2 ;i<n;i++)
    { r[0]=r[i] ;
    j=i-l ;
    while (r[0]<r[j])
    { r[j+l]=r[j] ;
    j=j-1 ;
    }
    r[j+l]=r[0] ;
    }
    }
    (1)这是哪一种插入排序算法 ?该算法是否稳定 ?
    (2)设置 r[0] 的作用是什么 ?
    在这里插入图片描述

    154、有向图的邻接矩阵类型定义如下:
    #define MVN 100 ∥ 最大顶点数
    typedef int EType; ∥ 边上权值类型
    typedef struct{
    EType edges[MVN][MVN]; ∥ 邻接矩阵,即边表
    int n; ∥ 图的顶点数
    } MGraph; ∥ 图类型
    例如,一个有向图的邻接矩阵如下所示:
    在这里插入图片描述

    阅读下列算法,并回答问题:
    Void f31(MGraph G)
    {
    Int i,j,k=0;
    Step1:
    for (i=0; i<G.n; i++)
    for (j=0; j<G.n; j++)
    if (G.edges[i][j]= =1) k++;
    printf( “ %d n” ,k);
    step2:
    for (j=0; j<G.n; j++)
    { k=0;
    for (i=0; i<G.n; j++)
    if (G.edges[i][j]= =1) k++;
    printf ( “ %d n” ,k);
    }
    }
    (1)stepl 到 step2之间的二重循环语句的功能是什么 ?
    (2)step2 之后的二重循环语句的功能是什么 ?
    在这里插入图片描述

    155、顺序表类型定义如下:

    define ListSize 100

    typedef struct {
    int data[ListSize] ;
    int length;
    }SeqList ;
    阅读下列算法,并回答问题:
    void f30(SeqList *L)
    { int i,j;
    i=0;
    while(ilength)
    if (L->data[i] %2!=0)
    { for(j=i+1; jlength; j++ }
    L->data[j-1]=L->data[j];
    L->length–;
    }
    else i++
    }
    (1)若 L->data 中的数据为( 22,4,63,0,15,29,34,42,3),则执行上述算法后 L->data 中的数据以及 L->length 的值各是
    什么?
    (2)该算法的功能是什么?

    在这里插入图片描述

    156、一组记录关键字 (55,76,44,32,64,82,20,16,43) ,用散列函数 H(key)=key %11 将记录

    散列到散列表 HT[0…12] 中去,用线性探测法解决冲突。
    (1)画出存入所有记录后的散列表。
    (2)求在等概率情况下,查找成功的平均查找长度。
    在这里插入图片描述

    157、用归并排序法对序列 (98,36,-9,0,47,23,1,8)进行排序,问:
    (1)一共需要几趟归并可完成排序。
    (2)写出第一趟归并后数据的排列次序。
    在这里插入图片描述

    158、已知一个无向图如题 27 图所示,以①为起点,用普里姆 (Prim)算法求其最小生成树,画出最小生成树的构
    造过程。
    在这里插入图片描述
    答:

    在这里插入图片描述

    159、假设 Q 是一个具有 11 个元素存储空间的循环队列 (队尾指针指向队尾元素的下一

    个位置,队头指针指向队头元素 ),初始状态 Q.front=Q.rear=0 ;写出依次执行
    下列操作后头、尾指针的当前值。
    a,b,c,d,e,f 入队, a,b,c,d出队; (1) Q.front=______ ;Q.rear=______。
    g,h,i,j,k,l 入队, e,f,g,h 出队; (2) Q.front=______ ;Q.rear=______。
    M,n,o,P 入队, i,j,k,l,m 出队; (3) Q.front=______ ;Q.rear=______。
    在这里插入图片描述

    160、
    在这里插入图片描述
    在这里插入图片描述
    161、

    在这里插入图片描述
    在这里插入图片描述
    162、
    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述
    163、
    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述
    164、
    在这里插入图片描述
    在这里插入图片描述
    165、
    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述
    已知一个无向图如题 27 图所示,以①为起点,用普里姆 (Prim)算法求其最小生成树,画出最小生成树的构造过程。
    在这里插入图片描述
    在这里插入图片描述

    28.用归并排序法对序列 (98,36,-9,0,47,23,1,8)进行排序,问:

    (1)一共需要几趟归并可完成排序。
    (2)写出第一趟归并后数据的排列次序。
    (1)3趟
    (2)(36,98,-9,0,23,47,1,8)

    29.一组记录关键字 (55,76,44,32,64,82,20,16,43) ,用散列函数 H(key)=key %11 将记录
    散列到散列表 HT[0…12] 中去,用线性探测法解决冲突。
    (1)画出存入所有记录后的散列表。
    (2)求在等概率情况下,查找成功的平均查找长度。
    在这里插入图片描述
    在这里插入图片描述
    (1)、date[]={22,4,0,34,42}
    length=5
    (2)、删除顺序表中的奇数数据元素
    在这里插入图片描述
    在这里插入图片描述
    (1)、统计输出图中边的数目
    (2)、统计输出图中每个顶点的入度数。
    在这里插入图片描述
    (1)、直接插入排序
    该算法稳定
    (2)、r[0]的作用是监视监视兵/哨兵
    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述
    166、
    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述

    167、

    168、

    展开全文
  • 数据结构(C++)有关练习

    热门讨论 2008-01-02 11:27:18
    在计算机科学发展过程中,早期数据结构教材大都采用PASCAL语言为描述工具,后来出现了采用C语言为描述工具的教材版本、至今又出现了采用C++语言为描述工具的多种教材版本。本教实验指导书是为已经学习过C++语言的...
  • 数据结构 排序习题

    千次阅读 2018-05-23 22:36:53
    10数据结构复习排序) 一.判断(下列各,正确的请在前面的括号内打√;错误的打╳ ) ( )(1)如果某种排序算法不稳定,则该排序方法就没有实用价值。( )(2)希尔排序是不稳定的排序。( )(3)...
  • 我们经典的排序有内部排序和外部排序,内部排序数据记录在内存中进行排序,而外部排序是因排序数据很大,一次不能容纳全部的排序记录,在排序过程中需要访问外存。 算法复杂度如下图: 下面我们一一来总结...
  • 考研数据结构

    千次阅读 多人点赞 2020-11-08 21:21:15
    数据结构总结 1 绪论 2 线性表的存储 3 串 4 线性表 5 树 6 图 7 查找 8 排序
  • 计算机复试面试总结

    万次阅读 多人点赞 2019-03-07 20:06:56
     数据结构与算法面试 3. c++ 与STL 面试 4. 计算机网络面试 面试问题之编程语言 1。C++的特点是什么? 封装,继承,多态。支持面向对象和面向过程的开发。 2.C++的异常处理机制? 抛出异常和捕捉异常进行...
  • 数据结构与算法习题库

    万次阅读 多人点赞 2018-12-26 21:24:55
    1.数据结构被形式地定义为(K,R),其中K是①_B_的有限集合,R是K上的②_D_的有限集合。  ①A.算法 B.数据元素 C.数据操作 D.逻辑结构  ②A.操作 B.映象 C.存储 D.关系 2.算法分析的目的是①C...
  • 数据结构算法设计汇总

    千次阅读 2020-12-23 15:37:09
    typedef struct BSTNode {∥ 二叉排序树的结点结构 int data; ∥数据域 struct BSTNode *lchild, *rchild; ∥左、右孩子指针 }BSTNode,*BSTree; 设计递归算法,统计一棵二叉排序树T中值小于a的结点个数。 ...
  • 数据结构简答汇总

    千次阅读 多人点赞 2020-05-12 23:56:08
    面对即将要参加的考研复试,数据结构是必考科目,希望以下能派上用场 1.算法的时间复杂度: 答:在程序中反复执行的语句的执行次数被称为语句的频度,时间复杂度就是所有语句频度之和的数量级,而所有语句的频度之和...
  • 数据结构1800及答案.pdf

    热门讨论 2011-12-04 17:11:44
    7.从逻辑上可以把数据结构分为( )两大类。 【武汉交通科技大学 1996 一 、4(2 分) 】 A.动态结构、静态结构 B.顺序结构、链式结构 C.线性结构、非线性结构 D.初等结构、构造型结构 8.以下与数据的存储...
  • 数据结构1800.docx

    2020-07-09 00:39:37
    数据结构1800 可修改 可打印 数据结构1800例题与答案 第一章 绪 论 一、选择(每小2分) 1.算法的计算量的大小称为计算的( B )。  A.效率 B.复杂性 C.现实性 D.难度 2.算法的时间复杂度取决于(C...
  • 八大数据结构及常见面试

    千次阅读 2020-12-01 21:39:16
    几乎所有的问题都需要面试者对数据结构有深刻的理解。无论你是初入职场的新兵(刚从大学或者编程培训班毕业),还是拥有几十年经验的职场老鸟。 即便是对于一些非常基础的工作来说,学习数据结构也是必须的。那么,...
  • 数据结构试题及答案 单项选择 1 一个算法应该是 1 一个算法应该是 A程序 C要满足五个基本属性 算法指的是 A计算机程序 C排序算法 B问题求解步骤的描述 D A 和 C B解决问题的计算方法 D解决问题的有限运算序列 3 与...
  • 22计算机408考研—数据结构排序(详解加例题)

    万次阅读 多人点赞 2021-09-20 14:29:19
    排序 排序的基本概念 顾名思义,给一个无序数组的值进行顺序存储 原数组:2 3 1 5 6 4 8 9 7 排序后:1 2 3 4 5 6 7 8 9 直接插入排序 思路: 插入 == 把数插进去 也是两层循环 数组num 第一层循环从下标为1的值...
  • 网页 资讯 视频 图片 知道 文库 贴吧 采购 地图 | 百度首页 登录 VIP新客立...百度文库 专业资料 IT/计算机 课 程 设 计 课 程 设 计 课程数据结构 课程数据结构 排序算法比较 排序算法比较 专业班级 专业班
  • 数据结构与算法三十,弄懂这些面试就够了!

    万次阅读 多人点赞 2019-02-01 08:30:28
    由于数据结构用来以有组织的形式存储数据,而且数据是计算机科学中最重要的实体,因此数据结构的真正价值显而易见。 无论你解决什么问题,你都必须以这种或那种方式处理数据比如员工的工资,股票价格,购物清单,...
  • 奇偶排序算法不是严蔚敏老师书上的算法,是今年上海大学计算机考研(832计算机组成原理与数据结构)的一道考试,听朋友说了之后感觉很不错,给大家分享一下。 题目大致含义如下: 已知奇偶交换排序如下所述: ...
  • Java知识体系最强总结(2021版)

    万次阅读 多人点赞 2019-12-18 10:09:56
    基础知识 并发理论 并发关键字 Lock体系 并发容器 线程池 原子操作类 并发工具 并发实践 数据结构与算法 数据结构 算法 排序算法 LeetCode 数据库 Oracle MySQL 数据库基础知识 数据类型 引擎 索引 三大范式 常用SQL...
  • 北京理工大学-数据结构期末考试试题(二)

    千次阅读 多人点赞 2018-11-11 23:01:00
    数据结构试卷(二) 一、选择(24分) 1.下面关于线性表的叙述错误的是(&nbsp;&nbsp;)。 &nbsp;&nbsp; (A) 线性表采用顺序存储必须占用一片连续的存储空间 (B) 线性表采用链式存储不必占用一片...
  • 2021版王道《数据结构》编程汇总

    千次阅读 2020-03-27 16:43:26
    2021版王道《数据结构》编程汇总 第二章 线性表P19 1 ​ 1.从顺序表中删除具有最小值的元素(假设唯一)并由函数返回被删元素的值。空出的位置由最后一个元素填补,若顺序表为空则显示出错信息并退出运行。 ​ ...
  • Java练习算法代码(排序数据结构,小算法,LeetCode练习) 一、sort文件夹是排序算法 八大排序算法 冒泡排序 选择排序 插入排序 归并排序 快速排序 基数排序(桶排序) 希尔排序排序 三、basic文件夹是基础相关 ...
  • Java面试--数据结构

    千次阅读 2019-04-07 12:32:48
    排序算法对比 算法 时间复杂度(平均) 最好 最坏 稳定性 冒泡排序 o(n^2) n o(n^2) 稳定 插入排序 o(n^2) n o(n^2) 稳定 ...
  • 数据结构习题及解析四

    千次阅读 2018-12-20 12:58:11
    来源:我是码农,转载请保留出处和链接! ...一、选择 1、非空循环链表head 的尾结点 p 满足下列( )条件。...数据结构习题解析及答案解析:本考点是非空循环链表的特性。 因为是非空循环链表,所以尾结...
  • 数据结构复习 简答 抽象数据类型是如何定义的写出一个 ADT的描述 数据的存储结构可用哪四种基本的存储方法得到 简述单链表的概念 画出在单链表上插入和删除结点的示意图 试比较顺序表和链表的优缺点 二叉树是...
  • Java面试大全(2020版)

    万次阅读 多人点赞 2019-11-26 11:59:06
    发现网上很多Java面试都没有答案,所以花了很长时间搜集整理出来了这套Java面试大全,希望对大家有帮助哈~ 本套Java面试大全,全的不能再全,哈哈~ 一、Java 基础 1. JDK 和 JRE 有什么区别? JDK:Java ...
  • Java常见数据结构面试(带答案)

    千次阅读 2020-09-02 15:17:53
    栈通常采用的两种存储结构是(线性存储结构和链表存储结构)5.下列关于栈的叙述正确的是(D)     A.栈是非线性结构B.栈是一种树状结构C.栈具有先进先出的特征D.栈有后进先出的特征6.链表不具有...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 90,510
精华内容 36,204
关键字:

数据结构排序计算题

数据结构 订阅