2021年上半年软件设计师上午真题及答案解析（六）
51、如下圖如下E-R圖中，兩個實體R1、R2之間有一個聯系E，當E的類型為（ ）時必須將E轉換成—個獨立的關系模式？
A.1:1
B.1:*
C.*:1
D.*:*
參考答案：D
答案解析：
E-R圖轉關系模式轉換原則：實體必須單獨轉換為1個關系模式。
聯系根據類型不同：
- 1對1聯系可以轉換為獨立的關系模式，也可以歸并到任意一端實體中。
- 1對多聯系可以轉換為獨立的關系模式，也可以歸并到多端實體中。
- 多對多聯系只能轉換為獨立的關系模式，不能歸并。
52、53、給定關系R (U,F)，其中U={A,B,C,D,E,H}，F={A→B，B→DH，A→H,C→E}。關系有（ ），F中（ ）。
1）
A.一個候選碼A
B.2個候選碼A、B
C.一個候選碼AC
D.兩個候選碼A、C
2）
A.不存在傳遞依賴，但存在冗余函數依賴
B.既不存在傳遞依賴,也不存在冗余函數依賴
C.存在傳遞依賴A→D和A→H，但不存在冗余函數依賴
D.存在傳遞依賴A→D和A→H，并且還存在冗余函數依賴
參考答案：CD
答案解析：
- 第一空，關于候選鍵分析，其中A和C是入度為0的屬性，所以候選鍵集合必須包含AC組合鍵，選擇C選項。
- 第二空，本題A→B，B→DH，存在傳遞函數依賴A→DH，此時根據armstrong公理，可以分解得到A→D和A→H，此時F中A→H是冗余函數依賴，選擇D選項。
54、55、56、某銷售公司員工關系E（工號、姓名、部門名、電話、住址），商品關系C（商品號、商品名、庫存數）和銷售關系EC（工號、商品號、銷售數、銷售日期）。查詢“銷售部1”在2020年11月11日銷售“HUWEI Mate40”商品的員工工號、姓名、部門名及其銷售的商品名，銷售數的關系代數表達式為π1,2,3,7,8( ( ) ? ( ( ) ? ( ) ) )
1）
A.σ3=銷售部1(E)
B.σ3=銷售部1(C)
C.σ3=‘銷售部1’(E)
D.σ3=‘銷售部1’(C)
2）
A.π2,3(σ2=‘HUWEI Mate40 ’(C))
B.π1,2(σ2= ‘HUWEI Mate40 ’(C))
C.π2,3(σ2=‘HUWEI Mate40 ’(EC))
D.π1,2(σ2=‘HUWEI Mate40 ’(EC))
3）
A.σ4=‘2020年11月11日’(C)
B.σ3=‘2020年11月11日’(C)
C.σ4=‘2020年11月11日’(EC)
D.σ3=‘2020年11月11日’(EC)
參考答案：CBC
答案解析：
本題考查的是關系代數相關知識內容。
本題看起來邏輯非常復雜，涉及到了3個關系表的聯合使用，但結合選項來看，可以快速找到正確答案。
首先對于第一空，選擇的對象一定是表E或表C，而此時C是沒有部門名的，因此篩選對象一定是表E，其次判斷某個列的取值，需要用引號標注，排除錯誤格式A，本題選擇的應該是C選項。
接著對于第二空，選擇的對象一定是表C或表EC，而此時EC是沒有商品名的，因此篩選對象一定是表C，并且投影需要保留商品號和商品名，因此投影的列號是1和2，本題選擇的應該是B選項。
接著對于第三空，選擇的對象一定是表C或表EC，而此時C是沒有銷售日期的，因此篩選對象一定是表EC，并且位于EC的第4列即列號為4，本題選擇的應該是C選項。
57、設有棧S和隊列Q初始狀態為空，數據元素序列a,b,c,d,e,f依次通過棧S，且多個元素從S出棧后立即進入隊列Q，若出隊的序列是b,d,f, e, c, a,則S中的元素最多時，棧底到棧頂的元素依次為（ ）。
A.a,b,c
B.a,c,d
C.a,c,e,f
D.a,d,f,e
參考答案：C
答案解析：
棧先進后出，隊列先進先出。
出隊序列與入隊序列是一致的，出隊的序列是b,d,f, e, c, a，即入隊序列也為b,d,f, e, c, a。
此時出棧后即入隊，即出棧順序也為b,d,f, e, c, a，元素出棧時，棧內情況依次如下：
棧S中元素最多時，從棧底到棧頂的元素依次為a、c、e、f。本題選擇C選項。
58、當二叉樹中的結點數目確定時，( )的高度一定是最小的。
A.二叉排序樹
B.完全二叉樹
C.線索二叉樹
D.最優二叉樹
參考答案：B
答案解析：
- 完全二叉樹是讓二叉樹的每一層的結點都盡可能全滿，除了最底層，此時樹的高度一定是最小的。
- 排序二叉樹可能會得到單枝樹，每一層只有1個結點，此時樹的高度可能最大。
- 線索二叉樹與二叉樹遍歷序列相關，高度并沒有確定性。
- 最優二叉樹與結點的權值相關，構成的樹的高度也是不確定的。
59、()是對稀疏矩陣進行壓縮存儲的方式。
A.二維數組和雙向鏈表
B.三元組順序表和十字鏈表
C.鄰接矩陣和十字鏈表
D.索引順序表和雙向鏈表
參考答案：B
答案解析：
- 在矩陣中，若數值為0的元素數目遠遠多于非0元素的數目，并且非0元素分布沒有規律時，則稱該矩陣為稀疏矩陣。
- 與之相反，若非0元素數目占大多數時，則稱該矩陣為稠密矩陣。
- 定義非零元素的總數比上矩陣所有元素的總數為矩陣的稠密度。
- 存儲矩陣的一般方法是采用二維數組，其優點是可以隨機地訪問每一個元素，因而能夠較容易地實現矩陣的各種運算。
- 但對于稀疏矩陣而言，若用二維數組來表示，會重復存儲了很多個0了，浪費空間，而且要花費時間來進行零元素的無效計算，所以必須考慮對稀疏矩陣進行壓縮存儲。
- 稀疏矩陣的三元組表的順序存儲結構稱為三元組順序表，常用的三元組表的鏈式存儲結構是十字鏈表。
- 最常用的稀疏矩陣存儲格式主要有：COO（Coordinate Format）和CSR（Compressed Sparse Row）。
- COO很簡單，就是使用3個數組，分別存儲全部非零元的行下標（row index）、列下標（column index）和值（value）。
- CSR稍復雜，對行下標進行了壓縮，假設矩陣行數是m，則壓縮后的數組長度為m+1，記作（row ptr），其中第i個元素（0-base）表示矩陣前i行的非零元個數。
60、設用線性探查法解決沖突構造哈希表，且哈希函數為H(key)=key%m，若在該哈希表中查找某關鍵字e是成功的且與多個關鍵字進行了比較，則（ ）。
A.這些關鍵字形成一個有序序列
B.這些關鍵字都不是e的同義詞
C.這些關鍵字都是e的同義詞
D.這些關鍵字的第一個可以不是e的同義詞
參考答案：D
答案解析：
本題是對哈希查找表的考查。
關鍵字e的同義詞，指的是其他關鍵字利用哈希函數進行求值時，得到的函數結果與e是一致的，此時這些關鍵字就是e的同義詞。
在哈希表查找關鍵字e時成功且經過多次比較，可以知道經過計算e的位置，此時該位置存放的并不是關鍵字e，并且這些關鍵字的順序與原序列順序相關，與大小無關，A選項有序序列說法不正確。
由于本題采用的線性探測法解決哈希沖突，此時該位置對同義詞開放，對非同義詞也是開放的，也就是說，其他非同義關鍵字在使用線性探測法解決沖突時，也有可能直接占據該位置。所以對該位置進行比較的關鍵字，可能是e的同義詞，也可能不是e的同義詞，B和C的說法太過絕對，相比而言D的說法更合適，本題選擇D選項。
61、對于一個初始無序的關鍵字序列，在下面的排序方法中，( )第一趟排序結束后，一定能將序列中的某個元素在最終有序序列中的位置確定下來。
①直接插入排序
②冒泡排序
③簡單選擇排序
④堆排序
⑤快速排序
⑥歸并排序
A.①②③⑥
B.①②③⑤⑥
C.②③④⑤
D.③④⑤⑥
參考答案：C
答案解析：
- 選擇類排序，每一輪會選擇最值（最大值或最小值）與第一個位置進行交換，此時確定第一個元素位置。③④都滿足要求。
- 冒泡排序，每一輪會讓最值相鄰交換直至放到最終的位置，②滿足要求。
- 快速排序，每一輪會根據基準元素劃分左右數組，此時基準元素的位置可以確定，因此⑤也滿足要求。
- 其他排序方式每一輪只能確定元素的當前位置，不能確定該元素的最終位置。
62、對數組A=(2,8,7,1,3,5,6,4)構建大頂堆為( )(用數組表示)。
A.(1,2,3,4,5,6,7,8)
B.(1,2,5,4,3,7,6,8)
C.(8,4,7,2,3,5,6,1)
D.(8,7,6,5,4,3,2,1)
參考答案：C
答案解析：
- 堆是一種非線性結構，可以把堆看作一棵二叉樹，也可以看作一個數組，即：堆就是利用完全二叉樹的結構來維護的一維數組。
- 堆可以分為大頂堆和小頂堆。
- 大頂堆：每個結點的值都大于或等于其左右孩子結點的值。
- 小頂堆：每個結點的值都小于或等于其左右孩子結點的值。
- 如果是排序，求升序用大頂堆，求降序用小頂堆。
- 大頂堆的構建過程就是從最后一個非葉子結點開始從下往上調整。
A數組初始構造如下：
從最底層依次調整不符位置：
此時滿足大頂堆，此時序列記為：8、4、7、2、3、5、6、1。
63、最大尺寸和問題描述為，在n個整數(包含負數)的數組A中，求之和最大的非空連續子數組,如數組A= (-2, 11, -4，13, -5，-2) ，其中子數組B= (11, -4, 13)具有最大子段和20 (11-4+13=20) 。求解該問題時,可以將數組分為兩個n/2個整數的子數組最大子段或或者在前半段,或者在后半段,或者跨越中間元素，通過該方法繼續劃分問題，直至最后求出最大子段和，該算法的時間復雜度為( )。
A.O(nlgn)
B.O(n2)
C.O(n2lgn)
D.O(n3)
參考答案：A
答案解析：
分治法的時間復雜度為 nlogn
最簡單的應用分治策略的算法是歸并排序
64、65、在求解某問題時，經過分析發現該問題具有最優子結構和重疊子問題性質。則適用(64) 算法設計策略得到最優解。若了解問題的解空間，并以廣度優先的方式搜索解空間，則采用的是(65)算法策略。
(1)
A.分治
B.貪心
C.動態規劃
D.回溯
(2)
A.動態規劃
B.貪心
C.回溯
D.分支限界
參考答案：CD
答案解析：
- 要想直接解決一個較大的問題，有時是相當困難的，分治法的設計思想是將一個難以解決的大問題分解成一些規模較小的相同問題，以便各個擊破，分而治之。
- 動態規劃法與分治法類似，其基本思想也是將帶求解問題分解為若干個子問題，先求解子問題再從這些子問題的解得到原問題的解。與分治法不同的是，適合用動態規劃法求解的問題，經分解得到的子問題往往不是獨立的。若用分治法來解這類問題，則相同的子問題會被求解多次，以至于最后解決原問題需要耗費指數級時間。此時用一個中間表記錄重復子問題的解，可以避免大量的重復計算。這就是動態規劃法的基本思路。
- 動態規劃法的應用場景一般會出現“最優子結構”的描述，并且針對重復子問題的計算通過記錄-查表，可以提高效率。
- 貪心法也經常用于解決最優化問題，與之不同的是，貪心法在解決問題的策略上是僅根據當前已有的信息做出選擇，而且一旦做出選擇，無論未來如何都不會改變。也就是只考慮當前最優，不考慮全局最優。一般不涉及劃分和求解重復子問題。
- 回溯法可以系統地搜索一個問題的所有解或任意解。它在包含問題的解空間樹中，按照深度優先的策略的策略，從根結點出發搜索解空間樹。
- 分支限界法類似于回溯法，也是一種在問題的解空間樹T上搜索問題解的算法，但在一般情況下，分支限界法與回溯法的求解目標不同。分支限界法的求解目標是找出滿足約束條件的一個解即可。由于求解目標不同，其探索方式與回溯法也不同，分支限界法以廣度優先或以最小耗費優先的方式搜索解空間樹。
66、IPv6 地址長度為( )bit。
A.16
B.32
C.64
D.128
參考答案：D
答案解析：
- IPv6地址長度為128位，由兩個邏輯部分組成：一個64位的網絡前綴和一個64位的主機地址。
- IPv6，互聯網協議第6版本，英文全稱Internet Protocol Version 6，用于替代IPV4的下一代IP協議。
- IPv6地址是獨立接口的標識符，所有的IPv6地址都被分配到接口，而非節點。
- IPv6類別上可分為單播地址、任播地址、組播地址等。
- IPv4的地址是32位，地址空間只有4,294,967,296（2的32次方）個地址，減去私有網段、網絡ID、廣播ID、保留網段、本地環回127.0.0.0網段、組播224.0.0.0網段，大概剩余25億左右。
- IPv6的地址是128位，是IPv4地址長度的4倍，采用十六進制表示。
67、在地址欄輸入www.abc.com，瀏覽器默認的應用層協議是( )。
A.HTTP
B.DNS
C.TCP
D.FTP
參考答案：A
答案解析：
- 在沒有錄入協議的情況下，URL默認是HTTP協議。
- HTTP：超文本傳輸協議（Hyper Text Transfer Protocol，HTTP）是一個簡單的請求-響應協議，它通常運行在TCP之上。它指定了客戶端可能發送給服務器什么樣的消息以及得到什么樣的響應。
- DNS：域名系統（英文：Domain Name System，縮寫：DNS）是互聯網的一項服務。它作為將域名和IP地址相互映射的一個分布式數據庫，能夠使人更方便地訪問互聯網。DNS使用UDP端口53。當前，對于每一級域名長度的限制是63個字符，域名總長度則不能超過253個字符。
- TCP：傳輸控制協議（TCP，Transmission Control Protocol）是一種面向連接的、可靠的、基于字節流的傳輸層通信協議，由IETF的RFC 793定義。
- FTP：文件傳輸協議（File Transfer Protocol，FTP）是用于在網絡上進行文件傳輸的一套標準協議，它工作在 OSI 模型的第七層， TCP 模型的第四層， 即應用層， 使用 TCP 傳輸而不是 UDP， 客戶在和服務器建立連接前要經過一個“三次握手”的過程， 保證客戶與服務器之間的連接是可靠的， 而且是面向連接， 為數據傳輸提供可靠保證。FTP允許用戶以文件操作的方式（如文件的增、刪、改、查、傳送等）與另一主機相互通信。
68、使用電子郵件客戶端向服務器發送郵件的協議是( )。
A.SMTP
B.POP3
C.IMAP4
D.MIME
參考答案：A
答案解析：
- SMTP：SMTP是一種提供可靠且有效的電子郵件傳輸的協議。SMTP是建立在FTP文件傳輸服務上的一種郵件服務，主要用于系統之間的郵件信息傳遞，并提供有關來信的通知。
- POP3：POP3，全名為"Post Office Protocol - Version 3"，即"郵局協議版本3"，是TCP/IP協議族中的一員，由RFC1939 定義。本協議主要用于支持使用客戶端遠程管理在服務器上的電子郵件，是一種郵件收取協議。提供了SSL加密的POP3協議被稱為POP3S。
- IMAP4：Internet Message Access Protocol 4，交互式數據消息訪問協議第四個版本，與POP3協議一樣也是規定個人計算機如何訪問網上的郵件的服務器進行收發郵件的協議，但是IMAP4協議同POP3協議相比更高級。
- MIME：Multipurpose Internet Mail Extensions多用途互聯網郵件擴展類型。是設定某種擴展名的文件用一種應用程序來打開的方式類型，當該擴展名文件被訪問的時候，瀏覽器會自動使用指定應用程序來打開。
69、以下 Windows 系統中用于清除本地 DNS 緩存的命令是( )。
A.ipconfig/ release
B.ipconfig/ flushdns
C.ipconfig/ displaydns
D.ipconfig/ registerdns
參考答案：B
答案解析：
- ipconfig/release ：釋放IP地址租約。
- pconfig/ flushdns：清楚本地DNS緩存。
- ipconfig/ displaydns：顯示本地DNS內容。
- ipconfig/ registerdns：DNS客戶端手工向服務器進行注冊。
- ipconfig /all：顯示本機TCP/IP配置的詳細信息。
- ipconfig /renew：DHCP客戶端手工向服務器刷新請求。
- ipconfig /showclassid：顯示網絡適配器的DHCP類別信息。
- ipconfig /setclassid：設置網絡適配器的DHCP類別。
70、在網絡系統設計時，不可能使所有設計目標都能達到最優，下列措施中最為合理的是( )。
A.盡量讓最低建設成本目標達到最優
B.盡量讓最短的故障時間達到最優
C.盡量讓最大的安全性目標達到最優
D.盡量讓優先級較高的目標達到最優
參考答案：D
答案解析：
網絡設計面臨的沖突：最低的安裝成本、最低的運行成本、最高的運行性能、最大的適應性、最短的故障時間、最大的可靠性、最大的安全性。不可能存在一個網絡設計方案，能夠使得所有的子目標都達到最優。可采用優先級和建立權重的方法權衡各目標的關心度。
71~75、Designing object -oriented software is hard,and designing (71)object -oriented software is even harder.You must find pertinent objects,factor them into class at the rightgranularity,define class interfaces and inheritances,and establish key relationships among them.You design should be specific to the problem at hand,but also(72)enough to address future problems and requirements.You also want to avoid redesign,or atleast minimize it.Experienced object -oriented designers will tell you that a reusable and flexible design is difficult if not impossible to get “right” the first time.Before a design is finished,they usually try to reuse it several times,madifring it each time.Yet experienced object-oriented designers do make good designs.Meanwhile new designers are (73)by the options available and tend to fall back on non-object-oriented techniques they’re used before.lt takes a long time for novices to learn that good obeject-oriented design is all about.Experienced designers evidently know something inexperiencedones.What is it?One thing expert desigeners know not to do is solve every problem from first principles.Rather, they reuse solutions that have worked for them in the past.When they find a good (74).They use it aqain and again.Such experience is part of what makes them experts.Consequently,you’ll find (75) patterns of classes and communicating objects in many object-oriented systems.
(1)
A.runnable
B.right
C.reusable
D.pertinent
(2)
A.clear
B.general
C.personalized
D.customized
(3)
A.excited
B.shocken
C.surprised
D.overwhelmed
(4)
A.tool
B.component
C.system
D.solution
(5)
A.recurring
B.right
C.experienced
D.past
參考答案：CBDDA
答案解析：
設計面向對象的軟件很難，而設計（可復用的）面向對象軟件就更難了。
你必須找到合適的相關的對象，以適當的粒度將它們劃分為類，定義類接口和繼承，并在它們之間建立關鍵關系。
你的設計應該針對眼前的問題，但（一般 ）足以解決未來的問題和要求。
你也要避免重新設計，或者至少最小化它。
有經驗的面向對象設計師會告訴你，一個可重用和靈活的設計是很難第一次就“正確”的。
在設計完成之前，他們通常會嘗試多次重復使用，每次都是這樣。
然而，有經驗的面向對象設計師確實能做出好的設計。
同時，新的設計師們對可用的選項感到（不安），他們傾向于使用以前使用的非面向對象技術。
新手要花很長時間才能了解好的面向對象的設計。
經驗豐富的設計師顯然知道一些缺乏經驗的東西。它是什么？有一件事專家設計師知道不能做的就是從一開始解決每一個問題。相反，他們選擇了過去對他們有效的解決方案。
當他們找到一個好的（解決方案）。他們一次又一次地使用它。這樣的經驗是他們成為專家的部分原因。
因此，您將在許多面向對象系統中找到類和通信對象的復用模式。
1）
A. runnable可運行的
B. right對的
C. reusable可復用的
D. pertinent中肯的，相關的
2）
A. clear清除
B. general總則
C. personalized個性化
D. customized定制
3）
A. excited興奮
B. shocken 震驚
C. surprised驚訝
D. overwhelmed不知所措
4）
A. tool工具
B. component組成部分
C. system系統
D. solution解決方案
5）
A. recurring循環
B. right對的
C. experienced經驗豐富
D. past過去
總結
以上是生活随笔為你收集整理的2021年上半年软件设计师上午真题及答案解析（六）的全部內容，希望文章能夠幫你解決所遇到的問題。
- 上一篇： Android Camera 开发你该知
- 下一篇： rng(‘default‘)