数据结构复习试题

数据结构复习试题 线性表 一 选择题 共 20 题 每题 1 5 分 共计 30 分 1 下列哪一条是顺序存储结构的优点 A 插入运算方便 B 可方便地用于各种逻辑结构的存储表示 C 存储密度大 D 删除运算方便 2 下面关于线性表的叙述中 错误的是哪一个 A 线性表采用顺序存储 必须占用一片连续的存储单元 B 线性表采用顺序存储 便于进行插入和删除操作 C 线性表采用链接存储 不必占用一片连续的存储单元 D 线性表采用链接存储 便于进行插入和删除操作 3 线性表是具有 n 个 的有序序列 n 0 A 表元素 B 字符 C 数据元素 D 数据项 4 若某线性表最常用的操作是存取任一指定序号的元素和在最后进行插入和删除运算 则 利用 存储方式最节约时间 A 顺序表 B 双链表 C 带头结点的双循环链表 D 单循环链表 5 若某线性表最常用的操作是在最后一个元素之后插入一个元素和删除第一个元素 则采 用 存储方式最节省运算时间 A 单链表 B 仅有头指针的单循环链表 C 双链表 D 仅有尾指针的单循环链表 6 若某线性表最常用的操作是在末尾插入结点和删除尾结点 则选用 最节省运算 时间 A 带头结点的双循环链表 B 单循环链表 C 带尾指针的单循环链表 D 单链表 7 若某线性表最常用的操作是存取第 I 个元素及其前驱和后继元素的值 则采用 存储方式最节省运算时间 A 单链表 B 双向链表 C 单循环链表 D 顺序表 8 对于一个头指针为 head 的带头结点的单链表 判定该表为空的条件是 A head NULL B head next NULL C head next head D head NULL 9 链表不具有的特点是 A 插入 删除不需要移动元素 B 可随机访问任一元素 C 不必事先估计存储空间 D 所需空间与线性长度成正比 10 单链表中 增加一个头结点的目的是为了 A 使单链表至少有一个结点 B 标示表结点中首结点的位置 C 方便运算的实现 D 说明单链表是线性表的链式存储 11 在一个以 h 为头的单循环链中 p 指针指向链尾的条件是 A p next h B p next NULL C p next next h D p data 1 12 对于一个线性表既要求能够进行快速的插入和删除 又要求存储结构能反映数据之间 的逻辑关系 则应该使用 A 顺序存储方式 B 链式存储方式 C 散列存储方式 D 以上均可以 13 一个算法应该具有 确定性 等 5 个特性 下面对另外 4 个特性的描述中错误的是 A 有零个或多个输入 B 有零个或多个输出 C 有穷性 D 可行性 14 一个线性表第一个元素的存储地址是 100 每个元素的长度为 2 则第 5 个元素的地址是 A 110 B 108 C 100 D 120 15 向一个有 127 个元素的顺序表中插入一个新元素并保持原来顺序不变 平均要移动 个元素 A 64 B 63 C 63 5 D 7 16 线性表采用链式存储结构时 其地址 A 必须是连续的 B 部分地址必须是连续的 C 一定是不连续的 D 连续与否均可以 17 在一个单链表中 若 p 所指结点不是最后结点 在 p 之后插入 s 所指结点 则执行 A s next p p next s B s next p next p next s C s next p next p s D p next s s next p 18 在一个单链表中 若删除 p 所指结点的后续结点 则执行 A p next p next next B p p next p next p next next C p next p next D p p next next 19 线性表是具有 n 个 的有限序列 n 0 A 表元素 B 字符 C 数据元素 D 数据项 20 下列有关线性表的叙述中 正确的是 A 线性表中的元素之间隔是线性关系 B 线性表中至少有一个元素 C 线性表中任何一个元素有且仅有一个直接前趋 D 线性表中任何一个元素有且仅有一个直接后继 二 填空题 共 8 题 每题 2 分 其中第 5 题没空 2 分 共计 18 分 1 已知 P 为单链表中的非首尾结点 在 P 结点后插入 S 结点的语句为 2 顺序表中逻辑上相邻的元素物理位置 相邻 单链表中逻辑上相邻的元素物理位置 相邻 3 线性表 L a1 a2 an 采用顺序存储 假定在不同的 n 1 个位置上插入的概 率相同 则插入一个新元素平均需要移动的元素个数是 4 在非空双向循环链表中 在结点 q 的前面插入结点 p 的过程如下 p prior q prior q prior next p p next q 5 已知 L 是无表头结点的单链表 是从下列提供的答案中选择合适的语句序列 分别实现 1 表尾插入 s 结点的语句序列是 2 表尾插入 s 结点的语句序列是 1 p next s 2 p L 3 L s 4 p next s next 5 s next p next 6 s next L 7 s next null 8 while p next Q p p next 9 while p next null p p next 6 向一个长度为 n 的向量的第 i 个元素 1 i n 1 之前插入一个元素时 需向后移动 个元素 7 向一个长度为 n 的向量中删除第 i 个元素 1 i n 时 需向前移动 个元素 8 在顺序表中插入或删除一个元素 需要平均移动 元素 具体移动的元素个数与 有关 三 读程序写结果 共 4 题 每题 5 分 共计 20 分 1 include long g long k if k 1 return k return 10 g k 1 20 g k 2 2008 int main void long n scanf ld printf ld n g n return 0 输入 6 输出 2 include int main int i j f a 9 for i 1 i 8 i f i 2 if f 0 a i 0 else a i 1 for j 1 j i j if f 1 a i a i j else a i a i j for i 1 i 8 i printf d a i return 0 输出 3 include int main int a b c p q r 3 scanf d d d p a b c q b c a p r 0 a p q q r 1 r 0 r 0 300 if 3 q p 3 r 0 else r 1 q p printf d n r 0 r 1 return 0 输入 128 8 8 输出 4 include void digit long n long m if m 0 printf 2ld n if m 1 digit n 10 m 10 printf 2ld n int main long x x2 printf Input a number n scanf ld x2 1 while x2next p p q 2 对单链表中元素按插入方法排序的算法如下 其中 L 为链表的头结点指针 请填充算法 中标出的空白处 完成其功能 typedef struct node int data struct node next linknode link void Insertsort link L link p q r u p L next while r L q L next while q q next u p next p u 线性表 一 单项选择题 共 20 题 每题 1 5 分 共计 30 分 12345678910 CBCADADBBC 11121314151617181920 ABBBCDBACA 二 填空题 共 8 题 每题 2 分 其中第 5 题没空 2 分 共计 18 分 1 s next p next p next s 2 一定 不一定 3 n 2 4 q prior p 5 1 6 3 2 2 9 1 7 6 n i 1 7 n i 8 1 表中一半 2 表