2015年韓山師范學(xué)院本科插班生《數(shù)據(jù)結(jié)構(gòu)》試卷

1、（a卷）第 6 頁(yè) 共 6 頁(yè)2015年韓山師范學(xué)院本科插班生考試試卷計(jì)算機(jī)科學(xué)與技術(shù) 專業(yè) 數(shù)據(jù)結(jié)構(gòu) 試卷（a卷）一、 單項(xiàng)選擇題（每題2分，共30分）1. 棧和隊(duì)列的共同特點(diǎn)是( )。a. 只允許在端點(diǎn)處插入和刪除元素 b. 都是先進(jìn)后出 c. 都是先進(jìn)先出 d. 沒(méi)有共同點(diǎn) 2. 用鏈接方式存儲(chǔ)的隊(duì)列，在進(jìn)行插入運(yùn)算時(shí)( )。 a. 僅修改頭指針 b. 頭、尾指針都要修改 c. 僅修改尾指針 d. 頭、尾指針可能都要修改3. 以下數(shù)據(jù)結(jié)構(gòu)中哪一個(gè)是非線性結(jié)構(gòu)？( ) a. 隊(duì)列 b. 棧 c. 線性表 d. 二叉樹(shù)4. 設(shè)有一個(gè)二維數(shù)組amn，假設(shè)a00存放位置在644，a22存放位置在

2、676，每個(gè)元素占一個(gè)空間，問(wèn)a33存放在什么位置？ a688 b678 c692 d6965. 樹(shù)最適合用來(lái)表示( )。 a.有序數(shù)據(jù)元素 b.無(wú)序數(shù)據(jù)元素 c.元素之間具有分支層次關(guān)系的數(shù)據(jù) d.元素之間無(wú)聯(lián)系的數(shù)據(jù)6. 二叉樹(shù)的第k層的結(jié)點(diǎn)數(shù)最多為( )。 a2k-1 b.2k+1 c.2k-1 d. 2k-17. 設(shè)有向無(wú)環(huán)圖g中的有向邊集合e=<1，2>，<2，3>，<3，4>，<1，4>，則下列屬于該有向圖g的一種拓?fù)渑判蛐蛄械氖牵?）。a. 1,2,3,4b. 2,3,4,1c. 1,4,2,3d. 1,2,4,38. 下列關(guān)于數(shù)據(jù)

3、結(jié)構(gòu)的敘述中，正確的是 （ ）。 a. 數(shù)組是同類型值的集合 b. 樹(shù)是一種線性結(jié)構(gòu) c. 一般情況下遞歸算法的程序結(jié)構(gòu)更為精煉、效率更高 d. 用一維數(shù)組存儲(chǔ)二叉樹(shù)，總是以先序遍歷的順序存儲(chǔ)各結(jié)點(diǎn)9. 對(duì)于線性表（7，34，55，25，64，46，20，10）進(jìn)行散列存儲(chǔ)時(shí)，若選用h（k）=k % 9作為散列函數(shù)，則散列地址為1的元素有（ ）個(gè)。 a1 b2 c3 d410. 設(shè)有6個(gè)結(jié)點(diǎn)的無(wú)向圖，該圖至少應(yīng)有( )條邊才能確保是一個(gè)連通圖。 a. 5 b. 6 c. 7 d. 811. 在帶有頭結(jié)點(diǎn)的單鏈表hl中，要向表頭插入一個(gè)由指針p指向的結(jié)點(diǎn)，則執(zhí)行( )。a. p->next

4、=hl->next; hl->next=p; b. p->next=hl; hl=p; c. p->next=hl; p=hl; d. hl=p; p->next=hl;12. 線性表采用鏈?zhǔn)酱鎯?chǔ)時(shí)，結(jié)點(diǎn)的存儲(chǔ)地址（ ）。 a必須是不連續(xù)的 b連續(xù)與否均可 c必須是連續(xù)的 d和頭結(jié)點(diǎn)的存儲(chǔ)地址相連續(xù)13. 任何一個(gè)無(wú)向連通圖的最小生成樹(shù)（ ）。a. 只有一棵 b. 一棵或多棵 c. 一定有多棵 d. 可能不存在14. 設(shè)指針變量p指向單鏈表結(jié)點(diǎn)a，則刪除結(jié)點(diǎn)a的后繼結(jié)點(diǎn)b需要的操作為（ ）。a. p->next=p->next->nextb. p

