数据结构C++模拟卷子2

1、第 1 题.( 复合题 共计 20 分) 简答题第 1.1 题.(主观 题 5 分) 已知用二元组表示的数据结构如下，请画图表示其数据关系，并说明该数据结构属于哪种逻辑结构？（本小题4分）B=(K,R);K=A,B,C,D,E;R=<A,B>,<B,C>,<B,D>,<D,A>,<D,B>,<D,E>,<E,C>参考答案逻辑结构：图图示结构：略(课本p158图5.2a)第 1.2 题.(主观 题 5 分) 设一个有序顺序表中存放以下整数：16，87，154，170，275，426，503，509，512，612

2、，653，677，703，765，897，908。运用二分（折半）法检索元素，请问：（1）检索612，需要经过多少次比较？每次比较的元素是什么？（2）检索900，需要经过多少次比较才能确定其不存在？每次比较的元素是什么？参考答案检索元素612第一次：m=(0+16)/2=8，与512比较；第二次：m=(9+16)/2=12，与703比较；第三次：m=(9+12)/2=10，与653比较；第四次：m=(9+10)/2=9，与612比较；检索成功。检索元素900第一次：m=(0+16)/2=8，与512比较；第二次：m=(9+16)/2=12，与703比较；第三次：m=(13+16)/2=14，与

3、897比较；第四次：m=(15+16)/2=15，与908比较；此时，low=15，high=15，因为 900<908，high=mid-1为14，使得low>high，检索停止，900不存在。第 1.3 题.(主观 题 5 分) 设有编号为1，2，3，4的4辆列车，依次顺序开进一个栈式结构的站台，问是否有3，2，4，1和4，1，3，2两种开出车站的可能？如有，该如何操作？参考答案顺序3，2，4，1是可能的，操作方法：1、2、3号车依次开进车站，3、2号车依次出站，4号车进站然后出站，最后1号车出站。顺序4，1，3，2是不可能的。第 1.4 题.(主观 题 5 分) 假设一棵二叉

4、树的中序遍历为DCBGEAHFIJK，后序遍历为DCEGBFHKJIA，请问：（1）该二叉树每层各有多少个结点？（2）该二叉树的形态是怎样的？请画图表示。参考答案（1）每一层：1个结点；第二层：2个结点；第三层：4个结点；第四层：4个结点。二叉树：图略（课本P155习题）第 2 题.( 复合题 共计 25 分) 算法分析题第 2.1 题.(主观 题 5 分) 顺序表定义如课本。顺序表初始设置的参数size为10，存储的数据为12，3，8，41，63，25，16，36，23。第1次调用下列函数的实参是（100，1），第2次调用的实参是（10，11）。请问：（1）第1次调用后，存储的数据是什么？参

5、数size是多少？（2）第2次调用后，存储的数据是什么？参数size是多少？template<class ElemType>bool SqList<ElemType>:Insert(const ElemType &e, int i) if (i < 1 | i > len + 1) return false; if (len >= size) ElemType *newbase; newbase = new ElemTypesize + 10; if (!newbase) return false; for (int j = 0; j <

6、 len; j+) newbasej = elemj; delete elem; elem = newbase; size += 10; ElemType *p,*q; q = &elemi - 1; for(p = &elemlen - 1; p >= q; -p) *(p + 1) = *p; *q = e; +len; return true; 参考答案（1）100，12，3，8，41，63，25，16，36，23。size是10。（2）100，12，3，8，41，63，25，16，36，23，10。size是20。第 2.2 题.(主观 题 5 分) 带头结点的单

7、链表定义如课本。下列算法对序列12，6，1，25，41，36，21，15，19，7连续进行操作，请问：（1）第1次调用时实参表是（e，4），则操作完成后的序列是什么？变量e存储的值是什么？（2）第2次调用时实参表是（e，9），则操作完成后的序列是什么？变量e存储的值是什么？template<class ElemType>bool LinkList<ElemType>:Delete(ElemType &e,int i) if (i<1 | i>len) return false; LinkNode<ElemType> *p,*q; int

8、k = 1; p = head ; while (k < i) p = p->next; k+; q=p->next; p->next=q->next; if (q = tail) tail = p; e=q->data; delete q; -len; return true; 参考答案（1）12，6，1，41，36，21，15，19，7。25（2）12，6，1，41，36，21，15，19。7第 2.3 题.(主观 题 5 分) 阅读下列程序，请问：（1）以下程序执行后，输出是什么？（2）外循环执行了多少次？（3）在程序运行中，发生了数据交换，那些数据之

9、间发生了交换？这些交换的数据都有什么特点？#include <iostream.h>template <class T>void partition(T v, int low, int high) T temp;while (low<=high)while (vlow<=0 && low<high)low+;while (vhigh>0 && low<high)high-;if (low<high)temp=vlow;vlow=vhigh;vhigh=temp;low+; high-;void main

