数据结构期末考试

1、 实现数据结构的基本存储方法有：⑴ 顺序存储结构；⑵ 链接存储结构

2、 若算法中的语句执行次数之和为 T ( n )=3525 n +4 n log n ，则算法的时间复杂度是 ⑶O （ n log n ） 。

3、 假设以 S 和 X 分别表示进栈和出栈操作，则对输入序列 a , b , c , d , e 进行一系列操作 SSXSXSSXXX 之后，得到的输出序列为 ⑷ b , c , e d , a 。

4、 在串 S=\"structure\" 中，以 t 为首字符的子串有 ⑸ 个。

5、 下三角矩阵 A [ n ][ n ] 按行优先存储在一维数组 B 中，实现随机存取下三角中元素 A [ i ][ j ] 的地址公式是 ⑹i × ( i+1 ) /2+j 。（注意元素下标是从 0 开始）

6、 广义表 (( a , b ), c , d, ( e , ( f , g ))) 的表头是 ⑺ ，表尾是 ⑻ ，表的长度为 ⑼ ，表的深度为 ⑽ 。

7、 包含 n 个结点的二叉树，深度最大为 n ，深度最小为 [log 2 n ]+1 。

8、 含有 n 个结点和 e 条边的无向图的邻接矩阵中，零元素的个数为 ⒀ 。

9、 快速排序在 正序或逆序 的初始状态下，时间效率最差，其时间复杂度为 O （ n 2 ）。平均情况下快速排序的时间复杂度为 ⒂ 。

二、简答题（每小题 5 分，共 20 分）

1、 数据结构中研究的经典结构有那些？各有什么特点？

2、 栈上有那些基本运算？请写出链栈的抽象数据类型定义。（提示：先定义结点结构，再定义链栈类，在类中只给出函数声明，不需要定义函数） 2 、答：

栈上有的基本运算有：入栈、出栈、取栈顶元素、判断栈是否为空、初始化等。

