精华内容
下载资源
问答
  • 数据结构c语言版期末考试复习试题 1《数据结构与算法》复习一、选择。1.在数据结构中,从逻辑上可以把数据结构分为 C 。A.动态结构和静态结构 B.紧凑结构和非紧凑结构C.线性结构和非线性结构 D.内部结构和...

    41528d3028836879cd698677c3999917.gif数据结构c语言版期末考试复习试题

    1《数据结构与算法》复习题一、选择题。1.在数据结构中,从逻辑上可以把数据结构分为 C 。A.动态结构和静态结构 B.紧凑结构和非紧凑结构C.线性结构和非线性结构 D.内部结构和外部结构2.数据结构在计算机内存中的表示是指 A 。A.数据的存储结构 B.数据结构 C.数据的逻辑结构 D.数据元素之间的关系3.在数据结构中,与所使用的计算机无关的是数据的 A 结构。A.逻辑 B.存储 C.逻辑和存储 D.物理4.在存储数据时,通常不仅要存储各数据元素的值,而且还要存储 C 。A.数据的处理方法 B.数据元素的类型 C.数据元素之间的关系 D.数据的存储方法5.在决定选取何种存储结构时,一般不考虑 A 。A.各结点的值如何 B.结点个数的多少C.对数据有哪些运算 D.所用的编程语言实现这种结构是否方便。6.以下说法正确的是 D 。A.数据项是数据的基本单位B.数据元素是数据的最小单位C.数据结构是带结构的数据项的集合D.一些表面上很不相同的数据可以有相同的逻辑结构7.算法分析的目的是 C ,算法分析的两个主要方面是 A 。(1)A.找出数据结构的合理性 B.研究算法中的输入和输出的关系C.分析算法的效率以求改进 C.分析算法的易读性和文档性(2)A.空间复杂度和时间复杂度 B.正确性和简明性C.可读性和文档性 D.数据复杂性和程序复杂性8.下面程序段的时间复杂度是 O(n2) 。s =0;for( I =0; inext ==NULL C.head-next ==head D head!=NULL15.带头结点的单链表 head 为空的判定条件是 B 。A.head == NULL B head-next ==NULL C.head-next ==head D head!=NULL16.若某表最常用的操作是在最后一个结点之后插入一个结点或删除最后一个结点,则采用D 存储方式最节省运算时间。A.单链表 B.给出表头指针的单循环链表 C.双链表 D.带头结点的双循环链表17.需要分配较大空间,插入和删除不需要移动元素的线性表,其存储结构是 B 。A.单链表 B.静态链表 C.线性链表 D.顺序存储结构18.非空的循环单链表 head 的尾结点(由 p 所指向)满足 C 。A.p-next == NULL B.p == NULLC.p-next ==head D.p == head19.在循环双链表的 p 所指的结点之前插入 s 所指结点的操作是 D 。3A.p-prior = s;s-next = p; p-prior-next = s;s-prior = p-priorB.p-prior = s ;p-prior-next = s;s-next = p;s-prior = p-priorC.s-next = p;s-prior = p-prior;p-prior = s;p-prior-next = sD.s-next = p ;s-prior = p-prior;p-prior-next = s;p-prior = s20.如果最常用的操作是取第 i 个结点及其前驱,则采用 D 存储方式最节省时间。A.单链表 B.双链表 C.单循环链表 D. 顺序表21.在一个具有 n 个结点的有序单链表中插入一个新结点并仍然保持有序的时间复杂度是 B 。A.O(1) B.O(n) C.O (n2) D.O(nlog2n)22.在一个长度为 n(n1)的单链表上,设有头和尾两个指针,执行 B 操作与链表的长度有关。A.删除单链表中的第一个元素B.删除单链表中的最后一个元素C.在单链表第一个元素前插入一个新元素D.在单链表最后一个元素后插入一个新元素23.与单链表相比,双链表的优点之一是 D 。A.插入、删除操作更简单 B.可以进行随机访问C.可以省略表头指针或表尾指针D.顺序访问相邻结点更灵活24.如果对线性表的操作只有两种,即删除第一个元素,在最后一个元素的后面插入新元素,则最好使用 B 。A.只有表头指针没有表尾指针的循环单链表B.只有表尾指针没有表头指针的循环单链表C.非循环双链表D.循环双链表25.在长度为 n 的顺序表的第 i 个位置上插入一个元素(1≤ i ≤n+1) ,元素的移动次数为: A 。A.n – i + 1 B.n – i C.i D.i – 1 26.对于只在表的首、尾两端进行插入操作的线性表,宜采用的存储结构为 C 。A.顺序表 B. 用头指针表示的循环单链表C.用尾指针表示的循环单链表 D.单链表27.下述哪一条是顺序存储结构的优点? C 。A 插入运算方便 B 可方便地用于各种逻辑结构的存储表示C 存储密度大 D 删除运算方便28.下面关于线性表的叙述中,错误的是哪一个? B 。4A 线性表采用顺序存储,必须占用一片连续的存储单元B 线性表采用顺序存储,便于进行插入和删除操作。C 线性表采用链式存储,不必占用一片连续的存储单元D 线性表采用链式存储,便于进行插入和删除操作。29.线性表是具有 n 个 B 的有限序列。A.字符 B.数据元素 C.数据项 D.表元素30.在 n 个结点的线性表的数组实现中,算法的时间复杂度是 O(1)的操作是 A 。A.访问第 i(1next=s; s-next=p-next B. s-next=p-next ;p-next=s;C.p-next=s ;p-next=s-next D.p-next=s-next;p-next=s36.线性表的顺序存储结构是一种 A 。A.随机存取的存储结构 B.顺序存取的存储结构C.索引存取的存储结构 D.Hash 存取的存储结构37.栈的特点是 B ,队列的特点是 A 。A.先进先出 B.先进后出38.栈和队列的共同点是 C 。A.都是先进后出 B.都是先进先出C.只允许在端点处插入和删除元素 D.没有共同点539.一个栈的进栈序列是 a,b,c,d,e ,则栈的不可能的输出序列是 C 。A.edcba B.decba C.dceab D.abcde40.设有一个栈,元素依次进栈的顺序为 A、B、C、D、E。下列 C 是不可能的出栈序列。A.A,B,C,D,E B.B,C,D,E,A C.E,A,B,C,D D.E,D,C,B,A41.以下 B 不是队列的基本运算?A.从队尾插入一个新元素 B.从队列中删除第 i 个元素C.判断一个队列是否为空 D.读取队头元素的值42.若已知一个栈的进栈序列是 1,2,3, ,n,其输出序列为 p1,p2,p3,…,pn,若p1=n,则 pi 为 C 。A.i B.n-i C.n-i+1 D.不确定43.判定一个顺序栈 st(最多元素为 MaxSize)为空的条件是

    展开全文
  • 数据结构c语言习题

    千次阅读 多人点赞 2021-03-21 16:55:22
    数据结构c语言习题 第一章 绪论 一、选择 1.以下说法正确的是( D )。 A、数据元素是数据的最小单位 B、数据项是数据的基本单位 C、数据结构是带有结构的各数据项的集合 D、一些表面上很不相同的数据可以有相同...

    数据结构c语言版习题

    第一章 绪论

    一、选择题
    1.以下说法正确的是( D )。
    A、数据元素是数据的最小单位
    B、数据项是数据的基本单位
    C、数据结构是带有结构的各数据项的集合
    D、一些表面上很不相同的数据可以有相同的逻辑结构
    解析:A、B、C不对,正确答案是:数据项是数据的最小单位;数据元素是
    数据的基本单位;数据结构是带有结构的各数据元素的集合;D正确,如:windows系统中文件的组织架构图和一个单位的组织架构图,表面上是不相同的数据,但其实都是树形结构。
    2.计算机算法指的是解决问题的步骤序列,它必须具备( B ) 这五个特性。
    A、可执行性、可移植性、可扩充性、输入、输出
    B、可执行性、确定性、有穷性、输入、输出
    C、确定性、有穷性、稳定性、输入、输出
    D、易读性、稳定性、安全性、输入、输出
    解析:一个算法具备的5个重要特性是:有穷性,确定性,可行性,有零个或多个的输入,有1个或多个的输出;
    3.设n为某问题的规模,若某算法的时间复杂度为O(n2),则表示该算法的( C )。(北航2019年考研题)
    A、执行时间为n。
    B、执行时间为n2。
    C、执行时间与n2成正比关系。
    D、执行时间与n无关。
    解析:T(n) = O(f(n))“大O记法”,它表示随问题规模n的增大,算法执行时间的增长率和f(n)的增长率相同。
    4.程序运行时间函数f(n) = 1000, 下面哪项是用“大O记法”表示的时间复杂度。(B)
    A、O(1000)
    B、O(1)
    C、O(n=1000)
    D、O(n)
    解析:只要运行时间为常数,均用O(1)表示,即时间复杂度的常数阶为O(1)
    5.算法的时间复杂度取决于(D )。
    A、问题的规模
    B、待处理数据的初态
    C、计算机的配置
    D、A和B
    解析:算法的时间复杂度不仅与问题的规模有关,还与问题的其他因素有关。如某些排序的算法,其执行时间与待排序记录的初始状态有关。为此,有时会对算法有最好、最坏以及平均时间复杂度的评价。
    6.在存储数据时,通常不仅要存储各数据元素的值,而且还要存储( D )。
    A、数据的处理方法
    B、数据的存储方法
    C、数据元素的类型
    D、数据元素之间的关系
    解析:存储数据时,或者用顺序方式来描述数据元素之间的关系,或者用链
    式来描述数据元素之间的关系。
    7.在数据结构中,与所使用的计算机无关的是数据的(A)结构。
    A、逻辑
    B、存储
    C、逻辑和存储
    D、物理
    解析:数据的逻辑结构反映的是数据元素之间的逻辑关系,与使用的计算机无关:数据的物理结构,又称存储结构,是指数据在计算机中的表示,它包括数据元素的值和元素的关系,其中数据元素之间的关系在计算机中主要有顺序存储结构和链式存储结构两种。
    8.在下面的程序段中,对x的赋值的语句频度为(C  )
    for(i=0;i<n;i++)
    for(j=0;j<n;j++) x=x+1;
    A、O(2n) 
    B、O(n)
    C、O(n*n)
    D、O(log2n)
    解析:外循环的循环次数为n, 内循环的循环次数为n, 所以两个循环嵌套起来,时间复杂度为:O(n2)。
    9.在数据结构中,从逻辑上可以把数据结构分成(C)。
    A、动态结构和静态结构
    B、紧凑结构和非紧凑结构
    C、线性结构和非线性结构
    D、内部结构和外部结构
    解析:线性表属于线性结构,集合、树和图属于非线性结构。
    10.下面这段描述不能满足算法的特性,请问它违反了算法的哪条特性?( B )
    void exam()
    {
    int n = 2;
    while (n % 2 == 0)
    n = n + 2;
    printf(“%d\n”, n);
    }
    A、算法的确定性
    B、算法的有穷性
    C、算法的可行性
    D、以上三条都违反了
    解析:其中有一个死循环,违反了算法的有穷性特征。
    11.数据结构的逻辑结构被形式化地定义为一个二元组(D,S),其中D是(① )的有限集合,S是D上( ② )的有限集合。(B)
    A、数据 映射
    B、数据元素 关系
    C、算法 操作
    D、数据操作 存储
    解析:举个例子便于大家理解:如包含6个元素(a1,a2,a3,a4,a5,a6)的一维数组可以用这样的二元组形式化的描述为:D={a1,a2,a3,a4,a5,a6},S={<ai,ai+1>|i=1,2,3,4,5}。
    12.下面的程序段中, n为正整数,则最后一行的语句频度在最坏情况下是(D  )

    for(i=n-1;i>=1;i–)
    for(j=1;j<=i;j++)
    if (A[j]>A[j+1])
    A[j]与A[j+1]对换;
    A、O(n)
    B、O(nlog2n)
    C、O(n^3)
    D、O(n^2)
    解析;最后一行的语句频度在最坏情况下对应的情况是,每次if的条件都满足,从程序可看出,内循环的循环次数和外循环的循环变量有关系,f(n)=(n-1)+(n-2)+…+1=(n-1+1)(n-1)/2=(n2-n)/2。根据时间复杂度常系数可忽略和低次项可忽略的规则,可知时间复杂度为O(n2)。
    13.下面程序段的时间复杂度为( C )。(2014年全国考研题)
    count = 0;
    for (k=1; k<=n; k
    =2)
    for(j=1; j<=n; j++)
    count++;
    A、O(log2n)
    B、O(n)
    C、O(nlog2n)
    D、O(n^2)
    解析:分开来看,若外循环中的语句执行频度是f(n), 则,
    2f(n)<=n; f(n)<=log2n; 取最大值f(n)= log2n;
    又内循环的循环次数为n, 所以两个循环嵌套起来,时间复杂度为,O(nlog2n)
    二、简答题
    1.2020年注定是让人难忘的一年,这一年开头中国就备受新冠病毒的侵扰,让全国人民待在家里过了一个与众不同的春节,关注疫情数据也成了大家每天的“必修课”。作为重灾区的湖北,在2020年3月18日新增确诊首次清零。表1_1是2020年3月19日在疫情实时更新系统中查到的部分省份的数据,请描述其中的数据元素,数据项,数据对象和数据。
    在这里插入图片描述
    答:数据元素:一个地区的疫情记录。如:(湖北,0,67800,57681,3130)。
    数据项:湖北,0,67800,57681,3130均是该数据元素的数据项。
    数据对象:如果要研究的是国内的疫情,那么数据对象就是国内各地区的疫情记录的集合。
    数据:如果要研究的是全球的疫情,那么数据就是全球各国家各地区的疫情记录的集合。
    2.分析下面完成冒泡排序的算法的时间复杂度和空间复杂度。
    void bubbleSort(int array[], int n)
    {
    int i, j, tmp,flag;
    if (n <= 1) return;
    for (i = n-1; i > 0; i-- ){
    flag = 0; // 变量flag用来标记本趟排序是否发生了交换
    for (j = 0; j < i; j++){
    if (array[j] > array[j+1]){
    tmp = array[j];
    array[j] = array[j+1];
    array[j+1] = tmp;
    flag = 1; // 没发生交换flag=0不变, 发生了交换flag变为1
    }
    }
    if (flag == 0) return; //
    }
    }
    答案:
    该冒泡排序算法的时间复杂度为T(n)=O(n^2)
    该冒泡排序算法的空间复杂度为S(n)=O(1)
    解析:时间复杂度的计算
    因为计算时间复杂度时,常数项可以忽略,所以可选取最内层循环中的关键字交换操作为基本操作,又因为输入数据的情况不一样,基本操作的执行频度也不一样,所以以最坏情况来计算本算法的时间复杂度。本算法的最坏情况为待排序列为逆序,此时,对于外层循环的每次执行,内层循环中if语句的条件均成立,即基本操作的执行次数为n-i,i的取值为1~n-1。因此,基本操作总的执行次数为(n-1+1)(n-1)/2=n(n-1)/2,其中常系数和低次项可以忽略。
    所以,该冒泡排序算法的时间复杂度为T(n)=O(n2)。
    空间复杂度的计算
    由算法代码可以看出,算法在运行过程中临时占用的存储空间只有一个temp,与问题规模n没有关系,所以该冒泡排序算法的空间复杂度为S(n)=O(1)。
    以下是有关用“指针”操作“三元组”的相关程序,请将程序中缺少的语句补充完整。(请注意:答案中不要有多余的空格)

    # include<stdio.h>
    
    # include<stdlib.h>
    
    # define OK 1
    
    # define ERROR 0
    
    # define OVERFLOW -2 
    
    typedef int Status;
    
    typedef float ElemType;
    
    typedef ElemType *Triplet; // 声明Triplet为ElemType指针类型 
    
     
    
    //三元组的初始化
    
    Status initTriplet(Triplet &T, ElemType v0, ElemType v1, ElemType v2)
    
    {
    
        T = (       ElemType * Triplet             )malloc(3*sizeof(ElemType)); // 第一空
    
        if (              T==NULL !T      )   // 第二空
    
        {
    
            printf("分配内存失败!");
    
            exit(OVERFLOW);
    
        }
    
        T[0] = v0;
    
        T[1] = v1;
    
        T[2] = v2;
    
        return OK;
    
    }
    
    //释放内存,退出系统, 注意:动态分配内存需要及时释放内存空间
    
    void destroyTriplet(Triplet &T)
    
    {
    
              free(T)                   ; // 第三空
    
        printf("分配内存已释放!");
    
         exit(0);
    
    }
    
    // 用e获取T的第i(1~3)个元素的值, 
    
    Status getElem(Triplet T, int i, ElemType &e)
    
    {
    
        if (i < 1 || i > 3)
    
            return ERROR;
    
        else                e=T[i-1]       ; // 第四空
    
            return OK;
    
    }
    
    // 置T的第i元的值为e 
    
    Status putElem(Triplet &T,int i,ElemType e)
    
    {
    
        if (i < 1 || i > 3)
    
            return ERROR;
    
        else                 T[i-1]=e       ; // 第五空
    
            return OK;
    
    }
    
    int main()
    
    {
    
        Triplet T;
    
        Status flag;
    
        ElemType v0, v1, v2, e;
    
        
    
        printf("请进入三元组的三个值v0,v1,v2:\n"); 
    
        scanf("%f%f%f",         &v0,&v1,&v2                      ); //第6空
    
        // 初始化三元组 
    
        initTriplet(T,            v0,v1,v2           ); //第7空
    
        printf("调用初始化函数后,T的三个值为:%.1f,%.1f,%.1f\n", T[0], T[1], T[2]);
    
        // 请调用函数获得T的第2元的值 
    
                                getElem(T,2,e)       ; // 第8空
    
        printf("三元组第2元的值为:%.1f\n",e); 
    
        // 请调用函数修改T的第2元的值为56.7
    
                                        putElem(T,2,56.7)        ; // 第9空
    
        // 再次输出T的第2元的值 
    
        printf("三元组第2元的值改成了:%.1f\n",T[1]); 
    
        // 销毁三元组
    
                          destroyTriplet(T)                            ; // 第10空
    
        return 0;
    
    } 
    

    第二章 线性表

    1.在双向循环链表中,在p指针所指的结点后插入q所指向的新结点,其修改指针的操作是( C )。
    A、p->next=q; q->prior=p; p->next->prior=q; q->next=q;
    B、p->next=q; p->next->prior=q; q->prior=p; q->next=p->next;
    C、q->prior=p; q->next=p->next; p->next->prior=q; p->next=q;
    D、q->prior=p; q->next=p->next; p->next=q; p->next->prior=q;
    解析:双向循环链表的操作,与单链表相似,重接链条,语句有次序
    2.在双向链表存储结构中,删除p所指的结点时须修改指针( A )。
    A、p->next->prior=p->prior; p->prior->next=p->next;
    B、p->next=p->next->next; p->next->prior=p;
    C、p->prior->next=p; p->prior=p->prior->prior;
    D、p->prior=p->next->next; p->next=p->prior->prior;
    解析:双向链表的删除操作,双向链表的操作,注意语句的次序
    3.在单链表中,要将s所指结点插入到p所指结点之后,其语句应为( D )。
    A、s->next=p+1; p->next=s;
    B、(*p).next=s; (*s).next=(*p).next;
    C、s->next=p->next; p->next=s->next;
    D、s->next=p->next; p->next=s;
    解析:插入后重新接链条:s->next=p->next; p->next=s; 语句的次序不能改变
    4.设一个有序的单链表中有n个结点,现要求插入一个新结点后使得单链表仍然保持有序,则该操作的时间复杂度为( D)。
    A、o(log2n)
    B、o(1)
    C、o(n^2)
    D、o(n)
    解析:该题主要完成的是查找新元素应该插入的位置,所以查找的时间复杂度是该题的时间复杂度,为o(n)
    5.`设有一个正整数序列组成的有序单链表,试编写能实现下列功能的算法:确定在序列中比正整数x大的数有几个。

    #include<stdio.h>

    #include<stdlib.h>

    //定义单链表结构

    typedef struct LNode{

    int data;

    struct LNode *next;

    }LNode,*LinkList;

    //创建空的单链表

    LinkList creat_head(){

     LinkList p;
    
     p=(LinkList)malloc(sizeof(LNode));
    

    ­­­­ _______(1)______________;//p->next=NULL
    return§;

    }

    //输出单链表

    void print_list(LinkList &L){

       LinkList p;
    
       for(p=L->next;p!=NULL;)
    
       { 
    
          printf("%d",____(2)______);//p->data
    
          _____(3)__________;//p=p->next
    
       }
    
    }
    

    // 生成单链表

    void creat_list(LinkList &L,int n){

    LinkList p,q; 
    
     int i; 
    
     p=L; 
    
     for(i=1;i<=n;i++){ 
    
       q=(LinkList)malloc(sizeof(LNode)); 
    
       printf("data:"); 
    
       scanf("%d",&q->data);
    
       q->next=NULL;
    

    p->next=q;

      _____(4)_______;//p=q
    }   
    

    print_list(L); //显示创建好的链表元素

    }
    

    //计算函数

    int count(LinkList L,int x)

    {

    int num=0;

    LNode *p;

    p=L->next;

    while(p&&p->data<=x)

      ______(5)_________;//p=p->next
    
    while(p){
    

    if((6)__)//p->data>x {

    num++;

    __(7) ____;//p=p->next
    }

    else{

     p=p->next;
    

    }

    }

    return num;

    }

    main(){

    int i,num,n;
    
    LinkList L;   
    
    _____(8)________;      //创建链表头结点//L = creat_head()
    

    printf(“输入链表的结点个数 n=”);

    scanf("%d",&n);   
    
    ______(9)__________;   //创建n个结点的单链表  //creat_list(L,n)
    
     printf("输入一个数:");
    
     scanf("%d",&i);
    
     printf("%d",____(10)________);//count(L,i)
    

    }`
    6.将两个各有n个元素的有序表归并成一个有序表,其最少的比较次数是( A)。
    A、n
    B、2n-1
    C、2n
    D、n-1
    解析:当第一个有序表中所有的元素都小于(或大于)第二个表中的元素,只需要用第二个表中的第一个元素依次与第一个表的元素比较,总计比较n次。
    7.在一个长度为n的顺序表中,在第i个元素(1≤i≤n+1)之前插入一个新元素时须向后移动( B )个元素
    A、n-i
    B、n-i+1
    C、n-i-1
    D、i
    解析:在第i个位置插入元素,操作时需移动的元素从第i个元素到最后一个元素
    8.在n个结点的顺序表中,算法的时间复杂度是O(1)的操作是(A )。
    A、访问第i个结点(1≤i≤n)和求第i个结点的直接前驱(2≤i≤n)
    B、在第i个结点后插入一个新结点(1≤i≤n)
    C、删除第i个结点(1≤i≤n)
    D、将n个结点从小到大排序
    解析:在顺序表中插入一个结点的时间复杂度都是O(n^2),排序的时间复杂度为O(n ^2)或O(nlog2n)。顺序表是一种随机存取结构,访问第i个结点和求第i个结点的直接前驱都可以直接通过数组的下标直接定位,时间复杂度是O(1)。
    9.创建一个包括n个结点的有序单链表的时间复杂度是(C )。
    A、O(1)
    B、O(n)
    C、O(n ^2)
    D、O(nlog2n)
    解析:单链表创建的时间复杂度是O(n),而要建立一个有序的单链表,则每生成一个新结点时需要和已有的结点进行比较,确定合适的插入位置,所以时间复杂度是O(n ^2)
    10.已知L是带表头结点的单链表,删除第一个元素结点的语句是(B )。
    A、L = L->next;
    B、L-> next = L-> next -> next;
    C、L = L;
    D、L-> next = L;
    解析:删除图中的第一个元素a1,则头指针的next域(L->next)指向的是a1的下一个元素,a1元素的位置可表示为L-> next,a1的下一个元素为L-> next->next,所以答案为L-> next = L-> next -> next;
    在这里插入图片描述

    11.若某线性表最常用的操作是存取任一指定序号的元素和在最后进行插入和删除运算,则利用( A )存储方式最节省时间。
    A、顺序表
    B、双链表
    C、带头结点的双循环链表
    D、单循环链表
    解析:顺序存储结构的特点是随机存取(时间复杂度为常数阶),在顺序表的最后进行插入和删除不需要移动元素,时间复杂度是常数阶。
    12.设计一个函数Max(LinkList L),实现通过一趟遍历确定单链表中值最大的结点,且返回该值。

    float Max (LinkList L ){ 
    
    if(L->next==NULL) return NULL; 
    
    pmax=L->next; //假定第一个结点中数据具有最大值
    
    p=L->next->next; 
    
    while(p != NULL ){//如果下一个结点存在
    
    if(p->data > pmax->data)pmax=p; //如果p的值大于pmax的值,则重新赋值
    
    p=p->next;//遍历链表
    
    } 
    
    return pmax->data;
    
    } 
    
    以下程序是采用单链表存储结构实现线性表的插入操作,阅读程序,补全代码
    
    #include<stdio.h>
    
    #include<stdlib.h>
    
    typedef  struct LNode{
    
    int data;  
    
    struct LNode *next;
    
    }LNode,*LinkList;
    
     
    
    void creat_list(LinkList &L,int); //创建链表
    
     
    
    void insert_list(LinkList &L,int,int ); //插入数据
    
     
    
    void print_list(LinkList &L);//显示数据  
    
     
    
    //尾插法创建单链表
    
    void creat_list(LinkList &L,int n)
    
    {  
    
      LinkList p,q;
    
    //创建头结点
    
       L=(LinkList)malloc(sizeof(LNode));
    
      ——(1)—— ;//L->next=NULL
    
       int i;  
    
       p=L;    
    
       for(i=1;i<=n;i++)  
    
      {  
    
         q=(LinkList)malloc(sizeof(LNode));  
    
         printf("data:");  
    
         scanf("%d",&——(2)——);//q->data
    
         q->next=NULL;
    
         ——(3)——);//p->next=q
    
         p =q;
    
       }  
    
     }
    
     
    
    //插入新数据
    
    void insert_list(LinkList &L,int x,int i )
    
    {  
    
     
    
       int j=0;  
    
       LinkList p,s;
    
       p=L;
    
       while((p!=NULL)&&(j<i-1))
    
      {  
    
         ——(4)——;//p=p->next
    
           j++;
    
       }
    
       if(p==NULL|| j >i-1)  
    
       {
    
        printf("插入点位置错误!\n");
    
        exit(0);
    
       }   
    
       s=(LinkList)malloc(sizeof(LNode));
    
      ——(5)——;//s->data=x
    
       s->next=p->next;
    
     ——(6)——;//p->next=s
       print_list(L);
    
     }
    
     
    
    //显示数据值
    
    void print_list(LinkList &L)
    
    {  
    
       LinkList p;
    
      ——(7)——;//p=L->next
    
       while(p!=NULL)
    
      {  
    
           printf("%d,",p->data);  
    
          ——(8)——;//p=p->next
       }
    
    }  
    
    main()
    
    {  
    
     LinkList L,p;  
    
     int n;  
    
     int x,i;  
    
     printf("输入链表的结点个数 n=");
    
     scanf("%d",&n);    
    
    ——(9)——;   //创建n个结点的单链表//creat_list(L,n)
    
     printf("\n*****************************************************\n");
    
     printf("输入要插入的元素值 x=");
    
     scanf("%d",&x);
    
     printf("\n输入要插入的位置 i=");
    
     scanf("%d",&i);
    
    ——(10)——;   //向链表的第i个元素前插入数据x//insert_list(L,x,i)
    
      system("pause");    
    
    }
    

    第四章 串

    1.串是一种特殊的线性表,其特殊性体现在( B)。
    A、可以顺序存储
    B、数据元素是字符
    C、可以链式存储
    D、数据元素没限制
    解析:串的特殊性是数据元素是字符
    2.下面关于串的的叙述中,( B )是不正确的?
    A、串是字符的有限序列
    B、空串是由空格构成的串
    C、模式匹配是串的一种重要运算
    D、串既可以采用顺序存储,也可以采用链式存储
    解析:空串的长度为0,空格串是有元素的(空格符),长度不为0
    3.串的长度是指( B)。
    A、串中所含不同字母的个数
    B、串中所含字符的个数
    C、串中所含不同字符的个数
    D、串中所含非空格字符的个数
    解析:串中字符的数目称为串的长度
    4.( D )是C语言中“abcd321ABCD”的子串。
    A、abcd
    B、321AB
    C、“abcABC”
    D、“21AB”
    解析:C语言中规定字符串是用一对双引号括起来的字符序列。
    5.设有两个串p和q,求q在p中首次出现的位置的运算称做(B )。
    A、连接
    B、模式匹配
    C、求子串
    D、求串长
    解析:寻找q在p中首次出现的位置的运算称作模式匹配
    6.串“ababaaabab”的next数组为( C )。
    A、0123456789
    B、0121211112
    C、0112342234
    D、0123012322
    解析:按照next数组的算法依次计算即可
    7.SubString( sub, “structure”, 4, 3)的结果是( “uct” )。注意:字符串用双引号括起来
    解析:该含义是从第4个位置截取3个元素结果为uct
    8.S = “stg” ,T =“rin”,则执行 StrInsert(S, 3, T) 之后得到( “string” )。注意:字符串用双引号括起来
    解析:该函数的意义是在S串的第3个位置插入T串结果为string
    9.INDEX(“DATASTRUCTURE”, “C”)=9____。(位置从1开始)
    解析:该函数是查找str在主串中的索引位置
    10.`以下算法是采用BF算法实现字符串的模式匹配过程,请补全代码(位置从0开始)。

    int mate(char *a, char *c){

    int i=0,j=0;

    while(i<strlen(a) && j<strlen©){

       if(___(1)____)//a[i]==c[j]
       {
    
           i++;
    
           j++;
    

    }

    else{

       _____(2)____;//i=i-j+1
       j=0;
    

    }

    }

    if(j==strlen©){

       return i-strlen(c)+1;
    

    }

    return 0;

    }

    int main(int argc, char *argv[]) {

    int n=mate(“abc”,“a”);

    printf("%d",(3));//n

    return 0;

    }`

    采用堆分配存储方式实现在串S的第pos个位置前插入串T,补全代码
    
    //存储结构定义
    
    typedef struct {
    
        char *ch;    
    
        int  length;  
    
     } HString
    
    int StrInsert(HString &S,int pos,HString T){  
    
      int i;
    
      if (pos<1||pos>S.length+1) return 0;
    
      if (T.length){
    
         if (!(S.ch=(char*) realloc(S.ch,(S.length+T.length)*sizeof(char))))
    
         exit(OVERFLOW);
    
         for (i=S.length-1;i>=pos-1;--i){
    
            ___(1)_________ ;//S.ch[i+T.length]=S.ch[i]
    
      }
    
      for (i=0; i<=T.length-1;i++)
    
      _______(2)___________;//S.ch[pos-1+i]=T.ch[i]
    
      _______(3)_____________;//S.length+=T.length
      } return OK;
    
    }
    

    第五章数组和广义表作业

    1.假设以行序为主序存储二维数组A=array[1…100,1…100],设每个数据元素占2个存储单元,基地址为10,则LOC[5,5]=( B )。
    A、808
    B、818
    C、1010
    D、1020
    解析:以行序为主,则LOC[5,5]=[(5-1)*100+(5-1)]*2+10=818。
    2.设有数组A[i,j],数组的每个元素长度为3字节,i的值为1到8,j的值为1到10,数组从内存首地址BA开始顺序存放,当用以列为主存放时,元素A[5,8]的存储首地址为(B )。
    A、BA+141
    B、BA+180
    C、BA+222
    D、BA+225
    习题解析:以列序为主,则LOC[5,8]=[(8-1)*8+(5-1)]*3+BA=BA+180。
    3.多维数组之所以有行优先顺序和列优先顺序两种存储方式是因为(D )。

    A、数组的元素处在行和列两个关系中
    B、数组的元素必须从左到右顺序排列
    C、数组的元素之间存在次序关系
    D、数组是多维结构,内存是一维结构
    习题解析:由于存储单元是一维的结构,而数组可能是多维的结构,所以用一组连续存储单元存放数组的数据元素就有次序约定问题。因此多维数组有行优先顺序和列优先顺序两种存储方式,因此答案选择D。
    4.设二维数组A[1… m,1… n](即m行n列)按行存储在数组B[1… m*n]中,则二维数组元素A[i,j]在一维数组B中的下标为( A)。
    A、(i-1)n+j
    B、(i-1)n+j-1
    C、i
    (j-1)
    D、j
    m+i-1
    习题解析:特殊值法。取i=j=1,易知A[1,1]的的下标为1,四个选项中仅有A选项能确定的值为1,故选A。
    5.二维数组A的每个元素是由10个字符组成的串,其行下标i=0,1,…,8,列下标j=1,2,…,10。若A按行先存储,元素A[8,5]的起始地址与当A按列先存储时的元素( B )的起始地址相同。设每个字符占一个字节。
    A、A[8,5]
    B、A[3,10]
    C、A[5,8]
    D、A[0,9]
    习题解析:设数组从内存首地址M开始顺序存放,若数组按行先存储,元素A[8,5]的起始地址为:M+[(8-0)*10+(5-1)]*1=M+84;若数组按列先存储,易计算出元素A[3,10]的起始地址为:M+[(10-1)*9+(3-0)]1=M+84。故选B。
    6.一维数组的逻辑结构是__、
    线性结构___________,存储结构是__顺序结构 顺序存储结构___________。
    习题解析:一维数组{a0,a1,…,an-1}是n个相同类型数据元素构成的有限序列,线性表是具有相同特性的数据元素的一个有限序列。所以一维数组的逻辑结构是线性结构。数组中的有限序列存储在一块连续的内存单元中,所以一维数组的存储结构是顺序结构
    7.二维数组A[10][20]采用列序为主方式存储,每个元素占一个存储单元,且A[0][0]的地址是200,则A[6][12]的地址是(326     )
    习题解析:采用列主序时,LOC(A[6][12])=LOC(A[0][0]+(12
    10+6)*1)=326
    8.设数组a[1…50,1…80]的基地址为2000,每个元素占2个存储单元,若以行序为主序存储,则元素a[45,68]的存储地址为( 9174 )。
    习题解析:Loc(ai,j)=2000+((45-1)×80+(68-1))×2=9174
    9.数组A中,每个元素A[i,j]的长度均为32个二进制位,行下标从-1到9,列下标从1到11,从首地址S开始连续存放主存储器中,主存储器字长为16位。求:
    ① 存放该数组所需多少单元?( 242 )
    ② 存放数组第4列所有元素至少需多少单元?( 22 )
    ③ 数组按行存放时,元素A[7,4]的起始地址是多少?( S+182 )
    ④ 数组按列存放时,元素A[4,7]的起始地址是多少?( S+142 )
    习题解析:
    每个元素32个二进制位,主存字长16位,故每个元素占2个字长,行下标可平移至1到11。
    (1)242。该数组包括的元素个数总计有:(9-(-1)+1)×(11-1+1)=121,因为每个元素占2个字长,存放该数组所需单元总计为121×2=242个。
    (2)22。第4列包括的元素个数总计有(9-(-1)+1)=11,每个元素占2个字长,因此,存放第4列所有元素至少需单元为121×2=242个。
    (3)S+182。LOC=S+((7-(-1))×(11-1+1)+(4-1))×2= S+182。
    (4)S+142。LOC=S+((7-1) ×(9-(-1)+1) +(4-(-1))) ×2= S+142。
    10.对特殊矩阵采用压缩存储的主要目的是(D )。
    A、表达变得简单
    B、对矩阵元素的存取变得简单
    C、去掉矩阵中多余的元素
    D、减少不必要的存储空间
    11.对n阶对称矩阵压缩存储时,需要表长为( C )的顺序表。
    A、n/2
    B、n2/2
    C、n(n+1)/2
    D、n(n-1)/2
    习题解析:对称矩阵只需要存储一半元素,即存储其下(上) 三角(包括对角线)中的元素,总计包括元素个数为1+2+3+…+(n-1)+n=n(n+1)/2。
    12.稀疏矩阵一般的压缩存储方法有两种,即(C )。
    A、二维数组和三维数组
    B、三元组和散列
    C、三元组和十字链表
    D、散列和十字链表
    13.下面说法不正确的是( A )。
    A、广义表的表头总是一个广义表
    B、广义表的表尾总是一个广义表
    C、广义表难以用顺序存储结构
    D、广义表可以是一个多层次的结构
    习题解析:任何一个非空广义表的表头元素可能是原子元素,也可能是表元素,但其表尾元素一定是广义表。由于广义表中的数据元素既可以是单个元素,也可以是子表,因此广义表难以用顺序存储结构来表示,通常用链式存储结构来表示。表中的每个元素可用一个结点来表示,广义表中有两类结点:一类是单个元素结点,一类是子表结点。
    14.广义表((a,b,c,d))的表头是(C)。
    A、a
    B、( )
    C、(a,b,c,d)
    D、(b,c,d)
    习题解析:
    表头为非空广义表的第一个元素,可以是一个原子,也可以是一个子表,((a,b,c,d))的表头为一个子表(a,b,c,d)。
    15.广义表((a,b,c,d))的表尾是(B )。
    A、a
    B、( )
    C、(a,b,c,d)
    D、(b,c,d)
    习题解析:表尾为除去表头之外,由其余元素构成的表,表尾一定是个广义表,((a,b,c,d))的表尾为空表( )。
    16.设有广义表D=(a,b,D),则其长度为( B)。
    A、1
    B、3
    C、∞
    D、5
    习题解析:广义表的长度是指广义表中所含元素的个数。

    第六章 树与二叉树理论作业

    1.由3个结点可以构造出多少种不同的二叉树?(D)
    A、2
    B、3
    C、4
    D、5
    在这里插入图片描述
    2.一棵完全二叉树上有1001个结点,其中叶子结点的个数是(D)。
    A、250
    B、500
    C、254
    D、501
    习题解析:答案解析:解释:设度为0结点(叶子结点)个数为A,度为1的结点个数为B,度为2的结点个数为C,有A=C+1,A+B+C=1001,可得2C+B=1000,由完全二叉树的性质可得B=0或1,又因为C为整数,所以B=0,C=500,A=501,即有501个叶子结点。
    3.深度为h的满m叉树的第k层有(A)个结点。(1=<k=<h)
    A、m^(k-1)
    B、m^k-1
    C、m^(h-1)
    D、m^h-1
    习题解析:深度为h的满m叉树共有m ^ h-1个结点,第k层有 m^(k-1)个结点。
    4.一棵非空的二叉树的先序遍历序列与后序遍历序列正好相反,则该二叉树一定满足(C)。
    A、所有的结点均无左孩子
    B、所有的结点均无右孩子
    C、只有一个叶子结点
    D、是任意一棵二叉树
    答案解析:因为先序遍历结果是“中左右”,后序遍历结果是“左右中”,当没有左子树时,就是“中右”和“右中”;当没有右子树时,就是“中左”和“左中”。则所有的结点均无左孩子或所有的结点均无右孩子均可,所以A、B不能选,又所有的结点均无左孩子与所有的结点均无右孩子时,均只有一个叶子结点,故选C。
    5.对二叉树的结点从1开始进行连续编号,要求每个结点的编号大于其左、右孩子的编号,同一结点的左右孩子中,其左孩子的编号小于其右孩子的编号,可采用(C)遍历实现编号。
    A、先序
    B、中序
    C、后序
    D、从根开始按层次遍历
    答案解析:根据题意可知按照先左孩子、再右孩子、最后双亲结点的顺序遍历二叉树,即后序遍历二叉树。
    6.在树中,若结点A有4个兄弟,而且B是A的双亲,则B的度为(C )
    A、3
    B、4
    C、5
    D、6
    答案解析:B有5个孩子,故B的度为5.
    7.若树T中度为1、2、3、4的结点个数分别为4、3、2、2,则T中叶子结点的个数为(B )。
    A、13
    B、14
    C、15
    D、24
    答案解析:树中的分支数为14+23+32+42=24,树中的结点总数为24+1=25,叶子结点个数为25-4-3-2-2=14
    8.以下属于前缀编码的是(C )。
    A、{0,1,01,010,110}
    B、{01,00,10,001,110,101}
    C、{0,1101,1110,1100,1111}
    D、{00,01,10,11,101}
    答案解析:前缀编码指的是,任何一个字符的编码都不是同一字符集中另一个字符的编码的前缀。本题中只有C选项符合前缀编码的定义。
    9.引入二叉线索树的目的是(A)。
    A、加快查找结点的前驱或后继的速度
    B、为了能在二叉树中方便的进行插入与删除
    C、为了能方便的找到双亲
    D、使二叉树的遍历结果唯一
    答案解析:为了保存二叉树遍历过程中得到的每个结点的前驱和后继信息,引入了线索二叉树,以加快查找结点的前驱或后继的速度。
    10.设F是一个森林,B是由F变换得的二叉树。若F中有n个非终端结点,则B中右指针域为空的结点有( C )个。
    A、n−1
    B、n
    C、n + 1
    D、n + 2
    答案解析:n个非终端结点即表示森林中有n颗二叉树,转换成二叉树中,这n个结点的左子树中会有n个右指针域为空的结点,另外n个非终端结点中的最后一个结点的右指针域也为空,共n+1个。
    11.给定二叉树的先序、中序和后序遍历序列中的两个,就可以唯一确定一棵二叉树。(错误)
    答案解析:二叉树的存储结构有顺序存储结构和链式存储结构
    12.定二叉树的先序、中序和后序遍历序列中的两个,就可以唯一确定一棵二叉树。(同上
    13.在线索二叉树中每个结点通过线索都可以直接找到它的前驱和后继。(错误)
    答案解析:线索二叉树中的有左右子树的结点,它们的指针指向其左右子树,并没有指向前驱或后继,因此这些结点是不能直接找到它的前驱和后继的。
    14.将一棵树转成二叉树,根结点一定没有右子树。(正确
    习题解析:树转换成二叉树按照“左孩子,有兄弟”结构存储,由于一棵树没有兄弟,所以右子树为空。
    15.着信息时代的到来,信息越来越多,如何压缩信息已经是重要课题。哈夫曼编码是一种无损压缩编码方式,经常应用于数据压缩。现有一段通信的电文仅由8个字母A、B、C、D、E、F、G、H组成,字母在电文中出现的频率分别为0.07,0.19,0.02,0.06,0.32,0.03,0.21,0.10。试为这8个字母设计合适的编码,使得电文的长度最短。
    规定(1)在构造哈夫曼树时,左子树结点的权值小于右子树结点的权值;
    (2)进行哈夫曼编码是,左分支标0,右分支标1;
    答案:请将每个字母的哈夫曼编码填在下面的空中
    (1): 1010
    (2): 00
    (3):10000
    (4):1001
    (5):11
    (6):10001
    (7):01
    (8):1011
    答案解析:先将概率放大100倍,以方便构造哈夫曼树。
    w={7,19,2,6,32,3,21,10},按照哈夫曼算法可以得出相应的哈夫曼编码
    16.以下程序的功能是按照先序次序创建二叉树,并对二叉树中序遍历,输出中序遍历的结果,请将程序中缺少的语句补充完整。

    #include<stdio.h>
    #include<stdlib.h>
    #include<malloc.h>
    #include<string.h>
    #define OK 1
    #define ERROR 0
    #define OVERFLOW -1
    #define STACK_INIT_SIZE 50
    typedef int Status;
    typedef char ElemType;
    //树节点
    typedef struct BiTNode{
    ElemType data; // 1                            
    struct BiTNode *lchild,*rchild;
    }BiTNode, *BiTree;
    //栈结构
    typedef struct{   
          BiTNode *base;       
          BiTNode *top;       
          int stacksize;       
    }SqStack;
    //初始化栈
    Status InitStack(SqStack &s) 
    {  //过程略,此处不做答
    } 
    //取栈顶元素
    BiTNode *Top (SqStack s)
    {  //过程略,此处不做答
    //入栈
    Status Push(SqStack &s, BiTree e)
    { 
    //过程略,此处不做答
    } 
    //出栈
    Status  Pop(SqStack &s)
    {  //过程略,此处不做答
    } 
    //判空栈
    int StackEmpty(SqStack S) 
    {//过程略,此处不做答
    } 
    //先序创建二叉树
    BiTree Create(BiTree T)
    {
           ElemType ch;
           ch=getchar();//2                        
           if(ch=='#')
           T=NULL;
           else
           {
          T=(BiTNode *)malloc(sizeof(BiTNode));//3
          T->data=ch; T -> data=ch; T->data= ch; T ->data=ch; T ->data=ch; T -> data=ch;                         /*根结点赋值
          T->lchild=Create(T->lchild);        
          T->rchild=Create(T->rchild);//5                                                         /*先序创建右子树
           }
           return T;
     } 
    //二叉树的中序非递归遍历算法:
    void IneOrderNoRec(BiTree BT)
    {
      SqStack S;
      InitStack(S);
      BiTree p=BT;//6       
     while((NULL!=p)||!StackEmpty(S))
      { // 找到最左下的结点
    if(NULL!=p)
        {      
    Push(S,p);    //7    /*压栈
         p=p->lchild;
        }         
           else
        {//根指针退栈,访问根结点
          p=Top(S);
          Pop(S);
      printf("%c",p->data);//8  /*访问根结点
    p=p->rchild;
        }
      }
    }
    //主函数
    main() 
    {
      BiTree T;
      SqStack S;
      int flag;
      printf("请按先序次序输入二叉树节点的值(一个字符),用#表示空树:\n");      
    T=Create(T);  //9             /*先序创建二叉树
      printf("\n二叉树的中序非递归遍历结果:"); 
    IneOrderNoRec(T);   //10                   /*中序非递归遍历
      }
    

    第七章图作业

    1.用邻接表表示图进行广度优先遍历时,通常借助( B )来实现算法。
    A、栈
    B、队列
    C、散列表
    D、链表
    习题解析:广度优先搜索是一种分层的搜索过程,每向前走一步可能访问一批顶点,为了实现逐层访问,算法中使用了一个队列,用以记忆正在访问的这一层和上一层的顶点,以便于向下一层访问。
    2.下列哪一种图的邻接矩阵是对称矩阵(A )。
    A、无向图
    B、其它都不对
    C、AOV网
    D、有向图
    习题解析:图的邻接矩阵概念
    3.在AOV网中,该图的拓扑序列中,若顶点Vi在顶点Vj之前,则下列情形不可能出现的是(D )。
    A、图中有弧<Vi,Vj>
    B、图中有一条从Vi到Vj的路径
    C、图中没有弧<Vi,Vj>
    D、图中有一条从Vj到Vi的路径
    习题解析:图的邻接矩阵概念
    4.下列关于最小生成树的说法中,正确的是(A) l、最小生成树的代价唯一、最小生成树的代价唯一 Ⅱ、所有权值最小的边一定会出现在所有的最小生成树中 Ⅲ、使用普里姆(Prim)算法从不同顶点开始得到的最小生成树一定相同 Ⅳ、使用普里姆算法和克鲁斯卡尔(Kruskal)算法得到的最小生成树总不相同
    A、仅Ⅰ
    B、仅Ⅱ
    C、仅Ⅰ、Ⅲ
    D、仅Ⅱ、Ⅳ
    5.在无向图G的邻接矩阵A中,若A[i][j]等于1,则A[j][i]等于( A)。
    A、1
    B、0
    C、不确定
    D、无穷大
    习题解析:无向图的邻接矩阵是对称矩阵,A[i][j]=1,所以A[j][i]=1。
    6.在这里插入图片描述
    D
    习题解析:每次输出入度为0的点,输出之后从原图删去该点以及该点为起点的边,然后继续输出入度为0的点,知道输出全部顶点。
    7.如果一个有向无权图图采用邻接矩阵表示,计算第i个结点的入度的方法是(B)。
    A、该邻接矩阵第 i 行中为1的个数
    B、该邻接矩阵第 i 列中为1的个数
    C、无法确定
    D、该邻接矩阵第 i 行中为1的个数加该邻接矩阵第 i 列中为1的个数
    习题解析:有向无权图的邻接矩阵中,行中为1的个数是该结点的出度,列中为1的个数是该结点的入度。
    8.在这里插入图片描述
    f,d,e
    在这里插入图片描述
    9.在这里插入图片描述
    1、f,g,2 g,f,2
    2、e,f,3 f,e,3 a,c,3 c,a,3
    3、e,f,3 f,e,3 a,c,3 c,a,3
    4、a,b,4 b,a,4 d,h,4 h,d,4
    5、a,b,4 b,a,4 d,h,4 h,d,4
    6、b,d,5 d,b,5 c,d,5 d,c,5 d,g,5 g,d,5 c,h,5 h,c,5
    7、b,d,5 d,b,5 c,d,5 d,c,5 d,g,5 g,d,5 c,h,5 h,c,5
    在这里插入图片描述
    10.在这里插入图片描述
    1、28
    2、v3 V3
    3、v5 V5
    4、v8 V8
    5、v9 V9
    6、v10 V10
    7、v11 V11
    在这里插入图片描述
    实验填空题(注意大小写要严格按规定写,语法按照C语言语法完成):

    #define MAX_VEX_NUM 20
    图的邻接矩阵定义如下:
    typedef struct
    {
    int vertex[MAX_VEX_NUM]; //顶点信息
    int arcs[MAX_VEX_NUM][MAX_VEX_NUM];//边信息
    int vex_num, arc_num;
    } Mgraph;
    int LocateVex(Mgraph g, int v) //确定v在g中位置
    { 
    int i;
    for (i = 0; i < g.vex_num; ++i)
    { 
    if(g.vertex[i]==v)
    return i; 
    } 
    return -1;
    }
    创建无向不带权图的算法如下:
    void create_UDG(Mgraph &g)
    { 
    int i, j, k; 
    int v1, v2; 
    printf("请输入顶点个数,边的个数:\n");
    scanf("%d,%d",     &g.vex_num   ,&g.arc_num); 
    printf("请输入顶点信息:\n");
    for (i = 0; i < g.vex_num; ++i) 
    scanf("%d", &g.vertex[i]); //构造顶点向量
    for (i = 0; i < g.vex_num; ++i) //初始化邻接矩阵
    for (j = 0; j < g.vex_num; ++j) 
    g.arcs[i][j] = 0  ;
    printf("请输入边的信息:\n"); 
    for (k = 0; k < g.arc_num; ++k) 
    {
    //构造邻接矩阵
    scanf("%d,%d",&v1, &v2); //输入一条边依附的顶点
    i = LocateVex(g, v1); //确定v1和v2在G中位置
    j = LocateVex(g, v2 ); 
    if(i == -1 || j==-1) return;
    g.arcs[i][j] = 1; 
    g.arcs[j][i] =  g.arcs[i][j] ;
    }
    }
    int main()
    { 
    Mgraph g; 
     create_UDG(g) ;//创建图
    out_UDG(g); 
    return 0;
    }
    

    第八章查找作业

    1.对n个元素的表做顺序查找时,若查找每个元素的概率相同,则平均查找长度为( C)。
    A、(n-1)/2
    B、n/2
    C、(n+1)/2
    D、n
    习题解析:总查找次数N=1+2+3+…+n=n(n+1)/2,则平均查找长度为N/n=(n+1)/2。
    2.设哈希表长为14,哈希函数是H(key)=key%11,表中已有数据的关键字为15,38,61,84共四个,现要将关键字为49的元素加到表中,用二次探测法解决冲突,则放入的位置是( D )。
    A、8
    B、3
    C、5
    D、9
    习题解析:关键字15放入位置4,关键字38放入位置5,关键字61放入位置6,关键字84放入位置7,再添加关键字49,计算得到地址为5,冲突,用二次探测法解决冲突得到新地址为6,仍冲突,再用用二次探测法解决冲突,得到新地址为4,仍冲突,再用用二次探测法解决冲突,得到新地址为9,不冲突,即将关键字49放入位置9。
    3.对于哈希函数H(Key) = key % 13, 被称为同义词的关键字是( D )。
    A、35和41
    B、23和39
    C、15和44
    D、25和51
    习题解析:具有相同函数值的关键字对该哈希函数来说称作同义词,即key1不等于key2,而f(key1) = f(key2)。25和51对13取余得到相同的余数12。
    4.从空树开始,依次插入结点23,12,8,34,28,78构造二叉平衡排序树,则构造好的二叉树按层序遍历的结果是(C)。
    A、12,8,28,23,34,78
    B、23,12,28,34,8,78
    C、28,12,34,8,23,78
    D、8,12,23,28,34,78
    在这里插入图片描述

    5.在这里插入图片描述
    1、28
    2、43
    3、8
    4、37
    5、18
    6、47
    7、75
    8、26
    9、62
    10、1.444
    习题解析:链地址法解决冲突,是将所有关键字为同义词的记录存储在同一线性链表中。
    6在这里插入图片描述
    1、12
    2、7
    3、17
    4、2
    5、11
    6、16
    7、21
    8、1
    9、9
    10、23
    习题解析:二叉排序树中左子树的值均比根结点小,右子树的值均比根结点大,且每一颗子树均是二叉排序树。
    7.在这里插入图片描述
    1、12
    2、1
    3、49
    4、1
    5、38
    6、2
    7、1
    8、21
    9、2
    10、1.375
    8.下列算法的功能为:采用折半方法进行关键字的查找,请将算法中缺失的语句按照顺序填入对应的空格。(注意:答案中不要出现空格)
    结构定义:

    typedef int KeyType;
    typedef struct{      
       KeyType key;  
    }ElemType;
    typedef struct {
        ElemType *elem;   
       int length;       
    } SSTable;
    折半查找算法:
    int Search_Bin(SSTable &ST,KeyType key){
    //在有序表ST中折半查找其关键字等于key的数据元素
    //若找到,则函数值为该元素在表中的位置,否则为0
    int low=1, high=ST.length,mid;  
    while(low<=high){
    
              
    mid=(low+high)/2 ; // (1)
    
    if(EQ(key,   ST.elem[mid].key ))    // (2)
       return mid;
        else if(LT(key,ST.elem[mid].key))             
    high=mid-1  ; // (3)
             else     
      low=mid+1 ;  // (4)
    }
    return 0;   
    }
    
    展开全文
  • 数据结构C语言习题集答案第三章.doc习题三3.1 3.10 3.13 3.5 3.6 3.15 3.17 3.19 3.24 3.29 3.31 3.51 给定操作序列P1P2P3PiPn(Pk为S或X,k1,2,n )是合法的,当且仅当满足下列条件a. 序列中包含的S的个数和X的个数...

    253b171540df25e1b84436cbe50dfc72.gif数据结构C语言习题集答案第三章.doc

    习题三3.1 3.10 3.13 3.5 3.6 3.15 3.17 3.19 3.24 3.29 3.31 3.51 给定操作序列P1P2P3PiPn(Pk为S或X,k1,2,n )是合法的,当且仅当满足下列条件a. 序列中包含的S的个数和X的个数相等;b. 对于任意的j(1jn);有P1P2P3Pj子序列中所包含的S的个数大于等于X的个数;2证明设P1P2P3PiPn ,Q1Q2Q3QiQn是两个不同的合法序列; 两者不同, kmini| PiQi , 1in 且k1, PkQk (因P1 ,Q1肯定是S,否则不合法) 即,P1P2P3Pk-1 和Q1Q2Q3Qk-1是相等的,但PkQk由此可知两个操作序列在前k-1步操作后输出序列和栈中所剩元素均相同,由于PkPk不妨设PkX,而QkS;这样,在操作序列P1P2P3PiPn中的第k-1步后输出的第一个元素是目前栈中的元素,而对于操作序列Q1Q2Q3QiQn中的第k-1步后输出的第一个元素是目前还在栈外的元素。所以输出序列不同。即两个不同的合法操作序列,不可能得到相同的输出序列。证毕3.6 用反证法证明假设存在这样的输出序列,P1PiPjP kPn ,满足ijk,使PjPkPi ;因Pi在这三个数中最大,且Pi最先出栈,按照题意所给进栈顺序,在Pi出栈时Pj和P k都还在栈中;又因,PjP k ,所以Pj比P k先进栈,则出栈顺序应该是P k先出栈而不是Pj先出栈,矛盾证毕3.10 1 输出序列为0,5,9,12,14,152 由于输入的数据个数不定,采用单链表存储输入的元素,又因是先输入的,后累加到累加器里,所以用链栈的形式存储。(类型定义与书本上第二章相同)void test LinkList L ,P; int x,sum; LNULL; 建立空链表sum0; printfsum; scanfx;读入第一个数 whilex PLinkListmallocsizeofLNode;产生一个结点 P-datax; P-nextL; LP;插入在链头 scanfx;读下一个数 whileL sumsumL-data;取值累加 printfsum;输出 PL-next; freeL; LP; 3.15 所用类型定义如下define Stack_Init_Size 100typedef struct stack SElemType base0,base1,*top0,*top1; int StackSize ; DuSqStack;void InistackDuSqStack iftws.base0 exitOVERFLOW; tws.top0 tws.base0; tws.base1tws.top1tws0.base0 Stack_Init_Size-1; tws.StackSize Stack_Init_Size; InistackStatus Push DuSqStack switchicase 0 *tws.top0x; tws.top0;break;case 1 *tws.top1x; tws.top1;break;return OK; PushStatus Pop DuSqStack x*tws.top0;break;case 1 iftws.base1tws.top1 return ERROR; x*tws.top0;break;return OK; Pop3.17Status judge 判断输入的字符序列是否为型如序列1 初始化栈Scgetchar ;读第一个字符whilec cgetchar ;ifc cgetchar ;读下一个whilec EmptyStacks pops,e; ifce return FALSE; cgetchar ;ifc EmptyStacks return TRUE;return FALSE; judge3.19Status judgedSqList LL为数据元素类型为字符的顺序存储的线性表,表示一个表达式,判断该表达式的括号是否匹配InitStackS;初始化栈Sforj0;jL.length;j switchL.elemj case case case pushS, L.elemj ;break; case case case ifEmptyStackS return FALSE; else PopS,e; switchL.elemj case ife return FALSE;break; case ife return FALSE;break; case ife return FALSE;break; ifEmptyStackS return TRUE;else return FALSE; judged3.24 int gint m,int n 不考虑输入参数的非法性ifm0 n0 return 0;else ifm0 n0 return gm-1,2*nn; g329 类型定义define MAX_Init_Size 100typedef struct QElemType *base; int front,rear ,tag; SqQueue;Status InitQueueSqQueue IfQ.base exitOVERFLOW;G.frontQ.rearQ.tag0;表示队列为空return OK; InitQueueStatus EnQueueSqQueue Q.baseQ.rearx;Q.rearQ.rear1MAX_Init_Size;ifQ.frontQ.rear Q.tag1;尾指针追上头指针return OK; EnQueueStatus DelQueueSqQueue xQ.baseQ.front;Q.front Q.front1 MAX_Init_Size;ifQ.frontQ.rear Q.tag0;头指针追上尾指针return OK;DelQueue3.31Status Ispalindrome 判断输入的字符序列是否为回文,是返回TRUE ,否则返回FALSEInitStackS; 初始化栈SInitQueueQ;初始化一个队列Qcgetchar ;读第一个字符whilec pushS,c; 入栈EnQueueQ,c;入队列cgetchar ;whileEmptyStackS PopS,e; DelQueueQ,c; ifce return FALSE;return TRUE; Ispalindrome3.24 Status gint m,int n,int else ifm0n0 sngm-1,2*n;else return ERROR;return OK;g 3.29 Status EnCyQueueCyQueue Q.baseQ.rearx;Q.rearQ.rear1MAXSIZE;ifQ.frontQ.rear Q.tag1; 队列满EnCyQueue Status DeCyQueueCyQueue Q.frontQ.front1MAXSIZE;xQ.baseQ.front; ifQ.frontQ.rear Q.tag1; 队列空return OK;DeCyQueue分析当循环队列容量较小而队列中每个元素占的空间较多时,此种表示方法可以节约较多的存储空间,较有价值.

    展开全文
  • 数据结构C语言版章节练习题》由会员分享,可在线阅读,更多相关《数据结构C语言版章节练习题(10页珍藏版)》请在人人文库网上搜索。1、数据结构章节练习题第一章 绪 论一、单选题1. 一个数组元素 ai 与 的表示等价...

    《数据结构C语言版章节练习题》由会员分享,可在线阅读,更多相关《数据结构C语言版章节练习题(10页珍藏版)》请在人人文库网上搜索。

    1、数据结构章节练习题第一章 绪 论一、单选题1. 一个数组元素 ai 与 的表示等价。A 、 *(a+i) B 、 a+i C 、 *a+i D 、 &a+i2. 下面程序段的时间复杂度为 。for(int i=0; inext = HL;B 、p-next = HL; HL = p;C 、p-next = HL; p = HL;D 、p-next = HL-next; HL-next = p;5 .在一个单链表 HL中,若要在指针q所指的结点的后面插入一个由指针p所指的结点,则执行。A 、q-next = p-next ; p-next = q;B 、p-next = q-next; q = 。

    2、p;C、q-next = p-next; p-next = q;D、p-next = q-next ; q-next = p;6.在一个单链表 HL中,若要删除由指针q所指向结点的后继结点,则执行。A 、p = q-next ; p-next = q-next;B 、p = q-next ; q-next = p;C、p = q-next ; q-next = p-next;D、q-next = q-next-next; q-next = q;二、填空题1在线性表的单链式存储结构中,每个结点包含有两个域,一个叫域,另一个叫 域。2 在下面数组a中链式存储着一个线性表,表头指针为a0.next,。

    3、则该线性表为 。3. 对于一个长度为 n的顺序存储的线性表,在表头插入元素的时间复杂度为 ,在表尾插入元素的时间复杂度为 。4. 对于一个长度为 n的单链式存储的线性表,在表头插入元素的时间复杂度为 ,在表尾插入元素的时间复杂度为 。5在线性表的顺序存储中,若一个元素的下标为i,则它的前驱元素的下标为 ,后继元素的下标为。6在线性表的单链式存储中,若一个元素所在结点的地址为p,则其后继结点的地址为 若假定p为一个数组a中的下标,则其后继结点的下标为 。7在循环单链表中,最后一个结点的指针指向 结点。8在双向链表中每个结点包含有两个指针域,一个指向其 结点,另一个指向其 结点。9在循环双向链表中。

    4、表头结点的左指针域指向 结点,最后一个结点的右指针域指向 ___结点。10在以 HL 为表头指针的带表头结点的单链表和循环单链表中,链表为空的条件分别为 和 。三、应用题1在下面的每个程序段中,假定线性表La 的类型为 List ,元素类型 ElemType 为 int ,并假定每个程序段是连续执行的,试写出每个程序段执行后所得到的线性表La。(1) InitList(La);int a=48,26,57,34,62,79;for(i=0; i1) 为 15假定一棵二叉树顺序存储在一维数组a 中,但让编号为 1 的结点存入 a0 元素中,让编号 为 2 的结点存入 a1 元素中,其余类推,则编。

    5、号为 i 结点的左孩子结点对应的存储位置为,若编号为 i 结点的存储位置用 j 表示,则其左孩子结点对应的存储位置为 16若对一棵二叉树从 0 开始进行结点编号, 并按此编号把它顺序存储到一维数组 a 中, 即编号为 0 的结点存储到 a0 中,其余类推,则 ai 元素的左孩子元素为 ,右孩子元素为,双亲元素 (i0) 为 。17对于一棵具有 n 个结点的二叉树,对应二叉链表中指针总数为 个,其中 个用于指向孩子结点, 个指针空闲着。18一棵二叉树广义表表示为 a(b(d(,h),c(e,f(g,i(k) ,该树的结点数为 个,深度为 。19假定一棵二叉树广义表表示为a(b(c),d(e,f)。

    6、 ,则对它进行的先序遍历结果为,中序遍历结果为 ,后序遍历结果为 ,按层遍历结果为20假定一棵普通树的广义表表示为 a(b(e),c(f(h,i,j),g),d) ,则先根遍历结果为 ,按层遍历结果为 。二、应用题1已知一棵具有 n 个结点的完全二叉树被顺序存储于一维数组的 A1An 元素中,试编写一 个算法打印出编号为 i 的结点的双亲和所有孩子。2 编写一算法,求岀一棵二叉树中所有结点数和叶子结点数,假定分别用变参C1和C2统计所有结点数和叶子结点数,初值均为0。第六章 二叉树的应用(二)一、单选题1. 从二叉搜索树中查找一个元素时,其时间复杂度大致为 。A、 O(n) B 、 O(1) 。

    7、C 、 O(log2n) D 、 O(n2)2. 向二叉搜索树中插入一个元素时,其时间复杂度大致为 。A 、 O(1)B、 O(log2n )C、 O(n) D、 O(nlog2n)3. 根据 n 个元素建立一棵二叉搜索树时,其时间复杂度大致为 。A 、 O(n)B、 O(log2n )C、 O(n2) D 、 O(nlog2n)4. 从堆中删除一个元素的时间复杂度为 。A 、 O(1) B 、 O(n) C 、 O(log2n) D 、 O(nlog2n)5. 向堆中插入一个元素的时间复杂度为 。A 、 O(log2n) B 、 O(n) C 、 O(1) D 、 O(nlog2n)6. 由。

    8、权值分别为 3,8,6,2,5 的叶子结点生成一棵哈夫曼树,它的带权路径长度为 。A 、 24 B 、 48 C 、 72 D 、 53二、填空题1. 在一棵二叉搜索树中,每个分支结点的左子树上所有结点的值一定该结点的值,右子树上所有结点的值一定 该结点的值。2 对一棵二叉搜索树进行中序遍历时,得到的结点序列是一个。3 从一棵二叉搜索树中查找一个元素时,若元素的值等于根结点的值,则表明,若元素的值小于根结点的值,则继续向 查找,若元素的大于根结点的值,则继续向 查找。4在一个堆的顺序存储中,若一个元素的下标为i,则它的左孩子元素的下标为 ,右孩子元素的下标为 。5. 在一个小根堆中,堆顶结点的。

    9、值是所有结点中的 ,在一个大根堆中,堆顶结点的值是所有结点中的 。6当从一个小根堆中删除一个元素时,需要把 元素填补到 位置,然后再按条件把它逐层 调整。三、应用题1. 已知一组元素为 (46,25,78,62,12,37,70,29) ,画出按元素排列顺序输入生成的一棵二叉搜索 树。2. 空堆开始依次向堆中插入线性表 ( 38,64,52,15,73,40,48,55,26,12)中的每个元素, 请以线性表的形式给出每插入一个元素后堆的状态。3. 已知一个堆为( 12,15,40,38,26,52,48,64 ),若需要从堆中依次删除四个元素,请给出每删 除一个元素后堆的状态。4. 有七个带。

    10、权结点,其权值分别为 3,7,8,2,6,10,14 ,试以它们为叶子结点构造一棵哈夫曼树, 并计算出带权路径长度 WPL。数据结构期末复习练习题答案(仅供参考)第一章 绪 论一、单选题1. A 2. C 3. B 4. C 5. D 6. B二、填空题1. 集合结构、线性结构、树型结构、图形结构 2. 顺序、链式 3. 1:1 、 1:N 、 M:N4. 数据定义、操作声明 5. 引用形参 ( 或指针形参 ) 6. 引用类型 ( 或 指针类型 ) 7. 实参、值 、 、 rand( ) %21 10. sizeof(a)、 a+i*sizeof(a0)、 a+i11. 参数类型、数量、次序 。

    11、12. 2 、用户自定义 13. = = 、ra 、rb 14. O(n) 、 O(m*n)15. n 、 n(n+1)/2 、 O(n2) 16. O(n)第二章 线性表一、单选题1. B 2. A 3. C 4. B 5. D 6. C二、填空题1. 元素值、指针 2.( 38,56,25,60,42,74) 3. O(n)、O(1) 4.(1) 、O(n) 、 i+1p-next 、 ap.next 7. 表头 8. 前驱、后继 9. 表尾、表头10 HL-next = = NULL、 HL-next = = HL三、应用题1.(1) ( 79 , 62 , 34 , 57 , 26 ,。

    12、 48 )(2) ( 26 , 34 , 48 , 57 , 62 , 79 )(3) ( 26, 34 , 39 , 48 , 57 , 62 )212,26,9,8, 15,30,50)3(1) ElemType DMValue( List & L ) if ( ListEmpty(L) ) A 2. B二、填空题1. 行号、列号、元素值 2. 行号、列号 3. 引用 ( 或指针 ) 4. 等于 5. 4 、5 6. 列号、行号7. 单、表 8. 括号 9. 3 10.元素值、子表指针 11. true 、 NULL12234556247142644-3185-726(2)(3) (1,3。

    13、,8),(2,1,4),(2,5,-7),(4,2,-3),(4,4,5), (4,6,6),(6,5, 2),(7,2,1)122444673152465284-7-356212(1) A:长度: 1深度:2 (2) B:长度:3深度: 1(3) C:长度: 2深度: 3(4) D:长度: 2深度:2 (5) E:长度:3深度: 3(6) F:长度: 1深度: 4第四章栈和队列一、单选题1. A 2.B 3. C 4.A 5. B6. B 7. D8. D三、应用题1(1) ( (1,2,4),(2,4,-3),(2,7,1),(3,1,8),(4,4,5),(5,2,-7),(5,6,2)。

    14、,(6,4,6) )、填空题3. 栈顶指针、存储4. 栈顶元素、栈顶指针1. 队尾、队首 2. 后进先出 (LIFO) 、先进先出 (FIFO)5. front = = rear、 (rear+1)%QueueMaxSize = = front 6. -1、 StackMaxSize-17. 栈空、空队、队列只有一个元素 8. 新结点的指针域、栈顶指针 9. 指 针域、栈顶指针10. 队尾指针、存储 = = 0 next = HS、 HS = p 13. HS = HS-next14. ( front = = rear ) & ( front n ) cerr 编号为 i 的结点不存在! en。

    15、dl; exit(1);cout 当前结点为 Aiendl;int j = i/2;C 2. B 3. D 4. C 5. A 6. D、填空题1. 小于、大于等于2. 按升序排列的有序序列3. 找到、左子树、右子树4. 2i+1 、 2i+25. 最小值、最大值6. 堆尾、堆顶、向下三、应用题1.初态:空堆( )插入38 后:( 38 )插入64 后:( 38 , 64 )插入52 后:( 38 , 64 , 52 )插入15 后:( 15 , 38 , 52 , 64 )插入73 后:( 15 , 38 , 52 , 64 , 73 )插入40 后:( 15 , 38 , 40 , 64 。

    16、, 73 , 52 )插入48 后:( 15 , 38 , 40 , 64 , 73 , 52 , 48 )插入55 后:( 15 , 38 , 40 , 55 , 73 ,52 , 48 , 64 )插入26 后:( 15 , 26 , 40 , 38 , 73 ,52 , 48 , 64 ,55 )插入12 后:( 12 , 15 , 40 , 38 , 26 ,52 , 48 , 64 ,55 ,73 )2.删除第 1 个元素后堆 删除第 2 个元素后堆 删除第 3 个元素后堆 删除第 4 个元素后堆3. 初态堆: ( 12 , 15 , 40 , 38 , 26 ,52 , 48 , 64 )( 15 , 26 , 40 , 38 , 64 , 52 , 48 )( 26 , 38 , 40 , 48 , 64 , 52 )( 38 , 48 , 40 , 52 , 64 )( 40 , 48 , 64 , 52 )4. 哈夫曼树:WPL = 3*4+7*3+8*3+2*4+6*3+10*2+14*2 = 131。

    展开全文
  • 数据结构C语言习题详细的答案目录第 1 章 绪论 11.1简述下列术语:数据,数据元素、数据对象、数据结构、存储结构、数据类型和抽象数据类型。 1第2 章 线性表 9第3 章 栈和队列 36第4 章 串 65以下是关于广义表...
  • 李春葆编着数据结构c语言篇――习题与解析修订版李春葆编著:数据结构(C语言篇)――习题与解析(修订版)清华大学出版社答案一、绪论选择1.数据结构是一门研究非数值计算的程序设计问题中计算机的 A 以及它们之间...
  • 数据结构c语言描述耿国华习题及答案 第一章 习题答案 2、 ××√ 3、 (1 )包含改变量定义的最小范围(2)数据抽象、信息隐蔽(3 )数据对象、对象间的关系、一组处理数据的操作(4 )指针类型(5 )集合结构、线性结构、树形...
  • 数据结构章节练习题第一章 绪 论一、单选题1.一个数组元素a[i]与________的表示等价。A、 *(a+i) B、 a+i C、 *a+i D、 &a+i 2.下面程序段的时间复杂度为____________。 for(int i=0; iA、 O(m2) B、 O(n2) C、 ...
  • 数据结构C语言版考研复习第一章 绪论1.1 简述下列概念:数据、数据元素、数据类型、数据结构、逻辑结构、存储结构、线性结构、非线性结构。1. 常用的存储表示方法有哪几种? 1. 算法的时间复杂度仅与问题的规模相关...
  • 第二章 习题与解答一 判断1.线性表的逻辑顺序与存储顺序总是一致的。2.顺序存储的线性表可以按序号随机存取。3.顺序表的插入和删除操作不需要付出很大的时间代价,因为每次操作平均只有近一半的元素需要移动。4...
  • ~~~1. 绪 论1.将下列复杂度由小到大重新排序:A.2nB.n!5nC.n5D.10 000 E.n*log2 (n)【答】10 000< n*log2(n)< n< 2 < n! 2.将下列复杂度由小到大重新排序:A.n*log2(n)40.5B.n + n2 +... n + n...
  • 数据结构C语言版严蔚敏 是《data structures and algorithm analysis in c》一书第2版的简体中译本。原书曾被评为20世纪顶尖的30部计算机著作之一,作者mark allen weiss在数据结构和算法分析方面卓有建树,他的数据...
  • 严蔚敏《数据结构c语言版)习题集》全答案.doc 免费范文网为全国范文类知名网站,下载全文稍作修改便可使用,即刻完成写稿任务。 已有11人下载 百度搜索“77cn”或“免费范文网”即可找到本站免费阅读全部范文。...
  • 1.3 设n是正整数。试写出下列程序段中用记号“△”标注的语句的频度: (2) i=1; k=0; do {△ k+=10*i; i++;}while(i<=n-1) 当n=1时,执行1;当n>=2时,执行n-1次; (3) i=1;... do {△ k+ = 10*i;...
  • 数据结构题集(c语言版)答案及部分代码第十章 内部排序10.23void Insert_Sort1(SqList &L)//监视哨设在高下标端的插入排序算法{k=L.length;for(i=k-1;i;--i) //从后向前逐个插入排序if(L.r[i].key>L.r[i+1]....
  • 数据结构c语言版第2版课后习题答案.doc 数据结构(C语言版)(第2版)课后习题答案李冬梅2015.3I目录第1章绪论1第2章线性表5第3章栈和队列13第4章串、数组和广义表26第5章树和二叉树33第6章图43第7章查找54第8章排序650...
  • 本题库是详解研究生入学考试指定考研参考书目为严蔚敏《数据结构》(C语言版)的专业课复习题库,包括名校考研真题、章节题库和模拟试题三大部分。具体来说包括以下三部分:**部分为名校考研真题。精选七套考研真题,...
  • 数据结构(c语言版)课后习题答案完整版第1章 绪论5.选择:CCBDCA6.试分析下面各程序段的时间复杂度。(1)O(1)(2)O(m*n)(3)O(n2)(4)O(log3n)(5)因为x++共执行了n-1+n-2+……+1= n(n-1)/2,所以执行时间为O(n2)(6)O...
  • 数据结构(C语言版 第2版)》(严蔚敏 著)《数据结构(C语言版 第2版)》(严蔚敏 著)第一章练习题答案第一章练习题答案11第 章 绪论第 章 绪论1.简述下列概念:数据、数据元素、数据项、数据对象、数据结构、逻辑结构...
  • 选择:CCBDCA6.试分析下面各程序段的时间复杂度。(1)O(1)(2)O(m*n)(3)O(n2)(4)O(log3n)(5)因为x++共执行了n-1+n-2+……+1= n(n-1)/2,所以执行时间为O(n2)(6)O()第2章 线性表1.选择babadbcabdcddac2.算法...
  • 数据结构是一门研究非数值计算的程序设计问题中计算机的 操作对象 以及它们之间的 关系 和运算等的学科。2. 数据结构被形式地定义为(D, R),其中D是的有限集合,R是D上的有限集合。3. 数据结构包括数据的 逻辑结构...
  • 哈夫曼编/译码器#include #define MAX 1000#define MAXSYMBS 30#define MAXNODE 59typedef struct{int weight;int flag;int parent;int lchild;}huffnode;typedef struct{int bits[MAXSYMBS];int start;...
  • 严蔚敏版数据结构C语言版)参考答案第一至三章第一章 绪论1.16void print_descending(int x,int y,int z)//按从大到小顺序输出三个数{ scanf("%d,%d,%d",&x,&y,&z); if(xy; //为表示交换的双目运算符,...
  • 清华数据结构习题集答案 (C 语言版严蔚敏 )第 1 章 绪论简述下列术语:数据,数据元素、数据对象、数据结构、存储结构、数据类型和抽象数据类型。解:数据 是对客观事物的符号表示。在计算机科学中是指所有能输入到...
  • 数据结构(C语言版)习题及答案习 一、选择1、一组记录的排序码为(46,79,56,38,40,84),则利用堆排序的方法建立的初始堆为( B )。A、79,46,56,38,40,80 B、84,79,56,38,40,46C、84,79,56,46,40...
  • 第二章 线性表(参考答案) 在以下习题解答中,假定使用如下类型定义: (1)顺序存储结构: #define MAXSIZE 1024 typedef int ElemType;// 实际上,ElemType可以是任意类型 typedef struct { ElemType data[MAXSIZE...
  • #include#include#include#define elemt inttypedef struct qnode{elemt data;struct qnode *next;}node,*nd;typedef struct{nd front;nd rear;}lq;lq InitQueue (void){lq t;t。front=t。rear=(nd )malloc(sizeof...
  • 满意答案pz68322013.04.28采纳率:44%等级:12已帮助:6970人2.【解】int matching(SqList L){//判定顺序表L所保存算术表达式中括号是否匹配,若匹配则返回1,否则返回0InitStack(S); //初始化辅助栈Sfor (i=0;...
  • 数据结构( C语言版) (第2 版) 课后习题答案 李冬梅 2015.3 II 目 录 第 1 章 绪论 1 第 2 章 线性表 5 第 3 章 栈和队列 . 14 第 4 章 串、数组和广义表 . 27 第 5 章 树和二叉树 . 34 第 6 章 图 44 第 7 章 查找 ...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 21,189
精华内容 8,475
关键字:

数据结构c语言练习题

c语言 订阅
数据结构 订阅