韓山師范學(xué)院2009年專升本插班生考試試卷計(jì)算機(jī)科學(xué)與技術(shù) 專業(yè) 數(shù)據(jù)結(jié)構(gòu) 樣卷題號(hào)一二三四五六七八九十總分評(píng)卷人得分一、單項(xiàng)選擇題（每題2分，共40分）題號(hào)12345678910答案題號(hào)11121314151617181920答案1.關(guān)于線性表的描述，錯(cuò)誤的是（ ） A. 線性表是線性結(jié)構(gòu) B. 線性表就是單鏈表 C. 線性表的順序存儲(chǔ)結(jié)構(gòu)，必須占用一片連續(xù)的存儲(chǔ)單元 D. 線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)，不必占用連續(xù)的存儲(chǔ)單元2.在存儲(chǔ)數(shù)據(jù)時(shí)，通常不僅要存儲(chǔ)各數(shù)據(jù)元素的值，而且還要存儲(chǔ)( )A.數(shù)據(jù)的處理方法 B.數(shù)據(jù)元素的類型 C.數(shù)據(jù)元素之間的關(guān)系 D.數(shù)據(jù)的存儲(chǔ)方法3.與單鏈表相比，雙鏈表的優(yōu)點(diǎn)之一是( )A.插入、刪除操作更簡(jiǎn)單 B.可以進(jìn)行隨機(jī)訪問C.可以省略表頭指針或表尾指針 D.順序訪問相鄰結(jié)點(diǎn)更靈活4. 對(duì)ｎ個(gè)不同的排序碼進(jìn)行冒泡排序，在元素?zé)o序的情況下比較的次數(shù)為( )A. n+1 B. n C. n-1 D. n(n-1)/25．如果結(jié)點(diǎn)A有3個(gè)兄弟，而且B為A的雙親，則B是度為（ ）A．3 B．4 C．5 D．16．在具有N個(gè)單元的順序存儲(chǔ)循環(huán)隊(duì)列中，假定front和rear分別為隊(duì)頭指針和隊(duì)尾指針，則判斷隊(duì)滿的條件為（ ）。

A．front == rear B．(rear+1) % MAXSIZE == frontC．front - rear==1 D．rear % MAXSIZE == front7. 某二叉樹的前序遍歷序列為 ABDGCEFH ，中序遍歷序列為 DGBAECHF ，則后序遍歷序列為（ ） A. BDGCEFHA B. GDBECFHA C. BDGAECHF D. GDBEHFCA 8．設(shè)無向圖的頂點(diǎn)個(gè)數(shù)為n，則該圖最多有（ ）條邊A. n-1 B. n(n-1)/2 C．n(n+1)/2 D. 09. 在一個(gè)長(zhǎng)度為N的線性表中順序查找值為x的元素時(shí)，在等概率的情況下查找成功時(shí)的平均查找長(zhǎng)度為（ ）A. N B. N/2 C. (N+1)/2 D. (N-1)/210．深度為5的二叉樹至多有( )個(gè)結(jié)點(diǎn)A.16 B.32 C.31 D.1011. 堆的形狀是一棵( ) A. 二叉排序樹 B.滿二叉樹 C. 完全二叉樹 D. 平衡二叉樹12．下列關(guān)于數(shù)據(jù)結(jié)構(gòu)的敘述中，正確的是( )。

A. 數(shù)組是同類型值的集合 B. 樹是一種線性結(jié)構(gòu)C. 遞歸算法的程序結(jié)構(gòu)比迭代算法的程序結(jié)構(gòu)更為精煉D. 用一維數(shù)組存儲(chǔ)二叉樹，總是以先序遍歷的順序存儲(chǔ)各結(jié)點(diǎn)13. 在具有 n(n>1) 個(gè)結(jié)點(diǎn)的完全二叉樹中，結(jié)點(diǎn) i(2*i>n) 的左孩子結(jié)點(diǎn)是（ ） A. 2*i B. 2*i+1 C. 不存在 D. 2*i-1 14. 在有n個(gè)結(jié)點(diǎn)的二叉樹中，值為非空的鏈域的個(gè)數(shù)為(?????)A.?n-1????????B.?2*n-1?? C.?n+1??? ??D.?2*n+115. 若對(duì)一個(gè)已排好序的序列進(jìn)行排序，在下列四種方法中，哪種比較好（ ）A. 冒泡法 B. 直接選擇法 C. 直接插入法 D. 歸并法 16. 設(shè)單鏈表中指針p指向結(jié)點(diǎn)A，若A的后繼結(jié)點(diǎn)存在，則刪除該后繼結(jié)點(diǎn)需要修改指針的操作為（ ）A．p->next=p->next->next B．p=p->nextC．p=p->next->next D．p->next=p17. 隊(duì)列操作的原則是(???? ?)。

