西北大学2014年数据结构试卷

西北大学2014年数据结构试卷一、简答问题：（每小题4分，共16分）四类数据结构线性结构与非线性结构有何差别？简述算法的定义与特性。设有1000个无序元素，仅要求找出前10个最小元素，在下列排序方法中（归并排序、基数排序、快速排序、堆排序、插入排序）哪一种方法最好，为什么？二、判断正误：（每小题1分，共5分）正确在（）内打√，否则打r。（）二叉排序树或是一棵空树，或是具有下列性质的二叉树：若它的左子树非空，则根结点的值大于其左孩子的值，若它的右子树非空，则根结点的值大于其右孩子的值。（）索引顺序表的特点是块内可无序，块间要有序。（）子串是主串中任意个连续字符组成的序列。（）线性结构只能用顺序结构存放，非线性结构只能用链表存放。（）快速排序的枢轴元素可以任意选定。三、单项选择题：(每小题1分，共4分)1．栈S最多能容纳4个元素。现有6个元素按A、B、C、D、E、F的顺序进栈,问下列哪一个序列是可能的出栈序列?A)E、D、C、B、A、FB)B、C、E、F、A、DC)C、B、E、D、A、FD)A、D、F、E、B、C2．将一棵有100个结点的完全二叉树从根这一层开始，每一层从左到右依次对结点进行编号，根结点编号为1，则编号为49的结点的左孩子的编号为：A、98 B、99 C、50 D、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）M1B）M1+M2C）M3D）M2+M3四、填空题：(每小题2分,共20分)设一哈希表表长M为100，用除留余数法构造哈希函数，即H（K）=KMODP（P<=M）,为使函数具有较好性能，P应选N个结点的二叉树采用二叉链表存放，共有空链域个数为单链表与多重链表的区别是在各种查找方法中，平均查找长度与结点个数无关的是深度为6（根层次为1）的二叉树至多有个结点。已知二维数组A[20][10]采用行序为主方式存储,每个元素占2个存储单元,并且A[10][5]的存储地址是1000,则A[18][9]的存储地址是在一个单链表中p所指结点之后插入s所指结点时,应执行s->next=和p->next=的操作.8．广义表((a,b),c,d)的表头是,表尾是9．循环单链表LA中，指针P所指结点为表尾结点的条件是10．在一个待排序的序列中，只有很少量元素不在自己最终的正确位置上，但离他们的正确位置都不远，则使用排序方法最好。五、构造题：（每小题5分，共25分）已知一棵二叉树，其中序序列DBCAFGE，后序序列DCBGFEA，构造该二叉树。设哈希表长度为11，哈希函数H（K）=（K的第一字母在字母表中的序号）MOD11，若输入顺序为（D，BA，TN，M，CI，I，K，X，TA），处理冲突方法为线性探测再散列或链地址法，要求构造哈希表，并求出等概率情况下查找成功平均查找长度。有一组关键字{50，52，85，22，96，17，36，55}，请用快速排序，写出第一趟排序结果。已知叶子结点值2，3，5，6，9，11，构造哈夫曼树，计算其带权路径长度。画出8个结点的折半判定树。六、算法设计题：（每小题15分，共30分）（仅要求给出子程序）1．编写算法，判断带头结点的双向循环链表L是否对称。（15分）对称是指：设各元素值a1,a2,...,an,则有ai=an-i+1，即指：a1=an，a2=an-1。。。。。。。结点结构为：priordatanext二叉排序树T用二叉链表表示，其中各元素均不相同。写出递归算法，按递减顺序打印各元素的值。（10分）写出完成上述要求的非递归算法。（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–1

6.1168

7.p->next

、

s

8.(a,b)

、

(c,d)9.P->next==LA

10.直接插入五、构造题：（每小题5分，共25分）1．

2．

012345678910KTABAMDCIX

TNIASL=20/9

012345678910

ASL=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．[解答]：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;}[注]：可以不用返回值，而用打印信息。2．

[解答]：（1）voidprint_1(BiTreeT){if(T!=NULL)

{print_1(T->RChild);

printf(“%c”,T->data);

print_1(T->LChild);

}}（2）void

Print_2（BiTreeT）{InitStack(&S);p=T;while(p!=NULL||!IsEmp