template struct Node { T data; Node *next; }; template class LinkStack { public:

LinkStack ( ) {top= NULL ;} ~LinkStack ( ); void Push (T x); T Pop ( );

T GetTop ( ) {if (top!= NULL ) return top -> data;} bool Empty ( ) {top== NULL ?return 1:return 0;} private:

Node *top; // 栈顶指针即链栈的头指针 };

4、 什么叫稳定排序？请列举出三种实现稳定排序的排序算法名称

。 假定在待排序的记录序列中，存在多个具有相同键值的记录，若经过排序，这些记录的相对次序保持

不变，即在原序列中， k i = k j ，且 r i 在 r j 之前，而在排序后的序列中， r i 仍在 r j 之前，则称这种排序算法是稳定的；否则称为不稳定的

稳定的排序有：直接插入排序、起泡排序、直接选择排序和归并排序等。

5、 散列函数的设计原则是什么？有那些常用的散列函数设计方法？ 设计散列函数一般应遵循

以下原则：

⑴ 计算简单。散列函数不应该有很大的计算量，否则会降低查找效率。

⑵ 函数值（即散列地址）尽量分布均匀。函数值要尽量均匀散布在地址空间，这样才能保证存储空间的有效利用，并减少冲突。

常用的散列函数设计方法有：直接定址法、平方取中法、除留余数法、数字分析法等。

三、 假设在长度大于 1 的循环链表中，即无头结点也无头指针， S 为指向链表中某个结点的指针，试编写算法删除结点 S 的前趋结点。（ 8 分） void delete( LinkList s ) {

pre=s; q=pre à next; while (q à next!=s) {pre=q; q=q à next; } pre à next=s; free(q); }//delete

四、 已知叶子结点（ a , b , c , d , e , f ）及对应的权值（ 12, 5, 3, 20, 9, 10 ），请画出哈夫曼树并给出各叶子结点的哈夫曼编码。（ 10 分）

五、 已知有如下二叉树：（共 15 分）

(1) 画出该二叉树的二叉链表存储示意图；（ 4 分） (2) 写出前序遍历的递归算法；（ 5 分） 前序遍历的递归算法：（ 5 分） template

void BiTree::PreOrder （ BiNode *root ） {

if (root == NULL ) return; else {

输出 root -> data;

PreOrder （ root -> lchild ） ;

PreOrder （ root -> rchild ） ; }

(3) 写出前序、中序、后序遍历得到的结点序列（ 6 分） 六、 已知有向图：（共 15 分） G= （ V ， E ）

V={ a , b , c , d , e , f , g }

E={< a , b >,< a , c >,< a , d >,< b , d >,< b , e >,< c , f >,< d , f >,< e , g >,< f , g >} (1) 画出此有向图的邻接表存储结构图示；（ 5 分）

(2) 写出一个拓扑序列；（ 2 分）

a b c d e f g

(3) 假设初始时各顶点的入度已经存放在邻接表的 in 域中，请用伪代码写出拓扑排序算法。（ 8 分）

七、 已知散列函数为： H ( k )= k mod 7 ，用拉链法处理冲突，请画出依次插入 23, 14, 9, 6, 18, 30, 49, 12, 34 后的散列表，并求出检索成功的平均检索长度。（ 9 分）

AVL= （ 5*1+3*2+1*3 ） /9=14/9 （ 2 分）

八、 设有八枚硬币，分别表示为 a ， b ， c ， d ， e ， f ， g ， h ，其中有且仅有一枚硬币是伪造的，假币的重量与真币的重量不同，可能轻，也可能重。现要求以天平为工具，用最少的比较次数挑选出假币，并同时确定这枚硬币的重量比其它真币是轻还是重。写出你的判定过程或画出判定树。（ 8 分）

一、 填空题（每空 1 分，共 15 分） 1、 ⑴ 顺序存储结构；⑵ 链接存储结构 2、 ⑶ O （ n log n ） 3、 ⑷ b , c , e d , a 4、 ⑸ 12

5、 ⑹ i × ( i+1 ) /2+j

6、 ⑺ ( a , b ) ；⑻ ( c , d, ( e , ( f , g ))) ；⑼ 4 ；⑽ 3 7、 ⑾ n ；⑿ [log 2 n ]+1 8、 ⒀ n 2 - 2 e

9、 ⒁ 正序或逆序；⒂ O （ n log n ） 二、 简答题（每小题 5 分，共 20 分）

1 、答：根据数据元素之间逻辑关系的不同，数据结构分为四类：

⑴ 集合 数据元素之间就是“属于同一个集合”，除此之外，没有任何关系；

⑵ 线性结构 数据元素之间存在着一对一的线性关系；

⑶ 树形结构 数据元素之间存在着一对多的层次关系；

⑷ 图型结构 数据元素之间存在着多对多的任意关系。

2 、答：栈上有的基本运算有：入栈、出栈、取栈顶元素、判断栈是否为空、初始化等。

template

struct Node

{

T data;

Node *next;

};

template

class LinkStack

{

public:

LinkStack ( ) {top= NULL ;}

~LinkStack ( );

void Push (T x);

T Pop ( );

T GetTop ( ) {if (top!= NULL ) return top -> data;}

bool Empty ( ) {top== NULL ?return 1:return 0;}

private:

Node *top; // 栈顶指针即链栈的头指针

};

一、填空题（每空1分，共10分）

1．顺序存储结构中数据元素之间的逻辑关系是由存储位置表示的，链接存储结构中的数据元素之间的逻辑关系是由指针）表示的。

2．非空的单循环链表由头指针head指示，则其尾结点（由指针p所指）满足（ p>next=head ）。

3．n个顶点的连通图用邻接矩阵表示时，该矩阵至少有（ 2(n-1) ）个非零元素。 4．（ 栈 ）可作为实现递归函数调用的一种数据结构。

5．由权值为{3, 8, 6, 2, 5}的叶子结点生成一棵哈夫曼树，其带权路径长度为（53 ）。 6．设S=\"I_ am_ a_ teacther\"，其长度为（15 ）。

7．稀疏矩阵一般压缩存储方法有两种，分别是（ 三元组顺序表 ）和（ 十字链表 ）。 8．分块有序是指将文件划分为若干块，（ 快内 ）无序，（ 快间 ）有序。

二、判断题（你认为正确的请打对，错误的打错。每题2分，共10分） 1．线性表的顺序存储结构优于链接存储结构。

2．B—树是一种动态索引结构，它既适用于随机查找，也适用于顺序查找。 3．在线索二叉树中，任一结点均有指向其前趋和后继的线索。 4．用一维数组存储二叉树时，总是以前序遍历存储结点。

5．在索引顺序表上采用分块查找，在等概率情况下，其平均查找长度不仅与子表个数有关，而且与每一个子表中的对象个数有关。

三、单选题（请把你认为正确的答案填入括号内，每小题1分，共10分）

四、简单应用题（47分）

1 已知一个非空二叉树，中序遍历序列为CGBAHEDJFI；后序遍历序列为GBCHEJIFDA，试将这棵二叉树构造出来。若已知前序和后序遍历结果，能否构造出这棵二叉树，举例说明。（9分）

2．二维数组M中每个元素的长度是3个字节，行下标从0到7，列下标从0到9，从首地址d开始存储。若按行优先方式存储，元素M[7][5]的起始地址为多少，若按列优先方式存储，元素M[7][5]的起始地址为多少。（5分）d+225;d+141

3．如右图所示：（1）从顶点A出发，画出深度优先生成树； （2）从顶点E出发，画出广度优先生成树；

（3）根据Kruskal算法，求出它的最小生成树。（12分）

第3题图

4．如右图是一棵正在进行插入运算的平衡二叉树，关键码70的插入使它失去了平衡，按照平衡二叉树的插入方法，需要对它的结构进行调整以恢复平衡。请画出调整后的平衡二叉树。（5分）

第4题图

5．写出下列程序段的时间复杂度。（3分） (1)count=0; x=1; while (xk=k+10*i; i++; ｝

第5题图

6．设记录的关键码集合为K={15,25,26,4,5,20,3,12,2},

（1）设散列函数为H(k)= k mod 15,散列表表长为16，采用线性探测法处理冲突，试构造闭散列表； （2）写出对K进行直接插入排序的每趟排序结果。（13分） 五、阅读程序（8分）

下面伪代码是一个广度优先遍历算法，请给出该算法在下图上执行BFS（G，v1）的结果，指出其中的错误产生原因，如何修改？

void BFS(ALGraph*G , int k) { /*G是图的邻接表，k是顶点序号*/ InitQueue(&Q); /*初始化队列Q*/ EnQueue(&Q , k); /*k入队*/ while (!QueueEmpty(&Q)){

i=DeQueue(&Q); /*队头元素出队*/ visited[i]=1; /*设置访问标记*/ 访问顶点vi;

for (p=G->adjlist[i].firstedge[i];p;p=p->next) /*遍历顶点vi的相邻顶点vj（设p->adjvex=j）*/

if (!visited[p->adjvex])

EnQueue(&Q , p->adjvex); /*顶点vj的序号入队*/ } }

六、已知非空单链表第一个结点的指针为head，写一个算法，找出链表中的数据域值最大的那个结点，并将其链接到链表的最前面。8（分）

七、以二叉链表为存储结构，求二叉树的深度。（7分）

一、填空题（每空1分，共10分）

1.指针 2． p->next=head 3．2(n-1) 4．栈 5．53 6．15 7．三元组顺序表，十字链表 8．块内，块间

二、判断题（你认为正确的，请在前面的括号内打对，错误的打错。每题1分，共10分） 1．错。 2．对。 3．错。 4．错。 5．对。

三、单选题（请把你认为正确的答案填入括号内，每小题1分，共10分） 1．B 2．B 3．A 4．D 5．C 6．C 7．D 8． B 9． A 10．B 四、简单应用题（47分） 1

不能。例如：前序：ABC，后序BCA，则可以构造出如下二叉树。

2 d+225;d+141 3

4

5. Ｏ(log2n) O(1) 6

五 结果为v1,v2,v3,v4,v5,v6,v6,v6,v6

错误：当v2,v3,v4,v5出队时均执行了v6入队操作，导致v6的重复入队和出队。 修改：入队时做标记，使已经标记的顶点不重复入队。 六 void linkmax(node *head) 七 int Depth(BiNode *root) {p=head->next; { while (p) if (!root) return 0; { if (head->datadata) else { {head->data<-->p- hl= Depth(root->lchild);

>data; p=p->next;}

else p=p->next}}

hr= Depth(root ->rchild); return max(hl, hr)+1; } }

答案说明：

除了客观题外，其他试题由于解题思路的多样性，教师可以根据学生答题的实际情况，具体问题具体分析，酌情批阅。

一、填空题（每空1分，共10分） 1.（数据元素 ）是数据的基本单位，在计算机程序中通常作为一个整体进行考虑和处理。 2. 已知线性表A采用顺序存储结构，每个元素占用4个存储单元，第9个元素的地址为144，则第一个元素的地址是（112 ）。 3. 数组Q[n]用来表示一个循环队列，front为队头元素的前一个位置，rear为队尾元素的位置，计算队列中元素个数的公式为（ rear-front+n）。 4. 设有一个10阶的对称矩阵A采用压缩存储，A[0][0]为第一个元素，其存储地址为d，每个元素占1个存储单元，则元素A[8][5]的存储地址为（d+41 ）。 5. 已知广义表LS=(a，(b，c，d)，e)，用Head和Tail函数取出LS中原子b的运算是（ ）。 6. 设高度为h的二叉树上只有度为0和度为2的结点，该二叉树的结点数可能达到的最大值是（ ），最小值是（ ）。 7. 某二叉树的前序遍历序列是ABCDEFG，中序遍历序列是CBDAFGE，则其后序遍历序列是（ ）。 8. 对于一个具有n个顶点的无向图，若采用邻接矩阵存储，则该矩阵的大小是（ ）。 9. 快速排序在（ ）情况下最不利于发挥其长处。 二、选择题（每题1分，共10分） 1. 算法指的是（A ）。 A 对特定问题求解步骤的一种描述，是指令的有限序列。 B 计算机程序 C 解决问题的计算方法 D 数据处理 2. 链表不具有的特点是（A ）。 A 可随机访问任一元素 B 插入、删除不需要移动元素 C 不必事先估计存储空间 D 所需空间与线性表长度成正比 3. 设栈S和队列Q的初始状态为空，元素e1、e2、e3、e4、e5、e6依次通过栈S，一个元素出栈后即进入队列Q，若6个元素出队的顺序是e2、e4、e3、e6、e5、e1，则栈S的容量至少应该是（C ）。 A 6 B 4 C 3 D 2 4. 设二叉树有n个结点，则其深度为（D ）。 A n-1 B n C +1 D 不能确定 5. 一个高度为h的满二叉树共有n个结点，其中有m个叶子结点，则有（ D ）成立。 A n=h+m B h+m=2n C m=h-1 D n=2m-1 6. 下面关于工程计划的AOE网的叙述中，不正确的是（B ）。 A 关键活动不按期完成就会影响整个工程的完成时间 B 任何一个关键活动提前完成，那么整个工程将会提前完成 C 所有的关键活动都提前完成，那么整个工程将会提前完成 D 某些关键活动若提前完成，那么整个工程将会提前完成 7. 静态查找与动态查找的根本区别在于（B ）。 A 它们的逻辑结构不一样 B 施加在其上的操作不同 C 所包含的数据元素的类型不一样 D 存储实现不一样 8. 散列技术中的冲突指的是（D ）。 A 两个元素具有相同的序号 B 两个元素的键值不同，而其他属性相同 C 数据元素过多 D 不同键值的元素对应于相同的存储地址 9. 当待排序序列基本有序或个数较小的情况下，最佳的内部排序方法是（A 。 A 直接插入排序 B 起泡排序 C简单选择排序 D快速排序 10. 设要将序列（Q，H，C，Y，P，A，M，S，R，D，F，X）中的关键码按升序排列，（ ）是堆排序初始建堆的结果。 A（F，H，C，D，P，A，M，Q，R，S，Y，X） B（P，A，C，S，Q，D，F，X，R，H，M，Y） C（A，D，C，R，F，Q，M，S，Y，P，H，X） D（H，C，Q，P，A，M，S，R，D，F，X，Y） 三、解答下列各题（共55分） 1. 举例说明在单链表中设置头结点的作用。（8分） 为了运算方便,例如在插入和删除操作时不必对表头的情况进行特殊处理。 2. 在无回溯的模式匹配KMP算法中，关键是在匹配不成功时确定模式的滑动距离。设模式T=\"a b a a b a b c\"，求模式T在每一个位置j匹配不成功时的滑动距离next[j]。（6分） 3. 已知一棵二叉树如下图所示，画出该二叉树的顺序存储、二叉链表、三叉链表存储示意图。（8分） 4. 已知上图所示是一个无向带权图，请说明Prim算法的求解思想，并写出用Prim算法求最小生成树的过程。（10分） 5. 已知某字符串S中共有8种字符，各种字符分别出现2次、1次、4次、5次、7次、3次、4次和9次，对该字符串用[0，1]进行前缀编码，问该字符串的编码至少有多少位。（8分） 6. 将数列（24，15，38，27，121，76，130）的各元素依次插入一棵初始为空的二叉排序树中，请画出最后的结果，在这棵二叉排序树上删除值为38的结点，请画出删除后的状态。（7分） 7. 设有关键码序列(26, 25, 20, 33, 21, 24, 45, 29, 31)，用散列方法进行存储，给定散列空间为12个存储单元，请采用除留余数法设计一个散列函数，按你所设计的散列函数，画出采用线性探测法处理冲突构造的散列表。（8分） 四、算法设计题（共25分） 1. 设计算法，在一个有序单链表（从小到大排列）中插入一个元素值为x的结点，使插入后单链表仍然有序。（8分） 2. 以邻接矩阵作存储结构，设计算法实现图的广度优先遍历。（8分） 3. 给定n个记录的有序序列A[n]和m个记录的有序序列B[m]，将它们归并为一个有序序列，存放在C[m+n]中，试写出这一算法。 （9分） 一、填空题（每空1分，共10分） 1. 数据元素 2. 112 3. rear-front+n）% n 4. d+41 5. Head(Head(Tail(LS))) 6. 2h -1，2h-1 7. CDBGFEA 8. n2 9. 待排序的数据已基本有序 二、选择题（每题1分，共10分） 1.A 2.A 3.C 4.D 5.D 6.B 7.B 8.D 9.A 10.C 三、解答下列各题（共55分） 1. 【解答】为了运算方便,例如在插入和删除操作时不必对表头的情况进行特殊处理。 2. 【解答】next[1 ]=0，next[2]=1，next[3]=1，next[4]=2，next[5]=2，next[6]=3，next[7]= 4，next[8]=3 3. 【解答】 4. 【解答】按Prim算法求最小生成树的过程如下：

5. 【解答】以各字符出现的次数作为叶子结点的权值构造的哈夫曼编码树如图5-14所示。其带权路径长度=2×5+1& times;5+3×4+5×3+9×2+4×3+4× 3+7×2=98，所以，该字符串的编码长度至少为98位。

6. 【解答】二叉排序树如图所示，其平均查找长度=1+2×2+3×2+4×2=19/7

7. 【解答】 散列函数H（key）=key mod 11 散列表 四、算法设计题（共25分） 1. 【解答】 void StraightSort(Node *first) { pre=first; p=first->next; q=p->next; while (p) { while (q!=p) { while (p->datadata) { pre=p; p=p->next; } if (p!=q) { u=q->next; pre->next=q; q->next=p; q=u; } else q=q->next; } pre=first; p=first->next; } } 2. 【解答】 template void MGraph::BFSTraverse(int v) { front=rear=-1; //初始化队列,假设队列采用顺序存储且不会发生溢出 cout< while (front!=rear) { v=Q[++front]; //将队头元素出队并送到v中 for (j=0; j if (arc[v][j]==1 && visited[j]==0 ) { cout< } } } 3. 【解答】 采用二路归并排序中一次归并的思想，设三个参数i、j和k分别指向两个待归并的有序序列和最终有序序列的当前记录，初始时i、j分别指向两个有序序列的第一个记录，即i=1，j=1，k指向存放归并结果的位置，即k=1。然后，比较i和j所指记录的关键码，取出较小者作为归并结果存入k所指位置，直至两个有序序列之一的所有记录都取完，再将另一个有序序列的剩余记录顺序送到归并后的有序序列中。 void Union(int A[ ], int n, int B[ ], int n, int C[ ] ) { i=1; j=1; k=1; while (i<=n && j<=m) { if (A[i]<=B[j]) C[k++]=A[i++]; else C[k++]=B[j++]; } while (i<=n) C[k++]=A[i++]; while (j<=m) C[k++]=B[j++]; }