数据结构期末考试复习题.docx

第一部分 线性一.选择题（共10题）1.以下说法正确的是（）。A.数据元素是数据的最小单位。B. 数据结构是带结构的各数据项的集合。C.数据项是数据的基本单位。D. 数据结构是带结构的数据元素的集合。2. 在设计存储结构时，通常不仅要存储各数据元素的值，而且还要存储（）。A.数据的处理方法B.数据元素的类型C.数据元素之间的关系D.数据的存储方法3.树状结构中的数据元素之间存在（）逻辑关系。A.一对一 B.多对一 C.多对多 D.一对多4.以下数据结构中，哪一个不属于线性结构（）。A.串 B.广义表 C.栈 D.树5.对一个具有n个结点的单链表，在表头位置插入其值等于x的结点时，操作的时间复杂度为（）。A. O(1) B. O(x) C. O(n) D. O(n2)6. 设一顺序栈已含3个元素a（栈底）、b、c（栈顶），元素d正等待进栈。那么下列4个序列中不可能出现的出栈序列是（）。A. dcba B. cdba C. cbda D. cadb 7. 如果栈采用顺序存储结构，则入栈操作时（）。A. 必须判别栈是否满。 B. 必须判别栈是否空。C. 判别栈元素的类型。 D. 对栈不做任何操作。8.用一个大小为N的数组来实现循环队列Q，假定front和rear分别为队头指针和队尾指针，判断该循环队列为满的条件是（）。A.(Q.rear+1)==Q.front B. Q.front==Q.rear C.(Q.rear+1)%N==Q.front D. (Q.front+1)%N==Q.rear9.串S=“串string”的长度是（）。 A. 6 B. 7 C. 8 D. 910.设二维数组arr[6][4]（行列下标从0开始）的每个元素占6个单元，按行优先顺序存放在起始地址为2000的连续内存单元中，则存储地址为2066的是元素（）。A. arr[2][3] B. arr[3][3] C. arr[5][1] D. arr[4][1]二.填空题（共25空）1.根据数据元素之间关系的不同特性，通常有4类基本数据结构，它们是: (____________)、(___________)、(___________)、(___________)。2.在数据结构中，(______________)用于完整地描述一个研究对象，是数据的基本单位。3.计算机中的算法指的是解决某类问题的有限操作序列，它必须具备输入、输出、(____________)、(______________)、(______________)等5个特性。4.顺序表中逻辑上相邻的元素的物理位置(___________)。5.下面程序段的时间复杂度是(___________)。int r=1; int i=1;while(in) { r=r*i;i ++; }6.循环单链表H中，指针P所指结点是表尾结点的判断条件是(___________)。7. 在线性表A,采用单链表存储，已经有数据（b,c,d,e,f,h）中，要删除元素c，此时已经有指针p指向b元素，语句为：q=p-next; (___________); x=q-data;free(q);要插入元素g，使得此线性表变为（b,c,d,e,f,g,h）,此时已经有指针p指向f元素，插入g的语句为：s-data=‘g’，s-next= (___________); p-next=s;8. 设有一顺序栈S，元素A、B、C、D、E、F依次进栈，如果6个元素出栈的顺序是A、D、F、E、C、B，则栈的容量至少应该是(___________)。9.在一个具有n个单元的顺序栈中，假定以地址低端（即0单元）作为栈底，以top作为栈顶指针，当做入栈处理时，top变化为(___________)。10.设有一空栈，现有输入序列a，b，c，d，e，操作push代表入栈，pop代表出栈，经过push，push，push，pop，push，pop，pop后，栈顶元素为(___________)。11. 用一个大小为10的数组来实现循环队列，且当前队头和队尾的值分别为2和7，当从队列中删除3个元素，再加入4个元素后，rear的值为(___________)，front的值为(___________)，当前队列的长度为(___________)。12.若Replace(S,V,T)表示用字符串T替换主串S中的所有子串V的操作，则对于S=“software”，V=“ware”，T=“l