数据结构历年试卷.doc

江西财经大学 学年 第 学期期末考试试卷试卷代码：03265A卷 课时：96课程名称：数据结构 适用对象：信息管理与信息系统一、名词解释（每小题2分，共10分）1、 抽象数据类型 2、 排序的稳定性 3、 二叉排序树 4、 冲突 5、 哈希表二、填空题（每空1分，共14分）1、通常要表达一种数据结构，要说明 、 、 三方面。2、带头结点的双向循环链表，空链表的条件是 。3、已知一棵度为3的树有3个度为1的结点，3个度为2的结点，3个度为3的结点，则该数有 个叶子。4、有一个长度为21的有序表采用二分查找方法进行查找，共有 个元素查找长度为5。5、假设一完全二叉树共378个结点，则其中有 个叶子。6、在内部排序中，需求附加内存容量最大的是 排序。7、在长度为N的顺序表中的第i（1=inext;while ( ) pos=p; ;while (q!=NULL) if (q-data.keydata.key) ;q=q-next; if ( ) x=p-data; p-data=pos-data;pos-data=x; p=p-next; 五、设计题（共32分）每题请先用C语言描述其存储结构（有步骤分）。1、编写一算法对单链表实现就地逆置。（10分）2、编写判别给定表达式中所含括号是否匹配的算法（设表达式中只有一种小括号）。（12分）3、编写树采用孩子兄弟表示法做存储结构的统计叶子数目的算法。（10分）江西财经大学- 学年第 学期期末考试试卷试卷代码：03265B卷 课时：96课程名称：数据结构 适用对象：信息管理与信息系统一、名词解释（每小题2分，共10分）1、 空间复杂度2、 外部排序 3、 完全二叉树 4、 前缀编码 5、 散列 二、填空题（每空1分，共14分）1、衡量一个算法的好坏主要看 、 、 、 几方面。2、带头结点的双向链表，空链表的条件是 。3、已知一棵度为3的树有3个度为1的结点，2个度为2的结点，4个度为3的结点，则该树有 个叶子。4、有一个长度为24的有序表采用二分查找方法进行查找，共有 个元素查找长度为5。5、假设一完全二叉树共497个结点，则其中有 个叶子。6、在内部排序中，就平均时间而言最好的排序是 排序。7、在长度为N的顺序表中删除第i（1=idata); pop(S,p); if(!StackEmpty(S) pop(S,p); /while /PreOrder_Nonrecursive五、设计题（共32分）每题请先用C语言描述其存储结构。（有步骤分）1、 假设在长度大于1的单循环链表中，既无头结点也无头指针，S为指向链表中某个结点的指针，试编写算法删除S所指向的结点的前驱结点。（10分）2、编写二叉树采用二叉链表做存储形式的层序遍历算法。（11分）3、假设一数组中有N个数据，从1号单元开始存放，有正数也有负数，请编写一个高效算法将所有正数存放到所有负数之后。（要求排列好的数据仍存在原数组中）（11分）江西财经大学- 学年第 学期期末考试试卷试卷代码：03265C卷 课时：96课程名称：数据结构 适用对象：信息管理与信息系统一、 名词解释（每小题2分，共10分）1、 时间复杂度 2、 排序的稳定性 3、 平衡二叉树4 、哈希函数5、静态查找表二、填空题（每空1分，共14分）1、通常的数据结构有 、 、 、 四种。2、在最好和最坏情况下的时间复杂度均为O（nlgn）且稳定的排序方法是 。3、在一棵度为3的树中，度为3的结点个数为2，度为2的结点个数为1，度为1的结点个数为4，则度为0的结点个数为 。4、有一个长度为19的有序表采用二分查找方法进行查找，共有 个元素查找长度为4。5、假设一完全二叉树共768个结点，则其中有 个叶子。6、在具有N个单元的循环队列中，队满时共有 个元素。7、已知A，B，C三个结点可以构造 棵不同形态的二叉树， 棵不同形态的树。8、在关键字序列（07，12，15，18，27，32，41，92）中用折半查找92，依次和92比较的关键字个数为 个。9、若一个栈的输入序列是1，2，3.n，输出序列的第一个元素为n，则第i个输出元素是 。10、循环队列Q中，队列长度为 。三、计算题（要求写出主要计算步骤及结果。每小题6分，共36分）1、任何一棵二叉树T，采用二叉链表作为存储结构，如果其结点总数为n，则空链域E=n+1,试证明之。2、令 t=aaabcaabcaabcc,求它的next函数值。3、已知一电报中abcdefgh八个字符，他们在电报中出现的权重为0.32，0.05，0.18，0.08，0.34，0.06 ，0.27，0.15，给出一种可行的哈夫曼编码。（画出相应哈夫曼树）4、若一数据元素序列为5,12,20,31,37,40,49,53,58,67，他们的权重为6，5，8，20，15，26，11，8，7，6，试构造一棵次优查找树，并计算PH值。5、已知一二叉树中序遍历顺序为GDHBAECIF，前序遍历顺序为ABDGHCEFI，试画出该树。并写出其后序遍历和层序遍历的结果。6、 已知一数组中有10个数分别为67，20，97，16，80，10，50，62，26，72，对其进行堆排序（按升序排），请写出创建的初始堆，以及前三趟每趟排序后数组的结果。四、程序填空题（每空2分，共8分）下面的算法是用堆排序算法完成对文件中各个记录按关键字递增次序排序，仔细阅读程序并填空。假设数据从1号空间存放，0号空间做中转站使用。Typedef struct record int key; othertype other; record;void heap_sort(record r, int n) for (_; i=1; i- ) creat_heap( r,i,n); while(n0) r0=_ _;r1=rn;_=r0;_creat_heap(r,1,n) 五、设计题（共32分）每题请先用C语言描述其存储结构。（有步骤分）2、 设有一带头结点链表L，结点个数至少为3，编写算法判断该链表是否成等差数列。即设元素依次为a1,a2,a3,.an