文档介绍：专业资料专业资料参考首选第1章绪论一、选择题 1. 算法的时间复杂度取决于(C) A .问题的规模 B. 待处理数据的初态 2. 计算机算法指的是( C) ,它必须具备( B) 这三个特性。(1) A .计算方法 B. 排序方法 C. 解决问题的步骤序列 D. 调度方法(2) A .可执行性、可移植性、可扩充性 B. 可执行性、确定性、有穷性 C. 确定性、有穷性、稳定性 D. 易读性、稳定性、安全性 3 .从逻辑上可以把数据结构分为( C )两大类。 A .动态结构、静态结构 B .顺序结构、链式结构 C .线性结构、非线性结构 D .初等结构、构造型结构 4 .以下与数据的存储结构无关的术语是( D)。 A .循环队列 B. 链表 C. 哈希表 5 .在下面的程序段中,对 x 的赋值语句的频度为( C) FOR i:=1 TOn DO FOR j:=1 TOn DO x:=x+1; A. O(2n) B. O(n) C. O(n 2)D. O(log 2 n) 6 .连续存储设计时,存储单元的地址( A)。 A .一定连续 B .一定不连续 C .不一定连续 D .部分连续,部分不连续二、判断题 1. 数据元素是数据的最小单位。(F)【山东师范大学 2001 一、 1(2分)】 2. 记录是数据处理的最小单位。(F) 3 .数据的物理结构是指数据在计算机内的实际存储形式。(T)【山东师范大学 2001 一、 2(2分)】 4. 在顺序存储结构中,有时也存储数据结构中元素之间的关系。(F) 5. 顺序存储方式的优点是存储密度大,且插入、删除运算效率高。(F) 三、填空 1 .数据的物理结构包括的表示和的表示。 2. 对于给定的 n 个元素, 可以构造出的逻辑结构有(1),(2),(3),_(4) 四种。 3 .数据的逻辑结构是指。 4 .一个数据结构在计算机中称为存储结构。 5 .数据结构中评价算法的两个重要指标是 6 .已知如下程序段 FOR i:= n DOWNTO 1 DO { 语句 1} BEGIN x:=x+1 ;{ 语句 2} FOR j:=n DOWNTO i DO { 语句 3} y:=y+1; { 语句 4} END ; 语句 1 执行的频度为(1); 语句 2 执行的频度为(2); 语句 3 执行的频度为(3); 语句 4 执行的频度为(4)。答案:1. 数据元素数据元素间关系 2. 集合线性结构树形结构图状结构或网状结构。 3 .数据的组织形式,即数据元素之间逻辑关系的总体。而逻辑关系是指专业资料专业资料参考首选数据元素之间的关联方式或称“邻接关系”。4. 表示( 映像)。5. 时间复杂度和空间复杂度。 6.(1) n+1 (2)n(3) n(n+3)/2 (4) n(n+1)/2 。四、应用题 1. 数据元素之间的关系在计算机中有几种表示方法?各有什么特点? 四种表示方法(1 )顺序存储方式。数据元素顺序存放,每个存储结点只含一个元素。存储位置反映数据元素间的逻辑关系。存储密度大,但有些操作(如插入、删除)效率较差。(2) 链式存储方式。每个存储结点除包含数据元素信息外还包含一组( 至少一个) 指针。指针反映数据元素间的逻辑关系。这种方式不要求存储空间连续,便于动态操作(如插入、删除等) ,但存储空间开销大(用于指针) ,另外不能折半查找等。(3) 索引存储方式。除数据元素存储在一地址连续的内存空间外, 尚需建立一个索引表, 索引表中索引指示存储结点的存储位置,兼有静态和动态特性。(4 )散列存储方式。通过散列函数和解决冲突的方法,将关键字散列在连续的有限的地址空间内, 并将散列函数的值解释成关键字所在元素的存储地址, 这种存储方式称为散列存储。其特点是存取速度快,只能按关键字随机存取,不能顺序存取,也不能折半存取。 2 .若有 100 个学生,每个学生有学号,姓名,平均成绩,采用什么样的数据结构最方便, 写出这些结构? 【山东师范大学 1996 二、 2】将学号、姓名、平均成绩看成一个记录(元素,含三个数据项) ,将 100 个这样的记录存于数组中。因一般无增删操作,故宜采用顺序存储。 typedef struct { int num;// 学号 char name[8];// 姓名 float score;/ 平均成绩}node ; node student[100]; 第2章线性表一选择题 1 .线性表是具有 n 个( 数据元素)的有限序列( n>0 )。 2. 若某线性表最常用的操作是存取任一指定序号的元素和在最后进行插入和删除运算, 则利用(顺序表)存储方式最节省时间。 3 .某线性表中最常用的操作是在最后一个元素之后插入一个元素和删除第一个元素, 则采用( 仅有尾指针的