数据结构(期末总复习)

这篇具有很好参考价值的文章主要介绍了数据结构(期末总复习)。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

目录

第一章 绪论

第二章 线性表

线性表常用操作辨析总结

第三章 栈和队列

第四章 串

第五章 数组与广义表

第六章 树


第一章 绪论

1.结构体成员的类型必须是基本数据类型。(F)

原因:结构体成员类型不只是基本数据类型,同时也可以是另一种结构体类型,也可以是指针类型,同时也可以为数组。(数组,结构体,共用体,枚举,指针都可以为成员,但是他们都不是基本数据类型)

而基本数据类型是指int,double等

2.数据元素是数据的最小单位。(F)

原因:数据元素是数据的基本单位,数据项是数据的最小单位

3.数据的逻辑结构是指数据的各数据项之间的逻辑关系。(F)

原因:数据的逻辑结构是指数据元素之间的关系,而不是数据内部的各数据项之间的关系。

结构体成员的类型必须是基本数据类型,C语言,数据结构

4. 数据的逻辑结构说明数据元素之间的顺序关系,它依赖于计算机的存储结构。(F) 

原因:数据的逻辑结构,是数据之间的关系,和存储结构即物理结构之间没有直接的关系

第二章 线性表

5.线性表中的所有数据元素的数据类型必须相同。(T)

原因:线性表中所有元素具有相同性质,在设计存储结构时,它们对应的数据类型也必然相同。

数据类型:是一个值的集合和定义在该值上的一组操作的总称

6.可以用带表头附加结点的链表表示线性表,也可以用不带头结点的链表表示线性表,前者最主要的好处是(B)。

A.可以加快对表的遍历

B.使空表和非空表的处理统一

C.节省存储空间

D.可以提高存取表元素的速度

 7.下面哪个不是线性表(D)

A.循环链表

B.队列

C.双向链表

D.关联数组

解析:关联数组(Associative Array),又称映射(Map)、字典( Dictionary)是一个抽象的数据结构,它包含着类似于(键,值)的有序对。 不是线性表

线性表常用操作辨析总结

8.某线性表中最常用的操作是在最后一个元素之后插入一个元素和删除第一个元素,则采用什么存储方式最节省运算时间?(B)

A.单链表  B.仅有尾指针的单循环链表  C.仅有头指针的单循环链表  D.双链表

结构体成员的类型必须是基本数据类型,C语言,数据结构

解析: 链表特点,插入删除方便,修改指针即可。但注意,在最后一个元素插入删除,有顺序表就选顺序表,没有顺序表,选链表就选带尾指针的,因为链表也需要从头结点遍历到尾节点,因此带尾指针的单循环链表最省时间。

9.若某线性表最常用的操作是存取任一指定序号的元素和在表尾进行插入和删除运算,则利用( A)存储方式最节省时间。

  A.顺序表               B.双向链表        C.带头结点的双向循环链表       D.单循环链表

 解析:题目中说,存取任一指定序号的元素。注意顺序表的特性,随机存取。另外在表尾删除,顺序表最后一个元素删除不需要移动元素。

10.设一个链表最常用的操作是在末尾插入结点和删除尾结点,则选用(  D  )最节省时间。

  A. 单链表              B.单循环链表     C. 带尾指针的单循环链表   D. 带头结点的双循环链表

结构体成员的类型必须是基本数据类型,C语言,数据结构

解析:链表操作,末尾插入删除,选择带尾指针的单循环链表的话,插入操作得遍历一遍;选择带头结点的双循环链表,前后都能到达,时间复杂度O(1). 

填空:


#include <stdio.h>
#include <malloc.h>
typedef struct node
{
     int data;
     struct node *next;
}Snode,*ptr;

void insert(ptr h,int x)//将x插入在表头位置,即监督元之后
{
    ptr p;
    p=(ptr)malloc(sizeof(Snode));
    p->data=x;
    
    p->next=h->next;
    h->next=p;
}

