数据结构绪论、顺序表课后练习题

柔光的暖阳◎ 2024-03-31 08:30 117阅读 0赞

#### 文章目录 ####

*  第1章 绪论
 *   *  一 填空题
     *  二 选择题
     *  三 判断题✅❎
 *  第2章 线性表
 *   *  一 判断正误
     *  二 单项选择题
     *  三 简答题

## 第1章 绪论 ##

### 一 填空题 ###

1.  数据结构被形式地定义为（D, R），其中D是***数据元素***的有限集合，R是D上的***关系***有限集合。
2.  数据结构按逻辑结构可分为两大类，它们分别是***线性结构和非线性结构***。
3.  线性结构中元素之间存在***一对一***关系，树形结构中元素之间存在***一对多***关系，图形结构中元素之间存在***多对多***关系。
4.  数据的存储结构可用四种基本的存储方法表示，它们分别是***顺序存储结构、链式存储结构、索引、散列。***
5.  一个算法的效率可分为 ***时间效率和空间效率***。
6.  数据结构是研讨数据的***逻辑结构和物理/存储结构***，以及它们之间的相互关系，并对与这种结构定义相应的***操作/算法***，设计出相应的***算法***。
7.  下面程序段中带下划线的语句的执行次数的数量级是( n log ⁡ 2 n n \\log\_2 n nlog2n)。

int i=1;
    while (i<n){
        
    	for (int j=1;j<=n;j++){
        
    		x=x+1;
    	}
    	i=i*2;
    }

1.  设有数据结构(D, R)，其中 D=\{d1, d2, d3, d4\} R=\{r\}， r=\{（d1, d2）（d2, d3）（d3, d4）\} ,则数据结构D是***线性的数据结构。***

### 二 选择题 ###

1.  连续存储设计时，存储单元的地址（ ）。  
    ***A. 一定连续***  
    B．一定不连续  
    C．不一定连续  
    D．部分连续，部分不连续
2.  数据结构中，与所使用的计算机无关的是数据的 结构.  
    A) 存储  
    B) 物理  
    ***C) 逻辑***  
    D) 物理和存储
3.  算法分析的目的是（）  
    A) 找出数据结构的合理性  
    B) 研究算法中的输入和输出的关系  
    ***C) 分析算法的效率以求改进***  
    D) 分析算法的易懂性和文档性
4.  计算机算法必须具备输入、输出和（ ）等5个特性。  
    A) 可行性、可移植性和可扩充性  
    ***B) 可行性、确定性和有穷性***  
    C) 确定性、有穷性和稳定性  
    D) 易读性、稳定性和安全性
5.  下面说法错误的是（ ）  
    ***(1)算法原地工作的含义是指不需要任何额外的辅助空间✅***  
    (2)在相同的规模n下，复杂度O(n)的算法在时间上总是优于复杂度O(2n)的算法  
    (3)所谓时间复杂度是指最坏情况下，估算算法执行时间的一个上界  
    ***(4)同一个算法，实现语言的级别越高，执行效率就越低。❌***  
    A．(1)  
    B.(1),(2)  
    ***C.(1),(4)***  
    D.(3)  
    6．从逻辑上可以把数据结构分为（ ）两大类。  
    A．动态结构、静态结构  
    B．顺序结构、链式结构  
    ***C．线性结构、非线性结构***  
    D．初等结构、构造型结构

### 三 判断题✅❎ ###

1.  数据元素是数据的最小单位。(❎)***解析：数据元素是数据的最小单位***
2.  数据项是数据处理的最小单位。 ( ✅ )
3.  数据的逻辑结构是指数据的各数据元素之间的逻辑关系。( ✅ )
4.  数据的物理结构是指数据在计算机内的实际存储形式。( ✅ )
5.  顺序存储方式的优点是存储密度大，且插入、删除运算效率高。( ❎ )
6.  数据的逻辑结构说明数据元素之间的顺序关系,它依赖于计算机的储存结构。( ❎ )

## 第2章 线性表 ##

### 一 判断正误 ###

（ ❎ ）1. 链表的每个结点中都恰好包含一个指针。

