《[2017年整理]数据结构复习指导》由会员分享，可在线阅读，更多相关《[2017年整理]数据结构复习指导（13页珍藏版）》请在金锄头文库上搜索。
1、数据结构复习指导一、单项选择题1. 数据结构是指（ A ） 。A.数据元素的组织形式 B.数据类型 C.数据存储结构 D.数据定义2. 数据在计算机存储器内表示时，物理地址与逻辑地址不相同的，称之为（ C ） 。A.存储结构 B.逻辑结构 C.链式存储结构 D.顺序存储结构3. 树形结构是数据元素之间存在一种（ D ） 。A.一对一关系 B.多对多关系 C.多对一关系 D.一对多关系4. 设语句 x+的时间是单位时间，则以下语句的时间复杂度为（ B ） 。for(i=1; inext=s; s-prior=p;p-next-prior=s; s-next=p-next;B s-prior=p;
2、 s-next=p-next;p-next=s; p-next-prior=s;C p-next=s; p-next-prior=s;s-prior=p; s-next=p-next;D s-prior=p; s-next=p-next;p-next-prior=s; p-next=s; 6. 设单链表中指针 p 指向结点 m，若要删除 m 之后的结点（若存在） ，则需修改指针的操作为_A_。Ap-next=p-next-next; Bp=p-next;Cp=p-next-next; Dp-next=p;7. 在一个长度为 n 的顺序表中向第 i 个元素(0next=p-next; p-nex
3、t=s Bq-next=s; s-next=pCp-next=s-next; s-next=p Dp-next=s; s-next=q9. 以下关于线性表的说法不正确的是_B_ 。 A线性表中的数据元素可以是数字、字符、记录等不同类型。B线性表中包含的数据元素个数不是任意的。C线性表中的每个结点都有且只有一个直接前趋和直接后继。D存在这样的线性表：表中各结点都没有直接前趋和直接后继。10. 线性表的顺序存储结构是一种_A_ 的存储结构。 A随机存取 B顺序存取 C索引存取 D散列存取11. 在顺序表中，只要知道_D_ ，就可在相同时间内求出任一结点的存储地址。A基地址 B结点大小 C向量大小
4、D基地址和结点大小12. 在等概率情况下，顺序表的插入操作要移动_B_结点。 A全部 B一半 C三分之一 D四分之一13. 在_C_运算中，使用顺序表比链表好。 A插入 B删除 C根据序号查找 D根据元素值查找14. 在一个具有 n 个结点的有序单链表中插入一个新结点并保持该表有序的时间复杂度是_B_。 AO(1) BO(n) CO(n 2) DO(log2n)15. 设有一个栈，元素的进栈次序为 A, B, C, D, E,下列是不可能的出栈序列_C_。AA, B, C, D, E BB, C, D, E, A CE, A, B, C, D DE, D, C, B, A 16. 在一个具有
5、n 个单元的顺序栈中，假定以地址低端（即 0 单元）作为栈底，以 top 作为栈顶指针，当做出栈处理时，top 变化为_C_。Atop 不变 Btop=0 Ctop- Dtop+17. 向一个栈顶指针为 hs 的链栈中插入一个 s 结点时，应执行_。Ahs-next=s; Bs-next=hs; hs=s;Cs-next=hs-next;hs-next=s; Ds-next=hs; hs=hs-next;18. 在具有 n 个单元的顺序存储的循环队列中，假定 front 和 rear 分别为队头指针和队尾指针，则判断队满的条件为_。Arearn= = front B （front+l）n= =
6、 rearCrearn -1= = front D(rear+l)n= = front19. 在具有 n 个单元的顺序存储的循环队列中，假定 front 和 rear 分别为队头指针和队尾指针，则判断队空的条件为_。Arearn= = front Bfront+l= rearCrear= = front D(rear+l)n= front20. 在一个链队列中，假定 front 和 rear 分别为队首和队尾指针，则删除一个结点的操作为_。Afront=front-next Brear=rear-nextCrear=front-next Dfront=rear-next二、填空题 1. 线性表
7、是一种典型的_结构。2. 在一个长度为 n 的顺序表的第 i 个元素之前插入一个元素，需要后移_个元素。3. 顺序表中逻辑上相邻的元素的物理位置_。4. 要从一个顺序表删除一个元素时，被删除元素之后的所有元素均需_一个位置，移动过程是从_向_依次移动每一个元素。5. 在线性表的顺序存储中，元素之间的逻辑关系是通过_决定的；在线性表的链接存储中，元素之间的逻辑关系是通过_决定的。6. 在双向链表中，每个结点含有两个指针域，一个指向_结点，另一个指向_结点。7. 当对一个线性表经常进行存取操作，而很少进行插入和删除操作时，则采用_存储结构为宜。相反，当经常进行的是插入和删除操作时，则采用_存储结构
8、为宜。8. 顺序表中逻辑上相邻的元素，物理位置_相邻，单链表中逻辑上相邻的元素，物理位置_相邻。9. 线性表、栈和队列都是_结构，可以在线性表的_位置插入和删除元素；对于栈只能在_位置插入和删除元素；对于队列只能在_位置插入元素和在_位置删除元素。10. 根据线性表的链式存储结构中每个结点所含指针的个数，链表可分为_和_；而根据指针的联接方式，链表又可分为_和_。11. 在单链表中设置头结点的作用是_。12. 对于一个具有 n 个结点的单链表，在已知的结点 p 后插入一个新结点的时间复杂度为_，在给定值为 x 的结点后插入一个新结点的时间复杂度为_。13. 对于一个栈作进栈运算时，应先判别栈是
9、否为_，作退栈运算时，应先判别栈是否为_，当栈中元素为 m 时，作进栈运算时发生上溢，则说明栈的可用最大容量为_。为了增加内存空间的利用率和减少发生上溢的可能性，由两个栈共享一片连续的内存空间时，应将两栈的_分别设在这片内存空间的两端，这样只有当_时才产生上溢。14. 设有一空栈，现有输入序列 1，2，3，4，5，经过 push, push, pop, push, pop, push, push 后，输出序列是_。15. 无论对于顺序存储还是链式存储的栈和队列来说，进行插入或删除运算的时间复杂度均相同为_。习题 2 参考答案一、单项选择题1A 2A 3D 4C 5D 6A 7B 8B 9C 1
10、0A 11D 12B 13C 14B 15C 16C 17B 18D 19C 20A二、填空题1线性 2n-i+1 3相邻 4前移，前，后 5物理存储位置，链域的指针值 6前趋，后继 7顺序，链接 8一定，不一定 9线性，任何，栈顶，队尾，队头10单链表，双链表，非循环链表，循环链表 11使空表和非空表统一；算法处理一致12O(1)，O(n) 13栈满，栈空，m ，栈底，两个栈的栈顶在栈空间的某一位置相遇142、3 15O(1)第 3 章 串一、单项选择题1. 空串与空格字符组成的串的区别在于（ ） 。A.没有区别 B.两串的长度不相等C.两串的长度相等 D.两串包含的字符不相同2. 一个子串
11、在包含它的主串中的位置是指（ ） 。A.子串的最后那个字符在主串中的位置 B.子串的最后那个字符在主串中首次出现的位置C.子串的第一个字符在主串中的位置 D.子串的第一个字符在主串中首次出现的位置3. 下面的说法中，只有（ ）是正确的。A.字符串的长度是指串中包含的字母的个数 B.字符串的长度是指串中包含的不同字符的个数C.若 T 包含在 S 中，则 T 一定是 S 的一个子串 D.一个字符串不能说是其自身的一个子串4. 两个字符串相等的条件是（ ） 。A.两串的长度相等 B.两串包含的字符相同C.两串的长度相等，并且两串包含的字符相同 D.两串的长度相等，并且对应位置上的字符相同5. 若 S
12、UBSTR（S ，i，k）表示求 S 中从第 i 个字符开始的连续 k 个字符组成的子串的操作，则对于S=“BeijingNanjing”，SUBSTR（S ，4，5）=（ ） 。A. “ijing” B. “jing” C. “ ingNa” D. “ingN”6. 若 INDEX（S ，T）表示求 T 在 S 中的位置的操作，则对于 S=“BeijingNanjing” ，T=“jing”，INDEX（S，T）= （ ） 。A.2 B.3 C.4 D.57. 若 REPLACE（S ，S1，S2）表示用字符串 S2 替换字符串 S 中的子串 S1 的操作，则对于S=“BeijingNanj
13、ing”，S1=“Beijing”，S2=“Shanghai”，REPLACE（S，S1 ，S2）=（ ） 。A. “NanjingShanghai” B. “NanjingNanjing”C. “ShanghaiNanjing” D. “ShanghaiNanjing”8. 在长度为 n 的字符串 S 的第 i 个位置插入另外一个字符串， i 的合法值应该是（ ） 。A.i0 B. in C.1in D.1in+19. 字符串采用结点大小为 1 的链表作为其存储结构，是指（ ） 。A.链表的长度为 1B.链表中只存放 1 个字符C.链表的每个链结点的数据域中不仅只存放了一个字符D.链表的每个链结点的数据域中只存放了一个字符二、填空题1. 计算机软件系统中，有两种处理字符串长度的方法：一种是_，第二种是_。2. 两个字符串相等的充要条件是_和_。3. 设字符串 S1= “ABCDEF”，S2= “PQRS”