void output(ptr h)//输出链表中的元素,即输出除监督元以外的所有元素
{
    ptr p;
    p=h->next;
    while(p!=NULL)
    {
        printf("%d ",p->data);
        p=p->next;
    }
    printf("\n");
}

void del(ptr h)//删除表头元素,即监督元后第一个元素结点
{
    ptr p;
    p=h->next;
    h->next=p->next;
    free(p);
}    
    
int main()
{
    ptr head;
    int x;
    head=(ptr)malloc(sizeof(Snode));
    head->next=NULL;
    scanf("%d",&x);
    while(x!=0)
    {
        insert(head,x);
        scanf("%d",&x);
    }
    output(head);
    del(head);
    output(head);
    return 0; 
}

11.在下列关于线性表的叙述中正确的是(D)。

A.线性表的逻辑顺序与物理顺序总是一致的

B.线性表的顺序存储表示优于链式存储表示

C.线性表若采用链式存储表示时所有存储单元的地址可连续可不连续

D.除数组外,每种数据结构都应具备3种基本运算:插入、删除和査找

第三章 栈和队列

12.令P代表入栈,O代表出栈。若利用堆栈将中缀表达式3*2+8/4转为后缀表达式,则相应的堆栈操作序列是:C

A.PPPOOO  B.POPOPO  C.POPPOO  D.PPOOPO

解析:将中缀表达式转换为后缀表达式的过程如下:(1)如果遇到空格,则认为是分隔符,不需要处理。(2)若遇到运算数,则直接输出(3)若是左括号,则将其压入栈中。(4)若遇到右括号,表明括号内的中极表达式已经扫描完毕,将栈顶的元素弹出并输出,直到遇到左括号为(5)若遇到的是运算符,该运算符的优先级大于栈顶运算符的优先级时,则把它压入栈中;该运算符的优先级小于等于栈顶运算符时,则将栈顶运算符弹出并输出。

所以该题,一开始遇到‘*’,先将‘*’入栈,遇到‘+’,弹出栈顶运算符,遇到‘/’,将‘/’入栈,然后再出栈所以是POPPOO

13、若采用带头、尾指针的单向链表表示一个堆栈,那么该堆栈的栈顶指针top应该如何设置?A

A.将链表头设为top

B.将链表尾设为top

C.随便哪端作为top都可以

D.链表头、尾都不适合作为top

解析:因为是单向链表,如果表尾设为top,每次删除都是O(N)的时间复杂度,而表头设为top就是O(1)。

第四章 串

14.Among the following assignments or initializations, A__ is wrong.

A.char str[10]; str="string";

B.char str[]="string";

C.char *p="string";

D.char *p; p="string";

解析:str是一个指针常量,它是不能被赋值的也不能进行自增自减的!char *p;是定义的一个指针变量,它指向一个字符型数据,它是可以被赋值的。指针变量和普通变量是一个道理的,不同的只是指针变量存放的是地址,而普通变量存放的是数值或字符等。

 15.假设scanf语句执行时输入ABCDE<回车>,能使puts(s)语句正确输出ABCDE字符串的程序段是( D)。

A.char s[5]={“ABCDE”}; puts(s);
B.char s[5]={‘A’, ‘B’, ‘C’, ‘D’, ‘E’}; puts(s);
C.char *s; scanf("%s", s); puts(s);
D.char *s; s=“ABCDE”; puts(s);

解析:要正常输出ABCDE必须在字符串的末尾有’\0’作为结束,这样输出函数才知道什么时候终止。
A选项中字符串数组大小为5只能放ABCDE,放不下’\0’了。如果大小为6,会自动在后面补’\0’
B选项与A一样,放不下’\0’
C选项,楼主要知道,字符串读入进来是要存起来的,而s只是个指针,存不下这么多字符。必须是char s[6];scanf("%s",s);puts(s);
D选项是正确的,"ABCDE"作为静态常量存储于程序段,地址赋给s,可以正常输出。

16.若串S="software",其子串的数目是(B)

A.8   B.37  C.36  D.9

长为0的子串:1
长为1的子串:8
长为2的子串:7
长为3的子串:6
长为4的子串:5
长为5的子串:4
长为6的子串:3
长为7的子串:2
长为8的子串:1
    总和为37

