作业1-数据结构的基本概念及顺序表基本操作

怼烎@ 2022-12-24 13:56 192阅读 0赞

1-1  
若用链表来表示一个线性表，则表中元素的地址一定是连续的。(F)

1-2  
数据的逻辑结构是指数据的各数据项之间的逻辑关系。(F)  
\[解析\]逻辑结构就是数据元素之间的逻辑关系  
而不是数据元素内部的数据项之间的关系

1-3  
抽象数据类型中基本操作的定义与具体实现有关。(F)  
\[解析\]抽象数据类型的定义不涉及到存储结构以及具体实现

2-1

数据的()包括集合、线性结构、树形结构和图形结构四种基本类型。(B)  
A.存储结构  
B.逻辑结构  
C.基本运算  
D.算法描述  
\[解析\]存储结构指在内存中的存储方式,包括连续存储和离散存储  
逻辑结构指数据元素之间的逻辑关系,包括集合,线性结构,树,图形

2-2  
数据在计算机内存中的表示是指(A)  
A.数据的存储结构  
B.数据结构  
C.数据的逻辑结构  
D.数据元素之间的关系

2-3  
下列关于数据的逻辑结构的叙述中，()是正确的。(A)  
A.数据的逻辑结构是数据元素间关系的描述  
B.数据的逻辑结构反映了数据在计算机中的存储方式  
C.数据的逻辑结构分为顺序结构和链式结构  
D.数据的逻辑结构分为静态结构和动态结构

2-4  
数据结构是一门研究非数值计算的程序设计问题中计算机的()  
以及它们之间的关系和运算等的学科。(A)  
A.操作对象  
B.计算方法  
C.逻辑存储  
D.数据映象

2-5  
在数据结构中，与所使用的计算机无关的数据结构是()。(A)  
A.逻辑结构  
B.存储结构  
C.逻辑结构和存储结构  
D.物理结构  
\[解析\]存储结构和物理结构应该都是指逻辑结构在内存的实现方式  
两个名词分别在逻辑角度和物理角度对同一现象进行描述

2-6  
在决定选取何种存储结构时，一般不考虑()。(A)  
A.各结点的值如何  
B.结点个数的多少  
C.对数据有哪些运算  
D.所用编程语言实现这种结构是否方便  
\[解析\]  
存储结构:数据的逻辑结构在计算机中的表示  
包括顺序存储结构和链式存储结构

结点的个数对存储结构的影响我没有想到例子  
对数据有哪些运算,比如对线性表插入删除操作  
链式结构就比顺序结构更方便  
有的语言没有指针,链式存储结构实现起来比较复杂

2-7  
线性结构中元素之间存在()关系。(A)  
A.一对一  
B.一对多  
C.多对多  
D.多对一

2-8  
树形结构中元素之间存在()关系。(B)  
A.一对一  
B.一对多  
C.多对多  
D.多对一

2-9  
图形结构中元素之间存在()关系。©  
A.一对一  
B.一对多  
C.多对多  
D.多对一  
\[解析\]个人感觉,图的元素之间其实还是一对多的结构.  
怎么来解释多对多?

2-10  
从物理存储上可以把数据结构分为(B)  
A.动态结构、静态结构  
B.顺序结构、链式结构  
C.线性结构、树形结构、图形结构和集合结构  
D.基本结构、构造型结构

2-11  
在数据结构中，从逻辑上可以把数据结构分成()。©  
A.动态结构和静态结构  
B.紧凑结构和非紧凑结构  
C.线性结构和非线性结构  
D.内部结构和外部结构

2-12  
与数据元素本身的形式、内容、相对位置、个数无关的是数据的()。©  
A.存储结构  
B.存储实现  
C.逻辑结构  
D.运算实现  
\[解析\]逻辑结构是抽象概念与具体对象无关

2-13  
通常要求同一逻辑结构中的所有数据元素具有相同的特性，这意味着()。(B)  
A.数据在同一范围内取值  
B.不仅数据元素所包含的数据项的个数要相同，  
而且对应数据项的类型要一致  
C.每个数据元素都一样  
D.数据元素所包含的数据项的个数要相等

2-14  
算法的时间复杂度取决于()。(D)  
A.问题的规模  
B.待处理数据的初态  
C.计算机的配置  
D.A和B  
\[解析\]B不知道

2-15  
以下数据结构中，是非线性数据结构。(A)  
A.树  
B.字符串  
C.队列  
D.栈

2-16  
以下说法正确的是()。(D)  
A.数据元素是数据的最小单位  
B.数据项是数据的基本单位  
C.数据结构是带有结构的各数据项的集合  
D.一些表面上很不相同的数据可以有相同的逻辑结构  
\[解析\]数据项是数据的最小单位,数据元素是基本数据单位  
数据结构是带有结构的各数据元素的集合

2-17  
数据的基本单位是(). (A)  
A.数据元素  
B.文件  
C.数据项  
D.数据结构

