一、选择,在A,B,C,D中选一个最确切的(1.5*16分)

1.若一直一个占的入栈序列是1,2,3,┉…,n,其输出序列为P1,P2,P3……PN,若PN是n,则P是_____.

A、i B、n-I C、n-I+1 D、不确定

2.表达式a*(b+c)-d的后缀表达式是_______

A、abcd*+- B、abc+*d- C、abc*+d- D、- +*abcd

3.下面说法不正确的是_____

A、广义表的表头总是一个广义表

B、广义表的表尾总是一个广义表

C、广义表难以用顺序存储结构

D、广义表可以是一个多层次的结构

4.疏矩阵一般的压缩存储结构有两种,他们是用____表示

A、二维数组和三维数组B、三元组和哈希表

C、三元组和十字链表D、哈希表和十字链表

5.循环队列A[0..m-1]存放其元素值,用front和rear分别表示队头和队尾,则当队列中的元素是_____

A、(rear-front+m)%m B、rear-front+1

C、rear-front-1 D、rear-front

6.下面说法正确的是____

(1)叉树按某种方式线索化后,任意结点均有指向前驱和后继的线索

(2)二叉数的前序遍历序列中,任意一个结点均处在子孙结点前

(3)二叉排序树中任一结点的值大于其左孩子的值,小于右孩子的值

A、(1)(2)(3) B、(1)(2) C、(1)(3) D、前面的可选答案都不对

7.下列排序算法中,_____排序在一趟结束后不一定能选出一个元素放在其最终位置上.

A、选择B、冒泡C、归并D、堆

8.在平衡二叉树中插入了一个结点后引起了不平衡,设最低(最接近于叶子)的平衡点是A,并已知A的左,右孩子的平衡因子分别是-1和0,则应进行的平衡旋转是.

A、LL B、RR C、RL D、RR

9.设图G用邻结表存储,则拓扑排序的时间复杂度为.

A、0(n) B、0(n+e) C、0(n2) D、0(n*e)

10.下面的说法正确的是_____.

1)一棵二叉树的叶子结点在三种遍历中的相对次序不变;

2)叉树定义,具有三个结点的二叉数共有6种:

A、(1)(2) B、(1) C、(2) D、(1) (2)都错

11.一棵二叉树高度为h,所有结点的度或为0,或为2,则这棵二叉树最少有____结点

A、2h B、2h-1 C、2h+1 D、h+1

12.下列排序算法中,在待排序数据已有序时,花费时间反而最多的是__排序.

A、冒泡B、希尔C、快速D、堆

13.数组A[0..5,0..6]的每个元素占五个字节,将其按列优先次序存储在起始地址为1000的内存单元中,则元素A[5,5]的地址是____

A、1175 B、1180 C、1205 D、1210

14.无向图G=(V,E),其中:V={a,b,c,d,e,f},E={(a,b),(a,e),(a,c),(b,e),(c,f),(f,d),(e,d)}对该图进行深度优先遍历,得到的顶点序列正确的是____

A、a,b,e,c,d,f B、a,c,f,e,b,D、C、a,e,b,c,f,D、D、a,e,d,f,c,b

15.设哈希表厂为14,哈希函数是H(key)=key%11,表中已有数据的关键字为15,38,61,84共四个,现要将关键字为49的结点加到表中,用二次探测再散列法解决冲突,则放入的位置是____

A、8 B、3 C、5 D、9

16.用数组r存储静态链表,结点的next域指向后继,工作指针j指向链中结点,使j沿链移动的操作是____

A、j=r[j].next B、j=j+1 C、j=j^.next D、r[j]^.next

二、填空

1.下面程序时间复杂度为( ).

三、根据条件补充完整程序.

线索二叉树有数据域data:在右孩子域lchild和rchild,左右标志ltag及rtag,

规定标志为1对应的孩子域是线索,0则为指向孩子的指针.规定在储存线索二叉树时,完成下面中序链表过程.(储存线索二叉树,不增加头结点,只在原有的由tree指向的二叉树中增加线索,此处也不考虑c语言的具体语法与约定,线索化前所有的标志tag都是0).

pre是同tree类型相同的指针,初值是null

thread-inorder (tree)

{

if(tree!=null){

thread-inorder( );

if(tree->lchild== ) {tree->ltag=1;tree->lchild=pre;}

if( ==null) { ; ;}

pre=p;

thread-inorder( );

}

}.

下面的排序思想是:第一趟比较将最小的元素放在r[1]中,最大的元素放在r[n]中,第二趟比较将次小的放在r[2]中,次大的放在r[n-1]中,….依次下去,直到待排序列为递增序.(注:)代表两个数据交换).

Void sort(sqlist&r,int n) {

i=1;

While( ) {

Min=max=1;

For (j=i+1; ;++j) {

If ( ) min=j;

Else if(r[j].key>r[max].key max=j; )

}

if( ) r[min] r[j];

if (max!=n-i+1)

if ( ) r[min] r[n-i+1];

else ( );

}

i++;

}

}//sort

下面的算法将一个带头结点的单链表la分解为两个链表la,lb,使得la表中含有原表中奇数项结点,而lb表内含偶数项结点,且保持结点间原有的相对顺序.

Void disb(listtedlist&la,luistedlist&lb) {

Lb=(linktype)malloc(sizeof(nodetype));

R=lb;p=la->next!=mull)

While ( ( ) && p->next!=null)

q=p->next;

( )

r->next=q;r=q;

( );

}

( );

}//disab

四、(0·×12)下表中M、N分别是一棵二叉树中的两个结点,表中行号i=1,2,3,分别表示四种M、N的相对关系,列号j=1,2,3分别表示中序后续遍历中要求在i,j所表示的关系能够发生的方格内例如:如果你认为n是m的祖先,并且在中续遍历中

先根遍历时先n被访问

中根遍历时先n被访问

后根遍历时先n被访问

五、(14分)对给定的7个顶点的临接矩阵如下:

1).(3分)画出该有向图;

2).(3分)画出邻接图;

3).(3分)从V1出发到其余各个定点得罪短路经常度(定点号从1计);

4).(5分)若将图看,列出其关键活动及相应的有向边,关键路径长度是多少

∞2 5 3∞∞∞

∞∞2∞∞7∞

∞∞∞1 3 5∞

∞∞∞∞5∞∞

∞∞∞∞∞3 7

∞∞∞∞∞∞5

∞∞∞∞∞∞∞