第一章绪论
一. 填空题（每空1分，共33分） 1. 一个计算机系统包括 硬件系统
和
软件系统
两大部分。
2. 一台计算机中全部程序的集合，称为这台计算机的软件资源 '；（系统） °
3. 计算机软件可以分为系统 软件和应用 软件两大类。科学计算程序包属于应用软 性—,诊断程序属于系统软件（工具）°
4. 一种用助忆符号来表示机器指令的操作符和操作数的语言是一汇編语言
5?数据结构是一门研究非数值计算的程序设计问题中计算机的 操作对皱 以及它们之间的 关系 和运算等的学科。
6?数据结构被形式地定义为（D,R）,其中D是 数据元素 的有限集合,R是D上的 关系 有限集 合。
7. 数据结构包括数据的 逻辑结构、数据的存储结构 和数据的 运算 这三个方面的内容。 8. 数据结构按逻辑结构可分为两大类，它们分别是—线性结构和非线性结构 °
9. 线性结构中元素之间存在一对一关系,树形结构中元素之间存在一对多关系,图形结构中元素之间存 在多对多关系。
10. 在线性结构中，第一个结点 没有前驱结点,其余每个结点有且只有1个前驱结点；最后一个结 点 没有 后续结点,其余每个结点有且只有1个后续结点。
11 在树形结构中，树根结点没有前驱 结点,其余每个结点有且只有_1_个前驱结点；叶子结点没 有 后续 结点,其余每个结点的后续结点数可以任意多个 。 12 13 14 15
在图形结构中，每个结点的前驱结点数和后续结点数可以 任意多个 。
数据的存储结构可用四种基本的存储方法表示，它们分别是撅序、链式、索引和 散列。 数据的运算最常用的有5种，它忙J分别是插入、删除.修改.査找.排序。 一个算法的效率可分为 时间 效率和 空间 效率o
和若干个被调用的其它函数组成。
16.任何一个C程序都由 一个主函数 二. 单项选择题（每小题1分，共15分） （B ） 1.通常所说的主机是指：
A） CPU B） CPU和内存
C） CPU.内存与外存 D） CPUx内存与硬盘
D）十六进制
（c ） 2.在计算机内部，一切信息的存取.处理和传送的形式是：
A） ACSII码 B） BCD码 C）二进制
（D ） 3?软件与程序的区别是：
A） 程序价格便宜.软件价格昂贵；
B） 程序是用户自己编写的，而软件是由厂家提供的； C） 程序是用髙级语言编写的，而软件是由机器语言编写的；
D） 软件是程序以及开发.使用和维护所需要的所有文档的总称，而程序只是软件的一部 分。
（C ） 4?所谓“裸机”是指：
A）单片机
机
（0）5.应用软件是指：
A）所有能够使用的软件
B）能被各应用单位共同使用的某种软件
C）所有微机上都应使用的基本软件 D）专门为某一应用目的而编制的软件
B）单板机
C）不装备任何软件的计算机 D）只装备操作系统的计算
*A
）6.C语言中的常量可分为整型常量、实型常量.字符型常量及（枚举）四种。
（A）符号常量
（B）长整型常量 （C） 逻辑常量 （D）二进制整数
*C ）7.编译程序的功能是：
A）发现源程序中的语法错误 C）将源程序编译成目标程序
B）改正源程序中的语法错误
D）将某一髙级语言程序翻译成另一种高级语言程序
）8.系统软件中最重要的是：
C）工具软件 D）数据库管理系统 A）操作系统 B）语言处理系统 ）
9.可移植性最好的计算机语言是：
C）高级语言 D）自然语言 A）机器语言 B）汇编语言
10. 非线性结构是数据元素之间存在一种：
B）多对多关系 C）多对一关系 D） 一对一关系 A） 一对多关系
_结构； 11. 数据结构中，与所使用的计算机无关的是数据的
D）物理和存储 C）逻辑 A）存储 B）物理 12. 算法分析的目的是：
A）找出数据结构的合理性 C）分析算法的效率以求改进 13. 算法分析的两个主要方面是 A）空间复杂性和时间复杂性
B）研究算法中的输入和输出的关系 D）分析算法的易懂性和文档性 B）正确性和简明性
D）数据复杂性和程序复杂性
C）可读性和文档性 14. 计算机算法指的是：
D）调度方法 A）计算方法 B）排序方法 C）解决问题的有限运算序列
______ 等5个特性。 15. 计算机算法必须具备输入.输出和
B）可行性.确定性和有穷性 A）可行性.可移植性和可扩充性
D）易读性、稳定性和安全性 C）确定性.有穷性和稳定性
第2章线性表
一、 填空（每空1分，共13分）
1. 【严题集2.2①】在顺序表中插入或删除一个元素，需要平均移动表中一半元素,具体移动的元素个 数与表
长和该元素在表中的位置 有关。 2. 线性表中结点的集合是有限 的,结点间的关系是 一对一 的。
3. 向一个长度为n的向量的第i个元素（lWiWn+1）之前插入一个元素时，需向后移动n?i+l个元素。 4. 向一个长度为n的向量中删除第i个元素（lWiWn）时，需向前移动竝—个元素。
5. 在顺序表中访问任意一结点的时间复杂度均为0（1）,因此，顺序表也称为随机存取 的数据结 构。
6. 【严题集2.2①】顺序表中逻辑上相邻的元素的物理位置卫生相邻。单链表中逻辑:上相邻的元素的物 理位置不-淀相邻。
7. 【严题集2.2①】在单链表中，除了首元结点外，任一结点的存储位置由其直接前驱结点的链域的值 指示。
8?在n个结点的单链表中要删除已知结点％，需找到它的前驱结点的地址,其时间复杂度为O（n）o 二、 判断正误（在正确的说法后面打勾，反之打叉）（每小题I分，共10分）
（x ） 1.链表的每个结点中都恰好包含一个指针。
答：错误。链表中的结点可含筝个捋针域.分别存放藝个指针。例如，双向链表中的结点可以含有两个指针
7
域.分别存放抬向其直接前趋和直接后继结点的指针。
（x ）2.链表的物理存储结构具有同链表一样的顺序。断链表的存储结构特点是无序，而链表的示意图有序。 （X ） 3.链表的删除算法很简单，因为当删除链中某个结点后，计算机会自动地将后续的各个单元向 前移动。错.链表的结点不会移动.只是抬针内容改变。
（X ） 4.线性表的每个结点只能是一个简单类型，而链表的每个结点可以是一个复杂类型。
锚，混淆了逻辑结构与物理结构，链表也是线性表！且即使是顺序表，也能存放记录型数据。
（X ） 5.顺序表结构适宜于进行顺序存取，而链表适宜于进行随机存取。
错，正好说反了。顺序表才适合随机存取，链表恰恰适于“顺藤摸瓜”
（X ） 6.顺序存储方式的优点是存储密度大，且插入、删除运算效率髙。
错，前一半正确.但后一半说法错误.那是链式存储的优点。顺序存储方式插入、删除运算效率较低， 在表长为n的顺序表中.插入和删除一个数据元素，平均需移动表长一半个数的数据元素。 （X ） 7.线性表在物理存储空间中也一定是连续的。
错，线性表有两种存储方式?顺序存储和链式存储。后者不要求连续存放。
（X ） 8.线性表在顺序存储时，逻借上相邻的元素未必在存储的物理位置次序上相邻。
错误。线性表有两种存储方式，在顺序存储时.逻辑上相邻的元素在存储的物理位宜次序上也相邻。
（X ） 9.顺序存储方式只能用于存储线性结构。
错谋。顺序存储方式不仅能用于存储线性结构，还可以用来存放非线性结构，例如完全二叉树是属于非线性结构，但 其最佳存储方式是顺序存储方式。（后一节介绍） （X ） 10.线性表的逻借顺序与存储顺序总是一致的。
错，理由同7。链式存储就无需一致° 三. 单项选择题（每小题1分，共10分）
（C ） 1.数拯在讣算机存储器内表示时，物理地址与逻辑地址相同并且是连续的，称之为：
（A）存储结构 （B）逻借结构 （C）顺序存储结构 （D）链式存储结构 （B ） 2 -个向量第一个元素的存储地址是100,每个元素的长度为2,则第5个元素的地址是 ________________ （A） 110 （B） 108 （C） 100 （D） 120
（A ） 3.在n个结点的顺序表中，算法的时间复杂度是O （1）的操作是：
（A） 访问第1个结点（lWiWn）和求第i个结点的直接前驱（2^n） （B） 在第1个结点后插入一个新结点（lWiWa）
（C） 删除第1个结点（lWiWn） （D） 将n个结点从小到大排序
（B ） 4.向一个有127个元素的顺序表中插入一个新元素并保持原来顾序不变，平均要移动_个元素 （A） 8 （B） 63.5 （C） 63 （D） 7
（A ） 5.链接存储的存储结构所占存储空间：
（A） 分两部分，一部分存放结点值，另一部分存放表示结点间关系的指针 （B） 只有一部分，存放结点值
（C） 只有一部分，存储表示结点间关系的指针 （D） 分两部分，一部分存放结点值，另一部分存放结点所占单元数
（B ） 6.链表是一种采用 ___________ 存储结构存储的线性表；
（A）顺序 （B）链式 （C）星式 （D）网状 （D ） 7.线性表若采用链式存储结构时，要求内存中可用存储单元的地址： （A）必须是连续的 （B）部分地址必须是连续的
3
相关推荐：
loading