![](http://oshiete.xgoo.jp/images/v2/pc/qa/question_title.png?5a7ff87)
アルゴリズム、C言語に関する過去問を解いたのですが、あまり自分の解答に自身がないです...
添付したPDFの問題3,4の解答を教えてくれる方がいたらお願いしたいです。
記述問題もあるので、それに関する説明もしていただけると嬉しいです。
<URL(PDF)>
https://www.dropbox.com/s/m39m6283nd8bsjg/H28%E9 …
以下、自分の解答を載せておきます。(合っているかは分かりません)
問題3
(1)
(a) end = middle - 1
(b) -1
(2)
時間計算量はO(logN)
(理由)二分探索による配列の探索では、プログラム中のwhileループが一回実行されるごとに探索対象の要素数が半分ずつに減っていくから。
(3)
(c) n -> next_char[numchar(key[i]) - 1]
(d) n -> value
(4)
時間計算量はO(k)
(理由)探索はkeyに含まれた文字を有向辺とするため、キーと値の組の数には影響を受けず、プログラム中のfor文のステップ数はkeyの長さ文だけ実行されるから。
(5)
文字種が多いと、キー同士が同じ文字種を含んでいる可能性が低くなり、rootノードからのポインタが極端に多く、それ以外のノードでは枝分かれがほぼないような木構造になってしまうから。
問題4
(1)
略
(2)
図1(a) : 3, 図1(b) : 1
(3)
O(mn^2)
二重forループの内側のfor文にある「rank++;」という処理の計算量はO(m)であり、それに二重forループの計算量であるO(n^2)をかければ良いから
お探しのQ&Aが見つからない時は、教えて!gooで質問しましょう!
似たような質問が見つかりました
- Java Java 南京錠 2 2023/02/04 11:46
- Visual Basic(VBA) vba 等間隔の列に対しての計算 6 2022/05/17 20:15
- 情報処理技術者・Microsoft認定資格 応用情報処理技術者試験のシステム利用率の計算について 2 2022/03/28 07:43
- C言語・C++・C# C言語 3 2022/10/04 15:07
- C言語・C++・C# C言語プログラム変更 2 2022/12/21 15:03
- 英語 以下の英文法の四択問題について質問です。 The Internet service provider 1 2023/02/01 19:50
- C言語・C++・C# numpyスライス機能を使った数値計算 2 2023/05/08 16:01
- Excel(エクセル) VBAで組み合わせ算出やCOUNTIFSの処理を高速化したいです。 4 2022/04/07 02:38
- 計算機科学 判定問題がPに属するなら探索問題はNPに属する。では判定問題がNPに属するとき探索問題は? 2 2023/05/20 19:10
- C言語・C++・C# C 言語の Gauss Jordan 法について 2 2022/12/28 11:16
デイリーランキングこのカテゴリの人気デイリーQ&Aランキング
-
y=1/3xとy=8/3x -14を連立す...
-
機械言語はどうやって決めてる...
-
数値計算の時間の刻み幅について
-
exp(13.4)を関数電卓で計算する...
-
logの計算がわかりません
-
270万円の6対4の計算式を教え...
-
計算ソフトでの計算精度について
-
グラフの問題で、よく「yをxの...
-
6ビット(符号含む)の二進数
-
QC検定3級の問題です。 どんな...
-
2.028×10の-26乗mをnmで表すと...
-
シリカゲルからコバルトの含有...
-
1キログラムって重さでいうとど...
-
NPU付きのPCを買ったのですが、...
-
4を4つ使って1〜100を作って欲...
-
有効数字の掛け算
-
蓮舫の「2位じゃダメなんです...
-
二次関数のグラフで、切片をど...
-
キログラムからトンの変換 1.15...
-
高校1年の数学です! ユークリ...
マンスリーランキングこのカテゴリの人気マンスリーQ&Aランキング
-
VB.NETで階乗を求めるプログラ...
-
VBとフィボナッチに明るい方、...
-
式?文?節?
-
COBOLのIFの入れ子について
-
OpenCV cvmatchtemplate
-
FORTRAN77の質問です。
-
GoTo文について
-
COBOL計算
-
アルゴリズム、C言語に関する...
-
アプレットで三次方程式1
-
プログラミングの問題です。
-
fortranのif文で・・・
-
二つの図形を画面上で同時に動...
-
反省文
-
苦しんで覚えるc言語について
-
Ruby / passenger のインストー...
-
システムエンジニアの適正について
-
小文字wと大文字Wの区別
-
初心者 パイソンプログラム
-
プログラミング講師はまだ需要...
おすすめ情報