数据结构-C++实现(第二版)答案

数据结构第二章练习

一、选择题

1. L是线性表，已知L.GetLen( )的值是4，经运算L.DelElem(3)后，L.GetLen( )的值是( )。 ①1②2③3④4 ;3

2. 线性表中，只有一个直接前驱和一个直接后继的是( )。 ①首元素②尾元素③中间的元素④所有的元素 ;3

3. 带头结点的单链表head为空表的判定条件是( )。

①head==NULL②head->next==NULL③head->next==head④head!=NULL ;2

4. 不带头结点的单链表head为空表的判定条件是( )。

①head==NULL②head->next==NULL③head->next==head④head!=NULL ;1

5. 非空的循环单链表head的尾结点p满足( )。

①p==NULL②p->next==NULL③p->next==head④p==head ;3

6. 线性表中各元素之间的关系是( )关系。 ①层次②网状③有序④集合 ;3

7. 在循环(单)链表的一个结点有( )个指针。 ①1②2③3④0 ;1

8. 在单链表的一个结点有( )个指针。 ①1②2③3④0 ;1

9. 在双向链表的一个结点

题目二：

约瑟夫生者死者游戏（链表存储）

一：【内容与要求】

约瑟夫游戏的大意是：每30个旅客同乘一条船，因为严重超载，加上风高浪大，危险万分；因此船长告诉乘客，只有将全船一半的旅客投入还中，其余人才能幸免遇难。无奈，大家只得同意这种办法，并议定30个人围成一圈，由第一个人数起，依次报数，数到第9人，便把他投入大海中，然后再从他的下一个人数起，数到第9人，再将他扔进大海中，如此循环地进行，直到剩下15个乘客为止。问哪些位置是将被扔下大海的位置。

二：概要设计

利用链表循环来解决。首先，就必须先定义一个链表，按照所需要的长度进行定义，然后令其为指针指向头指针，即完成了一个循环链表的创建。接下来先打印链表输出。其次，就是算法实现，需要利用指针来进行，数据域标记人员编号，先用一个指针循环查找，找到第一个需要删除的人，标记为1，先输出节点数，再进行删除。依次循环查找，直到被删除的节点数量为总人数的一半的时候则结束。

三：程序执行流程图

开始 创建N个节点的循环链表打印输出链表 循环找到报数起始位置，用指针标记 判定剩下人数是否为一半 否 是 从报数位置起，依次循环数到找到第m个人 输出该节点并且删除，指针后移，标记下一次的起始位置 程序结束

第 3 章 线性表的链式存储

3.1 选择题

（1）两个有序线性表分别具有 n 个元素与 m 个元素且 n≤m，现将其归并成一个有序表， 其最少的比较次数是（ A ）。

A．n B．m C．n ? 1 D．m + n

（2）非空的循环单链表 head 的尾结点（由 p 所指向）满足（ C ）。

A．p->next==NULL B．p==NULL C．p->next==head D．p==head （3）在带头结点的单链表中查找 x 应选择的程序体是（ C ）。

A．node *p=head->next; while (p && p->info!=x) p=p->next;

if (p->info==x) return p else return NULL;

B．node *p=head; while (p&& p->info!=x) p=p->next; return p; C．node *p=head->next; while (p&&p->info!=x) p=p->next; return p; D．node *p=head; while (p->info!=x) p=p-

第 3 章 线性表的链式存储

3.1 选择题

（1）两个有序线性表分别具有 n 个元素与 m 个元素且 n≤m，现将其归并成一个有序表， 其最少的比较次数是（ A ）。

A．n B．m C．n ? 1 D．m + n

（2）非空的循环单链表 head 的尾结点（由 p 所指向）满足（ C ）。

A．p->next==NULL B．p==NULL C．p->next==head D．p==head （3）在带头结点的单链表中查找 x 应选择的程序体是（ C ）。

A．node *p=head->next; while (p && p->info!=x) p=p->next;

if (p->info==x) return p else return NULL;

B．node *p=head; while (p&& p->info!=x) p=p->next; return p; C．node *p=head->next; while (p&&p->info!=x) p=p->next; return p; D．node *p=head; while (p->info!=x) p=p-

第 3 章 线性表的链式存储

3.1 选择题

（1）两个有序线性表分别具有 n 个元素与 m 个元素且 n≤m，现将其归并成一个有序表， 其最少的比较次数是（ A ）。

A．n B．m C．n ? 1 D．m + n

（2）非空的循环单链表 head 的尾结点（由 p 所指向）满足（ C ）。

A．p->next==NULL B．p==NULL C．p->next==head D．p==head （3）在带头结点的单链表中查找 x 应选择的程序体是（ C ）。

A．node *p=head->next; while (p && p->info!=x) p=p->next;

if (p->info==x) return p else return NULL;

B．node *p=head; while (p&& p->info!=x) p=p->next; return p; C．node *p=head->next; while (p&&p->info!=x) p=p->next; return p; D．node *p=head; while (p->info!=x) p=p-

第 1 章 绪 论

课后习题讲解

1. 填空

⑴（ 数据元素 ）是数据的基本单位，在计算机程序中通常作为一个整体进行考虑和处理。

【解答】数据元素

⑵（ 数据项）是数据的最小单位，（数据元素 ）是讨论数据结构时涉及的最小数据单位。

【解答】，

【分析】数据结构指的是数据元素以及数据元素之间的关系。

⑶ 从逻辑关系上讲，数据结构主要分为（ 集合）、（ 线性结构）、（ 树结构）和（ 图结构 ）。

