1、大學專業考試試卷天津工業大學算法與數據結構考試試卷及參考答案1一、單項選擇題(5)1 .下列關于線性表的敘述中正確的是()。A、線性表的邏輯順序與物理順序總是一致的B、線性表的順序存儲表示優于鏈式存儲表示C、線性表若采用鏈式存儲表示時所有存儲單元的地址可連續或可不連續D每種數據結構都應具備三種基本運算：插入、刪除和查找答案：C2 .對一個初始為空的棧S執行操作S.Push(5),S.Push(2),S.Push(4),S.Pop(x),S.getTop(x)后，x的值應是()。A5B、2C、4D0答案：B3 .將遞歸算法轉換成對應的非遞歸算法時，除了單向遞歸和尾遞歸的情況外，通常需要使用()保

2、存中間結果。A、鏈表B、棧C、隊列D順序表答案：B4 .算法的時間復雜度的表示方法是：()。A、實現算法的程序在指定機器上執行的時間B、標準程序在機器上的執行時間C、基本操作重復次數，即問題規模n的某個函數D、與刻畫基本操作重復次數的函數同階無窮大的函數f(n)答案：D大學專業考試試卷5 .在樹中，樹的度與結點的度之間的關系是：()。A、樹的度就是結點的度B、樹的度為2,結點的度可以是0,1和2C、結點度中最大值為樹的度D、樹的度與結點的度無關答案：C6 .用鏈接方式存儲的隊列，在進行插入運算時：A、僅修改頭指針頭、尾指針都要修改B、頭、尾指針都要修改C、僅修改尾指針D、頭、尾指針可能都要修改

3、答案：D7 .設有一個二維數組Amn,假設A00存放位置在644(10),A22存放位置在676(10),每個元素占一個空間，問A33(10)存放在什么位置？腳注(10)表示用10進制表示。A、688B、678C、692D、696答案：C8 .最好情況下插入排序的比較次數是：()。AO(n)BnCn-1DO(n*n)答案：C二、多項選擇題(5)1 .以下程序段的完成的功能是():/*head是指向由data和link兩個域的結大學專業考試試卷點構成的單向鏈表頭*/P=head;While(p!=NULL)Printf(p-data);P=p-link;A、對鏈表的遍歷B、輸出了鏈表中所有數據信

4、息C、沒有功能，因為只是輸出與循環D、輸出了除表頭結之外的所有結點信息答案：AB2 .數據是信息的載體，它有以下幾種形式():A、整數和實型數B、字符串C、圖像和聲音D、信息E、磁盤文件答案：ABC3 .一維數組元素的類型可以是():A、簡單變量，如整數、浮點數B、復合變量，如結構體，數組C、只有簡單變量D、指針變量E、字符串答案：ABD4 .在算法分析與數據結構中，算法描述方法有():A、自然語言B、框圖C、類計算機語言D、數據結構答案：ABC5 .一棵含有25個結點的完全二叉樹的深度是多少():A、4大學專業考試試卷B、5C、6D、log225答案：AD二、判斷題（5）1 .數組是一種靜態

5、的存儲空間分配，就是說，在程序設計時必須預先定義數組的數據類型和存儲空間大小，由編譯程序在編譯時進行分配。答案：錯誤2 .順序存儲方式只能用于存儲線性結構。答案：錯誤3 .任意圖都是其自身的子圖。答案：正確4 .如果圖中有一部分邊的權為負值，那么用Dijkstra算法求圖的最短路徑是可行的。答案：錯誤5 .線性表中的元素只能是簡單類型。答案：錯誤6 .線性表是數組。答案：錯誤7 .指針就是地址，有人在數組中采用指示下標值的方法實現單向鏈表。另外的人說這不是鏈表結構，他的說法對嗎？答案：錯誤8 .棧滿是數據對象棧的固有操作。答案：錯誤9 .在求最短路徑的Dijkstra算法和Floyd算法中，D

6、ijkstra算法只能求從一點到其他各點的最短路徑，而Floyd算法可以求圖中兩兩點之間的最短路徑。答案：錯誤大學專業考試試卷填空題（5）1 .棧只能在插入和刪除元素；對于隊列只能在插入和刪除元素。答案：棧頂；隊尾；隊首2 .一棵具有257個結點的完全二叉樹，它的深度為。答案：93 .在一個順序棧中，若棧頂指針等于,則為空棧；若棧頂指針等于則為滿棧。答案：-1,maxSize-1簡答題（20）1 .數據的邏輯結構分為線性結構和非線性結構兩大類。線性結構包括數組、鏈表、棧、隊列、優先級隊列等；非線性結構包括樹、圖等。這兩類結構各自的特點是什么？答案：線性結構的特點是：在結構中所有數據成員都處于一

7、個序列中，有且僅有一個開始成員和一個終端成員，并且所有數據成員都最多有一個直接前驅和一個直接后繼。非線性結構的特點是：一個數據成員可能有零個、一個或多個直接前驅和直接后繼。2 .試寫出如圖所示的二叉樹分別按先序、中序、后序遍歷時得到的結點序列。答案：DLRABDFJGKCEHILMLDR:BFJDGKACHELIMLRD:JFKGDBHLMIECA大學專業考試試卷3 .如果一棵有n個結點的滿二叉樹的深度為d(樹根所在的層次為1),則給出推導式：(1)用深度d表達其結點總數n。(2)用結點總數n表達深度do(3)若對該樹的結點從1開始按中序遍歷次序進行編號，則樹根結點的編號如何用d表示？樹根結點的左子女結點的編號如何用d表示？右子女結點的編號如何用d表小?答案：(1)對于深度為d的滿二叉樹，結點個數為n=