一、 判断题 1．线性表的逻辑顺序与存储顺序总是一致的。(FALSE) 2．顺序存储的线性表可以按序号随机存取。(TRUE) 3．顺序表的插入和删除一个数据元素，每次操作平均只有近一半的元素需要移动。 （TRUE） 4．线性表中的元素可以是各种各样的，但同一线性表中的数据元素具有相同的特性，因此是属于同一数据对象。（TRUE） 5．在线性表的顺序存储结构中，逻辑上相邻的两个元素在物理位置上并不一定紧邻。（FALSE） 6．在线性表的链式存储结构中，逻辑上相邻的元素在物理位置上不一定相邻。（TRUE） 7．线性表的链式存储结构优于顺序存储结构。（FALSE） 8．在线性表的顺序存储结构中，插入和删除时，移动元素的个数与该元素的位置有关。（TRUE） 9．线性表的链式存储结构是用一组任意的存储单元来存储线性表中数据元素的。（TRUE） 10．在单链表中，要取得某个元素，只要知道该元素的指针即可，因此，单链表是随机存取的存储结构。（FALSE） 二、 单选题、 (请从下列A，B，C，D选项中选择一项) 11．线性表是( ) 。 (A) 一个有限序列，可以为空； (B) 一个有限序列，不能为空； (C) 一个无限序列，可以为空； (D) 一个无序序列，不能为空。 答：A 12．对顺序存储的线性表，设其长度为n，在任何位置上插入或删除操作都是等 概率的。插入一个元素时平均要移动表中的（ ）个元素。 (A) n/2 (B) (n+1)/2 (C) (n –1)/2 (D) n 答：A 13．线性表采用链式存储时，其地址( D ) 。 (A) 必须是连续的； (B) 部分地址必须是连续的； (C) 一定是不连续的； (D) 连续与否均可以。 答：D 14．用链表表示线性表的优点是 （ ）。 (A)便于随机存取 (B)花费的存储空间较顺序存储少 (C)便于插入和删除 (D)数据元素的物理顺序与逻辑顺序相同 答：C 15. 某链表中最常用的操作是在最后一个元素之后插入一个元素和删除最后一个元素，则采用( )存储方式最节省运算时间。 (A)单链表 (B)双链表 (C)单循环链表 (D)带头结点的双循环链表 答：D 16. 循环链表的主要优点是( ) 。 (A)不再需要头指针了 (B)已知某个结点的位置后，能够容易找到他的直接前趋 (C)在进行插入、删除运算时，能更好的保证链表不断开 (D)从表中的任意结点出发都能扫描到整个链表 答：D 18. 单链表中，增加一个头结点的目的是为了（ ）。 (A) 使单链表至少有一个结点 (B)标识表结点中首结点的位置 （C）方便运算的实现 (D) 说明单链表是线性表的链式存储 答：C 19. 若某线性表中最常用的操作是在最后一个元素之后插入一个元素和删除第一个元素，则采用（ ）存储方式最节省运算时间。 (A) 单链表 (B) 仅有头指针的单循环链表 (C) 双链表 (D) 仅有尾指针的单循环链表 答：D 20. 若某线性表中最常用的操作是取第i个元素和找第i个元素的前趋元素，则采用（ ）存储方式最节省运算时间（B ）。 (A) 单链表 (B) 顺序表 (C) 双链表 (D) 单循环链表 答：B 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个结点的向量，建立一个有序单链表的时间复杂度_______。 A. O(1); B. O(n2); C. O(n ); D. O(nlog n); 答：C 四、算法设计题： 31. 有一个单链表（不同结点的数据域值可能相同），其头指针为head，编写一个函数计算数据域为x的结点个数。 提示：本题是遍历通过该链表的每个结点，每遇到一个结点，结点个数加1，结点个数存储在变量n中。 int count (head, x) {
/*本题中head 为链头指针，不含头结点*/ node *p; int n=0; p=head;
while (p!=NULL) {
if (p->data= =x) n++; p=p->next; }
return(n); }