山东大学软件学院2018-2019 数据结构真题
需积分: 44 75 浏览量
2019-01-10
17:05:21
上传
评论 7
收藏 39KB DOCX 举报
山东大学软件学院 2018-2019 数据结构真题
一、线性结构
1，已知线性表（8,9,2,13,0,7,1,6,5）回答下列各题
（1） 请描述公式化描述以及链表描述的空间需求。如果需要删除元素 13.请描述
各自的时间复杂度。
（2）请分别进行选择排序、插入、快速（以 8 为轴），并给出第一轮排序结束后
的结果。
（3）设计散列表，Hash 函数为 H(k)=k%7，散列表长为 11，请给出线性开型寻址
的散列表。
（4）基于以上散列表，查找元素 1，给出需要的查找次数。
（5）若使用单链表存储以上线性表，请读以下程序并给出运行结果和时间复杂度。
template<class T>
Chain<T>& Chain<T>::R(){
ChainNode<T>*last=0,
*current=first,
*next;
while(cur){
next=cur->link;
cur->link=last;
last=current;
cur=next;
}
first=last;
return *this;
}
评论0