《数据结构复习指导.doc》由会员分享，可在线阅读，更多相关《数据结构复习指导.doc（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; i=n; i+)for(j=i; j=n; j+)x+;A.O(1)B.O()C.O(n)D.O()5. 算法分析的目的是（C），算法分析的两
2、个主要方面是（A）。（1） A.找出数据结构的合理性 B.研究算法中的输入和输出关系C.分析算法的效率以求改进 D.分析算法的易懂性和文档性（2） A.空间复杂度和时间复杂度 B.正确性和简明性C.可读性和文档性 D.数据复杂性和程序复杂性6. 计算机算法指的是（C），它具备输入，输出和（B）等五个特性。（1） A.计算方法 B.排序方法 C.解决问题的有限运算序列 D.调度方法（2） A.可行性，可移植性和可扩充性 B.可行性，确定性和有穷性C.确定性，有穷性和稳定性 D.易读性，稳定性和安全性7. 数据在计算机内有链式和顺序两种存储方式，在存储空间使用的灵活性上，链式存储比顺序存储要（ B
3、 ）。A.低 B.高 C.相同D.不好说二、填空题 1. 数据结构按逻辑结构可分为两大类，分别是_线性结构_和_非线性结构_。2. 数据的逻辑结构有四种基本形态，分别是_集合_、_线性_、 树_和_图_。3. 线性结构反映结点间的逻辑关系是一对一的，非线性结构反映结点间的逻辑关系是_一对多或多对多的。4. 一个算法的效率可分为_时间_效率和_空间_效率。5. 在树型结构中，树根结点没有_前趋_结点，其余每个结点的有且只有_1_个前趋驱结点；叶子结点没有_后继_结点；其余每个结点的后续结点可以_多个_。6. 在图型结构中，每个结点的前趋结点数和后续结点数可以_有多个_。7. 线性结构中元素之间存
4、在_一对一_关系；树型结构中元素之间存在_一对多_关系；图型结构中元素之间存在_多对多_关系。8. 下面程序段的时间复杂度是_ O()_。for(i=0;in;i+)for(j=0;jn;j+)Aij=0;9. 下面程序段的时间复杂度是_ O()_。i=s=0;while(sn) i+; s+=i;10. 下面程序段的时间复杂度是_ O()_。s=0;for(i=0;in;i+)for(j=0;jn;j+)s+=Bij;sum=s;11. 下面程序段的时间复杂度是_ O(logn)_。i=1;while(i=n)i=i*3;12. 衡量算法正确性的标准通常是_程序对于精心设计的典型合法数据输入
5、得出符合要求的结果_。13. 算法时间复杂度的分析通常有两种方法，即_事后统计_和_事前估计_的方法，通常我们对算法求时间复杂度时，采用后一种方法。第2章 线性表一、单项选择题 1. 线性表是_A_。A一个有限序列，可以为空B一个有限序列，不可以为空C一个无限序列，可以为空D一个无限序列，不可以为空2. 在一个长度为n的顺序表中删除第i个元素(0=inext=s; s-prior=p; p-next-prior=s; s-next=p-next;B s-prior=p; s-next=p-next; p-next=s; p-next-prior=s;C p-next=s; p-next-pri
6、or=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个元素(0 inext=p-next; p-next=s Bq-next=s; s-next=pCp-next=s-next; s-next=p Dp-next=s; s-next=q9
7、. 以下关于线性表的说法不正确的是_B_。 A线性表中的数据元素可以是数字、字符、记录等不同类型。B线性表中包含的数据元素个数不是任意的。C线性表中的每个结点都有且只有一个直接前趋和直接后继。D存在这样的线性表：表中各结点都没有直接前趋和直接后继。10. 线性表的顺序存储结构是一种_A_的存储结构。 A随机存取B顺序存取C索引存取D散列存取11. 在顺序表中，只要知道_D_，就可在相同时间内求出任一结点的存储地址。A基地址B结点大小 C向量大小 D基地址和结点大小12. 在等概率情况下，顺序表的插入操作要移动_B_结点。 A全部 B一半 C三分之一 D四分之一13. 在_C_运算中，使用顺序表
8、比链表好。 A插入 B删除 C根据序号查找 D根据元素值查找14. 在一个具有n个结点的有序单链表中插入一个新结点并保持该表有序的时间复杂度是_B_。 AO(1) BO(n) CO(n2) 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. 在一个具有n个单元的顺序栈中，假定以地址低端（即0单元）作为栈底，以top作为栈顶指针，当做出栈处理时，top变化为_C_。Atop不变 Btop=0 Ctop- Dto
9、p+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= = rearCrearn -1= = front D(rear+l)n= = front 19. 在具有n个单元的顺序存储的循环队列中，假定front和rear分别为队头指针和队尾指针，则判断队空
10、的条件为_。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. 线性表是一种典型的_结构。2. 在一个长度为n的顺序表的第i个元素之前插入一个元素，需要后移_个元素。3. 顺序表中逻辑上相邻的元素的物理位置_。4. 要从一个顺序表删除一个元素时，被删除元素之后的所有元素均需_一个位
11、置，移动过程是从_向_依次移动每一个元素。5. 在线性表的顺序存储中，元素之间的逻辑关系是通过_决定的；在线性表的链接存储中，元素之间的逻辑关系是通过_决定的。6. 在双向链表中，每个结点含有两个指针域，一个指向_结点，另一个指向_结点。7. 当对一个线性表经常进行存取操作，而很少进行插入和删除操作时，则采用_存储结构为宜。相反，当经常进行的是插入和删除操作时，则采用_存储结构为宜。8. 顺序表中逻辑上相邻的元素，物理位置_相邻，单链表中逻辑上相邻的元素，物理位置_相邻。9. 线性表、栈和队列都是_结构，可以在线性表的_位置插入和删除元素；对于栈只能在_位置插入和删除元素；对于队列只能在_位置插入元素和在_位置删除元素。10. 根据线性表的链式存储结构中每个结点所含指针的个数，链表可分为_和_；而根据指针的联接方式，链表又可分为_和_。11. 在单链表中设置头结点的作用是_。12.
