发布时间 : 星期日 文章西南交大2001年数据结构研究生入学出试题更新完毕开始阅读
西南交通大学2001年硕士研究生招生入学考试
数据结构 试题 考生请注意：
1.本试题共五题，共4页，考生请认真检查；
2.答题时，直接将答题内容写在试题和由我校提供的答题纸上； 3.本试题不得拆开，拆开后遗失后果自负。 题号 一 二 三 四 五 得分 签字 六 七 八 九 总分
说明：考生可以选用类—PASCAL或类—C语言答题。判断题、选择题和填空题可以直接答在试题上，简答题和算法设计题答在答题纸上。
一、判断题，正确的打√，错误的打×（共10分，每题2分） 1.KMP算法的最大特点是指示主串的指针不需要回溯。（）
2.一颗有n个结点的穿舍二叉树，从上到下，从左到右用自然数依次给与编号，则编号为i的结点的左孩子的编号是2i（2i?n)，右孩子是2i+1(2i+1?n）（） 3.有e跳变的无向图，在邻接表中有e个结点。（） 4.任何有向网络（AOV-网）拓扑排序的结果是唯一的。（） 5.在栈空的情况下，不能做退栈运算，否则产生下溢。（）
二、选择题（共20分，每题2分，A,B,C,D中只有一个是正确或最确切的） 1.在一个以h为头的单循环链中，p指针指向链尾的条件是______。 A)p->next=h B)p->next=NIL C)p->next->next=h D)p->data=-1
2.设字符串S='ABCDEFG'，T='PQRST'则运算
CONCAT(SUB(S,2,LENGTH(T),SUB(S,LENGTH(T),2))后的结果为_______。 A)'BCQR' B)'BCDEF' C)'BCDEFG' D)'BCDEFEF' 3.下面的序列中，__________ 是堆。 A)1,5,10,6,7,8,9,2 B)1,2,8,4,3,9,10,5 C)9,8,7,6,4,8,2,1 D)9,8,7,6,5,4,3,7
4题被黑掉了
A)D-Lchild=Null B)D->Lchild=Null C)D->ltag=1 D)D->ltag=0
5.设有数组A [i,j] ，数组的每个元素长度为3字节，i的值为1到8，j的值为1到10，数从内存首地址BA开始顺序存放，当用以行为主存放时，元素A[5,8]的存储首地址为 ____________。 A)
BA?4 B)BA+180 C)BA+222 D)BA+225
6.设abcdef以所给的次序进栈，若在进栈操作时，允许退栈操作，则下面得不到的序列为
_____________.
A)febcba B)bcafed C)dcefba D)cabdef
7.若数组S[1..n]作为两个栈S1和S2的存储空间，对任何一个栈，只有[1...n]当全满时才不能进行进栈操作，为这两个栈分配空间的最佳方案是_______. A)S1的栈底位置为0，S2的栈底位置为n+1 B)S1的栈底位置为0，S2的栈底位置为n/2 C)S1的栈底位置为1，S2的栈底位置为n
D)S1的栈底位置为1，S2的栈底位置为1
8.若线性表最常用的操作是存取第i个元素及其前趋的值，则采用__________存储方式节省时间。
A)单链表 B)双链表 C)单循环链表 D)顺序表
9.在平衡二叉树中插入一个节点后造成了不平衡，设最低的不平衡结点为A，并已知A的左孩子的平衡因子-1，右孩子的平衡因子为0，则应作__________ 型调整以使其平衡。 A)LL B)LR C)RL D)RR
10.若给定的关键字的集合为{20,15,14,18,21,36，40,10}，一趟快速排序结束时，数据的排列为_________。
A)10,15,14,18,20,36,40,21 B)10,15,14,18,20,40,36,21 C)10,15,14,20,18,40,36,21 D)15,10,14,18,20,36,40,21
三、简答题（共20分，每题4分）
1.有向图G=
3.设有4000个无序的元素，希望用最快速度挑选出前10个最大的元素，在以下的排序方中，采用哪种方法最好？为什么？（快速排序、堆排序、基数排序）
4.假定有n个关键字，具有相同的散列函数值，如果用线性探测法把这n个关键字放到散列表中，要做多少次探测？
5.设循环列Q[0..N-1]的头尾指针F,R,当插入元时素时尾指针R加1，头指针F总是指在队列中第一个元素的前一个位置，试求该队列中元素的个数。
四、算法填空题（共22分，每空2分，下面算法分别用类—PASCAL或—C语言给出，考生可任选一个做，都不选不给分）
1.以下算法是完成将单向循环链表F就地改为双向循环链表的功能，请填空使之完善。
pre 说明：链表F的结点结构为
其中data为数据域，next和pre为指针域，且next域的值为后续结点的地址，pre为空。 [类—PASCAL ] {类—C}
PROC Double_List(F); Void Double_List(F)
data next {p,q均为移动指针} //p,q均为移动指针
IF F',next=F { if (F-> next==F)
THEN [F',pre:=_______ ; {F-> pre= ______ ; RETUREN]; return};
q:=F p:=F'. next; q=F; p=F-> next; REPEAT do{
p'.pre:=_______ q:= _______ ; p-> pre=_____ ;q=______ ; ___________ :=p'.next _______ =p-> next; UNTIL p= ; }while(p==________);
p' .pre:=q p->pre=q; ENDP:{Double_List} }//Double_Lisr
2.下面算法是完成在二叉排序树T中查找关键值为k的结点，请填空使之完善。 二叉排序树的结点类型如下：
[类—PASCAL] {类—C} TYPE bitreptr=^node; typedef struct Node{ node=RECORD char data;
data:char; struct Node *]child,*rchild;
lchild,rchild:bitreptr }Node,*Bitree;
FUNC Search(T,k):bitreptr;{成功时返回指 Bitree*Search(T,k)//成功时返回指向该// 向该结点的指针，否则返回空指针} 结点的指针，否则返回空指针
IF T=NIL THEN RETUN(NIL) {if(!T)return Null;
ELSE IF T^,data=k THEN RETURN(T) else if (T->data==k)return T; ELSE IF T^.data>k THEN________ else if (T->data 3.下面算法是以有向图的领接表为基础，查找顶点k的入度算法，请填空使之完善。 说明：adj为邻接表，n为表的顶点数，结点的两个域为顶点域vex,指针域nextarc.邻接表指针域为firstarc. 类—PASCAL 类—C FUNC find(k,adj):integer; Void find(k,and) Count:=0; {Count=0; FOR i:=1 TO n DO for(i=1;i<=n;++i) [p:=_______; {p=________; WHILE_______DO while_________ [IF________ {if_________ THEN Count;=Count+1; Count++ p:=_______] p:=_______} ] } RETURN(Count) return Count; ENDF:{find} }//find 五、算法设计题（共28分。要求：所有算法以过程或函数形式给出，并同时给出设计思想及必要的中文注释：考生请注明所有语言（类—PASCAL或类—C)) . 1.已知N元整型数组a存放N个学生成绩，已按由大到小排序，试设计一个算法，用折半查找方法统计成绩大于或等于x分的学生人数。（8分） 2.设一颗二叉树T以二叉链表作为存储结构，试编写将二叉树T中所有节点的左、右子树相互交换的算法。（10分） 3.已知一个线性表中元素均为正、负整数，且依次存储在数组A[0..n-1]中，试设计算法将表中所有正整数均排列在负整数之后。要求不另增加存储空间，且时间复杂度为0（n）。