数据结构 习题 第五章 多维数组和广义表 (C语言描述)

2024-04-30 05:32

本文主要是介绍数据结构 习题 第五章 多维数组和广义表 (C语言描述),希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

最近在复习数据结构,所以想把平时上课做的习题做个总结,如果大家有遇到这方面的问题就可以参考一下了,废话不多说,直接开始吧。

1、单选题
稀疏矩阵一般的压缩存储方法有两种,即( D)
A. 二维数组和三维数组
B. 三元组表和散列
C. 散列和十字链表
D. 三元组表和十字链表

三元组表:将表示稀疏矩阵的非零元素的三元组表按行优先(或列优先)的顺序(跳过零元素),则得到一个其结点均是三元组的线性表,此线性表的顺序存储结构称为三元组表。
三元组表是稀疏矩阵的一种顺序存储结构。
(当非零元素的位置或个数经常发生变化时,三元组表不适合做稀疏矩阵的存储结构)
此时可采用链表做为存储结构更为恰当,如:十字链表

2、判断题
线性表可以看成是广义表的特例,如果广义表中的每个元素都是原子,则广义表便成为线性表.

正确
广义表(Lists):又称列表,是线性表的推广
线性表的元素仅限于原子项,原子是作为结构上不可分割的成分,它可以是一个数或一个结构,若放松对表元素的这种限制,容许它们具有其自身独立的类型结构,这就产生了广义表。
为了区分原子和广义表,书写时用大写字母表示广义表,小写字母表示原子。
一个表的“深度”是指表展开后所含括号的层数。

3、判断题
广义表是线性表的推广,是一类线性数据结构。

错误
广义表不仅是线性表的推广,也是树的推广。

4、填空题
二维数组A[10][20]采用行序为主方式存储,每一个元素点一个存储单元,且A[0][0]的存储地址是200,则A[6][12]的地址是▁▁▁。

答案(填空1):
332

数组中任一元素A[i][j]的存储位置可用下列公式计算:
LOC( A[i][j] ) = LOC ( A[0][0] ) + ( i×n+j ) × L
这是因为数组元素 A[i][j] 的前面有 i 行,每一行的元素个数为 n,在第 i 行中 A[i][j] 的前面还有 j 个数组元素。L 仍然是每个数据元素所占存储单元的个数。
LOC( A[6][12] )= LOC ( A[0][0] ) + (6*20+12)*1 = 200 + 132 = 332

5、单选题
设矩阵A是一个对称矩阵,为了节省存储空间。将其下三角部分按行序存放在一维数组SA[0…n(n+1)/2-1]中,对任一下三角部分元素aij(i≥j)。在一维数组SA的下标位置k的值是( A)
A. i * ( i + 1 ) / 2 + j
B. j * ( j + 1 ) / 2 + i - 1
C. i * ( i - 1 ) / 2 + j
D. j * ( j - 1 ) / 2 + i - 1

6、填空题
广义表(a,(a,b),d,e,((i,j),k))的长度是▁▁▁,深度是▁▁▁。
答案(填空1):
5
答案(填空2):
3

7、单选题
一个 n * n 的对称矩阵,如果以行或列为主序采用压缩存储,其容量为(B)。
A. ( n + 1 ) * ( n + 1 ) / 2
B. ( n + 1 ) * n / 2
C. n * n
D. n * n / 2

8、填空题
有一个10阶对称矩阵A,采用压缩存储方式(以行序为主存储,且A[0][0]=1)。则A[8][5]的地址是▁▁▁。
答案(填空1):
42

(1+8)*8/2+5+1=42

9、单选题
N是一个5×8的二维数组,当N按行优先方式存储时,表示该数组的第10个元素的是(B )
A. N[2][2]
B. N[1][1]
C. N[1][2]
D. N[2][1]

