数据结构模拟题答案.doc

第 7 页数据结构模拟试题答案一.选择题（每题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 2 B. 4 5 3 1 2 6 C. 3 4 6 5 2 1 D. 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.1 B. 2.5 C. 3 D. 5 10假设一个关键字的序列进行了如下的排序过程， 原序列：（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.简单选择排序选择题答案12345678910CDDACBBCBACC二. 判断题：（每题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 templateclass LinkedList;templateclass ListNode T data;/ 结点数据域 ListNode *link;/ 结点指针域 friend class LinkedList; ListNode(ListNode *ptr=NULL)link=ptr; ListNode(const T& item, ListNode *ptr=NULL ):data(item),link(ptr) ; /链表结点数据类型templateclass LinkedList public:LinkedList()first = new ListNode;/ 初始化带头结点的单向链表 LinkedList()makeEmpty(); void makeEmpty(); int Length()const; ListNode* Search(const T &x)const; ListNode* getData(int i); void setData(int i, T x); int Insert(int i,T x); int Remove(int i,int k); int IsEmpty()constreturn first-link=NULL; void input(); void output(); bool A ( LinkedList &L) ;private: ListNode *first;/定义头指针 bool A ( ListNode *ptr1, ListNode *ptr2);/链表模板类1其中，Search函数的功能是若链表中存在值为给定值x的结点，则返回该结点的地址；否则，返回NULL。在下面的Search函数实现代码的空白处填上适当的C+语句，使之能实现指定的功能。templateListNode* LinkedList:Search(T &x)constListNode *p = _ ; while ( ) _ ;if (p) _ _;else_;：first-link：p & p-data != x：p = p-link：return p return NULL2仔细阅读A函数的程序代码，并回答程序段后面的问题。templatebool LinkedList:A ( LinkedList &L) return A(first-link, L.first-link); templatebool LinkedList:A (ListNode *pa,ListNode *pb) if (pa = NULL) return true;while (pb )if (pa-data = pb-data)pa = pa-link;pb = pb-link;return (A(pa,pb);elsepb = pb-link; return false;其中，假设成员函数A ( LinkedList &L)涉及的两个链表中的值如下所示：（1）A ( LinkedList &L)函数实现的具体操作是：_判断子集_。（2）假定链表类中定义的其他函数均已实现（链表中数据的输入次序与上图一致），编写一个main函数，调用A函数，并写出运行结果。int main()LinkedList L1,L2;L1.input();L2.input();if(L1.A(L2) coutYes;else coutNo;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，用线性探测法处理冲突。试在012的散列地址空间中，对键序列（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, , k9R=, , , , , , , , ，要求：（5分）（1）画出这个逻辑结构的图示。略（2）画出该逻辑结构正向邻接表。略（3）在（2）的基础上，利用栈作为存放入度为0的顶点序号，写出该图示的拓扑排序序列。如果正向邻接表中邻接点序号从小到大排列，则拓扑排序序列：K2-K5-K4-K6-K1-K8-K3-K9-K7五.编程题：（25分，每题10