【解答】，，，

⑷ 数据的存储结构主要有（顺序存储结构 ）和（ 链接存储结构）两种基本方法，不论哪种存储结构，都要存储两方面的内容：（ 数据元素）

和（ 数据元素之间的关系 ）。

【解答】，，，

⑸ 算法具有五个特性，分别是（有零个或多个输入 ）、（有一个或多个输出 ）、（有穷性 ）、（确定性 ）、（可行性 ）。

【解答】，，，，

⑹ 算法的描述方法通常有（ 自然语言）、（程序设计语言 ）、（流程图 ）和（ 伪代码）四种，其中，（伪代码 ）被称为算法语言。

【解答】，，，，

⑺ 在一般情况下，一个算法的时间复杂度是（ 问题规模 ）的函数。

【解答】

⑻ 设待处理问题的规模为n，若一个算法的时间复杂度为一个常数，则表示成数量级的形式为（Ο(1) ），若

为n*log25n，则表示成数量级的形

前 言

《数据结构》是计算机及相关专业的一门核心基础课程，也是很多高校考研专业课之一。它主要介绍线性结构、树结构、图结构三种逻辑结构元素的存储实现，在此基础上介绍一些典型算法及时、空效率分析。这门课程的主要任务是培养学生的算法设计能力及良好的程序设计习惯。通过学习，要求学生能够掌握典型算法的设计思想及程序实现，能够根据实际问题选取合适的存储方案，设计出简洁、高效、实用的算法，为后续课程的学习及软件开发打下良好的基础。学习这门课程，习题和实验是两个关键环节。学生理解算法，上机实验是最佳的途径之一。因此，实验环节的好坏是学生能否学好《数据结构》的关键。为了更好地配合学生实验，特编写实验指导书。 一、实验目的

更好的理解算法的思想、培养编程能力。 二、实验要求

1、每次实验前学生必须根据试验内容认真准备实验程序及调试时所需的输入数据。 2、在指导教师的帮助下能够完成实验内容，得出正确的实验结果。 3、实验结束后总结实验内容、书写实验报告。

4、遵守实验室规章制度、不缺席、按时上、下机。

5、实验学时内必须做数据结构的有关内容，不允许上网聊天或玩游戏，如发现上述现

象，取消本次上机资格，平时成绩扣10分。

数据结构试题一

一、单项选择题（每小题3分，共30分）

1、在有n 个叶子结点的哈夫曼树中，其结点总数为（ ）。 A、不确定 B、2n C、2n+1 D、2n-1 2、下列序列中，（ ）是执行第一趟快速排序得到的序列（排序的关键字类 型是字符串）。

A、[da，ax，eb，de，bb]ff[ha，gc] B、[cd，eb，ax，da]ff[ha，gc，bb] C、[gc，ax，eb，cd，bb]ff[da，ha] D、[ax，bb，cd，da]ff[eb，gc，ha]

3、若线性表最常用的操作是存取第 i 个元素及其前驱的值，则采用（ ） 存储方式节省时间。

A、单链表 B、双链表 C、单循环链表 D、顺序表 4、下列排序算法中，时间复杂度不受数据初始状态影响，恒为O(nlogn)的是 （ ）。 A、堆排序 B、冒泡排序 C、直接选择排序 D、快序排序

5、某二叉树的先序序列和后序序列正好相反，则该二叉树一定是（ ）的 二叉树。

A、空

第二章基本控制结构程序设计习题 1

第一章 C++基础知识习题

1.1 判断下列标识符的合法性。 sin book 5arry _name Example2.1 main $1 class_cpp a3 x*y my name

答：合法的：sin book _name main class_cpp a3 非法的：5arry Example2.1 $1 x*y my name

1.2 假定有下列变量： int a=3,b=5,c=0;

float x=2.5,y=8.2,z=1.4;

char ch1=’a’,ch2=’5’,ch3=’0’,ch4;

求下列表达式的值，以及运算后表达式所涉及的各变量的值。

x+(int)y%a x=z*b++,b=b*x,b++ ch4=ch3-ch2+ch1 int(y/z)+(int)y/(int)z !(a>b)&&c&&(x*=y)&&b++ ch3||(b+=a*c)||c++ z=(a<<2)/(b>>1)

答：x+(int)y%a 表达式值为：4

第3章 栈和队列

1．选择题

（1）若让元素1，2，3，4，5依次进栈，则出栈次序不可能出现在（ ）种情况。 A．5，4，3，2，1 B．2，1，5，4，3 C．4，3，1，2，5 D．2，3，5，4，1 答案：C

解释：栈是后进先出的线性表，不难发现C选项中元素1比元素2先出栈，违背了栈的

后进先出原则，所以不可能出现C选项所示的情况。

（2）若已知一个栈的入栈序列是1，2，3，?，n，其输出序列为p1，p2，p3，?，pn，若p1=n，则pi为（ ）。

A．i B．n-i C．n-i+1 D．不确定 答案：C

解释：栈是后进先出的线性表，一个栈的入栈序列是1，2，3，?，n，而输出序列的第

一个元素为n，说明1，2，3，?，n一次性全部进栈，再进行输出，所以p1=n，p2=n-1，?，pi=n-i+1。

（3）数组Ｑ［ｎ］用来表示一个循环队列，ｆ为当前队列头元素的前一位置，ｒ为队尾元素的位置，假定队列中元素的个数小于ｎ，计算队列中元素个数的公式为（ ）。

A．r-f B．(n+f-r)%n C．n+r-f