17.串的长度是指( B)

A.串中所含不同字母的个数

B.串中所含字符的个数

C.串中所含不同字符的个数

D.串中所含非空格字符的个数

解释:串中字符的数目称为串的长度。

第五章 数组与广义表

18.一个广义表为 ( a, (b, c), d, (), ((f, g), h) ),则该广义表的长度与深度分别为(D)。

A.4和6    B.6和3  C.3和5  D.5和3

解析:长度为5:a,(b,c),d,(),((f,g),h))。深度为3:所含括号的层数

19.数组A[0..4,-1..-3,5..7]中含有元素的个数(B )。

A.55  B.45  C.36  D.16

解析:三维数组,0——4,共5页,-1——-3,3行,5——7列,共5*3*3=45个元素

20.设二维数组A[1… m,1… n]按行存储在数组B中,则二维数组元素A[i,j]在一维数组B[1…m*n]中的下标为 ( A)。

A.n*(i-1)+j  B.n*(i-1)+j-1  C.i*(j-1)  D.j*m+i-1

解析:计算前i一1行的个数,每行有n列,所以个数为(i一1)×n,再加上第i行的j个元素,就像A[2,3],先求出第二行之前,也就是第一行有多少个数,再加上第二行的第三个就是自己的下标了。

21.已知一个长度为16的顺序表L,其元素按关键字有序排列。若采用二分查找法查找一个L中不存在的元素,则关键字的比较次数最多是:

A.4  B.5  C.6  D.7
解析:二分查找的最大比较次数是 
结构体成员的类型必须是基本数据类型,C语言,数据结构
即[log(N)](向下取整)+1=4+1=5
文章来源地址https://www.toymoban.com/news/detail-772347.html

第六章 树

//创建二叉排序树
#include<iostream>
using namespace std;

typedef struct ElemType{    
    int key;
}ElemType;
int flag=1;

typedef struct BSTNode{
    ElemType data;
    BSTNode *lchild,*rchild;
}BSTNode,*BSTree;

void InsertBST(BSTree &T,ElemType e ) {
  if(!T) { 
    BSTree S = new BSTNode; 
    S->data =e; 
    S->lchild = S->rchild = NULL;
    T=S;//填空
  }
  else if (e.key< T->data.key) 
    InsertBST(T->lchild,e);//填空
  else if (e.key> T->data.key) 
   InsertBST(T->rchild,e);//填空
}

void CreateBST(BSTree &T ) {
  int i=1,n;
  cin >> n;
  T=NULL;
  ElemType e;
  while(i<=n){
    cin>>e.key;      
    InsertBST(T, e);
    i++;
  }            
}

void InOrderTraverse(BSTree &T)
{
    if(T)
    {
    InOrderTraverse(T->lchild);
    if(flag){cout<<T->data.key;flag=0;}
    else cout<<" "<<T->data.key;
    InOrderTraverse(T->rchild);
    }
}

int main()
{
    BSTree T;
    CreateBST(T);
    InOrderTraverse(T);
    return 0;
}

