第一章 数据结构习题参考答案
一、单项选择题
1．数据结构是一门研究非数值计算的程序设计问题中计算机的 ① 以及它们之间的 ② 和运算等的学科。
① A. 数据元素 B. 计算方法 C. 逻辑存储 D. 数据映象 ② A. 结构 B. 关系 C. 运算 D. 算法 答：① A ② B 2．数据结构被形式地定义为(K,R),其中K是 ① 的有限集，R是K上的 ② 有限集。
① A. 算法 B. 数据元素 C. 数据操作 D. 逻辑结构 ② A. 操作 B. 映象 C. 存储 D. 关系 答：① B ② D
3．在数据结构中，从逻辑上可以把数据结构分成________。
A. 动态结构和静态结构 B. 紧凑结构和非紧凑结构 C. 线性结构和非线性结构 D. 内部结构和外部结构 答：C
4．算法分析的目的是 ① ，算法分析的两个主要方面是 ② 。 ① A. 找出数据结构的合理性 B. 研究算法中的输入和输出的关系 C. 分析算法的效率以求改进 D. 分析算法的易懂性和文档性 ② A. 空间复杂度和时间复杂度 B. 正确性和简单性
C. 可读性和文档性 D. 数据复杂性和程序复杂性 答：① A ② A
5．计算机算法指的是 ① ，它必须具备输入、输出和 ② 等5个特性。
① A. 计算方法 B. 排序方法 C. 解决问题的有限运算序列 D. 调度方法 ② A. 可执行性、可移植性和可扩充性
B. 可行性、确定性和有穷性 C. 确定性、有穷性和稳定性 易读性、稳定性和安全性 答：① C ② B
二、简述下列概念
数据，数据元素，数据类型，数据结构，逻辑结构，存储结构，线性结构，非线性结构。
答：数据——是对客观事物的符号表示，在计算机科学中是指所有能输入到计算机中边被计算机程序处理的符号的总称。
数据元素——数据的基本单位，在计算机程序中通常做为一个整体进行考虑和处理。
数据类型——是具有相同性质的计算机数据的集合及在这个数据上的一组运算，是和数据结构密切相关的概念。
数据结构——是相互之间存在一种或多种特定关系的数据元素的集合。
1
逻辑结构——数据元素之间的逻辑关系的描述，称为数据的逻辑结构。 存储结构——数据结构在计算机中的表示称为数据的物理结构，又称存储结构。
线性结构——结构中的数据元素之间存在一个对一个的关系。
非线性结构——我们也可以将树形结构、集合和网状结构归纳为非线性结构。
三、填空题
1．下面程序段的时间复杂度是_______。 For (i=0;i 2．下面程序段的时间复杂度是_______。 i=s=0 While(s i++; /* i=i+1 */ s+=i; /* s=s+i */ } 答：O(n) 3．下面程序段的时间复杂度是_______。 s=0; for (i=0;i 4．下面程序段的时间复杂度是_______。 i=1; While (i<=n) i=i*3; 答：log3n 第二章 习题参考答案 一、 判断题 1．线性表的逻辑顺序与存储顺序总是一致的。(ERROR) 2．顺序存储的线性表可以按序号随机存取。(OK) 3．顺序表的插入和删除一个数据元素，因为每次操作平均只有近一半的元素需 2 要移动。 （OK） 4．线性表中的元素可以是各种各样的，但同一线性表中的数据元素具有相同的特性，因此是属于同一数据对象。（OK） 5．在线性表的顺序存储结构中，逻辑上相邻的两个元素在物理位置上并不一定紧邻。（ERROR） 6．在线性表的链式存储结构中，逻辑上相邻的元素在物理位置上不一定相邻。（OK） 7．线性表的链式存储结构优于顺序存储结构。（ERROR） 8．在线性表的顺序存储结构中，插入和删除时，移动元素的个数与该元素的位置有关。（OK） 9．线性表的链式存储结构是用一组任意的存储单元来存储线性表中数据元素的。（OK） 10．在单链表中，要取得某个元素，只要知道该元素的指针即可，因此，单链表是随机存取的存储结构。（ERROR） 二、 单选题、 (请从下列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) 线性表采用顺序存储，便于进行插入和删除操作； 3 (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，则第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个结点的向量，建立一个有序单链表的时间复杂度_______。 4 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 30．在一个单链表中p所指结点之前插入一个由指针s所指结点，可执行以下操作： s->next=__p->next_____; p->next=s; t=p->data; p->data=___s->data________; s->data=___t________; 四、算法设计题： 31. 有一个单链表（不同结点的数据域值可能相同），其头指针为head，编写一个函数计算数据域为x的结点个数。 解：本题是遍历通过该链表的每个结点，每遇到一个结点，结点个数加1，结点个数存储在变量n中。实现本题功能的函数如下： int count (head, x) node *head; ElemType x; { /*本题中head 为链头指针，不含头结点*/ node *p; int n=0; p=head; while (p!=NULL) { if (p->data= =x) n++; p=p->next; } return(n); } 32. 有一个有序单链表（从小到大排序），表头指针为head，编写一个函数向该单链表中插入一个元素为x的结点，使插入后该链表仍然有序。 解：本题算法的思想是先建立一个待插入的结点，然后依次与链表中的各结 5