《数据结构期中考试答案》由会员分享，可在线阅读，更多相关《数据结构期中考试答案（8页珍藏版）》请在金锄头文库上搜索。
1、数据结构数据结构期中考试试卷期中考试试卷一、一、 填空题（每空填空题（每空 1 分，共分，共 20 分）分）1. 数据的物理结构包括 （1）顺序顺序 的表示和 (2)链式链式 的表示。2. 一个算法具有 5 个性质: (3)有限性有限性 、 (4)确定性确定性 、 (5)可执行性可执行性 ，有零个或多个输入、有一个或多个输出。3. 抽象数据类型是指一个逻辑概念上的类型和这个类型上的 (6) 操作操作集合集合 。4当线性表的元素总数基本稳定，且很少进行插入和删除操作，但要求以最快的速度存取线性表中的元素时，应采用_(7)顺序顺序 _存储结构。5线性表 L=（a1,a2,an）用数组表示，假定删除
2、表中任一元素的概率相同，则删除一个元素平均需要移动元素的个数是_ _(8)_（n-1n-1）/2/2_。6. 在单链表中设置头结点的作用是_(9)使得删除插入等操作处理方法使得删除插入等操作处理方法相同相同7. 栈是一种特殊的线性表，允许插入和删除操作的一端称为 (10)栈顶栈顶 ，不允许插入和删除操作的一端称为 (11)栈底栈底 。8. 在顺序循环列队中，队空标志为_(12_count=0count=0_，队满标志为_(13)_Q-rear=Q-frontint mon;int day;struct accountlong accountNum;char ownerName20;struct
3、 time openTime;int accountType;duoble interest;duoble accountSum;2.设有一个二维数组 A1020，按行存放于一个连续的存储空间中，A00的存储地址是 200，每个数组元素占 1 个存储字，则 A62的存储字地址是多少。 【4 分】3223.设有数据元素序列序列 1，2，3，给出利用一个堆栈可以得到的所有出栈数据元素序列和不可以得到的出栈数据元素序列。 【6 分】答：可得到的序列：答：可得到的序列：123，132，213，231，321，不可能的，不可能的312。4.指出算法的功能和时间复杂度，若 n=20，则求出函数的返回值。
4、【6 分】int fun(int n)int i=1, s=1;while(s/*该文件包含 pringtf()等函数*/ #define MaxSize 100/*定义 MaxSize 为 100*/ typedef int DataType;/*定义 DataType 为 int*/ #include “SeqList.h“/*包含线性表文件*/void main(void) SeqList myList; int i , x;ListInitiate(/*初始化*/for(i = 0; i Aj+1 ) x=Aj;Aj=Aj+1;Aj+1=x;（3）b=true i+;冒泡排序冒泡排序8
5、. 假定 HL 为保存一个集合的有序有序单链表的表头表头指针，item 为一个新元素，HL 单链表中的结点包括值域 data 和指向后继结点的指针域 link，试根 据下面算法指出算法功能。 （链表结点中保存的数据元素的类型为ElemType） 【6 分】功能把功能把 item 插入到有序单链表插入到有序单链表 HL 中，构建一中，构建一个新的有序单链表个新的有序单链表void Unknown(ListNode *HL, ElemType item)ListNode* newptr=（ListNode *）malloc(sizeof(ListNode);newptr-data=item;if(
6、HL=NULL | itemdata) newptr-link=HL;HL=newptr;return;ListNode *cp, *ap; ap=HL; cp=HL-link;while(cp!=NULL) if(itemdata) break;ap=cp;cp=cp-link;newptr-link=cp;ap-link=newptr; 9. rear 是指向以循环链表表示的队列的队尾指针，EnLQueue 函数实现把 x 插入到队尾的操作。DeLQueue 函数实现删除队头元素并赋给 x 的操作。根据题意按标号把合适 的内容填写到算法后面相应标号的位置。 （队列元素的数据类型为 Elem
7、Type） 【6 分】void EnLQueue(ListNode *rear, ElemType x)/ rear 是指向以循环链表表示的队列的队尾指针，插入 x 为新的队尾元素。ListNode *p; p=(ListNode *)malloc(sizeof(ListNode);p-data=x; _(1)_p-link=rear-link_;rear-link=p; rear=p; bool DeLQueue(ListNode *rear, ElemType *x) / rear 是指向以循环链表表示的队列的队尾指针，若队列不空，则删除队头元 素，/并以 x 带回，并返回 true, 否
8、则返回 false, x 无意义if(rear=NULL) return false;if (rear-next=rear) x=rear-data; delete rear; rear=NULL; return false;ListNode *p=rear-link;rear-link=p-link;_(2)*x=p-data_;Free(p);_(3)return true_;10.设有下列递归算法: 【8 分】int vol(int n) if(n=0) return 0;elsereturn vol(n-1)+2; 如该函数被调用时，参数 n 值为 3,函数调用结束时返回值为多少?用图
9、示描述函 数的递归调用执行过程。答：参数答：参数 n 值为值为 3,函数调用结束时返回值为函数调用结束时返回值为 6，调用执行过程天：，调用执行过程天：vol(3) vol(2) return 2+vol(2) vol(2) vol(1) return 2+vol(1) vol(1) vol(0) return 2+vol(0) vol(0) return 0 vol(3) 0 2 4 6 三、三、 程序设计题（总分程序设计题（总分 20）试编写一个函数，在一个顺序表 A 中查找出具有最大值和最小值的整数。函数的原型如下所示，原型的参数表中给出顺序表 A，通过算法执行，从 参数表中的引用参数
10、Max 中得到表中的最大整数，Min 中得到表中的最小整数。注意，函数中可使用顺序表的如下两个公有函数：int ListLength(SeqList L ); 求表的长度；int ListGet(SeqList L, int i, DataType *x); 提取第 i 个元素的值。 /注意：该题原提取元素函数改变为注意：该题原提取元素函数改变为 ListGetListGet，以符合教材编写。，以符合教材编写。/#include “SeqList.h”void FindMaxMin(SeqList L, int *max, int *min) int i ,x;ListGet(L, 0, max);ListGet(L, 0, min);for(i=1;iListLength(L);i+)ListGet(L, i, if(maxx) min=x;
