数据结构习题及标准答案

1 5 第一章 1 在数据结构中 从逻辑上可以把数据结构分为 C A 动态结构和静态结构 B 紧凑结构和非紧凑结构 C 线性结构和非线性结构 D 内部结构和外部结构 2 在数据结构中 与所使用的计算机无关的是 A A 逻辑结构 B 存储结构 C 逻辑和存储结构 D 物理结构 3 下面程序的时间复杂度为 O mn for int i 1 i m i for int j 1 jnext null C head next head D head null 3 3 在线性表的下列存储结构中 读取元素花费时间最少的是 D A 单链表 B 双链表 C 循环链表 D 顺序表 4 对于只在表的首 尾两端进行手稿操作的线性表 宜采用的存储结构为 C A 顺序表 B 用头指针表示的单循环链表 C 用尾指针表示的单循环链表 D 单链表 5 在一个具有 n 个结点的有序单链表中插入一个新的结点 并保持链表元素仍然有序 则操作的时间复杂度为 D A O 1 B O log2n C O n2 D O n 6 在一个长度为 n n 1 的单链表上 设有头和尾两个指针 执行 B 操作与链表的长 度有关 A 删除单链表中第一个元素 B 删除单链表中最后一个元素 C 在第一个元素之前插入一个新元素 D 在最后一个元素之后插入一个新元素 7 与单链表相比 双向链表的优点之一是 D A 插入删除操作更简单 B 可以进行随机访问 C 可以省略表头指针或表尾指针 D 顺序访问相邻结点更容易 8 若 list 是某带头结点的循环链表的头结点指针 则该链表最后那个链结点的指针域 头结点的地址 中存放的是 B A list 的地址 B list 的内容 C list 指的链结点的值 D 链表第一个链结点 的地址 9 若 list1 和 list2 分别为一个单链表与一个双向链表的第一个结点的指针 则 B A list2 比 list1 占用更多的存储单元 B list1 与 list2 占用相同的存储单元 C list1 和 list2 应该是相同类型的指针变量 D 双向链表比单链表占用更多的存储单元 10 链表中的每个链结点占用的存储空间不必连续 这句话正确吗 不正确 11 某线性表采用顺序存储结构 元素长度为 4 首地址为 100 则下标为 12 的 第 13 个 元素的存储地址为 148 V 100 4 12 148 11 在顺序表的 最后一个结点之后 插入一个新的数据元素不必移动任何元素 12 若对线性表进行的操作主要不是插入删除 则该线性表宜采用 顺序 存储结构 若 频繁地对线性表进行插入和删除操作 则该线性表宜采用 链 存储结构 2 5 13 一个顺序表所占用存储空间的大小与 B 无关 A 表的长度 B 元素的存放顺序 C 元素的类型 D 元素中各的类型 14 设存储分配是从低地址到高地址进行的 若每个元素占用 4 个存储单元 则某元 素的地址是指它所占用的单元的 A A 第 1 个单元的地址 B 第 2 个单元的地址 C 第 3 个单元的地址 D 第 4 个单元的地址 15 若线性表采用顺序存储结构 每个元素占用 4 个存储单元 第 1 个元素的存储地址为 100 则第 12 个元素的存储地址是 B A 112 B 144 C 148 D 412 16 若长度为 n 的线性表采用顺序存储结构 在表的第 i 个位置插入一个数据元素 i 的合法值应该是 D A i 0 B i n C 1 i n D 1 i0 B y n C 1 i n D d inext p p next q B q next p next p next q C q next p next p q D p next q q next p 25 若删除非空线性链表中由 p 所指的链结点的直接后继链结点的过程过程是依次执行 B A r p next p next r free r B r p next p next r next free r C r p next p next r next free p D p next p next next free p 26 在非空双向循环链表中由 q 所指的链结点后面插入一个由 p 所指的链结点的操作依次 为 p prior q p next q next q next p C A q prior p B q next prior p C p next prior p D p prior next p 3 5 27 在非空双向循环链表中由 q 所指的链结点前面插入一个由 p 所指的链结点的操作依次 为 p next q p prior q prior q prior p D A q next p B q prior next p C p next prior p D p prior next p 28 顺序存储的线性表 a1 a2 an 在任一结点前插入一个新结点时所需移动结点的 平均次数为 D A n B n 2 C n 1 D n 1 2 29 在长度为 n 的顺序表的第 i 1 i n 1 个位置上插入一个元素 元素的移动次数是 A A n i 1 B n i C i D i 1 30 在线性表的下列存储结构中 读取元素花费时间最少的是 D A 单链表 B 双链表 C 循环链表 D 顺序表 31 在以单链表为存储结构的线性表中 数据元素之间的逻辑关系用 C A 数据元素的相邻地址表示 B 数据元素在表中的序号表示 C 指向后继元素的指针表示 D 数据元素的值表示 25 假设指针 p 指向单链表中的某一结点 若把 p 指针后面的结点删除 只需修改下列哪 个指针值即可 A p p next B p next p next next C p p next next D p next p 26 在一个单链表 HL 中 若要在指针 q 所指结点的后面插入一个由指针 P 所指向的结 点 则执行 D A q next p next p next q B p next q next q p C q next p next p next q D p next q next q next p 27 构造一个空的线性表 L 用 A A InitList free p A top p B top p next C p top next D p p next 20 若队列采用链式存储结构 队头元素指针与队尾元素指针分别为 front 和 rear 向队列 中插入一个由 p 所指的新结点的过程是依次执行 C rear p A rear p B front p C rear next p D front next p 21 若非空队列采用链式存储结构 队头元素指针与队尾元素指针分别为 front 和 rear 删除队列的一个元素的过程是依次执行 p front D free p A rear p B rear p next C p next rear D front p next 22 在循环队列中 若 front 与 rear 分别表示队头元素和队尾元素的位置 则判断循环队列 队空的条件是 C A front rear 1 B rear front 1 C front rear D front rear 0 23 若描述某循环队列的数组为为 Circle M 当循环队列满时 队列中有 B 个元素 A M B M 1 C M 1 D M 2 24 在解决计算机主机与打印机之间速度不匹配问题时通常设置一个打印数据缓冲区 主 机将要输出的数据依次写入该缓冲区 而打印机则依次从该缓冲区中取出数据打印 该缓 冲区应该是一个 D 结构 A 线性表 B 数组 C 堆栈 D 队列 25 设计一个递归问题的非递归算法通常需要设置 C 结构 A 线性表 B 数组 C 堆栈 D 队列 26 栈和队列都是 A