到了这里,关于数据结构(期末总复习)的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 数据结构笔记(c++版,期末复习)

      目录 一、绪论 1.数据结构基本概念 2.算法定义与特征 二、线性表 1.线性表的定义 2.顺序表的存储结构 3.链式存储结构 三、栈和队列 1、栈的基本概念 2.队列的基本概念 3.循环队列  四、字符串和多维数组 1.字符串的基本概念 2.串的简单模式匹配 3.多维数组 3.1数组的定义

    2024年02月12日
    浏览(49)
  • 【数据结构】——期末复习题题库(1)

    🎃个人专栏: 🐬 算法设计与分析:算法设计与分析_IT闫的博客-CSDN博客 🐳Java基础:Java基础_IT闫的博客-CSDN博客 🐋c语言:c语言_IT闫的博客-CSDN博客 🐟MySQL:数据结构_IT闫的博客-CSDN博客 🐠数据结构:​​​​​​数据结构_IT闫的博客-CSDN博客 💎C++:C++_IT闫的博客-CSDN博

    2024年02月03日
    浏览(56)
  • 【数据结构】——期末复习题题库(4)

    🎃个人专栏: 🐬 算法设计与分析:算法设计与分析_IT闫的博客-CSDN博客 🐳Java基础:Java基础_IT闫的博客-CSDN博客 🐋c语言:c语言_IT闫的博客-CSDN博客 🐟MySQL:数据结构_IT闫的博客-CSDN博客 🐠数据结构:​​​​​​数据结构_IT闫的博客-CSDN博客 💎C++:C++_IT闫的博客-CSDN博

    2024年02月02日
    浏览(77)
  • 数据结构(期末复习篇) 清华大学出版社

    1.1.1 数据结构的定义 数据:描述客观事物的数和字符的集合 数据元素: 数据的基本单位 数据对象: 性质相同的数据元素的集合,是数据的一个子集 数据结构: 数据元素以及数据元素之间的关系,可以看作互相之间有着特定关系的集合 1.1.2 逻辑结构 1.逻辑结构的表示 一 

    2024年01月20日
    浏览(49)
  • 【数据结构与算法】第七章-图【期末复习】

    图:有向图、网,无向图、网。 顶点 边:有向图图称作弧,分弧头弧尾。 依附:边依附点,边和点关联 邻接:点邻接点 度:点关联的边的数目 完全图: 无向: C n 2 C_n^2 C n 2 ​ 条边; 有向: 2 C n 2 2C_n^2 2 C n 2 ​ 条边 连通:若干结点互相可以通信,用手提起一个结点可以顺

    2024年02月01日
    浏览(58)
  • 数据结构与算法期末复习——知识点+题库

    (1)数据:所有能被计算机识别、存储和处理的符号的集合(包括数字、字符、声音、图像等信息 )。 (2)数据元素:是数据的基本单位,具有完整确定的实际意义。在计算机程序中通常作为一个整体进行考虑和处理。一个数据元素可由若干个数据项组成。 (3)数据项:构成数据元

    2024年02月12日
    浏览(53)
  • 数据结构期末复习(4)串 树和二叉树

    在数据结构中,串是由零个或多个字符组成的有限序列。它是一种线性数据结构,常用于表示和处理文本、字符串等信息。 串的特点包括: 顺序性:串中的字符按照一定的先后顺序排列,每个字符都有一个唯一的位置。 有限性:串的长度是有限的,它由字符的个数决定。

    2024年01月17日
    浏览(46)
  • 期末复习(3)C语言数据结构_图论基础

    目录 导言:  定义: 一、边和度的概念: 1.1 无向图中的边和度: 1.2 有向图中的边和度: 1.3 度序列和握手定理: 二、弧和度的关系: 2.1 有向图中的弧和度: 2.2 度序列和握手定理在有向图中的应用: 2.3 邻接矩阵和邻接表在有向图中的表示: 2.4 强连通图: 三、完全图:

    2024年02月03日
    浏览(41)
  • 【Python数据结构与算法】—— 搜索算法 | 期末复习不挂科系列

    ​ 🌈个人主页:  Aileen_0v0 🔥系列专栏:  数据结构与算法 💫个人格言: \\\"没有罗马,那就自己创造罗马~\\\" 这篇博客主要探索的是计算机科学常见问题---搜索算法 “时间紧,任务重!” 话不多说,开始今天的学习之旅吧⛵~ 目录 搜索 定义 -in 顺序搜索  无序表的顺序搜索

    2024年02月05日
    浏览(49)
  • 数据结构期末复习(1)学科定义、组成、算法的定义、时间复杂度比较

    目录 数据结构的几个方面 逻辑结构的描述 逻辑结构 存储结构 数据运算 数据结构和数据类型 数据类型 抽象数据类型(ADT) 算法及其描述 什么是算法 算法分析 算法的设计目标 算法时间性能分析 计算算法频度 算法时间复杂度 简化的算法时间复杂度分析 数据结构学科定义:

    2024年02月03日
    浏览(42)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包