最新数据结构模拟题答案
- 格式：doc
- 大小：115.50 KB
- 文档页数：8
数据结构模拟试题答案一.选择题（每题2分，共20分）（请将答案填写到表格中）1．数据结构主要研究数据的各种逻辑结构、存储结构，以及对数据的（）。
A. 关系描述B. 结构实现C. 各种操作D. 各种定义2．以下与数据的存储结构无关的术语是______。
A. 散列B. 循环队列C. 三元组表D. 数组3．指出下列各表中使用的是何种存储方式：表1是(（2）)存储方式；表2是(（3）)存储方式。
A. 循环链接B. 单向链接C. 双向链接D. 顺序存储4．有六个元素6，5，4，3，2，1 的顺序进栈，（）是不合法的出栈序列。
A. 5 4 3 6 1 2B. 4 5 3 1 2 6C. 3 4 6 5 2 1D. 2 3 4 1 5 65．已知广义表A((a,b,c),(d,e,f))，从A中取出原子e的运算是______。
A. Head(Tail(Head(A)))B. Head(Tail(Head(Tail(A))))C. Head(Head(Tail(A)))D. Head(Head(Tail(Tail(A))))6．表达式a*(b+c)-d的后缀表达式是( )。
A. abcd*+-B. abc+*d-C. abc*+d-D. -+*abcd7．判断有向图中是否有环的有效方法是______。
A. 求最短路径B. 广度优先搜索C. 拓扑排序D. 关键路径8．从下图中顶点v3出发，对图进行广度优先搜索后得到的序列是______；对图进行深度优先搜索后得到的序列是______。
A. v3,v5,v2,v1,v4,v6B.v3,v6,v1,v4,v5,v2C. v3,v1,v4,v5,v2,v6D.v3,v4,v2,v5,v6,v19．具有11个关键字的有序表，折半查找成功的平均查找长度（）。
A. 3.1B. 2.5C. 3D. 510．假设一个关键字的序列进行了如下的排序过程，原序列：（12，5，9，32，14，47，98，10）第一趟排序结果：（10，5，9，12，14，47，98，32）第二趟排序结果：（9，5，10，12，14，47，98，32）第三趟排序结果：（5，9，10，12，14，32，47，98）则这个排序为______。
A. 希尔排序B. 堆排序C. 快速排序D.简单选择排序二. 判断题：（每题1分，共10分）1．算法可以用不同的语言描述，如果用C语言或C++语言等高级语言来描述，则算法实际上就是程序了……………………………………………………………………………………（×）2．链表是一种随机存取结构，因而便于对链表进行插入和删除操作…………………….（×）3．循环队列的引入，目的是为了克服假溢出时数据大量的移动…………………………..（√）4．从逻辑结构看，n维数组的每个元素均属于n个向量.....................………………………（√）5．在图采用邻接表存储时，求最小生成树的Prim算法的时间复杂度为O(n+e)……..……（×) 6．由4个结点可以构造出21中不同的二叉树………………………………………………（×) 7．在表示某工程的AOE网中，加速其关键路径上的任意关键活动均可缩短整个工程的完成时间.....................…………………………………………………………………………………...（×) 8．二叉排序树的查找效率与构造其树形的初始序列相关………………. .......…………. …( √) 9．非空的二叉树一定满足：某结点若有左孩子，则其中序前驱一定没有右孩子………... ( √) 10．直接选择排序是一种不稳定的排序方法………………..............………………………..（√）三．读程序：（每题5分，共10分）现有一个单向链表类，如下所示：#include <iostream.h>template<class T>class LinkedList;template<class T>class ListNode{T data; // 结点数据域ListNode<T> *link; // 结点指针域friend class LinkedList<T>;ListNode(ListNode<T> *ptr=NULL){link=ptr;}ListNode(const T& item, ListNode<T> *ptr=NULL ):data(item),link(ptr) {}}; //链表结点数据类型template<class T>class LinkedList{public:LinkedList(){first = new ListNode<T>;} // 初始化带头结点的单向链表~LinkedList(){makeEmpty();}void makeEmpty();int Length()const;ListNode<T>* Search(const T &x)const;ListNode<T>* getData(int i);void setData(int i, T x);int Insert(int i,T x);int Remove(int i,int k);int IsEmpty()const{return first->link==NULL;}void input();void output();bool A ( LinkedList<T> &L) ;private:ListNode<T> *first; //定义头指针bool A ( ListNode<T> *ptr1, ListNode<T> *ptr2);};//链表模板类1．其中，Search函数的功能是若链表中存在值为给定值x的结点，则返回该结点的地址；否则，返回NULL。
在下面的Search函数实现代码的空白处填上适当的C++语句，使之能实现指定的功能。
template<class T>ListNode<T>* LinkedList<T>::Search(T &x)const{ListNode<T> *p = ______①__ ;while ( ②){③__ ;}if (p)____ __④_________;else_______⑤_________;}2．仔细阅读A函数的程序代码，并回答程序段后面的问题。
template<class T>bool LinkedList<T>::A ( LinkedList<T> &L){return A(first->link, L.first->link);}template<class T>bool LinkedList<T>::A (ListNode<T> *pa,ListNode<T> *pb){if (pa == NULL) {return true;}while (pb ){if (pa->data == pb->data){pa = pa->link;pb = pb->link;return (A(pa,pb));}else{pb = pb->link;}}return false;}其中，假设成员函数A ( LinkedList<T> &L)涉及的两个链表中的值如下所示：（1）A ( LinkedList<T> &L)函数实现的具体操作是：_____判断子集______。
（2）假定链表类中定义的其他函数均已实现（链表中数据的输入次序与上图一致），编写一个main函数，调用A函数，并写出运行结果。
int main(){LinkedList<int> L1,L2;L1.input();L2.input();if(L1.A(L2)) cout<<"Yes";else cout<<"No";return 1;}运行结果：Yes四. 简答题：（每题5分，共35分）1．画出与下列已知序列对应的树T，要求写出求解过程：（5分）（1）树的先根次序访问序列为GFKDAIEBCHJ；（2）树的后根次序访问序列为DIAEKFCJHBG。
见P1912．根据权值集W={7，19，2，6，32，3，21，10}，完成：（5分）（1）创建一棵Huffman树；（2）计算出该树带权路径长度WPL；（3）在这棵二叉树上加上中序线索。
3．用关键字序列（50，73，191，325，10，73，40，73）形成一棵二叉排序树，并计算它在查找成功时和查找不成功时的平均查找长度。
（5分）4．选取散列函数H（k）= k mod 11，用线性探测法处理冲突。
试在0~12的散列地址空间中，对键序列（33，19，53，45，30，13，2，67）构造散列表，并求等概率情况下查找成功与不成功的平均查找长度。
（5分）5．写出用Floyd算法求解下图中各顶点之间最短路径的过程。
（5分）略6．在堆排序、快速排序和归并排序中：（5分）(1) 若只从存储空间考虑，则应首先选取哪种排序方法，其次选取哪种排序方法？堆排序、快速排序(2) 若只从排序结果的稳定性考虑，则应选取哪种排序方法？归并排序(3) 若只从平均情况下排序最快考虑，则应选取哪种排序方法？快速排序(4) 若只从最坏情况下排序最快并且要节省内存考虑，则应选取哪种排序方法？堆排序7．设有数据逻辑结构为：B = (K, R), K = {k1, k2, …, k9}R={<k1, k3>, <k1, k8>, <k2, k3>,<k2, k4>, <k2, k5>, <k3, k9>,<k5, k6>, <k8, k9>, <k9, k7>, <k4, k7>, <k4, k6>}，要求：（5分）（1）画出这个逻辑结构的图示。
略（2）画出该逻辑结构正向邻接表。
略（3）在（2）的基础上，利用栈作为存放入度为0的顶点序号，写出该图示的拓扑排序序列。
如果正向邻接表中邻接点序号从小到大排列，则拓扑排序序列：K2---K5---K4---K6---K1---K8---K3---K9---K7五.编程题：（25分，每题10分）设计一个学生信息顺序表类（结构如下图所示），要求定义并实现三个成员函数：（1）构造函数：建立一个空表。
