2005级电子“数据结构”期中测验试卷

《2005级电子“数据结构”期中测验试卷》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、2005级电子“数据结构”期中测验试卷1．（24分）填空：1．一个完整的算法应该具有输入、输出、有穷性、确定性和___可行性_______等五个特性。其中有穷性表示__算法在有穷步结束___。2．数据的基本存储结构包括_连续的（数组）_和链式（指针）____。3.长度为n的线性表采用顺序存储结构，在表的第i个位置插入一个元素需要___n-i+1(包括写入欲插入的元素)______次移动元素的操作，在所有可能的位置插入的平均移动次数为____1＋2＋...＋n+1____。假定在每个位置插入的概率相等。4.L指向带头结点的单链表的头结点，则单链表空的条件是___L

2、->Next==NULL___。5.一个算法的时间复杂度表示为问题规模n的函数为T(n)=3n2+50nlgn–10000n。用大O表示法为___O(n2)___，因为_____T(n)<53n2___;用大QQ表示法为__Q(n2)______,因为____T(n)/n2->3_______________。6.在有序表（12，24，36，48，60，72，84）中折半查找关键字72时所需进行的关键字比较次数为3次。一般地，二分查找成功的最大比较次数与查找树的__高度________成正比。7.使用折半查找的查找表必须是按关键字有序的，其存储结构应该采用_连续

3、结构（随机存取结构，数组）_____________。8.由下列序列构造的初始(大顶)堆是__39343831241727____：172438313439279.假设哈希表的长度是M,使用的哈希函数为h,插入关键字k时发生冲突,那么使用线性探查法的探查序列为__(h(k)+1)%M,(h(k)+2)%M,...__________,使用平方探查法的探查序列为_(h(k)+1)%M,(h(k)+4)%M,(h(k)+9)%M,...______。10.使用哈希表进行查找的效率与哈希表的大小无关，但是与__装载因子______有关。11.简单插入排序在输入__输入

4、按关键字有序_的情况下表现最好，此时的比较次数为_______n-1,n是记录个数__.。12.快速排序的平均时间复杂度是___O(nlogn)___________，在最坏情况下的复杂度是_____O(n2)___。13.数据的逻辑结构是指__数据元素间的逻辑关系_，数据的存储结构是指___数据元素存储方式，或者数据元素的物理关系_____。二.（36分）简答题1．什么是抽象数据类型（ADT）?试举例说明。抽象数据类型的概念重要意义是什么？2．试就线性表的实现说明连续结构与链式结构各有什么特点。3．评估算法的主要指标有哪些？简要说明这些指标的含义。答：时间性能

5、、空间性能、可读性等。4．什么是排序算法的稳定性？试举例说明。简单插入排序，归并排序，快速排序和堆排序中，哪些是稳定的，哪些是不稳定的？templatestructNode{//datamembersNode_entryentry;Node*next;//constructorsNode();Node(Node_entry,Node*link=NULL);};三．（15分）完成ADT方法的实现假定使用带头节点的单链表实现线性表List，其中calssList和节点说明如下：t

6、emplateclassList{public:List();//构造一个只含头节点的空链表intsize()const;boolempty()const;voidclear();Error_coderetrieve(intposition,List_entry&x)const;Error_coderemove(intposition,List_entry&x);Error_codeinsert(intposition,constList_entry&x);//将元素x插入在位置position处。~List();List

7、(constList©);voidoperator=(constList©);protected:intcount;Node*head;//头指针，指向头节点//下列辅助函数返回指向处于position位置节点的指针。Node*set_position(intposition)const;};试用C++代码写出构造函数List()和插入函数insert的实现。答：templateList:

8、:List(){/Pos