习题一
一、单项选择题
1．数据结构是一门研究非数值计算的程序设计问题中计算机的 ① 以及它们之间的 ② 和运算等的学科。
① A. 数据元素 B. 计算方法 C. 逻辑存储 D. 数据映象 ② A. 结构 B. 关系 C. 运算 D. 算法 2．数据结构被形式地定义为(K,R),其中K是 ① 的有限集，R是K上的 ② 有限集。
① A. 算法 B. 数据元素 C. 数据操作 D. 逻辑结构 ② A. 操作 B. 映象 C. 存储 D. 关系 3．在数据结构中，从逻辑上可以把数据结构分成________。
A. 动态结构和静态结构 B. 紧凑结构和非紧凑结构 C. 线性结构和非线性结构 D. 内部结构和外部结构
4．算法分析的目的是 ① ，算法分析的两个主要方面是 ② 。
① A. 找出数据结构的合理性 B. 研究算法中的输入和输出的关系 C. 分析算法的效率以求改进 D. 分析算法的易懂性和文档性 ② A. 空间复杂度和时间复杂度 B. 正确性和简单性
C. 可读性和文档性 D. 数据复杂性和程序复杂性
5．计算机算法指的是 ① ，它必须具备输入、输出和 ② 等5个特性。
① A. 计算方法 B. 排序方法 C. 解决问题的有限运算序列 D. 调度方法 ② A. 可执行性、可移植性和可扩充性
B. 可行性、确定性和有穷性 C. 确定性、有穷性和稳定性 易读性、稳定性和安全性
二、简述下列概念
数据，数据元素，数据类型，数据结构，逻辑结构，存储结构，线性结构，非线性结构。
三、填空题
1．下面程序段的时间复杂度是_______。 For (i=0;i 2．下面程序段的时间复杂度是_______。 i=s=0 1 While(s i++; /* i=i+1 */ s+=i; /* s=s+i */ } 3．下面程序段的时间复杂度是_______。 s=0; for (i=0;i 4．下面程序段的时间复杂度是_______。 i=1; While (i<=n) i=i*3; 第二章 习题参考答案 一、 判断题 1．线性表的逻辑顺序与存储顺序总是一致的。(ERROR) 2．顺序存储的线性表可以按序号随机存取。(OK) 3．顺序表的插入和删除一个数据元素，因为每次操作平均只有近一半的元素需要移动。 （OK） 4．线性表中的元素可以是各种各样的，但同一线性表中的数据元素具有相同的特性，因此是属于同一数据对象。（OK） 5．在线性表的顺序存储结构中，逻辑上相邻的两个元素在物理位置上并不一定紧邻。（ERROR） 6．在线性表的链式存储结构中，逻辑上相邻的元素在物理位置上不一定相邻。（OK） 7．线性表的链式存储结构优于顺序存储结构。（ERROR） 8．在线性表的顺序存储结构中，插入和删除时，移动元素的个数与该元素的位置有关。（OK） 9．线性表的链式存储结构是用一组任意的存储单元来存储线性表中数据元素的。（OK） 10．在单链表中，要取得某个元素，只要知道该元素的指针即可，因此，单链表是随机存取的存储结构。（ERROR） 2 二、 单选题、 (请从下列A，B，C，D选项中选择一项) 11．线性表是( A ) 。 (A) 一个有限序列，可以为空； (B) 一个有限序列，不能为空； (C) 一个无限序列，可以为空； (D) 一个无序序列，不能为空。 12．对顺序存储的线性表，设其长度为n，在任何位置上插入或删除操作都是等概率的。插入一个元素时平均要移动表中的（A）个元素。 (A) n/2 (B) (n+1)/2 (C) (n –1)/2 (D) n 13．线性表采用链式存储时，其地址( D ) 。 (A) 必须是连续的； (B) 部分地址必须是连续的； (C) 一定是不连续的； (D) 连续与否均可以。 14．用链表表示线性表的优点是 （C ）。 (A)便于随机存取 (B)花费的存储空间较顺序存储少 (C)便于插入和删除 (D)数据元素的物理顺序与逻辑顺序相同 15. 某链表中最常用的操作是在最后一个元素之后插入一个元素和删除最后一个元素，则采用( D )存储方式最节省运算时间。 (A)单链表 (B)双链表 (C)单循环链表 (D)带头结点的双循环链表 16. 循环链表的主要优点是( D ) 。 (A)不再需要头指针了 (B)已知某个结点的位置后，能够容易找到他的直接前趋 (C)在进行插入、删除运算时，能更好的保证链表不断开 (D)从表中的任意结点出发都能扫描到整个链表 17. 下面关于线性表的叙述错误的是( B )。 (A) 线性表采用顺序存储，必须占用一片地址连续的单元； (B) 线性表采用顺序存储，便于进行插入和删除操作； (C) 线性表采用链式存储，不必占用一片地址连续的单元； (D) 线性表采用链式存储，便于进行插入和删除操作； 18. 单链表中，增加一个头结点的目的是为了（C ）。 (A) 使单链表至少有一个结点 (B)标识表结点中首结点的位置 （C）方便运算的实现 (D) 说明单链表是线性表的链式存储 19. 若某线性表中最常用的操作是在最后一个元素之后插入一个元素和删除第一个元素，则采用（D ）存储方式最节省运算时间。 (A) 单链表 (B) 仅有头指针的单循环链表 (C) 双链表 (D) 仅有尾指针的单循环链表 20. 若某线性表中最常用的操作是取第i个元素和找第i个元素的前趋元素，则采用（ ）存储方式最节省运算时间（B ）。 (A) 单链表 (B) 顺序表 (C) 双链表 (D) 单循环链表 21. 一个向量(一种顺序表)第一个元素的存储地址是100，每个元素的长度为2， 3 则第5个元素的地址是_______。 A. 110 B. 108 C. 100 D. 120 答：B [第5个元素的地址=100+2*(5-1)=108] 22. 不带头结点的单链表head为空的判定条件是______。 A. head = = NULL; B. head->next = = NULL; C. head->next = = head; D. head! = NULL; 答：A 23. 带头结点的单链表head为空的判定条件是______。 A. head = = NULL; B. head->next = = NULL; C. head->next = = head; D. head! = NULL; 答：B 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; 答：D 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; 答：C 26. 从一个具有n个结点的单链表中查找其值等于x结点时，在查找成功的情况下，需平均比较_____个结点。(参见网上讲义：1.4.2例1_5) A. n; B. n/2; C. (n-1)/2; D. (n+1)/2; 答：D 27. 给定有n个结点的向量，建立一个有序单链表的时间复杂度_______。 A. O(1); B. O(n); C. O(n2); D. O(nlog2n); 答：C 三、 填空题 28. 在一个长度为n的向量中的第i个元素(1≤i≤n)之前插入一个元素时，需向后移动_____个元素。 答：n-i+1 29. 在一个长度为n的向量中删除第i个元素(1≤i≤n)时，需向前移动_____个元素。 答：n-i 4