*  ***解析：链表中的结点可含多个指针域，分别存放多个指针。例如，双向链表中的结点可以含有两个指针域，分别存放指向其直接前趋和直接后继结点的指针。***  
    （❎ ）2. 链表的物理存储结构具有同链表一样的顺序。
 *  ***解析：链表的存储结构特点是无序，而链表的示意图有序。***  
    （ ❎ ）3. 链表的删除算法很简单，因为当删除链中某个结点后，计算机会自动地将后续的各个单元向前移动。
 *  ***解析：链表的结点不会移动，只是指针内容改变。***  
    （❎ ）4. 线性表的每个结点只能是一个简单类型，而链表的每个结点可以是一个复杂类型。
 *  ***解析：混淆了逻辑结构与物理结构，链表也是线性表！且即使是顺序表，也能存放记录型数据。***  
    （❎ ）5. 顺序表结构适宜于进行顺序存取，而链表适宜于进行随机存取。
 *  ***解析：正好说反了。顺序表才适合随机存取，链表恰恰适于“顺藤摸瓜”***  
    （❎ ）6. 顺序存储方式的优点是存储密度大，且插入、删除运算效率高。
 *  ***解析：前一半正确，但后一半说法错误，那是链式存储的优点。顺序存储方式插入、删除运算效率较低，在表长为n的顺序表中，插入和删除一个数据元素，平均需移动表长一半个数的数据元素。***  
    （ ❎ ）7. 线性表在物理存储空间中也一定是连续的。
 *  ***解析：线性表有两种存储方式，顺序存储和链式存储。后者不要求连续存放。***  
    （ ❎ ）8. 线性表在顺序存储时，逻辑上相邻的元素未必在存储的物理位置次序上相邻。
 *  ***解析：线性表有两种存储方式，在顺序存储时，逻辑上相邻的元素在存储的物理位置次序上也相邻。***  
    （ ❎ ）9. 顺序存储方式只能用于存储线性结构。
 *  ***解析：顺序存储方式不仅能用于存储线性结构，还可以用来存放非线性结构，例如完全二叉树是属于非线性结构，但其最佳存储方式是顺序存储方式。（后一节介绍）***  
    （❎ ）10. 线性表的逻辑顺序与存储顺序总是一致的。
 *  ***解析：理由同7。链式存储就无需一致。***

### 二 单项选择题 ###

1.  数据在计算机存储器内表示时，***物理地址与逻辑地址相同并且是连续的***，称之为（ C ）  
    （A）存储结构  
    （B）逻辑结构  
    ***（C）顺序存储结构***  
    （D）链式存储结构
2.  一个向量第一个元素的存储地址是100，每个元素的长度为2，则第5个元素的地址是（ B ）  
    （A）110  
    ***（B）108***  
    （C）100  
    （D）120
3.  在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个结点从小到大排序
4.  向一个有127个元素的顺序表中插入一个新元素并保持原来顺序不变，平均要移动（ B）个元素  
    （A）8  
    ***（B）63.5***  
    （C）63  
    （D）7

*  ***解析：一共127个元素，就有128个位置可以插入，表首插入移动次数为127，表尾插入移动次数为0，也就是从0累加到127，再除于128次，得63.5。***

1.  链接存储的存储结构所占存储空间：（ A ）  
    ***（A）分两部分，一部分存放结点值，另一部分存放表示结点间关系的指针。***  
    （B）只有一部分，存放结点值  
    （C）只有一部分，存储表示结点间关系的指针  
    （D）分两部分，一部分存放结点值，另一部分存放结点所占单元数
2.  线性表若采用***链式存储结构***时，要求内存中可用存储单元的地址:（ D ）  
    （A）必须是连续的  
    （B）部分地址必须是连续的  
    （C）一定是不连续的  
    ***（D）连续或不连续都可以***
3.  线性表Ｌ在\_\_\_\_情况下适用于使用链式结构实现。（ B ）  
    （Ａ）需经常修改Ｌ中的结点值  
    ***（Ｂ）需不断对Ｌ进行删除插入***  
    （Ｃ）Ｌ中含有大量的结点  
    （Ｄ）Ｌ中结点结构复杂
4.  单链表的***存储密度***（ C ）  
    （Ａ）大于1；  
    （Ｂ）等于1；  
    ***（Ｃ）小于1；***  
    （Ｄ）不能确定

*  ***解析：存储密度 = （结点数据本身所占的存储量）/（结点结构所占的存储总量）***

1.  设a1、a2、a3为3个结点，整数P0，3，4代表地址，则如下的链式存储结构称为（ B ）  
    ![在这里插入图片描述][7cd8c7ca35284f0da1f9db6e973c591b.png]  
    （Ａ）循环链表 ***（Ｂ）单链表*** （Ｃ）双向循环链表 （Ｄ）双向链表
2.  下面关于线性表的叙述中，***错误***的是哪一个？ （ B ）  
    A．线性表采用顺序存储，必须占用一片连续的存储单元。  
    ***B．线性表采用顺序存储，便于进行插入和删除操作。***  
    C．线性表采用链接存储，不必占用一片连续的存储单元。  
    D．线性表采用链接存储，便于插入和删除操作。
3.  线性表是具有n个\_\_\_\_\_\_\_\_的有限序列（n>0）。（ C ）  
    A．表元素 B．字符 ***C．数据元素*** D．数据项
