山东科技大学2012-2013学年数据结构试卷

发布于:2021-09-12 23:37:46

山东科技大学2012—2013学年第二学期 《数据结构》考试试卷

班级

姓名

学号

题号 一 二 三 四 总得 评卷 审核 分人 人
得分

1、 在顺序表中插入或删除一个元素,需要*均移动__________元

素,具体移动的元素个数与_______有关。

2、 表达式23+((12*3-2)/4+34*5/7)+108/9的后缀表达式是

_______。

3、 数据结构中评价算法的两个重要指标是



__________。

4、 下列程序判断字符串s 是否对称,对称则返回1,否则返回0;如

f("abba")返回1,f("abab")返回0;

int f((1)________){

int i=0,j=0;

while (s[j])(2)________;

for(j--; i<j && s[i]==s[j]; i++,j--);

return((3)_______) } .

5、 设广义表L=((),()), 则head(L)是___;tail(L)是____;L的长

度是___;深度是 __。

6、 已知一无向图G=(V,E),其中V={a,b,c,d,e } E={(a,b),

(a,d),(a,c),(d,c),(b,e)}现用某一种图遍历方法从顶点a开始

遍历图,得到的序列为abecd,则采用的是______遍历方法。

7、写出图2所示的AOV网的两个*诵蛄校





8、循环队列求队列中元素个数的公式是: ;顺序栈栈满的判定条件

是:

10、一棵完全二叉树有892个结点,则该树的高度为 ;其叶子结点

数为 。

1、 选择题 :18分(每个2分)

1、在双向链表指针p的结点前插入一个指针q的结点操作是( )。

A. p->Llink=q;q->Rlink=p;p->Llink->Rlink=q;q->Llink=q;

B. p->Llink=q;p->Llink->Rlink=q;q->Rlink=p;q->Llink=p-

>Llink;

C. q->Rlink=p;q->Llink=p->Llink;p->Llink->Rlink=q;p-

>Llink=q;

D. q->Llink=p->Llink;q->Rlink=q;p->Llink=q;p->Llink=q;

2、执行完下列语句段后,i值为:( )

int f(int x) { return ((x>0) ? x* f(x-

1):2);}

int i;

i =f(f(1));

A.2

B. 4

C. 8

D. 无限

递归

3、在带头结点的单链表中查找x应选择的程序体是( )。

(A)node *p=head->next; while (p && p->info!=x) p=p->next;

if (p->info==x) return p else return NULL;

(B)node *p=head; while (p&& p->info!=x) p=p->next;

return p;

(C)node *p=head->next; while (p&&p->info!=x) p=p->next;

return p;

(D)node *p=head; while (p->info!=x) p=p->next ;

return p;

4、若X是二叉中序线索树中一个有左孩子的结点,且X不为根,则x的

前驱为( )

A.X的双亲 B.X的右子树中最左的结点 C.X的左子树中最右

结点 D.X的左子树中最右叶结点

5、已知有向图G=(V,E),其中V={V1,V2,V3,V4,V5,V6,V7},E=

{<V1,V2>,<V1,V3>,<V1,V4>,<V2,V5>,<V3,V5>,<V3,V6>,<V4,V6>,

<V5,V7>,<V6,V7>},G的*诵蛄惺牵 )。

A.V1,V3,V4,V6,V2,V5,V7

B.

V1,V3,V2,V6,V4,V5,V7

C.V1,V3,V4,V5,V2,V6,V7

D.

V1,V2,V5,V3,V4,V6,V7

6、设栈S和队列Q的初始状态为空,元素e1、e2、e3、e4、e5和e6依

次通过栈S,一个元素出栈后即进入队列Q, 若6个元素出队的序列为

e2、e4、e3、e6、e5和e1, 则栈S的容量至少应该为( )。

(A)6

(B)4

(C)3

(D)2

7、任何一棵二叉树的叶结点在先序、中序和后序遍历序列中的相对次 序( )。 (A)不发生改变 (B) 发生改变 (C) 不能确定 (D)以上 都不对
2、 应用题:24分
1、一棵二叉树的中序遍历结果为:DBFEAGHCI,后序遍历结果为: DFEBHGICA。 (1)画出这棵二叉树,并写出它的前序遍历结果; (2)将这棵二叉树转换成等价的森林或树。
2、给出有向图G如图3所示,试求顶点V0到其他各顶点的最短距离和 路径,并写出源点V0到V5的最短路径。
3、设有正文AADBAACACCDACACAAD,字符集为A,B,C,D,设计一套二进制 编码,使编码最短。
3、 算法设计题:20分
①用自然语言说明算法思想;②给出所需的数据结构定义,做必要说 明;③用C语言写出算法程序,做必要注释。 1、设计算法求树的叶子数。10分 2、有一个带头结点的单链表,每个结点包括两个域,一个是整型域 data,另一个是指向下一个结点的指针域next。假设单链表已建立, 设计算法删除单链表中所有重复出现的结点,使得data域相等的结点 只保留一个。(10分) 将树看做一个森林,则森林的叶子数可如下递归求取: 若森林为空则叶 子数为0,否则,将森林分为两部分。第一部分是第一颗树,第二部分 是第二颗树及其后面的树组成的子森林。第二部分可以递归求叶子 数,至于第一部分,当树只有一个结点时叶子数为1,否则,为第一颗 树的子树森林的叶子数(可以递归求)。两部分加起来即可


相关推荐

最新更新

猜你喜欢