A. 先進(jìn)先出 ?B. 后進(jìn)先出 ?C. 只能進(jìn)行插入 ?D. 只能進(jìn)行刪除18. 對(duì)樹進(jìn)行層次遍歷時(shí)，通常是采用( )作為輔助來實(shí)現(xiàn)算法的A．棧 B. 隊(duì)列 C. 樹 D. 圖 19. ( )是順序存儲(chǔ)方式的優(yōu)點(diǎn)A. 存儲(chǔ)密度大 B. 插入運(yùn)算方便 C. 刪除運(yùn)算方便 D. 可方便地用于各種邏輯結(jié)構(gòu)的存儲(chǔ)表示20. 數(shù)組A[5][6]的每個(gè)元素占5個(gè)單元，將其按行優(yōu)先次序存儲(chǔ)在起始地址為1000的連續(xù)的內(nèi)存單元中，則元素A[5,5]的地址為(??? ??)A.?1140?? ??B.?1145 ??C.?1120? ??D.?1125二、判斷題（每題1分，共10分）以下各種說法，你認(rèn)為對(duì)的在前面括號(hào)打√，錯(cuò)誤的打×?????)1．隊(duì)列只能采用鏈?zhǔn)酱鎯?chǔ)方式 (?????)2.二叉樹的度一定是2?????)3.線性結(jié)構(gòu)也是一種樹結(jié)構(gòu)?????)4.有向圖用鄰接表表示后，頂點(diǎn)i的入度等于該頂點(diǎn)對(duì)應(yīng)的單鏈表的元素個(gè)數(shù)?????)5．滿二叉樹一定有偶數(shù)個(gè)結(jié)點(diǎn)?????)6．直接插入排序的關(guān)鍵碼比較次數(shù)與初始排列有關(guān)。

?????)7．順序存儲(chǔ)方式只能用于存儲(chǔ)線性結(jié)構(gòu) )8. 給出不同的輸入序列建造二叉排序樹，一定得到不同的二叉排序樹?????)9．在對(duì)鏈隊(duì)列作出隊(duì)操作時(shí)，不會(huì)改變front指針的值 )10. 堆排序是不穩(wěn)定排序三、填空題（每空2分，共18分）1．中綴算式（3+4）*2 /（8-5）所對(duì)應(yīng)的后綴算式為______ __2. 某算法的時(shí)間復(fù)雜度為(5*n2+1000*n*log2n+4*n-8)/(10*n)，其數(shù)量級(jí)表示為______________3. 用1000個(gè)結(jié)點(diǎn)構(gòu)造的二叉樹，最少___________層，最多__________層4. 假定一個(gè)線性表為(12,23,74,55,63,40,82,36)，若按Key % 3條件進(jìn)行劃分，使得同一余數(shù)的元素成為一個(gè)子表，則得到的三個(gè)子表分別為____________________、___________________和_____________________5. 假定一棵二叉樹廣義表表示為a(b(c),d(e,f))，其中序遍歷序列為____________________，層次遍歷序列為_____________________。

四、程序填空題（每個(gè)語(yǔ)句2分，共12分）1．下面是向以BST為樹根指針的二叉搜索樹上插入值為item的結(jié)點(diǎn)的遞歸算法請(qǐng)將缺失語(yǔ)句填上void Insert(BTreeNode*& BST, const ElemType& item){ if( BST == NULL ) { BTreeNode* p = new BTreeNode;p->data = item; _______________________; BST = p;}else if( item < BST->data ) ___________________; else ________________________; }2．下面是向單鏈表的末尾添加一個(gè)元素的算法請(qǐng)將缺失的語(yǔ)句填上Void InsertRear( LNode*& HL, const ElemType& item ){ LNode* newptr;newptr = new LNode;if ( newptr == NULL ){cerr << "Memory allocation failare!" << endl;exit( 1 );}newptr->data = item;_________________if ( HL == NULL ) HL = newptr;else{____________________;while ( ) p = p->next;p->next = newptr;}}五、算法設(shè)計(jì)題（20分）1．編寫算法函數(shù)，把順序表List原地置逆。

10分)順序表的數(shù)據(jù)結(jié)構(gòu)如下： typedef struct{ int data[100]; int last;//最后元素的下標(biāo)} SeqList;函數(shù)原形為：void fnReverse( SeqList &List );2.二叉樹采用左右孩子指針存儲(chǔ)結(jié)構(gòu)：Struct TreeNode{ Int data;//數(shù)據(jù)域 Struct TreeNode *left, *right;//指向其左右孩子結(jié)點(diǎn)};請(qǐng)編寫一個(gè)遞歸函數(shù)，要在一棵樹T中，找出值是x的結(jié)點(diǎn)的兄弟結(jié)點(diǎn)10分)函數(shù)原形如下：Struct TreeNode *fnGetBrother( Struct TreeNode *T, int x );。