4.  若某线性表最常用的操作是***存取任一指定序号的元素和在最后进行插入和删除运算***，则利用\_\_\_\_\_\_存储方式最节省时间。（ A ）  
    ***A．顺序表***  
    B．双链表  
    C．带头结点的双循环链表  
    D．单循环链表
5.  某线性表中最常用的操作是***在最后一个元素之后插入一个元素和删除第一个元素***，则采用 \_\_\_\_\_\_\_存储方式最节省运算时间。（ D ）  
    A．单链表  
    B．仅有头指针的单循环链表  
    C．双链表  
    ***D．仅有尾指针的单循环链表***
6.  ***静态链表中指针***表示的是\_\_\_\_\_\_\_\_. （ C ）  
    A． 内存地址  
    B．数组下标  
    ***C．下一元素地址***  
    D．左、右孩子地址  
    ![在这里插入图片描述][4f481ca9ee474393b2b4b1d86117f831.png]

typedef struct {
        
        int data;//数据域
        int cur;//游标
    }component;

1.  链表不具有的特点是\_\_\_\_\_\_\_\_\_. （ B ）  
    A．插入、删除不需要移动元素  
    ***B．可随机访问任一元素***  
    C．不必事先估计存储空间  
    D．所需空间与线性长度成正比
2.  完成在***双循环链表结点p之后插入s***的操作是（ ）.（ D ）  
    A． `p^.next:=s ; s^.priou:=p; p^.next^.priou:=s ; s^.next:=p^.next;`  
    B． `p^.next^.priou:=s; p^.next:=s; s^.priou:=p; s^.next:=p^.next;`  
    C． `s^.priou:=p; s^.next:=p^.next; p^.next:=s; p^.next^.priou:=s ;`  
    D．`s^.priou:=p; s^.next:=p^.next; p^.next^.priou:=s ; p^.next:=s;`  
    ![在这里插入图片描述][6fef5f080a4d481d8935c324553b9ea5.png]
3.  ***在单链表指针为p的结点之后插入指针为s的结点***，正确的操作是：（ B ）。  
    A.`p->next=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=s;`  
    ![在这里插入图片描述][b8ab3100284c427f8cf0cfb5b437df68.png]
4.  对于一个***头指针为head的带头结点的单链表***，判定该表为空表的条件是（ B ）  
    A．`head==NULL`  
    ***B．`head→next==NULL`***  
    C．`head→next==head`  
    D．`head!=NULL`
5.  在***双向链表存储结构***中，***删除p所指的结点***时须修改指针（ A ）。  
    ***A． `(p^.llink)^.rlink:=p^.rlink ; (p^.rlink)^.llink:=p^.llink;`***  
    B．`p^.llink:=(p^.llink)^.llink; (p^.llink)^.rlink:=p;`  
    C． `(p^.rlink)^.llink:=p ; p^.rlink:=(p^.rlink)^.rlink`  
    D． `p^.rlink:=(p^.llink)^.llink; p^.llink:=(p^.rlink)^.rlink;`  
    ![在这里插入图片描述][74670e177c174d6181b4c13a14508e7c.png]

### 三 简答题 ###

1.  线性表有两种存储结构：一是顺序表，二是链表。试问：
    
     *  如果有 n个线性表同时并存，并且在处理过程中各表的长度会动态变化，线性表的总数也会自动地改变。在此情况下，应选用哪种存储结构？ 为什么？
        
         *  选***链式存储结构***。它***可动态申请内存空间，不受表长度（即表中元素个数）的影响，插入、删除时间复杂度为O(1)***。
     *  若线性表的总数基本稳定，且很少进行插入和删除，但要求以最快的速度存取线性表中的元素，那么应采用哪种存储结构？为什么？
        
         *  选***顺序存储结构***。***顺序表可以随机存取，时间复杂度为O(1）***。
2.  在单链表中设置头结点的作用是什么？
    
     *  ***在单链表的首元结点（第一个数据元素）之前附设的结点，称为头结点，其作用是为了对单链表进行操作时，对空表和非空表的情况统一处理，对首元结点和其它结点统一处理。***

[7cd8c7ca35284f0da1f9db6e973c591b.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/31/15a903aa45204297a95746a73ee3a117.png
[4f481ca9ee474393b2b4b1d86117f831.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/31/32501a84c1ad4bed8b84778b25ad917d.png
[6fef5f080a4d481d8935c324553b9ea5.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/31/3722ed9781204874b0578d0f29a084a3.png
[b8ab3100284c427f8cf0cfb5b437df68.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/31/95994bfc3b16463aaa525d1d2519485f.png
[74670e177c174d6181b4c13a14508e7c.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/31/2d8a64caaddb49c4990fe5bf5682c0c3.png