10、()int a10=12,-3,26,12,-4,0,-6,11,24;int i;partition(a,0,8);for ( i=0; i<9; i+)cout<<ai<<' 'cout<<endl;参考答案（1）-6 -3 0 -4 12 26 12 11 24（2）3次（3）12与-6，26与0，12与-4。一个小于等于0的数据与一个大于0的数据交换。第 2.4 题.(主观 题 5 分) 对于序列15，88，36，9，2，95，5，请问：（1）在执行下列算法的过程中，外循环每次完成后的数据序列是怎样的？请完整写出来。（2）这是什

11、么算法？请写出名称，并写出其时间复杂度。（3）该算法的外循环执行了多少次？template<class ElemType>void process(ElemType data, int n) int lastSwapIndex = n - 1; int i, j; for (i = lastSwapIndex; i > 0;i = lastSwapIndex) lastSwapIndex = 0; for (j = 0; j < i; j+) if (dataj > dataj + 1) Swap( dataj,dataj + 1); lastSwapIndex

12、= j; 参考答案（1）15，36，9，2，88，5，9515，9，2，36，5，88，959，2，15，5，36，88，952，9，5，15，36，88，952，5，9，15，36，88，952，5，9，15，36，88，95（2）冒泡排序算法，O(n2)（3）6次 第 2.5 题.(主观 题 5 分) 下列程序中要运用队列进行数据处理，链式队列的定义如课本。参数v中存储整数：1，2，3，4，5，6，7，8，9，10 。请问处理结果的数据序列是怎样的？template <class T>void func(T v, int n)LinkQueue<T> qu;qu.C

13、lear();for ( int i=0; i<n; i+)qu.Append(vi);for(i=0;!qu.Empty();i+)vi=qu.GetHead();qu.Remove();vn-i-1=qu.GetHead();qu.Remove();参考答案把数据送进队列，然后按先两侧后中间的次序放回数组中，结果是：1 3 5 7 9 10 8 6 4 2第 3 题.( 复合题 共计 30 分) 算法填空题第 3.1 题.(主观 题 5 分) 下列算法对两组顺序表的数据进行处理，顺序表的定义如课本。请问：（1）La存储的数据是2，5，12，24，Lb存储的数据是1，3，6，7，8，9

14、，11，处理结束时，Lc存储的数据是什么？（2）程序中有三个循环，分别用“语句1”。表示。对于（1）给出的数据，执行的循环语句有哪些？循环开始时的变量i,j分别是多少？template<class T>void mergelist(SqList1<T> &La, SqList1<T>&Lb, SqList1<T> &Lc)int k, i, j, La_len, Lb_len;T ai, bj;k=1;i=j=1;La_len=La.Length();Lb_len=Lb.Length();while ( i<=La_

15、len && j<=Lb_len ) /语句1 La.GetElem(ai, i); Lb.GetElem(bj, j); if (ai<bj) Lc.Insert(ai,k ); i+; else Lc.Insert(bj,k ); j+; k+;while (i<= La_len) /语句2La.GetElem(ai, i); Lc.Insert(ai,k );k+; i+; while (j<=Lb_len) /语句3Lb.GetElem(bj, j); Lc.Insert(bj, k);k+; j+; 参考答案（1）Lc存储的数据是1，2，3，5

16、，6，7，8，9，11，12，24（2）执行了循环语句1和语句2。执行语句1时i是0，j是0；执行语句2时，i是3，j是8第 3.2 题.(主观 题 5 分) 二叉树的表定义如课本。下列算法是运用栈对二叉树进行中序遍历的算法。请把算法补充完整。如果用a1表示结点a入栈操作，a0表示出栈操作，n1表示空结点指针进栈，n0表示出栈。对于课本P114图4.9的二叉树，写出结点入栈出栈的过程。/ 中序遍历二叉树的非递归算法(利用栈)template <class ElemType>void BinaryTree<ElemType> :InorderTraverseNonRecu