2-18  
计算机算法指的是(). ( C)  
A.计算方法  
B.排序方法  
C.解决问题的有限运算序列  
D.调度方法

2-19  
在存储数据时，通常不仅要存储各数据元素的值，而且还要存储()。( C)  
A.数据的处理方法  
B.数据元素的类型  
C.数据元素之间的关系  
D.数据的存储方法

2-20  
(neuDS)链式存储设计时，各结点间的存储单元的地址()。()  
A.一定连续  
B.一定不连续  
C.不一定连续  
D.部分连续，部分不连续  
\[解析\]万一巧了呢,有两个或多个内存块是连续的.别问,问就是玄学

6-2 顺序表基本操作 (10分)
    
    //库函数头文件包含
    #include<stdio.h>
    #include<malloc.h>
    #include<stdlib.h>
    #include <iostream>
    using namespace std;
    
    //函数状态码定义
    #define TRUE        1
    #define FALSE       0
    #define OK          1
    #define ERROR       0
    #define INFEASIBLE -1
    #define OVERFLOW   -2
    
    typedef int  Status;
    
    //顺序表的存储结构定义
    #define LIST_INIT_SIZE  100
    #define LISTINCREMENT   10
    typedef int ElemType;  //假设线性表中的元素均为整型
    typedef struct{
        
        ElemType* elem;   //存储空间基地址
        int length;       //表中元素的个数
        int listsize;     //表容量大小
    }SqList;    //顺序表类型定义
    
    Status ListInsert_Sq(SqList &L, int pos, ElemType e)
    {
        
    	//扩容
    	if (L.length == L.listsize)
    	{
        
    		L.elem = (LNode*)realloc(sizeof(ElemType) * (L.listsize + LISTINCREMENT));
    		if (L.elem == NULL) exit(OVERFLOW);
    		L.listsize += LISTINCREMENT;
    	}
    	//pos合法性
    	if (pos <= 0 || pos >= L.length + 2) return ERROR;
    	//后移
    	for (i = L.length - 1; i >= pos - 1; i--)
    	{
        
    		L.elem[i + 1] = L.elem[i];
    	}
    	L.elem[pos - 1] = e;
    	L.length++;
    	return OK;
    }
    
    Status ListDelete_Sq(SqList &L, int pos, ElemType &e)
    {
        
    	//pos合法性
    	if (pos <= 0 || pos >= L.length + 1) return ERROR;
    	//保存要删除的值
    	e = L.elem[pos - 1];
    	//前移
    	for (int i = (pos - 1) + 1; i <= L.length - 1; i++)
    	{
        
    		L.elem[i - 1] = L.elem[i];
    	}
    	L.length--;
    	return OK;
    }
    int ListLocate_Sq(SqList L, ElemType e)
    {
        
    	for (int i = 1; i <= L.length; i++)		
    	{
        
    		if (L.elem[i-1] == e)
    			return i;
    	}
    	return 0;
    }
    
    void ListPrint_Sq(SqList L)
    {
        
    	for (int i = 0; i < L.length; i++)
    	{
        
    		if (i) cout << ' ';
    		cout << L.elem[i];
    	}
    	cout << endl;
    }
    
    //结构初始化与销毁操作
    Status InitList_Sq(SqList &L){
        
      //初始化L为一个空的有序顺序表
        L.elem=(ElemType *)malloc(LIST_INIT_SIZE*sizeof(ElemType));
        if(!L.elem)exit(OVERFLOW);
        L.listsize=LIST_INIT_SIZE;
        L.length=0;
        return OK;
    }
    
    int main() {
        
        SqList L;
    
        if(InitList_Sq(L)!= OK) {
        
            printf("InitList_Sq: 初始化失败！！！\n");
            return -1;
        }
    
        for(int i = 1; i <= 10; ++ i)
            ListInsert_Sq(L, i, i);
    
        int operationNumber;  //操作次数
        scanf("%d", &operationNumber);
    
        while(operationNumber != 0) {
        
            int operationType;  //操作种类
            scanf("%d", & operationType);
    
            if(operationType == 1) {
          //增加操作
                int pos, elem;
                scanf("%d%d", &pos, &elem);
                ListInsert_Sq(L, pos, elem);
            } else if(operationType == 2) {
          //删除操作
                 int pos; ElemType elem;
                 scanf("%d", &pos);
                 ListDelete_Sq(L, pos, elem);
                 printf("%d\n", elem);
            } else if(operationType == 3) {
          //查找定位操作
                ElemType elem;
                scanf("%d", &elem);
                int pos = ListLocate_Sq(L, elem);
                if(pos >= 1 && pos <= L.length)
                    printf("%d\n", pos);
                else
                    printf("NOT FIND!\n");
            } else if(operationType == 4) {
          //输出操作
                ListPrint_Sq(L);
            }
           operationNumber--;
        }
        return 0;
    }
    
    /* 请在这里填写答案 */