数据结构试卷带答案.doc

数据结构试卷(一）
一、选择题(20分）
1．组成数据的基本单位是( 1。C）。
（A） 数据项 （B） 数据类型 (C） 数据元素 （D） 数据变量
2．设数据结构A=（D,R）,其中D=｛1,2，3，4｝，R={r｝，r={〈1，2〉，〈2，3〉,〈3，4〉，〈4，1〉｝，则数据结构A是（C）。
（A) 线性结构 （B） 树型结构 (C） 图型结构 （D) 集合
3．数组的逻辑结构不同于下列（D)的逻辑结构。
(A) 线性表 (B） 栈 (C） 队列 （D) 树
4．二叉树中第i（i≥1）层上的结点数最多有（C）个。
(A） 2i（B) 2i （C) 2i-1 (D） 2i—1
5．设指针变量p指向单链表结点A,则删除结点A的后继结点B需要的操作为（。A ）。
(A) p—>next=p->next—〉next (B) p=p—〉next
(C） p=p-〉next—>next (D) p—〉next=p
6．设栈S和队列Q的初始状态为空，元素E1、E2、E3、E4、E5和E6依次通过栈S，一个元素出栈后即进入队列Q，若6个元素出列的顺序为E2、E4、E3、E6、E5和E1，则栈S的容量至少应该是（。C ).
（A) 6 (B) 4 (C） 3 （D) 2
7．将10阶对称矩阵压缩存储到一维数组A中，则数组A的长度最少为(C ）。
(A） 100 (B) 40 (C） 55 （D) 80
8．设结点A有3个兄弟结点且结点B为结点A的双亲结点,则结点B的度数数为（8。B
（A) 3 （B） 4 （C） 5 （D） 1
9．根据二叉树的定义可知二叉树共有( B）种不同的形态。
(A） 4 （B） 5 （C） 6 （D） 7
10. 设有以下四种排序方法，则( B )的空间复杂度最大。
（A) 冒泡排序 (B） 快速排序 (C） 堆排序 （D） 希尔排序
二、填空题（30分)
1. 设顺序循环队列Q［0:m—1］的队头指针和队尾指针分别为F和R，其中队头指针F指向当前队头元素的前一个位置，队尾指针R指向当前队尾元素所在的位置,则出队列的语句为F =____________;.
2. 设线性表中有n个数据元素，则在顺序存储结构上实现顺序查找的平均时间复杂度为___________,在链式存储结构上实现顺序查找的平均时间复杂度为___________。
3. 设一棵二叉树中有n个结点,则当用二叉链表作为其存储结构时，该二叉链表中共有________个指针域,__________个空指针域。
4. 设指针变量p指向单链表中结点A，指针变量s指向被插入的结点B，则在结点A的后面插入结点B的操作序列为______________________________________。
5. 设无向图G中有n个顶点和e条边,则其对应的邻接表中有_________个表头结点和_________个表结点.
6. 设无向图G中有n个顶点e条边，所有顶点的度数之和为m,则e和m有______关系。
7. 设一棵二叉树的前序遍历序列和中序遍历序列均为ABC，则该二叉树的后序遍历序列为__________.
8. 设一棵完全二叉树中有21个结点，如果按照从上到下、从左到右的顺序从1开始顺序编号，则编号为8的双亲结点的编号是___________，编号为8的左孩子结点的编号是_____________。
9. 下列程序段的功能实现子串t在主串s中位置的算法,要求在下划线处填上正确语句.
int index（char s［ ］, char t［ ])
｛
i=j=0;
while(i<strlen（s) ＆&j〈strlen（t)） if（s[i］==t［j］)｛i=i+l; j=j+l；｝else｛i=_______； j=______；｝
if （j==strlen（t））return(i—strlen(t)）；elsereturn (—1）;
｝
10. 设一个连通图G中有n个顶点e条边，则其最小生成树上有________条边。
三、应用题(30分）
1．设完全二叉树的顺序存储结构中存储数据ABCDE,要求给出该二叉树的链式存储结构并给出该二叉树的前序、中序和后序遍历序列.
2．设给定一个权值集合W=（3，5，7,9,11），要求根据给定的权值集合构造一棵哈夫曼树并计算哈夫曼树的带权路径长度WPL。
3．设一组初始记录关键字序列为(19,21，16,5,18,23），要求给出以19为基准的一趟快速排序结果以及第2趟直接选择排序后的结果。
4．设一组初始记录关键字集合为(25，10，8，27,32，68),散列表的长度为8,散列函数H(k）=k mod 7,要求分别用线性探测和链地址法作为解决冲突的方法设计哈希表.
5．设无向图G（所右图所示），要求给出该图的深度优先和广度优先遍历的序列并给出该图的最小生成树.
四、算法设计题(20分)
1. 设计判断单链表中结点是否关于中心对称算法.
2. 设计在链式存储结构上建立一棵二叉树的算法。
3. 设计判断一棵二叉树是否是二叉排序树的算法。
数据结构试卷（一）参考答案
一、选择题
1。C 2。C 3。D 4。C 5。A6。C 7。C 8。B 9。B 10.B
二、填空题
1. (F+1) % m
2. O(n），O（n）
3. 2n，n+1
4. s—〉next=p-〉next； p—〉next=s
5. n， 2e
6. m=2e
7. CBA
8. 4，16
9. i—j+1，0
10. n-1
三、应用题
1. 链式存储结构略，前序ABDEC，中序DBEAC,后序DEBCA。
2. 哈夫曼树略，WPL=78
3. （18,5，16，19,21，23）,(5，16，21,19,18，23）
4. 线性探测： 链地址法:
5. 深度:125364,广度：123456,最小生成树T的边集为E={（1，4），（1，3），(3，5)，(5，6），(5,6)}
四、算法设计题
1. 设计判断单链表中结点是否关于中心对称算法.
typedef struct ｛int s[100］; int top；} sqstack；
int lklistsymmetry（lklist *head)
{
sqstack stack； stack。top= —1; lklist ＊p；
for（p=head；p!=0;p=p—>next) ｛stack.top++； stack.s［stack.top]=p—〉data；｝
for（p=head；p！=0；p=p—〉next） if (p-〉data==stack.s[stack。top］) stack。top=stack。top—1； else return（0)；
return（1)；
｝
2. 设计在链式存储结构上建立一棵二叉树的算法。
typedef char datatype；
typedef struct node ｛datatype data； struct node *lchild，＊rchild;｝ bitree；
void createbitree（bitree ＊＆bt)
｛
char ch; scanf（”％c”，&ch)；
if（ch==’＃’） ｛bt=0; return;}
bt=（bitree＊）malloc(sizeof（bitree））； bt-〉data=ch；
createbitree(bt—>lchild）； createbitree(bt->rchild)；
}
3. 设计判断一棵二叉树是否是二叉排序树的算法。
int minnum=—32768,flag=1；
typedef struct node｛int key； struct node ＊lchild，*rchild；｝bitree；
void inorder（bitree ＊bt）
｛
if （bt！=0）
{inorder（bt->lchild）； if（minnum〉bt-〉key)flag=0； minnum=bt—〉key； inorder（bt—>rchild)；｝
｝
数据结构试卷（二）
一、选择题(24分）
1．下面关于线性表的叙述错误的是（。D
（A） 线性表采用顺序存储必须占用一片连续的存储空间
（B) 线性表采用链式存储不必占用一片连续的存储空间
（C） 线性表采用链式存储便于插入和删除操作的实现
（D） 线性表采用顺序存储便于插入和删除操作的实现
2．设哈夫曼树中的叶子结点总数为m，若用二叉链表作为存储结构,则该哈夫曼树中总共有（ 2。B)个空指针域.
（A）2m—1 （B)2m (C）2m+1 (D)4m
3．设顺序循环队列Q［0：M—1］的头指针和尾指针分别为F和R，头指针F总是指向队头元素的前一位置，尾指针R总是指向队尾元素的当前位置，则该循环队列中的元素个数为（ 3.C ）.
（A） R-F (B） F—R （C） (R—F+M）％M (D） （F-R+M）%M
4．设某棵二叉树的中序遍历序列为ABCD，前序遍历序列为CABD,则后序遍历该二叉树得到序列为（ 4。A )。
（A） BADC（B）BCDA(C） CDAB (D） CBDA
5．设某完全无向图中有n个顶点，则该完全无向图中有（5。A ）条边。
（A） n（n-1)/2 (B) n（n—1) (C） n2 （D） n2—1
6．设某棵二叉树中有2000个结点,则该二叉树的最小高度为（C）。
（A) 9 （B） 10 （C) 11 (D) 12
7．设某有向图中有n个顶点，则该有向图对应的邻接表中有(B)个表头结点。
(A） n—1 （B) n （C） n+1 （D） 2n—1
8．设一组初始记录关键字序列(5,2，6，3，8),以第一个记录关键字5为基准进行一趟快速排序的结果为（ 8。C）.
(A） 2，3，5，8,6 （B） 3，2,5，8,6
（C） 3，2，5，6，8 （D) 2，3,6,5，8
二、填空题（24分）
1. 为了能有效地应用HASH查找技术，必须解决的两个问题是____构造一个好的HASH函数________________和_确定解决冲突的方法________________________。
2. 下面程序段的功能实现数据x进栈，要求在下划线处填上正确的语句。
typedef struct ｛int s［100]； int top；｝ sqstack；
void push(sqstack ＆stack，int x)
｛
if （stack。top==m—1） printf(“overflow"）;
else {____________________；_________________；}
}
3. 中序遍历二叉排序树所得到的序列是___________序列(填有序或无序)。
4. 快速排序的最坏时间复杂度为___________，平均时间复杂度为__________。
5. 设某棵二叉树中度数为0的结点数为N0，度数为1的结点数为N1,则该二叉树中度数为2的结点数为_________;若采用二叉链表作为该二叉树的存储结构，则该二叉树中共有_______个空指针域。
6. 设某无向图中顶点数和边数分别为n和e,所有顶点的度数之和为d，则e=_______。
7. 设一组初始记录关键字序列为（55，63，44，38,75，80,31,56),则利用筛选法建立的初始堆为___________________________。
8. 设某无向图G的邻接表为，则从顶点V1开始的深度优先遍历序列为___________;广度优先遍历序列为____________。
三、应用题（36分)
1． 设一组初始记录关键字序列为（45，80，48，40,22，78），则分别给出第4趟简单选择排序和第4趟直接插入排序后的结果。
2． 设指针变量p指向双向链表中结点A,指针变量q指向被插入结点B,要求给出在结点A的后面插入结点B的操作序列（设双向链表中结点的两个指针域分别为llink和rlink）。
3． 设一组有序的记录关键字序列为(13,18，24，35,47，50，62，83，90），查找方法用二分查找，要求计算出查找关键字62时的比较次数并计算出查找成功时的平均查找长度.
4． 设一棵树T中边的集合为{（A，B)，（A，C)，（A，D），（B，E)，(C，F),（C,G）}，要求用孩子兄弟表示法（二叉链表）表示出该树的存储结构并将该树转化成对应的二叉树.
5． 设有无向图G（如右图所示),要求给出用普里姆算法构造最小生成树所走过的边的集合。
6． 设有一组初始记录关键字为(45，80，48,40，22，78),要求构造一棵二叉排序树并给出构造过程.
四、算法设计题(16分）
1． 设有一组初始记录关键字序列(K1，K2，…，Kn），要求设计一个算法能够在O（n）的时间复杂度内将线性表划分成两部分,其中左半部分的每个关键字均小于Ki，右半部分的每个关键字均大于等于Ki。
2． 设有两个集合A和集合B，要求设计生成集合C=A∩B的算法,其中集合A、B和C用链式存储结构表示.
数据结构试卷（二)参考答案
一、选择题
1.D 2。B 3.C 4.A 5.A 6.C 7.B 8。C
二、填空题
1. 构造一个好的HASH函数，确定解决冲突的方法
2. stack.top++,stack.s［stack。top］=x
3. 有序
4. O（n2），O(nlog2n)
5. N0—1，2N0+N1
6. d/2
7. (31，38，54,56,75，80，55，63）
8. (1,3，4,2)，(1，3，2，4)
三、应用题
1. (22，40，45，48，80,78)，(40，45，48,80，22，78）
2. q—〉llink=p; q—〉rlink=p—〉rlink; p—〉rlink-〉llink=q; p—〉rlink=q;
3. 2，ASL=91＊1+2＊2+3*4+4＊2）=25/9
4. 树的链式存储结构略,二叉树略
5. E=｛(1，3)，（1，2),(3,5），(5，6）,(6，4)｝
6. 略
四、算法设计题
1. 设有一组初始记录关键字序列（K1，K2，…，Kn），要求设计一个算法能够在O（n)的时间复杂度内将线性表划分成两部分，其中左半部分的每个关键字均小于Ki，右半部分的每个关键字均大于等于Ki.
void quickpass（int r［］， int s, int t）
｛
int i=s， j=t, x=r［s］；
while(i<j）{
while (i〈j && r［j］〉x) j=j-1； if （i<j） {r［i]=r[j］；i=i+1；｝
while （i<j && r［i］〈x） i=i+1； if （i〈j） ｛r[j]=r[i］;j=j—1；}
}
r[i］=x；
}
2. 设有两个集合A和集合B，要求设计生成集合C=A∩B的算法，其中集合A、B和C用链式存储结构表示。
typedef struct node ｛int data; struct node *next;｝lklist；
void intersection(lklist ＊ha,lklist *hb，lklist *＆hc)
｛
lklist *p,*q，＊t;
for（p=ha,hc=0；p！=0；p=p—>next）
{ for（q=hb；q！=0；q=q-〉next) if （q—〉data==p—>data） break;
if(q！=0）｛ t=（lklist *)malloc（sizeof(lklist）); t-〉data=p—>data；t—〉next=hc; hc=t;｝
｝
}
数据结构试卷（三）
一、选择题(30分）
1．设某数据结构的二元组形式表示为A=(D，R),D=｛01，02，03，04,05,06,07，08，09｝，R=｛r}，r=｛<01，02〉，<01，03〉,〈01,04〉，〈02，05〉，<02，06〉,<03，07〉，〈03,08>，<03,09〉}，则数据结构A是（ B ）.
(A） 线性结构 （B） 树型结构 (C） 物理结构 （D) 图型结构
2．下面程序的时间复杂为（B ）
for(i=1,s=0; i<=n; i++) {t=1;for（j=1；j〈=i;j++） t=t*j;s=s+t;｝
(A） O（n) （B） O（n2）（C） O(n3）（D） O（n4)
3．设指针变量p指向单链表中结点A,若删除单链表中结点A，则需要修改指针的操作序列为（ A ）。
（A） q=p—〉next；p-〉data=q—〉data；p—〉next=q—〉next；free(q)；
（B） q=p-〉next;q—〉data=p->data；p—>next=q—>next；free（q）；
（C） q=p->next；p-〉next=q—〉next；free（q)；
（D) q=p->next；p->data=q-〉data；free(q）；
4．设有n个待排序的记录关键字，则在堆排序中需要( A ）个辅助记录单元。
（A） 1 (B) n (C） nlog2n （D） n2
5．设一组初始关键字记录关键字为(20，15，14，18,21，36，40，10），则以20为基准记录的一趟快速排序结束后的结果为( A ）。
(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，2l
（D） 15,10，14,18，20，36，40，21
6．设二叉排序树中有n个结点，则在二叉排序树的平均平均查找长度为（ B ).
（A) O（1） （B） O（log2n） (C）O(n） (D） O（n2）
7．设无向图G中有n个顶点e条边，则其对应的邻接表中的表头结点和表结点的个数分别为( D ）。
（A） n，e （B） e,n （C） 2n,e (D） n,2e
8。 设某强连通图中有n个顶点，则该强连通图中至少有（ C )条边。
（A) n（n—1）（B） n+1(C） n（D） n(n+1）
9．设有5000个待排序的记录关键字,如果需要用最快的方法选出其中最小的10个记录关键字,则用下列( B )方法可以达到此目的。
(A）快速排序 （B）堆排序 （C）归并排序 (D）插入排序
10.下列四种排序中（ D ）的空间复杂度最大。
(A）插入排序 （B）冒泡排序 （C)堆排序 （D)归并排序
二、填空殖（48分，其中最后两小题各6分)
1. 数据的物理结构主要包括_____________和______________两种情况.
2. 设一棵完全二叉树中有500个结点，则该二叉树的深度为____9______;若用二叉链表作为该完全二叉树的存储结构，则共有___501________个空指针域.
3. 设输入序列为1、2、3，则经过栈的作用后可以得到_____5______种不同的输出序列。
4. 设有向图G用邻接矩阵A[n]［n］作为存储结构，则该邻接矩阵中第i行上所有元素之和等于顶点i的__出度______，第i列上所有元素之和等于顶点i的____入度____。
5. 设哈夫曼树中共有n个结点，则该哈夫曼树中有____0____个度数为1的结点。
6. 设有向图G中有n个顶点e条有向边，所有的顶点入度数之和为d，则e和d的关系为__e=d_______.
7. ___中序_______遍历二叉排序树中的结点可以得到一个递增的关键字序列（填先序、中序或后序）。
8. 设查找表中有100个元素，如果用二分法查找方法查找数据元素X，则最多需要比较____7____次就可以断定数据元素X是否在查找表中。
9. 不论是顺序存储结构的栈还是链式存储结构的栈，其入栈和出栈操作的时间复杂度均为__O（n）_________.
10. 设有n个结点的完全二叉树,如果按照从自上到下、从左到右从1开始顺序编号，则第i个结点的双亲结点编号为_[i/2］___________，右孩子结点的编号为___2i+1________.
11. 设一组初始记录关键字为(72，73，71，23，94,16，5），则以记录关键字72为基准的一趟快速排序结果为__(5,16,23,71,72，73,94）_________________________.
12. 设有向图G中有向边的集合E={〈1，2〉，<2，3>，〈1，4〉，<4,2>，〈4，3〉｝，则该图的一种拓扑序列为__1，4,2，3__________________.
13. 下列算法实现在顺序散列表中查找值为x的关键字，请在下划线处填上正确的语句.
struct record{int key; int others;｝;
int hashsqsearch(struct record hashtable［ ］，int k)
｛
int i，j; j=i=k ％ p；
while (hashtable［j].key！=k＆&hashtable[j]。flag！=0)｛j=(_j+1___） ％m； if (i==j) return（—1）;｝
if （_______________________ ) return（j)； else return（—1）；
｝
14. 下列算法实现在二叉排序树上查找关键值k，请在下划线处填上正确的语句.
typedef struct node｛int key； struct node *lchild; struct node ＊rchild；｝bitree；
bitree *bstsearch（bitree ＊t， int k）
｛
if （t==0 ） return(0）；else while (t!=0)
if （t-〉key==k）_____________;else if （t—〉key>k） t=t-〉lchild； else_____________;
｝
三、算法设计题（22分）
1． 设计在单链表中删除值相同的多余结点的算法。
2． 设计一个求结点x在二叉树中的双亲结点算法.
数据结构试卷(三）参考答案
一、选择题
1.B 2。B 3。A 4。A 5.A
6.B 7.D 8。C 9.B 10。D
第3小题分析：首先用指针变量q指向结点A的后继结点B，然后将结点B的值复制到结点A中，最后删除结点B.
第9小题分析:9快速排序、归并排序和插入排序必须等到整个排序结束后才能够求出最小的10个数，而堆排序只需要在初始堆的基础上再进行10次筛选即可,每次筛选的时间复杂度为O（log2n）。
二、填空题
1. 顺序存储结构、链式存储结构
2. 9，501
3. 5
4. 出度,入度
5. 0
6. e=d
7. 中序
8. 7
9. O(1)
10. i/2，2i+1
11. （5,16，71，23，72,94，73）
12. （1，4,3，2)
13. j+1，hashtable[j］。key==k
14. return（t)，t=t->rchild
第8小题分析:二分查找的过程可以用一棵二叉树来描述，该二叉树称为二叉判定树。在有序表上进行二分查找时的查找长度不超过二叉判定树的高度1+log2n。
三、算法设计题
1. 设计在单链表中删除值相同的多余结点的算法。
typedef int datatype；
typedef struct node ｛datatype data; struct node ＊next；｝lklist；
void delredundant(lklist *＆head)
{
lklist ＊p，＊q，*s；
for（p=head；p！=0；p=p-〉next）
{
for（q=p-〉next,s=q；q！=0; ）
if （q—〉data==p-〉data) {s-〉next=q->next； free(q);q=s—〉next;｝
else {s=q，q=q—〉next；｝
}
｝
2. 设计一个求结点x在二叉树中的双亲结点算法。
typedef struct node ｛datatype data； struct node ＊lchild，*rchild；｝ bitree；
bitree *q[20］； int r=0,f=0,flag=0；
void preorder（bitree *bt, char x)
｛
if （bt！=0 &＆ flag==0）
if （bt-〉data==x） ｛ flag=1； return;｝
else {r=（r+1)% 20； q［r]=bt; preorder（bt—〉lchild,x）； preorder（bt—>rchild，x）； ｝
｝
void parent（bitree *bt，char x）
｛
int i；
preorder(bt，x)；
for(i=f+1； i〈=r； i++)if （q[i］—〉lchild—〉data==x ｜｜ q[i]->rchild-〉data） break；
if （flag==0） printf（”not found x\n”）;
else if （i<=r） printf（”％c",bt->data）; else printf（”not parent"）；
｝
数据结构试卷（四）
一、选择题（30分）
1．设一维数组中有n个数组元素,则读取第i个数组元素的平均时间复杂度为（ ）。
(A) O(n) （B） O（nlog2n） （C） O(1） （D） O（n2)
2．设一棵二叉树的深度为k，则该二叉树中最多有（ ）个结点。
（A) 2k-1 (B） 2k (C) 2k—1 （D) 2k—1
3．设某无向图中有n个顶点e条边,则该无向图中所有顶点的入度之和为( ）。
(A) n (B） e （C) 2n (D） 2e
4．在二叉排序树中插入一个结点的时间复杂度为( ）。
（A） O(1) （B） O(n) (C） O（log2n） （D） O（n2)
5．设某有向图的邻接表中有n个表头结点和m个表结点,则该图中有（ ）条有向边。
（A) n （B) n—1 （C） m （D) m—1
6．设一组初始记录关键字序列为（345，253，674,924，627)，则用基数排序需要进行（ )趟的分配和回收才能使得初始关键字序列变成有序序列.
(A) 3 （B） 4（C) 5(D） 8
7．设用链表作为栈的存储结构则退栈操作（ )。
(A） 必须判别栈是否为满 （B) 必须判别栈是否为空
(C） 判别栈元素的类型 （D) 对栈不作任何判别
8．下列四种排序中( ）的空间复杂度最大。
(A) 快速排序 （B) 冒泡排序 （C） 希尔排序 (D) 堆
9．设某二叉树中度数为0的结点数为N0，度数为1的结点数为Nl，度数为2的结点数为N2,则下列等式成立的是（ ）。
（A） N0=N1+1(B） N0=Nl+N2(C） N0=N2+1（D） N0=2N1+l
10。设有序顺序表中有n个数据元素，则利用二分查找法查找数据元素X的最多比较次数不超过（ ）.
（A) log2n+1（B) log2n—1(C) log2n (D) log2（n+1）
二、填空题(42分）
1． 设有n个无序的记录关键字，则直接插入排序的时间复杂度为________，快速排序的平均时间复杂度为_________。
2． 设指针变量p指向双向循环链表中的结点X，则删除结点X需要执行的语句序列为_________________________________________________________（设结点中的两个指针域分别为llink和rlink）。
3． 根据初始关键字序列(19,22，01，38，10)建立的二叉排序树的高度为____________。
4． 深度为k的完全二叉树中最少有____________个结点.
5． 设初始记录关键字序列为(K1,K2，…，Kn)，则用筛选法思想建堆必须从第______个元素开始进行筛选。
6． 设哈夫曼树中共有99个结点,则该树中有_________个叶子结点;若采用二叉链表作为存储结构,则该树中有_____个空指针域.
7． 设有一个顺序循环队列中有M个存储单元,则该循环队列中最多能够存储________个队列元素;当前实际存储________________个队列元素（设头指针F指向当前队头元素的前一个位置,尾指针指向当前队尾元素的位置)。
8． 设顺序线性表中有n个数据元素,则第i个位置上插入一个数据元素需要移动表中_______个数据元素;删除第i个位置上的数据元素需要移动表中_______个元素.
9． 设一组初始记录关键字序列为（20，18，22，16，30，19),则以20为中轴的一趟快速排序结果为______________________________。
10． 设一组初始记录关键字序列为(20，18,22，16，30,19)，则根据这些初始关键字序列建成的初始堆为________________________。
11． 设某无向图G中有n个顶点，用邻接矩阵A作为该图的存储结构，则顶点i和顶点j互为邻接点的条件是______________________。
12． 设无向图对应的邻接矩阵为A，则A中第i上非0元素的个数_________第i列上非0元素的个数（填等于,大于或小于)。
13． 设前序遍历某二叉树的序列为ABCD，中序遍历该二叉树的序列为BADC，则后序遍历该二叉树的序列为_____________。
14． 设散列函数H（k）=k mod p,解决冲突的方法为链地址法。要求在下列算法划线处填上正确的语句完成在散列表hashtalbe中查找关键字值等于k的结点，成功时返回指向关键字的指针,不成功时返回标志0。
typedef struct node {int key； struct node *next；｝ lklist；
void createlkhash（lklist ＊hashtable［ ])
{
int i，k; lklist ＊s；
for（i=0；i〈m;i++）_____________________;
for(i=0；i〈n;i++)
{
s=(lklist ＊）malloc（sizeof(lklist））； s-〉key=a［i]；
k=a[i] ％ p； s—>next=hashtable[k]；_______________________；
}
}
三、算法设计题（28分）
1． 设单链表中有仅三类字符的数据元素(大写字母、数字和其它字符），要求利用原单链表中结点空间设计出三个单链表的算法，使每个单链表只包含同类字符。
2. 设计在链式存储结构上交换二叉树中所有结点左右子树的算法。
3. 在链式存储结构上建立一棵二叉排序树。
数据结构试卷（四)参考答案
一、选择题
1．C 2．D 3．D 4．B 5．C6．A 7．B 8。A 9．C 10．A
二、填空题
1. O（n2），O(nlog2n）
2. p>llink->rlink=p—〉rlink； p->rlink->llink=p—〉rlink
3. 3
4. 2k—1
5. n/2
6. 50，51
7. m-1，(R—F+M）%M
8. n+1-i，n—i
9. (19，18，16，20，30，22）
10. （16,18,19，20，32,22)
11. A[i］［j］=1
12. 等于
13. BDCA
14. hashtable[i］=0,hashtable［k］=s
三、算法设计题
1. 设单链表中有仅三类字符的数据元素（大写字母、数字和其它字符）,要求利用原单链表中结点空间设计出三个单链表的算法，使每个单链表只包含同类字符.
typedef char datatype;
typedef struct node {datatype data； struct node ＊next;｝lklist；
void split（lklist *head，lklist ＊＆ha,lklist *&hb，lklist *＆hc)
｛
lklist ＊p；ha=0，hb=0，hc=0；
for（p=head；p！=0；p=head)
｛
head=p—>next； p—〉next=0；
if (p—>data>='A' ＆＆ p—〉data〈=’Z’) {p—>next=ha; ha=p;｝
else if （p—〉data〉=’0’ &＆ p-〉data<=’9’） ｛p—>next=hb； hb=p；｝ else {p—>next=hc; hc=p；}
}
｝
2. 设计在链式存储结构上交换二叉树中所有结点左右子树的算法。
typedef struct node ｛int data； struct node ＊lchild，＊rchild；} bitree；
void swapbitree(bitree *bt）
｛
bitree ＊p；
if(bt==0) return；
swapbitree（bt—〉lchild）； swapbitree（bt->rchild）；
p=bt—>lchild； bt—〉lchild=bt—>rchild； bt—〉rchild=p；
｝
3. 在链式存储结构上建立一棵二叉排序树。
＃define n 10
typedef struct node｛int key； struct node ＊lchild,*rchild;｝bitree；
void bstinsert（bitree *&bt，int key）
{
if (bt==0)｛bt=(bitree *）malloc（sizeof(bitree）)； bt—〉key=key;bt—>lchild=bt—〉rchild=0;｝
else if （bt->key>key) bstinsert（bt-〉lchild,key）; else bstinsert（bt—〉rchild，key）；
}
void createbsttree（bitree ＊&bt）
{
int i；
for（i=1；i〈=n;i++） bstinsert（bt，random（100））;
}
数据结构试卷（五)
一、选择题(30分）
1．数据的最小单位是（ A ）.
（A） 数据项 (B） 数据类型 （C) 数据元素 （D) 数据变量
2．设一组初始记录关键字序列为(50，40，95