数据结构辅导试题一一、简答问题：1．四类数据结构2．线性结构与非线性结构有何差别？3．简述算法的定义与特性。
4．设有1000个无序元素，仅要求找出前10个最小元素，在下列排序方法中（归并排序、基数排序、快速排序、堆排序、插入排序）哪一种方法最好，为什么？二、判断正误：（每小题1分，共5分）正确在（）内打√，否则打 。
1．（）二叉排序树或是一棵空树，或是具有下列性质的二叉树：若它的左子树非空，则根结点的值大于其左孩子的值，若它的右子树非空，则根结点的值大于其右孩子的值。
2．（）索引顺序表的特点是块内可无序，块间要有序。
3．（）子串是主串中任意个连续字符组成的序列。
4．（）线性结构只能用顺序结构存放，非线性结构只能用链表存放。
5．（）快速排序的枢轴元素可以任意选定。
三、单项选择题：(每小题1分，共4分)1．栈S最多能容纳4个元素。
现有6个元素按A、B、C、D、E、F的顺序进栈, 问下列哪一个序列是可能的出栈序列?A)E、D、C、B、A、F B)B、C、E、F、A、DC)C、B、E、D、A、F D)A、D、F、E、B、C2．将一棵有100个结点的完全二叉树从根这一层开始，每一层从左到右依次对结点进行编号，根结点编号为1，则编号为49的结点的左孩子的编号为：A、98B、99C、50D、483. 对下列关键字序列用快速排序法进行排序时，速度最快的情形是：A）{21、25、5、17、9、23、30} B）{25、23、30、17、21、5、9}B）{21、9、17、30、25、23、5} D）{5、9、17、21、23、25、30}4. 设森林F中有三棵树，第一、第二和第三棵树的结点个数分别为M1、M2和M3。
与森林F对应的二叉树根结点的右子树上的结点个数是：A）M1 B）M1+M2 C）M3 D）M2+M3四、填空题：(每小题2分,共 20分)1．设一哈希表表长M为100 ，用除留余数法构造哈希函数，即H（K）=K MOD P（P<=M）, 为使函数具有较好性能，P应选2．N个结点的二叉树采用二叉链表存放，共有空链域个数为3．单链表与多重链表的区别是4．在各种查找方法中，平均查找长度与结点个数无关的是5．深度为6（根层次为1）的二叉树至多有个结点。
6．已知二维数组A[20][10]采用行序为主方式存储,每个元素占2个存储单元,并且A[10][5]的存储地址是1000,则A[18][9]的存储地址是7．在一个单链表中p所指结点之后插入s所指结点时,应执行s->next= 和p->next= 的操作.8．广义表((a,b),c,d)的表头是,表尾是9．循环单链表LA中，指针P所指结点为表尾结点的条件是10．在一个待排序的序列中，只有很少量元素不在自己最终的正确位置上，但离他们的正确位置都不远，则使用排序方法最好。
五、构造题：（每小题5分，共25分）1．已知一棵二叉树，其中序序列DBCAFGE，后序序列DCBGFEA，构造该二叉树。
2．设哈希表长度为11，哈希函数H（K）=（K的第一字母在字母表中的序号）MOD11，若输入顺序为（D，BA，TN，M，CI，I，K，X，TA），处理冲突方法为线性探测再散列或链地址法，要求构造哈希表，并求出等概率情况下查找成功平均查找长度。
3．有一组关键字{50，52，85，22，96，17，36，55}，请用快速排序，写出第一趟排序结果。
4．已知叶子结点值2，3，5，6，9，11，构造哈夫曼树，计算其带权路径长度。
5．画出8个结点的折半判定树。
六、算法设计题：（每小题15分，共30分）（仅要求给出子程序）1．编写算法，判断带头结点的双向循环链表L是否对称。
（15分）对称是指：设各元素值a1,a2,...,an, 则有ai=an-i+1 ，即指：a1= an，a2= an-1 。
结点结构为：prior data next2．二叉排序树T用二叉链表表示，其中各元素均不相同。
（1）写出递归算法，按递减顺序打印各元素的值。
（10分）（2）写出完成上述要求的非递归算法。
（5分）《数据结构》试卷参考答案一、简答问题：（每小题4分，共16分）1．集合结构、线性结构、树形结构、网状结构2．线性结构的前驱与后继之间为一对一关系，非线性结构的前驱与后继之间通常为一对多或多对多关系。
3．解决特定问题的有限指令序列。
有限性、确定性、可行性、有0个或多个输入数据、有1个或多个输出结果。
4．堆排序。
因为一趟堆排序排定一个元素，只需进行前10趟堆排序就可以了。
其它排序方法均需进行完全排序。
二、判断正误：（每小题1分，共5分）正确在（）内打√，否则打。
1.（）2.（√）3.（√）4.（）5.（√）三、单项选择题：(每小题1分，共4分)1．C) 2．A) 3. A) 4. D)四、填空题：(每小题2分,共20分)1．97 2. n+1 3. 链域数目不同4. 哈希查找法5. 26 – 16. 11687. p->next 、s 8.(a,b) 、(c,d)9. P->next==LA 10. 直接插入五、构造题：（每小题5分，共25分）1．2．012345678910 K TA BA M D CI X TN I012345678910ASL=15/93．{36，17，22，50，96，85，52，55}4．WPL=11×2+6×2+9×2 +5×3 +2×4+3×4 =87[注]：哈夫曼树的左右子树可以互换。
5．[注]：如果求中点时采用向上取整，则二叉树的形态为左子树偏长。
六、算法设计题：（每小题15分，共30分）（仅要求给出子程序）1．[解答]：int judge(DLinkList L){p=L->next; q=L->prior;while(p!=q){ if(p->data!=q->data) return 0;if(p->next==q) return 1;p=p->next;q=q->prior;}return 1;}[注]：可以不用返回值，而用打印信息。
2．[解答]：（1）void print_1(BiTree T){if(T!=NULL){ print_1(T->RChild);printf(“%c”, T->data);print_1(T->LChild);}}（2）void Print_2（BiTree T）{ InitStack (&S);p=T;while(p!=NULL || ! IsEmpty(S)){ while (p!=NULL){ Push(&S, p);p=p->RChild;}if ( ! IsEmpty(S) ){ Pop(&S, &p);prin tf (“%c”,p -> data );p = p -> LChild;}}}数据结构辅导试题二一、简答题：（每小题3分，共15分）1.什么情况下二叉排序树的查找性能较好？什么情况下二叉排序树的查找性能最差？2.比较顺序表与单链表的优缺点。
3.请写出栈的链式存储结构的类型定义。
4.在起泡排序过程中，有的关键字在某趟排序中可能朝着与最终排序相反的方向移动，试举例说明之。
5.简述参数传递的主要方式及其特点。
二、判断正误：（每小题1分，共5分）正确在（）内打√，否则打 。
( )（1）在拓朴序列中，如果结点Vi排在结点Vj的前面，则一定存在从Vi到Vj的路径。
( )（2）在采用线性探测法处理冲突的散列表中，所有同义词在表中一定相邻。
( )（3）在一个小根堆中，具有最大值的元素一定是叶结点。
( )（4）索引顺序表的特点是块间可无序，但块内一定要有序。
( )（5）哈夫曼树中没有度为1的结点，所以必为满二叉树。
三、单项选择题：(每小题1分，共5分)1．对于只在表的首、尾进行插入操作的线性表，宜采用的存储结构为:A) 顺序表B) 用头指针表示的单循环链表C) 用尾指针表示的单循环链表D) 单链表2．假设以第一个元素为分界元素，对字符序列（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)3．下面是三个关于有向图运算的叙述：（1）求有向图结点的拓扑序列，其结果必定是唯一的（2）求两个指向结点间的最短路径，其结果必定是唯一的（3）求AOE网的关键路径，其结果必定是唯一的其中哪个（些）是正确的？A) 只有（1）B) （1）和（2）C) 都正确D) 都不正确4．若进栈序列为a, b, c，则通过入出栈操作可能得到的a, b, c的不同排列个数为:A) 4 B) 5 C) 6 D) 75. 以下关于广义表的叙述中,正确的是：A) 广义表是由0个或多个单元素或子表构成的有限序列B) 广义表至少有一个元素是子表C) 广义表不能递归定义D) 广义表不能为空表四、填空题：(每小题2分,共20分)1．一棵含有101个结点的完全二叉树存储在数组A[1..101]中, 对1≤k≤101, 若A[k]是非叶结点, 则k的最小值是: ，k的最大值是: 。
2. 设s=’YOU ARE JUDGING IT RIGHT OR WRONG’，顺序执行下列操作：SubString(sub1,s,1,8); SubString(sub2,s,20,5); StrCat(sub1,sub2); 则最后sub1的值为：。
3. 若一个算法中的语句频度之和为T(n) = 3720n+4nlogn，则算法的时间复杂度为________________ 。
4．广义表((((a),b),c),d)的表头是，表尾是。
5．已知有向图的邻接矩阵，要计算i号结点的入度，计算方法是：将累加。
6．要在一个单链表中p所指结点之后插入一个子链表，子链表第一个结点的地址为s，子链表最后一个结点的地址为t, 则应执行操作：和。
7. 用带头结点的循环链表表示的队列,若只设尾指针rear, 则队空的条件是。
8．已知二维数组A[10][20]采用行序为主方式存储，每个元素占2个存储单元,并且A[0][0]的存储地址是1024, 则A[6][18]的地址是9．在表示二叉树的二叉链表中,共有个空链域。