1*8+1=9,N[1][1] 前面有九个元素,它是第十个元素。
下面补充一些关于对称矩阵的内容:

  • 对于一个n阶对称矩阵,第i行(0≤i<n)只需要存储i+1个元素,元素总数为:
    ∑ i = 0 n − 1 ( i + 1 ) = n ( n + 1 ) / 2 \sum_{i=0}^{n-1}(i+1)=\mathrm{n}(\mathrm{n}+1) / 2 i=0n1(i+1)=n(n+1)/2
  • 若i≥j,则A[i][j]在下三角矩阵中,A[i][j] 之前的i行一共有1+2+…+ i =i×(i+1)/2个元素,在第i行上,A[i][j] 之前有j个元素,因此有:
    k=i×(i+1)/2+j
  • 若i<j,则A[i][j]在上三角矩阵中。因为A[i][j] = A[j][i] ,所以只要交换上述对应关系式中的i和j即可得到:
    k=j×(j+1)/2+i
  • 若令I=max(i,j),J=min(i,j),得到:k=I×(I+1)/2+J (0≤k<n×(n+1)/2 )
    因此:
    LOC( A[i][j] ) = LOC( SA[k] ) = LOC( SA[0] ) + k×d
    = LOC(SA[0])+[I×(I+1)/2+J] ×d
  1. 设有一个10阶的对称矩阵A,采用压缩存储方式,以行序为主存储,a11为第一元素,其存储地址为8,每个元素占一个地址空间,则a54的地址为( 21

注意,这题是a11为第一元素,而不是a00为第一元素,所以:
4*(4+1)/ 2 + 3 + 8 = 21

  1. 设有一个10阶的对称矩阵A,采用压缩存储方式,以行序为主存储,a00为第一元素,其存储地址为8,每个元素占一个地址空间,则a45的地址为( 27

这里a45是所在位置是上三角矩阵,所以为了方便运算,我们要把它转化为下三角矩阵,转化方法请看上面。
所以变成下三角矩阵以后,使用a54 进行计算:
5*(5+1)/ 2 + 4 + 8 = 15 + 4 + 8 =27

  • 补充:

  • L 表示 每个数据元素所占存储单元的个数。

  • 一维数组中任一元素 A[i] 的存储位置为:
    LOC( A[i] )= LOC (A [0]) + i * L (从0下标开始)
    LOC( A[i] )= LOC (A [1]) + ( i - 1 ) * L (从1下标开始)

  • 二维数组 A[m][n]:
    以行序为主序: LOC( A[i][j] )= LOC (A [0][0]) + ( i * n + j ) * L
    以列序为主序: LOC( A[i][j] )= LOC (A [0][0]) + ( j * m + i ) * L

我把我目前写的关于数据结构 题目的链接全部汇总整理在下面,有需要的小伙伴自己点击哈。

  • 数据结构 习题 第一章 概论
  • 数据结构 习题 第二章 线性表 (C语言描述)
  • 数据结构 习题 第三章 栈和队列 (C语言描述)
  • 数据结构 习题 第四章 串 (C语言描述)
  • 数据结构 习题 第五章 多维数组和广义表(C语言描述)
  • 数据结构 习题 综合复习

实验:

  • 数据结构 实验一 顺序表的操作
  • 数据结构 实验二 链表的基本操作
  • 数据结构 实验三 栈的基本运算
  • 数据结构 实验四 二叉树的操作
  • 数据结构实验五-马踏棋盘
  • 数据结构-顺序表的排序操作-冒泡排序

因为最近还在准备别的考试,所以目前就先更新这么多哈,后面有时间的话,还会再写一篇关于数据结构实验的题目,欢迎大家关注呦!

如果大家觉得对你们有帮助的话,可以点个赞再走吗,嘿嘿。
笔者使用的教材是高等教育出版社唐策善、李龙澍、黄刘生编著的《数据结构——用C语言描述》。
因为都是我自己打字,或者我的答案,可能会有错误的地方,如果有的话,欢迎大家指出。

这篇关于数据结构 习题 第五章 多维数组和广义表 (C语言描述)的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/948022

相关文章

C语言中的数据类型强制转换

《C语言中的数据类型强制转换》:本文主要介绍C语言中的数据类型强制转换方式,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录C语言数据类型强制转换自动转换强制转换类型总结C语言数据类型强制转换强制类型转换:是通过类型转换运算来实现的,主要的数据类型转换分为自动转换

利用Go语言开发文件操作工具轻松处理所有文件

《利用Go语言开发文件操作工具轻松处理所有文件》在后端开发中,文件操作是一个非常常见但又容易出错的场景,本文小编要向大家介绍一个强大的Go语言文件操作工具库,它能帮你轻松处理各种文件操作场景... 目录为什么需要这个工具?核心功能详解1. 文件/目录存javascript在性检查2. 批量创建目录3. 文件

C语言实现两个变量值交换的三种方式

《C语言实现两个变量值交换的三种方式》两个变量值的交换是编程中最常见的问题之一,以下将介绍三种变量的交换方式,其中第一种方式是最常用也是最实用的,后两种方式一般只在特殊限制下使用,需要的朋友可以参考下... 目录1.使用临时变量(推荐)2.相加和相减的方式(值较大时可能丢失数据)3.按位异或运算1.使用临时

使用C语言实现交换整数的奇数位和偶数位

《使用C语言实现交换整数的奇数位和偶数位》在C语言中,要交换一个整数的二进制位中的奇数位和偶数位,重点需要理解位操作,当我们谈论二进制位的奇数位和偶数位时,我们是指从右到左数的位置,本文给大家介绍了使... 目录一、问题描述二、解决思路三、函数实现四、宏实现五、总结一、问题描述使用C语言代码实现:将一个整

C++原地删除有序数组重复项的N种方法

《C++原地删除有序数组重复项的N种方法》给定一个排序数组,你需要在原地删除重复出现的元素,使得每个元素只出现一次,返回移除后数组的新长度,不要使用额外的数组空间,你必须在原地修改输入数组并在使用O(... 目录一、问题二、问题分析三、算法实现四、问题变体:最多保留两次五、分析和代码实现5.1、问题分析5.

C语言字符函数和字符串函数示例详解

《C语言字符函数和字符串函数示例详解》本文详细介绍了C语言中字符分类函数、字符转换函数及字符串操作函数的使用方法,并通过示例代码展示了如何实现这些功能,通过这些内容,读者可以深入理解并掌握C语言中的字... 目录一、字符分类函数二、字符转换函数三、strlen的使用和模拟实现3.1strlen函数3.2st

Go语言中最便捷的http请求包resty的使用详解

《Go语言中最便捷的http请求包resty的使用详解》go语言虽然自身就有net/http包,但是说实话用起来没那么好用,resty包是go语言中一个非常受欢迎的http请求处理包,下面我们一起来学... 目录安装一、一个简单的get二、带查询参数三、设置请求头、body四、设置表单数据五、处理响应六、超

C语言中的浮点数存储详解

《C语言中的浮点数存储详解》:本文主要介绍C语言中的浮点数存储详解,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录1、首先明确一个概念2、接下来,讲解C语言中浮点型数存储的规则2.1、可以将上述公式分为两部分来看2.2、问:十进制小数0.5该如何存储?2.3 浮点

Java中数组转换为列表的两种实现方式(超简单)

《Java中数组转换为列表的两种实现方式(超简单)》本文介绍了在Java中将数组转换为列表的两种常见方法使用Arrays.asList和Java8的StreamAPI,Arrays.asList方法简... 目录1. 使用Java Collections框架(Arrays.asList)1.1 示例代码1.

基于Python实现多语言朗读与单词选择测验

《基于Python实现多语言朗读与单词选择测验》在数字化教育日益普及的今天,开发一款能够支持多语言朗读和单词选择测验的程序,对于语言学习者来说无疑是一个巨大的福音,下面我们就来用Python实现一个这... 目录一、项目概述二、环境准备三、实现朗读功能四、实现单词选择测验五、创建图形用户界面六、运行程序七、