当前位置:首页 >> >> Ch2习题

Ch2习题


习题二
一、 判断题
1.线性表的逻辑顺序与存储顺序总是一致的。( ) 2.顺序存储的线性表可以按序号随机存取。( ) 3.顺序表的插入和删除一个数据元素,因为每次操作平均只有近一半的元素需 要移动。 ( ) 4.线性表中的元素可以是各种各样的,但同一线性表中的数据元素具有相同的 特性,因此是属于同一数据对象。 ( ) 5.在线性表的顺序存储结构中,逻辑上相邻的两个元素在物理位置上并不一定 紧邻。 ( ) 6.在线性表的链式存储结构中,逻辑上相邻的元素在物理位置上不一定相邻。 ( ) 7.线性表的链式存储结构优于顺序存储结构。 ( ) 8.在线性表的顺序存储结构中,插入和删除时,移动元素的个数与该元素的位 置有关。 ( ) 9. 线性表的链式存储结构是用一组任意的存储单元来存储线性表中数据元素的。 ( ) 10.在单链表中,要取得某个元素,只要知道该元素的指针即可,因此,单链表 是随机存取的存储结构。 ( )

二、 单选题、 (请从下列 A,B,C,D 选项中选择一项)
11.线性表是( ) 。 (A) 一个有限序列,可以为空; (B) 一个有限序列,不能为空; (C) 一个无限序列,可以为空; (D) 一个无序序列,不能为空。 12.对顺序存储的线性表,设其长度为 n,在任何位置上插入或删除操作都是等 概率的。插入一个元素时平均要移动表中的( )个元素。 (A) n/2 (B) (n+1)/2 (C) (n –1)/2 (D) n 13.线性表采用链式存储时,其地址( ) 。 (A) 必须是连续的; (B) 部分地址必须是连续的; (C) 一定是不连续的; (D) 连续与否均可以。 14.用链表表示线性表的优点是 ( ) 。 (A)便于随机存取 (B)花费的存储空间较顺序存储少 (C)便于插入和删除 (D)数据元素的物理顺序与逻辑顺序相同 15. 某链表中最常用的操作是在最后一个元素之后插入一个元素和删除最后一 个元素,则采用( )存储方式最节省运算时间。 (A)单链表 (B)双链表 (C)单循环链表 (D)带头结点的双循环链表
1

16. 循环链表的主要优点是( ) 。 (A)不再需要头指针了 (B)已知某个结点的位置后,能够容易找到他的直接前趋 (C)在进行插入、删除运算时,能更好的保证链表不断开 (D)从表中的任意结点出发都能扫描到整个链表 17. 下面关于线性表的叙述错误的是( )。 (A) 线性表采用顺序存储,必须占用一片地址连续的单元; (B) 线性表采用顺序存储,便于进行插入和删除操作; (C) 线性表采用链式存储,不必占用一片地址连续的单元; (D) 线性表采用链式存储,便于进行插入和删除操作; 18. 单链表中,增加一个头结点的目的是为了( ) 。 (A) 使单链表至少有一个结点 (B)标识表结点中首结点的位置 (C)方便运算的实现 (D) 说明单链表是线性表的链式存储 19. 若某线性表中最常用的操作是在最后一个元素之后插入一个元素和删除第 一个元素,则采用( )存储方式最节省运算时间。 (A) 单链表 (B) 仅有头指针的单循环链表 (C) 双链表 (D) 仅有尾指针的单循环链表 20. 若某线性表中最常用的操作是取第 i 个元素和找第 i 个元素的前趋元素,则 采用什么存储方式最节省运算时间( ) 。 (A) 单链表 (B) 顺序表 (C) 双链表 (D) 单循环链表 21. 一个向量(一种顺序表)第一个元素的存储地址是 100,每个元素的长度为 2, 则第 5 个元素的地址是 ( )。 A. 110 B. 108 C. 100 D. 120 22. 不带头结点的单链表 head 为空的判定条件是( ) 。 A. head = = NULL; B. head->next = = NULL; C. head->next = = head; D. head! = NULL; 23. 带头结点的单链表 head 为空的判定条件是( ) 。 A. head = = NULL; B. head->next = = NULL; C. head->next = = head; D. head! = NULL; 24. 在循环双链表的 p 所指结点之后插入 s 所指结点的操作是( ) 。 A. p->right=s; s->left=p; p->right->left=s; s=->right=p->right; B. p->right=s; p->right->left=s; s->left=p; s->right=p->right; C. s->left=p; s->right= p->right; p->right=s; p->right->left=s; D. s->left=p; s->right=p->right; p->right->left=s; p->right=s; 25. 在一个单链表中,已知 q 所指结点是 p 所指结点的前驱结点,若在 q 和 p 之 间插入 s 结点,则执行( ) 。 A. s->next=p->next; p->next=s; B. p->next=s->next; s->next=p; C. q->next=s; s->next=p; D. p->next=s; s->next=q; 26. 从一个具有 n 个结点的单链表中查找其值等于 x 结点时,在查找成功的情况 下,需平均比较( )个结点。 A. n; B. n/2; C. (n-1)/2; D. (n+1)/2;
2

