數(shù)據(jù)結(jié)構(gòu)C++模擬卷子2

1、第 1 題.( 復(fù)合題 共計 20 分) 簡答題第 1.1 題.(主觀 題 5 分) 已知用二元組表示的數(shù)據(jù)結(jié)構(gòu)如下，請畫圖表示其數(shù)據(jù)關(guān)系，并說明該數(shù)據(jù)結(jié)構(gòu)屬于哪種邏輯結(jié)構(gòu)？（本小題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>參考答案邏輯結(jié)構(gòu)：圖圖示結(jié)構(gòu)：略(課本p158圖5.2a)第 1.2 題.(主觀 題 5 分) 設(shè)一個有序順序表中存放以下整數(shù)：16，87，154，170，275，426，503，509，512，612

2、，653，677，703，765，897，908。運(yùn)用二分（折半）法檢索元素，請問：（1）檢索612，需要經(jīng)過多少次比較？每次比較的元素是什么？（2）檢索900，需要經(jīng)過多少次比較才能確定其不存在？每次比較的元素是什么？參考答案檢索元素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，因?yàn)?900<908，high=mid-1為14，使得low>high，檢索停止，900不存在。第 1.3 題.(主觀 題 5 分) 設(shè)有編號為1，2，3，4的4輛列車，依次順序開進(jìn)一個棧式結(jié)構(gòu)的站臺，問是否有3，2，4，1和4，1，3，2兩種開出車站的可能？如有，該如何操作？參考答案順序3，2，4，1是可能的，操作方法：1、2、3號車依次開進(jìn)車站，3、2號車依次出站，4號車進(jìn)站然后出站，最后1號車出站。順序4，1，3，2是不可能的。第 1.4 題.(主觀 題 5 分) 假設(shè)一棵二叉

4、樹的中序遍歷為DCBGEAHFIJK，后序遍歷為DCEGBFHKJIA，請問：（1）該二叉樹每層各有多少個結(jié)點(diǎn)？（2）該二叉樹的形態(tài)是怎樣的？請畫圖表示。參考答案（1）每一層：1個結(jié)點(diǎn)；第二層：2個結(jié)點(diǎn)；第三層：4個結(jié)點(diǎn)；第四層：4個結(jié)點(diǎn)。二叉樹：圖略（課本P155習(xí)題）第 2 題.( 復(fù)合題 共計 25 分) 算法分析題第 2.1 題.(主觀 題 5 分) 順序表定義如課本。順序表初始設(shè)置的參數(shù)size為10，存儲的數(shù)據(jù)為12，3，8，41，63，25，16，36，23。第1次調(diào)用下列函數(shù)的實(shí)參是（100，1），第2次調(diào)用的實(shí)參是（10，11）。請問：（1）第1次調(diào)用后，存儲的數(shù)據(jù)是什么？參

5、數(shù)size是多少？（2）第2次調(diào)用后，存儲的數(shù)據(jù)是什么？參數(shù)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 分) 帶頭結(jié)點(diǎn)的單

7、鏈表定義如課本。下列算法對序列12，6，1，25，41，36，21，15，19，7連續(xù)進(jìn)行操作，請問：（1）第1次調(diào)用時實(shí)參表是（e，4），則操作完成后的序列是什么？變量e存儲的值是什么？（2）第2次調(diào)用時實(shí)參表是（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）以下程序執(zhí)行后，輸出是什么？（2）外循環(huán)執(zhí)行了多少次？（3）在程序運(yùn)行中，發(fā)生了數(shù)據(jù)交換，那些數(shù)據(jù)之

9、間發(fā)生了交換？這些交換的數(shù)據(jù)都有什么特點(diǎn)？#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的數(shù)據(jù)與一個大于0的數(shù)據(jù)交換。第 2.4 題.(主觀 題 5 分) 對于序列15，88，36，9，2，95，5，請問：（1）在執(zhí)行下列算法的過程中，外循環(huán)每次完成后的數(shù)據(jù)序列是怎樣的？請完整寫出來。（2）這是什

11、么算法？請寫出名稱，并寫出其時間復(fù)雜度。（3）該算法的外循環(huán)執(zhí)行了多少次？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 分) 下列程序中要運(yùn)用隊列進(jìn)行數(shù)據(jù)處理，鏈?zhǔn)疥犃械亩x如課本。參數(shù)v中存儲整數(shù)：1，2，3，4，5，6，7，8，9，10 。請問處理結(jié)果的數(shù)據(jù)序列是怎樣的？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();參考答案把數(shù)據(jù)送進(jìn)隊列，然后按先兩側(cè)后中間的次序放回數(shù)組中，結(jié)果是：1 3 5 7 9 10 8 6 4 2第 3 題.( 復(fù)合題 共計 30 分) 算法填空題第 3.1 題.(主觀 題 5 分) 下列算法對兩組順序表的數(shù)據(jù)進(jìn)行處理，順序表的定義如課本。請問：（1）La存儲的數(shù)據(jù)是2，5，12，24，Lb存儲的數(shù)據(jù)是1，3，6，7，8，9

