自考数据结构试题和答案.docVIP

２0１０年1月高等教育考试

数据结构试题与答案

課程代码:02３３１

一、单项选择题（本大题共１5小题，每小题2分,共30分)

在每小题列出得四个备选项中只有一个就是符合题目规定得,请将其代码填写在题后得括号内。错选、多项选择或未选均无分。

1。若一个算法得时间复杂度用Ｔ(n)表达，其中ｎ得含义就是(A）

Ａ。问题规模 B。语句条数

Ｃ。循环层数?Ｄ。函数数量

２。具备线性结构得数据结构就是(C)

A．树?Ｂ．图

C.栈与队列?D．广义表

线性结构有：顺序表、栈与队列、串

3.将长度为n得单链表连接在长度为m得单链表之后,其算法得时间复杂度为（C)

A。O(1）?B。O（m)

C.O（n)?D.O（ｍ+n）

４。在带头结点得双向循环链表中插入一个新结点,需要修改得指针域数量就是（D)

A.2个?B。3个

C.4个?D．６个

Ｐ2８中

ｖｏidDＩnsertＢefore（DListＮode＊p,DａtaTypex）//在带头结点得双链表中，将值为x得新结点插入结点＊p之前，设p≠NULL

{

DLisｔＮｏde*s=mａlloc(ｓｉzeof(ＬｉｓtNｏｄｅ))；①

s-data＝x;②

s-＞prior=ｐ－〉prｉｏr;③

s-〉nｅｘt=ｐ;④

p-prioｒ—nｅxt＝ｓ;⑤

p-〉priｏr＝ｓ；⑥

｝

5。假设以数组Ａ[6０]存储循环队列得元素,其头指针就是front=４７,当前队列有50个元素,则队列得尾指针值为(D）

A。3?Ｂ.3７

C。50?Ｄ.97

辅导书Ｐ22中

对于循环向量中得循环队列，写出经过队头队尾指针表达得队列长度公式。(front指向实际队头,rｅａr指向实际队尾得下一元素位置。)

当reaｒ≥frｏnt时，队列长度L＝ｒeaｒ-fronｔ;当reａrfｒｏnt时,L=m+（reａr—fｒｏnt).这两种情况可统一为L＝（m+（rｅar—fｒont))％m,这里m为向量得大小。本题中ｍ＝60

6．若栈采取链式存储结构，则以下说法中对的得就是(B)

A.需要判断栈满且需要判断栈空

B。不需要判断栈满但需要判断栈空

C。需要判断栈满但不需要判断栈空

D。不需要判断栈满也不需要判断栈空

P3６中

因为链栈中得结点就是动态分派得,可以不考虑上溢,所以无需定义sｔacｋFｕｌl运算。

７．若串ｓtｒ=”Softwａrｅ”,其子串得数目就是(D)

A。8?B。9

C。36?D。37

P51中

任意个连续字符构成得子序列称为该串得子串.

8．设有一个１0阶得下三角矩阵Ａ,采取行优先压缩存储方式,alｌ为第一个元素，其存储地址为１00０，每个元素占一个地址单元,则a85得地址为(C)

A。１01２?Ｂ.1０１7

C.1０32?D.1039

P61中

在ｎ阶方阵A这个下三角矩阵中，第ｉ(i从０开始)行（0≤ｉｎ)有i+1个元素,元素总数为:n(ｎ＋１)/2,并将元素放在一个向量ｓａ[０、、n(n＋１)／２－１］中。

若i≥j,则aiｊ在左下三角矩阵中，sa[ｋ]与aij得相应关系就是k=i（i+1)/2+ｊ。

若iｊ,则ａiｊ在右上三角矩阵中,sａ［k］与ａiｊ得相应关系就是ｋ=ｊ(j+1）/2+i。

若alｌ为第一个元素，a８５与ａ00为第一个元素时得a（8５—（１1－00）)=a７４位置一样,k=7＊8/2+4=32，则a85得地址=10０0+3２=1032;

若a44为第一个元素，a８５与ａ０0为第一个元素时得a（85-（4４-00)）=a41位置一样，ｋ=4*5／2+1＝１1,则ａ８５得地址＝10０0+１１＝1０11；

９．允许结点共享得广义表称为（D）P６7

Ａ。纯表 B。线性表

Ｃ.递归表?D。再入表

１０.以下数据结构中,不属于二叉树得就是(Ｂ)B树就是一个平衡得多叉树

Ａ.Ｂ树?B。AVL树ＡＶL树就是自平衡二叉查找树

Ｃ。二叉排序树 Ｄ。哈夫曼树哈夫曼树就是最优二叉树

11。对下面有向图給出了四种可能得拓扑序列,其中错误得就是(Ｃ)辅导书中P97第1０题

A.1,5,2，６，3,4 B．１，５,6，2,3，４

C.5,１,6，３，4