精华复习题解答(记得老田上课说没题库这回事).docVIP

第一部分 复习题 8、判断下列叙述的对错。 (2) 线性表的顺序存储表示优于链式存储表示。 (3) 线性表若采用链式存储表示时所有结点之间存储单元的地址可连续可不连续。 (4) 二维数组是其数组元素为线性表的线性表。 (5) 每种数据结构都应具备三种基本运算：插入、删除和有哪些信誉好的足球投注网站。 解答： (2)错 (3)对 (4)错 (5)对 10、线性结构可用顺序表或链表存储。试问： (2) 若表的总数基本稳定，且很少进行插入和删除，但要求以最快的速度存取表中的元素，这时，应采用哪种存储表示？为什么？ 解答： (2)顺序表 12、填空题 一维数组的逻辑结构是( ① )，存储结构是( ② )。对于二维数组，有( ③ )和( ④ )两种不同的存储方式。对于一个二维数组A[m][n]，若采取按行存储的方式，则任一数组元素A[i][j]相对于A[0][0]的地址为( ⑤ )。 解答：①线性结构 ②顺序结构 ③按行存放 ④按列存放 ⑤ i*n+j 16、设单链表中结点的结构为（data, link）。已知指针q所指结点是指针p所指结点的直接前驱，若在*q与*p之间插入结点*s，则应执行下列哪一个操作？ (1) s-link = p-link; p-link = s; (2) q-link = s; s-link = p; (3) p-link = s-link; s-link = p; (4) p-link = s; s-link = q; 解答：(2) 17、设单链表中结点的结构为（data, link）。已知指针p所指结点不是尾结点，若在*p之后插入结点*s，则应执行下列哪一个操作？ (1) s-link = p; p-link = s; (2) s-link = p-link; p-link = s; (3) s-link = p-link; p = s; (4) p-link = s; s-link = p; 解答：(2) 19、在单链表、双向链表和单循环链表中，若仅知道指针p指向某一结点，不知道表头指针，能否将结点*p从链表中删去？若可以，其时间复杂度各为多少？ 解答：在双向链表和单循环链表中可以删除。 双向链表中删除*p的时间复杂度为O(1)； 单循环链表中删除*p的时间复杂度为O(n)， 其中n是链表中结点个数。 20、设单循环链表中结点的结构为（data, link），且rear是指向非空的带表头结点的单循环链表的尾结点的指针。若想删除链表第一个结点，则应执行下列哪一个操作？ s = rear; rear = rear-link; free(s); rear = rear-link; free(rear); rear = rear-link-link; free(rear); s = rear-link-link; rear-link-link = s-link; free(s); 解答：(4) 23、试回答下列问题： (1) 设整数1, 2, 3, 4, 5, 6依次进栈，则可能的出栈序列有多少种? (2) 若整数1, 2, 3, 4, 5, 6依次进栈，那么是否能够得到435612, 325641, 154623和135426的出栈序列。 解答：(1) (2) 435612, 154623不能得到 24、设有一个顺序栈S，元素s1, s2, s3, s4, s5, s6依次进栈，如果6个元素的出栈顺序为s2, s3, s4, s6, s5, s1，则顺序栈的容量至少应为多少？ 解答：s1, s2, 出s2; s1, s3, 出s3; s1, s4, 出s4; s1, s5, s6, 出s6; s1, s5, 出s5; s1, 出s1； 顺序栈的容量至少为3. 27、设循环队列的结构是 const int MaxSize = 100; typedef int DataType; typedef struct { DataType data[MaxSize]; int front, rear; } Queue; 若有一个Queue类型的队列Q，试问判断队列满的条件应是下列哪一个语句？ (1) Q.front == Q.rear; (2) Q.front - Q.rear == MaxSize; (3) Q.front + Q.rear == MaxSize; (4) Q.front == (Q.rear+1) % MaxSize; 解答：(4) 28、设循环队列的结构是