【文章內容簡介】 能分離)。(a*b*)*表示由字符a和b組成的任何長度的字符串(若干個a后面跟若干個b，b后面再跟若干個a)。只有(a*b*)*與(a｜b)*含義相同，因此正規(guī)式(a｜b)*與(a*b*)*是等價的。4喬姆斯基（Chomsky）將文法分為4種類型，程序設計語言的大多數語法現象可用其中的（ ）描述。 A. 上下文有關文法 B. 上下文無關文法 C. 正規(guī)文法 D. 短語結構文法 答案： B 上下文無關文法：形式語言理論中一種重要的變換文法，用來描述上下文無關語言，在喬姆斯基分層中稱為2型文法。由于程序設計語言的語法基本上都是上下文無關文法，因此應用十分廣泛。50、運行下面的C程序代碼段，會出現（ ）錯誤。int k=0。for(。k100。)。{k++。} A. 變量未定義 B. 靜態(tài)語義 C. 語法 D. 動態(tài)語義 答案： D 在本題中，for語句后有“?！碧枺f明該循環(huán)語句的語句體為空，此時，循環(huán)會是一個死循環(huán)，所以存在語義錯誤5在數據庫系統中，一般由DBA使用DBMS提供的授權功能為不同用戶授權，其主要目的是為了保證數據庫的（ ）。 A. 正確性 B. 安全性 C. 一致性 D. 完整性 答案： B DBMS是數據庫管理系統，主要用來保證數據庫的安全性和完整性。而DBA通過授權功能為不同用戶授權，主要的目的是為了保證數據的安全性。5給定關系模式R（U,F），其中：U為關系模式R中的屬性集，F是U上的一組函數依賴。假設U={A1，A2，A3，A4}，F={A1→A2，A1A2→A3，A1→A4，A2→A4}，那么關系R的主鍵應為（52）。函數依賴集F中的（53）是冗余的。 A. A1 B. A1A2 C. A1A3 D. A1A2A3 答案： A5 A. A1→A2 B. A1A2→A3 C. A1→A4 D. A2→A4 答案： C 本題中U1={AAAA4}，構造出依賴關系圖之后，A1是入度為0的結點，且從A1出發(fā)能遍歷全圖，因此A1為主鍵。A1→A2，A2→A4利用傳遞率：A1→A4，因此A1→A4是冗余。5給定關系R（A ， B ， C ，D）和關系S（A ，C ，E ，F），對其進行自然連接運算R?S后的屬性列為（54）個；(R?S)等價的關系代數表達式為（55）。 A. 4 B. 5 C. 6 D. 8 答案： C 5 A. B. C. D. 答案： B 關系R（A,B,C,D）和S（A,C,E,F）做自然連接時，會以兩個關系公共字段做等值連接，然后將操作結果集中重復列去除，所以運算后屬性列有6個5下列查詢B=“大數據”且F=“開發(fā)平臺”，結果集屬性列為A、B、C、F的關系代數表達式中，查詢效率最高的是（ ）。 A. π1,2,3,8 （σ2=39。大數據39。 ^ 1=5 ^ 3=6 ^ 8=39。開發(fā)平臺39。（RS）） B. π1,2,3,8 （σ1=5 ^ 3=6 ^ 8=39。開發(fā)平臺39。（σ2=39。大數據39。（R）S）） C. π1,2,3,8（σ2=39。大數據39。 ^ 1=5 ^ 3=6（Rσ4=39。開發(fā)平臺39。（S）） D. π1,2,3,8（σ1=5 ^ 3=6（σ2=39。大數據39。（R）σ4=39。開發(fā)平臺39。（S））） 答案： D5拓撲序列是有向無環(huán)圖中所有頂點的一個線性序列，若有向圖中存在弧v，w或存在從頂點v到w的路徑，則在該有向圖的任一拓撲序列中，v一定在w之前。下面有向圖的拓撲序列是（ ）。 A. 41235 B. 43125 C. 42135 D. 41325 答案： A 拓撲排序通俗一點來講，其實就是依次遍歷沒有前驅結點的結點。而某一時刻沒有前驅結點的結點有可能存在多個，所以一個圖的拓撲排序可能有多個。4號結點沒有前戲，所以拓撲排序的第一個元素是4。當4訪問完了就可以訪問1，1號訪問完了就可以訪問2，2號訪問完了就可以訪問3或5。所以拓撲排序結果為：412(35)5設有一個包含n個元素的有序線性表。在等概率情況下刪除其中的一個元素，若采用順序存儲結構，則平均需要移動（58）個元素；若采用單鏈表存儲，則平均需要移動（59）個元素。 A. 1 B. (n1)/2 C. logn D. n 答案： B 若用順序表存儲，則最好情況是刪除最后一個元素，此時不用移動任何元素，直接刪除，最差的情況是刪除第一個元素，此時需要移動n1個元素，所以平均狀態(tài)是移動(n1)/2。若用鏈表存儲，直接將需要刪除元素的前趨next指針指向后繼元素即可，不需要移動元素，所以移動元素個數為0。5設有一個包含n個元素的有序線性表。在等概率情況下刪除其中的一個元素，若采用順序存儲結構，則平均需要移動（58）個元素；若采用單鏈表存儲，則平均需要移動（59）個元素。 A. 0 B. 1 C. (n1)/2 D. n/2 答案： A 若用順序表存儲，則最好情況是刪除最后一個元素，此時不用移動任何元素，直接刪除，最差的情況是刪除第一個元素，此時需要移動n1個元素，所以平均狀態(tài)是移動(n1)/2。若用鏈表存儲，直接將需要刪除元素的前趨next指針指向后繼元素即可，不需要移動元素，所以移動元素個數為0。60、具有3個節(jié)點的二叉樹有（ ）種形態(tài)。 A. 2 B. 3 C. 5 D. 7 答案： C6以下關于二叉排序樹（或二叉查找樹、二叉搜索樹）的敘述中，正確的是（ ） 。 A. 對二叉排序樹進行先序、中序和后序遍歷，都得到結點關鍵字的有序序列 B. 含有n個結點的二叉排序樹高度為（log2n）+1 C. 從根到任意一個葉子結點的路徑上，結點的關鍵字呈現有序排列的特點 D. 從左到右排列同層次的結點，其關鍵字呈現有序排列的特點 答案： D6下表為某文件中字符的出現頻率，采用霍夫曼編碼對下列字符編碼，則字符序列“bee”的編碼為（62）；編碼“110001001101”的對應的字符序列為（63）。 A. 10111011101 B. 10111001100 C. 001100100 D. 110011011 答案： A6 A. bad B. bee C. face D. bace 答案： C 110001001101 中：f(1100) a(0) c(100) e(1101)。6兩個矩陣Am*n和Bn*p相乘，用基本的方法進行，則需要的乘法次數為m*n*p。多個矩陣相乘滿足結合律，不同的乘法順序所需要的乘法次數不同?？紤]采用動態(tài)規(guī)劃方法確定Mi，M(i+1)，…，Mj多個矩陣連乘的最優(yōu)順序，即所需要的乘法次數最少。最少乘法次數用m[i,j]表示，其遞歸式定義為：其中i、j和k為矩陣下標，矩陣序列中Mi的維度為（pi1）*pi采用自底向上的方法實現該算法來確定n個矩陣相乘的順序，其時間復雜度為（64）。若四個矩陣M MMM4相乘的維度序列為3，采用上述算法求解，則乘法次數為（65）。 A. O（n2） B. O（n2lgn） C. O（n3） D. O（n3lgn） 答案： C 四個矩陣分別為：2*6 6*3 3*10 10*3先計算：M1*M2 amp。nbsp。及M3*M4，計算次數分別為：2*6*3=36，3*10*3=90。然后結果相乘，計算次數為：2*3*3=18。36+90+18=144。6 A. 156 B. 144 C. 180 D. 360 答案： B 四個矩陣分別為：2*6 6*3 3*10 10*3先計算：M1*M2 amp。nbsp。及M3*M4，計算次數分別為：2*6*3=36，3*10*3=90。然后結果相乘，計算次數為：2*3*3=18。36+90+18=144。6以下協議中屬于應用層協議的是（66），該協議的報文封裝在（67）。 A. SNMP B. ARP C. ICMP D. 答案： A ARP和ICMP是網絡層協議，只有SNMP是應用層協議。SNMP協議的報文是封裝在UDP協議中傳送。6以下協議中屬于應用層協議的是（66），該協議的報文封裝在（67）。 A. TCP B. IP C. UDP D. ICMP 答案： C ARP和ICMP是網絡層協議，只有SNMP是應用層協議。SNMP協議的報文是封裝在UDP協議中傳送。6其中wb是（ ）。 A. 主機名 B. 協議名 C. 目錄名 D. 文件名 答案： A6如果路由器收到了多個路由協議轉發(fā)的關于某個目標的多條路由，那么決定采用哪條路由的策略是（ ）。 A. 選擇與自己路由協議相同的 B. 選擇路由費用最小的 C. 比較各個路由的管理距離 D. 比較各個路由協議的版本 答案： C 對于多種不同的路由協議到一個目的地的路由信息，路由器首先根據管理距離決定相信哪一個協議70、（ ）。 A. B. C. D. 答案： D 0011，假如網絡號采用22位。Software entities are more plex for their size than perhaps any other human construct, because no two parts are alike (at least above the statement level). If they are, we make the two similar parts into one, a（71）, open or closed. In this respect software systems differ profoundly from puters,buildings, or automobiles, where repeated elements abound.Digital puters are themselves more plex than most things people build。 they have very large numbers of states. This makes conceiving, describing, and testing them hard. Software sys