5、=p->nextc. p=p->next->nextd. p->next=p15. 設(shè)某棵二叉樹(shù)的中序遍歷序列為abcd，前序遍歷序列為cabd，則后序遍歷該二叉樹(shù)得到序列為（ ）。a. bcdab. badcc. cdabd. cbda二、填空題（每空2分，共20分）1. 一個(gè)算法的時(shí)間復(fù)雜度為(n3+n2log2n+14n)/n2，其數(shù)量級(jí)表示為_(kāi)。2. 假定一棵樹(shù)的廣義表表示為a（c，d（e，f，g），h（i，j），則該樹(shù)的深度為_(kāi)，樹(shù)的度為_(kāi)。3. 后綴算式9 2 3 +- 10 2 / -的值為_(kāi)。中綴算式（3+4x）-2y/3對(duì)應(yīng)的后綴算式為_(kāi)。4. 若用鏈

6、表存儲(chǔ)一棵二叉樹(shù)時(shí)，每個(gè)結(jié)點(diǎn)除數(shù)據(jù)域外，還有指向左孩子和右孩子的兩個(gè)指針。在這種存儲(chǔ)結(jié)構(gòu)中，n個(gè)結(jié)點(diǎn)的二叉樹(shù)共有_個(gè)指針域，其中有_個(gè)指針是空指針。5. 有如下遞歸函數(shù)：void f( int w ) int i; static int j=1; if (w>0) printf(“%d:”,j+);for ( i=1; i<=w; i+ ) printf( “%d，”, w );printf( “n” );f( w 1 );調(diào)用語(yǔ)句f(3)的結(jié)果是_。6. 已知一有向圖的鄰接表存儲(chǔ)結(jié)構(gòu)如下：從頂點(diǎn)1出發(fā)，dfs遍歷的輸出序列是_，bfs遍歷的輸出序列是_。得分評(píng)卷人三、判斷題（對(duì)的

7、劃，錯(cuò)的劃×。每小題1分，共10分）（ ）1調(diào)用一次深度優(yōu)先遍歷可以訪問(wèn)到圖中的所有頂點(diǎn)。（ ）2哈夫曼樹(shù)上只有樹(shù)葉或者雙支結(jié)點(diǎn)。（ ）3冒泡排序在初始關(guān)鍵字序列為遞減有序的情況下執(zhí)行的交換次數(shù)最多。（ ）4滿二叉樹(shù)一定是完全二叉樹(shù)，完全二叉樹(shù)不一定是滿二叉樹(shù)。（ ）5已知一棵二叉樹(shù)的先序序列和后序序列，則能夠唯一確定該二叉樹(shù)的形狀。（ ）6層次遍歷二叉樹(shù)需要用到堆棧作為輔助結(jié)構(gòu)。（ ）7一棵樹(shù)按孩子兄弟法轉(zhuǎn)化成二叉樹(shù)，該二叉樹(shù)中一定沒(méi)有右子樹(shù)。（ ）8線性表的順序存儲(chǔ)結(jié)構(gòu)比鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)更好。（ ）9可以在有序單鏈表中實(shí)現(xiàn)二分查找算法。（ ）10. 兩個(gè)棧共享一片連續(xù)內(nèi)存空間時(shí)，為提

8、高內(nèi)存利用率，減少溢出機(jī)會(huì)，應(yīng)把兩個(gè)棧的棧底分別設(shè)在這片內(nèi)存空間的兩端。得分評(píng)卷人四、程序填空題（每個(gè)空2分，共10分）1. 下面程序段的功能實(shí)現(xiàn)數(shù)據(jù)x進(jìn)棧，要求在下劃線處填上正確的語(yǔ)句。#define m 100typedef struct int sm; int top; sqstack;void push( sqstack *stack, int x )if (stack->top=m-1) printf(“overflow”);else _;_;2下面算法是求二叉樹(shù)雙支個(gè)數(shù)的算法。請(qǐng)完成填空。struct treenode int data; struct treenode *l

9、eft, *right; ;int fngetleaf( treenode *t ) if(_) return 0; if( t->left!=null && t->right!=null) return (_); else return(_);得分評(píng)卷人五、分析簡(jiǎn)答題（10分）1（4分）試寫(xiě)出如圖所示的二叉樹(shù)分別按中序、后序遍歷時(shí)得到的結(jié)點(diǎn)序列。2. （6分）用序列（46，68，45，139，70，58，101，10，88，94）建立一個(gè)二叉排序樹(shù)，畫(huà)出該樹(shù)，并求在等概率情況下查找成功的平均查找長(zhǎng)度。得分評(píng)卷人六、算法設(shè)計(jì)題（20分）1、（8分）刪除順序表前i個(gè)元素。已知順序表的數(shù)據(jù)結(jié)構(gòu)如下：#define maxsize 100 typedef struct int datamaxsize; int last; seqlist;使用如下函數(shù)原型：bool fndelete( seqlist *l, int i );/成功刪除則返回true，否則返回false2、 (12分)假設(shè)二叉樹(shù)采用左右孩子指針存儲(chǔ)結(jié)構(gòu)，即其結(jié)點(diǎn)數(shù)據(jù)類型描述為：struct treenode int dat