《数据结构期中测试题答案.doc》由会员分享，可在线阅读，更多相关《数据结构期中测试题答案.doc（4页珍藏版）》请在三一文库上搜索。
1、数据结构期中测试班级： 姓名： 学号：一、 填空题：1、 在数据结构中，从逻辑上可以把数据结构分为集合、线性结构、树形结构和图状结构，其中树形结构和图状结构合称为非线性结构。数据结构被形式地定义为二元组（D，S），其中D是数据元素的有限集合，S是D上关系的有限集合。2、 算法的五个重要特性是有穷性、确定性、可行性、输入和输出。3、 一个顺序表第一个元素的存储地址是100，每个元素的长度为3，则第6个元素的地址是115。在顺序表中插入或删除一个元素，需要平均移动（n+1）/2个元素，具体移动的元素个数与插入或删除元素的位置有关。顺序表中逻辑上相邻的元素的物理位置相邻。单链表中逻辑上相邻的元素的物
2、理位置不一定相邻。单链表中，除了首元结点外，任一结点的存储位置由其前驱结点的指针域指示。在单链表中设置头结点的作用是使第一个结点与其他结点的操作统一。4、 从一个具有n个结点的单链表中查找其值等于x的结点时，在查找成功的情况下，需平均比较（n+1）/2个结点。在一个具有n个结点的有序单链表中插入一个新结点并仍然有序的时间复杂度是O（n）。给定有n个元素的线性表，建立一个有序单链表的时间复杂度是O（n2）。5、 已知L是无表头结点的非空单链表，且指针p所指结点既不是首元结点，也不是尾元结点，试从下列提供的答案中选择合适的语句序列。在p所指结点后插入s所指结点：4、1。在p所指结点前插入s所指结点
3、：7、11、8、4、1。在表首插入s所指结点：5、12。在表尾插入s所指结点：11、9、1、6。1) p-next=s;2) p-next=p-next-next;3) p-next=s-next;4) s-next=p-next;5) s-next=L;6) s-next=NULL;7) q=p;8) while(p-next!=q) p=p-next;9) while(p-next!=NULL) p=p-next;10) p=q;11) p=L;12) L=s;13) L=p;6、 已知指针p所指结点是某双向链表的中间结点，试从下列提供的答案中选择合适的语句序列。在p所指结点后插入s所指结
4、点的语句序列是7、12、6、3。在p所指结点前插入s所指结点的语句序列是8、13、5、4。删除p所指结点的直接后继结点的语句序列是15、p-next=q-next、q-next-prior=p、18。？删除p所指结点的直接前驱结点的语句序列是16、p-prior=q-prior、q-prior-next=p、18。？删除p所指结点的语句序列是1、2、17。1) p-next=p-next-next;2) p-prior=p-prior-prior;3) p-next=s;4) p-prior=s;5) s-next=p;6) s-prior=p;7) s-next=p-next;8) s-pr
5、ior=p-prior;9) p-prior-next=p-next;10) p-prior-next=p;11) p-next-prior=p;12) p-next-prior=s;13) p-prior-next=s;14) p-next-prior=p-prior;15) q=p-next;16) q=p-prior;17) free(p);18) free(q);7、 简述以下算法的功能。Status algo1(Stack S) int i,n,A255; n=0; while(!StackEmpty(S) n+; Pop(S,An); for(i=1;inext) return E
6、RROR;else p=L-next;while (!p-next) if(p-data!=p-next-data) p=p-next; else q=p-next; p-next=q-next; free(q);return ok;2、 编写一个函数从一给定的非空顺序表L中删除元素值在x到y（xy）之间的所有元素。请在空白处填上合适的语句以实现上述功能。void DelElem_Sq(SqList &L,int x,int y) for (i=0;i=x & L.elemi=0;i-) if(L.elemi=0) for (k=i;knext; if (!p) return (0); n=1
7、; while(p-next!=L) n+; p=p-next; return (n);4、 利用两个栈s1和s2模拟一个队列时，编写算法用栈的运算来实现该队列的入队操作enqueue和出队操作dequeue。分析：由于栈的特点是FILO，为了模拟FIFO的队列，必须用两个栈，一个栈s1用于插入元素，另一个栈s2用于删除元素，每次删除元素时应将前一个栈的所有元素读出然后进入第二个栈中，这样才能达到模拟队列的效果。Status enqueue(SqStack &s1,ElemType x) if(s1.top-s1.base=s1.stacksize) exit(OVERFLOW); else push(s1,x);Status dequeue(SqStack &s1,SqStack &s2,ElemType x) ClearStack(s2); while(!StackEmpty(s1) push(s2,pop(s1,x); pop(s2,x); while(!StackEmpty(s2) push(s1,pop(s2,x);