文档介绍：.
数据结构辅导试题一
一、简答问题：
1. 四类数据结构线性结构与非线性结构有何差别？
2. 简述算法的定义与特性。
3. 设有1000个无序元素，仅要求找出前10个最小元素，在下列排序方法中(归并排序、基数排序、快速排序一个元素，只需进行前10趟堆排序就可以了。其
它排序方法均需进行完全排序。
二、判断正误：(每小题1分，共5分)正确在()内打"，否则打。
1. ()2.(V)3.(V)4.()5.(")三、单项选择题：(每小题1分，共4分)
1. C))))四、填空题：(每小题2分,共20分)
1. +-
5. p->next、s8.(a,b)、(c,d)->next==
五、构造题：(每小题5分，共25分)
G
1.
2.
0
1
2
3
4
5
6
7
8
9
10
K
TA
BA
M
D
CI
X
TN
I
ASL=20/9
0
1
2
3
4
5
6
7
8
9
10
ASL=15/9
3.
{36,17,22,50,96,85,52,55}4.
WPL=11X2+6X2+9X2+5X3+2X4+3X4=87
［注］:哈夫曼树的左右子树可以互换。
5.
［注］:如果求中点时采用向上取整，则二叉树的形态为左子树偏长六、算法设计题：(每小题15分，共30分)
(仅要求给出子程序)［解答］:
intjudge(DLinkListL){p=L->next;q=L->prior;
while(p!=q)
{if(p->data!二q->data)return0;
if(p->next==q)return1;
p=p->next;
q=q->prior;
}return1;
}［注］:可以不用返回值，而用打印信息。
1. ［解答］:
(1)voidprint_1(BiTreeT){
if(T!二NULL)
{print_1(T->RChild);
printf(“%c->dTta);
print_1(T->LChild);
}}
(2)voidPrint_2(BiTreeT)
{InitStack(&S);p=T;
while(p!=NULL||!IsEmpty(S)){while(p!=NULL){Push(&S,p);p=p->RChild;
}if(!IsEmpty(S))
{Pop(&S,&p);
printf(“%pc”->,data);p=p->LChild;}
}
}
数据结构辅导试题二
一、简答题：(每小题3分，共15分)什么情况下二叉排序树的查找性能较好？什么情况下二叉排序树的查找性能最差？
1. 比较顺序表与单链表的优缺点。
2. 请写出栈的链式存储结构的类型定义。
3. 在起泡排序过程中，有的关键字在某趟排序中可能朝着与最终排序相反的方向移动，试举例说明之。
4. 简述参数传递的主要方式及其特点。
二、判断正误：(每小题1分，共5分)正确在()内打"，否则打。
()(1)在拓朴序列中，如果结点Vi排在结点Vj的前面，则一定存在从Vi到Vj的路径。
()(2)在采用线性探测法处理冲突的散列表中，所有同义词在表中一定相邻。
()(3)在一个小根堆中，具有最大值的元素一定是叶结点。
()(4)索引顺序表的特点是块间可无序，但块内一定要有序。
()(5)哈夫曼树中没有度为1的结点，所以必为满二叉树。
三、单项选择题：(每小题1分，共5分)•对于只在表的首、尾进行插入操作的线性表，宜采用的存储结构为：
A. 顺序表B)用头指针表示的单循环链表
C)用尾指针表示的单循环链表D)单链表•假设以第一个元素为分界元素，对字符序列(Q,H,C,Y,P,A,M,S,R,D,F,X)进行快
速排序，则第一次划分的结果是：
A)(A,C,D,F,H,M,P,Q,R,S,X,Y)B)(A,F,H,C,D,P,M,Q,R,S,Y,X)
C)(F,H,C,D,P,A,M,Q,R,S,Y,X)D)(P,A,M,F,H,C,D,Q,S,Y,R,X)下面是三个关于有向图运算的叙述：
(1) 求有向图结点的拓扑序列，其结果必定是唯一的
(2) 求两个指向结点间的最短路径，其结果必定是唯一的
(3) 求AOE网的关键路径，其结果必定是唯一的其中哪个(些)是正确的？
A)只有(1)B)(1)和(2)C)都正确D)都不正确若进栈序列为a,b,c,则通过入