2013專升本插班生考試《數(shù)據(jù)結構》課程試卷

韓山師范學院2013年專升本插班生考試試卷計算機科學與技術專業(yè)數(shù)據(jù)結構試卷（A卷）題號12345678910答案題號11121314151617181920答案1、從邏輯上可以把數(shù)據(jù)結構分為（）兩大類。動態(tài)結構、靜態(tài)結構B.順序結構、鏈式結構線性結構、非線性結構D.初等結構、構造型結構2、下面關于算法說法錯誤的是（）算法最終必須由計算機程序實現(xiàn)為解決某問題的算法同為該問題編寫的程序含義是相同的C．算法的可行性是指指令不能有二義性以上幾個都是錯誤的3、棧和隊列的共同特點是（）。只允許在端點處插入和刪除元素都是先進后出都是先進先出沒有共同點4、以下數(shù)據(jù)結構中，哪一個是線性結構（）？廣義表B.二叉樹C.稀疏矩陣D.串

5、下面關于線性表的敘述中，錯誤的是哪一個？（）線性表采用順序存儲，必須占用一片連續(xù)的存儲單元。線性表采用順序存儲，便于進行插入和刪除操作。線性表采用鏈接存儲，不必占用一片連續(xù)的存儲單元。線性表采用鏈接存儲，便于插入和刪除操作。6、靜態(tài)鏈表中指針表示的是（）。A.內存地址B.數(shù)組下標C.表頭地址D.下一元素地址7、若某線性表最常用的操作是存取任一指定序號的元素和在最后進行插入和刪除運算，則利用（）存儲方式最節(jié)省時間。A.順序表B.雙鏈表C.帶頭結點的雙循環(huán)鏈表D.單循環(huán)鏈表8、下列各種排序算法中平均時間復雜度為8、下列各種排序算法中平均時間復雜度為0血）是（）。A.快速排序A.快速排序B.堆排序歸并排序D.冒泡排序9、設散列表中有m個存儲單元,散列函數(shù)H（key）二key%p則p最好選擇）。A.小于等于m9、設散列表中有m個存儲單元,散列函數(shù)H（key）二key%p則p最好選擇）。A.小于等于m的最大奇數(shù)B.小于等于m的最大素數(shù)C.小于等于m的最大偶數(shù)D.小于等于m的最大合數(shù)10、字符串的長度是指（）。A.串中不同字符的個數(shù)B.串中不同字母的個數(shù)C.串中所含字符的個數(shù)D.串中不同數(shù)字的個數(shù)11、設指針變量top指向當前鏈式棧的棧頂，則刪除棧頂元素的操作序列為）。A.top=top+1;B.top=top-1;C.top->next=top;D.top=top->next;12、二叉排序樹可以得到一個從小到大的有序序列。（）A.先序遍歷B.中序遍歷C.后序遍歷D.層次遍歷13、時間復雜度不受數(shù)據(jù)初始狀態(tài)影響而恒為O（nlogn）的是（）。2A.堆排序B.冒泡排序C.希爾排序D.快速排序

14、設一個有序的單鏈表中有n個結點，現(xiàn)要求插入一個新結點后使得單鏈表仍然保持有序，則該操作的時間復雜度為()。A.O(logn)B.O(1)C.O(n2)D.O(n)215、設一棵二叉樹的深度為k,則該二叉樹中最多有()個結點。A.2k-1B.2kC.2k-1D.2k-116、設某有向圖的鄰接表中有n個表頭結點和m個表結點，則該圖中有()條有向邊。A.nB.n-1C.mD.m-117、已知一算術表達式的中綴形式為A+B*C-D/E,后綴形式為ABC*+DE/-,其前綴形式為()A．-A+B*C/DEB.-A+B*CD/EC．-+*ABC/DED.-+A*BC/DE18、設某強連通圖中有n個頂點，則該強連通圖中至少有()條邊。A.n(n-1)B.n+1C.nD.n(n+1)19、設一組初始記錄關鍵字序列(5,2,6,3,8),以第一個記錄關鍵字5為基準進行一趟快速排序的結果為()。A.2,3,5,8,6A.2,3,5,8,63,2,5,8,63,2,5,6,82,3,6,5,83,2,5,6,82,3,6,5,820、設無向圖的頂點個數(shù)為n,則該圖最多有()條邊。B．n(n-1)/2C．n(n+1)/2B．n(n-1)/2C．n(n+1)/2D．n2得分評卷人A．n-1二、填空題(每空2分,共20分)1、數(shù)據(jù)結構中評價算法的兩個重要指標是2、已知如下程序段FORi:=nDOWNTO1DO{語句1}BEGINx:=x+1；{語句2}FORj:=nDOWNTOiDO{語句3}

y:=y+1;{語句4}y:=y+1;END；TOC\o"1-5"\h\z語句3執(zhí)行的頻度為。3、解決散歹列表沖突的兩種方法是。4、判斷一個無向圖是一棵樹的條件是。5、設一棵二叉樹的前序序列為ABC,則有種不同的二叉樹可以得到這種序歹。6、設F和R分別表示順序循環(huán)隊列的頭指針和尾指針，則判斷該循環(huán)隊列為空的條件為。7、設有一個n階的下三角矩陣A，如果按照行的順序將下三角矩陣中的元素(包括對角線上元素)存放在n(n+1)個連續(xù)的存儲單元中，則A[i][j]與A[0][0]之間有個數(shù)據(jù)元素。8、已知8個數(shù)據(jù)元素為(34，76，45，18，26，54，92，65)按照依次插TOC\o"1-5"\h\z入結點的方法生成一棵二叉排序樹，則該樹的深度為。9、在一棵完全二叉樹中，若編號為i的結點有右孩子，則該右孩子結點的編號為。10、下面程序段的時間復雜度是。i=0；while(i<=N)i=i*3；得分評卷人得分評卷人每小題1分，共10分)1、順序存儲方式插入和刪除時效率太低，因此它不如鏈式存儲方式好。()2、向二叉排序樹中插入一個結點需要比較的次數(shù)可能大于該二叉樹的高度。()3、用鄰接矩陣法存儲一個圖所需的存儲單元數(shù)目與圖的邊數(shù)無關。()4、順序存儲方式只能用于存儲線性結構。()5、完全二叉樹中的葉子結點只可能在最后兩層中出現(xiàn)。()

6、無環(huán)有向圖才能進行拓撲排序。（）7、完全二叉樹一定是滿二叉樹，滿二叉樹不一定是完全二叉樹。（）8、對鏈表進行插入和刪除操作時不必移動鏈表中結點。（）9、一棵哈夫曼樹中不存在度為1的中間結點。（）10、強連通圖的各頂點間均可達。（）得分評卷人得分評卷人四、程序填空題（每個空1分，共10分）1、將二叉樹bt中每一個結點的左右子樹互換的C語言算法如下，其中ADDQ（Q,bt）,DELQ（Q）,EMPTY（Q）分別為進隊，出隊和判別隊列是否為空的函數(shù)，請?zhí)顚懰惴ㄖ械每瞻滋?，完成其功能。typedefstructnode{intdata;structnode*lchild,*rchild;}btnode;voidEXCHANGE(btnode*bt){btnode*p,*q;if(bt){ADDQ(Q,bt);while(!EMPTY(Q)){p二DELQ(Q);q=⑴;p->rchild=(2);(3)=q;if(p->lchild)(4);if(p->rchild)(5);}}}2、下列程序判斷字符串s是否對稱，對稱則返回1,否則返回0；如f（〃abba〃）返回1,f（〃abab〃）返回0；intf（（1））

{inti=O,.j二(2)while(s[j])(3)__;f