本文提供2015年408計算機學科專業基礎考研真題答案及解析，以下為具體內容

1、已知表頭元素為c的單鏈表在內存中的存儲狀態如下表所示。現將f存放于1014H處并插入到單鏈表中，若f在邏輯上位于a和e之間，則a，e，f的“鏈接地址”依次是（  ）。

A、 1010H， 1014H， 1004H

B、 1010H， 1004H， 1014H

C、 1014H， 1010H， 1004H

D、 1014H， 1004H， 1010H

2、已知一個帶有表頭結點的雙向循環鏈表L，結點結構為：其中，prev和next分別是指向其直接前驅和直接后繼結點的指針。現要刪除指針p所指的結點，正確的語句序列是（  ）。

A、 p->next->prev = p->prev; p->prev- >next = p->prev; free(p);

B、 p->next->prev = p->next; p->prev->next = p->next; free(p);

C、 p->next->prev = p->next; p->prev->next = p->prev; free(p);

D、 p->next-> prev = p->prev; p->prev->next = p->next; free(p);

3、設有下圖所示的火車車軌，入口到出口之間有n條軌道，列車的行進方向均為從左至右，列車可駛入任意一條軌道。現有編號為1~9的9列列車，駛入的次序依次是8，4，2，5，3，9，1，6， 7。若期望駛出的次序依次為1~9，則n至少是：

A、 2

B、 3

C、 4

D、 5

4、有一個100階的三對角矩陣M，其元素mi,j（1<=i<=100， 1<=j<=100）按行優先次序壓縮存入下標從0開始的一維數組IV中。元素m30,30在N中的下標是（  ）。

A、 86

B、 87

C、 88

D、 89

5、若森林F有15條邊、25個結點，則F包含樹的個數是（  ）。

A、 8

B、 9

C、 10

D、 11

6、下列選項中，不是下圖深度優先搜索序列的是（  ）。

A、 V1，V5，V4，V3，V2

B、 V1，V3，V2，V5，V4

C、 V1，V2，V5，V4，V3

D、 V1，V2，V3，V4，V5

7、若將n個頂點e條弧的有向圖采用鄰接表存儲，則拓撲排序算法的時間復雜度是（  ）。

A、 O（n）

B、 O（n+e）

C、 O（n²）

D、 O（ne）

8、使用迪杰斯特拉（Dijktra） 算法求下圖中從頂點1到其他各頂點的最短路徑，依次得到的各最短路徑的目標頂點是（  ）。

A、 5，2，3，4，6

B、 5，2，3，6，4

C、 5，2，4，3，6

D、 5，2，6，3，4