一 选择,在A,B,C,D中选一个最确切的(1.5*16分)
若一直一个占的入栈序列是1,2,3, ┉…,n,其输出序列为P1,P2,P3……PN,若
PN是n,则P是_____.
A i B n-I C n-I+1 D 不确定
表达式a*(b+c)-d的后缀表达式是_______
A abcd*+- B abc+*d- C abc*+d- D - +*abcd
3.下面说法不正确的是_____
A 广义表的表头总是一个广义表
B 广义表的表尾总是一个广义表
C 广义表难以用顺序存储结构
D 广义表可以是一个多层次的结构
疏矩阵一般的压缩存储结构有两种,他们是用____表示
A 二维数组和三维数组 B 三元组和哈希表
C 三元组和十字链表 D 哈希表和十字链表
循环队列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
∞ ∞ ∞ ∞ ∞ ∞ ∞