《第2章 线性表_3149》由会员分享，可在线阅读，更多相关《第2章 线性表_3149（23页珍藏版）》请在金锄头文库上搜索。
1、第 2 章 线性表 一一 选择题选择题 1 下述哪一条是顺序存储结构的优点 北方交通大学 2001 一 4 2 分 A 存储密度大 B 插入运算方便 C 删除运算方便 D 可方便地用于各种逻辑结构 的存储表示 2 下面关于线性表的叙述中 错误的是哪一个 北方交通大学 2001 一 14 2 分 A 线性表采用顺序存储 必须占用一片连续的存储单元 B 线性表采用顺序存储 便于进行插入和删除操作 C 线性表采用链接存储 不必占用一片连续的存储单元 D 线性表采用链接存储 便于插入和删除操作 3 线性表是具有 n 个 的有限序列 n 0 清华大学 1998 一 4 2 分 A 表元素 B 字符 C
2、数据元素 D 数据项 E 信息项 4 若某线性表最常用的操作是存取任一指定序号的元素和在最后进行插入和删除运算 则利用 存储方式最节省时间 哈尔滨工业大学 2001 二 1 2 分 A 顺序表 B 双链表 C 带头结点的双循环链表 D 单循环链表 5 某线性表中最常用的操作是在最后一个元素之后插入一个元素和删除第一个元素 则采用 存储方式最节省运算时间 南开大学 2000 一 3 A 单链表 B 仅有头指针的单循环链表 C 双链表 D 仅有尾指针的 单循环链表 6 设一个链表最常用的操作是在末尾插入结点和删除尾结点 则选用 最节省时 间 A 单链表 B 单循环链表 C 带尾指针的单循环链表 D
3、 带头结点的双循环链表 合肥工业大学 2000 一 1 2 分 7 若某表最常用的操作是在最后一个结点之后插入一个结点或删除最后一个结点 则 采用 存储方式最节省运算时间 北京理工大学 2000 一 1 2 分 A 单链表 B 双链表 C 单循环链表 D 带头结点的双循环链表 8 静态链表中指针表示的是 北京理工大学 2001 六 2 2 分 A 内存地址 B 数组下标 C 下一元素地址 D 左 右孩子地址 9 链表不具有的特点是 福州大学 1998 一 8 2 分 A 插入 删除不需要移动元素 B 可随机访问任一元素 C 不必事先估计存储空间 D 所需空间与线性长度成正比 10 下面的叙述不
4、正确的是 南京理工大学 1996 一 10 2 分 A 线性表在链式存储时 查找第 i 个元素的时间同 i 的值成正比 B 线性表在链式存储时 查找第 i 个元素的时间同 i 的值无关 C 线性表在顺序存储时 查找第 i 个元素的时间同 i 的值成正比 D 线性表在顺序存储时 查找第 i 个元素的时间同 i 的值无关 11 线性表的表元存储方式有 1 和链接两种 试指出下列各表中使用的是何种存 储方式 表 1 是 2 存储方式 表 2 是 3 存储方式 表 3 是 4 存储方式 表 4 是 5 存储方式 表左的 s 指向起始表元 表 1 s 表 2 s 表 3 s 表 4 s 供选择的答案 A
5、 连续 B 单向链接 C 双向链接 D 不连接 E 循环链接 F 树状 G 网状 H 随机 I 顺序 J 顺序循环 上海海运学院 1995 二 1 5 分 12 1 静态链表既有顺序存储的优点 又有动态链表的优点 所以 它存取表中第 i 个元 素的时间与 i 无关 2 静态链表中能容纳的元素个数的最大数在表定义时就确定了 以后不能增加 3 静态链表与动态链表在元素的插入 删除上类似 不需做元素的移动 以上错误的是 南京理工大学 2000 一 3 1 5 分 A 1 2 B 1 C 1 2 3 D 2 13 若长度为 n 的线性表采用顺序存储结构 在其第 i 个位置插入一个新元素的算法的时间 表
6、元编号 货号 数量 表元间联系 1 618 40 2 2 205 2 3 3 103 15 4 4 501 20 5 5 781 17 6 6 910 24 0 表元编号 货号 数量 表元间联系 1 618 40 5 2 205 2 1 3 103 15 4 4 501 20 2 5 781 17 6 6 910 24 3 表元编号 货号 数量 表元间联系 1 618 40 5 2 205 2 1 3 103 15 4 4 501 20 0 5 781 17 6 6 910 24 3 表元间联系 表元编号 货号 数量 1 2 1 618 40 5 2 2 205 2 1 0 3 103 15
7、4 6 4 501 20 0 3 5 781 17 6 1 6 910 24 3 5 复杂度为 1 iLlink q q Rlink p p Llink Rlink q q Llink q B p Llink q p Llink Rlink q q Rlink p q Llink p Llink C q Rlink p q Llink p Llink p Llink Rlink q p Llink q D q Llink p Llink q Rlink q p Llink q p Llink q 24 在单链表指针为 p 的结点之后插入指针为 s 的结点 正确的操作是 A p next s s
8、 next p next B s next p next p next s C p next s p next s next D p next s next p next s 青岛大学 2001 五 3 2 分 25 对于一个头指针为 head 的带头结点的单链表 判定该表为空表的条件是 A head NULL B head next NULL C head next head D head NULL 北京工商大学 2001 一 5 3 分 26 在双向链表存储结构中 删除 p 所指的结点时须修改指针 A p llink rlink p rlink p rlink llink p llink
9、B p llink p llink llink p llink rlink p C p rlink llink p p rlink p rlink rlink D p rlink p llink llink p llink p rlink rlink 西安电子科技大学 1998 一 1 2 分 27 双向链表中有两个指针域 llink 和 rlink 分别指向前趋及后继 设 p 指向链表中的一 个结点 现要求删去 p 所指结点 则正确的删除是 链中结点数大于 2 p 不是第一 个结点 A p llink rlink p llink p llink rlink p rlink dispose p
10、 B dispose p p llink rlink p llink p llink rlink p rlink C p llink rlink p llink dispose p p llink rlink p rlink D 以上 A B C 都不对 南京理工大学 1997 一 1 2 分 二 判断二 判断 1 链表中的头结点仅起到标识的作用 南京航空航天大学 1997 一 1 1 分 2 顺序存储结构的主要缺点是不利于插入或删除操作 南京航空航天大学 1997 一 2 1 分 3 线性表采用链表存储时 结点和结点内部的存储空间可以是不连续的 北京邮电大学 1998 一 2 2 分 4 顺
11、序存储方式插入和删除时效率太低 因此它不如链式存储方式好 北京邮电大学 2002 一 2 1 分 5 对任何数据结构链式存储结构一定优于顺序存储结构 南京航空航天大学 1997 一 3 1 分 6 顺序存储方式只能用于存储线性结构 中科院软件所 1999 六 1 2 2 分 上海海运学院 1997 一 1 1 分 7 集合与线性表的区别在于是否按关键字排序 大连海事大学 2001 一 5 1 分 8 所谓静态链表就是一直不发生变化的链表 合肥工业大学 2000 二 1 1 分 9 线性表的特点是每个元素都有一个前驱和一个后继 合肥工业大学 2001 二 1 1 分 10 取线性表的第 i 个元
12、素的时间同 i 的大小有关 南京理工大学 1997 二 9 2 分 11 循环链表不是线性表 南京理工大学 1998 二 1 2 分 12 线性表只能用顺序存储结构实现 青岛大学 2001 四 2 1 分 13 线性表就是顺序存储的表 青岛大学 2002 一 1 1 分 14 为了很方便的插入和删除数据 可以使用双向链表存放数据 上海海运学院 1995 一 1 1 分 上海海运学院 1997 一 2 1 分 15 顺序存储方式的优点是存储密度大 且插入 删除运算效率高 上海海运学院 1996 一 1 1 分 上海海运学院 1999 一 1 1 分 16 链表是采用链式存储结构的线性表 进行插入
13、 删除操作时 在链表中比在顺序存储结 构中效率高 上海海运学院 1998 一 2 1 分 三 填空三 填空 1 当线性表的元素总数基本稳定 且很少进行插入和删除操作 但要求以最快的速度存取 线性表中的元素时 应采用 存储结构 北方交通大学 2001 二 4 2 线性表 L a1 a2 an 用数组表示 假定删除表中任一元素的概率相同 则删除一 个元素平均需要移动元素的个数是 北方交通大学 2001 二 9 3 设单链表的结点结构为 data next next 为指针域 已知指针 px 指向单链表中 data 为 x 的结点 指针 py 指向 data 为 y 的新结点 若将结点 y 插入结点
14、 x 之后 则需要执行以 下语句 华中理工大学 2000 一 4 2 分 4 在一个长度为 n 的顺序表中第 i 个元素 1 i0 DO BEGIN 2 3 4 5 read k END q next NIL END 北京师范大学 1999 三 21 已给如下关于单链表的类型说明 TYPE list node node RECORD data integer next list END 以下程序采用链表合并的方法 将两个已排序的单链表合并成一个链表而不改变其排序性 升序 这里两链表的头指针分别为 p 和 q PROCEDURE mergelink VAR p q list VAR h r li
15、st BEGIN 1 h next NIL r h WHILE pNIL AND qNIL DO IF p data q data THEN BEGIN 2 r p p p next END ELSE BEGIN 3 r q q q next END IF p NIL THEN r next q 4 p h next dispose h END 厦门大学 2000 三 2 8 分 22 假设链表 p 和链表 q 中的结点值都是整数 且按结点值的递增次序链接起来的带表头结 点的环形链表 各链表的表头结点的值为 max 且链表中其他结点的值都小于 max 在程序中 取 max 为 9999 在各个
16、链表中 每个结点的值各不相同 但链表 p 和链表 q 可能有值相同 的结点 表头结点除外 下面的程序将链表 q 合并到链表 p 中 使得合并后的链表是按结 点值递增次序链接起来的带表头结点的环形链表 且链表中各个结点的值各不相同 请在划 线处填上适当内容 每个框只填一个语句或一个表达式 链表的结点类型如下 TYPE nodeptr nodetype nodetype RECORD data integer link nodeptr END CONST max 9999 PROCEDURE merge VAR p nodeptr q nodeptr VAR r s nodeptr BEGIN r p WHILE A DO BEGIN WHILE r link dataq link data THEN BEGIN s C D s link s link E F s G END ELSE BEGIN H s q link I dispose s END END dispose q END 复旦大学 1997 五 18 分 23 PROC ins linklist la linkisttp i
