当前位置：问答库＞考研信息

安徽工业大学2008年招收攻读硕士学位研究生专业试卷(A) (A)

科目名称：数据结构 代码：861

（注：总分：150 考试时间：180分钟）

一、单项选择题（单项选择题（30×30×1.5=45分）

1.程序段 FOR(i=n-1;i>=0;i--)

FOR(j=1;j<=n;j++)

IF A[j]>A[j+1]

A[j]与A[j+1]对换；

其中 n为正整数，则最后一行的语句频度在最坏情况下是______。

A. O（n） B. O(nlogn) C. O(n) D. O(n)

2.用链表表示线性表的优点是 ______。

A.便于随机存取 B.花费的存储空间较顺序存储少 C.便于插入和删除

D.数据元素的物理顺序与逻辑顺序相同

3.带头结点的单链表head 为空的判定条件是_______。

A. head==NULL B.head->next==NULL C.head->next==head

D.head!=NULL

4.在循环双链表的p 所指结点之后插入s 所指结点的操作是____。

A. p->next=s; s->prior=p; p->next->prior=s; s->next=p->next;

B. p->next=s; p->next->prior=s; s->prior=p; s->next=p->next;

C. s->prior=p; s->next=p->next; p->next=s; p->next->prior=s;

D. s->prior=p; s->next=p->next; p->next->prior=s; p->next =s;

5. 栈应用在______。

A. 递归调用 B. 子程序调用 C. 表达式求值 D. A，Ｂ，Ｃ都对

6. 设abcdef (a先进栈)顺序进栈，若在进栈操作时，允许出栈操作,则下面得不到的序列为______。

A．fedcba B. bcafed C. dcefba D. cabdef 注：序列xyz 表示 x先出栈；z最后出栈。

7. 若一个栈的输入序列为1,2,3,4,5则输出序列有______种可能。

A.14 B.120 C. 60 D. 42

8.循环队列存储在数组A[0..m]中，则入队时队尾的操作为______。

A. rear=rear+1 B. rear=(rear+1)%(m-1)

C. rear=(rear+1) % m D. rear=(rear+1)%(m+1)

9.在简单模式匹配中，当模式串位j 与主串位i 的比较时，新一趟匹配开始，主串的位移公式是 _________。

A．i=i+1 B．i=j+1 C．i=i-j+1 D．i=i-j+2

10. 稀疏矩阵一般的压缩方法是_________。

A.二维数组和三维数组 B.三元组和散列表 C.三元组和十字链表 D.