第二章 线性表 一 选择题 1. 线性表是 ( ) A. 一个有限序列, 可以为空 B. 一个有限序列, 不能为空 C. 一个有限序列, 可以为空 D. 一个无序序列, 不能为空 2. 对顺序存储的线性表, 设其长度为 n, 在任何位置上插入或删除操作都是等概率 插入一个元素 时大约要移动表中的 ( ) 个元素, 删除一个元素时大约要移动表中的 ( ) 个元素 A. n/2 B. (n+1)/2 C. (n-1)/2 D. n E. n+1 F. n-1 3. 线性表采用链式存储时, 其地址 ( ) A. 必须是连续的 B. 部分地址必须是连续的 C. 一定是不连续的 D. 连续与否均可以 4. 设单链表中指针 p 指着结点 M, 指针 f 指着将要插入的新结点 X, 问 : (1) 当 X 插在链表中两个数据元素 M 和 N 之间时, 只要先修改 ( ) 后修改 ( ) 即可 A. p->next=f B. p->next=p->next->next C. p->next=f->next D. f->next=p->next E. f->next=null F. f->next=p (2) 在链表中最后一个结点 M 之后时, 只要先修改 ( ) 后修改 ( ) 即可 A. f->next=p B. f->next=p->next C. p->next=f D. p->next=f->next E. f=null 5. 在单循环链表中指针 p 指向结点 A, 若要删除 A 之后的结点 ( 存在 ) 则指针的操作方式为 ( ) A. p->next=p->next->next B. p=p->next C. p=p->next->next D. next=p 6. 在双向链表存储结构中 : (1) 删除 p 所指的结点时需如何修改指针 ( ) (2) 删除 p 所指的结点的前驱结点 ( 若存在 ) 时需如何修改指针 ( ) (3) 删除 p 所指的结点的后继结点时, 指针的修改为 ( ) A. p->prior->next=p->next p->next->prior=p->prior B. p->prior=p->prior->next p->prior->prior-next=p C. p->prior->prior->next=p p->prior=p->prior->prior D. p->next->next->prior=p p->next=p->next->next 7. 在双向循环链表中, 在 p 所指的结点之后插入指针 f 所指的新结点, 其操作步骤是 ( ) A. p->next=f; f->prior=p; p->next->prior=f; f->next=p->next; B. p->next=f; p->next->prior=f; f->prior=p; f->next=p->next; C. f->prior=p; f->next=p->next; p->next=f; p->next->prior=f; D. f->prior=p; f->next=p->next; p->next->prior=f; p->next=f; 8. 不带头结点的单链表 head 为空的判定条件是 ( ) A. head==null B. head->next==null C. head->next==head D. head!=null 9. 带头结点的单链表 head 为空的判定条件是 ( ) A. head==null B. head->next==null C. head->next==head D. head!=null 10. 非空的循环单链表 head 的尾结点 ( 由 p 所指向 ) 满足 ( ) A. p->next==null B. p==null C. p->next==head D. p==head 11. 从一个具有 n 个结点的单链表中查找其值等于 x 的结点时, 在查找成功的情况下需平均比较 ( ) 个结点 A. n B. n/2 C. (n-1)/2 D. (n+1)/2 12. 在一个具有 n 个结点的有序单链表中插入一个新结点, 并仍然有序的时间复杂度为 ( ) A. O(1) B. O(n) C. O(n 2 ) D. O(nlog 2 n) - 1 -
13. 给定有 n 个元素的向量, 建立一个有序的单链表的时间复杂度为 ( ) A. O(1) B. O(n) C. O(n 2 ) D. O(nlog 2 n) 14. 如果线性表的总数基本稳定并很少进行插入和删除, 现要求以最快的速度存取线性表中的元素, 则应该选用线性表的 ( ) 存储结构 A. 顺序 B. 链式 C. 索引 D. 散列 15. 若 n 个线性表同时并存, 在处理过程中, 各表的长度和线性表的总数会自动变化, 在此情况下 应选用 ( ) 存储结构 A. 顺序 B. 链式 C. 索引 D. 散列 16. 每个结点只有一个指针的线性表是 ( ) A. 循环链表 B. 单链表 C. 双向链表 D. 线性链表 17. ( ) 表示表的第一个结点 A. 头指针 B. 头结点 C. 首结点 D. 头指针变量 18. ( ) 仅由一个尾指针就能访问链表上任何一个结点 A. 单链表 B. 循环链表 C. 循环单链表 D. 双向链表 19. 一维数组与线性表的特征是 ( ) A. 前者长度固定, 后者长度可变 B. 两者长度均固定 C. 后者长度固定, 前者长度可变 D. 两者长度均可变 20. 用链表表示线性表的优点是 ( ) A. 便于随机存取 B. 便于进行插入和删除操作 C. 占用的存储空间较顺序表少 D. 元素的物理顺序与逻辑顺序相同 21. 线性表采用顺序存储的缺点是 ( ) A. 存储密度低 B. 只能顺序访问 C. 元素的逻辑顺序与物理顺序不一致 D. 插入 删除操作效率低 22. 以下链表结构中, 从当前结点出发能够访问到任一结点的是 ( ) A. 单向链表和双向链表 B. 双向链表和循环链表 C. 单向链表和循环链表 D. 单向链表 双向链表和循环链表 23. 线性表是具有 n 个 ( ) 的有限序列 A. 数据项 B. 数据元素 C. 表元素 D. 字符 24. 若长度为 n 的线性表采用链式存储结构, 访问其第 i 个元素的算法时间复杂度为 ( ) A. O(1) B. O(n) C. O(n 2 ) D. O(log 2 n) 25. 以下对单链表的叙述错误的是 ( ) A. 单链表中每个结点都由存放结点值的数据域和存放直接后继结点地址信息的指针域两部分 组成 B. 从单链表的第 I 个结点出发, 可以访问到链表中的任何一个结点 C. 在单链表结构中加入头结点可以简化结点的插入和删除操作 D. 单链表尾结点的指针域应置成空指针 26. 以下对双向链表叙述错误的是 ( ) A. 双向链表的每个结点必定有两个指针域 B. 除首 尾结点外, 某一结点的地址既存储在其前驱结点的后继指针域中, 又存储在其后继结 点的前驱指针域中 C. 双向链表结点进行插入 删除操作所涉及的指针域变化与单链表相同 D. 从双向链表的任何一个结点出发都能访问到表中的其他结点 27. 以下叙述中正确的是 ( ) A. 线性表的链式存储结构优于顺序存储结构 B. 线性表的存储结构不影响其各种运算的实现 - 2 -
C. 选择线性表的存储结构就是要保证存储其各个元素的值 D. 顺序存储属于静态结构, 链式存储属于动态结构 28. 有如下函数 : void fun(struct node h1, struct node h2) { struct node *t; t=h1; while (t->next!= \0 ) t=t->next; t->next=h2; 其中形参 h1 和 h2 分别指向 2 个不同链表的第一个结点, 此函数的功能是 ( ) A. 将链表 h2 接到链表 h1 后 B. 将链表 h1 接到链表 h2 后 C. 找到链表 h1 的最后一个结点由指针返回 D. 将链表 h1 拆分成两个链表 二 填空题 1. 在一个长度为 n 的顺序线性表 (1<=I<=n) 的第 I 个元素之前插入一个元素需向后移动个元素 2. 在长度为 n 的顺序线性表中, 把第 I 个元素删除, 需向前移动个元素 3. 带有头结点 head 的单链表为空的条件是 4. 非空循环单链表 head 的尾结点 ( 由 p 指向 ) 满足条件 5. 在一个具有 n 个结点的单链表中, 在已知 S 所指结点之后插入一个新结点的时间复杂度是 ; 在给定值为 m 的结点后插入一个新结点的时间复杂度为 6. 把下面求单链表中数据域为 x 的结点个数的程序补充完整 Int count(head,x) Node *head; Elemtype x; int n=0; p=head; while (p!=null) { if ( ) n++; p=p->next; return(n); 7. 在一个具有 n 个结点的有序单链表中插入一个新结点, 使得数据仍然有序, 其算法时间复杂度为 8. 把下面求循环单链表长度的程序补充完整 Int length(head) Node *head - 3 -
int n=0; if ( ) n=0; else { p=head->next; n=1; while (p!=head) { ; n++; return(n); 9. 把下面在头指针为 head 的双链表中查找元素值为 x 的程序补充完整 Void find(head,x) Node *head Int x; ; while ( ) p=p->next; if (p!=null) printf( 结点找到了!\n ); else printf( 结点未找到!\n ); 10. 把下面删除单链表中重复的结点的程序补充完整 Void delete(lrlist L) { Lnode *p,*q,*l; Elemtype m; p=l; while (p->next!=null) { m=p->next->data; q=p; while (q->next!=null) if ( ) {l=q->next; ; free(l); p=p->next; 11. 常用链表有 和, 单链表中又包含, 双链表中包 含 - 4 -
12. 是一种最常用最简单的数据结构 13. 每个结点只包含一个指针域的线性表叫 14. 反映双向链表的语句对描述为 15. 线性表具有 和 两种存储结构 16. 建立单链表的算法时间复杂度为 ; 建立有序单链表的算法时间复杂度为 三 判断题 1. 顺序存储的线性表可以随机存取 ( ) 2. 顺序存储的线性表的插入和删除操作不需要付出很大的代价, 因为平均每次操作只有近一半的元素需要移动 ( ) 3. 由于顺序存储要求连续的存储区域, 所以在存储管理上不够灵活 ( ) 4. 线性表中的元素可以是各种各样的, 但同一线性表中的数据元素具有相同的特性, 因此是属于同一数据对象 ( ) 5. 在线性表的顺序存储结构中, 逻辑上相邻的两个元素但是在物理位置上并不一定是相邻的 ( ) 6. 在线性表的链式存储结构中, 逻辑上相邻的元素在物理位置上不一定相邻 ( ) 7. 在单链表中, 任何两个元素的存储位置之间都有固定的联系, 因为可以从头结点进行查找任何一个元素 ( ) 8. 线性表的链式存储结构优于顺序存储结构 ( ) 9. 在线性表的顺序存储结构中, 插入和删除元素时, 移动元素的个数与该元素的位置有关 ( ) 10. 线性表的链式存储结构的特点是用一组任意的存储单元存储线性表的数据元素 ( ) 11. 在单链表中, 要取得某个元素, 只要知道该元素的指针即可, 因此, 单链表是随机存取的存储结构 ( ) 12. 顺序存储结构属于静态结构, 链式结构属于动态结构 ( ) 13. 顺序存储方式只能用于存储线性结构 ( ) 14. 顺序存储方式的优点是存储密度大, 且插入 删除运算效率高 ( ) 15. 链表的每个结点中都恰好包含一个指针 ( ) 四 算法设计 1. 设计算法 : 输出带有头结点的单向链表中各结点的值 2. 设有带头结点的单向链表,head 为指向头结点的指针 设计算法 : 实现在值为 x 的结点前插入值为 y 的结点 若值为 x 的结点不存在, 则将值为 y 的结点插在链表的最后, 作为尾结点 - 5 -