数据结构历年试卷

江西财经大学

学年 第 学期期末考试试卷

试卷代码：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<=i<=N+1）个元素位置插入一个元素，元素的移动次数为 。

8、循环队列Q中，利用浪费一个空间的办法处理队列，则队空的条件是 ，队满的条件是 。

9、设深度为h的二叉树只有度为0和2的结点，则此类二叉树中所含的结点数至少为 。

10、3个结点可以构造 棵不同形态的二叉树， 棵不同形态的树。 三、计算题（每小题6分,共36分）

1、一棵二叉树T，如果其终端结点数为n0，度为2的结点为n2，则n0=n2+1,试证明之。 2、令 t=‘aaabaabcaabacaa’,求它的next函数值。

3、已知一电报中abcdefgh八个字符，他们在电报中出现的权重为0.25，0.13，0.18，0.34，0.41，0.16，0.15，0.10，给出一种可行的哈夫曼编码。（画出相应哈夫曼树）

4、数据元素序列为5,25,28,30,46,47,55,58,75,84，他们的权重为10，20，6，9，3，12，30，14，7，4试构造一棵次优查找树，并计算PH值。

5、已知一二叉树中序遍历顺序为CBEDFAHJKIG，后序遍历顺序为CEFDBKJIHGA，试画出该树。并写出其先序遍历和层序遍历的结果。

6、已知一数组中有10个数分别为43，45，77，96，87，25，13，42，86，17，对其进行堆排序（按升序排），请写出创建的初始堆，以及前三趟每趟排序后数组的结果。

第1页 共6页

四、程序填空题（每空2分，共8分）

以下是在单链表上实现选择排序的算法，请填空：

void selectsort(linklist head ) //head为指向头结点的指针 { linklist p,pos,q; elemtype x ;

p=head->next;

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分）

第2页 共6页

江西财经大学

- 学年第 学期期末考试试卷

试卷代码：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<=i<=N）个元素，元素的移动次数为 。 8、3个不同结点可构成 个不同形态的二叉树。

9、若有一栈S，元素S1，S2,S3,S4,S5,S6依次进栈，如果6个元素的岀栈顺序依次为：S2，S3，S4，S6，S5，S1，则栈的容量至少应该是 。 10、在单链表上难以实现的排序方法有 和堆排序。

11、在各种查找算法中，平均查找长度与结点的个数N无关的查找方法是 。 三、计算题（要求写出主要计算步骤及结果。每小题6分，共36分） 1、 证明：在有N个叶子的哈夫曼树上，其结点总数为2N-1。

2、令 t=‘abccababccaabaa’,求它的next函数值。

3、已知一电报中abcdefgh八个字符，他们在电报中出现的权重为0.41，0.19， 0.18，0.08，0.20，0.17，0.23，0.04，给出一种可行的哈夫曼编码。（画出相应哈夫曼树） 4、数据元素序列为7,15,20,31,38,69,75,80,92,94，他们的权重为12，2，9，6， 25， 20，16， 3，15，9，试构造一棵次优查找树，并计算PH值。

5、已知一二叉树层序遍历顺序为ABCDEFGHIJ，中序遍历顺序为DBGEHJACIF，试画出该树。并写出其先序遍历和后序遍历的结果。

6、已知一数组中有10个数分别为53，25，77，16，67，90，23，12，96，47，对其进行堆排序（按升序排），请写出创建的初始堆，以及前三趟每趟排序后数组的结果。

第3页 共6页

四、程序填空题（每空2分，共8分） 以下是先序遍历二叉树的非递归算法，请填空 void PreOrder_Nonrecursive(Bitree T) {

① ; Push(S,T);

while( ② ) {

while(Gettop(S,p)&&p)

{ printf(p->data); ③ } 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分）

第4页 共6页

江西财经大学

- 学年第 学期期末考试试卷

试卷代码：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，试画出该树。并写出其后序遍历和层序遍历的结果。

第5页 共6页

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(n>0)

{ r[0]=___② ____; r[1]=r[n];

_______③__=r[0]; _______④_____ creat_heap(r,1,n) } }

五、设计题（共32分）

每题请先用C语言描述其存储结构。（有步骤分）

2、 设有一带头结点链表L，结点个数至少为3，编写算法判断该链表是否成等差数列。即设元素依次为a1,a2,a3,….an,判断ai+1-ai=ai-ai-1是否成立，其中i满足2<=I<=n-1。（10分） 2、编写一算法将通常书写正确的原表达式转换为后缀表达式（逆波兰式）。（提示：可借用栈的基本运算）（12分）

3、以二叉链表做为存储结构，编写拷贝二叉树的递归算法。（10分）

第6页 共6页

本文来源：https://www.bwwdw.com/article/oxqt.html