27. 给定有 n 个结点的向量,建立一个有序单链表的时间复杂度( A. O(1); B. O(n); C. O(n 2 ); D. O(nlog 2 n);

) 。

三、 填空题
28. 在一个长度为 n 的向量中的第 i 个元素(1≤i≤n)之前插入一个元素时,需向 后移动_____个元素。 答: 29. 在一个长度为 n 的向量中删除第 i 个元素(1≤i≤n)时, 需向前移动_____个元 素。 答: 30.在一个单链表中 p 所指结点之后插入一个由指针 s 所指结点,可执行以下操 作: ___________________; ___________________;

四、算法设计题:
31. 有一个单链表(不同结点的数据域值可能相同) ,其头指针为 head,编写一 个函数计算数据域为 x 的结点个数。 解:本题是遍历通过该链表的每个结点,每遇到一个结点,结点个数加 1,结点 个数存储在变量 n 中。实现本题功能的函数如下: int count (head, x) node *head; DataType x; { /*本题中 head 为链头指针,不含头结点*/

} 32. 有一个有序单链表(从小到大排序) ,表头指针为 head,编写一个函数向该 单链表中插入一个元素为 x 的结点,使插入后该链表仍然有序。 解:本题算法的思想是先建立一个待插入的结点,然后依次与链表中的各结 点的数据域比较大小,找出该结点的位置,最后插入该结点。实现本题功能的函 数如下:
3

Node *insertorder(head, x) Node *head; DataType x; { /*本题中 head 为链头指针,不含头结点*/

} node *p, *q; { /*本题中 p、q 为链头指针,不含头结点。*/

33. 设有一个线性表 L,要求写出一个将该表逆置的算法。

4


更多相关文档:

习题二(ch2)

习题课-ch2 18页 1财富值 ch2-6习题 30页 免费如要投诉违规内容,请到百度文库投诉中心;如要提出功能问题或意见建议,请点击此处进行反馈。 ...

数据结构Ch2习题答案

Ch2 线性表 一.填空: 1.按顺序存储方法存储的线性表称为 的线表称为 链表 。。 n/2 个结点,在第 i i-1 i i+1… 顺序表 ,按链式存储方法存储 2....

CH2习题题目

CH2习题题目_五年级其它课程_其它课程_小学教育_教育专区。wo kao! hai yao xie jianjie第二章部分习题题目 2.3 掷一枚硬币定义一个随机过程: ?cos π t X...

高数ch2练习题

高数ch2练习题_理学_高等教育_教育专区。Ch1 第二次练习题一、选择题(3×6=18) 1. 函数 f(x)在 x = a 点连续是它在该点有定义的( )(A)充分条件 (...

CH2习题解答

CH2习题解答 隐藏>> 它们名称及作用如下: 2-1.答:Rose 主要支持 8 种不同类型的 UML 图,它们名称及作用如下: 1.答 ? 用例图(确定系统中所包含的参与者...

数据结构Ch2习题答案

习题及详细答案习题及详细答案隐藏>> Ch2 线性表 一.填空: 1.按顺序存储方法存储的线性表称为 顺序表 ,按链式存储方法存储的线表称为 链表 。。 2.线性表是...

Ch2习题参考答案

章一、 判断题 习题参考答案 1.线性表的逻辑顺序与存储顺序总是一致的。(ERROR) . 2.顺序存储的线性表可以按序号随机存取。(OK) . 3.顺序表的插入和...

高数上册ch2练习题解答

高数上册ch2练习题解答_理学_高等教育_教育专区。Ch1 第二次练习题一、选择题(6×3=18) 1. (A) 2(C) 3(D ) 4(A) 5(B) 6.(D) 二、判断题(3×...

常微分方程ch2练习题

常微分方程ch2练习题_理学_高等教育_教育专区。一、求解下列微分方程 dy 1、 dx 2、 ? y ln x dy ? y ln y dx dy x2 ? dx y 1 ? x 3 3、 ...

Ch2习题

材料力学Ch2 61页 免费 材料力学习题 22页 免费 2-2材料力学课件 10页 5财富值 材料力学 6页 5财富值如要投诉违规内容,请到百度文库投诉中心;如要提出功能问...
更多相关标签:
网站地图

文档资料共享网 nexoncn.com copyright ©right 2010-2020。
文档资料共享网内容来自网络,如有侵犯请联系客服。email:zhit325@126.com