发布时间 : 星期四 文章13994数据结构习题及参考答案更新完毕开始阅读0b72c50f76c66137ee061984
C．向量大小 D．基地址和结点大小
12. 在等概率情况下，顺序表的插入操作要移动___B___结点。 A．全部 B．一半 C．三分之一 D．四分之一 13. 在___C___运算中，使用顺序表比链表好。 A．插入 B．删除
C．根据序号查找 D．根据元素值查找
14. 在一个具有n个结点的有序单链表中插入一个新结点并保持该表有序的时间复杂度是___B____。
A．O(1) C．O(n2)
B．O(n) D．O(log2n)
15. 设有一个栈，元素的进栈次序为A, B, C, D, E,下列是不可能的出栈序列_____C_____。
A．A, B, C, D, E C．E, A, B, C, D
B．B, C, D, E, A D．E, D, C, B, A
16. 在一个具有n个单元的顺序栈中，假定以地址低端（即0单元）作为栈底，以top作为栈顶指针，当做出栈处理时，top变化为___C___。
A．top不变 B．top=0 C．top--
D．top++
17. 向一个栈顶指针为hs的链栈中插入一个s结点时，应执行__B____。 A．hs->next=s;
B．s->next=hs; hs=s;
C．s->next=hs->next;hs->next=s; D．s->next=hs; hs=hs->next;
18. 在具有n个单元的顺序存储的循环队列中，假定front和rear分别为队头指针和队尾指针，则判断队满的条件为___D____。
A．rear％n= = front B．（front+l）％n= = rear
C．rear％n -1= = front D．(rear+l)％n= = front
19. 在具有n个单元的顺序存储的循环队列中，假定front和rear分别为队头指针和队尾指针，则判断队空的条件为___C_____。
A．rear％n= = front B．front+l= rear C．rear= = front D．(rear+l)％n= front
20. 在一个链队列中，假定front和rear分别为队首和队尾指针，则删除一个结点的操
作为____Ａ____。
A．front=front->next B．rear=rear->next C．rear=front->next D．front=rear->next
二、填空题
1. 线性表是一种典型的___线性______结构。
2. 在一个长度为n的顺序表的第i个元素之前插入一个元素，需要后移__ｎ－ｉ＋１
-5-
__个元素。
3. 顺序表中逻辑上相邻的元素的物理位置____相邻____。
4. 要从一个顺序表删除一个元素时，被删除元素之后的所有元素均需___前移____一个位置，移动过程是从___前____向___后____依次移动每一个元素。
5. 在线性表的顺序存储中，元素之间的逻辑关系是通过__物理存储位置_____决定的；在线性表的链接存储中，元素之间的逻辑关系是通过___链域的指针值____决定的。 6. 在双向链表中，每个结点含有两个指针域，一个指向__前趋_____结点，另一个指向___后继____结点。
7. 当对一个线性表经常进行存取操作，而很少进行插入和删除操作时，则采用__顺序_____存储结构为宜。相反，当经常进行的是插入和删除操作时，则采用___链接____存储结构为宜。
8. 顺序表中逻辑上相邻的元素，物理位置__一定_____相邻，单链表中逻辑上相邻的元素，物理位置___不一定____相邻。
9. 线性表、栈和队列都是___线性____结构，可以在线性表的__任何____位置插入和删除元素；对于栈只能在___栈顶____位置插入和删除元素；对于队列只能在___队尾____位置插入元素和在___队头____位置删除元素。
10. 根据线性表的链式存储结构中每个结点所含指针的个数，链表可分为___单链表______和___双链表____；而根据指针的联接方式，链表又可分为___非循环链表_____和___循环链表______。
11. 在单链表中设置头结点的作用是__使空链表和非空链表统一，算法处理一致______。
12. 对于一个具有n个结点的单链表，在已知的结点p后插入一个新结点的时间复杂度为___Ｏ（１）___，在给定值为x的结点后插入一个新结点的时间复杂度为___Ｏ（ｎ）____。
13. 对于一个栈作进栈运算时，应先判别栈是否为___栈满____，作退栈运算时，应先判别栈是否为___栈空____，当栈中元素为m时，作进栈运算时发生上溢，则说明栈的可用最大容量为__ｍ_____。为了增加内存空间的利用率和减少发生上溢的可能性，由两个栈共享一片连续的内存空间时，应将两栈的__栈底_____分别设在这片内存空间的两端，这样只有当___两个栈的栈顶在栈空间的某一位置相遇____时才产生上溢。
14. 设有一空栈，现有输入序列1，2，3，4，5，经过push, push, pop, push, pop, push, push后，输出序列是___２，３______。
15. 无论对于顺序存储还是链式存储的栈和队列来说，进行插入或删除运算的时间复杂度均相同为__Ｏ（０）______。
-6-
习题3
一、单项选择题
1. 空串与空格字符组成的串的区别在于（B ）。
A.没有区别
C.两串的长度相等
B.两串的长度不相等
D.两串包含的字符不相同
2. 一个子串在包含它的主串中的位置是指（ D ）。
A.子串的最后那个字符在主串中的位置
B.子串的最后那个字符在主串中首次出现的位置 C.子串的第一个字符在主串中的位置 D.子串的第一个字符在主串中首次出现的位置 3. 下面的说法中，只有（ C ）是正确的。
A.字符串的长度是指串中包含的字母的个数
B.字符串的长度是指串中包含的不同字符的个数 C.若T包含在S中，则T一定是S的一个子串 D.一个字符串不能说是其自身的一个子串 4. 两个字符串相等的条件是（ D ）。
A.两串的长度相等
B.两串包含的字符相同
C.两串的长度相等，并且两串包含的字符相同 D.两串的长度相等，并且对应位置上的字符相同
5. 若SUBSTR（S，i，k）表示求S中从第i个字符开始的连续k个字符组成的子串的操作，则对于S=“Beijing＆Nanjing”，SUBSTR（S，4，5）=（ B ）。
A. “ijing” B. “jing＆”
C. “ingNa” D. “ing＆N”
6. 若INDEX（S，T）表示求T在S中的位置的操作，则对于S=“Beijing＆Nanjing”，T=“jing”，INDEX（S，T）=（ C ）。
A.2 B.3 C.4 D.5
7. 若REPLACE（S，S1，S2）表示用字符串S2替换字符串S中的子串S1的操作，则对于S=“Beijing＆Nanjing”，S1=“Beijing”，S2=“Shanghai”，REPLACE（S，S1，S2）=（ B ）。
A. “Nanjing＆Shanghai” B. “Nanjing＆Nanjing”
C. “ShanghaiNanjing” D. “Shanghai＆Nanjing” 8. 在长度为n的字符串S的第i个位置插入另外一个字符串，i的合法值应该是（ C ）。
A.i＞0 B. i≤n
C.1≤i≤n D.1≤i≤n+1
9. 字符串采用结点大小为1的链表作为其存储结构，是指（ D ）。
-7-
A.链表的长度为1
B.链表中只存放1个字符 C.链表的每个链结点的数据域中不仅只存放了一个字符 D.链表的每个链结点的数据域中只存放了一个字符
二、填空题
1. 计算机软件系统中，有两种处理字符串长度的方法：一种是____固定长度_______，第二种是_______设置长度指针____________。
2. 两个字符串相等的充要条件是__________两个串的长度相等___________和______对应位置的字符相等_____________。
3. 设字符串S1= “ABCDEF”，S2= “PQRS”，则运算S=CONCAT（SUB（S1，2，LEN（S2）），SUB（S1，LEN（S2），2））后的串值为_______ＢＣＤＥＤＥ____________。
4. 串是指________含ｎ个字符的有限序列（ｎ＞＝０）___________。
5. 空串是指_______不含任何字符的串____________，空格串是指______仅含空格字符的字符串_____________。
习题4 一、单项选择题
1. 设二维数组A[0…m-1][0…n-1]按行优先顺序存储在内存中，第一个元素的地址为p，每个元素占k个字节，则元素aij的地址为（ A ）。
A.p +[i*n+j-1]*k
C.p+[(j-1)*n+i-1]*k
B.p+[(i-1)*n+j-1]*k D.p+[j*n+i-1]*k
2. 已知二维数组A10×10中，元素a20的地址为560，每个元素占4个字节，则元素a10
的地址为（ A ）。
A.520 B.522 C.524 D.518 3. 若数组A[0…m][0…n]按列优先顺序存储，则aij地址为（ A ）。
A.LOC(a00)+[j*m+i] B. LOC(a00)+[j*n+i]
C.LOC(a00)+[(j-1)*n+i-1] D. LOC(a00)+[(j-1)*m+i-1]
4. 若下三角矩阵An×n，按列顺序压缩存储在数组Sa[0…(n+1)n/2]中，则非零元素aij
的地址为（ B ）。（设每个元素占d个字节）
A. [(j-1)*n-B. [(j-1)*n-C．[(j-1)*n-D．[(j-1)*n-(j?2)(j?1)2(j?2)(j?1)2(j?2)(j?1)2(j?2)(j?1)+i-1]*d +i]*d +i+1]*d +i-2]*d
25. 设有广义表D=(a,b,D)，其长度为（B ），深度为（ A ）。
-8-