14、，11，處理結(jié)束時，Lc存儲的數(shù)據(jù)是什么？（2）程序中有三個循環(huán)，分別用“語句1”。表示。對于（1）給出的數(shù)據(jù)，執(zhí)行的循環(huán)語句有哪些？循環(huán)開始時的變量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存儲的數(shù)據(jù)是1，2，3，5

16、，6，7，8，9，11，12，24（2）執(zhí)行了循環(huán)語句1和語句2。執(zhí)行語句1時i是0，j是0；執(zhí)行語句2時，i是3，j是8第 3.2 題.(主觀 題 5 分) 二叉樹的表定義如課本。下列算法是運(yùn)用棧對二叉樹進(jìn)行中序遍歷的算法。請把算法補(bǔ)充完整。如果用a1表示結(jié)點(diǎn)a入棧操作，a0表示出棧操作，n1表示空結(jié)點(diǎn)指針進(jìn)棧，n0表示出棧。對于課本P114圖4.9的二叉樹，寫出結(jié)點(diǎn)入棧出棧的過程。/ 中序遍歷二叉樹的非遞歸算法(利用棧)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） ; 參考答案補(bǔ)充完整算法：（1）m_root（2）p=p->lchild（3）S.push(p)（4）!S.empty

18、()（5）S.push(p->rchild)結(jié)點(diǎn)進(jìn)出棧過程：按照0的次序取字母，得到中序序列dbgheafca1b1d1n1 n0d0 n1n0 b0e1g1 n1n0 g0h1 n1n0 h0 n1n0 e0 n1n0 a0c1f1 n1n0 f0 n1n0 c0 n1n0 第 3.3 題.(主觀 題 5 分) 二叉樹定義如課本。（1）請說明下列算法的功能；（2）說明該處理結(jié)果可以得到的信息有哪些？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）該算法能夠在二叉樹中查找結(jié)點(diǎn)值為e的結(jié)點(diǎn)指針；（2）算法處理結(jié)果得到的信息有兩個可能，一是沒有找到值為e的結(jié)點(diǎn)，返回值為NULL（空指針）；二是查到該結(jié)點(diǎn)，則返回指向該結(jié)點(diǎn)的指針。第 3.4

20、題.(主觀 題 5 分) 以下是二分法檢索算法，請補(bǔ)充完整算法，并說明，該算法處理結(jié)束時能夠返回什么信息？/折半查找template <class ElemType,class KeyType >int BinarySearch(StaticTable<ElemType, KeyType > &R,const KeyType key) / low表示所查區(qū)間的下界，high表示所查區(qū)間的上界 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 ; 參考答案補(bǔ)充完整算法：（1）(low + high) / 2（2）R.m_datasmid = key（3）high = mid - 1（4）low = mid + 1（5）return該算法結(jié)束時，返回的信息有兩種可能：一是查找成功，返回關(guān)鍵碼所在位置，二是查找失敗，返回-1。第 3.5 題.(主觀 題 5 分) 二叉樹定義如課本，下列算法實(shí)現(xiàn)二叉樹非遞歸前序遍歷。用a1表示結(jié)點(diǎn)a進(jìn)棧，a0表示出棧。對于課本P110圖4.7，寫出結(jié)點(diǎn)進(jìn)出棧的過程。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 分) 二叉排序樹的定義如課本，下列算法在二叉排序樹查找結(jié)點(diǎn)，如果查找成功，則獲得該結(jié)點(diǎn)的指針p和父結(jié)點(diǎn)的指針f，并返回true，否則返回false。請把算法補(bǔ)充完整。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 題.( 復(fù)合題 共計 15 分) 算法設(shè)計題第 4.1 題.(主觀 題 5 分) 在二叉排

25、序樹中查找給定關(guān)鍵字結(jié)點(diǎn)的算法如下，請對下列算法稍作修改，在查找結(jié)點(diǎn)的同時，確定其所在層次，若查找成功，返回該結(jié)點(diǎn)所在層數(shù)，否則，返回。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 分) 順序隊列的定義如下，使用循環(huán)數(shù)組，并保證留一個空的單元以區(qū)分隊列滿的狀態(tài)。請完成隊列成員函數(shù)Clear,Empty,GetHead,Append,Remove的實(shí)現(xiàn)。templat

28、e <class ElemType> / 聲明一個類模板class SqQueuepublic: SqQueue(int m = 100); / 構(gòu)造函數(shù) SqQueue(); / 析構(gòu)函數(shù) 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