〈新〉精华复习题解答.doc

第一部分 复习题 8、判断下列叙述的对错。 (1) 线性表的逻辑顺序与物理顺序总是一致的。 (2) 线性表的顺序存储表示优于链式存储表示。 (3) 线性表若采用链式存储表示时所有结点之间存储单元的地址可连续可不连续。 (4) 二维数组是其数组元素为线性表的线性表。 (5) 每种数据结构都应具备三种基本运算：插入、删除和有哪些信誉好的足球投注网站。 解答：(1)错 (2)错 (3)对 (4)错 (5)对 10、线性结构可用顺序表或链表存储。试问： (1) 如果有n个表同时并存，并且在处理过程中各表的长度会动态发生变化，表的总数也可能自动改变、在此情况下，应选用哪种存储表示？为什么？ (2) 若表的总数基本稳定，且很少进行插入和删除，但要求以最快的速度存取表中的元素，这时，应采用哪种存储表示？为什么？ 解答：(1)链表 (2)顺序表 12、填空题 一维数组的逻辑结构是( ① )，存储结构是( ② )。对于二维数组，有( ③ )和( ④ )两种不同的存储方式。对于一个二维数组A[m][n]，若采取按行存储的方式，则任一数组元素A[i][j]相对于A[0][0]的地址为( ⑤ )。 解答：①线性结构 ②顺序结构 ③按行存放 ④按列存放 ⑤ i*n+j 13、设有一个10(10的对称矩阵A[10][10]，采取按行压缩存储的方式存放于一个一维数组B[ ]中，则数组B[ ]的容量应有多大？若设A[0][0]为第一个元素，存放于B[0]，且数组A[ ][ ]的每一个数组元素在数组B[ ]中占一个数组元素位置，则A[8][5]在数组B[ ]中的地址是多少？ 解答：B[ ]的容量为10*(10+1)/2 = 55。 下三角方式：8*(8+1)/2+5 = 41 上三角方式：(2*10-5-1)*5/2+8 = 43 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) 22、设双向循环链表中结点的结构为（data, prior, next），且不带表头结点。若想在指针p所指结点之后插入指针s所指结点，则应执行下列哪一个操作？ p-next = s; s-prior = p; p-next-prior = s; s-next = p-next; p-next = s; p-next-prior = s; s-prior = p; s-next = p-next; s-prior = p; s-next = p-next; p-next = s; p-next-prior = s; s-prior = p; s-next = p-next; p-next-prior = s; p-next = s; 解答：(4)