北外考研网

北外考研培训辅导班有哪些



南京理工大学2001年数据结构专业课考研真题试卷(回忆版)(南京理工大学2013年录取分数线)

一、选择,在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则为指向孩子的指针.规定在储存线索二叉树时,完成下面中序链表过程.(储存线索二叉树,不增加头结点,只在原有的由t
南京理工大学2001年数据结构专业课考研真题试卷(回忆版)(南京理工大学2013年录取分数线)插图
ree指向的二叉树中增加线索,此处也不考虑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
∞∞∞∞∞∞∞

LEAVE A RESPONSE

您的电子邮箱地址不会被公开。 必填项已用 * 标注

Related Posts

|京ICP备18012533号-326