17、rsive (void (*visit)(constElemType &e) stack<BTNode<ElemType> *> S; S.push( （1）); while(!S.empty() BTNode<ElemType> *p; p=S.top (); while(p) （2） ; （3） ; S.pop(); if( （4） ) p=S.top (); S.pop(); visit(p->data); （5） ; 参考答案补充完整算法：（1）m_root（2）p=p->lchild（3）S.push(p)（4）!S.empty

18、()（5）S.push(p->rchild)结点进出栈过程：按照0的次序取字母，得到中序序列dbgheafca1b1d1n1 n0d0 n1n0 b0e1g1 n1n0 g0h1 n1n0 h0 n1n0 e0 n1n0 a0c1f1 n1n0 f0 n1n0 c0 n1n0 第 3.3 题.(主观 题 5 分) 二叉树定义如课本。（1）请说明下列算法的功能；（2）说明该处理结果可以得到的信息有哪些？template <class ElemType>BTNode<ElemType>* BinaryTree<ElemType>:Process(BTNod

19、e<ElemType>* bt,const ElemType &e) if(!bt | bt->data = e) return bt; BTNode<ElemType> *q; q = _Locate(bt->lchild, e); if (q) return q; q = _Locate(bt->rchild, e); return q;参考答案（1）该算法能够在二叉树中查找结点值为e的结点指针；（2）算法处理结果得到的信息有两个可能，一是没有找到值为e的结点，返回值为NULL（空指针）；二是查到该结点，则返回指向该结点的指针。第 3.4

20、题.(主观 题 5 分) 以下是二分法检索算法，请补充完整算法，并说明，该算法处理结束时能够返回什么信息？/折半查找template <class ElemType,class KeyType >int BinarySearch(StaticTable<ElemType, KeyType > &R,const KeyType key) / low表示所查区间的下界，high表示所查区间的上界 int low = 0,high = R.m_size - 1; while (low <= high) int mid = （1） ; if (（2） ) retu

21、rn mid; else if (R.m_datasmid > key) （3） ; else （4） ; （5） -1 ; 参考答案补充完整算法：（1）(low + high) / 2（2）R.m_datasmid = key（3）high = mid - 1（4）low = mid + 1（5）return该算法结束时，返回的信息有两种可能：一是查找成功，返回关键码所在位置，二是查找失败，返回-1。第 3.5 题.(主观 题 5 分) 二叉树定义如课本，下列算法实现二叉树非递归前序遍历。用a1表示结点a进栈，a0表示出栈。对于课本P110图4.7，写出结点进出栈的过程。templat

22、e <class ElemType>void BinaryTree<ElemType> :PreorderTraverseNonRecursive (void (*visit)(constElemType &e) stack<BTNode<ElemType> *> S; BTNode<ElemType> *p; S.push(m_root); while(!S.empty() p=S.top (); S.pop(); visit(p->data); if (p->rchild) S.push(p->rchil

23、d); if (p->lchild) S.push(p->lchild); 参考答案a1a0 c1b1 b0 e1d1 d0 e0 f1 f0 c0第 3.6 题.(主观 题 5 分) 二叉排序树的定义如课本，下列算法在二叉排序树查找结点，如果查找成功，则获得该结点的指针p和父结点的指针f，并返回true，否则返回false。请把算法补充完整。template< class ElemType,class KeyType>bool BST<ElemType,KeyType>:_Search(KeyType key,BSTNode<ElemType,Key

24、Type> * &f,BSTNode<ElemType, KeyType> * &p) const f = NULL; p = （1） ; while (p && p->data != key) f = p; if (key < p->data) （2） ; else （3） ; return （4） ;参考答案（1）m_root（2）p = p ->lchild（3）p = p->rchild（4）p != NULL第 4 题.( 复合题 共计 15 分) 算法设计题第 4.1 题.(主观 题 5 分) 在二叉排

25、序树中查找给定关键字结点的算法如下，请对下列算法稍作修改，在查找结点的同时，确定其所在层次，若查找成功，返回该结点所在层数，否则，返回。template< class ElemType,class KeyType>bool BST<ElemType,KeyType>:_Search(KeyType key,BSTNode<ElemType,KeyType> * &f,BSTNode<ElemType, KeyType> * &p) const f = NULL; p = m_root; while (p && p-

26、>data != key) f = p; if (key < p->data) p = p ->lchild; else p = p->rchild; return p != NULL;参考答案template< class ElemType,class KeyType> int BST<ElemType,KeyType>:_Search(KeyType key,BSTNode<ElemType,KeyType> * &f,BSTNode<ElemType, KeyType> * &p) const

27、f = NULL; p = m_root; int i=1; while (p && p->data != key) f = p; i+; if (key < p->data) p = p ->lchild; else p = p->rchild; if ( p != NULL ) return i ; else return -1;第 4.2 题.(主观 题 5 分) 顺序队列的定义如下，使用循环数组，并保证留一个空的单元以区分队列满的状态。请完成队列成员函数Clear,Empty,GetHead,Append,Remove的实现。templat

28、e <class ElemType> / 声明一个类模板class SqQueuepublic: SqQueue(int m = 100); / 构造函数 SqQueue(); / 析构函数 void Clear(); / 清空队列 bool Empty() const; / 判队列空 int Length() const; / 求长度 ElemType & GetHead() const; / 取队头元素值 ElemType & GetLast() const; / 取队尾元素值 void Append(const ElemType &e); / 入队 v

29、oid Remove(); / 出队private: ElemType *m_base; / 基地址指针 int m_front; / 队头指针 int m_rear; / 队尾指针 int m_size; / 向量空间大小;参考答案/ 清空队列template <class ElemType>void SqQueue <ElemType>:Clear()m_front = m_rear = 0;/ 判队列是否为空，若为空，则返回true，否则返回falsetemplate <class ElemType>bool SqQueue <ElemType>:Empty() constreturn m_front = m_rear;/ 取队头元素的值。先决条件是队列非空template <class ElemType>ElemType & SqQueue <ElemType>:GetHead() constreturn m_basem_front;/ 入队，插入e到队尾template <class ElemType>void SqQueue <ElemType>:Append(const ElemType